18.2.1 Advances in cryptanalysis
In June 2013, The Guardian and Washington Post simultaneously published an article about a secret order issued by the United States Foreign Intelligence Surveillance Court ordering Verizon, one of the largest telecommunication providers in the US, to hand over all call records and the metadata of millions Verizon customers to the National Security Agency.
It was the prelude to what eventually became known as the Snowden leaks, a cache of top secret NSA documents revealed by then 29-year-old Edward Snowden, who worked as an intelligence contractor for Booz Allen Hamilton in Hawaii.
One of the documents published by the Washington Post – a summary of a ”black budget” for US intelligence gathering activities – contained a statement by James Clapper (at that time, the Director of National Intelligence) that the US National Intelligence Program is ”investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic” [159].
In response to the Snowden leaks, the American cryptographer Bruce Schneier wrote an article for the Wired magazine [159] assessing the alleged groundbreaking cryptographic capabilities. According to Schneier, whatever the NSA’s cryptanalytic capabilities were, cryptography would still be the most secure part of an encryption system given that, in practice, social engineering, software bugs, bad passwords, malware, or insecure network configuration are much more likely.
Nevertheless, Schneier speculated that the NSA is very likely to have cryptanalytic techniques that are unknown to the public. The most probable scenario, according to Schneier, is that the NSA achieved some mathematical breakthroughs in the area of public-key cryptography: ”There are a lot of mathematical tricks involved in public-key cryptanalysis, and absolutely no theory that provides any limits on how powerful those tricks can be. […] It is not unreasonable to assume that the NSA has some techniques in this area that we in the academic world do not” [159].
While cryptanalytic techniques and theoretical cryptanalytic results are difficult to turn into practical attacks – especially attacks on symmetric key cryptography – Schneier quotes a well-known NSA saying that cryptanalysis only gets better, never worse. He concludes the article by saying it would be ”naive to assume we have discovered all the mathematical breakthroughs in cryptography that can ever be discovered” [159].
According to the Snowden leaks, the US Department of Defense employed 35,000 people in their cryptologic program, with an annual budget of $11 billion. And this is just one country; numerous nations outside the United States have similar cryptologic programs. As a result, from time to time, we should expect cryptanalytic advances, and occasionally, even groundbreaking results.
A prime example of this is the NSA’s role in the improvement of the DES block cipher in the 1970s. Recall that after the original DES algorithm submitted by IBM was sent for review to the NSA, it came back with completely different S-boxes. The modifications were analyzed by the cryptographic community – there was even an official review conducted on behalf of the US Senate’s Select Committee on Intelligence – but no statistical or mathematical weaknesses were found throughout the 1970s and the 1980s.
Only in 1990, after Eli Biham and Adi Shamir published differential cryptanalysis, a novel method for breaking block ciphers, did cryptographers discover that DES S-boxes were much more resistant against differential cryptanalysis than randomly chosen S-boxes could ever be.
Finally, when Don Coppersmith, one of the IBM cryptographers who designed DES, published original design criteria for DES S-boxes in 1994, the cryptographic community learned that the NSA and IBM knew about differential cryptanalysis as early as 1974. As a result, DES S-boxes were deliberately tweaked to resist differential cryptanalysis, but the NSA requested to keep it a secret because the attack was applicable to a wide range of cryptographic algorithms and was considered by the NSA to be a serious risk to national security if it became public.
Leave a Reply