Support ConditionallySelectable for types that are not Copy

[haslersn]

This is a feature request to support the trait ConditionallySelectable for types that are not Copy.

Motivation

I have large types (e.g. polynomials of high degree) that I'd like to be conditionally selectable.

[tarcieri]

It's unclear to me what the rationale for the Copy bound even is.

Looking at how subtle uses it, AFAICT it's only used by conditional_swap. Questions of breaking changes aside, it looks like the bound could potentially be moved to that method only.

[rozbb]

Copy can also appear in conditional_select, like in this code that implements ConditionallySelectable for all fixed-size arrays.

If I understand correctly, Henry's stated reasoning is that allowing Clone types gives people too much leeway in their impls, allowing them to possibly do a clone() whose timing leaks bits about the data.

I'm not opposed to this reasoning. I just wonder if there's an escape hatch we could make that allows you to do this if you're very careful.

[tarcieri]

Copy can also appear in conditional_select, like in this code that implements ConditionallySelectable for all fixed-size arrays.

The Copy bound could potentially be moved to that impl, e.g.

impl<T, const N: usize> ConditionallySelectable for [T; N]
where T: ConditionallySelectable + Copy

If I understand correctly, Henry's #56 is that allowing Clone types gives people too much leeway in their impls, allowing them to possibly do a clone() whose timing leaks bits about the data.

That is a reasonable concern. Copy should always be constant-time, whereas Clone admits a sharp edge.

However, I do also sympathize with the concern that it may be unwise to impl Copy on very large types. Personally I tend to use the size of an x86 cache line (64-bytes) as my personal rule of thumb for a boundary after which one should consider if types are too large to impl Copy.

[rozbb]

Agreed. A not-great idea: make a trait SafeConditionallySelectable: Copy and then make trait ConditionallySelectable unconstrainted. That way people can still write generics relying on ConditionallySelectable. And it'd be the case that SafeConditionallySelectable is always ConditionallySelectable. Downsides: this changes the meanings of pre-existing terms, doesn't remove the footgun, and requires a major version release.

[tarcieri]

Another option besides splitting the ConditionallySelectable trait would be adding a marker trait like:

pub trait CtClone: Clone {}

impl<T: Copy> CtClone for T {}

...and then changing ConditionallySelectable to be bound on CtClone.

CtClone would be a marker trait which means "I assert my Clone impl is constant-time".

[rozbb]

Oh, that's pretty nice. I'd be fine with that.

[sonti-lurker]

I think a similar argument applies to CtOption::map (and and_then, or_else).
The code has a comment:

    /// This operates in constant time, because the provided closure
    /// is always called.

which is obviously only true if the called closure runs in constant-time but there is nothing enforcing that.

[tarcieri]

A big drawback of the Copy bound is it makes it impossible to implement ConditionallySelectable for heap allocated types, e.g. a heap-backed big integer.

[tarcieri]

However, changing it seems like a breaking change due to removing the supertrait bound on Copy.

Currently anything that's ConditionallySelectable can be assumed to be Copy via that supertrait bound. Removing it might require changing bounds in existing code to ConditionallySelectable + Copy.

It's the kind of thing that makes me wish we had something like Crater to see if it would break any real-world code. I think there's a real chance it might.

[tarcieri]

It seems like the only way to support non-Copy types without breaking changes would be to define a new trait and use a blanket impl for backwards compatibility. Something like:

pub trait ConstantTimeClone: Clone {}

impl<T: Copy> ConstantTimeClone for T {}

pub trait ConstantTimeSelect: ConstantTimeClone {
    fn ct_select(a: &Self, b: &Self, choice: Choice) -> Self;

    [...]
}

impl<T: ConditionallySelectable> ConstantTimeSelect for T {
    [...]
}

...then ConditionallySelectable could potentially be deprecated.

[tarcieri]

I've been attempting to make use of subtle with heap-allocated BoxedInteger/BoxedResidue types, with the goal of using those to implement the rsa and dsa crates.

I can attest the Copy bound becomes a major impediment in these cases, because without ConditionallySelectable the CtOption combinators don't work, which IMO is one of subtle's best features for writing constant-time code.

I can try to open a PR with what I've outlined above, which in theory should be a backwards compatible change as current ConditionallySelectable users can leverage the new trait via the blanket impl (though it should likely be deprecated).

CtOption will need to be changed to use the new trait, which again shouldn't be breaking due to the blanket impl. #63 will also likely need to be addressed for my use cases to work, as we need to ensure fixed-but-dynamic precisions are consistent throughout, and Default will return a value with a number of limbs smaller than e.g. an RSA modulus.