hibe

README.md

Hardened-Plus key derivation using Identity Based Cryptography

Ordinary crypto wallet key derivation (like in Bitcoin and Ethereum, see BIP32) presents you with a dilemma. There are two bonus features: hardening, and xpub keys. Without hardening, a single private key and xpub, or two private keys, can be used to decrypt the entire master key. With hardening, the xpub is useless, can't be used to derive individual keys. Why can't we have both?

With Identity Based Cryptgraphy, we can fix this.

More specifically, in hierarchical deterministic wallets, we always have a master private key xpriv, that can be used to derive private keys according to a path string, like m/44/0/0/.... The "hierarchical" bit means that you can delegate subkeys like m/44/0 that can be used like wildcard, i.e. they can sign for keys under their subtree like m/44/0/*/*/....

with normal key derivation using key derivation paths like m/44/0/0/..., we also have a master public key xpub that can be used to derive the public keys for each path. It acts like a viewing key. (See for instance this xpub tool). However, the downside of normal key derivation is that the keys are not truly isolated. Either two private keys, or one private key and the xpub, can be used to derive the master key.

Hardened keys use a different path identifier, like m/44'/0'/0'/..., where hardening acts like a circuit breaker. The private keys are all now properly isolated from each other, but there is no longer an xpub that can be used to derive public keys.

Hardened-Plus Derivation this with Hierarchical ID Based Digital Signatures (HIBD)

Identity Based Cryptography is a useful way to approach this problem. The proposal is to define a signature scheme supporting derivation paths such as m/44*/0*/0* which support both hardening as well as useful xpub keys.

There is a general approach to key distribution that works for hierarchical encryption and digital signatures like this, based on pairings. (BBG05) This is ordinarily presented for hierarchical ID based encryption, but there is a generic transformation from HIBE encryption to signatures (GS02), so we implement that here.

Because this uses pairing, it cannot be implemented using secp256k1, but might be a good fit for BLS12-381 or related. This is an implementation in Charm using a symmetric bilinear group.

Hierarchical IBE from BBG05

See ./hibe.py for an implementation of hierarchical identity based encryption

Hierarchical ID Based signatures from Cha-Cheon signatures.

See ./hibd.py for an implementation of the proposed m/44*/0*/0*/... "hardened plus xpub"

Setup

This uses a Docker file to build Charm.

docker build -t hibe .

docker run -it hibe

Dockerfile

FROM python:3.8.0-buster AS charm

# Get the Dockerfile from here
# https://raw.githubusercontent.com/sbellem/docker-charm-crypto/master/latest/python3.8/buster/Dockerfile
# docker build -f docker-charm-crypto/master/latest/python3.8/buster/Dockerfile -t charm .
ENV PYTHONUNBUFFERED 1

RUN apt-get update && apt-get install -y --no-install-recommends \
                bison \
                flex \
        && rm -rf /var/lib/apt/lists/*

ENV LIBRARY_PATH /usr/local/lib
ENV LD_LIBRARY_PATH /usr/local/lib
ENV LIBRARY_INCLUDE_PATH /usr/local/include

# PBC
COPY --from=initc3/pbc:0.5.14-buster \
                /usr/local/include/pbc \
                /usr/local/include/pbc
COPY --from=initc3/pbc:0.5.14-buster \
                /usr/local/lib/libpbc.so.1.0.0  \
                /usr/local/lib/libpbc.so.1.0.0
RUN set -ex \
    && cd /usr/local/lib \
    && ln -s libpbc.so.1.0.0 libpbc.so \
    && ln -s libpbc.so.1.0.0 libpbc.so.1

# Setup virtualenv
ENV PYTHON_LIBRARY_PATH /opt/venv
ENV PATH ${PYTHON_LIBRARY_PATH}/bin:${PATH}

# Install charm
# Creates /charm/dist/Charm_Crypto...x86_64.egg, which gets copied into the venv
# /opt/venv/lib/python3.7/site-packages/Charm_crypto...x86_64.egg
RUN set -ex \
        \
        && mkdir -p /usr/src/charm \
        && git clone https://github.com/JHUISI/charm.git /usr/src/charm \
        && cd /usr/src/charm \
        && python -m venv ${PYTHON_LIBRARY_PATH} \
        && ./configure.sh \
        && make install \
        && rm -rf /usr/src/charm


FROM charm

RUN pip install ipython

WORKDIR /root

ADD hibe.py hibe.py
ADD hibd.py hibd.py
ADD chch.py chch.py
ADD README.md README.md

CMD python hibd.py

hibd.py

from charm.toolbox.pairinggroup import PairingGroup,ZR,G1,G2,GT,pair
from hibe import HIBE, group, ZR, g

###### I. HIBE (BBG05) from Boneh Boyen Goh 2005

"""
Hierarchical ID Based Digital signatures from BBG05
===

[1] Dirjvers Neven.
[2] BBG05 HIBE.
[3] https://eprint.iacr.org/2003/083.pdf

This is the same approach from Drijvers and Neven [1], and is basically the BBG [2] key derivation, with a generic approach for giving signatures from HIBE due to CHK07 [3]
 from 

The basic idea is the following: For a signing key of path depth D, we create a BBG key with depth D+1. The extra layer is used for the hash of the message being signed. 
 For example m/44*/0*/0*/{H(m)}

