While reading Real-World Cryptography, I came across the "million message attack". This is an attack that Daniel Bleichenbacher demonstrated in 1998, which effectively broke RSA with a particular encoding function called PKCS #1. It was only mentioned briefly, so I dug in and decided to try to understand the attack, eventually to implement it.

Most crypto libraries do not ship with a vulnerable implementation of this, for good reason. It's been broken! And if I implement the full attack against a real implementation, it would also come with using realistic key size.

Instead, I decided to implement RSA myself so that I could implement a weak encoding scheme so I could implement the Bleichenbacher attack! So far, I have an implementation of RSA and of PKCS (the vulnerable one). The basics of RSA took an hour to implement, then what felt like days to debug. And now it (seemingly) works! The attack will follow soon, with any luck.

What's RSA, anyway?

RSA is a public-key cryptosystem, in contrast to symmetric key cryptosystems. With symmetric keys, the sender and the recipient both share a key and use the same key to encrypt and decrypt the message. In contrast, public-key cryptosystems have a key pair, a public and a private key. The public key can be used to encrypt messages and the private key to decrypt them¹.

One of the drawbacks of a symmetric key system is that you have to share the key. This means you have to use a different secure channel to transmit the key, and then both parties need to be really careful to keep it a secret. This isn't manageable for a system with a lot of participants, like the internet!

But symmetric key encryption is often very fast, and we have some of the operations for it even baked into hardware. It would be nice to use it where we can for that efficiency.

