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

[Dan Brown <[e-mail]>]

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.