Subject: [Cfrg] Switching the zero-check from MUST to MAY in the curves draft.

From: Adam Langley <[email-masked]>
Date: Mon, 16 Nov 2015 15:03:01 -0800

At the moment, the curves draft says that implementations MUST check
for the all-zero output and abort if it's found, at least in
Diffie-Hellman. The all-zero output results when the input point has
small order and this sort of thing has, in the past, broken at least
Tor and TLS channel bindings.

While reactions on the list were ambivalent to the suggestion, I had
hoped that implementations would take this requirement as a simple
defence-in-depth measure in keeping with the general robustness theme
of this work.

I was mistaken. It's since become clear that some disagree
sufficiently strongly about this that we aren't going to see a
realignment of implementations around this behaviour. While I still
think that it's a sensible requirement, RFCs that are prescriptive
rather than descriptive are terrible and so I currently hope to switch
from MUST to MAY once the draft has completed the editor's queue.
Instead, some wording would be added to the Security Considerations
section.

This change contains the accumulation of tweaks that I currently have
saved up, including this one:
https://github.com/agl/cfrgcurve/commit/c7749d4bb5ceabdb30f211d4aaa6df2b68d7c5e1

This email is notice that I currently plan on making this change. Note
that the question here isn't whether the zero check is a good idea or
not. Rather it's that, given that a non-trivial number of
implementations aren't going to implement it, what's the best thing to
write?

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 16 Nov 2015 23:12:27 +0000

On one hand, an RFC describes a protocol, not an implementation. On the
other hand, having an implementation that does not check for zero in DH
sounds strange, to say the least.

If you don’t want to use the IETF term “MUST” (or “SHOULD”), perhaps you
can just say that “not checking for zero can lead to catastrophic security
failures, and it is responsibility of the application developer to make
sure it doesn’t happen”…
-- 
Regards,
Uri Blumenthal

On 11/16/15, 18:03 , "Cfrg on behalf of Adam Langley"
<[email-masked] on behalf of [email-masked]> wrote:

>_______________________________________________
>Cfrg mailing list
>[email-masked]
>https://www.irtf.org/mailman/listinfo/cfrg

---

From: Deirdre Connolly <[email-masked]>
Date: Mon, 16 Nov 2015 23:46:46 +0000

I think that your description fits 'SHOULD' more than 'MAY', given that the
expanded Security Considerations imply that "the full implications must be
understood and carefully weighed" before not checking for an all-zero
output.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 16 Nov 2015 21:01:51 -0500

What is the probability that all zeros occurs at random?

Is there a mechanism that would allow an attacker to force use of all zeros?

---

From: Mike Hamburg <[email-masked]>
Date: Mon, 16 Nov 2015 18:29:42 -0800

Sent from my phone.  Please excuse brevity and typos.

> On Nov 16, 2015, at 18:01, Phillip Hallam-Baker <[email-masked]> wrote:
> 

I believe the answer is: for x25519, zero. For x448, 1/2^445 per party, which is essentially zero.  This is because the order of curve25519 is slightly greater than a power of 2, and the order of curve448 is slightly less.

An implementation which is actually worried about this can call the x448 ephemeral keygen in a loop until it succeeds.

> Is there a mechanism that would allow an attacker to force use of all zeros?

Yes, an attacker can easily force it by sending specific values of g^x, most of which cannot be produced by a legitimate implementation.   There are something like 5 such values for curve448 and 14 such values for curve25519.

-- Mike

---

From: Taylor R Campbell <[email-masked]>
Date: Tue, 17 Nov 2015 14:16:14 +0000

Date: Mon, 16 Nov 2015 18:29:42 -0800
   From: Mike Hamburg <[email-masked]>

   > Is there a mechanism that would allow an attacker to force use of

   Yes, an attacker can easily force it by sending specific values of
   g^x, most of which cannot be produced by a legitimate
   implementation.  There are something like 5 such values for
   curve448 and 14 such values for curve25519.

A malicious peer can do that, but so what?  A malicious peer can also
use a secret key k known to an eavesdropper, and send k*B where B is
the standard base point.  Then the eavesdropper seeing the good guy's
public key h*B over the wire can readily predict k*h*B and find the
session key.  A malicious peer could also email the session transcript
to the eavesdropper.

What is the serious attack that is prevented by a zero check?  It
seems to me an answer to that question is more important than the
choice of verb.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 17 Nov 2015 09:31:04 -0500

> seems to me an answer to that question is more important than the

Some protocols require contributory behavior from DH exchanges.
Examples include TLS. Most protocol designers understood how to avoid
this, but TLS was not designed by a cryptographer. This went unnoticed
until very recently, when it was exploited in the Triple-Handshake
attack.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 17 Nov 2015 10:53:31 -0500

> until very recently, when it was exploited in the Triple-Handshake

SSL 1.0 and SSL 2.0 were not. But SSL 3.0 was designed by Paul Kocher
working for Taher El-Gamal.

