Cryptographic Primitives

Knowing which concept to use to protect your information is crucial when applying cryptography on production systems. Not all primitives are built equally, and their guarantees need to be understood to prevent catastrophic mistakes. Before diving in to the details, consider your end goal for the data that you protect:

• Secrecy: An adversary with access to a piece of data should not be able to extract any meaningful information out of it.
• Authenticity: An adversary should not be able to forge a message or spoof the identity of the original author.
• Trustworthyness: How can one party trust the other when exchanging information?

There are other goals, but the main ones fall into the three categories shown above. The primitives presented here address all of them, along with some nuances and consequences. These primitives make up the vast majority of modern safe digital communication.

Ciphers

Ciphers are just algorithms that obfuscate and transform data into a format that is designed to be hard to extract meaningful information from. There are countless examples of ciphers used in history, such as the well-known Caeser cipher. Ciphers can be built many ways (a lot are not as secure as they seem), but this guide will only focus on key-based algorithms.

Symmetric Encryption

Symmetric-key encryption involves a pair of functions $E, D$ and a secret key $k$. The functions take in a plaintext message $m$ and produce a ciphertext $c$:

\[E(m, k) = c \neq m,\] \[D(E(m, k), k) = m.\]

In order for $E$ to somewhat maintain secrecy, it cannot produce $c = m$. Otherwise, the whole purpose of encryption is defeated. A common example of this is $\text{XOR}(m, 0) = m$. The decryption function $D$ should undo the encryption and retrieve $m$ in its original form. Notably, $k$ used for both encryption and decryption and is shared between both parties.

Symmetric-key encryption can use either stream ciphers or block ciphers. Stream ciphers encrypt the bytes of a message one at a time. Block ciphers take a number of bits and encrypt them in a single unit, padding the plaintext to achieve a multiple of the block size. Examples of popular symmetric-key algorithms include Twofish, AES (Rijndael), Camellia, ChaCha20, Blowfish, RC4, DES, and 3DES. The details of each algorithm could be further explored in a distinct lesson.

Asymmetric Encryption

These types of algorithms belong to a broader field of public-key cryptography. As the name implies, rather than having a shared secret key, asymmetric encryption uses a keypair $(k_{pub}, k_{pri})$, where $k_{pub}$ is the public key and $k_{pri}$ is the private key. Each party has their own keypair making the total number of keys twice the number of parties involved. Using math that will not be discussed in detail here, the public key can be freely shared with anybody in the world, including the adversary. The private key must be kept secret at all times, however. Below shows an example of how asymmetric encryption can be used:

1. Bob wants to send plaintext $m$ to Alice.
2. Bob encrypts with Alice’s public key: $E(m, k^{(A)}_{pub}) = c$.
3. Bob sends ciphertext $c$ to Alice. Any adversary positioned along this path would be able to intecept, but not decrypt $c$.
4. Alice receives $c$ and decrypts it using her own private key: $D(m, k^{(A)}_{pri}) = m$.
5. $m$ should be decrypted and readable to Alice.

Some famous asymmetric encryption algorithms include the Diffie–Hellman key exchange protocol, DSS (Digital Signature Standard), ElGamal, Elliptic-curve cryptography, and RSA. The details of each algorithm could be explored in a distinct lesson.

A notable application of both symmetric and asymmetric encryption is TLS, the protocol powering HTTPS. Asymmetric encryption is harder to compute than symmetric encryption, making it slower for certain tasks. TLS uses asymmetric encryption during the handshake, where Diffie Hellman key exchange is performed to get a shared key. Once established, both parties using TLS switch to a faster symmetric algorithm using the shared key generated by the handshake. This key does not live very long and is regenerated each time a new handshake occurs.

Initialization Vectors

Currently, our encryption algorithm $E(m, k)$ always produces the same $c$. This may not seem problematic at first, but consider the following scenario:

1. Alice sends numerous messages with the same key $k$ to Bob.
2. Among those messages, $c’ = E(m’, k)$ is send a bunch of times.
3. The adversary sees that the contents matching $c’$ were sent repeatedly.
4. This does not directly leak $m’$, but may be consequential in some circumstances.
5. Even though the adversary cannot directly read the plaintext, they can still learn patterns and structures over time.

IVs aim to prevent the above scenario by introducing randomness like so:

\[E(m, k, IV_1) \neq E(m, k, IV_2).\]

Namely, even if $m$ and $k$ are the exact same, the ciphertext generated would differ due to separate IVs. This ensures a randomized encoding of a message is fresh, so identical inputs never produce predictable or repeatable outputs.

Hashing

A hash function takes an input of any size (generalized as a bit stream) and returns an output of a fixed size such that changing any bit of the input would also change the output. The output of a hash function is called the digest.

\[H : \{0, 1\}^* \rightarrow \{0, 1\}^n,\]

where $n$ is the digest length.

A crytographically-secure hash function is not feasibly invertible. That is, given the output of the hash function and the code of the function itself, finding an input that would generate that output requires work equivalent to brute forcing until the desired output is found. Some popular hash functions are MD5 (proven not secure), SHA-1, SHA-2, SHA-3, BLAKE2, and BLAKE3. You can learn more about SHA-256, a variant of SHA-2 where the digest length $n = 256$ bits.

Salting

Among other applications, hashing is used to store passwords in databases safely. Due to the one-way nature, an adversary that has compromised the database will only be able to see the digest and not original password. However, if a particular $H(p) = h$ is found, the adversary can store them in rainbow tables like the one shown below:

Plaintext	Digest
$p_0$	$h_0$
$p_1$	$h_1$
…	…

