The Cryptographic Doom Principle: Some Observations
The article to be discussed:
The Principle:
If you have to perform any cryptographic operation before verifying the MAC on a message you've received, it will somehow inevitably lead to doom.
This doesn't seem likely to lead to a PGP advocacy article. The OpenPGP standard does not refer to any sort of a MAC (Message Authentication Code). So it would seem to be out of scope. Honestly, I just want to comment on the common wisdom expressed in The Cryptographic Doom Principle (TCDP). The insight behind my comments came from the process of writing the PGP advocacy articles. So close enough I guess…
The basic idea behind TCDP is fairly accessible. If you want to prevent any bad effects due to malicious changes to something, you are better off using the MAC to check for those changes first before doing anything that might be affected by those changes. This line of thought leads to this business of “encrypt then MAC” vs “MAC then encrypt” where encrypt then MAC is considered better. Here is how encrypt then MAC works:
The encrypt then MAC part happens when you first build the encrypted message. You encrypt the data and then create a MAC for it. You then send it and the MAC off somewhere.
When it it time to decrypt the message you check the MAC to see if the message was modified somehow along the way. If the check fails you do something appropriate to prevent any bad outcomes from the modification. Otherwise you decrypt the encrypted material with the assurance that it is as sent.
The first example given in TCDP references the paper by Serge Vaudenay1) and calls out the padding oracle seen with SSL. About that…
Simplified version of Figure 1 from Lucky Thirteen: Breaking the TLS and DTLS Record Protocols
For the SSL example as shown in the diagram, the problematic padding isn't covered by the MAC. Applying TCDP here would not help anything. The MAC could be checked first, but modifications to the padding would not be detected.
The observation here is that TCDP, as with other principles, has a scope. An example like the SSL padding issue is out of scope and is thus not applicable. Vaudenay provides other examples that are in the scope of TCDP and a good general discussion of the padding issue so let's move on.
The second example involving SSH is definitely in the scope of the TCDP. The requirement to check the MAC first means that you could not have the encrypted length available. So you would not know where the MAC was located to check it. You would have to structure things differently.
Encrypt Then MAC vs MAC Then Encrypt
TCDP precludes MAC then encrypt because that method hides the MAC under the encryption. You have to decrypt first to get at the MAC. What would a principle in the form of TCDP look like that allowed MAC then encrypt? Here is a suitably modified version of TCDP:
If you have to perform any operation based on the decrypted plain text before verifying the MAC on a message you've received, it will somehow inevitably lead to doom.
I will dub this the relaxed cryptographic doom principle (TRCDP). Let's apply it to the examples referenced from TCDP.
The SSL example is out of the scope of TRCDP for exactly the same reason it is out of the scope of TCDP. TRCDP provides no advantage but is no worse than TCDP.
A quick skim of the examples provided by Vaudenay revealed that all are prevented by the application of TRCDP just as they are by TCDP. Vaudenay only mentions the question of encrypt then MAC vs MAC then encrypt in passing. He was mostly exploring the necessity of a check like a MAC at all. So this is not surprising.
Now the SSH issue. Decrypting the first 4 bytes is allowed under TRCDP. But then you have to interpret those 4 bytes as a length and go looking for the MAC. That counts as an operation and is not permitted under TRCDP. So TRCDP works as well as TCDP here.
So we are now left with the interesting observation that TCDP article does not provide any examples that show that encrypt then MAC is better than MAC then encrypt.
What would be an appropriate example? That would have to be some attack on the decryption itself that the detection of a modification would prevent. The decryption has no way to directly leak data back to an attacker so it would have to be some sort of appropriate side channel attack. Something involving timing differences or electromagnetic leakage would work here. Not just any attack of that sort; it would have to be some attack that would not work without the ability to modify the encrypted data. Is such an attack likely or even possible? I have no idea. So I will answer a different but related question instead.
Generally the way this stuff works is that encrypt then MAC protects the encryption and MAC then encrypt protects the MAC (or whatever is being used as an integrity check). Since the encryption is mostly what we want to protect, doesn't that mean that encrypt then MAC is generically better, even if the threat is low or nonexistent? Well, yes, but the thing is, there are significant advantages to protecting the MAC.
The big advantage is that if the MAC is protected by the encryption, then you don't even need a MAC. That is why the OpenPGP block cipher mode does not require the use of a MAC. It only requires a non-reversible hash. So that hash is much less likely to cause issues from future discoveries of cryptographic weaknesses. This is an important attribute for a standard like OpenPGP that is expected to be secure for as long as someone keeps encrypted files around or archived messages.
If you don't have a MAC then you don't have to generate a separate key for the MAC unrelated to the encryption key. So the result can be simpler.
The OCB block cipher mode2) is an excellent example of why violating the TCDP (at least in spirit) can be a good idea. It not only does not require the use of a MAC, it doesn't even require the use of a hash. It manages with just a simple checksum. The modification check comes from the properties of the encryption so that decryption must occur before checking for modification. The reward is a block encryption mode that is significantly faster/efficient than other block cipher modes.