Re: [tor-dev] Action items wrt ed25519 onion address verification in prop224 (was Re: [tor-project] Network team meetings notes from 17 April 2017)

[Ian Goldberg <iang@xxxxxxxxxxxxxxx>]

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@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev