Aug. 27, 1998KCDSA Task Force Team1 Specification and Analysis of CRYPTON V1.0 Chae Hoon Lim Future Systems, Inc - [PPT Powerpoint] (2024)

1

Specification and Analysis of CRYPTON V1.0

Chae Hoon Lim

Future Systems, Inc.

2

Contents

Design history

Basic building blocks

Encryption/decryption

Key Scheduling

Security/efficiency analysis

Conclusion

3

Design Objectives

An efficient and secure block cipher

Security:– security bounds high enough to defeat various existing attac

ks such as differential and linear cryptanalysis.

– A large safety margin for the future

Efficiency:– high performance in software on large microprocessors

– efficient implementation on low-cost 8-bit microprocessors

– very high speed in hardware; low hardware complexity

Simplicity

4

Design Choices

Feistel vs Substitution-Permutation Network (SPN)– Feistel: more cryptanalytic experience, fewer constraints in

round function design; poor parallelism

– SPN: more parallelism, more hardware-efficient; more constraints in round function design

Choice from two alternative designs

– design based on Feistel: much like Twofish

SALTIS (unpublished)

– design based on SPN: used the global structure of Square

– final decision: SPN-type cipher CRYPTON

5

Main Features

secure against existing attacks

a simple, fine-grained design: easy to implement/analyze

symmetry in encryption and decryption

high performance on most CPU architectures

fast key scheduling: much faster than one-block encryption

efficient hardware implementation; low complexity

high degree of parallelism very high speed in hardware: ca

n achieve several Gbits/sec using about 30000 gates

6

CRYPTON v1.0: Motivations / Changes

Original AES proposal (CRYPTON v0.5): – at almost final stage of design, but not complete

Motivations to revision:– key scheduling was under examination for modification.

– somewhat weak S-boxes; decided to replace S-boxes with stronger ones in this opportunity.

Tried to keep changes minimal: no substantial redesign

Changes:– Key scheduling strengthened (overall structure unchanged).

– New 8 x 8 Sboxes (2 S-boxes --> 4 S-boxes).

7

High-level Structure of CRYPTON

Bit

-wis

e ke

y ad

diti

on

Col

umn-

wis

e bi

t per

mut

atio

n

Col

umn-

to-r

ow tr

ansp

osit

ion

Bit

-wis

e ke

y ad

diti

on

Byt

e-w

ise

subs

titu

tion

Row

-wis

e bi

t per

mut

atio

n

44

byte

arra

yIn

put

Inpu

t whi

teni

ng

Rou

ndtr

ansf

orm

atio

n(1

2 ro

unds

)

Out

put

tran

sfor

mat

ion

Out

put

8

Notation

Data representation in 4 x 4 byte array

A = (A[3], A[2], A[1], A[0])t =

A[0]A[1]A[2]A[3]

a03 a02 a01 a00

a13 a12 a11 a10

a23 a22 a21 a20

a33 a32 a31 a30

=

9

Basic Building Blocks

Components of Round Transformation:– Byte-wise Substitution – Column-wise Bit Permutation – Column-to-Row Transposition – Key Xoring

Round Transformation – Even rounds: eK = K o o e o e

– Odd rounds: oK = K o o o o o

10

Encryption/Decryption

Round keys

– i-th round encryption: Kei = {Ke [4i+j]}(0 j 3)

– i-th round decryption: Kdi = {Kd [4i+j]}(0 j 3)

e = o e o , o = o o o

– Kdi =

e(Ke i) for even i, o(Ke

i) for odd i.

Encryption EK :

Decryption DK :

– same as encryption except for using Kd instead of Ke.

0121112 eeeee KeKeKeKeKe

11

Byte-wise Substitution

Odd rounds:

Even rounds:

S1

S0S1

S1

S1S0

S0

S0

S2

S2

S2

S2

S3

S3

S3

S3

S1

S0S1

S1

S1 S0

S0

S0

S2

S2

S2

S2

S3

S3

S3

S3

