subtle icon indicating copy to clipboard operation
subtle copied to clipboard

implement lexicographical ordering for slices of arbitrary types

Open conduition opened this issue 2 years ago • 0 comments
trafficstars

This generalizes the implementation of ConstantTimeEq for [T] to also support ConstantTimeGreater and ConstantTimeLess. I haven't touched the implementation of ConstantTimeEq for [T] as the standalone implementation is more efficient than the multi-purpose code i've added here. However in principle the execution of the code is very similar.

I added a utility function ct_slice_lex_cmp(x, y) which produces a cmp::Ordering in time proportional to min(x.len(), y.len()). I chose this approach rather than implementing ConstantTimeGreater directly, because it allows us to also implement ConstantTimeLess without invoking both ct_eq and ct_gt, which would perform up to twice as many loop iterations over both slices.

Reasoning

I wrote this PR because I found a need in my project for constant time comparison on fixed-size arrays of bytes (secret data), beyond simple equality checking. Specifically, I needed to check if an elliptic curve secret scalar value represented as [u8; 32] was larger than the curve order (some fixed [u8; 32] constant).

In non-constant time operations, one could simply do x >= y. I wrote ct_slice_lex_cmp to fulfill this duty and realized it might be handy upstream here.

PS those formatting changes in test/mod.rs were automatically applied by cargo fmt. I can revert commit ca90794 if you'd prefer to keep that code formatted as it was before.

conduition avatar Oct 18 '23 02:10 conduition