Least-authority web-3 subkey management: allowing root level accumulation?

[Rob Meijer]

I'm working on my pet project, a hash-based signature and least-authority key-management library for Web 3.0 chains, and I'm being asked about rethinking a design decission that I felt was fundamental, but I'm not sure anymore. I'll try to minimaly describe the relevant parts of the interaction and base design in order to explain my dilemma, I hope it will be enough.

The lib is based on the use of key-index-space as a resource. Th libsodium lib comes with a call  crypto_kdf_derive_from_key that allows deriving up to 2^64 crypto seeds from a single master key. I'm using this to create a (lazy) multi-level tree of level-keys that sign the layer below where every level key consists of dual WOTS tree based one-time signing keys. One such a key represents an actual user, let's call these account keys, while others keys that I refer to as 'accept' keys represent either the in-band or out of band receivers of delegated authority.

The design now has two scenario's for decomposition of authority through key management, but the mechanism is basicly the same for both. 

We have an Allice account key that enhabits the first chunk of the Allice account key key-index space and a large piece of account key key-index space "heap". Allice dimensions the signing space for a new sub-authority, marks that space as allocated, and creates a delegation message for some sub-authority, it adds a public key to that message for some receiver, signs it, and communicated the signed message to the receiver unless that receiver is herself.

In the current design it is possible for Allice to use the key herself with her own root key as master key,  but this is only menat to make sure her initial master key doesn't run out, so she delegates "all: her authority to herself to use more of the keyspace.  This concept was never meant to be used for attenuated authority usage.

It is important to note that the library uses chunks of key-space for revocation, so there is a kind of memory map that marks index space chunks as unallocated. allocated, used, or revoked. 

Now normally to get a key with attenuated authority of Alice, either to be used by Bob or by  Allice herself, an accept key is created. This key is similar to the account key, but it is bound to the delegation with an accept message that basicly states: I Bob, rightfull receiver of this dellegated authority from Allice put this authority into this new key. It is important to note that the new actual key in terms of index space is now set-up to match that of the revokable indices in Alice her allocation for this authority. 

So now Bob has two keys, his own account key, and an accept key with delegated authority plus index space from Allice. Inmy mind this was perfectly POLA.

But now feedback from potential user projects has me thinking if this isn't too strict.
Their argument: If you already have the possibility for a new second level keys tree to reside in the same index space, why not allow account keys to act as accept keys themselves so users don't need to manage multiplle keys?

While I absolutely can see the utility, I feel it violates POLA, but I'm not sure. 

I hope I didn't leave out too much about the design to make this description hard to follow. If I didn't, I would really like to hear your views on the idea of the less strict POLA adherence by allowing receivers of delegated authority to remap recieved authority into their account key rather than needing to create a seperate accept key for that purpose.

T.I.A for any input,

Rob 

[Alan Karp]

I don't follow most of this description.  It sounds like you're using symmetric keys.  Is that right?

--------------
Alan Karp

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/cap-talk/741bbfd9-b838-4264-a9f4-ce38f0c60c9bn%40googlegroups.com.

[Rob Meijer]

No; no symetric keys: It's hash based signatures.

So the private key of any single WOTS chain is the seed and the public key is result of the max number of hashing rounds of that seed.
A huge collection of WOTS private keys like that is derived from a single private key using libsodium crypto_kdf_derive_from_key. The matching public key is than derived by taking the
merkle tree root of (small collections of) all those public keys. On signing additional merkle tree node values are added to allow for validation of the signature.

I'll elaborate, but note it's not where the POLA dilemma is about:

