Re: Use of cryptography with W3C VCs and DIDs released

On Fri, Apr 22, 2022 at 8:12 AM bengoering@gmail.com <bengoering@gmail.com>
wrote:

> Christopher, originally I read your message as being against all of the
> recommendations. Personally, I find at least the first couple
> recommendations fairly reasonable. Would you be willing to be more explicit
> about which recommendations, if any, you don’t find to be largely bad
> long-term decisions? Is there any common ground?
>

Some more of my highly-opinionated thoughts on this topic for
non-incremental, long-term use cases, this time on *Hash Algorithms*.

On Thu, Apr 21, 2022 at 3:27 PM Christopher Allen <
ChristopherA@lifewithalacrity.com> wrote:

> However, about the only thing I agree with is that we should start to
> transition away from SHA-256, initially maybe to SHAKE256 (though I have
> other nuances not considered by this report given VRFs, Schnorr and
> ZK-proofs opportunities).
>

My take is that SHA-256 until recently was* "Best Practice"*, however, I
believe it should now be moved to my category *"Best Practice ->
Legacy"* meaning
it is time now to start moving away from it.

SHA2, and in particular SHA-256 is not broken, there have been no
successful collision attacks. However, there are emerging weaknesses. For
instance, it appears that a SHA-256 can be distinguished from a random
oracle given 2^64 examples, so when SHA-256 is used alone as a method to
stretch entropy it isn't perfect, but neither is there a practical attack.
There are other possible attacks that on the horizon, but I don't believe
that any (if successful) would reduce SHA-256 to less then 2^80, which is
my current boundary of *"Legacy -> Deprecated"*. One attack in particular
might offer some special collisions down to 2^65.  I think there is a risk
that it will fall into my *"Legacy -> Deprecated"*  in the next decade.

In
> RECOMMENDATION: Implement all hash functions using approved cryptographic
modules.

…which if you read further is that they'd like to see everyone move
everyone to the SHA3 family.

SHA3 is basically a subset KECCAK-p family of mathematical permutations,
which is radically different from the SHA-2 family using an approach called
sponge construction. Overall, it addresses the key concerns with the SHA2,
and certainly is different enough from SHA2 that 30 years of approaches
attacking the SHA family don't apply.

SHA3 competed against a number of other approaches that also were
significant improvements over SHA2, but at a price. Among other things,
SHA3 is consistently slower in software hardware and faster in silicon with
dedicated circuits. It also may offer some quantum-resistant qualities, but
these are not proven.

However, there are other hash algorithms that address the issues of SHA2
that are not as radical, but have other advantages. Part of the reason why
SHA2 family is weak is that we understand it so well, and thus we also
understand how to improve that family.

Of these, my favorite is BLAKE2 https://www.blake2.net (and in
particular the BLAKE2b variant), which has a lot of advantages in speed,
can be run in parallel, is being used in IETF protocols, and mature and
reviewed implementations. Interestingly, it also leverages approaches from
the ChaCha family of ciphers (see my previous post on why I like ChaCha
https://lists.w3.org/Archives/Public/public-credentials/2022Apr/0112.html ).
The SRI report mentions BLAKE2 only once, saying that they recommend SHA3
over it with BBS+ signatures (this may be valid, but I've not dived into
this, but I also have real doubts.)

There are those that argue we should skip SHA3 entirely (or until the chip
industry supports it in silicon everywhere) (Adam Langley from Google
writes in https://www.imperialviolet.org/2017/05/31/skipsha3.html) but
there are counter-arguements as well
https://www.cryptologie.net/article/400/maybe-dont-skip-sha-3/

In my personal use cases I do care about speed and parallelization. I'm
particular interested in evaluating BLAKE3 (
https://github.com/BLAKE3-team/BLAKE3) as it is optimized for hash trees. I
want my future data formats to be correlation resistant by using large
redaction trees (inspired by Kademlia (
https://en.wikipedia.org/wiki/Kademlia) and Key Transparency with VRF
commitments).

In summary:

** *SHA-256d (aka double sha) - *"Legacy - Deprecated"* doesn't offer the
promises many claimed. In some specific attacks may reduce security to
2^64, though no devastating attacks on the horizon (see
https://crypto.stackexchange.com/questions/7895/weaknesses-in-sha-256d).
* SHA-256 - *"Best Practice -> Legacy"*
* BLAKE2b - *"Best Practice"*
* BLAKE3 - *"Emerging -> Best Practice"* (probably what I will use, still
needs evaluation)
* SHA3-128 - *"Emerging -> Best Practice"* (for software, or with
ristretto244 IETF standards) & *"Best Practice"* if silicon support for it
is available).
* SHA3-256 - *"Emerging -> Best Practice"* (probably overkill as a
replacement for SHA256, but may be useful for decaf448).

Note that the SRI document does not talk at all about VRFs (Verifiable
Random Functions https://tools.ietf.org/id/draft-goldbe-vrf-01.html), which
in many cases can serve the purpose of Hash Algorithms, but offer
advantages with asymettric public-private keys. VRFs have been deployed in
Certificate Transparency for over a decade, and are well proven. Though
there is little existing code for it, I'd like to see a VRF using ECC
aggregatable multisig curves that avoid small subgroup and invalid curve
attacks (right now only secp256k1, ristretto255 & decaf448).

* VRF-next - *"Needs spec/implementation -> Emerging"*

There are also interesting hash algorithms that are specifically designed
form MPC (Multi-Party Computation) which as a category have huge security
advantage at the cost of many order of magnitude computational cost +
network latency.  Using a hash algorithms optimized for zk-proofs and/or
MPC can speed them up to be practical. I've not sufficiently researched
these yet.

* MPK/ZK Hashes - "*"Needs study"*

I end again, with a request: The Blockchain Common community is seeking
support to do more here than just incrementally iterate on existing
cryptographic architectures for digital identity. I welcome your
participation to develop and define the next generation of these
technologies with research, specifications, reference libraries and tools.
Your monthly financial patronage (even if a small $20 a month, your social
proof of support is valuable!) at
https://github.com/support/BlockchainCommons.

-- Christopher Allen