[Cbor] Gordian Envelope and Crypto-Agility for its Hash

[Christopher Allen <[e-mail]>]

On Mon, Mar 6, 2023 at 1:55 PM Carsten Bormann <[e-mail]> wrote:

> On 2023-03-06, at 22:13, Christopher Allen <
> [e-mail]> wrote:
> > We will have an updated draft -01 this week, based on feedback from
> > many parties, including one of the co-authors of BLAKE, and have
> > decided we can't fully take advantage of its capabilities, and thus
> > will be using SHA-256.
>
> Makes this much more interesting to me (but don’t forget putting in some
> crypto agility!).
> (Generally, we try to get analysis from CFRG before we employ new crypto
> components; I am not aware of any attention that has been paid there to
> BLAKE3.)


I thought we should move this part of the conversation to a separate
thread.

When looking at switching back to SHA-256 from BLAKE3, we decided to
forebear crypto-agility with Gordian Envelope, especially as we have only 1
cryptographic algorithm (the hash), and desire to the conservative stance
that having only one makes it easier to review, and if something major
happens, we'll revise the standard to v2.

This is the approach that more and more cryptographers and protocol
designers like Wireguard are taking. I'm working now on an article about
the various risks of crypto-agility, and alternatives like crypto-suites,
methods, better layering, etc.

There is some discussion about trying to reserve a 2nd top-level tag for a
future version 2 without actually defining it as a form of future-proofing.
I'm not sure IANA would allow us to do that.

One fundamental issue specific to Gordian Envelope is that since we are
using the hash algorithm to sort, changes to the hash algorithm not only
change the digests of nodes, they can change the structure of the tree.

This is what our https://datatracker.ietf.org/doc/draft-mcnally-envelope/
 -01 draft will say (to be released this week) is:

"For changes that are more sweeping, like supporting a different hash
algorithm to produce the merkle tree digests, it would be necessary to use
a different top-level CBOR tag to represent the envelope itself. Currently
the envelope tag is #6.200, and the choice of digest algorithm in our
reference implementation is SHA-256. If this version were officially
released and a future version of Gordian Envelope was also released that
supported BLAKE3, it will need to have a different tag. However, a problem
for interoperability of these two distinct formats then arises in the
choice of whether a particular envelope is encoded assuming SHA-256 or
BLAKE3. Whenever there is a choice about two or more ways to encode
particular data, this violates the determinism requirement that Gordian
Envelopes are designed to uphold. In other words, an envelope encoding
certain information using SHA-256 will not, in general, be structurally
identical to the same information encoded in an envelope using BLAKE3. For
instance, they will both have different root hashes, and simply knowing
which algorithm produced each one will not help you know whether they have
equivalent content. Only two envelope cases actually encode their digest in
the binary stream: ELIDED and ENCRYPTED. If an envelope doesn't use either
of these cases, then you could choose to decode the envelope with either
algorithm, but if it does use either of these cases then the envelope will
still decode, but attempting to decrypt or unelide its contents will result
in mismatched digests. This is why the envelope itself needs to declare the
hashing algorithm used using its top-level CBOR tag, and why the choice of
which hash algorithm to commit to should be carefully considered."


I'd really not like to go down the alley that Protocol Labs did with
https://datatracker.ietf.org/doc/draft-multiformats-multihash/ — our
experience has been that the lack of constraint in that list resulted in a
large surface area for attacks.

In addition, specifically for us, as the Envelope tag and Wrapped Envelope
tag is used so often, adding even more bytes to specify a hash algorithm
risks support in constrained environments (for instance, signing on
JavaCard is quite limited).

That being said, if the community demands a different approach, we'll
support the outcome.

-- Christopher Allen