Problem 3
Skipjack
specification in HTML
Problem 4
1. In public key cryptosystems the encryption box is given to
everyone
(and that is what you are given as an attacker), and the decryption
box
is accessible only to the owner of the private key.
2. By Linear Transform we mean an
invertible linear transform over {GF2}^n.
T(X) =
Y,
T:
{GF2}^n-> {GF2}^n.
In other words Y can be expressed
as a system of n linear equations
with n variables x_i, i=1,..,
n
over GF2 (linearly independent equations, in order to provide a unique
solution).
An equivalent form is to say: Y = M *X, where M is an invertible 0-1 matrix.
Examples:
a) Permutation of bits is a simple linear transform
b) XOR of X with a cyclically rotated
version of itself is a linear transform
c) The 64-bit input block X is
viewed as a 64-dimensional vector (x_0, .., x_63),
x_i in {0,1}. The 64-bit output block Y
is a 64-dimensional vector (y_0, .., y_63), y_i
in
{0,1}.
y_1 = x_1 + x_3 + x_17 + x_63
y_2 = x_2 + x_7 + x_8 + x_22 + x_ 38
....
y_63 = x_7 + x_24 + x_33 + x_56
These equations are written over GF2 (i.e. mod 2) , + and XOR operations are equivalent in this field.
d) Here is a linear transform from AES cipher Serpent.
3. Please note that the S-boxes and linear transforms in the first and second layers are different.
Problem 1
There was a minor bug in S-box S7:
S(100100) = 9 = S(100101).
in violation of DES design principle "one
bit difference must cause difference in at least two output bits".
The entries 9 an 3 of the last row of S7 must be swapped.
See here
(or on the homework page) the corrected table.
(new 20.06.2000)
Problem 1
It is sufficient to multiply the entries of the
Difference Distribution Tables
for adjacent S-boxes in order to estimate
the probabilities and not to study the exact values of the adjacent
inputs. This is true since all the differential analysis is done on average
over all possible pairs with the certain fixed difference and over all
possible keys.
This is a subtle and important point, if you want to understand it better
you can
read Definition 5, Lemma 1 and Corollary, on page 18 in the
on-line book version, or page 21 in the printed book (this page was
given with the first handout on DC). A closely related issue is that of
"enchanced characteristic probabilities" (page 54 in the on-line book,
and 46 in the printed version).
You may also read the paper below (its section 5):
Lars Knudsen,
Iterative
characteristics of DES and s^{2}-DES.
Advances in Cryptology - Crypto'92. Springer Verlag, Lecture Note Series
746, pp. 497-511, Berlin Heidelberg 1993.
"...Finally we examine the
probabilities of the two characteristics used by Biham and Shamir. We found
that for some keys we do not get the probabilities used in the attack...."
Problem 3
The aim of this exercise is to train you on analysis of new cipher
constructions (not necessarily DES-like). Compared with DES, in Skipjack
the avalanche is about 2 times slower and thus 16 rounds of SJ are similar
to 8 rounds of DES, so it is a weak cipher.
The second aim was to show a cipher that works with bytes and not bits, and thus more generic "differential" approach to the analysis is possible. Consider input differences with some (but not fixed) difference in one of the 16-bit words and zero difference in the other 3 input words. See if you can pack data into structures efficiently, see if some nR-attack can chop the rounds from the end of the cipher. See if some first round trick can gain you one-two of the first rounds.
In question (A) I would expect complexity about O(2^16)
but if you can find
attacks below O(2^32) it would be considered as a good progress.
In question
(B) better results are expected.
Problem4
Here complexity O(2^32) is enough.