# Why do we encrypt then decrypt then encrypt data with different keys?

In GlobalPlatform specification for smartcards, I came accross this rather strange scheme* ISO/IEC ISO/IEC 9797-1 MAC Algorithm 3:

To calculate the Message Authentication Code, we take some original data (a host cryptogram and a padding), then we apply multiple chained DES calculations, as shown in the image attached. We use a 2-bytes S-MAC key (noted S-MAC = K1K2, where K1 and K2 are 1 byte long). I just can't understand for the moment what's the purpose of encrypting data with K1, then decrypting the result with K2, then encrypting it again with K1.

1. If symetric cryptography is about using the same key for encryption and decryption, then what's the logic behind decrypting data with a different key than the one used to encrypt it?

2. What's the difference between this scheme and a scheme like: encrypt(with K1)->encrypt(with K2)->encrypt(with K1) which seems more logical?

*Not a strange scheme at all, it's actually an industry standard

• 3DES-EDE circuit is designed to be backward compatible with DES. If K1 & K2 keys are different the cipher is 3DES and if K1 & K2 keys are same, the cipher becomes DES. Apr 3 at 17:05
• I just realized that even 3DES does in fact an E-D-E scheme. I always thought it was a triple encryption
– Ryan B.
Apr 3 at 17:13
• @defalt Their scheme mixes between CBC and ECB modes, is it common practice? If I change their algorithm with a normal 3DES (either CBC or ECB) I get the first byte of the result correct, but the next byte isn't the same...
– Ryan B.
Apr 3 at 17:43
• @RyanB. CBC of a single unpadded block of input and a zero IV is, in fact, exactly the same as ECB. CBC only differs from ECB if the IV is non-zero (in which case for a single block it's just "ECB but we XORed the plaintext with a known value"), or if the block length (including padding if present) is greater than 1. Apr 4 at 9:54
• Beware that this has little to nothing to do with encryption of data. A block cipher is a generic construction that can be used for multiple purposes, and here it is just used for calculating a MAC. In that sense, the question title doesn't make much sense. Requiring the key makes the reverse operation impossible, but that's really the only part that has to do with confidentiality. Apr 4 at 12:17

This is usually called "RetailMAC" as it is mainly used by commercial applications. Sometimes it is also referred to as ISO7816-4D2 MAC, even though ISO/IEC 7816-4 not the place where it is directly defined; the scheme has been defined in ISO/IEC 9797-1. The idea is economics: it simply uses a single DES over the data to calculate the MAC, and then adds triple-DES protection requiring two keys to calculate the actual "authentication tag" or MAC value. You'd have close to 112 bits of security while only performing 56 bit DES over most of the data.

The final set of calculations makes it much harder to guess the key value and/or to calculate a valid MAC. The trick of first using single DES is particularly useful on old smart cards that only contain circuitry for single DES; nowadays you'd expect 3DES circuitry to be present, and you'd probably get the same kind of performance if the scheme would use CBC-MAC with the full 3DES cipher.

The CBC-MAC derived scheme does of course need to use CBC to calculate a CBC-MAC; with ECB only the value of the last block will be part of the MAC value. As shown, it uses an all-zero IV, which is OK since it isn't actually used for encryption / confidentiality at all. Furthermore it uses "bit padding", a single 1 followed by as many zeros as needed to fill the final block.

The final operation can also be thought of as a single triple-DES CBC operation. Instead of ending the single DES CBC at the final padded block, it can be stopped at the unpadded block before the last. The final operation is then tripple-DES CBC using the final block of single-DES CBC as IV.

Notes:

• Putting ECB mode in the given picture is misleading; the final encrypt / decrypt is simply a direct application of the block cipher (without padding or any other operation).
• Generally you should not be using these kind of schemes anymore; if possible try and use a scheme that uses AES-CMAC.
• Addition. This "retail MAC", which was used in bank applications, is also called ISO/IEC 9797-1 MAC Algorithm 3. The K1 and K2 are two components of the same key (K1,K2), a two-keys triple-DES key. K2 deciphers because it does in 3DES. The rationale of using a single encryption except in the last block is speed. Problem is: if we can make a collision between messages (which has 40% chance to occur after $2^{32}$ authentications), this allows to attack K1 separately, then find K2.
– fgrieu
Apr 4 at 11:16
• Yeah, it is far from perfect, it relies on a minimal number of authentication tags. This is especially a problem if you'd only allow response authentication, but it might be that is generally prohibited. Anyway, that relies on system security, which is always tricky. Apr 4 at 11:24

If symetric cryptography is about using the same key for encryption and decryption, then what's the logic behind decrypting data with a different key than the one used to encrypt it?

Operations consisting of multiple steps of applying the same cipher - in either direction - with each step taking the output of the last is often an attempt to increase the effective key length when using a cipher with a short key (such as DES, which uses 7-byte keys, too short for real security today). For example, in 3DES (DES with three steps), the effective key security is 112 bits instead of 56, and a single Encrypt operation consists of encrypting the input with K1, then decrypting the result with K2, then encrypting the second result with K3 (which is sometimes the same as K1, as here). The Decrypt operation is the reverse: decrypt the ciphertext with K3, then encrypt the result with K2, then decrypt the second result with K1 to get the original input again.

If you encrypt and then decrypt with the same key (or indeed decrypt and then encrypt with the same key) - such as if K2 were the same as either K1 or K3 - the result is effectively a no-op. You have to do something with the intermediate value - such as encrypt or decrypt it with a different key - for all that computation to have any actual effect at all.

What's the difference between this scheme and a scheme like: encrypt(with K1)->encrypt(with K2)->encrypt(with K1) which seems more logical?

As far as I know (not a cryptographer, though): it doesn't matter. Triple-DES (a.k.a. 3DES and TDEA) did it that way, but Wikipedia implies that the reason is just so that "keying schedule 3" produces identical output to single DES (which is, frankly, a questionable reason to do something). As far as I can tell, it could have been E-E-E/D-D-D instead of E-D-E/D-E-D without impacting the security (but an actual cryptographer may know better than me).

The use of three or more steps in general helps mitigate meet-in-the-middle attacks, which allow recovering the encryption key of a multiply-wrapped encryption scheme much faster (though with much more data needed) than naively brute-forcing the whole combined key. In effect, you break the total key into two pieces and brute force each individually; for short keys like DES this is viable and means a two-step scheme like E-E or E-D, even with two full completely independent DES keys, would be only slightly more secure than a single DES operation with a single key. Note that even three-or-more-step constructions are vulnerable to meet-in-the-middle, but you do get some meaningful increase in key strength (for example, 3DES with 168 bits of independent key material is considered to have only 112 bits of effective key strength; that's a worse ratio than most symmetric ciphers but still MUCH better than the 56 bit strength of single DES though, without needing to invent a whole new cipher).

Meet-in-the-middle attacks do require having a plaintext-ciphertext pair available (you can't use them to decrypt something if you don't have any way to see a plaintext and its associated ciphertext with the same key, though of course if you do have such a pair you can use the recovered key to decrypt any other ciphertext encrypted with that key), but for a MAC it's catastrophic; the MAC is the ciphertext (so an attacker would always have a known plaintext+ciphertext pair) and key recovery would completely negate the point of the MAC (the attacker could tamper with the plaintext and then re-generate the MAC such that it appears authentic).

 It can also be a way to handle multi-party encryption, where a ciphertext is created by multiple parties each with their own key, and it can't be decrypted without each party's key again. There are other ways to achieve that, though, and since the same party presumably has both K1 and K2, that's not what's going on here.

 This implies an interesting fact: in most symmetric ciphers, the choice of "encrypt" and "decrypt" algorithms are merely conventions, and it would be equally secure to invert them. For example, you could encrypt with DES' or AES' or XChaCha20's "decrypt" operation, and encrypt with the "decrypt" operation (caveat: I'm not sure if this applies in all modes of operation, though I didn't immediately think of any where it wouldn't as long as you did it within the mode rather than inverting the "encrypt" and "decrypt" steps of the whole mode). In fact, for stream ciphers like [X]ChaCha20, the "encrypt" and "decrypt" operation are literally the same thing! You can take an input, "decrypt" twice with the same key, and you'll get the same input back again (or "decrypt" it seven times, and get the same result as if you'd "encrypted" it three times).

 Unfortunately, DES has weaknesses besides its short key length, such that even 3DES is insecure for many uses and has been completely deprecated from most uses such as TLS, SSH, VPNs, file encryption, etc. We do in fact have "a whole new cipher" - several of them, in fact - which don't have DES' flaws.

• Yes, the order of E & D's does not matter as long as you use 3 separate keys. The construction of triple DES also allows two key (ABA) encryption though. ¶ The feature that triple DES can simulate single DES is only applicable to hardware really. Say you make a circuit that performs triple-DES, just giving it data using the CPU and getting it back after an interrupt. In that case you only require one circuit tot be implemented instead of two. In software you'd just be wasting cycles. May 2 at 8:35