Hash Functions and MACs Flashcards
Explain what Preimage resistance is.
A function is preimiage resistant if it is very time consuming to find the input of the output.
Explain what second preimage resistance is.
Given a hash function described as H(x)=y, it should be hard to find a value of x’ such that H(x’) = H(x) = y.
hard -> not thesible.
Explain what collision resistance is.
Given a hash function H, it should be inthesible to find two values (x1, x2) such that H(x1) = H(x2).
Explain what HI-CR security
Human ignorance collision resistant, means that it is not thesible for the adversary to win the collision resistant security game.
it obviously it possible to find collisions for any compression function, hence we assume human ignorance. This means it is not thesible to occur.
When is padding required?
When a (hash) function takes a fixed length input value.
Explain padding method 0, and why it is not practical.
Method 0 appends zeros to the end of your message:
m1 || 0*
This is not practical as the receiver will have no clue if padding was even applied and how many zeros were appended.
Explain padding method 1, and if it is practical.
Method 1 appends a single 1, and then zeros to the end of your message:
m1 || 1 || 0*
It is practical, as we know can determine the lenght of the padding
Explain padding method 2, and if it is practical.
Method 2 appends the 64 bit encoded length of the message |m| = L, if fills the space by inserting a single 1, and then zeros between the lenght and message. :
m1 || 1 || 0* || {L}^64
It is practical, as we know can determine the lenght of the padding, however at least 65 bits need to be padded.
Explain padding method 3, and if it is practical.
Method 3 appends the 64 bit encoded length of the message |m| = L:
m1 ||0* || {L}^64
It is practical, as we know can determine the lenght of the padding, however at least 64 bits need to be padded.
Explain padding method 4, and if it is practical.
Method 4 appends a single 1, and then zeros between the lenght and message. Then it concludes by appending a 1 again :
m1 || 1 || 0* || 1
It is practical, as we know can determine the lenght of the padding. And padding lenght only needs to be at least 2.
What abreviation is MD
Merkle-Damgard construction
What general problem does MD solve? And how does it achieve this?
Input message of function can now be of abritrary length.
It achieves this by deviding the input values into smaller blocks and performs sequential operations (with fixed input length) on these blocks, such that only the last block needs to be padded
Explain the notation MD[f_k, s]
f is the sequential operation function used in the MD construction (with optional key k subscript). s is the initial state for the first operation (similar to IV)
f is public, k and s are secret.
Explain how the birthday paradox can be applied to find collisions.
The birthday paradox states that when two elements are drawn from the Domain, that after sqrt(n) calls a collision could be expected.
This means that for an hash function with 128 bits output, only sqrt(2^128) = 2^64 calls would be needed. This suddenly becomes thesible to do so.
How did Yuval propose meaningful birthdaying?
He proposes that we first need to find two meaningful message m1 and m2, and identify 2/n bits in each message that could be changed individually, witout changing the meaning of the message. Then we can randomly select a version of m1 and m2 in order to find a collision, as both domains have a size of 2^(n/2).
