How to check for "less than"?

[dignifiedquire]

I am trying to implement check for <=, but as far as I can tell I can only check for equality with this crate. Is this something that could be added here?

[isislovecruft]

Hi @dignifiedquire! Out of curiosity, what type(s) did you want to be able to compare, and for what algorithm?

[dignifiedquire]

I am working on an RSA implementation in rust, based on the one found in the stdlib of Go.

My current rust version is here: https://github.com/dignifiedquire/rust-rsa/blob/master/src/pkcs1v15.rs#L205-L211 and the go version is here: https://github.com/golang/go/blob/master/src/crypto/rsa/pkcs1v15.go#L171

[JeremyRubin]

Is there any point in not providing a '<' subtle trait for a couple basic types (e.g., u64)? Would be happy to submit a patch if it would be accepted.

Is the obvious implementation ((a<b) as u8).into() not viable?

The nice thing is we can then also provide a constant time 'compare_and_swap'. I use this currently for my constant time (for given N) sorting crate https://github.com/JeremyRubin/const-sort I'm working on.

fn compare_and_swap<T, F>(v: &mut T, s: &mut T, cmp: &F)
where
    F: Fn(&T, &T) -> subtle::Choice,
    T: subtle::ConditionallySwappable,
{
    let choice: subtle::Choice = cmp(&v, &s);
    v.conditional_swap(s, choice);
}
// With Constant Compare
fn compare_and_swap<T, F>(v: &mut T, s: &mut T)
where
    T: subtle::ConditionallySwappable + sublte::ConstantCompare,
{
    v.conditional_swap(s, v.ct_cmp(s));
}

// With Constant Ordering
fn compare_and_swap<T, F>(v: &mut T, s: &mut T)
where
    T: subtle::ConstantSort
{
    v.ct_order(s);
}

The nice thing about providing the compare_and_swap API is that it can be implemented as

let mask = -(((x<y) as u8).into().unwrap_u8() as to_signed_int!($t)) as $t;
x ^= y & mask
y ^= x & mask
x ^= y &mask

Which should be slightly better performance wise (if it's safe?).

[isislovecruft]

@JeremyRubin

Is the obvious implementation ((a<b) as u8).into() not viable?

It's a bit trickier.. on some architectures (a < b) requires a branch instruction. I believe the standard CT implementation for testing a<=b depends on signed integer arithmetic and non-negativity of a and b and usually goes like:

((to_signed_int!(a) - to_signed_int!(b) - 1) >> ($bitwidth - 1)) & 1

where $bitwidth in this case would be e.g. 16 for u16, etc.

[JeremyRubin]

The link you shared seems to be for computing min as a<b ? a:b, not just a<b. Are you sure there are processors where a<b requires a branch?

[pornin]

@JeremyRubin It's complicated. In many architectures, the comparison uses a "cmp" opcode which stores its result in a dedicated flags register. Then the problem becomes one of getting the right flags into a normal integer register. On x86 there is are SETcc opcodes, since the 80386 -- on a 80286, a conditional jump would have been needed. On (modern) ARMv7 systems (e.g. ARM Cortex M4), the "normal" way is to use conditional execution (IT prefix) but it's anyone's guess whether conditional execution is CT, and/or will be in future processors (also, on ARMv8, multi-instruction IT is deprecated). Conditional execution is not available on the low-end systems (e.g. ARM Cortex M0+) where a conditional jump is typically used. The jump can be avoided in some specific cases, e.g. when comparing unsigned integers, because the result is then in the carry flag, and the carry flag can be retrieved with an ADC or SBB opcode (add-with-carry or subtract-with-borrow). However, other flags (e.g. for signed comparisons) are not so easily obtained.

The 80286 is an old remnant from the musically awesome but technologically archaic 1980s. However, the ARM Cortex M0+ is a very much alive, popular processor, known for its compactness and low power consumption, and used in many small embedded systems.

You can do a CT comparison on unsigned types without resorting to signed types. For instance, for 32-bit unsigned values, you can do something like this:

z = y - x;
return (z ^ ((x ^ y) & (x ^ z))) >> 31;

(I am using C notation here, forgive me.)

I wrote a C library which is full of such things, you can see it here. See in particular the contents of the inc/cttk.h, which has inline functions for all comparisons of signed and unsigned integer types (32 and 64 bits).

[hdevalence]

Hi all, there's a lot of good information in this issue, but I'm going to close it for now because there's no current or planned PR to go with it. (There could always be a new issue referencing this one later).