A hash function H HH is a transformation that takes a variable-sized 해시게임 input m mm and returns a fixed-sized string called the hash value h hh (ie, h = H ( m ) h = H ( m ) h =H(m)).
Hash functions of this nature have a variety of general computational uses,
but when used in cryptography,
hash functions are often chosen to have some additional properties.
What is a hash function?
The basic requirements for a cryptographic hash function are:
The input can be of any length,
The output has a fixed length,
relatively easy to compute for any given x xx,
is unidirectional,
is collision-free.
A hash function H HH is said to be one-way, if it is difficult to invert,
where ‘hard to invert’ means that given a hash value h hh,
it is computationally difficult to find some input x xx such that H ( x ) = h H ( x ) = hH(x)=h.
Given a message x xx, it is computationally impossible to find a message y yy not equal to x xx such
that H ( x ) = H ( y ) H ( x ) = H ( y )H(x)=H(y ), then H HH is said to be a weak collision-free hash function.
A strong collision-free hash function H HH that is computationally infeasible to find any two messages x xx and y yy such that H ( x ) = H ( y ) H ( x ) = H ( y )H(x )=H(y).
A hash value succinctly represents the longer message or document from which it was computed;
a message digest can be thought of as a ‘digital fingerprint’ of a larger document.
Examples of well-known hash functions are MD2 and MD5 (see here) and SHA (see here).
Perhaps the primary role of cryptographic hash functions is to provide digital signatures.
Since hash functions are generally faster than digital signature algorithms, therefore,
Computing the digital signature of some documents by computing the signature is classic on the hash of the document,
which is small compared to the document itself.
Furthermore, an information abstract can be made public without revealing the bibliographic content of its source.
This is important in digital timestamping (see here) because using hash functions it is possible to get timestamps withou
t revealing the contents of the document to the timestamping service.
What is a birthday attack?
a birthday attack is a name used to refer to a type of brute force attack.
It gets its name from the surprising result that the probability of two or more people in a group of 23 sharing the same birthday is greater than 1 2 \frac{1}{2}
2
1
; such a result is called the birthday paradox.
If some function, when fed a random input, returns one of k k classical probability values, then by iterative evaluation of the function on different inputs, we expect that in about 1.2 k 1 2 1.2k^{\frac{1 }{2}}1.2k
2
1
to get the same output. For the birthday paradox above, replace k with 365.
The birthday attack is often used to find collisions of hash functions.
How does the length of the hash value affect security?
The fundamental cryptographic property of a hash function is that it is both one-way and collision-free.
The most basic attack we can make on a hash function is to randomly choose inputs to the hash function until we find some input,
that gives the target output value we’re looking for (thus contradicting the one-way property),
or find two an input that produces the same output (thus contradicting the collision-free property).
Suppose the hash function produces an output that is n bits long.
If we try to find some input that produces some target output value y, then since every output is equally possible,
we expect to try 2 n 2^{n}2
n
possible input values.
If we were trying to find a conflict, then according to the birthday paradox we would expect that after trying 2 n 2 2^{\frac{n}{2}}2
2
n
After possible input values, we have some conflicts.
Van Oorschot and Wiener show how to perform this brute force attack.
Regarding the use of hash functions when providing digital signatures,
Yuval proposes the following strategy based on the birthday paradox,
where n is the length of the message digest:
- The attacker chooses a harmless target message that Alice is likely to sign.
- The attacker generates 2 n 2 2^{\frac{n}{2}}2
2
n
variants of an innocuous message (i.e., with some minor editorial changes), all of which convey the same meaning and their corresponding message summaries. He then generates an equal number of variations of the target message to be replaced.
- According to the birthday paradox, the probability that one of the variations of the harmless message matches one of the variations of the target message is greater than 1 2 \frac{1}{2}
- The attacker then obtains Alice’s signature on the change of the innocuous message.
- Take the signature from the innocuous message and append it to the variant of the target message that produces the same message digest. The attacker successfully forged the message without using the encryption key.
- To avoid attacks that rely on brute force methods, the output of the hash function must be long enough.