Do hash functions need to “look random”?
up vote
5
down vote
favorite
I've noticed that looking random is not often listed as a requirement for a good hash function in the same way that preimage or collision resistance is.
- Do we need hash functions to look random?
Specifically, suppose $s$ is a seed, and consider the PRNG that outputs $$H(s |0) | H(s |1 ) | H(s |2) | ...$$
- Do we need this to be indistinguishable from random?
- Will any protocols be weakened if it wasn't?
hash random-number-generator
edited Nov 8 at 9:04
kelalaka
4,07211635
asked Nov 8 at 8:26
David Lui
1533
add a comment |
up vote
5
down vote
favorite
I've noticed that looking random is not often listed as a requirement for a good hash function in the same way that preimage or collision resistance is.
- Do we need hash functions to look random?
Specifically, suppose $s$ is a seed, and consider the PRNG that outputs $$H(s |0) | H(s |1 ) | H(s |2) | ...$$
- Do we need this to be indistinguishable from random?
- Will any protocols be weakened if it wasn't?
hash random-number-generator
edited Nov 8 at 9:04
kelalaka
4,07211635
asked Nov 8 at 8:26
David Lui
1533
1
looking random? What is the definition? We can apply some statistical test to determine the randomness. If they fail to pass some margins, this will indicate that there is some weakness in the construction to behave like randomly.
– kelalaka
Nov 8 at 9:03
Note that for hash functions to have $n$ bits of security or $n/2$ bits of security for collision resistance you would expect a relatively well distributed output: if some values are more likely then the security of the function would also be affected. A hash with an output of 256 bits would not deliver 256 / 128 bits of security, in other words.
– Maarten Bodewes
Nov 8 at 15:13
"Being random" is an opposite to "having patterns". And "having patterns" is close to "insecure". So if you are talking about cryptografically secure hash function then I would say "yes".
– freakish
Nov 8 at 20:53
I found that Matthew Green's blog post about indifferentiability and his series about the Random Oracle Model are wonky-but-not-too-hard readings to get a beginner's sense of hash functions vs. randomness. Lots of linked references to follow up, too.
– Luis Casillas
Nov 9 at 0:25
@kelalaka By "looking random" I mean : For every efficient adversary that takes in a bitstring and outputs 0 or 1, give the adversary either H(s ||0) || H(s || 1) || H(s || 2) || ...., or a random string . The difference in the probability that the adversary outputs 1 is negligible.
– David Lui
Nov 9 at 4:58
add a comment |
up vote
5
down vote
favorite
up vote
5
down vote
favorite
I've noticed that looking random is not often listed as a requirement for a good hash function in the same way that preimage or collision resistance is.
- Do we need hash functions to look random?
Specifically, suppose $s$ is a seed, and consider the PRNG that outputs $$H(s |0) | H(s |1 ) | H(s |2) | ...$$
- Do we need this to be indistinguishable from random?
- Will any protocols be weakened if it wasn't?
hash random-number-generator
edited Nov 8 at 9:04
kelalaka
4,07211635
asked Nov 8 at 8:26
David Lui
1533
I've noticed that looking random is not often listed as a requirement for a good hash function in the same way that preimage or collision resistance is.
- Do we need hash functions to look random?
Specifically, suppose $s$ is a seed, and consider the PRNG that outputs $$H(s |0) | H(s |1 ) | H(s |2) | ...$$
- Do we need this to be indistinguishable from random?
- Will any protocols be weakened if it wasn't?
hash random-number-generator
hash random-number-generator
edited Nov 8 at 9:04
kelalaka
4,07211635
asked Nov 8 at 8:26
David Lui
1533
edited Nov 8 at 9:04
kelalaka
4,07211635
asked Nov 8 at 8:26
David Lui
1533
edited Nov 8 at 9:04
kelalaka
4,07211635
edited Nov 8 at 9:04
kelalaka
4,07211635
edited Nov 8 at 9:04
kelalaka
4,07211635
4,07211635
asked Nov 8 at 8:26
David Lui
1533
asked Nov 8 at 8:26
David Lui
1533
asked Nov 8 at 8:26
David Lui
1533
1533
1
looking random? What is the definition? We can apply some statistical test to determine the randomness. If they fail to pass some margins, this will indicate that there is some weakness in the construction to behave like randomly.
– kelalaka
Nov 8 at 9:03
Note that for hash functions to have $n$ bits of security or $n/2$ bits of security for collision resistance you would expect a relatively well distributed output: if some values are more likely then the security of the function would also be affected. A hash with an output of 256 bits would not deliver 256 / 128 bits of security, in other words.
– Maarten Bodewes
Nov 8 at 15:13
"Being random" is an opposite to "having patterns". And "having patterns" is close to "insecure". So if you are talking about cryptografically secure hash function then I would say "yes".
– freakish
Nov 8 at 20:53
I found that Matthew Green's blog post about indifferentiability and his series about the Random Oracle Model are wonky-but-not-too-hard readings to get a beginner's sense of hash functions vs. randomness. Lots of linked references to follow up, too.
– Luis Casillas
Nov 9 at 0:25
@kelalaka By "looking random" I mean : For every efficient adversary that takes in a bitstring and outputs 0 or 1, give the adversary either H(s ||0) || H(s || 1) || H(s || 2) || ...., or a random string . The difference in the probability that the adversary outputs 1 is negligible.
– David Lui
Nov 9 at 4:58
add a comment |
1
looking random? What is the definition? We can apply some statistical test to determine the randomness. If they fail to pass some margins, this will indicate that there is some weakness in the construction to behave like randomly.
– kelalaka
Nov 8 at 9:03
Note that for hash functions to have $n$ bits of security or $n/2$ bits of security for collision resistance you would expect a relatively well distributed output: if some values are more likely then the security of the function would also be affected. A hash with an output of 256 bits would not deliver 256 / 128 bits of security, in other words.
– Maarten Bodewes
Nov 8 at 15:13
"Being random" is an opposite to "having patterns". And "having patterns" is close to "insecure". So if you are talking about cryptografically secure hash function then I would say "yes".
– freakish
Nov 8 at 20:53
I found that Matthew Green's blog post about indifferentiability and his series about the Random Oracle Model are wonky-but-not-too-hard readings to get a beginner's sense of hash functions vs. randomness. Lots of linked references to follow up, too.
– Luis Casillas
Nov 9 at 0:25
@kelalaka By "looking random" I mean : For every efficient adversary that takes in a bitstring and outputs 0 or 1, give the adversary either H(s ||0) || H(s || 1) || H(s || 2) || ...., or a random string . The difference in the probability that the adversary outputs 1 is negligible.
– David Lui
Nov 9 at 4:58
1
1
looking random? What is the definition? We can apply some statistical test to determine the randomness. If they fail to pass some margins, this will indicate that there is some weakness in the construction to behave like randomly.
– kelalaka
Nov 8 at 9:03
looking random? What is the definition? We can apply some statistical test to determine the randomness. If they fail to pass some margins, this will indicate that there is some weakness in the construction to behave like randomly.
– kelalaka
Nov 8 at 9:03
Note that for hash functions to have $n$ bits of security or $n/2$ bits of security for collision resistance you would expect a relatively well distributed output: if some values are more likely then the security of the function would also be affected. A hash with an output of 256 bits would not deliver 256 / 128 bits of security, in other words.
– Maarten Bodewes
Nov 8 at 15:13
Note that for hash functions to have $n$ bits of security or $n/2$ bits of security for collision resistance you would expect a relatively well distributed output: if some values are more likely then the security of the function would also be affected. A hash with an output of 256 bits would not deliver 256 / 128 bits of security, in other words.
– Maarten Bodewes
Nov 8 at 15:13
"Being random" is an opposite to "having patterns". And "having patterns" is close to "insecure". So if you are talking about cryptografically secure hash function then I would say "yes".
– freakish
Nov 8 at 20:53
"Being random" is an opposite to "having patterns". And "having patterns" is close to "insecure". So if you are talking about cryptografically secure hash function then I would say "yes".
– freakish
Nov 8 at 20:53
I found that Matthew Green's blog post about indifferentiability and his series about the Random Oracle Model are wonky-but-not-too-hard readings to get a beginner's sense of hash functions vs. randomness. Lots of linked references to follow up, too.
– Luis Casillas
Nov 9 at 0:25
I found that Matthew Green's blog post about indifferentiability and his series about the Random Oracle Model are wonky-but-not-too-hard readings to get a beginner's sense of hash functions vs. randomness. Lots of linked references to follow up, too.
– Luis Casillas
Nov 9 at 0:25
@kelalaka By "looking random" I mean : For every efficient adversary that takes in a bitstring and outputs 0 or 1, give the adversary either H(s ||0) || H(s || 1) || H(s || 2) || ...., or a random string . The difference in the probability that the adversary outputs 1 is negligible.
– David Lui
Nov 9 at 4:58
@kelalaka By "looking random" I mean : For every efficient adversary that takes in a bitstring and outputs 0 or 1, give the adversary either H(s ||0) || H(s || 1) || H(s || 2) || ...., or a random string . The difference in the probability that the adversary outputs 1 is negligible.
– David Lui
Nov 9 at 4:58
add a comment |
1 Answer
1
active
oldest
votes
up vote
15
down vote
accepted
The answer is most certainly not! Well, I sort of lied, since it depends on what you are doing. I'll explain.
The basic property of hash functions is collision resistance, and this requires nothing beyond that. The output doesn't have to look random in any form, and this suffices for anywhere that you need collision resistance.
However, in many cases, because most hash functions in practice do look sort of random (completely undefined), they are used for other things. For example, HMAC assumes that the compression function (with one part of the input being the key) is essentially a pseudorandom function. More extreme, but very common examples, are the modeling of the hash function as a "random oracle". This is used for OEAP encryption padding, in most cases in practice for signatures, and more. You also somewhat assume this property for hashing passwords. (Note that for any hash function $H$, if you define $H'(x) = x|_n|H(x)$ where $x|_n$ is the first $n$ bits of $x$, then $H'$ is collision resistant if $H$ is collision resistant. However $H'$ would be a very poor choice for password hashing.)
answered Nov 8 at 12:21
Yehuda Lindell
18.2k3359
1
It's also good to add that there is a strong separation between collision-resistance and "looking random", i.e. you can have collision-resistant hash functions whose output does not look random at all! e.g. $H'(x) = 0^ell|H(x)$ where $H$ is a collision-resistant hash function. (Realized you addressed this in the answer already)
– Daniel
Nov 8 at 13:33
1
@Daniel You can even give an example in the other direction. I.e., a function can look random for some reasonable interpretation of "looking random" but have trivial collisions. E.g., if the function would happen to be a PRG for inputs somewhat shorter than the output size. Those certainly "look random", but their security says nothing about collisions.
– Maeher
Nov 8 at 14:57
1
An interesting class of hashes to consider in this discussion are similarity preserving hashes. These are very intentionally and specifically non-random, and are very useful in a number of scenarios. A survey of the motivations and methods is given here: arxiv.org/pdf/1408.2927.pdf
– Ken Goss
Nov 8 at 15:16
1
@UKMonkey this is not a good example since it doesn’t compress the output. Collision resistance without compression is trivial and uninteresting.
– Yehuda Lindell
Nov 8 at 15:33
1
@UKMonkey an arbitrary size means that it has to work for arbitrary size inputs, so also large inputs.
– Yehuda Lindell
Nov 8 at 15:42
|
show 6 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
15
down vote
accepted
The answer is most certainly not! Well, I sort of lied, since it depends on what you are doing. I'll explain.
The basic property of hash functions is collision resistance, and this requires nothing beyond that. The output doesn't have to look random in any form, and this suffices for anywhere that you need collision resistance.
However, in many cases, because most hash functions in practice do look sort of random (completely undefined), they are used for other things. For example, HMAC assumes that the compression function (with one part of the input being the key) is essentially a pseudorandom function. More extreme, but very common examples, are the modeling of the hash function as a "random oracle". This is used for OEAP encryption padding, in most cases in practice for signatures, and more. You also somewhat assume this property for hashing passwords. (Note that for any hash function $H$, if you define $H'(x) = x|_n|H(x)$ where $x|_n$ is the first $n$ bits of $x$, then $H'$ is collision resistant if $H$ is collision resistant. However $H'$ would be a very poor choice for password hashing.)
answered Nov 8 at 12:21
Yehuda Lindell
18.2k3359
1
It's also good to add that there is a strong separation between collision-resistance and "looking random", i.e. you can have collision-resistant hash functions whose output does not look random at all! e.g. $H'(x) = 0^ell|H(x)$ where $H$ is a collision-resistant hash function. (Realized you addressed this in the answer already)
– Daniel
Nov 8 at 13:33
1
@Daniel You can even give an example in the other direction. I.e., a function can look random for some reasonable interpretation of "looking random" but have trivial collisions. E.g., if the function would happen to be a PRG for inputs somewhat shorter than the output size. Those certainly "look random", but their security says nothing about collisions.
– Maeher
Nov 8 at 14:57
1
An interesting class of hashes to consider in this discussion are similarity preserving hashes. These are very intentionally and specifically non-random, and are very useful in a number of scenarios. A survey of the motivations and methods is given here: arxiv.org/pdf/1408.2927.pdf
– Ken Goss
Nov 8 at 15:16
1
@UKMonkey this is not a good example since it doesn’t compress the output. Collision resistance without compression is trivial and uninteresting.
– Yehuda Lindell
Nov 8 at 15:33
1
@UKMonkey an arbitrary size means that it has to work for arbitrary size inputs, so also large inputs.
– Yehuda Lindell
Nov 8 at 15:42
|
show 6 more comments
up vote
15
down vote
accepted
The answer is most certainly not! Well, I sort of lied, since it depends on what you are doing. I'll explain.
The basic property of hash functions is collision resistance, and this requires nothing beyond that. The output doesn't have to look random in any form, and this suffices for anywhere that you need collision resistance.
However, in many cases, because most hash functions in practice do look sort of random (completely undefined), they are used for other things. For example, HMAC assumes that the compression function (with one part of the input being the key) is essentially a pseudorandom function. More extreme, but very common examples, are the modeling of the hash function as a "random oracle". This is used for OEAP encryption padding, in most cases in practice for signatures, and more. You also somewhat assume this property for hashing passwords. (Note that for any hash function $H$, if you define $H'(x) = x|_n|H(x)$ where $x|_n$ is the first $n$ bits of $x$, then $H'$ is collision resistant if $H$ is collision resistant. However $H'$ would be a very poor choice for password hashing.)
answered Nov 8 at 12:21
Yehuda Lindell
18.2k3359
1
It's also good to add that there is a strong separation between collision-resistance and "looking random", i.e. you can have collision-resistant hash functions whose output does not look random at all! e.g. $H'(x) = 0^ell|H(x)$ where $H$ is a collision-resistant hash function. (Realized you addressed this in the answer already)
– Daniel
Nov 8 at 13:33
1
@Daniel You can even give an example in the other direction. I.e., a function can look random for some reasonable interpretation of "looking random" but have trivial collisions. E.g., if the function would happen to be a PRG for inputs somewhat shorter than the output size. Those certainly "look random", but their security says nothing about collisions.
– Maeher
Nov 8 at 14:57
1
An interesting class of hashes to consider in this discussion are similarity preserving hashes. These are very intentionally and specifically non-random, and are very useful in a number of scenarios. A survey of the motivations and methods is given here: arxiv.org/pdf/1408.2927.pdf
– Ken Goss
Nov 8 at 15:16
1
@UKMonkey this is not a good example since it doesn’t compress the output. Collision resistance without compression is trivial and uninteresting.
– Yehuda Lindell
Nov 8 at 15:33
1
@UKMonkey an arbitrary size means that it has to work for arbitrary size inputs, so also large inputs.
– Yehuda Lindell
Nov 8 at 15:42
|
show 6 more comments
up vote
15
down vote
accepted
up vote
15
down vote
accepted
The answer is most certainly not! Well, I sort of lied, since it depends on what you are doing. I'll explain.
The basic property of hash functions is collision resistance, and this requires nothing beyond that. The output doesn't have to look random in any form, and this suffices for anywhere that you need collision resistance.
However, in many cases, because most hash functions in practice do look sort of random (completely undefined), they are used for other things. For example, HMAC assumes that the compression function (with one part of the input being the key) is essentially a pseudorandom function. More extreme, but very common examples, are the modeling of the hash function as a "random oracle". This is used for OEAP encryption padding, in most cases in practice for signatures, and more. You also somewhat assume this property for hashing passwords. (Note that for any hash function $H$, if you define $H'(x) = x|_n|H(x)$ where $x|_n$ is the first $n$ bits of $x$, then $H'$ is collision resistant if $H$ is collision resistant. However $H'$ would be a very poor choice for password hashing.)
answered Nov 8 at 12:21
Yehuda Lindell
18.2k3359
The answer is most certainly not! Well, I sort of lied, since it depends on what you are doing. I'll explain.
The basic property of hash functions is collision resistance, and this requires nothing beyond that. The output doesn't have to look random in any form, and this suffices for anywhere that you need collision resistance.
However, in many cases, because most hash functions in practice do look sort of random (completely undefined), they are used for other things. For example, HMAC assumes that the compression function (with one part of the input being the key) is essentially a pseudorandom function. More extreme, but very common examples, are the modeling of the hash function as a "random oracle". This is used for OEAP encryption padding, in most cases in practice for signatures, and more. You also somewhat assume this property for hashing passwords. (Note that for any hash function $H$, if you define $H'(x) = x|_n|H(x)$ where $x|_n$ is the first $n$ bits of $x$, then $H'$ is collision resistant if $H$ is collision resistant. However $H'$ would be a very poor choice for password hashing.)
answered Nov 8 at 12:21
Yehuda Lindell
18.2k3359
answered Nov 8 at 12:21
Yehuda Lindell
18.2k3359
answered Nov 8 at 12:21
Yehuda Lindell
18.2k3359
answered Nov 8 at 12:21
Yehuda Lindell
18.2k3359
18.2k3359
1
It's also good to add that there is a strong separation between collision-resistance and "looking random", i.e. you can have collision-resistant hash functions whose output does not look random at all! e.g. $H'(x) = 0^ell|H(x)$ where $H$ is a collision-resistant hash function. (Realized you addressed this in the answer already)
– Daniel
Nov 8 at 13:33
1
@Daniel You can even give an example in the other direction. I.e., a function can look random for some reasonable interpretation of "looking random" but have trivial collisions. E.g., if the function would happen to be a PRG for inputs somewhat shorter than the output size. Those certainly "look random", but their security says nothing about collisions.
– Maeher
Nov 8 at 14:57
1
An interesting class of hashes to consider in this discussion are similarity preserving hashes. These are very intentionally and specifically non-random, and are very useful in a number of scenarios. A survey of the motivations and methods is given here: arxiv.org/pdf/1408.2927.pdf
– Ken Goss
Nov 8 at 15:16
1
@UKMonkey this is not a good example since it doesn’t compress the output. Collision resistance without compression is trivial and uninteresting.
– Yehuda Lindell
Nov 8 at 15:33
1
@UKMonkey an arbitrary size means that it has to work for arbitrary size inputs, so also large inputs.
– Yehuda Lindell
Nov 8 at 15:42
|
show 6 more comments
1
It's also good to add that there is a strong separation between collision-resistance and "looking random", i.e. you can have collision-resistant hash functions whose output does not look random at all! e.g. $H'(x) = 0^ell|H(x)$ where $H$ is a collision-resistant hash function. (Realized you addressed this in the answer already)
– Daniel
Nov 8 at 13:33
1
@Daniel You can even give an example in the other direction. I.e., a function can look random for some reasonable interpretation of "looking random" but have trivial collisions. E.g., if the function would happen to be a PRG for inputs somewhat shorter than the output size. Those certainly "look random", but their security says nothing about collisions.
– Maeher
Nov 8 at 14:57
1
An interesting class of hashes to consider in this discussion are similarity preserving hashes. These are very intentionally and specifically non-random, and are very useful in a number of scenarios. A survey of the motivations and methods is given here: arxiv.org/pdf/1408.2927.pdf
– Ken Goss
Nov 8 at 15:16
1
@UKMonkey this is not a good example since it doesn’t compress the output. Collision resistance without compression is trivial and uninteresting.
– Yehuda Lindell
Nov 8 at 15:33
1
@UKMonkey an arbitrary size means that it has to work for arbitrary size inputs, so also large inputs.
– Yehuda Lindell
Nov 8 at 15:42
1
1
It's also good to add that there is a strong separation between collision-resistance and "looking random", i.e. you can have collision-resistant hash functions whose output does not look random at all! e.g. $H'(x) = 0^ell|H(x)$ where $H$ is a collision-resistant hash function. (Realized you addressed this in the answer already)
– Daniel
Nov 8 at 13:33
It's also good to add that there is a strong separation between collision-resistance and "looking random", i.e. you can have collision-resistant hash functions whose output does not look random at all! e.g. $H'(x) = 0^ell|H(x)$ where $H$ is a collision-resistant hash function. (Realized you addressed this in the answer already)
– Daniel
Nov 8 at 13:33
1
1
@Daniel You can even give an example in the other direction. I.e., a function can look random for some reasonable interpretation of "looking random" but have trivial collisions. E.g., if the function would happen to be a PRG for inputs somewhat shorter than the output size. Those certainly "look random", but their security says nothing about collisions.
– Maeher
Nov 8 at 14:57
@Daniel You can even give an example in the other direction. I.e., a function can look random for some reasonable interpretation of "looking random" but have trivial collisions. E.g., if the function would happen to be a PRG for inputs somewhat shorter than the output size. Those certainly "look random", but their security says nothing about collisions.
– Maeher
Nov 8 at 14:57
1
1
An interesting class of hashes to consider in this discussion are similarity preserving hashes. These are very intentionally and specifically non-random, and are very useful in a number of scenarios. A survey of the motivations and methods is given here: arxiv.org/pdf/1408.2927.pdf
– Ken Goss
Nov 8 at 15:16
An interesting class of hashes to consider in this discussion are similarity preserving hashes. These are very intentionally and specifically non-random, and are very useful in a number of scenarios. A survey of the motivations and methods is given here: arxiv.org/pdf/1408.2927.pdf
– Ken Goss
Nov 8 at 15:16
1
1
@UKMonkey this is not a good example since it doesn’t compress the output. Collision resistance without compression is trivial and uninteresting.
– Yehuda Lindell
Nov 8 at 15:33
@UKMonkey this is not a good example since it doesn’t compress the output. Collision resistance without compression is trivial and uninteresting.
– Yehuda Lindell
Nov 8 at 15:33
1
1
@UKMonkey an arbitrary size means that it has to work for arbitrary size inputs, so also large inputs.
– Yehuda Lindell
Nov 8 at 15:42
@UKMonkey an arbitrary size means that it has to work for arbitrary size inputs, so also large inputs.
– Yehuda Lindell
Nov 8 at 15:42
|
show 6 more comments
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63780%2fdo-hash-functions-need-to-look-random%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
looking random? What is the definition? We can apply some statistical test to determine the randomness. If they fail to pass some margins, this will indicate that there is some weakness in the construction to behave like randomly.
– kelalaka
Nov 8 at 9:03
Note that for hash functions to have $n$ bits of security or $n/2$ bits of security for collision resistance you would expect a relatively well distributed output: if some values are more likely then the security of the function would also be affected. A hash with an output of 256 bits would not deliver 256 / 128 bits of security, in other words.
– Maarten Bodewes
Nov 8 at 15:13
"Being random" is an opposite to "having patterns". And "having patterns" is close to "insecure". So if you are talking about cryptografically secure hash function then I would say "yes".
– freakish
Nov 8 at 20:53
I found that Matthew Green's blog post about indifferentiability and his series about the Random Oracle Model are wonky-but-not-too-hard readings to get a beginner's sense of hash functions vs. randomness. Lots of linked references to follow up, too.
– Luis Casillas
Nov 9 at 0:25
@kelalaka By "looking random" I mean : For every efficient adversary that takes in a bitstring and outputs 0 or 1, give the adversary either H(s ||0) || H(s || 1) || H(s || 2) || ...., or a random string . The difference in the probability that the adversary outputs 1 is negligible.
– David Lui
Nov 9 at 4:58