This means any $p$ that has an associated $h$ would be forever unsafe to use as a password. Just like IVs, salts can prevent this by introducing some randomness to make rainbow tables essentially useless:

\[H(s_1p) \neq H(s_2p),\]

where $s_1p$ and $s_2p$ stand for the salt $s_1$ and $s_2$ concatenated with the plaintext $p$ respectively.

Digital Signatures

So far, methods that attain secrecy have been covered: ciphers allow messages to be secret when passed around and digests make inferring plaintext nearly impossible. This section will address how to ensure authenticity when communicating. Even though the adversary may not be able to read messages, they can still pretend to be someone they are not, and digital signatures prevent this. We can reuse the concept of asymmetric encryption to sign messages:

1. Alice sends $m$ to Bob, but Bob wants Alice to prove that $m$ was sent by her and not somebody pretending to be her.
2. Alice generates $c_{signed} = E(m, k^{(A)}_{pri})$ using her private key.
3. Since Alice’s public and private keys are mathematically tied as a keypair, Bob can get the original $m = D(c_{signed}, k^{(A)}_{pub})$.

This whole process is just utilizing asymmetric encryption in reverse. Alice encrypts (or signs) the message using her private key, then Bob can use her public key to undo the encryption. In order for this to work, he needs to trust the public key actually belongs to Alice (more on this in the next section).

Side note: it is inefficient to sign the entire message. In real use cases, only the digest $H(m)$ is signed, making the process $E(H(m), k_{pri})$. Besides signatures, $H(m)$ also serves as the checksum, which is a more general way of detecting message corruption.

Message Authentication Codes

A version of digital signatures exists for symmetric encryption. Since $k$ is shared between both parties, the function works as follows:

\[t = \text{MAC}(m, k)\]

produces a tag $t$ that is sent along with $m$. This ensures that $m$ was sent by somebody who had the secret key $k$. The symmetric cipher itself only ensures that the message contents is secret, but it doesn’t ensure that it is not maliciously corrupted. Combining asymmetric encryption and a message authentication code is called authenticated encryption.

Certificates

Recall from above, Bob needed to trust $k^{(A)}_{pub}$ is the actual public key that Alice owns. A simple method to accomplish this is for Alice to directly tell Bob her public key. However, this becomes quickly infeasible over the internet. You would have to physically reach out to every website you visit, which would be a nightmare! Instead, modern web has adopted public-key infrastructure, and a common tool for verifying public keys are certificates. Below displays an example certificate for this site:

There are different certificate formats, such as X.509 and PKCS, but at a high level, a certificate contains:

• Subject: Who this certificate is about (in our example, Alice is the subject).
• Public key: The public key that the certificate verifies (in our example: $k^{(A)}_{pub}$).
• Issuer: Who is the authority that made the claim?
• Signature: This proves the issuer signed the certificate. It also places responsibility on the issuer and they cannot claim they were not in the know because they had to have used their $k^{(issuer)}_{pri}$ to sign the certificate.

Certificate Authority

Since certificates require the issuer to sign, this raises a circular problem. How can anyone trust that the issuer is who they say they are? The solution is for more high-profile authorities to issue certificates to the lower-level issuers. This forms a hierarchical structure of CAs ending at the root CA:

The important question now becomes: if root CAs are not certified, how can they be trusted? The answer is a combination of politics, laws, and human governance. At a certain point, your system (OS or browser) hardcodes a curated set of root public keys, and verification starts from there. This might be an unsatisfying answer not rooted in cryptography, but it is what we really use today. Here is an example of 8 out of 134 trust anchors trusted by Google Chrome:

These root CAs are scattered around the world, and are constantly verified to make sure no breaches occur. If an adversary manages to impersonate a root CA, catastrophic consequences for the global web will occur because of everything we have discussed above.

Common Pitfalls

Many crytographers around the world have proven the security of common crytographic algorithms, so why are there still exploits related to crytography? In the vast majority of cases, non-careful use of encryption and authentication has often resulted in security flaws despite using otherwise secure cryptographic functions. Here are some subtle ways an adversary might compromise a seemingly safe implementation:

Alice signs with $k$ that Bob also knows. The ciphertext $c$ is transferred from Alice to Bob.

Problem: An adversary could modify $c$ and Bob would never know if that was Alice’s true intention.

Solution: Alice should use a MAC so that Bob can ensure $m$ is authentic.

Suppose Alice sends to her bank c = E(“pay Bob $100”, k) as a one-time transaction. They both use authenticated encryption, so everything seems correct…

Problem: Bob later could replay $c$ to the bank, tricking it to believe Alice wanted to pay him $100 again. This is known as a replay attack.

Solution: Alice and her bank should use a nonce. Alice could choose a random large nonce $n$ and send $c = E(nm, k)$ to the bank, where $nm$ is the nonce concatenated with the message. The nonce changes each message, meaning the next message sent is $c’ = E(n’m, k)$. Bob would need to know the exact nonce every time in order to replay $c’$. This would be very hard for Bob since the nonce is also encrypted.

A weak random number generator is used.

Problem: Most software random number generators are actually pseudo-random number generators, meaning they are created by a deterministic subroutine with some internal state. If you know the value of that state, you can predict the sequence of random numbers perfectly, and observing a sequence of generated numbers is sufficient to re-construct the state.

Solution: Modern operating systems typically harvest likely sources of entropy and maintain an entropy pool. Hardware often contributes timing variations in operational noise, such as thermal fluctuations, microarchitectural behavior, unpredictable delays in disk access, network packet arrivals, and interrupt scheduling.