Odd rounds Even rounds

)( )( 4 mod ijjiijo aSbAB

)( )( 4 mod 2 ijjiije aSbAB

12

Column-wise Bit Permutation (1)

3 2 1 0

Odd rounds

1 0 3 2

Even rounds

)(),(),(),( :roundsEven

)(),(),(),( : rounds Odd0

21

32

03

1

00

11

22

33

AAAA

AAAA

e

o

13

Column-wise Bit Permutation (2)

m0 = 0xfc, m1 = 0xf3, m2 = 0xcf, m3 = 0x3f

for 4-byte column vectors a and b, b = 0(a) is defined by

03102133

02132033

01122333

00112233

3

2

1

3

2

1

amamamam

amamamam

amamamam

amamamam

a

a

a

a

b

b

b

b

b

2

1

3

3

2

1

3

1

3

2

3

2

1

2

3

2

1

3

2

1

1

3

2

1

3

2

1

, ,

b

b

b

b

a

a

a

a

b

b

b

b

a

a

a

a

b

b

b

b

a

a

a

a

a

a

a

a

b

b

b

b

14

Column-to-Row Transposition / Key Add

Transposition: B = (A) bij = aji

Key addition:

– B = K(A) B[i] = A[i] K[i] for i=0,1,2,3.

a03 a02 a01 a00

a33 a32 a31 a30

a13 a12 a11 a10

a23 a22 a21 a20

a03

a02

a01

a00

a33

a32

a31

a30

a13

a12

a11

a10

a23

a22

a21

a20

15

Key Scheduling (1)

Overall structure: two-step generation

facilitate low-level implementations

User Key (0~32bytes)

Expanded Keys (32bytes)

Encryption Round Keys Decryption Round Keys

Decryption Transform

16

Key Scheduling (2)

Already planned at the beginning Known weakness: 232 weak keys for 256-bit key

– found by J. Borst and S. Vaudenay independently.

– due to regular patterns preserved in both round key generation and round transformation

Changes:– major changes made in round key generation

– used distinct round constants

– used 2/6-bit byte rotation and word-wise rotation Consequence: believed secure against most known ke

y schedule weaknesses

17

Diffusion Property of (1)

Achieve diffusion order 4

at least 4 active bytes on average per round

Minimum diffusion set = x y =

{0x01,0x02, 0x03, 0x04, 0x08, 0x0c, 0x10, 0x20, 0x30, 0x40, 0x80, 0xc0}

{0x11, 0x12, 0x13, 0x21, 0x22, 0x23, 0x31, 0x32, 0x33, 0x44, 0x48, 0x4c,

0x84, 0x88, 0x8c, 0xc4, 0xc8, 0xcc}

order 4 5 6 7 8

No 204 13464 1793364 13058978 4162570479

ratio 4.75x10-8 3.13x10-6 4.18x10-4 3.04x10-2 96.92x10-2

18

Diffusion Property of i (2)

Ij = a set of input vectors of diffusion order 4 under i with j nonzero bytes

No.minimum diffusion vectors = 48+48+60+48 = 204

}.|)0,,,(,),0,,(,),,0,(,),,,0{(

},|)0,,0,(,),0,,0{(

},|),0,0,(,)0,0,,(,)0,,,0(,),,0,0{(

},|)0,0,0,(,)0,0,,0(,)0,,0,0(,),0,0,0{(

3

2

2

1

xtttt

yxtt

xtttt

xtttt

xxxxxxxxxxxxxI

yyyyyI

xxxxxxxxxI

xxxxxI

22

4

)(

,3,2,1for )(

IaIa

jIaIa

i

jij

19

Minimum Diffusion Patterns by o

Round 1

Round 2

Round 3

Round 4

Type-1 Type-2 Type-3 Type-4

20

Differential/Linear Prob. for nn S-box S

S-box differential prob.: x / y : input/output differences, resp.

S-box linear prob.: x / y : input/output selection vectors, resp.

21

12

2|})(|{|)(Pr

nyxSxxXx

yxn

nyxxSxSXx

yx2

|})()(|{|)(Pr

21

S-box Construction (1)

One 8x8 involution S-box S 4 S-boxes Si

S

ROL1

S0

S

ROL3

S1

S

ROL7

S2

S

ROL5

S3

22

S-box Construction (2)

Design criteria for S-boxes:– should be efficiently implementable in hardware logic and o

n low-cost smart cards.

– The prob. of differential and linear characteristics should be as small as possible.

– High prob. I/O differences/selection vectors in S should have as high Hamming weights as possible.

– The number of such pairs in all Si’s should be as small as possible when restricted to .

23

The S-box S Search Model

Bit

Per

mut

atio

n

RO

Ln

Inve

rse

Bit

Per

mut

atio

n

P0-1

P1-1

P1

P0

RO

LnL

eft r

otat

eby

n b

its

24

The Selected S-box S

x7 x6 x5 x4 x3 x2 x1 x0 Input x

P1 P0

z7 z6 z5 z4 z3 z2 z1 z0

4-bit P-boxes

w3 w2 w1 w0 w7 w6 w5 w4

Output y

P0-1 P1

-1

y3 y2 y1 y0 y7 y6 y5 y4

Inverse P-boxes

Linear involution

z7 z6 z5 z4 z3 z2 z1 z0

z4 z0 z3 z7 z5 z1 z2 z6

z2 z5 z7 z0

25

Differential/Linear Char. of S-boxes (1)

Difference distributionvalue 0 2 4 6 8 10No 39584 20158 4976 749 62 7

Linear approx. distributionvalue 0 4 8 12 16 20 24 28 32No 13927 22058 15948 8460 3731 1094 276 36 6

Previous S-boxes: too many high prob. I/O pairs The new S-boxes:

– Pr(DC) 10/256 = 2-4.68 for only 7 pairs

– Pr(LC) (32/128)2 = 2-4 for only 6 pairs

– High prob. char.: sum of Hamming weights is at least 4, on average 8.

26

Differential/Linear Char. of S-boxes (2)

DC( 6) (11,c0) (22,8c) (32,cc) (88,11) S0

LC(24) (88,11) DC( 6) (11, 3) (22,32) (32, 33) (88,44)

S1 LC(24) (88,44) DC( 6) (c0,11) (11,88) (8c,22) (cc,22)

S2 LC(24) (11,88) DC( 6) ( 3,11) (32,22) (33,32) (44,88)

S3 LC(24) (44,88)

Observarion:– min. 4 active bytes/round only for byte values in – for such values, max. entry in distr. tables : 6 / 24

– Pr(DC) 6/256 = 2-5.42

– Pr(LC) (24/128)2 = 2-4.83

27

Differential/Linear Cryptanalysis - Bounds

Observations:– Min. No. of active S-boxes up to 8 rounds = 32

– Suppose that all such active S-boxes have

Pr(DC) = 2-5.42 and Pr(LC) = 2-4.83.

Overall char.prob.of DC/LC up to 8 rounds:– pC8 (2-5.42)32 = 2-173.3

– pL8 (2-4.83)32 = 2-154.6

Differential, linear hull/multiple linear approx.:– may increase the probabilities by a constant factor.

28

Differential/Linear Cryptanalysis - Simulation

Partial exhaustive search over the minimum diffusion set theoretically breakable up to 7 rounds

Char. Prob. Diff. Prob.No. ofrounds DC LC DC LC

DiffusionType

5 110.3 105.0 109.5 105.0 3 / 4

6 127.1 122.8 124.3 120.7 3 / 3

7 156.9 145.1 155.4 144.2 3 / 4

8 185.7 169.3 181.5 169.1 4 / 4

figure = -log2 (prob.)

29

Variants/Extensions of DC/LC

Variants of DC:– truncated/higher-order differentials,

– impossible differentials: a number of impossible differentials up to 4 rounds; none for more than 5 rounds

Variants of LC:– nonlinear approximations, generalized LC, partitioning cryp

tanalysis

30

Other Possible Attacks

interpolation attacks: no simple algebraic description

dedicated SQUARE attacks: – the best known attack up to 6 rounds

– can’t be extended to more round versions

Side-channel cryptanalysis: – timing attacks

– differential fault analysis

– differential power analysis

Key schedule cryptanalysis– weak keys, semi-weak keys, equivalent keys

– simple relations, related keys

31

Software Efficiency

32-bit Ps: same as the previous version– Pentium Pro 200 MHz, Windows 95, MSVC 5.0

– UltraSparc 167 MHz, Solaris 2.5, GNU C

]

8-bit Ps: 256 byte ROM, 52 byte RAM; a little bit slower than the previous version

Language\Clocks Key setup (enc/dec) Enc/Dec

In-line Asm (PC) N/A 381/381 (64Mbps)

MSVC 5.0 (PC) 327/397 452/452 (54Mbps)

GNU C (UltraSparc) 496/564 575/575 (42Mbps)

32

Hardware Efficiency

Gate array implementation of 2-round iterative version – VHDL description & logic synthesis using Synopsys + HY

UNDAI’s 0.35 micron gate array library

Simulation results:

Opt.in

ClockPeriod(nsec)

Enc /Dec

(cycles)

Keysetup

KeySwitch(cycles)

Speed(Mbits/s

ec)

CellArea(no.ofgates)

TotalArea(no.ofgates)

Area 18.98 7 0 1 919 18322 51527

Time 10.23 7 0 1 1705 28179 74021

33

Conclusion

Advantages:– strong security against various known attacks (with at least

3-round safety margin)

– symmetry in encryption and decryption

– uniformly fast on various architectures in software

– efficiently implementable in hardware

– high degree of parallelism: very high speed in hardware

Remarks:– can be freely used: royalty-free

– welcome any comments/analysis reports