Public Key Cryptography

Brave New Cipher

As an avid reader of Scientific American in the 1970s, and of Martin Gardner's Mathematical Games column in particular, I was lucky enough to be schooled in the basics of public key cryptography just as it was being invented. Well, two years after its 1975 inception, to be accurate. Firstly through Martin's column, which in the August 1977 issue became the first to publicize the PKC method worldwide; and then in the same journal, subsequently from the writings of Rivest, Shamir and Adleman (RSA) themselves.

It was an exciting time for anyone of a mathematically sympathetic imagination. For the first time in history, the question of the practicability of devising a cipher, to be encoded and decoded rapidly by computer, used repeatedly without changing the key, and unbreakable by sophisticated cryptanalysis, received an answer and a proof; and the answer was affirmative.

Martin's original article can be read here:

http://www.fortunecity.com/emachines/e11/86/cipher1.html

The number theory behind the scheme is simple and elegant, as we hope from such things. But that very beauty of theory and expression can distract the student from the equally important subject of housekeeping.

Secure Public Keys

This is the main message in Eric Lippert's recent article, Keep it secret, keep it safe. As an example, most of us will be aware that Alice and Bob each have one private and one public key, based upon a certain mathematical "trapdoor function", namely prime factorisation. Each party must ensure that his or her private key remains known only to him or herself. What's perhaps less obvious is that their initial exchange of public keys must also be made via a guaranteed secure channel.

Why? Surely the strength of the scheme rests on the fact that eavesdropper Eve can do nothing with full knowledge of these keys? True enough, but Eve is not the only shadowy figure in the telephone exchange room.

Historical note: in cryptography discussions such as these, the cast of characters (Alice, Bob, Eve, etc.) is mostly drawn from Bruce Schneier's seminal book, Applied Cryptography.

Eric uses Mallory to denote this malicious, meddlesome, man-in-the-middle, although Trudy (for intruder) is possibly more common. If Mallory can intercept the initial exchange of public key information, then he may modify these keys in transit, replacing them with his own public key.

Any message from Alice will be encrypted using her private key, and Bob's public key. But now Mallory can intercept such messages, and replace them with alternatives containing his own subversive propaganda, encrypted using his own private key, and Bob's public key. Bob will then in turn decrypt the bogus message using his own private key and Mallory's public key, which he still believes to be Alice's; and so all will appear to be well. Oops!

An Opportune Time

This is a particularly urgent time to be reminding ourselves of the basic mechanics of the system. We have recently seen Certifying Authorities become compromised, appearing to issue shedloads of bogus certificates, and even go bust (DigiNotar). Ironically, RSA itself has become the victim of one of the most wide-ranging breaches in the history of the industry, its SecurID token system and thereby the security of its targeted (Lockheed Martin) and collateral clients being utterly compromised. Meanwhile, the SSL itself, in its most common implementation (TLS 1.0/SSL 3.0), has been hacked by a cookie thieving BEAST.

It's only by understanding the detailed operation of PKC that we'll be able to discern the implications of breaches and failures such as these. But the important details are not in the pretty mathematics, they're higher up in the wider system, where the real, exploitable vulnerabilities reside. They're in the arena of public/private key housekeeping. As Eric puts it, solve the key management problem first!

Related articles:

Authencity of Web pages comes under attack
Hackers impersonating 'trusted' Web pages
Secure online payment system requires end-to-end encryption

Pic: Adi Shamir, 2009. Source: Wikipedia.