Cryptography - Lecture 10 - Recent Block Ciphers

This lesson continues with descriptions of more recent block ciphers, including LOKI, IDEA, RC5 and the AES cipher.

1. LOKI

LOKI is a cipher designed at ADFA
from PhD by Dr Brown under Profs Seberry & Pieprzyk
from detailed analysis of DES, and work on S-box design
original version known as LOKI89
designed tweaked following analysis to form LOKI91
LOKI intended to be compatible with DES
hence uses 64-bit data and a 64-bit key
design criteria were to be published for critique

2. Overall LOKI91 Structure

3. LOKI Design

overall design is based on detailed analysis of DES:
- permutation P and its role in growth of dependence of cipher bits on input bits
- permutation PC2 and key rotation schedule and its role in growth of dependence of cipher bits on key bits
design of the LOKI S-Boxes is based on the non-linearity criteria developed by Seberry and Pieprzyk
verified against known design criteria for S-boxes
aim was for structure to be as simple as possible without compromising security
LOKI is a Feistel class cipher, a form of Substitution-Permutation (S-P) network (Shannon)
provision of avalanche and completeness achieved by a two phase design
- overall structure assuming S-boxes have these properties
- S-boxes with these properties

4. LOKI Key Schedule

uses a large key rotation removing the need for PC2
with rotation values of 12 or 13 larger than S-box size
16 rounds chosen based on Biham-Shamir research in late 80's

5. LOKI Keys

LOKI Keys are 64-bit blocks, with no parity bits, which may be written in hex as hhhhhhhhhhhhhhhh₁₆
Weak, Semi-weak, and Demi-semi-weak keys are those which generate 1, 2 or 4 internal sub-keys only and which should be avoided
have just 16 weak/semi-weak keys (all word combinations of 0,5,a,f)
also have a single bit complementation property (like DES):
```
_________       _ _
LOKI(P,K)= LOKI(P,K)
```

6. LOKI Function f

7. LOKI Key Addition and Expansion E

add key bits before expansion for simplicity
E duplicates input + key bits to provide autoclaving
is based on a regular selection of overlapping groups of 12 bits
is designed to use 32-bit inputs for ease of software implementation

8. LOKI S-Boxes

a family of S-boxes with avalanche and completeness properties was used
key principle was the concept of boolean functions with maximum non-linearity, by Pieprzyk and Seberry
LOKI S-boxes were chosen to have 12 inputs and 8 outputs
partitioned into 16 row functions with 256 columns
each function is exponentiation in GF(2⁸) as follows:
```
Sfn(r,c)=(c+((r*17) XOR ff₁₆)&ff₁₆)³¹ mod gen_r
```

using the following 16 polynomials as moduli:

375 379 391 395 397 415 419 425 433 445 451 463 471 477 487 499

9. LOKI S-boxes

10. LOKI Permutation P

sends output bits from each S-box to inputs of all S-boxes in turn

generated by a difference function on the S-box number of

[+3 +2  +1  0  +3  +2  +1  0]
-----------------------------
31, 23, 15, 7, 30, 22, 14, 6,
29, 21, 13, 5, 28, 20, 12, 4,
27, 19, 11, 3, 26, 18, 10, 2,
25, 17,  9, 1, 24, 16,  8, 0

11. Security of LOKI91

Knudsen at Auscrypt92:
- confirmed there are no characteristics with high enough probability to attack LOKI91 faster than keyspace search
- showed size of image of LOKI f function is F(8,13) x 2 ^(32) significance of this is debateable
- presents chosen plaintext attack reducing exhaustive keyspace search by 4 using 2 ^(32) + 2 chosen plaintexts
Biham has presented his related key attacks
- only applicable if attacker can force rekey by pattern
seem to confirm security of LOKI91 at present
is now susceptible to exhaustive keyspace search, though harder than for DES (60-64 bits vs 56 for DES)

12. IDEA

developed by James Massey & Xuejia Lai at ETH originally in Zurich in 1990 and called IPES
was revised in 1991/2 as IDEA
encrypts 64-bit blocks using a 128-bit key
based on mixing operations from different (incompatible) algebraic groups
XOR, Addition mod 2¹⁶, Multiplication mod 2¹⁶+1
all operations are on 16-bit sub-blocks, with no permutations used, hence its very efficient in s/w
IDEA is patented in Europe & US, however non-commercial use is freely permitted
used in the public domain PGP secure email system (with agreement from the patent holders)
currently no attack against IDEA is known (it appears secure against differential cryptanalysis), and its key is too long for exhaustive search

13. Overview of IDEA

IDEA encryption works as follows:
- the 64-bit data block is divided by 4 into: X₁, X₂, X₃, X₄
- in each of eight rounds the sub-blocks are XORd, added, multiplied with one another and with six 16-bit sub-blocks of key material, and the second and third sub-blocks are swapped
- finally some more key material is combined with the sub-blocks