The problem was that he only had two weeks to do the work and Netscape
did not put the proposal out for public review. You might think that
you would want to do that after your first attempt was broken fifteen
minutes into the first (and only) presentation outside the company.
Thats not the way Netscape went about things.

---

From: Adam Langley <[email-masked]>
Date: Tue, 17 Nov 2015 16:19:39 -0800

> understood and carefully weighed" before not checking for an all-zero

I'm not sure that I've strong feelings between SHOULD and MAY in this
case, but I see your point. I expect I'll see what the feelings of the
other authors and chairs is during AUTH48 and exactly where to draw
this line.

Cheers

AGL

---

From: Deirdre Connolly <[email-masked]>
Date: Tue, 17 Nov 2015 20:05:43 -0500

> other authors and chairs is during AUTH48 and exactly where to draw

Sounds good.

---

From: Rene Struik <[email-masked]>
Date: Mon, 23 Nov 2015 10:13:30 -0500

Hi Adam:

I think it is imprudent to remove "MUST" language, so would definitely 
not be in favor of this.

Just curious who the "some" are in the sentence you wrote on "some 
disagree" below.

Shouldn't implementers do the right thing and add the *tiny* 
implementation check to their code in case they haven't done so yet? 
What are the perceived obstacles?

Best regards, Rene

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Rene Struik <[email-masked]>
Date: Mon, 23 Nov 2015 10:50:34 -0500

[additional note]

Hi Adam:

I think implementations that do not implement the check should not be 
able to claim compliance (which "MUST" accomplishes).

Rene

==

---

From: Greg Hudson <[email-masked]>
Date: Mon, 23 Nov 2015 11:26:58 -0500

On 11/23/2015 10:13 AM, Rene Struik wrote:
> Just curious who the "some" are in the sentence you wrote on "some disagree" below. 

See this thread:

http://www.ietf.org/mail-archive/web/cfrg/current/msg06558.html

The primary concern is that it turns a function with no exception cases
into a function with an exception case, or requires the function to draw
from a source of randomness in order to ensure that the exchange fails.

On a related note, I haven't seen a justification for the check stated
in a way that would make sense to the audience of the CFRG
recommendation, and I think there's no justification at all in the
draft.  The closest I have seen here are statements that the check is
required when the protocol requires contributory behavior.

I assume the risk is that an attacker could MITM the exchange and cause
both sides of the MITM'd exchange to use the same K=0 by sending a point
of low order.  If the protocol does a channel-bound authentication using
only K to derive the channel ID, then the authentication will also
succeed, with the attacker controlling the channel.  Such a protocol
would be ignoring the advice from the draft to "use a key-derivation
function that includes K, K_A and K_B," but it's possible (even likely)
that the protocol designer hasn't read the CFRG recommendation, only the
X25519 implementor.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 23 Nov 2015 11:38:58 -0500

> that the protocol designer hasn't read the CFRG recommendation, only the

The problem here is the protocol designer is unaware of the actual
workings of prime field DH as well, and many implementations of
prime-order ECC. Just because implementors return an error value
doesn't mean that protocol implementations will check it: it is far
more robust to demand that protocols hash transcripts.

---

From: Rene Struik <[email-masked]>
Date: Mon, 23 Nov 2015 12:04:37 -0500

Hi Greg:

If I understand correctly, it seems you prefer to impose design constraints on the kdf that might not have been necessary if one would have simply implemented this simple check (which was already in the Handbook of Applied Cryptography, 1996, Note 12.50). This seems to preclude "drop in" use of the CFRG curve DH function in contexts with an existing kdf that does not have the "hash everything" form. Moreover, skipping this check makes the overall analysis of protocols harder, since deviating from modular building blocks.

I also do not understand the remark on randomness: doesn't ECDH already require a source of randomness for generating a "fresh" ephemeral private key?

Best regards,

Rene

---

From: Watson Ladd <[email-masked]>
Date: Mon, 23 Nov 2015 12:28:41 -0500

On Nov 23, 2015 12:04 PM, "Rene Struik" <[email-masked]> wrote:
>
> Hi Greg:
>
> If I understand correctly, it seems you prefer to impose design
constraints on the kdf that might not have been necessary if one would have
simply implemented this simple check (which was already in the Handbook of
Applied Cryptography, 1996, Note 12.50). This seems to preclude "drop in"
use of the CFRG curve DH function in contexts with an existing kdf that
does not have the "hash everything" form. Moreover, skipping this check
makes the overall analysis of protocols harder, since deviating from
modular building blocks.

This is wrong: contributory behavior is a well understood assumption. This
is not an issue for EICS encryption, as contributory behavior is not
required. It's not an issue for SSH, either. We know that these checks are
frequently omitted: protocols which require contributory behavior are not
robust.

>
> I also do not understand the remark on randomness: doesn't ECDH already
require a source of randomness for generating a "fresh" ephemeral private
key?

No, the caller provides a key. Whether that key is random or from disk is
irrelevant.
disagree" below.