# Tag Info

13

The MAC value should be calculated over all of the input, not just the first block. The chaining of CBC makes sure that the bits in the last block of ciphertext depends on all the previous blocks.

12

Well, let's try it, and see how hard it is to forge a message. Let's say for illustrative purposes that each character is a block, and that numbers represent the length indicator section. And let's start by putting the length indicator at the end. So, XXXXXXX7 represents a 7-block message, with the '7' indicator at the end. Let's also say that, ...

9

I'll assumme All ciphered blocks means the same as ciphertext for CBC-Encryption with implicit zero IV, while CBC-MAC is the last block of that. All ciphered blocks is unsafe as a message authenticator for messages longer than one block, for it succumbs to a trivial attack (here with two blocks): Eve intercepts message $M=M_0||M_1$ and its authenticator ...

8

This scheme is not worth the name MAC; it is horribly weak. First and foremost, the tag/MAC is unchanged when two blocks of plaintext are exchanged (because of the commutativity and associativity of the $\oplus$ operation). If follows that from any message with at least two different blocks, we can make a different message for which we know the tag/MAC. ...

8

Can anyone explain why CBC-MAC is not secure for variable length message? For the previous question I'll quote Matthew Green's post from 2013: A quick reminder. CBC-MAC is very similar to the classic CBC mode for encryption, with a few major differences. First, the Initialization Vector (IV) is a fixed value, usually zero. Second, CBC-MAC only ...

7

Well, yes, it does matter; however the terminology 'CBC-MAC' does not specify which. CBC-MAC is a generic construction that takes an arbitrary block cipher, and turns it into an object that acts like a MAC for fixed length messages (much like CBC mode is a generic construction that takes an arbitrary block cipher, and turns it into a object that encrypts ...

7

The problem with CBC-MAC for variable-length messages is that CBC-MAC applied to a one-block message essentially amounts to an oracle for evaluating the block cipher at values of the adversary's choice. And that oracle allows an adversary to break the scheme. Consider first CMAC restricted to messages that consist of a whole number of blocks. Then the ...

7

Yes, this is exactly what a message authentication code is for. Its job is to prevent an attacker from tampering with your message, or from forging completely bogus messages. For a secure MAC, it should not matter what these messages contain. (And no, a secure MAC cannot compromise your key; if it did, it would by definition not be secure, since an ...

5

The CBC-MAC construction indeed can use a PRF instead of PRP. It is now based on PRP due to historical reasons: the blockciphers used for CBC-MAC were based on permutations. From the security point of view there will be no difference: the security proof for the CBC-MAC first converts PRP to PRF (which is indistinguishable up to $2^{n/2}$ queries) and then ...

5

The quoted sentences means: if there is a collision among the MACs of the $2^{(n+1)/2}$ messages submitted, the attacker playing the distinguishing game announces that the oracle is a random function; else announces that the oracle is CBC-MAC. This works because the messages submitted differ only in their first block, thus will never collide under CBC-MAC, ...

5

Yes. Assume that the attacker knows the ciphertext $c = c_1 \mathbin\| c_2$, the initialization vector $v$ and the plaintext $m = m_1 \mathbin\| m_2$. This tells them that $D_k(c_1) = m_1 \oplus v$ and $D_k(c_2) = m_2 \oplus c_1$, where $D_k(\cdot)$ denotes block cipher decryption under the (unknown) key $k$. In particular, this implies that, if the ...

5

Why over-complicate it like that, D1 and D2 generates random 64-bit P (half the block size of AES) they send it to each other both generate AES(key,P_own||P_other) and again send to each other (note that these are different for each) then both can verify that what they received is equal to AES(key,P_other||P_own) Upside here is that it is a fully ...

5

1) The adversary queries the oracle (with some randomly chosen message $m$) and gets as a result a message $m=m_1|m_2|...$ and its tag $t=(t_0,F_{k_2}(t_r))$. She then draws $\rho$ uniformly at random in $\{0,1\}^n$ and outputs the message $m=\rho\oplus m_1|m_2|...$ and its (valid) tag $t=(\rho\oplus t_0,F_{k_2}(t_r))$. 2) The adversary queries the oracle ...

5

Because CBC-MAC with inputs that are not prefix free is weak against existential forgery, meaning it is not a "secure" MAC. More precisely, CBC-MAC is easily distinguishable from a random function (i.e. not a PRF) when the input domain is not prefix-free. This is because an adversary can request the CBC-MAC of messages $M_0$ and $M_1$, and then xor the MAC ...

4

The identification of the lexicographically first irreducible degree-b binary polynomial with the minimal number of ones can be implemented by testing reducibility (second algorithm) of those polynomials in order until you get to the first irreducible polynomial in that order. Alternatively, you could look them up. The constant itself is then derived from ...

4

From the sound of your questions, it almost appears that you have some confusion between the CBC-MAC key and the CBC-MAC tag. The CBC-MAC algorithm takes the message (in this case, most likely the ciphertext) and a secret key; it outputs a tag (which can be public). The security property of CBC-MAC is that someone who does not know the key cannot generate ...

