Breaking computers: Padding Oracle Attack

Attacking modern cyrptography

Watch the animated video here: Animated Explanation

Encryption lets you convert a message into a cipher using a key
so that only someone with the same key can convert it back

even the smallest change in input massively changes the output cipher 




and thanks to maths it's unbreakable (for now... maybe *cough cough* NSA)



but you are limited to how much you can encrypt, usually only 8 or 16 bytes at a time
which means it needs to be used as part of a larger system

system

ˈsɪstəm/

noun

1. 1.

   a set of things working together as parts of a mechanism or an interconnecting network; a complex whole.

   "the state railway system"

   synonyms:

   structure, organization, order, arrangement, complex, apparatus,network; More

which by definition makes it more complex, and unfortunately, all it takes is a tiny leak to completely destroy a crypto system

What if we encode each block separately?

This is equivalent to encoding every letter in a sentence
Guvf vf rdhvinyrag gb rapbqvat rirel yrggre va n fragrapr

Or every pixel in an image

Cipher block chaining

where ECB is glorified rot13
CBC is a glorified enigma machine

The idea is simple, mix the output with more input to create more randomness in the result

Less fuzzy penguins but more complexity

it's used everywhere, especially places it shouldn't be

encrypt the first block 
xor that with the next block and encrypt that
xor that with the next block and encrypt that



where xor just means magic computer addition (google it)

to decrypt, just do every step in reverse

notice that when we encrypt we have to go one after another
so that every input block will impact the rest of the cipher

but when we decrypt we can do the whole thing in parallel

how much of the cipher text do you need to recover any given block of input?

ideally, if you changed any of the cipher, the entire decryption should be broken

but!
turns out each plaintext block is only dependant on 2 cipher blocks

so what happens if we start changing some of the cipher blocks?

Incrementing the last digit of the middle cipher block only ruins the previous block's decryption

remember how xor is just very-simple-computer-addition 
this means we can very precisely change part of the decryption

and the previous block is the only thing that gets completely ruined

which you can abuse in certain situations to have no effect anyway

is this algorithm totally broken?
is everything insecure?

yeah kinda,

Demo Time

say this was being used on a website, where you want to save someone's login details in a cookie so that they don't have to log in constantly (hint, this is a BAD IDEA)

but you don't want them changing things like their permissions
so you encrypt it with a key that's only on the server on the other side of the internet (seems legit, right?)

something like this
{
"name" : "mr joe",
"thought of the day" : "cyber cyber cyber cyber cyber",
"admin" : 0 
}


think about how the last couple of blocks will be encrypted

[yber cyber cyber] [","admin" : 0 ]

if we flip the bit corresponding to the admin flag then the previous block will be ruined but it doesn't really matter.

{
"name" : "mr joe",
"thought of the day" : "cyber cyber c????????????????",
"admin" : 1 
}

hahah!
mr joe was able to adjust his 'thought of the day' so that when the admin bit was flipped it had no impact on how the data would be used.

Even without any technical faults, we can already do a lot of damage

lets have a look at just how devastating it can get if you have even the tiniest leak

Padding Oracle Time

When you encrypt a block it has to fit the block size, and if it's too small you need to pad it out
and you need to be able to remove the padding once you decode the message

the standard way is to use the amount you need to pad as the padding.


if a service gives you an error when it recieves an incorrectly padded message, it's game over for the service. 
We can now encrypt and decrypt anything without ever knowing the key.

To decode the message block D7FF we cycle through all the values of the last digit in the previous block until we get a valid padding

which we know must be ???1 becasue it was padded correctly

Side Note:

It could also have been a 2 if the second last digit was a 2, or 33, 444 etc. Just starting again with a different second digit

End Side Note 

We can xor that with the digit we used in the cipher, to work out the last digit of the intermediate block. 

Using that we can get a 2 in the last position of the decrypted block and now we can find the next digit


Using that, we can get 3's in the last 2 positions of the decrypted block and now we can find the second digit

Using that, we can get 4's in the last 3 positions of the decrypted block and now we can find the first digit









Then we know the entire intermediate block pre encryption
so all we have to do is xor it with the original cipher block
and we'll have decoded that block of cipher text.