CS306: Introduction to IT Security Fall 2020
Lecture 5: Ciphers in Practice (II)
Instructor: Nikos Triandopoulos September 29, 2020
2
5.0 Announcements
CS306: Other announcements
u HW1 is due this Friday u please
u start early
u ask for help if needed
u respect the non-collaboration policy
u HW2 to come out next week
3
CS306: Tentative Syllabus
Week
Date
Topics
Reading
Assignment
1
Sep 1
Introduction
Lecture 1
–
2
Sep 8
Symmetric-key encryption
Lecture 2
Lab 1
3
Sep 15
Perfect secrecy
Lecture 3
Lab 2, HW 1
4
Sep 22
Ciphers in practice I
Lecture 4
Lab 3, HW 1
5
Sep 29
Public-key crypto II
6
Oct 6
Access control & authentication
–
Oct 13
No class (Monday schedule)
7
Oct 20
Midterm
All materials covered
4
CS306: Tentative Syllabus
(continued)
Week
Date
Topics
Reading
Assignment
8
Oct 27
Software & Web security
9
Nov 3
Network security
10
Nov 10
Database security
11
Nov 17
Cloud security
12
Nov 24
Privacy
13
Dec 1
Economics
14
Dec 8
Legal & ethical issues
15
Dec 10 (or later)
Final
(closed “books”)
All materials covered*
5
* w/ focus on what covered after midterm
Last week
u Ciphers in practice
u The big picture
u Computational security u Pseudo-randomness
u stream ciphers, pseudorandom generators
u Demo
u The Caesar and Vigenère ciphers and their cryptanalysis (Evening) u Pseudo-randomness in practice (Afternoon)
6
Today
u Ciphers in practice u Revision
u the big picture, computational security, pseudo-randomness, stream ciphers, PRGs u Block ciphers, pseudorandom functions
u Modes of operations
u DES, AES
u Demo
u The Caesar and Vigenère ciphers and their cryptanalysis (Afternoon) u Pseudo-randomness in practice (Evening)
7
8
5.1 Revision
Recall: Formal treatment in modern cryptography
Problem is formulated as an abstract crypto primitive
u captures the essence of the problem at hand, provides clarity and focus Design & evaluation of crypto primitives follows a systematic process
u (A) formal definitions
u (B) precise assumptions
u (C) provable security
(what it means for a crypto primitive to be secure?) (which forms of attacks are allowed – and which aren’t?)
(why a candidate solution is secure – or not)?
9
Recall: Main security properties against eavesdropping
“plain” security
u protects against ciphertext-only attacks
plaintext
Hi, Bob. Don’t invite Eve to the party! Love, Alice
ciphertext
Encryption Algorithm
“advanced” security
u protects against chosen plaintext attacks 10
plaintext
ABCDEFG HIJKLMNO PQRSTUV WXYZ.
ciphertext
key
Eve
Encryption Algorithm
key
Eve
Recall: Computational security to relax “perfectness
Refined model
u a relaxed notion of security, called computational security, requires that
u the ciphertext leaks a tiny amount of extra information about the plaintext u to adversaries with bounded computational power
Asymptotic approach
u “A scheme is secure if any efficient attacker A succeeds in breaking the
scheme with at most negligible probability”
11
Recall: Security relaxation for encryption
Perfect security: |K| = 128 bits, M, EncK(M) are independent, unconditionally u no extra information is leaked to any attacker
Computational security: M, EncK(M) are independent, for all practical purposes
u no extra information is leaked but a tiny amount
u e.g., with prob. 2-128 (or much less than the likelihood of being hit by lighting)
u to computationally bounded attackers
u e.g., who cannot count to 2128 (or invest work of more than one century)
u attacker’s best strategy remains ineffective
u random guess a secret key or exhaustive search over key space (brute-force attack)
12
Recall: Computational plain & advanced secrecy
Relax the definition of perfect secrecy that is based on indistinguishability
u target messages m0, m1 are chosen by a PPT attacker
u no such attacker can tell Enck(m0), Enck(m1) apart non-negligibly better than guessing Strengthen the definition of computational plain-security for advanced secrecy
u allow attacker to have access to an encryption “box”
T
DK → k {0, 1} → b Enck(mb) → cb
PPT
A
3) indistinguishability
For every PPT A, it holds that Pr[b’=b]=1/2 +negligible
mi ci
m0, m1 cb
b’
PPT
something that can be safely ignored
13
Recall: Symmetric encryption as “OPT w/ pseudorandomness”
Stream cipher
Uses a short key to encrypt long symbol
streams into a pseudorandom ciphertext u based on abstract crypto primitive of
pseudorandom generator (PRG)
Block cipher
Uses a short key to encrypt blocks of symbols
into pseudorandom ciphertext blocks
u based on abstract crypto primitive of
… RESTUOKD
Plaintext
state
… rrywytovty
Ciphertext
key
Encryption
Encryption
pseudorandom function (PRF) key
(next block) STU
(block) OKD
Plaintext
tty
Ciphertext
14
Recall: Generic PRG-based symmetric encryption
u Fixed-length message encryption
15
encryption scheme is plain-secure as long as the underlying PRG is secure
16
5.2 Pseudorandom functions
Block ciphers
(next block) STU
(block) OKD
Plaintext
key
Encryption
tty
Ciphertext
17
Realizing ideal block ciphers in practice
We want a random mapping of n-bit inputs to n-bit outputs u there are ~2^(n2n) possible such mappings
u none of the above can be implemented in practice
Instead, we use a keyed function Fk : {0,1}n → {0,1}n
u indexed by a t-bit key k
u there are only 2t such keyed functions
u a random key selects a “random-enough” mapping or a pseudorandom function
x
Fk
y = Fk(x)
18
Generic PRF-based symmetric encryption
u Fixed-length message encryption
19
encryption scheme is advanced-secure as long as the underlying PRF is secure
Generic PRF-based symmetric encryption (cont.)
u Arbitrary-length message encryption
u specified by a mode of operation for using an underlying stateless block cipher,
repeatedly, to encrypt/decrypt a sequence of message blocks
20
Electronic Code Book (ECB)
u The simplest mode of operation
u block P[i] encrypted into ciphertext block C[i] = Enck(P[i]) u block C[i] decrypted into plaintext block M[i] = Deck(C[i])
21
Strengths & weaknesses of ECB
Strengths
u very simple
u allows for parallel encryptions
of the blocks of a plaintext
u can tolerate the loss or damage of a block
Weaknesses
u poor security
u produces the same ciphertext on the
same plaintext (under the same key)
u documents and images are not suitable for ECB encryption, since patterns in the plaintext are repeated in the ciphertext
u e.g., 22
ECB
Cipher Block Chaining (CBC) [or chaining]
Alternatively, the previous-block ciphertext is “mixed” with the current-block plaintext u e.g., using XOR
u each block is encrypted as C[i] = Enck (C[i -1] Å P[i]),
u each ciphertext is decrypted as P[i] = C[i -1] Å Deck (C[i])
u here, C[0] = IV is a uniformly random initialization vector that is transmitted separately
P[1] P[2] IV
Enck Enck C[1] C[2]
P[1] P[2] IV
Deck Deck
C[1] C[2]
CBC
23
24
5.3 Modes of operations
Block ciphers: Modes of operations (I)
u ECB – electronic code book
u insecure, of only historic value
u deterministic, thus not CPA-secure u actually, not even EAV-secure
25
Block ciphers: Modes of operations (II)
u CBC – cipher block chaining
u CPA-secure if Fk a permutation
u uniform IV
u otherwise security breaks
u Chained CBC
u use last block ciphertext of current
message as IV of next message
u saves bandwidth but not CPA-secure
26
Block ciphers: Modes of operations (III)
u OFB – output feedback u uniform IV
u no need message length to be multiple of n u resembles synchronized stream-cipher mode u CPA-secure if Fk is PRF
27
Block ciphers: Modes of operations (IV)
u CTR – counter mode
u uniform ctr
u no need message length to be multiple of n u resembles synchronized stream-cipher mode u CPA-secure if Fk is PRF
u no need for Fk to be invertible
u parallelizable
28
Notes on modes of operation
u block length matters
u if small, IV or ctr can be “recycled”
u IV are often misused
u e.g., reused or not selected uniformly at random u in this case, CBC is a better option than OFB/CTR
29
Brute-force attacks against stream/block ciphers
Brute-force attack amounts to checking all possible 2t seeds/keys
u for block ciphers, by construction (due to confusion & diffusion, as we will see), the key cannot be extracted even if a valid plaintext/ciphertext pair is captured
u thus, as expected, the longer the key size the stronger the security
30
31
5.4 Block ciphers in practice: DES & AES
Recall: Stream ciphers
key
… RESTUOKD state
Plaintext Encryption
… rrywytovty
Ciphertext
32
Recall: Block ciphers
(next block) STU
(block) OKD
Plaintext
key
Encryption
tty
Ciphertext
33
Stream Vs. Block ciphers
Stream
Block
Advantages
• Speed of transformation
• Low error propagation
• High diffusion
• Immunity to
insertion of symbol
Disadvantages
• Low diffusion
• Susceptibility to
malicious insertions and modifications
• Slowness of encryption
• Padding
• Error
propagation
34
Techniques used in practice for symmetric encryption
u Substitution
u exchanging one set of bits for another set
u Transposition
u rearranging the order of the ciphertext bits
u to break any regularities in the underlying plaintext u Confusion
u enforcing complex functional relationship between the plaintext/key pair & the ciphertext u e.g., flipping a bit in plaintext or key causes unpredictable changes to new ciphertext
u Diffusion
u distributes information from single plaintext characters over entire ciphertext output
u e.g., even small changes to plaintext result in broad changes to ciphertext 35
Substitution boxes
u substitution can also be done on binary numbers
u such substitutions are usually described by substitution boxes, or S-boxes
36
DES vs. AES
37
AES: Advanced Encryption System
u symmetric block cipher, a.k.a. Rijndael
u developed in 1999 by independent Dutch cryptographers in response to the 1997 NIST’s public call for a replacement to DES
u still in common use
u on the longevity of AES
u larger key sizes possible to use
u not known serious practical attacks
38
AES: Key design features
u use of substitution, confusion & diffusion
u block size is 128 bits
u variable-length keys: key size is 128, 192 or 256 bits
u variable number of rounds: 10, 12 or 14 rounds for keys of resp. 128, 192 or 256 bits u depending on key size, yields ciphers known as AES-128, AES-192, and AES-256
39
AES: Basic structure
40
AES: Basic structure (cont.)
41
DES: The Data Encryption Standard
u Symmetric block cipher
u Developed in 1976 by IBM for the US National Institute of Standards and
Technology (NIST)
u Employs substitution & transposition, on top of each other, for 16 rounds
u block size = 64 bits, key size = 56 bits
u Strengthening (since 56-bit security is not considered adequately strong)
u double DES: E(k2, E(k1, m)), not effective!
u triple DES: E(k3, E(k2, E(k1, m))), more effective
u two keys, i.e., k1=k3, with E-D-E pattern, 80-bit security u three keys with E-E-E pattern, 112-bit security
42
DES: Security strength
43
DES: High-level view
44
DES: Basic structure
45
DES: Initial and final permutations
u Straight P-boxes that are inverses of each other w/out crypto significance
46
DES: Round via Feistel network
u DES uses 16 rounds, each applying a Feistel cipher u L(i) = R(i-1)
u R(i) = L(i-1) XOR f (K(i),R(i-1)),
where f applies a 48-bit key to the rightmost 32 bits to produce a 32-bit output
47
DES: Low-level view
u Expansion box
u since RI−1 is a 32-bit input & KI is a 48-bit key,
we first need to expand RI−1 to 48 bits u S-box
u where real mixing (confusion) occurs u DES uses 8 6-to-4 bits S-boxes
48
DES: S-box in detail
49