Symmetric Cryptography
SFL @ TU Dortmund
Cryptography Goals: Confidentiality
Copyright By PowCoder代写 加微信 powcoder
• No confidentiality
• Confidentiality
Alice says: Hello!
Alice says: Hello!
Alice says: Hello!
7929ce9d50cc0a7bf
Cryptography Goals: Integrity
• No Integrity
Alice says: Hell!
• Integrity
Hell! Elice
Message was modified!
Hello! Alice
Cryptography: An Introduction
• Cryptography is the study of techniques that allows secure communication in presence of attackers
plaintext ciphertext
ciphertext plaintext
(encryption) (decryption)
Cryptographic Algorithm
Symmetric Key Cryptography (a.k.a. private-key crypto)
• Same key used for encrypting and decrypting a message
• Single key needs to be shared among communication partners
• Usually computationally fast
Next 2 weeks
Asymmetric Cryptography
(a.k.a. public-key crypto)
• Uses pairs of keys (public key for encr., and private key for decr.)
• Public keys can be disseminated to everyone→easy distribution
• Usually computationally slow
Kerckhoffs’s Principle
“A cryptosystem should be secure if everything about the system, except the key, is public knowledge.”
• Standardized, widely-accepted solutions are secure
• Security through algorithm obscurity fails: • Easier to hide a key than an algorithm
• Easier to change a key than an algorithm
• Easier to communicate if everyone shares the same algorithm
Cryptographic Keys
• We represent a key as a bit string of the appropriate length n
• The number of possible keys is 2n
• Enumerating the set of all possible keys requires a computation that is exponential in the length of the key (see graph)
18.446.744.073.709.600.000 72.057.594.037.927.900 281.474.976.710.656 1.099.511.627.776 4.294.967.296 16.777.216 65.536 256 1
1 2 4 8 16 32 64
Key length (n)
• There should be no more efficient way to break a cryptosystem than enumerating all possible keys
Number of keys
Two Historic Example: & Enigma
Ancient Encryption:
• User by Caesar in Rome, 70 B.C.
• “Encryption” by shifting individual characters in the alphabet
• Only 25 “encryption keys”
(shifted by 3)
Ancient Encryption:
• Decryption possible by bruteforce attempt •
•Awzcpqgafcpfcgr •Bxadqrhbgdqgdhs •Cybersicherheit
Shifted by 1 Shifted by 2 Shifted by 3
Paradigm Change: Enigma
Paradigm Change: Turing Bomb Cracks Enigma
Confidentiality in Private-Key Crypto
Private Key Cryptography
• 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)
• Example key spaces in historic designs:
• Caesar: ‘a’ – ‘z’ → key strength log2(25) = ~5 bit
• Enigma: log2(150.738.274.937.250) configurations = ~47 bit
Private Key Encryption
Alice says: ???
Alice says: Hello!
7929ce9d50cc0a7bf
One Time Pad (1/2)
Encryption
Decryption
• OTPs are provably secure iff used once
• Encrypted message reveals no information about plaintext message
(other than the message length, if used without padding)
• Even bruteforcing all keys does not help: generates all possible plaintexts
One Time Pad (2/2)
Encryption
Con #1: the OTP is secret only for exactly one message
Con #2: OTP has to be (at least) as long as the message →impractical key generation and sharing
Decryption
From OTP to Block Ciphers
• Goals for a symmetric cryptosystem
1. Encryption should be possible for arbitrary input lengths (large |m|)
2. Keys do not necessarily need to be as long as messages (|k| << |m|)
3. Allow key-reuse for multiple messages
4. Ciphertext should not be (much) longer than plaintext
5. Decryption should be efficient
6. Patterns in plaintext should not be visible in ciphertext
Block Ciphers
• Block cipher cryptosystem
• Split m into fixed-length blocks m1,...,mn
m1 m2 m3 m4 m5 m6
• Block cipher:
• Fk(m) encryption function
• Fk-1(m) decryption function (inverse of encryption function)
Soon will be your birthday!! I'll donate $50.00
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.
对于所有的m值，函数的输出在随机选择k的情况下与随机无异。
• (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.)
(换句话说。对于每一个不能猜出密钥的有效区分算法来说，输出应该是随机的。)
• Pseudorandom permutations can be used as a block cipher
• Several believed-to-be-PRP constructions exist in practice:
- Triple Data Encryption Standard (3DES)
- Advanced Encryption Standard (AES)
AES: Advanced Encryption Standard (a.k.a. Rijndael) (1/2)
• AES combines pseudorandom permutation with substitutions • AES is a commonly-used private-key cryptographic scheme
• 128-bit (16B) block size with variables keys (128 to 256 bits) • 10 (AES-128) to 14 (AES-256) rounds
• Each AES round follows these four primitives per 16B block
1. Octet-for-octet substitution via a fixed S-box (see below; right)
2. ShiftRows: Shift octets within i’th 4B row by i to the left with wrapping
3. MixColumn: Multiply each column with constant matrix (see below; left)
4. AddRoundKey operation, which XORs the block with round keys (derived from key k)
B1,i X B2,i
Input column (i <= 4)
02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02
Constant AES MixColumn multiplication matrix
C0,i C1,i C2,i C3,i
Output column (i <= 4)
AES Enc. S-Box (https://captanu.wordpress.com/tag2/0aes/)
AES: Advanced Encryption Standard (2/2)
Advanced Encryption with Block Ciphers
• Block Ciphers work on blocks (128 bits in AES) of plain- or ciphertext • The Mode of Operation thereby describes how to encrypt arbitrary length
messages by combining the blocks
• Non-trivial constructions! A poorly designed mode of operation can leak the content of the ciphertext even though the underlying block cipher is secure
Soon will be your birthday!! I'll donate $50.00
m1 m2 m3 m4 m5 m6
Electronic Code Book (ECB) Mode (1/4)
• ECB encrypts each block separately
• Split message m in n blocks m1 ... mn
• Encryption of mk independent from any other mj • Reuse key k for each block permutation
(m = m1 | m2 | m3)
(c = c1 | c2 | c3)
Electronic Code Book (ECB) Mode (2/4)
• Drawback #1 of ECB:
• Equal plaintext blocks will result in equal ciphertext blocks (and vice versa)
• Thus: Common substrings in plaintexts messages may result in common substrings in their ciphertexts (even for a strong PRP!)
S F!IRUSGAsdazz
Electronic Code Book (ECB) Mode (3/4)
• Drawback #1 of ECB graphically demonstrated by the “ECB penguin”:
Leaks the plaintext pattern
Electronic Code Book (ECB) Mode (4/4)
• Drawback #2 of ECB:
• Assume an attacker can modify the ciphertext
• Ciphertext modifications only affects the reflective block(s) in the plaintext • Modifying one ciphertext block leaves all other plaintext blocks untouched
• Example:
Cipher Block Chaining (CBC) Mode (1/2)
• CBC is a chained block cipher
• CBC uses cipher block to XOR the input block before encryption
• Initialization Vector (IV) is a random (non-secret) XOR pad for first block
• Formally: ci := Fk(mi ⊕ ci-1) for i>1 (for i=1: c1 := Fk(mi ⊕ IV))
m1 m2 m3 IV
• Decryption analog to encryption: mi := ci-1 ⊕ Fk-1(ci)
• Could you implement the Caesar cipher in CBC mode?
A: No way.
B: Yes, and it is more secure.
C: Yes, but it is similarly weak.
Cipher Block Chaining (CBC) Mode (2/2)
• 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) cx中的比特翻转使mx无效，并在翻转位置修改mx+1(由于XOR)。
• Disadvantages:
• Parallel encryption is not possible (decryption is, though)
• Why is parallel decryption possible in CBC, while encryption is sequential?
enc(): ci := Fk(mi ⊕ ci-1) dec(): mi := ci-1 ⊕ Fk-1(ci)
A: Special hardware support.
B: Fewer data dependencies.
C: Because the XOR operation and Fk can execute in parallel.
Counter (CTR) Mode
• CTR is a chained block cipher
• CTR concatenates a constant IV to a block-unique counter; fed as input to Fk
• Public counter sequence is arbitrary, but must be free of repetitions (in practice, counter starts at 0 and increments by one per block)
• Formally: ci := Fk(IV|CTRi) ⊕ mi
m1 IV|CTR c1
• Decryption analog to encryption: mi := ci ⊕ Fk(IV|CTRi)
• Benefits: Enc./Dec. parallelizable and random read possible
Integrity in Private-Key Crypto
Message Authentication Code (MAC)
• Integrity
• Message was not tampered with on its way from sender to receiver
• Message Authentication Code guarantees this based on secret key
Something is wrong!
Hell! Elice signk(Hello!)
Hello! Alice signk(Hello!)
MAC from Block Cipher
Signing Verification
Security: The adversary who doesn’t know the key cannot FORGE a valid signature!
Bob’s verification succeeds only if the message was generated by : Encrypting the entire message just for a signature is not efficient enough for practical purposes (signature length = message length)
Hash Functions (1/3)
• A (cryptographic) hash function is a deterministic function H(m) that takes as input a message m of any length and the following conditions hold:
• (COMPRESSION) The output of the function has a fixed length
• (COLLISION RESISTANCE) It is computationally hard (i.e., practically
impossible) to find two inputs m and m’ such that H(m) = H(m’)
• (ONE WAY) For a random message m, it is infeasible to infer m from H(m)
except by trying all possible candidates of m.
• Hash functions in practice:
• MD5 (broken, possible to find collisions efficiently)
• SHA-1 (partially broken, possible to find collisions in ~100 GPU years)
• SHA-2 (by NSA)
• SHA-3 (by Bertoni, Daemen, Peeters, van Assche)
believed to be strong as of now
Likelihood of Collisions
• How many people would you need to place into the same room on average such that at least two of them share a birthday (the date, not year)?
B: 300 (and I really always hated statistics).
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) • Reasoning behind birthday paradox
• Chances for one pair to match is low, but:
• Number of pairs n(n-1)/2 grows quadratic with number of participants n
• Number of pairs dominate the chance of collisions • Implications to hash functions
• Compression must not be too aggressive
• If hash digests to n bits, it requires about 2n/2 messages to find a collision
Hash Functions (3/3)
• Quality criteria for hashes
• Collision resistance: 2n/2 (attempts required ideally)
– “Hard to find any two collisions”
– Formally: Hard to find any m, m’ such that h(m) = h(m’)
• Preimage resistance: 2n
– “Hard to infer input from hash”
– Formally: Given h(m), it is hard to find m • Second preimage resistance: 2n
– “Hard to find collision for concrete input.”
– Formally: Given m, h(m) it is hard to find m’ != m such that h(m) = h(m’)
Alternative Hash Function #1
• A fellow student suggests the following hash function:
Which of the three fundamental conditions of a cryptographic hash function does it fulfill?
A: Only compression.
B: Compression and Collision Resistance.
C: Compression and One- Wayness.
Alternative Hash Function #2
• A fellow student suggests the following hash function:
H’(m) → AESenc(m, k) mod 2128
Which of the three fundamental conditions of a cryptographic hash function does it fulfill?
A: Only compression.
B: Compression and Collision Resistance.
C: Compression, Collision Resistance and One-Wayness.
Alternative Hash Function #3
• Can you come up (= invent) a better hash function that fulfills all three properties, i.e., one- wayness, compression and collision resistance?
B: What are you talking about.
C: Hold my beer…
Hash Example: SHA-1 (1/3)
• Designed by the NSA; broken (collisions within ~100 GPU years) • Better: SHA-2 (e.g., SHA-256), SHA-3 (a.k.a. Keccak)
• Still, we use the SHA-1 construction for educational purposes
• Input preparation
• Pad 1x bit “1” and then at least 64x bit “0” to a multiple of 512 bits
• Store original length in final 64 bits of padding • Split message into 512 bit blocks
• Feed each 512-bit block to compression function (next slide)
• Finally, apply output function to transform inner state into a digest
SHA-1 in Python: https://github.com/ajalt/python-sha1/blob/master/sha1.py SHA-1 in JavaScript: https://github.com/emn178/js-sha1/blob/master/src/sha1.js SHA-1 in C: https://github.com/clibs/sha1/blob/master/sha1.c
Hash Example: SHA-1 (2/3)
• SHA-1’s compression function c(Mi) first performs block expansion
• Expand 512-bit block Mi to 5x 512 bits
– Divide Mi (512 bits) into 16x 4B words: W0, …, W15
– Generate further 64x 4B words using prior words:
Wt = (Wt-3 ⊕ Wt-8 ⊕ Wt-14 ⊕ Wt-16) <<1 0 64
Length (in hex)
Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod\01\00\00\00......\00\00\00\00\00\00\00\00\00\50
Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed dia
crIsGS*~aMMALg:m5x1V"dZw-&)Zgu[eGs;?&+*0qE?
W0…W15 W16…W31 W32…W47 W48…W63
Wt = (Wt-3 ⊕ Wt-8 ⊕ Wt-14 ⊕ Wt-16) <<1
Hash Example: SHA-1 (3/3)
• Initialize variables A-E to well-defined constants (omitted for brevity)
• For each of the 80x 4B words compute:
• Atmp = E + (A << 5) + Wt + Kt + f(t,B,C,D)
• E := D; D := C; C := B << 30
• B := A; A := Atmp
• The sum of A’s, B’s, C’s, D’s and E’s, expanded by well-defined constants, represent the hash value
Kt = 230 Kt = 230 Kt = 230 Kt = 230
2 for 0≤t≤19
3 for 20≤t≤39 5 for 40≤t≤59 10 for 60≤t≤79
f() = (B&C)|(~B&D) for 0≤t≤19
f() = B⊕C⊕D for 20≤t≤39 and 60≤t≤79 f() = (B&C)|(B&D)|(C&D) for 40≤t≤59
Hash and MAC
Verification
If we combine a secure MAC and a cryptographic hash function the resulting scheme is still a secure MAC!
Merkle-Damgård Hash Function Construction
• Merkle–Damgård hash function construction
• Merkle–Damgård proposed a method to build collision-resistant hash
functions from collision-resistant one-way compression functions
• Iterate block-wise over input by splitting message into chunks M1 ... Mn • Apply collision-resistant compression function C to each block
• Final transformation g into a hash digest h(m)
M1 M2 M3 Mn IV C C C
Hash and MAC – The Wrong Way (simple keyed hash)
• Basic idea: hash over key and data using a secret prefix MAC • s = H(k | m)
• Susceptible to hash length extension attacks
• Merkle-Damgard hash constructions allow for extension attacks
• Assumption: Attacker knows H(k | m), m and len(k), but does not know k
• Goal: Compute H(m*) with m* = m | m’ without knowing/guessing k
• Basic idea: Resume hash computation
- Initialize inner state of hash (e.g., variables A-E in SHA-1) 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
- Works with an arbitrary number of added blocks!
- In practice, attacker has to consider the (deterministic) padding, too
• Attacker can sign arbitrary longer messages with this bad keyed hash
Hash and MAC – The Better (Yet Still Not Ideal) Way
• Basic idea: secret suffix MAC • s = H(m | k)
• Extension not possible, as key is at the end of the message to be signed • Still fundamental drawbacks:
• Broken if underlying hash function is not collision-resistant (which turned out to be true for, e.g., MD5/SHA-1)
• Weak for hash functions with swapped input order: H’(m) := H(reverse(m))
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)),
whereas k’ is derived by padding k with 0x00 bytes until size 512 bits
• To some extent resistant against collisions in the underlying hash function
padding (0...0)
opad = 0x5c,...,0x5c ipad = 0x36,...,0x36
Authenticated Encryption With Associated Data (AEAD)
• Some ciphers guarantee authenticated encryption (integrity + confid.)
• Example: Galois/Counter Mode (GCM)
• Extension of CTR mode
• Basic idea: Implicitly compute an authentication tag during encryption (which also includes the IV)
• Compute tag by multiplying previous tag with constant H in finite space
• Advantages
• Authenticate “on the fly”
GCM Mode Basic Operation
Source: https://en.wikipedia.org/wiki/Galois/Counter_Mode
during de/encryption
• Easy to parallelize decryption/encryption
Summary: Symmetric Encryption
• Shared private key can be used for encryption (once in OTP, or repeatedly in block ciphers) for to obtain confidentiality
• Block modes (ECB, CBC, CTR, GCM ...) have a significant impact on the overall encryption security
• MACs (usually paired with hash functions) guarantee integrity, so does Authenticated Encryption
Further Reading (e-book see library)
• Paar / Pelzl – Understanding Cryptography (2016) (“Kryptografie verständlich“, German version)
• Introduction (Chapter 1, up to 1.4.3 incl.)
• AES (Chapters 4.2, 4.4 and 4.5)
• Cipher block modes (Chapter 5.1)
• Hash functions (Chapter 11, up to 11.4 incl.) • MACs (Chapters 12.1 and 12.2)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com