When The NSA Made Crypto Better

When The NSA Made Crypto Better

In 2013, Edward Snowden outlined how the NSA had pushed a specific elliptic curve method as a standard — Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) — and which they knew that they could crack. There is thus always a challenge for law enforcement agencies in creating backdoors in cryptography, in that they will provide them with an advantage over their adversaries. But, there is a case from the 1990s of the NSA actually improving a cryptography method, in order to stop it from being vulnerable.

Differential cryptanalysis method

A differential attack on a block cipher is where we analyse the change between one plaintext value and another, and the change that it makes on the output ciphers. In many cases we change one bit in the input, and observe one bit change on the input and observe the change in the output. A well designed cipher will cause an average of 50% of the bits to change. If the result is non-random, it gives an attacker an advantage in cracking the block cipher.

The differential cryptanalysis method was created in the 1990s and where it was possible to change a single bit in plaintext (P and P’) and then observe the change in the output ciphertext (C and C’):

The difference in encryption is then created with the addition of the key, and where parts of the key will be revealed through the differential method.

Tracing the s-boxes

An S-box is often used in a crypto method, and where it is possible to follow a bit through each round and watch how it will be routed to the output, and we can then discover parts of the keys. As the differential cryptanalysis was being defined, IBM found-out that a common encryption method — DES (Data Encryption Standard) — was free of attacks for its S-boxes. It has since been shown that the NSA had actually defined an update to the original S-box specification for DES, in order to improve its resistance. It is thought that the NSA was actually trying to shore-up the DES method, in order that differential cryptanalysis would not show that it to be flawed.

While the differential cryptanalysis was published by Eli Biham and Adi Shamir in the late 1980s, it is thought that the NSA already knew about the technique before it was made public.

So why did the NSA want to shore-up DES? Because DES has a 56-bit key, and it was thought that the NSA had the computational resources to crack the relatively small key. Thus, they wanted to keep the method going.

So let’s look at a bit of background on s-boxes…

S-box and Inverse S-box

Let’s look at an example of AES, and which uses S-boxes, and were we operate on 128 bit blocks (16 bytes), and where we use substitution bytes (S-boxes) for each round:

Figure 1: Example of AES

The method transforms the inputs to a new value as an output each state into a new value using an S-box table. In this case the S-Box table is 16x16 matrix which takes each input value, and where the first four bits is used to define row of the table, and the next four bits defines the column (Figure 2). For example if the input byte is CF, then the output will be 8A. The inverse S-box does the reverse of the S-box process, so the DF maps back to CF (Figure 3).

Figure 2

Figure 3

Conclusions

Most modern cryptography methods are fairly robust against differential cryptanalysis, as it is one of the main tests that are understand in the evaluation of the method. AES is thus robust against it.

Here is some of our work here and cracking AES keys by listening the power supply of a chip: