For some curves it\'s necessary to validate the public-key of the other side bef
ID: 650340 • Letter: F
Question
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:
Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?
Which validations need to be performed? Just check if the order of the point is large enough?
Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?
Explanation / Answer
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...