From exim@www1.ietf.org Mon Apr 12 09:53:52 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA19687 for ; Mon, 12 Apr 2004 09:53:52 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BD1sL-000535-3q for cfrg-archive@odin.ietf.org; Mon, 12 Apr 2004 09:53:25 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3CDrP3H019403 for cfrg-archive@odin.ietf.org; Mon, 12 Apr 2004 09:53:25 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BD1sK-00052s-VZ for cfrg-web-archive@optimus.ietf.org; Mon, 12 Apr 2004 09:53:25 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA19680 for ; Mon, 12 Apr 2004 09:53:21 -0400 (EDT) Received: from ietf-mx ([132.151.6.1]) by ietf-mx with esmtp (Exim 4.12) id 1BD1sI-0004JP-00 for cfrg-web-archive@ietf.org; Mon, 12 Apr 2004 09:53:22 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BD1rX-0004CJ-00 for cfrg-web-archive@ietf.org; Mon, 12 Apr 2004 09:52:35 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BD1qn-00046R-00 for cfrg-web-archive@ietf.org; Mon, 12 Apr 2004 09:51:49 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BD1q1-0004n9-PP; Mon, 12 Apr 2004 09:51:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BD1pL-0004mj-JX for cfrg@optimus.ietf.org; Mon, 12 Apr 2004 09:50:19 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA19605 for ; Mon, 12 Apr 2004 09:50:15 -0400 (EDT) Received: from ietf-mx ([132.151.6.1]) by ietf-mx with esmtp (Exim 4.12) id 1BD1pI-0003z7-00 for cfrg@ietf.org; Mon, 12 Apr 2004 09:50:16 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BD1oC-0003sw-00 for cfrg@ietf.org; Mon, 12 Apr 2004 09:49:08 -0400 Received: from sj-iport-3-in.cisco.com ([171.71.176.72] helo=sj-iport-3.cisco.com) by ietf-mx with esmtp (Exim 4.12) id 1BD1nC-0003i3-00 for cfrg@ietf.org; Mon, 12 Apr 2004 09:48:06 -0400 Received: from sj-core-2.cisco.com (171.71.177.254) by sj-iport-3.cisco.com with ESMTP; 12 Apr 2004 05:57:32 +0000 Received: from mira-sjc5-b.cisco.com (IDENT:mirapoint@mira-sjc5-b.cisco.com [171.71.163.14]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id i3CDlXKj001505 for ; Mon, 12 Apr 2004 06:47:34 -0700 (PDT) Received: from [10.34.251.98] (stealth-10-34-251-98.cisco.com [10.34.251.98]) by mira-sjc5-b.cisco.com (MOS 3.4.5-GR) with SMTP id ARZ85983; Mon, 12 Apr 2004 06:46:46 -0700 (PDT) Mime-Version: 1.0 (Apple Message framework v613) Content-Transfer-Encoding: 7bit Message-Id: Content-Type: text/plain; charset=US-ASCII; format=flowed To: cfrg@ietf.org From: "David A. McGrew" Date: Mon, 12 Apr 2004 06:47:33 -0700 X-Mailer: Apple Mail (2.613) Content-Transfer-Encoding: 7bit Subject: [Cfrg] security level of keyed MD5 as used in RFC 2385 Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=AWL autolearn=no version=2.60 Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Hello, you might be interested in the technical details of draft-iesg-tcpmd5app-00.txt, "Standards Maturity Variance Regarding the TCP MD5 Signature Option (RFC 2385) and the BGP-4 Specification.', online at http://www.ietf.org/internet-drafts/draft-iesg-tcpmd5app-00.txt. Section 3 of that draft outlines the problems in the TCP MD5 Signature Option (RFC 2385), which uses 'keyed MD5' as an authentication method for TCP. The interesting technical question here is: how bad (or how good) is the security of the keyed MD5 TCP option? An important factor in the security analysis is the fact that there is no key management system for this mechanism. I believe that it is common to use a single key across an entire set of machines. Insights into the real security level could provide useful guidance for future work. Please note that I'm not asking for input on the standards process issue here; SAAG is the proper place for such discussions. David _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 11:27:42 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA16141 for ; Fri, 16 Apr 2004 11:27:42 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEV9r-0006i4-Vd for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 11:21:36 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GFLZOc025788 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 11:21:35 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEV1p-0004Ts-Hy for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 11:13:17 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA15092 for ; Fri, 16 Apr 2004 11:13:15 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEV1o-00043r-P2 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 11:13:16 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEV17-000415-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 11:12:34 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEV0P-0003wq-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 11:11:49 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEUsq-000814-MZ; Fri, 16 Apr 2004 11:04:00 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEUJG-0007Mt-F0 for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 10:27:14 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA12223 for ; Fri, 16 Apr 2004 10:27:10 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEUJD-0001BZ-UT for cfrg@ietf.org; Fri, 16 Apr 2004 10:27:12 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEUIN-00019a-00 for cfrg@ietf.org; Fri, 16 Apr 2004 10:26:20 -0400 Received: from p-mail1.rd.francetelecom.com ([195.101.245.15]) by ietf-mx with esmtp (Exim 4.12) id 1BEUHw-00017D-00 for cfrg@ietf.org; Fri, 16 Apr 2004 10:25:52 -0400 Received: from parmhs4.rd.francetelecom.fr ([10.193.117.63]) by parsmtp1.rd.francetelecom.com with Microsoft SMTPSVC(6.0.3790.0); Fri, 16 Apr 2004 16:25:16 +0200 Received: from rd.francetelecom.fr ([10.193.167.13]) by parmhs4.rd.francetelecom.fr with Microsoft SMTPSVC(5.0.2195.6747); Fri, 16 Apr 2004 16:25:14 +0200 Message-ID: <407FED13.9070707@rd.francetelecom.fr> Date: Fri, 16 Apr 2004 16:26:27 +0200 From: Florent Bersani User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.6b) Gecko/20031205 Thunderbird/0.4 X-Accept-Language: en-us, en MIME-Version: 1.0 To: cfrg@ietf.org Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 16 Apr 2004 14:25:14.0194 (UTC) FILETIME=[A200DB20:01C423BE] Content-Transfer-Encoding: 7bit Subject: [Cfrg] MACs: to truncate or not to truncate? Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.4 required=5.0 tests=AWL,HTML_MESSAGE, HTML_TITLE_EMPTY,MIME_HTML_ONLY autolearn=no version=2.60 Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Hi,

Sorry to bother you with a somewhat naive question I stumbled across while trying to work on an EAP method (EAP is RFC 2284 revised by 2284bis) .

In short, many modes of operation of block ciphers that provide authentication (e.g. OMAC) allow for a variable MAC tag length. Yet, recommendation on how to choose the tag length does not seem to be given - apart perhaps very briefly in the first draft of NIST SP 800-38b Table 2. Maybe such a recommendation is deemed to be trivial or a matter of taste... Unfortunately for the profane and young engineer I am, this point is not totally trivial and I would be more than happy if you could confirm (or correct) my current understanding:

For instance with OMAC1 and AES-128 (the assumption here is hence that I am using a 128 bit key and 128 bit block cipher - whether this is appropriate or not could be discussed in another naive question ;-)), the recommended tag length would be 96 bits (the choice had to be made between 1 and 128).

Indeed
  • Truncating appears to be a good idea (but we should not truncate below 64)
  • 96 bits should provide enough security margin against the MAC guessing attack
  • 96 bits is aligned on 32 bit boundaries ;-)
Any feedback would be most welcome,

Florent

The reference I consulted before daring to turn to the CFRG are:
  • "Handbook of Applied Cryptography" by Menezes et al.:  "Remark 9.60 (truncated MAC outputs) Exhaustive attack may, depending on the unicity distance of the MAC, be precluded (information-theoretically) by using less than n bits of the final output as the m-bit MAC. (This must be traded off against an increase in the probability of randomly guessing the MAC: 2^−m.) For m = 32 and E = DES, an exhaustive attack reduces the key space to about 224 possibilities. However, even for m < n, a second text-MAC pair almost certainly determines a unique MAC key."
  • HMAC (RFC 2104 or the companion papers available at http://www-cse.ucsd.edu/users/mihir/papers/hmac.html) by Bellare et al.: "Remark 4.8 Preneel and van Oorschot  recommend outputting only half of the bits of the hash output as the authentication tag. This recommendation is motivated by the fact that forgery attacks are anyway doable with complexity 2^l/2 through birthday attacks (see Section 6), and that by outputting only half of the bits these attacks require more chosen messages. Carrying this recommendation to our constructions would require the assumption that the compression function with truncated output (e.g., only the l/2 most significant bits of output) constitutes a secure MAC. Whether this is acceptable or not depends on the assumed properties of the particular compression function in use. (The tradeoff here is that by outputting less bits the attacker has less bits to predict in a MAC forgery but, on the other hand, the attacker also learns less about the output of the compression function from seeing the authentication tags computed by the legitimate parties.)Applications for which a saving in the MAC length is important can adopt our constructions with a reduced output of (at least) l/2 bits"
  • "MDx-MAC and building fast MACs from hash functions" by Preneel and van Oorschoot (quoted by HMAC)
  • A thread of the IPsec mailing list archive (http://www.netsys.com/ipsec/1997/msg00194.html) started by H. Krawczyk and containing a very nice summary by Bart Preneel (http://www.netsys.com/ipsec/1997/msg00202.html)
  • The pretty recent RFC 3566 specifying "The AES-XCBC-MAC-96 Algorithm and Its Use With IPsec" which contains a discussion in section 4.3 on truncation and 96 bits: AES-XCBC-MAC produces a 128-bit authenticator value. AES-XCBC-MAC-96 is derived by truncating this 128-bit value as described in [HMAC] and verified in [XCBC-MAC-2]. For use with either ESP or AH, a
    truncated value using the first 96 bits MUST be supported. Upon sending, the truncated value is stored within the authenticator field. Upon receipt, the entire 128-bit value is computed and the
    first 96 bits are compared to the value stored in the authenticator field. No other authenticator value lengths are supported by AES-XCBC-MAC-96. The length of 96 bits was selected because it is the default authenticator length as specified in [AH] and meets the security requirements described in [XCBC-MAC-2]." Unfortunately, I did not find [XCBC-MAC-2]: Rogaway, Phil, email communications, October 2001 :-(
My main fears are that
  • I didn't understand right the nice references I read
  • Some references may be outdated (though I did not find any recent paper that would infirm them)
_______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 13:47:13 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA23982 for ; Fri, 16 Apr 2004 13:47:13 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEXM3-0004g7-Ti for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 13:42:20 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GHgJ1w017979 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 13:42:19 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEXID-0002kQ-Q9 for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 13:38:21 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA23532 for ; Fri, 16 Apr 2004 13:38:19 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEXIB-0006qg-Jm for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 13:38:19 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEXHH-0006n6-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 13:37:24 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEXGK-0006j7-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 13:36:24 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEX7E-0000AC-Di; Fri, 16 Apr 2004 13:27:00 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEWvt-00054I-7J for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 13:15:17 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA22623 for ; Fri, 16 Apr 2004 13:15:15 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEWvr-0005K0-5Z for cfrg@ietf.org; Fri, 16 Apr 2004 13:15:15 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEWv5-0005G4-00 for cfrg@ietf.org; Fri, 16 Apr 2004 13:14:28 -0400 Received: from auemail1.lucent.com ([192.11.223.161] helo=auemail1.firewall.lucent.com) by ietf-mx with esmtp (Exim 4.12) id 1BEWuJ-00056t-00 for cfrg@ietf.org; Fri, 16 Apr 2004 13:13:39 -0400 Received: from nwmail.wh.lucent.com (h135-5-40-100.lucent.com [135.5.40.100]) by auemail1.firewall.lucent.com (Switch-2.2.8/Switch-2.2.8) with ESMTP id i3GHD4j28632 for ; Fri, 16 Apr 2004 12:13:04 -0500 (CDT) Received: by nwmail.wh.lucent.com (8.11.7p1+Sun/EMS-1.5 sol2) id i3GHD3615139; Fri, 16 Apr 2004 13:13:03 -0400 (EDT) Cc: cfrg@ietf.org Received: from bell-labs.com by nwmail.wh.lucent.com (8.11.7p1+Sun/EMS-1.5 sol2) id i3GHD0D15120; Fri, 16 Apr 2004 13:13:00 -0400 (EDT) Message-ID: <40801419.8090704@bell-labs.com> Date: Fri, 16 Apr 2004 13:12:57 -0400 From: Uri Blumenthal Organization: Lucent Technologies / Bell Labs User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Florent Bersani Original-CC: cfrg@ietf.org Subject: Re: [Cfrg] MACs: to truncate or not to truncate? References: <407FED13.9070707@rd.francetelecom.fr> In-Reply-To: <407FED13.9070707@rd.francetelecom.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit The length should be reasonably large so that an attacker cannot guess the MAC etc., and at the same time reasonably enough MAC bits should be concealed so that the attacker cannot verify his guess of the key. Note the word "reasonably". MAC of 96 bits of 128-bit string is considered OK. Florent Bersani wrote: > Hi, > > Sorry to bother you with a somewhat naive question I stumbled across > while trying to work on an EAP method (EAP is RFC 2284 revised by > 2284bis) . > > In short, many modes of operation of block ciphers that provide > authentication (e.g. OMAC) allow for a variable MAC tag length. Yet, > recommendation on how to choose the tag length does not seem to be > given - apart perhaps very briefly in the first draft of NIST SP > 800-38b Table 2. Maybe such a recommendation is deemed to be trivial > or a matter of taste... Unfortunately for the profane and young > engineer I am, this point is not totally trivial and I would be more > than happy if you could confirm (or correct) my current understanding: > > For instance with OMAC1 and AES-128 (the assumption here is hence that > I am using a 128 bit key and 128 bit block cipher - whether this is > appropriate or not could be discussed in another naive question ;-)), > the recommended tag length would be 96 bits (the choice had to be made > between 1 and 128). > > Indeed > > * Truncating appears to be a good idea (but we should not truncate > below 64) > * 96 bits should provide enough security margin against the MAC > guessing attack > * 96 bits is aligned on 32 bit boundaries ;-) > > Any feedback would be most welcome, > > Florent > > The reference I consulted before daring to turn to the CFRG are: > > * "Handbook of Applied Cryptography" by Menezes et al.: "Remark > 9.60 (truncated MAC outputs) Exhaustive attack may, depending on > the unicity distance of the MAC, be precluded > (information-theoretically) by using less than n bits of the > final output as the m-bit MAC. (This must be traded off against > an increase in the probability of randomly guessing the MAC: > 2^-m.) For m = 32 and E = DES, an exhaustive attack reduces the > key space to about 224 possibilities. However, even for m < n, a > second text-MAC pair almost certainly determines a unique MAC key." > * HMAC (RFC 2104 or the companion papers available at > http://www-cse.ucsd.edu/users/mihir/papers/hmac.html) by Bellare > et al.: "Remark 4.8 Preneel and van Oorschot recommend > outputting only half of the bits of the hash output as the > authentication tag. This recommendation is motivated by the fact > that forgery attacks are anyway doable with complexity 2^l/2 > through birthday attacks (see Section 6), and that by outputting > only half of the bits these attacks require more chosen > messages. Carrying this recommendation to our constructions > would require the assumption that the compression function with > truncated output (e.g., only the l/2 most significant bits of > output) constitutes a secure MAC. Whether this is acceptable or > not depends on the assumed properties of the particular > compression function in use. (The tradeoff here is that by > outputting less bits the attacker has less bits to predict in a > MAC forgery but, on the other hand, the attacker also learns > less about the output of the compression function from seeing > the authentication tags computed by the legitimate > parties.)Applications for which a saving in the MAC length is > important can adopt our constructions with a reduced output of > (at least) l/2 bits" > * "MDx-MAC and building fast MACs from hash functions" by Preneel > and van Oorschoot (quoted by HMAC) > * A thread of the IPsec mailing list archive > (http://www.netsys.com/ipsec/1997/msg00194.html) started by H. > Krawczyk and containing a very nice summary by Bart Preneel > (http://www.netsys.com/ipsec/1997/msg00202.html) > * The pretty recent RFC 3566 specifying "The AES-XCBC-MAC-96 > Algorithm and Its Use With IPsec" which contains a discussion in > section 4.3 on truncation and 96 bits: AES-XCBC-MAC produces a > 128-bit authenticator value. AES-XCBC-MAC-96 is derived by > truncating this 128-bit value as described in [HMAC] and > verified in [XCBC-MAC-2]. For use with either ESP or AH, a > truncated value using the first 96 bits MUST be supported. Upon > sending, the truncated value is stored within the authenticator > field. Upon receipt, the entire 128-bit value is computed and the > first 96 bits are compared to the value stored in the > authenticator field. No other authenticator value lengths are > supported by AES-XCBC-MAC-96. The length of 96 bits was selected > because it is the default authenticator length as specified in > [AH] and meets the security requirements described in > [XCBC-MAC-2]." Unfortunately, I did not find [XCBC-MAC-2]: > Rogaway, Phil, email communications, October 2001 :-( > > My main fears are that > > * I didn't understand right the nice references I read > * Some references may be outdated (though I did not find any > recent paper that would infirm them) > > _______________________________________________ Cfrg mailing list > Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 14:26:13 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA25678 for ; Fri, 16 Apr 2004 14:26:13 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEXvg-0006sO-Se for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 14:19:08 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GIJ881026427 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 14:19:08 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEXrf-0005vy-ML for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 14:14:59 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA25105 for ; Fri, 16 Apr 2004 14:14:57 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEXrd-0001gt-6N for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 14:14:57 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEXqY-0001Yv-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 14:13:51 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEXpY-0001QL-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 14:12:48 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEXh5-0002Vz-Ir; Fri, 16 Apr 2004 14:04:03 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEXVj-0007vE-Oi for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 13:52:19 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA24258 for ; Fri, 16 Apr 2004 13:52:17 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEXVh-00005p-Bt for cfrg@ietf.org; Fri, 16 Apr 2004 13:52:17 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEXUl-00001g-00 for cfrg@ietf.org; Fri, 16 Apr 2004 13:51:20 -0400 Received: from sj-iport-3-in.cisco.com ([171.71.176.72] helo=sj-iport-3.cisco.com) by ietf-mx with esmtp (Exim 4.12) id 1BEXTy-0007hD-00 for cfrg@ietf.org; Fri, 16 Apr 2004 13:50:30 -0400 Received: from sj-core-5.cisco.com (171.71.177.238) by sj-iport-3.cisco.com with ESMTP; 16 Apr 2004 10:00:46 +0000 Received: from irp-view5.cisco.com (irp-view5.cisco.com [171.70.65.142]) by sj-core-5.cisco.com (8.12.10/8.12.6) with ESMTP id i3GHnu7u028208; Fri, 16 Apr 2004 10:49:57 -0700 (PDT) Date: Fri, 16 Apr 2004 10:49:56 -0700 (PDT) From: Scott Fluhrer To: Uri Blumenthal cc: Florent Bersani , cfrg@ietf.org Subject: Re: [Cfrg] MACs: to truncate or not to truncate? In-Reply-To: <40801419.8090704@bell-labs.com> Message-ID: References: <407FED13.9070707@rd.francetelecom.fr> <40801419.8090704@bell-labs.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 On Fri, 16 Apr 2004, Uri Blumenthal wrote: > The length should be reasonably large so that an attacker cannot guess > the MAC etc., and at the same time reasonably enough MAC bits should be > concealed so that the attacker cannot verify his guess of the key. Note > the word "reasonably". While I agree with the first point, I am a bit confused about the second. A MAC key will, in general, be used to authenticate several messages. That being the case, an attacker can still verify his guess of the key, by checking if that key works with the truncated MACs found in several captured messages. For example, consider the case that we have a MAC of 96 bits with a 128 bit string. Then, if the attacker has two known good message/MAC pairs, then he can verify a key guess. If a guessed key generates the correct 96 bit truncated MAC for both messasges, then it is almost certainly the right key. In this example, if we assume the MAC acts as a random function, then there is a probability of about 2**-64 that there exists a second key that will generate the same two MACs. > > MAC of 96 bits of 128-bit string is considered OK. > > Florent Bersani wrote: > > > Hi, > > > > Sorry to bother you with a somewhat naive question I stumbled across > > while trying to work on an EAP method (EAP is RFC 2284 revised by > > 2284bis) . > > > > In short, many modes of operation of block ciphers that provide > > authentication (e.g. OMAC) allow for a variable MAC tag length. Yet, > > recommendation on how to choose the tag length does not seem to be > > given - apart perhaps very briefly in the first draft of NIST SP > > 800-38b Table 2. Maybe such a recommendation is deemed to be trivial > > or a matter of taste... Unfortunately for the profane and young > > engineer I am, this point is not totally trivial and I would be more > > than happy if you could confirm (or correct) my current understanding: > > > > For instance with OMAC1 and AES-128 (the assumption here is hence that > > I am using a 128 bit key and 128 bit block cipher - whether this is > > appropriate or not could be discussed in another naive question ;-)), > > the recommended tag length would be 96 bits (the choice had to be made > > between 1 and 128). > > > > Indeed > > > > * Truncating appears to be a good idea (but we should not truncate > > below 64) > > * 96 bits should provide enough security margin against the MAC > > guessing attack > > * 96 bits is aligned on 32 bit boundaries ;-) > > > > Any feedback would be most welcome, > > > > Florent > > > > The reference I consulted before daring to turn to the CFRG are: > > > > * "Handbook of Applied Cryptography" by Menezes et al.: "Remark > > 9.60 (truncated MAC outputs) Exhaustive attack may, depending on > > the unicity distance of the MAC, be precluded > > (information-theoretically) by using less than n bits of the > > final output as the m-bit MAC. (This must be traded off against > > an increase in the probability of randomly guessing the MAC: > > 2^-m.) For m = 32 and E = DES, an exhaustive attack reduces the > > key space to about 224 possibilities. However, even for m < n, a > > second text-MAC pair almost certainly determines a unique MAC key." > > * HMAC (RFC 2104 or the companion papers available at > > http://www-cse.ucsd.edu/users/mihir/papers/hmac.html) by Bellare > > et al.: "Remark 4.8 Preneel and van Oorschot recommend > > outputting only half of the bits of the hash output as the > > authentication tag. This recommendation is motivated by the fact > > that forgery attacks are anyway doable with complexity 2^l/2 > > through birthday attacks (see Section 6), and that by outputting > > only half of the bits these attacks require more chosen > > messages. Carrying this recommendation to our constructions > > would require the assumption that the compression function with > > truncated output (e.g., only the l/2 most significant bits of > > output) constitutes a secure MAC. Whether this is acceptable or > > not depends on the assumed properties of the particular > > compression function in use. (The tradeoff here is that by > > outputting less bits the attacker has less bits to predict in a > > MAC forgery but, on the other hand, the attacker also learns > > less about the output of the compression function from seeing > > the authentication tags computed by the legitimate > > parties.)Applications for which a saving in the MAC length is > > important can adopt our constructions with a reduced output of > > (at least) l/2 bits" > > * "MDx-MAC and building fast MACs from hash functions" by Preneel > > and van Oorschoot (quoted by HMAC) > > * A thread of the IPsec mailing list archive > > (http://www.netsys.com/ipsec/1997/msg00194.html) started by H. > > Krawczyk and containing a very nice summary by Bart Preneel > > (http://www.netsys.com/ipsec/1997/msg00202.html) > > * The pretty recent RFC 3566 specifying "The AES-XCBC-MAC-96 > > Algorithm and Its Use With IPsec" which contains a discussion in > > section 4.3 on truncation and 96 bits: AES-XCBC-MAC produces a > > 128-bit authenticator value. AES-XCBC-MAC-96 is derived by > > truncating this 128-bit value as described in [HMAC] and > > verified in [XCBC-MAC-2]. For use with either ESP or AH, a > > truncated value using the first 96 bits MUST be supported. Upon > > sending, the truncated value is stored within the authenticator > > field. Upon receipt, the entire 128-bit value is computed and the > > first 96 bits are compared to the value stored in the > > authenticator field. No other authenticator value lengths are > > supported by AES-XCBC-MAC-96. The length of 96 bits was selected > > because it is the default authenticator length as specified in > > [AH] and meets the security requirements described in > > [XCBC-MAC-2]." Unfortunately, I did not find [XCBC-MAC-2]: > > Rogaway, Phil, email communications, October 2001 :-( > > > > My main fears are that > > > > * I didn't understand right the nice references I read > > * Some references may be outdated (though I did not find any > > recent paper that would infirm them) > > > > _______________________________________________ Cfrg mailing list > > Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg > > > > _______________________________________________ > Cfrg mailing list > Cfrg@ietf.org > https://www1.ietf.org/mailman/listinfo/cfrg > _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 14:56:27 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA27526 for ; Fri, 16 Apr 2004 14:56:26 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEYOw-0008Cp-1H for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 14:49:22 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GInMcD031541 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 14:49:22 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEYAo-0001yE-CV for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 14:34:46 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA26272 for ; Fri, 16 Apr 2004 14:34:43 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEYAl-0003O6-Ju for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 14:34:43 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEY9j-0003H4-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 14:33:40 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEY8y-0003Am-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 14:32:52 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEY2M-0008MH-4P; Fri, 16 Apr 2004 14:26:02 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEXus-0006q1-7N for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 14:18:18 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA25344 for ; Fri, 16 Apr 2004 14:18:15 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEXup-00021t-Na for cfrg@ietf.org; Fri, 16 Apr 2004 14:18:15 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEXtu-0001xr-00 for cfrg@ietf.org; Fri, 16 Apr 2004 14:17:19 -0400 Received: from sj-iport-3-in.cisco.com ([171.71.176.72] helo=sj-iport-3.cisco.com) by ietf-mx with esmtp (Exim 4.12) id 1BEXt3-0001pX-00 for cfrg@ietf.org; Fri, 16 Apr 2004 14:16:26 -0400 Received: from sj-core-2.cisco.com (171.71.177.254) by sj-iport-3.cisco.com with ESMTP; 16 Apr 2004 10:26:42 +0000 Received: from mira-sjc5-b.cisco.com (IDENT:mirapoint@mira-sjc5-b.cisco.com [171.71.163.14]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id i3GIFp0c022371; Fri, 16 Apr 2004 11:15:54 -0700 (PDT) Received: from [128.107.163.157] (dhcp-128-107-163-157.cisco.com [128.107.163.157]) by mira-sjc5-b.cisco.com (MOS 3.4.5-GR) with ESMTP id ASE08245; Fri, 16 Apr 2004 11:15:04 -0700 (PDT) In-Reply-To: <407FED13.9070707@rd.francetelecom.fr> References: <407FED13.9070707@rd.francetelecom.fr> Mime-Version: 1.0 (Apple Message framework v613) Content-Type: text/plain; charset=CP950; format=flowed Message-Id: <1A038D56-8FD2-11D8-9109-0003935495EC@cisco.com> Content-Transfer-Encoding: quoted-printable Cc: cfrg@ietf.org From: "David A. McGrew" Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Date: Fri, 16 Apr 2004 11:15:54 -0700 To: Florent Bersani X-Mailer: Apple Mail (2.613) Content-Transfer-Encoding: quoted-printable Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 Content-Transfer-Encoding: quoted-printable Content-Transfer-Encoding: quoted-printable Florent, On Apr 16, 2004, at 7:26 AM, Florent Bersani wrote: > Hi, > > Sorry to bother you with a somewhat naive question I stumbled across=20= > while trying to work on an EAP method (EAP is RFC 2284 revised by=20 > 2284bis) . > since it is EAP, I assume that the use of the MAC is for entity=20 authentication. I expect that you don't care about the amount of=20 bandwidth taken up by the MAC value, and just want to maximize the=20 security that it provides. Also, if you are writing an Internet Draft, please let us know the=20 timetable on which you need to get comments back. > In short, many modes of operation of block ciphers that provide=20 > authentication (e.g. OMAC) allow for a variable MAC tag length. Yet,=20= > recommendation on how to choose the tag length does not seem to be=20 > given - apart perhaps very briefly in the first draft of NIST SP=20 > 800-38b Table 2. Maybe such a recommendation is deemed to be trivial=20= > or a matter of taste... Unfortunately for the profane and young=20 > engineer I am, this point is not totally trivial and I would be more=20= > than happy if you could confirm (or correct) my current understanding: > > For instance with OMAC1 and AES-128 (the assumption here is hence=20 > that I am using a 128 bit key and 128 bit block cipher - whether this=20= > is appropriate or not could be discussed in another naive question=20 > ;-)), the recommended tag length would be 96 bits (the choice had to=20= > be made between 1 and 128). There are really two issues here: 1) what is the security level that=20 you need from your MAC, and 2) how do the security properties of the=20 MAC degrade as the tag length is reduced. For OMAC, which is a=20 pseudorandom function if I recall correctly, you don't need to worry=20 about the second issue. 96 bits is a widely accepted security level=20 for MACs, though I don't know of any citation that formally justifies=20 this conventional wisdom (perhaps someone else does). > > Indeed > > =A1E Truncating appears to be a good idea (but we should not = truncate=20 > below 64) > =A1E 96 bits should provide enough security margin against = the MAC=20 > guessing attack > > =A1E 96 bits is aligned on 32 bit boundaries ;-) > Any feedback would be most welcome, > This seems sound to me. You could always cite some established=20 specifications that recommend that tag size. Though if you don't care=20= about how many bits the tags take up, you might consider not truncating=20= at all (unless the MAC recommends truncating for a security reason). Will your specification only cover the use of a single MAC, or do you=20 need to write guidelines that will cover the use of any choice of MAC? > Florent > > The reference I consulted before daring to turn to the CFRG are: > Thanks for providing so much background! David > =A1E "Handbook of Applied Cryptography" by Menezes et al.: = "Remark=20 > 9.60 (truncated MAC outputs) Exhaustive attack may, depending on the=20= > unicity distance of the MAC, be precluded (information-theoretically)=20= > by using less than n bits of the final output as the m-bit MAC. (This=20= > must be traded off against an increase in the probability of randomly=20= > guessing the MAC: 2^-m.) For m =3D 32 and E =3D DES, an exhaustive = attack=20 > reduces the key space to about 224 possibilities. However, even for m=20= > < n, a second text-MAC pair almost certainly determines a unique MAC=20= > key." > =A1E HMAC (RFC 2104 or the companion papers available at=20 > http://www-cse.ucsd.edu/users/mihir/papers/hmac.html) by Bellare et=20 > al.: "Remark 4.8 Preneel and van Oorschot recommend outputting only=20= > half of the bits of the hash output as the authentication tag. This=20 > recommendation is motivated by the fact that forgery attacks are=20 > anyway doable with complexity 2^l/2 through birthday attacks (see=20 > Section 6), and that by outputting only half of the bits these attacks=20= > require more chosen messages. Carrying this recommendation to our=20 > constructions would require the assumption that the compression=20 > function with truncated output (e.g., only the l/2 most significant=20 > bits of output) constitutes a secure MAC. Whether this is acceptable=20= > or not depends on the assumed properties of the particular compression=20= > function in use. (The tradeoff here is that by outputting less bits=20 > the attacker has less bits to predict in a MAC forgery but, on the=20 > other hand, the attacker also learns less about the output of the=20 > compression function from seeing the authentication tags computed by=20= > the legitimate parties.)Applications for which a saving in the MAC=20 > length is important can adopt our constructions with a reduced output=20= > of (at least) l/2 bits" > =A1E "MDx-MAC and building fast MACs from hash functions" by = Preneel=20 > and van Oorschoot (quoted by HMAC) > =A1E A thread of the IPsec mailing list archive=20 > (http://www.netsys.com/ipsec/1997/msg00194.html) started by H.=20 > Krawczyk and containing a very nice summary by Bart Preneel=20 > (http://www.netsys.com/ipsec/1997/msg00202.html) > =A1E The pretty recent RFC 3566 specifying "The = AES-XCBC-MAC-96=20 > Algorithm and Its Use With IPsec" which contains a discussion in=20 > section 4.3 on truncation and 96 bits: AES-XCBC-MAC produces a 128-bit=20= > authenticator value. AES-XCBC-MAC-96 is derived by truncating this=20 > 128-bit value as described in [HMAC] and verified in [XCBC-MAC-2]. For=20= > use with either ESP or AH, a > truncated value using the first 96 bits MUST be supported. Upon=20 > sending, the truncated value is stored within the authenticator field.=20= > Upon receipt, the entire 128-bit value is computed and the > first 96 bits are compared to the value stored in the authenticator=20= > field. No other authenticator value lengths are supported by=20 > AES-XCBC-MAC-96. The length of 96 bits was selected because it is the=20= > default authenticator length as specified in [AH] and meets the=20 > security requirements described in [XCBC-MAC-2]." Unfortunately, I did=20= > not find [XCBC-MAC-2]: Rogaway, Phil, email communications, October=20 > 2001 :-( > My main fears are that > > =A1E I didn't understand right the nice references I read > > =A1E Some references may be outdated (though I did not find = any recent=20 > paper that would infirm them) > _______________________________________________ Cfrg mailing list=20 > Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg= _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 17:04:47 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA09852 for ; Fri, 16 Apr 2004 17:04:47 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEaS2-0007AU-Lz for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 17:00:42 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GL0g2A027548 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 17:00:42 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEaKf-0003Jv-Cv for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 16:53:05 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA08071 for ; Fri, 16 Apr 2004 16:53:02 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEaKd-00006y-AH for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 16:53:03 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEaHZ-0007SH-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 16:49:54 -0400 Received: from [65.246.255.50] (helo=mx2.foretec.com) by ietf-mx with esmtp (Exim 4.12) id 1BEaGX-0007M2-02 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 16:48:49 -0400 Received: from optimus22.ietf.org ([132.151.6.22] helo=optimus.ietf.org) by mx2.foretec.com with esmtp (Exim 4.24) id 1BEaEs-0004gF-QV for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 16:47:06 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEZvQ-0000aC-Dp; Fri, 16 Apr 2004 16:27:00 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEYHD-00069I-5N for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 14:41:23 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA26750 for ; Fri, 16 Apr 2004 14:41:19 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEYHA-00042K-8V for cfrg@ietf.org; Fri, 16 Apr 2004 14:41:20 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEYGR-0003xj-00 for cfrg@ietf.org; Fri, 16 Apr 2004 14:40:36 -0400 Received: from p-mail2.rd.francetelecom.com ([195.101.245.16]) by ietf-mx with esmtp (Exim 4.12) id 1BEYFh-0003sb-00 for cfrg@ietf.org; Fri, 16 Apr 2004 14:39:50 -0400 Received: from parmhs4.rd.francetelecom.fr ([10.193.117.63]) by parsmtp2.rd.francetelecom.com with Microsoft SMTPSVC(6.0.3790.0); Fri, 16 Apr 2004 20:39:43 +0200 Received: from rd.francetelecom.fr ([10.193.167.13]) by parmhs4.rd.francetelecom.fr with Microsoft SMTPSVC(5.0.2195.6747); Fri, 16 Apr 2004 20:39:42 +0200 Message-ID: <408028B7.6050907@rd.francetelecom.fr> Date: Fri, 16 Apr 2004 20:40:56 +0200 From: Florent Bersani User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.6b) Gecko/20031205 Thunderbird/0.4 X-Accept-Language: en-us, en MIME-Version: 1.0 To: "David A. McGrew" CC: cfrg@ietf.org Subject: Re: [Cfrg] MACs: to truncate or not to truncate? References: <407FED13.9070707@rd.francetelecom.fr> <1A038D56-8FD2-11D8-9109-0003935495EC@cisco.com> In-Reply-To: <1A038D56-8FD2-11D8-9109-0003935495EC@cisco.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed X-OriginalArrivalTime: 16 Apr 2004 18:39:42.0194 (UTC) FILETIME=[2E70C520:01C423E2] Content-Transfer-Encoding: quoted-printable X-MIME-Autoconverted: from 8bit to quoted-printable by ietf.org id OAA26751 Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.1 required=5.0 tests=AWL autolearn=no version=2.60 Content-Transfer-Encoding: quoted-printable Content-Transfer-Encoding: quoted-printable Hi David, Many thanks for your answer! Some more in-line. BR, Florent David A. McGrew wrote: > Florent, > > On Apr 16, 2004, at 7:26 AM, Florent Bersani wrote: > >> Hi, >> >> Sorry to bother you with a somewhat naive question I stumbled across=20 >> while trying to work on an EAP method (EAP is RFC 2284 revised by=20 >> 2284bis) . >> > > since it is EAP, I assume that the use of the MAC is for entity=20 > authentication. Correct and I am also willing to provide a protected communication=20 channel thanks to an AEAD mode of operation (EAX for now since, for=20 instance, OMAC is already used for entity authentication), thus I have=20 another tag length to choose > I expect that you don't care about the amount of bandwidth taken up=20 > by the MAC value, and just want to maximize the security that it=20 > provides. You are right > > Also, if you are writing an Internet Draft, please let us know the=20 > timetable on which you need to get comments back. The draft I am writing is IMHO totally immature as of now to be worth=20 reading. I'll however let you know of it very much in advance when I=20 find it decent (with the associated review time-line) and be more than=20 happy to get your comments. FYI, right now, the words "protected communication channel" and my=20 background (I believe in avoiding to invent something new when=20 unnecessary, especially in cryptography) prompted me to investigate=20 thoroughly if the existing protocols (TLS, IKEv2) could not fit... and I=20 am still investigating this issue (there is indeed an EAP-TLS RFC which=20 could be extended to support password/shared keys thanks to the work=20 done in TLS and an EAP IKEv2 I-D is proposed) > >> In short, many modes of operation of block ciphers that provide=20 >> authentication (e.g. OMAC) allow for a variable MAC tag length. Yet,=20 >> recommendation on how to choose the tag length does not seem to be=20 >> given - apart perhaps very briefly in the first draft of NIST SP=20 >> 800-38b Table 2. Maybe such a recommendation is deemed to be trivial=20 >> or a matter of taste... Unfortunately for the profane and young=20 >> engineer I am, this point is not totally trivial and I would be more=20 >> than happy if you could confirm (or correct) my current understanding: >> >> For instance with OMAC1 and AES-128 (the assumption here is hence=20 >> that I am using a 128 bit key and 128 bit block cipher - whether this=20 >> is appropriate or not could be discussed in another naive question=20 >> ;-)), the recommended tag length would be 96 bits (the choice had to=20 >> be made between 1 and 128). > > > There are really two issues here: 1) what is the security level that=20 > you need from your MAC, and 2) how do the security properties of the=20 > MAC degrade as the tag length is reduced. For OMAC, which is a=20 > pseudorandom function if I recall correctly, you don't need to worry=20 > about the second issue. 96 bits is a widely accepted security level=20 > for MACs, though I don't know of any citation that formally justifies=20 > this conventional wisdom (perhaps someone else does). OK > >> >> Indeed >> >> =A1E Truncating appears to be a good idea (but we should not=20 >> truncate below 64) >> =A1E 96 bits should provide enough security margin against the= =20 >> MAC guessing attack >> >> =A1E 96 bits is aligned on 32 bit boundaries ;-) >> Any feedback would be most welcome, >> > > This seems sound to me. You could always cite some established=20 > specifications that recommend that tag size. Like IPsec AH ;-) > Though if you don't care about how many bits the tags take up, you=20 > might consider not truncating at all (unless the MAC recommends=20 > truncating for a security reason). That's my whole naive question: if I want the "better" security with my=20 tag, what should I do (maybe refine what I mean by "better" security=20 ;-))? Truncate or not truncate? > > Will your specification only cover the use of a single MAC, or do you=20 > need to write guidelines that will cover the use of any choice of MAC? Well, I was wondering indeed if such guidelines would not be useful to=20 the community, though I was only concerned with my specification... but=20 what's been done some place might be useful to others, isn't it? If any=20 support (e.g. editing or investigating more deeply the matter), I am=20 volunteering to give a hand! _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 17:05:18 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA09890 for ; Fri, 16 Apr 2004 17:05:18 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEaSB-0007Fp-M5 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 17:00:51 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GL0p8q027874 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 17:00:51 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEaLW-0003cP-8p for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 16:53:58 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA08285 for ; Fri, 16 Apr 2004 16:53:55 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEaLU-0000EC-6C for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 16:53:56 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEaIe-0007cB-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 16:51:02 -0400 Received: from [65.246.255.50] (helo=mx2.foretec.com) by ietf-mx with esmtp (Exim 4.12) id 1BEaGe-0007MQ-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 16:48:56 -0400 Received: from optimus22.ietf.org ([132.151.6.22] helo=optimus.ietf.org) by mx2.foretec.com with esmtp (Exim 4.24) id 1BEaGe-0004qd-4b for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 16:48:56 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEa3K-0004AH-Qw; Fri, 16 Apr 2004 16:35:10 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEZN3-0000M1-6k for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 15:51:29 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA01837 for ; Fri, 16 Apr 2004 15:51:27 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEZN1-0000se-Gx for cfrg@ietf.org; Fri, 16 Apr 2004 15:51:27 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEZM8-0000py-00 for cfrg@ietf.org; Fri, 16 Apr 2004 15:50:33 -0400 Received: from mail.esmartstart.com ([66.119.143.50] helo=mail.radioburst.com) by ietf-mx with esmtp (Exim 4.12) id 1BEZLW-0000mI-00 for cfrg@ietf.org; Fri, 16 Apr 2004 15:49:54 -0400 Received: from localhost.localdomain (dav.rfburst.com [209.90.91.153]) by mail.radioburst.com (8.12.8/8.12.8) with ESMTP id i3GJn6dC015679; Fri, 16 Apr 2004 13:49:07 -0600 Received: from localhost.localdomain (tobermory [127.0.0.1]) by localhost.localdomain (8.12.8/8.11.6) with ESMTP id i3GJhVIZ011050; Fri, 16 Apr 2004 13:43:31 -0600 Received: (from ho@localhost) by localhost.localdomain (8.12.8/8.12.8/Submit) id i3GJhU2w011046; Fri, 16 Apr 2004 13:43:30 -0600 Date: Fri, 16 Apr 2004 13:43:30 -0600 Message-Id: <200404161943.i3GJhU2w011046@localhost.localdomain> From: "The Purple Streak, Hilarie Orman" To: cfrg@ietf.org Cc: florent.bersani@rd.francetelecom.fr In-reply-to: Yourmessage <1A038D56-8FD2-11D8-9109-0003935495EC@cisco.com> Subject: Re: [Cfrg] MACs: to truncate or not to truncate? X-esmartscan-MailScanner: Found to be clean Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=AWL autolearn=no version=2.60 A 96-bit MAC will have a collision in about 2^48 usages. That seems too high for many applications. If one can guarantee a key change reasonably often, 96-bits is probably OK. Why truncate a MAC at all? This is a murky area. If there is some possibility of an attacker obtaininig information that constrains the key space, truncation is a defense. But should this happen in a Properly Designed System? I'd hope not. I think that without knowing the exact algorithm used to generate the MAC, one cannot say much about whether or not truncation is a help or hindrance. It is an interesting question for theorists, but I think that IETF guidance should be that the value should not be truncated to less than 128 bits unless there's a good reason, and in no case less than 96 bits. Hilarie _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 17:14:47 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA10741 for ; Fri, 16 Apr 2004 17:14:47 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEaXI-0000jY-M1 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 17:06:09 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GL68Q8002816 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 17:06:08 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEaSk-0007qZ-MW for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 17:01:26 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA09493 for ; Fri, 16 Apr 2004 17:01:23 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEaSi-0001EO-Ld for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 17:01:24 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEaRk-00016l-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 17:00:25 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEaQv-00011r-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 16:59:33 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEaEL-0001K3-Ky; Fri, 16 Apr 2004 16:46:33 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEZuF-00009g-Se for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 16:25:47 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA05409 for ; Fri, 16 Apr 2004 16:25:45 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEZuD-0004x1-U1 for cfrg@ietf.org; Fri, 16 Apr 2004 16:25:46 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEZtN-0004qG-00 for cfrg@ietf.org; Fri, 16 Apr 2004 16:24:54 -0400 Received: from brmea-mail-1.sun.com ([192.18.98.31]) by ietf-mx with esmtp (Exim 4.12) id 1BEZsT-0004ia-00 for cfrg@ietf.org; Fri, 16 Apr 2004 16:23:57 -0400 Received: from esunmail ([129.147.156.34]) by brmea-mail-1.sun.com (8.12.10/8.12.9) with ESMTP id i3GKNvWo010842 for ; Fri, 16 Apr 2004 14:23:57 -0600 (MDT) Received: from xpa-fe2 (esunmail [129.147.156.34]) by edgemail1.Central.Sun.COM (iPlanet Messaging Server 5.2 HotFix 1.21 (built Sep 8 2003)) with ESMTP id <0HWA00MZF5ZXTX@edgemail1.Central.Sun.COM> for cfrg@ietf.org; Fri, 16 Apr 2004 14:23:57 -0600 (MDT) Received: from sun.com ([129.150.32.184]) by mail.sun.net (iPlanet Messaging Server 5.2 HotFix 1.21 (built Sep 8 2003)) with ESMTPSA id <0HWA00MM65ZUV5@mail.sun.net> for cfrg@ietf.org; Fri, 16 Apr 2004 14:23:57 -0600 (MDT) Date: Fri, 16 Apr 2004 13:22:19 -0700 From: =?ISO-8859-1?Q?G=E9_Weijers?= Subject: Re: [Cfrg] MACs: to truncate or not to truncate? In-reply-to: <407FED13.9070707@rd.francetelecom.fr> To: Florent Bersani Cc: cfrg@ietf.org Message-id: <4080407B.9090909@sun.com> Organization: Sun Microsystems, Inc. MIME-version: 1.0 Content-type: text/plain; charset=ISO-8859-1; format=flowed Content-transfer-encoding: quoted-printable X-Accept-Language: en-us, en User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.6) Gecko/20040113 References: <407FED13.9070707@rd.francetelecom.fr> Content-Transfer-Encoding: quoted-printable Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 Content-Transfer-Encoding: quoted-printable Content-Transfer-Encoding: quoted-printable Florent, It's all a matter of simple counting. Assuming the key of the MAC=20 function is long enough to make brute-force search infeasible, and the=20 MAC is a good PRF you just determine: 1. the level of security you want to achieve, e.g. the chance of the adversary getting access should be less than, say, one in a 1000 million (10**9) 2. the number of guesses the adversary can make during the lifetime of the key, e.g. 100 guesses per second for 5 years, about 15778800000 guesses You then simply multiply the two, and see how many bits you need: 10**9=20 * 15778800000 =3D 15778800000000000000. log_2(15778800000000000000) =3D=20 63.77, so 64 bits should do it for guessing attacks. The overly prudent=20 engineer then could add some bits to compensate for mistakes in his=20 assumptions :-) The other types of known attacks do not seem very relevant: * brute force key search does not depend on the size of the MAC value= * shortcut attacks require you to capture 2^(n/2) valid authentication exchanges, which means that you'd be reauthenticating at dizzying rates, and your adversary needs to have more than a zettabyte (10^21 bytes) worth of storage by the time you store and index all that. This is mindboggingly unrealisti= c. * even if someone would come up with a birthday or other attack against the MAC with complexity O(2^(n-2)) you're likely safe for a long time. From a practical point of view anything from 64 bits on is large enough = that the bad guys will think of a different way to get you (such as=20 bribe your sysadmin). Ge' --=20 G=E9 Weijers mailto:ge.weijers@sun.com Installation and Linux Group Tel: (877)240-7611 x69536 Sun Microsystems, Inc. Fax: (877)240-7611 =3D=3D=3D Expressed opinions are my own, I do not speak for Sun =3D=3D=3D= _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 18:16:00 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA15163 for ; Fri, 16 Apr 2004 18:16:00 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEbPc-00011B-Ic for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 18:02:16 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GM2GIa003905 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 18:02:16 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEbJz-0006Gu-6B for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 17:56:27 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA12640 for ; Fri, 16 Apr 2004 17:56:23 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEbJw-0004bc-IP for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 17:56:24 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEbJ1-0004Ys-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 17:55:27 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEbIF-0004X4-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 17:54:39 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEb7x-0003X7-6D; Fri, 16 Apr 2004 17:44:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEaxn-0000OH-BR for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 17:33:31 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA11465 for ; Fri, 16 Apr 2004 17:33:27 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEaxk-0003Ji-Sd for cfrg@ietf.org; Fri, 16 Apr 2004 17:33:28 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEaws-0003FO-00 for cfrg@ietf.org; Fri, 16 Apr 2004 17:32:34 -0400 Received: from sj-iport-2-in.cisco.com ([171.71.176.71] helo=sj-iport-2.cisco.com) by ietf-mx with esmtp (Exim 4.12) id 1BEaw4-0003BB-00 for cfrg@ietf.org; Fri, 16 Apr 2004 17:31:44 -0400 Received: from sj-core-5.cisco.com (171.71.177.238) by sj-iport-2.cisco.com with ESMTP; 16 Apr 2004 13:40:51 +0000 Received: from irp-view5.cisco.com (irp-view5.cisco.com [171.70.65.142]) by sj-core-5.cisco.com (8.12.10/8.12.6) with ESMTP id i3GLVD7u004038; Fri, 16 Apr 2004 14:31:13 -0700 (PDT) Date: Fri, 16 Apr 2004 14:31:12 -0700 (PDT) From: Scott Fluhrer To: "The Purple Streak, Hilarie Orman" cc: cfrg@ietf.org, florent.bersani@rd.francetelecom.fr Subject: Re: [Cfrg] MACs: to truncate or not to truncate? In-Reply-To: <200404161943.i3GJhU2w011046@localhost.localdomain> Message-ID: References: <200404161943.i3GJhU2w011046@localhost.localdomain> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 On Fri, 16 Apr 2004, The Purple Streak, Hilarie Orman wrote: > A 96-bit MAC will have a collision in about 2^48 usages. That seems too > high for many applications. What is the significance of a MAC collision? If the attacker knows that two messages A and B were both generated by the sender and happen to have the common MAC value M, what can he do with that information? Another approach that an attacker could try is to take 2^48 valid messages A_i with MAC tags M_i. If he always has a pile of 2^48 bogus messages B_j, then there is likely to be a pair of messages A_i,B_j that have a common MAC value. However. since he doesn't have the MAC key, he can't determine which ones they might be. He might grab MACs M_i, attach them to random B_j's and hope to get lucky, but that doesn't have any advantage over picking MACs at random. > If one can guarantee a key change reasonably > often, 96-bits is probably OK. -- scott _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 18:21:39 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA15752 for ; Fri, 16 Apr 2004 18:21:39 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEbgQ-0001Pl-M9 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 18:19:38 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GMJcPO005427 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 18:19:38 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEbWW-0005PI-Kr for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 18:09:24 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA13774 for ; Fri, 16 Apr 2004 18:09:20 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEbWT-00057B-Qs for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 18:09:21 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEbVV-00053N-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 18:08:21 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEbUY-00050X-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 18:07:22 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEbKY-0006SI-3l; Fri, 16 Apr 2004 17:57:02 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEaZt-0001RT-0U for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 17:08:49 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA10387 for ; Fri, 16 Apr 2004 17:08:45 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEaZq-0002Da-Le for cfrg@ietf.org; Fri, 16 Apr 2004 17:08:46 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEaYm-00021z-00 for cfrg@ietf.org; Fri, 16 Apr 2004 17:07:41 -0400 Received: from abraham.cs.berkeley.edu ([128.32.37.170]) by ietf-mx with esmtp (Exim 4.12) id 1BEaWm-0001jZ-00 for cfrg@ietf.org; Fri, 16 Apr 2004 17:05:36 -0400 Received: from news by abraham.cs.berkeley.edu with local (Exim 4.21) id 1BEaYf-0007la-IA for cfrg@ietf.org; Fri, 16 Apr 2004 14:07:33 -0700 To: cfrg@ietf.org Path: not-for-mail From: daw@taverner.cs.berkeley.edu (David Wagner) Newsgroups: isaac.lists.ietf-cfrg Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Date: Fri, 16 Apr 2004 21:07:33 +0000 (UTC) Organization: University of California, Berkeley Lines: 26 Distribution: isaac Message-ID: References: <1A038D56-8FD2-11D8-9109-0003935495EC@cisco.com> <200404161943.i3GJhU2w011046@localhost.localdomain> Reply-To: daw-usenet@taverner.cs.berkeley.edu (David Wagner) NNTP-Posting-Host: taverner.cs.berkeley.edu X-Trace: abraham.cs.berkeley.edu 1082149653 29546 128.32.153.228 (16 Apr 2004 21:07:33 GMT) X-Complaints-To: usenet@abraham.cs.berkeley.edu NNTP-Posting-Date: Fri, 16 Apr 2004 21:07:33 +0000 (UTC) X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Originator: daw@taverner.cs.berkeley.edu (David Wagner) Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 The Purple Streak, Hilarie Orman wrote: >A 96-bit MAC will have a collision in about 2^48 usages. That seems too >high for many applications. Why? Collisions aren't a problem for a MAC; you can't use them to break the message authentication property. A MAC is different from an unkeyed hash in this respect. (Now, *internal* collisions are indeed a problem, due to the Wiener and van Oorschot attack. Consequently, a hash with a 96-bit internal chaining value would be a questionable choice. However, I presume we're talking about taking a MAC with a large internal chaining variable, like MD5-HMAC or SHA1-HMAC, and truncating its output. In that case, truncating to 96 bits should be fine.) >is an interesting question for theorists, but I think >that IETF guidance should be that the value should not be truncated to >less than 128 bits unless there's a good reason, and in no case less >than 96 bits. I disagree. Truncating SHA1-HMAC to 96 bits is fine, and there's no reason to spread fear or uncertainty about it. (One can even prove that it's fine, under reasonable assumptions about the SHA1 internal compression function. Under appropriate assumptions, SHA1-HMAC is a PRF, and truncating a PRF is harmless.) _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 18:52:34 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA17501 for ; Fri, 16 Apr 2004 18:52:34 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEc3K-0002iS-5e for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 18:43:18 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GMhIdH010435 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 18:43:18 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEbxn-0008BT-1H for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 18:37:35 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA16819 for ; Fri, 16 Apr 2004 18:37:30 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEbxj-0007Y4-Pl for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 18:37:31 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEbwe-0007UE-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 18:36:25 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEbvi-0007SG-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 18:35:26 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEboW-0004Fi-Uy; Fri, 16 Apr 2004 18:28:00 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEbhA-0002es-9r for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 18:20:24 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA15702 for ; Fri, 16 Apr 2004 18:20:20 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEbh7-0006Jm-Bf for cfrg@ietf.org; Fri, 16 Apr 2004 18:20:21 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEbgB-0006GY-00 for cfrg@ietf.org; Fri, 16 Apr 2004 18:19:23 -0400 Received: from [65.246.255.50] (helo=mx2.foretec.com) by ietf-mx with esmtp (Exim 4.12) id 1BEbfM-0006Cu-00 for cfrg@ietf.org; Fri, 16 Apr 2004 18:18:32 -0400 Received: from garie.qualcomm.com ([203.30.171.17]) by mx2.foretec.com with esmtp (Exim 4.24) id 1BEbfM-0006Ca-3H for cfrg@ietf.org; Fri, 16 Apr 2004 18:18:32 -0400 Received: from grose1.qualcomm.com ([1.1.1.4]) by garie.qualcomm.com (8.12.8/8.12.1/1.0) with ESMTP id i3GMHsQ4005438; Sat, 17 Apr 2004 08:17:55 +1000 Message-Id: <6.0.0.22.2.20040417080154.03cf7cb8@203.30.171.17> X-Sender: ggr2@203.30.171.17 X-Mailer: QUALCOMM Windows Eudora Version 6.0.0.22 Date: Sat, 17 Apr 2004 08:17:54 +1000 To: "The Purple Streak, Hilarie Orman" From: Greg Rose Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Cc: cfrg@ietf.org, florent.bersani@rd.francetelecom.fr In-Reply-To: <200404161943.i3GJhU2w011046@localhost.localdomain> References: <200404161943.i3GJhU2w011046@localhost.localdomain> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 At 01:43 PM 4/16/2004 -0600, The Purple Streak, Hilarie Orman wrote: >A 96-bit MAC will have a collision in about 2^48 usages. That seems too >high for many applications. If one can guarantee a key change reasonably >often, 96-bits is probably OK. While I agree with the correctness of your comment, I'm not at all sure that it represents a problem. For most usages of MACs, collisions simply aren't a threat. After all, a collision just means that the attacker gets to substitute a message that has the same MAC tag, when he was already able to substitute a (recorded) message that had a different MAC tag. Similarly, the probablility of a forgery succeeding doesn't depend on collisions, so a k-bit MAC still gives a 2^k protection. Of course if Florent had presented a threat analysis ;-), we might be able to tell whether collisions represent a threat or not. If they do, 96 bits is clearly inadequate. But I'd go so far as to say that in almost all cases collisions are not a threat to usage of MAC functions. >Why truncate a MAC at all? This is a murky area. If there is some >possibility of an attacker obtaininig information that constrains the >key space, truncation is a defense. But should this happen in a >Properly Designed System? I'd hope not. Agreed; truncation of a MAC is usually driven by bandwidth requirements, not cryptographic considerations. A MAC is pure overhead... >I think that without knowing the exact algorithm used to generate the >MAC, one cannot say much about whether or not truncation is a help or >hindrance. It is an interesting question for theorists, but I think >that IETF guidance should be that the value should not be truncated to >less than 128 bits unless there's a good reason, and in no case less >than 96 bits. Maybe. Attacks on MACs generally fall into two classes: 1. attacks that can be performed offline, on the NS... err... attacker's supercomputer farm. Brute forcing the key is the usual example, unless the underlying algorithm is badly broken. 2. Adaptive forgery attacks, which usually require oracle-style assistance from the entity being attacked. Now it's pretty much a given that I will not add server capacity to a machine that's dropping 99.9% of the incoming packets. I believe that, absent any algorithmic weakness, MACs can be much shorter and still provide a formidable barrier to attack. For example, the authentication MAC introduced in the old analog mobile phones was only 18 bits, but where used, it completely stopped all over-the-air fraudulent calls. (No, I'm not advocating only 18 bits; but there's a much better return on your investment buying lottery tickets, even at 18 bits. The brute-force attack on the 64-bit key was more likely to pay off, though.) For per-packet MACs, I think 96 bits is total overkill. For authentication, I'd go for the full 128 bits. Greg. Greg Rose INTERNET: ggr@qualcomm.com Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 18:52:41 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA17518 for ; Fri, 16 Apr 2004 18:52:41 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEc3M-0002jf-6l for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 18:43:20 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GMhKVT010507 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 18:43:20 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEbzo-0001In-93 for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 18:39:40 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA16942 for ; Fri, 16 Apr 2004 18:39:35 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEbzl-0007hP-5g for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 18:39:37 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEbyy-0007dz-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 18:38:48 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEbyA-0007aE-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 18:37:58 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEbsQ-0006Y2-SL; Fri, 16 Apr 2004 18:32:02 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEbm2-0003oq-P1 for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 18:25:26 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA15920 for ; Fri, 16 Apr 2004 18:25:22 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEblz-0006cA-Nz for cfrg@ietf.org; Fri, 16 Apr 2004 18:25:23 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEbl0-0006ZX-00 for cfrg@ietf.org; Fri, 16 Apr 2004 18:24:22 -0400 Received: from mail.esmartstart.com ([66.119.143.50] helo=mail.radioburst.com) by ietf-mx with esmtp (Exim 4.12) id 1BEbk7-0006WI-00 for cfrg@ietf.org; Fri, 16 Apr 2004 18:23:27 -0400 Received: from localhost.localdomain (dav.rfburst.com [209.90.91.153]) by mail.radioburst.com (8.12.8/8.12.8) with ESMTP id i3GMMZdC000530; Fri, 16 Apr 2004 16:22:36 -0600 Received: from localhost.localdomain (tobermory [127.0.0.1]) by localhost.localdomain (8.12.8/8.11.6) with ESMTP id i3GMGZIZ014963; Fri, 16 Apr 2004 16:16:36 -0600 Received: (from ho@localhost) by localhost.localdomain (8.12.8/8.12.8/Submit) id i3GMGYDZ014959; Fri, 16 Apr 2004 16:16:34 -0600 Date: Fri, 16 Apr 2004 16:16:34 -0600 Message-Id: <200404162216.i3GMGYDZ014959@localhost.localdomain> From: "The Purple Streak, Hilarie Orman" To: sfluhrer@cisco.com Cc: cfrg@ietf.org In-reply-to: Yourmessage Subject: Re: [Cfrg] MACs: to truncate or not to truncate? X-esmartscan-MailScanner: Found to be clean Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=AWL autolearn=no version=2.60 > What is the significance of a MAC collision? If the attacker knows that > two messages A and B were both generated by the sender and happen to have > the common MAC value M, what can he do with that information? An attacker could corrupt the integrity of a system by playing back a value in a context not expected by the victim. If the victim is using MACs as an index, he'll take the bogus value. This assumes the victim is not aware of the collision, because he only keeps a subset of the MACs. Hilarie _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 19:19:30 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id TAA19119 for ; Fri, 16 Apr 2004 19:19:30 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEcYa-0005Ba-7v for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 19:15:36 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3GNFac6019930 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 19:15:36 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEcTo-0003FU-I3 for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 19:10:40 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id TAA18544 for ; Fri, 16 Apr 2004 19:10:37 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEcTl-0001fw-AK for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 19:10:37 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEcT5-0001cp-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 19:09:55 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEcSR-0001Y9-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 19:09:15 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEcKT-0007oy-Q9; Fri, 16 Apr 2004 19:01:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEcEA-0005Rq-GQ for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 18:54:30 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA17608 for ; Fri, 16 Apr 2004 18:54:25 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEcE6-0000el-Ob for cfrg@ietf.org; Fri, 16 Apr 2004 18:54:26 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEcD6-0000aU-00 for cfrg@ietf.org; Fri, 16 Apr 2004 18:53:25 -0400 Received: from sj-iport-3-in.cisco.com ([171.71.176.72] helo=sj-iport-3.cisco.com) by ietf-mx with esmtp (Exim 4.12) id 1BEcCB-0000VY-00 for cfrg@ietf.org; Fri, 16 Apr 2004 18:52:27 -0400 Received: from sj-core-5.cisco.com (171.71.177.238) by sj-iport-3.cisco.com with ESMTP; 16 Apr 2004 15:02:46 +0000 Received: from mira-sjc5-b.cisco.com (IDENT:mirapoint@mira-sjc5-b.cisco.com [171.71.163.14]) by sj-core-5.cisco.com (8.12.10/8.12.6) with ESMTP id i3GMpt7t003612 for ; Fri, 16 Apr 2004 15:51:56 -0700 (PDT) Received: from [128.107.163.157] (dhcp-128-107-163-157.cisco.com [128.107.163.157]) by mira-sjc5-b.cisco.com (MOS 3.4.5-GR) with ESMTP id ASE33318; Fri, 16 Apr 2004 15:51:08 -0700 (PDT) Mime-Version: 1.0 (Apple Message framework v613) In-Reply-To: References: Content-Type: text/plain; charset=US-ASCII; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: "David A. McGrew" Date: Fri, 16 Apr 2004 15:51:58 -0700 To: cfrg@ietf.org X-Mailer: Apple Mail (2.613) Content-Transfer-Encoding: 7bit Subject: [Cfrg] Re: cfrg added to Gmane Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Hello, this is just an FYI: someone requested that CFRG be archived at Gmane, You can now get CFRG from their news server, or from their web interface. David On Apr 3, 2004, at 3:28 PM, Gmane Administrator wrote: > We have received a request for adding the cfrg@irtf.org mailing list > to the Gmane mail-to-news gateway/archive. A subscription request > message has been sent. If this is contrary to your wishes, please send > a mail to admin@gmane.org saying so, and the list will be removed from > Gmane. > > Gmane is a mail-to-news portal that never expires its messages. It > therefore also functions as a mailing list archive. It's a > bi-directional gateway, but Gmane verifies that its users' email > addresses are valid before passing the messages through the > news-to-mail gateway. (Groups can also be made "read-only", which > means that Gmane won't forward any messages at all to the mailing > list.) > > Gmane can encrypt addresses to make address harvesting difficult, and > heeds X-No-Archive and related headers. > > If you wish to import older archives into Gmane, send a message to > the Gmane administrators with the URL of a Unix mbox archive of the > mailing list. > > The following parameters are set for this mailing list: > > * Newsgroup name: gmane.ietf.irtf.cfrg > * Mailing list address: cfrg@irtf.org > * The gateway is bi-directional > * Address encryption is off > * Spam detection is on > * The list is described as: > "Crypto Forum Research Group" > * News URL: news://news.gmane.org/gmane.ietf.irtf.cfrg > * Web URL: http://news.gmane.org/gmane.ietf.irtf.cfrg > > This newsgroup will be created when the first message from the > mailing list arrives. > > For more information about the Gmane project, go to > . > > This request was handled by > Lars Magne Ingebrigtsen . > > _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 16 20:52:45 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA23795 for ; Fri, 16 Apr 2004 20:52:44 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEe3O-0000An-FD for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 20:51:30 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3H0pU73000656 for cfrg-archive@odin.ietf.org; Fri, 16 Apr 2004 20:51:30 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEdwg-0006qH-VO for cfrg-web-archive@optimus.ietf.org; Fri, 16 Apr 2004 20:44:34 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA23433 for ; Fri, 16 Apr 2004 20:44:32 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEdwe-00077f-Lj for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 20:44:32 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEdvh-00074G-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 20:43:34 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BEdus-00071P-00 for cfrg-web-archive@ietf.org; Fri, 16 Apr 2004 20:42:42 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEdrJ-0004h4-8G; Fri, 16 Apr 2004 20:39:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEc1e-0001eo-V6 for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 18:41:35 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA17116 for ; Fri, 16 Apr 2004 18:41:30 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEc1b-000013-T2 for cfrg@ietf.org; Fri, 16 Apr 2004 18:41:31 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEc0n-0007mB-00 for cfrg@ietf.org; Fri, 16 Apr 2004 18:40:41 -0400 Received: from centaur.acm.jhu.edu ([128.220.223.65] ident=postfix) by ietf-mx with esmtp (Exim 4.12) id 1BEc0K-0007im-00 for cfrg@ietf.org; Fri, 16 Apr 2004 18:40:12 -0400 Received: by centaur.acm.jhu.edu (Postfix, from userid 528) id 7F1063EBCD; Fri, 16 Apr 2004 22:40:07 +0000 (US/Eastern) Date: Fri, 16 Apr 2004 18:40:07 -0400 From: Jack Lloyd To: cfrg@ietf.org Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Message-ID: <20040416224007.GC32122@acm.jhu.edu> Mail-Followup-To: cfrg@ietf.org References: <200404162216.i3GMGYDZ014959@localhost.localdomain> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200404162216.i3GMGYDZ014959@localhost.localdomain> X-GPG-Key-ID: 4DCDF398 X-GPG-Key-Fingerprint: 2DD2 95F9 C7E3 A15E AF29 80E1 D6A9 A5B9 4DCD F398 Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 On Fri, Apr 16, 2004 at 04:16:34PM -0600, The Purple Streak, Hilarie Orman wrote: > > What is the significance of a MAC collision? If the attacker knows that > > two messages A and B were both generated by the sender and happen to have > > the common MAC value M, what can he do with that information? > > An attacker could corrupt the integrity of a system by playing back a > value in a context not expected by the victim. If the victim is using > MACs as an index, he'll take the bogus value. This assumes the victim > is not aware of the collision, because he only keeps a subset of > the MACs. How is this different from a simple message replay? -J _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Mon Apr 19 09:09:33 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA09261 for ; Mon, 19 Apr 2004 09:09:32 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFYTr-0000NK-Lc for cfrg-archive@odin.ietf.org; Mon, 19 Apr 2004 09:06:36 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3JD6ZjV001438 for cfrg-archive@odin.ietf.org; Mon, 19 Apr 2004 09:06:35 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFYOT-0007jP-Sh for cfrg-web-archive@optimus.ietf.org; Mon, 19 Apr 2004 09:01:02 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA08864 for ; Mon, 19 Apr 2004 09:00:59 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFYOS-0007dM-FV for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 09:01:00 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFYNX-0007QW-00 for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 09:00:03 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BFYNF-0007Dj-00 for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 08:59:45 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFYHi-0006HN-CC; Mon, 19 Apr 2004 08:54:02 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BEepp-0005gH-Ll for cfrg@optimus.ietf.org; Fri, 16 Apr 2004 21:41:33 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id VAA26251 for ; Fri, 16 Apr 2004 21:41:30 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BEepm-0003Al-Pu for cfrg@ietf.org; Fri, 16 Apr 2004 21:41:30 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BEeoo-000387-00 for cfrg@ietf.org; Fri, 16 Apr 2004 21:40:31 -0400 Received: from abraham.cs.berkeley.edu ([128.32.37.170]) by ietf-mx with esmtp (Exim 4.12) id 1BEenv-00035x-00 for cfrg@ietf.org; Fri, 16 Apr 2004 21:39:35 -0400 Received: from news by abraham.cs.berkeley.edu with local (Exim 4.21) id 1BEepo-0003FF-0m for cfrg@ietf.org; Fri, 16 Apr 2004 18:41:32 -0700 To: cfrg@ietf.org Path: not-for-mail From: daw@taverner.cs.berkeley.edu (David Wagner) Newsgroups: isaac.lists.ietf-cfrg Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Date: Sat, 17 Apr 2004 01:41:31 +0000 (UTC) Organization: University of California, Berkeley Lines: 10 Distribution: isaac Message-ID: References: <200404162216.i3GMGYDZ014959@localhost.localdomain> Reply-To: daw-usenet@taverner.cs.berkeley.edu (David Wagner) NNTP-Posting-Host: taverner.cs.berkeley.edu X-Trace: abraham.cs.berkeley.edu 1082166091 12434 128.32.153.228 (17 Apr 2004 01:41:31 GMT) X-Complaints-To: usenet@abraham.cs.berkeley.edu NNTP-Posting-Date: Sat, 17 Apr 2004 01:41:31 +0000 (UTC) X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Originator: daw@taverner.cs.berkeley.edu (David Wagner) Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 The Purple Streak, Hilarie Orman wrote: >An attacker could corrupt the integrity of a system by playing back a >value in a context not expected by the victim. That's only exploitable if the attacker can predict in advance which pair of messages will cause a collision. With an unkeyed hash, the attacker can predict. With a MAC, the attacker can't (at least, not using the standard birthday attack). Therefore, birthday attacks are not a problem for MACs. There is no problem with using a 96-bit MAC, if the MAC is otherwise secure. _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Mon Apr 19 09:11:41 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA09362 for ; Mon, 19 Apr 2004 09:11:41 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFYUV-0000de-Tc for cfrg-archive@odin.ietf.org; Mon, 19 Apr 2004 09:07:16 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3JD7F98002444 for cfrg-archive@odin.ietf.org; Mon, 19 Apr 2004 09:07:15 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFYQT-00087n-5j for cfrg-web-archive@optimus.ietf.org; Mon, 19 Apr 2004 09:03:05 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA08901 for ; Mon, 19 Apr 2004 09:03:02 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFYQR-0000Hb-L6 for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 09:03:03 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFYPU-00003f-00 for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 09:02:05 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BFYOy-0007eJ-00 for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 09:01:32 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFYHi-0006Ha-N0; Mon, 19 Apr 2004 08:54:02 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BExnO-0005Kk-7r for cfrg@optimus.ietf.org; Sat, 17 Apr 2004 17:56:18 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA28507 for ; Sat, 17 Apr 2004 17:56:13 -0400 (EDT) From: lstewart@acm.org Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BExnL-0006n4-Kc for cfrg@ietf.org; Sat, 17 Apr 2004 17:56:15 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BExmP-0006f4-00 for cfrg@ietf.org; Sat, 17 Apr 2004 17:55:17 -0400 Received: from win.lh.vix.com ([204.152.188.39]) by ietf-mx with esmtp (Exim 4.12) id 1BExlf-0006X8-00 for cfrg@ietf.org; Sat, 17 Apr 2004 17:54:31 -0400 Received: from alaska.stewart.org (pool-141-154-223-106.bos.east.verizon.net [141.154.223.106]) (authenticated) by win.lh.vix.com (8.11.6/8.11.6) with ESMTP id i3HNeTM22295 for ; Sat, 17 Apr 2004 19:40:30 -0400 Received: from localhost (localhost [127.0.0.1]) by alaska.stewart.org (Postfix) with ESMTP id 6D40BFBF0A for ; Sat, 17 Apr 2004 13:51:36 -0400 (EDT) X-Mailer: exmh version 2.5 07/13/2001 with nmh-1.0.4 To: cfrg@ietf.org Subject: Re: [Cfrg] MACs: to truncate or not to truncate? In-Reply-To: Your message of "Fri, 16 Apr 2004 18:40:07 EDT." <20040416224007.GC32122@acm.jhu.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Sat, 17 Apr 2004 13:51:36 -0400 Message-Id: <20040417175136.6D40BFBF0A@alaska.stewart.org> Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=1.0 required=5.0 tests=AWL,DATE_IN_PAST_03_06, NO_REAL_NAME autolearn=no version=2.60 Back in 1995 I helped design a system in which we used secret key MACs to validate URLs, so web clients couldn't mess with our servers' minds. We used 128 bit MACs, and XOR'd the halves together to get to 64 bits and XOR'd the halves again to get to 32 bits. Was that a bad design or just pointless? Was the result better or worse than truncating to 32 or 64 bits? We didn't expect to get more than 32 or 64 bits of protection. If it matters, we used MD5 with HMAC and 128 bit keys. -Larry _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Mon Apr 19 13:47:26 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA26978 for ; Mon, 19 Apr 2004 13:47:26 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFclp-0007vz-6b for cfrg-archive@odin.ietf.org; Mon, 19 Apr 2004 13:41:25 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3JHfP4i030497 for cfrg-archive@odin.ietf.org; Mon, 19 Apr 2004 13:41:25 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFcfx-0006Zs-F5 for cfrg-web-archive@optimus.ietf.org; Mon, 19 Apr 2004 13:35:21 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA26128 for ; Mon, 19 Apr 2004 13:35:17 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFcfv-00031S-AC for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 13:35:19 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFcfB-0002nC-00 for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 13:34:33 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BFceV-0002Xp-00 for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 13:33:51 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFcW0-00059K-32; Mon, 19 Apr 2004 13:25:04 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFcQL-0003mI-Me for cfrg@optimus.ietf.org; Mon, 19 Apr 2004 13:19:13 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA24733 for ; Mon, 19 Apr 2004 13:19:09 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFcQJ-0006Nj-JZ for cfrg@ietf.org; Mon, 19 Apr 2004 13:19:11 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFcPU-0006AJ-00 for cfrg@ietf.org; Mon, 19 Apr 2004 13:18:20 -0400 Received: from mail.esmartstart.com ([66.119.143.50] helo=mail.radioburst.com) by ietf-mx with esmtp (Exim 4.12) id 1BFcOf-0005ii-00 for cfrg@ietf.org; Mon, 19 Apr 2004 13:17:29 -0400 Received: from localhost.localdomain (dav.rfburst.com [209.90.91.153]) by mail.radioburst.com (8.12.8/8.12.8) with ESMTP id i3JHGkdC017780; Mon, 19 Apr 2004 11:16:47 -0600 Received: from localhost.localdomain (tobermory [127.0.0.1]) by localhost.localdomain (8.12.8/8.11.6) with ESMTP id i3JGHCDU018073; Mon, 19 Apr 2004 10:17:12 -0600 Received: (from ho@localhost) by localhost.localdomain (8.12.8/8.12.8/Submit) id i3JGHB8j018069; Mon, 19 Apr 2004 10:17:11 -0600 Date: Mon, 19 Apr 2004 10:17:11 -0600 Message-Id: <200404191617.i3JGHB8j018069@localhost.localdomain> From: "The Purple Streak, Hilarie Orman" To: daw@taverner.cs.berkeley.edu Cc: cfrg@ietf.org In-reply-to: Yourmessage Subject: Re: [Cfrg] MACs: to truncate or not to truncate? X-esmartscan-MailScanner: Found to be clean Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=AWL autolearn=no version=2.60 > The Purple Streak, Hilarie Orman wrote: > >An attacker could corrupt the integrity of a system by playing back a > >value in a context not expected by the victim. > That's only exploitable if the attacker can predict in advance which > pair of messages will cause a collision. With an unkeyed hash, the > attacker can predict. With a MAC, the attacker can't (at least, not > using the standard birthday attack). Therefore, birthday attacks are > not a problem for MACs. There is no problem with using a 96-bit MAC, > if the MAC is otherwise secure. Depends on what you mean by exploitable. Simply getting any invalid data accepted by the victim is enough to corrupt some systems. Hilarie _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Mon Apr 19 17:37:33 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA12159 for ; Mon, 19 Apr 2004 17:37:33 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFgJF-000508-Jm for cfrg-archive@odin.ietf.org; Mon, 19 Apr 2004 17:28:09 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3JLS9us019219 for cfrg-archive@odin.ietf.org; Mon, 19 Apr 2004 17:28:09 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFgFb-00040A-Bk for cfrg-web-archive@optimus.ietf.org; Mon, 19 Apr 2004 17:24:23 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA11539 for ; Mon, 19 Apr 2004 17:24:20 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFgFZ-0004it-1G for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 17:24:21 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFgEk-0004VX-00 for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 17:23:30 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BFgEK-0004Hf-00 for cfrg-web-archive@ietf.org; Mon, 19 Apr 2004 17:23:04 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFg5Z-0001wI-Nm; Mon, 19 Apr 2004 17:14:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFfrN-0005Fs-Hd for cfrg@optimus.ietf.org; Mon, 19 Apr 2004 16:59:21 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA09858 for ; Mon, 19 Apr 2004 16:59:18 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFfrL-0006Mb-Cw for cfrg@ietf.org; Mon, 19 Apr 2004 16:59:19 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFfqO-00067q-00 for cfrg@ietf.org; Mon, 19 Apr 2004 16:58:22 -0400 Received: from sj-iport-3-in.cisco.com ([171.71.176.72] helo=sj-iport-3.cisco.com) by ietf-mx with esmtp (Exim 4.12) id 1BFfpY-0005fG-00 for cfrg@ietf.org; Mon, 19 Apr 2004 16:57:28 -0400 Received: from sj-core-5.cisco.com (171.71.177.238) by sj-iport-3.cisco.com with ESMTP; 19 Apr 2004 13:08:21 +0000 Received: from mira-sjc5-b.cisco.com (IDENT:mirapoint@mira-sjc5-b.cisco.com [171.71.163.14]) by sj-core-5.cisco.com (8.12.10/8.12.6) with ESMTP id i3JKuu7t011925; Mon, 19 Apr 2004 13:56:56 -0700 (PDT) Received: from [10.34.251.98] (stealth-10-34-251-98.cisco.com [10.34.251.98]) by mira-sjc5-b.cisco.com (MOS 3.4.5-GR) with SMTP id ASF69068; Mon, 19 Apr 2004 13:56:08 -0700 (PDT) In-Reply-To: <200404191617.i3JGHB8j018069@localhost.localdomain> References: <200404191617.i3JGHB8j018069@localhost.localdomain> Mime-Version: 1.0 (Apple Message framework v613) Content-Type: text/plain; charset=US-ASCII; format=flowed Message-Id: <18B2944C-9244-11D8-997B-0003935495EC@cisco.com> Content-Transfer-Encoding: 7bit Cc: cfrg@ietf.org From: "David A. McGrew" Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Date: Mon, 19 Apr 2004 13:56:57 -0700 To: "The Purple Streak, Hilarie Orman" X-Mailer: Apple Mail (2.613) Content-Transfer-Encoding: 7bit Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=AWL autolearn=no version=2.60 Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Hilarie, I think that there's some confusion here because you have a model in mind that is different from the conventional one used with MACs; I mean the one in which there is a tag generation function and a tag verification function, and the latter takes as inputs the secret key, a message, an authentication tag, and maybe a nonce. If I understand you correctly, you have in mind a model in which an authentication tag is used as a 'shorthand' for the entire message. In this system, there wouldn't be a verification function, but instead a lookup function, which takes as inputs a key and an authentication tag, and which returns the message corresponding to the tag. Is this right? Such a system would require collision resistance, as you point out. But then again, it is different from the typical use of a MAC. David On Apr 19, 2004, at 9:17 AM, The Purple Streak, Hilarie Orman wrote: >> The Purple Streak, Hilarie Orman wrote: >>> An attacker could corrupt the integrity of a system by playing back a >>> value in a context not expected by the victim. > >> That's only exploitable if the attacker can predict in advance which >> pair of messages will cause a collision. With an unkeyed hash, the >> attacker can predict. With a MAC, the attacker can't (at least, not >> using the standard birthday attack). Therefore, birthday attacks are >> not a problem for MACs. There is no problem with using a 96-bit MAC, >> if the MAC is otherwise secure. > > Depends on what you mean by exploitable. Simply getting any invalid > data accepted by the victim is enough to corrupt some systems. > > Hilarie > > _______________________________________________ > Cfrg mailing list > Cfrg@ietf.org > https://www1.ietf.org/mailman/listinfo/cfrg > _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Tue Apr 20 09:36:19 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA17223 for ; Tue, 20 Apr 2004 09:36:19 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFvIH-0000nm-LO for cfrg-archive@odin.ietf.org; Tue, 20 Apr 2004 09:28:10 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3KDS9La003082 for cfrg-archive@odin.ietf.org; Tue, 20 Apr 2004 09:28:09 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFvGO-00007g-9U for cfrg-web-archive@optimus.ietf.org; Tue, 20 Apr 2004 09:26:12 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA16473 for ; Tue, 20 Apr 2004 09:26:09 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFvGM-0006eS-Kp for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 09:26:10 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFvFG-0006MQ-00 for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 09:25:03 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BFvEe-000673-00 for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 09:24:24 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFv7V-0004t5-Qc; Tue, 20 Apr 2004 09:17:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFgNJ-0005ZR-R3 for cfrg@optimus.ietf.org; Mon, 19 Apr 2004 17:32:21 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA11947 for ; Mon, 19 Apr 2004 17:32:18 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFgNH-0006Zs-6r for cfrg@ietf.org; Mon, 19 Apr 2004 17:32:19 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFgMI-0006MO-00 for cfrg@ietf.org; Mon, 19 Apr 2004 17:31:18 -0400 Received: from abraham.cs.berkeley.edu ([128.32.37.170]) by ietf-mx with esmtp (Exim 4.12) id 1BFgLQ-00068h-00 for cfrg@ietf.org; Mon, 19 Apr 2004 17:30:24 -0400 Received: from news by abraham.cs.berkeley.edu with local (Exim 4.21) id 1BFgNF-00050M-QI for cfrg@ietf.org; Mon, 19 Apr 2004 14:32:17 -0700 To: cfrg@ietf.org Path: not-for-mail From: daw@taverner.cs.berkeley.edu (David Wagner) Newsgroups: isaac.lists.ietf-cfrg Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Date: Mon, 19 Apr 2004 21:32:17 +0000 (UTC) Organization: University of California, Berkeley Lines: 27 Distribution: isaac Message-ID: References: <200404191617.i3JGHB8j018069@localhost.localdomain> Reply-To: daw-usenet@taverner.cs.berkeley.edu (David Wagner) NNTP-Posting-Host: taverner.cs.berkeley.edu X-Trace: abraham.cs.berkeley.edu 1082410337 18976 128.32.153.228 (19 Apr 2004 21:32:17 GMT) X-Complaints-To: usenet@abraham.cs.berkeley.edu NNTP-Posting-Date: Mon, 19 Apr 2004 21:32:17 +0000 (UTC) X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Originator: daw@taverner.cs.berkeley.edu (David Wagner) Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 The Purple Streak, Hilarie Orman wrote: >David Wagner writes: >> The Purple Streak, Hilarie Orman wrote: >> >An attacker could corrupt the integrity of a system by playing back a >> >value in a context not expected by the victim. > >> That's only exploitable if the attacker can predict in advance which >> pair of messages will cause a collision. > >Depends on what you mean by exploitable. Simply getting any invalid >data accepted by the victim is enough to corrupt some systems. No, it doesn't. Look, work out the details. Try it. You'll find that with a 96 bit MAC, there's no way an attacker can trick the victim into accepting invalid data, unless the attacker sends about 2^96 packets. Here's my definition of exploitable: If the receiver ever accepts (as valid) any data that was not actually transmitted or authorized by the sender, then the scheme is broken. This is a very conservative definition. For instance, if you can get the victim to accept invalid data, you've broken the MAC. And, even under this strong definition, birthday collisions pose no threat. Summary: Birthday attacks are not a problem. Truncating SHA1-HMAC to 96 bits is safe and reasonable. _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Tue Apr 20 09:45:32 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA17656 for ; Tue, 20 Apr 2004 09:45:32 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFvPk-0002R6-Cc for cfrg-archive@odin.ietf.org; Tue, 20 Apr 2004 09:35:54 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3KDZqnA009360 for cfrg-archive@odin.ietf.org; Tue, 20 Apr 2004 09:35:52 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFvIQ-0000oY-Rx for cfrg-web-archive@optimus.ietf.org; Tue, 20 Apr 2004 09:28:18 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA16704 for ; Tue, 20 Apr 2004 09:28:16 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFvIP-0007GP-5k for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 09:28:17 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFvHc-0006yi-00 for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 09:27:29 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BFvGb-0006fv-00 for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 09:26:25 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFv7W-0004u1-8U; Tue, 20 Apr 2004 09:17:02 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFphc-0001sY-S2 for cfrg@optimus.ietf.org; Tue, 20 Apr 2004 03:29:57 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id DAA28489 for ; Tue, 20 Apr 2004 03:29:55 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFpha-0003EK-H4 for cfrg@ietf.org; Tue, 20 Apr 2004 03:29:54 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFpga-0002yl-00 for cfrg@ietf.org; Tue, 20 Apr 2004 03:28:53 -0400 Received: from mail.netvista.net ([206.170.46.14] helo=degas.netvista.net) by ietf-mx with esmtp (Exim 4.12) id 1BFpgE-0002jO-00 for cfrg@ietf.org; Tue, 20 Apr 2004 03:28:30 -0400 Received: from alten.comcast.net (c-24-5-235-103.client.comcast.net [24.5.235.103]) (authenticated) by degas.netvista.net (8.11.6/8.11.6) with ESMTP id i3K7P0v21132; Tue, 20 Apr 2004 00:25:00 -0700 Message-Id: <4.3.2.7.1.20040420001138.03c36ed8@mail.netvista.net> X-Sender: alten@mail.netvista.net X-Mailer: QUALCOMM Windows Eudora Version 4.3.2 Date: Tue, 20 Apr 2004 00:30:05 -0700 To: Greg Rose , "The Purple Streak, Hilarie Orman" From: Alex Alten Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Cc: cfrg@ietf.org, florent.bersani@rd.francetelecom.fr In-Reply-To: <6.0.0.22.2.20040417080154.03cf7cb8@203.30.171.17> References: <200404161943.i3GJhU2w011046@localhost.localdomain> <200404161943.i3GJhU2w011046@localhost.localdomain> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-MailScanner: Found to be clean Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 At 08:17 AM 4/17/2004 +1000, Greg Rose wrote: >I believe that, absent any algorithmic weakness, MACs can be much shorter >and still provide a formidable barrier to attack. For example, the >authentication MAC introduced in the old analog mobile phones was only 18 >bits, but where used, it completely stopped all over-the-air fraudulent >calls. (No, I'm not advocating only 18 bits; but there's a much better >return on your investment buying lottery tickets, even at 18 bits. The >brute-force attack on the 64-bit key was more likely to pay off, though.) > >For per-packet MACs, I think 96 bits is total overkill. For >authentication, I'd go for the full 128 bits. Heck, 32 bits is probably more than good enough for a per-packet MAC, when it's in-flight life-time is usually less than a second. - Alex -- Alex Alten alten@EscalonNetworks.com 925-425-9601 _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Tue Apr 20 13:37:36 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA07073 for ; Tue, 20 Apr 2004 13:37:36 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFyyo-0004bC-NT for cfrg-archive@odin.ietf.org; Tue, 20 Apr 2004 13:24:18 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3KHOI5u017673 for cfrg-archive@odin.ietf.org; Tue, 20 Apr 2004 13:24:18 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFygU-0004QF-00 for cfrg-web-archive@optimus.ietf.org; Tue, 20 Apr 2004 13:05:22 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA04441 for ; Tue, 20 Apr 2004 13:05:18 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFygS-0000jF-6N for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 13:05:20 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFyfN-0000fi-00 for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 13:04:14 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BFyem-0000dJ-00 for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 13:03:36 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFyJt-0002E9-9s; Tue, 20 Apr 2004 12:42:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFwKC-0001Ld-TV for cfrg@optimus.ietf.org; Tue, 20 Apr 2004 10:34:13 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA21984 for ; Tue, 20 Apr 2004 10:34:09 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFwKA-0002nF-8t for cfrg@ietf.org; Tue, 20 Apr 2004 10:34:10 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFwJY-0002Xb-00 for cfrg@ietf.org; Tue, 20 Apr 2004 10:33:33 -0400 Received: from p-mail2.rd.francetelecom.com ([195.101.245.16]) by ietf-mx with esmtp (Exim 4.12) id 1BFwIf-0002FC-00 for cfrg@ietf.org; Tue, 20 Apr 2004 10:32:37 -0400 Received: from parmhs4.rd.francetelecom.fr ([10.193.117.63]) by parsmtp1.rd.francetelecom.com with Microsoft SMTPSVC(6.0.3790.0); Tue, 20 Apr 2004 16:32:10 +0200 Received: from rd.francetelecom.fr ([10.193.167.13]) by parmhs4.rd.francetelecom.fr with Microsoft SMTPSVC(5.0.2195.6747); Tue, 20 Apr 2004 16:32:09 +0200 Message-ID: <408534BB.5060807@rd.francetelecom.fr> Date: Tue, 20 Apr 2004 16:33:31 +0200 From: Florent Bersani User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.6b) Gecko/20031205 Thunderbird/0.4 X-Accept-Language: en-us, en MIME-Version: 1.0 To: lstewart@acm.org CC: cfrg@ietf.org Subject: Re: [Cfrg] MACs: to truncate or not to truncate? References: <20040417175136.6D40BFBF0A@alaska.stewart.org> In-Reply-To: <20040417175136.6D40BFBF0A@alaska.stewart.org> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 20 Apr 2004 14:32:09.0278 (UTC) FILETIME=[4310A5E0:01C426E4] Content-Transfer-Encoding: 7bit Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.1 required=5.0 tests=AWL autolearn=no version=2.60 Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Well, since I am (very) new to cryptography, please consider my reply with the utmost caution! (*) From a theoretical point of view, if you MAC is a PRF, then xor-folding will do no harm to this property, hence your MAC security bound (which is classically related to the PRF advantage, see e.g. Mihir Bellare, Joe Kilian, and Phillip Rogaway, "The security of the cipher block chaining message authentication code", Journal of Computer and System Sciences (JCSS), vol. 61, no. 3, Dec 2000, pp. 362-399. Earlier version in CRYPTO '94. Available at http://www.cs.ucdavis.edu/~rogaway/papers/index.html) will only degrade as if you truncated the MAC, i.e. AdcMAC <= AdvPRF + 2**(-taglength) From a practical point of view, I bet that the effect of your xor-folding regarding shortcut attacks (internal collision) is quite similar to truncation (making internal collision search require more chosen messages). Hope this helps, Florent (*) Two reasons made me reply: 1) No expert had replied so far 2) It is a good opportunity to see if I have started to understood my reading ;-) lstewart@acm.org wrote: >Back in 1995 I helped design a system in which we used secret key MACs to >validate URLs, so web clients couldn't mess with our servers' minds. >We used 128 bit MACs, and XOR'd the halves together to get to 64 bits >and XOR'd the halves again to get to 32 bits. Was that a bad design >or just pointless? Was the result better or worse than truncating to >32 or 64 bits? We didn't expect to get more than 32 or 64 bits of protection. > >If it matters, we used MD5 with HMAC and 128 bit keys. > >-Larry > > > >_______________________________________________ >Cfrg mailing list >Cfrg@ietf.org >https://www1.ietf.org/mailman/listinfo/cfrg > > > _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Tue Apr 20 14:38:06 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA11063 for ; Tue, 20 Apr 2004 14:38:06 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFzz6-0004S5-IF for cfrg-archive@odin.ietf.org; Tue, 20 Apr 2004 14:28:40 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3KISesL017113 for cfrg-archive@odin.ietf.org; Tue, 20 Apr 2004 14:28:40 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFzso-0001tE-KW for cfrg-web-archive@optimus.ietf.org; Tue, 20 Apr 2004 14:22:10 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA10017 for ; Tue, 20 Apr 2004 14:22:08 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFzsm-0005iz-4K for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 14:22:08 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFzrq-0005gZ-00 for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 14:21:11 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BFzrI-0005et-00 for cfrg-web-archive@ietf.org; Tue, 20 Apr 2004 14:20:36 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFzcC-0003UT-QC; Tue, 20 Apr 2004 14:05:00 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BFyVq-0000Fr-3G for cfrg@optimus.ietf.org; Tue, 20 Apr 2004 12:54:22 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA03665 for ; Tue, 20 Apr 2004 12:54:18 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BFyVo-00068T-8M for cfrg@ietf.org; Tue, 20 Apr 2004 12:54:20 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BFyUi-0005oa-00 for cfrg@ietf.org; Tue, 20 Apr 2004 12:53:12 -0400 Received: from abraham.cs.berkeley.edu ([128.32.37.170]) by ietf-mx with esmtp (Exim 4.12) id 1BFyTn-0005Ua-00 for cfrg@ietf.org; Tue, 20 Apr 2004 12:52:16 -0400 Received: from news by abraham.cs.berkeley.edu with local (Exim 4.21) id 1BFyVb-00063y-CH for cfrg@ietf.org; Tue, 20 Apr 2004 09:54:07 -0700 To: cfrg@ietf.org Path: not-for-mail From: daw@taverner.cs.berkeley.edu (David Wagner) Newsgroups: isaac.lists.ietf-cfrg Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Date: Tue, 20 Apr 2004 16:54:07 +0000 (UTC) Organization: University of California, Berkeley Lines: 11 Distribution: isaac Message-ID: References: <200404161943.i3GJhU2w011046@localhost.localdomain> <1A038D56-8FD2-11D8-9109-0003935495EC@cisco.com> <200404161943.i3GJhU2w011046@localhost.localdomain> <4.3.2.7.1.20040420001138.03c36ed8@mail.netvista.net> Reply-To: daw-usenet@taverner.cs.berkeley.edu (David Wagner) NNTP-Posting-Host: taverner.cs.berkeley.edu X-Trace: abraham.cs.berkeley.edu 1082480047 22863 128.32.153.228 (20 Apr 2004 16:54:07 GMT) X-Complaints-To: usenet@abraham.cs.berkeley.edu NNTP-Posting-Date: Tue, 20 Apr 2004 16:54:07 +0000 (UTC) X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Originator: daw@taverner.cs.berkeley.edu (David Wagner) Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 Alex Alten wrote: >Heck, 32 bits is probably more than good enough for a per-packet MAC, when >it's in-flight life-time is usually less than a second. The time-of-flight of a packet shouldn't matter. The relevant time constant is the lifetime of the system, measured in packets. If I can send 2^32 packets to your system within its lifetime, and if you use a 32-bit MAC, I can probably cause one invalid packet to be accepted. Either you do the security analysis to figure out whether that's acceptable, or you make your MAC large enough that you don't have to worry about invalid packets being accepted. _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Wed Apr 21 19:21:16 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id TAA29512 for ; Wed, 21 Apr 2004 19:21:16 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGQck-0001nh-Dd for cfrg-archive@odin.ietf.org; Wed, 21 Apr 2004 18:55:22 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3LMtM1q006912 for cfrg-archive@odin.ietf.org; Wed, 21 Apr 2004 18:55:22 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGQIc-0006Yi-Fe for cfrg-web-archive@optimus.ietf.org; Wed, 21 Apr 2004 18:34:34 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA25769 for ; Wed, 21 Apr 2004 18:34:29 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGQIZ-0002DH-B0 for cfrg-web-archive@ietf.org; Wed, 21 Apr 2004 18:34:31 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGQH8-0001jQ-00 for cfrg-web-archive@ietf.org; Wed, 21 Apr 2004 18:33:03 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BGQFi-0001KI-00 for cfrg-web-archive@ietf.org; Wed, 21 Apr 2004 18:31:34 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGPry-0003zr-Pj; Wed, 21 Apr 2004 18:07:02 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGP5y-0001Rn-AZ for cfrg@optimus.ietf.org; Wed, 21 Apr 2004 17:17:26 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA15026 for ; Wed, 21 Apr 2004 17:17:22 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGP5w-0000Fj-1P for cfrg@ietf.org; Wed, 21 Apr 2004 17:17:24 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGP4z-00001Y-00 for cfrg@ietf.org; Wed, 21 Apr 2004 17:16:25 -0400 Received: from av6-1-sn3.vrr.skanova.net ([81.228.9.179]) by ietf-mx with esmtp (Exim 4.12) id 1BGP45-0007QV-00 for cfrg@ietf.org; Wed, 21 Apr 2004 17:15:29 -0400 Received: by av6-1-sn3.vrr.skanova.net (Postfix, from userid 502) id 8C8AC37EB3; Wed, 21 Apr 2004 23:14:58 +0200 (CEST) Received: from smtp3-2-sn3.vrr.skanova.net (smtp3-2-sn3.vrr.skanova.net [81.228.9.102]) by av6-1-sn3.vrr.skanova.net (Postfix) with ESMTP id 7AB8E37E5B; Wed, 21 Apr 2004 23:14:58 +0200 (CEST) Received: from streamsec.se (h32n1fls31o985.telia.com [213.65.16.32]) by smtp3-2-sn3.vrr.skanova.net (Postfix) with ESMTP id 0A52B37E44; Wed, 21 Apr 2004 23:14:58 +0200 (CEST) Message-ID: <4086E453.9000504@streamsec.se> Date: Wed, 21 Apr 2004 23:14:59 +0200 From: =?ISO-8859-1?Q?Henrick_Hellstr=F6m?= Organization: StreamSec User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.6) Gecko/20040113 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Alex Alten Cc: cfrg@ietf.org Subject: Re: [Cfrg] MACs: to truncate or not to truncate? References: <4.3.2.7.1.20040420001138.03c36ed8@mail.netvista.net> <200404161943.i3GJhU2w011046@localhost.localdomain> <200404161943.i3GJhU2w011046@localhost.localdomain> <4.3.2.7.1.20040420001138.03c36ed8@mail.netvista.net> <4.3.2.7.1.20040421133551.0368fca8@mail.netvista.net> In-Reply-To: <4.3.2.7.1.20040421133551.0368fca8@mail.netvista.net> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=1.0 required=5.0 tests=NO_COST autolearn=no version=2.60 Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Alex Alten wrote: >> (1-2^-31) * v > 2^-31 * c >> >> where: >> >> v: the value of sending packets with a 32 bit MAC instead of a larger >> c: the expect loss associated with acceptance of a forge packet. > > > Unfortunately v and c are usually hard to specify with any precision. No, I don't think it is. Suppose, for instance, that I am sending bills to the head office over a DSL line and I pay a fixed amount each month to my ISP. The value of c is determined by the total amount we have on the account we use for paying these bills. The value of v is zero since there is no cost associated with the difference between using a 32 bit MAC and using a 128 bit MAC. The inequality is false. The inequality might have been true if I had used a dial-up connection. It would be fairly simple calculation to make. _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Thu Apr 22 10:03:20 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA27573 for ; Thu, 22 Apr 2004 10:03:20 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGekA-0006Oe-5u for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 09:59:58 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3MDxwcH024588 for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 09:59:58 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGePu-00011l-0M for cfrg-web-archive@optimus.ietf.org; Thu, 22 Apr 2004 09:39:02 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA26390 for ; Thu, 22 Apr 2004 09:38:54 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGePm-0000OG-Hw for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 09:38:54 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGeOu-00006v-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 09:38:00 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BGeNq-0007dU-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 09:36:54 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGeFF-0005nu-3x; Thu, 22 Apr 2004 09:28:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGaiO-0007Ci-Fn for cfrg@optimus.ietf.org; Thu, 22 Apr 2004 05:41:52 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id FAA14753 for ; Thu, 22 Apr 2004 05:41:46 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGaiJ-0003iP-44 for cfrg@ietf.org; Thu, 22 Apr 2004 05:41:47 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGahK-0003Tr-00 for cfrg@ietf.org; Thu, 22 Apr 2004 05:40:46 -0400 Received: from mail.netvista.net ([206.170.46.14] helo=degas.netvista.net) by ietf-mx with esmtp (Exim 4.12) id 1BGagX-0003ET-00 for cfrg@ietf.org; Thu, 22 Apr 2004 05:39:57 -0400 Received: from alten.comcast.net (c-24-5-235-103.client.comcast.net [24.5.235.103]) (authenticated) by degas.netvista.net (8.11.6/8.11.6) with ESMTP id i3M9af519835; Thu, 22 Apr 2004 02:36:41 -0700 Message-Id: <4.3.2.7.1.20040422020414.03ef4f88@mail.netvista.net> X-Sender: alten@mail.netvista.net X-Mailer: QUALCOMM Windows Eudora Version 4.3.2 Date: Thu, 22 Apr 2004 02:42:03 -0700 To: daw-usenet@taverner.cs.berkeley.edu (David Wagner) From: Alex Alten Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Cc: cfrg@ietf.org In-Reply-To: References: <200404161943.i3GJhU2w011046@localhost.localdomain> <1A038D56-8FD2-11D8-9109-0003935495EC@cisco.com> <200404161943.i3GJhU2w011046@localhost.localdomain> <4.3.2.7.1.20040420001138.03c36ed8@mail.netvista.net> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-MailScanner: Found to be clean Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 At 04:54 PM 4/20/2004 +0000, David Wagner wrote: >Alex Alten wrote: > >Heck, 32 bits is probably more than good enough for a per-packet MAC, when > >it's in-flight life-time is usually less than a second. > >The time-of-flight of a packet shouldn't matter. The relevant time >constant is the lifetime of the system, measured in packets. If I >can send 2^32 packets to your system within its lifetime, and if you >use a 32-bit MAC, I can probably cause one invalid packet to be accepted. >Either you do the security analysis to figure out whether that's acceptable, >or you make your MAC large enough that you don't have to worry about >invalid packets being accepted. Right. It's a a classic security vs engineering tradeoff. If one needs to protect 2^32 packets in the lifetime of the system then use a larger MAC. Otherwise don't transmit more than, say, 2^16 packets. -- Alex Alten alten@EscalonNetworks.com 925-425-9601 _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Thu Apr 22 10:04:07 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA27704 for ; Thu, 22 Apr 2004 10:04:07 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGekp-0006se-NO for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 10:00:39 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3ME0dQp026441 for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 10:00:39 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGeQu-0001T6-V1 for cfrg-web-archive@optimus.ietf.org; Thu, 22 Apr 2004 09:40:05 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA26447 for ; Thu, 22 Apr 2004 09:39:57 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGeQn-0000fZ-G7 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 09:39:57 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGePq-0000Os-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 09:38:59 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BGeP3-00008E-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 09:38:09 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGeGC-0006Ik-OB; Thu, 22 Apr 2004 09:29:00 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGOlO-0007Tv-DZ for cfrg@optimus.ietf.org; Wed, 21 Apr 2004 16:56:10 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA13767 for ; Wed, 21 Apr 2004 16:56:07 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGOlM-0003ig-B2 for cfrg@ietf.org; Wed, 21 Apr 2004 16:56:08 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGOkR-0003VU-00 for cfrg@ietf.org; Wed, 21 Apr 2004 16:55:12 -0400 Received: from mail.netvista.net ([206.170.46.14] helo=degas.netvista.net) by ietf-mx with esmtp (Exim 4.12) id 1BGOjS-00038C-00 for cfrg@ietf.org; Wed, 21 Apr 2004 16:54:10 -0400 Received: from alten.comcast.net (c-24-5-235-103.client.comcast.net [24.5.235.103]) (authenticated) by degas.netvista.net (8.11.6/8.11.6) with ESMTP id i3LKoa514360; Wed, 21 Apr 2004 13:50:36 -0700 Message-Id: <4.3.2.7.1.20040421133551.0368fca8@mail.netvista.net> X-Sender: alten@mail.netvista.net X-Mailer: QUALCOMM Windows Eudora Version 4.3.2 Date: Wed, 21 Apr 2004 13:55:54 -0700 To: Henrick =?iso-8859-1?Q?Hellstr=F6m?= From: Alex Alten Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Cc: cfrg@ietf.org In-Reply-To: <40852BF8.6070503@streamsec.se> References: <4.3.2.7.1.20040420001138.03c36ed8@mail.netvista.net> <200404161943.i3GJhU2w011046@localhost.localdomain> <200404161943.i3GJhU2w011046@localhost.localdomain> <4.3.2.7.1.20040420001138.03c36ed8@mail.netvista.net> Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1"; format=flowed Content-Transfer-Encoding: quoted-printable X-MailScanner: Found to be clean Content-Transfer-Encoding: quoted-printable Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 Content-Transfer-Encoding: quoted-printable Content-Transfer-Encoding: quoted-printable At 03:56 PM 4/20/2004 +0200, Henrick Hellstr=F6m wrote: >Alex Alten wrote: >>Heck, 32 bits is probably more than good enough for a per-packet MAC,=20 >>when it's in-flight life-time is usually less than a second. > >The "in-flight life-time" is irrelevant, given that a truncated MAC is=20 >used. The only question is if the following inequality is true: > > (1-2^-31) * v > 2^-31 * c > >where: > > v: the value of sending packets with a 32 bit MAC instead of a larger > c: the expect loss associated with acceptance of a forge packet. > >The thing is that v might be (practically) zero (if there are no direct=20 >transmission costs and transmission time is not an issue), and that=20 >entails that the inequality is false even if c is relatively small. Or in= =20 >plain English: If sending a 128 bit MAC isn't a problem, then just do it. Unfortunately v and c are usually hard to specify with any precision. If you are sending something like 10,000 packets per second down a TCP/IP data link, then a small MAC is ok, especially just for access control. Also a 128-bit MAC may cost too much time per packet or use up too much packet header space, the usual engieering vs security tradeoffs. - Alex -- Alex Alten alten@EscalonNetworks.com 925-425-9601 _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Thu Apr 22 10:41:55 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA01235 for ; Thu, 22 Apr 2004 10:41:54 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGfA6-00050O-3B for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 10:26:46 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3MEQkU7019236 for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 10:26:46 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGf6a-0003Cv-0R for cfrg-web-archive@optimus.ietf.org; Thu, 22 Apr 2004 10:23:08 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA29845 for ; Thu, 22 Apr 2004 10:23:00 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGf6R-00047A-UZ for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 10:23:00 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGf5d-0003ru-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 10:22:10 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BGf4q-0003d1-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 10:21:20 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGen6-0001If-W2; Thu, 22 Apr 2004 10:03:00 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGeeQ-00053U-5J for cfrg@optimus.ietf.org; Thu, 22 Apr 2004 09:54:02 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA27009 for ; Thu, 22 Apr 2004 09:53:54 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGeeI-0004Cc-Eu for cfrg@ietf.org; Thu, 22 Apr 2004 09:53:54 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGedH-0003wL-00 for cfrg@ietf.org; Thu, 22 Apr 2004 09:52:52 -0400 Received: from [65.246.255.50] (helo=mx2.foretec.com) by ietf-mx with esmtp (Exim 4.12) id 1BGecD-0003VL-00 for cfrg@ietf.org; Thu, 22 Apr 2004 09:51:45 -0400 Received: from garie.qualcomm.com ([203.30.171.17]) by mx2.foretec.com with esmtp (Exim 4.24) id 1BGecG-0004Z7-Cq for cfrg@ietf.org; Thu, 22 Apr 2004 09:51:48 -0400 Received: from grose1.qualcomm.com (pat-ras.qualcomm.com [129.46.54.33]) by garie.qualcomm.com (8.12.8/8.12.1/1.0) with ESMTP id i3MDp1Q4022757; Thu, 22 Apr 2004 23:51:05 +1000 Message-Id: <6.0.0.22.2.20040422234528.03e3ed90@203.30.171.17> X-Sender: ggr2@203.30.171.17 X-Mailer: QUALCOMM Windows Eudora Version 6.0.0.22 Date: Thu, 22 Apr 2004 23:50:59 +1000 To: Alex Alten From: Greg Rose Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Cc: daw-usenet@taverner.cs.berkeley.edu (David Wagner), cfrg@ietf.org In-Reply-To: <4.3.2.7.1.20040422020414.03ef4f88@mail.netvista.net> References: <200404161943.i3GJhU2w011046@localhost.localdomain> <1A038D56-8FD2-11D8-9109-0003935495EC@cisco.com> <200404161943.i3GJhU2w011046@localhost.localdomain> <4.3.2.7.1.20040420001138.03c36ed8@mail.netvista.net> <4.3.2.7.1.20040422020414.03ef4f88@mail.netvista.net> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 At 02:42 AM 4/22/2004 -0700, Alex Alten wrote: >Right. It's a a classic security vs engineering tradeoff. If one needs >to protect 2^32 >packets in the lifetime of the system then use a larger MAC. Otherwise don't >transmit more than, say, 2^16 packets. But you seem to have missed the whole thrust of the discussion... no such birthday limit applies. And anyway, "good" packets don't count. The lifetime of the system should be limited by the number of "bad" packets the attacker gets to send before being kneecapped; that's why ATM cards can get away with 4 digit PINs. If there's some way to throttle failed attempts, relatively small MACs might well suffice. That's why you need the threat analysis. Greg. Greg Rose INTERNET: ggr@qualcomm.com Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Thu Apr 22 12:30:59 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA08782 for ; Thu, 22 Apr 2004 12:30:58 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGh37-0001Jj-8k for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 12:27:41 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3MGRfc2005058 for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 12:27:41 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGghD-00020e-DV for cfrg-web-archive@optimus.ietf.org; Thu, 22 Apr 2004 12:05:03 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA07641 for ; Thu, 22 Apr 2004 12:04:59 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGgh9-0001Qj-Qv for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 12:04:59 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGggB-00019n-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 12:04:00 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BGgfC-0000sl-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 12:02:58 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGgTg-0006Fc-6G; Thu, 22 Apr 2004 11:51:04 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGgMq-0004Mz-Rp for cfrg@optimus.ietf.org; Thu, 22 Apr 2004 11:44:00 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA06433 for ; Thu, 22 Apr 2004 11:43:57 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGgMn-0003Up-JO for cfrg@ietf.org; Thu, 22 Apr 2004 11:43:57 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGgLq-0003Cv-00 for cfrg@ietf.org; Thu, 22 Apr 2004 11:42:59 -0400 Received: from ns.ca.certicom.com ([66.48.18.197] helo=mail.ca.certicom.com ident=postfix) by ietf-mx with esmtp (Exim 4.12) id 1BGgKt-0002uo-00 for cfrg@ietf.org; Thu, 22 Apr 2004 11:41:59 -0400 Received: from spamfilter.certicom.com (storm [127.0.0.1]) by mail.ca.certicom.com (Postfix) with ESMTP id 5366D10447; Thu, 22 Apr 2004 11:42:01 -0400 (EDT) Received: from mail.ca.certicom.com ([127.0.0.1]) by spamfilter.certicom.com (storm [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 08917-07; Thu, 22 Apr 2004 11:41:49 -0400 (EDT) Received: from certicom1.certicom.com (domino1.certicom.com [10.0.1.24]) by mail.ca.certicom.com (Postfix) with ESMTP id 95E0810295; Thu, 22 Apr 2004 11:41:49 -0400 (EDT) In-Reply-To: To: daw-usenet@taverner.cs.berkeley.edu (David Wagner) Cc: cfrg@ietf.org Subject: Re: [Cfrg] MACs: to truncate or not to truncate? MIME-Version: 1.0 X-Mailer: Lotus Notes Release 6.0.1 February 07, 2003 Message-ID: From: Daniel Brown Date: Thu, 22 Apr 2004 11:35:48 -0400 X-MIMETrack: Serialize by Router on Certicom1/Certicom(Release 6.0.1|February 07, 2003) at 04/22/2004 11:35:49 AM, Serialize complete at 04/22/2004 11:35:49 AM Content-Type: multipart/alternative; boundary="=_alternative 00563D8385256E7E_=" Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=HTML_MESSAGE autolearn=no version=2.60 This is a multipart message in MIME format. --=_alternative 00563D8385256E7E_= Content-Type: text/plain; charset="US-ASCII" David Wagner wrote on 04/19/2004 05:32:17 PM: > > Summary: Birthday attacks are not a problem. Truncating SHA1-HMAC > to 96 bits is safe and reasonable. > Just curious, can somebody summarize (again?) answers to: a) Are there any security advantages to truncating an (H)MAC value (say to 96 bits), or is it just a performance advantage? (I've seen arguments that not using all MAC bits hides something from some adversaries, is this so?) b) Is truncating to 80 bits also "safe and reasonable", just like 96 bits? c) When speaking of security levels, e.g. 80-bit vs 128-bit, what level does SHA1-HMAC-96 have? Does SHA1 limit security of HMAC to 80 bits? If not, does 96-bit truncation limit security to 96 bits? If not, does SHA1-HMAC-96 have 128 or 160 bits of security? d) In some schemes, e.g. DHAES and KEM-DEM, the MAC serves an auxiliary role to provide confidentiality, i.e. IND-CCA2 security. Extreme MAC truncating, say to 32 bits, undermines IND-CCA2 security, doesn't it? (Maybe IND-CCA1 is not affected?) Does this carry over to any other uses of a MAC? Thanks in advance, Dan --=_alternative 00563D8385256E7E_= Content-Type: text/html; charset="US-ASCII"
David Wagner wrote on 04/19/2004 05:32:17 PM:

>
> Summary: Birthday attacks are not a problem.  Truncating SHA1-HMAC
> to 96 bits is safe and reasonable.
>

Just curious, can somebody summarize (again?) answers to:

a) Are there any security advantages to truncating an (H)MAC value (say to 96 bits), or is it just a performance advantage?  (I've seen arguments that not using all MAC bits hides something from some adversaries, is this so?)

b) Is truncating to 80 bits also "safe and reasonable", just like 96 bits?

c) When speaking of security levels, e.g. 80-bit vs 128-bit, what level does SHA1-HMAC-96 have?  Does SHA1 limit security of HMAC to 80 bits? If not, does 96-bit truncation limit security to 96 bits?  If not, does SHA1-HMAC-96 have 128 or 160 bits of security?

d) In some schemes, e.g. DHAES and KEM-DEM, the MAC serves an auxiliary role to provide confidentiality, i.e. IND-CCA2 security.  Extreme MAC truncating, say to 32 bits, undermines IND-CCA2 security, doesn't it?  (Maybe IND-CCA1 is not affected?) Does this carry over to any other uses of a MAC?

Thanks in advance,

        Dan --=_alternative 00563D8385256E7E_=-- _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Thu Apr 22 13:15:38 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA11230 for ; Thu, 22 Apr 2004 13:15:38 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGhhx-0007IN-6q for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 13:09:53 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3MH9rX4028039 for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 13:09:53 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGhZ7-0004DZ-Rg for cfrg-web-archive@optimus.ietf.org; Thu, 22 Apr 2004 13:00:46 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA10660 for ; Thu, 22 Apr 2004 13:00:41 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGhZ3-0001I6-MC for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 13:00:41 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGhY8-0000yz-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 12:59:45 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BGhWz-0000eM-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 12:58:33 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGhOp-00019W-5z; Thu, 22 Apr 2004 12:50:07 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGhEG-0005Po-H6 for cfrg@optimus.ietf.org; Thu, 22 Apr 2004 12:39:12 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA09341 for ; Thu, 22 Apr 2004 12:39:08 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGhEC-00034f-Kd for cfrg@ietf.org; Thu, 22 Apr 2004 12:39:08 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGhDJ-0002mO-00 for cfrg@ietf.org; Thu, 22 Apr 2004 12:38:14 -0400 Received: from [66.228.74.116] (helo=OHTHREE.jjj-i.com) by ietf-mx with esmtp (Exim 4.12) id 1BGhCN-0002Bz-00 for cfrg@ietf.org; Thu, 22 Apr 2004 12:37:15 -0400 Received: by ohthree.jjj-i.com with Internet Mail Service (5.5.2657.72) id ; Thu, 22 Apr 2004 12:36:33 -0400 Message-ID: <30F37C4533D8564FB1D58BFDAF6687C1EA7812@ohthree.jjj-i.com> From: "Whyte, William" To: "'Daniel Brown'" , daw-usenet@taverner.cs.berkeley.edu Cc: cfrg@ietf.org Subject: RE: [Cfrg] MACs: to truncate or not to truncate? Date: Thu, 22 Apr 2004 12:36:32 -0400 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2657.72) Content-Type: text/plain; charset="iso-8859-1" Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 > a) Are there any security advantages to truncating an (H)MAC value > (say to 96 bits), or is it just a performance advantage? (I've seen > arguments that not using all MAC bits hides something from some > adversaries, is this so?) My understanding is that there is no significant security advantage to truncating an HMAC, although the folklore has it that there is. Consider messages A and B of the same length, such that the length is a multiple of the compression block size of the underlying hash function, and which produce the same MAC value M. Then an attacker can ask for the MAC on A || X, for any extension value X, and know that this will also be a MAC on B || X. The argument that truncating is more secure goes as follows: Say the internal chaining variable is of size k bits, and the output MAC is also k bits. Then after 2^k/2 messages there will be a collision, and the attacker will detect the collision by noting that the MACs are the same. However, if the output MAC is truncated to t bits, a collision in the MAC no longer necessarily indicates an internal collision. A MAC collision is necessary but not sufficient. The attacker will have to observe 2^k/2 messages, which will result in roughly 2^(k-t) pairwise collisions, and then make an extended-message query for each of those collisions. More work for the attacker ==> truncated MACs are more secure. (You can also argue that the attacker will send the victim 2^(k-t) messages, of which only one will be accepted, and that this will alert the victim to the fact that an attack's going on). I think that represents the "more secure" argument fairly, but it also shows why I don't really believe in it. There's an amount of additional work to be done by the attacker if the MAC is truncated. However, it never increases the total number of queries to the MAC oracle by a factor of more than 2. And the argument that a large number of fake MACs will alert the victim makes an assumption about the behaviour of the victim, which I don't think we can rely on. In summary: if the internal chaining value is of size k bits, I don't know of significant security advantages or disadvantages to truncating the MAC to any length between k and k/2. Cheers, William (willing to be corrected...) _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Thu Apr 22 17:31:47 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA02349 for ; Thu, 22 Apr 2004 17:31:47 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGkkM-0001bG-Dy for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 16:24:34 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3MKOYXM006148 for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 16:24:34 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGkJx-0006ti-06 for cfrg-web-archive@optimus.ietf.org; Thu, 22 Apr 2004 15:57:17 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA24265 for ; Thu, 22 Apr 2004 15:57:14 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGkJt-0005uw-FQ for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 15:57:13 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGkIp-0005ac-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 15:56:08 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BGkHo-00055o-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 15:55:04 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGjwT-0005Li-4W; Thu, 22 Apr 2004 15:33:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGizp-00081Y-2n for cfrg@optimus.ietf.org; Thu, 22 Apr 2004 14:32:25 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA16421 for ; Thu, 22 Apr 2004 14:32:21 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGizj-0004IH-Up for cfrg@ietf.org; Thu, 22 Apr 2004 14:32:20 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGiyY-0003zi-00 for cfrg@ietf.org; Thu, 22 Apr 2004 14:31:07 -0400 Received: from abraham.cs.berkeley.edu ([128.32.37.170]) by ietf-mx with esmtp (Exim 4.12) id 1BGixS-0003UW-00 for cfrg@ietf.org; Thu, 22 Apr 2004 14:29:58 -0400 Received: from news by abraham.cs.berkeley.edu with local (Exim 4.21) id 1BGizA-00028Q-Bb for cfrg@ietf.org; Thu, 22 Apr 2004 11:31:44 -0700 To: cfrg@ietf.org Path: not-for-mail From: daw@taverner.cs.berkeley.edu (David Wagner) Newsgroups: isaac.lists.ietf-cfrg Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Date: Thu, 22 Apr 2004 18:31:44 +0000 (UTC) Organization: University of California, Berkeley Lines: 10 Distribution: isaac Message-ID: References: <30F37C4533D8564FB1D58BFDAF6687C1EA7812@ohthree.jjj-i.com> Reply-To: daw-usenet@taverner.cs.berkeley.edu (David Wagner) NNTP-Posting-Host: taverner.cs.berkeley.edu X-Trace: abraham.cs.berkeley.edu 1082658704 8131 128.32.153.228 (22 Apr 2004 18:31:44 GMT) X-Complaints-To: usenet@abraham.cs.berkeley.edu NNTP-Posting-Date: Thu, 22 Apr 2004 18:31:44 +0000 (UTC) X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Originator: daw@taverner.cs.berkeley.edu (David Wagner) Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 Whyte, William wrote: >I think that represents the "more secure" argument fairly, but >it also shows why I don't really believe in it. [...] >In summary: if the internal chaining value is of size k bits, I >don't know of significant security advantages or disadvantages >to truncating the MAC to any length between k and k/2. For whatever it's worth, I agree with you. I don't see any security advantages or disadvantages to truncating. (There may well be performance advantages to truncation, of course.) _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Thu Apr 22 17:42:09 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA03025 for ; Thu, 22 Apr 2004 17:42:09 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGlNv-0004uO-6U for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 17:05:27 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3ML5Rkb018861 for cfrg-archive@odin.ietf.org; Thu, 22 Apr 2004 17:05:27 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGkKs-00076c-AV for cfrg-web-archive@optimus.ietf.org; Thu, 22 Apr 2004 15:58:14 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA24424 for ; Thu, 22 Apr 2004 15:58:11 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGkKo-0006GQ-SQ for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 15:58:10 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGkJo-0005uC-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 15:57:09 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BGkIk-0005RH-00 for cfrg-web-archive@ietf.org; Thu, 22 Apr 2004 15:56:02 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGjwT-0005Lq-Ep; Thu, 22 Apr 2004 15:33:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BGj9G-0002aP-4A for cfrg@optimus.ietf.org; Thu, 22 Apr 2004 14:42:10 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA16848 for ; Thu, 22 Apr 2004 14:42:06 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BGj9B-0006yR-Ce for cfrg@ietf.org; Thu, 22 Apr 2004 14:42:05 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BGj8C-0006gl-00 for cfrg@ietf.org; Thu, 22 Apr 2004 14:41:04 -0400 Received: from abraham.cs.berkeley.edu ([128.32.37.170]) by ietf-mx with esmtp (Exim 4.12) id 1BGj79-0006GG-00 for cfrg@ietf.org; Thu, 22 Apr 2004 14:39:59 -0400 Received: from news by abraham.cs.berkeley.edu with local (Exim 4.21) id 1BGj8x-0002HN-68 for cfrg@ietf.org; Thu, 22 Apr 2004 11:41:51 -0700 To: cfrg@ietf.org Path: not-for-mail From: daw@taverner.cs.berkeley.edu (David Wagner) Newsgroups: isaac.lists.ietf-cfrg Subject: Re: [Cfrg] MACs: to truncate or not to truncate? Date: Thu, 22 Apr 2004 18:41:51 +0000 (UTC) Organization: University of California, Berkeley Lines: 58 Distribution: isaac Message-ID: References: Reply-To: daw-usenet@taverner.cs.berkeley.edu (David Wagner) NNTP-Posting-Host: taverner.cs.berkeley.edu X-Trace: abraham.cs.berkeley.edu 1082659311 8764 128.32.153.228 (22 Apr 2004 18:41:51 GMT) X-Complaints-To: usenet@abraham.cs.berkeley.edu NNTP-Posting-Date: Thu, 22 Apr 2004 18:41:51 +0000 (UTC) X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Originator: daw@taverner.cs.berkeley.edu (David Wagner) Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 Ok, here are my opinions. Daniel Brown wrote: >a) Are there any security advantages to truncating an (H)MAC value (say to >96 bits), or is it just a performance advantage? I don't know of any significant security advantages to truncating SHA1-HMAC, assuming SHA1 has no weaknesses. (If SHA1 does have weaknesses, we should change hash functions, not try to patch it up with truncation.) >b) Is truncating to 80 bits also "safe and reasonable", just like 96 bits? It is as safe and reasonable as any ideal 80-bit MAC. If an 80-bit MAC is good enough for your application, then SHA1-HMAC-80 should be good enough. As you know, if you shorten the MAC too much, it will become feasible to forge packets. The exact length needed will depend on a detailed threat analysis of your particular system. >c) When speaking of security levels, e.g. 80-bit vs 128-bit, what level >does SHA1-HMAC-96 have? Does SHA1 limit security of HMAC to 80 bits? If >not, does 96-bit truncation limit security to 96 bits? If not, does >SHA1-HMAC-96 have 128 or 160 bits of security? What do you mean by "security level"? Some might consider the notion of a "security level" a little bit of an oversimplification. Anyway, the answer will depend on what kind of attack you're worried about. Let me assume you're using SHA1-HMAC-96 with a 160-bit key. Then the best key-recovery attack known takes about 2^160 work. The best message-forgery attack known needs to send about 2^96 packets. So, if I had to pick a number, I'd say that calling it "96-bit security" probably is the least distortion. But, that doesn't mean that you can directly compare SHA1-HMAC-40 to a scheme with a 40-bit key. 2^40 offline trial encryptions may well be a lot cheaper to perform than sending 2^40 packets, so SHA1-HMAC-40 (with a 160-bit key) might be stronger than a scheme with a 40-bit key. >d) In some schemes, e.g. DHAES and KEM-DEM, the MAC serves an auxiliary >role to provide confidentiality, i.e. IND-CCA2 security. Extreme MAC >truncating, say to 32 bits, undermines IND-CCA2 security, doesn't it? Yes. >Does this carry over to any other uses of a MAC? Yes. Almost any time you want confidentiality, you really need a MAC (whether you realize it or not). Therefore, truncating the MAC will likely undermine confidentiality. For instance, IPSec requires that if you use encryption, you should also use a MAC. That's for a very good reason: Bellovin found all sorts of nasty attacks if you omit the MAC. Therefore, truncating IPSec's MAC to, say, 32 bits would be a real mistake; it would put both integrity and confidentiality at risk. _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Fri Apr 23 18:15:29 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA17811 for ; Fri, 23 Apr 2004 18:15:29 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BH8ll-0007km-QF for cfrg-archive@odin.ietf.org; Fri, 23 Apr 2004 18:03:38 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3NM3boM029800 for cfrg-archive@odin.ietf.org; Fri, 23 Apr 2004 18:03:37 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BH8c2-0002KI-GC for cfrg-web-archive@optimus.ietf.org; Fri, 23 Apr 2004 17:53:34 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA15812 for ; Fri, 23 Apr 2004 17:53:30 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BH8bz-00060C-VZ for cfrg-web-archive@ietf.org; Fri, 23 Apr 2004 17:53:31 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BH8ax-0005iK-00 for cfrg-web-archive@ietf.org; Fri, 23 Apr 2004 17:52:28 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BH8a6-0005SS-00 for cfrg-web-archive@ietf.org; Fri, 23 Apr 2004 17:51:34 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BH8N7-0004VZ-QF; Fri, 23 Apr 2004 17:38:09 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BH882-0006kR-3q for cfrg@optimus.ietf.org; Fri, 23 Apr 2004 17:22:34 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA13707 for ; Fri, 23 Apr 2004 17:22:30 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BH87z-0005Dm-Nv for cfrg@ietf.org; Fri, 23 Apr 2004 17:22:31 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BH86N-0004oD-00 for cfrg@ietf.org; Fri, 23 Apr 2004 17:20:53 -0400 Received: from ns.ca.certicom.com ([66.48.18.197] helo=mail.ca.certicom.com ident=postfix) by ietf-mx with esmtp (Exim 4.12) id 1BH83d-0003yS-00 for cfrg@ietf.org; Fri, 23 Apr 2004 17:18:01 -0400 Received: from spamfilter.certicom.com (storm [127.0.0.1]) by mail.ca.certicom.com (Postfix) with ESMTP id D3D431022B; Fri, 23 Apr 2004 17:18:01 -0400 (EDT) Received: from mail.ca.certicom.com ([127.0.0.1]) by spamfilter.certicom.com (storm [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 31232-61; Fri, 23 Apr 2004 17:17:49 -0400 (EDT) Received: from certicom1.certicom.com (domino1.certicom.com [10.0.1.24]) by mail.ca.certicom.com (Postfix) with ESMTP id 3390E100F8; Fri, 23 Apr 2004 17:17:49 -0400 (EDT) In-Reply-To: To: daw-usenet@taverner.cs.berkeley.edu (David Wagner) Cc: cfrg@ietf.org Subject: Re: [Cfrg] MACs: to truncate or not to truncate? MIME-Version: 1.0 X-Mailer: Lotus Notes Release 6.0.1 February 07, 2003 Message-ID: From: Daniel Brown Date: Fri, 23 Apr 2004 17:11:46 -0400 X-MIMETrack: Serialize by Router on Certicom1/Certicom(Release 6.0.1|February 07, 2003) at 04/23/2004 05:11:47 PM, Serialize complete at 04/23/2004 05:11:47 PM Content-Type: multipart/alternative; boundary="=_alternative 0075002D85256E7F_=" Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=HTML_MESSAGE autolearn=no version=2.60 This is a multipart message in MIME format. --=_alternative 0075002D85256E7F_= Content-Type: text/plain; charset="US-ASCII" David, William: thanks so much for the answers. I have more questions. David Wagner wrote on 04/22/2004 02:41:51 PM: > > >c) When speaking of security levels, e.g. 80-bit vs 128-bit, what level > >does SHA1-HMAC-96 have? Does SHA1 limit security of HMAC to 80 bits? If > >not, does 96-bit truncation limit security to 96 bits? If not, does > >SHA1-HMAC-96 have 128 or 160 bits of security? > > What do you mean by "security level"? Some might consider the notion of a > "security level" a little bit of an oversimplification. > > Anyway, the answer will depend on what kind of attack you're worried > about. Let me assume you're using SHA1-HMAC-96 with a 160-bit key. > Then the best key-recovery attack known takes about 2^160 work. The best > message-forgery attack known needs to send about 2^96 packets. So, > if I had to pick a number, I'd say that calling it "96-bit security" > probably is the least distortion. Is it fair to extend your reasoning to say that HMAC-SHA1-160 has "160-bit security" and HMAC-SHA1-80 has "80-bit security"? If so, does HMAC-SHA1-80 with AES-128 undermine 128-bit confidentiality, whereas HMAC-SHA1-160 does not? William's attack on HMAC-SHA1-160 uses only 2^80 MAC generation queries to find a MAC forgery, right? If so, does HMAC-SHA1-160 have at most "80-bit security"? Or, can we use a different "exchange rate" for online queries, so that the 2^80 MAC generation queries are regarded as a "160-bit" cost in the attack? The security level of HMAC-SHA1 may well depend on the "exchange rate" between off-line and on-line work (as well as MAC generation vs verification queries, and treatment of failed verifications), but wouldn't a conservative, and maybe "oversimplified", answer would take the worst security rating over all exchange rates? I agree that a more aggressive rating could be used with application-specific detailed threat analysis. Has anybody ever formally studied the security of HMAC-SHA1-80 vs HMAC-SHA1-160, or is it just "folklore" that one is better than, as good as, or worse than the other? Anyway, am I right to infer that "80-bit security" is the most conservative rating for both HMAC-SHA1-80 and HMAC-SHA1-160? What's the most conservative rating for HMAC-SHA1-96 or HMAC-SHA1-128? What are the ratings under other "reasonable", but more aggressive, exchange rates? Is there a simple characterization of some useful situations when these more aggressive ratings are safe to use (instead of going through an analysis for every application)? > > >Does this carry over to any other uses of a MAC? > > Yes. Almost any time you want confidentiality, you really need a MAC > (whether you realize it or not). Therefore, truncating the MAC will > likely undermine confidentiality. > > For instance, IPSec requires that if you use encryption, you should also > use a MAC. That's for a very good reason: Bellovin found all sorts of > nasty attacks if you omit the MAC. Therefore, truncating IPSec's MAC to, > say, 32 bits would be a real mistake; it would put both integrity and > confidentiality at risk. > So, the suggestions on this mailing list to a 32-bit MAC for per-packet protection may be inappropriate if the packet payloads are encrypted, but may be fine if the packets are plaintext? --=_alternative 0075002D85256E7F_= Content-Type: text/html; charset="US-ASCII"
David, William: thanks so much for the answers.  

I have more questions.

David Wagner wrote on 04/22/2004 02:41:51 PM:

>
> >c) When speaking of security levels, e.g. 80-bit vs 128-bit, what level
> >does SHA1-HMAC-96 have?  Does SHA1 limit security of HMAC to 80 bits? If
> >not, does 96-bit truncation limit security to 96 bits?  If not, does
> >SHA1-HMAC-96 have 128 or 160 bits of security?
>
> What do you mean by "security level"?  Some might consider the notion of a
> "security level" a little bit of an oversimplification.
>
> Anyway, the answer will depend on what kind of attack you're worried
> about.  Let me assume you're using SHA1-HMAC-96 with a 160-bit key.
> Then the best key-recovery attack known takes about 2^160 work.  The best
> message-forgery attack known needs to send about 2^96 packets.  So,
> if I had to pick a number, I'd say that calling it "96-bit security"
> probably is the least distortion.
Is it fair to extend your reasoning to say that HMAC-SHA1-160 has "160-bit security" and HMAC-SHA1-80 has "80-bit security"? If so, does HMAC-SHA1-80 with AES-128 undermine 128-bit confidentiality, whereas HMAC-SHA1-160 does not?

William's attack on HMAC-SHA1-160 uses only 2^80 MAC generation queries to find a MAC forgery, right? If so,  does HMAC-SHA1-160 have at most "80-bit security"?  Or, can we use a different "exchange rate" for online queries, so that the 2^80 MAC generation queries are regarded as a "160-bit" cost in the attack?

The security level of HMAC-SHA1 may well depend on the "exchange rate" between off-line and on-line work (as well as MAC generation vs verification queries, and treatment of failed verifications), but wouldn't a conservative, and maybe "oversimplified", answer would take the worst security rating over all exchange rates?  I agree that a more aggressive rating could be used with application-specific detailed threat analysis.

Has anybody ever formally studied the security of HMAC-SHA1-80 vs HMAC-SHA1-160, or is it just "folklore" that one is better than, as good as, or worse than the other?

Anyway, am I right to infer that "80-bit security" is the most conservative rating for both HMAC-SHA1-80 and HMAC-SHA1-160?  What's the most conservative rating for HMAC-SHA1-96 or HMAC-SHA1-128?  What are the ratings under other "reasonable", but more aggressive, exchange rates? Is there a simple characterization of some useful situations when these more aggressive ratings are safe to use (instead of going through an analysis for every application)?

>
> >Does this carry over to any other uses of a MAC?
>
> Yes.  Almost any time you want confidentiality, you really need a MAC
> (whether you realize it or not).  Therefore, truncating the MAC will
> likely undermine confidentiality.
>
> For instance, IPSec requires that if you use encryption, you should also
> use a MAC.  That's for a very good reason: Bellovin found all sorts of
> nasty attacks if you omit the MAC.  Therefore, truncating IPSec's MAC to,
> say, 32 bits would be a real mistake; it would put both integrity and
> confidentiality at risk.
>

