Re: [TLS] Twist security for brainpoolp256r1

Oleg Gryb <> Thu, 13 November 2014 06:37 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 565091A1B9E for <>; Wed, 12 Nov 2014 22:37:55 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.594
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id h03nygY2-7M5 for <>; Wed, 12 Nov 2014 22:37:53 -0800 (PST)
Received: from ( []) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 9CE481A19F4 for <>; Wed, 12 Nov 2014 22:37:53 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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;; b=HvlW/0j0EXjHrw/VKARnWo3qHRgR5yDmvlXRVshJ6JpVB7du9UUYkuY1L8TN4lfFffah7qiN/y9YHY2dnZaS4RscCIuEhTXDTxYvW8mseVNj6qP+68Bm5Md+2z4nRGiepDIuIrZaHg91CtWggXApBDfRPZ92ONraBHK4BUZ24Oqm04cTTZ4QKa2xXSjVCoDi+ItrI0MkNfeOmdSKfw3tNWfR2nUXyQs0bIxagq/gUsteQ+HVWv6zNl9jejEsSk22EwTfEaoocn32cRT1Q3x3E3G+8KV0nAj+WVddHMEafBFxoYTnoKm7E37ksljbko1w8X58+ZPqjeqHSGSC2kLMGg==;
Received: from [] by with NNFMP; 13 Nov 2014 06:37:52 -0000
Received: from [] by with NNFMP; 13 Nov 2014 06:37:52 -0000
Received: from [] by with NNFMP; 13 Nov 2014 06:37:52 -0000
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: bi_UTTYVM1mEEehJTHQ6eNZRPPCulaw9HRhwxzs.La9_2ITJ_NIbSTBX0lqngQD IVIe9ZwkrTOxkO01kS.Nk60JYta9RJt_IJbeluYWjw6GkOXMUKdcCBPgDNgljGyPg1XL7nM9Oe_C kkSSfSgKfi6yfOqgEK0y8.4ThNeq_.daq7wjmsIRRvYf0vpwKw6p849uD11ZtrAVD5I4tmWTK6tc wq6jGMeBYjxAwT.Sg_T71DcbGBH5KeZEXpMlHfsD8wOCfsDQz2o6Dc_yK8eUbURkvRZViBakooX3 Edb59ju1rOwussvYLeMvoaqFLUCP3GzF2_l2miup8Q0at2z1ipi723UzCAQ6KL8FXIp26w5.F8m_ GG4eoLJ4g7fhbmBKvnPE0pvJCt0uvTFG.L4tiZ1ZVLW1ohnlztHs3LNxfyWibippFUfvO
Received: by; Thu, 13 Nov 2014 06:37:52 +0000
Date: Thu, 13 Nov 2014 06:35:21 +0000
From: Oleg Gryb <>
To: Johannes Merkle <>, Oleg Gryb <>, "" <>
Message-ID: <>
In-Reply-To: <>
References: <>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
Subject: Re: [TLS] Twist security for brainpoolp256r1
X-Mailman-Version: 2.1.15
Precedence: list
Reply-To: Oleg Gryb <>
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 13 Nov 2014 06:37:55 -0000

----- Original Message -----
> From: Johannes Merkle <>
> To: Oleg Gryb <>; "" <>
> 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