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

Sent from my phone.  Please excuse brevity and typos.

> On Nov 16, 2015, at 18:01, Phillip Hallam-Baker <phill@hallambaker.com> wrote:
> 
> What is the probability that all zeros occurs at random?

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

> 
>> On Mon, Nov 16, 2015 at 6:03 PM, Adam Langley <agl@imperialviolet.org> wrote:
>> 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 agl@imperialviolet.org https://www.imperialviolet.org
>> 
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg