design.html
4fc0a89b6bb377332b0e6fc28f2a97aebe4b815e5a05b062a9db6551c0f26be0<HTML>
<HEAD> <TITLE> ICE Design Decisions </TITLE> </HEAD>
<BODY BGCOLOR="#d8d8d8" TEXT="#000080" LINK="#0000FF">
<H1> ICE Design Decisions </H1>
<P>
This section is an attempt to explain, fairly briefly, why certain
design decisions were made. </P>
<H3> The Feistel structure </H3>
<P>
The Feistel structure, as used by DES and LOKI to name but a few,
has a number of advantages. </P>
<UL>
<LI> 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.
<LI> 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.
<LI> Feistel ciphers a reasonably fast and simple to implement in
both hardware and software.
</UL>
<H3> The 64-bit block and key size </H3>
<P>
The 64-bit block size and default 64-bit key size were chosen for
a variety of reasons. <P>
<UL>
<LI> 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.
<LI> 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.
<LI> The strength of a 64-bit block cipher under a chosen-plaintext
attack is always 2<SUP>64</SUP> time and memory, by simply storing
all 2<SUP>64</SUP> plaintext/ciphertext pairs in a lookup table.
Using a larger key size may give a false sense of security.
<LI> The author couldn't think of a fast, secure way to implement a
128-bit block cipher using the Feistel structure.
</UL>
<H3> Keyed Permutation </H3>
<P>
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. </P>
<P>
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. </P>
<P>
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. </P>
<P>
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. </P>
<P>
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. </P>
<P>
An attacker can bypass the keyed permutation by using input differences
whose leftmost 16 bits are the same as the rightmost 16 bits (called
<EM>symmetric</EM> 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. </P>
<P>
Similarly, linear cryptanalysis is forced to use symmetric inputs, again
with much lower probabilities. </P>
<H3> The S-boxes </H3>
<P>
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. </P>
<P>
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<SUP>71</SUP> evaluations.
As result, the selection process was done in incremental steps.
<UL>
<LI> 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.
<LI> Given that 509 groups of four primes have the same peak
probabilities, pairs of groups were chosen using following rules
<UL>
<LI> No pair could share a prime in common.
<LI> The product of probabilities for the same input difference should
be as low as possible.
</UL>
<LI> 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.
<LI> 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.
</UL>
<P>
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. </P>
<UL>
<LI> 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.
<LI> There should be no x where F(x) = x.
<LI> 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).
<LI> 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.
</UL>
<H3> The Key Schedule </H3>
<P>
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. </P>
<UL>
<LI> 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.
<LI> 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.
<LI> Each subkey bit should only be dependent on only one key bit. This
simplifies the proof that the above two conditions are satisfied.
<LI> 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.
<LI> 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.
<LI> Immunity to related-key cryptanalysis. This means some sort of
irregularity in the key schedule.
<LI> The key scheduling algorithm must be simple to implement in software,
yet not too fast, so as to hinder exhaustive key searches.
</UL>
</BODY>
</HTML>
© 2024 Packet Storm. All rights reserved.
%7Cutmcsr%3D(direct)%7Cutmcmd%3D(none)){kind=small}
Follow us on Twitter
Follow us on Facebook
Subscribe to an RSS Feed