Cryptanalysis of ICE

As a new cipher, ICE has not yet undergone rigorous third-party cryptanalysis. These are the results of the author's own cryptanalysis.

Weak keys

ICE has no weak keys. Weak, or self-decrypting, keys are keys which, if they are used to encrypt the same data twice, produce the original unencrypted data. DES has four of them.

There are no semi-weak keys either. Semi-weak keys come in pairs, where the second key decrypts the first. DES has 16 of them, including the four weak keys.

A weak or semi-weak key occurs if there is another key that generates an identical key schedule, but in the reverse order. These keys can be found by setting up a series of linear (under XOR) equations expressing the fact that the schedule of key 1 is the reverse of the schedule of key 2, then solving the equations. The number of independent variables in the solution gives the log base 2 of the number of weak keys.

For ICE, there were 960 equations (16 rounds, 60 bits per round) and 129 variables (2 x 64-bit keys, plus an inversion bit). The solution was "1=0", which means that there are no keys that satisfy the equations.

Key inversion weaknesses

ICE has no key-inversion weaknesses. These occur when inverting certain bits in the key and plaintext simply cause bits to invert in the ciphertext. DES has one weakness of this sort.

They are caused in DES by the fact that key bits are only used with the XOR function. If both key and plaintext bits are inverted, the inversions are cancelled out by the XOR function, and DES behaves linearly. However, ICE also uses key bits to permute the outputs of the E boxes, so if the key is inverted, the S-boxes will receive totally different inputs.

Differential cryptanalysis

ICE levels 1 and above cannot be broken by differential cryptanalysis. However, there is a possibility that Thin-ICE can be broken by a chosen-plaintext attack with roughly 256 encryptions. This has been calculated by simply multiplying the round-by-round probabilities, so it is not yet certain whether it yields a valid attack. DES can be broken by differential cryptanalysis with 247 encryptions.

The use of keyed permutation after the E boxes means that an attacker cannot know which S-box will be affected by a particular input bit. However, since the keyed permutation acts to simply swap bits between the left and right halves of a 32-bit value, the attacker can use inputs whose leftmost 16 bits are the same as the rightmost 16 bits. This enables the attacker to send known differences to the S-boxes, but it usually also means that twice as many S-boxes have to be attacked simultaneously, often with low-probability differences. This typically at least squares the number of pairs required to achieve a result.

The best input differences for attacking the ICE F-function are b2d6b2d6 and cad6cad6, both of which produce a zero output difference with probability 4320/240. They can be combined into 5-round characteristics which have a probability of 2-55.85, and it is these characteristics that may be able to break Thin-ICE, which is an 8-round cipher.

Linear cryptanalysis

None of the ICE variants appear to be breakable by linear cryptanalysis. Even Thin-ICE, the weakest variant, seems to need over 282 encryptions to be reliably broken, but since it is only a 64-bit cipher, there aren't that many plaintexts available. DES can be broken with approximately 243 encryptions.

The resistance of ICE to linear cryptanalysis is due to the larger S-boxes, and to the keyed permutation, which roughly squares the effort otherwise required.

Related-key cryptanalysis

This attack relies on simple relations between subkeys in adjacent rounds. ICE is not susceptible to this attack because it uses an irregular key rotation schedule, meaning that there is no consistent relationship between subkeys. DES is also resistant to this attack.

Meet-in-the-middle attacks

If you encrypt data twice, with two different keys, you usually find yourself susceptible to a meet-in-the-middle attack. That is why Triple-DES is used instead of double encryption, despite the factor of three speed penalty.

ICE avoids this weakness in its extended variants by extending the key schedule with insertions in the middle of the schedule. Although ICE-n effectively encrypts the data n times with n different 64-bit keys, it does this not by encrypting with one key after another, but by doing half encryptions (i.e. the first 8 rounds) n times, then doing the second halves n times.

Codebook reconstruction attacks

It must be remembered that any 64-bit cipher can be broken under a chosen-plaintext attack in 264 time and memory by simply constructing a lookup table of all 264 possible plaintext/ciphertext pairs. This is regardless of the key size and how well the cipher has been designed.

So it must be remembered that although the strength of ICE-n under ciphertext-only attacks is probably 264n, the strength of all ICE variants under chosen-plaintext is, at best, 264.