Can this key revocation scheme using hierarchical deterministic keys work?

Question

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.

Answer 1

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 = c_par, Data = ser_P(point(k_par)) || ser₃₂(i))
then you split I into two 32-byte sequences, I_L and I_R
and the child key k_i is: parse₂₅₆(I_L) + k_par (mod n)
the chain code c_i is I_R, which is part of the extended public key
and finally you can compute the child public key either by computing point(parse₂₅₆(I_L)) + K_par
or by computing point(k_i), 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 = c_par, Data = ser_P(K_par) || ser₃₂(i))
then split I into two 32-byte sequences, I_L and I_R
The child key K_i is point(parse₂₅₆(I_L)) + K_par, just like above.

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

k_par = k_i - parse₂₅₆(I_L) (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.