See also: http://www.subspacefield.org/security/security_concepts/index.html#toc-Subsection-31.2 Especially section 31.2.4

If you're encrypting then HMACing, then telling them whether HMAC passed or not shouldn't matter much (under normal assumptions), since they can't get it to pass except under very rare conditions (P(2^-n) for n bits of HMAC). But yeah, ideally, you want to leak as little info as possible to the end user.

I personally also find CBC and padding a little obnoxious and artificial, and used CFB in certain applications of my own that I wrote as learning exercises before such things were widely available - see http://www.subspacefield.org/security/hard_drives_of_doom/

The whole idea of decryption "failing" is a bit weird and specific to certain modes and padding techniques; generally, any encryption which doesn't add information (padding, b64 encoding, metadata such as MAC) cannot fail, since there's just as many plaintexts as ciphertexts, so it is one-to-one.

I find no problem with a library throwing a "decryption failed" exception internally, but in your web app that interacts with the user, you want to catch all exceptions and simply return an error code meaning something like "your message was not accepted". Your software should be like an enigmatic sphinx, giving out as little information as possible. In fact, the strategy used by firewalls is to simply ignore denied packets and not even respond - but this makes it difficult to distinguish crypto failures from network failures.

Schneier once pointed out that you should never take your asserts out of production security code. According to his argument, an assert means "I cannot give a proper response under these conditions", and therefore only secure response is for the program to terminate. Now for a daemon that doesn't respawn, that may be a bit annoying, but I think you can easily modify this by throwing an exception to an outer loop that terminates the connection, emulating a respawn. Yes, this does give out some information, but under the circumstances, there's little alternative.

Oh yeah, forgot how to apply this to the first block - I think it depends on IV, and if it's not part of the blob under client control, or can't be tampered with, it requires special handling. They seem to discuss this in their paper.

The root cause of the problem, like the earlier Flickr API Signature Forgery vulnerability, is “web developers used encryption when they should have used MAC”.

MAC = Message Authentication Code, prevents a client from forging a valid value. You can think of it like a digital signature, except that it’s much faster and the same key creates and verifies the data - which is perfect when your web app generates, sends the value to the client, receives the value from the client, and wants to verify that it is the same thing it sent originally (i.e. hasn't been changed/forged).

Given an oracle, this vuln does make decrypting a token – and thus getting the plaintext – O(n), instead of O(2^n) as brute force would dictate. It doesn’t require plaintext, just a ciphertext, and the attack finds the plaintext a byte at a time, from the end. From skimming it, it seems their paper doesn’t actually describe the attack (see below), but rather just describes how to test for the presence of the vulnerability.

Anyway, the oracle condition typically occurs when you hand something to the client and check it later, which is really a sign you should be using MAC (specifically HMAC). You can also use encryption if you want to hide the value, but for random nonces and session IDs, it doesn’t usually matter (doesn’t hurt, either). You’ll want to encrypt-then-MAC if you do both.

Background knowledge necessary for the attack:

PKCS#5 padding is: If your input is a multiple of the block length, add a full block of padding. Otherwise, add enough octets to pad to a block length. Each octet of the pad always has the number of octets of padding used. So for example, the plaintext ALWAYS ends in 01, or 02 02, or 03 03 03, etc.

In CBC mode: flipping bits in the previous ciphertext block flips the same bits in the next plaintext block after decryption. See my paper[1] for a pretty picture.

Attack

Suppose your plaintext ends in 04 04 04 04. If I twiddle the last octet of the (previous block of) ciphertext, only one value will give valid padding in the plaintext – 01. Now I fix the last octet to 02 (by flipping the two least significant bits), and go to work on the previous octet, trying to make the plaintext end in 02 02.

As a side effect, if I know what bits I had to flip to get the valid padding values, I know that your plaintext differs from the valid padding value in exactly those bits. But the real problem is that the only thing between me and a valid plaintext is this padding (and the vagaries of your block cipher mode). It's like using a screwdriver when you should be using a hammer. You'll see this over and over again in crypto; "use things for what they are designed", or "only rely on the actual security guarantees of your primitives".

Extra credit:

• Figure out how to handle a plaintext already ending in 01, or trying to determine the fourth-to-last octet in the example above. Come up with a general algorithm that works for all cases. Compare to Vaudenay's.
• Ponder the merits of encrypt-then-MAC vs MAC-then-encrypt, with respect to timing side channels, attacks like this, etc.

[1] http://www.subspacefield.org/security/web_20_crypto/ - the premise of which could have been "you probably want to use MAC, not encryption"

[2] http://www.subspacefield.org/security/security_concepts.html - for crypto-related reading (I'll put this description in there shortly)

I have a free online book here: http://www.subspacefield.org/security/security_concepts.html It covers this attack and some other hardware attacks in this section: http://www.subspacefield.org/security/security_concepts/index.html#tth_sEc8

I think the one-man shop would be Alladin software(?) makers of Ghostscript.