Linked-Data Key (Previously Multikey)

[Kubuxu]

I didn't see any specs for multikey so here are my notes what I'd love to see in it and how it could look.

We need a way to represent key types but also how are those keys stored, for example password they might protected. As keys might be getting much bigger (QC and hash based signature crypto) we also need a way to express keys bigger than 256 bytes. There are three options for that:

• use two bytes for size (64KiB = 524Kibit)
• use one byte multiplied by 4 (1KiB = 8Kibit)
• use two bytes multiplied by 4 (256KiB = 2Mibit)

(maybe something even bigger).
Each of them hash its pros and cons.

As format goes I would see it as:

[key protection schema+key type][crypto type][size][protected key]

First byte in 3 lower bits would include information if it is public, private or secret key (3bits = 8 values, rest left for future) and in 5 higher bits it would include information about how the key was protected, for example: no protection, scrypt+AES256, scrypt+salsa20, pure AES and so on.

Next byte would point onto crypto schema of key itself, it would depend on key type.

In case of symmetric key it might be AES128, AES256, salsa20.
In case of private and public for example RSA1024, RSA2048, ed25519, curve25519, ECDSA.

Questions:

• - ~~ in case of public/private keys not all of them are suited for both signing and encryption. Should we have key types for such keys. How about two cryptos being used in pair, example : ed25519+curve25519 (one is suited for signing and one for encrypting), should we have crypto key type or just have two keys in full multikey wrapping? ~~ no longer a problem as for ed25519 <-> curve25519 public key conversion
• - were should be designation of Hash-based message authentication codes placed (probably as symmetric but then we have symmetric keys that some are suited for encryption and some signing)
• - list of protection schemes and cryptos to include in initial spec.

Edit: Point of key protection schema is to allow sending for example password protected private keys. In case that just exchange of public keys took place, no-protection schema should be expected.

[daviddias]

Yes, thank you for pushing this 🙌 Currently, most of the context of multikey lives on jbenet/random-ideas#31 and probably will live as one of the components of https://github.com/ipfs/specs/tree/master/keychain.

[jbenet]

I'm ever closer to specing this out-- need it for keychain yes.

A use case is motivating all of this:

• signed web documents
• need secure identities
• need key rotations and chains of trust
• need multikey
• needs ipld

Working my way up :)
On Sat, Jan 2, 2016 at 16:49 David Dias [email protected] wrote:

Yes, thank you for pushing this 🙌 Currently, most of the context of
multikey lives on jbenet/random-ideas#31
jbenet/random-ideas#31 and probably will live
as one of the components of
https://github.com/ipfs/specs/tree/master/keychain.

—
Reply to this email directly or view it on GitHub
#58 (comment).

[almereyda]

I'm finally sure this is the right place to drop this here, despite I never seem to be able to find the fs:// discussion ever again.

When doing a broad and rough research into the ICN topic, I've stumbled into http://tools.ietf.org/html/draft-farrell-ni-00 via http://dirk-kutscher.info/publications/uris-for-named-information/. There don't seem to be any implementations of this, but multikey follows similar patterns, thus the reference.

[jbenet]

@almereyda nice find! just open another issue in this repo about it. if ni:// is widely deployed (i havent seen it) we could see about supporting it too. (i think you mean it looks like multihash -- https://github.com/jbenet/multihash)

[Kubuxu]

Since I written the issue a method of merging ed25519 and curve25519 keys got established this means we can use just one (probably ed25519) and transform the public key when we want to use encryption (curve25519).

What motivates me the most about that is possibility of switching off RSA for the communication. Using ed25519 would also allow for DHT record signing as it is much much quicker than RSA and signature is only 64 bytes.

[Kubuxu]

ianopolous in IRC highlighted that separating encrypting and signing keys is important, both for RSA and post quantum crypto systems.

Also about post QC systems, we should account for quite big key sizes of those.

[ianopolous]

Yep, multiple megabytes for keys is necessary in some of the PQC schemes. But so long as you can also include the multihash of a (public) key instead of the key itself you should be fine.

[ianopolous]

It would be great to progress this. A first step could be to agree on a format for public keys only. I'm hoping it will be ipld/cbor based to ease writing en/decoders.

For reference, the format we use in Peergos so far is a cbor list with two elements, the first is a cbor int which specifies the type (and needs an accompanying lookup table like multihash), and the second is the cbor byte[] of the key contents. This ends up as a single byte for the list and its length, a single byte for the type, and two bytes for the length of the byte array and the fact it is a byte[], then the bytes themselves. So a four byte overhead on a 32 byte key like Ed25519.

[whyrusleeping]

@JustinDrake might be interested in this too

[daviddias]

Getting back to this issue (thanks for the ping @whyrusleeping ;)). A couple of questions come to mind:

