Mixing
Do hash functions need to “look random�
Clash Royale CLAN TAG#URR8PPP
up vote
3
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 4 hours ago
kelalaka
2,621625
asked 5 hours ago
David Lui
412
add a comment |Â
up vote
3
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 4 hours ago
kelalaka
2,621625
asked 5 hours ago
David Lui
412
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
4 hours ago
add a comment |Â
up vote
3
down vote
favorite
up vote
3
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 4 hours ago
kelalaka
2,621625
asked 5 hours ago
David Lui
412
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 4 hours ago
kelalaka
2,621625
asked 5 hours ago
David Lui
412
edited 4 hours ago
kelalaka
2,621625
asked 5 hours ago
David Lui
412
edited 4 hours ago
kelalaka
2,621625
edited 4 hours ago
kelalaka
2,621625
edited 4 hours ago
kelalaka
2,621625
2,621625
asked 5 hours ago
David Lui
412
asked 5 hours ago
David Lui
412
asked 5 hours ago
David Lui
412
412
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
4 hours ago
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
4 hours ago
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
4 hours ago
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
4 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
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 1 hour ago
Yehuda Lindell
17.4k2955
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
10 mins ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
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 1 hour ago
Yehuda Lindell
17.4k2955
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
10 mins ago
add a comment |Â
up vote
3
down vote
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 1 hour ago
Yehuda Lindell
17.4k2955
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
10 mins ago
add a comment |Â
up vote
3
down vote
up vote
3
down vote
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 1 hour ago
Yehuda Lindell
17.4k2955
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 1 hour ago
Yehuda Lindell
17.4k2955
answered 1 hour ago
Yehuda Lindell
17.4k2955
answered 1 hour ago
Yehuda Lindell
17.4k2955
answered 1 hour ago
Yehuda Lindell
17.4k2955
17.4k2955
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
10 mins ago
add a comment |Â
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
10 mins ago
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
10 mins ago
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
10 mins ago
add a comment |Â
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
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
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
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
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
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
4 hours ago