Re: [Cfrg] On the use of Montgomery form curves for key agreement

[Brian LaMacchia <[e-mail]>]

Hi Dan,

Regarding the specific issue you raised concerning Microsoft’s TLS implementation, as you will recall Tanja first mentioned this issue to me during dinner in Toronto.  She said she found it as part of testing Internet Information Server for your Dual_EC_DRBG research which appeared at USENIX Security two weeks ago.  Her comment, and your subsequent mentions on this mailing list are the only reports of the issue of which I am personally aware.  In any event, I did look into this for you and can now confirm that there is indeed an issue and that it is in the SChannel platform implementation of TLS itself (not IIS).  

The folks in Windows who own SChannel have asked me to ask you to please open a case with the Microsoft Security Response Center on this issue.  You can do that by sending an e-mail message to the address [e-mail] describing the issue you and Tanja found.  If you CC me on the e-mail I can give some additional internal information to the MSRC case officer to whom it is assigned.  As I am in Microsoft Research and not the Operating System Group (where Windows is), MSRC will be your best contact for updating you on the progress of your case.

Thanks again for reporting this.

As for your suggestion regarding a blanket prohibition on reuse of any ephemeral cryptographic keys across all IETF protocols, given the current environment that does indeed seem like a good idea to me.  I guess what we’d really want to do is have CFRG issue a BCP on this point, if that’s something the IRTF is allowed to do (I don’t know the answer to that process question).  Perhaps CFRG can take that issue up once the curve selection process has concluded.

--bal

-----Original Message-----
From: Cfrg [mailto:[e-mail]] On Behalf Of D. J. Bernstein
Sent: Tuesday, September 2, 2014 9:54 AM
To: [e-mail]
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement

Brian LaMacchia writes:
> For the case of ECDHE, Dan Bernstein has argued for a definition of 
> “ephemeral” that would allow keys to be re-used for some amount of 
> time

Several reports have indicated that Microsoft's standard TLS library
(SChannel) reuses ephemeral DH keys (specifically TLS ECDHE keys) for two hours. Are those reports not accurate?

Even if keygen were implemented as variable-base scalarmult without the complication of a separate fixed-base scalarmult function, wouldn't you agree that this key reuse makes the cost of key generation irrelevant?
Wouldn't you expect other implementors to reuse keys for this reason?

Obviously two hours is not the right choice: repressive police states can certainly seize equipment within that time interval. In my message dated 1 Aug 2014 01:36:59 -0000, I suggested 10 seconds as an upper limit. However, this doesn't change the DH performance picture!
Variable-base scalarmult is dominant for DH, including ephemeral DH.

I concluded that CFRG should consider the performance of variable-base scalarmult (for DH), fixed-base scalarmult (for signing), and double-base scalarmult (for signature verification). But I don't expect this to produce different curve choices from considering solely variable-base scalarmult---which is also the most fundamental operation and the usual focus of DH performance analyses in the literature.

> allowing X25519 implementations to amortize the cost of operations 
> which are particularly expensive for X25519 over multiple uses of the 
> same key.

The "expensive for X25519" claim here is completely wrong. X25519 allows all the usual speed benefits from all the usual fixed-base speedups. As Mike Hamburg put it in his mail message dated 7 Aug 2014 11:57:45 -0700, optimized fixed-base scalarmult "will pretty much always cost about a third of what the variable-base scalar multiply costs."

Concretely,

   https://github.com/floodyberry/ed25519-donna
   https://github.com/agl/curve25519-donna
   
support all Curve25519/X25519/Ed25519 operations under discussion: DH keygen (curved25519_scalarmult_basepoint is the fast version), DH shared-secret computation, signature keygen, signing, and verification.
These are faster than the speeds announced by Microsoft for each of these operations (and of course also for combinations of operations in ECDHE etc.) on the CPU that Microsoft has selected for benchmarks. Also, unlike Microsoft's library, these actually do the work of signing etc.

There are many X25519 implementations, reflecting the wide use of X25519 in many real-world protocols. It's of course true that reusing DH keys practically eliminates keygen cost, which is exactly why typical users don't care about DH keygen time, which is exactly why typical DH implementations prioritize simplicity over DH keygen optimizations. This has given you the flexibility to cherry-pick X25519 implementations that don't bother speeding up keygen, and to misrepresent the performance of those implementations as the keygen performance of X25519, even though faster X25519 keygen code has been available for longer than Microsoft's library has. Your position is not defensible.

> There has been no legitimate argument put forward for repeated use of 
> ephemeral keys in ECDHE.

If a server notices keygen time, it can gain far more performance by reusing a key 100 times than by switching to fixed-base scalarmult.
Reusing keys also costs less code in many settings than implementing fixed-base scalarmult, but even without this simplicity argument you have to admit that there's a legitimate performance argument.

Out of curiosity: If it wasn't for performance, why did Microsoft's TLS library ever reuse ephemeral DH keys in the first place? Would you say that the Microsoft reason was illegitimate? Even if you're sure that it was illegitimate, wouldn't you agree that taking this reuse off of the CFRG radar screen would require a blanket prohibition on this reuse in all IETF protocols, and that no such prohibition exists?

> Assuming that implementations will implement more than one security 
> level, choosing X25519 for ECDHE at the 128 bit security level will 
> require implementations to use different curve arithmetic for the 128 
> bit security level than other security levels.

No. All Edwards (and twisted Edwards) curves, at all security levels, are compatible with choosing Montgomery coordinates for ECDHE. See my message dated 25 Aug 2014 23:43:05 -0000 for the relevant formulas.

When Tanja Lange and I introduced Edwards-curve cryptography, we correctly and publicly predicted that Edwards coordinates would be close in performance to Montgomery coordinates. However, nothing has ever matched the amazing _simplicity_ of the Montgomery X-coordinate for DH.
This simplicity is more than just a time-saver; it also removes many opportunities for DH implementors to screw up security.

> clear drawback to requiring different curve forms for key agreement 
> and digital signature at the same security level.

The Montgomery approach to DH is exceptionally simple---costing very few lines of code for a unified DH+signatures implementation (as TweetNaCl demonstrates), and at the same time saving many more lines of code for a pure DH implementation. If the picture looks like

   * complexity 300: DH using Montgomery
   * complexity 500: DH using Edwards
   * complexity 600: DH using Edwards + signatures using Edwards
   * complexity 610: DH using Montgomery + signatures using Edwards

you can't claim that there is a "clear drawback" to DH using Montgomery.

---Dan

_______________________________________________
Cfrg mailing list
[e-mail]
http://www.irtf.org/mailman/listinfo/cfrg