Differential cryptanalysis
The discovery of differential cryptanalysis is generally attributed to Eli Biham and Adi Shamir in the late 1980s, who published a number of attacks against various block ciphers and hash functions, including a theoretical weakness in the Data Encryption Standard (DES).It was noted by Biham and Shamir that DES was surprisingly resistant to differential cryptanalysis, but small modifications to the algorithm would make it much more susceptible.[2] According to author Steven Levy, IBM had discovered differential cryptanalysis on its own, and the NSA was apparently well aware of the technique.This in turn would weaken the competitive advantage the United States enjoyed over other countries in the field of cryptography.[4] While DES was designed with resistance to differential cryptanalysis in mind, other contemporary ciphers proved to be vulnerable.An analysis of the algorithm's internals is undertaken; the standard method is to trace a path of highly probable differences through the various stages of encryption, termed a differential characteristic.Observing the desired output difference (between two chosen or known plaintext inputs) suggests possible key values.In essence, to protect a cipher from the attack, for an n-bit non-linear function one would ideally seek as close to 2−(n − 1) as possible to achieve differential uniformity.In fact, the AES cipher would be just as immune to differential and linear attacks with a much weaker non-linear function.For example, with the current S-box AES emits no fixed differential with a probability higher than (4/256)50 or 2−300 which is far lower than the required threshold of 2−128 for a 128-bit block cipher.