Re: [Cfrg] Side channel attack and Edwards curves...

[Taylor R Campbell <[e-mail]>]

> Date: Wed, 5 Jul 2017 14:38:18 -0400
> From: Phillip Hallam-Baker <[e-mail]>
> 
> http://thehackernews.com/2017/07/gnupg-libgcrypt-rsa-encryption.html?m=1
> 
> Just another side channel attack and not something that bothers me writing
> reference code. But have we maybe put our eggs in the Montgomery ladder
> basket when maybe we should have gone for 'randomly split the private key
> into two parts, perform two separate multiplications with each part and add
> the result'.
> 
> We can play the blinding game in Edwards or Montgomery but it is easier in
> Edwards.

You can always convert from Montgomery x to Edwards (x, y) and back
without losing anything and costing only one field element inversion;
see XEdDSA <https://whispersystems.org/docs/specifications/xeddsa/>
for something similar.

But there is no reason to flail around with blinding when you can just
use constant-time code for both Edwards and Montgomery arithmetic.

You can even do RSA in constant time, but it's hard if you naively
start with a generic bignum library that automatically normalizes away
high-order zeros for in-memory representations of secret integers.

Unfortunately, both OpenSSL and libgcrypt did just that, and generally
made basic mistakes for writing constant-time code in C.  Not even
anything interesting, like code that just happens to be `optimized' by
a fancy compiler into variable-time -- they just have unnecessary
explicit branches and array indices that are dependent on secrets.

I wrote some details on and recommendations for libgcrypt a while
back:

https://lists.gnupg.org/pipermail/gcrypt-devel/2015-November/003618.html

The easy bugs I observed in twisted Edwards scalarmult were fixed
immediately; the harder bugs about generic bignum arithmetic were not
fixed when I last checked.