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

91–100 of 145 posts

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

#91

Post by orangepenguin »

arcastroe wrote: post #88
orangepenguin wrote: post #82

Earlier quoted context omitted.

Maybe I'm being incredibly naive, but it seems like this would be trivial. Can you just start with the output hash and then essentially run the algorithms backwards? Obviously the resulting "input" would be random-ish garbage, but it seems like if all you care about is the output, you can pretty much just "pick" any data for the last step that produces the output. Then do likewise for the step prior, and so on.

As a comment above stated, part of the "input" is the initialized values: > Initialize hash value h0 to h7: first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19). My guess is h0 to h7 change throughout the algorithm. If you perform each step in "reverse" as you suggest, "picking" any input at each step that produces the required output for that step, then you may not arrive to the cor…

Ah, yep. You're right. I overlooked that part. It looks like it's truly non-reversible—even if you don't care what the resulting input is.

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

#92

Post by pbsd »

tromp wrote: post #15
em3rgent0rdr wrote: post #12

Earlier quoted context omitted.

how long would the cycle last before it starts repeating?

On the order of 2^256 steps, if SHA-256 behaves randomly, since the largest cycle in a random permutation on N elements has expected length ~ 0.62 * N.

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

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

#93

Post by p1mrx »

orangepenguin wrote: post #91
arcastroe wrote: post #88

Earlier quoted context omitted.

As a comment above stated, part of the "input" is the initialized values: > Initialize hash value h0 to h7: first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19). My guess is h0 to h7 change throughout the algorithm. If you perform each step in "reverse" as you suggest, "picking" any input at each step that produces the required output for that step, then you may not arrive to the cor…

Ah, yep. You're right. I overlooked that part. It looks like it's truly non-reversible—even if you don't care what the resulting input is.

If you do ever figure out how to reverse SHA-256, best keep it a secret until you've sold all your free Bitcoin.

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

#94

Post by sedatk »

tptacek wrote: post #71
picture wrote: post #36

So, how do people come up with these things? I assume every aspect of the design is carefully considered to defend it against various attacks. For example, why "right rotate 7 XOR right rotate 18 XOR right shift 3" and not "right rotate 2 XOR right rotate 3 XOR right shift 4"?

It's helpful to understand that the algorithm wasn't designed the way it's presented in this illustration, and consists of somewhat discrete components. It's an iterated design, like a block cipher, meaning that it's built around a simple round function that's repeated a bunch of times on each input, rather than a super-complicated function run once. It belongs to a large, important family of cryptographic hashes cal…

What a great question and what an excellent answer. Thank you!

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

#95

Post by pbsd »

p1mrx wrote: post #68
y42 wrote: post #59

Earlier quoted context omitted.

Sure, that would be a pretty high difficult factor, but its possible.

But is it provably possible for SHA-256? An n-bit cryptographic hash function should ideally cover every n-bit output value, given slightly more than n bits of input, but I don't know whether this has been proven for any real-world functions.

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 as a 768 to 256 bit random function, but we can stick to the worst-case single-block message case here) we have that the probability of 0 _being_ an output for a single-block message is 1-e^(-256) which effectively means it exists, but the probability never quite reaches 1.

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

#96

Post by holoduke »

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…

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

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

#98

Post by [deleted] »

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?

[deleted]

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

#99

Post by p1mrx »

pbsd wrote: post #95
p1mrx wrote: post #68

Earlier quoted context omitted.

But is it provably possible for SHA-256? An n-bit cryptographic hash function should ideally cover every n-bit output value, given slightly more than n bits of input, but I don't know whether this has been proven for any real-world functions.

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?

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

#100

Post by colejohnson66 »

pbsd wrote: post #92
tromp wrote: post #15

Earlier quoted context omitted.

On the order of 2^256 steps, if SHA-256 behaves randomly, since the largest cycle in a random permutation on N elements has expected length ~ 0.62 * N.

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

Pigeonhole principle?
Post reply on HN