APR. 24, 2018 | THE FRONT LINE

Previous: What is Crypto? Part 2: Secret Keys

If you remember, all the types of cryptographic algorithms and modes discussed in the last post still assume that Alice and Bob first securely shared secret keys. Of course, it isn’t always practical in today’s world to expect people or businesses to first physically meet up to exchange keys before communicating securely. And it certainly doesn’t make sense to assume that people will have some other secure channel already established they can share keys through, or they would not need cryptography in the first place.

Asymmetric Cryptography

To help address the problem of key exchange, public key cryptography was designed. It uses advanced math employing two different kinds of keys, a public key and a private key, together known as a keypair. Suppose Alice has a keypair. The public part can be posted and shared widely between everybody. If people share and compare keys, any potential Man-in-the-Middle (MITM) attacker trying to distribute a fake key would be quickly discovered. That is, unless they could permanently intercept all communications on every link, which is highly unlikely.

With Alice’s public key available to anyone, those who wish to can use it to encrypt a message to her. However, once encrypted, no one but Alice can read that message since they do not have Alice’s private key.

A similar, but reverse process can also be used to authenticate messages: Alice can cryptographically sign a message with her private key, and everyone can verify she signed it by checking against her public key. No one else could forge a signature for something she did not sign if they did not have her private key.

The most common asymmetric algorithm is RSA, named for the three mathematicians and cryptographers who first publicly described it, Rivest, Shamir, and Adleman. Clifford Cocks, a cryptographer with the United Kingdom’s Government Communications Headquarters (GCHQ) had discovered it first, but it remained classified and unused until later rediscovered and published by the more widely known trio.

Clifford Cocks, Photo credit: The Royal Society

Other algorithms include the related digital signature algorithm (DSA) and the Elliptic-curve digital signature algorithm (ECDSA), which is an implementation of elliptic-curve cryptography (ECC). ECC is a more recent development than RSA and DSA and is far more efficient in terms of both time to compute encryption and decryption and number of bytes required to send an encrypted key.

Like the details of block ciphers, explaining exactly how these function goes far beyond this blog series. If you do want to understand how RSA/DSA works, I would first recommend taking a course in number theory. ECC would likely require higher level courses than that. Also, like block ciphers, without a deep understanding of the math behind these and the many pitfalls in the form of weak keys or other mistakes, any naïve implementation of these algorithms, or modification to standardized implementations is very likely to result in an easily breakable result that is both weak and slow.

Public Key Infrastructure

We have covered the basics of asymmetric cryptography, but there is still the issue of how to distribute keys. Our scheme to share everyone’s keys to everyone else peer-to-peer, while still better than the symmetric alternative, and useful for a thought exercise, presents three main problems. First, it is very resource-intensive. Second, it does not stop an attacker who has control over all your network traffic when you first visit a website (like nearly any Wi-Fi-intercepting attacker at a coffee shop). And third, it is prone to disruption. You could easily launch a denial of service attack against Google by simply sending out unsolicited warnings claiming Google gave you a different key, so everyone would not know which of Google’s keys were the real one.

In search of a better option, a public key infrastructure (PKI) was created. Certain organizations that were either authors of operating systems (like Microsoft) or developers and hardware manufacturers trusted by operating systems (like Symantec) to perform validation of the identities of people, companies, and computer systems were designated Certificate Authorities (CA’s). The methods they use to validate identities were agreed to beforehand and include things like validating ownership over servers at specific IP addresses, calling phone numbers of registered domain owners, etc. Their public keys were bundled together with associated information such as a validity period and the name of the responsible organization into a certificate. This certificate was installed as a “root certificate” on the operating systems of each of these systems.

Now whenever a website owner wants to accept secure connections to their website, they must undergo validation by one of these CA’s. Once that happens, the CA will sign the website’s certificate (including the website’s public key) using the CA’s private key. The website can then send that certificate to anyone wishing to visit the site securely, and without previously communicating with anyone else, using only the built-in root certificates on their OS, the visitor can validate that the website’s public key has been approved by the CA and can be used to exchange symmetric keys.

Key Exchange

At this point, we have a pretty good system. And indeed, this kind of crypto powers much of the web today. But we can make it stronger. By using similar algorithms, you can also protect previous communications against being read even if your main key was compromised later by using key agreement protocols. These use fancy math to calculate an ephemeral secret value between two people without ever sending that secret value over the network. By themselves, they are not secure against MITM attacks, but when authenticated with a public key they are. These algorithms include Diffie-Hellman (aka DH aka Diffie-Hellman-Merkle) but now almost everyone uses Elliptic Curve Diffie Hellman (aka ECDH), which is much faster and uses fewer bytes for the same security level. These provide what’s known as forward secrecy.

Now that we have covered block and stream ciphers, block cipher modes of operation, hash functions and message authentication codes, asymmetric (public key) crypto, and key exchange algorithms, we have covered all the basic “cryptographic primitives” as they are called. However, even if you use all strong cryptographic primitives, it is still possible to make mistakes when combining and using them. The next post will cover how these are combined into full-featured encryption protocols, and some attacks that may still cut through to reveal plaintext.

NEXT: What is Crypto? Part 4: How Good Crypto Dies