June 2017 - tor-commits - lists.torproject.org

[tor/release-0.3.1] Merge branch 'ahf_bugs_22702_squashed' into maint-0.3.1
by nickm＠torproject.org 27 Jun '17

27 Jun '17

commit 2cd49d9ea6f8bad20215ad17d5057a8eea8e39e8 Merge: 32eba3d 09ae4fc Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Jun 27 18:28:34 2017 -0400 Merge branch 'ahf_bugs_22702_squashed' into maint-0.3.1 changes/bug22702 | 5 +++++ src/or/consdiffmgr.c | 18 ++++++++++++++++++ src/or/consdiffmgr.h | 3 +++ src/or/directory.c | 31 +++++++++++++++++++++++++++++++ src/or/dirserv.c | 6 ++++++ 5 files changed, 63 insertions(+)

1 0

[tor/master] Merge branch 'ahf_bugs_22702_squashed' into maint-0.3.1
by nickm＠torproject.org 27 Jun '17

27 Jun '17

commit 2cd49d9ea6f8bad20215ad17d5057a8eea8e39e8 Merge: 32eba3d 09ae4fc Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Jun 27 18:28:34 2017 -0400 Merge branch 'ahf_bugs_22702_squashed' into maint-0.3.1 changes/bug22702 | 5 +++++ src/or/consdiffmgr.c | 18 ++++++++++++++++++ src/or/consdiffmgr.h | 3 +++ src/or/directory.c | 31 +++++++++++++++++++++++++++++++ src/or/dirserv.c | 6 ++++++ 5 files changed, 63 insertions(+)

1 0

[tor/master] Merge branch 'asn_bug22006_final_squashed'
by nickm＠torproject.org 27 Jun '17

27 Jun '17

commit 733ce556ad6a59a111b63a860904799c30513a24 Merge: c0f0351 3f94041 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Jun 27 18:21:46 2017 -0400 Merge branch 'asn_bug22006_final_squashed' src/common/crypto_ed25519.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)

1 0

[tor/master] no newlines in log messages.
by nickm＠torproject.org 27 Jun '17

27 Jun '17

commit 3f940415897ec905859314fe2bf129951cd54678 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Jun 27 18:21:35 2017 -0400 no newlines in log messages. --- src/common/crypto_ed25519.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/src/common/crypto_ed25519.c b/src/common/crypto_ed25519.c index 6ebb2a7..1a6d19b 100644 --- a/src/common/crypto_ed25519.c +++ b/src/common/crypto_ed25519.c @@ -783,7 +783,7 @@ ed25519_validate_pubkey(const ed25519_public_key_t *pubkey) /* First check that we were not given the identity element */ if (ed25519_point_is_identity_element(pubkey->pubkey)) { - log_warn(LD_CRYPTO, "ed25519 pubkey is the identity\n"); + log_warn(LD_CRYPTO, "ed25519 pubkey is the identity"); return -1; } @@ -792,12 +792,12 @@ ed25519_validate_pubkey(const ed25519_public_key_t *pubkey) * identity element is returned. */ if (get_ed_impl()->ed25519_scalarmult_with_group_order(result, pubkey->pubkey) < 0) { - log_warn(LD_CRYPTO, "ed25519 group order scalarmult failed\n"); + log_warn(LD_CRYPTO, "ed25519 group order scalarmult failed"); return -1; } if (!ed25519_point_is_identity_element(result)) { - log_warn(LD_CRYPTO, "ed25519 validation failed\n"); + log_warn(LD_CRYPTO, "ed25519 validation failed"); return -1; }

1 0

[tor/master] whitespace fix
by nickm＠torproject.org 27 Jun '17

27 Jun '17

commit c0f0351e06f30b81c77d853a7f90c55309b602bb Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Jun 27 17:22:53 2017 -0400 whitespace fix --- src/test/test_crypto.c | 1 - 1 file changed, 1 deletion(-) diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c index 1f0c803..924dd7d 100644 --- a/src/test/test_crypto.c +++ b/src/test/test_crypto.c @@ -2893,7 +2893,6 @@ test_crypto_ed25519_validation(void *arg) tt_int_op(ed25519_validate_pubkey(&pub1), OP_EQ, 0); } - done: ; }

1 0

[tor/master] ed25519: Add python code to test our ed25519 validation.
by nickm＠torproject.org 27 Jun '17

27 Jun '17

commit 39b5dca7201bb3f30606be199f4d234c86fcaded Author: George Kadianakis <desnacked(a)riseup.net> Date: Mon Apr 24 16:22:02 2017 +0300 ed25519: Add python code to test our ed25519 validation. See https://lists.torproject.org/pipermail/tor-dev/2017-April/012213.html . --- src/test/ed25519_exts_ref.py | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) diff --git a/src/test/ed25519_exts_ref.py b/src/test/ed25519_exts_ref.py index af50104..1898256 100644 --- a/src/test/ed25519_exts_ref.py +++ b/src/test/ed25519_exts_ref.py @@ -69,6 +69,11 @@ def signatureWithESK(m,h,pk): def newSK(): return os.urandom(32) +def random_scalar(entropy_f): # 0..L-1 inclusive + # reduce the bias to a safe level by generating 256 extra bits + oversized = int(binascii.hexlify(entropy_f(32+32)), 16) + return oversized % ell + # ------------------------------------------------------------ MSG = "This is extremely silly. But it is also incredibly serious business!" @@ -126,6 +131,31 @@ class SelfTest(unittest.TestCase): self._testSignatures(besk, bpk) + def testIdentity(self): + # Base point: + # B is the unique point (x, 4/5) \in E for which x is positive + By = 4 * inv(5) + Bx = xrecover(By) + B = [Bx % q,By % q] + + # Get identity E by doing: E = l*B, where l is the group order + identity = scalarmult(B, ell) + + # Get identity E by doing: E = l*A, where A is a random point + sk = newSK() + pk = decodepoint(publickey(sk)) + identity2 = scalarmult(pk, ell) + + # Check that identities match + assert(identity == identity2) + # Check that identity is the point (0,1) + assert(identity == [0L,1L]) + + # Check identity element: a*E = E, where a is a random scalar + scalar = random_scalar(os.urandom) + result = scalarmult(identity, scalar) + assert(result == identity == identity2) + # ------------------------------------------------------------ # From pprint.pprint([ binascii.b2a_hex(os.urandom(32)) for _ in xrange(8) ])

1 0

[tor/master] ed25519: Add func that checks for torsion component in pubkeys.
by nickm＠torproject.org 27 Jun '17

27 Jun '17

