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

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

2017-04-25 Thread George Kadianakis

Ian Goldberg  writes:

> 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
>> >  =(-1,0)
>> > c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a
>> > ec7f =(0,-1)
>> > c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa
>> > 0080 =(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
>

Oops yes, I was actually testing the pure torsion points, instead of
generating fresh points P = b*B + t*T as I think you are suggesting.

Doing ed25519 addition in the tor unittests is kind of a PITA, so I'll
just borrow the points you are suggesting above and test those directly.

Pushed a fixup commit here:
https://gitweb.torproject.org/user/asn/tor.git/commit/?h=bug22006_v2=eb3530fc8999b3a3028d60f86bd04445273f247f

>> 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.
>

Hmm, and that's just to ensure that there are no equivalent forms of
those pubkeys, right? And also to ensure that no one is sending random
garbage to us. Because IIUC using an ed25519 pubkey with a torsion
component does not really affect the security of signature verification
in other ways.

Anyhow, these two commits do the validation in a bunch of places we
receive ed25519 pubkeys from the net:

https://gitweb.torproject.org/user/asn/tor.git/commit/?h=bug22006_v2=e37c0c3fa5d572421e52d4cd144f0617ad4d10e0

https://gitweb.torproject.org/user/asn/tor.git/commit/?h=bug22006_v2=8965bf278e5efe3f17e6d99123659a26da02c589

Thanks for the script as well! :)
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

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

2017-04-25 Thread Ian Goldberg

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
> >  =(-1,0)
> > c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a
> > ec7f =(0,-1)
> > c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa
> > 0080 =(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 
#include 
#include 
#include 
#include 
#include 
#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(, p, k, zero);
	label[2] = '0'+i;
	dump_point(label, );
}
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, );

	dump_point("Orig =", );
	// Multiply by the group order
	ge25519_double_scalarmult_vartime(, , modm_m, zero);
	dump_multiples();
}

return 0;
}
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

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

2017-04-25 Thread George Kadianakis

Ian Goldberg  writes:

