CS2107 Padding Oracle Attack

Summary

This video script offers an in-depth exploration of the padding oracle attack, a complex cryptographic exploit. It breaks down the attack into its core components: the XOR operation, block ciphers in CBC mode, padding standards like PKCS#7, and the oracle mechanism. The script explains how attackers can exploit the oracle's feedback to decrypt ciphertext and recover plaintext, despite not knowing the encryption key. The tutorial uses clear examples and diagrams to illustrate the step-by-step process of the attack, emphasizing the significance of understanding each component's role in the exploit.

Takeaways

• 🔐 The padding oracle attack allows an attacker to retrieve the original plaintext from ciphertext without knowing the encryption key.
• 🧩 The attack involves understanding the XOR operation, which is fundamental to how block ciphers function, especially in CBC mode.
• 🔄 The XOR operation's property where knowing any two of three involved entities (two operands and the result) can reveal the third is crucial for the attack.
• 🗜️ Block ciphers in CBC mode decrypt data by XORing the decrypted block with the previous ciphertext block to get the plaintext block.
• 📐 Padding standards like PKCS#7 are necessary when the input data size isn't a multiple of the block size, ensuring complete blocks for encryption.
• 👁️‍🗨️ The padding oracle is a component that checks if the decrypted plaintext has valid padding, without revealing sensitive decryption details.
• 🔄 The attack manipulates the ciphertext input to the padding oracle to gradually determine the plaintext byte by byte through XOR operations.
• 🔍 An exhaustive search is used to find the correct ciphertext block values that will result in valid padding when decrypted.
• 🔄 By keeping one ciphertext block constant and altering the previous one, attackers can isolate and determine the plaintext bytes step by step.
• ⚠️ The attack highlights the risks of disclosing whether padding is valid, as this information can be exploited to reconstruct the plaintext.

Q & A

What is a padding oracle attack?

A padding oracle attack is a form of cryptographic attack that allows an attacker to retrieve the original plaintext from a ciphertext by exploiting the way a system handles decryption and padding errors.

Why is the XOR operation significant in the context of a padding oracle attack?

The XOR operation is significant because it is a bitwise operation that is used both in the decryption process and in manipulating ciphertext to influence the decrypted plaintext. Its properties allow attackers to determine unknown values by comparing known outputs.

How does the block cipher decryption process work in CBC mode?

In CBC (Cipher Block Chaining) mode, each decrypted ciphertext block is XORed with the previous ciphertext block to retrieve the plaintext block. This process is repeated for each block to reconstruct the original plaintext.

What is the role of the padding standard in a padding oracle attack?

The padding standard, such as PKCS#7, defines how padding is added to plaintext that is not an exact multiple of the block size. In a padding oracle attack, the attacker manipulates the ciphertext to determine the padding and, consequently, the plaintext.

What does the padding oracle do in the context of an attack?

The padding oracle is a component that checks if the decrypted plaintext has valid padding according to the padding standard. It responds with a 'yes' or 'no' without revealing the actual plaintext or the decryption key.

How does an attacker use the responses from the padding oracle?

An attacker uses the 'yes' or 'no' responses from the padding oracle to iteratively determine the bytes of the plaintext by manipulating the ciphertext and observing whether the decrypted padding is valid.

What is the purpose of the exhaustive search method mentioned in the script?

The exhaustive search method is used by the attacker to try all possible byte values (0 to 255) to find the correct value that will cause the padding oracle to respond with 'yes,' indicating valid padding and allowing the recovery of a byte of the plaintext.

How does the attacker manipulate the ciphertext to affect the decrypted plaintext?

The attacker manipulates the ciphertext by changing specific bytes while keeping others constant, aiming to create a desired valid padding pattern in the decrypted plaintext that will be reflected in the padding oracle's response.

What is the significance of the deterministic nature of the block cipher decryption algorithm in a padding oracle attack?

The deterministic nature of the block cipher decryption algorithm ensures that the same ciphertext input will always produce the same intermediate state, allowing the attacker to make precise manipulations and predictions about the plaintext.

How does the attacker move from finding the last byte of plaintext to the second last byte in the attack?

