BEAST Attack: from guessing to decoding

I understood the XOR trick that allows an attacker to guess a block of a previously sent message from the client to the server: the attacker forces the client to send the message $\tilde{m} = c_n \oplus m_g \oplus c$ where

• $c_n$ is the last block of the last ciphertext;
• $m_g$ is the attacker guess of the decryption of an arbitrary block of a previously sent message;
• $c$ is the encrypted block that was chained with the real plaintext block $m$ (i.e., the one that attacker is trying to guess).

When the client sends $\tilde{m}$ to the server the result is

$$E_K(c_n \oplus \tilde{m}) = E_K(c \oplus m_g)$$

that is equal to $E_K(c \oplus m)$ iff the block $m = m_g$. Iterating this attack on all the blocks of a message $M$, the attacker can say if the message $M = M_g$.

So far, so good. What I can't figure out from now on, is how can he change his attack to decrypt a message, without doing a guessing attack. In particular, the problem is that if he tries to guess the block, he only has $2^{-64}$ (supposing to use a 8 byte block cipher) chance of success.

The articles that explain this second part of the attack say: "suppose you already know 7 byte out of 8, you only got a few more guessing to try ($2^8$)", but I don't understand how an attacker can know the first 7 byte of the block he want to decrypt.

As an example, this is an article that goes into the details of the attack. In the last part, he gives the following example

GET /index.html HTTP/1.1
Host: mysite.com
Accept-Encoding: text/html
Accept-Charset: utf-8


How could an attacker find out the session number? This message would be encrypted as

GET /ind         ex.html         HTTP/1.1         \r\nHost         : mysite         .com\r\n         Cookie:          Session=         12345678


It's not clear (to me) how they achieved this result in the article.

Other resources that I've checked out are

(added) Disclaimer: in the years since 2011 browsers have closed the holes that allowed sending a fully-chosen first block plus practically all TLS stacks now do 1/n splitting for TLS1.0 CBC providing defense in depth. And many servers no longer allow TLS1.0 at all (particularly those subject to PCI-DSS). So this A and Q are mainly of historical interest.

Actually that example is wrong, because it counts \r and \n each as two bytes instead of the single byte each actually represents. Also it uses DES as the block cipher, which has been broken and obsolete since the late 1990s.

However, if we ignore those minor errors, in the very next paragraphs that article does correctly explain the principle (graphics simplified to what I can do in SX):

.... On the other hand, if he can inject packets, he can make modifications to the request as well. Lets say he did this:
GET /ind | ex.jsp H | ... | ession=1 | 2345678
Here, I've removed one character from the page being requested to the completely innocent-looking index.jsp, but I've also split the victim block across an 8-byte boundary. Now, if I want to find the first digit of the session ID, I only need a maximum of 10 guesses:
ession=0
ession=1

Notice the latter is a result of the former; making the URL one character shorter caused a subsequent block to contain known text ession= (we know the server uses cookie name Session and the secret is the value) plus only one unknown character from the beginning of the value, so we only need to try a small number of possible guess blocks.

... Now, armed with the first digit, I can alter the request again:
GET /ind | ex.js HT | ... | ssion=12 | 345678
And make up to 10 guesses:
ssion=10
ssion=11
ssion=12

Again by changing the URL we caused a block to contain known text ession=1 and a single unknown character (the second), making it easy to guess. Repeat as needed.

If index.js or even index.j causes a server error and attracts attention, as it might, it is easy to choose other URLs that are the correct length (modulo 8 for DES/3DES/IDEA or 16 for AES/Camellia) like query.cgi?search=able query.cgi?search=baker query.cgi?search=chubby

poncho's answer in the question you link says the same thing, except he calls it 'maneuver[ing] the cookie' into the desired position just before a block boundary and then 'remaneuver[ing]'.

• "On the other hand, if he can inject packets, he can make modifications to the request as well." isn't the url request encrypted? If yes, how can an attacker play with the ciphertext to reflect the desired change (i.e., reduce the url of a single character to move the first session digit in the previous block) in the plaintext?
– user47454
Apr 25, 2017 at 8:15
• @BlackBrain: BEAST is a Chosen Plaintext Attack (CPA) where the attacker gets the victim to encrypt plaintext chosen at least partially by the attacker -- here by javascript in the browser directing the browser to fetch a URL, which is something javascript in web pages very often does, causing the browser to format and send (encrypted) an HTTP GET request including that URL, like the example one you copied in your Q. Apr 26, 2017 at 1:29