ICE Design Decisions

This section is an attempt to explain, fairly briefly, why certain design decisions were made.

The Feistel structure

The Feistel structure, as used by DES and LOKI to name but a few, has a number of advantages.

• It is guaranteed to carry out one-to-one mappings, which is kind of essential if you want your ciphertext to be decryptable. Since this is taken care of automatically by the structure, it enables a designer to concentrate on more important things, like security.
• Feistel ciphers have been publicly cryptanalysed for more than two decades, and no systematic weaknesses have been uncovered. In addition, the techniques that have been used to analyse existing ciphers are generally applicable to new ones, so the designer isn't forced to traverse completely uncharted waters.
• Feistel ciphers a reasonably fast and simple to implement in both hardware and software.

The 64-bit block and key size

The 64-bit block size and default 64-bit key size were chosen for a variety of reasons.

• To maintain compatability with DES. There are probably thousands of DES applications out there, and maintaining the same interface will simplify the task of porting to ICE, should anyone try to do so.
• The default key size is the same as the block size so that plaintexts or ciphertexts can be used as keys if needed. This might be useful when designing hash functions or something.
• The strength of a 64-bit block cipher under a chosen-plaintext attack is always 2⁶⁴ time and memory, by simply storing all 2⁶⁴ plaintext/ciphertext pairs in a lookup table. Using a larger key size may give a false sense of security.
• The author couldn't think of a fast, secure way to implement a 128-bit block cipher using the Feistel structure.

Keyed Permutation

This is one of the few original ideas incorporated into ICE, so the reasoning will be explained in a bit more detail. The inspiration for the use of keyed permutation comes from the salt value in the Unix password encryption function, crypt(3), designed by Ken Thompson and Denis Ritchie at AT&T Bell laboratories.

From an aesthetic point of view it has a certain consistency. The cornerstone of block cipher design has been the use of substitution and permutation networks to encrypt data. Keyed substitution, usually in the form of XORing key bits with an S-box input, has been commonly used, and it is felt that keyed permutation should complement this nicely.

To begin with, keyed permutation gives ICE immunity to complementation weaknesses. These result from situations where key and plaintext bits are inverted, but cancel each other out at the inputs to the S-boxes, causing the S-boxes to produce identical outputs. However, if key bits are inverted in ICE, the S-boxes will receive their inputs from totally different bits, and thus not regularly produce identical outputs.

A great challenge to cryptosystem designers has been resistance to differential cryptanalysis. Although the keyed permutation used in ICE doesn't grant immunity to differential cryptanalysis, it does greatly reduce its effectiveness.

Differential cryptanalysis relies an attacker sending XOR differences to the inputs of S-boxes, where the S-boxes will then produces an XOR difference as output with some probability. But because these input bits are being permuted in ICE, the attacker does not know which S-box will receive the bit.

An attacker can bypass the keyed permutation by using input differences whose leftmost 16 bits are the same as the rightmost 16 bits (called symmetric inputs), but this means the attacker now has to target at least two S-boxes at a time, so the probability of success is typically squared or worse.

Similarly, linear cryptanalysis is forced to use symmetric inputs, again with much lower probabilities.

The S-boxes

The S-boxes in ICE were primarily designed to be resistant to differential cryptanalysis, and in particular to symmetric attacks. The way the S-boxes are generated, from 16 offsets and 16 primes, was chosen so that the boxes were parameterised. This enabled software to automate the generation and evaluation of millions upon millions of different possible S-boxes.

In an ideal world, every possible Galois Field prime and XOR offset would be tried, and the resulting S-boxes evaluated. However, with 30 Galois primes to try in 16 positions, and 16 8-bit offsets to choose, this would require more than 10⁷¹ evaluations. As result, the selection process was done in incremental steps.

• Choose primes so that when S-boxes are attacked via the 6 input bits that are unique to them, the XOR profile has the lowest possible peak probability.
• Given that 509 groups of four primes have the same peak probabilities, pairs of groups were chosen using following rules
  • No pair could share a prime in common.
  • The product of probabilities for the same input difference should be as low as possible.
• The XOR offsets in each S-box were selected to minimise the probability of an input difference producing a zero output difference, and consequently to minimise the probability that a symmetric input difference would produce a zero output difference.
• 4096 sets of XOR offsets had the same probabilities, so the set was chosen which had the lowest probability of a symmetric input difference producing itself as output.

With respect to differential cryptanalysis, it makes no difference if all the XOR offsets in a row are XORed with a constant, or if the positions of the primes are XORed with a constant, so there were still 1024 choices available for each S-box. None of these choices would have any effect on differential (and, it turns out, linear) cryptanalysis, so some new, and increasingly arbitrary, criteria were used to narrow down the choice of parameters.

• There should be no x where F(x) = 0, assuming a zero subkey. If F in all rounds produces zero outputs, then a plaintext would encrypt to itself.
• There should be no x where F(x) = x.
• The sum of the bit count of F(x) XOR x over all symmetric x values should be perfectly balanced (i.e. equal to 1048576).
• Finally there were 16 sets of values to choose from. They were evaluated for the bitcount of F(x) for all 32 single-bit x values. None gave the balanced value of 512, but the closest was 506, which was then chosen as the set of primes and offsets for the S-boxes.

The Key Schedule

ICE has been designed with an extensible key schedule to permit a tradeoff between speed and security. The following design criteria were used for all the ICE variants.

• There must be no weak keys. In other words, for a given key, there must not be another key that generate the same key schedule, but in the reverse order.
• Minimal key complementation weaknesses. Although keyed permutation makes this attack impossible, the schedule was design so that there was only a single key complementation weakness.
• Each subkey bit should only be dependent on only one key bit. This simplifies the proof that the above two conditions are satisfied.
• No meet-in-the-middle attacks. This means that, for any round N, all key bits must be used either in the preceeding rounds, or all must be used in the following rounds.
• Since the F function makes use of 60 key bits per round, in the ICE and the ICE-n ciphers each key bit must be used 15 times, once in every 4-bit block. For Thin-ICE, every key bit must be used 7 or 8 times, 2 or 3 times in every 20-bit block.
• Immunity to related-key cryptanalysis. This means some sort of irregularity in the key schedule.
• The key scheduling algorithm must be simple to implement in software, yet not too fast, so as to hinder exhaustive key searches.