Help with one's-complement add method generic on uN


#1

I’m going nuts trying to get a simple trait with a default generic implementation to compile. I’ve tried everything I could think of, or found hints for online, and I’m out of ideas. I’ve tried many ways to include a use clause for generic wrapping_add on integers, all of which have been unsuccessful. I’ve tried adding turbofish everywhere imaginable, to no avail. Is it possible to implement this generic trait in Rust? If so, what is best-practice code? TIA

Here’s a playground link.


#2

Not sure I fully understand, but don’t you need to put those bound on Self rather than T? Judging by line 19 probably on both… didn’t solve all problems in my tried, but removed a fair but of errors.

(e) This is as far as I got. Needs nightly for that u32::From<bool>. The problem though is expressing the zero…


#3

I’m not entirely sure what design you’re going for (what’s the T for? Do you want to allow the type implementing the trait to work against other Ts?), but here is a way.


#4

Interesting. Thanks.

I originally had Copy among the trait requirements on T, but thought that Integer would subsume that need. Your version does compile. So now I just need to convert the conditional branch back to a computed carry-out so that the function will not be susceptible to timing-side-channel attacks, because it’s intended use is in a crypto algorithm.


#5

You need to be careful because compiler can rearrange (ie optimize) your code to make it timing dependent. This is a general problem with crypto and why a lot of it is done in raw assembly as far as I know.


#6

Which is how the core of this algorithm is actually implemented, at the register level in C. I’ve been building an API ecosystem around the underlying algorithm as a means of learning Rust. I only need the u32 version of this particular function, but thought that others might have a use for one’s-complement add and subtract, so decided to try my hand at a generic trait impl, which is where I foundered.


#7

I see. Well, for the Rust version you have close to zero chance of ensuring timing-free implementation :slight_smile:.

You won’t be able to use as Self to do the bool cast - casts aren’t overloadable. Instead, you can create your own trait that does the conversion, like this. But, this has branching as well.


#8

Have you looked at the subtle crate written by the Tor contributors? They’ve done their best to stop the compiler from introducing timing-dependent branches. The subtle Choice type and either of its ConditionallyAssignable or ConditionallySwappable traits meet my needs. As their README points out

The nightly feature enables the use of an optimization barrier to protect the Choice type. Using the nightly feature is recommended for security.


#9

Actually, a timing side-channel leak on the one’s-complement add would not seriously impact the cipher I’m implementing in Rust; all that could be determined is whether two quasi-random inputs summed to ≥ 232. That would disclose that the resultant sum was not 0xffff_ffff, which is not much, particularly since the summation result is used only once before the inputs change.

A much more severe side-channel leak exists in the hardware implementation of the integer multiply primitive on many processors, including ARM and Power. For those architectures, when one of the multiplicands has low Hamming weight the hardware uses a simplified algorithm, thus providing observable timing variances. Fortunately that side-channel leak provides no useful attack against the cipher I’m implementing in Rust, even though it uses a 32x32 -> 64 multiply.

Edits: Deleted incorrect conclusion. 0xffff_ffff is a one’s-complement minus zero, which can be added to any value other than plus zero without changing the value binary bit pattern (due to the resulting carry-out and wrap-around carry-in).


#10

I’ve not heard of it before - thanks for mentioning it. A quick glance at their readme suggests they use inline asm as a compiler barrier, and hence the nightly requirement (which likely will stick around for quite a while).