CS2107 Padding Oracle Attack
Summary
TLDRThis 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
🔐 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.
🔑 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.
🔠 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.
🕵️♂️ 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.
Mindmap
Keywords
💡Padding Oracle Attack
💡XOR Operation
💡Block Cipher
💡Cipher Block Chaining (CBC) Mode
💡Padding Standard
💡Oracle
💡Deterministic Algorithm
💡Exhaustive Search
💡Valid Padding
💡Man-in-the-Middle (MitM)
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
5.0 / 5 (0 votes)