Subject: [saag] RFC 7748, Section 6.1, and the "all 0's check"

From: Jeffrey Walton <[email-masked]>
Date: Thu, 18 Jan 2018 12:51:31 -0500

Hi Everyone,

RFC 7748 is Elliptic Curves for Security
(https://tools.ietf.org/html/rfc7748). Section 6.1 states:

   ...
   The check for the all-zero value results from the fact that the
   X25519 function produces that value if it operates on an input
   corresponding to a point with small order, where the order divides
   the cofactor of the curve (see Section 7). ...

I believe the all 0's check is too late. By the time the result is
available the multiplication has been performed and the leak has
already been witnessed.

It looks like libsodium is using a blacklist method to screen-out
low-order elements that lead to an all 0's shared secret at
https://github.com/jedisct1/libsodium/blob/master/src/libsodium/crypto_scalarmult/curve25519/ref10/x25519_ref10.c

Jeff

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 18 Jan 2018 14:46:14 -0500

> On Jan 18, 2018, at 12:51 PM, Jeffrey Walton <[email-masked]> wrote:
> 

What "leak" did you have in mind?  IIRC, the check for all 0's is intended
to ensure "contributory" key-agreement, it is not any sort of side-channel
counter-measure.

-- 
	Viktor.

---

From: Jeffrey Walton <[email-masked]>
Date: Thu, 18 Jan 2018 15:00:17 -0500

> to ensure "contributory" key-agreement, it is not any sort of side-channel

"May the Fourth Be With You: A Microarchitectural Side Channel Attack
on Several Real-World Applications of Curve25519",
https://eprint.iacr.org/2017/806.pdf. Section 1.1 (p.3):

    ... Even when countermeasures against low order elements and
    small subgroup attacks exist, they often do not prevent all
    side-channel attacks. For example, RFC 7748 [53] recommends
    “ORing all the bytes (of the output) together and checking
    whether the result is zero, as this eliminates standard
    side-channels in software implementations.” One reason that
    this countermeasure does not work against side-channel attacks
    that exploit low-order elements is that it is enacted after the
    scalar-by-point multiplication has been performed, when the
    leakage is already obtained by the adversary.

Jeff

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 18 Jan 2018 15:08:26 -0500

> On Jan 18, 2018, at 3:00 PM, Jeffrey Walton <[email-masked]> wrote:
> 
> 

Key agreement private keys should be single-use.  The all zero
check is solely a counter-measure against non-contributory outcomes.

-- 
	Viktor.

---

From: Jeffrey Walton <[email-masked]>
Date: Thu, 18 Jan 2018 15:08:45 -0500

>     leakage is already obtained by the adversary.

By the way... if interested, here are the libsodium test vectors that
include the small element case:
https://github.com/jedisct1/libsodium/blob/master/test/default/box.c .
The useage of interest is:

    // 0 = success; non-0 = failure
    ret = crypto_box(c, m, 163, nonce, small_order_p, alicesk);
    assert(ret != 0);

If a function or system consumes the small order element then it may
be susceptible to the side channel attack.

This is how we came to know the paper and the blacklist. We did not
fail when we were supposed to.

Jeff

---

From: Jeffrey Walton <[email-masked]>
Date: Thu, 18 Jan 2018 15:12:39 -0500

> check is solely a counter-measure against non-contributory outcomes.

Thanks. The RFC states otherwise:

   The check for the all-zero value results from the fact that the
   X25519 function produces that value if it operates on an input
   corresponding to a point with small order, where the order divides
   the cofactor of the curve ...

Jeff

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 18 Jan 2018 15:24:23 -0500

> On Jan 18, 2018, at 3:12 PM, Jeffrey Walton <[email-masked]> wrote:
> 

You're reading meaning into that text that is not there.  All the
all-zero outcome is the only non-contributory outcome.  All small-order
points result in that value.  The check avoids non-contributory shared
keys.  That's all.  Implementations that re-use private keys need to
avoid computations that leak, quite separately from this check.

-- 
	Viktor.

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 18 Jan 2018 15:26:41 -0500

> On Jan 18, 2018, at 3:24 PM, Viktor Dukhovni <[email-masked]> wrote:
> 

Quoting the RFC:

   Protocol designers using Diffie-Hellman over the curves defined in
   this document must not assume "contributory behaviour".  Specially,
   contributory behaviour means that both parties' private keys
   contribute to the resulting shared key.  Since curve25519 and
   curve448 have cofactors of 8 and 4 (respectively), an input point of
   small order will eliminate any contribution from the other party's
   private key.  This situation can be detected by checking for the all-
   zero output, which implementations MAY do, as specified in Section 6.
   However, a large number of existing implementations do not do this.

-- 
	Viktor.

---

From: Jeffrey Walton <[email-masked]>
Date: Thu, 18 Jan 2018 15:43:28 -0500

>    However, a large number of existing implementations do not do this.

As it is written, Section 6.1 states the "all 0's check" is used for
the standard side channel attacks, which includes the attack detailed
in the paper. If the "all 0's check" in Section 6.1 only applies to
contributory behavior, then Section 6.1 needs to clearly state it.
That's what the Security Considerations section is for. Otherwise, it
is confusing (q.v.).

Jeff

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 18 Jan 2018 15:49:09 -0500

> On Jan 18, 2018, at 3:43 PM, Jeffrey Walton <[email-masked]> wrote:
> 
> in the paper.

No, it just says that when performing the check one should not introduce
new side-channel attacks.  It does NOT say that the check is a side-channel
counter-measure:

   The check for the all-zero value results from the fact that the
   X25519 function produces that value if it operates on an input
   corresponding to a point with small order, where the order divides
   the cofactor of the curve (see Section 7).  The check may be
   performed by ORing all the bytes together and checking whether the
   result is zero, as this eliminates standard side-channels in software
   implementations.

The "...as this eliminates..." language is only about avoiding side-channel
issues when doing the comparison.

-- 
	Viktor.

---

From: Jeffrey Walton <[email-masked]>
Date: Thu, 18 Jan 2018 15:53:09 -0500

> issues when doing the comparison.

Here we go again... Here is what Section 6.1 says:

The "all 0's check" does not eliminate the standard side-channels in software.

The world is a bigger place than single use DH in TLS.

Jeff

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 18 Jan 2018 15:58:14 -0500

> On Jan 18, 2018, at 3:53 PM, Jeffrey Walton <[email-masked]> wrote:
> 

You (and the paper's authors) are misreading the text of the RFC.  There
is NO claim that the all zeros check is a side-channel counter-measure
(let alone a universally effective one).  ALL that is said is that
the comparison should be done in constant time, such as by using OR
on all the bytes, THEREBY avoiding creating a side-channel.

The "this" in question is the use of "OR" not the all the all zeros check
itself.  Perhaps this could have been more clear, but to me that is the
most natural reading of the RFC's language.

-- 
	Viktor.