Mixing
What makes SHA256 secure?
$begingroup$
For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem.
What makes SHA256 and similar hash functions, of the same family, secure against pre-image and collision attacks? What's the math behind it?
hash collision-resistance sha-256 preimage-resistance
edited Jan 10 at 9:06
kelalaka
7,12522244
asked Jan 9 at 22:28
rapadurarapadura
18616
$endgroup$
add a comment |
$begingroup$
For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem.
What makes SHA256 and similar hash functions, of the same family, secure against pre-image and collision attacks? What's the math behind it?
hash collision-resistance sha-256 preimage-resistance
edited Jan 10 at 9:06
kelalaka
7,12522244
asked Jan 9 at 22:28
rapadurarapadura
18616
$endgroup$
$begingroup$
Check these 1 2 3
$endgroup$
– kelalaka
Jan 9 at 22:33
1
$begingroup$
Thanks for the good links. My question is different from "Why cant we reverse hashes", since I dont want to reverse a hash, merely curious about, if any, mathematical foundations for "security" of hash functions, as opposed to confusion and obfuscation. Seems the compression f in SHA256 is not provably secure, just hard.
$endgroup$
– rapadura
Jan 9 at 22:51
1
$begingroup$
It's worth noting that RSA and ECDSA are currently also not provably secure. We believe factoring and DLP are hard because no one we know of has found a way to do it efficiently. But we have no proof of their hardness, and perhaps we never will.
$endgroup$
– marcelm
Jan 10 at 21:00
add a comment |
$begingroup$
For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem.
What makes SHA256 and similar hash functions, of the same family, secure against pre-image and collision attacks? What's the math behind it?
hash collision-resistance sha-256 preimage-resistance
edited Jan 10 at 9:06
kelalaka
7,12522244
asked Jan 9 at 22:28
rapadurarapadura
18616
$endgroup$
For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem.
What makes SHA256 and similar hash functions, of the same family, secure against pre-image and collision attacks? What's the math behind it?
hash collision-resistance sha-256 preimage-resistance
hash collision-resistance sha-256 preimage-resistance
edited Jan 10 at 9:06
kelalaka
7,12522244
asked Jan 9 at 22:28
rapadurarapadura
18616
edited Jan 10 at 9:06
kelalaka
7,12522244
asked Jan 9 at 22:28
rapadurarapadura
18616
edited Jan 10 at 9:06
kelalaka
7,12522244
edited Jan 10 at 9:06
kelalaka
7,12522244
edited Jan 10 at 9:06
kelalaka
7,12522244
7,12522244
asked Jan 9 at 22:28
rapadurarapadura
18616
asked Jan 9 at 22:28
rapadurarapadura
18616
asked Jan 9 at 22:28
rapadurarapadura
18616
18616
$begingroup$
Check these 1 2 3
$endgroup$
– kelalaka
Jan 9 at 22:33
1
$begingroup$
Thanks for the good links. My question is different from "Why cant we reverse hashes", since I dont want to reverse a hash, merely curious about, if any, mathematical foundations for "security" of hash functions, as opposed to confusion and obfuscation. Seems the compression f in SHA256 is not provably secure, just hard.
$endgroup$
– rapadura
Jan 9 at 22:51
1
$begingroup$
It's worth noting that RSA and ECDSA are currently also not provably secure. We believe factoring and DLP are hard because no one we know of has found a way to do it efficiently. But we have no proof of their hardness, and perhaps we never will.
$endgroup$
– marcelm
Jan 10 at 21:00
add a comment |
$begingroup$
Check these 1 2 3
$endgroup$
– kelalaka
Jan 9 at 22:33
1
$begingroup$
Thanks for the good links. My question is different from "Why cant we reverse hashes", since I dont want to reverse a hash, merely curious about, if any, mathematical foundations for "security" of hash functions, as opposed to confusion and obfuscation. Seems the compression f in SHA256 is not provably secure, just hard.
$endgroup$
– rapadura
Jan 9 at 22:51
1
$begingroup$
It's worth noting that RSA and ECDSA are currently also not provably secure. We believe factoring and DLP are hard because no one we know of has found a way to do it efficiently. But we have no proof of their hardness, and perhaps we never will.
$endgroup$
– marcelm
Jan 10 at 21:00
$begingroup$
Check these 1 2 3
$endgroup$
– kelalaka
Jan 9 at 22:33
$begingroup$
Check these 1 2 3
$endgroup$
– kelalaka
Jan 9 at 22:33
1
1
$begingroup$
Thanks for the good links. My question is different from "Why cant we reverse hashes", since I dont want to reverse a hash, merely curious about, if any, mathematical foundations for "security" of hash functions, as opposed to confusion and obfuscation. Seems the compression f in SHA256 is not provably secure, just hard.
$endgroup$
– rapadura
Jan 9 at 22:51
$begingroup$
Thanks for the good links. My question is different from "Why cant we reverse hashes", since I dont want to reverse a hash, merely curious about, if any, mathematical foundations for "security" of hash functions, as opposed to confusion and obfuscation. Seems the compression f in SHA256 is not provably secure, just hard.
$endgroup$
– rapadura
Jan 9 at 22:51
1
1
$begingroup$
It's worth noting that RSA and ECDSA are currently also not provably secure. We believe factoring and DLP are hard because no one we know of has found a way to do it efficiently. But we have no proof of their hardness, and perhaps we never will.
$endgroup$
– marcelm
Jan 10 at 21:00
$begingroup$
It's worth noting that RSA and ECDSA are currently also not provably secure. We believe factoring and DLP are hard because no one we know of has found a way to do it efficiently. But we have no proof of their hardness, and perhaps we never will.
$endgroup$
– marcelm
Jan 10 at 21:00
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The design and security of SHA-256 rely on two cryptographic structures; one-way compression function which is based on Davies–Meyer structure which uses SHACAL-2 block cipher and on the top the Merkle–Damgård structure that uses the Davies–Meyer structure.
A little deeper;
Compression function: transforms $2n$-bit input into $n$-bit. The transformation performed in a way that it achieves avalanche effect, i.e. whenever one bit complemented from the input, each of the output bits changes with 50% probability.
One-way function: Easy to compute hard to invert.
One way compression function should have these properties;
Easy to compute: the calculation of the output is easy for a given input.
Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account.
Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 neq m_2$ and $Hash(m_1)=Hash(m_2)$. Producing a forgery of a given message.
Collision resistance : if it is hard to find two inputs that hash to the same output $a$ and $b$ such that $H(a)= H(b)$, $a neq b.$
Collision resistance implies second pre-image resistance. If the attacker is able to find second pre-images then he chooses arbitrary $m_1$ then computes the second pre-image $m_2$ to obtain a collision. But Collision resistance doesn't imply pre-image resistance. See, more at Rogaway et. al paper.
(SHA256 Compression function, from Wikipedia )
Middle level;
Davies–Meyer structure is a one-way compression function based on a block cipher. Security of this construction is in the Ideal Cipher Model. However, there is a property of this construction; even the underlying block cipher is secure it is possible to find fixed points.
The block cipher of SHA-256 is called SHA-CAL-2. In Lu et. al presented a related-Key rectangle attack for 42 Rounds of SHACAL-2 by Lu et. al. Later, Lu et. al presented another attack Using Related-Key Rectangle Cryptanalysis] for 44-round of SHACAL-2.
Top layer;
Merkle–Damgård structure (MD) uses a compression function. MD is collision resistant if the compression function is collision resistant one-way compression function.. MD constructions have length extension attack that SHA-256 is also prone to this attack. It is recommended to switch SHA-3.
Note: There is a pre-image resistance attack for 52 out of 64 rounds of SHA-256.
answered Jan 9 at 23:46
kelalakakelalaka
7,12522244
$endgroup$
1
$begingroup$
@rapadura Did you try looking for SHA-256 on GitHub? For example, B-Con/crypto-algorithms.
$endgroup$
– forest
Jan 10 at 8:46
1
$begingroup$
I would have listed "Collision resistance" first, in that it is a weaker condition than "Second Pre-image resistant". (If we can break second pre-image resistance, then we can trivially break collision resistance by choosing a random $a$ as $m_1$, and then using the second pre-image algorithm to calculate $b$. OTOH if we have an algorithm to find collisions, that doesn't allow us to find second pre-images)
$endgroup$
– Martin Bonner
Jan 10 at 10:09
1
$begingroup$
"avalanche effect, i.e. every output bit depends on every input bit" Is that right? I could be misremembering, but I thought the ideal avalanche effect was when each input bit affected half of the output bits.
$endgroup$
– a CVn
Jan 10 at 12:00
2
$begingroup$
@aCVn When you flip a single bit in the input roughly 50% of the output bit should get flipped. Note however that if you flip bit at index 0 for different inputs the output bits that get flipped will change and you want all possible subsets to be possible. So in that sense all output bits depend on every single bit, while comparing two input whose difference is just one bit should give roughly 50% of difference.
$endgroup$
– Bakuriu
Jan 10 at 19:35
1
$begingroup$
Will accept this answer, despite both being really good answers. Learned a lot, thank you guys.
$endgroup$
– rapadura
Jan 11 at 14:47
|
show 4 more comments
$begingroup$
It's worth pointing out that in the case of SHA2 and most other hashes the compression function has a block cipher (keyed permutation) as its core.
Basically what you are asking is identical to asking how can block ciphers be resistant to known-plaintext attacks and chosen-plaintext attacks (arguably doesn't apply to SHA2 specifically because an attacker doesn't control that aspect) and even related-key attacks in the case of SHA2 (because it uses a Davies-Meyer construction where the attacker has control over what gets fed into the key schedule).
There is no proof that this methodology is reducible to something that is proven secure. It is believed to be secure due to diffusion and confusion properties which as far as is known allow no efficient backtracking. You can think of it as extreme sensitivity-to-initial-conditions in a discrete non-continuous domain.
Edit: The reason I went to block ciphers is because hash security is provably reducible to the security of the core keyed permutation (or even unkeyed if you look at SHA3) - that's how hashes are designed to begin with. Which I believe is the spirit of your inquiry. But the buck stops there, no security proof for those exists.
answered Jan 9 at 23:46
Jacklos44773Jacklos44773
1813
$endgroup$
$begingroup$
Very interesting, thank you
$endgroup$
– rapadura
Jan 10 at 8:40
add a comment |
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%2f66371%2fwhat-makes-sha256-secure%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The design and security of SHA-256 rely on two cryptographic structures; one-way compression function which is based on Davies–Meyer structure which uses SHACAL-2 block cipher and on the top the Merkle–Damgård structure that uses the Davies–Meyer structure.
A little deeper;
Compression function: transforms $2n$-bit input into $n$-bit. The transformation performed in a way that it achieves avalanche effect, i.e. whenever one bit complemented from the input, each of the output bits changes with 50% probability.
One-way function: Easy to compute hard to invert.
One way compression function should have these properties;
Easy to compute: the calculation of the output is easy for a given input.
Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account.
Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 neq m_2$ and $Hash(m_1)=Hash(m_2)$. Producing a forgery of a given message.
Collision resistance : if it is hard to find two inputs that hash to the same output $a$ and $b$ such that $H(a)= H(b)$, $a neq b.$
Collision resistance implies second pre-image resistance. If the attacker is able to find second pre-images then he chooses arbitrary $m_1$ then computes the second pre-image $m_2$ to obtain a collision. But Collision resistance doesn't imply pre-image resistance. See, more at Rogaway et. al paper.
(SHA256 Compression function, from Wikipedia )
Middle level;
Davies–Meyer structure is a one-way compression function based on a block cipher. Security of this construction is in the Ideal Cipher Model. However, there is a property of this construction; even the underlying block cipher is secure it is possible to find fixed points.
The block cipher of SHA-256 is called SHA-CAL-2. In Lu et. al presented a related-Key rectangle attack for 42 Rounds of SHACAL-2 by Lu et. al. Later, Lu et. al presented another attack Using Related-Key Rectangle Cryptanalysis] for 44-round of SHACAL-2.
Top layer;
Merkle–Damgård structure (MD) uses a compression function. MD is collision resistant if the compression function is collision resistant one-way compression function.. MD constructions have length extension attack that SHA-256 is also prone to this attack. It is recommended to switch SHA-3.
Note: There is a pre-image resistance attack for 52 out of 64 rounds of SHA-256.
answered Jan 9 at 23:46
kelalakakelalaka
7,12522244
$endgroup$
1
$begingroup$
@rapadura Did you try looking for SHA-256 on GitHub? For example, B-Con/crypto-algorithms.
$endgroup$
– forest
Jan 10 at 8:46
1
$begingroup$
I would have listed "Collision resistance" first, in that it is a weaker condition than "Second Pre-image resistant". (If we can break second pre-image resistance, then we can trivially break collision resistance by choosing a random $a$ as $m_1$, and then using the second pre-image algorithm to calculate $b$. OTOH if we have an algorithm to find collisions, that doesn't allow us to find second pre-images)
$endgroup$
– Martin Bonner
Jan 10 at 10:09
1
$begingroup$
"avalanche effect, i.e. every output bit depends on every input bit" Is that right? I could be misremembering, but I thought the ideal avalanche effect was when each input bit affected half of the output bits.
$endgroup$
– a CVn
Jan 10 at 12:00
2
$begingroup$
@aCVn When you flip a single bit in the input roughly 50% of the output bit should get flipped. Note however that if you flip bit at index 0 for different inputs the output bits that get flipped will change and you want all possible subsets to be possible. So in that sense all output bits depend on every single bit, while comparing two input whose difference is just one bit should give roughly 50% of difference.
$endgroup$
– Bakuriu
Jan 10 at 19:35
1
$begingroup$
Will accept this answer, despite both being really good answers. Learned a lot, thank you guys.
$endgroup$
– rapadura
Jan 11 at 14:47
|
show 4 more comments
$begingroup$
The design and security of SHA-256 rely on two cryptographic structures; one-way compression function which is based on Davies–Meyer structure which uses SHACAL-2 block cipher and on the top the Merkle–Damgård structure that uses the Davies–Meyer structure.
A little deeper;
Compression function: transforms $2n$-bit input into $n$-bit. The transformation performed in a way that it achieves avalanche effect, i.e. whenever one bit complemented from the input, each of the output bits changes with 50% probability.
One-way function: Easy to compute hard to invert.
One way compression function should have these properties;
Easy to compute: the calculation of the output is easy for a given input.
Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account.
Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 neq m_2$ and $Hash(m_1)=Hash(m_2)$. Producing a forgery of a given message.
Collision resistance : if it is hard to find two inputs that hash to the same output $a$ and $b$ such that $H(a)= H(b)$, $a neq b.$
Collision resistance implies second pre-image resistance. If the attacker is able to find second pre-images then he chooses arbitrary $m_1$ then computes the second pre-image $m_2$ to obtain a collision. But Collision resistance doesn't imply pre-image resistance. See, more at Rogaway et. al paper.
(SHA256 Compression function, from Wikipedia )
Middle level;
Davies–Meyer structure is a one-way compression function based on a block cipher. Security of this construction is in the Ideal Cipher Model. However, there is a property of this construction; even the underlying block cipher is secure it is possible to find fixed points.
The block cipher of SHA-256 is called SHA-CAL-2. In Lu et. al presented a related-Key rectangle attack for 42 Rounds of SHACAL-2 by Lu et. al. Later, Lu et. al presented another attack Using Related-Key Rectangle Cryptanalysis] for 44-round of SHACAL-2.
Top layer;
Merkle–Damgård structure (MD) uses a compression function. MD is collision resistant if the compression function is collision resistant one-way compression function.. MD constructions have length extension attack that SHA-256 is also prone to this attack. It is recommended to switch SHA-3.
Note: There is a pre-image resistance attack for 52 out of 64 rounds of SHA-256.
answered Jan 9 at 23:46
kelalakakelalaka
7,12522244
$endgroup$
1
$begingroup$
@rapadura Did you try looking for SHA-256 on GitHub? For example, B-Con/crypto-algorithms.
$endgroup$
– forest
Jan 10 at 8:46
1
$begingroup$
I would have listed "Collision resistance" first, in that it is a weaker condition than "Second Pre-image resistant". (If we can break second pre-image resistance, then we can trivially break collision resistance by choosing a random $a$ as $m_1$, and then using the second pre-image algorithm to calculate $b$. OTOH if we have an algorithm to find collisions, that doesn't allow us to find second pre-images)
$endgroup$
– Martin Bonner
Jan 10 at 10:09
1
$begingroup$
"avalanche effect, i.e. every output bit depends on every input bit" Is that right? I could be misremembering, but I thought the ideal avalanche effect was when each input bit affected half of the output bits.
$endgroup$
– a CVn
Jan 10 at 12:00
2
$begingroup$
@aCVn When you flip a single bit in the input roughly 50% of the output bit should get flipped. Note however that if you flip bit at index 0 for different inputs the output bits that get flipped will change and you want all possible subsets to be possible. So in that sense all output bits depend on every single bit, while comparing two input whose difference is just one bit should give roughly 50% of difference.
$endgroup$
– Bakuriu
Jan 10 at 19:35
1
$begingroup$
Will accept this answer, despite both being really good answers. Learned a lot, thank you guys.
$endgroup$
– rapadura
Jan 11 at 14:47
|
show 4 more comments
$begingroup$
The design and security of SHA-256 rely on two cryptographic structures; one-way compression function which is based on Davies–Meyer structure which uses SHACAL-2 block cipher and on the top the Merkle–Damgård structure that uses the Davies–Meyer structure.
A little deeper;
Compression function: transforms $2n$-bit input into $n$-bit. The transformation performed in a way that it achieves avalanche effect, i.e. whenever one bit complemented from the input, each of the output bits changes with 50% probability.
One-way function: Easy to compute hard to invert.
One way compression function should have these properties;
Easy to compute: the calculation of the output is easy for a given input.
Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account.
Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 neq m_2$ and $Hash(m_1)=Hash(m_2)$. Producing a forgery of a given message.
Collision resistance : if it is hard to find two inputs that hash to the same output $a$ and $b$ such that $H(a)= H(b)$, $a neq b.$
Collision resistance implies second pre-image resistance. If the attacker is able to find second pre-images then he chooses arbitrary $m_1$ then computes the second pre-image $m_2$ to obtain a collision. But Collision resistance doesn't imply pre-image resistance. See, more at Rogaway et. al paper.
(SHA256 Compression function, from Wikipedia )
Middle level;
Davies–Meyer structure is a one-way compression function based on a block cipher. Security of this construction is in the Ideal Cipher Model. However, there is a property of this construction; even the underlying block cipher is secure it is possible to find fixed points.
The block cipher of SHA-256 is called SHA-CAL-2. In Lu et. al presented a related-Key rectangle attack for 42 Rounds of SHACAL-2 by Lu et. al. Later, Lu et. al presented another attack Using Related-Key Rectangle Cryptanalysis] for 44-round of SHACAL-2.
Top layer;
Merkle–Damgård structure (MD) uses a compression function. MD is collision resistant if the compression function is collision resistant one-way compression function.. MD constructions have length extension attack that SHA-256 is also prone to this attack. It is recommended to switch SHA-3.
Note: There is a pre-image resistance attack for 52 out of 64 rounds of SHA-256.
answered Jan 9 at 23:46
kelalakakelalaka
7,12522244
$endgroup$
The design and security of SHA-256 rely on two cryptographic structures; one-way compression function which is based on Davies–Meyer structure which uses SHACAL-2 block cipher and on the top the Merkle–Damgård structure that uses the Davies–Meyer structure.
A little deeper;
Compression function: transforms $2n$-bit input into $n$-bit. The transformation performed in a way that it achieves avalanche effect, i.e. whenever one bit complemented from the input, each of the output bits changes with 50% probability.
One-way function: Easy to compute hard to invert.
One way compression function should have these properties;
Easy to compute: the calculation of the output is easy for a given input.
Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account.
Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 neq m_2$ and $Hash(m_1)=Hash(m_2)$. Producing a forgery of a given message.
Collision resistance : if it is hard to find two inputs that hash to the same output $a$ and $b$ such that $H(a)= H(b)$, $a neq b.$
Collision resistance implies second pre-image resistance. If the attacker is able to find second pre-images then he chooses arbitrary $m_1$ then computes the second pre-image $m_2$ to obtain a collision. But Collision resistance doesn't imply pre-image resistance. See, more at Rogaway et. al paper.
(SHA256 Compression function, from Wikipedia )
Middle level;
Davies–Meyer structure is a one-way compression function based on a block cipher. Security of this construction is in the Ideal Cipher Model. However, there is a property of this construction; even the underlying block cipher is secure it is possible to find fixed points.
The block cipher of SHA-256 is called SHA-CAL-2. In Lu et. al presented a related-Key rectangle attack for 42 Rounds of SHACAL-2 by Lu et. al. Later, Lu et. al presented another attack Using Related-Key Rectangle Cryptanalysis] for 44-round of SHACAL-2.
Top layer;
Merkle–Damgård structure (MD) uses a compression function. MD is collision resistant if the compression function is collision resistant one-way compression function.. MD constructions have length extension attack that SHA-256 is also prone to this attack. It is recommended to switch SHA-3.
Note: There is a pre-image resistance attack for 52 out of 64 rounds of SHA-256.
answered Jan 9 at 23:46
kelalakakelalaka
7,12522244
edited Jan 10 at 12:11
answered Jan 9 at 23:46
kelalakakelalaka
7,12522244
answered Jan 9 at 23:46
kelalakakelalaka
7,12522244
answered Jan 9 at 23:46
kelalakakelalaka
7,12522244
7,12522244
1
$begingroup$
@rapadura Did you try looking for SHA-256 on GitHub? For example, B-Con/crypto-algorithms.
$endgroup$
– forest
Jan 10 at 8:46
1
$begingroup$
I would have listed "Collision resistance" first, in that it is a weaker condition than "Second Pre-image resistant". (If we can break second pre-image resistance, then we can trivially break collision resistance by choosing a random $a$ as $m_1$, and then using the second pre-image algorithm to calculate $b$. OTOH if we have an algorithm to find collisions, that doesn't allow us to find second pre-images)
$endgroup$
– Martin Bonner
Jan 10 at 10:09
1
$begingroup$
"avalanche effect, i.e. every output bit depends on every input bit" Is that right? I could be misremembering, but I thought the ideal avalanche effect was when each input bit affected half of the output bits.
$endgroup$
– a CVn
Jan 10 at 12:00
2
$begingroup$
@aCVn When you flip a single bit in the input roughly 50% of the output bit should get flipped. Note however that if you flip bit at index 0 for different inputs the output bits that get flipped will change and you want all possible subsets to be possible. So in that sense all output bits depend on every single bit, while comparing two input whose difference is just one bit should give roughly 50% of difference.
$endgroup$
– Bakuriu
Jan 10 at 19:35
1
$begingroup$
Will accept this answer, despite both being really good answers. Learned a lot, thank you guys.
$endgroup$
– rapadura
Jan 11 at 14:47
|
show 4 more comments
1
$begingroup$
@rapadura Did you try looking for SHA-256 on GitHub? For example, B-Con/crypto-algorithms.
$endgroup$
– forest
Jan 10 at 8:46
1
$begingroup$
I would have listed "Collision resistance" first, in that it is a weaker condition than "Second Pre-image resistant". (If we can break second pre-image resistance, then we can trivially break collision resistance by choosing a random $a$ as $m_1$, and then using the second pre-image algorithm to calculate $b$. OTOH if we have an algorithm to find collisions, that doesn't allow us to find second pre-images)
$endgroup$
– Martin Bonner
Jan 10 at 10:09
1
$begingroup$
"avalanche effect, i.e. every output bit depends on every input bit" Is that right? I could be misremembering, but I thought the ideal avalanche effect was when each input bit affected half of the output bits.
$endgroup$
– a CVn
Jan 10 at 12:00
2
$begingroup$
@aCVn When you flip a single bit in the input roughly 50% of the output bit should get flipped. Note however that if you flip bit at index 0 for different inputs the output bits that get flipped will change and you want all possible subsets to be possible. So in that sense all output bits depend on every single bit, while comparing two input whose difference is just one bit should give roughly 50% of difference.
$endgroup$
– Bakuriu
Jan 10 at 19:35
1
$begingroup$
Will accept this answer, despite both being really good answers. Learned a lot, thank you guys.
$endgroup$
– rapadura
Jan 11 at 14:47
1
1
$begingroup$
@rapadura Did you try looking for SHA-256 on GitHub? For example, B-Con/crypto-algorithms.
$endgroup$
– forest
Jan 10 at 8:46
$begingroup$
@rapadura Did you try looking for SHA-256 on GitHub? For example, B-Con/crypto-algorithms.
$endgroup$
– forest
Jan 10 at 8:46
1
1
$begingroup$
I would have listed "Collision resistance" first, in that it is a weaker condition than "Second Pre-image resistant". (If we can break second pre-image resistance, then we can trivially break collision resistance by choosing a random $a$ as $m_1$, and then using the second pre-image algorithm to calculate $b$. OTOH if we have an algorithm to find collisions, that doesn't allow us to find second pre-images)
$endgroup$
– Martin Bonner
Jan 10 at 10:09
$begingroup$
I would have listed "Collision resistance" first, in that it is a weaker condition than "Second Pre-image resistant". (If we can break second pre-image resistance, then we can trivially break collision resistance by choosing a random $a$ as $m_1$, and then using the second pre-image algorithm to calculate $b$. OTOH if we have an algorithm to find collisions, that doesn't allow us to find second pre-images)
$endgroup$
– Martin Bonner
Jan 10 at 10:09
1
1
$begingroup$
"avalanche effect, i.e. every output bit depends on every input bit" Is that right? I could be misremembering, but I thought the ideal avalanche effect was when each input bit affected half of the output bits.
$endgroup$
– a CVn
Jan 10 at 12:00
$begingroup$
"avalanche effect, i.e. every output bit depends on every input bit" Is that right? I could be misremembering, but I thought the ideal avalanche effect was when each input bit affected half of the output bits.
$endgroup$
– a CVn
Jan 10 at 12:00
2
2
$begingroup$
@aCVn When you flip a single bit in the input roughly 50% of the output bit should get flipped. Note however that if you flip bit at index 0 for different inputs the output bits that get flipped will change and you want all possible subsets to be possible. So in that sense all output bits depend on every single bit, while comparing two input whose difference is just one bit should give roughly 50% of difference.
$endgroup$
– Bakuriu
Jan 10 at 19:35
$begingroup$
@aCVn When you flip a single bit in the input roughly 50% of the output bit should get flipped. Note however that if you flip bit at index 0 for different inputs the output bits that get flipped will change and you want all possible subsets to be possible. So in that sense all output bits depend on every single bit, while comparing two input whose difference is just one bit should give roughly 50% of difference.
$endgroup$
– Bakuriu
Jan 10 at 19:35
1
1
$begingroup$
Will accept this answer, despite both being really good answers. Learned a lot, thank you guys.
$endgroup$
– rapadura
Jan 11 at 14:47
$begingroup$
Will accept this answer, despite both being really good answers. Learned a lot, thank you guys.
$endgroup$
– rapadura
Jan 11 at 14:47
|
show 4 more comments
$begingroup$
It's worth pointing out that in the case of SHA2 and most other hashes the compression function has a block cipher (keyed permutation) as its core.
Basically what you are asking is identical to asking how can block ciphers be resistant to known-plaintext attacks and chosen-plaintext attacks (arguably doesn't apply to SHA2 specifically because an attacker doesn't control that aspect) and even related-key attacks in the case of SHA2 (because it uses a Davies-Meyer construction where the attacker has control over what gets fed into the key schedule).
There is no proof that this methodology is reducible to something that is proven secure. It is believed to be secure due to diffusion and confusion properties which as far as is known allow no efficient backtracking. You can think of it as extreme sensitivity-to-initial-conditions in a discrete non-continuous domain.
Edit: The reason I went to block ciphers is because hash security is provably reducible to the security of the core keyed permutation (or even unkeyed if you look at SHA3) - that's how hashes are designed to begin with. Which I believe is the spirit of your inquiry. But the buck stops there, no security proof for those exists.
answered Jan 9 at 23:46
Jacklos44773Jacklos44773
1813
$endgroup$
$begingroup$
Very interesting, thank you
$endgroup$
– rapadura
Jan 10 at 8:40
add a comment |
$begingroup$
It's worth pointing out that in the case of SHA2 and most other hashes the compression function has a block cipher (keyed permutation) as its core.
Basically what you are asking is identical to asking how can block ciphers be resistant to known-plaintext attacks and chosen-plaintext attacks (arguably doesn't apply to SHA2 specifically because an attacker doesn't control that aspect) and even related-key attacks in the case of SHA2 (because it uses a Davies-Meyer construction where the attacker has control over what gets fed into the key schedule).
There is no proof that this methodology is reducible to something that is proven secure. It is believed to be secure due to diffusion and confusion properties which as far as is known allow no efficient backtracking. You can think of it as extreme sensitivity-to-initial-conditions in a discrete non-continuous domain.
Edit: The reason I went to block ciphers is because hash security is provably reducible to the security of the core keyed permutation (or even unkeyed if you look at SHA3) - that's how hashes are designed to begin with. Which I believe is the spirit of your inquiry. But the buck stops there, no security proof for those exists.
answered Jan 9 at 23:46
Jacklos44773Jacklos44773
1813
$endgroup$
$begingroup$
Very interesting, thank you
$endgroup$
– rapadura
Jan 10 at 8:40
add a comment |
$begingroup$
It's worth pointing out that in the case of SHA2 and most other hashes the compression function has a block cipher (keyed permutation) as its core.
Basically what you are asking is identical to asking how can block ciphers be resistant to known-plaintext attacks and chosen-plaintext attacks (arguably doesn't apply to SHA2 specifically because an attacker doesn't control that aspect) and even related-key attacks in the case of SHA2 (because it uses a Davies-Meyer construction where the attacker has control over what gets fed into the key schedule).
There is no proof that this methodology is reducible to something that is proven secure. It is believed to be secure due to diffusion and confusion properties which as far as is known allow no efficient backtracking. You can think of it as extreme sensitivity-to-initial-conditions in a discrete non-continuous domain.
Edit: The reason I went to block ciphers is because hash security is provably reducible to the security of the core keyed permutation (or even unkeyed if you look at SHA3) - that's how hashes are designed to begin with. Which I believe is the spirit of your inquiry. But the buck stops there, no security proof for those exists.
answered Jan 9 at 23:46
Jacklos44773Jacklos44773
1813
$endgroup$
It's worth pointing out that in the case of SHA2 and most other hashes the compression function has a block cipher (keyed permutation) as its core.
Basically what you are asking is identical to asking how can block ciphers be resistant to known-plaintext attacks and chosen-plaintext attacks (arguably doesn't apply to SHA2 specifically because an attacker doesn't control that aspect) and even related-key attacks in the case of SHA2 (because it uses a Davies-Meyer construction where the attacker has control over what gets fed into the key schedule).
There is no proof that this methodology is reducible to something that is proven secure. It is believed to be secure due to diffusion and confusion properties which as far as is known allow no efficient backtracking. You can think of it as extreme sensitivity-to-initial-conditions in a discrete non-continuous domain.
Edit: The reason I went to block ciphers is because hash security is provably reducible to the security of the core keyed permutation (or even unkeyed if you look at SHA3) - that's how hashes are designed to begin with. Which I believe is the spirit of your inquiry. But the buck stops there, no security proof for those exists.
answered Jan 9 at 23:46
Jacklos44773Jacklos44773
1813
edited Jan 9 at 23:51
answered Jan 9 at 23:46
Jacklos44773Jacklos44773
1813
answered Jan 9 at 23:46
Jacklos44773Jacklos44773
1813
answered Jan 9 at 23:46
Jacklos44773Jacklos44773
1813
1813
$begingroup$
Very interesting, thank you
$endgroup$
– rapadura
Jan 10 at 8:40
add a comment |
$begingroup$
Very interesting, thank you
$endgroup$
– rapadura
Jan 10 at 8:40
$begingroup$
Very interesting, thank you
$endgroup$
– rapadura
Jan 10 at 8:40
$begingroup$
Very interesting, thank you
$endgroup$
– rapadura
Jan 10 at 8:40
add a comment |
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%2f66371%2fwhat-makes-sha256-secure%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
$begingroup$
Check these 1 2 3
$endgroup$
– kelalaka
Jan 9 at 22:33
1
$begingroup$
Thanks for the good links. My question is different from "Why cant we reverse hashes", since I dont want to reverse a hash, merely curious about, if any, mathematical foundations for "security" of hash functions, as opposed to confusion and obfuscation. Seems the compression f in SHA256 is not provably secure, just hard.
$endgroup$
– rapadura
Jan 9 at 22:51
1
$begingroup$
It's worth noting that RSA and ECDSA are currently also not provably secure. We believe factoring and DLP are hard because no one we know of has found a way to do it efficiently. But we have no proof of their hardness, and perhaps we never will.
$endgroup$
– marcelm
Jan 10 at 21:00