Security Core Lecture

2 Symmetric Cryptography

Dr. Nils Ole Tippenhauer | 2025

Roadmap of the next lectures

 Goals of cryptography

 Symmetric cryptography (a.k.a. secret-key / private-key cryptography)

- Symmetric encryption (Block ciphers)
- Message Authentication Codes and Authenticated Encryption

 Next lecture: Asymmetric cryptography (a.k.a. Public-key cryptography)

- Asymmetric encryption (RSA)
- Digital signatures

 Followed by cryptographic protocols in the week afterward

2
Goal: Confidentiality

 No confidentiality Eve
Alice says: Banana!

Alice says: Banana!

Banana!

Alice Bob

 Confidentiality Eve
Alice says:???

Alice says: Banana!

69342c5c39e5ae

Alice Bob
3
Goal: Integrity

 No integrity

Alice says: No
Banana! No banana banana

Alice Eve Bob

 Integrity

Message was
Banana! No banana modified!

Alice Eve Bob

4
Composability

 Confidentiality & integrity

Alice says:???

Message was
69342c5c39e5ae 693aac5c39f5ae modified!

Alice Eve Bob

5
Kerckhoff’s principle

“A cryptosystem should be secure if everything about the system, except the key, is public knowledge.”

 Standardized, widely-accepted cryptosystems are secure

 Security through algorithm obscurity is a bad idea:

- Easier to hide a key than an algorithm
- Easier to change a key than an algorithm
• Containment of breaches is an important principle
 Easier to communicate if everyone shares the same algorithm

6
Cryptographic keys

 We represent a key as a bit string of the appropriate length n

- The number of possible keys is 2n
1E+020
- Enumerating the set of all possible keys requires 1E+016

Number of keys
a computation that is exponential in the 1000000000000
length of the key 100000000
10000
1
1 10 100
Key length (n)

 There should not be a more efficient way to break a cryptosystem than enumerating all possible
keys

7
Symmetric Encrypti on
Symmetric cryptography

 Classical cryptographic settings (first scheme ~500 BC)

 The communicating parties share a secret key
- In other words: The key is unknown to anyone else, and it is hard to guess
 The key can be deployed for a single session and then be discarded (session key) or for all future
communications (long-term key)

 Historical examples:
- Caesar cipher: simple per-character mono-alphabetic shift used by Julius Caesar (~50 BC)
- Vigenère cipher: poly-alphabetic shift (published 1553, broken 1863)
- Enigma: one of the first machines to encrypt, used in WW II by Germany

9
Confidentiality in symmetric encryption

Eve
Alice says:???

Alice says: Banana!

69342c5c39e5ae

Alice Bob
Shared key Shared key

10
One Time Pad

Key

Plaintext

Alice Ciphertext Bob

Encryption Decryption

Message

11
One Time Pad

Alice Bob

Encryption Decryption

OTPs are perfectly secret

 Encrypted message reveals no information about plaintext message
(other than the message length, if used without padding)
 Even bruteforcing all keys does not help: it generates all possible plaintexts
12
One Time Pad – Brute Forcing the Key

(iterating over all 5-byte keys will generate all possible 5-byte strings; unclear which k was the
correct one)

13
One Time Pad – Reusing the Key

Alice Bob

Encryption Decryption

 Condition #1: the OTP is secret only for exactly one message

14
One Time Pad – Visual Example Key Reuse Leakage

15
One Time Pad – Key Padding

Alice Bob

Encryption Decryption

 Condition #2: OTP must be (at least) as long as the message

 Do not use a repeated short key (e.g., k:= k0 || k0||k0 ||k0 with k0 ∈ {0,1}n/4 )

16
Flawed use of One Time Pad

10 bytes
6c:66:d7:e0:51:02:c9:29:a2:39

610,014 bytes
17
Flawed use of One Time Pad

 Key k is shorter than plaintext and reused for encrypting entire plaintext
 Recover key k← c⊕ m: Repeated patterns reveal key length; Statistical analysis, such as