After finding the last byte of plaintext, the attacker modifies the ciphertext to target the second last byte of the plaintext, using the knowledge of the previous plaintext byte and the properties of the XOR operation to iteratively uncover more of the plaintext.

Outlines

00:00

🔐 Introduction to Padding Oracle Attack

The paragraph introduces the concept of the padding oracle attack, a method used by attackers to retrieve the original plaintext from ciphertext. It emphasizes the complexity of the attack due to the multiple components involved and the XOR operations used. The video aims to simplify the understanding of the attack mechanics. The attack is set within a specific context involving four main parts: the XOR operation, a block cipher using Cipher Block Chaining (CBC) mode, the padding standard, and an oracle. The paragraph discusses the XOR operation in detail, explaining its bit-by-bit nature and its property of being reversible when any two of the three involved entities (two operands and one result) are known.

05:00

🔑 Block Cipher and CBC Mode

This section delves into the workings of block ciphers, particularly focusing on the decryption process. It explains how block ciphers process ciphertext in fixed-size blocks and how decryption is performed. The paragraph introduces Cipher Block Chaining (CBC) mode, where each decrypted block is XORed with the previous ciphertext block to obtain the plaintext. The paragraph uses a diagram to illustrate the decryption process in CBC mode, highlighting how the process is repeated for each block. It also touches on the necessity of padding when the input size is not a multiple of the block size, setting the stage for the padding standard discussion in the next paragraph.

10:02

🔠 Padding Standard and Oracle

The paragraph discusses the padding standard, specifically PKCS#7, which is used to handle scenarios where the plaintext does not fill an entire block. It explains how padding is added to complete the last block according to a specific pattern. The paragraph then introduces the concept of an oracle, which is a mechanism that can answer whether the decrypted plaintext has valid padding without revealing sensitive information. The padding oracle is highlighted as a key component of the attack, as it performs decryption and can be manipulated by the attacker to extract information about the plaintext.

15:04

🕵️‍♂️ Padding Oracle Attack Process

This paragraph explains the process of the padding oracle attack, focusing on how an attacker can manipulate the ciphertext to learn about the plaintext. It details the attacker's strategy of changing the ciphertext in a way that the padding oracle responds positively, indicating valid padding. The paragraph describes how the attacker can iteratively determine the plaintext byte by byte by forcing the decrypted plaintext to have a desired valid padding. It outlines the steps involved in the attack, including the use of XOR operations to deduce the original plaintext from the ciphertext. The paragraph concludes by emphasizing the significance of the padding oracle's role in the attack and the information it inadvertently reveals.

Keywords

💡Padding Oracle Attack

The Padding Oracle Attack is a cryptographic attack that exploits the way a system handles errors in the padding of a block cipher. In the context of the video, this attack allows an attacker to decrypt a ciphertext without knowing the encryption key by observing the system's response to incorrect padding. The video emphasizes that this attack is particularly dangerous because it can reveal the original plaintext from just the ciphertext alone, given the right conditions and an 'oracle' that can be queried about the validity of the padding.

💡XOR Operation

The XOR (Exclusive OR) operation is a binary operation that takes two binary inputs and returns true if exactly one of the inputs is true. In the video, XOR is crucial for understanding the mechanics of the Padding Oracle Attack because it is used in the decryption process of block ciphers. The video explains that XOR operations are done bit by bit, affecting only the specific byte being manipulated, which is key to the attack's methodology.

💡Block Cipher

A block cipher is a symmetric key cipher that encrypts plaintext in blocks, typically 64 or 128 bits long. The video discusses how block ciphers operate, particularly in Cipher Block Chaining (CBC) mode, where each block of ciphertext is XORed with the previous block before decryption. The Padding Oracle Attack relies on the deterministic nature of the block cipher's decryption process to infer information about the plaintext.

💡Cipher Block Chaining (CBC) Mode

CBC mode is a mode of operation for block ciphers that uses an initialization vector (IV) and the previous ciphertext block to encrypt the current plaintext block. In the video, the decryption process in CBC mode is highlighted, where the decrypted ciphertext block is XORed with the previous ciphertext block to obtain the plaintext. This process is integral to the Padding Oracle Attack, as it allows the attacker to manipulate the plaintext by altering the ciphertext.