Imagine you want a one-time asymetric siging key with what you can sign say 12 bit. Let's use hex values to denote the possible values.
Now imaggine that if I want to sign the value 0x000, I hash the secret once. If I want to sign the value 0x001, I take the result of the first hashing round and hash it one more time.
Same for all other possible values, so if I want to sign the value 0xfff, I go through 2^12+1 hashing round and the result of that would be my signature. 
But I still need a one time signing pubkey, so what do I do? I take the privite key and take it through 2^12+2 hashing rounds and the result is my public key. 
So if that 12 bits was all I wanted to ever sign, I would share that one time signing-key pubkey, take the 12 bit value V I want to sign, and hash my private key V+1 times.
The receiver of my signature can than take that hash, hash it another 2^12+1-V times, and the value should match my public key.
But there is a bit of a problem here.  An attacker now could use this signature and my pubkey to sign any down-stream value. If by chance I signed the value 0x001,
an attacker couldn't sign 0x000, but he could sign any other value. Other algoritms use CRC solutions to solve this, but in my current code I use a second one-time
secret key with what I sign the two's complement of the 12 bit value. This means that after me siging 0x001, an attacker could sign 0x001 upto 0xfff with the UP part
of my signature, he would also be able to sign 0x000 upto 0x001 with the DOWN part of my signature, so using my full two part signature of these 12 bits, he would only
be able to sign the exact value that my signature already signed.

Signing 12 bits like this is nice, but imagine I wan to sign a transaction or a message. I would start off by hashing the message resulting in a secure hash of the data. A 12 bit hash
wont do, so maybe we take a 192 bit hash. That means we need to 16 signatures to sign that many bits. 32 hashes in total as a one time signature using a 192 bit transaction hash.
Also 32 equaly sized secret keys and 32 public keys. On the public key side, I already know I am going to be using all 32 pubkey chunks at once, so I can simply replace the long pubkey
with a short one by hashing it so I only have one single hash as pubkey for the whole thing. On the secret key side, I can use crypto_kdf_derive_from_key to derive all secret keys from a
single master key.

But while the double chain protects me after using my key once, it will protect me less and less if I kept signing with it. If I sign 0x1b3 with it the first time and 0x1af, an attacker could
sign 0x1af, 0x1b0, 0x1b1, 0x1b2 and 0x1b3, not a big hole to squeeze through, but what if I signed 0xfec first and 0x005 second? All of the 12 bit of siging space would be wide open for

attacks. So these keys are single usage, and we need more. So what do we do? We take maybe 1024, 2048 or 4096 such one-time signing keys, and  create a new type of key.
On the private key side, we just exend the use of crypto_kdf_derive_from_key to a wider key-index space. On the pubkey size we extend our collection of public keys into a merkle tree
and now we use the merkle tree root as our public key. Now if we sign a transaction, we don't share the specific public key to check against directly, we share merkle tree nodes with

our signature so the validator can reconstruct the merkle tree root and validate it against our public key.

So far so good, but in Web 3.0 a key that can only sign maybe 4096 transactions isn't much good on its own. It will exaust too soon. We want a key to last millions of transactions 

at least, billions in some cases. So instead of trying to calculate the pubkey and merkle tree signing nodes for a billion one time keys,  we say a billion is avout 1024x1024x1024
and we choose to make our previous merkle tree based multi signature key into a level key. Level 0 is the one that shouldn't run out during your lifetime. In this case, level 2 would

be the key signing the actual transactions. We use the level 0 key to sign the active level 1 key and the level 1 key to signh the active level 2 key. When the level 2 key gets exausted,
and here it gets interesting, we can retire it by creating and publishing a new level 2 key and "revoking" the index space of that key. When eventualy the active level 1 key is exausted,
we do the same for that key. This revoking further reduces the attack surface a tiny bit, but the mechanism will be crucial to later POLA stuff.  

Because the same one time signing key can't be re-used in signing algoritms like this, index space is fundamentaly an exaustible resource. From a POLA perspective, I 
consider this property to be a feature, not some anoying condition we need to live with.

Now if we consifer our one-billion signatures ready stack of 3 keys considsting of our lifetime key and our two active level keys (level 1 and level 2) as our key, then functionaly, 

we realize that the 64 bitof index space that crypto_kdf_derive_from_key grants us (for 20 byte subkeys and up) is much and much bigger than the maybe 35 or 36 bit of index space that our 3 levels of

