# What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply?

This page on Twist security mentions a combined attack and a twist rho attack, applicable in particular to NIST P-224 curve with cost $2^{58.4}$ something, with no mention precise definition of protocols concerned by the attack(s), beyond:

Some of the ECDLP security requirements for the twist are overkill for DH on the original curve: DH does not actually reveal nQ to Eve, so there is no obvious way for Eve to apply (e.g.) an additive transfer. There are, however, other ECC protocols that make full use of both the original curve and its twist, and twist security is important for these protocols. See, e.g., 1986 Kaliski, 1988 Kaliski, and 2001 Boyd–Montague–Nguyen.

What are theses attacks (in the simplest meaningful terms possible please, including some introduction to the twist)? To what class of protocols (perhaps: signature, key establishment..) and operational setup (number/nature of queries to signer/server..) do they apply?

Note: the present question is closely related to (and inspired by) this more technical one.

• I think it refers to using small subgroup attacks on the twist, when doing ECDH. I've recenlty posted a similar questions specifically on short Weierstrass curve since I don't understand how the twist attack applies to them. – Ruggero Oct 29 '14 at 12:29
• @Ruggero: I have added reference to your question, and quote that I interpret as suggesting the attack(s) do not apply to protocols doing straight ECDH; I'm seeking clarification of this. – fgrieu Oct 29 '14 at 12:58
• To be honest, I do understand the attacks mentioned more than I understand your quote. Are you familiar with invalid curve attacks against ECDH ? If not see this. In the context the attacker can't use invalid curve, due to x-only ladders, so she uses the twist making an ECDH for each low-order subgroup of the twist (and of the original curve, if any). I'm sorry but I don't have time to write a full answer now. – Ruggero Oct 29 '14 at 13:55
• Bernstein likes doing ECDH using x-only ladders without first verifying if the given x value is on the curve or the twist. For example the Curve25519 implementation in NaCl works like that. – CodesInChaos Oct 30 '14 at 18:28

I don't consider the following a complete answer, but it is a start, and best I can do with my very limited knowledge. I hope someone could fix it or improve it.

These type of attacks are only possible against specific implementation of higher level protocols.
I will start by describing an invalid-curve attack against a specific ECDH based protocol.

Simple Pairing protocol: Entity A wants to establish an encrypted and authenticated channel with Entity B, and both support the same pairing protocol, based on ECDH using P-224

1. Entity A sends its own ECC public key ($pub_A$) to B
2. Entity B sends its own ECC public key ($pub_B$) to A
3. Both devices computes ECDH, thus generating a shared point ($SP = priv_A*pub_B = priv_B*pub_A$)
4. Individually they run this shared point through a KDF, generating $K_{ENC}$ and $K_{MAC}$
5. Entity A starts communicating to B using AES CTR to encrypt the communication and AES CMAC to authenticate the ciphertext.

Let's now suppose B is malicious and wants to recover A's private key.

Conditions for the attack to succeed:

1. A doesnt't check if the B's public key, or computed shared point, actually lie on P-224.
2. Public keys are exchanged with both $x$ and $y$ coordinates and both are used in the scalar multiplication algorithm.
3. The scalar multiplication algorihtm doesn't use the value of $b$ in the computation (this is very common for short Weierstrass curves)

B generates elliptic curves $EC'$ over the same field $F_p$ of P-224 with the same $a$ parameter but different value for the $b$ parameter. B computes the order of those curves, and factor it, looking for small primes divisors.
Let's suppose he finds a suitable curve with order of form $17*h$ where $h$ is a composite not divisible by $17$. This means that there is a subgroup of $EC'$ with order $17$.
B finds a point of this small subgroup, calls it $pub_B$ (his public key) and sends it to A.

A will compute $SP = priv_A*pub_B$, derive $K_{ENC}$ and $K_{MAC}$ and starts the secured communication.
Note that A will in fact compute the scalar multiplication over $EC'$ and therefore $SP$ has only $17$ possible values. In this way he finds the value of $priv_A\mod17$

He repeats the attack with other small groups having order coprime to each other (he can use several $EC'$), and then uses the $CRT$ to recover $priv_A$.

Let's now discuss the case where the scalar multiplication doesn't use the $y$ coordinate.
Premise: Hereafter I will assume that a x-coordinate only ladder can be used on the original curve and on the twist. The answer to this question explains how a twist curve can be used for short Weierstrass curves.

Now the job of B is much more complicated because he can't easily provide to A a public key on a generic $EC'$ since the $y$ coordinate is key for this, as without the $y$ A will compute the scalar multiplication on $EC$ and not on $EC'$. But, since A algorithm will work for the twist also (as in our premise) then B can use a non trivial quadratic twist of $EC$.

There is one set of isomorphic curves, each curve within the set is defined through a $c$ that is not a quadratic residue in $F_P$, by $y^2 = x^3 + c^2ax + c^3b$.
$a$ and $b$ are the original curve's parameter, and this set is the $twist$.
These curves have order different from the order of $EC$, namely $p+1+t$ where $t$ is the trace of $EC$.
If the order factors in many (relative) small primes then it opens the door to an invalid curve attack, where B sends public keys lying on small subgroups of the twist.

For P-224 the order of the twist factors to:
$$3^2 * 11 * 47 * 3015283 * 40375823 * 267983539294927 * 177594041488131583478651368420021457$$ So he can use the small subgroups of orders $3,11,47,3015283,40375823,267983539294927$. He needs to bruteforce on $K_{MAC}$ for each subgroup so this attack requires about $2^{log(267983539294927)} = 2^{47.93}$ operations to get by CRT the value of: $$priv_A \mod(3 * 11 * 47 * 3015283 * 40375823 * 267983539294927)$$ Now B can computes the actual value of $priv_A$ by Pollard's kangaroo. He uses the information he just got, limiting the search to $n/(3 * 11 * 47 * 3015283 * 40375823 * 267983539294927)$ which is about $2^{105.32}$.
Due to Pollard's kangaroo complexity it requires about $2^{105.32/2}=2^{59.34}$ operations, which dominates the complexity analysis.

Note this number is close but not equal to Dr. Bernstein's number of $2^{58.4}$ operations. In this page he shows that he calculates the complexity of the combined attack as $log(\pi/4*l)/log(4)$ where $l$ is the largest prime in the divisors of the order (that is exacly our $n/(3*11*47*3015283*40375823*267983539294927)$, which approximate to the $2^{58.4}$ value of the question. I don't know where his formula come from, most likely from a much better knowledge of Pollard's Kangaroo running time.

Edit1: understood calculation from bernestein, modified the premise since my question was answered.

• $\log(\pi/4 l)/\log(4) = \log(\sqrt{\pi/4 l})/\log(2) = \log(\sqrt{\pi l / 2} / \sqrt{2})/\log(2)$. It's the usual Pollard rho complexity with the negation map taken into account. – Samuel Neves Oct 30 '14 at 22:30
• Does the rho have the same complexity as the kangaroo? – Ruggero Oct 30 '14 at 22:34
• The complexity for kangaroo is slighly different when taking the negation map into account. You can use rho in this situation, though, like you would in Pohlig-Hellman. – Samuel Neves Oct 30 '14 at 22:41
• Nevermind, I was assuming you had direct access to the points on the twist. Here you cannot use plain rho. – Samuel Neves Oct 30 '14 at 22:49