Cryptopals Set 2 Challenge 16 // code repo // demo

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 As.

The challenge has us write some basic one-liners to escape and de-escape the special characters ; and = (to prevent the trivial solution of just entering these directly into the user-supplied data).

const enc = { ";": "%3B", "=": "%3D" };
const decr = { "%3B": ";", "%3D": "=" };
const quoteOut = (txt) => txt.replace(/(\;|\=)/g, ($1) => enc[$1]);
const quoteIn = (esc) => esc.replace(/(\%3B|\%3D)/g, ($1) => decr[$1]);

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.

function randomEncrypt(pText) {
  pText = txtToHex(quoteOut(pText)).map((e) => hexPad(e));
  let input = PKCS7(pre.concat(pText, post), 16);
  return aesEncryptCBC(input, randomKey, randomIV, 16);
}

We write a function to decrypt and unescape the special characters.

const randomDecrypt = (c) =>
  quoteIn(aesDecryptCBC(c, randomKey, randomIV, 16).map(hexToText).join(""));

We’re then challenged to manipulate the ciphertext results of the encryption function to produce a ciphertext that decrypts to contain the string ;admin=true;.

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[0] = ‘n’ (0x6e)
• Cn[0] (post-decryption) is the value we wish the plaintext to have Z (0x5A)
• Cn-1[0] 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 Zg%20MCs%3Buserd. Zing!

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 0s.

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 ; and = 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.

for (var i = 0; i < theReplacements.length; i++) {
  e[32 + i] = hexXOR(e[32 + i], theReplacements[i]);
}
randomDecrypt(e);

comment1=cooking%20MCs;userdo|=¦1^<ÉTv¤Ï;admin=true;comment2=%20like%20a%20pound%20of%20bacon

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 blockLength chars.