[Cryptography] where is the weakness? related-key, mac-then-encrypt, CBC, padding oracle ????

[John Denker]

On 11/08/2015 10:43 AM, Krisztián Pintér wrote:

> the notion that encrypt-then-MAC would be
> the secure option over mac-then-encrypt is just as false the other
> weird recommendations we often hear.

I mostly agree with the sentiment, although that seems
a bit overstated.

By way of analogy:  Suppose a drunk driver jumps the curb,
plows through the flowerbed, and smashes into my house.
I'm not sure it's fair to blame the flowers ... although 
technically it could be argued that if I had planted oak 
trees instead of daffodils, they would have defended against
this particular attack.

It seems to me that if a given cryptosystem (or subsystem)
must be followed by a MAC to make it secure, then the 
subsystem was no good to begin with.  To say the same 
thing the other way, if MAC-then-encrypt is not safe, 
then the encrypt step itself is unsafe (with or without
any earlier MAC) and it's not logical to blame the early 
MAC.

Never confuse the presence of one thing with the absence
of another.

Here is perhaps a better way to think about it:  A block
cipher such as AES is just fine for a *single* block.
For a multi-block message, the block cipher would be
just fine if a different key were used for each block.
That's the logical approach, but almost nobody actually 
does that.  They're too lazy to do all that rekeying.
Instead they use "modes" which are IMHO a kludge that
gives an /approximation/ to rekeying.  ECB mode is the
trivial case of no rekeying and no concealment, leading
to disastrous results.  CBC is better under favorable
conditions, but in less-favorable situations it leaks
horribly.  This includes situations that I like to call
cowbird attacks, i.e. situations where inside your nest
you have a bad actor who can inject stuff into the channel.
BEAST is the poster child for this.

Let's be clear: In CBC mode, in some situations, the late
MAC is required for basic secrecy, not just for authentication.
The late MAC must be considered part of the cost of doing 
business in this mode.

So let's take a step back and ask what is the real problem,
and what solution(s) might there be?

I see this as fundamentally a related-key attack.  Not
just related, but identical.  The same exact key is being
used for every block of the message.  To fix this:
 a) we could change the block cipher to make it easier to rekey
 b) we could stop using CBC mode
 c) we could perhaps try to keep cowbirds out of our nest
 d) we could not leave padding oracles lying around
 e) we could encrypt-then-MAC
 f) we could move to purpose-built authenticated-encryption
 *) ????

As for (f), that seems to be a work-in-progress;  see e.g.
  http://www1.spms.ntu.edu.sg/~diac2015/program.shtml

As for (e), that seems like a kludge IMHO.  I'm not an
expert, but it would seem that (a) and/or (b) is better.
The latter are almost equivalent;  changing the IV is almost
the same as rekeying, if the new IV is based on something
/not/ observable to the attacker, i.e. not merely based
on the previous Cipher Block.  Also note that the late MAC
comes at a cost, and the cost of rekeying (or computing a
new IV) can be weighed against this.  Similarly, transmitting
the late MAC consumes bandwidth, whereas rekeying does not.
This could be the deciding factor in some situations, 
especially if authentication is being performed at some 
other layer.

Specific constructive suggestion:  From now on, whenever
there is a cipher competition, the evaluation criteria 
should include the cost of rekeying.

Actually, the AES implementations I've seen in my limited
experience are rather cheap to re-key.  I could imagine
operating the thing in key-counter mode, where the key
gets changed for every block.

=======

Here's another reason for moving away from CBC:  It only
works for sequential things like TCP file transfers. 
 -- It does not work in datagram situations.
 -- It does not work for random-access disk encryption.

I haven't looked into it in any detail, but I assume the
datagram guys and the disk-encryption guys have figured
out some decent solutions.

Bottom line:  I see this as a related-key attack.  The
real solution is to use a different key for every block.
CBC does not really solve the problem.  Encrypt-then-MAC
does not really solve the problem.