Hash chains are well-known as a simple and efficient solution for asymmetric identification and authentication. They appear in many guises, often in contexts with severe performance constraints. For example, the TESLA scheme and friends use hash chains at their core and provide authentication in wireless sensor networks and satellite communication.
In this notebook we construct an MPyC program for handling hash chains in a multiparty setting. There will be no single point of failure, as no single party will ever know the secret information from which the hash chains are built. This way of protecting secret keys is similar to what companies like Sepior and Unbound do using threshold cryptography and MPC-based hardware security modules (HSMs).
A one-way hash chain of length $n$ is essentially a sequence of values $\{x_i\}_{i=0}^{n-1}$, satisfying $x_{i+1}=f(x_i)$, where $f:\{0,1\}^{128}\rightarrow\{0,1\}^{128}$ is a one-way function (128-bit security level, for concreteness).
The Lamport identification scheme lets a prover generate a hash chain $\{x_i\}_{i=0}^{n-1}$ with seed $x_0$ chosen uniformly at random in $\{0,1\}^{128}$. The prover registers $v=x_{n-1}$ with a verifier, after which the prover is set up to perform $n-1$ rounds of identification as follows. The first time the prover wishes to identify itself to the verifier it sends $x_{n-2}$; the verifier checks that $f(x_{n-2})=v$ holds. If so, identification succeeded and the verifier keeps $v=x_{n-2}$. The next time the prover will send $x_{n-3}$ to the verifier who checks $f(x_{n-3})=v$ and keeps $v=x_{n-3}$ upon success. And so on, until the prover sends $x_0$ in the last round of identification---at which point the hash chain is exhausted.
Lamport identification is asymmetric in the sense that the information held by the verifier does not need to be kept secret. In other words, the initial value $v=x_{n-1}$ can be seen as the public key of the prover. The value $x_0$ is the corresponding private key.
Taking advantage of the MPyC AES demo, we obtain an MPyC program for a secure one-way function with almost no effort.
import aes # Provides AES key expansion and AES encryption, using 4x4 arrays over GF(256).
We take the well-known Matyas-Meyer-Oseas one-way function $f:\{0,1\}^{128}\rightarrow\{0,1\}^{128}$ defined as
$$f(x)= \textrm{AES}_{\textrm{IV}}(x) \oplus x$$The 128-bit string IV is used as fixed key for the AES block cipher. The string IV is public and can be chosen arbitrarily, as no weak keys are known for AES. We take:
IV = [[aes.secfld(3)] * 4] * 4 # IV as a 4x4 array of GF(256) elements
The elements of IV are of type aes.secfld to ensure that we can use it as input to the aes.key_expansion() function. The use of MPC for key expansion is overkill for the publicly known key IV, but it does not hurt the performance too much because it is only run once:
K = aes.key_expansion(IV)
Let's take a look at the resulting AES key schedule, which is not secret anyway:
for i, k in enumerate(K):
await aes.xprint(f'K{i:<2}', k)
K0 03030303030303030303030303030303 K1 797878787a7b7b7b797878787a7b7b7b K2 5a5959a2202222d9595a5aa1232121da K3 a3a40e8483862c5ddadc76fcf9fd5726 K4 fffff91d7c79d540a6a5a3bc5f58f49a K5 854041d2f93994925f9c372e00c4c3b4 K6 b96eccb1405758231fcb6f0d1f0facb9 K7 8fff9a71cfa8c252d063ad5fcf6c01e6 K8 5f8314fb902bd6a940487bf68f247a10 K9 7259de88e2720821a23a73d72d1e09c7 K10 36581850d42a1071761063a65b0e6a61
And with this we are ready to define our MPyC one-way function f() as follows:
f = lambda x: aes.mpc.matrix_add(aes.encrypt(K, x), x)
Evaluation of y = f(x) will be done on secure GF(256) elements throughout, ensuring that no single party will learn x, y, nor any other information pertaining to these values.
Using function $f$, we will now generate one-way hash chains in a secure way, such that the initial seed value $x_0$ as well as all other values on the chain will be secret-shared when the program is run in a multiparty setting. Moreover, we will also traverse the so-generated hash chain in the reverse order, operating on secret-shared values throughout the entire process.
The traversal of the hash chain in reverse corresponds to the way a hash chain is used in the Lamport identification scheme, first revealing $x_{n-1}$, then $x_{n-2}$, and so on, until $x_0$ is revealed at the end. To reverse one-way hash chain efficiently, we use algorithms for optimal binary pebbling. This way, we will only use at most $\lceil k/2\rceil$ hashes (applications of $f$) in any identification round, while limiting the storage to $k+1$ hash values at any time.
We basically copy the Python code for binary pebbling, which makes judicious use of Python generators. The hash function is replaced with the MPyC one-way function f() defined above:
import itertools
# 'magic' formula for optimal schedule for binary pebbling
tS = lambda k, r: 0 if r < 2**(k-1) else ((k+r)%2+ k+1 - ((2*r)%(2**(2**k-r).bit_length())).bit_length()) // 2
def P(k, x): # Recursive pebbler outputs {f^i(x)}_{i=0}^{n-1} in reverse, n=2^k.
y = [None]*k + [x]
i = k; g = 0
for r in range(1, 2**k):
for _ in range(tS(k, r)):
z = y[i]
if g == 0: i -= 1; g = 2**i
y[i] = f(z)
g -= 1
yield
yield y[0]
for v in itertools.zip_longest(*(P(i-1, y[i]) for i in range(1, k+1))):
yield next(filter(None, v))
We test the MPyC program for hash chains of lengths 1, 2, 4, and 8, using the function getrandbits() from the mpyc.random module to generate uniformly random secret-shared GF(256) elements for the seeds of the chains. For the purpose of demonstration, the seed x0 is reused, such that the hash chains share a common prefix.
x0 = [[aes.mpc.random.getrandbits(aes.secfld, 8) for _ in range(4)] for _ in range(4)] # random seed
for k in range(4):
print(f'Order-{k} hash chain of length {2**k} ({2**(k+1) - 1} rounds):')
r = 1 # round number
for v in P(k, x0):
if v is None:
print(f'{r:2}', '-') # initial stage
else:
await aes.xprint(f'{r:2} x{2**(k+1) - 1 - r:<2}=', v) # output stage
r += 1
print()
Order-0 hash chain of length 1 (1 rounds): 1 x0 = 604fc4433bbbba2e5c4796510010ed48 Order-1 hash chain of length 2 (3 rounds): 1 - 2 x1 = fe242be2c20da3cd87370d1614277d0d 3 x0 = 604fc4433bbbba2e5c4796510010ed48 Order-2 hash chain of length 4 (7 rounds): 1 - 2 - 3 - 4 x3 = fb38d81680a23a43d8063ee81de10c90 5 x2 = 8b613cbcfaa17ff36b1823d599f535e2 6 x1 = fe242be2c20da3cd87370d1614277d0d 7 x0 = 604fc4433bbbba2e5c4796510010ed48 Order-3 hash chain of length 8 (15 rounds): 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 x7 = 104a0c631c5a3fdac68ddc47dc140bce 9 x6 = a5a807b0270387b6a599545bf23a455c 10 x5 = 74ba842fc3c53005b3ba4a3d56ae3228 11 x4 = 5f6d0953546e5fbdc4a4c1f3cd1dd380 12 x3 = fb38d81680a23a43d8063ee81de10c90 13 x2 = 8b613cbcfaa17ff36b1823d599f535e2 14 x1 = fe242be2c20da3cd87370d1614277d0d 15 x0 = 604fc4433bbbba2e5c4796510010ed48
The Python program onewayhashchains.py follows the same approach as presented in this notebook. In addition to the recursive pebbler shown above, however, the optimal binary pebbler is also implemented as an iterative algorithm. Moreover, np_onewayhashchains.py demos the use of the faster Numpy-based np_aes.py reimplementation of the AES demo as well as the use of the Numpy-based sha3.py threshold SHA-3 hash functions.