Schneier's Law

    image

    In 1998, the famous American cryptographer Bruce Schneier wrote:
    Anyone, starting from the most stupid amateur and ending with the best cryptographer, can create an algorithm that he himself is not able to crack.

    A reformulation of this quote, proposed by journalist Corey Doctorow in 2004, became known as Schneier’s Law:
    Everyone can invent a security system that he would not be able to crack.

    A very good illustration of Schneier’s law, in my opinion, is the attempt 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 at the time. However, Moore's law is relentless, and some cryptographers already began to sound the alarm.
    One of the first to criticize the key length of the new 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 an exhaustive search attack.

    In light of the above remark, attempts to increase the durability of the DES algorithm using the multiple encryption technique look quite logical. This method allows you to artificially increase the key length by applying several times the encryption operation with different keys.
    At first glance, it might seem that to solve the DES problem, it is enough to double the length of the key, 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 the 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 to 2 112 and makes the brute force attack a meaningless 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 created an encryption scheme and cannot find any flaws in it, this does not mean that they are not there.
    In 1981, Ralph Merkle and Martin Hellman examined in detail the security of double encryption and described a way to recover the encryption key not for 2 112 encryption operations, but for relatively trivial 2 57 .
    The method proposed by Merkle and Hellman belongs to the class of attacks based on plaintext, 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 open the key, the attacker enumerates all possible 2 56 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 56 variants of the key K2 and writes to the table T2 the values ​​{D K2 (C), K2}.
    Having sorted the tables T1 and T2, the attacker accepts K1 and K2 as probable keys for which E K1 (P) = D K2 (С).
    The described attack is called a “meeting in the middle”, because encryption is performed on the one hand and decryption on the other. The resulting “in the middle” results are compared.

    Triple encryption

    In 1978, Walter Tutchman proposed using triple encryption to increase the strength of the DES algorithm. Tachman’s 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-engagement attack. Even if the attacker forms the table {D K1 (C), K1}, for the attack he will need to get all possible values ​​{D K2 ((E K1 (P)), K1 || K2}, which is 2 112 entries and of course does not seem real.
    But Tachman’s method was not long considered reliable.

    Merkle and Hellman described an attack option with the selected clear text on the triple encryption scheme.
    In the attack proposed by Mekl and Hellman, the so-called decrypting 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 56 variants of the key K2, decrypts the block consisting of zero bytes and writes the values ​​{D K2 (0), K2} to table T1
    • attacking for each of the 2 56 variants of the key K1, decrypts the block consisting of zero bytes: D K1 (0). The attacker sends a value of 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 key variant K1 {D K1 (Enc (D K1 (0))), K1} is written to table T2
    • Having sorted the tables T1 and T2, the attacker accepts K1 and K2 as probable keys for which
      D K1 (Enc (D K1 (0))) = D K2 (0).

    The essence of the method is not entirely obvious. For clarification, we write what the Enc () function represents. 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 calculates 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 the keys K1 and K2 are selected as probable candidates.
    Attack requires 2 57encryption operations, which differs significantly from the expected strength of triple encryption 2 112 .
    Of course, the attacks described by Merkle and Hellman are more theoretical and their practical implementation is very unlikely, but they very well show how easy it is to make a mistake in the design of cryptosystems.

    Schneier's Law

    Schneier’s law warns against the use of unverified security systems and especially 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 shortcomings that were missed during the design. It is naive to believe that an amateur will be able to create a stable system.
    Phil Zimmermann, creator of PGP, wrote the following about this:
    When I was in college in the 70s, I came up with what I thought was the ideal encryption scheme. A simple pseudo-random number generator generated a gamma that added up with plain text. The scheme was resistant to the frequency analysis of ciphertext and was completely unbreakable for 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 you have created a perfectly stable system, do not rush to use it in your project. Think of Schneier’s law and better use the widely known method.

    References

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

    Also popular now: