Recently while reading Real-World Cryptography, I got nerd sniped¹ by the mention of Bleichenbacher's attack on RSA. This is cool, how does it work? I had to understand, and to understand something, I usually have to build it.

Well, friends, that is what I did. I implemented RSA from scratch, wrote the attack to decrypt a message, and made a web demo of it. Here's how I did it, from start to finish.

If you're here for the demo, feel free to peruse it before, during, or after reading this post! It's a lot of fun. Otherwise, buckle in for a fun ride.

What even is the Bleichenbacher attack? Wait, what is RSA?

Okay, so let's take a step back. RSA itself is a cryptosystem that's, unfortunately, still widely used despite it being a bad idea to use it. That's covered in my post about RSA, which gives a nice overview. And the Bleichenbacher attack is a famous way to take an RSA-encrypted message² and find what it means without having the private key.

When I learned about the Bleichenbacher attack, I wanted to know how it worked in detail, not just broad strokes. So I went to the source, the paper he wrote in 1998. The paper contains a lot of math, but it's surprisingly approachable as long as you're looking to understand how to implement the attack. Why it works, and the math derivations? I dunno. But how it works in practice, algorithmically? Approachable!

After I read the paper, though, I realized I needed to know more—a lot more—about how RSA itself works. So I read the RSA page on Wikipedia a couple of times and worked through some examples by hand with very small numbers. Comfortable that I understood it more or less, I turned back to the paper.

That's when I remembered that the paper was talking about a particular encoding scheme used with RSA, called PKCS #1 v1.5. So I had to read about that, too. Then I read the paper again in that context, and was ready to dive in.

I came up with a plan of attack, pun intended:

• Implement RSA. I wanted to do this myself so I can use very small keys and small messages, which would be faster to attack, so that I would know more quickly if my attack works or not. A lot of existing implementations strongly discourage, or prevent, using the vulnerable stuff, which was kind of the point here.
• Implement the attack. Then it would just be code up the paper, right? How hard could it be, right?
• Make a web demo! This was always the end goal, so it influenced the design from the beginning. I don't want to ship Python to the browser, for example.

Implementing RSA

Writing my own RSA library was definitely a good choice for learning. I strongly recommend people do this for fun and education, and also please license it under something that discourages usage unless you're actually getting it vetted and checked.

For my library, cryptoy, I used Rust so that I could use that sweet WASM toolchain. This would let me build it for the web and make an interactive demo!

I built it once, then rebuilt it again to make the interfaces better. And then I realized that the bigint library I was using was going to make things difficult for the demo I wanted, so I migrated to a different one. I was originally using crypto-bigint, which is probably the one you want for any real cryptography applications in Rust, because it uses constant time operations wherever possible. The challenge was that it requires fixed precision³, and that meant that it would be tough to write something that handles both very small and very large keys.

So, I migrated to use num-bigint-dig. It has bigints with arbitrary precision at runtime, exactly what I want. It library seems reasonable for my purposes, but doesn't have the vetting that crypto-bigint does, so I'd be more wary of it in production. It very well could be fine, but it hasn't been audited and I don't know if there are problems. But given that the whole point here is to produce something vulnerable to a particular attack? Yeah, I'm okay with that.

The other point in favor of num-bigint-dig was that it had nice things built in, like generating random primes. These were needed and I didn't have to go looking for them, so it makes the code nicer and tighter. The ergonomics of the code also feel better, which is subjective.

After I implemented RSA, I started to build a demo of it in a little playground. I got started, but didn't finish it. It was really fun pairing with a friend on this for a bit, and ultimately I didn't find the thing that would make it a compelling demo, so it was dropped. But like Chekov's gun, will it return?

Implementing the attack

The attack itself was pretty easy to get partially working, and then very challenging to flush the bugs out of. It would make progress, make progress, then stall. At some point I figured out that the problem related to rounding (in part by looking at other implementations, and mostly by squinting at the paper a lot). Somewhere, my rounding went wrong. I fixed it, mostly. Then I rewrote it again and it worked! I'm still not sure what the difference was and I'm not looking back to figure out.

That part was left with one fatal bug which annoying but I accepted, just to be done with the project: keys over a certain size would just totally fail! Except I couldn't really let it go, it kept bugging me. Eventually I realized that my iteration counter was an 8-bit int, for reasons that escape me⁴. The upshot of that was that every 256th iteration, my code thought it was at iteration 0, and it reset things. Once that was a larger type, bigger keys worked!

