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