From msuinfo!agate!boulder!tigger!bear Mon May 24 13:18:23 1993 Newsgroups: sci.crypt Path: msuinfo!agate!boulder!tigger!bear From: bear@tigger.cs.Colorado.EDU (Bear Giles) Subject: Analysis of S-boxes (Cryptology final exam problem) Message-ID: <1993May19.041656.18907@colorado.edu> Sender: news@colorado.edu (The Daily Planet) Nntp-Posting-Host: tigger.cs.colorado.edu Organization: National Oceanic & Atmospheric Adminstration / Boulder Labs Date: Wed, 19 May 1993 04:16:56 GMT Lines: 95 Reprinted, with permission, from my final exam in cryptology. This was one of three problems in a 3-hour exam, so it should only take you 1 to 1-1/2 hours to solve. But it illustrates an interesting attack.... ---- The following "mini-DES" uses 6-bit blocks of data (see code table below) and 9 bits of key (the 9 bits are independent. It has the following structure: L' = R R' = L + S (R + K) where S is input output 000 011 001 111 010 000 011 100 100 101 101 001 110 110 111 010 where there are three stages in this algorithm. The code table is: 000000 space 001000 H 010000 P 011000 X 000001 A 001001 I 010001 Q 011001 Y 000010 B 001010 J 010010 R 011010 Z 000011 C 001011 K 010011 S 011011 0 000100 D 001100 L 010100 T 011100 1 000101 E 001101 M 010101 U 011101 2 000110 F 001110 N 010110 V 011110 3 000111 G 001111 O 010111 W 011111 4 100000 . 101000 h 110000 p 111000 x 100001 a 101001 i 110001 q 111001 y 100010 b 101010 j 110010 r 111010 z 100011 c 101011 k 110011 s 111011 5 100100 d 101100 l 110100 t 111100 6 100101 e 101101 m 110101 u 111101 7 100110 f 101110 n 110110 v 111110 8 100111 g 101111 o 110111 w 111111 9 Example: Encode 'f' using key K = { 110, 101, 100 } L0, R0 = 100, 110 L1, R1 = 110, 111 L2, R2 = 111, 110 L3, R3 = 110, 111 Problem: Decipher the following: cvxrUXkl (That is, 100011 110110 111000 111011 010101 011000 101011 101100)) The following pairs are known: e -> 0 100101 -> 011011 t -> 5 110100 -> 111011 a -> Q 100001 -> 010001 o -> U 101111 -> 010101 space -> 2 000000 -> 011101 (b) Why is this system so weak? Could the security be improved by using more rounds (but all other things unchanged)? What is your suggestion to improve the security? Explain! Hints: Do all computations in GF(2^3) : { 001, 010, 100, 011, 110, 111, 101 } (GF(2^3)/x^3+x+1). Express S as a y = f(x) = ax + b Use the recursions for R' and L' to explicitly compute L3 = g(L0, R0, K0, K1, K2) R3 = h(L0, R0, K0, K1, K2) Use the knowledge about the S-box and known plaintext/ciphertext pairs to determing g and h. Decipher the given ciphertet. For the solution, finger my academic account (bear@tigger.cs.colorado.edu) Have fun! -- Bear Giles bear@cs.colorado.edu/fsl.noaa.gov From msuinfo!agate!howland.reston.ans.net!darwin.sura.net!news.dfn.de!news.belwue.de!news.uni-stuttgart.de!rz.uni-karlsruhe.de!stepsun.uni-kl.de!uklirb!posthorn!vier!neuhaus Mon May 24 13:18:24 1993 Newsgroups: sci.crypt Path: msuinfo!agate!howland.reston.ans.net!darwin.sura.net!news.dfn.de!news.belwue.de!news.uni-stuttgart.de!rz.uni-karlsruhe.de!stepsun.uni-kl.de!uklirb!posthorn!vier!neuhaus From: neuhaus@vier.informatik.uni-kl.de (Stephan Neuhaus (HiWi Mattern)) Subject: Re: Analysis of S-boxes (Cryptology final exam problem) Message-ID: Sender: news@posthorn.informatik.uni-kl.de (News system account) Nntp-Posting-Host: vier.informatik.uni-kl.de Organization: University of Kaiserslautern, Germany References: <1993May19.041656.18907@colorado.edu> Date: Fri, 21 May 1993 08:33:19 GMT Lines: 80 Solved! This took me somewhat more than 3 hours, because I had totally forgotten how to do arithmetic in GF(2^3), and had to create a multiplication table. There is an error in the original problem, because the `r' in the ciphertext should be a `5'. Anyway, the solution follows. If you don't like your fun spoiled, hit `n' now. (And I hope the ^L makes it.) You sense the presence of spoilers --more-- The plaintext is "Victory." The key is any of K0 K1 K2 --------------- 000 011 101 001 111 100 010 000 111 011 100 110 100 101 001 101 001 000 110 110 001 111 010 010 The S-box can be written as S(x) = 100x + 011. The relation between L3, R3 and L0, R0, K0, K1, K2 is L3 = 100L0 + 111R0 + 110K0 + 100K1 + 100 R3 = 111L0 + 101R0 + 001K0 + 110K1 + 100K2 + 110 from which you get, with one plaintext/ciphertext pair, 111 = 110K0 + 100K2 011 = 001K0 + 110K1 + 100K2 and the reverse relation from substituting any key from the above table is L0 = 101L3 + 111R3 + 010 R0 = 111L3 + 100R3 Only one plaintext/ciphertext pair was needed for the solution, but the others were helpful in verifying some of the intermediate results. I have used my own notation here, not the one in Bear Giles' .plan. A number like 101 means the polynomial 1x^2 + 0x + 1. The system is so weak because the S-box is a linear function in GF(2^3). Composition of linear functions gives another linear function. More rounds won't help, since the resulting function will still be linear. Neither increasing nor decreasing the rank of the coefficient matrix will help, because all solutions (keys) are equivalent and will solve the cryptogram. Suggestions: a) Use the cipher in stream mode; otherwise, it's a simple monalphabetic which can be solved without arithmetic in GF(2^3) with a moderate amount of plaintext b) Use a nonlinear S-box c) Use longer keys (9 bits is too short) d) Use a more complicated key schedule, reusing key bits Suggestions b) and d) together will make an attack as the one used to break this particular system fail, and suggestion c) is needed to make exhaustive search infeasible, and suggestion a) should make it harder to get at plaintext/ciphertext pairs. Have fun. -- Stephan sig closed for inventory. Please leave your pickaxe outside. PGP 2.2 public key available on request. Note the expiration date. From msuinfo!agate!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!csn!boulder!tigger!bear Mon May 24 13:18:24 1993 Newsgroups: sci.crypt Path: msuinfo!agate!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!csn!boulder!tigger!bear From: bear@tigger.cs.Colorado.EDU (Bear Giles) Subject: Re: Analysis of S-boxes (Cryptology final exam problem) Message-ID: <1993May21.183652.2674@colorado.edu> Sender: news@colorado.edu (The Daily Planet) Nntp-Posting-Host: tigger.cs.colorado.edu Organization: National Oceanic & Atmospheric Adminstration / Boulder Labs References: <1993May19.041656.18907@colorado.edu> Date: Fri, 21 May 1993 18:36:52 GMT Lines: 67 In article neuhaus@vier.informatik.uni-kl.de (Stephan Neuhaus (HiWi Mattern)) writes: >Solved! > >This took me somewhat more than 3 hours, because I had totally >forgotten how to do arithmetic in GF(2^3), and had to create a >multiplication table. I thought I included a power table in the original post.... (Of course, the notation may have been too terse unless you knew what you were looking at). >There is an error in the original problem, because the `r' in the >ciphertext should be a `5'. I'll try to remember to check this when I get home tonight (notes are at home; I leave on vacation tomorrow). If I did make a transcription error, I apologize. (After bitching about how most of our problems set had at least one typo in them this would be _extremely_ embarassing!) >Anyway, the solution follows. If you don't like your fun spoiled, hit >`n' now. (And I hope the ^L makes it.) BTW, you didn't need to figure out the possible keys to decrypt the message. I started to, then realized it wasn't important -- the system could be cracked without knowing the key(s). >The S-box can be written as S(x) = Yes >The relation between L3, R3 and L0, R0, K0, K1, K2 is > > L3 = ... > R3 = ... Yes. >from which you get, with one plaintext/ciphertext pair, >... >and the reverse relation from substituting any key from the above >table is >... Yes. I used matrix notation, but this is equivalent. >I have used my own notation here, not the one in Bear Giles' .plan. A >number like 101 means the polynomial 1x^2 + 0x + 1. I was using the smallest positive power of a particular solution to a polynomal in GF(2^3). It makes multiplication much simplier -- you just add the exponents modulo phi(2^3). Your notation requires a full multiplication table -- easy in GF(2^3), not so easy in GF(2^8). >The system is so weak because... Yes. >Have fun. I actually did have fun on this problem. Very strange, since it was on my final... :-) Of course, I did get an "A" in the class. -- Bear Giles bear@cs.colorado.edu/fsl.noaa.gov