commit 559658ff1ca1492543ad60d10b7101c70a62eaa2 Author: George Kadianakis <desnacked(a)riseup.net> Date: Tue Apr 25 15:19:41 2017 +0300 ed25519: Add func that checks for torsion component in pubkeys. See https://lists.torproject.org/pipermail/tor-dev/2017-April/012213.html . --- changes/bug22006 | 4 +++ src/common/crypto_ed25519.c | 50 +++++++++++++++++++++++++++++++ src/common/crypto_ed25519.h | 2 ++ src/ext/ed25519/donna/ed25519_donna_tor.h | 5 ++++ src/ext/ed25519/donna/ed25519_tor.c | 27 +++++++++++++++++ src/ext/ed25519/ref10/blinding.c | 37 +++++++++++++++++++++++ src/ext/ed25519/ref10/ed25519_ref10.h | 4 +++ 7 files changed, 129 insertions(+) diff --git a/changes/bug22006 b/changes/bug22006 new file mode 100644 index 0000000..912bdd8 --- /dev/null +++ b/changes/bug22006 @@ -0,0 +1,4 @@ + o Minor features (ed25519): + - Add validation function that checks for torsion components in ed25119 + public keys. Currently unused but will be used by prop224 client-side + code. Addresses ticket #22006. Math help by Ian Goldberg. diff --git a/src/common/crypto_ed25519.c b/src/common/crypto_ed25519.c index 188e18c..6ebb2a7 100644 --- a/src/common/crypto_ed25519.c +++ b/src/common/crypto_ed25519.c @@ -28,6 +28,7 @@ #include "crypto_format.h" #include "torlog.h" #include "util.h" +#include "util_format.h" #include "ed25519/ref10/ed25519_ref10.h" #include "ed25519/donna/ed25519_donna_tor.h" @@ -57,6 +58,9 @@ typedef struct { int (*pubkey_from_curve25519_pubkey)(unsigned char *, const unsigned char *, int); + + int (*ed25519_scalarmult_with_group_order)(unsigned char *, + const unsigned char *); } ed25519_impl_t; /** The Ref10 Ed25519 implementation. This one is pure C and lightly @@ -77,6 +81,7 @@ static const ed25519_impl_t impl_ref10 = { ed25519_ref10_blind_public_key, ed25519_ref10_pubkey_from_curve25519_pubkey, + ed25519_ref10_scalarmult_with_group_order, }; /** The Ref10 Ed25519 implementation. This one is heavily optimized, but still @@ -97,6 +102,7 @@ static const ed25519_impl_t impl_donna = { ed25519_donna_blind_public_key, ed25519_donna_pubkey_from_curve25519_pubkey, + ed25519_donna_scalarmult_with_group_order, }; /** Which Ed25519 implementation are we using? NULL if we haven't decided @@ -754,3 +760,47 @@ ed25519_init(void) pick_ed25519_impl(); } +/* Return true if point is the identity element of the ed25519 group. */ +static int +ed25519_point_is_identity_element(const uint8_t *point) +{ + /* The identity element in ed25159 is the point with coordinates (0,1). */ + static const uint8_t ed25519_identity[32] = { + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }; + tor_assert(sizeof(ed25519_identity) == ED25519_PUBKEY_LEN); + return tor_memeq(point, ed25519_identity, sizeof(ed25519_identity)); +} + +/** Validate pubkey to ensure that it has no torsion component. + * Return 0 if pubkey is valid, else return -1. */ +int +ed25519_validate_pubkey(const ed25519_public_key_t *pubkey) +{ + uint8_t result[32] = {9}; + + /* First check that we were not given the identity element */ + if (ed25519_point_is_identity_element(pubkey->pubkey)) { + log_warn(LD_CRYPTO, "ed25519 pubkey is the identity\n"); + return -1; + } + + /* For any point on the curve, doing l*point should give the identity element + * (where l is the group order). Do the computation and check that the + * identity element is returned. */ + if (get_ed_impl()->ed25519_scalarmult_with_group_order(result, + pubkey->pubkey) < 0) { + log_warn(LD_CRYPTO, "ed25519 group order scalarmult failed\n"); + return -1; + } + + if (!ed25519_point_is_identity_element(result)) { + log_warn(LD_CRYPTO, "ed25519 validation failed\n"); + return -1; + } + + return 0; +} + diff --git a/src/common/crypto_ed25519.h b/src/common/crypto_ed25519.h index 77a3313..3a43920 100644 --- a/src/common/crypto_ed25519.h +++ b/src/common/crypto_ed25519.h @@ -127,6 +127,8 @@ void ed25519_pubkey_copy(ed25519_public_key_t *dest, void ed25519_set_impl_params(int use_donna); void ed25519_init(void); +int ed25519_validate_pubkey(const ed25519_public_key_t *pubkey); + #ifdef TOR_UNIT_TESTS void crypto_ed25519_testing_force_impl(const char *name); void crypto_ed25519_testing_restore_impl(void); diff --git a/src/ext/ed25519/donna/ed25519_donna_tor.h b/src/ext/ed25519/donna/ed25519_donna_tor.h index d225407..7d7b8c0 100644 --- a/src/ext/ed25519/donna/ed25519_donna_tor.h +++ b/src/ext/ed25519/donna/ed25519_donna_tor.h @@ -30,4 +30,9 @@ int ed25519_donna_blind_public_key(unsigned char *out, const unsigned char *inp, int ed25519_donna_pubkey_from_curve25519_pubkey(unsigned char *out, const unsigned char *inp, int signbit); + +int +ed25519_donna_scalarmult_with_group_order(unsigned char *out, + const unsigned char *pubkey); + #endif diff --git a/src/ext/ed25519/donna/ed25519_tor.c b/src/ext/ed25519/donna/ed25519_tor.c index 9537ae6..bd11027 100644 --- a/src/ext/ed25519/donna/ed25519_tor.c +++ b/src/ext/ed25519/donna/ed25519_tor.c @@ -340,5 +340,32 @@ ed25519_donna_pubkey_from_curve25519_pubkey(unsigned char *out, return 0; } +/* Do the scalar multiplication of pubkey with the group order + * modm_m. Place the result in out which must be at least 32 + * bytes long. */ +int +ed25519_donna_scalarmult_with_group_order(unsigned char *out, + const unsigned char *pubkey) +{ + static const bignum256modm ALIGN(16) zero = { 0 }; + unsigned char pkcopy[32]; + ge25519 ALIGN(16) Point, Result; + + /* No "ge25519_unpack", negate the public key and unpack it back. + * See ed25519_donna_blind_public_key() */ + memcpy(pkcopy, pubkey, 32); + pkcopy[31] ^= (1<<7); + if (!ge25519_unpack_negative_vartime(&Point, pkcopy)) { + return -1; /* error: bail out */ + } + + /* There is no regular scalarmult function so we have to do: + * Result = l*P + 0*B */ + ge25519_double_scalarmult_vartime(&Result, &Point, modm_m, zero); + ge25519_pack(out, &Result); + + return 0; +} + #include "test-internals.c" diff --git a/src/ext/ed25519/ref10/blinding.c b/src/ext/ed25519/ref10/blinding.c index ee3e866..8503f90 100644 --- a/src/ext/ed25519/ref10/blinding.c +++ b/src/ext/ed25519/ref10/blinding.c @@ -74,3 +74,40 @@ int ed25519_ref10_blind_public_key(unsigned char *out, return 0; } + +/* This is the group order encoded in a format that + * ge_double_scalarmult_vartime() understands. The group order m is: + * m = 2^252 + 27742317777372353535851937790883648493 = + * 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed + */ +static const uint8_t modm_m[32] = {0xed,0xd3,0xf5,0x5c,0x1a,0x63,0x12,0x58, + 0xd6,0x9c,0xf7,0xa2,0xde,0xf9,0xde,0x14, + 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, + 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x10}; + +/* Do the scalar multiplication of pubkey with the group order + * modm_m. Place the result in out which must be at least 32 + * bytes long. */ +int +ed25519_ref10_scalarmult_with_group_order(unsigned char *out, + const unsigned char *pubkey) +{ + unsigned char pkcopy[32]; + unsigned char zero[32] = {0}; + ge_p3 Point; + ge_p2 Result; + + /* All this is done to fit 'pubkey' in 'Point' so that it can be used by + * ed25519 ref code. Same thing as in blinding function */ + memcpy(pkcopy, pubkey, 32); + pkcopy[31] ^= (1<<7); + if (ge_frombytes_negate_vartime(&Point, pkcopy) != 0) { + return -1; /* error: bail out */ + } + + /* There isn't a regular scalarmult -- we have to do r = l*P + 0*B */ + ge_double_scalarmult_vartime(&Result, modm_m, &Point, zero); + ge_tobytes(out, &Result); + + return 0; +} diff --git a/src/ext/ed25519/ref10/ed25519_ref10.h b/src/ext/ed25519/ref10/ed25519_ref10.h index af7e21a..5965694 100644 --- a/src/ext/ed25519/ref10/ed25519_ref10.h +++ b/src/ext/ed25519/ref10/ed25519_ref10.h @@ -27,4 +27,8 @@ int ed25519_ref10_blind_public_key(unsigned char *out, const unsigned char *inp, const unsigned char *param); +int +ed25519_ref10_scalarmult_with_group_order(unsigned char *out, + const unsigned char *pubkey); + #endif

