What are the consequences of removing a single byte from a sha256 hash?
$begingroup$
I'm working on a system (Ethereum) where it is significantly cheaper to store 32 bytes than 33 bytes. I'd like to create a table where data is stored based on its hash.
Sha256 would meet this criteria since it outputs 32 bytes.
However, I'd also like to include a "version" byte in case I need to change the hash algorithm in the future. This would require 33 bytes.
One simple solution is to simply chop off the last byte and only use the first 31 bytes for the lookup.
- Does this bias the hash in any way?
- My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
- My assumption is this would increase the likelyhood of a hash collision by 25600%. Is that correct?
hash collision-resistance sha-256 preimage-resistance
edited Nov 25 '18 at 23:03
kelalaka
7,12522244
asked Nov 25 '18 at 21:36
Aakil FernandesAakil Fernandes
19015
$endgroup$
add a comment |
$begingroup$
I'm working on a system (Ethereum) where it is significantly cheaper to store 32 bytes than 33 bytes. I'd like to create a table where data is stored based on its hash.
Sha256 would meet this criteria since it outputs 32 bytes.
However, I'd also like to include a "version" byte in case I need to change the hash algorithm in the future. This would require 33 bytes.
One simple solution is to simply chop off the last byte and only use the first 31 bytes for the lookup.
- Does this bias the hash in any way?
- My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
- My assumption is this would increase the likelyhood of a hash collision by 25600%. Is that correct?
hash collision-resistance sha-256 preimage-resistance
edited Nov 25 '18 at 23:03
kelalaka
7,12522244
asked Nov 25 '18 at 21:36
Aakil FernandesAakil Fernandes
19015
$endgroup$
add a comment |
$begingroup$
I'm working on a system (Ethereum) where it is significantly cheaper to store 32 bytes than 33 bytes. I'd like to create a table where data is stored based on its hash.
Sha256 would meet this criteria since it outputs 32 bytes.
However, I'd also like to include a "version" byte in case I need to change the hash algorithm in the future. This would require 33 bytes.
One simple solution is to simply chop off the last byte and only use the first 31 bytes for the lookup.
- Does this bias the hash in any way?
- My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
- My assumption is this would increase the likelyhood of a hash collision by 25600%. Is that correct?
hash collision-resistance sha-256 preimage-resistance
edited Nov 25 '18 at 23:03
kelalaka
7,12522244
asked Nov 25 '18 at 21:36
Aakil FernandesAakil Fernandes
19015
$endgroup$
I'm working on a system (Ethereum) where it is significantly cheaper to store 32 bytes than 33 bytes. I'd like to create a table where data is stored based on its hash.
Sha256 would meet this criteria since it outputs 32 bytes.
However, I'd also like to include a "version" byte in case I need to change the hash algorithm in the future. This would require 33 bytes.
One simple solution is to simply chop off the last byte and only use the first 31 bytes for the lookup.
- Does this bias the hash in any way?
- My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
- My assumption is this would increase the likelyhood of a hash collision by 25600%. Is that correct?
hash collision-resistance sha-256 preimage-resistance
hash collision-resistance sha-256 preimage-resistance
edited Nov 25 '18 at 23:03
kelalaka
7,12522244
asked Nov 25 '18 at 21:36
Aakil FernandesAakil Fernandes
19015
edited Nov 25 '18 at 23:03
kelalaka
7,12522244
asked Nov 25 '18 at 21:36
Aakil FernandesAakil Fernandes
19015
edited Nov 25 '18 at 23:03
kelalaka
7,12522244
edited Nov 25 '18 at 23:03
kelalaka
7,12522244
edited Nov 25 '18 at 23:03
kelalaka
7,12522244
7,12522244
asked Nov 25 '18 at 21:36
Aakil FernandesAakil Fernandes
19015
asked Nov 25 '18 at 21:36
Aakil FernandesAakil Fernandes
19015
asked Nov 25 '18 at 21:36
Aakil FernandesAakil Fernandes
19015
19015
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
- Does this bias the hash in any way?
We want the avalanche criteria on the output bits, that is a change in the any of input bit must randomly affect half of the output bits. Each bit of the hash function must depend on the input bits; removing one bit doesn't affect the others.
- My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
First of all, hash functions are not really reversible since they are compression functions, that is, they map from a large input space to a shorter space.
$$ H:{0,1}^* rightarrow {0,1}^l$$
If we want to talk about collision resistance, see the next answer.
For generic pre-image search, yes; it will decrease the computational power, as you noted.
- My assumption is this would increase the likelihood of a hash collision by 25600%. Is that correct?
Collision resistance is measured by the generic birthday attack, that is, $sqrt {2^l}$, $l$ being the output size of the hash function. SHA256 has $sqrt {2^{256}} = 2^{128}$ generic birthday attack time.
In your case we will have $sqrt {2^{256-8}} = 2^{124}$ as generic birthday attack time. Thus, we have a $2^{4}= 16$ speed-up in the attack time.
TL;DR: Truncating the hash to 31 bytes will be safe (see also this stack exchange answer
Note 1: Bitcoin miners reached $approx2^{91.6}$ SHA-256 hashes per year in 25 September 2018.
Note 2: SHA-224 defined in FIPS180-4 is calculated by truncating the SHA-256 hash value (and using different initial constants, for various technical reasons, so the value is not the same as the first 28 bytes of the SHA-256 value).
answered Nov 25 '18 at 21:57
kelalakakelalaka
7,12522244
$endgroup$
1
$begingroup$
Thanks very much! Quick question, why did you subtract 256 by 32 when calculating the generic birthday attack time? I'm decreasing the output size by 1 byte (8 bits) not 32 bits.
$endgroup$
– Aakil Fernandes
Nov 25 '18 at 22:04
2
$begingroup$
it should be 8, my mistake. let me correct.
$endgroup$
– kelalaka
Nov 25 '18 at 22:05
3
$begingroup$
@kelalaka - FWIW, what you are proposing is exactly how some SHA variants work. For example SHA-224 is often implemented by generating SHA-256 and chopping off 4 bytes. So you can simply claim you're using SHA-248
$endgroup$
– slebetman
Nov 26 '18 at 9:57
8
$begingroup$
@slebetman, IIRC, SHA-224 uses different initialization constants, too, so it doesn't give the same results as SHA-256 chopped off to length. And no, you can't say "you're using SHA-248", since no such thing exists in any standards. You could say you're using SHA-256 truncated to 248 bits, since, well, that's what you are doing.
$endgroup$
– ilkkachu
Nov 26 '18 at 11:19
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%2f64314%2fwhat-are-the-consequences-of-removing-a-single-byte-from-a-sha256-hash%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$
- Does this bias the hash in any way?
We want the avalanche criteria on the output bits, that is a change in the any of input bit must randomly affect half of the output bits. Each bit of the hash function must depend on the input bits; removing one bit doesn't affect the others.
- My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
First of all, hash functions are not really reversible since they are compression functions, that is, they map from a large input space to a shorter space.
$$ H:{0,1}^* rightarrow {0,1}^l$$
If we want to talk about collision resistance, see the next answer.
For generic pre-image search, yes; it will decrease the computational power, as you noted.
- My assumption is this would increase the likelihood of a hash collision by 25600%. Is that correct?
Collision resistance is measured by the generic birthday attack, that is, $sqrt {2^l}$, $l$ being the output size of the hash function. SHA256 has $sqrt {2^{256}} = 2^{128}$ generic birthday attack time.
In your case we will have $sqrt {2^{256-8}} = 2^{124}$ as generic birthday attack time. Thus, we have a $2^{4}= 16$ speed-up in the attack time.
TL;DR: Truncating the hash to 31 bytes will be safe (see also this stack exchange answer
Note 1: Bitcoin miners reached $approx2^{91.6}$ SHA-256 hashes per year in 25 September 2018.
Note 2: SHA-224 defined in FIPS180-4 is calculated by truncating the SHA-256 hash value (and using different initial constants, for various technical reasons, so the value is not the same as the first 28 bytes of the SHA-256 value).
answered Nov 25 '18 at 21:57
kelalakakelalaka
7,12522244
$endgroup$
1
$begingroup$
Thanks very much! Quick question, why did you subtract 256 by 32 when calculating the generic birthday attack time? I'm decreasing the output size by 1 byte (8 bits) not 32 bits.
$endgroup$
– Aakil Fernandes
Nov 25 '18 at 22:04
2
$begingroup$
it should be 8, my mistake. let me correct.
$endgroup$
– kelalaka
Nov 25 '18 at 22:05
3
$begingroup$
@kelalaka - FWIW, what you are proposing is exactly how some SHA variants work. For example SHA-224 is often implemented by generating SHA-256 and chopping off 4 bytes. So you can simply claim you're using SHA-248
$endgroup$
– slebetman
Nov 26 '18 at 9:57
8
$begingroup$
@slebetman, IIRC, SHA-224 uses different initialization constants, too, so it doesn't give the same results as SHA-256 chopped off to length. And no, you can't say "you're using SHA-248", since no such thing exists in any standards. You could say you're using SHA-256 truncated to 248 bits, since, well, that's what you are doing.
$endgroup$
– ilkkachu
Nov 26 '18 at 11:19
add a comment |
$begingroup$
- Does this bias the hash in any way?
We want the avalanche criteria on the output bits, that is a change in the any of input bit must randomly affect half of the output bits. Each bit of the hash function must depend on the input bits; removing one bit doesn't affect the others.
- My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
First of all, hash functions are not really reversible since they are compression functions, that is, they map from a large input space to a shorter space.
$$ H:{0,1}^* rightarrow {0,1}^l$$
If we want to talk about collision resistance, see the next answer.
For generic pre-image search, yes; it will decrease the computational power, as you noted.
- My assumption is this would increase the likelihood of a hash collision by 25600%. Is that correct?
Collision resistance is measured by the generic birthday attack, that is, $sqrt {2^l}$, $l$ being the output size of the hash function. SHA256 has $sqrt {2^{256}} = 2^{128}$ generic birthday attack time.
In your case we will have $sqrt {2^{256-8}} = 2^{124}$ as generic birthday attack time. Thus, we have a $2^{4}= 16$ speed-up in the attack time.
TL;DR: Truncating the hash to 31 bytes will be safe (see also this stack exchange answer
Note 1: Bitcoin miners reached $approx2^{91.6}$ SHA-256 hashes per year in 25 September 2018.
Note 2: SHA-224 defined in FIPS180-4 is calculated by truncating the SHA-256 hash value (and using different initial constants, for various technical reasons, so the value is not the same as the first 28 bytes of the SHA-256 value).
answered Nov 25 '18 at 21:57
kelalakakelalaka
7,12522244
$endgroup$
1
$begingroup$
Thanks very much! Quick question, why did you subtract 256 by 32 when calculating the generic birthday attack time? I'm decreasing the output size by 1 byte (8 bits) not 32 bits.
$endgroup$
– Aakil Fernandes
Nov 25 '18 at 22:04
2
$begingroup$
it should be 8, my mistake. let me correct.
$endgroup$
– kelalaka
Nov 25 '18 at 22:05
3
$begingroup$
@kelalaka - FWIW, what you are proposing is exactly how some SHA variants work. For example SHA-224 is often implemented by generating SHA-256 and chopping off 4 bytes. So you can simply claim you're using SHA-248
$endgroup$
– slebetman
Nov 26 '18 at 9:57
8
$begingroup$
@slebetman, IIRC, SHA-224 uses different initialization constants, too, so it doesn't give the same results as SHA-256 chopped off to length. And no, you can't say "you're using SHA-248", since no such thing exists in any standards. You could say you're using SHA-256 truncated to 248 bits, since, well, that's what you are doing.
$endgroup$
– ilkkachu
Nov 26 '18 at 11:19
add a comment |
$begingroup$
- Does this bias the hash in any way?
We want the avalanche criteria on the output bits, that is a change in the any of input bit must randomly affect half of the output bits. Each bit of the hash function must depend on the input bits; removing one bit doesn't affect the others.
- My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
First of all, hash functions are not really reversible since they are compression functions, that is, they map from a large input space to a shorter space.
$$ H:{0,1}^* rightarrow {0,1}^l$$
If we want to talk about collision resistance, see the next answer.
For generic pre-image search, yes; it will decrease the computational power, as you noted.
- My assumption is this would increase the likelihood of a hash collision by 25600%. Is that correct?
Collision resistance is measured by the generic birthday attack, that is, $sqrt {2^l}$, $l$ being the output size of the hash function. SHA256 has $sqrt {2^{256}} = 2^{128}$ generic birthday attack time.
In your case we will have $sqrt {2^{256-8}} = 2^{124}$ as generic birthday attack time. Thus, we have a $2^{4}= 16$ speed-up in the attack time.
TL;DR: Truncating the hash to 31 bytes will be safe (see also this stack exchange answer
Note 1: Bitcoin miners reached $approx2^{91.6}$ SHA-256 hashes per year in 25 September 2018.
Note 2: SHA-224 defined in FIPS180-4 is calculated by truncating the SHA-256 hash value (and using different initial constants, for various technical reasons, so the value is not the same as the first 28 bytes of the SHA-256 value).
answered Nov 25 '18 at 21:57
kelalakakelalaka
7,12522244
$endgroup$
- Does this bias the hash in any way?
We want the avalanche criteria on the output bits, that is a change in the any of input bit must randomly affect half of the output bits. Each bit of the hash function must depend on the input bits; removing one bit doesn't affect the others.
- My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
First of all, hash functions are not really reversible since they are compression functions, that is, they map from a large input space to a shorter space.
$$ H:{0,1}^* rightarrow {0,1}^l$$
If we want to talk about collision resistance, see the next answer.
For generic pre-image search, yes; it will decrease the computational power, as you noted.
- My assumption is this would increase the likelihood of a hash collision by 25600%. Is that correct?
Collision resistance is measured by the generic birthday attack, that is, $sqrt {2^l}$, $l$ being the output size of the hash function. SHA256 has $sqrt {2^{256}} = 2^{128}$ generic birthday attack time.
In your case we will have $sqrt {2^{256-8}} = 2^{124}$ as generic birthday attack time. Thus, we have a $2^{4}= 16$ speed-up in the attack time.
TL;DR: Truncating the hash to 31 bytes will be safe (see also this stack exchange answer
Note 1: Bitcoin miners reached $approx2^{91.6}$ SHA-256 hashes per year in 25 September 2018.
Note 2: SHA-224 defined in FIPS180-4 is calculated by truncating the SHA-256 hash value (and using different initial constants, for various technical reasons, so the value is not the same as the first 28 bytes of the SHA-256 value).
answered Nov 25 '18 at 21:57
kelalakakelalaka
7,12522244
edited Jan 25 at 11:04
answered Nov 25 '18 at 21:57
kelalakakelalaka
7,12522244
answered Nov 25 '18 at 21:57
kelalakakelalaka
7,12522244
answered Nov 25 '18 at 21:57
kelalakakelalaka
7,12522244
7,12522244
1
$begingroup$
Thanks very much! Quick question, why did you subtract 256 by 32 when calculating the generic birthday attack time? I'm decreasing the output size by 1 byte (8 bits) not 32 bits.
$endgroup$
– Aakil Fernandes
Nov 25 '18 at 22:04
2
$begingroup$
it should be 8, my mistake. let me correct.
$endgroup$
– kelalaka
Nov 25 '18 at 22:05
3
$begingroup$
@kelalaka - FWIW, what you are proposing is exactly how some SHA variants work. For example SHA-224 is often implemented by generating SHA-256 and chopping off 4 bytes. So you can simply claim you're using SHA-248
$endgroup$
– slebetman
Nov 26 '18 at 9:57
8
$begingroup$
@slebetman, IIRC, SHA-224 uses different initialization constants, too, so it doesn't give the same results as SHA-256 chopped off to length. And no, you can't say "you're using SHA-248", since no such thing exists in any standards. You could say you're using SHA-256 truncated to 248 bits, since, well, that's what you are doing.
$endgroup$
– ilkkachu
Nov 26 '18 at 11:19
add a comment |
1
$begingroup$
Thanks very much! Quick question, why did you subtract 256 by 32 when calculating the generic birthday attack time? I'm decreasing the output size by 1 byte (8 bits) not 32 bits.
$endgroup$
– Aakil Fernandes
Nov 25 '18 at 22:04
2
$begingroup$
it should be 8, my mistake. let me correct.
$endgroup$
– kelalaka
Nov 25 '18 at 22:05
3
$begingroup$
@kelalaka - FWIW, what you are proposing is exactly how some SHA variants work. For example SHA-224 is often implemented by generating SHA-256 and chopping off 4 bytes. So you can simply claim you're using SHA-248
$endgroup$
– slebetman
Nov 26 '18 at 9:57
8
$begingroup$
@slebetman, IIRC, SHA-224 uses different initialization constants, too, so it doesn't give the same results as SHA-256 chopped off to length. And no, you can't say "you're using SHA-248", since no such thing exists in any standards. You could say you're using SHA-256 truncated to 248 bits, since, well, that's what you are doing.
$endgroup$
– ilkkachu
Nov 26 '18 at 11:19
1
1
$begingroup$
Thanks very much! Quick question, why did you subtract 256 by 32 when calculating the generic birthday attack time? I'm decreasing the output size by 1 byte (8 bits) not 32 bits.
$endgroup$
– Aakil Fernandes
Nov 25 '18 at 22:04
$begingroup$
Thanks very much! Quick question, why did you subtract 256 by 32 when calculating the generic birthday attack time? I'm decreasing the output size by 1 byte (8 bits) not 32 bits.
$endgroup$
– Aakil Fernandes
Nov 25 '18 at 22:04
2
2
$begingroup$
it should be 8, my mistake. let me correct.
$endgroup$
– kelalaka
Nov 25 '18 at 22:05
$begingroup$
it should be 8, my mistake. let me correct.
$endgroup$
– kelalaka
Nov 25 '18 at 22:05
3
3
$begingroup$
@kelalaka - FWIW, what you are proposing is exactly how some SHA variants work. For example SHA-224 is often implemented by generating SHA-256 and chopping off 4 bytes. So you can simply claim you're using SHA-248
$endgroup$
– slebetman
Nov 26 '18 at 9:57
$begingroup$
@kelalaka - FWIW, what you are proposing is exactly how some SHA variants work. For example SHA-224 is often implemented by generating SHA-256 and chopping off 4 bytes. So you can simply claim you're using SHA-248
$endgroup$
– slebetman
Nov 26 '18 at 9:57
8
8
$begingroup$
@slebetman, IIRC, SHA-224 uses different initialization constants, too, so it doesn't give the same results as SHA-256 chopped off to length. And no, you can't say "you're using SHA-248", since no such thing exists in any standards. You could say you're using SHA-256 truncated to 248 bits, since, well, that's what you are doing.
$endgroup$
– ilkkachu
Nov 26 '18 at 11:19
$begingroup$
@slebetman, IIRC, SHA-224 uses different initialization constants, too, so it doesn't give the same results as SHA-256 chopped off to length. And no, you can't say "you're using SHA-248", since no such thing exists in any standards. You could say you're using SHA-256 truncated to 248 bits, since, well, that's what you are doing.
$endgroup$
– ilkkachu
Nov 26 '18 at 11:19
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%2f64314%2fwhat-are-the-consequences-of-removing-a-single-byte-from-a-sha256-hash%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
