Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Chopped, Stored, Secured – The Story of the Hash Function

0xkrt26.github.io

Post reply on HN
Print view View original

11–18 of 18 posts

Re: Chopped, Stored, Secured – The Story of the Hash Function

#11

Post by teo_zero »

ksenzee wrote: post #4
tptacek wrote: post #2

The right way to understand modern general-purpose cryptographic hash functions (like SHA2) is just to understand block ciphers. A hash function is a block cipher's permutation core, wired to a "compression" function (much simpler than compression as typically understood; somewhat analogous to the chaining CBC does) that feeds blocks through the same permutation continuously, scrambling state as it goes. Everything g…

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

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

Re: Chopped, Stored, Secured – The Story of the Hash Function

#12

Post by ksenzee »

teo_zero wrote: post #11
ksenzee wrote: post #4

Earlier quoted context omitted.

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

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

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.

Re: Chopped, Stored, Secured – The Story of the Hash Function

#13

Post by dchest »

ksenzee wrote: post #4
tptacek wrote: post #2

The right way to understand modern general-purpose cryptographic hash functions (like SHA2) is just to understand block ciphers. A hash function is a block cipher's permutation core, wired to a "compression" function (much simpler than compression as typically understood; somewhat analogous to the chaining CBC does) that feeds blocks through the same permutation continuously, scrambling state as it goes. Everything g…

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

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

Re: Chopped, Stored, Secured – The Story of the Hash Function

#14

Post by NuclearPM »

thequux wrote: post #3

I can't judge the veracity of the history of hash functions, but the moment it starts talking about cryptography it goes completely off the rails: it seems to indicate that finite field exponentiation o'r high degree polynomials are used in cryptographic hash functions; they are emphatically not. It presents password hashing as just applying a suggest function to the password; in practice a KDF is used, which is a co…

O’r?

Re: Chopped, Stored, Secured – The Story of the Hash Function

#15

Post by AlotOfReading »

dchest wrote: post #13
ksenzee wrote: post #4

Earlier quoted context omitted.

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

> 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 t…

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

Re: Chopped, Stored, Secured – The Story of the Hash Function

#16

Post by tptacek »

ksenzee wrote: post #10
tptacek wrote: post #7

Earlier quoted context omitted.

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,…

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 wi…

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.

Re: Chopped, Stored, Secured – The Story of the Hash Function

#17

Post by dchest »

AlotOfReading wrote: post #15
dchest wrote: post #13

Earlier quoted context omitted.

> 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 t…

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

Oops, of course, thanks for correction!

Re: Chopped, Stored, Secured – The Story of the Hash Function

#18

Post by 0xkrt26 »

thequux wrote: post #3

I can't judge the veracity of the history of hash functions, but the moment it starts talking about cryptography it goes completely off the rails: it seems to indicate that finite field exponentiation o'r high degree polynomials are used in cryptographic hash functions; they are emphatically not. It presents password hashing as just applying a suggest function to the password; in practice a KDF is used, which is a co…

Author here. In the article I explicitly mention that the second part (about high degree polynomial and descrete exponentation) is based on Diffie-Hellman's 1976 paper and presents their one-way function constructions, not MD5 or SHA family (my goal is to cover the history of hashing from the beginning, so I haven't done a research on modern systems yet).

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)

Post reply on HN