A padding oracle example

Early last week, I posted a blog about padding oracle attacks. I explained them in detail, as simply as I could (without making diagrams, I suck at diagrams). I asked on Reddit about how I could make it easier to understand, and JoseJimeniz suggested working through an example. I thought that was a neat idea, and working through a padding oracle attack by hand seems like a fun exercise!

(Having done it already and writing this introduction afterwards, I can assure you that it isn't as fun as I thought it'd be :) )

I'm going to assume that you've read my previous blog all the way through, and jump right into things!

The setup

As an example, let's assume we're using DES, since it has nice short block sizes. We'll use the following variables:

  P   = Plaintext (with the padding added)
  Pn  = The nth block of plaintext
  N   = The number of blocks of either plaintext or ciphertext (the number is the same)
  IV  = Initialization vector
  E() = Encrypt, using a given key (we don't notate the key for reasons of simplicity)
  D() = Decrypt, using the same key as E()
  C   = Ciphertext
  Cn  = The nth block of ciphertext

We use the following values for the variables:

  P   = "Hello World\x05\x05\x05\x05\x05"
  P1  = "Hello Wo"
  P2  = "rld\x05\x05\x05\x05\x05"
  N   = 2
  IV  = "\x00\x00\x00\x00\x00\x00\x00\x00"
  E() = des-cbc with the key "mydeskey"
  D() = des-cbc with the key "mydeskey"
  C   = "\x83\xe1\x0d\x51\xe6\xd1\x22\xca\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"
  C1  = "\x83\xe1\x0d\x51\xe6\xd1\x22\xca"
  C2  = "\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"

For what it's worth, I generated the ciphertext like this:

  irb(main):001:0>; require 'openssl'
  irb(main):002:0>; c = OpenSSL::Cipher::Cipher.new('des-cbc')
  irb(main):003:0>; c.encrypt
  irb(main):004:0>; c.key = "mydeskey"
  irb(main):005:0>; c.iv = "\x00\x00\x00\x00\x00\x00\x00\x00"
  irb(main):006:0>; data = c.update("Hello World") + c.final
  irb(main):007:0>; data.unpack("H*")
  => ["83e10d51e6d122ca3faf089c7a924a7b"]

Now that we have our variables, let's get started!

Creating an oracle

As I explained in my previous blog, this attack relies on having a decryption oracle that'll return a true/false value depending on whether or not the decryption operation succeeded. Here's a workable oracle that, albeit unrealistic, will be a perfect demonstration:

  irb(main):012:0> def try_decrypt(data)
  irb(main):013:1>   begin
  irb(main):014:2>     c = OpenSSL::Cipher::Cipher.new('des-cbc')
  irb(main):015:2>     c.decrypt
  irb(main):016:2>     c.key = "mydeskey"
  irb(main):017:2>     c.iv = "\x00\x00\x00\x00\x00\x00\x00\x00"
  irb(main):018:2>     c.update(data)
  irb(main):019:2>     c.final
  irb(main):020:2>     return true
  irb(main):021:2>   rescue OpenSSL::Cipher::CipherError
  irb(main):022:2>     return false
  irb(main):023:2>   end
  irb(main):024:1> end

As you can see, it returns true if we send C:

  irb(main):025:0> try_decrypt("\x83\xe1\x0d\x51\xe6\xd1\x22\xca\x3f\xaf\x08\x9c\x7a
  \x92\x4a\x7b")
  => true

And false if we flip the last bit of C (effectively changing the padding):

  irb(main):026:0> try_decrypt("\x83\xe1\x0d\x51\xe6\xd1\x22\xca\x3f\xaf\x08\x9c\x7a
   \x92\x4a\x7a")
  => false

Now we have our data, our encrypted data, and a simple oracle. Let's get to work!

Breaking the last character

Now, let's start with breaking the second block of ciphertext, C2. The first thing we do is create our own block of ciphertext — C′ — which has no particular plaintext value:

  C′ = "\x00\x00\x00\x00\x00\x00\x00\x00"

In reality, we can use any value, but all zeroes makes it easier to demonstrate. We concatenate C2 to that block, giving us:

  C′ || C2 = "\x00\x00\x00\x00\x00\x00\x00\x00\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"

We now have a two-block string of ciphertext. When you send that string to the oracle, the oracle will, following the cipher-block chaining standard: a) decrypt the second block, b) XOR the decrypted block with the ciphertext block that we control, and c) check the padding on the resulting block and fail if it's wrong. Read that sentence a couple times. If you need to know one thing to understand padding oracles, it's that.

