description.html
b3289dd5687a1b5dbbf290eb61c899c3442ccd6b533be7aa79e85f0181fd3fd3
<HTML>
<HEAD> <TITLE>The ICE Algorithm</TITLE> </HEAD>
<BODY BGCOLOR="#d8d8d8" TEXT="#000080" LINK="#0000FF">
<H1> The ICE Algorithm </H1>
<P>
This document gives a brief description of the internals of the ICE
algorithm. It is assumed that the reader is reasonably familiar with
block ciphers, and in particular with DES. If all else fails, the
source code may provide a more useful reference. </P>
<P>
The algorithm is also described in more detail in a
<A HREF="paper.html">paper</A> presented at the 4th Fast Software
Encryption Workshop in Haifa Israel in 1997. However, the paper is
only available in postscript form. </P>
<H3> The Structure </H3>
<P>
ICE is a standard Fiestel block cipher, as illustrated below.
It takes a 64-bit plaintext, which is split into two 32-bit halves.
In each round the right half and a 60-bit subkey are fed into the
F-function. The output of F is XORed with the left half, then the
halves are swapped. This is repeated for all but the final round,
where the final swap is left out. </P>
<P>
The number of rounds is determined by the level of the variant
in use. Level 0 (or Thin-ICE) uses 8 rounds, while higher levels
<EM>n</EM> use 16<EM>n</EM> rounds. </P>
<CENTER><IMG SRC="feistel.gif"></CENTER>
<H3> The F Function </H3>
<P>
This is best described by the illustration below. </P>
<CENTER><IMG SRC="f-func.gif"></CENTER>
<P>
This is very similar to the function used in DES, except for the use
of keyed permutation, controlled by a 20-bit subkey in each round.
Basically, these 20 bits determine the path that will be taken
by the bits leaving E1, E2, E3, and E4. If a bit in the subkey is
set, then the corresponding bit from E1 or E2 will be swapped with
a bit from E3 or E4 respectively. If the subkey bit is not set, then
the bits will continue unimpeded. </P>
<P>
This keyed permutation is basically doing the same thing as the
<EM>salt</EM> value in the Unix crypt(3) command, except that the
salt here is 20 bits instead of 12, and is derived from the secret
key in each round rather than being fixed and publicly known. </P>
<P>
The S-boxes take 10-bit inputs and produce 8-bit outputs. The leftmost
and rightmost bits of the input are concatenated to produce a 2-bit
row selector <EM>R</EM>. The middle 8 bits form the column selector
<EM>C</EM>. For each row <EM>R</EM>, there is an XOR offset <EM>O</EM>
and a Galois Field prime <EM>P</EM>. The 8-bit output of the S-box is
given by </P>
<CENTER> (<EM>C</EM> xor <EM>O</EM>)^7 mod <EM>P</EM> </CENTER>
<P>
under 8-bit Galois Field arithmetic. This is probably better described
in the <A HREF="ice.c">source code</A>, which also lists the 16
XOR offsets and Galois Field primes used to select <EM>O</EM> and
<EM>P</EM>. </P>
<P>
The outputs of the S-boxes are permuted to a 32-bit value via a P-box.
The P-box has been designed to maximize diffusion from each S-box, and
to ensure that bits which are separated by 16 places never come from
that same S-box, nor from S-boxes separated by two places (eg. S1 and S3).
Given that these criteria were met, the P-box was also designed to be as
regular as possible. </P>
<H3> The Key Schedule </H3>
<P>
Again, it is probably best to refer to the source for a comprehensive
explanation. However, a brief description of the key schedule for
the various ICE variants is as follows. </P>
<UL>
<LI> Level 0 (Thin-ICE) simply uses the first 8 rounds of the standard
ICE schedule (level 1).
<LI> Level 1 uses a 16 round schedule, derived from 64 key bits.
Each round makes use of 60 bits, so each key bit is used 15 times.
Between rounds the bits are permuted, and after every time a key bit
is used it gets inverted.
<LI> Higher levels of ICE extend the key schedule from the level below
them. They do this by taking the key schedule, breaking it at the
half-way point, and inserting an extra 16 rounds in the middle.
These new 16 rounds use the standard ICE schedule, derived from the
next 64 bits of key.
</UL>
</BODY>
</HTML>