Look Around You

Seriously, just, look around you. In this thought experiment, you’ll learn about cryptographic primitives, combinitorical group theory, and along the way, gain a deeper appreciation for 1999’s film, The Matrix. My challenge here is to explain the 1998 “Padding Oracle Attack” by Swiss Cryptographer Daniel Bleichenbacher to the average Luddite, which for me, has truly become a term of endearment in our digital world.

To make this approachable, we will employ a spherical cow (full-time w/ comprehensive benefits package). That’s a "toy model”, where we intentionally simplify the problem to better focus upon different aspects. As we grasp core primitives of our problem, our spherical cow will begin to take shape, adding legs, a tail, perhaps a tactical foregrip. In this thought experiment, our spherical cow will be Rubik’s Cube; the 1970’s “Magic Cube” 3D combination puzzle toy. Colloquially, I’ll refer to this toy model as Rubik’s Cow.

$ cowsay
 ________________________________________
/ "They are already here among us - they \
\ just call themselves Hungarians"       /
 ----------------------------------------
     \   ^__^
      \  (oo)\_______
         (__)\       )\/\
             ||----w |
             ||     ||

Gather Your Supplies

For this experiment you will need the following supplies: colorblind glasses, a Rubik’s cube, a blind Skeptic, an all-knowing Oracle, and a mathematical Architect. In the absence of colorblind glasses, a 7W laser just outside the ultraviolet range, approximately 445nm to 470nm, will do. If neither are available, simply use a blindfold.

As for The Skeptic & The Oracle, to make this experiment accessible to all, you may assume any human that can speak is capable of both arrogant skepticism and prophetic predictions. For groups lacking a mathematical Architect, anyone who can echo the smug manifestation of machine will be perfectly adequate in lieu of mathematical prowess.

Experiment One

1. Select three volunteers, a blind Skeptic, an all-knowing Oracle, and a mathematical Architect.
2. Present a Rubik’s cube to The Architect in its solved state.
3. The Architect will scramble the cube and present it to The Skeptic.
4. The job of The Skeptic is to examine the cube without viewing it.
5. The Skeptic may alter the cube, present it to The Oracle and exclaim “O Oracle, tell us, is this the Answer?”.
6. The Oracle will respond “Yea!” or “Nay!”.

Group Theory & Combinatorics

There are approximately 43 quintillion , or 4.3x10¹⁹, possible permutations of a standard 3x3x3 Rubik’s Cube. Regardless, we do know our problem space is a finite group of possibilities. To describe a finite group of inputs, preimages, and their outputs, images, we could pass around a table consisting of all possibilities, but that would be very cumbersome. Instead, we think about the 43 quintillion possibilities in terms of how we generate the images and how they relate to their preimages. This is the basic explanation of Combinatorics; a study where data is deposited into a mystery machine and how the resulting output relates to its input.

In mathematics & cryptography, we would say our Rubik’s problem is preimage-resistant, i.e. it is computationally infeasible to find an input that maps to any pre-specified output.

The Cipher

In cryptography, a cipher is an algorithm or procedure to encrypt or decrypt, more accurately, encode or decode, some plain ole text into seemingly indecipherable gibberish. For now, our cipher will be the specific pattern in which the Rubik’s Cube was scrambled. So we can think of the solved state of our Cube as the “plaintext”, and the scrambled state as our “ciphertext”. In other words, the Cube represents a block of data we wish to encrypt.

Blocks & Streams

In cryptography, when we encrypt data, we typically do it one of two ways, in blocks or in a stream. A block cipher encrypts a fixed-length chunk of data to the same fixed-length output, but scrambled using some secretive pattern. A stream cipher applies the secretive pattern digit by digit; not requiring a certain length input or output.

Since block ciphers operate on a fixed-length of data, what happens when we have some data left over? Could we not simply divide our input data into nice equal chunks? You’re right, this is an old & insecure cipher mode known as ECB (Electronic Codebook). The problem with ECB is that it lacks “diffusion”. A good cipher will seek to increase the entropy of the produced ciphertext. An even better cipher will seek to drastically change the output of all the ciphertext when just one bit of the input changes. This is what we call the “Avalanche Effect” in cryptographic ciphers.

The mural below is built from over 2,800 hand-twisted Rubik’s Cubes. Using ECB to encrypt this mural, changing a single tile in the top left Rubik’s Cube would not result in mutating any other Rubik’s Cube in the mural. If you could intercept enough ECB-generated ciphertext, you may statistically reduce your problem space such that it becomes computationally feasible to bruteforce.

Our experiment focuses on block ciphers, mutating chunks of data at a time; so what the Rubik’s actually represents is but one chunk of a larger set of data. To accommodate data that doesn’t fit perfectly into our desired chunks, we just add some “padding”, some random data somewhere to ensure the length of our output matches the length of our input.

A Detour Through Bletchley Park

On October 25, 1944, during the Battle of Leyte Gulf, U.S. Fleet Admiral Chester Nimitz sent an encoded message ending with “the world wonders”. The phrase was intended to be nonsensical, as it was a form of cryptographically padding messages to make cryptanalysis more difficult. Upon decoding the message, the radio officer of Admiral William Halsey Jr removed the opening padding of “turkey trots to water”; however, left the final padding in confusion. As a result, Halsey misunderstood the message as an admonishment. Halsey had made the choice to abandon the role of covering landing-invasion forces to pursue a fleet of carriers that were later discovered to be decoys. The misunderstood message lead Halsey to abandon the chase and return to the Battle off Samar, albeit, too late to have much of an impact.

