From openpgp@brainhub.org Tue Dec 11 12:58:33 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DD34611E80A6 for ; Tue, 11 Dec 2012 12:58:33 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 1.052 X-Spam-Level: * X-Spam-Status: No, score=1.052 tagged_above=-999 required=5 tests=[BAYES_05=-1.11, FH_RELAY_NODNS=1.451, HELO_MISMATCH_NET=0.611, RDNS_NONE=0.1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id KPYgL9XD2kOh for ; Tue, 11 Dec 2012 12:58:33 -0800 (PST) Received: from qmta03.emeryville.ca.mail.comcast.net (qmta03.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:32]) by ietfa.amsl.com (Postfix) with ESMTP id 1A44F11E80A3 for ; Tue, 11 Dec 2012 12:58:33 -0800 (PST) Received: from omta22.emeryville.ca.mail.comcast.net ([76.96.30.89]) by qmta03.emeryville.ca.mail.comcast.net with comcast id aG6H1k0041vN32cA3LyY5e; Tue, 11 Dec 2012 20:58:32 +0000 Received: from [127.0.0.1] ([69.181.162.123]) by omta22.emeryville.ca.mail.comcast.net with comcast id aLyX1k00P2g33ZR8iLyYwS; Tue, 11 Dec 2012 20:58:32 +0000 Message-ID: <50C79E2A.9040100@brainhub.org> Date: Tue, 11 Dec 2012 12:57:14 -0800 From: Andrey Jivsov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120911 Thunderbird/15.0.1 MIME-Version: 1.0 To: saag@ietf.org, cfrg@irtf.org Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1355259512; bh=rbRVPX/LDSdt9hGAiV4SLbgFmGL36I7dAUIN5Q2AaoY=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=l02sW4U3HsaR4seMsUL+X30kvZfbh8fJ6yg0frqC9+s5kDS7iia2D6+m1ieUr+ob6 9Q0g7ArJ/FKOR425T8YlEPjZTXog+u1jwhxKNq5KGZpooyDB9g0yPsucVl4Rpzdxg3 dvCfjVDntJS/EcgmxSzpw83jpOsfJBm+HtFLjJOdqypm306T2eg5LTxB7+u+oR8HC3 1Gab3iVrj67yspu0F7wsEHjHudKzSb5pP5tZDBnKZAP/OAgOouReYOlEhqLYPF6cNk UVfjdQNKgQe2o6mTgHK51q4nMDUKPePcI6zCW9pxqnTuhH2GID2+HkB95I++BdkbrB DKpRMP9oHrnwA== Subject: [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 11 Dec 2012 20:58:34 -0000 Greetings. I thought that it would be useful for the Internet community to have an IETF document that describes how to encode an ECC point. I will focus on the elliptic curves over the prime fields here. http://datatracker.ietf.org/doc/draft-jivsov-ecc-compact Cryptographic protocols defined in IETF most often work with large integers, such as the modulus of an RSA key, which they encode with some applicable protocol-specific method. Unfortunately, the default representation of an ECC point is not just a "large integer". It is either a pair of integers of x,y, or x with optional information about y. Additional metadata tagged to x,y is common. The encoding of an ECC point needs further definition, plus the additional complexity is present due to the decisions to make ECC point compression optional (I suspect on the ground of IPR concerns). In the ideal world the situation would be the following: there is an RFC for ECC point definition; it uses compact representation; the representation is just a large integer; it's free of patents; secure; and that's the default mandatory method in every IETF standard. I am proposing here a format that in my opinion comes the closest to the ideal features outlined above. Getting to the ideal world is another story, but the first step on this journey is a working method that I am pleased to present here. At the very least, the new protocols can take advantage of the proposal; otherwise the new submissions will likely to gravitate towards the SEC1 format, at least on the practical grounds because the SEC1 is the only popular format that is searchable and publicly available. I would like to offer an alternative / useful point of reference to future standards. Thank you. From openpgp@brainhub.org Tue Dec 11 15:38:35 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A5D8B21E809D for ; Tue, 11 Dec 2012 15:38:35 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 0.059 X-Spam-Level: X-Spam-Status: No, score=0.059 tagged_above=-999 required=5 tests=[AWL=0.496, BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_NET=0.611, RDNS_NONE=0.1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id WUr-sEdEa1Ht for ; Tue, 11 Dec 2012 15:38:34 -0800 (PST) Received: from qmta01.emeryville.ca.mail.comcast.net (qmta01.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:16]) by ietfa.amsl.com (Postfix) with ESMTP id C9BA721E8099 for ; Tue, 11 Dec 2012 15:38:34 -0800 (PST) Received: from omta15.emeryville.ca.mail.comcast.net ([76.96.30.71]) by qmta01.emeryville.ca.mail.comcast.net with comcast id aDG11k00B1Y3wxoA1PeaH4; Tue, 11 Dec 2012 23:38:34 +0000 Received: from [127.0.0.1] ([69.181.162.123]) by omta15.emeryville.ca.mail.comcast.net with comcast id aPeY1k00a2g33ZR8bPeZsC; Tue, 11 Dec 2012 23:38:34 +0000 Message-ID: <50C7C3AC.7010405@brainhub.org> Date: Tue, 11 Dec 2012 15:37:16 -0800 From: Andrey Jivsov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120911 Thunderbird/15.0.1 MIME-Version: 1.0 To: Peter Gutmann References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1355269114; bh=ogTzxSDtUQwaZB4zSh2eqgLw9xnUnI1eM2VxgYl2zFc=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=tn/JtdbjY19cglsHHg7dLRMimjht/BmcSlNmjAaR9pFmtWfrd1CDgHlSsJ2CU52Au yTEHY2ETwOb2pZt9Il/ViPFsVFR5yZMtDwF6lGZW0szg8wXLOSy2wWmjYl1vKaTyUv 6uwKY+ZvxBWqvoxFO6q6SmFFn8lRECocTI6onJjqA6OOtFfFhdhCwhY1Vh29ODV/Cv JlGlt7yd6S/7GAJkZEyb8CC86FLzrtctdKG8Y9c/2BN6A9Xj3lkELHattZej/GjYQe D31Zp2fxIWd8Sc9z99ECj+tsTuSCEu/rtS6M05S9v2LOnINwHUhj50PDtghKCWzN0E wbShPV5osYHeQ== Cc: cfrg@irtf.org, saag@ietf.org Subject: Re: [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 11 Dec 2012 23:38:35 -0000 On 12/11/2012 03:15 PM, Peter Gutmann wrote: > Andrey Jivsov writes: > >> I thought that it would be useful for the Internet community to have an IETF >> document that describes how to encode an ECC point. > > Maybe I'm missing something here, but wouldn't this just consist of: > > -- Snip -- > > See [1]. > > [1] X9.62-2005, "Public Key Cryptography for the Financial Services Industry: > The Elliptic Curve Digital Signature Standard (ECDSA)", November, 2005. > > -- Snip -- > > That's what every existing RFC that uses ECC seems to be using. > > Peter. > Hello Peter. "X9.62-2005" in the search engine lends me on a page that asks for $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is more popular as a reference (assuming they are identical regarding the point compression method). I claim that what I submitted is better in many respects than SEC1. Let me expand on one of the benefits not covered in the spec. It's very likely that an employee of a commercial company thinking about using [SEC1] compression with any ECC method would get an order from the legal department to stay away from compression. The fact that somebody on the Internet posted something to the contrary has little weight for them. My contribution is an attempt towards a compact representation that is actually usable in practice. It's the most direct extension to the 1985 idea by [Miller] (see my document for details). Thank you. From rstruik.ext@gmail.com Wed Dec 12 06:17:24 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3D0C321F8978 for ; Wed, 12 Dec 2012 06:17:24 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -3.599 X-Spam-Level: X-Spam-Status: No, score=-3.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 8xvYFLmZLQPr for ; Wed, 12 Dec 2012 06:17:23 -0800 (PST) Received: from mail-ie0-f174.google.com (mail-ie0-f174.google.com [209.85.223.174]) by ietfa.amsl.com (Postfix) with ESMTP id 2576E21F8A39 for ; Wed, 12 Dec 2012 06:17:23 -0800 (PST) Received: by mail-ie0-f174.google.com with SMTP id c11so1890948ieb.33 for ; Wed, 12 Dec 2012 06:17:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=L2ncPzH57WVqzbmXY/27Cbx1PZyk6WS0u39QrRgUeRw=; b=wNBuFaenznZLOcgOUfzM6U2GaSoe4XcuiokJtSC0hUdCnn3+lPwdoLGi8ymOjOfp6y d5yCT6yqhC7bqsKVelCbX500Y3w4FrXV9qr2LQ230lgz84CT53WQEtfYHWJa9d2Xg/rT mlggK40tuOeL2r7SQ8dwbCgHu3OFuCOuhsLypn345V21VEFg2xn5y8Dwrva2y7jKyhFX B7AGwXtu/foiefMA+1FcpcA/Zmc92cPf7t6nEKzHaPJksveUopC8K6rkJfW5DHY6YPMG ubN2Gi9XuElu60GcRG1yMl5exfAGCEmTMOWOV9A4tPO2JbxEdIazoRgAYs4zLB1HZxVc HNZw== Received: by 10.50.33.147 with SMTP id r19mr13461385igi.73.1355321842136; Wed, 12 Dec 2012 06:17:22 -0800 (PST) Received: from [192.168.1.103] (CPE0013100e2c51-CM001cea35caa6.cpe.net.cable.rogers.com. [99.231.4.27]) by mx.google.com with ESMTPS id wg2sm1853537igb.13.2012.12.12.06.17.21 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 12 Dec 2012 06:17:21 -0800 (PST) Message-ID: <50C891E7.4000009@gmail.com> Date: Wed, 12 Dec 2012 09:17:11 -0500 From: Rene Struik User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/17.0 Thunderbird/17.0 MIME-Version: 1.0 To: Andrey Jivsov References: <50C7C3AC.7010405@brainhub.org> In-Reply-To: <50C7C3AC.7010405@brainhub.org> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: cfrg@irtf.org, saag@ietf.org Subject: Re: [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 14:17:24 -0000 Hi Andrey: One can already implement the x-coordinate only representation of an elliptic curve point simply by converting the affine representation into compressed representation and randomizing the compression "bit". The reverse operation then yields the point or its inverse (which have the same x-coordinate). To my knowledge, this does not require any changes to data formatting (nor additional bytes). Best regards, Rene On 12/11/2012 6:37 PM, Andrey Jivsov wrote: > On 12/11/2012 03:15 PM, Peter Gutmann wrote: >> Andrey Jivsov writes: >> >>> I thought that it would be useful for the Internet community to have >>> an IETF >>> document that describes how to encode an ECC point. >> >> Maybe I'm missing something here, but wouldn't this just consist of: >> >> -- Snip -- >> >> See [1]. >> >> [1] X9.62-2005, "Public Key Cryptography for the Financial Services >> Industry: >> The Elliptic Curve Digital Signature Standard (ECDSA)", November, 2005. >> >> -- Snip -- >> >> That's what every existing RFC that uses ECC seems to be using. >> >> Peter. >> > > Hello Peter. > > "X9.62-2005" in the search engine lends me on a page that asks for > $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is > more popular as a reference (assuming they are identical regarding the > point compression method). > > I claim that what I submitted is better in many respects than SEC1. > > Let me expand on one of the benefits not covered in the spec. It's > very likely that an employee of a commercial company thinking about > using [SEC1] compression with any ECC method would get an order from > the legal department to stay away from compression. The fact that > somebody on the Internet posted something to the contrary has little > weight for them. My contribution is an attempt towards a compact > representation that is actually usable in practice. It's the most > direct extension to the 1985 idea by [Miller] (see my document for > details). > > Thank you. > > _______________________________________________ > saag mailing list > saag@ietf.org > https://www.ietf.org/mailman/listinfo/saag -- email: rstruik.ext@gmail.com | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 From prvs=9693c77741=dbrown@certicom.com Wed Dec 12 10:41:05 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id CFA461F0CE0 for ; Wed, 12 Dec 2012 10:41:05 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -5.103 X-Spam-Level: X-Spam-Status: No, score=-5.103 tagged_above=-999 required=5 tests=[AWL=0.100, BAYES_00=-2.599, MIME_QP_LONG_LINE=1.396, RCVD_IN_DNSWL_MED=-4] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6qfIHOacmaha for ; Wed, 12 Dec 2012 10:41:04 -0800 (PST) Received: from mhs060cnc.rim.net (mhs060cnc.rim.net [208.65.73.34]) by ietfa.amsl.com (Postfix) with ESMTP id 19E691F0CDB for ; Wed, 12 Dec 2012 10:41:03 -0800 (PST) X-AuditID: 0a41282f-b7fea6d000001d56-c0-50c8cfb13308 Received: from XCT106CNC.rim.net (xct106cnc.rim.net [10.65.161.206]) by mhs060cnc.rim.net (SBG) with SMTP id 6D.59.07510.1BFC8C05; Wed, 12 Dec 2012 12:40:49 -0600 (CST) Received: from XCT111CNC.rim.net (10.65.161.211) by XCT106CNC.rim.net (10.65.161.206) with Microsoft SMTP Server (TLS) id 14.2.318.1; Wed, 12 Dec 2012 13:40:49 -0500 Received: from XMB111CNC.rim.net ([fe80::fcd6:cc6c:9e0b:25bc]) by XCT111CNC.rim.net ([::1]) with mapi id 14.02.0318.001; Wed, 12 Dec 2012 13:40:48 -0500 From: Dan Brown To: 'Andrey Jivsov' , "saag@ietf.org" , "cfrg@irtf.org" Thread-Topic: [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) Thread-Index: AQHN1+JKYfEillVVT0CYN/ZbTZXZi5gVcVkg Date: Wed, 12 Dec 2012 18:40:48 +0000 Message-ID: <810C31990B57ED40B2062BA10D43FBF50ECB6A@XMB111CNC.rim.net> References: <50C79E2A.9040100@brainhub.org> In-Reply-To: <50C79E2A.9040100@brainhub.org> Accept-Language: en-CA, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.65.160.245] Content-Type: text/plain; charset="us-ascii" content-transfer-encoding: quoted-printable MIME-Version: 1.0 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFrrOKsWRmVeSWpSXmKPExsXC5bjwnO7G8ycCDJZP07To/nGQyeJ11y8m iyn9nUwOzB63px9m81iy5CeTx+SNh9kCmKMaGG2SEkvKgjPT8/TtbBLz8vJLEktSFVJSi5Nt lXxS0xNzFAKKMssSkysVXDKLk3MSM3NTi5QUMlNslUyUFApyEpNTc1PzSmyVEgsKUvNSlOy4 FDCADVBZZp5Cal5yfkpmXrqtkmewv66FhamlrqGSnW5CJ0/GlOO3WAqmKlfMb3jI2MB4QKaL kYNDQsBE4kWTdhcjJ5ApJnHh3nq2LkYuDiGBVYwSs/uWM0E4Kxklbi4/C+XMYZQ42NvICNLC JqAqcf/oOWaQSSICeRL/tteBhIWBzO7La9hAbBGBfInN+9dD2UYSLbt62UFsFqDW1vlHmEBs XgE3ieX/14CNFBLQlnja/gasnlNAR+LSuyfMIDajgKzE7rPXweqZBcQlbj2ZzwRxtYDEkj3n mSFsUYmXj/+xQtiKEqtf3WKDqNeRWLD7E5StLbFs4WtmiL2CEidnPmGB2KsgceX6PpYJjOKz kKyYhaR9FpL2WUjaFzCyrGIUzM0oNjAzSM5L1ivKzNXLSy3ZxAhOKRr6Oxjfvrc4xCjAwajE wztxx4kAIdbEsuLK3EOMEhzMSiK8bgeAQrwpiZVVqUX58UWlOanFhxhdgSE0kVmKOzkfmO7y SuKNDQxwc5TEeZWZDwYICaQDk1V2ampBahHMHCYOTpA9XFIixcCUk1qUWFqSEQ9KjPHFwNQo 1cCY8tIgWk3/1eqLvz8kbDmXdsF1r+2Lk2cvZ7RZHmN3OfegwUf2U2fs1n9L1nbM4b7PL2vc sEFhcsBFhgu9Dsfzu3qCHy32O2fgaVvx66I5h8fL8jSTx15pRl9THDy/3/q2KsSAb6Zs2DfO sDvmxxrffFh+NHe9ypyVHgof/WIm85yYmzxN4dMvJZbijERDLeai4kQA4ER++WoDAAA= Subject: Re: [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 18:41:05 -0000 Hi Andrey, Some quibbles. The SEC1 EC point format profiles the ANSI X9.62 and IEEE 1363 formats. My belief is that octet strings, rather than integers, were chosen (long bef= ore I was involved) for these formats because (at least partly, and perhaps= mainly) these standards also allowed other finite fields (binary and odd ch= aracteristic extension fields), which are not naturally represented by integ= ers. The SEC1 format also has the property of being a prefix-free encoding (for a= given elliptic curve), which I think was intentional. My limited understan= ding of networking theory is that prefix-free encoding helps to avoid misint= erpretations of streams. Well, at least DER encoding of ASN.1 seems (to me)= to be prefix-free. Certainly, the SEC1 format prefix-free property is redu= ndant when inside an ASN.1 wrapper, but otherwise, if used outside of ASN.1,= the prefix-free property of SEC1 may be a little helpful. Your ID mentions power-of-two byte alignment. I understand alignment to be= quite important for storage, but how important is it for networking? (Octe= t string formats help networking interoperability; for local storage, an imp= lementation can really use any format.) Because your format specifies integers, it can fit into an ASN.1 type. The= current ASN.1 types for ECC public keys (and generators in domain parameter= s) expect ASN.1 octet string types. These ASN.1 ECC public key formats wou= ld need to be changed. Some formats use two's complement, which assumes signed integers. I think t= hat BER and DER use it for integers. This forces a sign bit, which could ad= d a byte. Section 6 of your ID says a P-256 point will never exceed 32 byte= s, but it might need an extra byte if DER encoded. (Please correct me if I= am wrong, which is likely, since I am not an ASN.1 expert.) The extra sign= byte would have value zero, which slightly conflicts with the SEC1 format f= or the point-at-infinity. Also, since DER encodings are variable length, th= e power-of-two alignment might suffer. Best regards, Daniel Brown Research In Motion Limited > -----Original Message----- > From: saag-bounces@ietf.org [mailto:saag-bounces@ietf.org] On Behalf Of > Andrey Jivsov > Sent: Tuesday, December 11, 2012 3:57 PM > To: saag@ietf.org; cfrg@irtf.org > Subject: [saag] A proposal for compact representation of an elliptic > curve point (ECC point compression) > > Greetings. > > > I thought that it would be useful for the Internet community to have an > IETF document that describes how to encode an ECC point. I will focus > on the elliptic curves over the prime fields here. > > http://datatracker.ietf.org/doc/draft-jivsov-ecc-compact > > > Cryptographic protocols defined in IETF most often work with large > integers, such as the modulus of an RSA key, which they encode with > some applicable protocol-specific method. > > Unfortunately, the default representation of an ECC point is not just a > "large integer". It is either a pair of integers of x,y, or x with > optional information about y. Additional metadata tagged to x,y is > common. The encoding of an ECC point needs further definition, plus the > additional complexity is present due to the decisions to make ECC point > compression optional (I suspect on the ground of IPR concerns). > > In the ideal world the situation would be the following: there is an > RFC for ECC point definition; it uses compact representation; the > representation is just a large integer; it's free of patents; secure; > and that's the default mandatory method in every IETF standard. > > I am proposing here a format that in my opinion comes the closest to > the ideal features outlined above. Getting to the ideal world is > another story, but the first step on this journey is a working method > that I am pleased to present here. At the very least, the new protocols > can take advantage of the proposal; otherwise the new submissions will > likely to gravitate towards the SEC1 format, at least on the practical > grounds because the SEC1 is the only popular format that is searchable > and publicly available. I would like to offer an alternative / useful > point of reference to future standards. > > Thank you. > > _______________________________________________ > saag mailing list > saag@ietf.org > https://www.ietf.org/mailman/listinfo/saag --------------------------------------------------------------------- This transmission (including any attachments) may contain confidential infor= mation, privileged material (including material protected by the solicitor-c= lient or other applicable privileges), or constitute non-public information.= Any use of this information by anyone other than the intended recipient is= prohibited. If you have received this transmission in error, please immedia= tely reply to the sender and delete this information from your system. Use,= dissemination, distribution, or reproduction of this transmission by uninte= nded recipients is not authorized and may be unlawful. From housley@vigilsec.com Wed Dec 12 10:43:41 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D10BA21F87FB for ; Wed, 12 Dec 2012 10:43:41 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -102.564 X-Spam-Level: X-Spam-Status: No, score=-102.564 tagged_above=-999 required=5 tests=[AWL=0.035, BAYES_00=-2.599, USER_IN_WHITELIST=-100] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id qLBnlpGyWSrt for ; Wed, 12 Dec 2012 10:43:41 -0800 (PST) Received: from odin.smetech.net (mail.smetech.net [208.254.26.82]) by ietfa.amsl.com (Postfix) with ESMTP id 49C7C21F87C9 for ; Wed, 12 Dec 2012 10:43:41 -0800 (PST) Received: from localhost (unknown [208.254.26.81]) by odin.smetech.net (Postfix) with ESMTP id 9B6039A4023; Wed, 12 Dec 2012 13:43:50 -0500 (EST) X-Virus-Scanned: amavisd-new at smetech.net Received: from odin.smetech.net ([208.254.26.82]) by localhost (ronin.smetech.net [208.254.26.81]) (amavisd-new, port 10024) with ESMTP id lOVl++H6dLy7; Wed, 12 Dec 2012 13:43:27 -0500 (EST) Received: from [192.168.2.100] (pool-96-255-37-162.washdc.fios.verizon.net [96.255.37.162]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by odin.smetech.net (Postfix) with ESMTP id DB52E9A401E; Wed, 12 Dec 2012 13:43:49 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v1085) Content-Type: text/plain; charset=us-ascii From: Russ Housley In-Reply-To: <810C31990B57ED40B2062BA10D43FBF50ECB6A@XMB111CNC.rim.net> Date: Wed, 12 Dec 2012 13:43:39 -0500 Content-Transfer-Encoding: quoted-printable Message-Id: <5B13CF7D-9D78-40DF-B3E9-C20EAE5AE03C@vigilsec.com> References: <50C79E2A.9040100@brainhub.org> <810C31990B57ED40B2062BA10D43FBF50ECB6A@XMB111CNC.rim.net> To: Dan Brown X-Mailer: Apple Mail (2.1085) Cc: "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [saag] [Cfrg] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 18:43:41 -0000 Dan: OCTET STRING was chosen to avoid the need to carry an extra byte to make = the sign bit a zero. Russ On Dec 12, 2012, at 1:40 PM, Dan Brown wrote: > My belief is that octet strings, rather than integers, were chosen = (long before I was involved) for these formats because (at least partly, = and perhaps mainly) these standards also allowed other finite fields = (binary and odd characteristic extension fields), which are not = naturally represented by integers. =20 From openpgp@brainhub.org Wed Dec 12 11:04:02 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 4D02421E80C0 for ; Wed, 12 Dec 2012 11:04:02 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -0.065 X-Spam-Level: X-Spam-Status: No, score=-0.065 tagged_above=-999 required=5 tests=[AWL=0.372, BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_NET=0.611, RDNS_NONE=0.1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id TTAwNdAszqQ3 for ; Wed, 12 Dec 2012 11:04:01 -0800 (PST) Received: from qmta07.emeryville.ca.mail.comcast.net (qmta07.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:64]) by ietfa.amsl.com (Postfix) with ESMTP id 5766521F88A8 for ; Wed, 12 Dec 2012 11:04:01 -0800 (PST) Received: from omta08.emeryville.ca.mail.comcast.net ([76.96.30.12]) by qmta07.emeryville.ca.mail.comcast.net with comcast id afbH1k0040FhH24A7j40BH; Wed, 12 Dec 2012 19:04:00 +0000 Received: from [127.0.0.1] ([69.181.162.123]) by omta08.emeryville.ca.mail.comcast.net with comcast id aj3z1k0062g33ZR8Uj3zPk; Wed, 12 Dec 2012 19:04:00 +0000 Message-ID: <50C8D4D1.8050805@brainhub.org> Date: Wed, 12 Dec 2012 11:02:41 -0800 From: Andrey Jivsov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120911 Thunderbird/15.0.1 MIME-Version: 1.0 To: "Scott Fluhrer (sfluhrer)" References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1355339040; bh=5Q2wWUFeHobYtuR14fHD1+17lLionxmlcOlL9hCEMvQ=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=s0c5x0P44doKGtZwVoYzHxlXWL496eoJNvvlj3w1xONbZKSCFunRox02fZCgatzO0 I2IRdgTJ8TMNNn6ORxPebvqGUIutRRtnPgxr1Q0blBXadt6DgclokrtDS3uywfNaB+ w/zteoOHNQKk4YIZhcYH9YFj6RBTDn3Bm2wxZiyD79mUbQ4fBuf9kiSaZ7cmqQHLLq SGDtyAHj2ls63139zC5FxawtVz3N4+sx8yp4OIPCJ2/I1YEwKN8ZYQdKIk79UiWGIX gugQNpBLV+nhJQa5bePRXEXX194umwh8SrUzrk0a1LxpIx4+KW+iJMNGPBXuqquEdG fR3X8OfXKpEEw== Cc: "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [saag] [Cfrg] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 19:04:02 -0000 I have the same comment as Scott, but I am not sure exactly what Rene means. I will assume that Rene says that because there are two y for each x, one can calculate the corresponding y or p-y and choose one at random. The format I proposed indeed fits very well with the feature of the ECDH-based protocol that Scott refers to (which covers ECC encryption and key agreement). As the draft shows, one simply drops the y coordinate to obtain the compact representation, while there are no extra steps for ECDH key generation (because ECDH keys are not sensitive to maintaining the "right" y). The extra key generation step is only needed for ECDSA keys. On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote: > > >> -----Original Message----- >> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of >> Rene Struik >> Sent: Wednesday, December 12, 2012 9:17 AM >> To: Andrey Jivsov >> Cc: cfrg@irtf.org; saag@ietf.org; Peter Gutmann >> Subject: Re: [Cfrg] [saag] A proposal for compact representation of an >> elliptic curve point (ECC point compression) >> >> Hi Andrey: >> >> One can already implement the x-coordinate only representation of an >> elliptic curve point simply by converting the affine representation into >> compressed representation and randomizing the compression "bit". The >> reverse operation then yields the point or its inverse (which have the same >> x-coordinate). >> >> To my knowledge, this does not require any changes to data formatting (nor >> additional bytes). > > That randomization of the y-component works fine for ECDH (at least, if you use only the x-component of the shared secret); however, it doesn't work for ECDSA public keys. > >> >> Best regards, >> >> Rene >> >> On 12/11/2012 6:37 PM, Andrey Jivsov wrote: >>> On 12/11/2012 03:15 PM, Peter Gutmann wrote: >>>> Andrey Jivsov writes: >>>> >>>>> I thought that it would be useful for the Internet community to have >>>>> an IETF document that describes how to encode an ECC point. >>>> >>>> Maybe I'm missing something here, but wouldn't this just consist of: >>>> >>>> -- Snip -- >>>> >>>> See [1]. >>>> >>>> [1] X9.62-2005, "Public Key Cryptography for the Financial Services >>>> Industry: >>>> The Elliptic Curve Digital Signature Standard (ECDSA)", November, 2005. >>>> >>>> -- Snip -- >>>> >>>> That's what every existing RFC that uses ECC seems to be using. >>>> >>>> Peter. >>>> >>> >>> Hello Peter. >>> >>> "X9.62-2005" in the search engine lends me on a page that asks for >>> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is >>> more popular as a reference (assuming they are identical regarding the >>> point compression method). >>> >>> I claim that what I submitted is better in many respects than SEC1. >>> >>> Let me expand on one of the benefits not covered in the spec. It's >>> very likely that an employee of a commercial company thinking about >>> using [SEC1] compression with any ECC method would get an order from >>> the legal department to stay away from compression. The fact that >>> somebody on the Internet posted something to the contrary has little >>> weight for them. My contribution is an attempt towards a compact >>> representation that is actually usable in practice. It's the most >>> direct extension to the 1985 idea by [Miller] (see my document for >>> details). >>> >>> Thank you. >>> >>> _______________________________________________ >>> saag mailing list >>> saag@ietf.org >>> https://www.ietf.org/mailman/listinfo/saag >> >> >> -- >> email: rstruik.ext@gmail.com | Skype: rstruik >> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 >> >> _______________________________________________ >> Cfrg mailing list >> Cfrg@irtf.org >> http://www.irtf.org/mailman/listinfo/cfrg From rstruik.ext@gmail.com Wed Dec 12 11:23:32 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3E66E21E804E for ; Wed, 12 Dec 2012 11:23:32 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -3.599 X-Spam-Level: X-Spam-Status: No, score=-3.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id fZ2ztyR5sPT4 for ; Wed, 12 Dec 2012 11:23:32 -0800 (PST) Received: from mail-ie0-f172.google.com (mail-ie0-f172.google.com [209.85.223.172]) by ietfa.amsl.com (Postfix) with ESMTP id 12AB621F8703 for ; Wed, 12 Dec 2012 11:23:12 -0800 (PST) Received: by mail-ie0-f172.google.com with SMTP id c13so2589504ieb.31 for ; Wed, 12 Dec 2012 11:23:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=bLF5wp8re59uYAV9+TpJcAsa8fmxN8q1+e2rAMoDcE8=; b=s9jA1GLmGpWEwgCdT3Gn0HnjXlLF5v3jM9wbMGyF2YYTyHrhXIj4+B70oSPyc8AN8g hP+OEJ0mizMoLxeHJR8BMQ/KAFEHItSpjdoWBeLZwDzygNEVmjm3jZD3ncyepJ8+sEOl ElqV6KvywgroNhkyXXYYHrUtHGXh3vl2U255SueG1d/gCqbEdX213bc6kAZNboLbiHnm ePtBc4ziKa9AnG+CvHi2PczZeYK+jtcGiCNiYrY6v7WDrsrT5ZnAUTNU5UpHNftubLY+ C+aHfjAu4sYAw0Y5WPS4+o8iErKayNxt5Poi7614k3ORGuAtgn8I5TTcBzIThwDZKTpB Zx9w== Received: by 10.43.130.131 with SMTP id hm3mr1728001icc.25.1355340187690; Wed, 12 Dec 2012 11:23:07 -0800 (PST) Received: from [192.168.1.103] (CPE0013100e2c51-CM001cea35caa6.cpe.net.cable.rogers.com. [99.231.4.27]) by mx.google.com with ESMTPS id gz10sm12808741igc.9.2012.12.12.11.23.06 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 12 Dec 2012 11:23:07 -0800 (PST) Message-ID: <50C8D991.5080809@gmail.com> Date: Wed, 12 Dec 2012 14:22:57 -0500 From: Rene Struik User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/17.0 Thunderbird/17.0 MIME-Version: 1.0 To: Andrey Jivsov References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <50C8D4D1.8050805@brainhub.org> In-Reply-To: <50C8D4D1.8050805@brainhub.org> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: "cfrg@irtf.org" , "saag@ietf.org" , "Scott Fluhrer \(sfluhrer\)" Subject: Re: [saag] [Cfrg] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 19:23:32 -0000 Hi Andrey: I just wanted to understand the problem one tries to solve. My simple suggestion was aimed at realizing the same effect. [I had a short offline exchange with Scott Fluhrer on this, including on the ECDSA verification angle - summarized by the sentence below] In most common implementations, ECDSA signature verification cost is roughly the same, no matter whether one know the y-coordinate of the signature verification key or not. Given this, it seems that for ECDSA signature verification and ECDH the argument for yet another construct seems to be somewhat weak: my simple suggestion would also work, does not require new formatting, or transition periods (and, to my knowledge, does not read on any "nontechnical issues"). I hope this helps. Best regards, Rene On 12/12/2012 2:02 PM, Andrey Jivsov wrote: > I have the same comment as Scott, but I am not sure exactly what Rene > means. > > I will assume that Rene says that because there are two y for each x, > one can calculate the corresponding y or p-y and choose one at random. > > The format I proposed indeed fits very well with the feature of the > ECDH-based protocol that Scott refers to (which covers ECC encryption > and key agreement). As the draft shows, one simply drops the y > coordinate to obtain the compact representation, while there are no > extra steps for ECDH key generation (because ECDH keys are not > sensitive to maintaining the "right" y). > > The extra key generation step is only needed for ECDSA keys. > > On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote: >> >> >>> -----Original Message----- >>> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of >>> Rene Struik >>> Sent: Wednesday, December 12, 2012 9:17 AM >>> To: Andrey Jivsov >>> Cc: cfrg@irtf.org; saag@ietf.org; Peter Gutmann >>> Subject: Re: [Cfrg] [saag] A proposal for compact representation of an >>> elliptic curve point (ECC point compression) >>> >>> Hi Andrey: >>> >>> One can already implement the x-coordinate only representation of an >>> elliptic curve point simply by converting the affine representation >>> into >>> compressed representation and randomizing the compression "bit". The >>> reverse operation then yields the point or its inverse (which have >>> the same >>> x-coordinate). >>> >>> To my knowledge, this does not require any changes to data >>> formatting (nor >>> additional bytes). >> >> That randomization of the y-component works fine for ECDH (at least, >> if you use only the x-component of the shared secret); however, it >> doesn't work for ECDSA public keys. >> >>> >>> Best regards, >>> >>> Rene >>> >>> On 12/11/2012 6:37 PM, Andrey Jivsov wrote: >>>> On 12/11/2012 03:15 PM, Peter Gutmann wrote: >>>>> Andrey Jivsov writes: >>>>> >>>>>> I thought that it would be useful for the Internet community to have >>>>>> an IETF document that describes how to encode an ECC point. >>>>> >>>>> Maybe I'm missing something here, but wouldn't this just consist of: >>>>> >>>>> -- Snip -- >>>>> >>>>> See [1]. >>>>> >>>>> [1] X9.62-2005, "Public Key Cryptography for the Financial Services >>>>> Industry: >>>>> The Elliptic Curve Digital Signature Standard (ECDSA)", November, >>>>> 2005. >>>>> >>>>> -- Snip -- >>>>> >>>>> That's what every existing RFC that uses ECC seems to be using. >>>>> >>>>> Peter. >>>>> >>>> >>>> Hello Peter. >>>> >>>> "X9.62-2005" in the search engine lends me on a page that asks for >>>> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is >>>> more popular as a reference (assuming they are identical regarding the >>>> point compression method). >>>> >>>> I claim that what I submitted is better in many respects than SEC1. >>>> >>>> Let me expand on one of the benefits not covered in the spec. It's >>>> very likely that an employee of a commercial company thinking about >>>> using [SEC1] compression with any ECC method would get an order from >>>> the legal department to stay away from compression. The fact that >>>> somebody on the Internet posted something to the contrary has little >>>> weight for them. My contribution is an attempt towards a compact >>>> representation that is actually usable in practice. It's the most >>>> direct extension to the 1985 idea by [Miller] (see my document for >>>> details). >>>> >>>> Thank you. >>>> >>>> _______________________________________________ >>>> saag mailing list >>>> saag@ietf.org >>>> https://www.ietf.org/mailman/listinfo/saag >>> >>> >>> -- >>> email: rstruik.ext@gmail.com | Skype: rstruik >>> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 >>> >>> _______________________________________________ >>> Cfrg mailing list >>> Cfrg@irtf.org >>> http://www.irtf.org/mailman/listinfo/cfrg > -- email: rstruik.ext@gmail.com | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 From openpgp@brainhub.org Wed Dec 12 12:03:41 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2324C11E80BA for ; Wed, 12 Dec 2012 12:03:41 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 0.851 X-Spam-Level: X-Spam-Status: No, score=0.851 tagged_above=-999 required=5 tests=[AWL=-0.693, BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_NET=0.611, RDNS_NONE=0.1, SARE_FWDLOOK=1.666, SARE_MILLIONSOF=0.315] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VxxEKtGIhOrK for ; Wed, 12 Dec 2012 12:03:40 -0800 (PST) Received: from qmta11.emeryville.ca.mail.comcast.net (qmta11.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:44:76:96:27:211]) by ietfa.amsl.com (Postfix) with ESMTP id 856B711E809A for ; Wed, 12 Dec 2012 12:03:40 -0800 (PST) Received: from omta08.emeryville.ca.mail.comcast.net ([76.96.30.12]) by qmta11.emeryville.ca.mail.comcast.net with comcast id aeZ51k0010FhH24ABk3gHx; Wed, 12 Dec 2012 20:03:40 +0000 Received: from [127.0.0.1] ([69.181.162.123]) by omta08.emeryville.ca.mail.comcast.net with comcast id ak3f1k00C2g33ZR8Uk3fF4; Wed, 12 Dec 2012 20:03:40 +0000 Message-ID: <50C8E2CD.3050002@brainhub.org> Date: Wed, 12 Dec 2012 12:02:21 -0800 From: Andrey Jivsov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120911 Thunderbird/15.0.1 MIME-Version: 1.0 To: Dan Brown References: <50C79E2A.9040100@brainhub.org> <810C31990B57ED40B2062BA10D43FBF50ECB6A@XMB111CNC.rim.net> In-Reply-To: <810C31990B57ED40B2062BA10D43FBF50ECB6A@XMB111CNC.rim.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1355342620; bh=A/5b2HIwUqLVL5Re3yTAPUcecR8EP5rA0t3ZIG1PW1M=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=LgKDsfntUF9RBTthClxD63PYCfOzUhOQKLiLBDDOZRdNNJ+uphVx2ZypUskczzoS/ 0c0NnS6X3rvrRzhsYyWDROT7n7YGyp9SoPsZskfVuDXsls5+IiSR88xl4qcXF/ZEAn bXog0PduuGQ2ewTZ6CeKScoWiteAdVPdAENAIGN7ped1dn15Zq9llt3dRS2ZAvMhSZ yBrmxnMBVTIf+EuIInU9L42u2RD8X/UIEy1caFe3pWAMMfjOKYHbwC0GafeGvlELXN AwjlpwCQBVhbykc09SQYxbufT2kxhyj2ry2XJgAnPZCRZmEcH1XnsvrCnc7ByvhSsE 3CiUdquSiKPuA== Cc: "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 20:03:41 -0000 Hello Dan: On 12/12/2012 10:40 AM, Dan Brown wrote: > Hi Andrey, > > Some quibbles. > > The SEC1 EC point format profiles the ANSI X9.62 and IEEE 1363 formats. > > My belief is that octet strings, rather than integers, were chosen (long before I was involved) for these formats because (at least partly, and perhaps mainly) these standards also allowed other finite fields (binary and odd characteristic extension fields), which are not naturally represented by integers. I believe that the same ideas I used in my proposal will carry over to EC(F(2^m)) curves, i.e. "binary curves", but I put emphasis on the proposal being a very simple spec for the ease of reference and analysis. As a very forward-looking thought, if there is interest in similar proposal for binary curves, this could be another document. > > The SEC1 format also has the property of being a prefix-free encoding (for a given elliptic curve), which I think was intentional. My limited understanding of networking theory is that prefix-free encoding helps to avoid misinterpretations of streams. Well, at least DER encoding of ASN.1 seems (to me) to be prefix-free. Certainly, the SEC1 format prefix-free property is redundant when inside an ASN.1 wrapper, but otherwise, if used outside of ASN.1, the prefix-free property of SEC1 may be a little helpful. > Interesting. It sheds more light on the rationale behind the SEC1 format. I feel that the complexity of SEC1 doesn't compare favorably with my value proposition: An ECC key in F(p) can be represented the same way as we represent an RSA key modulus. It's just an integer. One might advance the simplicity even further and say that there is no compressed or uncompressed point: there is the compact definition that I proposed. This is simple and elegant. > Your ID mentions power-of-two byte alignment. I understand alignment to be quite important for storage, but how important is it for networking? (Octet string formats help networking interoperability; for local storage, an implementation can really use any format.) My thought was about applications that need to pack lots of ECC points together. For example, a blob with millions of public keys. It helps that the indexing is an efficient bit shift of the offset to get an index and there there is no space wasted on a byte that carries only one bit. > > Because your format specifies integers, it can fit into an ASN.1 type. The current ASN.1 types for ECC public keys (and generators in domain parameters) expect ASN.1 octet string types. These ASN.1 ECC public key formats would need to be changed. ( One can put an integer that is less than 2^256 into a 256 bit octet string by zero-padding it. ) My format will be able to be encoded as an OCTET STRING, BIT STRING, or INTEGER. So, the higher level encodings are free to select the optimal encoding. > > Some formats use two's complement, which assumes signed integers. I think that BER and DER use it for integers. This forces a sign bit, which could add a byte. Section 6 of your ID says a P-256 point will never exceed 32 bytes, but it might need an extra byte if DER encoded. (Please correct me if I am wrong, which is likely, since I am not an ASN.1 expert.) The extra sign byte would have value zero, which slightly conflicts with the SEC1 format for the point-at-infinity. Also, since DER encodings are variable length, the power-of-two alignment might suffer. > Let's analyze this by comparison with the encoding of an RSA key modulus (or P,Q,G of DSA parameters). Does the encoding that packages together the integers (such as ASN.1+DER) requires a leading zero? Well, then I will respectfully note that this is an unfortunate design decision because overwhelmingly all crypto protocol rely on positive integers. If an RSA modulus encoding will need a leading zero, so will the ECC compact point. In any case, I would argue for a modular design in which an ECC point format shall not attempt to remedy any issue with higher-level encodings (because it will inevitably bring some overhead). I am simply bringing the ECC encoding within the pack of currently used algorithms. Just as for an RSA modulus, one can try to generate keys so that they don't have the high bit set, but I am not proposing that in general. Note, however, that there is an interesting option that my proposal introduced. There are applications that involve keys being read/typed by humans, where the key size is important. In this case one can generate an ECC key with some number of highest bits being zero. The method is also of value for P-521 keys that can be represented under 2^512. My format will mean that the final key will get shorter ("it is just an integer"). I believe that SEC1 will encode it as 03 00 00 00 ... FF, where FF is the most significant byte of the x. (Am I correct that SEC1 doesn't allow 03 FF encoding in my example?). Thank you. From openpgp@brainhub.org Wed Dec 12 12:52:49 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A0ABD21F84DC for ; Wed, 12 Dec 2012 12:52:49 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 0.059 X-Spam-Level: X-Spam-Status: No, score=0.059 tagged_above=-999 required=5 tests=[AWL=0.496, BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_NET=0.611, RDNS_NONE=0.1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id B9aFX04OybbZ for ; Wed, 12 Dec 2012 12:52:49 -0800 (PST) Received: from qmta03.emeryville.ca.mail.comcast.net (qmta03.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:32]) by ietfa.amsl.com (Postfix) with ESMTP id 7D64921F84D0 for ; Wed, 12 Dec 2012 12:52:49 -0800 (PST) Received: from omta07.emeryville.ca.mail.comcast.net ([76.96.30.59]) by qmta03.emeryville.ca.mail.comcast.net with comcast id afmX1k00K1GXsucA3ksVBg; Wed, 12 Dec 2012 20:52:29 +0000 Received: from [127.0.0.1] ([69.181.162.123]) by omta07.emeryville.ca.mail.comcast.net with comcast id aksU1k0012g33ZR8UksUKr; Wed, 12 Dec 2012 20:52:29 +0000 Message-ID: <50C8EE3E.90600@brainhub.org> Date: Wed, 12 Dec 2012 12:51:10 -0800 From: Andrey Jivsov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120911 Thunderbird/15.0.1 MIME-Version: 1.0 To: "Scott Fluhrer (sfluhrer)" References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <50C8D4D1.8050805@brainhub.org> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1355345549; bh=szMoKcG7Fqcy8GXHO35kHVJLUcKby0dBoQ8Bvya0F+k=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=iQb6wro/bxjGcLg9a32OmzP2vduvMXjwvNjFjqrhUUrh1bsFvvB1um/Yr52gPbFhn ozOiBUYmnVcdMCKRx6Hf//jcpgVZhKCyVSY+kKAkaH7NeXtuneWSgYevJCgXBSkjRM T5+laIeqB9CFJHh+W/cVaI2kYRBK7lzmcVigQ6q2PGrdw92+32G/s9awA0HZl2R5XZ s0QY84WlM1Oj2twKaDBtM8ctU7LYVjNWNWCTZ7VahUZw73wSvZKBjY7H5kcQbrf0rO 7iWBX3v5iL7aAmdsY1wUHmhaHEYQmJXzshto081e7c5RMVxr83wjKiy5ssn6dVy/Rc mamCPPxg84u7A== Cc: "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [saag] [Cfrg] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 20:52:49 -0000 On 12/12/2012 12:10 PM, Scott Fluhrer (sfluhrer) wrote: > > >> -----Original Message----- >> From: Andrey Jivsov [mailto:openpgp@brainhub.org] >> Sent: Wednesday, December 12, 2012 2:03 PM >> To: Scott Fluhrer (sfluhrer) >> Cc: Rene Struik; cfrg@irtf.org; saag@ietf.org; Peter Gutmann >> Subject: Re: [Cfrg] [saag] A proposal for compact representation of an >> elliptic curve point (ECC point compression) >> >> I have the same comment as Scott, but I am not sure exactly what Rene >> means. >> >> I will assume that Rene says that because there are two y for each x, one can >> calculate the corresponding y or p-y and choose one at random. >> >> The format I proposed indeed fits very well with the feature of the ECDH- >> based protocol that Scott refers to (which covers ECC encryption and key >> agreement). As the draft shows, one simply drops the y coordinate to obtain >> the compact representation, while there are no extra steps for ECDH key >> generation (because ECDH keys are not sensitive to maintaining the "right" >> y). >> >> The extra key generation step is only needed for ECDSA keys. > > Actually, as Rene pointed out to me privately, it isn't much more for ECDSA, at least with the standard algorithm. > > The ECDSA verification is a check whether r = (uG + vQ)_x, where Q is the public key. If you are given only the x coordinate of Q, what you do is to pick a corresponding y coordinate (so you get a point S where either S=Q or S=-Q, where Q is the original public key), and check if one of these two holds: > > r = (uG + vS)_x > r = (uG - vS)_x > > If either does, the signature verifies. This adds the cost of a single point addition (and the cost of generating the y coordinate of S); fairly small. Signature verification is a very common crypto operation (i.e. verifying the certificate chain, verifying e-mail signatures in the users's mailbox, etc). It's important to optimize the format for most common operations. Given that we always have to calculate -/+ y from x, I will ignore this cost in the rest of this message. My proposal: no performance overhead for any operation with a public key. No storage overhead. Potentially will work with more than ECDH and ECDSA because it restores the precise y. Other proposals: at least one byte storage overhead, one point addition, IPR issues. The seeming magic with my proposal happens because it shifts the cost or determining the bit of y into the the key generation stage. Key generation is an offline operation. Keys can be pre-generated even for ephemeral keys used for encryption. However, in most cases the only additional overhead that my proposal adds to generation is at most one F(p) subtraction (negligible to the cost of a single point addition). Thank you. From openpgp@brainhub.org Wed Dec 12 14:15:26 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0313A21E8054 for ; Wed, 12 Dec 2012 14:15:26 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -0.003 X-Spam-Level: X-Spam-Status: No, score=-0.003 tagged_above=-999 required=5 tests=[AWL=0.434, BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_NET=0.611, RDNS_NONE=0.1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Uu+JAl6oimEj for ; Wed, 12 Dec 2012 14:15:25 -0800 (PST) Received: from qmta05.emeryville.ca.mail.comcast.net (qmta05.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:48]) by ietfa.amsl.com (Postfix) with ESMTP id F02FE21F8854 for ; Wed, 12 Dec 2012 14:15:21 -0800 (PST) Received: from omta11.emeryville.ca.mail.comcast.net ([76.96.30.36]) by qmta05.emeryville.ca.mail.comcast.net with comcast id ak6c1k0030mlR8UA5mFGBs; Wed, 12 Dec 2012 22:15:16 +0000 Received: from [127.0.0.1] ([69.181.162.123]) by omta11.emeryville.ca.mail.comcast.net with comcast id amFF1k0092g33ZR8XmFGVM; Wed, 12 Dec 2012 22:15:16 +0000 Message-ID: <50C901A5.3070409@brainhub.org> Date: Wed, 12 Dec 2012 14:13:57 -0800 From: Andrey Jivsov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120911 Thunderbird/15.0.1 MIME-Version: 1.0 To: Peter Gutmann References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1355350516; bh=hFK3p6wR5cpvITWTtmXfEfUqY+CGeZbvOLlA0U8dGcQ=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=aDwtwAgoeu6hTpUyaAKpvBu5KC+0Uzzggu6w/+PH0mSrrST4U0upj1tj3tmBpULC1 LwRpwy7lINADvja3Vgv2ySEMvDYtdPhVA2s/xOZpptubUS/H2zAfKU0UZ0YRrJeX+r S+noXYvxiNODLHtmH/hnGQA81Q0T/Qinjyn1Wl+ohwIpgTvw6lZ3GjBQ42r3JFs7l0 NLSVK2nh1GBn0nGUtNWNJOc432oFoDolyV0IzZYjN611CbtHe0gMGryRdlBMn1AptM gIiFBK49Hj+CWv+5xGVib1+oUvLTAfNnLlepvKbg7INubpbtM5eCun66JEdEDwPp5F AhbYbM5V8D8Kw== Cc: cfrg@irtf.org, saag@ietf.org Subject: Re: [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 22:15:27 -0000 On 12/12/2012 03:13 AM, Peter Gutmann wrote: > Andrey Jivsov writes: ... > >> I claim that what I submitted is better in many respects than SEC1. > > Well, it's up against a pretty much universally-adopted standard (at least in > the stuff I know of). So you have to convince the S/MIME folks, the OpenPGP > folks, the SSH folks, the SSL/TLS folks, ... to adopt your format. Given that > there's a huge amount of code deployed using the X9.62 format (or at least > implementing the X9.62 format, even if actual use is practically nonexistent), > it's going to be quite a battle to get a new format accepted. > > Peter. > I agree that it's a challenge to add this format to standards that already define point compression (OpenPGP doesn't, BTW). My message to persons working on the established protocols/formats is that here is an elegant method, consider using it the next time you introduce an incompatible change. My proposal provides the most value for the new protocols. I believe it should be a strong contender on technical grounds for anybody thinking to define new ECC-based protocol or format. The same is true for any proprietary format (i.e. let's say I want to start distributing keys as a URL... ). Thank you. From openpgp@brainhub.org Wed Dec 12 16:01:09 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 43B1B21E808E for ; Wed, 12 Dec 2012 16:01:09 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 0.249 X-Spam-Level: X-Spam-Status: No, score=0.249 tagged_above=-999 required=5 tests=[AWL=0.086, BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_NET=0.611, J_CHICKENPOX_22=0.6, RDNS_NONE=0.1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id zfB98dh8yzSS for ; Wed, 12 Dec 2012 16:01:08 -0800 (PST) Received: from qmta01.emeryville.ca.mail.comcast.net (qmta01.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:16]) by ietfa.amsl.com (Postfix) with ESMTP id A4B9121E8044 for ; Wed, 12 Dec 2012 16:01:08 -0800 (PST) Received: from omta09.emeryville.ca.mail.comcast.net ([76.96.30.20]) by qmta01.emeryville.ca.mail.comcast.net with comcast id acy11k00D0S2fkCA1o16w5; Thu, 13 Dec 2012 00:01:06 +0000 Received: from [127.0.0.1] ([69.181.162.123]) by omta09.emeryville.ca.mail.comcast.net with comcast id ao0h1k00T2g33ZR8Vo14u9; Thu, 13 Dec 2012 00:01:05 +0000 Message-ID: <50C91A57.6030207@brainhub.org> Date: Wed, 12 Dec 2012 15:59:19 -0800 From: Andrey Jivsov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120911 Thunderbird/15.0.1 MIME-Version: 1.0 To: William Whyte References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <50C8D4D1.8050805@brainhub.org> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1355356866; bh=w4aAoHVMbgfX8iXFQKADzhfyO8IySKKAkyulw9Ivyhk=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=UH3VvXXw6X/gi5XGf2L1bPSh8WMeB+Jyg+8GvCfFCQ+gzt6q8PmXUFN07RHzKqf1U EIvogxfBu/v0tSa72x5s4xOL4b550FfFhFTrP5+gLjKP4GWH2GoamRrAODbbM3DSHo RbwdrUA8VGDfNgCveNQK3T3i+uFtOyHc37uNv2lEGjOtrb4eCrnDIHshbjCYxynN+c 3A1rDoTgQOwNPDzM78pshJU5JanrginWANSWx5iMTGfIRml5J0txIUJ2s7tDK8IiOn lQnfjqEiMDRtfw33zh+2yRYRPWBE93oXgeI23MN+N9ezn7/lN1HPCryIoR8olzGhEU SmgWj+BX5M9rw== Cc: "cfrg@irtf.org" , "saag@ietf.org" , "Scott Fluhrer \(sfluhrer\)" Subject: Re: [saag] [Cfrg] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 13 Dec 2012 00:01:09 -0000 As a side note, I wonder how much the performance cost of decompression is a practical issue in protocols where ECC is used. In summary, if I am to pick the defaults, I would say that the static keys should be uncompressed, while the messages encrypted to compressed ephemeral keys. Here is what I mean: Let's look first at persistent data structures in various protocols. Decompression applies to public keys. For signature verification it means static (v.s. ephemeral) keys, which can be decompressed and cached. The stated decompression cost is only an issue for corner cases when we are verifying a stream of short messages signed by random identities. Consider an e-mail client application application (MUA), to be specific. Let's say the application is first loaded and it's verifying a large number of incoming e-mails. Many of them are likely to be from the same senders. It's likely that these are the same signers encountered in the past sessions. Thus, the keys could have been cached locally and it doesn't matter if compression is used for these keys. If the keys are unavailable (a case when the decompression cost cannot be amortized), they will be retrieved over the network from a key server. The network latency will dominate the cost of point decompression here. On the other hand, the saving is here only for the static public key. It's more of an issue for decryption of messages, when ephemeral keys are used. Especially because the point compression provides the most benefits for encrypted messages, given that they are typically encrypted to N>1 recipients, thus there is at least N*33 byte space improvement (for P-256) and each key produces M messages over its lifetime. Is the performance a practical concern here v.s. a space saving of N*M*33 given that the message need to parsed and the content decrypted? For online protocols with ephemeral keys, such as ephemeral ECDH in TLS, the point compression is probably not worth much. The point compression is optional today throughout the standards and it makes sense to keep it optional. On 12/12/2012 03:02 PM, William Whyte wrote: > Hi Scott, > >> Actually, as Rene pointed out to me privately, it isn't much more for ECDSA, at least with the standard algorithm. >> >> The ECDSA verification is a check whether r = (uG + vQ)_x, where Q is the public key. If you are given only the x coordinate of Q, what you do is to pick a corresponding y coordinate (so you get a point S where either S=Q or S=-Q, where Q is the original public key), and check if one of these two holds: >> >> r = (uG + vS)_x >> r = (uG - vS)_x >> >> If either does, the signature verifies. This adds the cost of a single point addition (and the cost of generating the y coordinate of S); fairly small. > > The problem here is that the standard speedup for ECDSA doesn't > calculate uG and vS independently, but calculates uG+vS as a single > operation. This takes much less time than the separate operations -- I > estimate about 69% of the time for openssl using the NIST p256 curve. > So the cost of doing verification without knowing Q_y is actually a > factor of close to 1.44, since you have to do the separate > calculations instead of the combined one. > > Generating the y coordinate isn't necessarily a small cost; it can > also be pretty expensive since it involves taking a square root mod a > prime. Obviously this cost also applies if you use any form of > y-coordinate compression as well as if you omit the y-coordinate, so > it's not necessarily a cost delta depending on what you're comparing > with. > > I've seen implementations in which decompression added 12% to the > running time for verify with NIST p256 and 23% to the running time for > verify with NIST p224; with openssl, last time I checked two years > ago, decompression added 12% to the running time for verify with NIST > p256 and 180% to the running time with NIST p224 because the > decompression algorithm at the time was, er, not optimized. (We > actually implemented an improved decompression algorithm for openssl > that brings the overhead back down to around 23%, but haven't had time > to release it back to the main source tree yet -- it's possible that > the openssl team have already improved it themselves). > > Cheers, > > William > From sfluhrer@cisco.com Wed Dec 12 08:52:36 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 82AE921F850D for ; Wed, 12 Dec 2012 08:52:36 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.599 X-Spam-Level: X-Spam-Status: No, score=-10.599 tagged_above=-999 required=5 tests=[AWL=0.000, BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id l0yIU1wqnqjc for ; Wed, 12 Dec 2012 08:52:30 -0800 (PST) Received: from rcdn-iport-5.cisco.com (rcdn-iport-5.cisco.com [173.37.86.76]) by ietfa.amsl.com (Postfix) with ESMTP id A7F8421F84D9 for ; Wed, 12 Dec 2012 08:52:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=3153; q=dns/txt; s=iport; t=1355331150; x=1356540750; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=+iPAqO5DXLAMkCnZWZkrUdUsgSlmM72zUu8qZddzMAQ=; b=G3HJCXvwX28diybaeCDJXLBv5eVUJuW8dRgSUe+O7vVZEeTiKXpLbDhd /yPJaBNIfts97Z7HTb0ngfjvMK5NfmcUUNlqh3YumMZ/D1IoZ2U++qOhw /l5BRkZKECpo2+h4fIAkWlUpoNChqFTwrzCvx/rW+TXn3TevDHxGoMhtv o=; X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgEFAOG1yFCtJV2a/2dsb2JhbABCA78VFnOCHgEBAQIBAQEBATc0CwwEAgEIDgMEAQEBChQFBAchBgsUCQgCBAENBQgBC4drAwkGDLQIDYlVi2JpC4EKgk1hA4pRiAWBXY0NhRGCc4FtNQ X-IronPort-AV: E=Sophos;i="4.84,267,1355097600"; d="scan'208";a="152169284" Received: from rcdn-core-3.cisco.com ([173.37.93.154]) by rcdn-iport-5.cisco.com with ESMTP; 12 Dec 2012 16:52:04 +0000 Received: from xhc-rcd-x14.cisco.com (xhc-rcd-x14.cisco.com [173.37.183.88]) by rcdn-core-3.cisco.com (8.14.5/8.14.5) with ESMTP id qBCGq4Mv012857 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Wed, 12 Dec 2012 16:52:04 GMT Received: from xmb-rcd-x04.cisco.com ([169.254.8.29]) by xhc-rcd-x14.cisco.com ([173.37.183.88]) with mapi id 14.02.0318.004; Wed, 12 Dec 2012 10:52:03 -0600 From: "Scott Fluhrer (sfluhrer)" To: Rene Struik , Andrey Jivsov Thread-Topic: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) Thread-Index: AQHN2HN1n0mZdiOeF06/Mfx4iUhUp5gVYE2g Date: Wed, 12 Dec 2012 16:52:03 +0000 Message-ID: References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> In-Reply-To: <50C891E7.4000009@gmail.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.32.244.86] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailman-Approved-At: Mon, 17 Dec 2012 08:11:33 -0800 Cc: "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [saag] [Cfrg] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 16:52:36 -0000 > -----Original Message----- > From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of > Rene Struik > Sent: Wednesday, December 12, 2012 9:17 AM > To: Andrey Jivsov > Cc: cfrg@irtf.org; saag@ietf.org; Peter Gutmann > Subject: Re: [Cfrg] [saag] A proposal for compact representation of an > elliptic curve point (ECC point compression) >=20 > Hi Andrey: >=20 > One can already implement the x-coordinate only representation of an > elliptic curve point simply by converting the affine representation into > compressed representation and randomizing the compression "bit". The > reverse operation then yields the point or its inverse (which have the sa= me > x-coordinate). >=20 > To my knowledge, this does not require any changes to data formatting (no= r > additional bytes). That randomization of the y-component works fine for ECDH (at least, if you= use only the x-component of the shared secret); however, it doesn't work f= or ECDSA public keys. >=20 > Best regards, >=20 > Rene >=20 > On 12/11/2012 6:37 PM, Andrey Jivsov wrote: > > On 12/11/2012 03:15 PM, Peter Gutmann wrote: > >> Andrey Jivsov writes: > >> > >>> I thought that it would be useful for the Internet community to have > >>> an IETF document that describes how to encode an ECC point. > >> > >> Maybe I'm missing something here, but wouldn't this just consist of: > >> > >> -- Snip -- > >> > >> See [1]. > >> > >> [1] X9.62-2005, "Public Key Cryptography for the Financial Services > >> Industry: > >> The Elliptic Curve Digital Signature Standard (ECDSA)", November, 2005= . > >> > >> -- Snip -- > >> > >> That's what every existing RFC that uses ECC seems to be using. > >> > >> Peter. > >> > > > > Hello Peter. > > > > "X9.62-2005" in the search engine lends me on a page that asks for > > $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is > > more popular as a reference (assuming they are identical regarding the > > point compression method). > > > > I claim that what I submitted is better in many respects than SEC1. > > > > Let me expand on one of the benefits not covered in the spec. It's > > very likely that an employee of a commercial company thinking about > > using [SEC1] compression with any ECC method would get an order from > > the legal department to stay away from compression. The fact that > > somebody on the Internet posted something to the contrary has little > > weight for them. My contribution is an attempt towards a compact > > representation that is actually usable in practice. It's the most > > direct extension to the 1985 idea by [Miller] (see my document for > > details). > > > > Thank you. > > > > _______________________________________________ > > saag mailing list > > saag@ietf.org > > https://www.ietf.org/mailman/listinfo/saag >=20 >=20 > -- > email: rstruik.ext@gmail.com | Skype: rstruik > cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 >=20 > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg From sfluhrer@cisco.com Wed Dec 12 12:10:56 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 19D7A11E80E3 for ; Wed, 12 Dec 2012 12:10:56 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.599 X-Spam-Level: X-Spam-Status: No, score=-10.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id MPfeDlg9znzG for ; Wed, 12 Dec 2012 12:10:55 -0800 (PST) Received: from rcdn-iport-5.cisco.com (rcdn-iport-5.cisco.com [173.37.86.76]) by ietfa.amsl.com (Postfix) with ESMTP id 0618711E80A5 for ; Wed, 12 Dec 2012 12:10:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=5125; q=dns/txt; s=iport; t=1355343055; x=1356552655; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=4NIuTZ3/j2mG1xF6w3EEnf7Q7xPNR/DU6IqzU2TehnY=; b=Sjqrk1vszWhl+T5q+gdCacU9Lf1P46PvEP/sqmnDq/ci6xzv7gr/hMYi lr4hOGjqW6RVJuJOFxYIK76Idu1Ge4ylWvqjPxwskgs5EN+lSprskt0l/ uUfieELlVdDJgbJ9hhlr8iNSbluT4xGBCM5T/frKfqYrp+nCF2Tl9zw8r g=; X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgEFAP/jyFCtJXG9/2dsb2JhbABCA78YFnOCHgEBAQIBAQEBATc0CwwEAgEIDgMEAQEBChQFBAchBgsUCQgCBA4FCAELh2sDCQYMtAsNiVWLYmkLgQqCTWEDilGIBYFdjQ2FEYJzgW01 X-IronPort-AV: E=Sophos;i="4.84,268,1355097600"; d="scan'208";a="152269685" Received: from rcdn-core2-2.cisco.com ([173.37.113.189]) by rcdn-iport-5.cisco.com with ESMTP; 12 Dec 2012 20:10:54 +0000 Received: from xhc-aln-x04.cisco.com (xhc-aln-x04.cisco.com [173.36.12.78]) by rcdn-core2-2.cisco.com (8.14.5/8.14.5) with ESMTP id qBCKAs09029605 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Wed, 12 Dec 2012 20:10:54 GMT Received: from xmb-rcd-x04.cisco.com ([169.254.8.29]) by xhc-aln-x04.cisco.com ([173.36.12.78]) with mapi id 14.02.0318.004; Wed, 12 Dec 2012 14:10:54 -0600 From: "Scott Fluhrer (sfluhrer)" To: Andrey Jivsov Thread-Topic: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) Thread-Index: AQHN2HN1n0mZdiOeF06/Mfx4iUhUp5gVYE2ggACJ5oD//6zskA== Date: Wed, 12 Dec 2012 20:10:53 +0000 Message-ID: References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <50C8D4D1.8050805@brainhub.org> In-Reply-To: <50C8D4D1.8050805@brainhub.org> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.32.244.86] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailman-Approved-At: Mon, 17 Dec 2012 08:11:33 -0800 Cc: "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [saag] [Cfrg] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 20:10:56 -0000 > -----Original Message----- > From: Andrey Jivsov [mailto:openpgp@brainhub.org] > Sent: Wednesday, December 12, 2012 2:03 PM > To: Scott Fluhrer (sfluhrer) > Cc: Rene Struik; cfrg@irtf.org; saag@ietf.org; Peter Gutmann > Subject: Re: [Cfrg] [saag] A proposal for compact representation of an > elliptic curve point (ECC point compression) >=20 > I have the same comment as Scott, but I am not sure exactly what Rene > means. >=20 > I will assume that Rene says that because there are two y for each x, one= can > calculate the corresponding y or p-y and choose one at random. >=20 > The format I proposed indeed fits very well with the feature of the ECDH- > based protocol that Scott refers to (which covers ECC encryption and key > agreement). As the draft shows, one simply drops the y coordinate to obta= in > the compact representation, while there are no extra steps for ECDH key > generation (because ECDH keys are not sensitive to maintaining the "right= " > y). >=20 > The extra key generation step is only needed for ECDSA keys. Actually, as Rene pointed out to me privately, it isn't much more for ECDSA= , at least with the standard algorithm. The ECDSA verification is a check whether r =3D (uG + vQ)_x, where Q is the= public key. If you are given only the x coordinate of Q, what you do is t= o pick a corresponding y coordinate (so you get a point S where either S=3D= Q or S=3D-Q, where Q is the original public key), and check if one of these= two holds: r =3D (uG + vS)_x r =3D (uG - vS)_x If either does, the signature verifies. This adds the cost of a single poi= nt addition (and the cost of generating the y coordinate of S); fairly smal= l. >=20 > On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote: > > > > > >> -----Original Message----- > >> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf > >> Of Rene Struik > >> Sent: Wednesday, December 12, 2012 9:17 AM > >> To: Andrey Jivsov > >> Cc: cfrg@irtf.org; saag@ietf.org; Peter Gutmann > >> Subject: Re: [Cfrg] [saag] A proposal for compact representation of > >> an elliptic curve point (ECC point compression) > >> > >> Hi Andrey: > >> > >> One can already implement the x-coordinate only representation of an > >> elliptic curve point simply by converting the affine representation > >> into compressed representation and randomizing the compression "bit". > >> The reverse operation then yields the point or its inverse (which > >> have the same x-coordinate). > >> > >> To my knowledge, this does not require any changes to data formatting > >> (nor additional bytes). > > > > That randomization of the y-component works fine for ECDH (at least, if > you use only the x-component of the shared secret); however, it doesn't > work for ECDSA public keys. > > > >> > >> Best regards, > >> > >> Rene > >> > >> On 12/11/2012 6:37 PM, Andrey Jivsov wrote: > >>> On 12/11/2012 03:15 PM, Peter Gutmann wrote: > >>>> Andrey Jivsov writes: > >>>> > >>>>> I thought that it would be useful for the Internet community to > >>>>> have an IETF document that describes how to encode an ECC point. > >>>> > >>>> Maybe I'm missing something here, but wouldn't this just consist of: > >>>> > >>>> -- Snip -- > >>>> > >>>> See [1]. > >>>> > >>>> [1] X9.62-2005, "Public Key Cryptography for the Financial Services > >>>> Industry: > >>>> The Elliptic Curve Digital Signature Standard (ECDSA)", November, > 2005. > >>>> > >>>> -- Snip -- > >>>> > >>>> That's what every existing RFC that uses ECC seems to be using. > >>>> > >>>> Peter. > >>>> > >>> > >>> Hello Peter. > >>> > >>> "X9.62-2005" in the search engine lends me on a page that asks for > >>> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] > >>> is more popular as a reference (assuming they are identical > >>> regarding the point compression method). > >>> > >>> I claim that what I submitted is better in many respects than SEC1. > >>> > >>> Let me expand on one of the benefits not covered in the spec. It's > >>> very likely that an employee of a commercial company thinking about > >>> using [SEC1] compression with any ECC method would get an order from > >>> the legal department to stay away from compression. The fact that > >>> somebody on the Internet posted something to the contrary has little > >>> weight for them. My contribution is an attempt towards a compact > >>> representation that is actually usable in practice. It's the most > >>> direct extension to the 1985 idea by [Miller] (see my document for > >>> details). > >>> > >>> Thank you. > >>> > >>> _______________________________________________ > >>> saag mailing list > >>> saag@ietf.org > >>> https://www.ietf.org/mailman/listinfo/saag > >> > >> > >> -- > >> email: rstruik.ext@gmail.com | Skype: rstruik > >> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 > >> > >> _______________________________________________ > >> Cfrg mailing list > >> Cfrg@irtf.org > >> http://www.irtf.org/mailman/listinfo/cfrg From wwhyte@securityinnovation.com Wed Dec 12 15:02:20 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8C5011F0CC5 for ; Wed, 12 Dec 2012 15:02:20 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.377 X-Spam-Level: X-Spam-Status: No, score=-2.377 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, J_CHICKENPOX_22=0.6, RCVD_IN_DNSWL_LOW=-1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id GVLdXp+Fodmq for ; Wed, 12 Dec 2012 15:02:19 -0800 (PST) Received: from mail-lb0-f172.google.com (mail-lb0-f172.google.com [209.85.217.172]) by ietfa.amsl.com (Postfix) with ESMTP id 8F72C1F0CB9 for ; Wed, 12 Dec 2012 15:02:18 -0800 (PST) Received: by mail-lb0-f172.google.com with SMTP id y2so1179332lbk.31 for ; Wed, 12 Dec 2012 15:02:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=securityinnovation.com; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=u/DOqTPFBuJ2/V+WQ0VKcd7C5OiDuO0eWLaeZIfJRxk=; b=Swg/c4MGqouINWj9YsOgxIMxZ+7hWyxr7xTef4xP9jTSEoRXx+hHdrologAM0wWTSn 6KWesPghvtkdZ3n5ffgtYwK34tDFyx/ukKuskORs71MCrBneL2TSoWVO9TY4LI4mgyVT fG3tEIFPBAiSzeQtZM8B5r3N1kPpgjZxDXp5c= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding:x-gm-message-state; bh=u/DOqTPFBuJ2/V+WQ0VKcd7C5OiDuO0eWLaeZIfJRxk=; b=Ivm9e512/0aY7prOvVXvFQuPN+eAfiKDZIjQ581ImGJVZ+tEu8gbJkJ2qqC8HAc4Lh WqDZlNZuRKllvKTzYHYoF196+JUV9qIh/OwNkgjp9AGSj1lz4WfmmzqOdYxTKL+Lu5So qui0fNYzRa96t1ABpjkVT0tveKEjAnEjv41cxjtKvwZwPoWZInmMHh/owbRT85I8N+HN mId7mGAOEHR9u98ut7tSR7RxfcjbY9fnl1t2eRWCUMTFWWgI9fyPKv7B4Dg5sh6UviB8 8eA+y9C54DH7N5YQ0XK4DI++5uz+2IrKetY+DI6u3toTgHxXNcADeEBP4/c+X7bZ3XV9 daog== MIME-Version: 1.0 Received: by 10.112.50.138 with SMTP id c10mr49195lbo.113.1355353337773; Wed, 12 Dec 2012 15:02:17 -0800 (PST) Received: by 10.114.28.228 with HTTP; Wed, 12 Dec 2012 15:02:17 -0800 (PST) In-Reply-To: References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <50C8D4D1.8050805@brainhub.org> Date: Wed, 12 Dec 2012 18:02:17 -0500 Message-ID: From: William Whyte To: "Scott Fluhrer (sfluhrer)" Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Gm-Message-State: ALoCoQlwBg6XBsNKsgmQrbpaK6SbIV/0ECElkEA38tnjJraq5N8ol830IPi0GWKAqJ9l1zxDaoDr X-Mailman-Approved-At: Mon, 17 Dec 2012 08:11:33 -0800 Cc: "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [saag] [Cfrg] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 23:02:20 -0000 Hi Scott, > Actually, as Rene pointed out to me privately, it isn't much more for ECD= SA, at least with the standard algorithm. > > The ECDSA verification is a check whether r =3D (uG + vQ)_x, where Q is t= he public key. If you are given only the x coordinate of Q, what you do is= to pick a corresponding y coordinate (so you get a point S where either S= =3DQ or S=3D-Q, where Q is the original public key), and check if one of th= ese two holds: > > r =3D (uG + vS)_x > r =3D (uG - vS)_x > > If either does, the signature verifies. This adds the cost of a single p= oint addition (and the cost of generating the y coordinate of S); fairly sm= all. The problem here is that the standard speedup for ECDSA doesn't calculate uG and vS independently, but calculates uG+vS as a single operation. This takes much less time than the separate operations -- I estimate about 69% of the time for openssl using the NIST p256 curve. So the cost of doing verification without knowing Q_y is actually a factor of close to 1.44, since you have to do the separate calculations instead of the combined one. Generating the y coordinate isn't necessarily a small cost; it can also be pretty expensive since it involves taking a square root mod a prime. Obviously this cost also applies if you use any form of y-coordinate compression as well as if you omit the y-coordinate, so it's not necessarily a cost delta depending on what you're comparing with. I've seen implementations in which decompression added 12% to the running time for verify with NIST p256 and 23% to the running time for verify with NIST p224; with openssl, last time I checked two years ago, decompression added 12% to the running time for verify with NIST p256 and 180% to the running time with NIST p224 because the decompression algorithm at the time was, er, not optimized. (We actually implemented an improved decompression algorithm for openssl that brings the overhead back down to around 23%, but haven't had time to release it back to the main source tree yet -- it's possible that the openssl team have already improved it themselves). Cheers, William From vf@unity.net Thu Dec 13 03:21:26 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8C3FC21F8945; Thu, 13 Dec 2012 03:21:25 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id hP6wexnLH3Pm; Thu, 13 Dec 2012 03:21:25 -0800 (PST) Received: from vc.unity.net (140-242.trifle.net [195.24.140.242]) by ietfa.amsl.com (Postfix) with ESMTP id D6C7021F8A4D; Thu, 13 Dec 2012 03:21:24 -0800 (PST) Received: from vf by vc.unity.net with local (Exim 4.72) (envelope-from ) id 1Tj6qn-0002ac-V3; Thu, 13 Dec 2012 13:21:13 +0200 Date: Thu, 13 Dec 2012 13:21:13 +0200 From: Vadym Fedyukovych To: "Scott Fluhrer (sfluhrer)" Message-ID: <20121213112113.GJ17472@unity.net> References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <50C8D4D1.8050805@brainhub.org> MIME-Version: 1.0 Content-Type: text/plain; charset=koi8-r Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) X-Mailman-Approved-At: Mon, 17 Dec 2012 08:11:33 -0800 Cc: "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [saag] [Cfrg] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 13 Dec 2012 11:21:27 -0000 On Wed, Dec 12, 2012 at 08:10:53PM +0000, Scott Fluhrer (sfluhrer) wrote: > > > -----Original Message----- > > From: Andrey Jivsov [mailto:openpgp@brainhub.org] > > Sent: Wednesday, December 12, 2012 2:03 PM > > > [...] > > I will assume that Rene says that because there are two y for each x, one can > > calculate the corresponding y or p-y and choose one at random. > [...] > Actually, as Rene pointed out to me privately, it isn't much more for ECDSA, at least with the standard algorithm. > > The ECDSA verification is a check whether r = (uG + vQ)_x, where Q is the public key. If you are given only the x coordinate of Q, what you do is to pick a corresponding y coordinate (so you get a point S where either S=Q or S=-Q, where Q is the original public key), and check if one of these two holds: > > r = (uG + vS)_x > r = (uG - vS)_x > > If either does, the signature verifies. This adds the cost of a single point addition (and the cost of generating the y coordinate of S); fairly small. This looks like a non-trivial change of threat model to me. There may be two different messages signed with such a signature. To be practical, one would consider generating (well, calculating) a key to fit any two pre-selected messages later. "IOY amount/10" could be an example for a nice article in game theory. > > On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote: > > > > > > > > >> -----Original Message----- > > >> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf > > >> Of Rene Struik > > >> Sent: Wednesday, December 12, 2012 9:17 AM > [...] From openpgp@brainhub.org Mon Dec 17 13:33:25 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3368421F85CE for ; Mon, 17 Dec 2012 13:33:25 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 0.233 X-Spam-Level: X-Spam-Status: No, score=0.233 tagged_above=-999 required=5 tests=[AWL=0.070, BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_NET=0.611, J_CHICKENPOX_62=0.6, RDNS_NONE=0.1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id hU9MpXZ6qhll for ; Mon, 17 Dec 2012 13:33:24 -0800 (PST) Received: from qmta05.emeryville.ca.mail.comcast.net (qmta05.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:48]) by ietfa.amsl.com (Postfix) with ESMTP id 752CD21F85C0 for ; Mon, 17 Dec 2012 13:33:24 -0800 (PST) Received: from omta05.emeryville.ca.mail.comcast.net ([76.96.30.43]) by qmta05.emeryville.ca.mail.comcast.net with comcast id cl9o1k0040vp7WLA5lZQy8; Mon, 17 Dec 2012 21:33:24 +0000 Received: from [127.0.0.1] ([69.181.162.123]) by omta05.emeryville.ca.mail.comcast.net with comcast id clZN1k00M2g33ZR8RlZPow; Mon, 17 Dec 2012 21:33:24 +0000 Message-ID: <50CF8F52.5090508@brainhub.org> Date: Mon, 17 Dec 2012 13:32:02 -0800 From: Andrey Jivsov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120911 Thunderbird/15.0.1 MIME-Version: 1.0 To: "Scott Fluhrer (sfluhrer)" References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <50C8D4D1.8050805@brainhub.org> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1355780004; bh=/B6UBOx78j5v146/9XEM/X2KLcCKGfJQXtROuXFQo9c=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=Zgi6UVa1vC1WRNVrssn2QkxMGwrQsUtDB0z1094EO5wAqKfqU3FCWLNT8DvU7iCcg eWbywp+DtGQx/sf61WfJdc+dRQxvKc/XF4G6zwUx5qbTICAISqBKVu4DmhJ1G9xjBj QoIGXMyfgZcKqMOj3qlwrNnWx4OYfN0isLJtXnThtC+Tg/JnTUijmGkB35VjWcI3xr vWD0pAutZAJGhFZl0TcibiyhGHwpD5EVb2P9cZDzhSx4QK6Gn5+bw6yB8qeW0lLQlc KGH5Mya+06MKje/3rQD0byNz4UWZZWh/SKelHTNHDKeHVAM5RY97ElZLaD98XqY1SV KsaNi9KKYoGLg== Cc: "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [saag] [Cfrg] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 17 Dec 2012 21:33:25 -0000 On 12/12/2012 12:10 PM, Scott Fluhrer (sfluhrer) wrote: > > >> -----Original Message----- >> From: Andrey Jivsov [mailto:openpgp@brainhub.org] >> Sent: Wednesday, December 12, 2012 2:03 PM >> To: Scott Fluhrer (sfluhrer) >> Cc: Rene Struik; cfrg@irtf.org; saag@ietf.org; Peter Gutmann >> Subject: Re: [Cfrg] [saag] A proposal for compact representation of an >> elliptic curve point (ECC point compression) >> >> I have the same comment as Scott, but I am not sure exactly what Rene >> means. >> >> I will assume that Rene says that because there are two y for each x, one can >> calculate the corresponding y or p-y and choose one at random. >> >> The format I proposed indeed fits very well with the feature of the ECDH- >> based protocol that Scott refers to (which covers ECC encryption and key >> agreement). As the draft shows, one simply drops the y coordinate to obtain >> the compact representation, while there are no extra steps for ECDH key >> generation (because ECDH keys are not sensitive to maintaining the "right" >> y). >> >> The extra key generation step is only needed for ECDSA keys. > > Actually, as Rene pointed out to me privately, it isn't much more for ECDSA, at least with the standard algorithm. > > The ECDSA verification is a check whether r = (uG + vQ)_x, where Q is the public key. If you are given only the x coordinate of Q, what you do is to pick a corresponding y coordinate (so you get a point S where either S=Q or S=-Q, where Q is the original public key), and check if one of these two holds: > > r = (uG + vS)_x > r = (uG - vS)_x > > If either does, the signature verifies. This adds the cost of a single point addition (and the cost of generating the y coordinate of S); fairly small. ... As was pointed out to me privately, two public keys Q and -Q will both verify the same signature. Let me explore this point further. One interesting side effect of this modification to ECDSA is that it's now possible to have two X.509 certificates with different identities that will both verify the same signed document. The subjectKeyIdentifier (SKI) will be different (so that keys will appear different at cryptographic material level too) It's my understanding that SMIME/CMS doesn't include identity of the signer into the signed attributes (which are the message digest, date of signing, etc, but not the issuer+SN or SKI). So, it will be then a "feature" of the new ECDSA that each principal can have up to two digital identities that the protocol cannot distinguish from at the cryptographic level. Speaking in terms of X.509 format, everybody is advised to get a pair of X.509 certificates issued from the legitimate CA (or CAs): the main one and the other one for the rainy day to claim limited repudiation. A principal will be able to show to court that by manually modifying the signed message the document in question will appear to be signed by another digital identity. X.509 certificate certification looks fine from this point. This leads us to the thought that the canonization of the point is a good thing, and my proposal or SEC1 don't leave that 1 bit of uncertainty. From housley@vigilsec.com Thu Dec 20 11:16:10 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 300EF21F8A56 for ; Thu, 20 Dec 2012 11:16:10 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -102.536 X-Spam-Level: X-Spam-Status: No, score=-102.536 tagged_above=-999 required=5 tests=[AWL=0.063, BAYES_00=-2.599, USER_IN_WHITELIST=-100] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id j-x1eakeJ5dP for ; Thu, 20 Dec 2012 11:16:08 -0800 (PST) Received: from odin.smetech.net (mail.smetech.net [208.254.26.82]) by ietfa.amsl.com (Postfix) with ESMTP id 499A721F8A51 for ; Thu, 20 Dec 2012 11:16:08 -0800 (PST) Received: from localhost (unknown [208.254.26.81]) by odin.smetech.net (Postfix) with ESMTP id 28BA89A400D for ; Thu, 20 Dec 2012 14:16:09 -0500 (EST) X-Virus-Scanned: amavisd-new at smetech.net Received: from odin.smetech.net ([208.254.26.82]) by localhost (ronin.smetech.net [208.254.26.81]) (amavisd-new, port 10024) with ESMTP id fORGlIQpKLf2 for ; Thu, 20 Dec 2012 14:16:05 -0500 (EST) Received: from [192.168.2.100] (pool-96-255-37-162.washdc.fios.verizon.net [96.255.37.162]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by odin.smetech.net (Postfix) with ESMTP id 147B09A400B for ; Thu, 20 Dec 2012 14:16:07 -0500 (EST) Content-Type: text/plain; charset=windows-1252 Mime-Version: 1.0 (Apple Message framework v1085) From: Russ Housley In-Reply-To: <7E264907-5D8F-49BF-88D2-A4E8F2AC56D1@oasis-open.org> Date: Thu, 20 Dec 2012 14:16:04 -0500 Content-Transfer-Encoding: quoted-printable Message-Id: <8D1CD4C4-90D4-4AB0-A79A-243A02D7068E@vigilsec.com> References: <7E264907-5D8F-49BF-88D2-A4E8F2AC56D1@oasis-open.org> To: IETF SAAG X-Mailer: Apple Mail (2.1085) Subject: [saag] Proposed OASIS Charter for PKCS 11 TC X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 20 Dec 2012 19:16:10 -0000 SAAG mail list participants may be interested ... -------- Original Message -------- Subject: Proposed Charter for PKCS 11 TC Date: Thu, 20 Dec 2012 10:38:42 -0500 From: Chet Ensign A draft TC charter has been submitted to establish the OASIS PKCS 11 = Technical Committee. In accordance with the OASIS TC Process Policy = section 2.2: = (https://www.oasis-open.org/policies-guidelines/tc-process#formation) = the proposed charter is hereby submitted for comment. The comment period = shall remain open until 11:59 pm ET on 03 January 2013. OASIS maintains a mailing list for the purpose of submitting comments on = proposed charters. Any OASIS member may post to this list by sending = email to: oasis-charter-discuss@lists.oasis-open.org. All messages will = be publicly archived at: = http://lists.oasis-open.org/archives/oasis-charter-discuss/. Members who = wish to receive emails must join the group by selecting "join group" on = the group home page: = http://www.oasis-open.org/apps/org/workgroup/oasis-charter-discuss/. = Employees of organizational members do not require primary = representative approval to subscribe to the oasis-charter-discuss = e-mail. A telephone conference will be held among the Convener, the OASIS TC = Administrator, and those proposers who wish to attend within four days = of the close of the comment period. The announcement and call-in = information will be noted on the OASIS Charter Discuss Group Calendar. We encourage member comment and ask that you note the name of the = proposed TC (PKCS 11) in the subject line of your email message. --- TC Charter (1) TC Charter (1)(a) Name of the TC OASIS PKCS 11 Technical Committee (1)(b) Statement of Purpose The purpose of the PKCS 11 Technical Committee is the on-going = enhancement and maintenance of the PKCS #11 standard, widely used across = the industry as a core specification for cryptographic services. The = PKCS #11 standard, originally developed under the leadership of RSA = Laboratories, specifies an API, called Cryptoki, for devices which hold = cryptographic information and perform cryptographic functions. The API = follows a simple object-based approach, addressing the goals of = technology independence (any kind of device) and resource sharing = (multiple applications accessing multiple devices), presenting to = applications a common, logical view of the device called a cryptographic = token. (1)(c) Scope of Work The committee will address requirements for enhancements to and = maintenance of the PKCS #11 standard as an API for devices that may hold = cryptographic information and may perform cryptographic functions. These = requirements include such areas as new mechanisms for instrumentation of = the PKCS #11 application programming interface. Other areas of in-scope = activity for the committee include the specification of new PKCS #11 = functionality in support of integration with other standards, = particularly OASIS Key Management Interoperability Protocol (KMIP). The = committee will also engage in activities that support effective and = interoperable implementation of PKCS #11, including such activities as = developing guidance on the use of PKCS #11, supporting interoperability = testing and coordination of reference implementations. (1)(d) List of Deliverables The initial goal of the OASIS PKCS 11 Technical Committee is to finalize = the current draft work on V2.30 of the PKCS #11 Specification, based on = the contributions listed in (2)(h)", within 12 to 18 months of the first = meeting. Inclusion of additional mechanisms and other enhancements will = also be considered for this release, to the extent that they can be = accommodated within a reasonable time-frame. The deliverable for this = initial work is the following: - PKCS #11 Specification. This provides the normative expression of the = application programming interface, including objects, attributes, = operations, mechanisms and other elements. The specification may be = created as a single document or (as is the case with the current draft) = or in multiple parts to facilitate ease-of-use of the standard. The PKCS #11 Specification will be the primary on-going deliverable of = the TC. However, as part of its continuing work, the PKCS 11 TC will = also support activities to encourage adoption of the PKCS #11 standard. = These activities and related deliverables are anticipated to include: - Development of PKCS #11 Test Cases documentation, describing test = scenarios and implementation details for purposes of validating PKCS #11 = functionality and verifying interoperability across PKCS #11 = implementations. - Development of PKCS #11 Profiles documentation, containing profiles = that enable PKCS #11 implementations to claim conformance to specific = sets of PKCS #11 functionality. - Development of PKCS #11 Usage Guide documentation, providing guidance = on the use of PKCS #11 functionality - Development of PKCS #11 Errata documentation, if and as needed. - Definition of integration mechanism for use of PKCS #11 with other = standards, such as OASIS KMIP. - Coordination of functional testing validating PKCS #11 functionality - Coordination of interoperability testing across PKCS #11 = implementations as interoperability sessions to test effectiveness of = the specification - Coordination of efforts to develop reference implementations of PKCS = #11 (1)(e) IPR Mode The PKCS 11 TC is anticipated to operate under RF on RAND mode of the = OASIS IPR Policy = [https://www.oasis-open.org/policies-guidelines/ipr#s10.2.2]. (1)(f) Anticipated Audience or Users PKCS #11 is intended for architects, designers and implementers of = providers and consumers of cryptographic services. (1)(g) Language Work group business and proceedings will be conducted in English. (2) Non-Normative Information Regarding TC (2)(a) Similar or Applicable Work PKCS #11 is one of the family of standards called Public-Key = Cryptography Standards (PKCS), originally developed under the leadership = of and published by RSA Laboratories. Minimal further development is = anticipated at this time for the other standards within the PKCS family, = some of which remain under RSA leadership and others of which have been = transferred to IETF. The PKCS 11 Technical Committee will maintain TC = Liaison relationships with both RSA and IETF with respect to the other = standards in the PKCS family, to the extent that there is relevant = activity in those organizations regarding these other standards. Activity in support of cryptographic standardization is also going on in = a number of other venues, including other OASIS committees such the Key = Management Interoperability Protocol (KMIP) Technical Committee, other = standards organizations such as IETF KeyProv, and under vendor = sponsorship such as the Microsoft MS-CAPI standard. The PKCS 11 = Technical Committee will seek to align its technical activities and = deliverables with these other standardization initiatives in order to = support harmonized vocabularies, avoid unnecessary duplication of = effort, and promote interoperability and integration with respect to = cryptographic objects and operations. Where deemed appropriate, the = OASIS PKCS 11 Technical Committee will establish formal TC Liaison = relationships with other organizations working on related standards. (2)(b) Date, Time, and Location of First Meeting The first meeting will be held in person on Monday, 4 March 2013, at = 9:00 AM Pacific Standard Time. It will be hosted by EMC/RSA in the San = Francisco area. Conference calling facilities will be provided for those = who cannot attend in person. (2)(c) Ongoing Meeting Plans and Sponsors The TC expects to meet bi-weekly by conference call. Sponsorship is to = be determined at the first meeting. (2)(d) Proposers of the TC 1. Tim Hudson, tjh@cryptsoft.com, Cryptsoft 2. Tony Cox, tjc@cryptsoft.com, Cryptsoft 3. Robert W. Griffin, robert.griffin@rsa.com, EMC. 4. Valerie Fenwick, valerie.fenwick@oracle.com, Oracle. 5. Michael Stevens, ms@quintessencelabs.com, Quintessence Labs 6. Ajai Puri, ajai.puri@safenet-inc.com, SafeNet. 7. Robert Lockhart, robert.lockhart@thales-esecurity.com, Thales. 8. Peter Gutmann, pgut001@cs.auckland.ac.nz , University of = Auckland (2)(e) Statements of Support 1. Tim Hudson, tjh@cryptsoft.com, Cryptsoft. "As Cryptsoft=92s primary = representative to OASIS, I approve the PKCS 11 TC charter and endorse = all Cryptsoft proposers listed in (2)(d)." 2. Robert Philpott, robert.philpott@rsa.com, EMC. "As EMC=92s primary = representative to OASIS, I approve the PKCS 11 TC charter and endorse = all EMC proposers listed in (2)(d)." 3. Martin Chapman, martin.chapman@oracle.com, Oracle. "As Oracle=92s = primary representative to OASIS, I approve the PKCS 11 TC charter and = endorse all Oracle proposers listed in (2)(d)." 4. John Leiseboer, jl@quintessencelabs.com, Quintessence Labs. "As = Quintessence Labs=92s primary representative to OASIS, I approve the = PKCS 11 TC charter and endorse all Quintessence Labs proposers listed in = (2)(d)." 5. Bill Becker, bill.becker@safenet-inc.com, SafeNet. "As SafeNet=92s = primary representative to OASIS, I approve the PKCS 11 TC charter and = endorse all SafeNet proposers listed in (2)(d)." 6. Darren Learmonth, darren.learmonth@thales-esecurity.com, Thales. "As = Thales=92 primary representative to OASIS, I approve the PKCS 11 TC = charter and endorse all Thales proposers listed in (2)(d)." (2)(f) TC Convener Robert Griffin, robert.griffin@rsa.com, EMC will be the convener. (2)(g) Member Section Affiliation The PKCS 11 TC will request affiliation with the IDtrust Member Section. (2)(h) Initial Contributions EMC will contribute =93PKCS #11 Specification V2.30)" consisting of the = following four documents: - PKCS #11 V2.30 Specification Front Matter [1] - PKCS #11 V2.30 Core Specification [2] - PKCS #11 V2.30 Mechanisms Part 1 [3] - PKCS #11 V2.30 Mechanisms Part 2 [4] (2)(i) FAQ Document An initial =93PKCS 11 TC FAQ=94 document is under development. (2)(j) Work Product Titles The PKCS 11 Technical Committee anticipates four work products with the = following draft titles: PKCS #11 Specification (this may consist of multiple documents, each = comprising part of the complete specification) PKCS #11 Test Cases PKCS #11 Profiles PKCS #11 Usage Guide =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D References =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D [1] PKCS #11 Version 2.30: Cryptographic Token Interface Standard: Front = Matter (draft), April 2009. ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-11/v2-30/pkcs-11v2-30-d1.pdf [2] PKCS #11 Version 2.30: Cryptographic Token Interface Standard: Core = Specification (draft), April 2009. ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-11/v2-30/pkcs-11v2-30b-d6.pdf [3] PKCS #11 Version 2.30: Cryptographic Token Interface Standard: = Mechanisms Part 1 (draft), April 2009. ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-11/v2-30/pkcs-11v2-30m1-d7.pdf [4] PKCS #11 Version 2.30: Cryptographic Token Interface Standard: = Mechanisms Part 2 (draft), April 2009. ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-11/v2-30/pkcs-11v2-30m2-d3.pdf /chet ---------------- Chet Ensign Director of Standards Development and TC Administration OASIS: Advancing open standards for the information society http://www.oasis-open.org From barryleiba@gmail.com Mon Dec 31 15:44:07 2012 Return-Path: X-Original-To: saag@ietfa.amsl.com Delivered-To: saag@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 30BE521F86C2; Mon, 31 Dec 2012 15:44:07 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -101.718 X-Spam-Level: X-Spam-Status: No, score=-101.718 tagged_above=-999 required=5 tests=[AWL=-1.341, BAYES_50=0.001, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_LOW=-1, USER_IN_WHITELIST=-100] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id YjyLZXZbokNI; Mon, 31 Dec 2012 15:44:05 -0800 (PST) Received: from mail-vb0-f50.google.com (mail-vb0-f50.google.com [209.85.212.50]) by ietfa.amsl.com (Postfix) with ESMTP id E1EC221F86C0; Mon, 31 Dec 2012 15:44:04 -0800 (PST) Received: by mail-vb0-f50.google.com with SMTP id ft2so1547135vbb.37 for ; Mon, 31 Dec 2012 15:44:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:date:x-google-sender-auth:message-id:subject :from:to:content-type; bh=oZnyB9U8vBN86R/VWbdpC+cFigNYBR73+mHzD4ZKHIQ=; b=X8c4tGX+NIMAhXtgoHTX4mY88D8vfcYNOsVTTIWpjvdqWGL51tr9LqNDVrUTguRrXl sfsjARQciEyvoPQoVU/JfuuwF/ikBsMgTNRQm+eM96PYhqUUeLs9l3l7VI9MBhQGV0Sw UUmeN21NotBAfP3e3iAoQ6mKJ2ZNT+vionBrEOQlIFC/9zfBWgbEqRkWZR19TToaG92B t0gq03zEolUPCi9auhHdXJufi6dbFnAn6ty3pvwFahxvciZXbeiuid6LKfTbqyK6pJkP XBIm8q7iWguNYCg3WKpTojsCgmXFFqTZc0JJyRgeKUjkGRVe/0GsFTmBov+xQfQlTpb2 TFRA== MIME-Version: 1.0 Received: by 10.220.238.148 with SMTP id ks20mr66390981vcb.5.1356997443865; Mon, 31 Dec 2012 15:44:03 -0800 (PST) Sender: barryleiba@gmail.com Received: by 10.58.28.231 with HTTP; Mon, 31 Dec 2012 15:44:03 -0800 (PST) Date: Mon, 31 Dec 2012 18:44:03 -0500 X-Google-Sender-Auth: GWxTfeXmTb1QtqC_0ptMeONikYw Message-ID: From: Barry Leiba To: "saag@ietf.org" , ietf-privacy@ietf.org, Apps Discuss Content-Type: text/plain; charset=ISO-8859-1 Subject: [saag] CfP for Second International Workshop on Privacy and Security in Online Social Media (PSOSM) X-BeenThere: saag@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Security Area Advisory Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 31 Dec 2012 23:44:07 -0000 Readers of these lists may be interested in this workshop, which is co-located with the next WWW Conference in Rio de Janeiro this May. I know both of the workshop chairs, and can recommend participation. Please don't respond here, but contact the workshop committee directly. Barry --------------------------------------------------------------------------------- CALL FOR PAPERS Second International Workshop on Privacy and Security in Online Social Media (PSOSM) http://precog.iiitd.edu.in/events/psosm2013 Co-located with 22nd International World Wide Web Conference Rio, Brazil May 13 - 17, 2013 With increase in the usage of the Internet, there has been an exponential increase in the use of online social media on the Internet. Websites like Facebook, YouTube, Orkut, Twitter, Flickr, Google+, FourSquare, Pinterest, and the likes have changed the way the Internet is being used. However, widely used, there is a lack of understanding of privacy and security issues on online social media. Privacy and security of online social media need to be investigated, studied and characterized from various perspectives (computational, cultural, psychological, etc.). It is critical to detect security treats and defend privacy through real-time and scalable systems. Since there are no logical boundaries for the social media, it is important to study the problem from an international perspective too. The main goals of the workshop are: To create a platform to discuss latest and upcoming issues, trends, and cutting-edge research approaches in security and privacy in online social media / complex networked systems; (2) To bring researchers who are working separately on security and privacy, and online social media, to discuss the problems that overlap and bring these two areas together. Topics / themes include, but not limited to the following: - Information privacy disclosure, revelation and its effects in OSM and online social networks - Collateral damage due to information leakage (e.g. through photo tagging) on OSM - Privacy issues related to location based services on OSM - Effective and usable privacy setting and policies on OSM - Anonymization of social network dataset - Identifying and preventing social spam (including phishing and frauds) campaigns - Tracking social footprint / identities across different social network - Detection and characterization of spam, phishing, frauds, hate crime, abuse, extremism via online social media - Cyber-bullying, abuse and harassment detection, and prevention strategies - Identifying and curbing malware, phishing, and botnets on OSM - Filtering of pornography, viruses, and human trafficking on OSM - Studying the social and economic impact of security and privacy issues on OSM - User behavior towards change in privacy features in OSM - Usability (including design flaws) of secure systems on online social media - Data modeling of human behavior in context of security and privacy threats - Privacy and security in social gaming applications - Trust systems based on social networks - Legal and ethical issues for researchers studying security and privacy on OSM - Information credibility on OSM - Security and Privacy issues in new entrants in OSM (e.g. Google Plus) - Effect of OSM on conventional crime (robberies and theft) - Means to maintain different legitimate identities on the same OSM service - Access control, rights management, and security of social content - Privacy-enhancing technologies, including anonymity, pseudonymity and identity management, specifically for the web - Identifying fraudulent entities in online social networks - Problems due to unification of different identities of the same persona on different social media services - Using social media (e.g. Twitter) as sensors for decision making at the organization level (i.e. detecting outbreaks) Important dates Abstract submission: February 22nd, 2013 Manuscripts due: February 25th, 2013 Notification of acceptance: March 13th, 2013 Final revised manuscript: April 1st, 2013 Workshop: May 14, 2013 (Full day) ** Best paper award will be given to the most outstanding paper submitted to the workshop.** Workshop chairs - Prof. Ponnurangam Kumaraguru ("PK"), IIIT-Delhi, pk [at] iiitd [dot] ac [dot] in - Prof. Virgilo Almeida, UFMG For more information: http://precog.iiitd.edu.in/events/psosm2013 Follow us at @precog_iiitd and tweet about the workshop using #psosm2013 -- Regards, PSOSM 2013 Team http://precog.iiitd.edu.in/events/psosm2013/ ---------------------------------------------------------------------------------