Is there a feasible preimage attack for any hash function (no matter how deprecated) today?
$begingroup$
Has there ever been a hash function that was actually used in the field, no matter how long ago, for which there is now a feasible preimage attack?
All hashes that are nowadays considered 'broken' (such as MD5 and MD4 and older, and to some extent also SHA-1) are only susceptible to collision attacks, i.e. generating two arbitrary chunks of data with the same hash.
I'm wondering if a successful preimage attack has ever been found for any hash algorithm? And I mean either kind of preimage attack:
- Regular, i.e. given a hash output H, being able to generate some data X so hash(X) = H
- Secondary, i.e. given data X, being able to generate some other data Y so hash(X)=hash(Y)
And with 'feasible' I mean it can be done on a reasonably powerful cluster of fast computers (with fast GPUs) within reasonable time (e.g. 6 months).
hash collision-resistance attack preimage-resistance 2nd-preimage-resistance
asked Feb 5 at 4:34
RocketNutsRocketNuts
7111713
$endgroup$
add a comment |
$begingroup$
Has there ever been a hash function that was actually used in the field, no matter how long ago, for which there is now a feasible preimage attack?
All hashes that are nowadays considered 'broken' (such as MD5 and MD4 and older, and to some extent also SHA-1) are only susceptible to collision attacks, i.e. generating two arbitrary chunks of data with the same hash.
I'm wondering if a successful preimage attack has ever been found for any hash algorithm? And I mean either kind of preimage attack:
- Regular, i.e. given a hash output H, being able to generate some data X so hash(X) = H
- Secondary, i.e. given data X, being able to generate some other data Y so hash(X)=hash(Y)
And with 'feasible' I mean it can be done on a reasonably powerful cluster of fast computers (with fast GPUs) within reasonable time (e.g. 6 months).
hash collision-resistance attack preimage-resistance 2nd-preimage-resistance
asked Feb 5 at 4:34
RocketNutsRocketNuts
7111713
$endgroup$
add a comment |
$begingroup$
Has there ever been a hash function that was actually used in the field, no matter how long ago, for which there is now a feasible preimage attack?
All hashes that are nowadays considered 'broken' (such as MD5 and MD4 and older, and to some extent also SHA-1) are only susceptible to collision attacks, i.e. generating two arbitrary chunks of data with the same hash.
I'm wondering if a successful preimage attack has ever been found for any hash algorithm? And I mean either kind of preimage attack:
- Regular, i.e. given a hash output H, being able to generate some data X so hash(X) = H
- Secondary, i.e. given data X, being able to generate some other data Y so hash(X)=hash(Y)
And with 'feasible' I mean it can be done on a reasonably powerful cluster of fast computers (with fast GPUs) within reasonable time (e.g. 6 months).
hash collision-resistance attack preimage-resistance 2nd-preimage-resistance
asked Feb 5 at 4:34
RocketNutsRocketNuts
7111713
$endgroup$
Has there ever been a hash function that was actually used in the field, no matter how long ago, for which there is now a feasible preimage attack?
All hashes that are nowadays considered 'broken' (such as MD5 and MD4 and older, and to some extent also SHA-1) are only susceptible to collision attacks, i.e. generating two arbitrary chunks of data with the same hash.
I'm wondering if a successful preimage attack has ever been found for any hash algorithm? And I mean either kind of preimage attack:
- Regular, i.e. given a hash output H, being able to generate some data X so hash(X) = H
- Secondary, i.e. given data X, being able to generate some other data Y so hash(X)=hash(Y)
And with 'feasible' I mean it can be done on a reasonably powerful cluster of fast computers (with fast GPUs) within reasonable time (e.g. 6 months).
hash collision-resistance attack preimage-resistance 2nd-preimage-resistance
hash collision-resistance attack preimage-resistance 2nd-preimage-resistance
asked Feb 5 at 4:34
RocketNutsRocketNuts
7111713
asked Feb 5 at 4:34
RocketNutsRocketNuts
7111713
asked Feb 5 at 4:34
RocketNutsRocketNuts
7111713
asked Feb 5 at 4:34
RocketNutsRocketNuts
7111713
asked Feb 5 at 4:34
RocketNutsRocketNuts
7111713
7111713
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Any hash function? Yes, certainly. In fact, most hash functions are not even designed to be resistant to preimage attacks. This includes CRCs and standard checksums like Fletcher. Creating preimages with them is trivial. The oldest popular hash algorithm is MD2 which has a preimage attack with a complexity of 273 and a memory requirement of storing 273 memory blocks. While the complexity is low enough that modern technology could achieve the preimage, memory requirements make this impractical.
There have certainly been older hashes that have not gained traction which were intended to be cryptographically secure but which ended up exhibiting preimage attacks. For example, there is a 233 operation second preimage attack on the very old 3-pass Snefru hash function.
If you want a more specific answer, you'll need to narrow down what kinds of hash functions you are talking about. I could give you a dozen old or experimental hashes that were either dropped or underwent tweaks which were vulnerable to practical preimage attacks. I could also list every non-cryptographic hash I know of, but I have a feeling you aren't asking for a list of standard checksums.
answered Feb 5 at 5:53
forestforest
4,2801641
$endgroup$
$begingroup$
Are you sure about 2^33? Is there anything better than described in this paper?
$endgroup$
– Sjoerd
Feb 5 at 9:53
2
$begingroup$
My interpretation of the question is that it is only asking about hash functions which where intended to be resistant to preimage attacks when they were designed. As such CRC would be outside the scope of the question but MD2 would be an answer. I wonder if the memory usage of $2^{73}$ for that attack could be improved, which would make the answer a clear yes.
$endgroup$
– kasperd
Feb 5 at 10:29
1
$begingroup$
@kasperd That's my interpretation as well. See the final sentence of the answer.
$endgroup$
– forest
Feb 5 at 11:24
1
$begingroup$
I'm actually surprised to learn that even with something as old and insecure and broken as MD2, it's still extremely impractical (close to impossible) to do a preimage attack. $2^{73}$ complexity is actually still a lot nowadays in most situations (considering that a really fast setup would perform, what.. several hundreds of billions attempts per sec?) and the $2^{73}$ memory requirement makes it virtually impossible even today.
$endgroup$
– RocketNuts
Feb 5 at 14:34
1
$begingroup$
@kelalaka It's not even close. The memory requirement is $2^{73}$ blocks, with each block being 512 bytes.
$endgroup$
– forest
Feb 6 at 3:35
|
show 3 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f67059%2fis-there-a-feasible-preimage-attack-for-any-hash-function-no-matter-how-depreca%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Any hash function? Yes, certainly. In fact, most hash functions are not even designed to be resistant to preimage attacks. This includes CRCs and standard checksums like Fletcher. Creating preimages with them is trivial. The oldest popular hash algorithm is MD2 which has a preimage attack with a complexity of 273 and a memory requirement of storing 273 memory blocks. While the complexity is low enough that modern technology could achieve the preimage, memory requirements make this impractical.
There have certainly been older hashes that have not gained traction which were intended to be cryptographically secure but which ended up exhibiting preimage attacks. For example, there is a 233 operation second preimage attack on the very old 3-pass Snefru hash function.
If you want a more specific answer, you'll need to narrow down what kinds of hash functions you are talking about. I could give you a dozen old or experimental hashes that were either dropped or underwent tweaks which were vulnerable to practical preimage attacks. I could also list every non-cryptographic hash I know of, but I have a feeling you aren't asking for a list of standard checksums.
answered Feb 5 at 5:53
forestforest
4,2801641
$endgroup$
$begingroup$
Are you sure about 2^33? Is there anything better than described in this paper?
$endgroup$
– Sjoerd
Feb 5 at 9:53
2
$begingroup$
My interpretation of the question is that it is only asking about hash functions which where intended to be resistant to preimage attacks when they were designed. As such CRC would be outside the scope of the question but MD2 would be an answer. I wonder if the memory usage of $2^{73}$ for that attack could be improved, which would make the answer a clear yes.
$endgroup$
– kasperd
Feb 5 at 10:29
1
$begingroup$
@kasperd That's my interpretation as well. See the final sentence of the answer.
$endgroup$
– forest
Feb 5 at 11:24
1
$begingroup$
I'm actually surprised to learn that even with something as old and insecure and broken as MD2, it's still extremely impractical (close to impossible) to do a preimage attack. $2^{73}$ complexity is actually still a lot nowadays in most situations (considering that a really fast setup would perform, what.. several hundreds of billions attempts per sec?) and the $2^{73}$ memory requirement makes it virtually impossible even today.
$endgroup$
– RocketNuts
Feb 5 at 14:34
1
$begingroup$
@kelalaka It's not even close. The memory requirement is $2^{73}$ blocks, with each block being 512 bytes.
$endgroup$
– forest
Feb 6 at 3:35
|
show 3 more comments
$begingroup$
Any hash function? Yes, certainly. In fact, most hash functions are not even designed to be resistant to preimage attacks. This includes CRCs and standard checksums like Fletcher. Creating preimages with them is trivial. The oldest popular hash algorithm is MD2 which has a preimage attack with a complexity of 273 and a memory requirement of storing 273 memory blocks. While the complexity is low enough that modern technology could achieve the preimage, memory requirements make this impractical.
There have certainly been older hashes that have not gained traction which were intended to be cryptographically secure but which ended up exhibiting preimage attacks. For example, there is a 233 operation second preimage attack on the very old 3-pass Snefru hash function.
If you want a more specific answer, you'll need to narrow down what kinds of hash functions you are talking about. I could give you a dozen old or experimental hashes that were either dropped or underwent tweaks which were vulnerable to practical preimage attacks. I could also list every non-cryptographic hash I know of, but I have a feeling you aren't asking for a list of standard checksums.
answered Feb 5 at 5:53
forestforest
4,2801641
$endgroup$
$begingroup$
Are you sure about 2^33? Is there anything better than described in this paper?
$endgroup$
– Sjoerd
Feb 5 at 9:53
2
$begingroup$
My interpretation of the question is that it is only asking about hash functions which where intended to be resistant to preimage attacks when they were designed. As such CRC would be outside the scope of the question but MD2 would be an answer. I wonder if the memory usage of $2^{73}$ for that attack could be improved, which would make the answer a clear yes.
$endgroup$
– kasperd
Feb 5 at 10:29
1
$begingroup$
@kasperd That's my interpretation as well. See the final sentence of the answer.
$endgroup$
– forest
Feb 5 at 11:24
1
$begingroup$
I'm actually surprised to learn that even with something as old and insecure and broken as MD2, it's still extremely impractical (close to impossible) to do a preimage attack. $2^{73}$ complexity is actually still a lot nowadays in most situations (considering that a really fast setup would perform, what.. several hundreds of billions attempts per sec?) and the $2^{73}$ memory requirement makes it virtually impossible even today.
$endgroup$
– RocketNuts
Feb 5 at 14:34
1
$begingroup$
@kelalaka It's not even close. The memory requirement is $2^{73}$ blocks, with each block being 512 bytes.
$endgroup$
– forest
Feb 6 at 3:35
|
show 3 more comments
$begingroup$
Any hash function? Yes, certainly. In fact, most hash functions are not even designed to be resistant to preimage attacks. This includes CRCs and standard checksums like Fletcher. Creating preimages with them is trivial. The oldest popular hash algorithm is MD2 which has a preimage attack with a complexity of 273 and a memory requirement of storing 273 memory blocks. While the complexity is low enough that modern technology could achieve the preimage, memory requirements make this impractical.
There have certainly been older hashes that have not gained traction which were intended to be cryptographically secure but which ended up exhibiting preimage attacks. For example, there is a 233 operation second preimage attack on the very old 3-pass Snefru hash function.
If you want a more specific answer, you'll need to narrow down what kinds of hash functions you are talking about. I could give you a dozen old or experimental hashes that were either dropped or underwent tweaks which were vulnerable to practical preimage attacks. I could also list every non-cryptographic hash I know of, but I have a feeling you aren't asking for a list of standard checksums.
answered Feb 5 at 5:53
forestforest
4,2801641
$endgroup$
Any hash function? Yes, certainly. In fact, most hash functions are not even designed to be resistant to preimage attacks. This includes CRCs and standard checksums like Fletcher. Creating preimages with them is trivial. The oldest popular hash algorithm is MD2 which has a preimage attack with a complexity of 273 and a memory requirement of storing 273 memory blocks. While the complexity is low enough that modern technology could achieve the preimage, memory requirements make this impractical.
There have certainly been older hashes that have not gained traction which were intended to be cryptographically secure but which ended up exhibiting preimage attacks. For example, there is a 233 operation second preimage attack on the very old 3-pass Snefru hash function.
If you want a more specific answer, you'll need to narrow down what kinds of hash functions you are talking about. I could give you a dozen old or experimental hashes that were either dropped or underwent tweaks which were vulnerable to practical preimage attacks. I could also list every non-cryptographic hash I know of, but I have a feeling you aren't asking for a list of standard checksums.
answered Feb 5 at 5:53
forestforest
4,2801641
answered Feb 5 at 5:53
forestforest
4,2801641
answered Feb 5 at 5:53
forestforest
4,2801641
answered Feb 5 at 5:53
forestforest
4,2801641
4,2801641
$begingroup$
Are you sure about 2^33? Is there anything better than described in this paper?
$endgroup$
– Sjoerd
Feb 5 at 9:53
2
$begingroup$
My interpretation of the question is that it is only asking about hash functions which where intended to be resistant to preimage attacks when they were designed. As such CRC would be outside the scope of the question but MD2 would be an answer. I wonder if the memory usage of $2^{73}$ for that attack could be improved, which would make the answer a clear yes.
$endgroup$
– kasperd
Feb 5 at 10:29
1
$begingroup$
@kasperd That's my interpretation as well. See the final sentence of the answer.
$endgroup$
– forest
Feb 5 at 11:24
1
$begingroup$
I'm actually surprised to learn that even with something as old and insecure and broken as MD2, it's still extremely impractical (close to impossible) to do a preimage attack. $2^{73}$ complexity is actually still a lot nowadays in most situations (considering that a really fast setup would perform, what.. several hundreds of billions attempts per sec?) and the $2^{73}$ memory requirement makes it virtually impossible even today.
$endgroup$
– RocketNuts
Feb 5 at 14:34
1
$begingroup$
@kelalaka It's not even close. The memory requirement is $2^{73}$ blocks, with each block being 512 bytes.
$endgroup$
– forest
Feb 6 at 3:35
|
show 3 more comments
$begingroup$
Are you sure about 2^33? Is there anything better than described in this paper?
$endgroup$
– Sjoerd
Feb 5 at 9:53
2
$begingroup$
My interpretation of the question is that it is only asking about hash functions which where intended to be resistant to preimage attacks when they were designed. As such CRC would be outside the scope of the question but MD2 would be an answer. I wonder if the memory usage of $2^{73}$ for that attack could be improved, which would make the answer a clear yes.
$endgroup$
– kasperd
Feb 5 at 10:29
1
$begingroup$
@kasperd That's my interpretation as well. See the final sentence of the answer.
$endgroup$
– forest
Feb 5 at 11:24
1
$begingroup$
I'm actually surprised to learn that even with something as old and insecure and broken as MD2, it's still extremely impractical (close to impossible) to do a preimage attack. $2^{73}$ complexity is actually still a lot nowadays in most situations (considering that a really fast setup would perform, what.. several hundreds of billions attempts per sec?) and the $2^{73}$ memory requirement makes it virtually impossible even today.
$endgroup$
– RocketNuts
Feb 5 at 14:34
1
$begingroup$
@kelalaka It's not even close. The memory requirement is $2^{73}$ blocks, with each block being 512 bytes.
$endgroup$
– forest
Feb 6 at 3:35
$begingroup$
Are you sure about 2^33? Is there anything better than described in this paper?
$endgroup$
– Sjoerd
Feb 5 at 9:53
$begingroup$
Are you sure about 2^33? Is there anything better than described in this paper?
$endgroup$
– Sjoerd
Feb 5 at 9:53
2
2
$begingroup$
My interpretation of the question is that it is only asking about hash functions which where intended to be resistant to preimage attacks when they were designed. As such CRC would be outside the scope of the question but MD2 would be an answer. I wonder if the memory usage of $2^{73}$ for that attack could be improved, which would make the answer a clear yes.
$endgroup$
– kasperd
Feb 5 at 10:29
$begingroup$
My interpretation of the question is that it is only asking about hash functions which where intended to be resistant to preimage attacks when they were designed. As such CRC would be outside the scope of the question but MD2 would be an answer. I wonder if the memory usage of $2^{73}$ for that attack could be improved, which would make the answer a clear yes.
$endgroup$
– kasperd
Feb 5 at 10:29
1
1
$begingroup$
@kasperd That's my interpretation as well. See the final sentence of the answer.
$endgroup$
– forest
Feb 5 at 11:24
$begingroup$
@kasperd That's my interpretation as well. See the final sentence of the answer.
$endgroup$
– forest
Feb 5 at 11:24
1
1
$begingroup$
I'm actually surprised to learn that even with something as old and insecure and broken as MD2, it's still extremely impractical (close to impossible) to do a preimage attack. $2^{73}$ complexity is actually still a lot nowadays in most situations (considering that a really fast setup would perform, what.. several hundreds of billions attempts per sec?) and the $2^{73}$ memory requirement makes it virtually impossible even today.
$endgroup$
– RocketNuts
Feb 5 at 14:34
$begingroup$
I'm actually surprised to learn that even with something as old and insecure and broken as MD2, it's still extremely impractical (close to impossible) to do a preimage attack. $2^{73}$ complexity is actually still a lot nowadays in most situations (considering that a really fast setup would perform, what.. several hundreds of billions attempts per sec?) and the $2^{73}$ memory requirement makes it virtually impossible even today.
$endgroup$
– RocketNuts
Feb 5 at 14:34
1
1
$begingroup$
@kelalaka It's not even close. The memory requirement is $2^{73}$ blocks, with each block being 512 bytes.
$endgroup$
– forest
Feb 6 at 3:35
$begingroup$
@kelalaka It's not even close. The memory requirement is $2^{73}$ blocks, with each block being 512 bytes.
$endgroup$
– forest
Feb 6 at 3:35
|
show 3 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.
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%2f67059%2fis-there-a-feasible-preimage-attack-for-any-hash-function-no-matter-how-depreca%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