You see the code breakers at England’s Bletchley Park, Alan Turing, et al., had been making use of “cribs”, what cryptanalysts refer to as a “known-plaintext attack”. To determine the cipher pattern used, they assumed messages would have common phrases at the beginning and end, e.g. “Dear” or “Sincerely”. Identifying a crib string of “Qrne” at the beginning of a message might reveal the cipher used was ROT13. As such, it was a required procedure of the U.S Navy to pad all messages.

The Padding Oracle

Going back to our experiment, we now understand that our Rubik’s Cube represents a block of data that may include some padding. But how can we avoid the folly of Halsey? What is legitimate data and what is just left-over random noise to meet our required block-size?

Well simply put, The Oracle will enlighten The Skeptic. When The Architect encrypts or scrambles the Rubik’s Cube, The Oracle will count each move used to transform the plaintext to the ciphertext; from the Rubik’s Cube solved state to the scrambled state.

When The Skeptic presents their Cube, The Oracle will now respond with “Yea!”, “Nay!”, or “Wrong Padding!”. So what strategy might our Skeptic adopt to reduce their problem space? The Skeptic will first aim to identify how many moves were used by The Architect to scramble the Cube. Now let’s imagine this particular block of data only has a single byte of plaintext, the rest is padding. In our Rubik’s Cube toy model, we will consider a single byte a single move. For our padding, we will use all zeros, i.e. we will not make any additional moves.

In a single move, we have 8 corners that can be oriented in 3 ways, but only 7 can be oriented independently. We have 12 edges that can be flipped, but only 11 may be flipped independently. Not withstanding symmetry, we are left with 3⁷ and 2¹¹, or 4,235 possibilities for a single move. A far cry from the 43 quintillion problem space we began with, and certainly not what we would consider computationally infeasible.

Record Splitting

So we can see how Padding Oracle attacks can drastically reduce our problem space when majority of the message is padding, but what if more moves were required and less padding was used? We may easily be back to our 43 quintillion possibilities.

Often times in cryptography, while The Skeptic does not know the cipher, they may be given control of what data is encrypted and how much. Consider the following:

1. The Skeptic knows the size of the block as they hold it in their hand.
2. The Skeptic can prefix additional moves, i.e. data.
3. As before, The Oracle, when presented with the last block of data, will proclaim “Wrong Padding!” if the wrong amount of moves are made.

The goal of The Skeptic is now to ensure that the total moves will always end with a remainder of 1, ensuring a reduction of the problem space to 4,235, allowing a computationally feasible brutefoce of the cipher, which may then be applied to previous blocks of data that required no padding.

That’s Cheating

In practice, what does it look like to allow The Skeptic to control the number of moves? In many applications, plaintext provided or controlled by the client will be turned to ciphertext. This might be the users email or name, URI parameters, or even an order number.

Initializing Legs

Our Rubik’s Cow still looks a bit funny. Previously, we thought of our cipher as the pattern of each twist and turn the Architect applied to the Cube; however, we shouldn’t think of our cipher, the encoding algorithm, as a key. We want to stick with a concrete, well-researched, algorithm that guarantees great confusion and diffusion in the ciphertext we output; not pick a new one each time, that perhaps may not be as computationally resilient.

Instead of starting with a solved Cube, the Architect will randomly twist and turn the Cube 20 times. This is what we call the Initialization Vector, seed, or nonce. We write our plaintext data on-top of this nonce, consequently interleaving our data; i.e. XOR’ing or bit-flipping. For the next block, we could use the same IV, but we achieve greater diffusion by chaining the blocks together. So our IV for the next block is the ciphertext output of the previous plaintext input block, what is referred to as residue, causing a cascading avalanche of bit-flips should one bit in the chain differ.

Whoa There!

Hold your horses cows! Can you spot the flaw in our chaining?

1. The Skeptic knows the size of the block as they hold it in their hand.
2. The Skeptic can prefix additional moves, i.e. data.
3. The IV for all subsequent blocks is the residue of the previous.

As a result, The Skeptic can control the IV for all blocks of data, except the first block. That’s not very helpful, unless, we, I don’t know, used a implicit or fixed IV for the first block. Welp.

Unlike previous versions of SSL and TLS, TLS 1.1 uses an explicit IV in order to prevent the attacks described by [CBCATT]. In prior versions of TLS, there was no IV field and the CBC residue and mask were one and the same.

RFC 4346 Section 6.2.3.2

So if an attacker can intercept the first block of a connection, they had the potential to control the IV of all subsequent blocks of all subsequent messages, as the IV was implicitly determined from other parameters such as the connection state and sequence counters. TLS 1.1 and later now requires that all subsequent IV’s are random. This is 2011’s BEAST Attack, or Browser Exploit Against SSL/TLS. Here is a really great article explaining the attack, from the Tor Project.

The Oracle

If you got this far, you are probably more than familiar with Neo’s role in The Matrix. Neo is The One, a statistically unavoidable remainder of a complex algorithm that arrives approximately every 100 years; a summation of anomalies in an equation that balances Man and Machine. Originally, this anomaly was encountered much sooner in earlier versions of The Matrix. Rather than root out the anomaly, The Architect aims to change the directive of Neo. The destiny of The One is not to destroy The Matrix, but to save Humanity.

Your life is the sum of a remainder of an unbalanced equation inherent to the programming of the matrix. You are the eventuality of an anomaly, which despite my sincerest efforts I have been unable to eliminate from what is otherwise a harmony of mathematical precision.

The Architect

Controlling The One was outside of The Machines’ capabilities, as The One represents an amalgamation of Man and Machine, the physical and the metaphysical. The Machines intended The Oracle to be a form of control over Humanity. The Oracle would guide The One to a gambit paraded as an illusion of free will, where The Machines assumed they could exploit Neo’s Human condition, a vulnerability to influence the perpetual enslavement of Humanity.