ECS726P: Security and Authentication
Week 2: Perfect Secrecy, Practical Security, Symmetric Key Encryption
Pasquale Malacaria EECS, QMUL
Copyright By PowCoder代写 加微信 powcoder
Table of contents
1. Perfect Secrecy
2. Practical Security
3. Symmetric-Key Encryption
Stream Ciphers
Block Ciphers
Block Ciphers’ Modes of Operation
Learning Outcomes
• Perfect secrecy.
• Understand difference between theoretical and
practical security
• Understand that all practical cryptosystems are (theoretically) insecure.
• Recognise the concept of “practical” security.
• Identify the basic design features of AES, as the
current standard for symmetric key encryption;
• Being able to compare several different block cipher “modes of operation” and their properties.
Perfect Secrecy
Perfect Secrecy: definition
Definition
A cryptosystem has perfect secrecy if, after seeing the ciphertext, an interceptor gets no extra information about the plaintext other than what was known before the ciphertext was observed.
Perfect Secrecy: Implication of the definition
◃ Notice that the definition of perfect secrecy does not refer to any computational restriction. So even if attackers have all the computational power and all the time in the universe at their disposal, they still cannot learn anything about the plaintext beyond what they already knew before observing the ciphertext.
◃ In particular even exhaustive key search (brute-force) cannot break “Perfect Secrecy”!!
but is this ever achievable?
Achieving Perfect Secrecy!
Surprisingly, perfect secrecy is achievable simply!
◃ To see why consider this example: there are only two possible plaintext messages: ATTACK, RETREAT.
◃ Now, consider the following encryption/decryption:
Key K1 EK1 (ATTACK) = 0
Key K2 EK2 (ATTACK) = 1
EK1 (RETREAT ) = 1
EK2 (RETREAT ) = 0
◃ The (symmetric) “key” is “which row” the sender uses to encode its message. The sender chooses one of the rows randomly with probability 0.5.
Achieving Perfect Secrecy!
Key K1 EK1 (ATTACK) = 0
Key K2 EK2 (ATTACK) = 1
Suppose the adversary sees the ciphertext is 0.
What can they learn about the plaintext?
Suppose the adversary knows “in advance” (beforehand) that with probability of 0.9, the sender is actually going to send ATTACK. What would be the answer the previous question?
EK1 (RETREAT ) = 1
EK2 (RETREAT ) = 0
Achieving Perfect Secrecy
Let us represent our two plaintexts in binary numbers: ATTACK:0 RETREAT:1
Similarly, let us represent the key (which row) in binary: K1(first row):0 K2(second row):1
Then the table will become: 01
(k1 =0) E0(0)=0 E0(1)=1 (k2 =1) E1(0)=1 E1(1)=0
In words: if the key bit is 0, the plaintext bit is as-is (not
changed), and if the key bit is 1, the plaintext bit is flipped.
Achieving Perfect Secrecy!
(k1 =0) E0(0)=0 E0(1)=1
(k2 =1) E1(0)=1 E1(1)=0
Does this remind you of a binary operation? plaintext key ciphertext
000 101 011 110
◃ This is the XOR operation!
c = Enck (m) := m ⊕ k 8
Reminder: the XOR operation xyx⊕y
000 101 011 110
(if the two bits are equal then the XOR operation returns 0 otherwise it returns 1)
the XOR operation is fundamental in cryptography and used everywhere so please learn it well!
XOR is often performed on a pair of sequences of bits; in this case one should apply the ⊕ operation to each pair of bits in the pair of sequences:
x1x2···⊕y1y2···=(x1 ⊕y1)(x2 ⊕y2)… For example
0010 ⊕ 1001 = (0 ⊕ 1)(0 ⊕ 0)(1 ⊕ 0)(0 ⊕ 1) = 1011
Achieving Perfect Secrecy!
Going back to our example: what about decryption?
plaintext key ciphertext
000 101 011 110
◃ It should be straightforward to see that the decryption function is the same as encryption:
m = Deck (c) := c ⊕ k
Achieving Perfect Secrecy!
◃ In words: if the plaintext bit is “as-is” (so the key=0), we also leave it “as-is”, if it has been “flipped” (so the key=1), we “flip it back”. This is exactly describing XORing with the ciphertext again.
◃ Or formally:
(m ⊕ k) ⊕ k = m ⊕ (k ⊕ k) = m ⊕ 0 = m
Achieving Perfect Secrecy!
Now, suppose we had four possible plaintext messages:
ATTACK FROM NORTH (N), ATTACK FROM SOUTH (S), HOLD POSITION (H), and RETREAT (R).
K1: K2: K3: K4:
EK1 (N) = 00 EK2 (N) = 01 EK3 (N) = 10 EK4 (N) = 11
EK1(S) = 01 EK2(S) = 00 EK3(S) = 11 EK4(S) = 10
EK1(H) = 10 EK2(H) = 11 EK3(H) = 00 EK4(H) = 01
EK1(R) = 11 EK2(R) = 10 EK3(R) = 01 EK4(R) = 00
What happens if one of the rows is missing?
What if the same ciphertext is repeated in a row? What if the same ciphertext is repeated in a column?
“Latin square”
The above tables are examples of what are known as Latin Squares, i.e., tables with the following properties:
1. Every row contains every table entry exactly once.
2. Every column contains every table entry exactly once.
A Latin square can work as a recipe to achieve “perfect secrecy”. For encryption of a plaintext message:
◃ select one of the rows (the “key”) uniformly randomly;
◃ look up the ciphertext for the plaintext in that row.
The decryption is as follows:
◃ knowing which row is used, the recipient looks up which column in that row the ciphertext appears.
“One-Time Pad”
What happens if the key is not (uniformly) randomly picked for every message?
Hint: consider a scenario where the key is “renewed” after every other plaintext message. Attime1,themessageisHandthekeyisK1,sothe attackers see 10.
At time 2, the message is N, and the key still K1. So the attackers see 00. What do they learn?
K1: K2: K3: K4:
EK1(N) = 00 EK2(N) = 01 EK3(N) = 10 EK4(N) = 11
EK1(S) = 01 EK2(S) = 00 EK3(S) = 11 EK4(S) = 10
EK1(H) = 10 EK2(H) = 11 EK3(H) = 00 EK4(H) = 01
EK1(R) = 11 EK2(R) = 10 EK3(R) = 01 EK4(R) = 00
“One-Time Pad”
◃ As before, we can turn our Latin Square cipher from a looking-up process to an efficient binary operation:
N=00 S=01 H=10 R=11
00: E00(00)=00 E00(01)=01 E00(10)=10 E00(11)=11 01: E01(00)=01 E01(01)=00 E01(10)=11 E01(11)=10 10: E10(00)=10 E10(01)=11 E10(10)=00 E10(11)=01 11: E11(00)=11 E11(01)=10 E11(10)=01 E11(11)=00
◃ Hence, as before, the encryption is XORing with the key (like a “pad”) for both encryption and decryption.
• Since the key should be uniformly randomly picked for each message, hence the name “one-time pad”.
Perfect Secrecy: Vernam Cipher
This can be generalized to as many messages as one likes, in what is known as Vernam Cipher:
◃ So, we have a very simple cipher that can be implemented in the simplest hardware (very fast and low power) and achieve “perfect secrecy”! Where is the catch?
Practical Security
Practical Problems with Perfect Secrecy
◃ Recall that the Latin Square needs as many rows as there are possible plaintext messages. That is: we need as many keys as there are messages.
◃ E.g., for 256 possible messages, i.e., an 8-bit message, one needs 256 keys, i.e., an 8-bit key.
◃ To see why this is a problem, suppose you were
going to watch a movie (about 1 Gigabyte) online securely. Then you would need to have established a key of size 1 Gigabyte securely somehow! (compare that to only 128 bits that AES typically uses)
◃ To make matters worse, once we use that 1GB of key, it is now useless!
Theoretical vs. Practical Security
◃ In practice, we use only short keys (e.g. 128 bits) for potentially gigabytes of traffic! So we definitely violate “key length being the same length as the message length” and “uniformly selecting a new key per each message”, in other words, we are not using one-time-pad.
◃ What does it imply about the “security” of our encryption schemes?
Every practical encryption scheme that we use is (theoretically) insecure!
Theoretical vs. Practical Security
Unlike perfect secrecy, practical security of a cryptosystem is measured in terms of the difficulty of executing known attacks against it.
◃ Note that known attacks include but is not limited to brute-force (exhaustive key search).
◃ But how do we measure the difficulty? Answer: by comparing how long it takes to conduct an attack, given the computational power of an attacker and the cover time (the length of time for which a plaintext must be kept secret).
Theoretical vs. Practical Security
To compute how long it takes to conduct a known attack on a cryptosystem, we need:
◃ what computational processes are involved in the attack; and
◃ how much time it takes to conduct these processes.
A well-designed cryptosystem is usually built around a computational problem that is proven or at least widely perceived to be hard to solve.
◃ This is where the notion of algorithmic “complexity” becomes useful.
Theoretical vs. Practical Security
The complexity of an algorithm (or a process) refers the relation of the number of simple (1-time-slot) machine operations that need to be done to finish the process with respect to the length of the input (usually, its representation in binary).
◃ examples of simple (1-time-slot) machine operations: logical operations (AND, OR, XOR, NOT, etc), addition, comparison, etc.
Theoretical vs. Practical Security
Operation Complexity Explanation
Addition of two n- n bit numbers
Multipl. of two n- n2 bit numbers
Raising a number n3 to an n-bit power
(using repeated
squaring trick)
Exhaustive search 2n for an n-bit key
Ignoring carrying, one addi- tion for every bit.
n additions, one for every bit of the input numbers.
n operations, each is either a squaring or a multiplication, both of which take n2 opera- tions, hence n3 in total.
trying out every possible n-bit
key, of which there are 2n.
Theoretical vs. Practical Security
For this module, you just need to appreciate that there two main classes of complexities: polynomial vs. exponential:
polynomial: if the time taken to execute the process for an input of size n is no greater than nr , for some r
◃ Informally, these are ‘quick’ on all inputs of ‘reasonable’ size. E.g.: multiplication of two n-bit numbers (complexity n2), raising a number to an n-bit power (n3), so all ‘easy’ processes.
exponential time if the time taken to execute the process for an input of size n is ∼ an, for some a.
◃ Informally, these are ‘too slow’ on all inputs of ‘reasonable’ size, as it becomes practically impossible to carry out. E.g. exhaustive search for an n-bit key.
Theoretical vs. Practical Security
Est. Attack Time (s) = complexity of the process computer speed (# operations/second)
Complexity n=10
n 0.00001s
n3 0.001s 2n 0.001s 3n 0.059s
0.00003s 0.027s
17.9 minutes 6.5 years
37.7 years
200 mil. centuries!
Execution time on a (single) processor capable of one million operations/sec. There is a significant difference between processes with polynomial vs. with exponential complexity.
Theoretical vs. Practical Security
So to summarise, for a measure of practical security: We need to make sure that all known attacks will take impractically long to finish. This implies:
◃ Making sure that the the computational complexity of all known attacks are at least exponential.
◃ Then choose large enough parameters (e.g. key length) such that (given a ‘reasonable’ estimate about the computational power of attackers), the attack time is ‘sufficiently’ longer than the cover time of the plaintext.
Semantic Security
(side note)
The notion of practical security can still be formalized:
Semantic Security : “a cryptosystem is semantically secure if any probabilistic, polynomial-time
algorithm (PPTA) that is given the ciphertext of a certain message m (taken from any distribution of messages), and the message’s length, cannot determine any partial information on the message with probability non-negligibly higher than all other PPTA’s that only have access to the message length (and not the ciphertext)”.
Questions?
Symmetric-Key Encryption
Stream Cipher vs Block Cipher
◃ Stream Cipher: Process one plaintext bit at a time.
◃ Block Cipher: Process a block of plaintext at a time.
Stream cipher
A keystream (a stream of pseudo-random bits) is generated from a secret key and the plaintext bits are XOR’ed with it.
◃ The keystream generator is a Cryptographically Strong Pseudo-Random Num. Gen. (CSPRNG).
– what does each of these terms mean? what qualifies as a CSPRNG? how to construct one?
◃ A practical stream cipher tries to mimic the Vernam stream cipher (Q: what are the similarities and what are the differences?)
Properties of stream ciphers
We say that error propagation has occurred if a number of errors in the ciphertext leads to a greater number of errors in the resulting plaintext.
Q: Where may such errors come from?
Q: If a steam-cipher is used, a 1 bit of error in the cipher-text results in how many error bits in the deciphered plaintext?
Q: Based on this property, what kind of application scenario it is good for? (high-error environment/low error environment?)
Properties of stream ciphers
◃ XOR is very fast to operate
On-the-fly encryption
◃ large chunks of plaintext do not sit around in registers
before being encrypted. Implementation efficiency
◃ Some stream cipher designs can be implemented in hardware extremely efficiently
For all these reasons, it is used in applications like mobile communications (3G/4G/5G), wifi, wimax, etc.
Disadvantage: critical need for synchronisation (what does it mean? why?)
Properties of block ciphers
Advantages of block ciphers (like AES):
◃ Versatility: not just used for encryption
◃ Compatibility: widely implemented and used in
encryption algorithms
◃ Adaptability: can be implemented in different modes of operation
Properties of block ciphers
Disadvantages of block ciphers (like AES):
◃ Error propagation: 1-bit transmission error of a ciphertext block will result in a plaintext block with, on average, half of its bits incorrect (why?)
◃ Need for padding: Block ciphers operate on fixed block sizes (such as 128 bits) but the length of most plaintexts is not a multiple of the block size, e.g., for a 400-bit plaintext, how many blocks will be needed?
Data Encryption Standard (DES) was the most well-known, well-studied, and well-used block cipher, constructed based on the “Feistel” design model:
Feistel cipher
Feistel encryption:
Q: what is Feistel decryption?
DES: attributes
DES was a block cipher with:
◃ Block size : 64 bits
◃ Key length : 56 bits
◃ Number of rounds: 16
Main issue: Inadequate key length. Modern dedicated hardware can search a 56 bits DES key in less than a day!
(side-note)
Triple-DES was introduced as an interim solution without replacing DES completely:
Advanced Encryption Standard (AES) – security standard for symmetric encryption most likely you encounter
◃ In 1998, NIST issued a call for proposals for a new block cipher standard to be referred to as the AES.
◃ The selection process was by an open public ‘competition’ and the chosen algorithm and design details made freely available.
◃ The Rijndael1 algorithm developed by Joan Daemen and (Belgium) was selected.
1pronounced like rain-doll!
AES is an iterated block cipher, based on a “substitution– permutation” network design principle. AES encryption:2
2Animation of AES (Rijndael) block cipher (hyperlink)
AES attributes
Key length: variable: (128, 192, or 256 bits).
Block size: 128-bit (fixed)
◃ AES performs all of its computations on bytes rather than bits. Hence, AES first interprets the 128 bits of a plaintext block as 16 bytes.
◃ AES computes a number of rounds. Each of these rounds uses a different 128-bit round key, which is calculated from the original AES key.
The encryption and decryption algorithms of AES have to be separately implemented, although they are very closely related.
AES is now widely adopted and supported in both hardware and software, including (even) for low-cost environments such as RFID.
◃ So far no practical cryptanalytic attacks despite great deal of scrutiny and analysis;
◃ has built-in flexibility of key length, which allows a degree of “future-proofing” against exhaustive key searches;
◃ However, as for any cryptographic algorithm, the use of AES only guarantees security if it is correctly implemented and good key management is applied.
Block-ciphers: Modes of Operation
Modes of operation: a generic block cipher can be used in different “modes” with distinct properties when applied to plaintexts longer than one block.
◃ These modes are designed to improve the encryption of block ciphers using the same key: A block cipher processes one block of data at a time, using the same key.
◃ Without these modes of operations, for a given key, the encryption would produce the same ciphertext for the same plaintext. THIS WOULD BE REALLY BAD! (Q: Why?)
Electronic Code Book (ECB) mode
A block cipher processes one block of data at a time, using the same key:
This mode should be avoided for encryption, especially when the plaintext is any longer than a single block (why?)
Cipher Block Chaining (CBC) mode
Encryption procedure in CBC mode:
P0 P1 P2 Pn
k Enc k Enc k Enc ······ k Enc C0 C1 C2 Cn
Notations: P0,. . . ,Pn: blocks of plaintext. C0,. . . ,Cn: blocks of ciphertext. k: cryptographic key. : the encryption block of the block cipher. ⊕: XOR (eXclusive OR) operator. IV : initialisation vector.
Cipher Block Chaining (CBC) mode
◃ Note: the key k is the same across encryption blocks.
◃ Also note: while the key k must be kept secret
(shared only between sender and the receiver), the initialisation vector, IV , is not assumed to be secret (so it can be sent in the clear over the channel!).
– Q: why do we even need an IV here?
– Q: how is the fact that the IV is not kept secret OK?
how does it not compromise the security of the
encryption?
◃ Note that now, the encryption of each block depends
on the encryption history.
– Q: Does this resolve the main problem with the ECB
mode? how?
Cipher Block Chaining (CBC) mode
Decryption procedure can be readily derived from the encryption procedure, and vice versa (how?)
C0 C1 C2 Cn k Dec k Dec k Dec ······ k Dec
P0 P1 P2 Pn
CBC decryption. Note that instead of blocks, we now must use blocks, why?
Cipher Block Chaining (CBC) mode
◃ Q: What’s the “error propagation” for the CBC mode (if 1-bit of error occurs during transmission of the ciphertext, how many extra bits will be in the recovered plaintext?)
– Hint: just mark one bit of one ciphertext block as erroneous, and follow its effect on the plaintext blocks in the decryption process (from the previous page).
Cipher Block Chaining (CBC) mode: Properties
+ Positional dependency: ciphertext is affected by position of the plaintext (besides the plaintext & key!)
∼ Limited error propagation (fully analyse!)
+ No synchronisation required: in the sense that the
receiver could miss the beginning of the ciphertext and still succeed in decrypting from the point the ciphertext is received (why?)
∼ Efficiency: only slightly less efficient than ECB thanks to XOR (fast!) but cannot be parallelised!
− Need for Padding: Plaintext must be padded before encryption (why?)
+ Implementation advantage: CBC mode forms the basis for a well-known data origin authentication mechanism (CMAC), to be discussed in later lectures.
Cipher FeedBack (CFB) mode
CFB Encryption:
k Enc k Enc k Enc ······ k Enc
P0 P1 P2 Pn
C0 C1 C2 Cn
Notations: P0,. . . ,Pn: blocks of plaintext. C0,. . . ,Cn: blocks of ciphertext. k: cryptographic key. : an encryption block of the block cipher. ⊕: XOR (eXclusive OR) operator. IV : initialisation vector.
Cipher FeedBack (CFB) mode
Again, decryption algorithm can be derived from the encryption algorithm and vice-versa (how?)
k Enc k E
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com