# Can this key revocation scheme using hierarchical deterministic keys work?

Assume I am working with crypto that supports hierarchical deterministic key generation, Bitcoin/Ethereum keys using secp256k1 is one example.

There is a decentralised key registry where users register their public keys for use and other users retrieve those public keys for verificaton. A similar setting could be a blockchain where users transfer coins to other people's public keys.

Now I want to support key revocation as if a user's private keys are stolen he can revoke corresponding public keys. The idea is that the user uses hierarchical deterministic key generation. The parent key is heavily guarded in maybe in a cold storage and its children keys are used for regular usage. It is the child public keys that are put on the registry. You use a knowledge of a parent (private) key to prove control over child keys to the registry and ask the registry to revoke child keys. The registry will verify that the child key is indeed derived from the parent key (can be done using this) and the revoker has the parent private key.

eg. Alice generates a parent keypair $$A$$ with secret and public keys as $$A_s$$ and $$A_p$$ respectively that it never uses apart for child key generation and keeps in a very secure storage. Now whenever Alice wants to create a new child key, it uses the parent key $$A$$. Say it 2 child keys based on keypair $$A1$$ ($$A1_s$$, $$A1_p$$) and $$A2$$ ($$A2_s$$, $$A2_p$$). Now it loses the wallet containing $$A1$$ and $$A2$$. Alice will not provide a signature to the registry using the private key $$A_s$$ and asking the registry to revoke $$A1$$ and $$A2$$. The registry checks that $$A1$$ and $$A2$$ are derived from $$A$$ and hence revokes.

UPDATE:
As the answer below shows, this scheme is not useful as revoking a child key enables the possesor of any child private key to know the parent private key.

• Why not set up a simple local CA? You would initially generate a self-signed CA that signs a second certificate. You would then upload the certificate to the registry and use its corresponding private key in production while storing the private key for the CA "heavily guarded". To revoke, you create a CRL containing your certificates, signed by the CA private key. Your way is the same principle, so yes, it should be possible – Ceriath Jan 11 at 9:26
• Yes, the principle is same, have a "master key" that can revoke regular keys. But with the CA approach you tell the registry explicitly that this is the "master key", with hierarchical deterministic keys, the registry knows that a parent key is the "master" of child keys. – lovesh Jan 11 at 10:07

One problem I can foresee with such a scheme is that when you know a parent extended public key and any non-hardened private key descending from it, you can easily compute the parent extended private key.

This is true because non-hardened public keys are of the form :

I = HMAC-SHA512(Key = cpar, Data = serP(point(kpar)) || ser32(i))
then you split I into two 32-byte sequences, IL and IR
and the child key ki is: parse256(IL) + kpar (mod n)
the chain code ci is IR, which is part of the extended public key
and finally you can compute the child public key either by computing point(parse256(IL)) + Kpar
or by computing point(ki), both are equivalent

So, as you can see, the child private key is the parent private key plus 256 bits of the computed HMAC-SHA512 using the chaincode of the parent private key (which is not a secret) as the HMAC key and, importantly, hashing the public key that corresponds to the extended parent private key along with the child key index.

This basically means that an attacker stealing a non-hardened private key (which you would then like to revoke using the parent private key to authenticate with the registry) could see the extended public key you used to authenticate with the registry if this is public, and from there derive the parent private key you've used to authenticate with the server.

Now, the attacker and the registry both can derive the child public key from the extended parent public key using:

I = HMAC-SHA512(Key = cpar, Data = serP(Kpar) || ser32(i))
then split I into two 32-byte sequences, IL and IR
The child key Ki is point(parse256(IL)) + Kpar, just like above.

But that also means that the attacker can compute the index value "parse256(IL)" and subtract it to the child non-hardened private key (which she stole) to recover the parent private key:

kpar = ki - parse256(IL) (mod n)

thus effectively allowing the attacker to revoke herself all other child keys derived from that parent key on the registry.

A way around it might be to say that when you register on the registry, for each child key, you register a different parent public key (which would be a hardened key), and that this key can then be used to revoke that child key, but only that child key...

I'm not convinced this eases the pain compared to having a certificate to sign your keys and allowing you to revoke them à la PGP, but with this method at least you're using only HD keys, as you seem to want.

So, in the end, this could work from what I can tell, as long as you take care to handle this caveat correctly.