Читать книгу Security Engineering - Ross Anderson - Страница 153

The first main property of a random function is one-wayness. Given knowledge of an input we can easily compute the hash value , but it is very difficult given to find if such an input is not already known. (The elf will only pick outputs for given inputs, not the other way round.) As the output is random, the best an attacker can do to invert a random function is to keep on feeding in more inputs until he gets lucky; with an -bit output this will take about guesses on average. A pseudorandom function will have the same properties, or they could be used to distinguish it from a random function, contrary to our definition. So a pseudorandom function will also be a one-way function, provided there are too many possible outputs for the opponent to guess an input that has a desired target output by chance. This means choosing so that the opponent can't do anything near computations. If we claim, for example, that SHA256 is a pseudorandom function, then we're saying that there's no practical way to find an input that hashes to a given 256-bit value, unless you knew it already and used it to compute that value.

A second property of pseudorandom functions is that the output will not give any information at all about even part of the input. So we can get a one-way encryption of the value by concatenating it with a secret key and computing . If the hash function isn't random enough, though, using it for one-way encryption in this manner is asking for trouble. (I'll discuss an example later in section 22.3.1: the hash function used by many phone companies in the 1990s and early 2000s to authenticate mobile phone users wasn't random enough, which led to attacks.)

A third property of pseudorandom functions with sufficiently long outputs is that it is hard to find collisions, that is, different messages with . Unless the opponent can find a shortcut attack (which would mean the function wasn't pseudorandom) then the best way of finding a collision is to collect a large set of messages and their corresponding hashes , sort the hashes, and look for a match. If the hash function output is an -bit number, so that there are possible hash values, then the number of hashes the enemy will need to compute before he can expect to find a match will be about the square root of this, namely hashes. This fact is of huge importance in security engineering, so let's look at it more closely.