Why was Vaudenay's original padding oracle attack not exploitable on TLS 1.0? Reading Password Interception in a SSL/TLS Channel that was released in 2003:


  At Eurocrypt’02, Vaudenay presented vulnerabilities in padding schemes used for block ciphers in CBC mode. He used a side channel, namely error information in the padding verification. This attack was not possible against SSL/TLS due to both unavailability of the side channel (errors are encrypted) and premature abortion of the session in case of errors.


In Vaudenay's 2002 paper:


  TLS v1.0 (also) provides an optional MAC which failed to thwart the attack: when the server figures out that the MAC is wrong, it yields the bad_record_mac error. However, the message padding is performed after the MAC algorithm, so the MAC does not preclude our attack since it cannot be checked before the padding in the decryption.


it continues:


  The reason why the attack is not so practical is because the padding format error (the decryption_failed error) is a fatal alert and the session must abort.


Now, how bad is this? Bad padding leads the section to break OK, but 1 out of 256 times the padding will be correct and one byte of plaintext will be recovered. This should be enough, and in the same manner of BEAST-style attacks more bytes could be recovered by shifting the payload so that the byte of a cookie we want to recover is always the LSB. I fail to understand why these people thought this was not exploitable.

To add to this, it looks like Canvel, Vaudenay and others actually knew about this but didn't know this was fully exploitable: 


  As pointed out in [17], the attack could have still worked in order to decrypt only the rightmost byte with a probability of success of 2−8. It can also be adapted in order to test if x ends with a given pattern.


Although they later add:


  This does not work either against TLS for another reason: because error messages are not available to the adversary (they are indeed encrypted and indistinguishable).


How is an error, even encrypted, indistinguishable? I'm guessing it would be a short message compared to a long normal response.
It's a question of attack model. Vaudenay places himself in a model where the attacker is "outside", and trying to work out the password that a human user enters in a Web site (or another similar password-protected protocol). Both client and server systems are honest and truthfully run the TLS protocol; the attacker can inspect and alter packets, but that's all. Chosen Plaintext Attacks are out of scope.

In that model, in case of repeated errors, the human user will consider things too fishy, and will not persist. Moreover, most alterations meant to check an hypothesis on the last byte of a block also mangle the previous bytes in the record, which contain the MAC, so the ultimate observable behaviour, from the attacker's point of view, is unchanged: an (encrypted) alert record is sent by the server, and the connection is aborted (so we are not talking about the difference between a short error message and a long non-error message, but about two error messages, who have the exact same length).

The 2003 paper "fixes" both issues:


It targets the case of an email client that automatically connects to an IMAPS server, every minute, and will try again and again even if connections abort; the errors are also silently ignored.
The difference between failure modes ("bad padding" vs "good padding but bad MAC") can be worked out by the attacker by measuring the server's response time.


Retrospectively, we may note that the problem about the alert message not being known can be avoided when the padding has the size of a full block and the receiving side does not check padding byte contents, as is nominally the case with SSL 3.0. Also some TLS 1.0 implementation did not check padding byte contents.

Around 2010, researchers made some sort of "mental breakthrough" in which they realised that CPA were a valid model in a Web context. This began with padding oracle attacks on ASP.NET, in which the attacker sits on the sending side, and wants to unravel the "viewstate", an encrypted blob that the server adds to a Web page in order to offload state information storage on the client. This is not a TLS attack, but it still demonstrates the "extra powers" awarded to the attacker: the attacker controls the connection and can decide to try again, repeatedly, with no supervision by a human victim; and he gets access to error messages.

Then, in 2011, the BEAST attack demonstrated an attack which was not about padding (though it was still about CBC in TLS), with a CPA model in a Web browser, and targeting a secret value sent automatically by the client (the cookie). From that point, researchers began to really believe that CPA with low success rate per connection were really practical in a Web context.

The padding oracle attack, Vaudenay-style, combined with BEAST-like attackers using hostile Javascript, to form the Lucky Thirteen attack. In the mean time (and thanks to Vaudenay's 2003 article), TLS libraries had adapted their code:


The same alert message was sent, whether the failure was on the padding or the MAC (also, that error message was not necessarily made available to the attacker).
The MAC was still computed even in case of bad padding, so as to have a constant processing time.


Yet, there was a small remnant of a timing leak, because the MAC computation time depends on the size of the plaintext, which is not exactly equal to the size of the ciphertext, because of the padding. If padding found upon decryption was incorrect, then the library had to choose some pseudo-padding length, which would leak a bit of information. The Lucky Thirteen attack uses that small leak, in a CPA model with hostile Javascript.

Modern TLS libraries implement really constant-time processing which removes this last timing leak, thus making TLS 1.0 CBC cipher suites safe again (but TLS 1.2 with AEAD suites is still largely preferable).



Summary: it took researchers a decade to understand that the Web offered a practical CPA setup. This entailed recognising that Javascript was not only meant to animate a dancing squid on a Web page, but was powerful enough to trigger many silent connection attempts; and, crucially, that each such connection could be made to include a secret value which, while not being the actual human-entered password, was still juicy enough to warrant some attacking effort.