[oleganza]

When I learned crypto 5-10 years ago, it turned out that a lot of "building blocks" are mostly hacks. Looking back from 2020s we see that some of the standards that we use for the last 20-30 years can in principle be thrown out of the window (they can't for compatibility reasons, though) and replaced with much cleaner and more universal replacements.

If we do not talk about modern exotic stuff (post-quantum crypto, zkSNARKS, homomorphic encryption), the 99% of everyday cryptography is based on two building blocks:

1. Symmetric crypto for ciphers and hash functions.

2. Algebraic group with "hard discrete log problem" for key exchange, signatures, asymmetric encryption and simple zero-knowledge proofs.

Historically, these two categories are filled with a zoo of protocols. E.g. AES is a block cipher, but SHA(1,2) is a hash function.

Today, you can roughly achieve everything of the above with two universal building blocks:

- Keccak for all of symmetric crypto: it is suited both for encryption, hashing, duplex transcripts for ZK protocols etc.

- Ristretto255 group based on Curve 25519: for diffie-hellman, signatures, key derivation, threshold schemes, encryption and more.

The problem is that none of the described features is implemented in a turnkey standard, and we are still stuck using older crypto. Heck, even Git is using SHA-1 still.

Then, after you have your building blocks, there are more hairy stuff such as application-specific protocols: TLS, Signal, PAKE/OPAQUE, proprietary hardware security schemes for full disk encryption and access controls etc.

[newpavlov]

>Keccak for all of symmetric crypto: it is suited both for encryption, hashing, duplex transcripts for ZK protocols etc.

Unfortunately, Keccak and sponge constructions in general are inherently sequential. Even with hardware acceleration it heavily restricts possible performance. For example, AES-CBC encryption is 4-8 times slower than AES-CTR on high-end CPUs with AES-NI available. VAES makes the difference even bigger. Algorithms like AES-GCM, ChaCha20, and BLAKE3 are designed specifically to allow parallelization.

[rainsford]

How much does the lack of parallelization matter in practice though? Sure, AES-CTR can be parallelized, but the authentication function you're probably pairing it with likely can't. And in a lot of cases I'm aware of where encryption parallelism is important for performance (e.g. line-rate VPN encryption), you can achieve parallelism for the operation as a whole without achieving stream based parallelism. In the VPN example, even if you can't encrypt all the blocks in a single packet in parallel, you can probably achieve just as much parallelism speedup by encrypting multiple packets in parallel.

[aleph_minus_one]

> Unfortunately, Keccak and sponge constructions in general are inherently sequential.

Couldn't you simply using BLAKE3 instead? To my knowledge BLAKE3 exactly was designed to solve this "parallelism problem" by combining the "cryptographic ideas" of BLAKE2 with the binary tree structure of Bao (the latter was designed to make the hash construction easy to parallelize).

[oconnor663]

Fwiw I don't think there's anything inherently sequential about the Keccak permutation itself. KangarooTwelve is a fully parallelizable hash built on Keccak. (Though they did use the sponge construction on the XOF side, so that part is serial.)

[newpavlov]

I meant the absorb and squeeze part. The permutation itself (or more specifically its round) could be efficiently implemented in hardware, but you can't mask latency by parallel application of the permutation. Yes, KangarooTwelve is an improvement in this regard, but the grandparent was talking specifically about Keccak/SHA-3.

[oleganza]

Sorry for lack of clarity, but i was saying “Keccak” and not “sha3” for that specific reason: it’s a permutation building block suitable for a whole range of constructions - cshake, kangaroo etc. sha3 specifically is an overkill and unnecessary imho.

CShake128 is much better replacement for hmac and sha512 in (zk)proofs, while Kangaroo for things like FDE and massive volumes of data.

[eXpl0it3r]

I'm absolutely clueless about crypto, isn't there also a trade-off between being mathematically superior and well optimized in software/hardware implementation?

[oleganza]

The tradeoff is not that simple (I wish it was :-).

Usually it goes like that: someone made something useful optimised for a specific use-case with certain time (or competence) constraints, within a total lack of decent alternatives. Then people adopt and use it, it becomes the standard. Then people want to do more things with it, and try to build around that thing, or on top of that thing and Frankenstein monsters get born and also become standard.

If you start from scratch you can do a crypto protocol that is both better designed (causes less UX pain and critical bugs) AND performs better on relevant hardware. Also do not forget that performance is easily solved by hardware: Moore's law and then custom hardware extensions are a thing.

Example: Keccak is so much better from the composition perspective, that when used ubiquitously you'd definitely have ubiquitous hardware support. But if everyone continues to use a mishmash of AES and SHA constructions on the pretext of "Keccak" is not as fast, then we'd never move forward. People would continue building over-complicated protocols, bearing subpar performance and keeping the reputation of dark wizardry inaccessible for mere mortals.

[eXpl0it3r]

> Also do not forget that performance is easily solved by hardware: Moore's law

"Just write slow algorithms, hardware will eventually get faster" doesn't really work when talking about performance implications now. If the hash algorithm used million of times doesn't perform on current user hardware, then the algorithm is simply not a good fit.

> and then custom hardware extensions are a thing.

That's the kind of trade-off I eluded to as well. As a developer of a tool (e.g. git), I'd pick hash algorithms that do have hardware extensions on the most common hardware and not use something, that may eventually get hardware extensions.

I guess developing such protocols right now for the future might still be advisable, but it seems odd to critic software that use well-optimized algorithms and fulfill the requirements.

[looofooo0]

sha-1 in git was just supposed to catch corruption, it was never intended to be used for security.

[hannob]

This is a justification that was made up after Git came under increasing criticism for its poor choise of a hash function after the shattered attack. It was already known that SHA-1 is weak before Git was invented.

The problem is... it doesn't line up with the facts.

Git has been using SHA-1 hashes for signatures since very early on. It also has claims in its documentation about "cryptographic security". It does not rigorously define what "cryptographic security" means, but plausibly, it should mean using a secure hash function without known weaknesses.

[looofooo0]

Torvald claimed:

"So that was one of the issues. But one of the issues really was, I knew I needed it to be distributed, but it needed to be really, really stable. And people kind of think that using the SHA-1 hashes was a huge mistake. But to me, SHA-1 hashes were never about the security. It was about finding corruption.

Because we’d actually had some of that during the BitKeeper things, where BitKeeper used CRCs and MD5s, right, but didn’t use it for everything. So one of the early designs for me was absolutely everything was protected by a really good hash."

https://github.blog/open-source/git/git-turns-20-a-qa-with-l...

[oleganza]

That's a valid point. However, modern hardware and crypto algorithms are fast enough that it pays off to have "do it all" protocols, with as little tradeoffs as possible.

Example: Git users do need both corruption protection AND secure authentication. If authentication is not built in, it will have to be built around. Building around is always going to be more costly in the end.

Unfortunately, 20-30 years ago considerations such as "sha1 is shorter + faster" were taken seriously, plus all the crypto that existed back then sucked big time. Remember Snowden scandal in 2013? That, plus Bitcoin and blockchains moving towards mainstream brought about review of TLS, started SHA-3 competition. Many more brains turned to crypto since then and the new era began.

[kbolino]

If this were true, then wouldn't MD5 have been the better choice?

Also, SHA-1's preimage resistance (which still isn't broken) is necessary for the security of signed commits, regardless of the hash function used for the signature itself, since a commit object references its tree and predecessor commit by their SHA-1 hashes.

[aiaiaiaiaiaiai]

Really nice summary! Thank you.