In contrast, with public-key cryptography, you can freely share the public key, and anyone can then use that to encrypt a message to you. This means you do not need a separate secure channel to share the key! (Although this ignores the whole problem of validating that the key comes from the right person, so you're not having your connection spoofed by an interloper.) And this is great! This is what RSA gives us, but the computations for RSA are slow and the messages you can send are also small.

In practice, RSA was used (regrettably, sometimes still is) to establish a secure connection and perform a key exchange, and then the keys you exchange let you use symmetric key encryption. You probably shouldn't use RSA. Modern alternatives exist that are better, like Curve25519 and other forms of elliptic-curve cryptography.

But for worse, we run into RSA, and it's also a fun historical artifact! It's worth understanding in, and hey, implementing it is just plain fun.

The basics of RSA

RSA is a nicely elegant cryptosystem. Its security is based on the difficulty of factoring the product of large prime numbers, and in its purest form it has no known breaks². However, as mentioned above, depending on how data is encoded, particular uses of it can be broken.

The basic operations of it are straightforward to express. There are three components:

1. Generating keys
2. Encrypting and decrypting!
3. Encoding messages

We'll go through each of those, starting with generating keys.

Generating your keys

First of all, what even is a key? We know that it's used to encrypt or decrypt a message, but what is inside it?

For RSA, a key comprises two numbers. One of these is called the exponent and one is the modulus. A key could be (exp=3, mod=3233), for example. It's really just this pair of numbers³.

The reason the pieces of it are called the exponent and modulus is because of how we use them! RSA relies on modular arithmetic (like clock math, if you're not familiar). These are the exponents and modulus for the encryption or decryption operations which we'll see later.

To generate a key, you follow a short procedure.

1. First, pick two prime numbers which we'll call p and q. Then we compute n = p * q.
2. Compute a number t = lcm(p-1, q-1). This is the totient, and we use this as our modulus for generating the keys but then never again.
3. Pick the public exponent, which we'll call e. The requirement is that it shares no factors with t and is greater than 2. One simple way is to start with 3, but go up through the primes until you find one coprime with t. Choosing 65537 is also quite common, since it's small enough to be efficient for encryption but large enough to avoid some particular attacks.
4. Calculate the private exponent, which we'll call d. We compute this as d = e^-1 mod t, or the inverse of e in our modulus.

Now you have d and e, the private and public exponents, and you have n, the modulus. Bundle those up into two tuples and you have your keys!

Let's work an example quickly to see how it ends up. For our primes, we can choose p = 17 and q = 29. So then n = 493.

Now we find t = lcm(17 - 1, 29 - 1) = lcm(16, 28) = 112. We'll choose e = 3, which works since 2 < 3 and gcd(3, 112) = 1 so we know they share no factors. Now we compute⁴ d = e^-1 = 3^-1 = 75 mod 112. And then we have our keys!

Our public key is (exp=3, mod=493), and our private key is (exp=75, mod=493). We'll use these again in our examples on encrypting and decrypting!

Encrypting and decrypting a message

Now that we have our keys, we can encrypt and decrypt a message! Normally, we would think of a message as something like "hello, world" but to RSA, every message is a single integer. Let's assume for now that we're okay with this, but we'll come back to how we get from a message to an integer later.

Our message integer has to be less than our modulus, otherwise we can't decrypt it, since you'll never get back something larger than the modulus in modular arithmetic. Let's call that message m.

To encrypt the message, we take our exponent e and modulus n from the public key and we compute the ciphertext c = m^e mod n. This gives us back another integer, which we can send to the recipient!

For them to decrypt it, they use the exponent d and the same modulus n from the private key, and compute the plaintext as m = c^d = (m^e)^d mod n. This works out and the exponents essentially cancel out (we're hand waving, but trust me—or at least trust Rivest, Shamir, and Adleman).

As an example, let's encrypt something and decrypt it again. Let's say our message is m = 42, for arbitrary reasons. To encrypt it using our keys from earlier, we compute c = m^e = 42^3 = 138 mod 493. And to decrypt our ciphertext, we compute m = c^d = 138^75 = 42 mod 493.

That's it as far as encrypting and decrypting goes! It's elegant, and deceptively simple: this simplicity is why so many people implement their own versions of RSA and roll their own crypto vulnerabilities. Don't do it for anything that matters! But do roll your own for the fun of it.

How do you encode messages?

Okay, so how do we get from a string of characters, like "hello, world", to an integer? We encode it! And if the message is too large to fit in one integer, we can split it into multiple integers and encrypt each of them.

Everything in a memory in a computer is just bytes. You have a string of characters, and underlying that is a byte array. You have an integer, and underlying that are some bytes! This is how we're going to go between them.

Let's assume for simplicity that we're using 64-bit integers. Then each integer is 8 bytes. In our message "hello, world", we have 12 bytes!

Each character has a byte value. Here, we're assuming it's ASCII encoded for simplicity. This converts nicely into an array of 8-bit integers, or single bytes.

And now we can turn this into two byte arrays of length 8. The first 8 bytes become one array, and the last 4 bytes become the second one. We can left-pad it with 0s, but we could also right pad if we prefer; either way we have to pad, and then we have to remember to stick with the same big-endian or little-endian encoding.

Now since these are 8 bytes each, we can use them as the memory for a 64-bit integer! They are 7522537965569712247 and 1869769828, respectively. You can encrypt each of these (given a key that has a high enough modulus), and then you're in business!

In practice, you want to use one of the other encoding schemes. PKCS #1 was popular for a while, but has some flaws. Notably, this made problems for some versions of SSL. There are improvements to PKCS now, but it's still not something you should use since that would mean you're using RSA! (Yes, I'm going to keep reminding all of us to not use RSA.)

Lessons learned

I learned a lot in the process of implementing RSA here. Here are a few of the key things, in kind of a scattered list.

• Implementing cryptosystems is fun. This was one of my biggest takeaways. One time I got to chop down a tree and it was exactly as fun as I imagined it would be. This was the same: I'd long imagined how satisfying it would be but was intimidated, and diving in let me understand that this isn't so scary, and it's a lot of fun.
• There are a lot of subtle ways to be vulnerable. We use libraries with constant-time operations to avoid timing attacks. Bleichenbacher's whole attack relies on being able to detect if encoding is incorrect, so any subtle signal of where the decryption fails is useful for this. There are myriad other ways to be vulnerable. This reminds me why we need to rely on deep expertise in cryptography, rather than go around implementing these ourselves.
• Big-endian vs. little-endian still trips me up. I can never remember which is which, so I really desperately need to write a blog post about it as my own reference.
• Debugging this is tricky! In particular, I'd originally missed the requirement that the message was less than the modulus, and ended up having sporadic failures depending on the primes chosen and the message. That made for tough debugging, but setting constant small p and q helped. There were a few other tough instances of debugging, and I expect there are some issues that remain!
• Security properties can be at odds with ergonomics. The bigint library I'm using has a lot of properties you want: constant-time operations, checked or wrapping operations, good efficiency. But it's also sometimes hard to read code written with it, since you have to be fairly explicit about the operations you're using. There are some improvements to be made, but it feels like there's an inherent tension here.
• Reading RFCs and some cryptography papers is... accessible? I was surprised when I read the Bleichenbacher paper and felt like it was pretty easy to read. I have a math degree, but not much background in cryptography (and a decade between me and a math classroom), so this was very encouraging! The RFC for PKCS was also readable, which was nice to find out.

What's next

Now I have a toy implementation of RSA and PKCS, so it's time to do what I came here for: break the thing. The toy implementation is published on crates.io, and the source is available. In a future blog post, I'll talk about how the attack works and provide a demo.

I might also take a swing at some of the other classic cryptosystems. The Diffie-Hellman key exchange is calling out to me, for example.

If you've implemented a cryptosystem just for fun, I'd love to see it.