[Cryptography-dev] "intrinsic" symmetric key identifier?

[lvh]

Hi, 

> On Jul 2, 2016, at 6:52 PM, Frank Siebenlist <frank.siebenlist at gmail.com> wrote:
> The aim is to find the most convenient symmetric key identifier to embed in a cipher message that would require the minimum amount of key management.
> 
> What is best depends on the context. Sometimes it's easy because there is only one key, or the security context is so unambiguous that associating the right key is trivial. Other times it's a bit more challenging. We have an existing application with tens of long-lived keys, and the current key-management complicates key-rotation and upgrades to modern algos and such.

I’m assuming these keys are symmetric and don’t live in an HSM (since you seem to be able to perform arbitrary computation with them)?

> If both Alice and Bob can generate key identifiers (kid's) from the key that they share directly, like derive if from the symmetric key, then there is no need to exchange or agree upon a name for that key as it would be kind of a "true name" (read Vinge if you haven't ;-) ). The parties only have to agree on the key identifier derivation method.
> 
> For example, if Alice and Bob agree to name their symmetric keys by taking the sha256 of that key's bytes, base64url encode the hash, and represent it as a urn, like "urn:s256:V2jyhd8tX-19vpEhyrDzIHgUYyDA5MS1Qi71iw1SUP0". This would allow both parties to maintain their own key-db with (kid, key) associations. Embedding the kid in the exchanged cipher messages would allow both parties to easily find the key to decrypt the received message.
> (very much like we often use the hash of the public key (or pk-cert) to identify the private key to decrypt)

For some more context on “it depends what you want to accomplish, and generic schemes are hard”; Bob and Alice may also want to have key ids that only work for _them_ — e.g. Bob and Alice’s static DH keys are used to generate a shared secret used for an AD key wrap scheme.

> The kid embedded in the cipher message is no more than a “hint”. It could be signed as part of the whole cipher message, but its integrity can only be confirmed after the message is decrypted&authenticated. Changing the kid in a cipher message results in DoS, but so would flipping any other bit in that message.

Does a failed decryption cause Bob to reject the message, or just try all the other keys? If so, what’s the benefit between just giving keys names, like sequence numbers or even strings?

> In its most simple form, I believe that the kid-derivation could be a sha2 of the key as long as the key is "truly" random. The only concern may be that some use a simple hash of the key for key derivation...(?). To avoid any of those usage collisions, you could define the convention of pre-pending the key with some publicly know constant, like b'pre-kid-constant' or fancier.

SHA2’s problems are a little less obvious when inputs are fixed length, but keys aren’t always — I’d recommend a SHA3-era hash like BLAKE2b or SHA-3 itself to not have to worry about that part at all :)

> If one believes that a simple sha2 hash is only borderline enough secure (?), then maybe use a CMAC or HMAC, where you use the key on the key-value itself, and the resulting tag would constitute the identifier. (I did something like that in franks42/naclj with blake2)

What’s the key used to compute the MAC? (In this case, I think what you _really_ want is AD key wrapping schemes, including GCM-SIV’s tiny mode).

> Or use HKDF, with maybe a kid-derivation specific constant for the salt, a kid-specific info value, and a sufficient length of the resulting key, i.e. identifier, that makes everybody happy.

I’d probably go with BLAKE2b if this is _all_ you’re trying to do, but I think what you might really want is key wrap :)

> Hope this additional explanation helps.

A little :) Is this for encryption at rest, with multiple recipients, where the recipients are assumed to already have all of the keys?

> PS. Don’t believe I will resurrect that franks42/naclj - I’ll add a note about depreciation and send them to your effort - it was a good experience learning about Curve/Ed25519 and the nacl/libsodium code though - also trying to keep all data structures as immutable as possible was a good exercise.

It definitely has. I’m working on a blog post (series of blog posts) on crypto API design, particularly in the context of libsodium and the JVMs plethora of byte types.


lvh

