Subject: [saag] The History of Dual_EC, RC4, and MtE (MD5 bonus) (was possible BCP on public review being needed for standards-track crypto)

From: Watson Ladd <[email-masked]>
Date: Sun, 10 Jul 2016 12:24:28 -0700

Dear all,
I'm hoping our email clients are smart enough to put this email in the
right place. The history of cryptography is extremely well documented,
and it's important to get this right before making judgments about it.
I'm going to discuss the history of all four, in great detail, so that
we understand what was known, and why standards bodies ignored it.

Dual_EC has a fairly incomplete story, but DJB has done a lot of work,
along with Matthew Green in exposing it.. The relevant facts are that
in 2005 Certicom patented the backdoor in Dual EC, in 2006 a bias was
discovered in the output, in 2007 the backdoor was independently
published, and in 2011 NIST decided to go through and standardize it
anyway. The ANSI crypto committee had members who were listed as
inventors on the Certicom patent, but neverthless standardized it
anyway. I don't have a copy of the standard, but I don't recall it
describing the backdoor.

In short had NIST bothered to do even the most cursory of searches in
2011 they would have seen that Dual_EC failed to meet minimal security
requirements, that it had a backdoor, and that it was slow as
molasses. A bit of thinking about what encrypting with AES means would
show that you don't need to have number theoretic based RNGs. NIST and
ANSI nevertheless proceeded to standardize Dual_EC without noting
these concerns. It is unclear what happened to Juniper: no one has
sued them yet to the best of my knowledge. (Please do if you have
standing: we want to know what happened!)

RC4 was broken within a year of public disclosure: the first byte
biases can be noted in fairly trivial experiments, and were. Long-term
biases in RC4 output were certainly known in 2001, and RC4 was never
required by the TLS specification. Nevertheless it took over a decade
to finally kill: the problem was ignored until 2013, and in fact
worsened by the response to errors in CBC mode, which was to use RC4
instead of adopt AES-GCM.

Why was CBC mode vulnerable? During the development of IPsec the fact
that EtM is secure was well-known: the often cited 2001 Vaudenay and
Rogaway papers merely demonstrated that what was not known to be true
was in fact false in many circumstances. The conservativism of EtM was
well known in 1995 as the Rogaway IPsec comments show. TLS 1.1 did not
fix this mistake. But this was not the only the only failure in CBC
mode ciphers: the use of a predictable IV breaks the necessary
condition in CBC indistinguishability results. This mistake was fixed
in TLS 1.1, but uptake was slow until exploits were developed.

MD5 has been exploited as late as 2012, 16 years after the first
freestart collision, and 8 years after the first collision. What
should have been an immediate ban on issuing new certificates using
MD5 and replacement with SHA1, followed by gradual phaseout, was
instead a series of stopgaps, making the eventual end extremely messy
and drawn out.

To this day we have to worry about the Bleichnbacher attack on PKCS
1.5 encryption. The obvious remedy is to not implement partial
countermeasure after countermeasure, but to root-and-branch replace
it. Each time we worry about the pain it will cause, and add another
stopgap, we only delay the inevitable.

In each of these cases actual cryptographers with actual knowledge
advised repeatedly against the decisions that were actually made. In
each case attacks were dismissed as theoretical possibilities, and
standardization bodies never looked at the actual state of knowledge
at the time. When standards bodies did react, there was no wider
understanding that migration was necessary. Implementors assumed that
standards bodies had knowledge: they did not. Were MD5, Dual_EC, RC4,
and MtE insufficiently reviewed? The answer is clearly no: the issues
were very well known, and in many cases documented. The response was
insufficient because of varying degrees of concern for backwards
compatibility (despite negotiation mechanisms intended to enable
change), failure to understand the issues, and some people rather like
being able to exploit everything in sight.

This email could easily be four times the size.: Does anyone use
policy mapping? The horror that is OpenPGP has been passed over in
silence. XML has its own share of crypto related mistakes. IPsec
compatibility issues have forced password based modes to remain for
years. Many standardized schemes receive almost no review: they are
slighter better then the random crypto related github project, but
chances are not much.  When review does happen the attitude taken is
not one of "this must be obviously correct" but "do I really need to
change it? Is this really an attack?". It's common in design
discussions for spurious considerations to be given equal or greater
weight to core cryptographic security considerations in working
groups: not the real constraints of migration and backwards
compatibility, but imaginary concerns.

Sincerely,
Watson Ladd

---

From: "Salz, Rich" <[email-masked]>
Date: Sun, 10 Jul 2016 19:28:51 +0000

> requirements, that it had a backdoor, and that it was slow as molasses.

Are you aware that, by law, the NSA is the crypto expert body for NIST?

That probably had something to do with it.