Subject: [Cfrg] Twist insecurity of 2y^2=x^3+x/GF(8^91+5)

From: Dan Brown <[email-masked]>
Date: Fri, 18 Aug 2017 21:20:01 +0000

Hi CFRG,

As noted in earlier discussions, the curve 2y^2=x^3+x over GF(8^91+5) was chosen without considering the criterion of twist security, instead electing for some other security goals.

In this thread, I wish to discuss and quantify the consequences of forgoing twist security for this specific curve, to ensure that an Internet-Draft on it (eventually) specifies any necessary security precautions, but also to be clear the tradeoffs in security features of this curve compared to others.

I'm a bit shaky on the theory and motivation of twist security, but I'll state what I currently think and hope for corrections from the CFRG list.

First of all, this curve has complex multiplication by i, which I vaguely understand to imply that the curve has four twists, under some of theoretical definition of a twist (1% sure).  Nevertheless, for the Montgomery ladder context of twist security, only two of these twists are relevant (10% sure): the original curve and the twist y^2=x^3+x.

The original curve has size 72n for n prime, while the relevant twist (20% sure) has size with prime factorization
2^2 * 5 * 1526119141 * 788069478421 * 182758084524062861993 * 3452464930451677330036005252040328546941
With the prime factors having base-2 logs of approximately:
1 1 2.3 30.5 39.5 67.3 131.3

This makes the ECDLP on the twist quite insecure (2^65), due to Pohlig-Hellman, which rules out using this curve in the few specialized protocols that make equal use of the curve and its twist.

For a conventional DH protocol using a Montgomery ladder, the critical question seems to be what is lost by skipping point validation?  Three interactions against the same static DH private key can used to find the private key at a cost of about 2^65 (off-line) operations.  (1% sure of no known faster attack).  By contrast, the gain of skipping point validation is about 5-10% in DH runtime (is this right?).  So, the remedy is either MUST not re-use DH private keys or MUST do point validation on public keys, but wait ...

If the static DH key in the Montgomery ladder implementation above is used in a higher-level protocol that requires key confirmation from the other side before using the shared key in encryption, then it seems the previous attacker's chances either are drastically reduced, or the attacker requires billions of (failed) interactions (instead of 5).  Is this right?  If so, in such a protocol, would a good remedy be to place a limit (e.g. 1000/month) on the number of failed key confirmation attempts?

Is this kind of key confirmation in a protocol the norm, or the exception?  For example, do current versions TLS and IKE and SSH check a MAC with the shared secret from the other side before using the shared secret in AES, etc.?  Non-interactive protocols cannot give key confirmation to the sender, but usually the sender/CA would also validate the receiver's certificate (reducing the relative incentive to skip point validation).

Best regards,

Dan

[BlackBerry]<http://www.blackberry.com/>

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 19 Aug 2017 18:33:02 +0300

On Fri, Aug 18, 2017 at 09:20:01PM +0000, Dan Brown wrote:
> 
> If the static DH key in the Montgomery ladder implementation above
> is used in a higher-level protocol that requires key confirmation
> from the other side before using the shared key in encryption,
> then it seems the previous attacker's chances either are
> drastically reduced, or the attacker requires billions of (failed)
> interactions (instead of 5).  Is this right?  If so, in such a
> protocol, would a good remedy be to place a limit (e.g. 1000/month)
> on the number of failed key confirmation attempts?

It depends on protocol.

As example of how things can go wrong, take TLS 1.3. If the server
keeps fixed DH key, one can send a few handshakes, and from the
resposes (the server does key confirmation first!) do offline ~2^65
operation attack to find the fixed DH key.

And TLS 1.3 breaks _really_ badly if the server static DH key is
compromised.

-Ilari

---

From: Dan Brown <[email-masked]>
Date: Mon, 21 Aug 2017 16:05:13 +0000

-----Original Message-----
From: [email-masked] 
On Fri, Aug 18, 2017 at 09:20:01PM +0000, Dan Brown wrote:
> 
> If the static DH key in the Montgomery ladder implementation above is 
> used in a higher-level protocol that requires key confirmation from 
> the other side before using the shared key in encryption, then it 
> seems the previous attacker's chances either are drastically reduced, 
> or the attacker requires billions of (failed) interactions (instead of 
> 5).  Is this right?  If so, in such a protocol, would a good remedy be 
> to place a limit (e.g. 1000/month) on the number of failed key 
> confirmation attempts?

It depends on protocol.

As example of how things can go wrong, take TLS 1.3. If the server keeps fixed DH key, one can send a few handshakes, and from the resposes (the server does key confirmation first!) do offline ~2^65 operation attack to find the fixed DH key.

And TLS 1.3 breaks _really_ badly if the server static DH key is compromised.

<DB>
Thanks.  

I reviewed TLS 1.3 based on your comments, and I agree with your conclusion.

I noticed that the client in TLS 1.3 should normally receive a protected {Finish} from the server before releasing information derived the shared secret.  So, the client receives key confirmation.  If the client is re-using the same static DH key, using a Montgomery without point validation, then by verifying key confirmation, the client is partially protected from small-subgroup attacks.  (I don't know if this is a known countermeasure.)  Or, am I missing something?

So, anyway, any initial I-D I write will likely put a MUST on point validation of static DH keys...

</DB>