Cryptography Reference
In-Depth Information
a collision. Thus a hash function like SHA-1 is currently regarded as second
preimage resistant but not as collision resistant (see the discussion in Sect. 5.7 ) .
Of course, these terms are applied here in the practical sense and SHA-1 could
well be found not to be second preimage resistant in the future. On the other
hand, the function h
x 2 mod n , where n is the product of two large primes,
is thought to be one-way by Theorem 3.8 but it is clearly not second preimage
resistant because, for a given x , we have that h
(
x
) =
x .
3. The function that assigns to each binary string its parity bit, i.e., the Xor of
all the bits in the string, is a hash function with only two possible hash values
and, obviously, does not have any of the resistance properties mentioned. This
construction can be generalized to an n -bit valued hash function by regarding bit
strings as the binary expansions of positive integers and assigning to x
(
x
) =
h
(
x
)
and x
=−
}
the bit string of length n (with leading zeros added if necessary) corresponding to
the integer x mod 2 n . Now, the number of possible hash values is 2 n , which can
be large but, again, this hash function does not have any of the required properties
for cryptographic use. Collisions are trivially found just by adding leading zeros
and, even if we limit ourselves to computing hashes of strings without leading
zeros, we only have to ensure that the values of the integers associated with the
strings differ by a multiple of 2 n to quickly find collisions. Moreover, preimages
are also easily computed. The construction of collision resistant hash functions
is nontrivial as we will later see.
∈{
0
,
1
Exercise 5.12 Prove that a collision resistant hash function need not be preimage
resistant by using the following example [140, 9.20]. Let g be a collision resistant
hash function with an n -bit output and define an
(
n
+
1
)
-bit hash function as follows:
1
||
x
if len
(
x
) =
n
,
h
(
x
) =
0
||
g
(
x
)
otherwise.
5.6.1 A Couple of Applications
We have mentioned that hash functions can be used to ensure message integrity and
we will see that these functions have many important cryptographic applications.
Before studying them in more detail, we now present, in a generic way, a couple of
relevant applications that give an idea of the importance of the resistance properties
we have mentioned. A function that is neither collision resistant nor preimage resis-
tant is not useful as a hash function for cryptographic use, so we consider a couple
of situations were one of these properties is required.
Protecting passwords and PINs. One simple application is the protection of
passwords or PINnumbers. In operating systems, for example, user passwords are not
stored and the hash values of these passwords are stored instead. Then, to guarantee
access, the system computes the hash of the supplied password and compares it with
the stored value. This way, even privileged users that have access to the system are
 
Search WWH ::




Custom Search