From cfrg-bounces@ietf.org Fri Sep 09 19:03:15 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EDrtr-0004Gd-3S; Fri, 09 Sep 2005 19:03:15 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EDrtp-0004GR-6J for cfrg@megatron.ietf.org; Fri, 09 Sep 2005 19:03:13 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id TAA17885 for ; Fri, 9 Sep 2005 19:03:10 -0400 (EDT) Received: from woodstock.binhost.com ([144.202.243.4]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1EDrxT-0004qB-QN for cfrg@ietf.org; Fri, 09 Sep 2005 19:07:01 -0400 Received: (qmail 2758 invoked by uid 0); 9 Sep 2005 23:02:51 -0000 Received: from unknown (HELO Russ-Laptop.vigilsec.com) (151.200.237.96) by woodstock.binhost.com with SMTP; 9 Sep 2005 23:02:51 -0000 Message-Id: <6.2.1.2.2.20050909190041.07faeeb0@mail.binhost.com> X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Fri, 09 Sep 2005 19:02:52 -0400 To: cfrg@ietf.org From: Russ Housley Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 0.1 (/) X-Scan-Signature: 7bac9cb154eb5790ae3b2913587a40de Subject: [Cfrg] UMAC X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org The RFC Editor has been requested to publish "UMAC: Message Authentication Code using Universal Hashing." The document can be found at: http://www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt Please let me know if any cryptographic concerns with this specification in the next two weeks. Russ _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Fri Sep 09 20:42:23 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EDtRn-00056r-Tz; Fri, 09 Sep 2005 20:42:23 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EDtRl-00056j-Qv for cfrg@megatron.ietf.org; Fri, 09 Sep 2005 20:42:21 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA24647 for ; Fri, 9 Sep 2005 20:42:20 -0400 (EDT) Received: from rproxy.gmail.com ([64.233.170.199]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EDtVQ-000808-7y for cfrg@ietf.org; Fri, 09 Sep 2005 20:46:10 -0400 Received: by rproxy.gmail.com with SMTP id r35so159184rna for ; Fri, 09 Sep 2005 17:42:16 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:references; b=nhXPkEqwS0kSX+667Q6ThAR9RCUbAC88lHL0nyZbOFZ1P6iewR69tzy1UaOZvBjPjRqgCtqvg2KRPSUby4CgF2KgBPs7njhAgcr/Dm8kj4TZto9GlU7Uc7LKlcG8Z+vWB9/tPpxVS4QNKHMXvZSEaCNA+45IjV8KGISIQwsFS/k= Received: by 10.38.98.16 with SMTP id v16mr82855rnb; Fri, 09 Sep 2005 17:42:16 -0700 (PDT) Received: by 10.38.151.25 with HTTP; Fri, 9 Sep 2005 17:42:16 -0700 (PDT) Message-ID: Date: Fri, 9 Sep 2005 17:42:16 -0700 From: Hal Finney To: Russ Housley Subject: Re: [Cfrg] UMAC In-Reply-To: <6.2.1.2.2.20050909190041.07faeeb0@mail.binhost.com> Mime-Version: 1.0 References: <6.2.1.2.2.20050909190041.07faeeb0@mail.binhost.com> X-Spam-Score: 0.0 (/) X-Scan-Signature: 9a2be21919e71dc6faef12b370c4ecf5 Cc: cfrg@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: hal.finney@gmail.com List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Content-Type: multipart/mixed; boundary="===============0851639752==" Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org --===============0851639752== Content-Type: multipart/alternative; boundary="----=_Part_1057_33023477.1126312936270" ------=_Part_1057_33023477.1126312936270 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On 9/9/05, Russ Housley wrote: >=20 > The RFC Editor has been requested to publish "UMAC: Message Authenticatio= n > Code using Universal Hashing." The document can be found at: >=20 > http://www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt >=20 > Please let me know if any cryptographic concerns with this specification= =20 > in > the next two weeks. There are two issues I am aware of with regard to UMAC. Dan Bernstein=20 published a paper at Eurocrypt 05, http://cr.yp.to/papers.html#securitywcs = ,=20 which pointed to some weaknesses in the proof of UMAC security. I think the= =20 problem was how the security results are stated and claimed, but it might b= e=20 helpful if Dan could comment on the statements in the RFC about the proofs= =20 of security, to make sure they are accurate. The second issue is that UMAC has the property that tags can be verified=20 incrementally, 32 bits at a time. A 64 bit tag can have the first 32 bits= =20 verified, and then if they are OK the second 32 bits can be verified. The= =20 current draft doesn't seem to discuss this but some of the UMAC working=20 papers have mentioned it as a possible advantage. However, from discussion on Dan Bernstein's poly1305-aes mailing list I=20 learned that implementing verification in this way opens up a potential=20 timing attack. It may allow an attacker to randomly guess tags and, with=20 about 2^32 guesses, find a tag which has the first 32 bits right, because= =20 those take slightly longer to be rejected. Then with the first 32 bits=20 fixed, he can try another 2^32 messages and get lucky on the 2nd 32 bits.= =20 This reduces the security from the claimed 2^60 down to about 2^33. Although the draft does not recommend implementing this mode, it is=20 something that a reader might think of, so it would be good for the draft t= o=20 caution against doing this in any situation where an attacker can=20 distinguish whether the verifier accepted the tag. Hal Finney ------=_Part_1057_33023477.1126312936270 Content-Type: text/html; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On 9/9/05, Russ Housley <housley@vigilsec.com> wrote:
The RFC Editor has been requested to publish "UMAC: Message Authentica= tion
Code using Universal Hashing."  The document can be = found at:

     http://www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt

Pl= ease let me know if any cryptographic concerns with this specification inthe next two weeks.

There are two issues I am aware of with regard to UMAC.  Dan Bernstein published a paper at Eurocrypt 05, http://cr.yp.to/papers.= html#securitywcs , which pointed to some weaknesses in the proof of UMAC security. I think the problem was how the security results are stated and claimed, but it might be helpful if Dan could comment on the statements in the RFC about the proofs of security, to make sure they are accurate.

The second issue is that UMAC has the property that tags can be verified incrementally, 32 bits at a time. A 64 bit tag can have the first 32 bits verified, and then if they are OK the second 32 bits can be verified. The current draft doesn't seem to discuss this but some of the UMAC working papers have mentioned it as a possible advantage.

However, from discussion on Dan Bernstein's poly1305-aes mailing list I learned that implementing verification in this way opens up a potential timing attack. It may allow an attacker to randomly guess tags and, with about 2^32 guesses, find a tag which has the first 32 bits right, because those take slightly longer to be rejected. Then with the first 32 bits fixed, he can try another 2^32 messages and get lucky on the 2nd 32 bits. This reduces the security from the claimed 2^60 down to about 2^33.

Although the draft does not recommend implementing this mode, it is something that a reader might think of, so it would be good for the draft to caution against doing this in any situation where an attacker can distinguish whether the verifier accepted the tag.

Hal Finney


------=_Part_1057_33023477.1126312936270-- --===============0851639752== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg --===============0851639752==-- From cfrg-bounces@ietf.org Sat Sep 10 02:35:36 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EDyxa-0000Lf-Me; Sat, 10 Sep 2005 02:35:34 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EDyxX-0000L4-UR for cfrg@megatron.ietf.org; Sat, 10 Sep 2005 02:35:32 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id CAA19002 for ; Sat, 10 Sep 2005 02:35:11 -0400 (EDT) Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1EDz0w-0006gf-02 for cfrg@ietf.org; Sat, 10 Sep 2005 02:39:05 -0400 Received: (qmail 91834 invoked by uid 1016); 10 Sep 2005 06:35:26 -0000 Date: 10 Sep 2005 06:35:26 -0000 Message-ID: <20050910063526.91833.qmail@cr.yp.to> Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html. From: "D. J. Bernstein" To: cfrg@ietf.org Subject: Re: [Cfrg] UMAC References: <6.2.1.2.2.20050909190041.07faeeb0@mail.binhost.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Score: 0.0 (/) X-Scan-Signature: e1b0e72ff1bbd457ceef31828f216a86 X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org http://www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt makes various false and deceptive statements regarding the security of UMAC. Perhaps I should start by summarizing what _has_ been proven regarding the security of UMAC: (1) There's a hash function inside UMAC. This hash function has been proven to have differential probability at most 1/2^60. (At least, allegedly proven; I haven't checked the details of the proof. But it's certainly not a shocking statement. The hash function is a Pentium-4-optimized-and-other-machines-be-damned complication of the standard Gilbert-MacWilliams-Sloane hash function, which has easy differential-probability bounds.) (2) Assume that we use a one-time pad instead of the AES outputs in UMAC. Assume that an attacker tries many forgeries against this one-time-pad-UMAC, say D forgeries. Then Pr[at least one forgery is successful] <= D/2^60. (3) What if we really use UMAC as specified, with AES, rather than one-time-pad-UMAC? What has been proven is that Pr[at least one forgery is successful] <= delta + A^2/2^129 + D/2^60 where delta is the maximum distinguishing probability (for the attacker's level of computing power) between AES and a uniform random permutation, and A is the total number of AES inputs used in legitimate messages and in forgery attempts. The UMAC authors misrepresent several important features of the bound Pr[at least one forgery is successful] <= delta + A^2/2^129 + D/2^60: * They often omit the delta term. For example, they start by saying that UMAC ``has been rigorously proven to be secure''---ignoring the possibility of an attacker forging messages by breaking AES. * They always omit the A^2/2^129 term---apparently because they've confused uniform random functions with uniform random permutations. They claim, for example, that ``an adversary ... can do no better than about 1/2^60'' per forgery attempt. They claim that this has been ``rigorously proven.'' But if A = 2^50 and D = 1 then what has actually been proven is around 1/2^29, not 1/2^60. I have recent theorems (http://cr.yp.to/papers.html#securitywcs and http://cr.yp.to/papers.html#permutations) that _often_ allow this type of A^2/2^129 term to be considerably reduced. Perhaps these theorems can be applied to UMAC, but one can't check this without delving into the details of how UMAC uses AES. The best UMAC security theorem so far includes the A^2/2^129 term. * They misrepresent Pr[at least one forgery is successful] as a limit on the _number_ of successful forgeries: ``a 1 / 2^60 forging probability means that if an attacker could try out 2^60 MACs, then the attacker would probably get one right.'' In fact, all we can say about the average number of successful forgeries is that it's Pr[at least one forgery is successful] times at most D. There's a big difference between Pr and D Pr. For example, an attacker who tries out 2^60 MACs would probably seize complete control and produce more than 2^59 selectively forged messages. (It's easy to write down attacks of this type against typical Wegman-Carter MACs, and presumably UMAC isn't an exception; anyway, the _proven_ bound is 2^60, not 1.) There's a big difference between ``probably get one right'' and ``produce more than 2^59 selectively forged messages.'' Similarly, an attacker who tries out 2^40 MACs has roughly a one-in-a-million chance of producing billions of forged messages. The reason that cryptographers normally don't bother counting forgeries after the first one is that cryptographers normally choose parameter sizes to prevent the first forgery. There's a big difference in security between 60 bits and 100 bits; I think it's highly irresponsible of the UMAC authors to recommend 64-bit tags. Beyond these issues, I see three timing-attack issues: * AES timings leak secret information, often allowing the attacker to deduce the AES key. This isn't a UMAC-specific problem; there are several papers that the UMAC document can cite. * As Hal Finney mentioned, accelerated rejection of forgeries leaks secret information, often dramatically speeding up UMAC attacks. The UMAC authors need to explain this danger to people. Actually, I'm not sure whether the UMAC authors understand the danger: memcmp(), which leaks similar information, is the only tag-checking mechanism provided in the UMAC source code. * Timings of the POLY(64) algorithm inside UMAC will leak secret information: namely, whether L1-Hash has produced several 0xff bytes in a row. This won't occur often by chance, but figuring out whether the attacker could trigger it deliberately would require a new analysis of the details of the L1-Hash function. ---D. J. Bernstein, Associate Professor, Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Mon Sep 12 20:50:11 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EEyzz-0005XM-33; Mon, 12 Sep 2005 20:50:11 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EEwZX-0006lx-3O for cfrg@megatron.ietf.org; Mon, 12 Sep 2005 18:14:43 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA05457 for ; Mon, 12 Sep 2005 18:14:40 -0400 (EDT) Received: from sj-iport-1-in.cisco.com ([171.71.176.70] helo=sj-iport-1.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EEwdn-00087t-7Y for cfrg@ietf.org; Mon, 12 Sep 2005 18:19:08 -0400 Received: from sj-core-2.cisco.com ([171.71.177.254]) by sj-iport-1.cisco.com with ESMTP; 12 Sep 2005 15:14:33 -0700 X-IronPort-AV: i="3.97,103,1125903600"; d="scan'208"; a="659345515:sNHT30980460" Received: from xbh-sjc-231.amer.cisco.com (xbh-sjc-231.cisco.com [128.107.191.100]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id j8CMELKG015370; Mon, 12 Sep 2005 15:14:25 -0700 (PDT) Received: from xfe-sjc-211.amer.cisco.com ([171.70.151.174]) by xbh-sjc-231.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Mon, 12 Sep 2005 15:14:22 -0700 Received: from [10.32.254.211] ([10.32.254.211]) by xfe-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Mon, 12 Sep 2005 15:14:21 -0700 Mime-Version: 1.0 (Apple Message framework v622) Content-Type: text/plain; charset=US-ASCII; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: David McGrew Date: Mon, 12 Sep 2005 15:14:19 -0700 To: tdk@acm.org X-Mailer: Apple Mail (2.622) X-OriginalArrivalTime: 12 Sep 2005 22:14:21.0956 (UTC) FILETIME=[53B3FC40:01C5B7E7] X-Spam-Score: 0.0 (/) X-Scan-Signature: bb8f917bb6b8da28fc948aeffb74aa17 Content-Transfer-Encoding: 7bit Cc: "'cfrg@ietf.org'" , Russ Housley , "D. J. Bernstein" Subject: [Cfrg] UMAC draft changes X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hi Ted, several points have been raised about the UMAC draft that ought to be addressed. I would like to see the draft be published as an RFC, but I think that these points should be cleared up first. Here are the items that I think are important (comments welcome): 1. Information about the key may be leaked via timing attacks. The standard fix of implementing a fixed-time comparison will work, and in my opinion should be a MUST for UMAC implementations. 2. The security claims don't take into consideration the number of times that AES is evaluated. 3. The security claims seem to imply that repeat forgeries are not an issue, saying that ``a 1 / 2^60 forging probability means that if an attacker could try out 2^60 MACs, then the attacker would probably get one right.'' Isn't it the case with UMAC that an attacker who can perpetrate a successful forgery would be able to use information from that success to forge more messages? This issue is especially important because of the presence of short tags in the spec. Also, Dan Bernstein points out that the POLY64 hash might leak timing information. It would be good to get some quantification of this, if possible. Do you think that it would be possible for you and the other UMAC authors to address these points? I know that there are several people interested in UMAC that are probably willing to help, at least on item 1. Thanks, and best regards, David _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Tue Sep 13 15:30:56 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFGUa-0003Zb-NY; Tue, 13 Sep 2005 15:30:56 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EF46T-0004tT-VW for cfrg@megatron.ietf.org; Tue, 13 Sep 2005 02:17:14 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id CAA04731 for ; Tue, 13 Sep 2005 02:17:04 -0400 (EDT) Received: from rproxy.gmail.com ([64.233.170.195]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EF4Af-000182-8E for cfrg@ietf.org; Tue, 13 Sep 2005 02:21:35 -0400 Received: by rproxy.gmail.com with SMTP id r35so424533rna for ; Mon, 12 Sep 2005 23:17:00 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:in-reply-to:mime-version:content-type:references; b=lXlcbNrUiVcQr9dDAGqd0MbpC6zY6xb+QTH+j6272nLXgh8zzHZZQp2pb0Ggk32xQSIWwvPrzGd+Pctl2iGWf/um15fDT/+NKurQUc0+GabnUB84dYo2QhfaXgxPnlj/CLAWKRfDikxnObOmNnXDQMZT6eAMILk/1XbN1ORTluY= Received: by 10.39.1.7 with SMTP id d7mr30998rni; Mon, 12 Sep 2005 23:17:00 -0700 (PDT) Received: by 10.38.151.25 with HTTP; Mon, 12 Sep 2005 23:17:00 -0700 (PDT) Message-ID: Date: Mon, 12 Sep 2005 23:17:00 -0700 From: Hal Finney To: cfrg@ietf.org Subject: Re: [Cfrg] UMAC In-Reply-To: <20050910063526.91833.qmail@cr.yp.to> Mime-Version: 1.0 References: <6.2.1.2.2.20050909190041.07faeeb0@mail.binhost.com> <20050910063526.91833.qmail@cr.yp.to> X-Spam-Score: 0.0 (/) X-Scan-Signature: 6ffdee8af20de249c24731d8414917d3 X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: hal.finney@gmail.com List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Content-Type: multipart/mixed; boundary="===============1675994020==" Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org --===============1675994020== Content-Type: multipart/alternative; boundary="----=_Part_3632_30221364.1126592220215" ------=_Part_3632_30221364.1126592220215 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Another question with UMAC relates to its definition of four tag lengths:= =20 32, 64, 96 and 128 bits. The issue is that the function is defined so that= =20 at least in some circumstances the shorter tags are exact prefixes of the= =20 longer ones. This could cause a problem if an attacker could query a=20 verification oracle and control the length of the tags being used. The=20 attacker could find a valid 32 bit tag and use it as a prefix to extend it= =20 another 32 bits and find a valid 64 bit tag. This could similarly be=20 extended to 96 and 128 bit tags. He could find a valid 128 bit tag with onl= y=20 about 2^34 queries. Of course this does require a perhaps implausibly=20 helpful kind of implementation. This could be avoided if the tag length were incorporated in some simple wa= y=20 into the algorithm, for example by stealing two bits of input into the bloc= k=20 cipher from the nonce and using them to encode tag size. Then each differen= t=20 tag length would produce unique tags. UMAC does something along these lines already, in that for 32 or 64 bit tag= s=20 it zeros respectively the bottom two or one bits of the nonce (and uses the= =20 erased bits to decide which 4 or 8 bytes from the 16 byte AES output to=20 use). This is described in section 3.3.1 of=20 http://www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt . This means that nonces which happen to have their low two bits set will in= =20 fact have the 32 and 64 bit tags not be prefixes of each other or of the=20 longer tags (however the 96 bit tag will still be a prefix of the 128). For= =20 nonces which have their low two bits clear, the different sizes of tags are= =20 all prefixes of each other as described above. No doubt there are simple ways to incorporate two bits of information=20 regarding tag size as inputs to the algorithm. That would avoid the arguabl= y=20 undesirable property of short tags revealing information about long ones. In looking at section 3.3.1 I just noticed another problem. It is important= =20 with these kinds of MACs that the nonce never be re-used for a given key.= =20 However the pad definition function takes a nonce of variable length, 1 to= =20 16 bytes, and then pads it up to 16 bytes by appending zeros. This means=20 that a nonce of 1 and one of 1,0 will both be treated mathematically as the= =20 same value. This would cause the nonce to effectively be re-used even thoug= h=20 the inputs to the PDF are different, harming the security of the MAC. Eithe= r=20 the padding needs to include some indicator of how many padding bytes are= =20 being added, or else the padding function should be defined just to take=20 nonces of length BLOCKLEN, all of which must be unique. Hal Finney ------=_Part_3632_30221364.1126592220215 Content-Type: text/html; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Another question with UMAC relates to its definition of four tag lengths: 32, 64, 96 and 128 bits. The issue is that the function is defined so that at least in some circumstances the shorter tags are exact prefixes of the longer ones. This could cause a problem if an attacker could query a verification oracle and control the length of the tags being used. The attacker could find a valid 32 bit tag and use it as a prefix to extend it another 32 bits and find a valid 64 bit tag. This could similarly be extended to 96 and 128 bit tags. He could find a valid 128 bit tag with only about 2^34 queries. Of course this does require a perhaps implausibly helpful kind of implementation.

This could be avoided if the tag length were incorporated in some simple way into the algorithm, for example by stealing two bits of input into the block cipher from the nonce and using them to encode tag size. Then each different tag length would produce unique tags.

UMAC does something along these lines already, in that for 32 or 64 bit tags it zeros respectively the bottom two or one bits of the nonce (and uses the erased bits to decide which 4 or 8 bytes from the 16 byte AES output to use). This is described in section 3.3.1 of h= ttp://www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt .

This means that nonces which happen to have their low two bits set will in fact have the 32 and 64 bit tags not be prefixes of each other or of the longer tags (however the 96 bit tag will still be a prefix of the 128). For nonces which have their low two bits clear, the different sizes of tags are all prefixes of each other as described above.

No doubt there are simple ways to incorporate two bits of information regarding tag size as inputs to the algorithm. That would avoid the arguably undesirable property of short tags revealing information about long ones.

In looking at section 3.3.1 I just noticed another problem. It is important with these kinds of MACs that the nonce never be re-used for a given key. However the pad definition function takes a nonce of variable length, 1 to 16 bytes, and then pads it up to 16 bytes by appending zeros. This means that a nonce of 1 and one of 1,0 will both be treated mathematically as the same value. This would cause the nonce to effectively be re-used even though the inputs to the PDF are different, harming the security of the MAC. Either the padding needs to include some indicator of how many padding bytes are being added, or else the padding function should be defined just to take nonces of length BLOCKLEN, all of which must be unique.

Hal Finney

------=_Part_3632_30221364.1126592220215-- --===============1675994020== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg --===============1675994020==-- From cfrg-bounces@ietf.org Wed Sep 14 01:46:08 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFQ5w-0001lH-R3; Wed, 14 Sep 2005 01:46:08 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFQ5k-0001kq-SM for cfrg@megatron.ietf.org; Wed, 14 Sep 2005 01:46:06 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id BAA25129 for ; Wed, 14 Sep 2005 01:45:55 -0400 (EDT) Received: from taverner.cs.berkeley.edu ([128.32.168.222]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EFQAH-0007HH-IG for cfrg@ietf.org; Wed, 14 Sep 2005 01:50:38 -0400 Received: from taverner.CS.Berkeley.EDU (localhost.localdomain [127.0.0.1]) by taverner.CS.Berkeley.EDU (8.13.1/8.13.1) with ESMTP id j8E5jbXv029827 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Tue, 13 Sep 2005 22:45:37 -0700 Received: (from news@localhost) by taverner.CS.Berkeley.EDU (8.13.1/8.13.1/Submit) id j8E5jbFO029824 for cfrg@ietf.org; Tue, 13 Sep 2005 22:45:37 -0700 To: cfrg@ietf.org Path: not-for-mail From: daw@cs.berkeley.edu (David Wagner) Newsgroups: isaac.lists.ietf-cfrg Subject: Re: [Cfrg] UMAC Date: Wed, 14 Sep 2005 05:45:37 +0000 (UTC) Organization: University of California, Berkeley Lines: 19 Message-ID: References: <6.2.1.2.2.20050909190041.07faeeb0@mail.binhost.com> <20050910063526.91833.qmail@cr.yp.to> NNTP-Posting-Host: taverner.cs.berkeley.edu X-Trace: taverner.CS.Berkeley.EDU 1126676737 29793 128.32.168.222 (14 Sep 2005 05:45:37 GMT) X-Complaints-To: news@taverner.CS.Berkeley.EDU NNTP-Posting-Date: Wed, 14 Sep 2005 05:45:37 +0000 (UTC) X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Originator: daw@taverner.cs.berkeley.edu (David Wagner) X-Spam-Score: 0.0 (/) X-Scan-Signature: d6b246023072368de71562c0ab503126 X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: David Wagner List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hal Finney wrote: >Another question with UMAC relates to its definition of four tag lengths: >32, 64, 96 and 128 bits. The issue is that the function is defined so that >at least in some circumstances the shorter tags are exact prefixes of the >longer ones. This could cause a problem if an attacker could query a >verification oracle and control the length of the tags being used. The >attacker could find a valid 32 bit tag and use it as a prefix to extend it >another 32 bits and find a valid 64 bit tag. This could similarly be >extended to 96 and 128 bit tags. He could find a valid 128 bit tag with only >about 2^34 queries. Of course this does require a perhaps implausibly >helpful kind of implementation. Yes. Good point. Phil Rogaway and I pointed out a similar observation about CCM. http://eprint.iacr.org/2003/070/ To fix this, it suffices to ensure that the tag length is a parameter that is immutably bound to the key and never changed. In other words, never use the same key with different parameter sizes. I don't think the algorithm needs to be changed, as long as this rule is followed. _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Wed Sep 14 16:30:24 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFdtg-0008KC-Ct; Wed, 14 Sep 2005 16:30:24 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFdte-0008K4-EJ; Wed, 14 Sep 2005 16:30:22 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA09296; Wed, 14 Sep 2005 16:30:20 -0400 (EDT) Received: from above.proper.com ([208.184.76.39]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EFdyI-00078Z-Tc; Wed, 14 Sep 2005 16:35:12 -0400 Received: from [10.20.30.249] (adsl-66-125-125-65.dsl.pltn13.pacbell.net [66.125.125.65]) (authenticated bits=0) by above.proper.com (8.12.11/8.12.9) with ESMTP id j8EKUE2g038273; Wed, 14 Sep 2005 13:30:15 -0700 (PDT) (envelope-from paul.hoffman@vpnc.org) Mime-Version: 1.0 Message-Id: Date: Wed, 14 Sep 2005 13:30:12 -0700 To: Hash WG , cfrg@ietf.org From: Paul Hoffman Content-Type: text/plain; charset="us-ascii" ; format="flowed" X-Spam-Score: 0.0 (/) X-Scan-Signature: 2409bba43e9c8d580670fda8b695204a Cc: Subject: [Cfrg] Fwd: Preliminary Program for the Cryptographic Hash Workshop (10/31-11/1/2005) Just Posted X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Of interest to both these lists: >X-Sender: sjchang@email.nist.gov >X-Mailer: QUALCOMM Windows Eudora Version 5.1.1 >Date: Wed, 14 Sep 2005 16:04:38 -0400 >To: hash-forum@nist.gov >From: Shu-jen Chang >Subject: Preliminary Program for the Cryptographic Hash Workshop > (10/31-11/1/2005) Just Posted >Cc: hash-function@nist.gov >X-NIST-MailScanner: Found to be clean >X-NIST-MailScanner-From: shu-jen.chang@nist.gov > >The preliminary program for the Cryptographic Hash Workshop has been >posted on the workshop web site at: >http://www.csrc.nist.gov/pki/HashWorkshop/program.htm > >The workshop is scheduled for 10/31-11/1/2005 at NIST, Gaithersburg, >MD. A link has been provided on the web site for workshop >registration. We appreciate your interest and look forward to your >participation. > >Sincerely, >Shu-jen Chang >Computer Security Division >NIST _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Thu Sep 15 05:50:39 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFqO6-0005DU-Uu; Thu, 15 Sep 2005 05:50:38 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFqO5-0005DP-NP for cfrg@megatron.ietf.org; Thu, 15 Sep 2005 05:50:37 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id FAA00312 for ; Thu, 15 Sep 2005 05:50:34 -0400 (EDT) From: kaisa.nyberg@nokia.com Received: from mgw-ext01.nokia.com ([131.228.20.93]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EFqSn-0003Dw-Tq for cfrg@ietf.org; Thu, 15 Sep 2005 05:55:34 -0400 Received: from esebh105.NOE.Nokia.com (esebh105.ntc.nokia.com [172.21.138.211]) by mgw-ext01.nokia.com (Switch-3.1.7/Switch-3.1.7) with ESMTP id j8F9oJwb032054; Thu, 15 Sep 2005 12:50:23 +0300 Received: from esebh101.NOE.Nokia.com ([172.21.138.177]) by esebh105.NOE.Nokia.com with Microsoft SMTPSVC(6.0.3790.1830); Thu, 15 Sep 2005 12:50:22 +0300 Received: from esebe104.NOE.Nokia.com ([172.21.143.44]) by esebh101.NOE.Nokia.com with Microsoft SMTPSVC(6.0.3790.1830); Thu, 15 Sep 2005 12:50:22 +0300 X-MimeOLE: Produced By Microsoft Exchange V6.5.7226.0 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Subject: RE: [Cfrg] AES GMAC Date: Thu, 15 Sep 2005 12:50:21 +0300 Message-ID: Thread-Topic: [Cfrg] AES GMAC Thread-Index: AcWtgSM7X0fmhx0ZRZuJCjzNyDT+zAMWVIWw To: , X-OriginalArrivalTime: 15 Sep 2005 09:50:22.0427 (UTC) FILETIME=[E3B5AAB0:01C5B9DA] X-Spam-Score: 0.3 (/) X-Scan-Signature: e8a67952aa972b528dd04570d58ad8fe Content-Transfer-Encoding: quoted-printable Cc: henri.gilbert@francetelecom.com, matt.robshaw@francetelecom.com X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Dear Russ Housley, As response to your request we express our concerns about the cryptographic quality of the MAC construction given in the GMAC specification by David MacGrew and John Viega.=20 The basic cryptographic requirement for a MAC with tag of length n is that the forgery probability of a tag should be close to 2^{-n}. Our concern is that the GMAC construction proposed by MacGrew and Viega does not meet this requirement. Indeed, for a message of length 2^m blocks the forgery probability is about 2^{m-n}. In the current proposal, upperbound of 2^{-64} to the forgery probability is achieved by using 128-bit tags and setting an upperbound of 2^64 to the message length. Moreover, truncation of tags is forbidden. This means that the current proposal mandates the use of 128-bit tags to achieve 64-bit security level for the MAC algorithm. If not a security risk, it is a cryptogaphic flaw, and a serious drawback. Even more so, since one could do better. In our note to NIST in June we drew attention to a previously known construction using which n-bit security level can be achieved with n-bit tags for messages of practically any length. Using this construction, for example, 64-bit security level can be achieved with 64-bit tags for messages of up to 2^{64} blocks, and it does not take more key, or more calls to the AES, or essentially more computations than with the construction by MacGrew and Viega. Our note to NIST can be found at: http://csrc.nist.gov/CryptoToolkit/modes/comments/General_Comments/paper s/Nyberg_Gilbert_and_Robshaw.pdf=20 With best regards, Kaisa Nyberg Henri Gilbert Matt Robshaw >-----Original Message----- >From: cfrg-bounces@ietf.org [mailto:cfrg-bounces@ietf.org] On Behalf Of >ext Russ Housley >Sent: 30 August, 2005 19:31 >To: cfrg@ietf.org >Subject: [Cfrg] AES GMAC > >David McGrew and John Viega have requested publication of an IPsec ESP=20 >cipher specification that uses AES GMAC. The specification can be=20 >found at: > > =20 >http://www.ietf.org/internet-drafts/draft-mcgrew-aes-gmac-esp-00.txt > >Please let me know if any cryptographic concerns with this=20 >specification in the next two weeks. > >Russ > > >_______________________________________________ >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 cfrg-bounces@ietf.org Thu Sep 15 07:46:30 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFsCE-00021H-FB; Thu, 15 Sep 2005 07:46:30 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFsCC-00021C-Jr for cfrg@megatron.ietf.org; Thu, 15 Sep 2005 07:46:29 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id HAA05294 for ; Thu, 15 Sep 2005 07:46:27 -0400 (EDT) Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1EFsGx-0006JI-6G for cfrg@ietf.org; Thu, 15 Sep 2005 07:51:26 -0400 Received: (qmail 1235 invoked by uid 1016); 15 Sep 2005 11:46:41 -0000 Date: 15 Sep 2005 11:46:40 -0000 Message-ID: <20050915114640.1234.qmail@cr.yp.to> Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html. From: "D. J. Bernstein" To: cfrg@ietf.org Subject: Re: [Cfrg] AES GMAC References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Score: 0.0 (/) X-Scan-Signature: 8b431ad66d60be2d47c7bfeb879db82c Cc: kaisa.nyberg@nokia.com, henri.gilbert@francetelecom.com, housley@vigilsec.com, matt.robshaw@francetelecom.com X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org It is _not_ true that truncation---specifically, twisted truncation of a 128-bit GMAC authenticator to 64 bits---preserves security level. Here's the chart: * Maximum forgery probability for _very long_ messages: Not affected by twisted truncation (unlike naive truncation). * Maximum forgery probability without regard to message length: Not affected by twisted truncation (unlike naive truncation). * Maximum forgery probability for _short_ messages: Made much worse by twisted truncation (like naive truncation). * Maximum forgery probability _per byte sent by the attacker_: Made much worse by twisted truncation (like naive truncation). For the record: I do not endorse, and I have never endorsed, 64-bit authenticators. Attackers can try an amazing number of short forgeries and end up with an unacceptably high chance of success. As for the ``secure truncation'' misquote: What my securitywcs paper discusses is the idea of _reducing_ forgery probabilities by using a ``larger field'' with a ``larger output size'' that (if you care about every last byte of bandwidth) can then be ``safely truncated after an appropriate twist.'' The original field size is 128 bits; the larger field size is, typically, 160 bits; the truncation is back to the original 128 bits. > The basic cryptographic requirement for a MAC with tag of length n is > that the forgery probability of a tag should be close to 2^{-n}. No. There's a cryptographic requirement that forgery probability be extremely small, but there's no cryptographic requirement that every last byte of bandwidth be saved. Should cryptographers pay attention to bandwidth? Of course. But this doesn't mean that we should take the crazy step of excluding all the non-minimal-bandwidth solutions. Minimizing bandwidth often imposes other costs that are much more important to the users---as illustrated by short elliptic-curve signatures whose verification time is, for many applications, unacceptably slow. Similar comments apply to key sizes, collision-free-hash output lengths, etc. A 128-bit security level requires _at least_ a 128-bit key and a 256-bit hash output, but there's no cryptographic justification for demanding _exactly_ a 128-bit key and _exactly_ a 256-bit hash output. Perhaps the most efficient way to achieve 128-bit security is with a 192-bit key and a 384-bit hash output. ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Thu Sep 15 10:35:46 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFuq2-0000dw-MZ; Thu, 15 Sep 2005 10:35:46 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EFuq1-0000do-1M for cfrg@megatron.ietf.org; Thu, 15 Sep 2005 10:35:45 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA14762 for ; Thu, 15 Sep 2005 10:35:42 -0400 (EDT) Received: from sj-iport-1-in.cisco.com ([171.71.176.70] helo=sj-iport-1.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EFuun-0002jU-P9 for cfrg@ietf.org; Thu, 15 Sep 2005 10:40:44 -0400 Received: from sj-core-2.cisco.com ([171.71.177.254]) by sj-iport-1.cisco.com with ESMTP; 15 Sep 2005 07:35:33 -0700 X-IronPort-AV: i="3.97,113,1125903600"; d="scan'208"; a="659989949:sNHT34998228" Received: from xbh-sjc-211.amer.cisco.com (xbh-sjc-211.cisco.com [171.70.151.144]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id j8FEZCKS017554; Thu, 15 Sep 2005 07:35:30 -0700 (PDT) Received: from xfe-sjc-212.amer.cisco.com ([171.70.151.187]) by xbh-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 15 Sep 2005 07:35:28 -0700 Received: from [10.32.254.211] ([10.32.254.211]) by xfe-sjc-212.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 15 Sep 2005 07:35:24 -0700 In-Reply-To: References: Mime-Version: 1.0 (Apple Message framework v622) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <8a5bffcdf965ab4158c2903586876179@cisco.com> Content-Transfer-Encoding: 7bit From: David McGrew Subject: Re: [Cfrg] AES GMAC Date: Thu, 15 Sep 2005 07:35:21 -0700 To: kaisa.nyberg@nokia.com X-Mailer: Apple Mail (2.622) X-OriginalArrivalTime: 15 Sep 2005 14:35:24.0468 (UTC) FILETIME=[B5520740:01C5BA02] X-Spam-Score: 0.0 (/) X-Scan-Signature: 42e3ed3f10a1d8bef690f09da16f507a Content-Transfer-Encoding: 7bit Cc: henri.gilbert@francetelecom.com, housley@vigilsec.com, cfrg@ietf.org, matt.robshaw@francetelecom.com X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hi Kaisa, thanks for your comments. Your comments to NIST are interesting and make some good points for a general-purpose message authentication code. However, they are less pertinent in the particular case of authentication of packetized data, especially at high data rates, which is the particular domain of draft-mcgrew-aes-gmac-esp-00.txt. I don't claim that ESP GMAC is the perfect general-purpose MAC, but it is well suited for its domain. More inline: On Sep 15, 2005, at 2:50 AM, kaisa.nyberg@nokia.com wrote: > Dear Russ Housley, > > As response to your request we express our concerns about the > cryptographic quality of the MAC construction given in the GMAC > specification by David MacGrew and John Viega. > > The basic cryptographic requirement for a MAC with tag of length n is > that the forgery probability of a tag should be close to 2^{-n}. I disagree that this is a requirement. If it was, then MACs would be essentially equivalent to PRFs, though the literature is full of MACs that aren't PRFs. > Our > concern is that the GMAC construction proposed by MacGrew and Viega > does > not meet this requirement. Indeed, for a message of length 2^m blocks > the forgery probability is about 2^{m-n}. In the current proposal, > upperbound of 2^{-64} to the forgery probability is achieved by using > 128-bit tags and setting an upperbound of 2^64 to the message length. But in the internet draft under discussion, messages are not going to be anywhere near that length. The largest that an IPv4 packet can get is 64 kilobytes (2^{12} blocks), which puts the single packet forgery probability at 2^{-116}. This value compares favorably to that of the recommended ESP authentication methods, which use 96-bit tags. In practice, packets on the Internet are significantly smaller, and only very rarely exceed 2kb (256 blocks) (see http://www.caida.org/outreach/papers/1998/Inet98/Inet98.pdf or similar studies), and MTUs around this size are common. > Moreover, truncation of tags is forbidden. This is a feature, not a bug! First, having a single tag length promotes interoperability and makes implementation easier. Second, ESP encapsulation overhead is significant, and truncating an ESP tag in order to save bandwidth is a questionable tradeoff. Each ESP packet has a minimum of ten bytes of data besides the payload, and GMAC uses an eight-byte IV that is explicitly carried in each packet, so each packet has 18 bytes of overhead in addition to the tag. There is little advantage in using a 96-bit tag, with total overhead of at least 30 bytes, over using a full tag with a total overhead of at least 34 bytes. > > This means that the current proposal mandates the use of 128-bit tags > to > achieve 64-bit security level for the MAC algorithm. If not a security > risk, it is a cryptogaphic flaw, and a serious drawback. Even more so, > since one could do better. In our note to NIST in June we drew > attention > to a previously known construction using which n-bit security level can > be achieved with n-bit tags for messages of practically any length. > Using this construction, for example, 64-bit security level can be > achieved with 64-bit tags for messages of up to 2^{64} blocks, and it > does not take more key, or more calls to the AES, or essentially more > computations than with the construction by MacGrew and Viega. I don't understand the claim in the last sentence. Is the "second 64-bit quantity" \lambda in Section 3 of your note to NIST not additional key material? When protecting packetized data at high data rates, there is a significant cost incurred for making keys larger, since they must be stored and must be fetched before packet processing. Each clock cycle that a fully-pipelined AES engine is idle is a missed opportunity to process 16 bytes. In many IPsec VPN implementations, there are large numbers of security associations, and the cost of storing and fetching them is non-trivial. This was the motivation behind minimizing the size of the GCM/GMAC context. This is not to say that your suggestion to NIST is no viable, it is just to explain our thinking. Your suggestions to NIST are interesting, and worth considering for the design of future MACs. However, draft-mcgrew-aes-gmac-esp-00.txt provides an adequate level of security and is compatible with RFC4106. Let's continue the discussion about MACs in a broader context. Best regards, David p.s. - your note to NIST mentions that there is an ETSI SAGE effort that is considering MAC designs. It would be great if CFRG and the IETF could liaison with that group and hear a report on the status of this work. Could you please let me know who in ETSI I could bug about this? > > Our note to NIST can be found at: > > http://csrc.nist.gov/CryptoToolkit/modes/comments/General_Comments/ > paper > s/Nyberg_Gilbert_and_Robshaw.pdf > > With best regards, > > Kaisa Nyberg > Henri Gilbert > Matt Robshaw > >> -----Original Message----- >> From: cfrg-bounces@ietf.org [mailto:cfrg-bounces@ietf.org] On Behalf >> Of > >> ext Russ Housley >> Sent: 30 August, 2005 19:31 >> To: cfrg@ietf.org >> Subject: [Cfrg] AES GMAC >> >> David McGrew and John Viega have requested publication of an IPsec ESP >> cipher specification that uses AES GMAC. The specification can be >> found at: >> >> >> http://www.ietf.org/internet-drafts/draft-mcgrew-aes-gmac-esp-00.txt >> >> Please let me know if any cryptographic concerns with this >> specification in the next two weeks. >> >> Russ >> >> >> _______________________________________________ >> 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 cfrg-bounces@ietf.org Thu Sep 15 17:18:50 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EG186-0008L5-Me; Thu, 15 Sep 2005 17:18:50 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EG0to-0004He-EY for cfrg@megatron.ietf.org; Thu, 15 Sep 2005 17:04:07 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA10359 for ; Thu, 15 Sep 2005 17:04:01 -0400 (EDT) Received: from ylpvm12-ext.prodigy.net ([207.115.57.43] helo=ylpvm12.prodigy.net) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EG0ye-0006mc-Ok for cfrg@ietf.org; Thu, 15 Sep 2005 17:09:07 -0400 Received: from ylpvm01.prodigy.net (ylpvm01-int.prodigy.net [207.115.5.207]) by ylpvm12.prodigy.net (8.12.10 outbound/8.12.10) with ESMTP id j8FL3piU005069 for ; Thu, 15 Sep 2005 17:03:51 -0400 X-ORBL: [66.127.112.169] Received: from [192.168.0.101] (adsl-66-127-112-169.dsl.scrm01.pacbell.net [66.127.112.169]) by ylpvm01.prodigy.net (8.13.4 dk-milter linux/8.13.4) with ESMTP id j8FL3h2o005113; Thu, 15 Sep 2005 17:03:44 -0400 Mime-Version: 1.0 (Apple Message framework v734) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: Ted Krovetz Subject: Re: [Cfrg] UMAC draft changes Date: Thu, 15 Sep 2005 14:03:50 -0700 To: David McGrew X-Mailer: Apple Mail (2.734) X-Spam-Score: 0.1 (/) X-Scan-Signature: 200d029292fbb60d25b263122ced50fc Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Thu, 15 Sep 2005 17:18:48 -0400 Cc: cfrg@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hi David, We're happy to make some clarifications. We think that most points that have been raised in recent postings to this list are covered in the RFC itself (see the introduction and the extensive ``Security considerations'' section). The one point that the RFC does not address is timing attacks. We will submit a revision that will include some ``warning'' to implementors regarding timing and other side-channel attacks. However, we see nothing in UMAC that makes it inherently vulnerable to these attacks. Let me further clarify some of the issues that you raise. > 1. Information about the key may be leaked via timing attacks. > The standard fix of implementing a fixed-time comparison will work, > and in my opinion should be a MUST for UMAC implementations. We don't think the spec should mandate any particular implementation technique to avoid timing attacks, or any other side-channel attack, first because side-channel attacks are so open-ended, and second because whether or not a timing attack is a threat is so application dependent. Warning about timing attacks seems to us more appropriate than mandating any particular counter-measure. As said, we'll add such a warning in the RFC. > Also, Dan Bernstein points out that the POLY64 hash might leak > timing information. It would be good to get some quantification of > this, if possible. There's no ``inherent'' leak in the POLY64 algorithm; it is an implementation choice whether or not to try to make running time data- independent in this algorithm. The illustrative reference code that we provide leaks timing information in its POLY64 implementation, and also in its choice of an off-the-shelf AES and memcmp. This code was never intended to mask against timing attacks. The fact that our reference code is open to timing attacks has no bearing on the content of a UMAC RFC. We expect that UMAC can be implemented in practical ways that eliminate the possibility of timing attacks to the same extent that other table-employing mechanisms can do so. > 2. The security claims don't take into consideration the number of > times that AES is evaluated. Formal statements of UMAC's security (in our papers) include the Adv^prf term that implies the A^2/2^129 term if you consider a block cipher. In high-level English descriptions, we omit focus or mention of the prf-to-prp term delta=A^2/2^129 because it is both well- understood (in particular, it is common to virtually all MAC functions that involve block-cipher computations) and low-order (if the weak link in your MAC algorithm is this term then you are doing well!). In particular, the term A^2/2^129 appears to be more an artifact of the proof than a real attack threat. This term is widely believed to be of no practical consequences in any realistic setting (and the results of Shoup and Bernstein prove it for some cases). That is especially true if one uses less than 2^64 tags per key, which is always the case in practice. For the sake of illustration, think of 8-byte tags for 2^64 messages. Just for the tags themselves (not counting the messages size), you have to send 8 * 2^64 bytes. Over a super-fast 1GigaByte/second link, it will take 2^37 seconds or some 4000 years! Now, not only you need the system (and attacker) to run for that time but you also need all messages to be MACed with the SAME KEY. The system doing that (and the patient attacker) deserve the break!! We will consider writing something about this in the security considerations. > 3. The security claims seem to imply that repeat forgeries are not > an issue, saying that ``a 1 / 2^60 forging probability means that > if an attacker could try out 2^60 MACs, then the attacker would > probably get one right.'' Isn't it the case with UMAC that an > attacker who can perpetrate a successful forgery would be able to > use information from that success to forge more messages? This > issue is especially important because of the presence of short tags > in the spec. This point is explicitly and clearly addressed in the security considerations section (which is where such a discussion belongs) under the heading of ``Tag lengths and forging probability'' (Sec 6.2). The text there says: ``It should be pointed out that once an attempted forgery is successful, it is possible, in principle, that subsequent messages under this key may be forged, too. This is important to understand in gauging the severity of a successful forgery, even though no such attack on UMAC is known to date.'' So while it is not known how easy or hard it would be to produce more forgeries once a first forgery is found, it is prudent to assume that repeat forgeries *are* easy and that initial forgeries should be avoided. UMAC was designed to support different levels of security. A security architect should choose a tag length suitable for their application. If the number of messages to be authenticated under one key is not astronomic and care is given to identify and act on forgery attempts, then 64-bit tags are appropriate. For low-value content, 32-bit tags might be appropriate (after all, these have been standard in retail banking for years...). For very high value content, or if one anticipates a large number of forgery attempts, UMAC offers a 96-bit tag (and even 128-bit tags for the really paranoid). In any case, the simple fact that someone could misuse short tags does not mean that they should be disallowed. We have stated our opinion often, and still believe it, that 64-bit tags are appropriate for most purposes, and if anyone needs more or less, UMAC can accommodate that. Some other points brought up by Finney and Bernstein: > UMAC has the property that tags can be verified incrementally, 32 > bits at a time. This is true. Because UMAC operates by making independent hash iterations, each producing 32-bits, and the results are concatenated, it is possible to do fewer iterations than specified in order to verify prefixes. However, by doing so the verifier may provide the attacker with information that will reduce the security of longer tags. As mentioned by Dave Wagner, a given key should normally be used with tags of one given size. We will make sure this is said quite explicitly in the RFC. > It is important with these kinds of MACs that the nonce never be re- > used for a given key. However the pad definition function takes a > nonce of variable length We agree, and the second sentence of the ``Nonce considerations'' subsection says, ``All nonces in an authentication session must be equal in length.'' > The hash function is a Pentium-4-optimized-and-other-machines-be- > damned complication ... UMAC is optimized to run well on any processor that supports well 32- bit x 32-bit --> 64-bit multiplication. This is a large class of processors. As it turns out, the SSE instructions on the Pentium 4 allows parallel computations of this sort, but it is a gross mis- representation that UMAC is ``Pentium-4-optimized-and-other-machines- be-damned''. Regards, John Black Shai Halevi Hugo Krawczyk Ted Krovetz Phillip Rogaway _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Sat Sep 17 07:51:02 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EGbDh-0003bi-Q3; Sat, 17 Sep 2005 07:51:01 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EGbDg-0003bd-6q for cfrg@megatron.ietf.org; Sat, 17 Sep 2005 07:51:00 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id HAA08952 for ; Sat, 17 Sep 2005 07:50:59 -0400 (EDT) Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1EGbIr-0005tb-0k for cfrg@ietf.org; Sat, 17 Sep 2005 07:56:23 -0400 Received: (qmail 79642 invoked by uid 1016); 17 Sep 2005 11:51:14 -0000 Date: 17 Sep 2005 11:51:14 -0000 Message-ID: <20050917115114.79641.qmail@cr.yp.to> Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html. From: "D. J. Bernstein" To: cfrg@ietf.org Subject: Re: [Cfrg] UMAC draft changes References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Score: 0.0 (/) X-Scan-Signature: 244a2fd369eaf00ce6820a760a3de2e8 X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org The UMAC draft claims that UMAC ``has been rigorously proven to be secure,'' and specifically that ``an adversary ... can do no better than about 1/2^60'' per forgery attempt. That claim is false. Among other problems, the proven bound on forgery probabilities includes an A^2/2^129 term, where A is the number of AES evaluations. UMAC does not require that A be limited to, e.g., 2^34. The UMAC authors admit that the A^2/2^129 term exists in the proven forgery-probability bound. They nevertheless attempt to weasel out of correcting the falsehoods in their draft: * They talk about how long it would take for a single sender to transmit 2^64 messages. So what? Transmitting 2^34 messages is a billion times faster than that. * They claim that A^2/2^129 is an ``artifact of the proof.'' What they mean, apparently, is that they know their proof produces bad bounds, but they think they can do better. So what? The question is about what ``has been rigorously proven,'' not about what the UMAC authors speculate they might prove in the future. * They observe, correctly, that Shoup and I have proven something better than A^2/2^129 for many other MACs. So what? The current discussion is about UMAC, not those other MACs. Maybe my techniques work for UMAC, but maybe they don't. If the UMAC authors want to claim that 1/2^60 ``has been rigorously proven'' then they need to show us the proof. * They claim that the A^2/2^129 term ``is widely believed to be of no practical consequences in any realistic setting.'' Even if this is true, so what? The question is about what ``has been rigorously proven,'' not about what people might believe. The UMAC security claim is clearly, obviously, indisputably false. When I pointed this out eight months ago, the UMAC authors didn't attempt to defend their false claim, but they also didn't fix it; instead they attempted to distract attention from it, just as they're doing now. The level of dishonesty here really amazes me. > If the number of messages to be authenticated under one key is not > astronomic and care is given to identify and act on forgery attempts, How, precisely, is one supposed to ``act on forgery attempts''? Close the connection, allowing trivial denial of service? Generate a new key, again degrading service and then allowing the attacker to continue with the new key? > In any case, the simple fact that someone could misuse short tags > does not mean that they should be disallowed. Short tags should be disallowed. > UMAC is optimized to run well on any processor that supports well 32- > bit x 32-bit --> 64-bit multiplication. This is a large class of > processors. And where are the benchmarks justifying these multiple-CPU performance claims? All I see are Pentium 4 benchmarks relying heavily on PMULUDQ. Unjustified claims of speed aren't as dangerous as unjustified claims of security, but they're still dishonest. ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Mon Sep 19 22:26:37 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EHXq9-00078n-9Z; Mon, 19 Sep 2005 22:26:37 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EHXq8-00078h-3G for cfrg@megatron.ietf.org; Mon, 19 Sep 2005 22:26:36 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id WAA15455 for ; Mon, 19 Sep 2005 22:26:33 -0400 (EDT) Received: from vms048pub.verizon.net ([206.46.252.48]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EHXvp-0005Q8-WA for cfrg@ietf.org; Mon, 19 Sep 2005 22:32:32 -0400 Received: from HP752c ([68.237.23.14]) by vms048.mailsrvcs.net (Sun Java System Messaging Server 6.2 HotFix 0.04 (built Dec 24 2004)) with ESMTPA id <0IN300FW9G452671@vms048.mailsrvcs.net> for cfrg@ietf.org; Mon, 19 Sep 2005 21:26:30 -0500 (CDT) Date: Mon, 19 Sep 2005 22:26:29 -0400 From: "Shai Halevi" In-reply-to: <200509171608.j8HG8NNL016108@alum-2.mit.edu> To: Message-id: MIME-version: 1.0 X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2900.2527 X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Content-type: text/plain; charset=US-ASCII Content-transfer-encoding: 7bit Importance: Normal X-Priority: 3 (Normal) X-MSMail-priority: Normal X-Spam-Score: 0.2 (/) X-Scan-Signature: 39bd8f8cbb76cae18b7e23f7cf6b2b9f Content-Transfer-Encoding: 7bit Subject: [Cfrg] RE: UMAC draft changes X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Daniel, bad-mouthing is a rather poor utilization of this bandwidth (and the time of the people reading this list). It is definitely your right to peddle your own scheme and claim that it is better than UMAC on this point or the other, but name-calling and FUD is not a very appropriate (or effective) way of doing that. > [...] > * They talk about how long it would take for a single sender to > transmit 2^64 messages. So what? Transmitting 2^34 messages is a > billion times faster than that. If you would bother reading the note before replying, you would discover that that illustration was there to demonstrate that 2^{64} is a safe bound for any realistic system. You seem to agree with that point. > * They claim that the A^2/2^129 term ``is widely believed to be of no > practical consequences in any realistic setting.'' Even if this is > true, so what? The question is about what ``has been rigorously > proven,'' not about what people might believe. Maybe for you it is, but for people using MAC the question is how safe it is to use, not what DBJ was able to prove about it. > The UMAC security claim is clearly, obviously, indisputably false. Actually, the technical claim in the paper is correct, and I believe that the English interpretation in the RFC is a reasonable one. You may think otherwise (which you made blatantly clear), but the readers of this group are intelligent enough to make their own mind regarding that. Regards, --Shai _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Thu Sep 22 12:37:18 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIU4U-0004FB-JL; Thu, 22 Sep 2005 12:37:18 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIU4R-0004F6-Mn for cfrg@megatron.ietf.org; Thu, 22 Sep 2005 12:37:16 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA10231 for ; Thu, 22 Sep 2005 12:37:12 -0400 (EDT) From: kaisa.nyberg@nokia.com Received: from mgw-ext03.nokia.com ([131.228.20.95]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EIUAg-0005zq-Nb for cfrg@ietf.org; Thu, 22 Sep 2005 12:43:44 -0400 Received: from esebh106.NOE.Nokia.com (esebh106.ntc.nokia.com [172.21.138.213]) by mgw-ext03.nokia.com (Switch-3.1.7/Switch-3.1.7) with ESMTP id j8MGZmXw014173; Thu, 22 Sep 2005 19:35:51 +0300 Received: from esebh104.NOE.Nokia.com ([172.21.143.34]) by esebh106.NOE.Nokia.com with Microsoft SMTPSVC(6.0.3790.1830); Thu, 22 Sep 2005 19:37:04 +0300 Received: from esebe104.NOE.Nokia.com ([172.21.143.44]) by esebh104.NOE.Nokia.com with Microsoft SMTPSVC(6.0.3790.1830); Thu, 22 Sep 2005 19:37:02 +0300 X-MimeOLE: Produced By Microsoft Exchange V6.5.7226.0 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Subject: RE: [Cfrg] AES GMAC Date: Thu, 22 Sep 2005 19:37:00 +0300 Message-ID: Thread-Topic: [Cfrg] AES GMAC Thread-Index: AcW6Avrf5zdnTy42RQy78hkj82M0TQFg9opA To: X-OriginalArrivalTime: 22 Sep 2005 16:37:02.0051 (UTC) FILETIME=[DBE91330:01C5BF93] X-Spam-Score: 0.3 (/) X-Scan-Signature: 3002fc2e661cd7f114cb6bae92fe88f1 Content-Transfer-Encoding: quoted-printable Cc: henri.gilbert@francetelecom.com, housley@vigilsec.com, cfrg@ietf.org, matt.robshaw@francetelecom.com X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Dear David, Thanks for reading our note to NIST and for your response. Please find our comments inline. >> Our >> concern is that the GMAC construction proposed by MacGrew and Viega=20 >> does not meet this requirement. Indeed, for a message of length 2^m=20 >> blocks the forgery probability is about 2^{m-n}. In the current=20 >> proposal, upperbound of 2^{-64} to the forgery probability=20 >is achieved=20 >> by using 128-bit tags and setting an upperbound of 2^64 to=20 >the message=20 >> length. > >But in the internet draft under discussion, messages are not=20 >going to be anywhere near that length. The largest that an=20 >IPv4 packet can get is 64 kilobytes (2^{12} blocks), which=20 >puts the single packet forgery probability at 2^{-116}. This=20 >value compares favorably to that of the recommended ESP=20 >authentication methods, which use 96-bit tags. In practice,=20 >packets on the Internet are significantly smaller, and only=20 >very rarely exceed 2kb (256 blocks) (see=20 >http://www.caida.org/outreach/papers/1998/Inet98/Inet98.pdf or=20 >similar studies), and MTUs around this size are common. > This being the case, one could set (for example) - the upperbound of the message length to 2^{32} 128-bit blocks - the tag length to 96 bits - the big field size to 2^{128} and the small field size to 2^{96} And use the double layer construction. To do this one needs the following keys - 128-bit point K1 for polynomial evaluation in the big field - 96-bit point for K2 polynomial evaluation in the smaller field - 96-bit one-time-pad K0 generated using CTR-AES with 128-bit key K Your concern is where to get these keys. We suggest to generate them using CTR-AES. With the above parameters this would mean either 1) three calls to AES, if all K0, K1 and K2 are generated in this manner; or 2) two calls to AES, if we set K1 =3D K (as in your GMAC) and generate = K2 and K0 using CTR-AES. Note that both alternatives give also resistance against the "Multiple Forgery Attack" since for each message, the polynomial is evaluated at a different point.=20 =20 >> Using this construction, for example, 64-bit security level can be=20 >> achieved with 64-bit tags for messages of up to 2^{64}=20 >blocks, and it=20 >> does not take more key, or more calls to the AES, or=20 >essentially more=20 >> computations than with the construction by MacGrew and Viega. > >I don't understand the claim in the last sentence. Is the=20 >"second 64-bit quantity" \lambda in Section 3 of your note to=20 >NIST not additional key material? > The idea is the same as above. With one 128-bit key K and one call to the AES one has 256 bits of key material which is enough: (with the same notation as above) - K1 =3D K - 64-bit K2 (one half of the AES output) - 64-bit one-time-pad K0 (another half of the AES output) >p.s. - your note to NIST mentions that there is an ETSI SAGE=20 >effort that is considering MAC designs. It would be great if=20 >CFRG and the IETF could liaison with that group and hear a=20 >report on the status of this work. Could you please let me=20 >know who in ETSI I could bug about this? > The work is still on going and will be completed by the end of the year. In our note to NIST the main features of the new 3GPP Integrity Algorithm by ETSI SAGE are described. With best regards, Kaisa=20 _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Thu Sep 22 15:05:06 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIWNW-0005W1-Ua; Thu, 22 Sep 2005 15:05:06 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIWNU-0005VY-8F for cfrg@megatron.ietf.org; Thu, 22 Sep 2005 15:05:05 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA18165 for ; Thu, 22 Sep 2005 15:05:02 -0400 (EDT) Received: from sj-iport-3-in.cisco.com ([171.71.176.72] helo=sj-iport-3.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EIWTj-0001Tr-85 for cfrg@ietf.org; Thu, 22 Sep 2005 15:11:34 -0400 Received: from sj-core-2.cisco.com ([171.71.177.254]) by sj-iport-3.cisco.com with ESMTP; 22 Sep 2005 12:04:50 -0700 X-IronPort-AV: i="3.97,138,1125903600"; d="scan'208"; a="344537418:sNHT35543064" Received: from xbh-sjc-211.amer.cisco.com (xbh-sjc-211.cisco.com [171.70.151.144]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id j8MJ3wKo002405; Thu, 22 Sep 2005 12:04:44 -0700 (PDT) Received: from xfe-sjc-211.amer.cisco.com ([171.70.151.174]) by xbh-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 22 Sep 2005 12:04:46 -0700 Received: from [192.168.1.101] ([10.32.254.211]) by xfe-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 22 Sep 2005 12:04:45 -0700 In-Reply-To: References: Mime-Version: 1.0 (Apple Message framework v733) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <0BF857D2-FBFC-4E10-99EF-1B6494BA34A7@cisco.com> Content-Transfer-Encoding: 7bit From: David McGrew Subject: Re: [Cfrg] AES GMAC Date: Thu, 22 Sep 2005 12:04:46 -0700 To: X-Mailer: Apple Mail (2.733) X-OriginalArrivalTime: 22 Sep 2005 19:04:45.0332 (UTC) FILETIME=[7ED66D40:01C5BFA8] X-Spam-Score: 0.0 (/) X-Scan-Signature: 29dc808194f5fb921c09d0040806d6eb Content-Transfer-Encoding: 7bit Cc: henri.gilbert@francetelecom.com, housley@vigilsec.com, cfrg@ietf.org, matt.robshaw@francetelecom.com X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hi Kaisa, On Sep 22, 2005, at 9:37 AM, wrote: > Dear David, > > Thanks for reading our note to NIST and for your response. Please find > our comments inline. > > >>> Our >>> concern is that the GMAC construction proposed by MacGrew and Viega >>> does not meet this requirement. Indeed, for a message of length 2^m >>> blocks the forgery probability is about 2^{m-n}. In the current >>> proposal, upperbound of 2^{-64} to the forgery probability >>> >> is achieved >> >>> by using 128-bit tags and setting an upperbound of 2^64 to >>> >> the message >> >>> length. >>> >> >> But in the internet draft under discussion, messages are not >> going to be anywhere near that length. The largest that an >> IPv4 packet can get is 64 kilobytes (2^{12} blocks), which >> puts the single packet forgery probability at 2^{-116}. This >> value compares favorably to that of the recommended ESP >> authentication methods, which use 96-bit tags. In practice, >> packets on the Internet are significantly smaller, and only >> very rarely exceed 2kb (256 blocks) (see >> http://www.caida.org/outreach/papers/1998/Inet98/Inet98.pdf or >> similar studies), and MTUs around this size are common. >> >> > > This being the case, one could set (for example) > > - the upperbound of the message length to 2^{32} 128-bit blocks > - the tag length to 96 bits > - the big field size to 2^{128} and the small field size to 2^{96} > > And use the double layer construction. > > To do this one needs the following keys > - 128-bit point K1 for polynomial evaluation in the big field > - 96-bit point for K2 polynomial evaluation in the smaller field > - 96-bit one-time-pad K0 generated using CTR-AES with 128-bit key K > > Your concern is where to get these keys. We suggest to generate them > using CTR-AES. Of course, but a design intended for high throughput needs to take into account the delay due to the computation of K2. > With the above parameters this would mean either > 1) three calls to AES, if all K0, K1 and K2 are generated in this > manner; or > 2) two calls to AES, if we set K1 = K (as in your GMAC) and > generate K2 > and K0 using CTR-AES. > > Note that both alternatives give also resistance against the "Multiple > Forgery Attack" since for each message, the polynomial is evaluated > at a > different point. Here you mean that K2 is generated by using the nonce associated with the message, rather than using a 'special' nonce not associated with any message, right? This has performance implications for software, since it would disallow the use of key-dependent precomputation for speeding up multiplication. > > >>> Using this construction, for example, 64-bit security level can be >>> achieved with 64-bit tags for messages of up to 2^{64} >>> >> blocks, and it >> >>> does not take more key, or more calls to the AES, or >>> >> essentially more >> >>> computations than with the construction by MacGrew and Viega. >>> >> >> I don't understand the claim in the last sentence. Is the >> "second 64-bit quantity" \lambda in Section 3 of your note to >> NIST not additional key material? >> >> > > The idea is the same as above. With one 128-bit key K and one call to > the AES one has 256 bits of key material which is enough: (with the > same > notation as above) > - K1 = K > - 64-bit K2 (one half of the AES output) > - 64-bit one-time-pad K0 (another half of the AES output) Yes, I understand. My point was in reference to the need to either store and fetch the additional keying material or to compute it from the main key prior to using in the tag computation. With your two-stage approach, there may be a nice design opportunity. The secondary key K2 isn't needed until the very last part of the message processing algorithm, so it may well be possible to fit its computation into the encryption pipeline without adding much overall delay. (This is in contrast to the initial hash key, which in some cases is needed before the encryption pipeline is done in order to process message headers or other authenticated but not encrypted data.) > > >> p.s. - your note to NIST mentions that there is an ETSI SAGE >> effort that is considering MAC designs. It would be great if >> CFRG and the IETF could liaison with that group and hear a >> report on the status of this work. Could you please let me >> know who in ETSI I could bug about this? >> >> > > The work is still on going and will be completed by the end of the > year. > In our note to NIST the main features of the new 3GPP Integrity > Algorithm by ETSI SAGE are described. > Since telephony is in scope there, I'd expect that the new integrity algorithm would be of interest to IETF SRTP. The SRTP voip community would *welcome* a MAC that is more implementation-friendly to DSPs than HMAC-SHA1, so this is very interesting. The main challenge in this domain seems to be to find a MAC that's not a PRF yet provides similar security even with short tags. Best regards, David > With best regards, > > Kaisa > _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Thu Sep 22 16:11:44 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIXQ0-0006Hs-Ah; Thu, 22 Sep 2005 16:11:44 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIXPy-0006H6-Ir for cfrg@megatron.ietf.org; Thu, 22 Sep 2005 16:11:42 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA23774 for ; Thu, 22 Sep 2005 16:11:40 -0400 (EDT) Received: from sj-iport-1-in.cisco.com ([171.71.176.70] helo=sj-iport-1.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EIXWG-0003fv-LO for cfrg@ietf.org; Thu, 22 Sep 2005 16:18:13 -0400 Received: from sj-core-2.cisco.com ([171.71.177.254]) by sj-iport-1.cisco.com with ESMTP; 22 Sep 2005 13:11:31 -0700 X-IronPort-AV: i="3.97,138,1125903600"; d="scan'208"; a="661481986:sNHT30949226" Received: from xbh-sjc-231.amer.cisco.com (xbh-sjc-231.cisco.com [128.107.191.100]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id j8MKB0KW007862; Thu, 22 Sep 2005 13:11:24 -0700 (PDT) Received: from xfe-sjc-212.amer.cisco.com ([171.70.151.187]) by xbh-sjc-231.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 22 Sep 2005 13:11:28 -0700 Received: from [192.168.1.101] ([10.32.254.211]) by xfe-sjc-212.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 22 Sep 2005 13:11:20 -0700 In-Reply-To: <20050917115114.79641.qmail@cr.yp.to> References: <20050917115114.79641.qmail@cr.yp.to> Mime-Version: 1.0 (Apple Message framework v733) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: David McGrew Subject: Re: [Cfrg] UMAC draft changes Date: Thu, 22 Sep 2005 13:11:30 -0700 To: "D. J. Bernstein" X-Mailer: Apple Mail (2.733) X-OriginalArrivalTime: 22 Sep 2005 20:11:20.0910 (UTC) FILETIME=[CC633EE0:01C5BFB1] X-Spam-Score: 0.0 (/) X-Scan-Signature: 9a2be21919e71dc6faef12b370c4ecf5 Content-Transfer-Encoding: 7bit Cc: canetti Canetti , "'cfrg@ietf.org'" X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hi Dan, can you please provide your comments on the UMAC draft as responses or additions to the points that I've raised with the UMAC authors (at the outset of this thread)? It will be easier to track topics and draft changes this way. The goal of the research group here is, of course, to produce the best possible document. Specific comments about what text you think should be amended or added to the draft are the most helpful. Comments that could be interpreted as being about the motives or integrity of others are counterproductive. thanks, David and Ran CFRG co-chairs On Sep 17, 2005, at 4:51 AM, D. J. Bernstein wrote: > The UMAC draft claims that UMAC ``has been rigorously proven to be > secure,'' and specifically that ``an adversary ... can do no better > than > about 1/2^60'' per forgery attempt. > > That claim is false. Among other problems, the proven bound on forgery > probabilities includes an A^2/2^129 term, where A is the number of AES > evaluations. UMAC does not require that A be limited to, e.g., 2^34. > > The UMAC authors admit that the A^2/2^129 term exists in the proven > forgery-probability bound. They nevertheless attempt to weasel out of > correcting the falsehoods in their draft: > > * They talk about how long it would take for a single sender to > transmit 2^64 messages. So what? Transmitting 2^34 messages is a > billion times faster than that. > > * They claim that A^2/2^129 is an ``artifact of the proof.'' What > they mean, apparently, is that they know their proof produces bad > bounds, but they think they can do better. So what? The question > is about what ``has been rigorously proven,'' not about what the > UMAC authors speculate they might prove in the future. > > * They observe, correctly, that Shoup and I have proven something > better than A^2/2^129 for many other MACs. So what? The current > discussion is about UMAC, not those other MACs. Maybe my > techniques > work for UMAC, but maybe they don't. If the UMAC authors want to > claim that 1/2^60 ``has been rigorously proven'' then they > need to > show us the proof. > > * They claim that the A^2/2^129 term ``is widely believed to be > of no > practical consequences in any realistic setting.'' Even if > this is > true, so what? The question is about what ``has been rigorously > proven,'' not about what people might believe. > > The UMAC security claim is clearly, obviously, indisputably false. > When > I pointed this out eight months ago, the UMAC authors didn't > attempt to > defend their false claim, but they also didn't fix it; instead they > attempted to distract attention from it, just as they're doing now. > The > level of dishonesty here really amazes me. > > >> If the number of messages to be authenticated under one key is not >> astronomic and care is given to identify and act on forgery attempts, >> > > How, precisely, is one supposed to ``act on forgery attempts''? Close > the connection, allowing trivial denial of service? Generate a new > key, > again degrading service and then allowing the attacker to continue > with > the new key? > > >> In any case, the simple fact that someone could misuse short tags >> does not mean that they should be disallowed. >> > > Short tags should be disallowed. > > >> UMAC is optimized to run well on any processor that supports well 32- >> bit x 32-bit --> 64-bit multiplication. This is a large class of >> processors. >> > > And where are the benchmarks justifying these multiple-CPU performance > claims? All I see are Pentium 4 benchmarks relying heavily on PMULUDQ. > Unjustified claims of speed aren't as dangerous as unjustified > claims of > security, but they're still dishonest. > > ---D. J. Bernstein, Professor, Mathematics, Statistics, > and Computer Science, University of Illinois at Chicago > > _______________________________________________ > 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 cfrg-bounces@ietf.org Thu Sep 22 16:11:39 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIXPv-0006Ej-V2; Thu, 22 Sep 2005 16:11:39 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIXPs-0006EG-Oi for cfrg@megatron.ietf.org; Thu, 22 Sep 2005 16:11:38 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA23768 for ; Thu, 22 Sep 2005 16:11:34 -0400 (EDT) Received: from sj-iport-3-in.cisco.com ([171.71.176.72] helo=sj-iport-3.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EIXWA-0003fn-Cj for cfrg@ietf.org; Thu, 22 Sep 2005 16:18:07 -0400 Received: from sj-core-5.cisco.com ([171.71.177.238]) by sj-iport-3.cisco.com with ESMTP; 22 Sep 2005 13:11:25 -0700 X-IronPort-AV: i="3.97,138,1125903600"; d="scan'208"; a="344567743:sNHT34119260" Received: from xbh-sjc-211.amer.cisco.com (xbh-sjc-211.cisco.com [171.70.151.144]) by sj-core-5.cisco.com (8.12.10/8.12.6) with ESMTP id j8MKBI4Z012139; Thu, 22 Sep 2005 13:11:23 -0700 (PDT) Received: from xfe-sjc-212.amer.cisco.com ([171.70.151.187]) by xbh-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 22 Sep 2005 13:11:20 -0700 Received: from [192.168.1.101] ([10.32.254.211]) by xfe-sjc-212.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 22 Sep 2005 13:11:12 -0700 In-Reply-To: References: Mime-Version: 1.0 (Apple Message framework v733) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <67D14CA3-53A5-4A3A-B8BB-032212C2BAB2@cisco.com> Content-Transfer-Encoding: 7bit From: David McGrew Subject: Re: [Cfrg] UMAC draft changes Date: Thu, 22 Sep 2005 13:11:21 -0700 To: "'cfrg@ietf.org'" X-Mailer: Apple Mail (2.733) X-OriginalArrivalTime: 22 Sep 2005 20:11:13.0055 (UTC) FILETIME=[C7B4AAF0:01C5BFB1] X-Spam-Score: 0.0 (/) X-Scan-Signature: e8c5db863102a3ada84e0cd52a81a79e Content-Transfer-Encoding: 7bit Cc: Ted Krovetz X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hello CFRG, I'd like to solicit your input on the UMAC draft (http://www.ietf.org/ internet-drafts/draft-krovetz-umac-04.txt) and the issues outlined below. There is a difference of opinion on some of these points, and it would be valuable to the group for you to provide your perspective. If you feel that there is a point that needs to be clarified, or a caveat that needs to be made, please go ahead and suggest text that you feel is appropriate. Thanks! David On Sep 15, 2005, at 2:03 PM, Ted Krovetz wrote: > Hi David, > > We're happy to make some clarifications. We think that most points > that have been raised in recent postings to this list are covered > in the RFC itself (see the introduction and the extensive > ``Security considerations'' section). The one point that the RFC > does not address is timing attacks. We will submit a revision that > will include some ``warning'' to implementors regarding timing and > other side-channel attacks. However, we see nothing in UMAC that > makes it inherently vulnerable to these attacks. > > Let me further clarify some of the issues that you raise. > > >> 1. Information about the key may be leaked via timing attacks. >> The standard fix of implementing a fixed-time comparison will >> work, and in my opinion should be a MUST for UMAC implementations. >> > > We don't think the spec should mandate any particular > implementation technique to avoid timing attacks, or any other side- > channel attack, first because side-channel attacks are so open- > ended, and second because whether or not a timing attack is a > threat is so application dependent. Warning about timing attacks > seems to us more appropriate than mandating any particular counter- > measure. As said, we'll add such a warning in the RFC. > > >> Also, Dan Bernstein points out that the POLY64 hash might leak >> timing information. It would be good to get some quantification >> of this, if possible. >> > > There's no ``inherent'' leak in the POLY64 algorithm; it is an > implementation choice whether or not to try to make running time > data-independent in this algorithm. The illustrative reference code > that we provide leaks timing information in its POLY64 > implementation, and also in its choice of an off-the-shelf AES and > memcmp. This code was never intended to mask against timing > attacks. The fact that our reference code is open to timing > attacks has no bearing on the content of a UMAC RFC. We expect that > UMAC can be implemented in practical ways that eliminate the > possibility of timing attacks to the same extent that other table- > employing mechanisms can do so. > > >> 2. The security claims don't take into consideration the number of >> times that AES is evaluated. >> > > Formal statements of UMAC's security (in our papers) include the > Adv^prf term that implies the A^2/2^129 term if you consider a > block cipher. In high-level English descriptions, we omit focus or > mention of the prf-to-prp term delta=A^2/2^129 because it is both > well-understood (in particular, it is common to virtually all MAC > functions that involve block-cipher computations) and low-order (if > the weak link in your MAC algorithm is this term then you are doing > well!). In particular, the term A^2/2^129 appears to be more an > artifact of the proof than a real attack threat. This term is > widely believed to be of no practical consequences in any realistic > setting (and the results of Shoup and Bernstein prove it for some > cases). That is especially true if one uses less than 2^64 tags per > key, which is always the case in practice. > > For the sake of illustration, think of 8-byte tags for 2^64 > messages. Just for the tags themselves (not counting the messages > size), you have to send 8 * 2^64 bytes. Over a super-fast > 1GigaByte/second link, it will take 2^37 seconds or some 4000 > years! Now, not only you need the system (and attacker) to run for > that time but you also need all messages to be MACed with the SAME > KEY. The system doing that (and the patient attacker) deserve the > break!! > > We will consider writing something about this in the security > considerations. > > >> 3. The security claims seem to imply that repeat forgeries are not >> an issue, saying that ``a 1 / 2^60 forging probability means that >> if an attacker could try out 2^60 MACs, then the attacker would >> probably get one right.'' Isn't it the case with UMAC that an >> attacker who can perpetrate a successful forgery would be able to >> use information from that success to forge more messages? This >> issue is especially important because of the presence of short >> tags in the spec. >> > > This point is explicitly and clearly addressed in the security > considerations section (which is where such a discussion belongs) > under the heading of ``Tag lengths and forging probability'' (Sec > 6.2). The text there says: > > ``It should be pointed out that once an attempted forgery is > successful, it is possible, in principle, that subsequent messages > under this key may be forged, too. This is important to understand > in gauging the severity of a successful forgery, even though no > such attack on UMAC is known to date.'' > > So while it is not known how easy or hard it would be to produce > more forgeries once a first forgery is found, it is prudent to > assume that repeat forgeries *are* easy and that initial forgeries > should be avoided. > > UMAC was designed to support different levels of security. A > security architect should choose a tag length suitable for their > application. If the number of messages to be authenticated under > one key is not astronomic and care is given to identify and act on > forgery attempts, then 64-bit tags are appropriate. For low-value > content, 32-bit tags might be appropriate (after all, these have > been standard in retail banking for years...). For very high value > content, or if one anticipates a large number of forgery attempts, > UMAC offers a 96-bit tag (and even 128-bit tags for the really > paranoid). In any case, the simple fact that someone could misuse > short tags does not mean that they should be disallowed. We have > stated our opinion often, and still believe it, that 64-bit tags > are appropriate for most purposes, and if anyone needs more or > less, UMAC can accommodate that. > > Some other points brought up by Finney and Bernstein: > > >> UMAC has the property that tags can be verified incrementally, 32 >> bits at a time. >> > > This is true. Because UMAC operates by making independent hash > iterations, each producing 32-bits, and the results are > concatenated, it is possible to do fewer iterations than specified > in order to verify prefixes. However, by doing so the verifier may > provide the attacker with information that will reduce the security > of longer tags. As mentioned by Dave Wagner, a given key should > normally be used with tags of one given size. We will make sure > this is said quite explicitly in the RFC. > > >> It is important with these kinds of MACs that the nonce never be >> re-used for a given key. However the pad definition function >> takes a nonce of variable length >> > > We agree, and the second sentence of the ``Nonce considerations'' > subsection says, ``All nonces in an authentication session must be > equal in length.'' > > >> The hash function is a Pentium-4-optimized-and-other-machines-be- >> damned complication ... >> > > UMAC is optimized to run well on any processor that supports well > 32-bit x 32-bit --> 64-bit multiplication. This is a large class of > processors. As it turns out, the SSE instructions on the Pentium 4 > allows parallel computations of this sort, but it is a gross mis- > representation that UMAC is ``Pentium-4-optimized-and-other- > machines-be-damned''. > > > Regards, > John Black > Shai Halevi > Hugo Krawczyk > Ted Krovetz > Phillip Rogaway > > _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From owner-ietf-openpgp@mail.imc.org Thu Sep 22 16:11:05 2005 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIXPN-0006AR-0T for openpgp-archive@megatron.ietf.org; Thu, 22 Sep 2005 16:11:05 -0400 Received: from above.proper.com (above.proper.com [208.184.76.39]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA23738 for ; Thu, 22 Sep 2005 16:11:02 -0400 (EDT) Received: from above.proper.com (localhost.vpnc.org [127.0.0.1]) by above.proper.com (8.12.11/8.12.9) with ESMTP id j8MJaiba060894; Thu, 22 Sep 2005 12:36:44 -0700 (PDT) (envelope-from owner-ietf-openpgp@mail.imc.org) Received: (from majordom@localhost) by above.proper.com (8.12.11/8.12.9/Submit) id j8MJaii4060893; Thu, 22 Sep 2005 12:36:44 -0700 (PDT) X-Authentication-Warning: above.proper.com: majordom set sender to owner-ietf-openpgp@mail.imc.org using -f Received: from sccrmhc11.comcast.net (sccrmhc11.comcast.net [63.240.76.21]) by above.proper.com (8.12.11/8.12.9) with ESMTP id j8MJah6D060884 for ; Thu, 22 Sep 2005 12:36:43 -0700 (PDT) (envelope-from dshaw@jabberwocky.com) Received: from walrus.hsd1.ma.comcast.net ([24.60.132.70]) by comcast.net (sccrmhc11) with ESMTP id <2005092219363801100pd5gre>; Thu, 22 Sep 2005 19:36:38 +0000 Received: from grover.jabberwocky.com (grover.jabberwocky.com [172.24.84.28]) by walrus.hsd1.ma.comcast.net (8.12.8/8.12.8) with ESMTP id j8MJac0m026622 for ; Thu, 22 Sep 2005 15:36:38 -0400 Received: from grover.jabberwocky.com (grover.jabberwocky.com [127.0.0.1]) by grover.jabberwocky.com (8.13.1/8.13.1) with ESMTP id j8MJaapt000457 for ; Thu, 22 Sep 2005 15:36:36 -0400 Received: (from dshaw@localhost) by grover.jabberwocky.com (8.13.1/8.13.1/Submit) id j8MJaate000456 for ietf-openpgp@imc.org; Thu, 22 Sep 2005 15:36:36 -0400 Date: Thu, 22 Sep 2005 15:36:36 -0400 From: David Shaw To: ietf-openpgp@imc.org Subject: Re: Some thoughts on a v5 key and why it shouldn't be a mess (fwd) Message-ID: <20050922193636.GE32759@jabberwocky.com> Mail-Followup-To: ietf-openpgp@imc.org References: <20050921202208.GB18050@jabberwocky.com> <20050921210015.GA2316@epointsystem.org> <200509222100.01040@zaphod.konrad.silmor.de> <20050922191832.GB2481@epointsystem.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20050922191832.GB2481@epointsystem.org> OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc User-Agent: Mutt/1.5.8i Sender: owner-ietf-openpgp@mail.imc.org Precedence: bulk List-Archive: List-Unsubscribe: List-ID: On Thu, Sep 22, 2005 at 09:18:36PM +0200, Daniel A. Nagy wrote: > > On Thu, Sep 22, 2005 at 09:00:00PM +0200, Konrad Rosenbaum wrote: > > > Let's say MDX is broken by some genius. > > Remember, that the key ID is the last 8 (or four) byes of the fingerprint. > If MDX is broken, one can generatet a key with an arbitrary ID. Well yes, but someone can generate a key with an arbitrary ID today. Even forgetting the DEADBEEF games that are possible with v3 RSA keys, there is a program out there that generates v4 DSA keys over and over until the requested (short) key ID comes up. David From cfrg-bounces@ietf.org Thu Sep 22 17:05:07 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIYFf-0001Df-Fm; Thu, 22 Sep 2005 17:05:07 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIXe4-0001gK-RZ for cfrg@megatron.ietf.org; Thu, 22 Sep 2005 16:26:16 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA24414 for ; Thu, 22 Sep 2005 16:26:14 -0400 (EDT) Received: from ylpvm15-ext.prodigy.net ([207.115.57.46] helo=ylpvm15.prodigy.net) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EIXkM-00040R-EZ for cfrg@ietf.org; Thu, 22 Sep 2005 16:32:47 -0400 Received: from pimout7-ext.prodigy.net (pimout7-int.prodigy.net [207.115.4.147]) by ylpvm15.prodigy.net (8.12.10 outbound/8.12.10) with ESMTP id j8MKQB8S007900 for ; Thu, 22 Sep 2005 16:26:11 -0400 X-ORBL: [66.127.112.169] Received: from [192.168.0.101] (adsl-66-127-112-169.dsl.scrm01.pacbell.net [66.127.112.169]) by pimout7-ext.prodigy.net (8.13.4 outbound domainkey aix/8.13.4) with ESMTP id j8MKQ3WW442866; Thu, 22 Sep 2005 16:26:03 -0400 In-Reply-To: <67D14CA3-53A5-4A3A-B8BB-032212C2BAB2@cisco.com> References: <67D14CA3-53A5-4A3A-B8BB-032212C2BAB2@cisco.com> Mime-Version: 1.0 (Apple Message framework v734) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: Ted Krovetz Subject: Re: [Cfrg] UMAC draft changes Date: Thu, 22 Sep 2005 13:26:00 -0700 To: David McGrew X-Mailer: Apple Mail (2.734) X-Spam-Score: 0.1 (/) X-Scan-Signature: 0bc60ec82efc80c84b8d02f4b0e4de22 Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Thu, 22 Sep 2005 17:05:02 -0400 Cc: "'cfrg@ietf.org'" X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hold on... > I'd like to solicit your input on the UMAC draft (http:// > www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt) and the > issues outlined below. There is a difference of opinion on some of > these points, and it would be valuable to the group for you to > provide your perspective. We are putting the finishing touches on a revised internet-draft that clarifies much of these issues. In particular: - We make it clear that POLY is open to timing attacks if an implementation is not careful. - We recommend that prefix verification should not be allowed. - We clarify that the number of AES calls is not an issue by referring to Bernstein's work at http://cr.yp.to/antiforgery/ permutations-20050323.pdf (in particular the beautiful Theorem 2.3). Please hold off on comments until we get the revised draft posted. Thank you, Ted Krovetz _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Thu Sep 22 17:59:23 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIZ6B-0004ag-EE; Thu, 22 Sep 2005 17:59:23 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIZ69-0004Yb-Mg for cfrg@megatron.ietf.org; Thu, 22 Sep 2005 17:59:22 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA28242 for ; Thu, 22 Sep 2005 17:59:19 -0400 (EDT) Received: from sj-iport-3-in.cisco.com ([171.71.176.72] helo=sj-iport-3.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EIZCR-0005yK-V1 for cfrg@ietf.org; Thu, 22 Sep 2005 18:05:53 -0400 Received: from sj-core-2.cisco.com ([171.71.177.254]) by sj-iport-3.cisco.com with ESMTP; 22 Sep 2005 14:59:09 -0700 X-IronPort-AV: i="3.97,138,1125903600"; d="scan'208"; a="344611938:sNHT29669282" Received: from xbh-sjc-231.amer.cisco.com (xbh-sjc-231.cisco.com [128.107.191.100]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id j8MLx2KE001724; Thu, 22 Sep 2005 14:59:04 -0700 (PDT) Received: from xfe-sjc-211.amer.cisco.com ([171.70.151.174]) by xbh-sjc-231.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 22 Sep 2005 14:59:00 -0700 Received: from [192.168.1.101] ([10.32.254.211]) by xfe-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 22 Sep 2005 14:58:59 -0700 In-Reply-To: References: <67D14CA3-53A5-4A3A-B8BB-032212C2BAB2@cisco.com> Mime-Version: 1.0 (Apple Message framework v733) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <96BF29BE-F752-4AC3-BD24-C286481B7FE9@cisco.com> Content-Transfer-Encoding: 7bit From: David McGrew Subject: Re: [Cfrg] UMAC draft changes Date: Thu, 22 Sep 2005 14:59:01 -0700 To: Ted Krovetz X-Mailer: Apple Mail (2.733) X-OriginalArrivalTime: 22 Sep 2005 21:58:59.0597 (UTC) FILETIME=[D610ABD0:01C5BFC0] X-Spam-Score: 0.0 (/) X-Scan-Signature: c1c65599517f9ac32519d043c37c5336 Content-Transfer-Encoding: 7bit Cc: "'cfrg@ietf.org'" X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Ted, On Sep 22, 2005, at 1:26 PM, Ted Krovetz wrote: > Hold on... > > >> I'd like to solicit your input on the UMAC draft (http:// >> www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt) and the >> issues outlined below. There is a difference of opinion on some >> of these points, and it would be valuable to the group for you to >> provide your perspective. >> > > We are putting the finishing touches on a revised internet-draft > that clarifies much of these issues. That's great. > > In particular: > > - We make it clear that POLY is open to timing attacks if an > implementation is not careful. > > - We recommend that prefix verification should not be allowed. > > - We clarify that the number of AES calls is not an issue by > referring to Bernstein's work at http://cr.yp.to/antiforgery/ > permutations-20050323.pdf (in particular the beautiful Theorem 2.3). Is this a preprint of the "better bounds" work published at Eurocrypt this year? > > Please hold off on comments until we get the revised draft posted. > Yes, makes sense. thanks, David > Thank you, > Ted Krovetz > _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Fri Sep 23 13:47:26 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIrdu-0000vi-UL; Fri, 23 Sep 2005 13:47:26 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EIrdt-0000vR-De for cfrg@megatron.ietf.org; Fri, 23 Sep 2005 13:47:25 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA26964 for ; Fri, 23 Sep 2005 13:47:24 -0400 (EDT) Received: from sj-iport-2-in.cisco.com ([171.71.176.71] helo=sj-iport-2.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EIrkM-0004N7-4J for cfrg@ietf.org; Fri, 23 Sep 2005 13:54:07 -0400 Received: from sj-core-2.cisco.com ([171.71.177.254]) by sj-iport-2.cisco.com with ESMTP; 23 Sep 2005 10:47:14 -0700 Received: from xbh-sjc-211.amer.cisco.com (xbh-sjc-211.cisco.com [171.70.151.144]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id j8NHkeKY025651; Fri, 23 Sep 2005 10:47:08 -0700 (PDT) Received: from xfe-sjc-211.amer.cisco.com ([171.70.151.174]) by xbh-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Fri, 23 Sep 2005 10:47:10 -0700 Received: from [192.168.1.100] ([10.32.254.211]) by xfe-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Fri, 23 Sep 2005 10:47:09 -0700 In-Reply-To: <10473.80.212.233.145.1127420587.squirrel@webmail.hia.no> References: <0BF857D2-FBFC-4E10-99EF-1B6494BA34A7@cisco.com> <10473.80.212.233.145.1127420587.squirrel@webmail.hia.no> Mime-Version: 1.0 (Apple Message framework v733) X-Priority: 3 (Normal) Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Message-Id: <12B168B3-F9AA-40E1-9BA9-86CCB3972756@cisco.com> Content-Transfer-Encoding: quoted-printable From: David McGrew Date: Fri, 23 Sep 2005 10:47:11 -0700 To: geir.koien@hia.no X-Mailer: Apple Mail (2.733) X-OriginalArrivalTime: 23 Sep 2005 17:47:09.0788 (UTC) FILETIME=[D25489C0:01C5C066] X-Spam-Score: 0.0 (/) X-Scan-Signature: a7d2e37451f7f22841e3b6f40c67db0f Content-Transfer-Encoding: quoted-printable Cc: cfrg@ietf.org Subject: [Cfrg] ETSI SAGE X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Geir, thanks for the info! The SNOW cipher is quite interesting, so it was a pleasant surprise =20 to find it in the specification (for others: in the d2_draft document =20= in the .zip file at the website that Geir referenced). Do you know =20 what, if any, differences there are between the "snow 3g" variant =20 that it defines and the "snow 2" version defined in SAC '02? David On Sep 22, 2005, at 1:23 PM, geir.koien@hia.no wrote: > Hi, > > The new UMTS integrity and confidentiality algorithms is currently =20 > under > security evaulation. They are *not* yet approved as standards for =20 > UMTS. > Anyway, the basis is SNOW and the temporary documents (tdoc's) are > released on the 3GPP web. > > You can fetch them via the email list at > http://list.3gpp.org/scripts/wa.exe?=20 > A2=3Dind0509&L=3D3gpp_tsg_sa_wg3&T=3D0&O=3DA&P=3D5277 > > ETSI SAGE is commisioned by the 3GPP SA3 group to do the =20 > development work. > This is the SA3 meeting minutes on the new algorithms: > > ******* > > TD S3-050579 contained a report from ETSI Sage. > ETSI SAGE project team STF 278 has produced draft specifications =20 > for UEA2 > and UIA2 According to the project plan and the SA3 decisions at SA3 > meetings #38 and #39 they are now going for public evaluation. This =20= > will > be performed by two contracted academic teams. Evaluation is of course > also open to all SA3 members and interested parties. The period for > external evaluation of the algorithms is 1st September - 30th =20 > October, so > anything received after the end of October may be too late. > It was noted that the UEA2 and UIA2 have a different structure than =20= > Kasumi > so that a potential break in Kasumi need not lead to the cracking =20 > of UEA2 > and UIA2. Based on this, it was noted that the evaluation period is =20= > short. > However, it was also noted that UEA2 and UIA2 are based on SNOW, =20 > which has > been available for some time. Still it was questioned why this is =20 > being > rushed. It was answered that there is a paid analysis and there is =20 > a time > limit on this hence the deadline. Also, the intention of the UEA2 =20 > and UIA2 > is to replace Kasumi if Kasumi should be broken. > However, the public evaluation (public scrutiny) is being based on > voluntary contributions and it was asked if the period could be =20 > extended > to allow for public comments. > A counter proposal was that the existing schedule should be kept in =20= > order > to allow UEA2 and UIA2 to be frozen and be part of Rel-7 as a =20 > candidate > for early implmentation. This would allow for mobile manufacturers to > implment UEA2 and UIA2 in the mobiles early; something that will not > happen unless the algorithms are frozen and mobile manufacturers =20 > gets some > assurance that it will not change. Of course, it is SA that decides if > this is for early implementation although only on the advice of SA3. > The chairman commented that some extra time could be given in order to > allow for comments from voluntary evaluators. The chairman asked if =20= > SAGE > could wait a little longer. If an error is found, then SAGE is the =20 > best > group to evaluate any comments. > It was decided to targetting the delivery of the final =20 > specifications as a > normal part of Rel-7. This will give some extra time to voluntary > evaluations. > Another question was if the paid for evaluations will be made =20 > public. It > was answered that there will be a report from SAGE on its work and =20 > this > will contain information on the evaluations of its work. > > ****** > > So, basically, you are welcome to comment on the algorithms at this =20= > stage, > but you should not yet plan to use them. > > BR, > > /Geir M. K=F8ien > Telenor R&D and Agder University College > > _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Tue Sep 27 09:05:36 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKF9M-0002IB-9K; Tue, 27 Sep 2005 09:05:36 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKF9I-0002HI-GO for cfrg@megatron.ietf.org; Tue, 27 Sep 2005 09:05:33 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA05876 for ; Tue, 27 Sep 2005 09:05:31 -0400 (EDT) Received: from sj-iport-2-in.cisco.com ([171.71.176.71] helo=sj-iport-2.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EKFGW-0004VI-4F for cfrg@ietf.org; Tue, 27 Sep 2005 09:13:02 -0400 Received: from sj-core-2.cisco.com ([171.71.177.254]) by sj-iport-2.cisco.com with ESMTP; 27 Sep 2005 06:05:21 -0700 Received: from xbh-sjc-211.amer.cisco.com (xbh-sjc-211.cisco.com [171.70.151.144]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id j8RD53KO027661; Tue, 27 Sep 2005 06:05:16 -0700 (PDT) Received: from xfe-sjc-211.amer.cisco.com ([171.70.151.174]) by xbh-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Tue, 27 Sep 2005 06:05:16 -0700 Received: from [192.168.1.100] ([10.32.254.212]) by xfe-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Tue, 27 Sep 2005 06:05:15 -0700 In-Reply-To: <12B168B3-F9AA-40E1-9BA9-86CCB3972756@cisco.com> References: <0BF857D2-FBFC-4E10-99EF-1B6494BA34A7@cisco.com> <10473.80.212.233.145.1127420587.squirrel@webmail.hia.no> <12B168B3-F9AA-40E1-9BA9-86CCB3972756@cisco.com> Mime-Version: 1.0 (Apple Message framework v733) X-Priority: 3 (Normal) Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: quoted-printable From: David McGrew Subject: Re: [Cfrg] ETSI SAGE Date: Tue, 27 Sep 2005 06:05:03 -0700 To: cfrg@ietf.org X-Mailer: Apple Mail (2.733) X-OriginalArrivalTime: 27 Sep 2005 13:05:15.0468 (UTC) FILETIME=[1A4320C0:01C5C364] X-Spam-Score: 0.0 (/) X-Scan-Signature: 8fbbaa16f9fd29df280814cb95ae2290 Content-Transfer-Encoding: quoted-printable Cc: geir.koien@hia.no X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org On Sep 23, 2005, at 10:47 AM, David McGrew wrote: > Geir, > > thanks for the info! > > The SNOW cipher is quite interesting, so it was a pleasant surprise =20= > to find it in the specification (for others: in the d2_draft =20 > document in the .zip file at the website that Geir referenced). Do =20= > you know what, if any, differences there are between the "snow 3g" =20 > variant that it defines and the "snow 2" version defined in SAC '02? FYI: I hear that it is an sbox change due to the work of Billet and =20 Gilbert (thanks to Mats N=E4slund for pointing this out). Olivier Billet and Henri Gilbert, Resistance of SNOW 2.0 Against =20 Algebraic Attacks. Available on Springer Online at http://=20 www.springerlink.com/(gp2ell45rueskr55umggnr55)/app/home/=20 contribution.asp?referrer=3Dparent&backto=3Dissue,3,25;journal,=20 281,2200;linkingpublicationresults,1:105633,1 David > > David > > On Sep 22, 2005, at 1:23 PM, geir.koien@hia.no wrote: > > >> Hi, >> >> The new UMTS integrity and confidentiality algorithms is currently =20= >> under >> security evaulation. They are *not* yet approved as standards for =20 >> UMTS. >> Anyway, the basis is SNOW and the temporary documents (tdoc's) are >> released on the 3GPP web. >> >> You can fetch them via the email list at >> http://list.3gpp.org/scripts/wa.exe?=20 >> A2=3Dind0509&L=3D3gpp_tsg_sa_wg3&T=3D0&O=3DA&P=3D5277 >> >> ETSI SAGE is commisioned by the 3GPP SA3 group to do the =20 >> development work. >> This is the SA3 meeting minutes on the new algorithms: >> >> ******* >> >> TD S3-050579 contained a report from ETSI Sage. >> ETSI SAGE project team STF 278 has produced draft specifications =20 >> for UEA2 >> and UIA2 According to the project plan and the SA3 decisions at SA3 >> meetings #38 and #39 they are now going for public evaluation. =20 >> This will >> be performed by two contracted academic teams. Evaluation is of =20 >> course >> also open to all SA3 members and interested parties. The period for >> external evaluation of the algorithms is 1st September - 30th =20 >> October, so >> anything received after the end of October may be too late. >> It was noted that the UEA2 and UIA2 have a different structure =20 >> than Kasumi >> so that a potential break in Kasumi need not lead to the cracking =20 >> of UEA2 >> and UIA2. Based on this, it was noted that the evaluation period =20 >> is short. >> However, it was also noted that UEA2 and UIA2 are based on SNOW, =20 >> which has >> been available for some time. Still it was questioned why this is =20 >> being >> rushed. It was answered that there is a paid analysis and there is =20= >> a time >> limit on this hence the deadline. Also, the intention of the UEA2 =20 >> and UIA2 >> is to replace Kasumi if Kasumi should be broken. >> However, the public evaluation (public scrutiny) is being based on >> voluntary contributions and it was asked if the period could be =20 >> extended >> to allow for public comments. >> A counter proposal was that the existing schedule should be kept =20 >> in order >> to allow UEA2 and UIA2 to be frozen and be part of Rel-7 as a =20 >> candidate >> for early implmentation. This would allow for mobile manufacturers to >> implment UEA2 and UIA2 in the mobiles early; something that will not >> happen unless the algorithms are frozen and mobile manufacturers =20 >> gets some >> assurance that it will not change. Of course, it is SA that =20 >> decides if >> this is for early implementation although only on the advice of SA3. >> The chairman commented that some extra time could be given in =20 >> order to >> allow for comments from voluntary evaluators. The chairman asked =20 >> if SAGE >> could wait a little longer. If an error is found, then SAGE is the =20= >> best >> group to evaluate any comments. >> It was decided to targetting the delivery of the final =20 >> specifications as a >> normal part of Rel-7. This will give some extra time to voluntary >> evaluations. >> Another question was if the paid for evaluations will be made =20 >> public. It >> was answered that there will be a report from SAGE on its work and =20= >> this >> will contain information on the evaluations of its work. >> >> ****** >> >> So, basically, you are welcome to comment on the algorithms at =20 >> this stage, >> but you should not yet plan to use them. >> >> BR, >> >> /Geir M. K=F8ien >> Telenor R&D and Agder University College >> >> >> > > _______________________________________________ > 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 cfrg-bounces@ietf.org Tue Sep 27 16:19:23 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKLv9-0002cs-0p; Tue, 27 Sep 2005 16:19:23 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKLv7-0002c7-1R for cfrg@megatron.ietf.org; Tue, 27 Sep 2005 16:19:21 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA14562 for ; Tue, 27 Sep 2005 16:19:18 -0400 (EDT) Received: from pimout5-ext.prodigy.net ([207.115.63.73]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EKM2M-0002w7-IQ for cfrg@ietf.org; Tue, 27 Sep 2005 16:26:54 -0400 X-ORBL: [66.127.112.169] Received: from [192.168.0.101] (adsl-66-127-112-169.dsl.scrm01.pacbell.net [66.127.112.169]) by pimout5-ext.prodigy.net (8.13.4 outbound domainkey aix/8.13.4) with ESMTP id j8RKJBIl165016 for ; Tue, 27 Sep 2005 16:19:11 -0400 Mime-Version: 1.0 (Apple Message framework v734) Content-Transfer-Encoding: 7bit Message-Id: Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: cfrg@ietf.org From: Ted Krovetz Date: Tue, 27 Sep 2005 13:19:02 -0700 X-Mailer: Apple Mail (2.734) X-Spam-Score: 0.1 (/) X-Scan-Signature: 97adf591118a232206bdb5a27b217034 Content-Transfer-Encoding: 7bit Subject: [Cfrg] New UMAC Draft X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hello, In response to various comments in this list we have revised the UMAC draft. http://www.ietf.org/internet-drafts/draft-krovetz-umac-05.txt We have not changed anything algorithmically or in the specification of UMAC, nor have we changed any of our claims. But we added further clarifications where needed according to the received comments. The most substantive changes we made were * Addressing explicitly the insignificance of the birthday bound in the context of UMAC. In particular, the Security Considerations section now states explicitly that our forgery bounds on UMAC hold for up to the generation of 2^64 MAC tags, citing Bernstein's work in this area. * Added a paragraph in the Security section warning against the possibility of timing-attacks is POLY is not carefully implemented. * Added a paragraph in the Security section warning against prefix- verification. We also took this opportunity to make numerous editorial changes that caught our eyes while we made these other changes. We thank those providing well-intended comments. Thank you, Ted Krovetz _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Tue Sep 27 20:00:11 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKPMp-0000SQ-3R; Tue, 27 Sep 2005 20:00:11 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKPMn-0000SL-AR for cfrg@megatron.ietf.org; Tue, 27 Sep 2005 20:00:09 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA29383 for ; Tue, 27 Sep 2005 20:00:08 -0400 (EDT) Received: from qproxy.gmail.com ([72.14.204.195]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EKPU7-0000za-R0 for cfrg@ietf.org; Tue, 27 Sep 2005 20:07:45 -0400 Received: by qproxy.gmail.com with SMTP id a33so230230qbd for ; Tue, 27 Sep 2005 16:59:55 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=Z8z9tN42lmkBwxRmZn2iPo/rUwSU3RHkA1qcHjDjn7bpcZMS5zWW6FVGrukR3B2ui7L/dEvgh+oWq6sc+GeGF43F5fgsJNlFNOBlRmu0WbezqGYkVIIYblERJ9MIPrTYN5Fct/gacacRt3S1qYXkh0u8s5KVUFiJLjpQyRGN1Vc= Received: by 10.65.15.20 with SMTP id s20mr312192qbi; Tue, 27 Sep 2005 16:59:55 -0700 (PDT) Received: by 10.64.210.1 with HTTP; Tue, 27 Sep 2005 16:59:55 -0700 (PDT) Message-ID: Date: Tue, 27 Sep 2005 16:59:55 -0700 From: Hal Finney To: cfrg@ietf.org Subject: Fwd: [Cfrg] New UMAC Draft In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline References: X-Spam-Score: 0.0 (/) X-Scan-Signature: 082a9cbf4d599f360ac7f815372a6a15 Content-Transfer-Encoding: quoted-printable X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: Hal Finney List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org ---------- Forwarded message ---------- From: Hal Finney Date: Sep 27, 2005 4:58 PM Subject: Re: [Cfrg] New UMAC Draft To: Ted Krovetz On 9/27/05, Ted Krovetz wrote: > http://www.ietf.org/internet-drafts/draft-krovetz-umac-05.txt I have been wondering about the problem of attackers reusing nonces. At the end of section 6.2 you write: It should be pointed out that once an attempted forgery is successful, it is possible, in principle, that subsequent messages under this key may be forged, too. This is important to understand in gauging the severity of a successful forgery, even though no such attack on UMAC is known to date. I don't know if you have looked into this "in principle" possibility very much, but I don't see a lot of resistance in UMAC against finding subsequent forgeries with a given nonce, once you have valid tags for two different (perhaps chosen) messages with that nonce. I haven't worked it out in detail but it looks like it should be possible to use the information from a valid forgery to speed up subsequent forgeries (all with the same nonce). Do you have any estimations of how resistant UMAC is likely to be to such an attack? Was such resistance part of the UMAC design? This affects the discussion of the replay attack in 6.4: A replay attack entails the attacker repeating a message, nonce, and authentication tag. In many applications, replay attacks may be quite damaging and must be prevented. In UMAC, this would normally be done at the receiver by having the receiver check that no nonce value is used twice. There are really two kinds of replay attacks: message+nonce replays as is described in the first sentence; and nonce replays (with different messages). These latter attacks are how one would exploit the theoretical vulnerability mentioned above. Now, the countermeasure suggested here, watching for duplicate nonces, successfully defends against both attacks. However the discussion does not make the threat of the nonce replay attack very clear. I am concerned that these theoretical nonce-replay attacks may become possible. However the way the issue is presented, an implementor may not realize that he has to worry about them. He might choose UMAC-32 in an environment where plain replay attacks are not a problem, but still think he is not going to have more than 1/2^30 of the messages come through as forgeries. In that case he would be vulnerable if it does turn out to be possible to multiply forgeries. My opinion is that UMAC-32 is really not a very safe mode of operation due to this problem. At a minimum, you need to emphasize the importance of avoiding nonce replays. With UMAC-64 on up it is really not an issue because finding the first forgery is so difficult that you can pretty much ignore it. But with UMAC-32 it is very possible, and if that first forgery leads cheaply to others (in an environment which doesn't detect nonce replays) the security is lost. Hal Finney _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Tue Sep 27 23:00:31 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKSBL-00016I-MD; Tue, 27 Sep 2005 23:00:31 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKSBJ-00016D-U9 for cfrg@megatron.ietf.org; Tue, 27 Sep 2005 23:00:29 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id XAA09592 for ; Tue, 27 Sep 2005 23:00:27 -0400 (EDT) Received: from ylpvm12-ext.prodigy.net ([207.115.57.43] helo=ylpvm12.prodigy.net) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EKSIg-0005yA-Aj for cfrg@ietf.org; Tue, 27 Sep 2005 23:08:07 -0400 Received: from ylpvm01.prodigy.net (ylpvm01-int.prodigy.net [207.115.5.207]) by ylpvm12.prodigy.net (8.12.10 outbound/8.12.10) with ESMTP id j8S30Grk006805 for ; Tue, 27 Sep 2005 23:00:16 -0400 X-ORBL: [66.127.112.169] Received: from [192.168.0.101] (adsl-66-127-112-169.dsl.scrm01.pacbell.net [66.127.112.169]) by ylpvm01.prodigy.net (8.13.4 dk-milter linux/8.13.4) with ESMTP id j8S2xsF7013313; Tue, 27 Sep 2005 22:59:54 -0400 In-Reply-To: References: Mime-Version: 1.0 (Apple Message framework v734) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <6F37EC53-72F6-46D7-B1D0-470D17540737@acm.org> Content-Transfer-Encoding: 7bit From: Ted Krovetz Subject: Re: [Cfrg] New UMAC Draft Date: Tue, 27 Sep 2005 20:00:23 -0700 To: Hal Finney X-Mailer: Apple Mail (2.734) X-Spam-Score: 2.4 (++) X-Scan-Signature: 798b2e660f1819ae38035ac1d8d5e3ab Content-Transfer-Encoding: 7bit Cc: cfrg@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hal, > I have been wondering about the problem of attackers reusing nonces. In the standard security model of MACs, the adversary is allowed to repeat nonces when attempting to forge. So our N/2^{30,60,90,120} bound for at least one successful forgery over N attempts holds even if the verifier is not checking for repeated nonces. So, in actuality replays are the only ones we really care about, and we can defend against them by disallowing repeated nonces. Now it is most likely true that an attacker wishing himself success would like to attack 32-bit nonces on a system that allows repeated nonces because that is likely the scenario that maximizes his probability of success, but that success is still bounded by N/2^30. How much stronger would UMAC be if repeated nonces were not allowed for forgery attempts? The new nonce would cause a new, nearly random pad value, making the chance that the tag matches h(m) xor aes(nonce) about 1/2^32. -Ted _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Wed Sep 28 08:10:50 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKalu-00078H-Jf; Wed, 28 Sep 2005 08:10:50 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKals-000780-Gz for cfrg@megatron.ietf.org; Wed, 28 Sep 2005 08:10:48 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id IAA01845 for ; Wed, 28 Sep 2005 08:10:47 -0400 (EDT) Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1EKatJ-0002ka-KR for cfrg@ietf.org; Wed, 28 Sep 2005 08:18:30 -0400 Received: (qmail 13295 invoked by uid 1016); 28 Sep 2005 12:10:59 -0000 Date: 28 Sep 2005 12:10:59 -0000 Message-ID: <20050928121059.13294.qmail@cr.yp.to> Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html. From: "D. J. Bernstein" To: cfrg@ietf.org Subject: Re: [Cfrg] New UMAC Draft References: <6F37EC53-72F6-46D7-B1D0-470D17540737@acm.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Score: 0.0 (/) X-Scan-Signature: de4f315c9369b71d7dd5909b42224370 X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Ted Krovetz writes: > How much stronger would UMAC be if repeated nonces were not allowed > for forgery attempts? So, if you use the standard nonce sequence 0, 1, 2, 3, ..., the attacker can destroy your connection by first sending forgeries with nonces 0, 1, 2, 3, ...? Brilliant. Of course, this ludicrously fragile network protocol fails to solve the problem under discussion, which is that your 2^30-packet attacker gains so much information about the UMAC key (by seeing which forgeries work) that he can then trivially replace all of your subsequent messages with the messages of his choice. If he prevents the original messages from getting through then there won't be any repeated nonces to detect. ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Wed Sep 28 09:48:58 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKcIs-00031v-FB; Wed, 28 Sep 2005 09:48:58 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKcIq-00031q-O9 for cfrg@megatron.ietf.org; Wed, 28 Sep 2005 09:48:56 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA08085 for ; Wed, 28 Sep 2005 09:48:55 -0400 (EDT) Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1EKcQI-0005jM-Py for cfrg@ietf.org; Wed, 28 Sep 2005 09:56:40 -0400 Received: (qmail 34061 invoked by uid 1016); 28 Sep 2005 13:49:13 -0000 Date: 28 Sep 2005 13:49:13 -0000 Message-ID: <20050928134913.34060.qmail@cr.yp.to> Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html. From: "D. J. Bernstein" To: cfrg@ietf.org Subject: Re: [Cfrg] New UMAC Draft References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Score: 0.0 (/) X-Scan-Signature: b19722fc8d3865b147c75ae2495625f2 X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Ted Krovetz writes: > In particular, the Security Considerations section > now states explicitly that our forgery bounds on UMAC hold for up > to the generation of 2^64 MAC tags I don't believe you. Your paper claims ``no more than 1/2^60,'' but it isn't possible to obtain the exact 1/2^60 bound from feeding a 1/2^60 function bound through a function-to-permutation switch, even if (as you claim) the switch is applicable. Something close to 1/2^60 is plausible, but that wouldn't justify the claim of ``no more than 1/2^60.'' Aren't you embarrassed to claim that something has been ``rigorously proven'' when you haven't even written down the claimed _theorem_, never mind the proof? More importantly, you claim that your apparently-never-written proof relies on a March 2005 theorem of mine. But you were already claiming in January 2005 to have ``rigorously proven'' a security bound of ``about 1/2^60.'' Do you admit that, at the time, you weren't capable of proving this bound without severely limiting the number of messages to something like 2^34? When you claimed to have ``rigorously proven'' this bound, you were claiming not just that it was true, but that you had _proven_ it. That was a false claim. Perhaps someone now has a proof, but that doesn't retroactively make your claim true. You owe the community an admission that you did not, in fact, have the proof that you claimed to have. Science moves forward because it has mechanisms to detect and correct errors. Your refusal to admit your errors is despicable behavior. ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Wed Sep 28 11:21:37 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKdkX-0004ig-I3; Wed, 28 Sep 2005 11:21:37 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKdkV-0004iY-LD for cfrg@megatron.ietf.org; Wed, 28 Sep 2005 11:21:35 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA14120 for ; Wed, 28 Sep 2005 11:21:33 -0400 (EDT) Received: from sj-iport-1-in.cisco.com ([171.71.176.70] helo=sj-iport-1.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EKdrx-00089s-E3 for cfrg@ietf.org; Wed, 28 Sep 2005 11:29:19 -0400 Received: from sj-core-5.cisco.com ([171.71.177.238]) by sj-iport-1.cisco.com with ESMTP; 28 Sep 2005 08:21:24 -0700 X-IronPort-AV: i="3.97,154,1125903600"; d="scan'208"; a="662471801:sNHT31715896" Received: from xbh-sjc-211.amer.cisco.com (xbh-sjc-211.cisco.com [171.70.151.144]) by sj-core-5.cisco.com (8.12.10/8.12.6) with ESMTP id j8SFL64j008047; Wed, 28 Sep 2005 08:21:22 -0700 (PDT) Received: from xfe-sjc-211.amer.cisco.com ([171.70.151.174]) by xbh-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Wed, 28 Sep 2005 08:21:16 -0700 Received: from [192.168.1.100] ([10.32.254.212]) by xfe-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Wed, 28 Sep 2005 08:21:16 -0700 In-Reply-To: <20050928134913.34060.qmail@cr.yp.to> References: <20050928134913.34060.qmail@cr.yp.to> Mime-Version: 1.0 (Apple Message framework v734) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: David McGrew Subject: Re: [Cfrg] New UMAC Draft Date: Wed, 28 Sep 2005 08:21:13 -0700 To: "D. J. Bernstein" X-Mailer: Apple Mail (2.734) X-OriginalArrivalTime: 28 Sep 2005 15:21:16.0211 (UTC) FILETIME=[44DB7030:01C5C440] X-Spam-Score: 0.0 (/) X-Scan-Signature: c0bedb65cce30976f0bf60a0a39edea4 Content-Transfer-Encoding: 7bit Cc: cfrg@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Dan, On Sep 28, 2005, at 6:49 AM, D. J. Bernstein wrote: > Ted Krovetz writes: > >> In particular, the Security Considerations section >> now states explicitly that our forgery bounds on UMAC hold for up >> to the generation of 2^64 MAC tags >> > > I don't believe you. Your paper claims ``no more than 1/2^60,'' but it > isn't possible to obtain the exact 1/2^60 bound from feeding a 1/2^60 > function bound through a function-to-permutation switch, even if > (as you > claim) the switch is applicable. Something close to 1/2^60 is > plausible, > but that wouldn't justify the claim of ``no more than 1/2^60.'' this is an important technical comment. If the forgery bounds aren't right, it would be good to correct them. However, some of your comments below stray from technical issues on to personal ones. Please keep the latter off this email list. > > Aren't you embarrassed to claim that something has been ``rigorously > proven'' when you haven't even written down the claimed _theorem_, > never > mind the proof? > > More importantly, you claim that your apparently-never-written proof > relies on a March 2005 theorem of mine. But you were already > claiming in > January 2005 to have ``rigorously proven'' a security bound of ``about > 1/2^60.'' Do you admit that, at the time, you weren't capable of > proving > this bound without severely limiting the number of messages to > something > like 2^34? > > When you claimed to have ``rigorously proven'' this bound, you were > claiming not just that it was true, but that you had _proven_ it. That > was a false claim. Perhaps someone now has a proof, but that doesn't > retroactively make your claim true. You owe the community an admission > that you did not, in fact, have the proof that you claimed to have. > > Science moves forward because it has mechanisms to detect and correct > errors. Your refusal to admit your errors is despicable behavior. Despicable behavior? Let him who is without sin cast the first stone. It is important that we avoid having an atmosphere of hostility in the RG. We rely on voluntary participation, and don't want to drive away potential contributors. David > > ---D. J. Bernstein, Professor, Mathematics, Statistics, > and Computer Science, University of Illinois at Chicago > > _______________________________________________ > 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 cfrg-bounces@ietf.org Wed Sep 28 15:28:56 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKhbr-0002zY-Vf; Wed, 28 Sep 2005 15:28:55 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKhbr-0002zT-5l for cfrg@megatron.ietf.org; Wed, 28 Sep 2005 15:28:55 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA01769 for ; Wed, 28 Sep 2005 15:28:53 -0400 (EDT) Received: from gaia.ecs.csus.edu ([130.86.71.9]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EKhjM-0007TB-2v for cfrg@ietf.org; Wed, 28 Sep 2005 15:36:41 -0400 Received: from [130.86.74.20] (isis.ecs.csus.edu [130.86.74.20]) by gaia.ecs.csus.edu (8.12.11/8.12.8) with ESMTP id j8SJSkMe005835 for ; Wed, 28 Sep 2005 12:28:46 -0700 Mime-Version: 1.0 (Apple Message framework v734) Content-Transfer-Encoding: 7bit Message-Id: <9C49EC50-7BD8-49CB-9EC9-5A1B448E5C9A@acm.org> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: cfrg@ietf.org From: Ted Krovetz Subject: Re: [Cfrg] New UMAC Draft Date: Wed, 28 Sep 2005 12:28:45 -0700 X-Mailer: Apple Mail (2.734) X-Spam-Score: 0.0 (/) X-Scan-Signature: c1c65599517f9ac32519d043c37c5336 Content-Transfer-Encoding: 7bit X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Dan, > I don't believe you. Your paper claims ``no more than 1/2^60,'' but it > isn't possible to obtain the exact 1/2^60 bound from feeding a 1/2^60 > function bound through a function-to-permutation switch, even if > (as you > claim) the switch is applicable. Something close to 1/2^60 is > plausible, > but that wouldn't justify the claim of ``no more than 1/2^60.'' The 1/2^60 bound collects a few terms, and we write 1/2^60 because that is nicer for most readers than to look at an uglier summation. The actual hash collision bound is closer to 1/2^61, which can withstand a small constant multiplier for the switch from function to permutation. The bound is correct. > More importantly, you claim that your apparently-never-written proof > relies on a March 2005 theorem of mine. But you were already > claiming in > January 2005 to have ``rigorously proven'' a security bound of ``about > 1/2^60.'' Do you admit that, at the time, you weren't capable of > proving > this bound without severely limiting the number of messages to > something > like 2^34? What is relevant to the current discussion is whether the UMAC draft is correct. If you believe the draft has inaccuracies, please point them out. UMAC is rigorously proven. We have good almost-SU bounds on UHASH collision probabilities, we know that almost-SU hash families along with random functions make good MACs, and your theorem shows that moving to a permutation has a small multiplicative effect up to $2^64 $ uses. As for the history, when we wrote that UMAC was rigorously proven, we were only considering the hash function's properties (as that is the most important component affecting real security). As you point out, we ignored the birthday bound for limiting permutation use. It is not that we "weren't capable" of including the birthday bound, it is simply that we didn't consider it. As your research shows, this is not an unreasonable thing to do. Nevertheless, it was an oversight that probably should not have happened, and I'm sorry that it did. Sincerely, Ted Krovetz _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Wed Sep 28 17:24:46 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKjPy-0007m2-9I; Wed, 28 Sep 2005 17:24:46 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKjPw-0007l9-Fb for cfrg@megatron.ietf.org; Wed, 28 Sep 2005 17:24:44 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA13314 for ; Wed, 28 Sep 2005 17:24:42 -0400 (EDT) Received: from qproxy.gmail.com ([72.14.204.206]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EKjXT-00049F-Et for cfrg@ietf.org; Wed, 28 Sep 2005 17:32:31 -0400 Received: by qproxy.gmail.com with SMTP id a10so253952qbd for ; Wed, 28 Sep 2005 14:24:35 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=s1yCypnqpUhry+VhLOo0Gprsj1HfxS37jKnJf/UjnhdOvSfb5dWYls1ibW96tbbe3e89I9NkduSfjeXKbLBSQCw3fJkTg6NTNDqjlt8shOvUlLiDYXYWBT6mMZybOQsyqU1Zqbg2UVYbnhEBSIxEl8pfuTdVI89bqBav2OiZurs= Received: by 10.64.213.2 with SMTP id l2mr64557qbg; Wed, 28 Sep 2005 14:24:35 -0700 (PDT) Received: by 10.64.210.1 with HTTP; Wed, 28 Sep 2005 14:24:35 -0700 (PDT) Message-ID: Date: Wed, 28 Sep 2005 14:24:35 -0700 From: Hal Finney To: Ted Krovetz Subject: Re: [Cfrg] New UMAC Draft In-Reply-To: <6F37EC53-72F6-46D7-B1D0-470D17540737@acm.org> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline References: <6F37EC53-72F6-46D7-B1D0-470D17540737@acm.org> X-Spam-Score: 0.0 (/) X-Scan-Signature: 39bd8f8cbb76cae18b7e23f7cf6b2b9f Content-Transfer-Encoding: quoted-printable Cc: cfrg@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: Hal Finney List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org On 9/27/05, Ted Krovetz wrote: > In the standard security model of MACs, the adversary is allowed to > repeat nonces when attempting to forge. So our N/2^{30,60,90,120} > bound for at least one successful forgery over N attempts holds even > if the verifier is not checking for repeated nonces. So, in actuality > replays are the only ones we really care about, and > we can defend against them by disallowing repeated nonces. Okay, but then if you allow the attacker to repeat nonces at will, you have the problem that if he manages even one forgery, then in principle your security is gone, right? This is what you describe as: It should be pointed out that once an attempted forgery is successful, it is possible, in principle, that subsequent messages under this key may be forged, too. This is important to understand in gauging the severity of a successful forgery, even though no such attack on UMAC is known to date. My main concern is from the perspective of an implementor who might be familiar with a CBC-MAC or HMAC construction, where a single "lucky" successful forgery does not allow the attacker to arbitrarily forge future messages with 100% success rate. This behavior of Wegman-Carter MACs may come as a dangerous surprise to an implementor. I just want to be sure that readers are adequately warned of the dangers of using short authenticators while allowing nonce replays. Perhaps you could reword the above paragraph to say something like: "It should be pointed out that once an attempted forgery is successful, this can in principle leak enough information about the key to allow an attacker to forge subsequent message tags at will. This is important to understand in gauging the severity of a successful forgery, even though no such attack on UMAC is known to date." Hal Finney _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Wed Sep 28 17:47:31 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKjlz-0007GR-Em; Wed, 28 Sep 2005 17:47:31 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKjlx-0007FF-5l for cfrg@megatron.ietf.org; Wed, 28 Sep 2005 17:47:29 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA14557 for ; Wed, 28 Sep 2005 17:47:26 -0400 (EDT) Received: from qproxy.gmail.com ([72.14.204.193]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EKjtU-0004lS-FA for cfrg@ietf.org; Wed, 28 Sep 2005 17:55:16 -0400 Received: by qproxy.gmail.com with SMTP id a10so256100qbd for ; Wed, 28 Sep 2005 14:47:20 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=Rnjtuy4HxoMs6BYwbizl7SCIg+HEyldwylSUqZeKDx17fnz71AklSbR7kp8/sWBbuLVikAJYSyDBnFR8C7Z44S9RXyKNArnWXCsSY5FVe1SHuFqTlxAuVPbxCQ78Br4E2QP9HaEFvd7QMdUB+u1cwRxK+aDL4clIDb16ZDyvzb4= Received: by 10.64.233.19 with SMTP id f19mr67665qbh; Wed, 28 Sep 2005 14:47:20 -0700 (PDT) Received: by 10.64.210.1 with HTTP; Wed, 28 Sep 2005 14:47:20 -0700 (PDT) Message-ID: Date: Wed, 28 Sep 2005 14:47:20 -0700 From: Hal Finney To: Ted Krovetz Subject: Re: [Cfrg] New UMAC Draft In-Reply-To: <9C49EC50-7BD8-49CB-9EC9-5A1B448E5C9A@acm.org> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline References: <9C49EC50-7BD8-49CB-9EC9-5A1B448E5C9A@acm.org> X-Spam-Score: 0.0 (/) X-Scan-Signature: 21c69d3cfc2dd19218717dbe1d974352 Content-Transfer-Encoding: quoted-printable Cc: cfrg@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: Hal Finney List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Let me throw another complication into the debate about security bounds. As I understand it, the original Wegman-Carter construction looked like UH(msg) + f(nonce) where UH is a universal hash, f is a random function, and "+" is some field operator. For reasons which are not completely clear to me, implementations of this idea like UMAC and Dan Bernstein's Poly1305-AES substitute a random permutation p(nonce) for the random function f(nonce). This is implemented as a block cipher, usually AES. The original WC security analysis based on a random function does not go through when using a random permutation. Dan's Eurocrypt 2005 paper explores this difference and develops improved security bounds when using a random permutation. This work is referenced by Ted Krovetz to support the UMAC security bounds. My comment is that UMAC actually does not use either a random function or a random permutation, except for the UMAC-128 variant. Shorter versions like UMAC-64 (which is probably going to be the most popular), use a truncated block cipher for f(). On the one hand, this is arguably at least as good as using a random permutation. A 64-bit truncated AES should actually be pretty close to a random function. On the other hand, we have analyses for random functions and for random permutations, but technically a 64 bit truncation of AES is neither. Perhaps this points to a gap in the security proof. Adding further complexity, UMAC does not just truncate the AES to 64 bits; rather, for two consecutive nonces, it uses alternating halves of a single AES invocation for f(). It uses the left half of AES(nonce) for even nonces, and the right half of AES(nonce-1) for odd. This means that even if we considered a 64 bit truncation of AES to be like a random function, if we look at two consecutive nonces, there is correlation between the random functions used for those cases due to the fact that they are the two halves of a permutation. I don't think the security proofs take this complexity into consideration. In practice, it's probably OK because truncating AES should not be any worse than using it untruncated. But for provable security it would be good to see some discussion of whether the optimization of using one AES for two nonces is OK. Hal Finney _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Wed Sep 28 20:30:03 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKmJH-0006O7-7J; Wed, 28 Sep 2005 20:30:03 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKmJF-0006NT-9y for cfrg@megatron.ietf.org; Wed, 28 Sep 2005 20:30:01 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA23545 for ; Wed, 28 Sep 2005 20:30:00 -0400 (EDT) Received: from ylpvm15-ext.prodigy.net ([207.115.57.46] helo=ylpvm15.prodigy.net) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EKmQn-0000Mq-0k for cfrg@ietf.org; Wed, 28 Sep 2005 20:37:50 -0400 Received: from pimout6-ext.prodigy.net (pimout6-int.prodigy.net [207.115.4.22]) by ylpvm15.prodigy.net (8.12.10 outbound/8.12.10) with ESMTP id j8T0U5KG024126 for ; Wed, 28 Sep 2005 20:30:05 -0400 X-ORBL: [66.127.112.169] Received: from [192.168.0.101] (adsl-66-127-112-169.dsl.scrm01.pacbell.net [66.127.112.169]) by pimout6-ext.prodigy.net (8.13.4 outbound domainkey aix/8.13.4) with ESMTP id j8T0Tt2l424180; Wed, 28 Sep 2005 20:29:56 -0400 In-Reply-To: References: <9C49EC50-7BD8-49CB-9EC9-5A1B448E5C9A@acm.org> Mime-Version: 1.0 (Apple Message framework v734) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <4358EF0B-3ED3-403F-A74C-50863872A51A@acm.org> Content-Transfer-Encoding: 7bit From: Ted Krovetz Subject: Re: [Cfrg] New UMAC Draft Date: Wed, 28 Sep 2005 17:29:51 -0700 To: Hal Finney X-Mailer: Apple Mail (2.734) X-Spam-Score: 2.4 (++) X-Scan-Signature: 7655788c23eb79e336f5f8ba8bce7906 Content-Transfer-Encoding: 7bit Cc: cfrg@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hal, > My comment is that UMAC actually does not use either a random function > or a random permutation, except for the UMAC-128 variant. Shorter > versions like UMAC-64 (which is probably going to be the most > popular), use a truncated block cipher for f(). As you said, Wegman-Carter MACs are secure when used with a random function f (eg, UH(msg) + f(nonce)). This applies even in the case of UMAC's splitting of outputs for consecutive nonces because the halves are independent for a random function. What Bernstein's theorem says is that it does not matter HOW the function f is used, but instead HOW MANY times it is used. In moving from a random function to a random permutation, degradation of security is no worse than a small multiple for up to 2^64 applications of f. So even though you might imagine that f() output half-splitting might introduce a weakness when using a permutation, it simply is not true. As for moving from a random permutation to AES, that had better not cause a significant degradation in security, or else AES is not behaving as we all expect it to. -Ted _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Wed Sep 28 23:36:25 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKpDd-00024D-Qv; Wed, 28 Sep 2005 23:36:25 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EKpDb-000248-IY for cfrg@megatron.ietf.org; Wed, 28 Sep 2005 23:36:23 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id XAA01684 for ; Wed, 28 Sep 2005 23:36:21 -0400 (EDT) Received: from sj-iport-2-in.cisco.com ([171.71.176.71] helo=sj-iport-2.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EKpL9-0004kg-Qr for cfrg@ietf.org; Wed, 28 Sep 2005 23:44:14 -0400 Received: from sj-core-2.cisco.com ([171.71.177.254]) by sj-iport-2.cisco.com with ESMTP; 28 Sep 2005 20:36:12 -0700 Received: from xbh-sjc-231.amer.cisco.com (xbh-sjc-231.cisco.com [128.107.191.100]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id j8T3ZvKM020962; Wed, 28 Sep 2005 20:36:07 -0700 (PDT) Received: from xfe-sjc-211.amer.cisco.com ([171.70.151.174]) by xbh-sjc-231.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Wed, 28 Sep 2005 20:36:06 -0700 Received: from [192.168.0.13] ([10.21.97.201]) by xfe-sjc-211.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.211); Wed, 28 Sep 2005 20:36:05 -0700 In-Reply-To: <20050928134913.34060.qmail@cr.yp.to> References: <20050928134913.34060.qmail@cr.yp.to> Mime-Version: 1.0 (Apple Message framework v734) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: Mark Baugher Subject: Re: [Cfrg] New UMAC Draft Date: Wed, 28 Sep 2005 20:36:04 -0700 To: "D. J. Bernstein" X-Mailer: Apple Mail (2.734) X-OriginalArrivalTime: 29 Sep 2005 03:36:05.0849 (UTC) FILETIME=[EC544C90:01C5C4A6] X-Spam-Score: 0.0 (/) X-Scan-Signature: 3e15cc4fdc61d7bce84032741d11c8e5 Content-Transfer-Encoding: 7bit Cc: cfrg@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Dan, On Sep 28, 2005, at 6:49 AM, D. J. Bernstein wrote: > Ted Krovetz writes: > >> In particular, the Security Considerations section >> now states explicitly that our forgery bounds on UMAC hold for up >> to the generation of 2^64 MAC tags >> > > I don't believe you. Your paper claims ``no more than 1/2^60,'' but it > isn't possible to obtain the exact 1/2^60 bound from feeding a 1/2^60 > function bound through a function-to-permutation switch, even if > (as you > claim) the switch is applicable. Something close to 1/2^60 is > plausible, > but that wouldn't justify the claim of ``no more than 1/2^60.'' > > Aren't you embarrassed to claim that something has been ``rigorously > proven'' when you haven't even written down the claimed _theorem_, > never > mind the proof? > > More importantly, you claim that your apparently-never-written proof > relies on a March 2005 theorem of mine. But you were already > claiming in > January 2005 to have ``rigorously proven'' a security bound of ``about > 1/2^60.'' Do you admit that, at the time, you weren't capable of > proving > this bound without severely limiting the number of messages to > something > like 2^34? > > When you claimed to have ``rigorously proven'' this bound, you were > claiming not just that it was true, but that you had _proven_ it. That > was a false claim. Perhaps someone now has a proof, but that doesn't > retroactively make your claim true. You owe the community an admission > that you did not, in fact, have the proof that you claimed to have. > > Science moves forward because it has mechanisms to detect and correct > errors. Your refusal to admit your errors is despicable behavior. I think this remark is not only counter-productive but in violation of list policy. It really is not acceptable by our standards here. Mark > > ---D. J. Bernstein, Professor, Mathematics, Statistics, > and Computer Science, University of Illinois at Chicago > > _______________________________________________ > 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 cfrg-bounces@ietf.org Fri Sep 30 00:36:22 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELCdC-0001ih-PZ; Fri, 30 Sep 2005 00:36:22 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELCdA-0001i2-Nc for cfrg@megatron.ietf.org; Fri, 30 Sep 2005 00:36:20 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id AAA05434 for ; Fri, 30 Sep 2005 00:36:17 -0400 (EDT) Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1ELCkx-0001zV-0n for cfrg@ietf.org; Fri, 30 Sep 2005 00:44:24 -0400 Received: (qmail 14127 invoked by uid 1016); 30 Sep 2005 04:36:34 -0000 Date: 30 Sep 2005 04:36:34 -0000 Message-ID: <20050930043634.14126.qmail@cr.yp.to> Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html. From: "D. J. Bernstein" To: cfrg@ietf.org Subject: Re: [Cfrg] New UMAC Draft References: <9C49EC50-7BD8-49CB-9EC9-5A1B448E5C9A@acm.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Score: 0.0 (/) X-Scan-Signature: 97adf591118a232206bdb5a27b217034 X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Ted Krovetz writes: > UMAC is rigorously proven. I don't believe you. It seems possible, perhaps even likely, that such a proof exists; but it's also clear that you haven't done the work yet. The risk of error is still unacceptably high. In October 2004 you claimed various ``rigorously proven'' bounds on the UMAC forgery probability. It's crystal clear that this claim was false; I'm sure that nobody knows how to prove those bounds; in fact, I think that your alleged bounds were flat-out wrong. (I'm reminded of the OAEP fiasco, where Bellare and your coauthor Rogaway claimed a security theorem that they weren't actually able to prove and that's now widely believed to be incorrect, although several applications of the claimed theorem were subsequently rescued by more sophisticated techniques.) The problem wasn't that you tried to write a proof and made a mistake. The problem was that you didn't even bother writing a proof. You looked at the collision-probability bounds in Black's thesis; you incorrectly assumed that forgery probabilities can't exceed collision probabilities (as you now admit); and then you falsely stated that your bounds had been ``rigorously proven.'' The same problem exists now. You have new resources at your disposal, specifically a theorem that helps transfer some forgery-probability bounds from uniform random functions to uniform random permutations, but all you've done with those resources is assert that they're applicable. Saying ``Another result [2], when combined with [3, 6], shows that [blah blah blah]'' is a far cry from giving a rigorous proof. You haven't even given a careful _statement_ of your alleged security bounds; you've neglected to add the AES distinguishing probability, for example. ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Fri Sep 30 01:05:04 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELD4y-0000Lm-4t; Fri, 30 Sep 2005 01:05:04 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELD4v-0000Kl-OG for cfrg@megatron.ietf.org; Fri, 30 Sep 2005 01:05:02 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id BAA06748 for ; Fri, 30 Sep 2005 01:05:01 -0400 (EDT) Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1ELDCi-0002gX-F6 for cfrg@ietf.org; Fri, 30 Sep 2005 01:13:05 -0400 Received: (qmail 47622 invoked by uid 1016); 30 Sep 2005 05:05:18 -0000 Date: 30 Sep 2005 05:05:18 -0000 Message-ID: <20050930050518.47621.qmail@cr.yp.to> Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html. From: "D. J. Bernstein" To: cfrg@ietf.org Subject: Re: [Cfrg] New UMAC Draft References: <9C49EC50-7BD8-49CB-9EC9-5A1B448E5C9A@acm.org> <4358EF0B-3ED3-403F-A74C-50863872A51A@acm.org> <9C49EC50-7BD8-49CB-9EC9-5A1B448E5C9A@acm.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Score: 0.0 (/) X-Scan-Signature: 0bc60ec82efc80c84b8d02f4b0e4de22 X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Hal Finney writes: > For reasons which are not completely clear to me, implementations of > this idea like UMAC and Dan Bernstein's Poly1305-AES substitute a > random permutation p(nonce) for the random function f(nonce). The reason is simple: We're taking advantage of the community's (perhaps misplaced) trust in the security of a block cipher, namely AES. I suspect that future cryptographers will regard the notion of a block cipher as a historical accident, not something to actually be deployed in any sort of cryptographic protocol. Using Poly1305 with a stream cipher is easy: insert 128 blank bits at the beginning of the message being encrypted, and steal those 128 bits of ciphertext for Poly1305. Ted Krovetz writes: > What Bernstein's theorem says is that it does not matter HOW the > function f is used, but instead HOW MANY times it is used. It's certainly true that the main parameters in the theorem are the maximum number of f applications and the size of f's domain. However, to apply the theorem, you also need a bound on Pr[A(f) = 1]; and producing that bound requires knowing how f can be used by the algorithm A. I agree that splitting isn't inherently a problem. The real question is how UMAC chooses oracle inputs. ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Fri Sep 30 01:39:23 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELDcB-00007D-8H; Fri, 30 Sep 2005 01:39:23 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELDc9-00006F-Pa for cfrg@megatron.ietf.org; Fri, 30 Sep 2005 01:39:21 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id BAA08166 for ; Fri, 30 Sep 2005 01:39:20 -0400 (EDT) Received: from mailgw2.technion.ac.il ([132.68.238.33]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1ELDjx-0003Qr-4x for cfrg@ietf.org; Fri, 30 Sep 2005 01:47:25 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by mailgw2.technion.ac.il (Postfix) with ESMTP id C8DFE390742 for ; Fri, 30 Sep 2005 08:39:11 +0300 (IDT) Received: from mailgw2.technion.ac.il ([127.0.0.1]) by localhost (mailgw2.technion.ac.il [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 03345-01-96 for ; Fri, 30 Sep 2005 08:39:11 +0300 (IDT) Received: from ee.technion.ac.il (ee.technion.ac.il [132.68.48.5]) by mailgw2.technion.ac.il (Postfix) with ESMTP id 8E29D390723 for ; Fri, 30 Sep 2005 08:39:11 +0300 (IDT) Received: from ee.technion.ac.il (localhost [127.0.0.1]) by ee.technion.ac.il (8.12.10+Sun/8.12.2) with ESMTP id j8U5etPP016778; Fri, 30 Sep 2005 08:40:55 +0300 (IDT) Received: from localhost (hugo@localhost) by ee.technion.ac.il (8.12.10+Sun/8.12.2/Submit) with ESMTP id j8U5esGF016768; Fri, 30 Sep 2005 08:40:54 +0300 (IDT) Date: Fri, 30 Sep 2005 08:40:54 +0300 (IDT) From: Hugo Krawczyk To: "D. J. Bernstein" Subject: Re: [Cfrg] New UMAC Draft In-Reply-To: <20050930043634.14126.qmail@cr.yp.to> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Virus-Scanned: by amavisd-new at technion.ac.il X-Spam-Score: 0.0 (/) X-Scan-Signature: 7655788c23eb79e336f5f8ba8bce7906 Cc: cfrg@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org On 30 Sep 2005, D. J. Bernstein wrote: > Ted Krovetz writes: > > UMAC is rigorously proven. > > I don't believe you. It seems possible, perhaps even likely, that such a > proof exists; but it's also clear that you haven't done the work yet. > The risk of error is still unacceptably high. > Indeed, I conjecture that the risk of error in our proofs after 2^64 annoying messages from Dan Bernstein to the cfrg list is still around 2^{-61} which as we all know is unacceptably high for the Gods but a great accomplishment for erring mortals like myself. Just in case you celebrate Rosh Ha-Shana (and also if you don't): HAPPY NEW YEAR :) Hugo _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Fri Sep 30 11:14:20 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELMaa-0001FT-A7; Fri, 30 Sep 2005 11:14:20 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELMaY-0001FG-Lb for cfrg@megatron.ietf.org; Fri, 30 Sep 2005 11:14:18 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA16186 for ; Fri, 30 Sep 2005 11:14:16 -0400 (EDT) Received: from gaia.ecs.csus.edu ([130.86.71.9]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1ELMiQ-00087D-HV for cfrg@ietf.org; Fri, 30 Sep 2005 11:22:27 -0400 Received: from [130.86.74.20] (isis.ecs.csus.edu [130.86.74.20]) by gaia.ecs.csus.edu (8.12.11/8.12.8) with ESMTP id j8UFEBM2012406 for ; Fri, 30 Sep 2005 08:14:11 -0700 Mime-Version: 1.0 (Apple Message framework v734) Content-Transfer-Encoding: 7bit Message-Id: <3C1D5161-1625-4456-B275-2CF122F37EAB@csus.edu> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: cfrg@ietf.org From: Ted Krovetz Subject: Re: [Cfrg] New UMAC Draft Date: Fri, 30 Sep 2005 08:14:11 -0700 X-Mailer: Apple Mail (2.734) X-Spam-Score: 0.0 (/) X-Scan-Signature: 97adf591118a232206bdb5a27b217034 Content-Transfer-Encoding: 7bit X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Lest anyone think we "haven't done the work yet", I am willing to continue to engage Bernstein further in this discussion. > > UMAC is rigorously proven. > > I don't believe you. It seems possible, perhaps even likely, that > such a > proof exists; but it's also clear that you haven't done the work yet. Please tell me which of the following is not true: - Suppose H is a \e-SU hash family with each h \in H returning n bits, further suppose that h is randomly chosen from H and f is a randomly chosen function returning n bits. Then, the probability an attacker could forge against h(msg) xor f(nonce) is at most \e. - Since UHASH is \e-SU, this bound holds for UMAC when UMAC is used with a random function. - Let A be an algorithm that is given random function \rho with 128- bit outputs and inputs. Let A run an attacker on UMAC-64 and let A simulate UMAC-64 for the attacker using \rho instead of AES. Let A output 1 if the attacker forges. We know that the probability of success here is no more than 2^{-61} (for the sake of argument) in the attacker's forgery attempt. This means A outputs 1 with probability no more than 2^{-61}. Let's say the attacker sees 2^i MACs along the way (meaning no more than 2^i \rho invocations). Then, Bernstein's theorem says that if we substitute random permutation \pi for \rho, then A will output 1 (indicating forgery success) with probability no more than (1 - 2^{i-128})^{2^{i-1}} 2^{-61} < 2^{-60} for i <= 64. Thank you, Ted Krovetz _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Fri Sep 30 12:22:50 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELNes-0002jF-LB; Fri, 30 Sep 2005 12:22:50 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELNer-0002jA-Am for cfrg@megatron.ietf.org; Fri, 30 Sep 2005 12:22:49 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA19179 for ; Fri, 30 Sep 2005 12:22:47 -0400 (EDT) Received: from gaia.ecs.csus.edu ([130.86.71.9]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1ELNmj-0001Cz-SR for cfrg@ietf.org; Fri, 30 Sep 2005 12:30:59 -0400 Received: from [130.86.74.20] (isis.ecs.csus.edu [130.86.74.20]) by gaia.ecs.csus.edu (8.12.11/8.12.8) with ESMTP id j8UGMh7P002840 for ; Fri, 30 Sep 2005 09:22:43 -0700 Mime-Version: 1.0 (Apple Message framework v734) Content-Transfer-Encoding: 7bit Message-Id: <8A405620-3AF4-4364-BB59-D31C9192F771@csus.edu> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: cfrg@ietf.org From: Ted Krovetz Date: Fri, 30 Sep 2005 09:22:42 -0700 X-Mailer: Apple Mail (2.734) X-Spam-Score: 0.0 (/) X-Scan-Signature: 7aefe408d50e9c7c47615841cb314bed Content-Transfer-Encoding: 7bit Subject: [Cfrg] cfrg@ietf.org X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org I'm going away for a few days. In my absence, please run the following algorithm while (1) { Dan says: "You're a liar!" Ted says: "No I'm not!" } _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg From cfrg-bounces@ietf.org Fri Sep 30 16:50:36 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELRq0-0007Kt-1K; Fri, 30 Sep 2005 16:50:36 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ELRpy-0007Jb-5C for cfrg@megatron.ietf.org; Fri, 30 Sep 2005 16:50:34 -0400 Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA18015 for ; Fri, 30 Sep 2005 16:50:32 -0400 (EDT) Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1ELRxr-0005rF-3u for cfrg@ietf.org; Fri, 30 Sep 2005 16:58:46 -0400 Received: (qmail 31668 invoked by uid 1016); 30 Sep 2005 20:50:48 -0000 Date: 30 Sep 2005 20:50:48 -0000 Message-ID: <20050930205048.31667.qmail@cr.yp.to> Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html. From: "D. J. Bernstein" To: cfrg@ietf.org Subject: Re: [Cfrg] New UMAC Draft References: <3C1D5161-1625-4456-B275-2CF122F37EAB@csus.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Score: 0.0 (/) X-Scan-Signature: 0bc60ec82efc80c84b8d02f4b0e4de22 X-BeenThere: cfrg@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: cfrg-bounces@ietf.org Errors-To: cfrg-bounces@ietf.org Ted Krovetz writes: > Please tell me which of the following is not true: [ series of lemmas that might be useful in a UMAC security proof ] As I see it, the main risk of error is not in any of your lemmas, but in how you're putting the lemmas together to obtain an overall bound on the UMAC forgery probability. Certainly this is the part that led to your incorrect UMAC security claims last year, and the part where you're continuing to be incredibly sloppy. Your latest UMAC security claim (which, like your incorrect claims, is alleged to be ``rigorously proven'') appears to be the following: Claimed theorem. An attack against UMAC-32n using at most 2^64 chosen messages and one forgery attempt cannot have success probability larger than 2^{-30n}, if AES is secure. There isn't much wiggle room here: you haven't defined ``secure'' yet, but you've clearly stated that you're bounding the forgery probability, you've clearly stated that your bounds are exactly 2^{-30}, 2^{-60}, 2^{-90}, 2^{-120} for UMAC-32, UMAC-64, UMAC-96, and UMAC-128, and you've clearly stated that you're allowing 2^64 chosen messages. Please define ``secure'' and then show us the proof of this claimed forgery-probability bound. ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg