Cryptography for you and me
This article is for the everyday Internet user to demystify cryptography and take a peek behind the curtains to understand basic cryptography, which has become an indispensable aspect of our everyday lives. From safeguarding our online communications and financial transactions to protecting our sensitive data, cryptography plays a vital role in ensuring our privacy and security online. However, for the uninitiated, the world of cryptography often seems like a complex and academic realm reserved exclusively for the tech-savvy elite. While there may be some truth to that, it's not essential for everyone to delve into the nitty-gritty details.
Cryptography on the web can be thought of as locks on our doors. Locks are amazing! A locked door is significantly harder to open than an unlocked door. But if you have the right key, then suddenly a locked door is easy to open. A lock doesn’t know me. It only knows the key, so anyone I give a key to can open the lock just as easily. No lock is infinitely secure. With enough effort, any lock can be broken or opened. While I'm sure locks are complicated with all pins and bolts on the inside, I don't necessarily need to understand the mechanics to build an intuition around locks or to use them. Cryptography is how we make digital locks. Instead of mechanical engineering, cryptography uses mathematics to build the locks. And just as we didn’t need to understand the internal mechanics of physical locks, we don’t need to understand the internal mathematics of cryptography to build intuition around it. Different cryptographic systems are used for different purposes, and this article describes the various cryptographic methods used today and their applications.
Symmetric Encryption
Symmetric encryption is a method that encrypts and decrypts a message using the same key, which needs to be kept secret.
Some of symmetric encryption ciphers are described below:
- Substitution Cipher: Substitution cipher works by substituting characters by other characters. In the below example, every letter in the plain text is substituted by the next letter in the alphabetic order. 'h' is changed to 'i', 'e' to 'f' and so on. The key here is 1, as the characters are shifted by one place in the alphabetic order.
hello world -> ifmmp xpsme
- Permutation Cipher: Permutation cipher works by changing the position of characters in the given message. In this example, the plain text is spelled out diagonally down and up over a number of rows and then read off row-by-row. The key is the number of rows, which in this case is 2.
hello world -> hlowrldel ol
h l o w r d
e l _ o l
However, these ciphers alone are not very secure. Also, combining multiple substitution ciphers together results in just another substitution cipher, and hence such a combination does not increase security. Similarly, combining multiple permutation ciphers results in just another permutation cipher, and hence such a combination does not increase security either. However, combining substitution ciphers with permutation ciphers results in ciphers that are much harder to break than the individual ciphers. These are called product ciphers.
While ignoring the mathematics of encryption algorithms, a problem does appear as just repeating encryption multiple times using the same key (as we have done above) is dangerous as a malicious user can study them to find patterns in them. This problem is solved by dividing the message into separate blocks and making each block’s encrypted value depend on all the previous blocks. Also, the key is expanded sufficiently such that a different part of the key can be put in at different rounds of substitution and permutation.
Still, however, if the same message is to be encrypted twice, it would provide the exact same encrypted text output, which may leak information. To subvert this, encryption algorithms ask you to enter a random value in the beginning, which will be disregarded during decryption later. This will ensure that the same plain text message will be encrypted to different cipher texts, making it harder to conduct analysis on resulting cipher texts.
The goal of substitution–permutation networks is to achieve good diffusion and confusion. Diffusion means that changing a single bit of the clear text should change (statistically) half of the bits in the cipher text. In other words, even small changes of the clear text lead to drastic changes of the cipher text. Confusion means that every bit of the cipher text should depend on several bits of the key. This obscures the connections between the two.
The Advanced Encryption Standard (AES) is a widely used symmetric encryption algorithm that works in this way. The advantage of this type of encryption is that it is easy to set up and implement. CPU nowadays have AES encryption capabilities built into the CPU hardware itself, which make them ridiculously fast and secure. AES is used by BitLocker on Windows to encrypt hard drive to prevent data leaks when the machine is stolen, it is used for storing encrypted backups and to store data at rest in servers.
The security of AES depends on the key, so it is necessary to use long keys. AES can be used with keys of 128 bits, 192 bits and 256 bits. The higher the number of bits, the more secure it is. The longer the key, the harder it is for an attacker to guess via brute force attack. However, there is nothing to worry about if your browser is using AES with just 128-bit keys because even a 128-bit key is secure against attack by modern technology. The largest computational power according to today's standards would take over 70,000,000,000,000,000,000,000,000 years to crack a single AES-128 key. Recently, the threat of quantum computing to cryptography has been well-publicized. Quantum computers work very differently than classical ones, and quantum algorithms can make attacks against cryptography much more efficient. Quantum computers decrease the effective key length of a symmetric encryption algorithm by half, so AES-128 has an effective key space of 64 bits and AES-256 has an effective key space of 128 bits. With the right quantum computer, AES-128 would take about 2.61×10^{12} years to crack, while AES-256 would take 2.29×10^{32} years. For reference, the universe is currently about 1.38×10^{10} years old, so cracking AES-128 with a quantum computer would take about 200 times longer than the universe has existed.
Asymmetric Encryption
Asymmetric encryption (also known as public key cryptography) works with a pair of keys: a public key used for encryption and a private key used for decryption. This is used mainly between two parties, a sender and a receiver. Notice that we cannot use symmetric encryption like in the previous example where we used a single key for both encryption and decryption. This is because when two parties are communicating, it is difficult to establish a common secret securely (over the internet for example) because anyone can see what's being communicated for deciding on a common secret key. In such cases, asymmetric encryption comes in handy. In this method, the receiver of the message generates a pair of key: a public key and a private key. The private key must be kept secure at all times by the receiver, while the public key can be shared with anyone, even freely over the internet. The sender then uses this public key to encrypt the message that he wants to send to the receiver. The encrypted message can then be sent over the internet. Remember that only the receiver has access to his private key, which can be used to decrypt the message. Therefore, anyone can encrypt a message using the public key, but only the holder of the private key can decrypt it back.
For example, a journalist can publish the public key of an encryption key pair on a website so that sources can send secret messages to the journalist in cipher text. Only the journalist who knows the corresponding private key can decrypt the cipher texts to obtain the sources' messages—an eavesdropper reading email on its way to the journalist cannot decrypt the cipher texts. Many protocols rely on asymmetric cryptography, including SSL and TLS protocols, which make HTTPS possible, which is of utmost importance today for establishing encrypted links between websites and browsers.
One important thing to know about asymmetric encryption algorithms is that they are compute-intensive, and as a result comparatively very slow. That’s the cost of the crazy magic that they do. Because of this, full messages are rarely encrypted using the public key. Instead, the message is first encrypted using the symmetric algorithm (single key encryption), and then the symmetric key is encrypted and transmitted using the asymmetric algorithm. This way, only a small key has to be encrypted/decrypted using the slower algorithm. Another important issue is confidence/proof that a particular public key is authentic, i.e. that it is correct and belongs to the person or entity claimed, and has not been tampered with or replaced by some (perhaps malicious) third party. If Bob wants to send Alice an encrypted message, Bob first needs to obtain Alice’s public key. If Mallory can interfere in this process and provide his public key instead of Alice’s key, then Mallory will be able to read the message. Another challenge associated with asymmetric encryption algorithms is the revocation of keys. If for some reason, Alice has lost her private key, then the associated public key should not be used anymore.
RSA and Elliptic Curve Cryptography (ECC) are the most widely used asymmetric encryption algorithms. These algorithms are based on trapdoor functions. RSA, for example, is based on the process of multiplication of two prime numbers, which is easy to perform in one direction but much harder to do in reverse. For example, it is trivial to multiply two numbers together: 593 times 829 is 491,597. But it is hard to start with the number 491,597 and work out which two prime numbers must have been multiplied to produce it. And it becomes increasingly difficult as the numbers get larger, even for computers of today. Indeed, computer scientists consider it practically impossible for a classical computer to factor numbers that are longer than 2048 bits, which is the basis of the most commonly used form of RSA encryption.
The security of RSA relies on the problem of factoring very large numbers and ECC depends on calculation of elliptic curve discrete logarithm, both of which can, however, be attacked by quantum computers. So if a large quantum computer ever gets built, all messages encrypted with RSA/ECC are at risk. To get ahead of this, the cryptographic community has been working towards post-quantum cryptography to find algorithms that don’t rely on problems that quantum computers can solve easily. The National Institute of Standards and Technology (NIST) of the USA wrote on one of their web pages:
The question of when a large-scale quantum computer will be built is a complicated one. While in the past it was less clear that large quantum computers are a physical possibility, many scientists now believe it to be merely a significant engineering challenge. Some engineers even predict that within the next twenty or so years sufficiently large quantum computers will be built to break essentially all public key schemes currently in use. Historically, it has taken almost two decades to deploy our modern public key cryptography infrastructure. Therefore, regardless of whether we can estimate the exact time of the arrival of the quantum computing era, we must begin now to prepare our information security systems to be able to resist quantum computing.
Hash functions
Hashing is the process of converting data — text, numbers, files, or anything, really — into a fixed-length value of letters and numbers. Data is converted into these fixed-length hash values, by using a special algorithm called a hash function. The properties of these hash functions are:
- The hash function should be efficient to compute for arbitrary inputs. For example, they should be able to calculate hash values for a small text file as well as a long movie file relatively quickly. An effective hashing algorithm quickly processes any data type into a unique hash value.
- Given a hash value, it should be nearly impossible to find the original message or file that generated this hash value. In fact, if the hashing function can be reversed to recreate the original input, it’s considered to be compromised. This is one thing that distinguishes hashing from encryption, which is designed to be reversible!
- No two inputs should generate the same hash value (hash collision). And the same input should always result in the same hash value every time.
hello world -> b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9
hello worlds -> 8067f1ae16f20dea0b65bfcbd50d59014d143c8ecebab179d923f6ef244b40f8
In the above examples, notice that the hash value of the two inputs are completely different even though the inputs themselves are very similar, and that the length of the hash values are exactly the same. In this example we hashed simple texts that generated two hash values of exact same length. But even if we had hashed a whole 3-hour-long movie, it would have given a unique hash with equal number of characters in its hash value.
Hashing is extensively used for storing passwords. The passwords that you set on online platforms are hashed and saved to the databases so that even if the database is somehow compromised, the attacker cannot recreate your actual password from the hash value. Each time you log in, your password is hashed and compared against the hash stored in the database. Cryptographic hash functions are also being used in the context of cryptocurrencies such as Bitcoins or more general distributed ledger technology to verify transactions.
When it comes to password hashing, if two users use the exact same password, it will result in the same hash value. This can be exploited by malicious actors seeking to crack passwords, which is why 'salt' is added to passwords before hashing. Salt is a random sequence of numbers that is added to the password prior to hashing, so that even if two users have the same plain text password, the hashes will look different as the hash is applied to the salt and the password. Each user's salt needs to be different and needs to be stored in the database to consistently apply this hashing technique.
Secure Hashing Algorithm(SHA) is a widely used hashing algorithm. Currently, SHA-256, SHA-512 and SHA-3 are considered industry standards. SHA-1 has been considered largely insecure since the 2000s, because researchers were able to generate hash collisions, i.e. two inputs that generated the same hash value. A hash algorithm is considered compromised if two different inputs generate the exact same hash. It is, however, impossible to get back the original input from the generated hash value. This is because the hash is a fixed length string, so the possible combinations of input strings are greater than the number of possible hashes. Thus it is clear that something is being lost when the hash is computed. Therefore, the information of which input was mapped to the output is lost forever.
Hashed Message Authentication Codes
Hashed Message Authentication Codes (HMACs) are widely used in communication protocols in situations where encryption of the messages is not considered important while message integrity and authentication of the messages is considered important. For example, if Alice intends to send a file to Bob while ensuring that the file remains unaltered during transit, Alice can include a hash of the file for Bob to verify. However, an adversarial user could potentially modify the file, compute a new hash based on the altered file, and send it to Bob. From Bob's perspective, when he independently computes the file's hash, it would match the hash he received.
To address this vulnerability, HMACs introduce a layer of security by combining the hash with a secret key. These HMACs take both the input and your secret key, and then generate a unique hash. In the event of a malicious user attempting to modify the file, they won't possess the necessary key to generate a valid hash. Consequently, when Bob calculates a hash of the received malicious file using the key, it will not match the hash computed by the malicious user, as the latter lacks knowledge of the secret key. This allows for the detection of an invalid message. Since the MAC can’t be spoofed (because the key is secret), you can store the hash next to the file and still trust the authenticity and integrity of your file.
HMAC (with SHA256 or SHA512) is a common algorithm used to combine input data with a key to generate a hash. Note that the message is sent unencrypted with the hash, so while a malicious user can read the contents of the file, he only can't alter it.
Authenticated Encryption
Now that we have discussed both encryption and integrity, it only seems reasonable to combine them. It is often necessary to combine encryption with authentication of the data for online communication. Encryption protects the data while message authentication codes (MAC) protect data against attempts to insert, remove, or modify data. Authenticated encryption is a way to transmit data encrypted while ensuring the integrity of data. In general, authenticated encryption makes use of a encryption algorithm together with a hash function to transmit the encrypted message and the MAC.
There are three approaches to authenticated encryption:
- Encrypt-then-Mac (EtM)
- Encrypt-and-Mac (EaM)
- Mac-then-Encrypt (MtE)
In general, Encrypt-then-Mac is preferred by most cryptographers since it protects against chosen cipher text attacks and avoids any confidentiality issues arising from the MAC of the clear text message.
Digital Signatures
Digital signatures serve the dual purpose of confirming the legitimacy of a message (or document) and ensuring its integrity. They enable a recipient to confirm the identity of the sender, thus the sender can later not deny that he/she sent the message. Importantly, any attempt to alter the message will result in an invalid signature, providing assurance to recipients that the signature is authentic and has not been copied from another source.
In the asymmetric encryption section, we saw how we can use public and private keys to encrypt and decrypt messages. These two keys are interchangeable, meaning it is entirely possible to employ the private key to encrypt a message, which can then be decrypted using the public key. This unique duality forms the foundation of digital signatures, a concept contrasting with the principles of asymmetric encryption. In the context of digital signatures, if the holder of the private key sends a message encrypted with his private key, the recipient can confidently ascertain the message's authenticity because of the fact that only the sender possesses the private key, making it impossible for anyone else to generate a message that can be decrypted with the sender's public key. This validation process is the essence of a digital signature.
We also saw the drawbacks of using asymmetric encryption. These also affect digital signatures in the same way. It is very inefficient to encrypt long messages and files using this scheme. Therefore, in practice, digital signatures most often work with hashes of documents, i.e., they are indirect signatures. Instead of signing a potential long electronic document, a cryptographic hash is calculated and then signed with the signer’s private key. The receiver of the document and signature can then verify the signature by obtaining the signer’s public key, calculating the hash of the document, and comparing the decrypted signature with the locally calculated hash. Previously, we were using hashes to make sure that our data hadn’t changed. But now, by hashing data with our private key and sharing that hash, we certify to others that we have “signed” the message. Others can verify that the hashes match our public key and can be sure that the message came from us.
Another drawback of asymmetric encryption was that it is difficult to verify the authenticity of the public key i.e. it belongs to the person or entity claimed, and has not been tampered with or replaced by some (perhaps malicious) third party. If Mallory creates a key pair and she manages to make Bob believe the public part of the key pair belongs to Alice, then she can send signed messages under the identity of Alice and Bob will believe them to be authentic. Another problem arises if private keys are leaked or broken (or expired). Such an event can effectively turn all past signatures useless. So Bob not only needs to trust that Alice’s key is in fact Alice’s key, he also needs to verify at the time he uses the key that the key is still valid and has not been revoked yet.
Also, do not confuse digital signatures, which use cryptographic mechanisms, with electronic signatures, which may just use a scanned signature or a name entered into a digital form. Electronic signature is pretty pointless from a security point of view since pretty much everybody can learn how to copy a scan of a hand signature into a document!
Digital Certificates
Earlier we ran into the problem of not being able to trust public keys as it is not trivial to guarantee that it actually belonged to the person or entity claimed. The solution to this lies in the implementation of digital certificates.
A public key certificate is an electronic document used to prove the ownership of a public key, which includes the following:
- information about the public key
- information about the identity of the owner of the key
- information about the lifetime of the certificate
- the digital signature of an entity that has verified the certificate’s contents (called the issuer of the certificate)
If the signature is valid, and the software examining the certificate trusts the issuer of the certificate, then it can trust the public key contained in the certificate to belong to the subject of the certificate. Obviously, to trust a given certificate, you need to trust the issuer of that certificate. This may require to trust the issuer of the issuer of the certificate and so on. This results in a chain of trust relationships that must be rooted somewhere.
A public key infrastructure (PKI) is a set of roles, policies, and procedures needed to create, manage, distribute, use, store, and revoke digital certificates and manage public-key encryption. A central element of a PKI is the certificate authority (CA), which is responsible for storing, issuing and signing digital certificates. CAs are often hierarchically organized. A root CA may delegate some of the work to trusted secondary CAs if they execute their tasks according to certain rules defined by the root CA. A key function of a CA is to verify the identity of the the owner of a public key certificate.
This mechanism is widely used on the internet. It's called the X.509 public key certificate format. X.509 certificates are used in many Internet protocols, including TLS/SSL, which is the basis for HTTPS, the secure protocol for browsing the web. This is used to verify that when I type in www.google.com, the response that I get is actually from Google and not anybody else. The website will first of all send the signed public key (digital certificate). My browser has a list of CAs that it trusts (and the public keys of those CAs). The browser will then determine if the CA that signed the certificate of Google lies in the chain of trust of CAs built into the browser. If that is the case, it will use the public key of the CA that signed this certificate to validate the signature of the certificate. If the signature matches, then the browser trusts the public key of the website. Once this trust is established, asymmetric encryption can allow for a new symmetric key to be exchanged which will allow for the rest of the communication on the channel to be securely encrypted! This is how the internet works!
Happy hacking!