[ksenzee]

> just to understand block ciphers

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.

[dchest]

> just a block cipher in the category of endofunctors

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]

This is SHA-2, SHA-1, MD5, etc, and with a slight variation and a larger block cipher, BLAKE(1,2,3).

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.

[AlotOfReading]

    ...then shuffled that array 115792089237316195423570985008687907853269984665640564039457584007913129639936 (2^256) times uniquely, each time recording the resulting shuffled array.

Correct as an analogy for block ciphers, but note that there are (2^256)! unique permutations of the input space. You're selecting an unimaginably small slice of possible keyed pseudorandom permutations.

[dchest]

Oops, of course, thanks for correction!

[teo_zero]

> understand hash functions less after reading this than I did before.

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."

[ksenzee]

Yes, exactly. I don't object; it's salutary to find out you don't know anything about topic X. It's just disconcerting after having read and understood an article purporting to explain topic X.

[tptacek]

You know what they do, right, that's what you mean by having an intuition for them? Do you understand how they work? Why they're designed the way they are? I'm not saying you need to, but that's what the article is about.

[ksenzee]

I read and understood the article, including the math in it, then came here (I know, that’s the wrong order) and read your comment, and promptly decided I knew less than I did before I started. It was very much like learning to use a monad in Haskell without knowing category theory, and then reading an article about them. Just because you understand an article written for the educated general public doesn’t mean you have the vocabulary to understand experts speaking to other experts.

[tptacek]

Yeah, I'm not vouching for the article, just saying my response to it was that the simpler explanation for cryptographic hash functions is that they're a specialized application of a block cipher core.

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.

[ksenzee]

Do you mean “simpler” or do you mean “more accurate”? I’m quite willing to accept your explanation as more accurate, but it is not simpler, at least if you don’t know much about modern cryptography. To understand the article, all I needed was some algebra. I think my 13-year-old could mostly get it. To try to understand your second paragraph here, I’ve spent about fifteen minutes so far looking things up (starting with the definition of “block cipher” and ending somewhere about halfway through the Wikipedia article on AES) and I have a sense of its meaning in the abstract, but if there’s a quiz tomorrow I’m in trouble.

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.

[tptacek]

Both, I think? There's no way around having to learn about block cryptography, and trying to learn specifically about cryptographic hash functions without learning how a cipher works seems like a bad plan. You get these huge visualizations of the internals of SHA2 or whatever and then attempts to explain every operation in them, most of which are missing the core abstraction those operations were designed around; it's like recapitulating a block cipher from first principles.