1 0

[tor/master] Merge branch 'asn_bug22006_final_squashed'
by nickm＠torproject.org 27 Jun '17

27 Jun '17

commit 7fff6cfead76263c0ced736996dd7ed35e95a6f4 Merge: 0576f9f a155035 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Jun 27 17:19:08 2017 -0400 Merge branch 'asn_bug22006_final_squashed' changes/bug22006 | 4 ++ src/common/crypto_ed25519.c | 50 +++++++++++++++++++++++ src/common/crypto_ed25519.h | 2 + src/ext/ed25519/donna/ed25519_donna_tor.h | 5 +++ src/ext/ed25519/donna/ed25519_tor.c | 27 +++++++++++++ src/ext/ed25519/ref10/blinding.c | 37 +++++++++++++++++ src/ext/ed25519/ref10/ed25519_ref10.h | 4 ++ src/or/dirserv.c | 16 +++++++- src/test/ed25519_exts_ref.py | 30 ++++++++++++++ src/test/test_crypto.c | 66 +++++++++++++++++++++++++++++++ 10 files changed, 239 insertions(+), 2 deletions(-)

1 0

[tor/master] ed25519: Dirauths validate router ed25519 pubkeys before pinning.
by nickm＠torproject.org 27 Jun '17

27 Jun '17