So, the suggestions on this mailing list to a 32-bit MAC for per-packet protection may be inappropriate if the packet payloads are encrypted, but may be fine if the packets are plaintext?

--=_alternative 0075002D85256E7F_=-- _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From exim@www1.ietf.org Mon Apr 26 16:46:13 2004 Received: from optimus.ietf.org (optimus.ietf.org [132.151.1.19]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA18185 for ; Mon, 26 Apr 2004 16:46:13 -0400 (EDT) Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BICEK-0005tD-0P for cfrg-archive@odin.ietf.org; Mon, 26 Apr 2004 15:57:31 -0400 Received: (from exim@localhost) by www1.ietf.org (8.12.8/8.12.8/Submit) id i3QJvR6U022634 for cfrg-archive@odin.ietf.org; Mon, 26 Apr 2004 15:57:27 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BIBpu-0000aE-NP for cfrg-web-archive@optimus.ietf.org; Mon, 26 Apr 2004 15:32:14 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA13674 for ; Mon, 26 Apr 2004 15:32:12 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BIBpt-0001KR-B4 for cfrg-web-archive@ietf.org; Mon, 26 Apr 2004 15:32:13 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BIBot-0001H9-00 for cfrg-web-archive@ietf.org; Mon, 26 Apr 2004 15:31:12 -0400 Received: from optimus.ietf.org ([132.151.1.19]) by ietf-mx with esmtp (Exim 4.12) id 1BIBoS-0001FI-00 for cfrg-web-archive@ietf.org; Mon, 26 Apr 2004 15:30:44 -0400 Received: from localhost.localdomain ([127.0.0.1] helo=www1.ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BIBe7-0007PL-K3; Mon, 26 Apr 2004 15:20:03 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by optimus.ietf.org with esmtp (Exim 4.20) id 1BIBZd-0005jZ-PB for cfrg@optimus.ietf.org; Mon, 26 Apr 2004 15:15:26 -0400 Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA12104 for ; Mon, 26 Apr 2004 15:15:23 -0400 (EDT) Received: from ietf-mx.ietf.org ([132.151.6.1] helo=ietf-mx) by ietf-mx with esmtp (Exim 4.32) id 1BIBZc-0000OB-E2 for cfrg@ietf.org; Mon, 26 Apr 2004 15:15:24 -0400 Received: from exim by ietf-mx with spam-scanned (Exim 4.12) id 1BIBYc-0000Jn-00 for cfrg@ietf.org; Mon, 26 Apr 2004 15:14:22 -0400 Received: from [66.228.74.116] (helo=OHTHREE.jjj-i.com) by ietf-mx with esmtp (Exim 4.12) id 1BIBYC-0000Fu-00 for cfrg@ietf.org; Mon, 26 Apr 2004 15:13:57 -0400 Received: by ohthree.jjj-i.com with Internet Mail Service (5.5.2657.72) id ; Mon, 26 Apr 2004 15:13:05 -0400 Message-ID: <30F37C4533D8564FB1D58BFDAF6687C1EA7837@ohthree.jjj-i.com> From: "Whyte, William" To: "'Daniel Brown'" , daw-usenet@taverner.cs.berkeley.edu Cc: cfrg@ietf.org Subject: RE: [Cfrg] MACs: to truncate or not to truncate? Date: Mon, 26 Apr 2004 15:13:04 -0400 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2657.72) Content-Type: text/plain; charset="iso-8859-1" Sender: cfrg-admin@ietf.org Errors-To: cfrg-admin@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.0.12 Precedence: bulk List-Unsubscribe: , List-Id: Crypto Forum Research Group List-Post: List-Help: List-Subscribe: , X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on ietf-mx.ietf.org X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 Hi Dan, > William's attack on HMAC-SHA1-160 uses only 2^80 MAC generation queries > to find a MAC forgery, right? If so, does HMAC-SHA1-160 have at most > "80-bit security"? Or, can we use a different "exchange rate" for > online queries, so that the 2^80 MAC generation queries are regarded as > a "160-bit" cost in the attack? > The security level of HMAC-SHA1 may well depend on the "exchange rate" > between off-line and on-line work (as well as MAC generation vs > verification queries, and treatment of failed verifications), but > wouldn't a conservative, and maybe "oversimplified", answer would take > the worst security rating over all exchange rates? I agree that a more > aggressive rating could be used with application-specific detailed > threat analysis. I'd say that it's reasonable under certain circumstances to assume a different (and higher) cost for MAC generation queries than for offline queries. But I'd always treat MAC verification queries as essentially free -- the sender has no guaratee over how the receiver will treat a failed message. The most conservative estimate of security might cap the strength at 80 bits. I think if it can be guaranteed that key lifetime will be less than a certain amount, the security can be considered higher. For example, if key lifetime is 2^16 messages, there's only a (roughly) 2^-128 chance of an internal collision. It seems reasonable to use HMAC-SHA1-128 or HMAC-SHA1-160 for 128-bit security under these circumstances. > Has anybody ever formally studied the security of HMAC-SHA1-80 vs > HMAC-SHA1-160, or is it just "folklore" that one is better than, as > good as, or worse than the other? I have a memory of seeing this addressed somewhere -- I thought by Bellare and Rogaway, but I can't track it down. There's surprisingly little discussion of the effect of truncation in the literature. > Anyway, am I right to infer that "80-bit security" is the most > conservative rating for both HMAC-SHA1-80 and HMAC-SHA1-160? > What's the most conservative rating for HMAC-SHA1-96 or HMAC-SHA1-128? > What are the ratings under other "reasonable", but more aggressive, > exchange rates? Is there a simple characterization of some useful > situations when these more aggressive ratings are safe to use (instead > of going through an analysis for every application)? 80-bit security is the most conservative rating for all of them. For 96-bit or 128-bit MACs, the attacker has to make attempts to get a MAC accepted that are unlikely to succeed, but he never has to make more than 2^80 of them. > So, the suggestions on this mailing list to a 32-bit MAC for per-packet > protection may be inappropriate if the packet payloads are encrypted, > but may be fine if the packets are plaintext? Interesting take on it. In either case, the attacker wants to have a forged packet be accepted, and the chance of this happening is (essentially) 2^-32. If the encryption scheme is CBC-pad + 32-bit MAC, and if the decrypting side throws an error that distinguishes between MAC failure and unpadding failure (as in Vaudenay's Eurocrypt attack, http://lasecwww.epfl.ch/php_code/publications/search.php?ref=Vau02a), then the attacker can mount Vaudenay's attack, at 2^32 times more effort than the raw attack would take, and the short MAC compromises confidentiality. So, yes, in certain circumstances a short MAC seems less suited to encrypted packets than to plaintext packets. But my feeling is that this is simply an illustration of the risks of short MACs, rather than a difference in the requirements of plaintexts and ciphertexts. Say you had nuclear launch codes unencrypted, but authenticated with a 32-bit MAC, for instance... I think short MACs are pretty scary full stop. Cheers, William _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg