Mini-DES 6-Bit Blocks
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.
The Solution:
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.
|