💡Padding Standard

Padding standards are used to fill the last block of plaintext with additional bytes to match the block size required by the block cipher. The video specifically mentions PKCS#7, a padding scheme where the padding bytes indicate the number of padding bytes added. The Padding Oracle Attack exploits the knowledge of the padding scheme to guess the plaintext byte by byte.

💡Oracle

In the context of the Padding Oracle Attack, an 'oracle' is a component of the system that can be queried to check if the decrypted plaintext has valid padding. The video explains that the oracle does not reveal any sensitive information like the encryption key but provides a 'yes' or 'no' response based on the validity of the padding. This binary response is the key to the attack, as it allows the attacker to iteratively guess the plaintext.

💡Deterministic Algorithm

A deterministic algorithm is one that, given the same input, will always produce the same output. The video points out that the block cipher decryption algorithm is deterministic, which is a critical property exploited in the Padding Oracle Attack. If the ciphertext (input) remains unchanged, the intermediate state produced by the decryption algorithm will also remain the same, allowing the attacker to make educated guesses about the plaintext.

💡Exhaustive Search

Exhaustive search, as mentioned in the video, is a method where all possible values are tried until the correct one is found. In the context of the Padding Oracle Attack, the attacker uses exhaustive search to determine the correct byte values in the ciphertext that will result in valid padding when decrypted. The video illustrates how this is done by changing one byte at a time and querying the oracle.

💡Valid Padding

Valid padding refers to the correct application of a padding scheme to the plaintext before encryption. In the video, the concept of valid padding is central to the Padding Oracle Attack. The attacker aims to manipulate the ciphertext in such a way that when decrypted, the plaintext appears to have valid padding according to the padding standard, which signals to the attacker that they have guessed a correct plaintext byte.

💡Man-in-the-Middle (MitM)

Although not explicitly mentioned in the provided transcript, the concept of a Man-in-the-Middle attack is related to the Padding Oracle Attack in that both involve an attacker intercepting and manipulating data. In a MitM attack, the attacker sits between the sender and receiver, potentially altering messages. The Padding Oracle Attack could be seen as a form of MitM where the attacker manipulates the ciphertext to interact with the decryption system and extract information.

Highlights

Padding oracle attack allows an attacker to retrieve the original plaintext from just the ciphertext.

The attack involves understanding the XOR operation, block cipher, padding standard, and an oracle.

XOR operations are bit-wise and can be used to manipulate specific bytes without affecting others.

The XOR operation has a unique property where any two of three entities can be used to retrieve the third.

Block ciphers decrypt ciphertext in blocks, using a fixed-size algorithm.

In CBC mode, the decrypted ciphertext block is XORed with the previous ciphertext block to retrieve plaintext.

Padding standards like PKCS#7 are used to handle inputs that aren't a multiple of the block size.

The padding oracle is a mechanism that checks if the decrypted plaintext has valid padding.

The padding oracle performs decryption but only reveals whether the padding is valid, not the key or algorithm.

The attack process involves manipulating the ciphertext to force the plaintext to have a desired valid padding.

By keeping one ciphertext block unchanged and manipulating another, attackers can deduce the plaintext byte by byte.

The attack leverages the deterministic nature of the block cipher decryption algorithm.

An exhaustive search is used to find the value of a byte that makes the plaintext padding valid.

The attack methodically works from the last byte of the plaintext to the first, using the padding oracle's feedback.

The padding oracle attack illustrates how revealing padding validity can inadvertently leak information.

The video aims to provide an intuitive understanding of the padding oracle attack's mechanics.

Transcripts

hey everyone in cs 107 one of the more

interesting attacks covered is the

padding oracle attack it's not

particularly easy to wrap your head

around the attack at first simply

because there are quite a few moving

parts and the xor operations involved

don't exactly lend themselves to quick

and easy interpretation this video aims

to provide an intuitive understanding

and explanation for the mechanics behind

the attack the padding oracle attack

really isn't that unapproachable once

you break it down the first part of this

video will be dealing with the context

and setup of the attack while the second

