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: 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]
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]