4

It is certainly wrong to state that "MAC can only be produced with AES in CBC and CFB mode", but there seems to be a simple reason that people were inspired by these modes when thinking up possible MAC constructions: They carry along some state that incorporates information from the message while traversing the input blocks. In both modes, encrypting a block ...

4

What you think of is called an extension attack and it turns out that this is the way to go if you would like to break the general CBC-MAC when the message length is not fixed. All that an adversary needs to do is to mount a chosen message attack. Suppose he asks for the tag on the message $m=m_1||m_2||...||m_l$. The resulting CBC MAC would be ...

4

If key 2 and key 3 has a nonnegligible chance to be the same, then the attacker has a nonnegligible chance of being able to generate a valid (Message, MAC) pair. Here's how it works, if the message is not a multiple of 16, then XCBC pads the message out to the next multiple of 16; if it already is, the message remains the same. Then, XCBC logically does a ...

4

No, it is not necessarily secure. Here is a simplified example of why not. Assume one block zero messages are encrypted without padding. The ciphertext is $I||E(I \oplus 0)$. The MAC value is thus $E(E(I) \oplus E(I)) = E(0)$. So regardless of the IV, the MAC is the same for all such messages. So if you encrypt several zero messages you can leak that fact ...

3

An answer surfaced from careful reading of appropriate documentation. The MAC in the question is also defined in ANSI X9.19, and is supported by some PKCS#11 tokens as the mechanism CKM_DES3_X919_MAC_GENERAL. Other than that, this MAC can be simulated using CKM_DES_MAC_GENERAL (or CKM_DES_CBC or CKM_DES3_CBC) for all but the last block, then CKM_DES3_CBC; ...

3

Yes, your understanding is correct. With the CBC-MAC's of $(a), (b)$ and $(a||b)$ you can forge the following new messages: $(a||b \oplus MAC(a)), \\ (b||a \oplus MAC(b)), \\ (b||b \oplus MAC(b)),\\ (a||a \oplus MAC(a)),\\ (a||b||a \oplus MAC(a||b)), \\ (a||b||b \oplus MAC(a||b)), \\ (a||b \oplus MAC(a)||a \oplus MAC(b))\\ (a||b \oplus MAC(a)||b \oplus ... 3 I'll give you a hint, and you can work out the details yourself. Take any$m_1,m_2,m_3$of length$n$(where$n$is the block length), with$m_1\neq m_2$. Query the oracle with$m_1$, then query the oracle with$m_2$, and finally query the oracle with$m_1\|n\|m_3$. Work through this, and you can find a message and its forgery. 3 Yes, this is secure. (one of the few cases where I'm pretty confident about this). Here are the arguments: Combining a secure (e.g. SUF-CMA) MAC with a secure (e.g. CPA-secure) encryption method in encrypt-then-authenticate is generally proven secure. This was shown in "Authenticated Encryption: Relations among notions and analysis of the generic ... 3 "Given the above assumptions and limitations, is the encryption scheme still secure?" No; the attacker can remove blocks of [IV + rest_of_ciphertext] from either end to remove corresponding plaintext blocks without affecting any other part of what it decrypts to change the IV to change the initial plaintext block in the same way as for the OTP, without ... 2 Why approximately$2^{(n+1)/2}$queries? Because it makes the attack work. As far as your final comment, it sounds like you are confusing$(n+1)/2$with$2^{(n+1)/2}$. If we use AES, then$n=128$, so$(n+1)/2=64.5$. However,$2^{64.5}$is a very large number. The exact number of queries is not important as long as it is approximately$2^{64.5}$, and it ... 2 CBC-MAC is calculated by iterating a block cipher in CBC mode over the blocks of the message, using a start value of 0 - i.e.$CBC{-}MAC(a)$is actually$CBC{-}MAC(0,a)$. Since the first part of the messages (i.e.$a$,$b$) in your example have sizes that are multiples of the block length, the$CBC{-}MAC\$ of each of them creates a chaining value that can be ...

2

Hash (message digest) and MAC (message authentication code) are a different thing. CBC-MAC turns block cipher into MAC. HMAC turns hash function into MAC. A good reason to use CBC-MAC would be that a MAC is needed and there is a suitable implementation of sufficiently secure block cipher available. For instance, many of recent Intel-based processors have ...

2

A hash function is not a MAC, although you can turn it into a MAC (see e.g. HMAC). The purpose of a MAC is message authenticity / integrity -- to prevent attackers (i.e. people who don't know the secret key) from modifying the message or forging fake messages. A hash function trivially cannot fulfill the function of a MAC, because hash functions are ...

2

That's a lot of questions, I'll try and answer in order. A hash or message digest alone is not secure because anybody can calculate and thus substitute a hash value. If you (correctly) add a key to the mix then you get a HMAC, which can be used. Nowadays often a HMAC is used, or an authenticated mode of authentication such as GCM, CCM (for packet ...

Only top voted, non community-wiki answers of a minimum length are eligible