half will delve into the mechanics

behind the attack now let's begin what

exactly is the padding oracle attack

well it provides a way for an attacker

to retrieve the original plaintext from

just the ciphertext alone but this is a

rather generic definition a lot of

attacks aim to do this instead what

really defines a padding oracle attack

is the context in which it is set up and

there are four main parts in this

context the xor operation a block cipher

using cipher block training or cbc mode

the padding standard and as well and

last but not least an oracle

let's go through each of these parts in

turn firstly the xor operation now i'm

sure most of you will be familiar with

the xo operation it's a very simple bit

operation that computers do all the time

i provided the xor table in the top

right hand corner over here for your

reference but there are two things about

the xor operation that are pertinent to

our discussion today the first is the

fact that xor operations are done bit by

bit by by what i mean by this is that if

you xor two sequences of bytes as shown

in this diagram over here the output

obtained is determined by comparing the

bytes in each lane

now this might seem like a very obvious

thing in the most of you but the point

i'm driving towards is the fact that if

i change one of the operand bytes say

the one right over here

only the bytes in this particular lane

will be affected

all the other lanes remain unaffected so

this means that when we want to

manipulate bytes in an xor operation we

only need to focus our attention on the

particular lane of interest

the xor operation also has another

peculiar property well firstly it's a

binary operation so it takes two

operands and returns one result so let's

say we have a xo of b giving us c that's

a total of two plus one equals three

entities involved correct well the thing

about the xo operation is that if you

take any two of these three entities and

you xor them you'll always get back the

third entity if you don't believe me you

can try it out for yourself

in this case we can take b x or to c to

give us back a we can also take a x or c

to give us back b this peculiar property

of the xor operation is repeatedly used

when we understand when we try to

understand and analyze the padding

oracle attack

next up we have the block cipher let's

focus on how block ciphers perform

decryption the encryption process is

just the reverse of the decryption

process so i won't be spending much time

on that

block ciphers take a ciphertext as input

and it will break up this input into

blocks of a certain fixed size in my

diagram over here i broke up the

ciphertext into eight byte blocks where

each of these little squares over here

represents one byte

then the block cipher proceeds to run a

decryption algorithm on each of these

blocks

the output plain text blocks can then be

concatenated to retrieve the original

plaintext now block ciphers have

different modes of operation

one mode of operation that we're

interested in is the cvc mode or cipher

block chaining mode

during the decryption process in cbc

mode the decrypted cipher text block

will also be xor with the previous

ciphertext block in order to retrieve

the plaintext block now this is quite a

mouthful so i personally prefer to just

trace through the diagram it's quite

easy to understand such diagrams if you

interpret all of these arrows it's kind

of like pipes for which all of these

bytes can flow through if we focus our

attention on ciphertext block number two

over here which i've drawn to be eight

bytes long and i'm representing it in

red

it will first be put through the block

cipher decryption algorithm let's treat

this algorithm as a black box the actual

algorithm and the implementation of it

does not matter do not matter for the

purposes of our discussion

after putting it through the

this particular black box we get an

output of eight bytes as well

note that this output will almost

certainly be different from the initial

ciphertext plot so i've drawn them in

different colors in this case blue

then we'll be taking the previous

ciphertext block the one illustrated in

green over here and we'll be performing

an xor operation giving us the plain

text block drawn here in yellow

now the same decryption process is

repeated for each and every single

ciphertext block so when we perform an

analysis we can simply focus our

attention to just this portion over here

because this entire portion is simply

repeated again and again and again for

all of the remaining blocks

next up we have the padding standard

since we're using a block cipher what

happens when our input can be nicely cut

out into these same size blocks in other

words what happens when our input size

isn't an integer multiple of the block

size such as this case here where we

only have six bytes in the last portion

which isn't enough to make an eight byte

block

the solution is very simple we can

simply add bytes at the end padding it

until we have enough bytes to form a

full block in this case we'll just be

adding two bytes but the question

remains what should these two added

bytes be we can't possibly fill them up

with random bytes right this is where

the padding standard comes in and there

are many different padding standards out

in existence but we'll focus on pkcs

number seven and the idea behind pkcs

