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