Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support ConditionallySelectable for types that are not Copy #94

Open
haslersn opened this issue Jul 21, 2022 · 12 comments
Open

Support ConditionallySelectable for types that are not Copy #94

haslersn opened this issue Jul 21, 2022 · 12 comments

Comments

@haslersn
Copy link

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
Copy link
Contributor

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 link

rozbb commented Oct 11, 2022

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 link
Contributor

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
Copy link

rozbb commented Oct 11, 2022

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
Copy link
Contributor

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
Copy link

rozbb commented Oct 11, 2022

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

@sonti-lurker
Copy link

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

tarcieri commented Apr 27, 2023

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 added a commit to RustCrypto/crypto-bigint that referenced this issue Nov 27, 2023
This is an inherent function with the same type signature as
`subtle::ConditionallySelectable::conditional_select`, however we can't
impl the upstream trait because it has a `Copy` bound.

See dalek-cryptography/subtle#94.
tarcieri added a commit to RustCrypto/crypto-bigint that referenced this issue Nov 27, 2023
This is an inherent function with the same type signature as
`subtle::ConditionallySelectable::conditional_select`, however we can't
impl the upstream trait because it has a `Copy` bound.

See dalek-cryptography/subtle#94.
@tarcieri
Copy link
Contributor

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.

tarcieri added a commit to RustCrypto/crypto-bigint that referenced this issue Nov 29, 2023
Unfortunately `BoxedUint` can't impl `subtle::ConditionallySelectable`
due to a supertrait bound on `Copy`. See dalek-cryptography/subtle#94

This bound is required by `CtOption::map` and `CtOption::and_then` which
are important for writing constant-time code.

As a workaround which makes it still possible to leverate `CtOption`,
this adds special `BoxedUint`-specialized combinators that are able to
work around this issue by generating a placeholder (zero) value to pass
to the provided callbacks in the event `CtOption` is none.

This requires branching on the output of `CtOption` (which is
unavoidable without an upstream fix in `subtle` itself), but still
ensures that the provided callback function is called with a `BoxedUint`
of a matching number of limbs regardless of whether the `CtOption` is
some or none, which is the best we can do for now (and really quite
close to what `subtle` is doing under the hood anyway).
tarcieri added a commit to RustCrypto/crypto-bigint that referenced this issue Nov 29, 2023
Unfortunately `BoxedUint` can't impl `subtle::ConditionallySelectable`
due to a supertrait bound on `Copy`. See dalek-cryptography/subtle#94

This bound is required by `CtOption::map` and `CtOption::and_then` which
are important for writing constant-time code.

As a workaround which makes it still possible to leverate `CtOption`,
this adds special `BoxedUint`-specialized combinators that are able to
work around this issue by generating a placeholder (zero) value to pass
to the provided callbacks in the event `CtOption` is none.

This requires branching on the output of `CtOption` (which is
unavoidable without an upstream fix in `subtle` itself), but still
ensures that the provided callback function is called with a `BoxedUint`
of a matching number of limbs regardless of whether the `CtOption` is
some or none, which is the best we can do for now (and really quite
close to what `subtle` is doing under the hood anyway).
tarcieri added a commit to tarcieri/subtle that referenced this issue Nov 29, 2023
`ConstantTimeSelect` is intended as a replacement to
`ConditionallySelectable`, which is preserved but deprecated. It
replaces the previous `Copy` bound with a bound on a new
`ConstantTimeClone` marker trait, which allows the trait to be impl'd
for heap-allocated types.

No existing impls of `ConditionallySelectable` have been removed,
however a blanket impl of `ConstantTimeSelect` for
`T: ConditionallySelectable` has been added, allowing the two traits to
interoperate and for `ConstantTimeSelect` to work on all types which
currently impl `ConditionallySelectable`.

`ConstantTimeClone` likewise has a blanket impl for all types which impl
`Copy`.

`CtOption`'s combinator methods have been changed to bound on
`ConstantTimeSelect` which unlocks using them with heap-allocated types,
which otherwise is a major limitation. In theory these changes are all
backwards compatible due to the blanket impl, which should allow all
types which previously worked to continue to do so.

Closes dalek-cryptography#63, dalek-cryptography#94
@tarcieri
Copy link
Contributor

tarcieri commented Nov 29, 2023

I went ahead and impl'd my aforementioned ConstantTimeSelect trait idea here: #118

tarcieri added a commit to tarcieri/subtle that referenced this issue Nov 29, 2023
`ConstantTimeSelect` is intended as a replacement to
`ConditionallySelectable`, which is preserved but deprecated. It
replaces the previous `Copy` bound with a bound on a new
`ConstantTimeClone` marker trait, which allows the trait to be impl'd
for heap-allocated types.

No existing impls of `ConditionallySelectable` have been removed,
however a blanket impl of `ConstantTimeSelect` for
`T: ConditionallySelectable` has been added, allowing the two traits to
interoperate and for `ConstantTimeSelect` to work on all types which
currently impl `ConditionallySelectable`.

`ConstantTimeClone` likewise has a blanket impl for all types which impl
`Copy`.

`CtOption`'s combinator methods have been changed to bound on
`ConstantTimeSelect` which unlocks using them with heap-allocated types,
which otherwise is a major limitation. In theory these changes are all
backwards compatible due to the blanket impl, which should allow all
types which previously worked to continue to do so.

Closes dalek-cryptography#63, dalek-cryptography#94
tarcieri added a commit to tarcieri/subtle that referenced this issue Aug 3, 2024
This commit contains a minimal set of proposed breaking changes, as an
alternative to trying to make additive changes which may be "subtly"
breaking:

- Add `ConstantTimeClone` trait and use it as
  `ConditionallySelectable`'s supertrait bound (alternative to dalek-cryptography#118):
  this makes it possible to implement `ConditionallySelectable` on
  heap-allocated types (fixes dalek-cryptography#94)
- Remove `Default` bound on `CtOption::map` and `CtOption::and_then`:
  allows using these methods with types that don't impl `Default` and
  avoids potential timing sidechannels if there might be timing
  variability in `Default` types (fixes dalek-cryptography#63)
tarcieri added a commit to tarcieri/subtle that referenced this issue Aug 3, 2024
To resolve dalek-cryptography#94, removes the `Copy` supertrait bound on
`ConditionallySelectable`, replacing it with `Sized` instead.

It turns out the bound is only used in the default implementation of
`ConditionallySelectable::conditional_swap`, and is easy to replace by
slightly changing that default implementation.

Removing this supertrait bound is arguably a breaking change since it
means types which impl `ConditionallySelectable` can no longer be
assumed to be `Copy`, so also bumps the version to `3.0.0-pre`.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants