1 of 12

Lec 13: Linear Cryptanalysis

2 of 12

  • 1992 — Matsui and Yamagishi, A New Method for Known Plaintext Attack of FEAL Cipher, EUROCRYPT 1992
  • 1993 — 松井 充, DES暗号の線形解読法(I), SCIS 1993 (in Japanese)
  • 1993 — Matsui, Linear Cryptanalysis Method for DES Cipher, EUROCRYPT 1993
  • 1994 — Matsui, The First Experimental Cryptanalysis of the Data Encryption Standard, CRYPTO 1994
    • Known-message attack, 247 (message, ciphertext) pairs

​

  • Unclear whether DES designers were aware of linear cryptanalysis

3 of 12

Notations

  •  

4 of 12

CIPHERA

  •  

5 of 12

  •  

​

0

1

2

3

4

5

6

7

8

9

a

b

c

d

e

f

​

f

e

b

c

6

d

7

8

0

3

9

a

4

2

1

5

​

0

1

0

1

0

1

0

1

1

0

1

0

1

0

1

0

​

1

1

1

0

1

0

1

0

0

1

0

1

0

1

0

0

6 of 12

Characteristics of S-Box

  •  

7 of 12

CIPHERB

  •  

8 of 12

  •  

9 of 12

  •  

10 of 12

CIPHERC

  •  

11 of 12

  •  

12 of 12

Student presentations reminder

  • No class next week
  • Presentations begin 11/16 (Mon)
    • Sign up if you haven’t
    • If you know your topic, add it to the sign-up sheet

​

  • 20-35mins
    • High-level expectation: similar to my lectures
    • Detailed expectation → see “Suggested Topics for Student Presentations”
  • Present from your laptop or mine
    • Either way, send your slides to be in advance