One of the most remarkable episodes in the history of cryptography began in the 1970s when researchers at IBM developed what was eventually to become DES. This algorithm can be described at a high level as consisting out of a goodly number of boxes
which are connected in some complex configuration. However, which particular configuration to choose among the billions of possibilities seemed largely arbitrary; the only important part was for everybody to agree on one particular choice.
IBM therefore submitted their design to the National Bureau of Standards and the NBS, as it was legally obligated to, published IBM’s draft for DES and requested public comment. One interesting comment came from the National Security Agency and suggested, without explanation, a particular, different choice of configuration. The NBS, perhaps deferring to another government agency or the 1970s having been a more trusting time, adopted the NSA’s changes as an official standard.
DES was widely used for almost two decades and only when DES’s usage was already in decline as a result of the rise of public-key cryptography (which undergirds much of the Internet today) did Biham and ShamirThe latter was also one of the fathers of public-key cryptography. Hence, RSA. publish a powerful and novel method of breaking codes, called differential cryptanalysis.
Many of the then-common and presumed-secure ciphers proved extremely vulnerable to attacks using differential cryptanalysis. One, however, exhibited strong resistance to differential cryptanalysis: DES. For it turned out that the particular configuration suggested by the NSA just so happened to be among the handful most resistant to differential cryptanalysis among the billions of possible choices.
This has multiple, interesting implications:
The NSA must have (or least have had and quite possibly still have) some very good mathematicians in their employ. To discover something this significant decades before anybody elseResearchers at IBM would much later, but creditably, claim that they too discovered differential cryptanalysis around the same time they designed DES. One would be inclined to believe them, but that only slightly diminishes this point. requires considerable talent.
The NSA is very good at keeping secrets. Scientific discoveries like differential cryptanalysis scream to be let out (or at least their discoverers do). To have suppressed this powerful urge for so long is impressive, even apart from the discovery.
The NSA may be benevolent. After all, it could just have offered the configuration most easily attacked by differential cryptanalysis and thereby gained easy access to all the secrets. Instead, it made the opposite choice, making secrets more secure against everybody, including the NSA.
An alternative explanation is that the NSA knew both (a) that it had other still-secret methods at its disposal which could break even the strong DES configuration and (b) that adversaries—one hears that there has been a Russian mathematician of distinction or two—have only differential cryptanalysis, but not the more powerful methods.
The main lesson to be drawn is that one should be very, very hesitant to conclude that there is anything the NSA cannot do, just because nobody else in the world can do it. This episode proves that this is not always a valid inference. It is far more likely that there is a basement in Fort Meade, Maryland, with a quantum computer happily and efficiently factoring integers even larger than 15 using Shor’s algorithm than that there is an alien autopsied corpse in Area 51.
