Symmetric Key Block Ciphers - Northern Kentucky University

Report
Jeff Ehme
Spelman College
[email protected]
Chris Christensen
Northern Kentucky University
[email protected]
Encipher(plaintext, key)
plaintext
CIPHERTEXT
Decipher(CIPHERTEXT, key)
function
patterned
"random"
inverse
Skytale
Caesar cipher
Playfair Cipher
19th century
Vigenere Cipher
16th century
Transposition Cipher
KL47
KW-7
ATM
IFF
Data Encryption
Standard 1977
“New Directions in
Cryptography” 1976
 Symmetric key block ciphers
 Public key ciphers
 Stream ciphers
 Post-quantum ciphers
Substitution
Transposition
DROSX
MDCYP
ONSXD
SXDRO
WKDRO
XEXNO
BONRY
OIMSZ
QBKZR
BOOAE
DSXQ
DOBOC
ZELVS
OBOCD
COMSZ
WKDSM
BQBKN
GOFOB
ROBCD
IWYNO
KVVIW
DSXQW
FUOIM
LIWKD
ROBCK
CDRKD
EKDOM
KBODR
ROGYB
BXZBS
KDROW
KDROW
SZROB
ROWKD
CKZZV
MKXLO
YEBCO
OWYNO
URYBC
FKDOS
KDSMK
KDSMK
CRKFO
SMCPK
SMKDS
ZBOCO
CYPDO
BXZBS
OCYPM
OIMSZ
VVISX
VKCZO
CZKBU
MEVDI
YXCYP
XDONS
XSQXY
FKDOU
BIZDY
ROBCK
DOBOC
Lester Hill (1891 – 1961)
Symmetric Key vs Asymmetric key
Symmetric Key
Asymmetric Key
If the solution to a problem can be quickly verified by a
computer, can the computer also solve that problem
quickly?
Horst Feistel (1915 – 1990)
Simplified DES: Wade Trapp and Lawrence Washington
DES
Simplified DES
64-bit block
56-bit key (8 parity bits)
8 S-boxes 6 x 4
16 rounds
Feistel cipher
12-bit block
9-bit key
2 S-boxes 4 x 3
4 rounds
Feistel cipher
9 bits of key 111 010 110
Use the 8 bits on the left for k1 1110 1011
Rotate to the left one bit 110 101 101
Use the 8 bits on the left for k12 1101 0110
Rotate to the left 1 bit 101 011 011
Use the 8 bits on the left for k3 1010 1101
Rotate to the left 1 bit 010 110 111
Use the 8 bits on the left for k4 0101 1011
S1
0
1
0
1
2
3
4
5
6
7
101 010 001 110 011 100 111 000
001 100 110 010 000 111 101 011
S2
0
1
0
1
2
3
4
5
6
7
100 000 110 101 111 001 011 010
101 011 000 111 110 010 001 100
Li
Li1  Ri
Ri




Ri1  Li  f Ri, Ki




Encryption
Li
Ri
Li1  Ri
Ri1  Li  f  Ri , Ki 








Li1  Ri
Ri1  Li  f Ri , Ki
Decryption




Li  Ri1 f  Ri , Ki 
Ri  Li1




Encryption
Decryption
Backdoor?
















EK 3 DK 2 EK1 plaintext








Perfect Security
Random key, as long as the message, and used only once.
Computational Security
Symmetric Key RSA and DH
80
1024
112
2048
128
3072
192
7680
256
15360
Today
112
ECC
160
224
256
384
521
64-bit block
80-bit key
32 rounds
Unbalanced Feistel cipher
Skipjack declassified 1998
Clipper Chip 1993 -1996
Claude Shannon (1916 – 2001)
“A Mathematical Theory of Communication” 1948
“The Theory of Secrecy Systems” 1949
Diffusion: “… the statistical structure of [the message]
which leads to its redundancy is dissipated into long
range statistics.”
Wire crossing, S-box
Confusion: “… make the relation between the simple
statistics of [the ciphertext] and the simple description
of [the key] a very complex and involved one.”
Permutation, P-box
Many
64-bit block
80- or 128-bit key
1 S-box 4 x 4
31 Rounds
Substitution-Permutation Network
How do they know it’s secure?
Joan Daemen and Vincent Rijmen
Simplified AES: Mohammad Musa, Edward Schaefer, and
Stephen Wedig
AES
Simplified AES
128-bit block
128-bit, 192-bit, or 256-bit
key
10, 12, or 14 rounds
SPN
16-bit block
16-bit key
2 rounds
SPN
y  1x
xy 1
k0k1k2k3 k4k5k6k7
k8k9k10k11 k12k13k14k15
W[0]
W[1]
pt

A

NS

SR

MC

A

NS

SR

A

CT
K
K
K
0
1
2
Serpent
Twofish
RC6
MARS
Simplified IDEA
Hoffman, N. 2007.
“A Simplified IDEA Algorithm,”
Cryptologia 31(2), 143 – 151.
TEA
Holden, J. 2013.
“Demitasse: A ‘Small’ Version of the Tiny
Encryption Algorithm and Its Use in a classroom
Setting.”
Cryptologia 37(1), 74 – 83.
Stream ciphers
Simplified DES
Trappe, W. and Washington, L.
Introduction to Cryptography with Coding
Theory
Simplified IDEA
Hoffman, N. 2007.
“A Simplified IDEA Algorithm,”
Cryptologia 31(2), 143 – 151.
PRESENT
Boganov, A. and others. 2007.
“PRESENT: An Ultra-Lightweight Block Cipher.”
(Search the net.)
Simplified AES
Musa, A., Schaefer, E., and Wedig, S. 2010.
“A Simplified AES Algorithm and Its Linear and
Differential Cryptanalysis,”
Cryptologia 27(12), 148 – 177.
TEA
Holden, J. 2013.
“Demitasse: A ‘Small’ Version of the Tiny
Encryption Algorithm and Its Use in a classroom
Setting.”
Cryptologia 37(1), 74 – 83.
Cryptology course notes and student-produced software
http://www.nku.edu/~christensen/1301cscmat483.htm

similar documents