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!
Comments
Join the conversation on this Mastodon post (replies will appear below)!
Loading comments...