Given the SHA256 hashing algorithm, is there any shortcut to determine whether 1 bit will be set in the output in a given position (or set of positions)? Relaxing the question a little bit, is there any probabilistic test (simpler than performing a full hash of course) to tell if a bit will be set (with probability 1) or not set (with probability <1)?
Asked
Active
Viewed 196 times
1
Gianluca Ghettini
- 981
- 1
- 5
- 12
-
Should that last probability not be 1 as well? I can tell if a bit is unset with probability 0.5 without any problem at all. – Maarten Bodewes Dec 19 '17 at 14:18
-
@MaartenBodewes I mean a probabilistic outcome as some primality tests: this number is not prime with probability 1 or it is prime with probability <1 – Gianluca Ghettini Dec 19 '17 at 14:22
1 Answers
5
No, the output of the hash is indistinguishable from random. If there was a shortcut to determine the value of an output bit given a certain input (other than executing the hash) then the hash would be broken.
Maarten Bodewes
- 92,551
- 13
- 161
- 313
-
Well, if you are just interesting in bit one of output word 1 I presume you could shave off an instruction or two, but I have the strong impression that this will not count towards a break (or a shortcut) :P – Maarten Bodewes Dec 19 '17 at 14:33
-
Yeah, you can ignore most of the last round if you only need one bit and it doesn't happen to be in the most mixed positions. – otus Dec 19 '17 at 14:48