number seven is actually very simple if

you have to pack one byte you'll pair it

with zero one if you have to pad two

bytes you pair it with zero two zero two

if you had the pad three bytes you

paired it with 030303

and so on i hope you get the idea

if the last block is full meaning it has

in our case a full 8 bytes then we have

to add an extra block of all zeros

finally we come to the last part of the

context the padding oracle now this is

the most interesting mechanism involved

but actually an oracle is very very

simple it's just a black box that

answers a certain question you give it

some input and

then oracle will answer yes or no

depending on the question that it's

designed to answer

in our case we're going to use a padding

oracle where we give the oracle some

ciphertext input and it will answer the

question on whether or not the decrypted

plain text has valid padding according

to the padding standard adopted in our

case we'll be using pkcs number seven as

was mentioned two slides ago

note this means that the padding oracle

actually performs decryption so it will

know the secret key and which encryption

algorithm to use it's just that it

doesn't reveal this key or anything else

that is sensitive it only reveals

whether or not the decrypted plain text

has valid padding nevertheless it is

important to recognize that a padding

oracle itself is capable of and will

perform decryption of the input cipher

text

so after all of this we now have a good

understanding of the context of the

attack but how does the attack actually

happen

let's focus our attention to a single

unit of the decryption process we've

seen this diagram before but let's first

agree on some notation

we want to obtain the plain text

corresponding to this ciphertext block

let's call this c2

c2 will be put through the block cipher

decryption algorithm generating some

kind of output let's call this output at

intermediate state and label it i2

we need the previous ciphertext block as

well let's call this c1 now c1 will be

x1 with i2 to give us the plain text

block let's call that p2

now for a very important fact

since this block cipher is a

deterministic algorithm

if we do not change c2

this means that i2 will also remain the

same

in other words if we keep c2 we don't

ever change it that means i2 will also

be the same

since we have the notation nailed down

now let's move forward and try to think

like an attacker the intuition behind

the panic oracle attack is reviewed when

you ask yourself a couple of questions

and make a couple of observations

firstly a yes from the panic oracle is

more helpful than a note because we

actually know the format of the last few

bytes of the plain text if it has a

valid padding it could be 0 1 it could

be 0 2 0 2 or it could be 0 3 0 3 03 etc

we still have a couple of options but

it's a very limited subset if it's a no

those last few bytes could literally be

anything else

next as an attacker we already have our

hands on the ciphertext plots we can

also control what ciphertext is provided

as input to the padding oracle

most importantly we can change what

ciphertext we input to the padding

oracle

lastly by changing this ciphertext input

we can also change the decrypted

plaintext that the patent oracle seeds

so here's the key insight we need to try

and introduce some kind of change so

that the padding oracle tells us the

decrypted plaintext has valid padding in

other words we can try to force the

plaintext decrypted by the parent oracle

to have some kind of desired valid

padding by manipulating the ciphertext

we provide as input to the padding

oracle

before we continue i want to emphasize

that we are dealing with two distinct

scenarios here the first is our original

decryption scenario over here we're

dealing with the original ciphertext

blocks and we never introduced any

changes but the thing is we're stuck

because we don't know the key for the

cipher text but for the block cipher

decryption algorithm over here so we

can't find the plain text

the second scenario we're dealing with

is the padding oracle scenario which as

we've mentioned a couple of slides ago

is fully capable of performing

decryption on the input ciphertext

we want to introduce some kind of change

in this padding oracle scenario over

here

but what kind of change should we

introduce so here is the clock sodium

type we are going to change c1

and we are going to leave c2 unchanged

as compared to the original decryption

scenario

and as i mentioned just now if we if we

leave c2 unchanged and since the block

cipher decryption algorithm is

deterministic this means that i2 will

also remain unchanged as well as

compared to the original decryption

scenario on the right hand side over

here

so let's focus our attention on the

padding oracle scenario first

for starters let's try and force the

very last byte of the plain text to be 0

1. we want and the thing is this is

valid padding

and in the original scenario the plain

text wouldn't have been decrypted to

become 0 1 but we're trying to force the

plaintext decrypted to have a 0 1

as its last byte