14. Overall IDEA Structure

15. IDEA Key Schedule

IDEA encryption subkeys are obtained by:
- splitting the 128-bits of key into eight 16-bit sub-keys
- once these are used the key is rotated by 25-bits and broken up again etc
the decryption keying material is a little more complex
must compute inverses of the ADD and MULTIPLY operations

16. IDEA Key Schedule

the keys used may be summarised as follows:

Round       Encryption Keys                   Decryption Keys
1   K1.1 K1.2 K1.3 K1.4 K1.5 K1.6   K9.1^-1 -K9.2  -K9.3  K9.4^-1  K8.5  K8.6
2   K2.1 K2.2 K2.3 K2.4 K2.5 K2.6   K8.1^-1 -K8.3  -K8.2  K8.4^-1  K7.5  K7.6
3   K3.1 K3.2 K3.3 K3.4 K3.5 K3.6   K7.1^-1 -K7.3  -K7.2  K7.4^-1  K6.5  K6.6
4   K4.1 K4.2 K4.3 K4.4 K4.5 K4.6   K6.1^-1 -K6.3  -K6.2  K6.4^-1  K5.5  K5.6
5   K5.1 K5.2 K5.3 K5.4 K5.5 K5.6   K5.1^-1 -K5.3  -K5.2  K5.4^-1  K4.5  K4.6
6   K6.1 K6.2 K6.3 K6.4 K6.5 K6.6   K4.1^-1 -K4.3  -K4.2  K4.4^-1  K3.5  K3.6
7   K7.1 K7.2 K7.3 K7.4 K7.5 K7.6   K3.1^-1 -K3.3  -K3.2  K3.4^-1  K2.5  K2.6
8   K8.1 K8.2 K8.3 K8.4 K8.5 K8.6   K2.1^-1 -K2.3  -K2.2  K2.4^-1  K1.5  K1.6
Output K9.1 K9.2 K9.3 K9.4          K1.1^-1 -K1.2  -K1.3  K1.4^-1
where:
	K1.1^-1 is the multiplicative inverse mod 2¹⁶+1
	-K1.2 is the additive inverse mod 2¹⁶
and the operations are:
    (+)	bit-by-bit XOR
    +	additional mod 2¹⁶ of 16-bit integers
    *	multiplication mod 2¹⁶+1 (where 0 means 2¹⁶ )

17. IDEA Example Encryption

#           Key (128-bits)       Plain (64-bit)   Cipher (64-bit)
7ca110454a1a6e5701a1d6d039776742 690f5b0d9a26939b 1bddb24214237ec7
idea(X=690f 5b0d 9a26 939b)
r=1, X=690f 5b0d 9a26 939b, SK=7ca1 1045 4a1a 6e57 01a1 d6d0
  steps=234a 6b52 e440 840f c70a ef5d 3606 2563 0311 3917 205b e751 5245 bd18
r=2, X=205b e751 5245 bd18, SK=3977 6742 8a94 34dc ae03 43ad
  steps=460a 4e93 dcd9 3995 9ad3 7706 d13d 4843 4b2d 1c6a 0d27 97f4 52f9 25ff
r=3, X=0d27 97f4 52f9 25ff, SK=a072 eece 84f9 4220 b95c 0687
  steps=3320 86c2 d7f2 7410 e4d2 f2d2 57cb 4a9d 04e4 5caf 37c4 d316 da6d 28bf
r=4, X=37c4 d316 da6d 28bf, SK=5b40 e5dd 9d09 f284 4115 2869
  steps=8920 b8f3 7776 69e3 fe56 d110 7266 4376 10c0 8326 99e0 67b6 3bd5 eac5
r=5, X=99e0 67b6 3bd5 eac5, SK=0eb6 81cb bb3a 13e5 0882 2a50
  steps=9c69 e981 f70f 8efb 6b66 677a b63b 1db5 f5a8 abe3 69c1 02a7 4262 2518
r=6, X=69c1 02a7 4262 2518, SK=d372 b80d 9776 7427 ca11 0454
  steps=d39a bab4 d9d8 75d4 0a42 cf60 ba4a 89aa d175 8bbf 02ef 08ad 310b fe6b
r=7, X=02ef 08ad 310b fe6b, SK=a1a6 e570 1a1d 6d03 4f94 2208
  steps=3420 ee1d 4b28 1deb 7f08 f3f6 c124 b51a 04bd c5e1 309d 4f95 2bfc d80a
r=8, X=309d 4f95 2bfc d80a, SK=a943 4dca e034 3ada 072e ece8
  steps=3df3 9d5f 0c30 0ada 31c3 9785 44a5 dc2a 7253 b6f8 4fa0 7e63 2ba7 bc22
