Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

For some curves it's necessary to validate the public-key of the other side before running an elliptic-curve Diffie-Hellman key-exchange. Apparently if you don't validate the public key, small subgroup attacks can leak your private key.

I have a few questions related to this issue:

  1. Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?
  2. Which validations need to be performed? Just check if the order of the point is large enough?
  3. Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?
share|improve this question
add comment

2 Answers 2

up vote 5 down vote accepted

Before we get to the questions, we need to understand what these attacks look like.

An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equation $y^2 = x^3 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$. (The equations I'm writing assume a curve over $GF(p)$; this attack works for binary curves, but the equations are somewhat different; the above definitions also ignore the Point at Infinity; that's mostly unimportant for what we're doing).

If we consider operating on a point that is provided by someone else, one thing that we need to ask is "what happens if he gives us a point that's not actually on the curve"; that is, is not actually a solution for $y^2 = x^3 + ax + b \bmod p$? Well, that rather depends on what is the exact algorithm we use to do point addition; in the standard algorithms (and where we're dealing solely with points derived from the attacker-provided pseudopoint, which is the case in ECDH), we end up with "points" which are solutions to $y^2 = x^3 + ax + c \mod p$, where $c$ is the value that original attacker-provided point was a solution to. That is, we're effectively doing the ECDH operation on a curve that the attacker chose.

Why is this a problem? Well, different elliptic curves have different numbers of points (that is, solutions to the underlying equation). The original curve may have been chosen to be a large prime; the attacker can select a curve which has an order with a small factor. For example, he may give us a curve whose order has $r$ as a factor, and give us a point $Y$ of order $r$ (that is, $xY$ can take on exactly $r$ distinct values). If he give us that point $Y$ as his ECDH public value, we compute $eY$ (where $e$ is our private value), and use that as the 'shared secret'); then, the attacker can determine the value $e \bmod r$ by checking what shared secret value we got; the details depend on the protocol that uses the shared secret. This effectively gives the attacker $log_2 r$ bits of our private exponent; doing this a handful of times for different values of $r$ allows him to recover our entire private exponent.

So, to answer your questions:

Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?

The attacker can choose a different curve (and a different value of $r$) each time; each different $r$ gives him more information about the private value

Which validations need to be performed? Just check if the order of the point is large enough?

The obvious validation that needs to be performed is to plug his values $(x, y)$ into the elliptic curve equation $y^2 = x^3 + ax + b \bmod p$; that's cheap and totally foils this attack. The other things that you ought to make sure (to avoid other attacks) is to make sure that his point isn't the point-at-infinity, and if the curve order is composite (which it typically isn't; check your curve to be sure), then whether his point is in the subgroup generated by the ECDH generator $G$ (this last bit can be done by verifying if $qY = 0$, where $q$ is the order of $G$, $Y$ is the point provided by the other side, and $0$ is the point-at-infinity).

Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?

This attack really isn't against the curve, but against the implementation (and what it does when given an invalid value). As far as I know, all curves can have implementations which are vulnerable.

share|improve this answer
    
I wasn't considering your first attack, because I forgot that many protocols don't use compressed points. I was only considering checks of points which result from decompression, and thus are on the curve. Such as checking that $ qY=0 $. I'll need to reread some papers, to check if some of the attacks I read about assume points not on the curve. At least some checks seem to be curve specific, since the Curve25519 paper mentions choosing parameters so that any compressed point can be used without validation. –  CodesInChaos Sep 19 '12 at 15:38
1  
@CodesInChaos: if we're talking about a prime-order curve, and we get a point $Y$ that's on the curve, and not the point at infinity, then there's no further validation possible; we know that there must be some value $y$ with $Y = yG$, and so it is a possible public value from the peer. –  poncho Sep 19 '12 at 15:43
add comment

Depends what you mean by "validate". You should always validate any Public Key, as otherwise how do you know who owns it? If you are not sure of the owner, you are open to a man-in-the-middle attack.

But I guess by validate you mean validate that the point is of the right order? You should certainly check that its on the curve (easy) and check that its not a point of small order. The possible orders are the divisors of the number of points on the curve. This possibility can and should be avoided by using a curve with a prime number of points, in which case only one order (the right one) is possible.

If your curve has multiple small subgroups, then an attacker can over time get to see your private key modulo the order of each of them. And then the Chinese Remaninder theorem might in theory be used to find your full secret.

So.. (a) Use a curve with a prime number of points on it and (b) Check that any points sent to you are actually on the curve. And you are good to go...

share|improve this answer
    
I thought order $1$ was possible even for curves with a prime number of points (although if I $\hspace{1.2 in}$ understand how things work, that's not a security risk). $\:$ –  Ricky Demer Sep 19 '12 at 18:27
    
@RickyDemer: the only order 1 point on an elliptic curve is the point at infinity. As long as we reject that, an order 1 point is not a possibility. –  poncho Oct 8 '12 at 17:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.