Re: [TLS] Twist security for brainpoolp256r1

Oleg Gryb <oleg_gryb@yahoo.com> Thu, 13 November 2014 06:37 UTC

Return-Path: <oleg_gryb@yahoo.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 565091A1B9E for <tls@ietfa.amsl.com>; Wed, 12 Nov 2014 22:37:55 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.594
X-Spam-Level:
X-Spam-Status: No, score=-2.594 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.594, SPF_PASS=-0.001] 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 h03nygY2-7M5 for <tls@ietfa.amsl.com>; Wed, 12 Nov 2014 22:37:53 -0800 (PST)
Received: from nm25-vm1.bullet.mail.bf1.yahoo.com (nm25-vm1.bullet.mail.bf1.yahoo.com [98.139.212.155]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9CE481A19F4 for <tls@ietf.org>; Wed, 12 Nov 2014 22:37:53 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1415860672; bh=PoPK0Iz94G6OYmjy0Rd0u3AmmkFngcQewlADS1jo3Qc=; h=Date:From:Reply-To:To:In-Reply-To:References:Subject:From:Subject; b=QwQUWKhCucGaFJkoZoy2oXxWaJhAfOrkp16A/8Mbv4mjFnY3ryJ8TdLC15OoLhs1PopJWwlDYTt/ZnqxF/q+gEbnJ2hDm0bMLhRyExnZltnQKjf8WaZXjZeWTJUVWvyWvElSc4ZWjX9OKzpKfXtl2aTC7CMsSaxEIuebVvRxQzulkmHl1lixjK0tEDSSoJia6BBD5AOtKXiJr1UlAEUpi9YuyLmXBq+lLlSMaT0mIvWSiyDyKklXFzyqsMKp1hSygQFocF6lKPr9BrYdMwlfOAXPKKMHgO6u7y06mddlGhu3i33hpCFtHkCkfw80KDJHnacwiBtjBMAXTjEFyEMajQ==
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s2048; d=yahoo.com; b=HvlW/0j0EXjHrw/VKARnWo3qHRgR5yDmvlXRVshJ6JpVB7du9UUYkuY1L8TN4lfFffah7qiN/y9YHY2dnZaS4RscCIuEhTXDTxYvW8mseVNj6qP+68Bm5Md+2z4nRGiepDIuIrZaHg91CtWggXApBDfRPZ92ONraBHK4BUZ24Oqm04cTTZ4QKa2xXSjVCoDi+ItrI0MkNfeOmdSKfw3tNWfR2nUXyQs0bIxagq/gUsteQ+HVWv6zNl9jejEsSk22EwTfEaoocn32cRT1Q3x3E3G+8KV0nAj+WVddHMEafBFxoYTnoKm7E37ksljbko1w8X58+ZPqjeqHSGSC2kLMGg==;
Received: from [66.196.81.174] by nm25.bullet.mail.bf1.yahoo.com with NNFMP; 13 Nov 2014 06:37:52 -0000
Received: from [98.139.215.250] by tm20.bullet.mail.bf1.yahoo.com with NNFMP; 13 Nov 2014 06:37:52 -0000
Received: from [127.0.0.1] by omp1063.mail.bf1.yahoo.com with NNFMP; 13 Nov 2014 06:37:52 -0000
X-Yahoo-Newman-Property: ymail-3
X-Yahoo-Newman-Id: 640236.47342.bm@omp1063.mail.bf1.yahoo.com
X-YMail-OSG: bi_UTTYVM1mEEehJTHQ6eNZRPPCulaw9HRhwxzs.La9_2ITJ_NIbSTBX0lqngQD Kv0dv9eT9PIPx.7yXrhVdmdyyl3YFeq5X2L4bhpaaQKvVWn_DHQFUi1tHZfrCMDOK_qbexcXk.bo IVIe9ZwkrTOxkO01kS.Nk60JYta9RJt_IJbeluYWjw6GkOXMUKdcCBPgDNgljGyPg1XL7nM9Oe_C kkSSfSgKfi6yfOqgEK0y8.4ThNeq_.daq7wjmsIRRvYf0vpwKw6p849uD11ZtrAVD5I4tmWTK6tc wq6jGMeBYjxAwT.Sg_T71DcbGBH5KeZEXpMlHfsD8wOCfsDQz2o6Dc_yK8eUbURkvRZViBakooX3 Edb59ju1rOwussvYLeMvoaqFLUCP3GzF2_l2miup8Q0at2z1ipi723UzCAQ6KL8FXIp26w5.F8m_ GG4eoLJ4g7fhbmBKvnPE0pvJCt0uvTFG.L4tiZ1ZVLW1ohnlztHs3LNxfyWibippFUfvO
Received: by 76.13.27.6; Thu, 13 Nov 2014 06:37:52 +0000
Date: Thu, 13 Nov 2014 06:35:21 +0000 (UTC)
From: Oleg Gryb <oleg_gryb@yahoo.com>
To: Johannes Merkle <johannes.merkle@secunet.com>, Oleg Gryb <oleg@gryb.info>, "tls@ietf.org" <tls@ietf.org>
Message-ID: <1821348128.254417.1415860521951.JavaMail.yahoo@jws10668.mail.bf1.yahoo.com>
In-Reply-To: <546394E9.2010208@secunet.com>
References: <546394E9.2010208@secunet.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/pqjQrQPHuN8xR1oPhbNYTWBhcBY
Subject: Re: [TLS] Twist security for brainpoolp256r1
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
Reply-To: Oleg Gryb <oleg@gryb.info>
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: Thu, 13 Nov 2014 06:37:55 -0000




----- Original Message -----
> From: Johannes Merkle <johannes.merkle@secunet.com>
> To: Oleg Gryb <oleg@gryb.info>; "tls@ietf.org" <tls@ietf.org>
> Cc: 
> Sent: Wednesday, November 12, 2014 9:12 AM
> Subject: Re: [TLS] Twist security for brainpoolp256r1
> 
> As Watson Ladd just pointed out to me, the terms "quadratic twists" 
> and "non-quadratic twists" are not common in math
> textbooks. For a curve in Weierstrass form E: y^2 = x^3 + a*x  + b mod p, the 
> term twist denotes a curve  E': y^2 = x^3
> + v^2*a*x + v^3* b mod p.
> - If v is a quadratic residue, i.e., if there is a w with w^2 = v mod p, then E 
> and E' are isomorphic mod p and thus
> have equivalent security.
> - If v is a quadratic non-residue, E' is not isomorphic to E and the curve 
> orders satisfy |E| + |E'| = p+2.
> Text books often discuss only the case of quadratic non-residues (e.g. Blake, 
> Seroussi, Smart).
> 
> In the case of the Brainpool curves, the twists mentioned in RFC 5639 are twists 
> via a quadratic residue and have the

> same security as the respective random curves.

Thanks, very helpful. Just to summarize yours and Manuel's notes in regard of quadratic non-residue, or non-quadratic twists (as they are called in other emails), they can be used as a source of malicious EC points to run invalid-curve attacks on the original curves, but since all implementations  compliant with X9* standards including openssl must have point-on-curve validation, invalid-curve attacks and small-group attacks become irrelevant when it comes to brainpoool's openssl implementation. Note - small group attacks are not possible, because of a different reason: cofactor for all brainpool curves is equal to 1.     


Efficiency is still an issue for me. Since curves such as NIST P-256 do have optimized EC arithmetic, but nothing like that is available for brainpool curves, it would be nice to know what the delta is. If it's up to 30% percent, I would probably ignore, if it's essentially more than that, I might need to re-consider my choice. If no quantitative data is available, I would probably need to write/run my own tests.


> > -- 
> Johannes
>