Working the Problem #2

I finally solved challenge #11 of Cryptopals, after sorting out a few key misunderstandings. Now, I’m working on challenge #12, “Byte-at-a-time ECB decryption (Simple)”. God help me — if this is simple, I hate to see what’s complicated. Granted, most of the steps are outlined, but I’m missing something key here when it comes to decrypting bytes beyond the first 15.

Let’s back up. What follows is basically a stream-of-consciousness: you’re seeing me work the problem in real-time, “rubber duck debugging”, essentially. Spoiler alert: if you’re doing the Cryptopals challenges or plan on doing so, this might ruin the fun, depending on how far I get.

The challenge is an interesting one. Essentially, if you add known plaintext to mystery text, encrypted using ECB (Electronic Code Book) mode, one byte at a time, you can decrypt the mystery text, without the key. If you write software, this should scare the living shit out of you.

This is how it works: you start by providing a plaintext byte (let’s say “A”). Appended to this byte is the mystery text, in what we’ll call an “oracle function”. You keep adding bytes, the same byte, until you see that the blocks start repeating — that’s the key that tells you it’s using ECB mode. You can determine the block size using the same technique, observing when the first block stops changing. That’s the easy part.

The hard part is decrypting the mystery text, byte by byte. The first byte? That’s easy enough. You take the block size, subtract one, and create plaintext with that one byte at that particular length. Run it through the oracle function. Now, you go through all the possible bytes, 0 through 255, and add them to your repeated “A”s to get a full block. Then, you compare each block to the actual ciphertext given by the oracle function — when you hit a match, boom, you have the first byte of the mystery text, because you know the rest of the block and you know that last byte.

Now how do we get the rest of the bytes? I get the first 15, no problem. What you do is essentially the same as the last paragraph, with a few exceptions. First of all, let’s say the block size is 16, which using AES in ECB mode, it is. That would mean, in the last paragraph, your plaintext was 15 bytes of “A”. This time, for the second byte, we’re going to make it 14 bytes of “A”. That way, the last byte in the 16 byte block will be the second byte of mystery text. Remember, we already know the first byte, so when we iterate over bytes 0 through 255, we can append the bytes we’ve already seen to the plaintext, followed by the byte we’re iterating. In this way, we discover bytes 0-14 (15 bytes total, like I said at the beginning).

This is where I’m really stuck right now. Once I exhaust the first block, I don’t quite know where to go. Sure, I could keep appending the known bytes to my repeated text. And that should give me bytes 15 to n. I just know I’m doing something wrong with the math for the block selection, and the multiple for the block length. But! I have a debugger (pry/byebug with Ruby) and I know what the values should be, so I just have to work backwards and figure out the arithmetic for the block index and block multiple. I think looking at it with fresh eyes tomorrow night will help, as I’ve been working on this literally all day, since I woke up.

That should do it for now — I’m getting a bit verbose, compared to my other posts. From here, I think a good night’s sleep and reflection on what I’ve written here will allow me to solve the problem tomorrow.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.