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 <[email protected]> Date: Thu, Apr 24, 2014 at 1:05 AM To: [email protected] 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 <[email protected]> Date: Thu, Apr 24, 2014 at 1:15 AM To: Frederick Akalin <[email protected]> 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 <[email protected]> Date: Thu, Apr 24, 2014 at 2:21 AM To: Colin Percival <[email protected]> On Thu, Apr 24, 2014 at 1:15 AM, Colin Percival <[email protected]> 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
