[TLS] (offline note) Re: Safe ECC usage

Rene Struik <rstruik.ext@gmail.com> Fri, 04 October 2013 13:09 UTC

Return-Path: <rstruik.ext@gmail.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 51F6121F9DCE for <tls@ietfa.amsl.com>; Fri, 4 Oct 2013 06:09:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.599
X-Spam-Level:
X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 2rAeGdtSEKUM for <tls@ietfa.amsl.com>; Fri, 4 Oct 2013 06:09:51 -0700 (PDT)
Received: from mail-ie0-x22d.google.com (mail-ie0-x22d.google.com [IPv6:2607:f8b0:4001:c03::22d]) by ietfa.amsl.com (Postfix) with ESMTP id 7DB0221F92CD for <tls@ietf.org>; Fri, 4 Oct 2013 05:57:53 -0700 (PDT)
Received: by mail-ie0-f173.google.com with SMTP id ar20so9041027iec.32 for <tls@ietf.org>; Fri, 04 Oct 2013 05:57:53 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=WEruhJNBsodI3digq5mt2LkuZBIUSe3hq6ujfn8XmBo=; b=Wb1dVIQYMhYpDLBio5fnZdaCGYv750wQX/ooeIah3vlLFie2PyPMmIO1ehupoywzUw HpSOX4wBx5MGUZQWfZ7b/oN4K08l0kG9wZRnClO9TJugMN9GsXvwWFP7apWFuk/9jZNk jiTbS+eoZnxRLguYrXr/ToFTtMkYAcgKNgF2r3TPOMbDAAf0VXUhgT6CjQXVhF/yLH97 xp7H8zYzAH5lEJcDBkV6f9pusxuRbX1m0CKuII6Hxf3MGP6N40n7BfOPs/yZ5cmNBox8 WLTJxf64CCKl6lr5G03eTmmo79GCffGl3yTVFFAeXkh5dM/yJ30tAISJ2u/xUkDcRCry yHcQ==
X-Received: by 10.43.60.139 with SMTP id ws11mr8581223icb.12.1380891472006; Fri, 04 Oct 2013 05:57:52 -0700 (PDT)
Received: from [192.168.1.102] (CPE0013100e2c51-CM001cea35caa6.cpe.net.cable.rogers.com. [99.230.254.17]) by mx.google.com with ESMTPSA id ri1sm6663699igc.2.1969.12.31.16.00.00 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 04 Oct 2013 05:57:51 -0700 (PDT)
Message-ID: <524EBB48.1050807@gmail.com>
Date: Fri, 04 Oct 2013 08:57:44 -0400
From: Rene Struik <rstruik.ext@gmail.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.0
MIME-Version: 1.0
To: Johannes Merkle <johannes.merkle@secunet.com>
References: <523E176F.3050304@gmail.com> <9A043F3CF02CD34C8E74AC1594475C7355674EE0@uxcn10-6.UoA.auckland.ac.nz> <20130926152757.15842.qmail@cr.yp.to> <810C31990B57ED40B2062BA10D43FBF5BDB49B@XMB116CNC.rim.net> <20130928223648.1113.qmail@cr.yp.to> <20130929025714.5578895.47771.4422@certicom.com> <20131001143511.11010.qmail@cr.yp.to> <810C31990B57ED40B2062BA10D43FBF5BDE21E@XMB116CNC.rim.net> <20131002161944.8125.qmail@cr.yp.to> <810C31990B57ED40B2062BA10D43FBF5BDE90F@XMB116CNC.rim.net> <524EB21C.6050606@secunet.com>
In-Reply-To: <524EB21C.6050606@secunet.com>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
Cc: "'tls@ietf.org'" <tls@ietf.org>
Subject: [TLS] (offline note) Re: Safe ECC usage
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 04 Oct 2013 13:09:59 -0000

[offline note]

Hi Johannes:

Thanks for your note. I presume you refer to the paper:
Side Channel Analysis - Simple Power Analysis on Fast Modular Reduction 
with ECC over Generalized Mersenne Primes (Yasuyuki Sakai, Kouichi 
Sakurai, IEICE Trans.Fund., 2006)

I am glad you refer to side channel resistance and implementation 
attacks, an often undershed aspect of security discussions (certainly in 
standardization bodies).

The paper suggests the need to weed out conditional branches, as are 
also a problem in other implementation attacks. Do you think that 
modular reductions with NISTp curves are generally hard to secure, or 
just the naive and well-documented approach? I would be curious if you 
have some data that delves on this with Brainpool curves. {As an 
example, if one uses Barrett reduction (Alg. 2.14 of Guide to ECC book), 
one has a conditional branch as well. This being said, this can be 
massaged away.}

As to patents: for basic scalar multiplication, this era should be 
nearly over, if one discards implementation attacks; if one doesn't, it 
does not seem to, though.

Best regards, Rene


On 10/4/2013 8:18 AM, Johannes Merkle wrote:
>> random prime instead of a special one incurs a computational cost.  So, I
>> think I was reasonable to infer that Brainpool was implying that special
>> fields were lacking in security.  (The implication against special values
>> may then be inferred further.)
> The primes used by NIST curves are so special that there is less room for suspicion of a backdoor in the primes than in
> the curve.
>
> Our main concern with the special primes used by NIST curves is that their special form requires more caution to harden
> your arithmetic against side-channel attacks. As a matter of fact, Sakai & Sakurai, for instance, have proposed power
> analysis attacks targeting arithmetic on Pseudo-Mersenne primes. And we don't know, if the NSA has developed improved
> side-channel attacks against ECC over such fields.
>
> As I understand, the Curve25519 papers address side-channel immunity by specifying an eligible arithmetic. No objection
> to that approach, but for the Brainpool curves we had a different one.
>
> Another aspect was that we avoid many patents by not using Pseudo-Mersenne primes.
>
>
>
> Johannes
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls


-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363