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

David Jacobson <dmjacobson@sbcglobal.net> Fri, 28 November 2014 03:42 UTC

Return-Path: <dmjacobson@sbcglobal.net>
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 CE52F1A1A10 for <cfrg@ietfa.amsl.com>; Thu, 27 Nov 2014 19:42:39 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_NONE=-0.0001] 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 lyFzNGxS5ktK for <cfrg@ietfa.amsl.com>; Thu, 27 Nov 2014 19:42:38 -0800 (PST)
Received: from nm4-vm8.access.bullet.mail.gq1.yahoo.com (nm4-vm8.access.bullet.mail.gq1.yahoo.com [216.39.63.212]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5FAA31A1A0C for <cfrg@irtf.org>; Thu, 27 Nov 2014 19:42:38 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s1024; t=1417146158; bh=7xK2xyzEAdZpnvvRGy1oq98PvqFsUGR7RT2f1deZ2d0=; h=Date:From:To:CC:Subject:References:In-Reply-To:From:Subject; b=h2nIQlPZMBdlbWBp1mBE4Fc2gB9nnuMy16vMPlFZmGdijWDm9qdIzXA4oSB3YuyTJs9wVQVezPHxH6PKAa7/3JYjZM2bZAMjZJZWImv/M56N8bLpopqYr2UAVVBorTsjlEjDHtUDVcEVUdMhEPuSr72hRuDXPcb9xynfM7ybMKM=
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=sbcglobal.net; b=EpmItNZbac4BObI5Z7kYMI0xA7VKmBP+/9d8bBXZwzxF3LkL028nl7MXNYxkwz57q/DigBCCHS1Q0ajvAb1PS50aIftd2rw6qO9zWHu/lYH1R2KKr/CLiTSOQZVJhO0h4vty8pmgizR30nQQfifdPqkbgj3Vq3hM+rxt4tEU2Gk=;
Received: from [216.39.60.173] by nm4.access.bullet.mail.gq1.yahoo.com with NNFMP; 28 Nov 2014 03:42:38 -0000
Received: from [67.195.23.144] by tm9.access.bullet.mail.gq1.yahoo.com with NNFMP; 28 Nov 2014 03:42:38 -0000
Received: from [127.0.0.1] by smtp116.sbc.mail.gq1.yahoo.com with NNFMP; 28 Nov 2014 03:42:38 -0000
X-Yahoo-Newman-Id: 115781.22864.bm@smtp116.sbc.mail.gq1.yahoo.com
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: oqwHipQVM1kB_BB64IvqzTJexHNA5ZsftpErdd6Xb5eLaWG iMvpe3zTM4VJZu_7ev.SEsttEGCjBPV.gi94y0o.2FCg1XHaTYkiUTU2NgIr dLNCY1V2.AqTyqfLuzfzeRwmMFiUjOAYX0ii5j0p0PseIi78gANluBBSh9Vn 2aNxfdFe831noBv8H0.tRmv5WKDL4svGDwqKFKyo6UpKXPySvC4eqAm0rshA sw2iQ1WfOz2DaZUw2.wJQauX2oBg2SsXaWySq6oXdYPjsrm94bcju0Cy.kaw uiaTHzcs8wePzf1SXzlsNHTCQs_u8Qzy5FaU4yo6vto1p7Tr.gRYiZ8oVlnq HA39aL7ekcZo.a4niFxdBUYrYTOdfMUyT.dYuWlWkPuaqh39wYlQESpG272F .ybD8kiUgFsPt6VaRFs63YSJLmSEkwtdDX79PAClFLqlFP0ZjoZW0tad_zvv 8j2Fsscoznzzh_ulq0c0MO3G5gM3kGcMLhWmfNwNrN5i1sR3miSJczBEBfU. hQ.nl0DTtwdN7WkD.iO8EdOcUSY89lCDS5xZKNZuVO9Un2CGme97XUEI-
X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g--
Message-ID: <5477EF2D.50808@sbcglobal.net>
Date: Thu, 27 Nov 2014 19:42:37 -0800
From: David Jacobson <dmjacobson@sbcglobal.net>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Dan Brown <dbrown@certicom.com>, "'watsonbladd@gmail.com'" <watsonbladd@gmail.com>
References: <810C31990B57ED40B2062BA10D43FBF5D0AB7B@XMB116CNC.rim.net> <5477EE2E.7040601@sbcglobal.net>
In-Reply-To: <5477EE2E.7040601@sbcglobal.net>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/bak-FJVY1KhuRlpHwEEW0FZH1ac
Cc: "cfrg@irtf.org" <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 03:42:40 -0000

On 11/27/14, 7:38 PM, David Jacobson wrote:
> 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
That was supposed to be z = y^3  + a * x + b.  Sorry for the typo. One 
always sees the mistake 3 seconds after clicking "send".

    --David