I have heard quotes by many that a SHA-512 hash output is random.
Does anyone know what method was used to come to this conclusion? If it is not randomized, how could that be shown?
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ There are hash function designed to function as random oracles (SHA-*) and there are ones that aren't (SWIFFT). $\endgroup$– DannyNiuCommented Jun 29, 2019 at 5:50
-
2$\begingroup$ SHA-512 output is not random at all, even though it may appear to be. $\endgroup$– PatriotCommented Jun 29, 2019 at 8:25
-
3$\begingroup$ I think we can all agree that pseudo-randomness is meant here: it is perceived as random bits to an observer that doesn't know the input to the hash function. $\endgroup$– Maarten Bodewes ♦Commented Jun 29, 2019 at 8:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Whilst the random oracle model(1) is the theoretical construct that should produce random 'looking' hash output, the scientific principle also requires that we test the hypothesis for proof.
So let us assume a simple set of inputs to the function. If the null hypothesis is that the output will appear random(2), the output will have certain testable properties:-
- For a simple counter input, we expect that any output bit will all uniformly distributed with $P(X = 0, X = 1) = \frac{1}{2}$, and for multiple conditional bits, $P(X | Y) = \frac{1}{2}$. These formulae extend as $P(\dots)= \frac{1}{2^n}$ and $P(\dots|\dots)= \frac{1}{2^n}$ for $n$ bit tuples.
- For randomly entered bits, we can count the numbers of set input and output bits and determine whether an avalanche effect is occurring. We expect that 50% of the bits will change per any random input. The actual probability mass function of the changes is expected to be Binomial, tending to a Normal probability distribution as the block width $(n)$ increases. We'd expect $\mu = 0.5n, \sigma = 0.5 \sqrt{n}$.
- Standardised randomness testing (Diehard, NIST etc.) can also be used, and we expect SHA-512 to pass all of them whilst hashing simple inputs. There is also no specialised distinguisher and can separate the hash output from a pseudo random sequence (3).
This 'random' hypothesis has so far held in the laboratory. So in your parlance, the output is random, and no one has yet proved otherwise. Some of these experiments might have shown it up otherwise, depending on the degree of bias.
Notes.
(1) A very imperfect model, as explained here.
(2) By random output, I take it you mean independent and identically distributed bits, not easily related to the input, or each other.
(3) Just be aware that these lab tests cannot determine any form of security measure.
answered Jun 30, 2019 at 17:00
-
$\begingroup$ Can you suggest reading for clarity on the variables used in the following formula. P(X=0,X=1)=12, and for multiple conditional bits, P(X|Y)=12. These formulae extend as P(…)=12n and P(…|…)=12n for n bit tuples. 2) You are correct identically distributed bits. $\endgroup$ Commented Jul 2, 2019 at 0:44
-
1$\begingroup$ @JonHutton Sorry Jon, I can't understand the meaning of your last point (2)... $\endgroup$ Commented Jul 2, 2019 at 0:55
-
$\begingroup$ I was asking if anyone or Paul Uszak could tell me a book, that I could read about the formulas he used in his post. "Can you suggest reading for clarity on the variables used in the following formula. P(X=0,X=1)=12, and for multiple conditional bits, P(X|Y)=12. These formulae extend as P(…)=12n and P(…|…)=12n for n bit tuples." His question in his notes section of his answer, " 2) By random output, I take it you mean independent and identically distributed bits, not easily related to the input, or each other." My post to clarify. 2) You are correct identically distributed bits. $\endgroup$ Commented Jul 2, 2019 at 2:53
-
1$\begingroup$ @JonHutton $P(X = 0, X = 1) = \frac{1}{2}$ simply means that the probability of any bit being either "0" or "1" is $1 \over 2$. Basic probability theory also means that if the bits are considered as tuples, then we can say $P(X = 00, X = 01, X = 10, X = 11) = \frac{1}{4}$. And so on with wider tuples. And likewise for conditional probabilities, the point here being that there are no conditional differences if the bits are all totally independent and un-correlated. So conditionally, it's also $\frac{1}{2^n}$. $\endgroup$ Commented Jul 2, 2019 at 10:00
$\begingroup$
$\endgroup$
SHA-512's output is neither random nor pseudo-random. A reasonable assumption is that one can define a function $F_k(x)$ based on SHA512 that will be a pseudorandom function. However, this is only when a random (secret) key $k$ is used. Having said all of the above, the random oracle model is a heuristic that can be applied when using SHA512. I suggest looking up the random oracle model to see what people mean by this.
answered Jun 30, 2019 at 8:08