> On Mon, Apr 24, 2017 at 04:47:44PM +0300, George Kadianakis wrote:
>> Ian Goldberg  writes:
>> 
>> > On Thu, Apr 20, 2017 at 03:40:58PM +0300, George Kadianakis wrote:
>> >> Hey Ian,
>> >> 
>> >> so the current problem with ed25519-donna is that when I'm doing the
>> >> above, I'm getting the following 32-byte key after ge25519_pack(). Here
>> >> it is hexed up:
>> >> 
>> >>0x0100
>> >> 
>> >> I don't see any methods in ed25519-donna for checking a point or a
>> >> packed point to see if it's the point at infinity (identity element).
>> >
>> > There actually is such a function, but it's buried in a weird place.
>> > ge25519_is_neutral_vartime in ed25519-donna-batchverify.h does what you
>> > want, but it's static, so you would need to copy it (and remove the line
>> > involving batch_point_buffer).  Probably not worthwhile.
>> >
>> > I can easily believe the representation of the identity (neutral)
>> > element in ed25519 is the hex value above.  (And it is; see below.)
>> >
>> >> I've been assuming that the point at infinity would be an all-zeroes
>> >> 32-byte array, because that's what we are doing in curve25519, but I
>> >> actually have no idea how the array representation of ge25519_pack()
>> >> works. Here is our process for curve25519:
>> >>
>> >> https://gitweb.torproject.org/tor.git/tree/src/common/crypto_curve25519.c#n123
>> >
>> > Curve25519 only outputs the x coordinate, which is indeed 0, so you get
>> > the all-zero value.  ed25519 outputs the y coordinate (which is the
>> > 255-bit value 0x000...0001 in little-endian format) and the single-bit
>> > parity of the x coordinate (which is 0), so you do get the hex you give
>> > above.  (The identity element is the point (0,1) in Edwards curves, not
>> > actually the point at infinity.)
>> >
>> >> The above packed point is an all zeroes 32-byte string, apart from the
>> >> very first bit which is set. Could it be that the first bit is the
>> >> compressed sign of the 'x' coordinate or something, and that's actually
>> >> the point at infinity?
>> >> 
>> >> But then what's the right way to check for the point at infinity? Check
>> >> that everything is 0 apart from the first sign bit?
>> >
>> > Yes, pack the point, and compare it to the above 32-byte value.
>> >
>> >> And after I figure this out, I need to do the same for the reference
>> >> implementation of ed25519, because as it seems Tor uses two simultaneous
>> >> implementations of ed25519:
>> >> https://gitweb.torproject.org/tor.git/tree/src/ext/ed25519
>> >
>> > Yes, hopefully that implementation packs points in the same way!
>> >
>> >> Thanks for the help Ian :) Very much appreciated!
>> >
>> > No worries.
>> >
>> 
>> [CCing tor-dev since people might find it interesting]
>> 
>> Thanks for the advice Ian :)
>> 
>> With your help, I have now implemented the validation check. Check out
>> the ticket #22006 and the branch `bug22006` here:
>> 
>> https://gitweb.torproject.org/user/asn/tor.git/commit/?h=bug22006=628dd1adfdc4cbde449d6ec6808a9f6aa6f6f6c4
>
> You should also check that the point it not *itself* the identity
> element.
>
>> One last thing I'd like to do here is test our validation function
>> against a pubkey with torsion component to make sure that it gets
>> rejected. How would you go about generating such a pubkey?
>> 
>> I was thinking of using the CRT to find an integer a \in Z, s.t
>>a == 0 (mod l) && a == 1 (mod 8)
>> but then I didn't know how to go from that scalar with a torsion
>> component to an ed25519 point...
>
> 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
>  =(-1,0)
> c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a
> ec7f =(0,-1)
> c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa
> 0080 =(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

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

2017-04-24 Thread Ian Goldberg

On Mon, Apr 24, 2017 at 04:47:44PM +0300, George Kadianakis wrote:
> Ian Goldberg  writes:
> 
> > On Thu, Apr 20, 2017 at 03:40:58PM +0300, George Kadianakis wrote:
> >> Hey Ian,
> >> 
> >> so the current problem with ed25519-donna is that when I'm doing the
> >> above, I'm getting the following 32-byte key after ge25519_pack(). Here
> >> it is hexed up:
> >> 
> >>0x0100
> >> 
> >> I don't see any methods in ed25519-donna for checking a point or a
> >> packed point to see if it's the point at infinity (identity element).
> >
> > There actually is such a function, but it's buried in a weird place.
> > ge25519_is_neutral_vartime in ed25519-donna-batchverify.h does what you
> > want, but it's static, so you would need to copy it (and remove the line
> > involving batch_point_buffer).  Probably not worthwhile.
> >
> > I can easily believe the representation of the identity (neutral)
> > element in ed25519 is the hex value above.  (And it is; see below.)
> >
> >> I've been assuming that the point at infinity would be an all-zeroes
> >> 32-byte array, because that's what we are doing in curve25519, but I
> >> actually have no idea how the array representation of ge25519_pack()
> >> works. Here is our process for curve25519:
> >>
> >> https://gitweb.torproject.org/tor.git/tree/src/common/crypto_curve25519.c#n123
> >
> > Curve25519 only outputs the x coordinate, which is indeed 0, so you get
> > the all-zero value.  ed25519 outputs the y coordinate (which is the
> > 255-bit value 0x000...0001 in little-endian format) and the single-bit
> > parity of the x coordinate (which is 0), so you do get the hex you give
> > above.  (The identity element is the point (0,1) in Edwards curves, not
> > actually the point at infinity.)
> >
> >> The above packed point is an all zeroes 32-byte string, apart from the
> >> very first bit which is set. Could it be that the first bit is the
> >> compressed sign of the 'x' coordinate or something, and that's actually
> >> the point at infinity?
> >> 
> >> But then what's the right way to check for the point at infinity? Check
> >> that everything is 0 apart from the first sign bit?
> >
> > Yes, pack the point, and compare it to the above 32-byte value.
> >
> >> And after I figure this out, I need to do the same for the reference
> >> implementation of ed25519, because as it seems Tor uses two simultaneous
> >> implementations of ed25519:
> >> https://gitweb.torproject.org/tor.git/tree/src/ext/ed25519
> >
> > Yes, hopefully that implementation packs points in the same way!
> >
> >> Thanks for the help Ian :) Very much appreciated!
> >
> > No worries.
> >
> 
> [CCing tor-dev since people might find it interesting]
> 
> Thanks for the advice Ian :)
> 
> With your help, I have now implemented the validation check. Check out
> the ticket #22006 and the branch `bug22006` here:
> 
> https://gitweb.torproject.org/user/asn/tor.git/commit/?h=bug22006=628dd1adfdc4cbde449d6ec6808a9f6aa6f6f6c4

You should also check that the point it not *itself* the identity
element.

> One last thing I'd like to do here is test our validation function
> against a pubkey with torsion component to make sure that it gets
> rejected. How would you go about generating such a pubkey?
> 
> I was thinking of using the CRT to find an integer a \in Z, s.t
>a == 0 (mod l) && a == 1 (mod 8)
> but then I didn't know how to go from that scalar with a torsion
> component to an ed25519 point...

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
 =(-1,0)
c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a
ec7f =(0,-1)
c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa
0080 =(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).

   - Ian
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

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

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

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

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

4 matches

Site Navigation

Mail list logo

Footer information