commit a155035d208fb2c05efdad22fe64ea2d6be929a1 Author: George Kadianakis <desnacked(a)riseup.net> Date: Tue Jun 27 15:53:00 2017 +0300 ed25519: Dirauths validate router ed25519 pubkeys before pinning. --- src/or/dirserv.c | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 70b0b22..59ede6a 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -680,10 +680,22 @@ dirserv_add_descriptor(routerinfo_t *ri, const char **msg, const char *source) /* Do keypinning again ... this time, to add the pin if appropriate */ int keypin_status; if (ri->cache_info.signing_key_cert) { + ed25519_public_key_t *pkey = &ri->cache_info.signing_key_cert->signing_key; + /* First let's validate this pubkey before pinning it */ + if (ed25519_validate_pubkey(pkey) < 0) { + log_warn(LD_DIRSERV, "Received bad key from %s (source %s)", + router_describe(ri), source); + control_event_or_authdir_new_descriptor("REJECTED", + ri->cache_info.signed_descriptor_body, + desclen, *msg); + routerinfo_free(ri); + return ROUTER_AUTHDIR_REJECTS; + } + + /* Now pin it! */ keypin_status = keypin_check_and_add( (const uint8_t*)ri->cache_info.identity_digest, - ri->cache_info.signing_key_cert->signing_key.pubkey, - ! key_pinning); + pkey->pubkey, ! key_pinning); } else { keypin_status = keypin_check_lone_rsa( (const uint8_t*)ri->cache_info.identity_digest);

1 0

[tor/master] ed25519: Add unittests for ed25519 pubkey validation.
by nickm＠torproject.org 27 Jun '17

27 Jun '17

commit e8eee3a50e3c38b6c8e97d78a637b8a331fb6560 Author: George Kadianakis <desnacked(a)riseup.net> Date: Tue Apr 25 15:20:13 2017 +0300 ed25519: Add unittests for ed25519 pubkey validation. --- src/test/test_crypto.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+) diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c index ec9d4e2..1f0c803 100644 --- a/src/test/test_crypto.c +++ b/src/test/test_crypto.c @@ -2170,6 +2170,9 @@ test_crypto_ed25519_simple(void *arg) tt_int_op(0, OP_EQ, ed25519_public_key_generate(&pub1, &sec1)); tt_int_op(0, OP_EQ, ed25519_public_key_generate(&pub2, &sec1)); + tt_int_op(ed25519_validate_pubkey(&pub1), OP_EQ, 0); + tt_int_op(ed25519_validate_pubkey(&pub2), OP_EQ, 0); + tt_mem_op(pub1.pubkey, OP_EQ, pub2.pubkey, sizeof(pub1.pubkey)); tt_assert(ed25519_pubkey_eq(&pub1, &pub2)); tt_assert(ed25519_pubkey_eq(&pub1, &pub1)); @@ -2832,6 +2835,68 @@ crypto_rand_check_failure_mode_predict(void) #undef FAILURE_MODE_BUFFER_SIZE +/** Test that our ed25519 validation function rejects evil public keys and + * accepts good ones. */ +static void +test_crypto_ed25519_validation(void *arg) +{ + (void) arg; + + int retval; + ed25519_public_key_t pub1; + + /* See https://lists.torproject.org/pipermail/tor-dev/2017-April/012230.html + for a list of points with torsion components in ed25519. */ + + { /* Point with torsion component (order 8l) */ + const char badkey[] = + "300ef2e64e588e1df55b48e4da0416ffb64cc85d5b00af6463d5cc6c2b1c185e"; + retval = base16_decode((char*)pub1.pubkey, sizeof(pub1.pubkey), + badkey, strlen(badkey)); + tt_int_op(retval, OP_EQ, sizeof(pub1.pubkey)); + tt_int_op(ed25519_validate_pubkey(&pub1), OP_EQ, -1); + } + + { /* Point with torsion component (order 4l) */ + const char badkey[] = + "f43e3a046db8749164c6e69b193f1e942c7452e7d888736f40b98093d814d5e7"; + retval = base16_decode((char*)pub1.pubkey, sizeof(pub1.pubkey), + badkey, strlen(badkey)); + tt_int_op(retval, OP_EQ, sizeof(pub1.pubkey)); + tt_int_op(ed25519_validate_pubkey(&pub1), OP_EQ, -1); + } + + { /* Point with torsion component (order 2l) */ + const char badkey[] = + "c9fff3af0471c28e33e98c2043e44f779d0427b1e37c521a6bddc011ed1869af"; + retval = base16_decode((char*)pub1.pubkey, sizeof(pub1.pubkey), + badkey, strlen(badkey)); + tt_int_op(retval, OP_EQ, sizeof(pub1.pubkey)); + tt_int_op(ed25519_validate_pubkey(&pub1), OP_EQ, -1); + } + + { /* This point is not even on the curve */ + const char badkey[] = + "e19c65de75c68cf3b7643ea732ba9eb1a3d20d6d57ba223c2ece1df66feb5af0"; + retval = base16_decode((char*)pub1.pubkey, sizeof(pub1.pubkey), + badkey, strlen(badkey)); + tt_int_op(retval, OP_EQ, sizeof(pub1.pubkey)); + tt_int_op(ed25519_validate_pubkey(&pub1), OP_EQ, -1); + } + + { /* This one is a good key */ + const char goodkey[] = + "4ba2e44760dff4c559ef3c38768c1c14a8a54740c782c8d70803e9d6e3ad8794"; + retval = base16_decode((char*)pub1.pubkey, sizeof(pub1.pubkey), + goodkey, strlen(goodkey)); + tt_int_op(retval, OP_EQ, sizeof(pub1.pubkey)); + tt_int_op(ed25519_validate_pubkey(&pub1), OP_EQ, 0); + } + + + done: ; +} + static void test_crypto_failure_modes(void *arg) { @@ -2918,6 +2983,7 @@ struct testcase_t crypto_tests[] = { ED25519_TEST(convert, 0), ED25519_TEST(blinding, 0), ED25519_TEST(testvectors, 0), + ED25519_TEST(validation, 0), { "ed25519_storage", test_crypto_ed25519_storage, 0, NULL, NULL }, { "siphash", test_crypto_siphash, 0, NULL, NULL }, { "failure_modes", test_crypto_failure_modes, TT_FORK, NULL, NULL },

1 0