Re: [Cfrg] invalid compressed point attack ...

Dan Brown <> Fri, 28 November 2014 12:43 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id C3B4B1A1B45 for <>; Fri, 28 Nov 2014 04:43:27 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 9KNnrkjAmTL7 for <>; Fri, 28 Nov 2014 04:43:26 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 37E701A1B38 for <>; Fri, 28 Nov 2014 04:43:25 -0800 (PST)
Received: from ([]) by with ESMTP/TLS/AES128-SHA; 28 Nov 2014 07:42:53 -0500
Received: from ([fe80::45d:f4fe:6277:5d1b]) by ([fe80::d13d:b7a2:ae5e:db06%16]) with mapi id 14.03.0174.001; Fri, 28 Nov 2014 07:42:52 -0500
From: Dan Brown <>
To: David Jacobson <>
Thread-Topic: [Cfrg] invalid compressed point attack ...
Thread-Index: AdALCNIlCnH673Mb3kC4452B702R2w==
Date: Fri, 28 Nov 2014 12:42:51 +0000
Message-ID: <>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="===============0325512528=="
MIME-Version: 1.0
Subject: Re: [Cfrg] invalid compressed point attack ...
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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; '';
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,


Cfrg mailing list‎