SHA1 computation with Modules
This document demonstrates the use of Modules in Concrete through a SHA1 computation example. SHA1 is a deprecated and broken hash function; we use it here for pedagogical purposes, not for its security.
The SHA1 code is available here. Execution times for the different functions are provided in the final section. We created our example by forking python-sha1 by AJ Alt and made extensive modifications to implement SHA1 in FHE and corresponding tests.
SHA1 overview
SHA1 is a deprecated broken hash function defined by NIST in 1995: You can find detailed information on SHA1 on its Wikipedia page or in its official description. We follow the structure of its pseudo-code in our implementation.
Our FHE implementation
In our implementation, only the compression function is implemented in FHE, corresponding to the
_process_encrypted_chunk_server_side function. The rest is done client-side in the clear,
including the message expansion. While more of the process could be done in FHE, this tutorial
focuses on demonstrating the use of Modules.
Our Module contains 7 functions which can be combined together:
xor3XORs three values togetherifterncomputes the ternary IF, i.e., c ? t : fmajcomputes the majority functionrotate30rotates a 32-bit word by 30 positionsrotate5rotates a 32-bit word by 5 positionsadd2adds two values togetheradd5adds five values together
@fhe.module()
class MyModule:
@fhe.function({"x": "encrypted", "y": "encrypted", "z": "encrypted"})
def xor3(x, y, z):
return x ^ y ^ z
@fhe.function({"x": "encrypted", "y": "encrypted", "z": "encrypted"})
def iftern(x, y, z):
return z ^ (x & (y ^ z))
@fhe.function({"x": "encrypted", "y": "encrypted", "z": "encrypted"})
def maj(x, y, z):
return (x & y) | (z & (x | y))
@fhe.function({"x": "encrypted"})
def rotate30(x):
ans = fhe.zeros((32,))
ans[30:32] = x[0:2]
ans[0:30] = x[2:32]
return ans
@fhe.function({"x": "encrypted"})
def rotate5(x):
ans = fhe.zeros((32,))
ans[5:32] = x[0:27]
ans[0:5] = x[27:32]
return ans
@fhe.function({"x": "encrypted", "y": "encrypted"})
def add2(x, y):
return fhe.bits(add_chunked_number(x, y))[0]
@fhe.function(
{"x": "encrypted", "y": "encrypted", "u": "encrypted", "v": "encrypted", "w": "encrypted"}
)
def add5(x, y, u, v, w):
result = add_chunked_number(x, y)
result = add_chunked_number(result, u)
result = add_chunked_number(result, v)
result = add_chunked_number(result, w)
return fhe.bits(result)[0]
We then compile this Module, setting p_error=10**-8 as a very small value to avoid computation
errors. The Module feature allows the combination of all these functions so that the outputs of
some to be used as inputs for others. This makes it convenient to create larger functions with
some control flow (conditions, branches, loops) handled in the clear while using these smaller
functions. In our case, this is done in the _process_encrypted_chunk_server_side function.
Details of _process_encrypted_chunk_server_side
_process_encrypted_chunk_server_side uses encrypted inputs and returns encrypted values. In the
clear, all variables are 32-bit words, but here they are represented as 32 encrypted bits to
simplify and accelerate the non-linear operations in SHA1.
Then, we have the main loop of the compression function:
for i in range(80):
if 0 <= i <= 19:
# Do f = d ^ (b & (c ^ d))
fsplit_enc = my_module.iftern.run(bsplit_enc, csplit_enc, dsplit_enc)
ksplit = split(0x5A827999)
elif 20 <= i <= 39:
# Do f = b ^ c ^ d
fsplit_enc = my_module.xor3.run(bsplit_enc, csplit_enc, dsplit_enc)
ksplit = split(0x6ED9EBA1)
elif 40 <= i <= 59:
# Do f = (b & c) | (b & d) | (c & d)
fsplit_enc = my_module.maj.run(bsplit_enc, csplit_enc, dsplit_enc)
ksplit = split(0x8F1BBCDC)
elif 60 <= i <= 79:
# Do f = b ^ c ^ d
fsplit_enc = my_module.xor3.run(bsplit_enc, csplit_enc, dsplit_enc)
ksplit = split(0xCA62C1D6)
In this main loop, we take the right choice of f and k. Here, we can see a first use of
the different functions in the Module.
Then we continue with other functions in the Module, to compute arot5 = _left_rotate(a, 5) and
arot5 + f + e + k + w[i]:
# Do arot5 = _left_rotate(a, 5)
arot5split_enc = my_module.rotate5.run(asplit_enc)
# Do arot5 + f + e + k + w[i]
ssplit_enc = my_module.add5.run(
arot5split_enc,
fsplit_enc,
esplit_enc,
wsplit_enc[i],
my_module.rotate5.encrypt(ksplit), # BCM: later remove the encryption on k
)
Finally, we update the different a, b, c, d, e values as in the clear
implementation but with the encrypted forms:
# Final update of the a, b, c, d and e registers
newasplit_enc = ssplit_enc
esplit_enc = dsplit_enc
dsplit_enc = csplit_enc
# Do c = _left_rotate(b, 30)
csplit_enc = my_module.rotate30.run(bsplit_enc)
bsplit_enc = asplit_enc
asplit_enc = newasplit_enc
You can see that we compiled the Module's different functions on inputset made with bits. Under the hood, Concrete adds a few programmable bootstrappings to compute the correct functions in FHE.
MLIR code
Compiling with show_mlir = True allows to see the different MLIR implementations.
Testing or using
This tutorial focuses on the use of Modules rather than a production-ready implementation. For a full client-server API, you might want to perform more operations in FHE, including message expansion, and function optimizations.
You can verify the implementation in FHE by running python sha1.py --autotest: it will
pick a certain number of random inputs, hash them in FHE and compare the result with the hashlib
standard implementation.
You can also hash a given value with
echo -n "The quick brown fox jumps over the lazy dog" | python sha1.py, and it will print
something like:
sha1-digest: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
computed in: 320.265383 seconds
Benchmarks
We have executed our implementation on an HPC7a machine with Concrete 2.7.
python sha1.py --autotest typically returns:
Checking SHA1(yozulCBAPuFosqTBMwPTVmvQvmfhGFJjdtSSiemdytn) for an input length 43
sha1-digest: aa1871c2d560221e14f18b43d559aafc4920d9bc
computed in: 93.844131 seconds
Checking SHA1(HwXFZxXUGckiuWysDtrpIijiRwRGPJZPGaNpJMlfbPptfNhzKOXZMiZnoLlaRCXqK) for an input length 65
sha1-digest: 8555e05fc2396a3b291e983901bdfa02cb454a72
computed in: 181.812173 seconds
Checking SHA1(am) for an input length 2
sha1-digest: 96e8155732e8324ae26f64d4516eb6fe696ac84f
computed in: 91.206739 seconds
Checking SHA1(OTzaWtYfzqKyTHIgBSlmI) for an input length 21
sha1-digest: c76426dbecb3afd015b132e0e44a1b4d0fc664cb
computed in: 91.182635 seconds
Checking SHA1(MBwAxKkvLOUzXkHILdVchwjfcUTlofyQdSqaonqcXvRVVwEJpmaGKOsNDCUGkt) for an input length 62
sha1-digest: 2231cecd803a9000c117a2f2d3ea35f70ecf6fce
computed in: 179.300580 seconds
Checking SHA1(iqObpuNHZXKztrUZYrpmAPjFflNLacYyUTBLZdbjbPcjbLOseIKqZNYCbsoaDuwvgbvfWE) for an input length 70
sha1-digest: 87cdf7a7f984ef5843d0cfc95a69eaef3e82e31b
computed in: 182.332336 seconds
Checking SHA1(nPIZWXYUXOerncJAeBQrcPhuHsXbYcQkKMRoAGzxFZjBXWvproNcHlHIFNNGzQChEVjZvsEmSOpQuoihPgudlqizwAfXzgU) for an input length 95
sha1-digest: 601db1e338e8b817f5309c7c3bf89450d70425a1
computed in: 182.233933 seconds
Checking SHA1(SfUDDjhLqcmifCpLlqnUZKFjwtPjfCrpdRChUWypdrhdDTjizF) for an input length 50
sha1-digest: 8c57e70e92af96c6df5aecb4f3740e68b0686883
computed in: 91.378782 seconds
Checking SHA1(VePVJXHljlLpkThrANZaEkkbYoFZVdSFFsvVkQPDlrwyisOIZqAUhGwHYYhxnFjOrUgFV) for an input length 69
sha1-digest: b54a98dc0f74b50669a5e0c81199a2819e26d3e9
computed in: 182.419465 seconds
Checking SHA1(hCOuPvLrBXYhaWLeSnyRxpJZmXyEeTCBdfkgvDwvFIgoVaXNPzHoHkitSvZLosTMEcDpuoLGqeCkuwLmQQLbSibizfPwxp) for an input length 94
sha1-digest: 19432e37fe0bbc7c5a5c9379ed38c4298d796fe6
computed in: 182.285430 seconds
Checking SHA1(IRZuLcbBXJAfgYMuFwGWUXiKgfoWwSAOTOoQiLaZHKwuTbGGsTChMLEdlaRXkIOYUFJRxRyAVHhQbFKyKOFDNairicMm) for an input length 92
sha1-digest: 4307a80365937a3ff6703763a8f1a759362c35e5
computed in: 182.162872 seconds
Checking SHA1(hsTWqDAwjdLiAhmLsnBJJozejydFLcksQmSQVcojeAhdZizXMzjKSAGjQUjRPGZlwGaKnE) for an input length 70
sha1-digest: 3889e4448d11e9d801608ab3a94378ee8d41aaa0
computed in: 182.288777 seconds
Checking SHA1(GihWwpolRavMdWHiNGVlOVsziPqZcYkPEyTmgfbBtwMowfKMipRxADcqqzMBlpCrWEOJpnZQcqAwt) for an input length 77
sha1-digest: 4b048588c8ec5d1602487124b5232889668f6b6a
computed in: 182.184901 seconds
Checking SHA1(GiSbjYHQyEozGliG) for an input length 16
sha1-digest: dc7a31c2e17ae503c6c808a02c05f8d1ad4b346f
computed in: 91.260812 seconds
Checking SHA1(boVGLdzvbKOTYUSErbeSyoiJQMox) for an input length 28
sha1-digest: 50a40fb6d0362087ed9b6dceda5378c14b96a743
computed in: 91.119592 seconds
Checking SHA1(kiaAjFJrzBaRFvSgIzIQdlJZokXGPBpjNRPqEcVDyCFGkxNzeiRNHuSmD) for an input length 57
sha1-digest: 44e423eaa7616d2a93b235d99b61f76a6f58e236
computed in: 179.129039 seconds
Checking SHA1(IylnzdjqldIJGkolzRlJhFz) for an input length 23
sha1-digest: 463137090865b283801d49d1546ce0dea45f2529
computed in: 91.211171 seconds
Checking SHA1(QEyszfMlKJjKIf) for an input length 14
sha1-digest: 937bfdff3bb97e9037a23bca4055302f97a90eb3
computed in: 91.124824 seconds
Checking SHA1(IOTanBIVaq) for an input length 10
sha1-digest: b8dca6ad5df447549f5a95d4c195b889f5be6069
computed in: 91.110348 seconds
Checking SHA1(FiWWroKJVGeMPfmaNKmXdalAyIRLpYJdFgCfBIEMXPDfWR) for an input length 46
sha1-digest: 84775d2c31df2ab191a0417cf26028f989d2cd9c
computed in: 91.031444 seconds
Checking SHA1()
sha1-digest: da39a3ee5e6b4b0d3255bfef95601890afd80709
computed in: 91.044046 seconds
Checking SHA1(The quick brown fox jumps over the lazy dog)
sha1-digest: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
computed in: 90.971023 seconds
These results mean that:
- one block of compression takes about 92 seconds
- two blocks of compression take about 181 seconds