Step 1: Flipping Bits, Wearing Knits
In CBC decryption, the plaintext of each block’s post-decryption is XOR’d with the previous block’s ciphertext. Altering ciphertext block
N-1 (Cn-1) thus effects the
Nth block of resulting plaintext (Pn). CBC cares not whether a message has been tampered with. It has no MAC. We can XOR arbitrary bytes into the ciphertext and have them appear in the plaintext under two conditions:
- We know the plaintext
- We know the ciphertext
Step 2: But How Can We Know the Plaintext?
Well, if there’s a user component, the plaintext can be whatever we’d like it to be. Lots of
The challenge has us write some basic one-liners to escape and de-escape the special characters
= (to prevent the trivial solution of just entering these directly into the user-supplied data).
We write a random encryption function that prepends the escaped string
comment1=cooking%20MCs;userdata= to user-supplied data, appends the escaped
;comment2=%20like%20a%20pound%20of%20bacon, PKCS#7 pads, and encrypts under a random key and IV using CBC.
We write a function to decrypt and unescape the special characters.
We’re then challenged to manipulate the ciphertext results of the encryption function to produce a ciphertext that decrypts to contain the string
Step 3: Twiddles and Bits (Theory)
You can write to the plaintext in contiguous blocks of
blockSize characters. Writing to block Pn+1 requires modifying block Cn-1 and creates gibberish in Pn, since the error introduced into Cn-1 propagates one block forward to Cn. If you’d like to write more than a
blockSize worth, write to every other plaintext block, so long as you do not care about intervening gibberish plaintext blocks.
What and how to write? Think about the decryption process (
n==block, i==block byte index):
Cn-1[i] XOR Cn[i] (post-decryption) = Pn[i].
We want to change Pn[i] to a given value, and we need to know what to change Cn-1[i] to in order to do this. So just solve for it.
Cn-1[i] = Pn[i] XOR Cn[i] (post-decryption)
- Pn[i] is just the current plaintext value of the block we wish to modify
- Cn[i] (post-decryption) is the value we wish the plaintext to have
- Cn-1[i] is the byte we flip (XOR-ing in (Pn[i] XOR Cn[i])) in the ciphertext
Note the special case when
n=1, and the previous ciphertext block is the CBC initialization vector.
Here’s one more visual, in case ASCII does it for you better:
Plaintext |comment1%3Dcooki||ng%20MCs%3Buserd| Block 1 Block 2 Ciphertext |----------------||----------------| Block 1 Block 2
Let’s say I want to flip ‘n’ in Block 2 to ‘Z’.
- Pn = ‘n’ (0x6e)
- Cn (post-decryption) is the value we wish the plaintext to have Z (0x5A)
- Cn-1 is the byte we need to flip in the ciphertext
0x63 XOR 0x5A = 0x39. Then just set byte 1 of block 1 of the ciphertext to ^=(0x39). The first block of plaintext in the decryption output is jumbled, but the second block reads
Step 4: Twiddles and Bits (Praxis)
We know that the blocks of plaintext (chunked 16 byte sections) look like this when userdata is
comment1%3Dcooki ng%20MCs%3Buserd ata%3D%3Bcomment 2%3D%20like%20a% 20pound%20of%20b acon
We know that we want to have a
%3B at the end of our string. But if we put it in ourselves, we’ll be over 16 characters, which is the limitation for contiguous character writing with
blockSize==16. So I’ll use the existing
%3B, before ‘comment’, padding out
userdata with 25
randomEncrypt('0000000000000000000000000') gives us this:
comment1%3Dcooki ng%20MCs%3Buserd ata%3D0000000000 000000000000000% 3Bcomment2%3D%20 like%20a%20pound %20of%20bacon
When we decrypt, we map the escaped characters
= back from their escaped forms, so we should really make the replacement of
%3Badmin%3Dtrue%3B. I’ll calculate my array of replacements and XOR each one with our padding character (‘0’ == 0x30).
'%3Badmin%3Dtrue'.split("").map(e=>parseInt(e.charCodeAt(),10).toString(16)).map(e=>hexXOR(e,'30')); => ["15", "3", "72", "51", "54", "5d", "59", "5e", "15", "3", "74", "44", "42", "45", "55"]
We can XOR in our 15 hex characters with ciphertext block 3, and the result will end up in plaintext block 4, followed by the
%3B we borrowed.
This replacement occurs without any direct knowledge of the encryption key or the initialization vector, simply a manipulation of the ciphertext output. What have we learned today? Use a MAC!
The challenge to write a function that lets you XOR arbitrary lengths of text into the ciphertext is left as an exercise for the reader. Though perhaps not a valuable one, what with the interleaved mangled plaintext block every