Fwd: Question re. exponent blinding in spiped

[Frederick Akalin <akalin@gmail.com>]

Hey all,

I e-mailed Colin a question, but I just realized there's no reason why
it couldn't have been sent to this list. Maybe someone else is
interested in the discussion and can save Colin the trouble of
answering my follow-up questions!

-- Fred

Forwarded conversation
Subject: Question re. exponent blinding in spiped
------------------------

From: Frederick Akalin <akalin@gmail.com>
Date: Thu, Apr 24, 2014 at 1:05 AM
To: cperciva@tarsnap.com


Dear Colin,

I was puzzling over your implementation of blinded mod-exp in
crypto_dh.c in libcperciva/spiped. In particular, I notice you add
2^258 to the DH private integers, and you also add 2^256 to the
randomly-generated blinding exponent. I'm guessing that omitting these
two additions would make the blinding less effective somehow, but I
can't figure out why.

Searching on the internet, I couldn't find any explanations -- all the
discussions of blinding involve different mechanisms, e.g. multiplying
by some suitable random x before doing the exponentiation, and then
multiplying by suitable y afterwards. The closest I could find was a
post by you https://news.ycombinator.com/item?id=240692 linked from
http://seb.dbzteam.org/crypto/side-channel-countermeasures.html.en .

If there's a canonical source for your blinding method, I'd appreciate
a pointer to it! If this is an original method, I'd appreciate an
explanation.

Thanks! :)

-- Fred

----------
From: Colin Percival <cperciva@tarsnap.com>
Date: Thu, Apr 24, 2014 at 1:15 AM
To: Frederick Akalin <akalin@gmail.com>


Hi Frederick,

On 04/24/14 01:05, Frederick Akalin wrote:
> I was puzzling over your implementation of blinded mod-exp in crypto_dh.c in
> libcperciva/spiped. In particular, I notice you add 2^258 to the DH private
> integers, and you also add 2^256 to the randomly-generated blinding exponent.
> I'm guessing that omitting these two additions would make the blinding less
> effective somehow, but I can't figure out why.

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).

> Searching on the internet, I couldn't find any explanations -- all the
> discussions of blinding involve different mechanisms, e.g. multiplying by some
> suitable random x before doing the exponentiation, and then multiplying by
> suitable y afterwards. The closest I could find was a post by you
> https://news.ycombinator.com/item?id=240692 linked
> from http://seb.dbzteam.org/crypto/side-channel-countermeasures.html.en .
>
> If there's a canonical source for your blinding method, I'd appreciate a pointer
> to it! If this is an original method, I'd appreciate an explanation.

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.

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


----------
From: Frederick Akalin <akalin@gmail.com>
Date: Thu, Apr 24, 2014 at 2:21 AM
To: Colin Percival <cperciva@tarsnap.com>


On Thu, Apr 24, 2014 at 1:15 AM, Colin Percival <cperciva@tarsnap.com> wrote:
>
> Hi Frederick,
>
>
> 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? (And I believe the second range should be [2^257 + 1,
2^258 - 1]...)

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?

>
> 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)?

-- Fred