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

David Jacobson <dmjacobson@sbcglobal.net> Fri, 28 November 2014 03:38 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 4E4F31A1A0F for <cfrg@ietfa.amsl.com>; Thu, 27 Nov 2014 19:38:27 -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 P0KH36YXPrKp for <cfrg@ietfa.amsl.com>; Thu, 27 Nov 2014 19:38:24 -0800 (PST)
Received: from nm17-vm6.access.bullet.mail.gq1.yahoo.com (nm17-vm6.access.bullet.mail.gq1.yahoo.com [216.39.63.165]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 33C0D1A1A0C for <cfrg@irtf.org>; Thu, 27 Nov 2014 19:38:24 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s1024; t=1417145903; bh=3zJaA9q2rWfp/Etl2VEMjl6mcdkT5sKD2YG26BS/pw8=; h=Date:From:To:CC:Subject:References:In-Reply-To:From:Subject; b=H6gFB0XbOSrx4UIsm06Pb+ubRo59bELVzi7963aU7YXl6e7pgym+oRnIOBJrEbJLHIokI4CxrS8LJxdZzBq7XY41HJVZ+04zLYtDaBvFeDONKOYc+TlZx0871JJ7qaDAYx3NHC5J+gfr3Yzk46CcLH5R1c0Lk8O/pLlOm8eqTcA=
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=sbcglobal.net; b=DhdFF8ibAByNDtCATE9dTqCKQTSDlcqDgsHoapfwQfY1AqqlqujVf10Md0lqjJCskMSahf750REskIW+KlUrLLDDodIXfEBK1CIJCTdHv5ytBnREYMvGs4zi/dxE8NV6nfZgPzEq6b/eX9oe4bV0brcNsCYqeDsC9SSNCWjHRCQ=;
Received: from [216.39.60.169] by nm17.access.bullet.mail.gq1.yahoo.com with NNFMP; 28 Nov 2014 03:38:23 -0000
Received: from [67.195.22.119] by tm5.access.bullet.mail.gq1.yahoo.com with NNFMP; 28 Nov 2014 03:38:23 -0000
Received: from [127.0.0.1] by smtp114.sbc.mail.gq1.yahoo.com with NNFMP; 28 Nov 2014 03:38:23 -0000
X-Yahoo-Newman-Id: 844000.60127.bm@smtp114.sbc.mail.gq1.yahoo.com
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: YOk5zDUVM1lpuGoGuNwQirSfTGdzmWVrx8lC6HeuXD0OfDB yfHurESVvpGx3Ft42gQ.SYsfhxdZpmhD1uGZZW749N0uSy9t_6FBpZ6ltlUm 8PabyCcR9tW1LFiVK9lv52IemRgDOWAOERl2JO20dIM36ZOcOcBonVxlRA4n MHAaEE_Bt4rDjaDqTUaBYnkY5uZvDP5UHe.s0c4nAPkXX19Z6Y7LWlsbTy2v WkGm3mSnZBttsSrHBEJsrZaYsZOiiQ70uHHVN9jBmD5jl.wn6JXITFZP20fb nBro3DBwui.qlewm3i22he8zdlllz8fdGMF12MxF.1BTgVMyp3gUzxoVZH8B BlKPRDLA4XNFIpcSbQZbWgj2RRHbYSvj2gTGrZ0XC8cftw25OL0UH6SRxDk. 1HbQu3bsGpZCHz.4a5xdfPkybot0Os_x50BlCHAsjPWAPZ5iChtHZ78F9YUN WNGLisk95mBcB65o8o29WQo78hAG5LIt3ZLAF2apjfpLBQe_KkKPPhb8llnd XPq_b5rMl7z1D1kDyxXCrJAlsE8daj3qTpk2k6z8TLZZDMXjFCXqO5Nbv
X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g--
Message-ID: <5477EE2E.7040601@sbcglobal.net>
Date: Thu, 27 Nov 2014 19:38:22 -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>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5D0AB7B@XMB116CNC.rim.net>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/86oY4YflRE4VV9MEMAZMSaK2cQA
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:38:27 -0000

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