Security Engineering. Ross Anderson

Скачать книгу

The random oracle

      5.3.1 Random functions – hash functions

      The first type of random oracle is the random function. A random function accepts an input string of any length and outputs a string of fixed length, say bits long. The same input gives the same output, but the set of outputs appears random. So the elf just has a simple list of inputs and outputs, which grows steadily as it works.

      Random functions are our model for cryptographic hash functions. These were first used in computer systems for one-way encryption of passwords in the 1960s and have many more uses today. For example, if the police seize your laptop, the standard forensic tools will compute checksums on all the files, to identify which files are already known (such as system files) and which are novel (such as user data). These hash values will change if a file is corrupted and so can assure the court that the police haven't tampered with evidence. And if we want evidence that we possessed a given electronic document by a certain date, we might submit it to an online time-stamping service or have it mined into the Bitcoin blockchain. However, if the document is still secret – for example an invention for which we want to establish a priority date – then we would not upload the whole document, but just the message hash. This is the modern equivalent of Hooke's anagram that we discussed in section 5.2.4 above.

       5.3.1.1 Properties

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.

5.3.1.2 The birthday theorem

      The birthday theorem gets its name from the following problem. A maths teacher asks a class of 30 pupils what they think is the probability that two of them have the same birthday. Most pupils intuitively think it's unlikely, and the maths teacher then asks the pupils to state their birthdays one after another. The odds of a match exceed 50% once 23 pupils have been called. As this surprises most people, it's also known as the ‘birthday paradox’.

      The birthday theorem was first used in the 1930’s to count fish, so it's also known as capture-recapture statistics [1668]. Suppose there are fish in a lake and you catch of them, ring them and throw them back, then when you first catch a fish you've ringed already, should be ‘about’ the square root of . The intuitive reason why this holds is that once you have samples, each could potentially match any of the others, so the number of possible matches is about x or , which is what you need³.

      This theorem has many applications for the security engineer. For example, if we have a biometric system that can authenticate a person's claim to identity with a probability of only one in a million that two randomly selected subjects will be falsely identified as the same person, this doesn't mean that we can use it as a reliable means of identification in a university with a user population of twenty thousand staff and students. This is because there will be almost two hundred million possible pairs. In fact, you expect to find the first

Скачать книгу