Re: Why is RMAC resistant to birthday attacks?
David Wagner wrote: Ed Gerck wrote: (A required property of MACs is providing a uniform distribution of values for a change in any of the input bits, which makes the above sequence extremely improbable) Not so. This is not a required property for a MAC. (Not all MACs must be PRFs.) Thanks. I should have written a usually required property. In general, to have a good MAC, we require a good PRF. Ed Gerck - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
Ed Gerck wrote: Wei Dai wrote: No matter how good the MAC design is, it's internal collision probability is bounded by the inverse of the size of its internal state space. Actually, for any two (different) messages the internal collision probability is bounded by the inverse of the SQUARE of the size of the internal state space. No, I think Wei Dai had it right. SHA1-HMAC has a 160-bit internal state. If you fix two messages, the probability that they give an internal collision is 1/2^160. Maybe you are thinking of the birthday paradox. If you have 2^80 messages, then there is a good probability that some pair of them collide. But this is the square root of the size of the internal state space. And again, Wei Dai's point holds: the only way to reduce the likelihood of internal collisions is to increase the internal state space. In short, I think Wei Dai has it 100% correct. Not really. You can prevent internal collision attacks, for example, by using the envelope method (e.g., HMAC) to set up the MAC message. This is not accurate. The original van Oorschot and Preneel paper describes an internal collision attack on MD5 with the envelope method. Please note also that HMAC is different from the envelope method, but there are internal collision attacks on HMAC as well. Once again, I think Wei Dai was 100% correct here, as well. You might want to consider reading some of the literature on internal collision attacks before continuing this discussion too much further. Maybe all will become clear then. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: comparing RMAC to AES+CBC-MAC or XCBC (Re: Why is RMAC resistant to birthday attacks?)
Adam Back [EMAIL PROTECTED] wrote: See for example Rogaway's arguments about limited value of defending against extension forgery attacks in XCBC: [... quote snipped ...] http://csrc.nist.gov/encryption/modes/workshop2/presentations/xcbc.pdf This doesn't contain the paragraph that you quoted, though a Google search found it in http://www.cs.ucdavis.edu/~rogaway/ocb/xcbc.pdf which appears to be the complete version of the same presentation. In any case, I don't see any mention of extension forgery attacks in either the portion you quoted nor elsewhere in the paper. There isn't reason to mention it since XCBC should be inherently resistant to extension forgery attacks. The attack requires that the MAC have the property that MAC(x) == MAC(y) implies that MAC(x||z) == MAC(y||z). In the case of XCBC, because of the padding and the use of K2 and K3 that would only be true when x and y are the same length or both have lengths that are multiples of the cipher block size. Given that RMAC's salt should be _optional_ [...] so they can match the defense to that which makes sense in the context they are deploying it. I agree with your conclusion, but I don't see how anything Rogaway says about XCBC has anything to do with it. In the case of RMAC, if the parameter sets were chosen to make the work factors comparable on the two attacks, I think it is making the mistake of comparing apples and oranges: In the exhaustive key search attack, the attackers captures one message and the work factor is multiplied times the time it takes to try a key on their own computers. In the extension forgery attack the work factor is multiplied by the time between captured messages. The latter is somewhat under the control of the person who is using RMAC. There is no reason to require that they have similar work factors if the scale is much different. It was just my supposition that equality of the work factors was the motivation behind selecting those parameter sets. I would like to see another reason or a pointer to an explanation by the author if there is one. -- sidney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: comparing RMAC to AES+CBC-MAC or XCBC (Re: Why is RMAC resistant to birthday attacks?)
On Thu, Oct 24, 2002 at 02:08:11AM -0700, Sidney Markowitz wrote: [...] XCBC should be inherently resistant to extension forgery attacks. The attack requires that the MAC have the property that MAC(x) == MAC(y) implies that MAC(x||z) == MAC(y||z). In the case of XCBC, because of the padding and the use of K2 and K3 that would only be true when x and y are the same length or both have lengths that are multiples of the cipher block size. The pre-conditions you give are a little over restrictive, but yes there are limitations due to the structure of XCBC. However provided the pre-conditions are met, and they don't seem that implausible to occur, the extension forgery attacks are possible so I wouldn't say RMAC is inherently resistant to extension forgery. I agree with your conclusion [...] In the case of RMAC, if the parameter sets were chosen to make the work factors comparable on the two attacks, I think it is making the mistake of comparing apples and oranges: In the exhaustive key search attack, the attackers captures one message and the work factor is multiplied times the time it takes to try a key on their own computers. In the extension forgery attack the work factor is multiplied by the time between captured messages. The latter is somewhat under the control of the person who is using RMAC. There is no reason to require that they have similar work factors if the scale is much different. Yes. Perhaps I/someone should submit my comment to them before the deadline. If RMAC parameter sets were interpreted strictly they would be quite incovenient and inflexible for the protocol designer. Adam -- http://www.cypherspace.net/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: collision resistance -- Re: Why is RMAC resistant to birthday attacks?
There seems to be a question about whether: 1. the internal collision probability of a hash function is bounded by the inverse of the size of its internal state space, or 2. the internal collision probability of a hash function is bounded by the inverse of the square root of size of its internal state space. [...] Thus, if we consider just two messages, affirmation #1 holds, because P reduces to 1/S. If we consider n 2 messages, affirmation #2 holds (the birthday paradox). Umm, that's basically what I said in my previous message to the cryptography mailing list. But my terminology was better chosen. In case 2, calling this the internal collision probability is very misleading; there is no event whose probability is the inverse of the square root of the size of the internal state space. Again, this is nothing new. This is all very basic stuff, covered in any good crypto textbook: e.g., _The Handbook of Applied Cryptography_. You might want to take the time to read their chapters on hash functions and message authentication before continuing this discussion. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
collision resistance -- Re: Why is RMAC resistant to birthday attacks?
There seems to be a question about whether: 1. the internal collision probability of a hash function is bounded by the inverse of the size of its internal state space, or 2. the internal collision probability of a hash function is bounded by the inverse of the square root of size of its internal state space. If we assume that the hash function is a good one and thus its hash space is uniformely distributed (a good hash function is a good PRF), then we can say: For a hash function with an internal state space of size S, if we take n messages x1, x2, ...xn, the probability P that there are i and j such that hash(xi) = hash(xj), for xi xj, is P = 1 - (S!/( (S^n)*(S - n)!) which can be approximated by P ~ 1 - e^(-n*(n - 1)/2^(S + 1) ). We see above a n^2 factor which will translate into a factor with sqrt(2^S) when we solve for n. For example, if we ask how many messages N we need in order to have P 0.5, we solve for n and the calculation gives: N ~ sqrt( 2*ln(2)*2^S ). Thus, if we consider just two messages, affirmation #1 holds, because P reduces to 1/S. If we consider n 2 messages, affirmation #2 holds (the birthday paradox). Cheers, Ed Gerck - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
... pls read this message with the edits below... missing ^ in exp and the word WITHOUT...still no coffee... David Wagner wrote: Ed Gerck wrote: Wei Dai wrote: No matter how good the MAC design is, it's internal collision probability is bounded by the inverse of the size of its internal state space. Actually, for any two (different) messages the internal collision probability is bounded by the inverse of the SQUARE of the size of the internal state space. No, I think Wei Dai had it right. SHA1-HMAC has a 160-bit internal state. If you fix two messages, the probability that they give an internal collision is 1/2^160. Maybe you are thinking of the birthday paradox. If you have 2^80 messages, then there is a good probability that some pair of them collide. But this is the square root of the size of the internal state space. And again, Wei Dai's point holds: the only way to reduce the likelihood of internal collisions is to increase the internal state space. In short, I think Wei Dai has it 100% correct. Thanks again. I should have had some coffee at that time...I meant SQUARE ROOT. As to the point you say is in question: the only way to reduce the likelihood of internal collisions is to increase the internal state space. -- this is clearly true but is NOT what is in discussion here. The point is whether the only way to reduce the likelihood of attacks based on MAC collisions is to increase the internal state space. These statements are not equivalent. Not really. You can prevent internal collision attacks, for example, by using the envelope method (e.g., HMAC) to set up the MAC message. This is not accurate. The original van Oorschot and Preneel paper describes an internal collision attack on MD5 with the envelope method. Please note also that HMAC is different from the envelope method, but there are internal collision attacks on HMAC as well. Once again, I think Wei Dai was 100% correct here, as well. However, it was possible to reduce the likelihood of attacks based on MAC collisions WITHOUT increasing the internal state space. This is what I was trying to explain. More below... You might want to consider reading some of the literature on internal collision attacks before continuing this discussion too much further. Maybe all will become clear then. It's always good to read more, and learn more. But what I'm saying is written in many such papers, including some that are written for a general audience: --- To attack MD5 [for example], attackers can choose any set of messages and work on these offline on a dedicated computing facility to find a collision. Because attackers know the hash algorithm and the default IV, attackers can generate the hash code for each of the messages that attackers generate. However, when attacking HMAC, attackers cannot generate message/code pairs offline because attackers do not know K. Therefore, attackers must observe a sequence of messages generated by HMAC under the same key and perform the attack on these known messages. For a hash code length of 128 bits, this requires 2^64 observed blocks (2^73 bits) generated using the same key. --in Dr. Dobbs, April 1999. The point is clear: WITHOUT increasing the internal search space of MD5, MD5 is used in a way that vastly reduces the likelihood of attacks based on MAC collisions. Cheers, Ed Gerck - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: comparing RMAC to AES+CBC-MAC or XCBC (Re: Why is RMAC resistant to birthday attacks?)
The problem with this one-size fits all approach is that for most applications given the key size of AES, the extension forgery is impractical. It would be more flexible to specify RMAC as having an optional salt, with the size determined by the implementer as appropriate for their scenario. So mostly no salt as the number of messages required under the same key to stand a non-negligible chance of finding a collision would be greater than that possibly exchanged in the life-time of the MAC key. For longer lived key scenarios, the size of the salt would be chosen to address the problem. See for example Rogaway's arguments about limited value of defending against extension forgery attacks in XCBC: No Added Resistance to Key-Search Attacks. While other CBC MAC variants use additional keys to improve resistance to key-search attacks, what is presented here does not. One can perform an exhaustive key-search on the MAC presented just as efficiently as on the underlying AES primitive. But this concern, quite appropriate for DES, would seem to be moot for AES. http://csrc.nist.gov/encryption/modes/workshop2/presentations/xcbc.pdf Given that RMAC's salt should be _optional_ on all MAC output sizes (contrary to the parameter sets given in the RMAC draft), and the choice of salt size should be up to the developer -- for example sizes ranging from 0 to 128 bits in increments of 8 bits, so they can match the defense to that which makes sense in the context they are deploying it. Adam On Tue, Oct 22, 2002 at 04:07:53PM -0700, Sidney Markowitz wrote: The choice of parameter sets is a bit odd. I think that they are chosen to make the work factors for General Forgery and Extension Forgery attacks about the same in any one parameter set. It would not make sense to have a parameter set which was a lot weaker to one of the attacks than to the other. Look at Table 2 to see that is so. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
On Mon, 21 Oct 2002, Aram Perez wrote: [EMAIL PROTECTED] wrote: While you are correct in the general case, I have worked on a system where Alice could only generate MACs and Bob could only verify MACs. The hardware was designed so that Alice could not verify MACs and Bob could not generate MACs even though they shared the same key (that was only known to the hardware). This is interesting, but it does not help me to understand what threat model is addressed RMAC, or more generally how do birthday attacks play out against (shared secret) keyed MAC algorithms. The details of the RMAC algorithm itselft are not at issue here, I want to understand the problem so I can use the solution under the right conditions. -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
On Tue, 22 Oct 2002, Ed Gerck wrote: Short answer: Because the MAC tag is doubled in size. Longer answer: The birthday paradox says that if the MAC tag has t bits, only 2^(t/2) queries to the MAC oracle are likely needed in order to discover two messages with the same tag, i.e., a collision, from which forgeries could easily be constructed. This is a point I don't think I quite get. Suppose that I have a MAC oracle and I bounce 2^32 messages off of it. With a 64-bit MAC, the odds are about even that two of those messages will come back with the same MAC. But why does that buy me the ability to easily make a forgery? Does it mean I can then create a bogus message, which the oracle has never seen, and generate a MAC that checks for it? If so how? In protocol terms, let's say Alice is a digital notary. Documents come in, and Alice attests to their existence on a particular date by adding a datestamp, affixing a keyed MAC, and sending them back. Now Bob sends Alice 2^32 messages (and Alice's key-management software totally doesn't notice that the key has been worn to a nub and prompt her to revoke it). Reviewing his files, Bob finds that he has a January 21 document and a September 30 document which have the same MAC. What does Bob do now? How does this get Bob the ability to create something Alice didn't sign, but which has a valid MAC from Alice's key? Bear - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
On Tue, Oct 22, 2002 at 11:09:41AM -0700, bear wrote: Now Bob sends Alice 2^32 messages (and Alice's key-management software totally doesn't notice that the key has been worn to a nub and prompt her to revoke it). Reviewing his files, Bob finds that he has a January 21 document and a September 30 document which have the same MAC. What does Bob do now? How does this get Bob the ability to create something Alice didn't sign, but which has a valid MAC from Alice's key? Call the Jan 21 document x, and the Sept 30 document y. Now Bob knows MAC_Alice(x | z) = MAC_Alice(y | z) for all z, because the internal states of the MAC after processing x and y are the same and therefore will remain equal given identical suffixes. So he can get a MAC on x | z and it's also a valid MAC for y | z, which Alice didn't sign. This applies for CBC-MAC, DMAC, HMAC, and any another MAC that is not randomized or maintains state (for example a counter) from message to message. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
bear wrote: On Tue, 22 Oct 2002, Ed Gerck wrote: Short answer: Because the MAC tag is doubled in size. Longer answer: The birthday paradox says that if the MAC tag has t bits, only 2^(t/2) queries to the MAC oracle are likely needed in order to discover two messages with the same tag, i.e., a collision, from which forgeries could easily be constructed. This is a point I don't think I quite get. Suppose that I have a MAC oracle and I bounce 2^32 messages off of it. With a 64-bit MAC, the odds are about even that two of those messages will come back with the same MAC. But why does that buy me the ability to easily make a forgery? ;-) please note that you already have one forgery... BTW, it is important to look at the size of the internal chaining variable. If it is 128-bit, this means that attacks with a 2^128 burden would likely work. However, if only a subset of the MAC tag is used OR if the message to be hashed has a fixed length defined by the issuer, this is not relevant. Only one of these conditions are needed. Cheers, Ed Gerck - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
On Tue, 22 Oct 2002, Ed Gerck wrote: Short answer: Because the MAC tag is doubled in size. I know, but this is not my question. Longer answer: The birthday paradox says that if the MAC tag has t bits, only 2^(t/2) queries to the MAC oracle are likely needed in order to discover two messages with the same tag, i.e., a collision, from which forgeries could easily be constructed. So the threat model assumes that there is a MAC oracle. What is a practical realization of such an oracle? Does Eve simply wait for (or entice) Alice to send enough (intercepted) messages to Bob? Are there any other birthday attack scenarios for keyed MAC? In many applications the collection sufficiently many messages between Alice and Bob is simply out of the question. In such cases if Eve cannot mount the attack independently and cannot collect 2^(n/2) messages from Alice to Bob, presumably RMAC does not offer an advantage over any other keyed MAC. I am not confused by the RMAC algorithm or so the associated work factor estimates, I want to understand the assumptions (threat models) behind the work factor estimates. Does the above look right? -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
Ed Gerck [EMAIL PROTECTED] It does to (as you can read in the paper). BTW, the easily applies to the case WITHOUT salt Well, to be really pedantic the paper never says that it is easy only that it has a work factor of the square root of the number of possible MAC strings without salt, and that adding the salt multiplies that by the square root of the possible number of salt values. That attack scenario certainly doesn't look easy to me :-). And as long as I'm being pedantic I'll point out my own mistake in my last message of using 'k' as the variable for block size (MAC length) instead of 'b' as in the paper. -- sidney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
[EMAIL PROTECTED] wrote: On Tue, 22 Oct 2002, Ed Gerck wrote: Short answer: Because the MAC tag is doubled in size. I know, but this is not my question. ;-) your question was Why is RMAC resistant to birthday attacks? Longer answer: The birthday paradox says that if the MAC tag has t bits, only 2^(t/2) queries to the MAC oracle are likely needed in order to discover two messages with the same tag, i.e., a collision, from which forgeries could easily be constructed. So the threat model assumes that there is a MAC oracle. What is a practical realization of such an oracle? Does Eve simply wait for (or entice) Alice to send enough (intercepted) messages to Bob? Eve may just watch traffic that comes into her company's servers, knowing the back-end plain text messages. No need to watch external networks. Eve may also be, for example, one of those third-party monitoring services that monitor traffic inside enterprise's networks for the purpose of assuring security. Are there any other birthday attack scenarios for keyed MAC? A birthday attack requires 2^(t/2) values, which looks surprising low -- hence the name paradox (btw, this attack provides the mathematical model behind the game of finding people with same birthday in a party, which works for a surprisingly low number of people). If you can get 2^(t/2) values, the attack works. In many applications the collection sufficiently many messages between Alice and Bob is simply out of the question. In such cases if Eve cannot mount the attack independently and cannot collect 2^(n/2) messages from Alice to Bob, presumably RMAC does not offer an advantage over any other keyed MAC. In an Internet message, datagrams can be inserted, dropped, duplicated, tampered with or delivered out of order at the network layer (and often at the link layer). TCP implements a reliable transport mechanism and copes with the datagram unreliability at the lower layers. However, TCP is unable to cope with a fraudulent datagram that is crafted to pass TCP's protocol checks and is inserted into the datagram stream. That datagram will be accepted by TCP and passed on to higher layers. A cryptographic system operating below TCP is needed to avoid this attack and filter out the deviant datagrams -- and that's where you would use a MAC, if you want to protect each datagram. It's not difficult, thus, to have more than 2^32 MACs in one message or in a series of messages. This is a scenario where it is not so difficult for an attacker to forge an acceptable MAC for a datagram that was not sent in a given sequence, possibly tampering with the upper-layer message and also making it more vulnerable to denial-of-service attacks. Note that having a MAC above TCP does not prevent this attack, even though it can detect it (and thus lead to a denial-of-service). I am not confused by the RMAC algorithm or so the associated work factor estimates, I want to understand the assumptions (threat models) behind the work factor estimates. Does the above look right? If birthday attack is a concern, RMAC is helpful. If not, then not. Cheers, Ed Gerck - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
On Tue, Oct 22, 2002 at 12:31:47PM -0700, Ed Gerck wrote: My earlier comment to bear applies here as well -- this attack can be avoided if only a subset of the MAC tag is used I can't seem to find your earlier comment. It probably hasn't gone through the mailing list yet. I don't see how the attack is avoided if only a substring of the MAC tag is used. (I assume you mean substring above instead of subset.) The attacker just needs to find messages x and y such that the truncated MAC tags of x|0, x|1, ..., x|n, matches those of y|0, y|1, ..., y|n, and this will tell him that there is an internal collision between x and y. n only has to be large enough so that the total length of the truncated MAC tags is greater than the size of the internal state of the MAC. OR if the message to be hashed has a fixed length defined by the issuer. Only one of these conditions are needed. No I don't think that works either. The attacker can try to find messages x and y such that MAC(x|0^n) = MAC(y|0^n) (where 0^n denotes enough zeros to pad the messages up to the fixed length). Then there is a good chance that the internal collision occured before the 0's and so MAC(x|z) = MAC(y|z) for all z of length n. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
[EMAIL PROTECTED] I want to understand the assumptions (threat models) behind the work factor estimates. Does the above look right? I just realized something about the salt in the RMAC algorithm, although it may have been obvious to everyone else: RMAC is equivalent to a HMAC hash-based MAC algorithm, but using a block cipher. The paper states that it is for use instead of HMAC iin circumstances where for some reason it is easier to use a block cipher than a cryptographic hash. The security of HMAC against attacks based on collisions is measured as a function of the bit length of the hash. Using a block cipher in CBC mode makes it in effect a b bit hash, where b is the block length of the cipher. In many cases the block length of a cipher being 64 or 128 bits will be too small by itself. Hence the need to add r bits from the salt and the need to write up explicitly how RMAC handles collision based attacks and how the salt affects that. -- sidney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
Wei Dai wrote: On Tue, Oct 22, 2002 at 12:31:47PM -0700, Ed Gerck wrote: My earlier comment to bear applies here as well -- this attack can be avoided if only a subset of the MAC tag is used I can't seem to find your earlier comment. It probably hasn't gone through the mailing list yet. I don't see how the attack is avoided if only a substring of the MAC tag is used. (I assume you mean substring above instead of subset.) Yes, subset -- not a string with less N characters at the end. For example, you can calculate the P subset as MAC mod P, for P smaller than 2^(bits in the MAC tag). The attacker just needs to find messages x and y such that the truncated MAC tags of x|0, x|1, ..., x|n, matches those of y|0, y|1, ..., y|n, and this will tell him that there is an internal collision between x and y. No. The attacker gets A and B, and sees that A = B. This does not mean that a=b in A = a mod P and B = b mod P. The internal states are possibly different even though the values seen by the attacker are the same. n only has to be large enough so that the total length of the truncated MAC tags is greater than the size of the internal state of the MAC. OR if the message to be hashed has a fixed length defined by the issuer. Only one of these conditions are needed. No I don't think that works either. The attacker can try to find messages x and y such that MAC(x|0^n) = MAC(y|0^n) (where 0^n denotes enough zeros to pad the messages up to the fixed length). Then there is a good chance that the internal collision occured before the 0's and so MAC(x|z) = MAC(y|z) for all z of length n. Why do you think there is a good chance? Note that all messages for which you can get a MAC have some fixed message length M. The attacker cannot leverage a MAC value to calculate the state of a M+1 length message -- exactly because this is prevented by making all messages have length M. Cheers, Ed Gerck - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
comparing RMAC to AES+CBC-MAC or XCBC (Re: Why is RMAC resistant to birthday attacks?)
But the salt doesn't increase the MAC length. It just frustrates attempts to collect message+MAC pairs to find a collision. Think of it like a salt on unix passwords. You can still brute force one particular target in the same time, but the salt reduces your scope for pre-computation. There is still probability 1/2^m of finding a collision given two random messages, whether the salt has size 0 or 64. Note that the salt is optional. They list parameter sets I through V. Parameter sets II through V are considered safe for general use. Parameter set II has salt size 0. Parameter set I is considered only safe for applications where only a limited number of messages could be sent. This is more a function of the small MAC size (32 bits) I think than the fact that the salt size is 0 for parameter set I. I would have thought that unless the keys can essentially never change (for example burnt into hardware) the salt option is of limited practical use. The choice of parameter sets is a bit odd. For example there are no 0 size salts for MAC outputs over 64 bits, while there is for the smaller MAC outputs, and yet you would think the smaller MAC outputs are more in need of the salt as finding a collision is more realistically achievable. Collecting 2^64 messages (for parameter set V) seems already quite theoretical for many applications without adding a 128 bit salt. Yet collecting 2^32 messages (parameter set II) seems much more plausible and yet there is no salt defined at that parameter set. Given the definition of the parameter sets I suspect people will interpret the standard as that they must use one of the listed parameter sets and can't use their own. At least most implementations will tend to do that. Would it not be simpler to just do away with the salt and parameter sets and describe the collision problem and note that minimally K2 should be changed (however the application may decide to arrange this) frequently enough to avoid a non-neglible risk of collisions being obtainable to attacker. If the salt is removed / ignored, RMAC is essentially the same as CBC-MAC but just defined for use with AES (rather than just DES), so providing more security due to larger block size (and key size). The one difference which is an incremental improvement over raw CBC-MAC is that the final CBC-MAC a-like output is encrypted with the 2nd key K3. (K3 defined as K2 xor salt, K2 an independent key). However for example Rogaway and Black's XCBC is simpler, more efficient (not requiring a key schedule for each salt-change) and equally deals with variable length messages). http://csrc.nist.gov/encryption/modes/proposedmodes/xcbc-mac/xcbc-mac-spec.pdf The protection against collisions is of limited practical value, and I think better left out of the standard. Adam On Tue, Oct 22, 2002 at 01:52:18PM -0700, Sidney Markowitz wrote: [EMAIL PROTECTED] I want to understand the assumptions (threat models) behind the work factor estimates. Does the above look right? I just realized something about the salt in the RMAC algorithm, although it may have been obvious to everyone else: RMAC is equivalent to a HMAC hash-based MAC algorithm, but using a block cipher. The paper states that it is for use instead of HMAC iin circumstances where for some reason it is easier to use a block cipher than a cryptographic hash. The security of HMAC against attacks based on collisions is measured as a function of the bit length of the hash. Using a block cipher in CBC mode makes it in effect a b bit hash, where b is the block length of the cipher. In many cases the block length of a cipher being 64 or 128 bits will be too small by itself. Hence the need to add r bits from the salt and the need to write up explicitly how RMAC handles collision based attacks and how the salt affects that. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
Sidney Markowitz wrote: [EMAIL PROTECTED] I want to understand the assumptions (threat models) behind the work factor estimates. Does the above look right? I just realized something about the salt in the RMAC algorithm, although it may have been obvious to everyone else: RMAC is equivalent to a HMAC hash-based MAC algorithm, but using a block cipher. No -- these are all independent things. One can build an RMAC wih SHA-1. An RMAC does not have to use an HMAC scheme. One can also have an HMAC hash-based MAC algorithm using a block cipher, that is not an RMAC. The paper states that it is for use instead of HMAC iin circumstances where for some reason it is easier to use a block cipher than a cryptographic hash. That's is not the reason it was devised. The reason is to prevent a birthday attack for 2^(t/2) tries on a MAC using a t-bit key. Needless to say, it also makes harder to try a brute force attack. Cheers, Ed Gerck - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
Ed Gerck [EMAIL PROTECTED] said: No -- these are all independent things. One can build an RMAC wih SHA-1. An RMAC does not have to use an HMAC scheme. One can also have an HMAC hash-based MAC algorithm using a block cipher, that is not an RMAC. Some quotes from the paper: This paper defines an authentication mode of operation, called RMAC, for a symmetric key block cipher algorithm The definition of RMAC in the table of defnintions: The name of the authentication mode that is specified in this Recommendation In particular, RMAC is an algorithm for generating a message authentication code (MAC) from the data to be authenticated and from an associated value called a salt, using a block cipher and two secret keys [...] Fips Pub 198 specified a different MAC algorithm, called HMAC, that is also appropriate for protection of sensitive data. Because HMAC is constructed from a hash function rather than a block cipher algorithm, RMAC may be preferable for application environments in which an approved block cipher is more convenient to implement than an approved hash function. The paper states that it is for use instead of HMAC iin circumstances where for some reason it is easier to use a block cipher than a cryptographic hash. That's is not the reason it was devised. The reason is to prevent a birthday attack for 2^(t/2) tries on a MAC using a t-bit key. Needless to say, it also makes harder to try a brute force attack. RMAC was devised for the reason I stated, as it says in the last quote from the paper above. The salt is there to make the cost of the extension forgery attack more expensive because the birthday surprise shows that just the number of bits in the cipher block may not make it expensive enough without a salt. The key size is not relevant to the birthday attack (actually extension forgery attack) as shown in the table where the work factor expressed as a function of the block length and the salt length, not the key size. -- sidney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
At 03:05 PM 10/22/2002 -0400, Wei Dai wrote: Call the Jan 21 document x, and the Sept 30 document y. Now Bob knows MAC_Alice(x | z) = MAC_Alice(y | z) for all z, because the internal states of the MAC after processing x and y are the same and therefore will remain equal given identical suffixes. So he can get a MAC on x | z and it's also a valid MAC for y | z, which Alice didn't sign. This applies for CBC-MAC, DMAC, HMAC, and any another MAC that is not randomized or maintains state (for example a counter) from message to message. A nit... this isn't *quite* true for HMAC; the collision could have been in the outer hash function evaluation, not the inner. I haven't yet looked at RMAC and don't know what DMAC is, so I can't comment on them. Still, the attack gives a 50% chance of forging an HMAC, so it's a valid attack. Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
Sidney Markowitz wrote: Ed Gerck [EMAIL PROTECTED] said: That's is not the reason it was devised. The reason is to prevent a birthday attack for 2^(t/2) tries on a MAC using a t-bit key. Needless to say, it also makes harder to try a brute force attack. RMAC was devised for the reason I stated, as it says in the last quote from the paper above. The salt is there to make the cost of the extension forgery attack more expensive because the birthday surprise shows that just the number of bits in the cipher block may not make it expensive enough without a salt. The key size is not relevant to the birthday attack (actually extension forgery attack) as shown in the table where the work factor expressed as a function of the block length and the salt length, not the key size. A minor nit, but sometimes looking into why things were devised is helpful. What I explained can be found in http://csrc.nist.gov/encryption/modes/workshop2/report.pdf and especially useful is the segment: The RMAC algorithm was a refinement of the DMAC algorithm in which a random bit string was exclusive-ORed into the second key and then appended to the resulting MAC to form the tag. The birthday paradox in principle was no longer relevant, for, say, the AES with 128 bit keys, because the tag would be doubled to 256 bits. Joux presented his underlying security model and the properties that he had proven for RMAC: the number of queries that bounded the chance of a forgery was relatively close to the number of 128 bit keys. Cheers, Ed Gerck - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
Ed Gerck [EMAIL PROTECTED] wrote: A minor nit, but sometimes looking into why things were devised is helpful. What I explained can be found in http://csrc.nist.gov/encryption/modes/workshop2/report.pdf Thank you, that was really helpful in seeing the motivation for the work that led to the NIST draft paper. The way I read it now, he includes a justification for block cipher based MACs in general, then presents his RMAC, which he devised to deal with the effect of the birthday surprise on the work factor of the forged extension attack on other block cipher based MACS. -- sidney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Why is RMAC resistant to birthday attacks?
The RMAC FIPS draft does not appear to explicitly state when RMAC is useful. What is the scenario in which (presumably unlike some other keyed MAC algorithms) RMAC is resistant to birthday attacks? More broadly for an arbitrary keyed MAC (in a plausible application!) how does the birthday attack come into play? With unkeyed message digests encrypted by a public key, the attacks are clear, Alice sends Bob message A, Bob agrees to message A, and signs it. Later Alice claims that Bob signed message B. The birthday paradox helps Alice because she can generate lots of minor variants of each message, generate ~sqrt(2^n) hashes of each and have a good shot at finding a collision. With keyed MACs Alice and Bob share the same secretkeys, either can freely generate messages with correct MAC values, so the MAC cannot be used as evidence to a third party that Alice is the signer of the message. In this case the attacker is clearly not either Alice or Bob. So Eve wants to convince Bob that a message really is from Alice. What does Eve do? Does Eve somehow entice Alice to send ~sqrt(2^n) messages to Bob? How does the birthday attack come into play when the attacker cannot independently test potential collisions? Please pardon the naive question, I just want to understand the premises of the problem to which RMAC is a solution. -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
I think they are presuming there will be no encryption, so Eve can verify collisions by observing the MAC values. Eve just records messages and their MACs that Alice sends Bob. They are also presuming exceedingly long lived MAC keys. (If you changed keys the collection of messages would have to start over). The optional salt ensures that K3 (the key used to do the final encryption of the CBC-MAC computed using K1) is different even if the same MAC keys are used indefinately. (K3 = K2 xor salt). Note also in A.3 they are talking about a full collision rather than just an equal MAC. If the MAC is truncated (mb), then you can have equal truncated MACs but different untruncated MACs. So the full collision looks like: MAC(x) = MAC(x') they then observe that for RMAC (and many other MACs) given (1) MAC(x||y) = MAC(x'||y) (2) and (2) means that if an attacker can get MAC(x||y) he automatically has MAC(x'||y) for all values of y he can induce Alice into MACing as they have the same full MACs (and truncated MACs). This leads to the comment that: (from A.3): | Moreover, if a parameter set is chosen in which mb, i.e., if | CIPHK3(On) is truncated to produce the MAC, then the discarded bits | may be difficult for an unauthorized party to determine, so collisions | may be difficult to detect. which means that if the MAC is truncated it could suprisingly be actually stronger (against this attack anyway) because the attacker can't distinguish a truncated MAC collision from a full MAC collision because he only sees the truncated MACs. Truncated MAC collisions are still useful to the attacker probably: he can swap the messages and fool the verifier. But full MAC collisions allow the attacker -- presuming he passively sees or can actively persuade Alice to compute multiple MAC(x||y) for different y values -- then he can subject to that limitation re-use the work of finding the full MAC collision. Adam -- [EMAIL PROTECTED] wrote: So Eve wants to convince Bob that a message really is from Alice. What does Eve do? Does Eve somehow entice Alice to send ~sqrt(2^n) messages to Bob? How does the birthday attack come into play when the attacker cannot independently test potential collisions? - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