> 
> On Fri, Jul 1, 2016 at 3:53 PM, lvh <_ at lvh.io> wrote:
>> 
>>> On Jul 1, 2016, at 12:54 PM, Frank Siebenlist <frank.siebenlist at gmail.com> wrote:
>>> 
>>> Hi lvh,
>>> 
>>> Guess you're the "lvh" who is responsible for "lvh/caesium" ;-).
>> 
>> Yup. I’m also a founding member of PyCA and the resident cryptographer, which is why I’m on this list :-)
>> 
>>> Good to see that you've reanimated that project! Believe you were kind of
>>> distracted for awhile, which "forced" me to play around with
>>> "franks42/naclj"... which has been on live-support for about a year
>>> now, because my new job consumes even my playtime.
>> 
>> It did what I needed it to do at the time, so I didn’t fix what wasn’t broken ;-) I don’t recall anyone reaching out or filing issues. Once someone did ask questions and contributed code, I was happy to merge/review/cut new releases/do new development. More dev is happening now to scratch my own itch :)
>> 
>> Currently I’m doing a lot of work around NMR as mentioned before, and API design around e.g. different byte buffer types, so that for example you can efficiently dump a nonce and a ciphertext in the same buffer, or derive multiple keys in one iteration of BLAKE2, etc. Also a bunch of work around e.g. pinning and verification of the produced binding and related benchmarking :)
>> 
>> I invite you to look at caesium again, because some of the criticisms you make in naclj’s README no longer apply (e.g. caesium no longer uses kalium and instead binds libsodium directly, albeit for a different reason than what naclj mentions). Because the binding is done in Clojure, it can do all sorts of metaprogramming including binding every permutation of a particular method for various byte types in addition to the inspection mentioned above, e.g.: https://github.com/lvh/caesium/blob/master/src/caesium/binding.clj#L56-L62
>> 
>> Do you intend to continue to develop naclj, or is it effectively retired?
>> 
>>> As part of that "franks42/naclj" effort, I suggested to standardize
>>> the derivation of a kid from the two curve25519 public keys. However,
>>> I recognize that you do not always have any DH-keys available when you
>>> have a bare symmetric key,
>> 
>> Is that scheme documented anywhere? I wonder what the use case is for two curve25519 pubkeys — the “obvious" case would seem to easily degenerate to the shared symmetric secret (after doing a DH exchange).
>> 
>>> so I suggested a scheme based on blake2. I
>>> wrote up some rationale for those choices here:
>>> "https://github.com/franks42/naclj/blob/master/Keys%2C%20IDs%2C%20and%20URNs.md",
>>> but never got much traction on the libsodium list,... and then I got
>>> distracted.
>>> 
>>> Now I'm faced again with similar key-management issues, which could
>>> benefit from such key-derived kid's - so I try again.
>>> 
>>> In summary, your suggestions all resonate very well, but... there are
>>> too many of them. Let's just pick one identifier derivation mechanism
>>> for symmetric keys, document it, implement it, use it!
>> 
>> I think there are a few problems preventing this from happening right now, including:
>> 
>> - Historically, cryptographers have not researched key wrap anywhere near as much as other schemes. I think the only reason it’s en vogue now is the interest in NMR, which at least a handful of cryptographers (Rogaway, Krovetz, and humbly, myself) care about now, and is incidentally a related problem.
>> - People want subtly different things for their protocols, further reducing interest. Do you just want to identify a key? That’s fine, but a problem many protocols dodge. Do you want to ship a key to someone who already has a secret or asymmetric key? AEAD (including NMR AEAD in particular, so key wrap) and just asymmetric encryption (a la non-PFS TLS or GPG) is probably where you’re going to land.
>> - How does this fit in a grander protocol and what is that protocol trying to accomplish?
>> - How is the key identifier authenticated? What prevents Mallory from just modifying the key id bytes to effectively deny service? E.g. if I’m doing this to make sure I can rotate keys effectively, how do I auth that? Ideally without replacing an unrotatable secret key with another unrotatable secret key :D (Effective key rotation for KEKs is definitely something I care about.)
>> - When keys are being sent alongside messages, how do we make this not a footgun for e.g. key selection attacks? (Granted, harder for EdDSA, but I want protocols to be correct for arbitrary schemes :)). PyCA cares about recipes being not footguns. That’s a mixed bag: on the one hand, it means we can give safe advice, on the other hand, it does mean that all we have is Fernet...
>> 
>> Overall, I think this is a reasonable idea for some protocols, but I think we need to be extremely clear about what that is, who it’s for, and how to use it.
>> 
>> 
>> lvh
>> 
>>> Groetjes, Frank.
>>> 
>>> On Fri, Jul 1, 2016 at 9:51 AM, lvh <_ at lvh.io> wrote:
>>>> Hi Frank,
>>>> 
>>>>> On Jul 1, 2016, at 11:11 AM, Frank Siebenlist <frank.siebenlist at gmail.com> wrote:
>>>>> 
>>>>> snip snip key identifiers
>>>> 
>>>> This is why some key derivation functions and PRFs have “purpose” or “info" fields, yes; including BLAKE2 and HKDF. Deriving a lesser key (which might just be a keyid) is a perfectly valid strategy from objcap practice. I’m doing something similar in the scheme of a larger semiprivate key scheme using libsodium. You probably do want something that explicitly supports that instead of just implicitly picking a particular nonce or whatever — I’m not sure which nonce you’re referring to, I don’t think the systems you mentioned take one. TL;DR: make the derivation completely distinct based on what you’re deriving and why you’re deriving it :)
>>>> 
>>>> You might also want to look at the related concept of NMR and key-wrap, which might let you solve the problem at a slightly different part of your protocol; essentially giving you a protected key with associated data about that key. It’s not entirely clear what the people standardizing GCM-SIV want to do exactly (other than “not TLS”, I don’t think they’ve said), but this is the obvious choice, especially given GCM-SIVs separate code path for tiny messages and the historical linking of the two from a crypto design perspective.
>>>> 
>>>> I am also writing NMR stuff on the side in libsodium/caesium, but that focuses mostly on being a Fernet replacement, rather than a keywrap, using secretbox (which makes it easy because big nonce space). Pretty sure I can translate it to the AEAD schemes, but the security proof gets iffier. Which reminds me: we should talk about Clojure bindings to libsodium some time :)
>>>> 
>>>> 
>>>> lvh
>>>> _______________________________________________
>>>> Cryptography-dev mailing list
>>>> Cryptography-dev at python.org
>>>> https://mail.python.org/mailman/listinfo/cryptography-dev
>>> _______________________________________________
>>> Cryptography-dev mailing list
>>> Cryptography-dev at python.org
>>> https://mail.python.org/mailman/listinfo/cryptography-dev
>> 
>> 
>> _______________________________________________
>> Cryptography-dev mailing list
>> Cryptography-dev at python.org
>> https://mail.python.org/mailman/listinfo/cryptography-dev
>> 
> _______________________________________________
> Cryptography-dev mailing list
> Cryptography-dev at python.org
> https://mail.python.org/mailman/listinfo/cryptography-dev