level keys require.  This gives room for using the remaining index space for decomposition of authority and delegation, and to expand on the revocation of chunks of index space as a more general tool.

That is the part I'm looking for feedback on. Consider that my secret key gives me access, either to the full 64 bit of index space for my key and any delegation stuff, 

or to a subset of that spece defined by whatever entity created my key. If my key started out with the full 64 bit of index space, and 36 bits would have been enough to hold 

all the possible level 1 and 2 keys our original key migh need, then we have quite some space left to work with. But we are going to treat index space as a resource across 

delegations, so we need to still be strategic to allow for multiple delegation steps. 

One rather weird form of delegation I'm implementing is self-delegation in case we run out of index space with our key. We shouldn't, but things might be misdimensioned 

and we might some day approach our 1 billion signatures  treshold that would make our level0 key exausted. Before this happens we can delegate all of our authority held 

by our key, and all of our furhter remaining index space, to a brand new key "within" our own index space. The last two signatures the 1G-transaction key could sign could be

a transaction delegating all authority and keyspace to its own keyspace, followed by a transaction that revokes the previous key it's entire key index space. Hope this makes sense.
This is a rather weird self-delegation. 

Basicly we end up with multiple pubkeys that map to the same privkey. So far this was a hack to make sure that a user never needs to lose his authority because he somehow 

signs his way out of signing key-space. But I'm considering expanding on this and make the multi-pubkey idea more common.

But first let me elaborate on the current design for delegation. Imagine a Web 3.0 social blogging blockchain where a user can use his key to administer his public info, 

post blog posts, comment and vote on other peoples blog posts, move tokens to other accounts, stake or unstake tokens,  send messages to other accounts, etc, etc.

Imagine two users, Alice and Bob. Alice is verry bussy, too busy to read many posts and upvote the good ones, so Alice wants to delegate the authority to vote to Bob. 
Maybe Bob wants to send a short comment to a post, so Alice also wants to delegate the right to upvote to Bob. 

In the core version of this scenario, three private keys are involved, but only two index-spaces. We have the Allice account key, the Bob account key, and a Bob accept key.

Alice allocates a big chunk of her index-space for the delegation, and creates a transaction that mentiones bob's account pubkey, the exact authority she is delegating

(full voting and commenting), and the amount of index-space she is granting Bob for this authority, and the specific Allice key-space section she is allocating for Bob.

Alice publishes this delegation, but the delegation isn't complete yet, it needs to be accepted. Now Bob needs to anchor this new authority somewhere before  using it.
His and Alice her key-space don't directly map, so Bob creats a new private key, dimensions a new key that fits or underfits the keyspace grantes (underfit so he may 

re-delegate if desired) , and he publishes an accept transaction that binds this new accept key to the delegated authority. The accept key is constrained to the index space 

explicityly allocated for this delegation by Allice, so not the full 64 bit index space. Index-space is a resource that we don't create from thin air by default, at least not for
accept keys.

So this is the design rigt now. 

Feedback that I've been given from a dev ion a potential project that could maybe end up using my code (just a single dev without special weight in the project, so it is nice

to be noticed but I'm not considering the project a true potential user yet) sugested to combine the weird hacky multi-pubkey keys with actual delegation.

That option would basicly give Bob the coice to map the allocated index-space to a different region in his own index space and let the bob account key be the accept key,
at least the private key.

This "feature" sounds convenient, but that convenience actualy also is what worries me, because it feels likely that in many cases the convenient choice in this won't be

the POLA choice in this.

So that last part is the actual part I really need POLA insights on. 

[Alan Karp]

Thanks for the explanation.  I understood about 10% of it, which means I won't be of much help to you.

--------------
Alan Karp

To view this discussion visit https://groups.google.com/d/msgid/cap-talk/bc7f791d-885d-49ea-af55-85e4537aa626n%40googlegroups.com.