How Encryption Works — The history and the Future
Encryption pervades all aspects of our lives today. We utilize it as a matter of course without even giving it a second thought. That book you ordered for your Kindle library last night, the message you sent your friend on WhatsApp this morning, the agreement you digitally signed just now — all these acts used encryption, or the science of Cryptography.
A bit of history
The desire to keep and hold secrets is ageless. Cryptography in the form of basic ciphers, has existed from the times of the Greek and Roman civilizations. These were rudimentary in nature and mainly designed to obfuscate messages so they didn’t make sense if they fell into the wrong hands. An early example called the Caesar Cipher basically shifted characters by 3 places (e.g. A = D, B = E, C = F, and so on). Such a cipher is called a substitution cipher. A modern example, called ROT13 is a modified version of the Caesar cipher that simply shifts characters by 13 places (instead of 3). ROT13 is interesting because there are 26 letters in the alphabet — and as a result, it is its own inverse. Basically, the same algorithm (shifting 13 places) can be used for both decryption and encryption ?
As ciphers go, however — ROT13 is an example of weak encryption and is rarely used where secrecy is valued.
An historically more recent example where encryption was used was when the German military used the Enigma machine to transmit and receive coded messages. The Enigma’s encryption key changed every day, making the messages hard to crack. The story of how Alan Turing famously cracked the code and helped the Allies win the 2nd world war is memorably captured in the Hollywood movie — “The Imitation Game”.
In more recent times, IBM created a block cipher back in 1973 to protect their customer data. It was later adopted by the United States as a national standard called DES (Data Encryption Standard). It was in wide use until 1997 when it was cracked and later replaced by AES (Advanced Encryption Standard). AES is still extant and widely used in all modern applications.
You can understand encryption in the simple form of multiplication. If you think of the message you are trying to encode as a string of digits, which you multiply using another long string of digits (think of this second number as your encryption key), their product is your encrypted message. Easy, right? In order to decrypt, you simply need to divide the encrypted product with the same encryption key, and voila! Your original message is back.
What we’ve described above is an example of Symmetric Key Encryption and so long as you have a long enough key, it actually works quite well. Both DES and AES are examples of Symmetric Key ciphers, although their algorithms are substantially more complex than the simple multiplication example I’ve used above. The reason the encryption key needs to be long is to make the decryption computationally expensive enough for an unauthorized actor who may use computing techniques to decipher the key.
AES-256 is arguably the most secure, practical implementation of a symmetric key cipher available today. The 256 denotes the length in bits of the key used. Longer keys obviously will make AES more secure, but they also make the task of encryption computationally more intensive. To crack a 256-bit key, an attacker would need to try 2256 different combinations. This number is 78 digits long and is several orders of magnitude greater than the number of atoms in the observable universe. So, for all practical purposes, AES-256 is virtually impenetrable. The 56-bit DES key which was cracked in 1997 can be cracked in less than a day using today’s computers. In comparison, AES would take billions of years to break (using current computing technology — but more on that later).
Types of Encryption
Ciphers like DES and AES are Symmetric key ciphers. This means that the key used to encrypt and decrypt are the same. This is fine for scenarios where the same system needs to decrypt at a later date, something it had encrypted earlier. In such a case, the key is kept a secret and is known only to the system.
However, what if a system needs to send an encrypted message to someone else? How would the other side decrypt it? Well, the other party would need the same key to decrypt the message, obviously. But therein lies the problem. How do you communicate the key securely to the other party? What would you do? Encrypt the key? And then how to you protect the key you encrypted the key with? We could go on forever.
In 1976, Stanford researchers Diffie and Hellman proposed a way which used 2 separate keys for the encryption and decryption operations. One key could be used only for encryption whereas the other could be used to decrypt what the former encrypted. Or vice versa. It was a revolutionary* concept and completely changed the encryption landscape.
We won’t get into the math of this right now — but in this model, 2 keys are assigned to each user. One is a private key and another a public key. The public key can be shared freely with the world, whereas the private key is held secret by the user.
When A wants to send a secure message to user B, she uses B’s public key to encrypt it. B in turn uses his private key to decrypt it. The message is secure because nobody other than B knows how to decrypt the package.
The public-private key pair can also be used for digital signing — i.e. to validate a sender. If B receives a message from A and he needs to be sure it is from A and nobody else, A uses her private key to sign the message. When B receives it, and is able to decode the signature using A’s public key, he can be a 100% sure the message is from A.
*In 1997, it was revealed that the British signals intelligence agency, had shown as early as 1969, how public-key cryptography could be achieved — but they did nothing about it.
So, in short, Symmetric encryption is useful when you have a single entity doing
both encryption and decryption. As an example, if you were to maintain a diary which you wished to keep private to yourself — you could make all your entries in a cipher that only you understood. That would be symmetric encryption. Symmetric key encryption is relatively fast computationally and doesn’t require very long keys to make it computationally defensible. As stated earlier, a 256 length key used with AES would take billions of years to break with currently extant computing power.
Asymmetric encryption is something you would use when you have at least 2 entities that need to exchange messages. In such a case transmitting a single “symmetric key” to the other party would be risk-prone because somebody might eavesdrop. Going back to the diary analogy, it would be like writing down instructions on how to decode your cipher. You would have to worry about the instructions falling in the wrong hands. Asymmetric key encryption therefore has 2 keys — one with which you encrypt; and another with which your recipient decrypts. Asymmetric key computation is also more intensive computationally and requires much longer keys to make it defensible. As an example a 1024 bit RSA key is only reasonably secure and can be cracked by a fairly determined hacker with sufficient computing power. A 2048 bit RSA key is predicted to be secure until 2030. The problem with making these keys longer is that the computation complexity increases, and the speed of encryption slows down drastically.
What is HTTPS and SSL/TLS?
If you recall, in our last blog, we we touched on the Diffie-Helman method of using two keys — one to encrypt and the other to decrypt.
In a practical application of asymmetric key encryption between 2 parties, the Diffie-Helman mechanism requires an exchange of public keys between the 2 entities — so they can encrypt messages meant for the other or decrypt messages sent by the other.
A practical implementation of Diffie-Helman was made possible by 3 MIT scientists — Rivest, Shamir and Adleman in 1977, the very next year after Diffie and Hellman made their theory public. Popularly known as RSA, this practical implementation of Diffie Helman used mathematical factoring as the way to create the one-way function that is essential as part of the Diffie-Helman key exchange.
In real-world scenarios using asymmetric encryption for transmission of all data would be frustratingly slow. So, asymmetric encryption is usually used to exchange a symmetric key confidentially between both sides — which is then used to encrypt the actual data payload.
The mechanism of this initial handshake, exchanging public keys, deciding on a confidential, common, symmetric key and transmitting data encrypted in flight is called SSL (Secure Sockets Layer), also known as TLS (Transport Layer Security). SSL was originally invented by Netscape and then handed over to the Internet Engineering Task Force (IETF). HTTPS is the protocol that SSL rides on.
SSL Certificates? Why do we need those?
One risk with Diffie-Helman is that an intermediary can intercept the public keys during the initial exchange and substitute them with their own public keys thus fooling the endpoints into believing they’re communicating with each other when in reality, all communications are being hijacked by an actor in between. This is commonly called a Man-In-The-Middle attack (MITM) and is the reason we use certificates today. A Certificate is a way to authoritatively attribute ownership of a public key to an entity or individual. Certificates are typically issued by trusted sources called Certificate Authorities and are protected dearly. This is why, when you are using a browser with a https URL, you may sometimes see a warning that the site may not be trustworthy. This usually means that the certificate being used by the site isn’t from a valid CA, and that it could be vulnerable to an MITM attack.
Quantum Computing and Quantum Resistant Encryption
While classical computers carry out logical operations using the definite position
of a physical state (0 or 1), quantum computers perform calculations based on the probability of an object’s state before it is measured — instead of just 1s or 0s — which means they have the potential to process exponentially more data compared to classical computers.
While quantum computing is still in its infancy, it is a fact that that mathematical problems which are considered computationally “too intensive” for today’s computers may not be so for quantum computers. Should that happen, the defensibility of today’s encryption algorithms could disappear or be seriously compromised.
Not surprisingly, asymmetric encryption algorithms (which are weaker and less defensible computationally) are likely to be the main casualties of quantum computing. But, work is already underway to build more quantum resistant versions of asymmetric encryption.
Symmetric encryption will not be impacted nearly as much by quantum computing. While quantum computing is likely to take a bite out of symmetric encryption algorithms, increasing the key size will again give symmetric encryption enough runway and defensibility.
Key Management and Segregation of Duties
A small though to end the blog with… remember that your encryption is only as good as how well your keys are protected. Many times, when you place data on the cloud (aka someone else’s computer), you need to be sure that the data is safe. Most cloud/SaaS vendors will claim to encrypt the data you put there in order to make you feel safe, but you should know that you really have no control over the encryption process or the keys used in that process.
Best practice encryption always requires a separation of duties between the owner of the data and the cloud or SaaS vendor. This means, you should control the encryption and the keys and let the cloud or SaaS vendor manage the data.
Strong encryption without a separation of duties is as good as no encryption. You can technically argue the data is secure, but since it can be decrypted by others you haven’t authorized, it is not private.
Encryption will be an important key (no pun intended) to the future of computing. Knowing how encryption works will put you in a position of advantage and let you have more control over your data assets.
Solutions like Parablu rely on strong encryption with a strict enforcement of separation of duties and are designed to keep your data safe. Write to me if you have any thoughts.