From dawagner@phoenix.princeton.edu Fri Sep 1 16:17:33 EDT 1995
Article: 39290 of sci.crypt
Path: cnn.Princeton.EDU!phoenix.princeton.edu!dawagner
From: dawagner@phoenix.princeton.edu (David A. Wagner)
Newsgroups: sci.crypt
Subject: NSEA
Date: 1 Sep 1995 20:17:03 GMT
Organization: Princeton University
Lines: 63
Message-ID: <427pnv$d7u@cnn.Princeton.EDU>
NNTP-Posting-Host: phoenix.princeton.edu
I just happened upon NSEA randomly, and thought I should warn people
that it looks very insecure. (Maybe this is already well-known.)
NSEA is a GUFN: the F function selects 16 bits from the control block,
munges them with two 8 bit -> 8 bit key-dependent S-boxes, and xors
the output into 16 bits of the target block. Each round applies F,
then rotates by 16 bits. NSEA has a 128 bit block and uses 16 rounds.
Each byte of the ciphertext is a plaintext byte xor-ed with 2 S-box
output bytes.
[ My earlier post listed an incorrect attack here. I cancelled it.
My bad! If it makes it to your site, disregard it... ]
So here's a differential attack. Fix 120 bits of the plaintext,
and vary only the byte x which enters the first S-box S_1 in round
8; let P_x denote such a plaintext. Obtain P_x for all 256 values
of x via a chosen ciphertext attack.
Now consider any difference byte d. There will be 256 plaintext
pairs P_x, P_{x^d} with difference d entering S_1 in round 8.
A right pair is one where d -> 0 in round 8. A right pair can
be recognized because the ciphertexts will differ in at most 16
bits (if d -> e in round 16, then the two non-zero bytes will
be d and e). Out of the 256 plaintext pairs P_x, P_{x^d} we
expect to get ~ 1 right pair. Now note that each right pair
gives us information of the form
S_1[a] ^ S_1[a'] = e (*)
where a, a' are ciphertext bytes entering S_1 in round 16 (so
in fact a ^ a' = d) and e is a byte of the ciphertext differential.
Since there are 256 possible differences d, we expect to get
about 256 relations of the form (*). Here's how to use those
relations to deduce the entries in the first S-box. Interpret
the relations (*) as a graph: the vertices are the S-box input
values, and there's an edge between two vertices a,a' if we have
a (*) relation i.e. if S_1[a] ^ S_1[a'] is known. Notice that
if there's a path between a and a'' in the graph then we know
S_1[a] xor S_1[a'']: say the path is through a', so
S_1[a] xor S_1[a'] = A
S_1[a'] xor S_1[a''] = A'
are known relations, so we can conclude that
S_1[a] xor S_1[a''] = A xor A'.
Suppose the graph for the first S-box has just one connected component
(which will happen with significant probability: if it doesn't
happen, just use another structure of 256 chosen plaintexts to
get more relations). Then we know S_1[a] xor S_1[a'] for all
a != a' (because there there is a path between a and a' for all
a != a'). Guess the value of S_1[0]; then we can derive the rest
of S_1.
Repeat with another 256 chosen plaintexts to derive S_2. Then
test the guesses of S_1[0] and S_2[0] with ~ 2^16 trial encryptions.
Thus this simple attack breaks NSEA with ~ 512 chosen plaintexts
and ~ 2^16 trial encryptions. The attack is probably not optimal,
but it's enough to demonstrate that NSEA is insecure.
To protect NSEA against these types of attacks, NSEA needs (at a
minimum) ~ 64 rounds, and needs much more diffusion in each round.
-------------------------------------------------------------------------------
David Wagner dawagner@princeton.edu