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