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
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <openssl/sha.h>
#include "ed25519-donna.h"
static void dump_point(const char *label, const ge25519 *p)
{
unsigned char packed[32];
int i;
if (label) {
printf("%s ", label);
}
ge25519_pack(packed, p);
for (i=0;i<32;++i) {
printf("%02x", packed[i]);
}
printf("\n");
}
static void dump_multiples(const ge25519 *p)
{
ge25519 kp;
bignum256modm k = {0};
bignum256modm zero = {0};
char label[7] = "* l =";
int i;
for (i=1;i<=8;++i) {
k[0] = i;
ge25519_double_scalarmult_vartime(&kp, p, k, zero);
label[2] = '0'+i;
dump_point(label, &kp);
}
printf("\n");
}
static void randpoint(char *randstate, ge25519 *p)
{
unsigned char hash[64];
SHA512(randstate, 32, hash);
ge25519_unpack_negative_vartime(p, hash);
memmove(randstate, hash+32, 32);
}
int main(int argc, char **argv)
{
unsigned char randstate[32];
ge25519 p, mp;
bignum256modm zero = {0};
int rfd = open("/dev/urandom", O_RDONLY);
if (rfd < 0) {
perror("open /dev/urandom");
exit(1);
}
if (read(rfd, randstate, 32) < 32) {
perror("read /dev/urandom");
exit(1);
}
close(rfd);
while(1) {
randpoint(randstate, &p);
dump_point("Orig =", &p);
// Multiply by the group order
ge25519_double_scalarmult_vartime(&mp, &p, modm_m, zero);
dump_multiples(&mp);
}
return 0;
}
_______________________________________________
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
