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

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 5 Jul 2017 14:38:18 -0400

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.

Anyone got code for adding points in compressed Montgomery?

Thoughts?

---

From: Taylor R Campbell <[email-masked]>
Date: Wed, 5 Jul 2017 21:03:20 +0000

> Date: Wed, 5 Jul 2017 14:38:18 -0400
> From: Phillip Hallam-Baker <[email-masked]>
> 

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.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 5 Jul 2017 17:56:16 -0400

> use constant-time code for both Edwards and Montgomery arithmetic.

'​Just use ​finely ground unicorn powder'.

I don't think the constant time code survives modern optimizers or hardware
accelerations nearly as robustly as you imagine. I would much rather go
with an approach that does not depend on the vagaries of implementation.

​The main reason not to do this was the Kocher patents on blinding. But
those are expiring soon.​

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 5 Jul 2017 15:01:11 -0700

On Wed, Jul 5, 2017 at 11:38 AM, Phillip Hallam-Baker <[email-masked]

> into two parts, perform two separate multiplications with each part and add

I'm not sure why you're talking about Montgomery vs Edwards here. This is a
Flush+Reload attack similar to:

- "Just A Little Bit": https://eprint.iacr.org/2014/161.pdf
- "Just A Little Bit More": https://eprint.iacr.org/2014/434.pdf
- Cachebleed: https://eprint.iacr.org/2016/224.pdf

If there was a conclusion I drew from these attacks, it's the need to
include random values, as the security proofs say we should do.

I will note that BoringSSL was not vulnerable to Cachebleed because they
continued to use random blinding in addition to Intel's allegedly "constant
time" RSA code. Though many are quick to dismiss it, random blinding seems
to provide defenses against a multitude of attacks, not just cache timing
but DPA as well.

-- 
Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 5 Jul 2017 19:16:24 -0400

On Wed, Jul 5, 2017 at 6:01 PM, Tony Arcieri <[email-masked]> wrote:

> On Wed, Jul 5, 2017 at 11:38 AM, Phillip Hallam-Baker <
> [email-masked]> wrote:
>
>> 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'.
>>
>
> I'm not sure why you're talking about Montgomery vs Edwards here. This is
> a Flush+Reload attack similar to:
>

​You can blind in either. But if you are going to blind then a lot of the
advantages of Montgomery start to collapse. because you have to do that add
stage.

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 5 Jul 2017 16:29:00 -0700

> advantages of Montgomery start to collapse. because you have to do that add

Ephemeral Montgomery keys, of the sort used by TLS ECDHE, are another
example of a use case which (if proper deployment procedures are followed)
shouldn't be vulnerable to this sort of attack.

I would agree that for long-term static keys, for this and other reasons
perhaps Edwards would be preferable.

-- 
Tony Arcieri

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 5 Jul 2017 17:07:01 -0700

> advantages of Montgomery start to collapse. because you have to do that add

What if you blinded kP with r using:

    r*([k r^-1]*P)

which only requires inversions?

-- 
Tony Arcieri

---

From: Samuel Neves <[email-masked]>
Date: Thu, 6 Jul 2017 01:35:29 +0100

Coron's countermeasures [1, §5]---the first and third one, in
particular---work well with Montgomery coordinates.

[1] http://www.jscoron.fr/publications/dpaecc.pdf

On Thu, Jul 6, 2017 at 1:07 AM, Tony Arcieri <[email-masked]> wrote:
>> You can blind in either. But if you are going to blind then a lot of the
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: David Jacobson <[email-masked]>
Date: Tue, 11 Jul 2017 19:18:18 -0700

>> which only requires inversions?

I think you miscounted the cost.   You need an extra inversion and an 
extra point multiplication.

And even then the security is dubious.  The original motivation 
apparently was that you are worried that computing kP will leak k.  
Well, the proposal first leaks k r^-1, then it leaks r.  The attacker 
can just multiply the two leaked quantities and she has k.

    --David Jacobson

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 12 Jul 2017 12:43:30 +0000

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of David Jacobson
> Sent: Tuesday, July 11, 2017 10:18 PM
> To: Samuel Neves; [email-masked]
> Subject: Re: [Cfrg] Side channel attack and Edwards curves...
> 
> >>> You can blind in either. But if you are going to blind then a lot of
> >>> the advantages of Montgomery start to collapse. because you have to
> >>> do that add stage.
> >>
> And even then the security is dubious.  The original motivation apparently
> was that you are worried that computing kP will leak k.
> Well, the proposal first leaks k r^-1, then it leaks r.  The attacker can just
> multiply the two leaked quantities and she has k.

I would disagree with this security assessment; side channel attacks generally don't leak the entire value in one run; they leak probabilistic information about the secret (and the attacker will typically use multiple runs using the same secret to recover sufficient information to actually do the recovery).  In this case, 'r' is selected randomly each time, and hence any specific multiplier that will be used will be uncorrelated with the secret and any other multiplier (except that the multiplication of two adjacent ones will result in the actual secret; partial leakage of bits of the multiplier isn't particularly useful to recover the modular product).  Hence, this actually does provide some level of protection, assuming that the attacker cannot obtain sufficient information from a single run (and if you start assuming that, you'd need to start looking into white-box crypto solutions).

Is this enough protection to be worth the cost?  That's a question I won't get into...