commit 7ca470e13c70eaff483010e4b5c8f1f3076b3b7e Author: Nick Mathewson nickm@torproject.org Date: Sun Aug 31 19:39:43 2014 -0400
Add a reference implementation of our ed25519 modifications
Also, use it to generate test vectors, and add those test vectors to test_crypto.c
This is based on ed25519.py from the ed25519 webpage; the kludgy hacks are my own. --- src/test/ed25519_exts_ref.py | 206 ++++++++++++++++++++++++++++++++++++++++++ src/test/ed25519_vectors.inc | 112 +++++++++++++++++++++++ src/test/include.am | 3 +- src/test/slow_ed25519.py | 6 +- src/test/test_crypto.c | 67 ++++++++++++++ 5 files changed, 392 insertions(+), 2 deletions(-)
diff --git a/src/test/ed25519_exts_ref.py b/src/test/ed25519_exts_ref.py new file mode 100644 index 0000000..199e1e1 --- /dev/null +++ b/src/test/ed25519_exts_ref.py @@ -0,0 +1,206 @@ +#!/usr/bin/python +# Copyright 2014, The Tor Project, Inc +# See LICENSE for licensing information + +""" + Reference implementations for the ed25519 tweaks that Tor uses. + + Includes self-tester and test vector generator. +""" + +from slow_ed25519 import * + +import os +import random +import slownacl_curve25519 +import unittest +import binascii + +#define a synonym that doesn't look like 1 +ell = l + +# This replaces expmod above and makes it go a lot faster. +def expmod(b,e,m): + return pow(b,e,m) + +def curve25519ToEd25519(c, sign): + u = decodeint(c) + y = ((u - 1) * inv(u + 1)) % q + x = xrecover(y) + if x & 1 != sign: x = q-x + return encodepoint([x,y]) + +def blindESK(esk, param): + h = H("Derive temporary signing key" + param) + mult = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) + s = decodeint(esk[:32]) + s_prime = (s * mult) % ell + k = esk[32:] + assert(len(k) == 32) + k_prime = H("Derive temporary signing key hash input" + k)[:32] + return encodeint(s_prime) + k_prime + +def blindPK(pk, param): + h = H("Derive temporary signing key" + param) + mult = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) + P = decodepoint(pk) + return encodepoint(scalarmult(P, mult)) + +def expandSK(sk): + h = H(sk) + a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) + k = ''.join([h[i] for i in range(b/8,b/4)]) + assert len(k) == 32 + return encodeint(a)+k + +def publickeyFromESK(h): + a = decodeint(h[:32]) + A = scalarmult(B,a) + return encodepoint(A) + +def signatureWithESK(m,h,pk): + a = decodeint(h[:32]) + r = Hint(''.join([h[i] for i in range(b/8,b/4)]) + m) + R = scalarmult(B,r) + S = (r + Hint(encodepoint(R) + pk + m) * a) % l + return encodepoint(R) + encodeint(S) + +def newSK(): + return os.urandom(32) + +# ------------------------------------------------------------ + +MSG = "This is extremely silly. But it is also incredibly serious business!" + +class SelfTest(unittest.TestCase): + + def _testSignatures(self, esk, pk): + sig = signatureWithESK(MSG, esk, pk) + checkvalid(sig, MSG, pk) + bad = False + try: + checkvalid(sig, MSG*2, pk) + bad = True + except Exception: + pass + + self.failIf(bad) + + def testExpand(self): + sk = newSK() + pk = publickey(sk) + esk = expandSK(sk) + sig1 = signature(MSG, sk, pk) + sig2 = signatureWithESK(MSG, esk, pk) + self.assertEquals(sig1, sig2) + + def testSignatures(self): + sk = newSK() + esk = expandSK(sk) + pk = publickeyFromESK(esk) + pk2 = publickey(sk) + self.assertEquals(pk, pk2) + + self._testSignatures(esk, pk) + + def testDerivation(self): + priv = slownacl_curve25519.Private() + pub = priv.get_public() + + ed_pub0 = publickeyFromESK(priv.private) + sign = (ord(ed_pub0[31]) & 255) >> 7 + ed_pub1 = curve25519ToEd25519(pub.public, sign) + + self.assertEquals(ed_pub0, ed_pub1) + + def testBlinding(self): + sk = newSK() + esk = expandSK(sk) + pk = publickeyFromESK(esk) + param = os.urandom(32) + besk = blindESK(esk, param) + bpk = blindPK(pk, param) + bpk2 = publickeyFromESK(besk) + self.assertEquals(bpk, bpk2) + + self._testSignatures(besk, bpk) + +# ------------------------------------------------------------ + +# From pprint.pprint([ binascii.b2a_hex(os.urandom(32)) for _ in xrange(8) ]) +RAND_INPUTS = [ + '26c76712d89d906e6672dafa614c42e5cb1caac8c6568e4d2493087db51f0d36', + 'fba7a5366b5cb98c2667a18783f5cf8f4f8d1a2ce939ad22a6e685edde85128d', + '67e3aa7a14fac8445d15e45e38a523481a69ae35513c9e4143eb1c2196729a0e', + 'd51385942033a76dc17f089a59e6a5a7fe80d9c526ae8ddd8c3a506b99d3d0a6', + '5c8eac469bb3f1b85bc7cd893f52dc42a9ab66f1b02b5ce6a68e9b175d3bb433', + 'eda433d483059b6d1ff8b7cfbd0fe406bfb23722c8f3c8252629284573b61b86', + '4377c40431c30883c5fbd9bc92ae48d1ed8a47b81d13806beac5351739b5533d', + 'c6bbcce615839756aed2cc78b1de13884dd3618f48367a17597a16c1cd7a290b'] + +# From pprint.pprint([ binascii.b2a_hex(os.urandom(16)) for _ in xrange(8) ]) +BLINDING_PARAMS = [ + '54a513898b471d1d448a2f3c55c1de2c0ef718c447b04497eeb999ed32027823', + '831e9b5325b5d31b7ae6197e9c7a7baf2ec361e08248bce055908971047a2347', + 'ac78a1d46faf3bfbbdc5af5f053dc6dc9023ed78236bec1760dadfd0b2603760', + 'f9c84dc0ac31571507993df94da1b3d28684a12ad14e67d0a068aba5c53019fc', + 'b1fe79d1dec9bc108df69f6612c72812755751f21ecc5af99663b30be8b9081f', + '81f1512b63ab5fb5c1711a4ec83d379c420574aedffa8c3368e1c3989a3a0084', + '97f45142597c473a4b0e9a12d64561133ad9e1155fe5a9807fe6af8a93557818', + '3f44f6a5a92cde816635dfc12ade70539871078d2ff097278be2a555c9859cd0'] + +PREFIX = "ED25519_" + +def writeArray(name, array): + print "static const char *{prefix}{name}[] = {{".format( + prefix=PREFIX,name=name) + for a in array: + h = binascii.b2a_hex(a) + if len(h) > 70: + h1 = h[:70] + h2 = h[70:] + print ' "{0}"\n "{1}",'.format(h1,h2) + else: + print ' "{0}",'.format(h) + print "};\n" + +def makeTestVectors(): + secretKeys = [ binascii.a2b_hex(r) for r in RAND_INPUTS ] + writeArray("SECRET_KEYS", secretKeys) + + expandedSecretKeys = [ expandSK(sk) for sk in secretKeys ] + writeArray("EXPANDED_SECRET_KEYS", expandedSecretKeys) + + publicKeys = [ publickey(sk) for sk in secretKeys ] + writeArray("PUBLIC_KEYS", publicKeys) + + writeArray("CURVE25519_PUBLIC_KEYS", + (slownacl_curve25519.smult_curve25519_base(sk[:32]) + for sk in expandedSecretKeys)) + + blindingParams = [ binascii.a2b_hex(r) for r in BLINDING_PARAMS ] + writeArray("BLINDING_PARAMS", blindingParams) + + writeArray("BLINDED_SECRET_KEYS", + (blindESK(expandSK(sk), bp) + for sk,bp in zip(secretKeys,blindingParams))) + + writeArray("BLINDED_PUBLIC_KEYS", + (blindPK(pk, bp) for pk,bp in zip(publicKeys,blindingParams))) + + writeArray("SELF_SIGNATURES", + (signature(pk, sk, pk) for pk,sk in zip(publicKeys,secretKeys))) + + + +if __name__ == '__main__': + import sys + if len(sys.argv) == 1 or sys.argv[1] not in ("SelfTest", "MakeVectors"): + print "You should specify one of 'SelfTest' or 'MakeVectors'" + sys.exit(1) + if sys.argv[1] == 'SelfTest': + unittest.main() + else: + makeTestVectors() + + diff --git a/src/test/ed25519_vectors.inc b/src/test/ed25519_vectors.inc new file mode 100644 index 0000000..ef0a20b --- /dev/null +++ b/src/test/ed25519_vectors.inc @@ -0,0 +1,112 @@ +static const char *ED25519_SECRET_KEYS[] = { + "26c76712d89d906e6672dafa614c42e5cb1caac8c6568e4d2493087db51f0d36", + "fba7a5366b5cb98c2667a18783f5cf8f4f8d1a2ce939ad22a6e685edde85128d", + "67e3aa7a14fac8445d15e45e38a523481a69ae35513c9e4143eb1c2196729a0e", + "d51385942033a76dc17f089a59e6a5a7fe80d9c526ae8ddd8c3a506b99d3d0a6", + "5c8eac469bb3f1b85bc7cd893f52dc42a9ab66f1b02b5ce6a68e9b175d3bb433", + "eda433d483059b6d1ff8b7cfbd0fe406bfb23722c8f3c8252629284573b61b86", + "4377c40431c30883c5fbd9bc92ae48d1ed8a47b81d13806beac5351739b5533d", + "c6bbcce615839756aed2cc78b1de13884dd3618f48367a17597a16c1cd7a290b", +}; + +static const char *ED25519_EXPANDED_SECRET_KEYS[] = { + "c0a4de23cc64392d85aa1da82b3defddbea946d13bb053bf8489fa9296281f495022f1" + "f7ec0dcf52f07d4c7965c4eaed121d5d88d0a8ff546b06116a20e97755", + "18a8a69a06790dac778e882f7e868baacfa12521a5c058f5194f3a729184514a2a656f" + "e7799c3e41f43d756da8d9cd47a061316cfe6147e23ea2f90d1ca45f30", + "58d84f8862d2ecfa30eb491a81c36d05b574310ea69dae18ecb57e992a896656b98218" + "7ee96c15bf4caeeab2d0b0ae4cd0b8d17470fc7efa98bb26428f4ef36d", + "50702d20b3550c6e16033db5ad4fba16436f1ecc7485be6af62b0732ceb5d173c47ccd" + "9d044b6ea99dd99256adcc9c62191be194e7cb1a5b58ddcec85d876a2b", + "7077464c864c2ed5ed21c9916dc3b3ba6256f8b742fec67658d8d233dadc8d5a7a82c3" + "71083cc86892c2c8782dda2a09b6baf016aec51b689183ae59ce932ff2", + "8883c1387a6c86fc0bd7b9f157b4e4cd83f6885bf55e2706d2235d4527a2f05311a359" + "5953282e436df0349e1bb313a19b3ddbf7a7b91ecce8a2c34abadb38b3", + "186791ac8d03a3ac8efed6ac360467edd5a3bed2d02b3be713ddd5be53b3287ee37436" + "e5fd7ac43794394507ad440ecfdf59c4c255f19b768a273109e06d7d8e", + "b003077c1e52a62308eef7950b2d532e1d4a7eea50ad22d8ac11b892851f1c40ffb9c9" + "ff8dcd0c6c233f665a2e176324d92416bfcfcd1f787424c0c667452d86", +}; + +static const char *ED25519_PUBLIC_KEYS[] = { + "c2247870536a192d142d056abefca68d6193158e7c1a59c1654c954eccaff894", + "1519a3b15816a1aafab0b213892026ebf5c0dc232c58b21088d88cb90e9b940d", + "081faa81992e360ea22c06af1aba096e7a73f1c665bc8b3e4e531c46455fd1dd", + "73cfa1189a723aad7966137cbffa35140bb40d7e16eae4c40b79b5f0360dd65a", + "66c1a77104d86461b6f98f73acf3cd229c80624495d2d74d6fda1e940080a96b", + "d21c294db0e64cb2d8976625786ede1d9754186ae8197a64d72f68c792eecc19", + "c4d58b4cf85a348ff3d410dd936fa460c4f18da962c01b1963792b9dcc8a6ea6", + "95126f14d86494020665face03f2d42ee2b312a85bc729903eb17522954a1c4a", +}; + +static const char *ED25519_CURVE25519_PUBLIC_KEYS[] = { + "17ba77846e04c7ee5ca17cade774ac1884408f9701f439d4df32cbd8736c6a1f", + "022be2124bc1899a78ba2b4167d191af3b59cadf94f0382bc31ce183a117f161", + "bf4fd38ef22f718f03c0a12ba5127bd1e3afd494793753f519728b29cc577571", + "56c493e490261cef31633efd2461d2b896908e90459e4eecde950a895aef681d", + "089675a3e8ff2a7d8b2844a79269c95b7f97a4b8b5ea0cbeec669c6f2dea9b39", + "59e20dcb691c4a345fe86c8a79ac817e5b514d84bbf0512a842a08e43f7f087e", + "9e43b820b320eda35f66f122c155b2bf8e2192c468617b7115bf067d19e08369", + "861f33296cb57f8f01e4a5e8a7e5d5d7043a6247586ab36dea8a1a3c4403ee30", +}; + +static const char *ED25519_BLINDING_PARAMS[] = { + "54a513898b471d1d448a2f3c55c1de2c0ef718c447b04497eeb999ed32027823", + "831e9b5325b5d31b7ae6197e9c7a7baf2ec361e08248bce055908971047a2347", + "ac78a1d46faf3bfbbdc5af5f053dc6dc9023ed78236bec1760dadfd0b2603760", + "f9c84dc0ac31571507993df94da1b3d28684a12ad14e67d0a068aba5c53019fc", + "b1fe79d1dec9bc108df69f6612c72812755751f21ecc5af99663b30be8b9081f", + "81f1512b63ab5fb5c1711a4ec83d379c420574aedffa8c3368e1c3989a3a0084", + "97f45142597c473a4b0e9a12d64561133ad9e1155fe5a9807fe6af8a93557818", + "3f44f6a5a92cde816635dfc12ade70539871078d2ff097278be2a555c9859cd0", +}; + +static const char *ED25519_BLINDED_SECRET_KEYS[] = { + "014e83abadb2ca9a27e0ffe23920333d817729f48700e97656ec2823d694050e171d43" + "f24e3f53e70ec7ac280044ac77d4942dee5d6807118a59bdf3ee647e89", + "fad8cca0b4335847795288b1452508752b253e64e6c7c78d4a02dbbd7d46aa0eb8ceff" + "20dfcf53eb52b891fc078c934efbf0353af7242e7dc51bb32a093afa29", + "116eb0ae0a4a91763365bdf86db427b00862db448487808788cc339ac10e5e089217f5" + "2e92797462bd890fc274672e05c98f2c82970d640084781334aae0f940", + "bd1fbb0ee5acddc4adbcf5f33e95d9445f40326ce579fdd764a24483a9ccb20f509ece" + "e77082ce088f7c19d5a00e955eeef8df6fa41686abc1030c2d76807733", + "237f5345cefe8573ce9fa7e216381a1172796c9e3f70668ab503b1352952530fb57b95" + "a440570659a440a3e4771465022a8e67af86bdf2d0990c54e7bb87ff9a", + "ba8ff23bc4ad2b739e1ccffc9fbc7837053ea81cdfdb15073f56411cfbae1d0ec492fc" + "87d5ec2a1b185ca5a40541fdef0b1e128fd5c2380c888bfa924711bcab", + "0fa68f969de038c7a90a4a74ee6167c77582006f2dedecc1956501ba6b6fb10391b476" + "8f8e556d78f4bdcb9a13b6f6066fe81d3134ae965dc48cd0785b3af2b8", + "deaa3456d1c21944d5dcd361a646858c6cf9336b0a6851d925717eb1ae186902053d9c" + "00c81e1331c06ab50087be8cfc7dc11691b132614474f1aa9c2503cccd", +}; + +static const char *ED25519_BLINDED_PUBLIC_KEYS[] = { + "722d6da6348e618967ef782e71061e27163a8b35f21856475d9d2023f65b6495", + "1dffa0586da6cbfcff2024eedf4fc6c818242d9a82dbbe635d6da1b975a1160d", + "5ed81f98fed5a6acda4ea6da2c34fab0ab359d950c510c256473f1f33ff438b4", + "6e6f92a54fb282120c46d9603df41135f025bc1f58f283809d04be96aeb04040", + "cda236f28edc4c7e02d18007b8dab49d669265b0f7aefb1824d7cc8e73a2cd63", + "367b03b17b67ca7329b89a520bdab91782402a41cd67264e34b5541a4b3f875b", + "8d486b03ac4e3b486b7a1d563706c7fdac75aee789a7cf6f22789eedeff61a31", + "9f297ff0aa2ceda91c5ab1b6446f12533d145940de6d850dc323417afde0cb78", +}; + +static const char *ED25519_SELF_SIGNATURES[] = { + "d23188eac3773a316d46006fa59c095060be8b1a23582a0dd99002a82a0662bd246d84" + "49e172e04c5f46ac0d1404cebe4aabd8a75a1457aa06cae41f3334f104", + "3a785ac1201c97ee5f6f0d99323960d5f264c7825e61aa7cc81262f15bef75eb4fa572" + "3add9b9d45b12311b6d403eb3ac79ff8e4e631fc3cd51e4ad2185b200b", + "cf431fd0416bfbd20c9d95ef9b723e2acddffb33900edc72195dea95965d52d888d30b" + "7b8a677c0bd8ae1417b1e1a0ec6700deadd5d8b54b6689275e04a04509", + "2375380cd72d1a6c642aeddff862be8a5804b916acb72c02d9ed052c1561881aa658a5" + "af856fcd6d43113e42f698cd6687c99efeef7f2ce045824440d26c5d00", + "2385a472f599ca965bbe4d610e391cdeabeba9c336694b0d6249e551458280be122c24" + "41dd9746a81bbfb9cd619364bab0df37ff4ceb7aefd24469c39d3bc508", + "e500cd0b8cfff35442f88008d894f3a2fa26ef7d3a0ca5714ae0d3e2d40caae58ba7cd" + "f69dd126994dad6be536fcda846d89dd8138d1683cc144c8853dce7607", + "d187b9e334b0050154de10bf69b3e4208a584e1a65015ec28b14bcc252cf84b8baa9c9" + "4867daa60f2a82d09ba9652d41e8dde292b624afc8d2c26441b95e3c0e", + "815213640a643d198bd056e02bba74e1c8d2d931643e84497adf3347eb485079c9afe0" + "afce9284cdc084946b561abbb214f1304ca11228ff82702185cf28f60d", +}; + diff --git a/src/test/include.am b/src/test/include.am index d5163aa..3fecbbd 100644 --- a/src/test/include.am +++ b/src/test/include.am @@ -73,7 +73,8 @@ src_test_bench_LDADD = src/or/libtor.a src/common/libor.a \
noinst_HEADERS+= \ src/test/test.h \ - src/test/test_descriptors.inc + src/test/test_descriptors.inc \ + src/test/ed25519_vectors.inc
if CURVE25519_ENABLED noinst_PROGRAMS+= src/test/test-ntor-cl diff --git a/src/test/slow_ed25519.py b/src/test/slow_ed25519.py index 3380079..f44708b 100644 --- a/src/test/slow_ed25519.py +++ b/src/test/slow_ed25519.py @@ -2,7 +2,11 @@ # http://ed25519.cr.yp.to/python/ed25519.py . # It is in the public domain. # -# It isn't constant-time. Don't use it except for testing. +# It isn't constant-time. Don't use it except for testing. Also, see +# warnings about how very slow it is. Only use this for generating +# test vectors, I'd suggest. +# +# Don't edit this file. Mess with ed25519_ref.py
import hashlib
diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c index d4478d5..6c2258e 100644 --- a/src/test/test_crypto.c +++ b/src/test/test_crypto.c @@ -13,6 +13,7 @@ #ifdef CURVE25519_ENABLED #include "crypto_curve25519.h" #include "crypto_ed25519.h" +#include "ed25519_vectors.inc" #endif
extern const char AUTHORITY_SIGNKEY_3[]; @@ -1456,6 +1457,71 @@ test_crypto_ed25519_blinding(void *arg) }
static void +test_crypto_ed25519_testvectors(void *arg) +{ + unsigned i; + char *mem_op_hex_tmp = NULL; + (void)arg; + + for (i = 0; i < ARRAY_LENGTH(ED25519_SECRET_KEYS); ++i) { + uint8_t sk[32]; + ed25519_secret_key_t esk; + ed25519_public_key_t pk, blind_pk, pkfromcurve; + ed25519_keypair_t keypair, blind_keypair; + curve25519_keypair_t curvekp; + uint8_t blinding_param[32]; + ed25519_signature_t sig; + int sign; + +#define DECODE(p,s) base16_decode((char*)(p),sizeof(p),(s),strlen(s)) +#define EQ(a,h) test_memeq_hex((const char*)(a), (h)) + + tt_int_op(0, ==, DECODE(sk, ED25519_SECRET_KEYS[i])); + tt_int_op(0, ==, DECODE(blinding_param, ED25519_BLINDING_PARAMS[i])); + + tt_int_op(0, ==, ed25519_secret_key_from_seed(&esk, sk)); + EQ(esk.seckey, ED25519_EXPANDED_SECRET_KEYS[i]); + + tt_int_op(0, ==, ed25519_public_key_generate(&pk, &esk)); + EQ(pk.pubkey, ED25519_PUBLIC_KEYS[i]); + + memcpy(&curvekp.seckey.secret_key, esk.seckey, 32); + curve25519_public_key_generate(&curvekp.pubkey, &curvekp.seckey); + + tt_int_op(0, ==, + ed25519_keypair_from_curve25519_keypair(&keypair, &sign, &curvekp)); + tt_int_op(0, ==, ed25519_public_key_from_curve25519_public_key( + &pkfromcurve, &curvekp.pubkey, sign)); + tt_mem_op(keypair.pubkey.pubkey, ==, pkfromcurve.pubkey, 32); + EQ(curvekp.pubkey.public_key, ED25519_CURVE25519_PUBLIC_KEYS[i]); + + /* Self-signing */ + memcpy(&keypair.seckey, &esk, sizeof(esk)); + memcpy(&keypair.pubkey, &pk, sizeof(pk)); + + tt_int_op(0, ==, ed25519_sign(&sig, pk.pubkey, 32, &keypair)); + + EQ(sig.sig, ED25519_SELF_SIGNATURES[i]); + + /* Blinding */ + tt_int_op(0, ==, + ed25519_keypair_blind(&blind_keypair, &keypair, blinding_param)); + tt_int_op(0, ==, + ed25519_public_blind(&blind_pk, &pk, blinding_param)); + + EQ(blind_keypair.seckey.seckey, ED25519_BLINDED_SECRET_KEYS[i]); + EQ(blind_pk.pubkey, ED25519_BLINDED_PUBLIC_KEYS[i]); + + tt_mem_op(blind_pk.pubkey, ==, blind_keypair.pubkey.pubkey, 32); + +#undef DECODE +#undef EQ + } + done: + tor_free(mem_op_hex_tmp); +} + +static void test_crypto_siphash(void *arg) { /* From the reference implementation, taking @@ -1597,6 +1663,7 @@ struct testcase_t crypto_tests[] = { { "ed25519_encode", test_crypto_ed25519_encode, 0, NULL, NULL }, { "ed25519_convert", test_crypto_ed25519_convert, 0, NULL, NULL }, { "ed25519_blinding", test_crypto_ed25519_blinding, 0, NULL, NULL }, + { "ed25519_testvectors", test_crypto_ed25519_testvectors, 0, NULL, NULL }, #endif { "siphash", test_crypto_siphash, 0, NULL, NULL }, END_OF_TESTCASES