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

Show HN: SHA-256 explained step-by-step visually

sha256algorithm.com

Post reply on HN
Print view View original

101–110 of 145 posts

Re: Show HN: SHA-256 explained step-by-step visually

#101

Post by pbsd »

p1mrx wrote: post #99
pbsd wrote: post #95

Earlier quoted context omitted.

A hash function aims to replicate the properties of a truly random function. The probability that a random function does _not_ output 0 given some specific input block is (1 - 1/2^n). Taking each of the possible 2^b input values into account this means that 0 is not an output for any input with probability (1 - 1/2^n)^(2^b) ~ e^(-2^(b-n)). For SHA-256 with n = 256 and b = 512 (one can treat the compression function a…

Your math looks plausible for an ideal cryptographic hash, but wouldn't you first have to prove that SHA-256 actually does behave as if each unique input generates an independent random number?

There's no real way to connect the compression function to any kind of mathematical model that would help here, other than modeling it as random. Provability is out the window.

So what you do is assume it behaves like a random function until proven otherwise, by _some_ property that deviates from this model. (This is not even the case for SHA-256, since neither the hash nor the compression function can be modeled as random oracles (due to length extension and the Davies-Meyer structure), but we can conveniently forget that for the duration of this thread.)

There _are_ some hash functions based on number-theoretic problems where you could reason about such things, but none of those are in common use since they are usually slow and/or require an output unstructured transformation anyway to turn them into proper, rather than just collision-resistant, hash functions.

Re: Show HN: SHA-256 explained step-by-step visually

#102

Post by dragontamer »

holoduke wrote: post #96
bsedlm wrote: post #44

Earlier quoted context omitted.

from what I've seen, there's a lot of "obscurity" to this; there are many seemingly arbitrary choices all over the place. In the end most encryption algorithms boil down to doing 'random' (arbitrary, hard to justify why) things to data and then undoing them exactly in order to decrypt. the math is all incredibly abstract but not all that complex, the high level of abstraction does make it quite difficult to grasp. Wh…

Isn't all the math involved in the end based on the modulo operator and prime numbers?

Yes in "Galois Field" arithmetic. But GF(2^8) (or whatever) arithmetic is only in AES and a few other ciphers/hash functions. SHA-256 looks like an XOR / Add / Rotate kinda cipher.

Re: Show HN: SHA-256 explained step-by-step visually

#103

Post by dragontamer »

bsedlm wrote: post #44
metalrain wrote: post #39

Earlier quoted context omitted.

Visualized like this it feels like security through obscurity, but there must be reason for this. I did wonder why initialization is like: 1. Initialize hash value h0 to h7: first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19). 2. Initialize array of K constants: first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311

from what I've seen, there's a lot of "obscurity" to this; there are many seemingly arbitrary choices all over the place. In the end most encryption algorithms boil down to doing 'random' (arbitrary, hard to justify why) things to data and then undoing them exactly in order to decrypt. the math is all incredibly abstract but not all that complex, the high level of abstraction does make it quite difficult to grasp. Wh…

> What's worse is that I fear there are incentives (mostly political/security interests) to keep the field small and to keep many people far away from this very practical use for all these beautiful, elegant, simple (but extremely abstract) mathematics (refering to the entire cryptography field).

I mean, everything you want to learn about crypto is available online, in libraries, in textbooks. Including differential cryptoanalysis, the theory behind these mathematical forms (Galois Field makes things _EASIER_, not harder actually. That's why CRC-checks and Reed-Solomon codes were based off of Galois Fields, and AES being based on GF(2^8) is to take advantage of those same properties).

--------

What has happened is that the "old generation" of programmers is dying out / retiring. And they aren't passing on their knowledge to the new generation. The "old generation" of programmers were high-math, abstract algebra and more, while "new generation" programmers just never bothered to learn this stuff.

Re: Show HN: SHA-256 explained step-by-step visually

#104

Post by pbsd »

colejohnson66 wrote: post #100
pbsd wrote: post #92

Earlier quoted context omitted.

SHA-256 is not a permutation; the expected cycle length is ~2^128. It's how collisions are (generically) found.

Pigeonhole principle?

Each new output value i can collide with output 1, 2, ..., i-1. So the collision probability of iteration i is (i-1)/2^256. Adding all of the iterations up you have 1/2^256 + 2/2^256 + ... + (i-1)/2^256 = 0.5 i (i-1)/2^256 which approaches 1/2 as you get to 2^128.

In reality you use some variant of Rho which does not store every previous value but uses something like Floyd's cycle detection or distinguished points and requires minimal storage, at the cost of some extra hash computations but still on the order of 2^128.

Re: Show HN: SHA-256 explained step-by-step visually

#105

Post by dragontamer »

colejohnson66 wrote: post #100
pbsd wrote: post #92

Earlier quoted context omitted.

SHA-256 is not a permutation; the expected cycle length is ~2^128. It's how collisions are (generically) found.

Pigeonhole principle?

This situation calls for Birthday paradox, not pigeon hole.

Re: Show HN: SHA-256 explained step-by-step visually

#107

Post by dragontamer »

taviso wrote: post #19

That's really cool. I made a terrible one for SHA1 years ago, yours is 1000x better. https://lock.cmpxchg8b.com/sha1/visualize.html I read a paper at the time where someone described a tool they made to find a near-collision, they explained they were just flipping bits and visually observing the affects. That sounded kinda fun, but they didn't release it, so I tried to replicate it from their description!

Your tool seems to understand the gist of differential cryptography better though.

You can track a 1-bit change or 3-bit change to "M" and see how it propagates through the SHA256 rounds in your tool.

----------

So your tool is probably better at understanding the underlying design of SHA2. We know that SHA2 was created well into the era of differential-analysis for example, so the designers would have inevitably done analysis similar to how your tool works.

Re: Show HN: SHA-256 explained step-by-step visually

#108

Post by miki725 »

oconnor663 wrote: post #35

Oh this is great. When we taught SHA-256 last semester, we linked to this YouTube video: https://youtu.be/f9EbD6iY9zI . Next time we do it, we'll probably link to both. Having several different ways to visualize the same thing is very helpful, and I like that this one moves quickly. A couple of details missing from this visualization are how you pad a message to be a multiple of the block size, and how you chain bloc…

Was about to reply with the link to the project. If anyone is curious about sha2 highly highly recommend to go thorough the project. Jack did an amazing job explaining everything step by step. Writing the code really helps to understand all the concepts much better.

Re: Show HN: SHA-256 explained step-by-step visually

#109

Post by a-dub »

this is funny. when i first learned the algorithm, i found some matlab code that computes it with bit vectors. i added support for displaying them as an image and used the movie feature to generate step by step movies to build intuition.

nice to see someone build something polished that visualizes it in the same way. once you look at the mechanics for each round of the compression function and see the bits get swirled around for yourself, it starts to make intuitive sense.

the other big intuitions are of course, the trapdoor nature of add mod 2^32 (which is implicit in unsigned integer overflow on many machines) and the fact that some operations (like xor) operate in galois field 2, while others (like addition) operate in galois field 32 and the repeated stacking of the operations in different fields gives the function it's nonlinear trapdoor property.

i remember reading a pretty good paper on the arx (add, rotate, xor) family of ciphers back in the day (sort of in the vein of, is that all you need?)...

Post reply on HN