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′ — 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′ 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 = "\x01". But, since we know the value of P′2, we know enough to calculate P2! Here's the calculation:

```  P′2 = P2 ⊕ C1 ⊕ C′
(re-arrange using XOR's commutative property):
P2 = P′2 ⊕ C1 ⊕ C′
P2 = 0x01 ⊕ 0xca ⊕ 0xce
P2 = 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 ⊕ C1, and the value we desire for P′2:

```  C′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x02 ⊕ 0x05 ⊕ 0xca
C′ = 0xcd
```

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

```  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′ = 0x25, P′2 = 0x02! Plug that back into our formula:

```  P2 = P′2 ⊕ C1 ⊕ C′
P2 = 0x02 ⊕ 0x22 ⊕ 0x25
P2 = 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′ and C′ such that P′ will end with "\x03\x03":

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

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

C′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x03 ⊕ 0x05 ⊕ 0x22
C′ = 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 = P′2 ⊕ C1 ⊕ C′
P2 = 0x03 ⊕ 0xd1 ⊕ 0xd7
P2 = 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′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x04 ⊕ 0x05 ⊕ 0xca
C′ = 0xcb

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

C′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x04 ⊕ 0x05 ⊕ 0xd1
C′ = 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 = P′2 ⊕ C1 ⊕ C′
P2 = 0x04 ⊕ 0xe6 ⊕ 0xe7
P2 = 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′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x05 ⊕ 0x05 ⊕ 0xca
C′ = 0xca

C′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x05 ⊕ 0x05 ⊕ 0x22
C′ = 0x22

C′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x05 ⊕ 0x05 ⊕ 0xd1
C′ = 0xd1

C′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x05 ⊕ 0x05 ⊕ 0xe6
C′ = 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 = P′2 ⊕ C1 ⊕ C′
P2 = 0x05 ⊕ 0x51 ⊕ 0x51
P2 = 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′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x06 ⊕ 0x05 ⊕ 0xca
C′ = 0xc9

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

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

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

C′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x06 ⊕ 0x05 ⊕ 0x51
C′ = 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 = P′2 ⊕ C1 ⊕ C′
P2 = 0x06 ⊕ 0x0d ⊕ 0x6f
P2 = 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′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x07 ⊕ 0x05 ⊕ 0xca
C′ = 0xc9

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

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

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

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

C′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x07 ⊕ 0x64 ⊕ 0x0d
C′ = 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 = P′2 ⊕ C1 ⊕ C′
P2 = 0x07 ⊕ 0xe1 ⊕ 0x8a
P2 = 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′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x08 ⊕ 0x05 ⊕ 0xca
C′ = 0xc7

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

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

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

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

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

C′ = P′2 ⊕ P2 ⊕ C1
C′ = 0x08 ⊕ 0x6c ⊕ 0xe1
C′ = 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 = P′2 ⊕ C1 ⊕ C′
P2 = 0x08 ⊕ 0x83 ⊕ 0xf9
P2 = 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!

## 8 thoughts on “A padding oracle example”

1. 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. 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. oplbhw

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

1. Alex

You're right,
When you have the first correct guess (by running the last byte from 0 to FF while keeping the rest unchanged), it could be either
0x01 or
0x02 0x02 or
0x03 0x03 0x03,
etc.
You get my gist.
The only way to confirm that it is indeed 0x01 is by changing the next to last byte - if the guess is still correct then we indeed got 0x01, otherwice the padding is wrong and we need to continue changthing the first byte until we got the correct value.
However getting 0x02 0x02 is unlikely, getting 0x03 0x03 0x03 is even more unlikely, so assuming that it is 0x01 will be almost always right.

1. Michal

You are guaranteed to hit 0x01 with one of the values of C'. If only one value works, you know that it is correct.

If your padding is 0x02 0x02 (or 0x03 0x03 0x03 ...), then you will get two possible values of C'. You can just increment C' until you get only one hit.

5. 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.)

6. Michael

Howdy all,

I followed this article and wrote a simple implementation in PHP. It works but I'm somewhat stuck after the first block has been decrypted. Code is on github, any pointers would be greatly appreciated...

https://github.com/mmeyer2k/phporacle