• Can't we just use a multicodec at the beginning to define it's key type? I understand it is 8 bits and probably more than enough, by using a multicodec would give us that property that we love, future proofing. Besides, multicodecs are 8 bits till we have to use a second byte for the varint.
• I believe it makes more sense to have first and then <more information such as if it is priv/pub key>. For example, we would skip spending that by entirely for any symmetric key.
• As for the segment , what about using a binary packed format that would let us make that decision on the fly, we could decide to transfer to some devices only the private key, others the priv + pub (I'm imagining that this would have some usage in low power devices) and others we might want to transfer the seed.

Other questions that arise:

• Will we enable some kind of ALPN for things like secio? The case I'm thinking is when I get the hash of the RSA PubKey, but I want to dial to that node using ECC.
• This would require creating new minor versions of all the network protocols like we did in bitswap, right? (So happy that we have semver in libp2p protocol muxer)

[ianopolous]

Hi @diasdavid, great to see this progressing. :-) In what follows I'm only referring to public keys.

I think the main question to decide first is whether you want the format to be cbor. Using cbor means that you can put the object directly into ipfs and naturally reference and pin it by the resulting cid. We already do this in Peergos for both signing and boxing public keys which are merkle linked from a root object for each user.

If you agree that it should be cbor, then the initial int in my suggestion is exactly a multicodec (remember a cbor int is actually a varint), functionally equivalent to the lookup table in multihash and future proof. Then decoders specialise based on this int. The second part, which is the actual key bytes, doesn't need to be understood by a parser because cbor takes care of that by encoding the length with a varint.

The only thing to be careful of is that large keys can't be stored as a single flat array (I'm thinking multi-megabyte post quantum keys), because of the object size limit, so will need to be chunked and linked accordingly. So maybe the type prefix could also include whether the key material is a single raw flat array or a merkle link.

[daviddias]

Just had a brainstorm with @ianopolous on steps to move this forward.

• The proposal to make Keys IPLD objects has been received with good ears. Keys should be full unixfs files so that they can be transferred using a regular exchange, getting IPFS ready to handle keys really large (GB or TB even).
• We both agreed that storing a Key as an IPLD object is not a multikey as multi* in the multiformats sense. A requirement for a multiformat is that it is self-describable and in the case of the Keys as IPFS Files or even just as IPLD Objects, it would require unpacking the object to then get the type. This doesn't fall into the self-describable definition, it is just like a unixfs object.
• We are proposing that the IPFS Repo blocks and datastore are renamed to something (we don't have good names yet) that mean "blocks that get published and exchanged" and "blocks that do not get published and exchanged", for now let's call it RepoDatastoreA and RepoDatastoreB respectively.
  • RepoDatastoreA would have any node that is intended to get published in the DHT and exchanged through Bitswap. This includes: Files, Nodes created with the DAG API , including keys.
  • RepoDatastoreB would have any node that is not intended to get published in the DHT and exchanged through Bitswap. This includes: PrivateKey, DHT Records, Root hash Pinset and so on.
• This would be part of the path towards migrating DHT records to full IPLD nodes.

Some notes from the discussion https://cryptpad.fr/code/#/1/edit/h57w6Cgcu72ZD8puM60teA/Tp-OpCZxIFk5KBr7nTJkCKMw/

[daviddias]

Alright, we have more :)

We went through more examples and we concluded that the format we are looking for is more a "Linked-Data Key" than a "Multi-Key" as Keys are not described by their links (remember, Keys are stored in IPLD graphs)

[daviddias]

One more!

Will we enable some kind of ALPN for things like secio? The case I'm thinking is when I get the hash of the RSA PubKey, but I want to dial to that node using ECC.

This can be simply resolved by having all the nodes understand how RSA/ECC works so that they know how to make the crypto challenges (SECIO) without needing to have the same type of keys.

This will require some fun on SECIO, Identify and libp2p-switch

[Stebalien]

Overall, a BIG 👍 from me.

---

I'd still call that "multikey" as the key describes its type (and should probably have a field that says that it's a key). But that's getting into semantics...

Keys should be full unixfs files so that they can be transferred using a regular exchange, getting IPFS ready to handle keys really large (GB or TB even).

I don't see why they have to be unixfs files for this. Exchanges exchange blocks (and, eventually, DAGs); they generally aren't unixfs specific. However, I've been pushing to have the next iteration of unixfs to be able to treat IPLD DAGs as files, if that helps (so we can store IPLD DAGs in unixfs without losing information about its structure).

no key with in CID

That proposal was for performance and we can still do that (although we should definitely stop using the DHT, regardless of what we do). That is, we can use <multibase><cidv0><dag-cbor><mh-identity><length><the embedded key>.

edit: cidv0 should be cidv1

[ghost]

That is, we can use .

Wouldn't that go against "no CIDv0 unless it addresses an actual dag-pb node"?

[Stebalien]

Sorry, I meant <cidv1>.

[dignifiedquire]

@diasdavid curious about why you and @ianopolous suggested the keys being unixfs files, this seems like unnecessary overhead to me.

[daviddias]

@dignifiedquire we need to account for keys that will be GB or even TB in size #58 (comment)

[dignifiedquire]

That only means we need a concept of general sharding. Requiring to use unixfs objects seems the wrong approach to this for me, as it mixes two abstractions.

…

On 13. Nov 2017, 18:26 +0100, David Dias ***@***.***>, wrote: @dignifiedquire we need to account for keys that will be GB or even TB in size #58 (comment) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[ianopolous]