The signature is simply the BBG leaf decryption key derived from that message hash.
To verify the signature, we can just check that the decryption works successfully.
"""

DEPTH=3

class HIBD():
    def __init__(self, ):
        self.hibe = HIBE()

    def setup(self, seed=None):
        # Setup is exactly the same as BBG05
        (mpk, msk) = self.hibe.setup(seed)
        return (mpk, msk)

    def keygen(self, msk, ID, seed=None):
        # Keygen is just the derivation up to our depth
        assert len(ID) == DEPTH
        return self.hibe.keygen(msk, ID, seed)
            
    def sign(self, priv, ID, m, seed=None):
        # Hash the message, use this to derive the last path element
        c = group.hash(m, ZR)
        # The signature is just the key
        sig = self.hibe.derive_child(priv, tuple(ID)+(c,), seed)
        return sig
    
    def verify(self, mpk, ID, m, sig, seed=None):
        # To verify the signature, need to check decryption
        mm = group.hash(m, ZR)
        M = pair(g,g)**0
        CT = self.hibe.encrypt(mpk, tuple(ID)+(mm,), M, seed=seed)
        M2 = self.hibe.decrypt(sig, tuple(ID)+(mm,), CT)
        assert M2 == M

hibd = HIBD()
(xpub, xpriv) = hibd.setup(seed=0xcafeee)
print('xpub:',xpub)
print('xpriv:',xpriv)


# Keygen for signing
priv = hibd.keygen(xpriv, [0x44,0x0,0x0])
print('Keygen: OK')
# print(priv)

# Signature
msg = 'hello wlrod'
sig = hibd.sign(priv, [0x44,0,0], msg)
# print(sig)
print('Sign: OK')

# Verify
hibd.verify(xpub, [0x44,0,0], msg, sig)
try:
    hibd.verify(xpub, [0x44,0,0], msg[:-1], sig)
except AssertionError:
    print('X Check OK')
else:
    assert False, 'failed?'
    

"""
Bitcoin Key Derivation
===

Analogous to trezor 
https://trezor.io/learn/a/what-is-bip32


"""

hibe.py

import charm

###### I. HIBE (BBG05) from Boneh Boyen Goh 2005 

## Our setting is a symmetric bilinear group
from charm.toolbox.pairinggroup import PairingGroup,ZR,G1,G2,GT,pair
from charm.schemes.pksig.pksig_chch import CHCH

group = PairingGroup('SS512')    

H1 = lambda x: group.hash(x, G1)
H2 = lambda x,y: group.hash((x,y), ZR)

g = H1('chch:g0')
g2 = H1('chch:g2')
g3 = H1('chch:g3')
DEPTH = 4
hgens = []
for i in range(DEPTH):
    hgens.append(H1(f'chch:g{i:05d}'))

class HIBE():
    def __init__(self):
        pass
    
    def setup(self, seed=None):
        a = group.random(ZR, seed=seed)
        msk = g2 ** a
        mpk = g1 = g ** a
        return (mpk, msk)

    def keygen(self, msk, ID, seed=None):
        k = len(ID)
        assert k <= DEPTH
        r = group.random(ZR, seed=seed) # TODO pseudorandom from ID
        a0 = g3
        for hi,ii in zip(hgens[:k], ID):
            a0 *= hi ** ii
        a0 **= r
        a0 *= msk
        a1 = g ** r
        bs = [h ** r for h in hgens[k:]]
        return (a0,a1) + tuple(bs)

    def encrypt(self, mpk, ID, msg, seed=None):
        k = len(ID)
        assert k <= DEPTH        
        g1 = mpk
        s = group.random(ZR, seed=seed) # TODO pseudorandom from ID        
        a = pair(g1,g2) ** s
        a *= msg
        b = g ** s
        c = g3
        for hi,ii in zip(hgens[:k],ID):
            c *= hi ** ii
        c **= s
        return a,b,c

    def decrypt(self, priv, ID, CT):
        k = len(ID)
        A, B, C = CT
        a0, a1 = priv[:2]
        bs = priv[2:]
        assert len(bs) == DEPTH-k
        M = A * pair(a1,C) / pair(B,a0)
        return M

    def derive_child(self, priv, ID, seed=None):
        k = len(ID)
        assert k <= DEPTH
        a0, a1 = priv[:2]
        bs = priv[2:]
        assert len(bs) == DEPTH-k+1
        t = group.random(ZR, seed=seed)
        A0 = g3
        for hi,ii in zip(hgens[:k],ID):
            A0 *= hi ** ii
        A0 **= t
        A0 *= a0 * (bs[0] ** ID[-1])
        A1 = a1 * g ** t 
        Bs = [bi * (hi ** t) for hi,bi in zip(hgens[k:], bs[1:])]
        return (A0,A1) + tuple(Bs)

hibe = HIBE()
(xpub, xpriv) = hibe.setup(seed=0xcafeee)
# print('xpub:',xpub)
# print('xpriv:',xpriv)

# Keygen the normal way
priv = hibe.keygen(xpriv, [0x44,0x0,0x1,0x2])
print('Keygen: OK')
# print(priv)

msg = pair(g, group.hash('chch:msg:hello', G1))
# print('msg:', msg)
ct = hibe.encrypt(xpub, [0x44,0x0,0x1,0x2], msg)
# print(ct)
print('Encrypt: OK')

msg2 = hibe.decrypt(priv, [0x44,0x0,0x1,0x2], ct)
assert(msg2 == msg)
print('Decryption and Original Message match: OK')

##### II. HIBE and Prefix delegation

# Keygen the hierarchical way
priv0 = (xpriv,1,1,1,1,1)
priv1 = hibe.derive_child(priv0, [0x44])
priv2 = hibe.derive_child(priv1, [0x44,0x0])
priv3 = hibe.derive_child(priv2, [0x44,0x0,0x1])
priv4 = hibe.derive_child(priv3, [0x44,0x0,0x1,0x2])

msg3 = hibe.decrypt(priv4, [0x44,0x0,0x1,0x2], ct)
assert(msg3 == msg)
print('Hierarchical Decryption and Original Message match: OK')