Once it was done and I had it output some stats like the number of iterations taken and the number of messages required, I was pretty sure there was a bug: this was converging too fast, yeah? But it turns out, it's actually fine! There's a thesis which shows that my messages required are about in the ballpark when using the kind of oracle⁵ I have.

The original paper called for an oracle which requires the padding to entirely be valid, but later results use a different oracle which just checks for two bytes at the start, 0x00 0x02. It was shown in Bock '18 that a lot of real-world cases of this attack provide this sort of oracle. So, this is a realistic assumption.

After this was done, I built another version of it as an iterator. I used the original code and encoded the state into an iterator so that, for a demo, I can show the progress and intermediate internal state along the way. Converting it to an iterator was fun, and pretty straightforward! It's a nice technique for looping algorithms, so that you have pause points between iterations where you can do other work.

Making the demo: it's Yew and me

To make the demo, I first procrastinated by looking at all the different Rust single-page app frameworks for an hour or two under the premise of "research". Then I decided to just use the one I already used on a different project, a framework called Yew.

I sketched out the design and figured out that what I wanted was something where you can see different steps along the way, but more importantly, get a feel for how the attack is progressing. I wanted you to feel how fast it is to decrypt one of these messages.

From there I just worked through it. Most of the code is boilerplate, lots of state hooks and forms passing data back out for later use. The code is all available if you do want to read it, so if you are curious, take a look! The most interesting part is probably the container for the attack itself. I needed to keep some state in there for where we are in the attack, and also needed to have it run on its own.

That state was kept inside the AttackDemo struct.

#[derive(Debug)]
pub struct AttackDemo {
    /// internal state, and the iterator for the attack
    pub attack_state: AttackState,

    /// stats we want to display
    pub iterations: usize,
    pub oracle_calls: usize,
    pub span: BigUint,

    /// a ticker which gives us a call every so often
    pub ticker: Option<Interval>,
}

Then I implement Yew's Component trait for it. We start with the associated types: we have Msg for the different messages we can send upon events, and a properties type for what's passed into the component.

impl Component for AttackDemo {
    type Message = Msg;
    type Properties = AttackProps;

    // ...
}

pub enum Msg {
    Step,
    Run,
    Pause,
    Reset,
}

#[derive(Properties, PartialEq)]
pub struct AttackProps {
    pub attack_state: AttackState,
}

Then we have the methods. The create and view functions are boilerplate, just initializing the state and rendering some HTML with buttons for emitting different messages. A stripped down form of view to just contain one button which sends a message would look like this. The rest of it is similar to add more buttons, and render some data which we get from self.

    def view(&self, ctx: Context<Self>) -> Html {
        let run = ctx.link().callback(|_| Msg::Run);

        html! {
            <div class="attack">
                <input type="button" value="Run" onclick={run} />
            </div>
        }
    }

The update function is where the attack code is invoked! It looks like this. We receive a message, and then pattern match on it. For Step, we perform one iteration and cancel the ticker if we've exhausted the iterator. For Run, we start a ticker for every 20 milliseconds (faster and you can't see the attack progress). Pause does the opposite, and stops the ticker. And Reset clears all the state so we can start over!

    fn update(&mut self, ctx: &Context<Self>, msg: Self::Message) -> bool {
        match msg {
            Msg::Step(n) => {
                if let Some((_message, state)) = self.attack_state.attack_iter.next() {
                    self.set_iteration_state(&state);
                    true
                } else {
                    self.ticker = None;
                    false
                }
            }
            Msg::Run => {
                self.ticker = {
                    let link = ctx.link().clone();
                    Some(Interval::new(20, move || {
                        link.send_message(Msg::Step(1));
                    }))
                };
                true
            }
            Msg::Pause => {
                self.ticker = None;
                true
            }
            Msg::Reset => {
                self.ticker = None;
                self.reset_state(&ctx.props().attack_state.current);
                self.attack_state = ctx.props().attack_state.clone();
                true
            }
        }
    }

While working on it, I had to remember to use release builds for larger key sizes as I was testing, otherwise my computer got really hot and things never finished. Then again, it was pretty cold outside... so that was sometimes a benefit.

The final step was to create the release build and put it in a page on my blog! This was pretty straightforward, though I have some manual steps. There's not a good way that I can see to have Trunk build artifacts you can embed into another page; it wants to build the page, and have other things embed into it. Since I wanted to use my usual blog templates, I snagged out the pieces that I wanted from there, all good.

This was a really fun project, end to end! I don't think I would use Yew in production, because I am just not as productive in it as other things. And I certainly wouldn't use my own RSA code (or any other RSA) in production! But the point was to learn and have fun, and that was well achieved.

Now if you haven't gone and played with the demo, please do!