[Cfrg] invalid compressed point attack ...
Dan Brown <email@example.com> Thu, 27 November 2014 18:33 UTC
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 455F71A00B5 for <firstname.lastname@example.org>; Thu, 27 Nov 2014 10:33:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham
Received: from mail.ietf.org ([18.104.22.168]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id F6ULC4xBBYsN for <email@example.com>; Thu, 27 Nov 2014 10:33:09 -0800 (PST)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [22.214.171.124]) by ietfa.amsl.com (Postfix) with ESMTP id 19F001A0078 for <firstname.lastname@example.org>; Thu, 27 Nov 2014 10:33:08 -0800 (PST)
Received: from xct103cnc.rim.net ([10.65.161.203]) by mhs214cnc.rim.net with ESMTP/TLS/AES128-SHA; 27 Nov 2014 13:33:03 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT103CNC.rim.net ([fe80::b8:d5e:26a5:f4d6%17]) with mapi id 14.03.0174.001; Thu, 27 Nov 2014 13:33:02 -0500
From: Dan Brown <email@example.com>
To: "'firstname.lastname@example.org'" <email@example.com>
Thread-Topic: invalid compressed point attack ...
Date: Thu, 27 Nov 2014 18:33:02 +0000
Accept-Language: en-CA, en-US
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_01DB_01D00A46.AA439A50"
Cc: "firstname.lastname@example.org" <email@example.com>
Subject: [Cfrg] invalid compressed point attack ...
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:firstname.lastname@example.org?subject=unsubscribe>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:email@example.com?subject=subscribe>
X-List-Received-Date: Thu, 27 Nov 2014 18:33:15 -0000
I don't know if the compressed version of the invalid-point attack is common knowledge - or whether people would think it is unrealistic - or even whether there is some drastic error in it. If so, then sorry for stating the obvious, and just skip reading the rest of this message. >From: Watson Ladd >Sent: Wednesday, October 22, 2014 12:11 PM >Cc: firstname.lastname@example.org >Subject: Re: [TLS] Should we require compressed points >Yes, but uncompressed points are not a security concern in X509, but they are >in ECDH. >Furthermore, the cost of adding compression support is very small: it's a >square root, a check, and potentially flipping the sign. >The benefit is that invalid point attacks are much harder to carry out. Minor clarification on the "much harder" part: there is a technical attack when invalid compressed points are "used" (as defined below). I assume short Weierstrass form, but some of this may extend to other curve forms. Review: An uncompressed point (x,y) is invalid if it fails a simple check. In an invalid point attack, a user applies the secret key to an invalid point using certain addition laws, and scalar multiplication algorithms, that have an action on uncompressed points that corresponds to the equivalent action on another curve in which the invalid point has low order. 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. In fact, a user might reason that an attacker's only approach with compressed points is to try random compressed points (x,z) until they have low order. Under the heuristic that random compressed (x,z) usually have random large orders upon invalid decompression, the user might then think it is infeasible to find such points, and therefore it is safe to use invalid decompression (e.g. saving the error-handling etc.) Well, here is an invalid compressed point, which on curve NIST P192 decompresses to invalid uncompressed point of order 11: 02 2f 8c 8c 8a 7c b1 1c 06 aa a3 4b 23 4f 7d 88 cd b9 9f d7 66 4a 00 a4 d7 I presented this point and a method (using division polynomials) to find such points in the slides at PKC 2003 (which I almost completely forgot about!). This method certainly has an additional pre-computation cost, compared to the uncompressed invalid-point attack, but I don't think it's too costly. After that initial cost, the attack is pretty much the same as the one on uncompressed points. Best regards, Dan