Let me repeat and rephrase, to make sure it's clear: We send two blocks of ciphertext, one we control (C′) and one we want to decrypt (C2). The one we want to decrypt (C2) is decrypted (secretly) by the server, XORed with the block we control (C′), then the resulting plaintext's padding is validated. That means that we know whether or not our ciphertext XORed with their plaintext has proper padding. That gives us enough information to decrypt the entire string, one character after the other!

This will, of course, work for blocks other than C2 (which I notate as Cn in the previous blog). I'm using C2 because I'm working through a concrete example.

So, we generate that string (C′ || C2). We send that to our decryption oracle, and should return a false result (unless we hit the 1/256 chance of getting the padding right at random, which we don't):

  irb(main):027:0> try_decrypt("\x00\x00\x00\x00\x00\x00\x00\x00\x3f\xaf\x08\x9c
   \x7a\x92\x4a\x7b")
  => false

Now, keep in mind that this isn't decrypting to anything remotely useful! It's decrypting to a garbage string, and all that matters to us is whether or not the padding is correct, because that, thanks to a beautiful formula, tells us something about the plaintext.

Let's now focus on just the last character of C′. Before we get to the math, let's find the value for the last byte of C′ — C′[8] — that returns valid padding, using a simple ruby script:

  irb(main):067:0> 0.upto(255) do |i|
  irb(main):068:1*   cprime = "\x00\x00\x00\x00\x00\x00\x00#{i.chr}" + 
   "\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"
  irb(main):069:1>   puts("#{i}: #{cprime.unpack("H*")}: #{try_decrypt(cprime)}")
  irb(main):070:1> end
  0: 00000000000000003faf089c7a924a7b: false
  1: 00000000000000013faf089c7a924a7b: false
  2: 00000000000000023faf089c7a924a7b: false
  3: 00000000000000033faf089c7a924a7b: false
  4: 00000000000000043faf089c7a924a7b: false
  5: 00000000000000053faf089c7a924a7b: false
  6: 00000000000000063faf089c7a924a7b: false
  7: 00000000000000073faf089c7a924a7b: false
  ...
  203: 00000000000000cb3faf089c7a924a7b: false
  204: 00000000000000cc3faf089c7a924a7b: false
  205: 00000000000000cd3faf089c7a924a7b: false
  206: 00000000000000ce3faf089c7a924a7b: true   <--
  207: 00000000000000cf3faf089c7a924a7b: false
  208: 00000000000000d03faf089c7a924a7b: false
  ...

So what did we learn here? That when C′[8] is 206 — 0xce — it decrypts to something that ends with the byte "\x01". We can see what it's decrypting to by using some more ruby code (note that this isn't possible in a normal attack, since we don't have access to the key, this is simply used as a demonstration):

  irb(main):075:0> puts (c.update("\x00\x00\x00\x00\x00\x00\x00\xce\x3f\xaf\x08\x9c
  \x7a\x92\x4a\x7b") + c.final).unpack("H*")
  62047db89b8144b8f18d6954e3d427

Note that this string is 15 characters long, and doesn't end with \x01. Why? Because the "\x01" on the end was considered to be padding by the library and removed. OpenSSL doesn't return padding to the programmer — why would it?

We refer to this garbage string as P′, and it's not useful to us in any way, except for the padding byte that the server validates. In fact, since the server is decrypting the string secretly, we never even have access to P′.

(For what it's worth, P′ is actually equal to the original block of plaintext (P2) XORed with the previous block of ciphertext (C1) and XORed with our ciphertext block (C′). If you work through the math, you'll discover why).

The math

Recall from my previous blog that the second block of our new plaintext value — P′2 — is calculated like this:

  P′2 = D(C2) ⊕ C′

That is, the second block of P′ — our newly and secretly decrypted string — is equal to the second block of the ciphertext decrypted, then XORed with C′.

But C2 was originally calculated like this:

  C2 = E(P2 ⊕ C1)

In other words, the second block of ciphertext is the second block of plaintext XORed with the first block of ciphertext, then encrypted.

We can substitute C2 in the first formula with C2 in the second formula, which results in this:

  P′2 = D(E(P2 ⊕ C1)) ⊕ C′

So, the server calculates P2 XORed with C1, then encrypts it, decrypts it, and XORs it with C′. But the encryption and decryption cancel out (D(E(x)) = x, by definition), so we can reduce the formula to this:

  P′2 = P2 ⊕ C1 ⊕ C′

So P′2 — the value whose padding we're trying to discover — is the second block of plaintext XORed with the first block of ciphertext, XORed with our ciphertext (C′).

What do we know about P′2? Well, once we discover the proper padding value, the server knows that the value of P′2 is "\xf1\x8d\x69\x54\xe3\xd4\x27\x01". Unfortunately, all we know is that the padding is correct, and that P′2[8] = "\x01". But, since we know the value of P′2[8], we know enough to calculate P2[8]! Here's the calculation:

  P′2[8] = P2[8] ⊕ C1[8] ⊕ C′[8]
  (re-arrange using XOR's commutative property):
  P2[8] = P′2[8] ⊕ C1[8] ⊕ C′[8]
  P2[8] = 0x01 ⊕ 0xca ⊕ 0xce
  P2[8] = 5

Holy crap! 5 is the last byte of padding! We just broke the last byte of plaintext!

The value we know for P2 is "???????\x05"

Second-last byte...

Now, to calculate the second-last byte, we need a new P′. We want the last byte of P′ to decrypt to 0x02 (so that our padding will wind up as "\x02\x02" once we bruteforce the second-last byte), so we use this formula from earlier:

  P′2[k] = P2[k] ⊕ C1[k] ⊕ C′[k]

And re-arrange it:

  C′[k] = P′2[k] ⊕ P2[k] ⊕ C1[k]

Then plug in the values we determined for P2[8] ⊕ C1[8], and the value we desire for P′2[8]:

  C′[8] = P′2[8] ⊕ P2[8] ⊕ C1[8]
  C′[8] = 0x02 ⊕ 0x05 ⊕ 0xca
  C′[8] = 0xcd

Now we have the last character of C′: 0xcd. We use the same loop from earlier, except guessing C′[7] instead of C′[8]:

  irb(main):076:0> 0.upto(255) do |i|
  irb(main):077:1>   cprime = "\x00\x00\x00\x00\x00\x00#{i.chr}\xcd" + 
  "\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"
  irb(main):078:1>   puts("#{i}: #{cprime.unpack("H*")}: #{try_decrypt(cprime)}")
  irb(main):079:1> end
  ...
  36: 00000000000024cd3faf089c7a924a7b: false
  37: 00000000000025cd3faf089c7a924a7b: true
  38: 00000000000026cd3faf089c7a924a7b: false
  ...

All right, now we know that when C′[7] = 0x25, P′2[7] = 0x02! Plug that back into our formula:

  P2[7] = P′2[7] ⊕ C1[7] ⊕ C′[7]
  P2[7] = 0x02 ⊕ 0x22 ⊕ 0x25
  P2[7] = 5

Boom! Now we know that the second-last character of P2 is 5.

The value we know for P2 is "??????\x05\x05"

Third-last character

Let's keep going! First, we calculate C′[7] and C′[8] such that P′ will end with "\x03\x03":

  C′[k] = P′2[k] ⊕ P2[k] ⊕ C1[k]

  C′[8] = P′2[8] ⊕ P2[8] ⊕ C1[8]
  C′[8] = 0x03 ⊕ 0x05 ⊕ 0xca
  C′[8] = 0xcc

  C′[7] = P′2[7] ⊕ P2[7] ⊕ C1[7]
  C′[7] = 0x03 ⊕ 0x05 ⊕ 0x22
  C′[7] = 0x24

And run our program (modified a bit to just show us what's interesting):

  irb(main):088:0> 0.upto(255) do |i|
  irb(main):089:1>   cprime = "\x00\x00\x00\x00\x00#{i.chr}\x24\xcc" +
  "\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"
  irb(main):090:1>   puts("#{i}: #{cprime.unpack("H*")}") if(try_decrypt(cprime))
  irb(main):091:1> end
  215: 0000000000d724cc3faf089c7a924a7b

And back to our formula:

  P2[6] = P′2[6] ⊕ C1[6] ⊕ C′[6]
  P2[6] = 0x03 ⊕ 0xd1 ⊕ 0xd7
  P2[6] = 5

The value we know for P2 is "?????\x05\x05\x05"

Fourth-last character

Calculate the C′ values for \x04\x04\x04:

  C′[k] = P′2[k] ⊕ P2[k] ⊕ C1[k]

  C′[8] = P′2[8] ⊕ P2[8] ⊕ C1[8]
  C′[8] = 0x04 ⊕ 0x05 ⊕ 0xca
  C′[8] = 0xcb

  C′[7] = P′2[7] ⊕ P2[7] ⊕ C1[7]
  C′[7] = 0x04 ⊕ 0x05 ⊕ 0x22
  C′[7] = 0x23

  C′[6] = P′2[6] ⊕ P2[6] ⊕ C1[6]
  C′[6] = 0x04 ⊕ 0x05 ⊕ 0xd1
  C′[6] = 0xd0

And our program:

  irb(main):092:0> 0.upto(255) do |i|
  irb(main):093:1>   cprime = "\x00\x00\x00\x00#{i.chr}\xd0\x23\xcb" + 
  "\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"
  irb(main):094:1>   puts("#{i}: #{cprime.unpack("H*")}") if(try_decrypt(cprime))
  irb(main):095:1> end
  231: 00000000e7d023cb3faf089c7a924a7b

And breaking it:

  P2[5] = P′2[5] ⊕ C1[5] ⊕ C′[5]
  P2[5] = 0x04 ⊕ 0xe6 ⊕ 0xe7
  P2[5] = 5

The value we know for P2 is "????\x05\x05\x05\x05"

Fifth-last character

Time for the last padding character! Calculate C′ values for \x05\x05\x05\x05:

  C′[k] = P′2[k] ⊕ P2[k] ⊕ C1[k]

  C′[8] = P′2[8] ⊕ P2[8] ⊕ C1[8]
  C′[8] = 0x05 ⊕ 0x05 ⊕ 0xca
  C′[8] = 0xca

  C′[7] = P′2[7] ⊕ P2[7] ⊕ C1[7]
  C′[7] = 0x05 ⊕ 0x05 ⊕ 0x22
  C′[7] = 0x22

  C′[6] = P′2[6] ⊕ P2[6] ⊕ C1[6]
  C′[6] = 0x05 ⊕ 0x05 ⊕ 0xd1
  C′[6] = 0xd1

  C′[5] = P′2[5] ⊕ P2[5] ⊕ C1[5]
  C′[5] = 0x05 ⊕ 0x05 ⊕ 0xe6
  C′[5] = 0xe6

Run the program:

  irb(main):096:0> 0.upto(255) do |i|
  irb(main):097:1*   cprime = "\x00\x00\x00#{i.chr}\xe6\xd1\x22\xca" + 
 "\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"
  irb(main):098:1>   puts("#{i}: #{cprime.unpack("H*")}") if(try_decrypt(cprime))
  irb(main):099:1> end
  81: 00000051e6d122ca3faf089c7a924a7b

And break the character:

  P2[4] = P′2[4] ⊕ C1[4] ⊕ C′[4]
  P2[4] = 0x05 ⊕ 0x51 ⊕ 0x51
  P2[4] = 5

The value we know for P2 is "???\x05\x05\x05\x05\x05"

Sixth-last character

Only three to go! Calculate C′ for \x06\x06\x06\x06\x06:

  C′[k] = P′2[k] ⊕ P2[k] ⊕ C1[k]

  C′[8] = P′2[8] ⊕ P2[8] ⊕ C1[8]
  C′[8] = 0x06 ⊕ 0x05 ⊕ 0xca
  C′[8] = 0xc9

  C′[7] = P′2[7] ⊕ P2[7] ⊕ C1[7]
  C′[7] = 0x06 ⊕ 0x05 ⊕ 0x22
  C′[7] = 0x21

  C′[6] = P′2[6] ⊕ P2[6] ⊕ C1[6]
  C′[6] = 0x06 ⊕ 0x05 ⊕ 0xd1
  C′[6] = 0xd2

  C′[5] = P′2[5] ⊕ P2[5] ⊕ C1[5]
  C′[5] = 0x06 ⊕ 0x05 ⊕ 0xe6
  C′[5] = 0xe5

  C′[4] = P′2[4] ⊕ P2[4] ⊕ C1[4]
  C′[4] = 0x06 ⊕ 0x05 ⊕ 0x51
  C′[4] = 0x52

Run the program:

  irb(main):100:0> 0.upto(255) do |i|
  irb(main):101:1*   cprime = "\x00\x00#{i.chr}\x52\xe5\xd2\x21\xc9" + 
  "\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"
  irb(main):102:1>   puts("#{i}: #{cprime.unpack("H*")}") if(try_decrypt(cprime))
  irb(main):103:1> end
  111: 00006f52e5d221c93faf089c7a924a7b

Break the character:

  P2[3] = P′2[3] ⊕ C1[3] ⊕ C′[3]
  P2[3] = 0x06 ⊕ 0x0d ⊕ 0x6f
  P2[3] = 0x64 = "d"

The value we know for P2 is "??d\x05\x05\x05\x05\x05"

Two left!

Only two left! Time to calculate C′ for "\x07\x07\x07\x07\x07\x07":

  C′[k] = P′2[k] ⊕ P2[k] ⊕ C1[k]

  C′[8] = P′2[8] ⊕ P2[8] ⊕ C1[8]
  C′[8] = 0x07 ⊕ 0x05 ⊕ 0xca
  C′[8] = 0xc9

  C′[7] = P′2[7] ⊕ P2[7] ⊕ C1[7]
  C′[7] = 0x07 ⊕ 0x05 ⊕ 0x22
  C′[7] = 0x21

  C′[6] = P′2[6] ⊕ P2[6] ⊕ C1[6]
  C′[6] = 0x07 ⊕ 0x05 ⊕ 0xd1
  C′[6] = 0xd2

  C′[5] = P′2[5] ⊕ P2[5] ⊕ C1[5]
  C′[5] = 0x07 ⊕ 0x05 ⊕ 0xe6
  C′[5] = 0xe5

  C′[4] = P′2[4] ⊕ P2[4] ⊕ C1[4]
  C′[4] = 0x07 ⊕ 0x05 ⊕ 0x51
  C′[4] = 0x52

  C′[3] = P′2[3] ⊕ P2[3] ⊕ C1[3]
  C′[3] = 0x07 ⊕ 0x64 ⊕ 0x0d
  C′[3] = 0x52

The program:

  irb(main):104:0> 0.upto(255) do |i|
  irb(main):105:1*   cprime = "\x00#{i.chr}\x6e\x53\xe4\xd3\x20\xc8" + 
  "\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"
  irb(main):106:1>   puts("#{i}: #{cprime.unpack("H*")}") if(try_decrypt(cprime))
  irb(main):107:1> end
  138: 008a6e53e4d320c83faf089c7a924a7b

The calculation:

  P2[2] = P′2[2] ⊕ C1[2] ⊕ C′[2]
  P2[2] = 0x07 ⊕ 0xe1 ⊕ 0x8a
  P2[2] = 0x6c = "l"

The value we know for P2 is "?ld\x05\x05\x05\x05\x05"

Last block!

For the last block — and the last time I ever do a padding oracle calculation by hand — we calculate C′ for "\x08\x08\x08\x08\x08\x08\x08":

  C′[k] = P′2[k] ⊕ P2[k] ⊕ C1[k]

  C′[8] = P′2[8] ⊕ P2[8] ⊕ C1[8]
  C′[8] = 0x08 ⊕ 0x05 ⊕ 0xca
  C′[8] = 0xc7

  C′[7] = P′2[7] ⊕ P2[7] ⊕ C1[7]
  C′[7] = 0x08 ⊕ 0x05 ⊕ 0x22
  C′[7] = 0x2f

  C′[6] = P′2[6] ⊕ P2[6] ⊕ C1[6]
  C′[6] = 0x08 ⊕ 0x05 ⊕ 0xd1
  C′[6] = 0xdc

  C′[5] = P′2[5] ⊕ P2[5] ⊕ C1[5]
  C′[5] = 0x08 ⊕ 0x05 ⊕ 0xe6
  C′[5] = 0xeb

  C′[4] = P′2[4] ⊕ P2[4] ⊕ C1[4]
  C′[4] = 0x08 ⊕ 0x05 ⊕ 0x51
  C′[4] = 0x5c

  C′[3] = P′2[3] ⊕ P2[3] ⊕ C1[3]
  C′[3] = 0x08 ⊕ 0x64 ⊕ 0x0d
  C′[3] = 0x61

  C′[2] = P′2[2] ⊕ P2[2] ⊕ C1[2]
  C′[2] = 0x08 ⊕ 0x6c ⊕ 0xe1
  C′[2] = 0x85

Then the program:

  irb(main):112:0> 0.upto(255) do |i|
  irb(main):113:1*   cprime = "#{i.chr}\x85\x61\x5c\xeb\xdc\x2f\xc7" + 
  "\x3f\xaf\x08\x9c\x7a\x92\x4a\x7b"
  irb(main):114:1>   puts("#{i}: #{cprime.unpack("H*")}") if(try_decrypt(cprime))
  irb(main):115:1> end
  249: f985615cebdc2fc73faf089c7a924a7b

And, finally, we calculate the character one last time:

  P2[1] = P′2[1] ⊕ C1[1] ⊕ C′[1]
  P2[1] = 0x08 ⊕ 0x83 ⊕ 0xf9
  P2[1] = 0x72 = "r"

The value we know for P2 is "rld\x05\x05\x05\x05\x05"

Conclusion

So, you've seen the math behind how we can decrypt a full block of a CBC cipher (specifically, DES) using only a padding oracle. The previous block would be decrypted the exact same way, and would wind up as "Hello Wo".

Hopefully this demonstration will help you understand what's going on! Padding oracles, once you really understand them, are one of the simplest vulnerabilities to exploit!

5 thoughts on “A padding oracle example

  1. Reply

    Spades

    Great explanation.

    Just a suggestion: I think you should make the link(s) to your extremely helpful Wiki more prominent somewhere on this blog. Maybe in its own widget or a link at the top or something.

  2. Reply

    bitwize

    That was an awesome explanation of a padding oracle attack. One thing to note is though, after decrypting the last byte of the ciphertext, you could have eliminated some work since you know that, due to the padding scheme, the last 5 bytes will all be 0x05.

  3. Reply

    oplbhw

    http://www.hack-ware.com/content/padding-oracle-exploit-tool-vs-apache-myfaces

  4. Reply

    Marc G

    Well, I'm missing something. I read thru this one and the detailed, more theoretical blog posts and am confused in the backtracking area.

    I understand all the math and the working backwards to "decrypt" the message. The only thing I'm confused about is how in this post it says that you know you got 0x01. While it can be confirmed after subsequent tests that all align as expected, are we just guessing it is 0x01 at that point or do we know for sure?

    If we know for sure; how? This is the only point I'm not getting it seems like. How do we know its not 0x02 or 3 or 4? At least not with additional requests to verify.

  5. Reply

    kaw

    Thanks for the nice example.

    In the "Two left!" section the numbers of the calculation are all wrong, aren't they? Seems like a cut&paste error from the previous section.

    (Also, the comment spam protection seems to be partially broken.)

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>