Schneier's Law

In 1998, the famous American cryptographer Bruce Schneier wrote:

Anyone, starting with the most stupid amateur and ending with the best cryptographer, can create an algorithm that he himself is not able to crack.

The reformulation of this quote, proposed by journalist Cory Doctorow in 2004, became known as the Schneier Act:

Each person can invent a security system that he would not be able to hack.

A very good illustration of Schneier's law, in my opinion, are attempts to strengthen the DES encryption algorithm.

Double encryption

DES was adopted as a standard in 1977. The key length of the new standard was 56 bits, a rather large number for those times. However, Moore's law is implacable, and some cryptographers had already begun to sound the alarm.
One of the first to criticize the length of the key standard was the notorious founding fathers of public-key cryptography: Whitfield Diffie and Martin Hellman. In one of their articles, they argued that the 56-bit key is too small and leaves room for a full brute-force attack.

In the light of the above remark, attempts to increase the strength of the DES algorithm using the multiple encryption technique seem quite logical. This method allows you to artificially increase the key length by applying the encryption operation with different keys several times.
At first glance it may seem that to solve the DES problem it is enough to double the key length, i.e. use the following scheme as encryption and decryption:
C = E _K2 (E _K1 (P)),
P = D _K1 (D _K2 (C)),
where C is a ciphertext; P - plaintext; and E _K (P) and D _K (C) are the encryption and decryption procedures, respectively.
The above scheme increases the key space up to 2 ¹¹² and makes the attack a brute force senseless undertaking.

It would seem that a solution has been found. But at this very moment it is time to recall the Schneier Law. If you have created an encryption scheme and cannot find flaws in it, this does not mean that there are none.
In 1981, Ralph Merkle and Martin Hellman understand in detail the security of double encryption and describe a way to restore the encryption key not for 2 ¹¹² encryption operations, but for relatively minor 2 ⁵⁷ .
The method proposed by Merkle and Hellman belongs to the class of open-text attacks, and is applicable if the attacker knows a pair of open-closed text.
The essence of the attack is as follows. The attacker knows the plaintext P and the corresponding ciphertext C = E _K2 (E _K1 (P)).
To unlock the key, the attacker enumerates all possible 2 ⁵⁶ variants of the key K1 and writes the values ​​{E _K1 (P), K1} to table T1.
Then using the value C, the attacker goes through 2 ⁵⁶ variants of the K2 key and writes the values ​​{D _K2 (), K2} to the table T2.
Having sorted the tables T1 and T2, the attacker takes as probable keys the following K1 and K2, for which E _K1 (P) = D _K2 ().
The described attack is called “meeting in the middle”, because on the one hand, encryption is performed, and on the other, decryption. The results obtained “in the middle” are compared.
')

Triple encryption

In 1978, Walter Tachman proposed using triple encryption to increase the strength of the DES algorithm. The Touchman scheme also uses two keys, K1 and K2, but the encryption and decryption process is as follows:
C = E _K1 (D _K2 (E _K1 (P)))
P = D _K1 (E _K2 (D _K1 (C))).
This method is protected against a “mid-encounter” attack. Even if the attacker forms the table {D _K1 (C), K1}, he will need to get all possible values ​​{D _K2 ((E _K1 (P)), K1 || K2} for the attack, which is 2 ¹¹² entries and of course does not seem real.
But the method of Tachman was not considered reliable for a long time.

Merkle and Hellman described a variant of the attack with a clear text on the triple encryption scheme.
In the attack proposed by Meckle and Hellman, an attacker has access to a so-called. decoding oracle. This means that an attacker can send any message to the input of the encryption function and receive its encrypted counterpart.
Merkle-Hellman’s attack on triple encryption boils down to the following actions:

• the attacker enumerates all possible 2 ⁵⁶ variants of the K2 key, decrypts the block consisting of zero bytes and writes the values ​​{D _K2 (0), K2} to the T1 table
• the attacker for each of the 2 ⁵⁶ variants of the key K1, decrypts the block consisting of zero bytes: D _K1 (0). The attacker sends the value D _K1 (0) to the encrypting oracle and decrypts the response received from the oracle using the selected key K1: D _K1 (Enc (D _K1 (0))). The resulting value and option key K1 {D _K1 (Enc (D _K1 (0))), K1} is written to table T2
• Having sorted the tables T1 and T2, the attacker takes as probable keys such K1 and K2, for which
  D _K1 (Enc (D _K1 (0))) = D _K2 (0).

The essence of the method is not entirely obvious. For clarification, let's write out what the Enc () function is. This is a compressed record of triple encryption, i.e. Enc (x) = E _K1 (D _K2 (E _K1 (x))).
In a Merkle-Hellman attack, the attacker computes D _K1 (Enc (D _K1 (0))). Thus, if K1 is correctly guessed, the result is the expression D _K1 (E _K1 (D _K2 (E _K1 (D _K1 (0))))) = D _K2 (0).
If the resulting value is in table T1, then keys K1 and K2 are selected as probable candidates.
To implement the attack, 2 ⁵⁷ encryption operations are required, which is significantly different from the expected strength of triple encryption 2 ¹¹² .
Of course, the attacks described by Merkle and Hellman are more theoretical in nature and their practical implementation is very unlikely, but they very well show how easily a mistake can be made when designing cryptosystems.

Schneier's Law

Schneier's Law warns against the use of untested security systems and in particular systems designed independently. Both of the above options for solving the DES key length problem were proposed by professional cryptographers and nevertheless contained very serious flaws that were missed when designing. It would be naive to believe that an amateur can create a stable system.
Phil Zimmermann, the creator of PGP, wrote the following about this:

When I was in college in the 70s, I came up with, as it seemed to me, the ideal encryption scheme. A simple pseudo-random number generator generated a gamut that was summed with plaintext. The scheme was resistant to the frequency analysis of the ciphertext and was completely unbreakable for the special services, with enormous computing power.
Years later, I found a similar scheme in some cryptography textbooks. Cool. Other cryptographers think in a similar direction. Unfortunately, the scheme was described as a simple homework: hack the scheme using basic cryptanalysis methods.

If you think that you have created a perfectly resistant system, do not rush to use it in your project. Remember the Schneier's law and better use the well-known method.

Links

Comments Bruce Schneier on his law.
Merkle, Hellman - On the security of multiple encryption
Phil Zimmermann on PGP