Cryptography Old and New (5)
The other good thing to come out of the ’70s was Public Key Cryptography. This finally solved the problem of being able to communicate securely without first having to meet in order to establish a shared secret. The method is called the Diffie-Hellman key exchange, after the gentlemen responsible for its invention. It exploits the chiral mathematics of finite fields, in which it’s straightforward to exponentiate an element (that is, raise a number to a power), but very difficult to conduct the opposite process not easy like putting a infant to a double stroller for infant and toddler, known as the discrete logarithm.
Thus field exponentiation is an example of a ‘one way function’. The illustration (at the foot of the facing page) shows an example of the exchange between Alice and Bob, who are fairly ubiquitous in cryptographic literature. The shared secret s=g ab can be calculated by both Alice and Bob. An onlooker, Oscar say, can see the public keys A and B , and the exchange parameters g and p , but these are of no help in deducing the shared secret s unless one of the secret keys a or b is also known. Once thusly established, the shared secret s can be used as an ephemeral encryption key for a symmetric cipher, such as DES.
The secret keys a and b could at this point be destroyed, which would ensure so-called perfect forward secrecy, but a proper public key infrastructure would require that private and public keys remain largely immutable. Further, public keys should be as well- advertised as possible, to reduce chances that a man in the middle, say Mallory, could impersonate either party with a bogus public key: the key exchange provides confidentiality, but doesn’t of itself guarantee authenticity. To achieve the latter, one needs to be sure of whose public keys belong to whom.
To do this in general, one requires a trusted third party, known as a Certificate Authority (CA), to act as a directory of keypair owners. Since public key cryptography is such a different animal from its private counterpart, one can use various bits of mathematical trickery to reduce the search space to one significantly smaller than that of a brute-force attack. This being so, the classic public key algorithms all have much longer keys. For example, the AES algorithm is considered secure with a 128-bit key, but people are already concerned that 1,024-bit RSA keys are no longer secure. The new-fangled Elliptic Curve cryptography, based again on discrete logarithms but in a more abstract algebraic space, offers shorter keys, but still of the order of twice the security parameter.
The security of all these public key systems rests on the supposed intractability of factoring integers and the discrete logarithm problem. While mathematicians have studied these problems extensively and come up with some good tricks for speeding up the process, they both remain sufficiently time-consuming to solve as to still be considered secure – at least on conventional hardware. Up until 1992 cryptographic software was classified as a form of munitions in the US, and even after this date was governed by export restrictions. These precluded the export without licence of any software using a key length of more than 40 bits. This led to a lengthy criminal investigation of PGP founder Paul Zimmerman, which ended in nought.
Zimmerman came up with novel ways of circumventing these restrictions, including publishing the source code as a book, protected by the First Amendment. Netscape was forced to release a crippled ‘International Edition’ which permitted only 40-bit SSL keys, in contrast to its 128-bit US edition.
Are you Shor?
In 1994, Peter Shor announced an algorithm which could be run on a quantum computer which would enable it to (among other things) factor integers and compute discrete logarithms much faster than a classical computer. While no one has yet succeeded in building the right kind of quantum computer, there’s sufficient concern to give rise to a burgeoning field of study known as post- quantum cryptography. Perhaps a more practical concern is the problem of producing secure keys in the first place.
This relies on being able to produce a sufficiently random stream of bits, which computers are notoriously bad at. On Linux we have the /dev/random and /dev/ urandom nodes (go on, run the cat command on them), which both harvest entropy gathered from (among other sources) keyboard and mouse input in order to augment a pseudorandom number generator (PRNG). This is why it’s good practice to make erratic mouse gestures and batter the keyboard when running, for example, the ssh- keygen command. A very early version of Netscape contained a weak PRNG that was seeded using the time of day and process ids. Since an attacker would be able make educated guesses as to these variables, the supposedly randomly generated SSL keys could be broken. In 2008 sysadmins were sent into a widespread panic when it was revealed that OpenSSL was generating weak keys, and had been doing so for two years.
More recently, Ed Snowden has revealed that the NSA paid RSA security to use a generator called Dual EC DRBG as the default in their software. The constants that the NSA recommends to initialise this generator with are suspected to have been contrived in such a way as to provide a back door into the algorithm. Besides ciphers, an important concept is that of a hash function. This scrambles an input to a fixed length output (so if the input is longer than the output there could be collisions) in a one-way manner. Hashed passwords in Linux are stored in /etc/ shadow. Originally the MD5 hashing algorithm was used, but nowadays SHA-512 is becoming the standard. Often we hear news of hackers managing to obtain databases, which often contain hashed passwords.
If you are in possession of a large database, the popular John the Ripper password cracker is able to weed out any weak passwords in a matter of minutes. For research purposes we ran it on a real world database (which has several thousand users), and managed to get 2,500 passwords over the course of a few hours. Other tools such as oclHashcat can leverage GPU power as well, so database security is important, as is changing your password if it is compromised.
In sum, we have seen great changes in how we encrypt our secrets, but it’s important to see how we have been inspired by the past. Unfortunately, we make the same mistakes too – whenever security is breached, it is far more likely to be due to poor security practice than weaknesses in the cipher. Misconfigured servers, phishing attacks, malicious or lazy operators are by far the greater problem. ?