Re: [Cfrg] invalid compressed point attack ...
Dan Brown <dbrown@certicom.com> Fri, 28 November 2014 12:43 UTC
Return-Path: <dbrown@certicom.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C3B4B1A1B45 for <cfrg@ietfa.amsl.com>; Fri, 28 Nov 2014 04:43:27 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 9KNnrkjAmTL7 for <cfrg@ietfa.amsl.com>; Fri, 28 Nov 2014 04:43:26 -0800 (PST)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id 37E701A1B38 for <cfrg@irtf.org>; Fri, 28 Nov 2014 04:43:25 -0800 (PST)
Received: from xct105cnc.rim.net ([10.65.161.205]) by mhs214cnc.rim.net with ESMTP/TLS/AES128-SHA; 28 Nov 2014 07:42:53 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT105CNC.rim.net ([fe80::d13d:b7a2:ae5e:db06%16]) with mapi id 14.03.0174.001; Fri, 28 Nov 2014 07:42:52 -0500
From: Dan Brown <dbrown@certicom.com>
To: David Jacobson <dmjacobson@sbcglobal.net>
Thread-Topic: [Cfrg] invalid compressed point attack ...
Thread-Index: AdALCNIlCnH673Mb3kC4452B702R2w==
Date: Fri, 28 Nov 2014 12:42:51 +0000
Message-ID: <20141128124249.6660245.30846.23556@certicom.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg="SHA1"; boundary="===============0325512528=="
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/g9bfUjlWXmyXtQYleLJd5EGzhX0
Cc: IRTF CFRG <cfrg@irtf.org>
Subject: Re: [Cfrg] invalid compressed point attack ...
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 28 Nov 2014 12:43:28 -0000
By invalid decompression, I meant skipping the check on the correctness of y^2==z, which is as bad and as silly as skipping the check y^2==x^3+ax+b in an uncompressed invalid-point attack, and actually the same check. Yes, checking y^2==z stops the attack for sure. Anyway , i'm seeing the skipped check as nearly equally natural in both cases, and apparently there's even some of incentive to skip these checks called "simplicity "... Best regards, -- Dan Original Message From: David Jacobson Sent: Thursday, November 27, 2014 10:38 PM To: Dan Brown; 'watsonbladd@gmail.com' Cc: cfrg@irtf.org Subject: Re: [Cfrg] invalid compressed point attack ... On 11/27/14, 10:33 AM, Dan Brown wrote: > Definitions: A compressed point (x,z) is invalid if it is not the compression > of a valid uncompressed point. > We can technically define an invalid point attack for compression by > specifying an invalid decompression rule for invalid compressed points. > For example, in prime fields of size p = 3 mod 4, the function z |-> > z^((p+1)/4) can be used to decompress invalid compressed points, in the place > where actual square root algorithm is used to decompress a valid compressed > point. > > To me, this invalid decompression rule seems as plausible an implementation > fault as the fault of not checking for curve membership of an uncompressed > point. You seem to be saying that using y = z^((p+1)/4) where z is computed from x using the curve equation, i.e. for short Weierstrass z = x^2 + a * x + b, is not a valid way of computing a valid (x,y) on the curve. Well, of course, it is possible that z is not a quadratic residue. But if you check that y^2 == z, is it still unsafe? Thank you, --David _______________________________________________ Cfrg mailing list Cfrg@irtf.org http://www.irtf.org/mailman/listinfo/cfrg
- [Cfrg] invalid compressed point attack ... Dan Brown
- Re: [Cfrg] invalid compressed point attack ... David Jacobson
- Re: [Cfrg] invalid compressed point attack ... David Jacobson
- Re: [Cfrg] invalid compressed point attack ... Dan Brown