{"id":696,"date":"2008-10-24T14:21:52","date_gmt":"2008-10-24T14:21:52","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/10\/24\/how-not-to-do-message-integrity-featuring-cbc-mac\/"},"modified":"2008-10-24T14:21:52","modified_gmt":"2008-10-24T14:21:52","slug":"how-not-to-do-message-integrity-featuring-cbc-mac","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/10\/24\/how-not-to-do-message-integrity-featuring-cbc-mac\/","title":{"rendered":"How Not to Do Message Integrity, featuring CBC-MAC"},"content":{"rendered":"

In my last cryptography post<\/a>, I wrote about using message authentication codes
\n(MACs) as a way of guaranteeing message integrity. To review briefly, most ciphers
\nare designed to provide message confidentiality – which means that no one but the
\nsender and the intended receiver can see the plain-text of the message. But
\nciphers that provide confidentiality don’t necessarily make any guarantees that
\nthe message received is exactly the message that was sent. There are a good number
\nof cryptographic attacks that work by altering the message in transit, and
\ndepending on the cipher, that can result in a variety of undesirable
\nresults.<\/p>\n

For example, if you use DES encryption with the ECB mode of operation,
\nyou can insert new blocks anywhere in a message that you want. By using
\na replay attack (where you take encrypted blocks from other messages using
\nthe same encryption, and resend them), an attacker can alter your messages, and
\nyou won’t be able to detect it.<\/p>\n

So in addition to just confidentiality, we need to provide integrity. What does integrity really mean? Basically, it expands the definition of the
\ndecryption function. Written as a function signature, confidential message
\ndecryption is a function decrypt : ciphertext × key → plaintext<\/code>. With message integrity, we add the
\noption that decrypt can return a result saying that the message is invalid: decryptinteg<\/sub> : ciphertext × key → (plaintext | REJECT)<\/code>. <\/p>\n

<\/p>\n

In the last post, I explained the basic concept behind integrity schemes: you add an addition chunk of data to the message, which summarizes the message; any change to the message will (with a very high degree of probability) result in
\na change in the authentication code; so if the message is altered, that change
\nwill be detected, because the authentication code will not match the rest
\nof the message.<\/p>\n

The idea of the message authentication code seems quite simple. We know lots
\nof pseudo-random functions that can do a good job as MAC functions. But like
\nso many things in cryptography, the fact that the concept is simple doesn’t
\nmean that the actual application of that concept is simple: it’s incredibly
\neasy to get it disastrously wrong, even when all of the building blocks are right.<\/p>\n

For example, let’s look at a very simple (and very weak) integrity
\nsystem, called CBC-MAC.<\/p>\n

In CBC-MAC, you compute an authentication code by running a your
\nblock cipher on the message with an initialization vector set
\nto 0. The output for encrypting the last block is your MAC.<\/p>\n

The reason that this works is fairly simple – CBC keeps pushing the
\nresult from the previous encryption step through to the next one – so
\nthe output from the final block conceptually includes information
\nfrom all of the other blocks. So you’ve got an authentication code
\nwhose security is, roughly, equivalent to the security of the block
\ncipher used in CBC mode.<\/p>\n

CBC-MAC isn’t a bad mode of operation. It’s got serious flaws – the biggest
\none is that there are a number of attacks against it if it’s used for
\nvariable length messages. (And you can’t fix it just by adding a message
\nlength indicator to the message, it’s deeper than that.) But CBC is
\na pretty good integrity mode for fixed-length messages, and there’s a widely
\nused variant, called CMAC, which works for variable length messages.<\/p>\n

So how can this go wrong?<\/p>\n

What do you use as the password to the MAC computation? CBC is
\na secure cryptographic mode, so why not just use the same password? Lots
\nof novices (and even some not-no-novice folks!) have implemented CBC-MAC
\nwhere the integrity and confidentiality modes used the same key. If you
\ncompute the MAC using the same key as the message, then you’re open to
\nan attack which completely voids the integrity guarantee!<\/p>\n

Imagine a message M, which is divided into n blocks: (M1<\/sub>, …, Mn<\/sub>). For convenience, we’ll treat the IV as if it were ciphertext block 0. Tuen using CBC with a key K, M encrypts to ciphertext blocks
\n(C1<\/sub>, …, CK<\/sub>), where C_i=Encrypt(Mi<\/sub> ⊕ Ci-1<\/sub>, K), plus a CBC-MAC integrity block. If you look
\nat the CBC block, if it’s using the same key as the main encryption,
\nthen the value of the MAC is the result of computing
\nEncrypt(Mn<\/sub> ⊕Cn-1<\/sub>, k). That value
\nis exactly<\/em> the same as CN<\/sub>! So it’s trivial<\/em>
\nto fake the MAC. If you use CBC-MAC with the same encryption key as
\nyou used to encrypt the message, you’re wasting your time: you might as well
\nnot bother with the MAC at all, because you’ve got no integrity guarantee.<\/p>\n

But that’s an amazingly common mistake. A huge number of implementations
\nof supposedly secure cryptosystems that claim to guarantee integrity have
\nactually used CBC-MAC with one key.<\/p>\n

I mentioned above that CBC-MAC is only safe for fixed-length messages. The reason for that is closely related to the trick I described above. Basically, the nature of CBC ultimately means that given a MAC value M, it’s not hard to generate a string to append to a message which will result in it having the desired
\nMAC. Suppose we know that the message M will generate the mac TM<\/sub>,
\nand we know that the block we want to replace the message with, N has
\nthe MAC TN<\/sub>. Then we can easily generate a string N’, such that
\nappending MAC(M,N) = MAC(N). All we do is XOR the first block of N
\nwith TM<\/sub>, and add it to the message. The new message
\nis is (M1<\/sub>,…,Mn<\/sub>,(N1<\/sub>⊕TN<\/sub>),
\nN2<\/sub>,…,Nn<\/sub>) – that is, we can remove the MAC from the
\nfirst message, use it to glue the two messages together, and tack TN<\/sub> on to the message as the MAC. TN<\/sub>, the MAC computed for T alone, will
\nbe the MAC for the combined message. <\/p>\n

It’s easy to do that if we’re allowed to change the length of the message. If the receiver doesn’t know how long the message is going to be, then they can’t
\ncount on its integrity using CBC-MAC. <\/p>\n

Next time, I’ll look at a variation of CBC-MAC that provides integrity
\nfor variable-length messages using 2 keys – one for confidentiality, and
\none for integrity. Then I’ll go on to a two-pass single-key mode of operation
\nthat provides both confidentiality and integrity.<\/p>\n","protected":false},"excerpt":{"rendered":"

In my last cryptography post, I wrote about using message authentication codes (MACs) as a way of guaranteeing message integrity. To review briefly, most ciphers are designed to provide message confidentiality – which means that no one but the sender and the intended receiver can see the plain-text of the message. But ciphers that provide […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[84],"tags":[],"class_list":["post-696","post","type-post","status-publish","format-standard","hentry","category-encryption"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-be","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/696","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=696"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/696\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=696"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=696"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}