module 9 Flashcards
What is the 2-step strategy for building a CRHF given a block cipher E?
- Given a CRHF for small fixed-size messages, we will build a CRHF for large, variable sized messages
- Build a CRHF for small fixed-size messages
What is Merkle-Damgard construction?
Given a compression function h (CRHF for small fixed-sized messages) we build a CRHF for large variable-sized messages
Take some file you want to hash.
You’re first going to split it into k bit chunks.
Say you t have L chunks. Once you’re done with all the chunks to the last chunk, what you’re going to do is you’re going to append a padding block.
You’re padding, the last message so that it is a multiple of k bits. This padding block has the following structure and is super important. The first one is padding so that it is a multiple of k bits, followed by the length of the message before you computed any padding.
For example, if my file was 275 bits, then the length is going to be 275 bits even if after adding padding.
Now, what does the padding look like? Well, the padding basically looks like a one followed by as many zeros as necessary. The length is just going to be a fixed 64-bit field. It’s going to consist of 64 bits.
(see corner cases)
we start with an IV (initialization vector, deterministic, not random!).
apply a compression function, which outputs n bits. and we continue doing this for each of the l k-bit blocks until we have a digest.
Explain some corner cases in the Merkle-Damgard construction.
- the last chunk of the message is small. say it is only 1 bit. you have 64 bits to account for the length. so you have k - 64 bits - 1 bit and that will be your pb. one 1 and then the rest will be zeros.
- the message happens to be a multiple of k. but you still need a padding block. so you have the 64 bits for the length and then k - 64 bits to pad.
- nl is not a multiple of k. so you need to add padding but there’s not enough space to add the 64 bits for the length. in this case, you start the padding on the second to last block and then in the last block add k-64 zeros and then finally the 64 bit length.
Theorem: if h is collision resistant then so is H
Prove this. Hint: show that a collision on H implies a collision on h.
???
How do we build a compression function from a block cipher?
- recall a block cipher (E,D) where E:{0,1}^k x {0,1}^n –> {0,1}^n
- we can build a compression function h: {0,1}^n+k –> {0,1}^n as follows
davies-meyer construction:
h(a||b) = E(b,a) xor a
Properties:
(1) compression: takes n + k bits as input and outputs n bits
(2) collision resistance: if E is an ideal cipher then h is collision resistant
consider the davies-meyer construction:
h(a||b) = E(b,a) xor a
why will there be collisions if we remove the xor a?
???
what is an ideal cipher?
a secure block cipher is a PRP
an n-bit cipher under a secret randomly chosen key is comp. indistinguishable from a randomly chosen n-bit permutation
but the above assumes the key is secret
in our construction of the compression function, the key is public (last k bits of the input). so what can we say about the block cipher?
Merkle-Damgard with Davies Meyer visual
Now that we have the Merkle-Damgard construction, we can see how the Davies-Meyer approach to building a compression function from a block cipher comes into play. What we’re going to do is, we’re going to take the k bits that make up the message and we’re going to take our initialization vector, which is n bits and we’re going to use the message as the key to the block cipher, not as the message through the block cipher, but as the key to the block cipher, because the message is k bits. That’s what we expect the keys to be. Then the initialization vector is going to be the message through this block cipher. We’re also going to be exploring the output of the block cipher with the initialization vector. This is going to produce some intermediate digest, lets call it d_0. Then we’re going to build d_1 by essentially doing the same thing. We’re going to take this message 1 and we’re going to use it as the key to this block cipher. Then we’re going to use the d_0 as the value to the block cipher that we’re encrypting, and then we’re going to XOR, the output with d_0, and that’s going to be d_1 and we’re going to repeat this process until finally we have our digest.
SHA256
- uses Merkle-Damgard construction
- Davies-Meyer compression function
- SHACAL-2 block cipher (not AES / assumed to approximate an ideal cipher; we cannot really build this)
Birthday paradox:
What is the probability that at least on of the 23 puppies is born on October 19?
Assuming one puppy is born on October 19, probability that at least one other puppy is also born on october 19?
part 1:
1 - Pr[no puppy is born on October 19] = 1 - (364/365)^23
1 - Pr[no puppy is born on October 19] = 1 - (364/365)^22
Probability that ANY 2 share a birthday
a little over 50%
any possible collision is okay, so this is why the percentage is so high
Birthday attack
Thanks to the birthday paradox, we only need to run this algorithm a few times to get a collision
takeaway: places a fundamental limitation on how short a digest can be / if the digest is too short, we can perform this birthday attack
Examples:
64 bit digests => O(2^32) operations (broken)
SHA1: 128-bit digests => O(2^64) operations (okayish, collisions already)
SHA256: 256-bit digest => O(2^128) operations (safe from generic attack)
length extension attack
the goal of the length extension attack is to essentially extend the hash of the message. In other words, given a hash of m, compute a hash of m plus something more, without knowing m. Here the key is that the attacker doesn’t know m, maybe m is secret and the victim didn’t release m, he just released the digest of m, and the attacker is interested in constructing a hash of m plus something else. How can an attacker do something like this? Well, the observation is that we can continue this chain. In other words, the attacker can use this digest as the initialization vector to the Merkle-Damgard construction. For example, let’s suppose that the attacker wants to extend m with some m-prime. In other words, the attacker ones that concarnation of m and m-prime. What the attacker will then do is start with the digest and then pass it as input and then process a block of m-prime. Then that’s going to produce some output. Process, another block of m-prime that’s going to produce some output, and then append a new padded block. This new padded block is going to have the length of the original message plus the padded block plus the new message that’s being appended. At the end, once we do the compression function on this padded block as well, we’re going to get this digest prime. What is this digest prime? Well, this digest prime is basically going to be the hash of our original message that the victim had hashed before, concarnated to the padding block that was part of the digest when the victim computed the hash of m, so this padding block concarnated to m-prime, which is the extension of the message that the attacker is adding via this attack. Notice this is not quite what we wanted. What we really wanted was a hash of m concatenated to m-prime. What we got is m concatenated to pb, to this padding block, concatenated to m-prime. But turns out this is still useful in many applications. You’re going to find some of those applications when you look at Project 2, when you’re actually going to be performing this exact attack.
MAC security game
A MAC M is secure if for all PPT A:
Adv_MAC[A,M] = Pr[Chal outputs 1] <= negl
what is a replay attack? how can we protect against it?
the adversary can do is the adversary can drop this message and just replay the previous message that Alice sent because notice this is a valid message and a valid tag. So the adversary cannot forge new messages, but it can replay old ones. And in some protocols, replay attacks can be very problematic, especially if the recipient is stateless, right? So if the recipient is stateless and it doesn’t keep track of all the tags that it’s seen in the past, this might be used to fool Bob into accepting a message again. So for example, this could be like a bank transaction and now you essentially charge Alice twice or something like that. So one way to provide this property known as freshness, in other words, that each message is a fresh message is people often add a counter. Okay, so they add a counter to their messages and then the recipient keeps track of this counter and every new message should have a mono-atomically increasing number. And so you can always get track to make sure that you are not receiving a replay of an older message. So that would be sort of a common solution. All right?
why is the merkle-damgard construction not a valid MAC construction?
due to length extension attacks that allow the adversary to come up with forgeries. even w/o access to secret key, the attacker can use the digest as the IV and keep appending more blocks. and then you’ll get a tag for the key plus all these messages plus the padding log. this is a valid forgery.
