compSec Lecture5
View on GitHub | Download Local
Extracted Content (for search)
Click to view slide text
CS 4173/5173 COMPUTER SECURITY Symmetric Cryptography in Practice
OUTLINE LAST TIME • “Key” issues
‒ Secret key cryptography ‒ Public key cryptography ‒ Hash
• Security Metrics
‒ Perfect Security ‒ Today’s cryptographic systems do not achieve perfect security.
• P and NP problems ‒ P: The set of questions that can be solved in polynomial time ‒ NP: the set of questions for which an answer can be verified in polynomial time ‒ Modern Cryptography: Without the key, the adversary must solve an NP problem, where a solution in P with polynomial time is “currently believed very hard” to find.
SECRET KEY CRYPTOGRAPHY plaintext
Encryption
ciphertext
Decryption
plaintext
key
• Same key is used for both encryption and decryption
‒ This one key is shared by two parties who wish to communicate securely
• Also known as symmetric key cryptography, or shared key cryptography 3
APPLICATIONS OF SECRET KEY CRYPTO • Communicating securely over an insecure channel – Alice encrypts using shared key – Bob decrypts result using same shared key
•
Authentication
– Bob can verify if a message is generated by Alice
4
GENERIC BLOCK ENCRYPTION • Converts one input plaintext block of fixed size n bits to an output ciphertext block also of n bits
n bits
plaintext
block 0 block 1
key
block 2
…
Encryption
ciphertext block 0 block 1
block 2
…
n bits 5
KEY SIZES • A Key should be selected from a large potential set to prevent brute force (exponential-time) attacks – If a key is of 3 bits, what are the possible keys? • 000, 001, 010, 011, 100, 101, 110,111
– Given a pair of (plaintext, ciphertext), an attacker can do a brute force !
Question: If a key is of n bits, how many possible keys does a brute force attacker need to search?
6
KEY SIZES (CONT’D) • Secret key sizes
– 40 bits were considered adequate in 70’s – 56 bits used by DES were adequate in the 80’s – 128 bits are adequate for now
– 2128 ≈ 3.4E + 38 – If a computer can finish 1 billion searches per second, it requires 3938453320844195178974243 years
‒ 256 bits are also used now
7
KEY SIZES (CONT’D) • Brute-force attack: try all combinations
‒ NP problem: currently, the time increases exponentially as the key size increases.
• The computing power
‒ Increases approximately linearly
• If computers increase in power by 40% per year, need roughly 5 more key bits per decade to stay “sufficiently” hard to break
8
SOME MOTIVATIONS
• How to design the ciphers?
9
SOME MOTIVATIONS • Early ciphers:
‒ Using substitutions:
• Ceasar variant, mono-alphabetic, Vigenere, …
‒ Using permutations:
• permutation ciphers
• One time pad:
‒ theory-supported
‒ Using XOR
• plaintext XOR a random key
10
FOLLOW SHANNON’S GUIDELINE make them pseudo random sequences
plaintext
key
substitutions permutations substitutions permutations
01011001 01000101 01010011
⊕
=
=
⊕
00010111 00001010 01110011
Ciphertext (so hopefully 01001110 01001111 00100000 nearly perfect security)
Q: Why also need to make the plaintext pseudo random? 11
PRINCIPLES FOR CIPHER DESIGN • Confusion:
‒ Make the relationship between the <plaintext, key> input and the
• Diffusion:
‒ Spread the influence of each input bit across many output bits ‒ Diffusion is mainly accomplished by permutations
12
EXPLOITING THE PRINCIPLES • Idea: use multiple, alternating Permutations and Substitutions, e.g., ‒ SPSPS… ‒ PSPSP…
• Do P and S have to alternate? e.g….
‒ SSSPPPSS…? ‒ Consecutive Ps or Ss do not improve security ‒ Example?
13
SECRET KEY… (CONT’D) • Basic technique used in secret key ciphers: multiple applications of alternating substitutions and permutations
plaintext
S
P
S
P
… S
ciphertext
… random keys to XOR
14
BASIC FORM OF MODERN BLOCK CIPHERS Plaintext block
Key
Preprocessing
Sub-Key Generation
Rounds of Encryption i=1,2,…,n
Sub-Key #1 Sub-Key #2 Sub-Key #3 … Sub-Key n
Postprocessing Ciphertext block 15
FEISTEL CIPHER • Feistel Cipher has been a very influential “template” for designing a block cipher • Major benefit: Encryption and decryption take the same time ‒ they can be performed on the same hardware
• Examples: DES, RC5
16
ONE “ROUND” OF FEISTEL ENCRYPTION
- Break input block i into left and right halves Li and Ri
- Copy Ri to create output half block Li+1
- Half block Ri and key Ki are “scrambled” by function f
- XOR result with input halfblock Li to create output half-block Ri+1 Key elements: substitution, XOR, and permutation
Input block i Li
Ri f
Ki
⊕ Li+1
Ri+1
Output block i+1 17
ONE “ROUND” OF FEISTEL DECRYPTION • Just reverse the arrows! • Why?
Output block i+1 Li
Ri f
Ki
⊕ Li+1
Ri+1
Input block i 18
FEISTEL CIPHER: ENCRYPTION (CONT’D) • Encryption: • 𝐿𝐿𝑖𝑖+1 = 𝑅𝑅𝑖𝑖 • 𝑅𝑅𝑖𝑖+1 = 𝐿𝐿𝑖𝑖 ⊕ 𝑓𝑓 𝑅𝑅𝑖𝑖 , 𝐾𝐾𝑖𝑖
Input block i Li
Ri f
Ki
⊕ Li+1
Ri+1
Output block i+1 19
FEISTEL CIPHER: DECRYPTION (CONT’D) • Decryption: • 𝑅𝑅�𝑖𝑖 = 𝐿𝐿𝑖𝑖+1 = 𝑅𝑅𝑖𝑖 • 𝐿𝐿� 𝑖𝑖 = 𝑅𝑅𝑖𝑖+1 ⊕ 𝑓𝑓 𝑅𝑅𝑖𝑖 , 𝐾𝐾𝑖𝑖 = 𝐿𝐿𝑖𝑖 ⊕ 𝑓𝑓 𝑅𝑅𝑖𝑖 , 𝐾𝐾𝑖𝑖 ⊕ 𝑓𝑓 𝑅𝑅𝑖𝑖 , 𝐾𝐾𝑖𝑖 = 𝐿𝐿𝑖𝑖 ⊕ all 0 bits = 𝐿𝐿𝑖𝑖
Output block i+1 Li
Ri f
Ki
⊕ Li+1
Ri+1
Input block i 20
EXERCISE Key generation: subkey is the key
0001
1101
Li
Ri
Scrambling function 𝑓𝑓(𝐾𝐾, 𝑅𝑅𝑖𝑖 ) = 𝐾𝐾 ⊕ 𝑅𝑅𝑖𝑖
f
Q: What’s the output?
Key:1 1 1 1
⊕ Li+1
Ri+1
What’s the output? 21
EXERCISE Key generation: subkey is the key
0001
1101
Li
Ri
Scrambling function 𝑓𝑓(𝐾𝐾, 𝑅𝑅𝑖𝑖 ) = 𝐾𝐾 ⊕ 𝑅𝑅𝑖𝑖
Key:1 1 1 1
f
0010
Q: What’s the output?
⊕ Li+1
1101
Ri+1
0011 22
COMPLETE FEISTEL CIPHER: ENCRYPTION Plaintext
L0
⊕
Round 1
R0 f
K1 K2
⊕
Round i
note this final swap!
⊕
…
Round n
…
L2
f R2
f
Ln Ln+1
Kn
Rn Rn+1 Ciphertext CSC/ECE 574
Dr. Peng Ning
23
COMPLETE FEISTEL CIPHER: DECRYPTION Ciphertext
L0
⊕
Round 1
R0 f
Kn Kn-1
⊕
Round i
note this final swap!
⊕
…
Round n
…
L2
f R2
f
Ln Ln+1
K1
Rn Rn+1 Plaintext CSC/ECE 574
Dr. Peng Ning
PARAMETERS OF A FEISTEL CIPHER • Block size • Key size • Number of rounds • Subkey generation algorithm • “Scrambling” function f
25