{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Multiparty One-Way Hash Chains Explained\n",
"\n",
"[Hash chains](https://en.wikipedia.org/wiki/Hash_chain) 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](https://www.rfc-editor.org/info/rfc4082) scheme and friends use hash chains at their core and provide authentication in wireless sensor networks and satellite communication.\n",
"\n",
"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](https://sepior.com/) and [Unbound](https://github.com/unboundsecurity) do using threshold cryptography and MPC-based hardware security modules (HSMs).\n",
"\n",
"## Hash Chains\n",
"\n",
"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).\n",
"\n",
"The **[Lamport](https://en.wikipedia.org/wiki/Leslie_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.\n",
"\n",
"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*.\n",
"\n",
"## A Multiparty One-Way Function\n",
"\n",
"Taking advantage of the MPyC [AES demo](https://github.com/lschoe/mpyc/blob/master/demos/aes.py), we obtain an MPyC program for a secure one-way function with almost no effort. "
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import aes # Provides AES key expansion and AES encryption, using 4x4 arrays over GF(256)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We take the well-known **[Matyas-Meyer-Oseas](https://en.wikipedia.org/wiki/One-way_compression_function#Matyas–Meyer–Oseas)** one-way function $f:\\{0,1\\}^{128}\\rightarrow\\{0,1\\}^{128}$ defined as \n",
"\n",
"$$f(x)= \\textrm{AES}_{\\textrm{IV}}(x) \\oplus x$$\n",
"\n",
"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](https://en.wikipedia.org/wiki/Weak_key) are known for AES. We take:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"IV = [[aes.secfld(3)] * 4] * 4 # IV as a 4x4 array of GF(256) elements"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"K = aes.key_expansion(IV)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's take a look at the resulting AES key schedule, which is not secret anyway:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"K0 03030303030303030303030303030303\n",
"K1 797878787a7b7b7b797878787a7b7b7b\n",
"K2 5a5959a2202222d9595a5aa1232121da\n",
"K3 a3a40e8483862c5ddadc76fcf9fd5726\n",
"K4 fffff91d7c79d540a6a5a3bc5f58f49a\n",
"K5 854041d2f93994925f9c372e00c4c3b4\n",
"K6 b96eccb1405758231fcb6f0d1f0facb9\n",
"K7 8fff9a71cfa8c252d063ad5fcf6c01e6\n",
"K8 5f8314fb902bd6a940487bf68f247a10\n",
"K9 7259de88e2720821a23a73d72d1e09c7\n",
"K10 36581850d42a1071761063a65b0e6a61\n"
]
}
],
"source": [
"for i, k in enumerate(K):\n",
" await aes.xprint(f'K{i:<2}', k)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And with this we are ready to define our MPyC one-way function `f()` as follows:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"f = lambda x: aes.mpc.matrix_add(aes.encrypt(K, x), x)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Multiparty Hash Chain Reversal\n",
"\n",
"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. \n",
"\n",
"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](https://www.win.tue.nl/~berry/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. \n",
"\n",
"We basically copy the [Python code for binary pebbling](https://www.win.tue.nl/~berry/pebbling/src/python/BinaryPebbling.html), which makes judicious use of [Python generators](https://docs.python.org/tutorial/classes.html#generators). The hash function is replaced with the MPyC one-way function `f()` defined above:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"import itertools\n",
"\n",
"# 'magic' formula for optimal schedule for binary pebbling\n",
"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\n",
"\n",
"def P(k, x): # Recursive pebbler outputs {f^i(x)}_{i=0}^{n-1} in reverse, n=2^k.\n",
" y = [None]*k + [x]\n",
" i = k; g = 0\n",
" for r in range(1, 2**k):\n",
" for _ in range(tS(k, r)):\n",
" z = y[i]\n",
" if g == 0: i -= 1; g = 2**i\n",
" y[i] = f(z)\n",
" g -= 1\n",
" yield\n",
" yield y[0]\n",
" for v in itertools.zip_longest(*(P(i-1, y[i]) for i in range(1, k+1))):\n",
" yield next(filter(None, v))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Order-0 hash chain of length 1 (1 rounds):\n",
" 1 x0 = 604fc4433bbbba2e5c4796510010ed48\n",
"\n",
"Order-1 hash chain of length 2 (3 rounds):\n",
" 1 -\n",
" 2 x1 = fe242be2c20da3cd87370d1614277d0d\n",
" 3 x0 = 604fc4433bbbba2e5c4796510010ed48\n",
"\n",
"Order-2 hash chain of length 4 (7 rounds):\n",
" 1 -\n",
" 2 -\n",
" 3 -\n",
" 4 x3 = fb38d81680a23a43d8063ee81de10c90\n",
" 5 x2 = 8b613cbcfaa17ff36b1823d599f535e2\n",
" 6 x1 = fe242be2c20da3cd87370d1614277d0d\n",
" 7 x0 = 604fc4433bbbba2e5c4796510010ed48\n",
"\n",
"Order-3 hash chain of length 8 (15 rounds):\n",
" 1 -\n",
" 2 -\n",
" 3 -\n",
" 4 -\n",
" 5 -\n",
" 6 -\n",
" 7 -\n",
" 8 x7 = 104a0c631c5a3fdac68ddc47dc140bce\n",
" 9 x6 = a5a807b0270387b6a599545bf23a455c\n",
"10 x5 = 74ba842fc3c53005b3ba4a3d56ae3228\n",
"11 x4 = 5f6d0953546e5fbdc4a4c1f3cd1dd380\n",
"12 x3 = fb38d81680a23a43d8063ee81de10c90\n",
"13 x2 = 8b613cbcfaa17ff36b1823d599f535e2\n",
"14 x1 = fe242be2c20da3cd87370d1614277d0d\n",
"15 x0 = 604fc4433bbbba2e5c4796510010ed48\n",
"\n"
]
}
],
"source": [
"x0 = [[aes.mpc.random.getrandbits(aes.secfld, 8) for _ in range(4)] for _ in range(4)] # random seed\n",
"for k in range(4):\n",
" print(f'Order-{k} hash chain of length {2**k} ({2**(k+1) - 1} rounds):')\n",
" r = 1 # round number\n",
" for v in P(k, x0): \n",
" if v is None:\n",
" print(f'{r:2}', '-') # initial stage\n",
" else:\n",
" await aes.xprint(f'{r:2} x{2**(k+1) - 1 - r:<2}=', v) # output stage\n",
" r += 1\n",
" print()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Python program [onewayhashchains.py](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](np_onewayhashchains.py) demos the use of the faster Numpy-based [np_aes.py](np_aes.py) reimplementation of the AES demo as well as the use of the Numpy-based [sha3.py](sha3.py) threshold SHA-3 hash functions."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 2
}