Re: [Cfrg] RGLC on draft-irtf-cfrg-spake2-13 (rejection sampling vs. modulo reduction)

[Annie Yousar <[e-mail]>]

Hi Björn, Watson,
there are *two* common solutions for "re-uniforming" from [0,2^N-1] to
[0,q-1], where the bitlength of q is n, and N>n (usually N=n+64 or
greater).

Pick r randomly and uniformly from [0,2^N-1] and
1. compute r mod q, or
2. compute r*q div 2^N

If you put all the 2^N values in to q boxes with one of these methods
you get all boxes filled with 2^64 or 2^64+1 values. Hardly you will see
here the differences.
The second method uses one multiplication (shift is not counted) instead
of modulo operation and may be a bit faster and easier to implement than
rejection sampling.

/Ann.




Am 2020-10-19 um 11:26 schrieb Björn Haase:
> Hi Watson,
> 
>> On 19.10. 2020 Watson Ladd wrote:
> 
>> Thank you! I will add such a warning to the security section and
>> advise the use of either reduction of a double length string or
>> rejection sampling.
> 
> Indeed you are right. With my mind focused on "constant time"
> implementation all the time, I
> did discard the cheap option of the rejection sampling too early. In
> fact, we won't
> leak any useful information with rejection sampling even if it's not
> constant time.
> 
> On the other hand there is a non-negligible risk of leakage when
> reducing a double-length string (in addition to the code bloat).
> 
> Therefore I'd advocate to recommend rejection sampling only and not
> double-length-string reduction
> (and this should also be the way to do for CPace on the
> short-Weierstrass curves).
> 
> Still there might worth pointing to the risk of a possible variable-time
> issue when re-using code from libraries that were written for
> conventional DH key exchange. I have seen implementations that just set
> the top-most bit of the secret scalar (loosing half a bit of security)
> during the sampling process in order to make sure that the windowed
> scalar multiplication algorithm runs in constant time.
> 
> If we have such a scalar multiplication algorithm with a uniformly
> sampled scalar, there is some risk
> of getting a variable execution time behaviour...
> 
> Maybe some note in the security section in the form:
> 
> "Some scalar multiplication algorithms designed for conventional ECDH
> key exchange might not run in constant time when using uniformly sampled
> secret scalars. Implementations should verify this aspect."
> 
> could be worthwile.
> 
> Yours,
> 
> Björn
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>