Walls have ears—Random numbers, Diffie-Hellman, Tom Hales and the NSA

I've been silent for a while, sorry.

Today's message will be quite short, essentially a bunch of links to various other blog posts related to cryptography, the NSA, and how our electronic messages are potentially listened to by people we did not think of, at least before Snowden leaked all this information.

I learned of this story through Thomas Hales's web page and his blog post The NSA back door to NIST (to be published in the Notices of the AMS). There he explains how a standard protocol referenced by the NIST (National Institute for Standards and Technology) has a structural flaw that may well be intended.

All modern cryptographic protocols rely on some randomness. This is in particular the case of the Diffie-Hellman key exchange protocol which allows two people to share a secret without risking to let anybody else aware of this secret.

However, in our computers, randomness is not really random, becaused it is produced by algorithms, but is enough random-looking so that it can be used safely in applications.

As Hales explains, one of these standards for pseudo-random numbers has a back door. While it looks secure at first sight, it is possible that somebody possesses the ``back door'' information that allows him to understand the logic in the output of our series of pseudo-random numbers, all over the world, thus undermining the solidity of the algorithm.

Worse, this somebody might well be the NSA (National Security Agency).

There are two arguments in favor of this thesis:

1. The back door is very elementary, so elementary in fact, that specialists can't believe its existence is not on purpose. According to a New York Times paper (N.S.A. Able to Foil Basic Safeguards of Privacy on Web, September 5th, 2013) classified memos apparently confirm this.
2. By American law, the use of NIST-approved protocols is required to obtain various certifications. Moreover, the NSA is consulted for whatever cryptographic protocol is issued and has been a strong advocate of this protocol at the NIST and subsequently promoted this protocol at all major members of the International Standard Organization (ISO).

 As Hales concludes: « An algorithm that has been designed by NSA with a clear mathematical structure giving them exclusive back door access is no accident, particularly in light of the Snowden documents. This is a work of experts. »

References:

• Thomas Hales, The NSA back-door to NIST, September 25th, 2013. Blog post, to appear in the Notices of the AMS.
•  Nicole Perlroth, Jeff Larson and Scott Shane, NSA Able to Foil Basic Safeguards of Privacy on Web, New York Times, September 5th, 2013
• Kim Zetter, How a Crypto 'Backdoor' Pitted the Tech World Against the NSA, Wired, September 24th, 2013
• Dan Shumow, Niels Ferguson, On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng, 2007