out, X=4fa0 2ba7 7e63 bc22, SK=1152 869b 95c0 6875 
    = 1bdd b242 1423 7ec7

18. RC5

RC5 is a proprietary cipher owned by RSADSI
designed by Ronald Rivest (of RSA fame)
replaces earlier RC2
widely licenced (in web browsers etc)
can vary key size / data size / no rounds
very clean and simple design
yet still regarded as secure

19. RC5 Overview

split input into two halves a and b
in each round update a as follows:
- a = a XOR b
- a = (a < b) + SK_i
- swap a and b
note that the rotation is the main source of non-linearity
so need a reasonable number of rounds (eg 12-16)

20. Other Block Ciphers

quite a few other block ciphers have been proposed
with varying degrees of information released on them
and with varying success against analysis
- Blowfish - 128+/64/16, Schneier 94, bulk data, slow keying
- CAST - 64/64/8, Adams 93 , appln specific boxes, Canadian browsers etc
- SAFER - 64-128/64/6+, Massey 94
- Skipjack - 80/64/32, escrowed cipher in US Govt Clipper
- Square - 128/64/8, Daemen/Rijmen
- TEA - 128/64/32 - simple, v. fast

21. Advanced Encryption Standard (AES)

clear a replacement for DES is needed
US NIST has AES call for candidate ciphers
announced Sept 97, submit by Jun 98, decided by 2000(1)
15 candidates were accepted in Jun 98 (6 rejected as incomplete)
5 were shortlisted in Aug-99
Rijndael was selected as the AES in Oct-2000
NIST have released all submissions & unclassified analyses

22. AES Requirements

private key symmetric block cipher
128-bit data, 128/192/256-bit keys
stronger & faster than Triple-DES
active life of 20-30 years (with archival use beyond that)
full specification & design details
both C & Java implementations

23. AES Shortlist

after testing and evaluation, shortlisted in Aug-99:
- MARS - complex, fast, high security margin
- RC6 - v. simple, v. fast, low security margin
- Rijndael - clean, fast, good security margin
- Serpent - slow, clean, v. high security margin
- Twofish - complex, v. fast, high security margin
further analysis & comments being taken
do see contrast between algs with
- few complex rounds vs many simple rounds
- refined existing ciphers vs brand new

24. AES Finalist - Rijndael

designed by Rijmen-Daemen in Belgium
has 128/192/256 bit keys, 128 bit data
an iterative rather than feistel cipher (like IDEA)
treats data in 4 groups of 4 bytes
has 9/11/13 rounds which:
- byte substitution step (1 S-box used on every byte)
- shift rows step (shuffle the bytes between groups)
- mix columns step (matrix mult of groups with each other)
- XOR key material step (add round key)
have initial XOR key material & incomplete last round also
all operations can be combined into XOR and table lookups - hence very fast & efficient

25. Rijndael Rounds

26. Summary

have discussed:
modes of use of block ciphers
LOKI91, IDEA, Skipjack, RC5 and other block ciphers
AES replacement cipher process

27. Exercises

Trace round 3 of the example IDEA encryption used in the lectures (and excerpted below), showing how each of the 14 steps are computed. Also describe how the subkey value is created from the original key.

#           Key (128-bits)       Plain (64-bit)   Cipher (64-bit)
7ca110454a1a6e5701a1d6d039776742 690f5b0d9a26939b 1bddb24214237ec7
idea(X=690f 5b0d 9a26 939b)
r=1, X=690f 5b0d 9a26 939b, SK=7ca1 1045 4a1a 6e57 01a1 d6d0
    steps=234a 6b52 e440 840f c70a ef5d 3606 2563 0311 3917 205b e751 5245 bd18
r=2, X=205b e751 5245 bd18, SK=3977 6742 8a94 34dc ae03 43ad
    steps=460a 4e93 dcd9 3995 9ad3 7706 d13d 4843 4b2d 1c6a 0d27 97f4 52f9 25ff
r=3, X=0d27 97f4 52f9 25ff, SK=a072 eece 84f9 4220 b95c 0687
    steps=3320 86c2 d7f2 7410 e4d2 f2d2 57cb 4a9d 04e4 5caf 37c4 d316 da6d 28bf
r=4, X=37c4 d316 da6d 28bf, SK=5b40 e5dd 9d09 f284 4115 2869

When implementing IDEA, could you pre-compute each of the functions, or would they have to be computed every time you performed an en/decryption? Discuss the implications of your answer.
Compare the computational efficiency of IDEA to RC5 in a few sentences, and hence suggest some reasons for why RC5 was chosen as the main block cipher used in web browsers.

[Back to CCS3 Lectures]

Lawrie.Brown@adfa.edu.au / 6 Feb 2001