# Stream Ciphers
# What is a Cipher?
Definition: A cipher defined over is a pair of “efficient” algorithms where:
where is referred as key space, is referred as message space, is referred as cipher space.
Sometimes we also use notation
PT (Plain Text) and
CT (Cipher Text).
The function is called encryption and is called decryption. While means the consistency that given a key , then for any message , the decryption of the encryption of is .
What is also important that we always assume that the function and are open to the public, while only the key is kept secret.
- Example:The One Time Pad
Where is bitwise xor. The One Time Pad is fast and secure if we choose the randomly. However, it needs as long keys as the plain text.
# What is a secure cipher?
Let’s assume that the attacker only have the
CT , and the secruity requirement is that the attacker cannot get any information from it.
Definition (Information Theoretic Security, Shannon 1949): A cipher over is perfect secrecy if:
where means that subjects to the uniform distribution over .
The definition indicates that given
CT can’t tell if the message is or , in other words, the attacker cannot get any information about
PT from the
However, other attacks (not only from
CT ) may be possible.
OTP is a perfect secrecy cipher, it reveals nothing about
PT .(except possible maximum length, from wikipedia).
Proof: First given a message, we can pad it with 0 to the maximum length of . Then:
because , so the number of keys satisfying this condition is .
Then the proof is self-evident, since for any
CT , the probability of encryption is all the same.
Theorem: If a cipher over is perfect secrecy, then:
Which indicates that if we want a cipher to be perfect secrecy, we need to have at least as many keys as messages, which is impractical.
# Pseudorandom Generators
How to make
OTP more practical?
- Idea: to replace the “random” key by “pseudorandom” key, which is much smaller.
Definition: A pseudorandom generator
PRG is a “efficient” function:
where is called the seed space.
Now since the length of is much smaller than plain text, so it’s impossible to be perfect secure. However, we will define other security requirements later.
PRG is predictable if there exists an “efficient” algorithm such that:
where is a non-negligible const.
The definition says that, the
PRG is predictable if there exists an algorithm, which is able to predict the bit of the output given the first bits of the output. And works well in most cases.
- Example: random() function if glibc:
is a typical weak
PRG and should NOT be used for crypto.
# Negligible vs. Non-negligible
- In practice: Whether is negligible is defined as a scalar, e.g. is non-negligible since it is likely to happen in 1GB data.
- In theory: is a function . is negligible if congruent to 0 faster than . While is non-negligible otherwise.
# Attacks to
# Two time pad is insecure!
If we use the cipher key more than once:
then the attacker can get by xoring .
There are enough redundancy in English and ASCII to recover by knowing .
- Real world examples:Project Venona, MS-PPTP
OTP is malleable and provides no integrity!
which means that tha attacker can easily modify the plain text even don’t need to know about it.
If the attacker get a
CT , then he can modify it by , and send it back. The receiver will decrypt it as , which is modified by the attacker.
# What is a secure
Definition: A statistical test on is an “efficient” algorithm , s.t. outputs “0” or “1”.
- Example: outputs “1” iff . Meaning that if the number of 0 and 1 is not too different, then the test believes that the string is random.
Definition(Advantage):let be a
PRG and a statistical test on , then the advantage is defined as:
which says given a stat. test , whether can tell the difference between
PRG and a real random.
Definition: We say a
PRG is a secure
PRG if “efficient” statistical test , is negligible.
Lemma: a predictable
PRG is insecure.
Proof: if is a predictable
PRG , then there exists a predict algorithm satisfying:
Now we can define a statistical test separating and random:
For real random, we have:
because in real random, and are of the same probability.
and we have:
Theorem(Yao’82): an unpredictable
PRG is secure.
Definition: Let be two distributions over , then we say are computationally indistinguishable if for any “efficient” statistical test ,
is negligible. Denoted as
# Semantic security
Definition: We say a cipher over is semantically secure if:
where is a probability distribution over .
Given and an “efficient” algorithm , we can define two experiments:
Adversary give two messages to the challenger, then the challenger will give back the cipher text determined by and randomly chosen . But don’t know , then will guess the value of .
Let is "when and is randomly chosen, the probability that guess ".
And let is "when and is randomly chosen, the probability that guess ".
then is semantically secure if for any , is negligible.
- Example: Given a cipher, which we can guess the last bit of
CT. Then we can construct a :
- choose two messages with different last bit.
- pass to the challenger.
- after receive the
CT, guess the last bit of
- output the guess.
in this case, . Since can always guess right. So it’s not semantically secure.
Lemma: Perfect secure Semantically secure.
# Stream ciphers are semantically secure
Theorem: Let be a
PRG , then is a secure
PRT stream cipher
OTP derived from is semantically secure.
Proof: we just need to prove that, adversary , s.t.
Given an adversary , we can construct two experiments:
one using and one using real random to crypt.
Let is when , the guess of first exp is 1.
Let is when , the guess of first exp is 1.
Let is when , the guess of second exp is 1.
Let is when , the guess of second exp is 1.
OTP is perfect secrecy when real random:
Next we need to construct an adversary to
PRG , and prove:
We can construct as follows:
Since , so:
PRG is secure, then is negligible, then is negligible.
# Block cipher
# What is a block cipher?
- Example: 3DES,n=64,k=168
- Example: AES,n=128,k=128 or 192 or 256
The process of encryption is:
for 3DES,n=48; for AES,n=10.
Definition: Pseudo Random Function
PRF defined over :
such that exists an “efficient” algorithm to evaluate .
Pseudo Random Permutation
PRP defined over :
such that :
- Exists “efficient” deterministic algorithm to evaluate .
- The function is one-to-one.
- Exists “efficient” inversion algorithm .
- Example: 3DES, where .
Definition: Let be a
PRF and . Then the
PRF is secure if a random function in is indistinguishable from a random function in .
- An easy application: let be a secure
PRF, then we can construct a secure
PRG is parallelizable and is secure.
# Data encryption standard (DES)
The core idea of
DES is Feistel Network: Given functions , build an invertible function :
It’s easy to construct the inverse network:
Theorem(Luby-Rackoff’85): if is a secure
PRF , then 3-round Feistel Network is a secure
DES is a 16-round Feistel Network, the Key size is 56 bits and block size is 64 bits, in other word, :
where works as follows:
where half block is and subkey is . “E” stands for some shifts and expand tricks, “P” is for permutation, while the “S” S-Box are functions . The choice of S-Box function matters a lot.
If the S-Box is linear, like:
then we can rewrite it in matrix as .
DES is entirely linear, and we have:
which is insecure.
Choosing S-Box and P-Box randomly would result in an insecure block cipher, the key would recover after outputs [BS’89]
There are several rules to choose P-Box and S-Box, the most important one is never choose any linear function.
# Exhaustive Search for block cipher key
Goal: given a few input output pairs , find the key .
DES is an ideal cipher (indistinguishable from a random permutation function ), then , there is at most one such that with probability .
so the probability that there does not exists is .
For two DES pairs , the prob. that key is unique is .
So with exhaustive searching method, we can find the key in time .
We can strengthen
DES against exhaustive search.
Method 1: Triple-DES, let as
for 3DES, key size=168 bits.
Why we don’t use Double
DES ? like ?
We will introduce a Meet in the middle attack:
Then we can construct a table:
and sort the table by the second column .
Then we can enumerate , and binary search in the table, to find .
So the total time is which is not large enough.
Method 2: DESX
It’s noteworthy that if DESX is defined as or , then it does nothing, it’s as vunerable to exhaustive search as DES.
# AES block cipher
Advanced Encryption Standard
Key size: 128 or 192 or 256 bits
Block size: 128 bits
where the input is 4x4=16 bytes and the key is 16 bytes.
each round contains 3 function:
- Bytes substitution: a non-linear function 1 byte 1 byte. The S-Box is a 256-size table.
- Shift rows:
- Mix columns: the four bytes of each column of the state are combined using an invertible linear transformation.
where the addition is XOR, multiplication is the multiplication of polynomials module , which is the minimal irreducible polynomial of degree 8.
[BK’09] Given pairs of input and output from 4 related keys in AES-256, can recover keys in time .
# Block ciphers from
Can we build a
PRF from a
Let be a secure
PRG , then Define 1-bit
Theorem: if is a secure
PRG , then is a secure
Similarly, we can construct n-bit
We can prove that is a secure
PRF with the theorem given above:
where stands for the real random number.
Lemma:We can build a secure
PRP by a secure
PRG with the Luby theorem and construction mentioned above.
# More discussion about
Firstly we introduce the equivalent definition of secure
Let’s make a brief explaination.
- is fixed and the adversary don’t know.
- Adversary can make several queries to challenger, each query can be modified according to the response of the last query.
- For the query , if , then the challenger should randomly choose a , then respond to the adversary.
If , then the challenger should randomly choose a function and respond to the adversary.
- After queries, the adversary will give the guess that or .
- EXP(0)=1 means that and the adversary guess . EXP(1)=1 means that and the adversary guess .
- Obviously, for a fixed adversary algorithm, due to the random choice of , the guess of adversary may vary. So we have the probability.
Similarly, we can define the secure
Noticing that the only difference is randomly choose in Permutations on .
- Example: all times algorithm have .
Lemma: Let be a
PRP over , then for any q-qeury adversary , we have:
So if is large enough, then a secure
PRP is also a secure
# Use block cipher: one time key
Don’t use the block cipher in Electronic Code Book(
The problem is that if , then .
Then we can introduce the semantic security of the cipher:
should be negligible.
ECB is not semantic secure.
Proof: Construct an adversary such that:
One secure construction is Deterministic counter mode from a secure
Theorem: For any , if is a secure
PRF over , then is a semantic secure cipher over .
In particularly, for any efficient adversary attacking , there exists an efficient PRF adversary such that:
# Use block cipher: many times key
Key used more than once adversary can see many
CT s with same key.
Adversary’s power: Chosen Plain text Attack(
- Adversary can choose a
PTand obtain its
CPAis quite a conservative abstract of the reality.
Adversary’s goal: To break semantic security.
Since the adversary can choose
PT , then we can introduce the semantic security over many-time key:
- After the random choice of , is fixed for the queries.
- Adversary can modify query according to the response of the last query.
- If the adversary just want to know , then he can query with .
- Other stuff is similar to the previous definition.
- Example: if the key is used more than once, and for fixed , is always the same, then it is not semantic secure. We can construct:
So we need to solve the problem that many-time key cipher is not semantic secure.
Solution 1: randomized encryption, where is a randomized function:
PT -size+#random bits.
Solution 2: nounce based encryption:
so that pairs are used only once.
# Use block cipher: Cipher Block Chaining(
Let be a
PRP , then we can construct a chain of :
where IV stands for initial vector, and is chosen randomly in .
The decryption circuit is:
Theorem: If is a secure
PRP over then is semantic secure under
CPA over .
In particular, for a q-query adversary attacting ,there exists a
PRP adversary such that
- Example, suppose we want , then for AES , we should guarantee . So after encrypting blocks, we should change the key.
for 3-DES, , so .
Warning: the IV must be chosen randomly each time of encryption!
CBC where attacker can predict IV is not
Proof: if given IV0, then IV1 is predictable, then we can construct the adversary:
- Since IV is in the head of
CTso the adversary can obtain IV.
- Once obtained IV0, the attacker will predict IV1.
- The blue box is , which is the same
PTin the first query .
A obvious modification is that we won’t give the adversary IV, that is we encrypt IV into a nounce:
# Use block cipher: Counter Mode (
Construction 1: rand
CTR , randomly choose an Initial Vector(IV):
Construction 2: nounce
CTR , we choose IV with counter:
Theorem: If is a secure
PRF over , then is semantic secure under
CPA over .
In particular, for a q-query adversary attacking , there exists a
PRF adversary such that
- Example: q=#messages encrypted with k, L=length of max messages, suppose we want , then for AES , we should guarantee . So after encrypting
CTs each len of , we must change the key.
# Message integrity
# Message Authentication Code(
The goal in this section is integrity while no confidentiality.
Definition: MAC defined over is a pair of algorithms:
- outputs .
- outputs ‘yes’ or ‘no’.
Let’s make a brief explaination. Alice uses message and generate function to generate a tag, and sends both message and tag to Bob. Bob uses the verification to verify if the message’s integrity.
- Example: generate function is , then the attacker could easily modify the message without being noticed.
The essence behind the example is that CRC is designed to detect random, but not malicious errors.
Let’s define a
which means that the attacker’s power is Chosen Message Attack, he can choose and query several times, and the challenge would response the tag.
Then the attacker’s goal is to construct a pair of message and its corresponding tag not in the queries.
If the attacker can construct such a pair, then the
MAC is not secure.
MAC is a secure
MAC if forall “efficient” adversary A:
- Example: In operating systems, every file and its filname is signed by a
MACto ensure the integrity of the file. So the virus can’t modify the file without being detected.
MAC based on
PRF , we can construct a
- : outputs ‘yes’ if and ‘no’ otherwise.
notice that when is too small, then the attacker can guess the tag easily.
Theorem: If is a secure
PRF and is negligible, then constructed as above is a secure
In particular, for every efficient adversary attacking , there exists an efficient
PRT adversary such that:
- Example: AES, A
MACfor 16-byte messages.
How to convert small
MAC to big
MAC ? We just need to convert small
PRF to big
PRF . Methods:
Construction 1. encrypted
Let be a
PRF , then the construction above defines .
NMAC (nested MAC)
Let’s consider why the last encryption step in
CBC-MAC is necessary?
Suppose we just define , where .
Then could be easily broken by chosen message attack:
- Choose an arbitrary one-block message .
- Request tag for , get .
- Ouput put t as MAC forgery for the two-block message . since:
so tag and message can be constructed and verified.
Theorem: For any , for every efficient q-query
PRF adversary attacking or , there exists an efficient adversary such that:
CBC-MACis secure as long as .
NMACis secure as long as .
- Example: For AES, if we want , then , since , so after messages must change the key.
Let’s see an attack when the key is not changed.
It’s easy to prove that
NMAC have the extension property:
let be a big
PRF that has the extension property, then we can attack it as following:
- Issue messages queries randomly, and obtain responses .
- We can find collision with high probability, according to the birthday paradox.
- Choose arbitrary and query for .
- Output .
So a better rand construct is Rand CBC
ECBCis commonly used as an AES-based
MAC. e.g. CCM encryption mode(used in 802.11i).
NMACnot usually used with
3DES, the main reason is that it changes the key on every block, so it needs to do the key expansion several times.
MAC (e.g. constructed by
ECBC )'s message length is not a multiple of block size, we need to pad the message.
Padding with all 0s.
MAC becomes insecure in that the attacker can obtain the tag of then output , since
For security, padding must be invertible, and secure:
Construction 2. (ISO)
Pad with “100…00” and Add new block if needed.
- Example, if block size = 8, then , .
Obviouly the padding strategy is invertible since one can remove several 0s until a single 1, then get the original message. It is secure as well.
Construction 3. (CMAC NIST standard)
key = , if we need padding then use the left circuit, otherwise use the right one.
- No final encrypton step, since extension attack is thwarted by last key xor.
- No dummy block, since we separate the cases with two different keys.
# PMAC and Carter-Wegman MAC
NMAC are sequential, can we build a parallel
MAC from a small
Of course, it is named
PMAC (Parallel MAC):
the function here is used to encrypt sequence, to avoid swap attack. Without , the attacker could swap two blocks and get the same tag.
Theorem: For any , If is a secure
PRF over then is a secure
PRF over .
In particular, for any efficient q-query
PRF adversary attacking , there exists an adversary such that:
If only one block of
PMAC is changed, then the tag can be re-computed quickly.
MAC is another kind of
MAC not based on
If the key is changed on every message like
OTP , then the attacking game could be defined as:
so the attacker could only query 1 message.
- Example, one time
- let be a large prime (e.g. )
- , two random int in .
- where each block is 128 bit int.
is a polynomial of degree .
Theorem: the one-time
MAC in the last example, we have:
So basicly given the adversary has no info about .
By one time
MAC we can construct many-time
MAC with high speed:
Let be a secure one-time
MAC over .
Let be a secure
for random .
So given , we can run the verification function as:
Theorem: If is a secure one time
MAC and is a secure
PRF then CW is a secure
MAC outputting tags in .
# Collision resistance
So far, four
Definition: Let be a hash function (),
A collision for is a pair such that:
A function is collision resistant if for all explicit efficient ,
Let be a
MAC for short messages over (e.g.
Then we can construct a
Theorem: If is a secure
MAC and is collision resistant then is a secure
Suppose is not resistant, and the attacker can obtain collision . Then after quering the tag for , the attacker can output since .
# Generic birthday attack
Theorem (birthday paradox): Let be independent identically distributed integers. Then when then .
Proof: we only prove when are all subject to uniform distribution (it’s the worst case):
So a generic attack is randomly choose elements in , then with a high probabilty that we can find a collision. .
# The Merkle-Damgard Paradigm
CR (collision resistant) hash function for short messages, we can construct
CR hash function for long messages. That is Merkle-Damgard iterated construction:
Give , we obtain .
We say is compression function and is the chaining variables (the output of each ).
if no space for at least 65-bits padding block, then add another block.
Theorem: If is collision resistant, then so is in Merkle-Damgard paradigm.
Proof: We prove collision on collision on .
Suppose , then we consider the chaining variables:
And we have
If or or , then we obtain a collision for .
Otherwise, we have , we can repeat the process above, since (collision for ), then at least can we find , then the collision for is found.
# Constructing compression functions
Suppose is a block cipher, then the Davies-Meyer compression function is:
Theorem: Suppose is an ideal cipher (is a collection of random permutations), then finding a collision takes evaluations of , and it’s the best cost possible.
And there are other compression functions based on block cipher:
- Miyaguchi-Preneel: , and the hash function “Whirlpool” is constructed by this compression function.
- , this one is insecure!
HMAC : a
MAC from SHA-256
We now talk about
MAC from a Merkle-Damgard hash function.
If is a collision resistant hash function, then we construct
MAC with it.
This one is insecure! Since Merkle-Damgard iteration has the extension property, so given , we can compute for any .
Construction 2. Standardized method:
where ipad and opad are consts defined previously.
It’s quite similar to
if we view the output as the input two keys for
NMAC . However, in
HMAC , and are not independent.
HMAC is assumed to be a secure
PRF , secure bounds are similar to
NMAC – need to be negligible.
# Timing attack on
In the process of verification, if we need to compare two strings, actually it’s comparing chars one by one, and return immediately if find a inequality.
So there is a timing attacking strategy:
- Query server with the message and a random byte.
- Loop over all possible first byte of tag, and query server. If it takes a little longer time to respond than step 1, then we find the right first byte tag for the message.
- Repeat the process to find other bytes of the tag.
So the attacker would not know the values being compared.
# Authenticated Encryption
# Active attacks on CPA-secure encryption
In this module, we talk about encryption against tampering, to ensure both confidentiality and integrity.
Without integrity, the confidentiality is vunable to active attacks.
- Example: In IP packet, the attacker could just modify the beginning:
then the server will “help” to decrypt the packet and send it to the attacker. In this case, the lack of integrity causes the confidentiality to be vunable to active attacks.
We can conclude lessons:
CPAsecurity cannot guarantee secrecy under active attack.
We use only two modes:
- If message needs integrity while no confidentiality, use a
- If message needs both integrity and confidentiality, use
authenticated encryption(this module).
Definition: An authenticated encryotion system is a cipher where
where is the space of nounce, and is optional. stands for the state that the cipher text is rejected.
The system is supposed to provide semantic secure under a
CPA attack and ciphertext integrity.
CPA attack is introduced before, it means that the attacker should not be able to distinguish two experiments by just querying several .
While for ciphertext integrity, it’s natural that the attacker should not construct a ciphertext that is accepted:
has ciphertext integrity if forall efficient ,
Definition: cipher has authenticated encryption (
AE ) if:
- semantically secure under
- has ciphertext integrity.
IVdoes not provide
AE, since it never outputs so the integrity is not guaranteed.
AE is guaranteed, what intuition can we get?
- authenticity, which means that the attacker could not fool Bob into thinking a message is sent from Alice:
- Security against
# Chosen ciphertext attacks (
Adversary’s Power: both
- Can obtain the encryption of arbitrary messages of his choice.
- Can decrypt any ciphertext of his choice, other than chosen plaintext.
Again, this is quite a conservative modeling of real life.
A more formal definition is as following:
CCA secure if for all efficient :
The attacker could first do the
CPAwith two 1-block messages , and get . Then the attacker can use
CCA, to query the decryption of , the decryption is , then the attacker can learn .
Theorem: Let be a cipher that provides
AE . then is
In particular, for any q-query efficient , there exists efficient such that:
Step 1. Since
AE guarantees ciphertext integrity (
CI ), then the attacker shouldn’t be able to construct any acceptable ciphertext other than ones he challenged. So it would be indinstinguishable thath the challenger always outputs in
Step 2. Since the challenger always outputs , then the
CCA queries is useless, we can ignore it. And because
CPA security, then it’s indistinguishable that the response to
CPA query is or :
Step 3. Similar to step 1, we can get back to
CCA queries. So as a whole:
# Constructions from ciphers and
It’s quite natural that since we need both
CPA secure and integrity, can we just combine the
CPA secure cipher and a secure
MAC ? There are three choices:
MAC-then-encrypt (SSL), which means that tag for
MACis also encrypted.
MAC(IPsec), which means that the tag is for the encrypted cipher text and not encrypted.
MAC(SSH), which means that the tag is for the plain text and not encrypted.
MAC-then-encrypt may be insecure against
CCAattacks. However when is rand-
CTRmode or rand-
CBCmode, then it provides
CTR-mode encryption then CW-
CTR-mode encryption then
Instead of the combination of secure encryption and
MAC , can we construct the
AE mode directly? Yes, it’s
where is a secure
PRP , and is similar to the one in
PMAC , the purpose of it is to emphasize the order. And is nouce, which should be distince between messages but does not need to be random, so a counter is sufficient.
CBC paddings attacks
MAC -then-encrypt mode, the decryption is three steps:
- Decrypt the cipher text.
- Check the padding to see if it’s valid.
- Check the tag to see the integrity.
So there are two petential erros: Padding error and MAC error.
Suppose the attacker can distinguish the two types of erros, then he can submit ciphertext and learns if last bytes of plaintext are a valid pad.
Let’s give an example for
If we want to know the very last byte of the plaintext, then we just iterate , and change the last byte of the second last block:
We know that is a valid pad. So if and only if when the last byte of the last block is equal to , then the decryption of it will be , and is a valid padding. Otherwise the attacker will get a padding error.
Similarly, by different length of padding, the attacker can get the bytes one by one.
MAC will completely avoid this problem.
# Special attack: attack on non-atomic decryption
SSH Binary Packet Protocol
The process of decryption is:
- decrypt packet length field only!
- read as many packets as length specifies.
- decrypt remaining ciphertext blocks.
- chech the
So if the attacker wants to know the plaintext of a given ciphertext (Notice here the ciphertext is given but not constructed by attacker, so it’s not a
CCA attack), then it can repeat sending 1-byte messages to the server until get a “
MAC -error”, then the left 32 bits of the plaintext (length field) will be learned by the attacker.
# Odds and ends
# Key derivation
Suppose the source key
SK is uniform in , and is a
PRF with key space and outputs in .
And we can construct a Key Derivation Function
where is used to identify different applications, even two applications have the same
SK , they will get the different key.
What will happen if the
SK is not uniform?
We know that the
PRF 's outputs will not look like random any more.
The solution is Extract-then-Expand paradigm:
where salt is a fixed non-secret string chosen at random, and after the extraction, the distribution will be uniform.
The implemention of the extractor is not going to be discussed here, but we know that
HKDF is a
KDF based on
HMAC , which is widely used.