From dawagner@flagstaff.princeton.edu Tue Jul 18 12:49:41 EDT 1995
Article: 37432 of sci.crypt
Path: cnn.Princeton.EDU!flagstaff.princeton.edu!dawagner
From: dawagner@flagstaff.princeton.edu (David A. Wagner)
Newsgroups: sci.crypt
Subject: Re: ZAES: algorythm by Timur Zambalaev
Date: 18 Jul 1995 15:20:15 GMT
Organization: Princeton University
Lines: 148
Message-ID: <3ugjff$m21@cnn.Princeton.EDU>
References: <3uadej$q8n@mx.nsu.nsk.su>
NNTP-Posting-Host: flagstaff.princeton.edu
Cc: yjj@math.nsk.su
In article <3uadej$q8n@mx.nsu.nsk.su>,
Yuri Zholobov Jr. wrote:
>
> He asks all you (if you have some interest and spare time)
> to take part in testing and exploration of ZAES weeknesses.
>
I took a look at it and thought about it during my ride home yesterday.
(I hate traffic!)
The basic idea looks sound, though the specifics of the design need a
bit more work.
Here's the idea, for those of you who haven't seen the algorithm. It
has a 128 bit blocksize and keylength. To encipher P[0..15] under key
K[0..15], do: (here P[i] is the i-th byte of the plaintext, etc.)
1. choose perm[0..15] (a permutation of {0,...,15}) from K[]
2. for i=0,...,15 do X[i] = g(P[i], K[i])
3. for i=0,...,15 do
t = perm[i]; X[t] = F(X[0..t-1], X[t], X[t+1..15])
4. for i=0,...,15 do C[i] = g(K[i], X[i])
Here g : {0,...,255} x {0,...,255} -> {0,...,255} is a fixed public
function; and its invertible when you hold one coordinate fixed.
The round function F() repeatedly folds the first and third input
using g, and then combines them, so F(a, C[t], b) = g(g(a, C[t]), b).
In other words, this is much like Schneier & Blaze's GUFN (generalized
unbalanced Feistel network): the round function affects only one byte
of the block, instead of half of it. There is one major difference
between ZAES & the GUFN architecture S&B envisioned, though: no key
dependence enters the ZAES round function F().
Anyhow, ZAES needs more rounds. Note that any ciphertext byte is
affected by only one round. (This would be analogous to only using
2 rounds in DES! And in fact, it does turn out to be about as weak.)
We have the following chosen plaintext attack on ZAES:
Choose three different values for P[t], and hold P[0..t-1] and P[t+1..15]
fixed. Ask for the encryption of those three chosen plaintexts. You
know that
C[t] = g(K[t], F(a, g(P[t], K[t]), b))
where a and b are folded versions of X[0..t-1], X[t+1..15] in some round.
Note that P[t], C[t] are different for each plaintext/ciphertext pair,
yet K[t], a, and b are fixed. Guess K[t] and a; each is a byte, so there
are only 2^16 guess to check. Infer b from the first pair (which the
invertability of g lets us do), and check K[t], a, and b on the second
two pairs. With high probability, only the correct guess will survive.
This gives you one key byte. Do this for each t; after 48 chosen
plaintexts and 2^20 off-line computations, you will have recovered
the entire key.
You really need each ciphertext byte to be mangled by at least 3 rounds;
with DES, each ciphertext byte is affected by 8 rounds. I'd recommend
increasing the number of rounds in ZAES to at least 64.
Also, note that there is very little key dependence entering each ZAES
round: there are only 16! ~= 2^44 possible permutations, and perm[i] is
the only key-dependent variable entering round i. Steps 2 and 4 are
where the key mostly enters.
So in some sense, this encryption algorithm is similar to one recently
proposed on sci.crypt.research: E(k,p) = k xor h(k xor p), where h is a
strong public permutation. The problem with this approach (as discussed
on sci.crypt.research) is that there are lots of complementation properties
which can speed up brute force search (and also make life hard for those
who want to make a hash mode from the block cipher).
Because the ZAES h() actually depends on perm[], there aren't quite
as many complementation properties as you might at first expect; also,
ZAES uses g() as its binary combining operation instead of xor. Still,
g() doesn't provide much diffusion, and there are definitely complementation
properties left. This looks like an unnecessary weakness.
In fact, it's worse than that. There's an efficient related key attack
on ZAES; I think it'll work no matter how many rounds you use.
ZAES generates perm[] in step 1 by using the classic elegant swapping
algorithm to generate a permutation from plain random bytes. This is
fine. But note one artifact of the algorithm:
If we let K'[15] = K[15] + 16, and K'[0..14] = K[0..14], then those
two keys will generate the same perm[] permutation. In general, if
K'[i] == K[i] mod i+1 for i=0,...,15
then K and K' will generate the same permutation.
Here's how to exploit that. Again let K'[15] = K[15] + 16 and
K'[0..14] = K[0..14]. Fix P[0..14]. Choose 16 values c_0, ..., c_15
for P[15] and encipher each plaintext under K; then choose 16 more
values d_0, ..., d_15 for P[15] and encipher each under K'. If we're
lucky, there will be two values c_i, d_j such that
g(c_i, K[15]) = g(d_j, K'[15]). (*)
Then after step 2, the X[] array will be the same whether or not
we encrypt P[0..14],c_i with key K or encrypt P[0..,14],d_j with
key K'; since perm[] is the same either way, after step 3 the X[]
array will still be the same either way. In this case, we will
have
g(K[15], X_i[15]) = C_i[15] = C'_j[15] = g(K'[15], X'_j[15])
= g(K[15] + 16, X_i[15])
in step 4; then we can guess K[15], invert up through g two ways,
and check whether the second coordinates match as they're supposed
to. When we find the correct value of the key byte K[15], we'll
recognize it, and with high probability only it will survive.
Now note that the lucky happenstance (*) can be detected when the
two ciphertexts match in all but byte 15; we already showed that
when we see it, we can exploit it to find one byte of the key.
Also, by the birthday paradox, (*) should happen for some i,j pair
with significant probability (since 16^2 = 256). Thus we can get
one key byte with 1 related key query & 2*16 chosen plaintexts.
[ Actually, I lied a bit: for some key values, e.g. K[i] > 256-i-1,
letting K'[i] = K[i] + i+1 won't work since K'[i] will wrap around;
but this doesn't happen often, and when it does it can be remedied
easily by letting K'[i] = K[i] - (i+1). ]
Finding the whole key requires a total of 32 related key queries,
16*2*16 = 512 chosen plaintexts, and about 2^20 computations in
this attack. You can also combine all the related key queries,
so you only need 1 related key query to get the whole key (but still
using the same # of chosen plaintexts, etc.).
Note that adding more rounds probably won't help against this attack
if you use the same type of key scheduling; each round really needs
more key dependence entering it.
So my two recommendations: add more rounds, and add more key dependence
into each round. Other than that, it looks like a good start.
David Wagner