Ross Anderson - Security Engineering

One security-protocol use of hash functions is worth a mention: key updating and autokeying. Key updating means that two or more principals who share a key pass it through a one-way hash function at agreed times: . The point is that if an attacker compromises one of their systems and steals the key, he only gets the current key and is unable to decrypt back traffic. The chain of compromise is broken by the hash function's one-wayness. This property is also known as backward security . A variant is autokeying where the principals update a key by hashing it with the messages they have exchanged since the last key change: . If an attacker now compromises one of their systems and steals the key, then as soon as they exchange a message which he can't observe or guess, security will be recovered; again, the chain of compromise is broken. This property is known as forward security . It was first used in banking in EFT payment terminals in Australia [208, 210]. The use of asymmetric cryptography allows a slightly stronger form of forward security, namely that as soon as a compromised terminal exchanges a message with an uncompromised one which the opponent doesn't control, security can be recovered even if the message is in plain sight. I'll describe how this works next.

The commonly used building blocks in asymmetric cryptography , public-key encryption and digital signature are based on number theory. I'll give a brief overview here, and look in more detail at some of the mechanisms in Part 2when I discuss applications.

The basic idea is to make the security of the cipher depend on the difficulty of solving a mathematical problem that's known to be hard, in the sense that a lot of people have tried to solve it and failed. The two problems used in almost all real systems are factorization and discrete logarithm.

The prime numbers are the positive whole numbers with no proper divisors: the only numbers that divide a prime number are 1 and the number itself. By definition, 1 is not prime; so the primes are {2, 3, 5, 7, 11, …}. The fundamental theorem of arithmetic states that each natural number greater than 1 factors into prime numbers in a way that is unique up to the order of the factors. It is easy to find prime numbers and multiply them together to give a composite number, but much harder to resolve a composite number into its factors. And lots of smart people have tried really hard since we started using cryptography based on factoring. The largest composite product of two large random primes to have been factorized in 2020 was RSA-250, an 829-bit number (250 decimal digits). This took the equivalent of 2700 years’ work on a single 2.2GHz core; the previous record, RSA-240 in 2019, had taken the equivalent of 900 years [302]. It is possible for factoring to be done surreptitiously, perhaps using a botnet; in 2001, when the state of the art was factoring 512-bit numbers, such a challenge was set in Simon Singh's ‘Code Book’ and solved by five Swedish students using several hundred computers to which they had access [44]. As for 1024-bit numbers, I expect the NSA can factor them already, and I noted in the second edition that ‘an extrapolation of the history of factoring records suggests the first factorization will be published in 2018.’ Moore's law is slowing down, and we're two years late. Anyway, organisations that want keys to remain secure for many years are already using 2048-bit numbers at least.

The algorithm commonly used to do public-key encryption and digital signatures based on factoring is RSA, named after its inventors Ron Rivest, Adi Shamir and Len Adleman. It uses Fermat's little theorem , which states that for all primes not dividing , (mod ) (proof: take the set {1, 2, …, } and multiply each of them modulo by , then cancel out each side). For a general integer , (mod ) where Euler's function is the number of positive integers less than with which it has no divisor in common (the proof is similar). So if is the product of two primes then .

In RSA, the encryption key is a modulus which is hard to factor (take for two large randomly chosen primes and , say of 1024 bits each) plus a public exponent that has no common factors with either or . The private key is the factors and , which are kept secret. Where is the message and is the ciphertext, encryption is defined by