On Tue, Apr 25, 2017 at 03:38:37PM +0300, George Kadianakis wrote:
It turns out the point whose packed representation is 32 bytes of 0x00 is a torsion point; it is the point (-1,0).
Indeed, these are the 7 pure torsion points in ed25519:
26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 0000000000000000000000000000000000000000000000000000000000000000 =(-1,0) c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f =(0,-1) c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa 0000000000000000000000000000000000000000000000000000000000000080 =(1,0) 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85
So just take any of the above points, and add it to a valid pubkey to get an invalid pubkey.
You should probably also check points not on the curve at all, such as:
e19c65de75c68cf3b7643ea732ba9eb1a3d20d6d57ba223c2ece1df66feb5af0
If you generate a 32-byte string at random, about 1/2 the time it won't be on the curve at all (that is, if P is the unpack of those 32 bytes, 8*l*P is *not* the identity), about 7/16 of the time it is on the curve, but has a torsion component (8*l*P is the identity, but l*P is not), and 1/16 of the time it's a valid pubkey (l*P is the identity, but P is not).
Good stuff Ian.
I pushed a new branch `bug22006` that:
- Checks that the pubkey is not the identity element itself.
- Adds tests based on the points you listed above.
Check it out here: https://gitweb.torproject.org/user/asn/tor.git/log/?h=bug22006_v2
It looks to me as though you're only checking the pure torsion points above. You should *add* one of those points to a valid pubkey in order to get a point to check. For example, the points:
300ef2e64e588e1df55b48e4da0416ffb64cc85d5b00af6463d5cc6c2b1c185e f43e3a046db8749164c6e69b193f1e942c7452e7d888736f40b98093d814d5e7 c9fff3af0471c28e33e98c2043e44f779d0427b1e37c521a6bddc011ed1869af
would be good additional tests (all should fail; they have order 8l, 4l, 2l respectively).
This one should pass:
4ba2e44760dff4c559ef3c38768c1c14a8a54740c782c8d70803e9d6e3ad8794
Another thing:
My understanding is that this is a special-case validation and it's expensive,
It's a single scalar multiplication (and packing, I suppose). I guess "expensive" is relative; you might time it to see if the cost matters to you.
so I opted to not perform it everytime we generate a new ed25519 keypair or when we receive one from the internet. So for example, I'm not doing it when we extract the ed25519 signing pubkey that signs the HS descriptor, since we don't care if there are equivalent forms of that key.
You indeed don't need to do it when you generate a key yourself in a known-good way (unless you're paranoid about fault attacks, which I don't think you are). I'm a little wary about ever not doing it on a pubkey you receive from the Internet, though. I would want to know if someone were sending me a malformed crypto-relevant value.
So this validation function is currently unused, and I plan to only use it on the prop224 client-side when a client handles received onion addresses.
Finally, how did you derive the list of points above? o.o
Attached.
- Ian