Does unixfs imply using protobufs? If so, then I would prefer a simpler cbor(ipld) based structure.

[daviddias]

It does not imply using protobufs, it only implies that an ipfs cat on the CID of the key should work.

There is a current endeavor of creating a new generation of unixfs using the new IPLD https://github.com/ipfs/ipld-unixfs

---

Edit(Kubuxu): fixed link to ipld-unixfs

[msporny]

Hey, I'm the current editor for the IETF Multihash spec: https://tools.ietf.org/html/draft-multiformats-multihash-00

I'm also updating Veres One to use multiformats for the cryptonym identifiers. Specifically, we do this for ed25519 keys:

// ed25519-pub 0xed01 + 32 pubkey-bytes
0xed01cccb336bf5e0f7b2fe0d7cfe0ccce7e2d9c59de5607a1bc1fce233a3b0caa11d
Example: did:v1:nym:z279wWXz4nugfh2XATAnFQkqaoSg97AWyNbsvdpr8hujamKJ

... and this for RSA keys (note the rsa-pub-fingerprint 0x5a value has not been requested yet):

// spki-der-fingerprint 0x5d + sha2-256 0x12 + 32 byte value 0x20
0x5a12209c82d16b3826b2616f11b23077a2949dcded03d774c90d7e241e071b57d9fea1
Example: did:v1:nym:z2czTJ1VEECSvESEamgp88mBLpqyJvyKvEE4YNamMoY1JWK29sKv

Is this the approach other folks are taking for cryptonyms (identifiers based on cryptographic material)?

[Stebalien]

Peer IDs are our current cryptographic identifiers. We currently just take this protobuf and then hash it with multihash.

We've also recently added a rule that all serialized keys shorter than 42 bytes should be hashed with the "identity" multihash so that it can be extracted from the key itself. This handles the ed25519 case and ensures that we always generate the same identifier from the same key.

We'd like to switch to CIDs/IPLD. In this world, the peer ID would just be a normal CID (e.g., cidv1-cbor-sha2-256-digest) and the key would likely be an IPLD object containing the key material and type (at a minimum).

---

Note: Unless the entire key is stored in the ID, there's little use in storing things like the rsa public key fingerprint in the ID. A sha2 hash should be sufficient.

[pawal]

@msporny In which wg is the draft discussed?

[msporny]

@pawal -- It hasn't been assigned to a WG yet. I want to get a few more revs of the spec done with possibly a test suite + 3 implementations passing the test suite before trying to push it into a WG.

[msporny]

@Stebalien said:

We'd like to switch to CIDs/IPLD. In this world, the peer ID would just be a normal CID (e.g., cidv1-cbor-sha2-256-digest) and the key would likely be an IPLD object containing the key material and type (at a minimum).

How are CIDs currently encoded? Here's what we are proposing:

w3c-ccg/lds-ed25519-2018#3

Does that look like it might be aligned with where CIDs want to go in IPFS? If not, why not?

Note: Unless the entire key is stored in the ID, there's little use in storing things like the rsa public key fingerprint in the ID. A sha2 hash should be sufficient.

The RSA SPKI public key fingerprint is a sha2-256/256 hash. There is an example of an RSA SPKI-based fingerprint used as a cryptographic CID:

w3c-ccg/lds-ed25519-2018#3

What do you think of that proposal? I'd like to get at least the Sovrin, Veres One, and IPFS communities aligned on cryptographic identifiers so I can propose a multibase+multicodec+multihash spec for cryptographic identifiers at IETF.

[pawal]

@msporny What wg do you have in mind?

A lot of things are going to change in the spec when going for standards track and going through a wg, so aiming for three implementations is not really necessary work, just more work for the implementations when things change.

[msporny]

What wg do you have in mind?

Perhaps SEC area and CFRG to start, get some input there. Then maybe move into ace. I expect that the area director will have an opinion on where this work goes... it's not clear that it fits neatly into an existing group.

A lot of things are going to change in the spec

hmm, I thought a good chunk of the multi* specs were pretty stable at this point. Are they not? Perhaps I'm misunderstanding where this work is at present. I thought there were multiple implementations of multibase, multicodec, and multihash already?

Or are you talking about the "how to encode CIDs" bit?

[pawal]

@msporny I meant that if you're aiming for standards track, getting the document through a wg will change a lot of details in the draft. Depending on the input of the wg.

[ChristopherA]

I'm needing to encode keys in base45 multiformats/multibase#64 encoded master seeds (BIP45) for QR encoding, in particular 32 and 64 byte master seeds, shamir secret shards (40 bytes), derived private and public keys (32 bytes plus path), ecdh signatures (72 bytes), Schnorr signatures (32 bytes or 64 with public key), etc.

All of these for QR encoded air gap scenarios.

Any progress on multikey?

-- Christopher Allen

[gobengo]

getting the document through a wg will change a lot of details in the draft. Depending on the input of the wg.
@pawal

now is a good time to shape the input of the wg. Here is a charter proposal.

There is also a new mailing list hosted by IETF to discuss multiformats. https://mailarchive.ietf.org/arch/browse/multiformats/