Post AF8i7ItPAOGpd744FU by tek@freeradical.zone
(DIR) More posts by tek@freeradical.zone
(DIR) Post #AF724t5Zk6yVmyxkZc by tek@freeradical.zone
2022-01-04T23:50:30Z
0 likes, 0 repeats
Is it thought that every 256-bit int could be a valid SHA-256 output?
(DIR) Post #AF73YyZQ1m2DQlphCK by smallsees@social.dropbear.xyz
2022-01-05T00:07:08Z
0 likes, 0 repeats
@tek It's an interesting thought experiment.That would mean an all-0s or all-1s could be a valid SHA-256 output. Either could be valid but very unlikely.Hashes don't have to be able to produce all values, but the good ones should. However, if say 5 values out of a possible 10^77 are not valid, is that really an issue?
(DIR) Post #AF74Dy94VpN5zB3Y37 by waterbear@scicomm.xyz
2022-01-05T00:14:31Z
0 likes, 0 repeats
@tek you could look at the code for the last round or two to at least see if it's possible
(DIR) Post #AF87vcl5so5DPzJCGO by eqe@aleph.land
2022-01-05T12:30:44Z
0 likes, 0 repeats
@tek yes I think so. Output is unbiased, there's nothing in the algorithm that says any particular bit or pattern of bits will have any particular value. So if you generate enough distinct inputs, the output should completely cover the range.It's quite easy to test this on truncated output, like 32 bits. I've done similar tests and got the expected results in the past...An interesting exercise is to estimate just how many inputs would be needed to actually cover the output range. It's quite large, because when you're trying to generate an input for the very last output, you're doing a brute force pre image attack on the full length hash.
(DIR) Post #AF8h9hcI7A4ow1dj4y by tek@freeradical.zone
2022-01-05T19:05:30Z
0 likes, 0 repeats
@smallsees I wouldn’t think it would be an issue. And that’s really what I was wondering: are there any impossible combinations, and if so, is it a small handful or like 2^192?(This is more out of curiosity than driven by any real concern.)
(DIR) Post #AF8hIHKdD63W1JT8Pg by tek@freeradical.zone
2022-01-05T19:07:03Z
0 likes, 0 repeats
@waterbear I don’t *think* that would be sufficient. Like, maybe due to previous rounds, there are specific combinations that can’t be reached.
(DIR) Post #AF8hJr8HaaPLLORels by drwho@hackers.town
2022-01-05T00:18:25Z
0 likes, 0 repeats
@smallsees @tek How much do you feel like trolling cryptography@metzdowd?
(DIR) Post #AF8hJraHuSoEkFY1QG by tek@freeradical.zone
2022-01-05T19:07:19Z
0 likes, 0 repeats
@smallsees @drwho I’m always down for a good troll.
(DIR) Post #AF8hSd8myo32YUrk5Q by zudlig@expired.mentality.rip
2022-01-05T00:47:34.377092Z
0 likes, 0 repeats
@tek Presumably it is, since otherwise you'd have found something wrong with sha-256.
(DIR) Post #AF8hSdcvAm9Q3wxo3M by tek@freeradical.zone
2022-01-05T19:08:42Z
0 likes, 0 repeats
@zudlig Would it be significantly wrong if, say, only all 0’s or all 1’s weren’t reachable?
(DIR) Post #AF8i7ItPAOGpd744FU by tek@freeradical.zone
2022-01-05T19:16:16Z
0 likes, 0 repeats
@eqe That was one possibility: that all outputs are possible (and equally likely). It seemed at least possible that the internal “wiring” means that some output states aren’t reachable, like all 0’s, all 1’s, or all alternating values, etc. (I’ve read Applied Cryptography, but that’s as close as I get to real crypto. This was a curiosity, a shower thought, and not something keeping me awake at night. 🙂)
(DIR) Post #AF8jWFs3ddQlS4tc6i by eqe@aleph.land
2022-01-05T19:31:57Z
0 likes, 0 repeats
@tek that's an interesting idea about "avoiding" special values! I don't *think* that kind of approach is in favor in the cryptography community, I think there would be a very justified worry that the mechanism to avoid them would weaken the hash in other ways. The special values are extremely rare (that's what makes them special) so just the probabilities are sufficient to be sure they are avoided.
(DIR) Post #AF8l7Ih4CqVusJz33o by tek@freeradical.zone
2022-01-05T19:49:53Z
0 likes, 0 repeats
@eqe I wasn’t thinking that such values might be deliberately avoided, but that an artifact of the algorithm is that certain values can’t be reached by any possible input.As a terrible example, RSA keys are prime. If there were some horrid hash function like “digest(x) = x & (pubkey + privkey)”, you could guarantee that pubkey + privkey will always be even, so the last bit off the output would always be 2. There’s nothing in the algorithm that deliberately enforces that condition.
(DIR) Post #AF8sBOtHo5TOvsbL8a by waterbear@scicomm.xyz
2022-01-05T21:09:01Z
0 likes, 0 repeats
@tek right, but there could be something in that logic that rules it out, in which case you got your answer without too much work