and we're going to achieve this by

introducing some kind of change to c1

while keeping c2 unchanged

so let's label the last part of i2 as x1

remember we kept c2 in its original form

when providing the ciphertext blocks as

input to the panning oracle since c2

remains unchanged that means that x1

remains unchanged as well but it's just

that we don't know its value

then we're going to try and change c1 we

only need to change the last part of c1

since we're only trying to change the

last part of the plane text to become

zero one so let's call this last part of

c1

t1

but thing is what should we change this

value of t1 to

this is where an exhaustive search comes

in and you have to recognize that t1 is

only one byte long so it can only take

on values from 0 to 255 or 0 0 to ff for

those of you who prefer hexadecimals

instead

so we only need a simple for loop

looping through and searching through 0

to 255 for the last few for the last

fight

and when the padding oracle finally

outputs cs then we'll know what value t1

needs to be

at this point in time we'll know the

value of t1

we also know the value of the last part

of p2 because we're forcing it to become

0 1.

and then we know that this is an xo

operation as i mentioned just now for an

excel operation if you know two of the

entities

you can simply xor them together to

retrieve the last entity

therefore we can now find out the value

of x1 initially we didn't know this it's

an unknown value but now through this

process we're able to find out the value

of x1 we just need the x or t1 together

with the value 0 1.

now let's sort back to our original

scenario where we didn't change the

cipher text

our aim is to find the last byte of the

original plain text

the one indicator and purple right over

here

we have our hands on all of the cypher

text blocks so that means we know the

last fight of the original ciphertext

block c1

on the previous slide we also found the

last byte of the intermediate state x1

of the intermediate state i2 and this

particular last fight will be x1

once again we have an xor operation over

here we know x1 our c1 as well as x1

over here so we can just x all these two

things together to get us p1 and just

like that we found the last byte of the

plain text

from now onwards we just need to repeat

this process for the rest of the bytes

moving from right to left

just to make things clear i'll go

through how to obtain the second last

bite of the plain text as well

back to the original sorry back to the

padding oracle scenario we now want to

force the plain text to have 0 2 0 2 for

the padding which is valid padding

according to the pkcs number 7 standard

once again we're going to keep c2

unchanged and make changes to c1 we're

only concerned with the last two bytes

of the intermediate state let's label

them as x1 and x2

we already found the value of x1

as was covered in the previous two

slides for x2 we don't know its exact

value but we know that since we didn't

change c2 that means i2 remains

unchanged as well so x2 will also remain

unchanged otherwise in other words it's

unknown its value is unknown but we know

that it's unchanged

let's also label the last two bytes of

c2 of c1 as t2 and t1 respectively

let's focus our attention on just the

xor operation involving all of these

last two bytes

over in this diagram over here

since we have both x1 and 02

we can easily find the value of t1 by

xoring x1 and 02

so just like that we know the value of

t1 now the question is what should t2 be

this is where similar to what was

covered two slides ago we have to

conduct an exhaustive search

t2 can only take on values from 0 to 255

we just do a simple for loop and the

moment the padding oracle outputs yes

we'll know what the value of t2 should

be

now we know the value of t2 we also know

the value 0 2 over here

we have two entities so we can simply x

or 0 2 with t2 to obtain the value of x2

now back to the original decryption

context we already know the last byte of

the plaintext but we're not interested

in the last bytes of this ciphertext

block or the intermediate state

we are interested in finding out the

second last byte of the plain text so do

you have our hands on the original

ciphertext blocks we know the second

last byte of c1

over here

we also found on the previous slide the

value of the second last byte of i2

which is x2 we found the value of x2 on

the previous slide once again this is an

xo operation so in order to retrieve the

second last part of the plain text over

here we simply need to x or c2 with x2

and just like that through these past

couple of times we have managed to find

out the last two bytes of the original

plain text in order to find out the rest

of the bytes

of the plain text we just need to repeat

this process for the rest of the blocks

i hope you guys get the idea by now

ultimately the padding oracle attack is

meant to illustrate the idea that

something as innocuous as revealing

whether the padding is valid when abused

in the right context can reveal a lot of

information

i hope you found this video helpful

thank you