A practical introduction into hash-based signatures using Python. Part One.

As you may know, I recently entered a proposal into the HIVE proposal system, for starting work on two libraries meant to aid HIVE in the future transition from the current elliptic-curve signatures (ECDSA) to post-quantum-ready hash based signatures.

If you are on HIVE and haven't voted to aprove the funding of my proposal yet, please go to its proposal page on peakd and push the 'SUPPORT NOW' button.

So what are hash based signatures? I could try to explain, but there are plenty of explanations out there already, and as a practical minded person I feel its probably better to show than tell. So in this post, and one comming up soon, we are going to look into hash based signatures by implementing a really simple one in Python.

I've decided to split this subject into two distinct posts. If you want to do usefull hash based signatures, you will need both of them, but as it would be a rather big post if I tried putting the two parts together straight away, I'm splitting things up.

• Part One: One-time (hash-based) signatures (with a one-time pub/priv keypair)
• Part Two: Hash-based signing with many-time-signing pub/priv keypair.

I hope that after reading this and the next post, it will be clearer to the more technically inclined amongst you what my proposal aims to implement, at least at a basic level.

One-time (hash-based) signatures

For real signatures we will need a secure one-way hash function. The problem with showing and secire one-way hash functions is that hashes created with these secure hash functions are rather long and don't quite demonstrate things as clearly as a really insecure one-way function such as CRC-16 does. For that reason, in these posts, we are going to actually be using CRC-16 to demonstrate how hash based signatures work.

Let us start importing some basic stuff and defining a few convenience functions.

import random
from bitstring import BitArray
from crc16 import crc16xmodem as crc16int
import struct

def get_random():
    return struct.pack(">H",random.randint(0,256*256-1))

def digest(data):
    return struct.pack(">H",crc16int(data))

def asbits(data):
    return BitArray(bytes=data).bin

Now let's say you want to sign something. Lets say you want to confess to having shot JFK. You type your confession and you want to put your signature on it so everybody knows its really you who did it. Signing the actual confession would be really resource intensive. So what do we do? We sign a message digest instead. To do that we take some hash (in our case crc16, but in real life something like SHA2 or BLAKE3 might be a decent choice.

confession = b"I shot John Fitzgerald from the grassy knoll."
checksum = digest(confession)
print("hex:", checksum.hex().upper())
print("bin:", asbits(checksum))

The result of this code looks like this:

hex: E19D
bin: 1110000110011101

One-time hash based signing. One bit at a time.

Now we have 16 bits to sign. In reality this will likely be at least 128 bit, but let's stick with the 16 bit for now. As you may have heart, hash based signatures are rather long compared to ECDSA signatures. There are some ways to attenuate this, but right now we start of by accepting it for now that the signature is going to be comparatively huge. We are going to be signing one bit at a time out of our 16 bit message digest.

So let's start by creating a one-time private key for signing our first bit. We will add some structure to our one time one bit signing key for later use, but for now we create a one time key that we can only sign one bit with. We do so by taking two random numbers, both again an insecure 16 bits long.

s1 = get_random()
s2 = get_random()
one_time_privkey = [[s1,s2]]
print("priv:", one_time_privkey[0][0].hex().upper(),one_time_privkey[0][1].hex().upper())

The result:

priv: D300 94BA

Now to derive the public key from this private key, we simply take the hash of each of the two numbers and use that as our publiv key.

def privkey_to_pubkey(privkey):
    rval = list()
    for pk in privkey:
        rval.append([digest(pk[0]), digest(pk[1])])
    return rval

one_time_pubkey = privkey_to_pubkey(one_time_privkey)
print("pub:", one_time_pubkey[0][0].hex().upper(),one_time_pubkey[0][1].hex().upper())

The result:

pub: 4074 D2BE

So given the receiver has our pubkey and knows it's us it belongs to, and given we ourselves have the private key. How do we use it to sign our own first bit with? Well, quite simply by sharing half of our private key. If the bit is zero, we share the first part. If it's one, we share the second. Now it also becomes clear why we were speaking about one-time signatures. After having signed our one bit, our private public key pair is rendered useless, because signing exposes part of our private key.

def sign_bit(dgst, privkey, bitno):
    bit = asbits(dgst)[bitno]
    if bit == "0":
        return privkey[bitno][0]
    else:
        return privkey[bitno][1]

signature = sign_bit(checksum, one_time_privkey, 0)
print(signature.hex().upper())

The result:

94BA

Scaling up

Now that we know how to sign one bit, lets see if we can scale it up. We were using a 16 bit digest, so we need to be able to sign 16 bits to do anything usefull.

def generate_privkey():
    rval = list()
    for _ in range(0,16):
        rval.append(list())
        for _ in range(0,2):
            rval[-1].append(get_random())
    return rval

def key_to_hex(key):
    rval = ""
    for pkey in key:
        for val in pkey:
            rval += val.hex().upper()
        rval += " "
    return rval

big_onetime_privkey = generate_privkey()
print("priv:", key_to_hex(big_onetime_privkey))
big_onetime_pubkey = privkey_to_pubkey(big_onetime_privkey)
print("pub:", key_to_hex(big_onetime_pubkey))

The result:

priv: 3D2801CF AFE44892 DEFB3D3C 94D0A520 14E333BB CE28B127 C78406E6 CA4FAAA6 DA105176 FC726B12 47894DD9 DBCB251E BBCE442F EF040B75 A7410036 465432E3 
pub: D6A31B92 B0EA279E 685C8416 1F52C6E9 02FA4676 903179B9 5ECF374E 40B42799 E8DD23DF 0879E5A3 94FA21C4 A1FA0AEC FA751485 4008F2C8 DC0C5695 BD1BAEBA

Quite huge keys, lets look at the signature.

def sign_digest(dgst, privkey):
    rval = list()
    for bitno in range(0,16):
        rval.append(list())
        rval[-1].append(sign_bit(dgst, privkey, bitno))
    return rval

big_signature = sign_digest(checksum, big_onetime_privkey)
print("sig:", key_to_hex(big_signature))

The result:

sig: 01CF 4892 3D3C 94D0 14E3 CE28 C784 AAA6 5176 FC72 4789 251E 442F 0B75 A741 32E3

32 bytes (256 bits) to sign a 16 bit digest. I hope it speaks for iself these numbers will be many times higher if both the digest and the random numbers of the private key are 128 or 256 bits instead.

Lets add a simple validator.

def validate_digest(dgst, signature, pubkey):
    for bitno in range(0,16):
        bit = asbits(dgst)[bitno]
        if bit == "0":
            expected = pubkey[bitno][0]
        else:
            expected = pubkey[bitno][1]
        if digest(signature[bitno][0]) != expected:
            return False
    return True

validate_digest(checksum, big_signature, big_onetime_pubkey)

Result:

True

Seed to private key

We have a huge-ish private key, a huge-ish public key and a quite large signature as well. For the private key there is a simple trick to reduce the size. Instead of taking 32 random numbers, we take just one. A seed. We then use the seed to construct the private key from. If this can be done quickly, we can as well consider the seed to be the actual private key.

def seed_to_privkey(seed):
    rval = list()
    for bitno in range(0,16):
        rval.append(list())
        for bitval in range(0,2):
            rval[-1].append(digest(chr(bitno).encode() + chr(bitval).encode() + seed))
    return rval

seed = get_random()
print("seed:", seed.hex().upper())
derived_privkey = seed_to_privkey(seed)
print("privkey:", key_to_hex(derived_privkey))
derived_pubkey = privkey_to_pubkey(derived_privkey)
print("pubkey:", key_to_hex(derived_pubkey))
derived_signature = sign_digest(checksum, derived_privkey)
print("signature:", key_to_hex(derived_signature))

Result:

seed: 54AE
privkey: 965FA16F E0EBD7DB 7B374C07 0D833AB3 5CAE6B9E 2A1A1D2A B1C686F6 C772F042 139C24AC 65285218 FEF4C9C4 8840BF70 D96DEE5D AFD998E9 34050335 42B17581 
pubkey: 1957B306 5CF7F6A6 92173846 D7B77DE6 1FF6B5A7 5A56F007 94B63EE7 D1167B47 1415BE44 51B5FBE4 9F553504 DAF570A4 12B4B8E5 5714FD45 99F433A5 DC547605 
signature: A16F D7DB 4C07 0D83 5CAE 2A1A B1C6 F042 24AC 6528 FEF4 BF70 EE5D 98E9 3405 7581 

Signing multiple bits at one time.

There are ways to reduce the size of both the public key and the signatures. The trick is to sign multiple bits at the same time. A good way to do that is called a WOTS-chain.

To create a WOTS chain, we take one random number, our n-bit secret key, and hash it two to the power n to get a public key for signing n bits with. I hope it's clear that reducing key and signature sizes this way comes at a performance penalty. Choosing a faster hashing algorithm like picking BLAKE3 over SHA256 might help shifting the sizes down a little bit more, but in the end there are limits to how much we can reduce the size of the signatures and public keys this way.

So how do we sign our n-bits with this scheme? Again we expose part of our private key, in a way, this time by using the x times hashed version of the private key. This however presents us with a problem. What if there is a man in the middle? Before a one at position one could only be used in a forged message to sign exactly the same value of one at exactly the same position, so the forged message that would be possible after key exposure would be an exact copy of the original message, making forgery useless. But now, an x-times hashed private key could allow a MITM to forge x+1, etc ar values. To overcome this problem, WOTS+ uses checksum bits.

Both to prefent confusion (afterall, rihgt now we are using an actual checksum in the place of a secure hash to demonstrate how hash based signatures work), and because, quite frankly, its most likely much more secure anyway, we use a different and more straight forward approach. We use two WOTS chains instead of one.

Let us use one nibble (4 bits) to sign at once. Now if we want to sign the number 5 or 0101, we hash the first time of our private key 5 times, and the second part of our private key 11 (16-5) times, and share both as our signature. That way signing the number 5 at position one will only really allow the creation of a forge message with the number 6 at postion one again. A few more signature bits than using a cahecksum, but much more straightforward ti implement and most likely many times more secure.

def seed_to_privkey_v2(seed):
    rval = list()
    for nibbleno in range(0,4):
        rval.append(list())
        for direction in range(0,2):
            rval[-1].append(digest(chr(nibbleno).encode() + chr(direction).encode() + seed))
    return rval

def privkey_to_pubkey_v2(privkey):
    rval = list()
    for pkey in privkey:
        rval.append(list())
        for subkey in pkey:
            val = subkey
            for _ in range(0,16):
                val = digest(val)
            rval[-1].append(val)
    return rval


def sign_nibble(dgst, privkey, nibbleno):
    count1 = int(dgst.hex()[nibbleno],16)
    count2 = 15 - count1
    val1 = privkey[nibbleno][0]
    val2 = privkey[nibbleno][1]
    for _ in range (0, count1):
        val1 = digest(val1)
    for _ in range (0, count2):
        val2 = digest(val2)
    return val1 + val2
    

def sign_digest_v2(dgst, privkey):
    rval = list()
    for nibbleno in range(0,4):
        rval.append(list())
        rval[-1].append(sign_nibble(dgst, privkey, nibbleno))
    return rval

seed = get_random()
print("seed:", seed.hex().upper())
derived_privkey = seed_to_privkey_v2(seed)
print("privkey:", key_to_hex(derived_privkey))
derived_pubkey = privkey_to_pubkey_v2(derived_privkey)
print("pubkey:", key_to_hex(derived_pubkey))
derived_signature = sign_digest_v2(checksum, derived_privkey)
print("signature:", key_to_hex(derived_signature))

Results:

seed: 54F8
privkey: AC6C9B5C DAD8EDE8 41047634 37B00080 
pubkey: 30555760 19147E21 62D705E2 4B962CA3 
signature: 77A95F68 B099A0C6 4826218E 2EC63B5A 

As for validation. A little bit more involved, but not much.

def validate_digest_v2(dgst, signature, pubkey):
    for nibbleno in range(0,4):
        count2 = int(dgst.hex()[nibbleno],16)
        count1 = 15 - count2
        val1 = signature[nibbleno][0][0:2]
        val2 = signature[nibbleno][0][2:]
        for _ in range (0, count1+1):
            val1 = digest(val1)
        for _ in range (0, count2+1):
            val2 = digest(val2)
        if val1 != pubkey[nibbleno][0]:
            return False
        if val2 != pubkey[nibbleno][1]:
            return False
    return True

validate_digest_v2(checksum, derived_signature, derived_pubkey)

Result:

True

Comming Up

In the second (and last) post in this series we will look into how to turn the One-Time signature scheme we discussed in this post into a setup with many-use private/public key pairs, looking into the use of a Merkle Tree.

I hope this post helped you in your understanding of the basics and properties of hash based signatures at least a bit. Hash based signatures are important for a post-quantum future for blockchains like HIVE, and if you think it is important that at least some work happens on this right now, please support my proposal with your aproval.

Also, if you are interested in this subject and are a decent JavaScript developer, please reach out. If my proposal gets funded and completed, it is only C++ and Python and we will need JavaScript too for the HIVE ecosystem. So follow-up proposals most definetely will need to include a JavaScript component that needs someone other than me with actual sollid JavaScript skills.