commit 19e3c5fc4cb54f044ab1015232969c0401b6ab1a Author: George Kadianakis <desnacked@riseup.net> Date: Mon Oct 7 13:21:23 2019 +0300 Add reference implementation for ed25519 key blinding. This is straight from little-t-tor (see #31912). We need this specific implementation because we can't do v3 key blinding with hazmat or pynacl, since they don't expose the primitives we need. So we are gonna use this simple ed25519 implementation to do key blinding when needed (it's very rarely needed so it's not affecting performance). --- stem/descriptor/ed25519_exts_ref.py | 235 ++++++++++++++++++++++++++++++++++++ stem/descriptor/slow_ed25519.py | 114 +++++++++++++++++ 2 files changed, 349 insertions(+) diff --git a/stem/descriptor/ed25519_exts_ref.py b/stem/descriptor/ed25519_exts_ref.py new file mode 100644 index 00000000..8e622eb3 --- /dev/null +++ b/stem/descriptor/ed25519_exts_ref.py @@ -0,0 +1,235 @@ +#!/usr/bin/python +# Copyright 2014-2019, 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 . import slow_ed25519 +from .slow_ed25519 import * + +import os +import random +import unittest +import binascii +import textwrap + +#define a synonym that doesn't look like 1 +ell = l + +# This replaces expmod above and makes it go a lot faster. +slow_ed25519.expmod = pow + +def blindESK(esk, param): + mult = 2**(b-2) + sum(2**i * bit(param,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(b"Derive temporary signing key hash input" + k)[:32] + return encodeint(s_prime) + k_prime + +def blindPK(pk, param): + mult = 2**(b-2) + sum(2**i * bit(param,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 = b''.join([bytes([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(b''.join([bytes([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) + +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 = b"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.assertFalse(bad) + + def testExpand(self): + sk = newSK() + pk = publickey(sk) + esk = expandSK(sk) + sig1 = signature(MSG, sk, pk) + sig2 = signatureWithESK(MSG, esk, pk) + self.assertEqual(sig1, sig2) + + def testSignatures(self): + sk = newSK() + esk = expandSK(sk) + pk = publickeyFromESK(esk) + pk2 = publickey(sk) + self.assertEqual(pk, pk2) + + self._testSignatures(esk, pk) + + 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.assertEqual(bpk, bpk2) + + 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 == [0,1]) + + # 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) ]) +RAND_INPUTS = [ + '26c76712d89d906e6672dafa614c42e5cb1caac8c6568e4d2493087db51f0d36', + 'fba7a5366b5cb98c2667a18783f5cf8f4f8d1a2ce939ad22a6e685edde85128d', + '67e3aa7a14fac8445d15e45e38a523481a69ae35513c9e4143eb1c2196729a0e', + 'd51385942033a76dc17f089a59e6a5a7fe80d9c526ae8ddd8c3a506b99d3d0a6', + '5c8eac469bb3f1b85bc7cd893f52dc42a9ab66f1b02b5ce6a68e9b175d3bb433', + 'eda433d483059b6d1ff8b7cfbd0fe406bfb23722c8f3c8252629284573b61b86', + '4377c40431c30883c5fbd9bc92ae48d1ed8a47b81d13806beac5351739b5533d', + 'c6bbcce615839756aed2cc78b1de13884dd3618f48367a17597a16c1cd7a290b'] + +# From pprint.pprint([ binascii.b2a_hex(os.urandom(32)) 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 = a.hex() + 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 comment(text, initial="/**"): + print(initial) + print(textwrap.fill(text,initial_indent=" * ",subsequent_indent=" * ")) + print(" */") + +def makeTestVectors(): + comment("""Test vectors for our ed25519 implementation and related + functions. These were automatically generated by the + ed25519_exts_ref.py script.""", initial="/*") + + + comment("""Secret key seeds used as inputs for the ed25519 test vectors. + Randomly generated. """) + secretKeys = [ bytes.fromhex(r) for r in RAND_INPUTS ] + writeArray("SECRET_KEYS", secretKeys) + + comment("""Secret ed25519 keys after expansion from seeds. This is how Tor + represents them internally.""") + expandedSecretKeys = [ expandSK(sk) for sk in secretKeys ] + writeArray("EXPANDED_SECRET_KEYS", expandedSecretKeys) + + comment("""Public keys derived from the above secret keys""") + publicKeys = [ publickey(sk) for sk in secretKeys ] + writeArray("PUBLIC_KEYS", publicKeys) + + comment("""Parameters used for key blinding tests. Randomly generated.""") + blindingParams = [ binascii.a2b_hex(r) for r in BLINDING_PARAMS ] + writeArray("BLINDING_PARAMS", blindingParams) + + comment("""Blinded secret keys for testing key blinding. The nth blinded + key corresponds to the nth secret key blidned with the nth + blinding parameter.""") + writeArray("BLINDED_SECRET_KEYS", + (blindESK(expandSK(sk), bp) + for sk,bp in zip(secretKeys,blindingParams))) + + comment("""Blinded public keys for testing key blinding. The nth blinded + key corresponds to the nth public key blidned with the nth + blinding parameter.""") + writeArray("BLINDED_PUBLIC_KEYS", + (blindPK(pk, bp) for pk,bp in zip(publicKeys,blindingParams))) + + comment("""Signatures of the public keys, made with their corresponding + secret keys.""") + 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/stem/descriptor/slow_ed25519.py b/stem/descriptor/slow_ed25519.py new file mode 100644 index 00000000..ba2766ba --- /dev/null +++ b/stem/descriptor/slow_ed25519.py @@ -0,0 +1,114 @@ +# This is the ed25519 implementation from +# 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. 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 + +b = 256 +q = 2**255 - 19 +l = 2**252 + 27742317777372353535851937790883648493 + +def H(m): + return hashlib.sha512(m).digest() + +def expmod(b,e,m): + if e == 0: return 1 + t = expmod(b,e//2,m)**2 % m + if e & 1: t = (t*b) % m + return t + +def inv(x): + return expmod(x,q-2,q) + +d = -121665 * inv(121666) +I = expmod(2,(q-1)//4,q) + +def xrecover(y): + xx = (y*y-1) * inv(d*y*y+1) + x = expmod(xx,(q+3)//8,q) + if (x*x - xx) % q != 0: x = (x*I) % q + if x % 2 != 0: x = q-x + return x + +By = 4 * inv(5) +Bx = xrecover(By) +B = [Bx % q,By % q] + +def edwards(P,Q): + x1 = P[0] + y1 = P[1] + x2 = Q[0] + y2 = Q[1] + x3 = (x1*y2+x2*y1) * inv(1+d*x1*x2*y1*y2) + y3 = (y1*y2+x1*x2) * inv(1-d*x1*x2*y1*y2) + return [x3 % q,y3 % q] + +def scalarmult(P,e): + if e == 0: return [0,1] + Q = scalarmult(P,e//2) + Q = edwards(Q,Q) + if e & 1: Q = edwards(Q,P) + return Q + +def encodeint(y): + bits = [(y >> i) & 1 for i in range(b)] + return b''.join([bytes([sum([bits[i * 8 + j] << j for j in range(8)])]) for i in range(b//8)]) + +def encodepoint(P): + x = P[0] + y = P[1] + bits = [(y >> i) & 1 for i in range(b - 1)] + [x & 1] + return b''.join([bytes([sum([bits[i * 8 + j] << j for j in range(8)])]) for i in range(b//8)]) + +def bit(h,i): + return (h[i//8] >> (i%8)) & 1 + +def publickey(sk): + h = H(sk) + a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) + A = scalarmult(B,a) + return encodepoint(A) + +def Hint(m): + h = H(m) + return sum(2**i * bit(h,i) for i in range(2*b)) + +def signature(m,sk,pk): + h = H(sk) + a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) + r = Hint(b''.join([bytes([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 isoncurve(P): + x = P[0] + y = P[1] + return (-x*x + y*y - 1 - d*x*x*y*y) % q == 0 + +def decodeint(s): + return sum(2**i * bit(s,i) for i in range(0,b)) + +def decodepoint(s): + y = sum(2**i * bit(s,i) for i in range(0,b-1)) + x = xrecover(y) + if x & 1 != bit(s,b-1): x = q-x + P = [x,y] + if not isoncurve(P): raise Exception("decoding point that is not on curve") + return P + +def checkvalid(s,m,pk): + if len(s) != b//4: raise Exception("signature length is wrong") + if len(pk) != b//8: raise Exception("public-key length is wrong") + R = decodepoint(s[0:b//8]) + A = decodepoint(pk) + S = decodeint(s[b//8:b//4]) + h = Hint(encodepoint(R) + pk + m) + if scalarmult(B,S) != edwards(R,scalarmult(A,h)): + raise Exception("signature does not pass verification")