Being a cryptanalyst at the NSA is better (more fun) than being a cipher maker, because the sense of success is far more tangible for the cryptanalyst than for the cipher maker. Once you break a code, you can prove that you have successfully broken the code. There is nothing indeterminate about that. You break it, and that's it. But if you are creating ciphers, once you created one that you think is secure, there is no guarantee whatsoever about its security in the future. All you can say is that this cipher is unbreakable using today's methods. So, you can't prove that your code is secure. If a cipher is unbreakable at present, you can't say that it will be unbreakable forever.
You can prove that a cipher is weak by breaking it, but you can't prove that a cipher is strong by showing that nobody currently can break it.
However, this is only true for chosen plaintext attack, in which the adversary can give arbitrary plaintext input to the cryptosystem and observe its output. This type of attack, although very powerful, is seldom available. So, if we can protect the system such that this attack is infeasible, the security of Triple-DES is 2128.
DES is a block cipher and encrypts 64-bit blocks using a 56 bit key. This key is usually expressed as a 64-bit number, in which case every eighth bit serves as a parity bit, and is ignored in the algorithm. The algorithm itself places no restrictions on the bit combination of the key, but some keys have undesirable property and are considered weak or semi-weak keys. There are four weak keys and twelve semi-weak keys that shouldn't be used. However,, since there are only 24 weak and semi-weak keys out of 264 possible DES keys, the chance that one of these keys is picked are very small (2-60). Also, the adversary doesn't know whether the system is using a weak key or not, and must check all the 264 key combinations.
The 56-bit DES key is used for generating sixteen different 48-bit subkeys which are part of the input to each round. These subkeys, Ki, are determined by two operations: First, the key is divided into two 28-bit parts. Then, depending on the round, each part is circularly shifted left by either one or two bits. After the shifting, 48 out of 56 bits are selected.
After an initial permutation, the block is broken into two parts (left and right). Then 16 rounds of operations are applied, each round generating new left and right pieces for the following round.
Ri = Li-1 xor f(Ri-1,Ki)
The key part of the algorithm is a specially designed function f. See Schneier's diagram 12.4 for the implementation of f.
The processing of the right part of each round is as follows : the 32-bit input data is expanded to 48 bits. Because this operation changes the order of the bits as well as repeating certain bits, it is called an expansion permutation. This operation makes the 32-bit input data have the same size as the 48-bit key, which is necessary because the input data will be XOR-ed with the key. The result of this XOR operation is then split into eight 6-bit parts. Each part is an input to one of eight different S-boxes, which take 6-bit input and produce 4-bit output. The resulting eight 4-bit outputs from this process are combined together again to form a 32-bit quantity, which is then permuted again.
Finally, the left and right pieces are joined and an inverse of the initial permutation is taken to obtain the result. The result is 64 bits long.
Can f be inverted? No. The S-boxes are non-linear (6 bits to 4 bits), so it is impossible to reverse this function. Fortunately, this is not necessary because of the way the algorithm is structured. Based on the algorithm outline, we can see that the right part of the ciphertext = R16 = L15 xor f(R15, K16) . Since the left part of the ciphertext = L16 = R15, we can compute f(R15, K16), and get L15. In other words, if we run the ciphertext through the same algorithm but reverse the key schedule (i.e. use K16 in the first round), we will effectively decipher DES. So, there is no need to find the inverse of the S-boxes.
The full criteria for f have never been published. There are several properties of S-boxes that have been observed :
Some of these properties make more sense in the light of differential cryptanalysis.
Modifying DES by changing f usually leads to an easier to break algorithm. One straightforward way to make DES stronger is to increase the size of the key, e.g make it 16x48 bits long.
The basic idea of differential cryptanalysis is to choose a pair of plaintexts that differ only at a few bits, run them through the encryption algorithm, analyze the evolution of these differences as the plaintexts propagate through the rounds of DES when they are encrypted with the same key, and compare the ciphertexts. By performing a number of such comparisons on different input pairs with the same delta (bitwise difference), we get a distribution of the output delta. This distribution tells us information about the key.
Since S-boxes are the only non-linear transformation inside DES, this is the only place where we really use differential cryptanalysis. Knowing the difference of the input, and observing the difference of the output, we can have several possibilities of the keys. This is because a particular difference in input doesn't create a uniform distribution of output differences. Some output differences are impossible, and the distribution of the possible ones is not flat. So, we can analyze the distribution and can make an intelligent guess of the key after running this procedure several times.
(See figure 12.5 in Schneier.) Suppose we run two different plaintexts, X and X', through a round of DES. X and X' differ by delta_X. If there are, for example, 2 bits difference between X and X', then after expansion E there will be at most 4 bits different. These 4 bits can hit at most 4 S-boxes, affecting at most 8 bits on the output.
(See figure 12.6a in Schneier.) We can look at certain special cases of input/output pairs for a given round or rounds. If the delta of the left hand sides of X and X' (L and L') is an arbitrary delta_L, while R = R' so that delta_R = 0, then the same deltas describe the left and right sides of the output values.
(See figure 12.6a in Schneier.) If the input delta_L is arbitrary, and delta_R is 0x60000000 (difference only in bits 2 & 3), then with probability 14/64, the output delta_L = (L xor 0x00808200) and delta_R = 0x60000000.
We can combine these two rounds. If the input delta_L = 0x00808200 and delta_R = 0x60000000, after the first round the output delta_L = 0, and delta_R = 0x60000000. These values feed into the second round. The final delta_L is 0x60000000 and delta_R is 0, with overall probability of 14/64 * 1 = 14/64.
We can continue to combine rounds and accumulate probabilities until we have a 16-round structure. This lets us find K16, which is 48 of the 56 bits of the DES key. Then we can find the other 8 bits by trial-and-error (28 keys, not very much work).
For every n-round of DES, where n > 16, differential cryptanalysis takes less work than exhaustive search to find the key. For example, it takes only 238 known-plaintext operations to break 8-round DES. The interesting case is n = 16. It turns out that it takes 255 operations to break 16-round DES, which is the standard DES. (This is exactly the same as a brute-force attack, because DES has a complement property, so we only have to search for 255 instead of 256 when trying to break DES using brute-force attack.) This explains why DES has exactly sixteen rounds. Fewer than sixteen rounds will make it susceptible to differential attack, but more rounds will add no more security.
One nice property of differential cryptanalysis is that it only cares about differences of the plaintext and not the contents of those plaintexts. So we can easily convert this attack from chosen-plaintext to known plaintext attack.
It's worth noting that the NSA has some expertise not open to the public. Techniques like differential cryptanalysis took public researchers 20 years to discover.
Recently, in a murder trial in New Jersey, people tried to trace a phone call. But the MCI phone record database came up with 2 different sets of records. So secure timestamping is needed.
Basic idea: People submit their documents to a notary, who gets a secure time from somewhere, then signs the document and its timestamp with his private key.
Problems and Solutions:
People also build a tree structure over the chain, where a parent node timestamps its children to further prevent tampering. The top node is published weekly in the New York Times.