Re: Fwd: Question re. exponent blinding in spiped

[Colin Percival <cperciva@tarsnap.com>]

Replying here rather than directly, for the benefit of the list...

> On Thu, Apr 24, 2014 at 1:15 AM, Colin Percival <cperciva@tarsnap.com> wrote:
>> Those ensure that the two exponents being computed are in the ranges [2^256,
>> 2^257-1) and [2^257, 2^258 - 1) respectively, in order to avoid leaking any
>> information via the bit-lengths (and thus the number of modular squarings
>> needed).
> 
> Ah, thanks, that makes sense! I think you meant to use closed ranges
> there, right?

Err, yes.  Or different half-open ranges.

> (And I believe the second range should be [2^257 + 1,
> 2^258 - 1]...)

Yes, but the important thing is that the exponents are both in [2^n, 2^{n+1} )
in order to have a fixed bitlength.

> And I assume one could choose larger exponents without losing anything
> (e.g., 2^257 and 2^259), but one would be doing more extra work in
> computing the larger numbers without much gain, right?

Right.  256 bits of blinding is enough to obscure the entire exponent.

>> I don't think anyone else is using this method, since it doubles the cost.
>> The base-blinding method you describe (precompute a^(-d), then compute x^d
>> as (a * x)^d * a^(-d)) only costs two extra multiplies, and it blinds the
>> message; but it does nothing to protect the exponent.
> 
> Ah, of course that blinding method doesn't help in this case! So if
> you're the only one using this method, what do other programs that do
> Diffie-Hellman do for exponent blinding (if anything)?

Nothing, as far as I know.

-- 
Colin Percival
Security Officer Emeritus, FreeBSD | The power to serve
Founder, Tarsnap | www.tarsnap.com | Online backups for the truly paranoid