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-stuttg.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-stuttt.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: <neuhaus.737973199@vier>
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 <neuhaus@informatik.uni-kl.de>
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 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> <neuhaus.737973199@vier>
Date: Fri, 21 May 1993 18:36:52 GMT
Lines: 67

In article <neuhaus.737973199@vier> neuhaus@vier.informatik.uni-kl.de (Stephan Neuhaus (HiWi Matternwrites:
>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