Chopped, Stored, Secured – The Story of the Hash Function
0xkrt26.github.io
0xkrt26.github.io
Considering that everything I have personal knowledge of here is obviously bunk, best ignore the rest of it too
As for the quantum computing stuff, I should have stated more clearly that I'm referring only to quantum computer allowing to calculate descrete logarithms rather fast, and provided a source such as https://math.mit.edu/~shor/elecpubs.html containing a link to the paper Algorithms for quantum computation: Discrete logarithms and factoring by Peter Shor. (I'm planning on covering post-quantum cryptography after I'm done with modern algorithms)
Everything gets tweaked differently because you have different constraints and parameters for a hash function than for a block cipher (though: there were SHA3 contestants that used Rijndael/AES for the core permutation, which is attractive because it has broad hardware support), but the core doodads are basically the same.
(And of course, you can run this argument in reverse and derive a cipher from a hash function trivially. That's how Chapoly happened.)
I have a decent intuition for what a hash function does after twenty years of encountering them in the wild. I don't even know what a block cipher is. I understand hash functions less after reading this than I did before. My conclusion is that a hash function is just a block cipher in the category of endofunctors.
The job of a modern block cipher core is to take a (heavily) iterated function, figure out how to apply a single input key securely to each of those iterated rounds, thoroughly combining the key with the block of data, achieving indistinguishability from random as quickly into the sequence of rounds as possible (in the same kind of simple step process as a Rubik's Cube), while breaking structure (like linearity) that would solve for the key or the data mathematically.
If you really were going for “simpler” rather than “more accurate” then I regret to inform you that you have joined the “monoid in the category of endofunctors” guy in room 2501 of the xkcd building.
Haha! Same for me (this being tptacek's comment, not the article).
It's like reading an introductory explanation of what an electric vehicle is ("a car with an electric motor that one can recharge at home") and then a comment saying "no, no, no, internally the whole powertrain is completely different, there are inverters and relays, etc."
A block cipher is just a keyed pseudorandom permutation! :)
Imagine that we have arranged all numbers from 0 to 115792089237316195423570985008687907853269984665640564039457584007913129639936 (2^256-1) in an array and then shuffled that array 115792089237316195423570985008687907853269984665640564039457584007913129639936 (2^256) times uniquely, each time recording the resulting shuffled array.
Here's the Go-like type:
var perm [115792089237316195423570985008687907853269984665640564039457584007913129639936]uint256
This is an unkeyed permutation (we can already build a secure hash function like SHA-3 from it, e.g. SHA-3 uses [2^1600]uint1600 permutation, while Ascon-Hash uses [2^320]uint320. The best we can do with ours is 2^127.5 collision security).
A keyed permutation takes 2^256 of these arrays, again shuffled differently and uniquely, so we have:
var keyedPerm [115792089237316195423570985008687907853269984665640564039457584007913129639936][115792089237316195423570985008687907853269984665640564039457584007913129639936]uint256
A block cipher is just P[k][p] where k and p are indexes into the arrays. Let's call k the key and p the plaintext — first we select one particular permutation using the key, and then select the resulting number (ciphertext) using the plaintext.
A simple hash function built from this keyed permutation splits the message into 256-bit numbers and then selects permutations using the message as k, and previous value as p and adds them together:
h = (some starting number called IV)
h += keyedPerm[m[0]][h]
h += keyedPerm[m[1]][h]
Of course, it's physically impossible to have that much memory for the arrays and it's physically impossible to shuffle that many times, so a block cipher is an approximation of that by smashing and rearranging bits, hoping to cause diffusion and confusion.
...then shuffled that array 115792089237316195423570985008687907853269984665640564039457584007913129639936 (2^256) times uniquely, each time recording the resulting shuffled array.