frequency analysis of natural language, to find correct plaintext m
OutofthenightthatcoversmeBlack L=-L< HY#Z8UH"U+UY8T-IN#J)O^!YQL/W-
asthepitfrompoletopole,Ithankw NY$Y<TY*N#P]#P)IB<S XH$\C'K$\
hatevergodsmaybeFormyunconquer Y)J)OJ#X?PL5^){B>Q5HC/S"LX)N-
[Link] _A)O#HAbu"IE)Z)QA/P9IN$S*^D>_9
umstance,Ihavenotwincednorcrie P^8]"^H`u$\[)R#IZ%R/XI"S>^_
[Link] %Y(\A#I(x"X)OY$[Link]([)RC
hanceMyheadisbloody,butunbowed %R+NB*_$\C/YDE)]
.Beyondthisplaceofwrathandtear 
(T^.P#[Link])XbH5S"YY$U?
sLoomsbuttheHorroroftheshade,A MA-_)RK;N-IE-R(IH-N?qB#Q?
ndyetthemenaceoftheyearsFinds, _X8H$Xe#N>R_#Z8UH?T-
andshallfind,[Link] YH`}"YT)H8UH!Y"\N)S*IE)E)\_?z
ersnothowstraitthegate,Howchar %SI?-SI?T-QA*U"Y!Y9SL*N-
gedwithpunishmentsthescroll,Ia TIbu8PL8H)O^"S8UB;O8OL
mthemasterofmyfateIamthecaptai %H8UH+]8XS;^E-N+XI;U8U]9R%NE!
nofmysoul. Y"I^8T)NN>S Q]!IE)Q-NY)N#[@5Z-
IH]!IE)_-MY-U"RK!E?RX 18
Breaking Flawed use of One Time Pad

 Example attacks if the key k was shorter than the message and reused for encrypting an entire
plaintext message written in natural language:
- Basic insight: If |k|=l then every mi+j*l for 0<i<l was XOR’d with the same byte ki
- Idea 1: Split the ciphertext into l parts; every part j contains only the bytes j||j+l||j+2l||...
of the ciphertext; use frequency analysis on each part to determine the most likely
candidates for the corresponding key byte (cf. breaking Vigenére cipher); test the
combinations of the key byte candidates for the parts to restore (partial) plaintext
- Idea 2: We know that ci⊕ cj = mi ⊕ mj where ci and cj are two blocks of length l; make a
guess mi' for the value of mi and check if (mi⊕ mj)⊕ m'i =m'j yields sensible natural text
- Idea 3: If the plaintext contains only certain character class (e.g., only lowercase), then a key
byte ki must satisfy that for every ci+j*l⊕ ki the result must be in this characterclass; this
allows reduction of the key space for every ki and allows for searching the key that yields a
sensible natural text

19
Idea of Computational Security

 OTP would provide perfect secrecy even against an attacker with unlimited computational
power (“information-theoretic security”)
 But…
- …impractical (e.g., key management/agreement)
- …“too strong” in practice

 Instead: schemes where it is acceptable if there is a “tiny probability” of leaking information to

an attacker with massive computational power (”computationally secure”)
- E.g., probability at most 2-60 when investing 200 years of computational effort on the fastest
available supercomputer
 Approach: Having proven, practical schemes with “k bits of security” where k is big enough that
the computational effort exceeds the attacker’s resources in a reasonable time

20
 Naïve Encryption via Block Cipher

Alice Bob
Encryption Decryption

 Security: any adversary who does not know the secret key k cannot extract any
information about m from the corresponding ciphertext c
 Given the random pad r, the key k can be used for multiple messages
 Drawback: (c,r) is twice as large as the plaintext message m
21
Practical Encryption with Block Ciphers

 From block cipher to practical encryption schemes

- Input length may not equal block size (in particular, it might be larger)!
- Keys should not be required to be as large as the messages
- We call Fk(m) encryption function and F k−1(c) decryption function (inverse of encryption
function) under plaintext input m and key k

 Goals to achieve
- Ciphertext should not be (much) longer than plaintext
- Decryption should be efficient (i.e., comparable to encryption efficiency)
- Patterns in plaintext should not be visible in ciphertext
- Allow key reuse for multiple messages

22
Pseudorandom Permutation (PRP)

 A Pseudorandom Permutation is a deterministic function Fk(m) that takes as input a random

key k, message m of length n, and the following conditions hold:
- Permutation: Bijection from a set (i.e., the input) to itself. This implies that the output of the
function is also exactly n bits long.
- Pseudorandomness: For all values of m, the output of the function is indistinguishable from
random over the random choice of k
(In other words: The output should look random for every efficient distinguishing algorithm
that cannot guess the key. If an algorithm exists that is faster than brute-forcing the key, the
function is “broken”)

 Pseudorandom permutations can be used as a block cipher

- Good block ciphers fulfill the Strict Avalanche Criterion: Flip a single bit in the input, every bit
in the output should be flipped with 50% probability

23
AES: Advanced Encryption Standard (1/4)

 Several believed-to-be-PRP constructions exist in practice, such as:

- Triple Data Encryption Standard (3DES)
- Advanced Encryption Standard (AES) AES-128
• Block size: 128 bits
• Key size: 128, 192, or 256 bits (10, 12, or 14 internal rounds)
• AES combines pseudorandom permutation (diffusion)
with substitutions (confusion)
• Decryption is reverse order and inverted internal operation
than encryption (i.e., inverted order of round keys generated)
• Same effort for de- and encryption; effective in software and
hardware

24
AES: Advanced Encryption Standard (2/4)

 Each AES round uses four primitives

1. Octet-for-octet substitution via a fixed S-
box (see below; c.f. inverse S-box)
2. Rearrangement of octets by rotating
row/column by a few cells
3. MixColumn operation, which replaces a
4B column by another 4B column
4. AddRoundKey operation, depends on key

AES Enc. S-Box ([Link]

AES: Advanced Encryption Standard (3/4)
AES: Advanced Encryption Standard (4/4)

 For the decryption process, each operation is inverted and applied in reverse order
 Round keys are derived in the original way, but applied in inverse order
 XOR of addRoundKey is easy to invert
 MixColumn and ShiftRows can both be inverted as well
 S-Boxes can also be inverted easily
 Overall, same effort for de- and encryption
Modes of operation

 Block Ciphers work on blocks (e.g., 128 bits) of plaintext and ciphertext
- The Mode of Operation thereby describes how to encrypt arbitrary-length messages by
combining the blocks of the plaintext/ciphertext
• Different modes exist: ECB, CBC, CTR, GCM, …
- Non-trivial constructions! A poorly designed mode of operation can leak the content of the
ciphertext even though the underlying block cipher is secure

I do not like David. If he resigns I pay $50.00

I do not like David. If he resigns I pay $50.00

m1 m2 m3 m4 m5 m6
28
 Electronic Code Book (ECB) Mode

 ECB encrypts each block separately

 Encryption of mk independent from any other mj
 Reuse key k for each block permutation

m m m (m = m1 | m2 | m3)

1 2 3

Fk Fk Fk

c1 c2 c3 (c = c1 | c2 | c3)
29
Electronic Code Book (ECB) Mode

 Drawback #1 of ECB:
- Equal plaintext blocks will result in equal ciphertext blocks (and vice versa)
- Thus: Similar plaintext messages will be similar in their ciphertext

I do not like David. If he resigns I pay $50.00

978GHQGAHAG)W*HGHG&@!HGOIALKG)!@GJGN!OGI!*&HGAG

My hourly salary is just $50.00 way too little!

*)#UALKJGH(P!@G*H*YAGS^G!*&HGAG GFBV@&^v jabs$9

I do not understand why many students are lazy.

978GHQGA3h09 hGOIAH G9-28h3g iuHS F!IRUSGAsdazz
30
Electronic Code Book (ECB) Mode

 Drawback #1 of ECB:
- Equal plaintext blocks will result in equal ciphertext blocks (and vice versa)
- Thus: Similar plaintext messages will be similar in their ciphertext
• Leading to information leakage about plaintext

Plaintext Ciphertext
31
Electronic Code Book (ECB) Mode

 Drawback #2 of ECB:
- Assume an attacker can modify the ciphertext
- Ciphertext modifications only affect the corresponding block(s) in the plaintext
- Modifying one ciphertext block leaves all other plaintext blocks untouched

m I'll give $500 to each student! (top-10)

c nG*}E)PFNuyf89G@O;g7iNq:K*L|'v~serc\L1gR
c’ nG*}E)PFNuyf89G@O;g7iNq:K*L|'v~sErc\L1gR
m’ I'll give $500 to each student! G%T``L^y

32
Electronic Code Book (ECB) Mode

 Drawback #3 of ECB:
- Assume an attacker can modify the ciphertext
- Blocks can be exchanged or deleted without affecting other blocks

m I'll give $500 to each student! (top-10)

c nG*}E)PFNuyf89G@O;g7iNq:K*L|'v~serc\L1gR
c’ nG*}E)PFO;g7iNq:Nuyf89G@K*L|'v~s
m’ I'll givo each se $500 ttudent!

33
Cipher Block Chaining (CBC) Mode

 CBC is a chained block cipher

- CBC uses the preceding cipher block to XOR the next input block before encryption
- Initialization Vector (IV) is a random (non-secret) XOR pad for the first block
- Formally:

m1 m2 m3
IV

Fk Fk Fk

IV c1 c2 c3 34
Cipher Block Chaining (CBC) Mode

 CBC’s advantages over ECB

- Identical plaintext blocks will not result in identical cipher blocks
(not even the very first block, due to the public yet random IV)
- Even similar plaintext patterns result in different ciphertexts
- Bit flip in mx changes cx … cn
- Bit flip in cx invalidates mx and modifies mx+1 at flip position (due to XOR)
 Disadvantages
- Parallel encryption is not possible (decryption is, though)

Plaintext Ciphertext
35
Cipher Block Chaining (CBC) Mode

 Lack of integrity:
Attacker that intercepted (c,IV) flips bits in public IV (1) which flips bits in the plaintext m 1 due
to the XOR (2); Attacker can also flip bits in the ciphertext c x (3) which will flip the same bit in
plaintext mi+1 (4) and affect the entire block mx due to the PRP nature of Fk (5)

Source: Wong, David. Real-World Cryptography.

36
Quiz time!

Why is parallel decryption of blocks possible

in CBC while encryption is sequential?
A: Special hardware support
Recap:

B: Fewer data dependencies

C: Precomputation is possible

37
Quiz time!

Why is parallel decryption of blocks possible

in CBC while encryption is sequential?
A: Special hardware support
Recap:

B: Fewer data dependencies

C: Precomputation is possible

38
Integrity in Symmetric Cryptography

43
Message Authentication Code (MAC)

 MAC provides integrity based on a secret key (Just checksums are not secure)
- Authentication tag attached to the message
 Covered in this lecture: based on hash function

Message was
Banana! No banana modified!

Alice Eve Bob

Shared key Shared key

44
Naïve MAC from Block Cipher

Alice Bob

Compute tag Verification

 Security: Adversary that does not know the key k cannot forge a valid authentication tag!
 Bob’s verification succeeds only if Alice generated the message
 Not efficient enough for practical purposes (tag length == message length)

45
Hash Functions (1/3)

 A (cryptographic) hash function is a deterministic function H(m) that takes as input a message
of any length, and the following conditions hold:
- Compression: The output of the function has a fixed length for input of arbitrary length
- Collision resistance: It is computationally hard (i.e., practically impossible) to find two inputs
and such that H(m)=H(m’)
- One Way: For a random message , it is infeasible to infer m from H(m) except by trying all
possible candidates of m (brute force attack).

 Hash functions in practice:

- MD5 (broken, possible to find collisions easily)
- SHA-1 (considered broken in practice, e.g., [Link]
- SHA-2 (by NSA) and SHA-3 (a.k.a. Keccak, by Bertoni, Daemen, Peeters, van Assche)

46
Hash Functions (2/3)

 About hash collisions: The Birthday Paradox

- With n=23 people in a room, there is p>50% chance that two persons share the same birthday
(modulo year, i.e., k=365 possible outputs)
n Pr (B = 365)
 Reasoning behind birthday paradox
5 2.7%
- Chances for one pair to match is low, but:
10 11.7%
- Number of pairs n(n-1)/2 grows quadratic with number of participants n
20 41.1%
- Number of pairs dominate the chance of collisions
23 50.7%
 Implications for hash functions 30 70.6%
- Compression must not be too aggressive 40 89.1%
70 attack
- If hash digests to d bits, it requires 2d/2 messages to find a collision with generic 99.9%
• Best attack on SHA-1: estimated 261 beats generic attack

47
Hash Functions (3/3)

Quality criteria for cryptographically secure hashes

 Collision resistance: 2n/2 (attempts required ideally)
- “Hard to find any two collisions”
- Find any m, m’ such that H(m) = H(m’)
 Preimage resistance (one-way property): 2n
- “Hard to infer input from hash”
- Given H(m), find m
 Second preimage resistance: 2n
- “Hard to find collision for concrete input”
- Given m, H(m) find m’ such that H(m) = H(m’), m ≠ m’

48
Hash and MAC

Alice Bob

Compute tag Verification

49
Hash and MAC — The Wrong Way

 Basic idea: hash over prepended key and data t = H(k || m)

 But: Merkle-Damgård hash constructions (e.g., SHA-1) allow for extension attacks
- Assumption: Attacker knows H(k || m) and len(m), but does not know m or k
- Goal: Compute H(m’) without knowing/guessing m and k
- Basic idea: Resume hash computation:
• Initialize inner state of hash (e.g., variables Hi below) based on H(k || m)
(note: the inner state can be deterministically derived from the hash digest)
• Continue hash computation at first block appended by attacker
- SHA-3: “Sponge” construction instead of Merkle-Damgård; prevents extension attacks

50
Hash and MAC — The Provably-Secure Way (HMAC)

 HMAC was proven secure (in contrast to simple keyed hashes)

 Derive two keys (inner/outer) for two separate hash computations
 HMAC(k, m) = H((k’ ⊕ opad) || H((k’ ⊕ ipad) || m)),
where k’ is derived by padding k with 0x00 bytes until size 512 bits
 To some extent resistant against collisions in the underlying hash function
k padding (0…0)

opad ipad
m

H()

H()
51
Security of cryptographic hash functions over time

1990 2004 2019

Snefru
MD2 (128-bit)
MD4
MD5
RIPEMD
HAVAL-128
SHA-0
SHA-1
RIPEMD-160
SHA-2 family (incl. SHA256)
SHA-3 (Keccak)
(source: [Link] )
52
Authenticated Encryption Schemes

 Combine a secure encryption scheme with a secure MAC for both confidentiality and integrity
 But: Certain approaches do not yield the intended security!
 Approaches:
1. Encrypt-and-authenticate: c := Encke(m) and t := MACkm(m)
• May not provide the most basic level of secrecy since secure MAC does not guarantee secrecy
(i.e., may leak information about , e.g., if the same message was sent again)
2. Authenticate-then-encrypt: c := Encke(m|t) and t := MACkm(m)
• May be prone to a padding-oracle attack (has been successfully used to attack AtE in TLS)
3. Encrypt-then-authenticate: c := Encke(m) and t := MACkm(c)
• This approach is sound (assuming ke!=km and keys are independent)
• Generally: “different instances of cryptographic primitives should always use independent keys”

53
Authenticated Encryption with Associated Data (AEAD)

 Some Block Cypher modes provide authenticated encryption (integrity + confidentiality)

- Modes like GCM provide both properties in one operation

 Example: Galois/Counter Mode (GCM)

- Basic idea: Implicitly compute an authentication tag
during encryption (that includes the IV)
- Any bit flip will be detectable
- Easy to parallelize the decryption/encryption

GCM Mode Basic Operation

Source: [Link]
54
Further Reading

 Katz, Jonathan and Lindel, Yehuda. Introduction to Modern Cryptography

- Chapters 2.2–2.3, 3.6.3, 4.2, 4.4, 6.1, 6.3–6.4, 7.2.5, 7.3.2
 Ferguson, Niels; Schneier, Bruce and Kohno, Tadayoshi. Cryptography Engineering:
Design Principles and Practical Applications
- Chapters 3–6.4
 Wong, David. Real-World Cryptography
- Chapters 1.2–1.3, 2.1–2.5, 3, 4.1–4.5.2
 Schneier, Bruce. Applied Cryptography
- Chapters 1.5, 2.3–2.4

55