Security Engineering. Ross Anderson
Чтение книги онлайн.
Читать онлайн книгу Security Engineering - Ross Anderson страница 77
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
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
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
A third property of pseudorandom functions with sufficiently long outputs is that it is hard to find collisions, that is, different messages
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
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