What do the security definitions of SHA-3 mean, quantitatively?
$begingroup$
In the SHA-3 standard (page 31) the security of SHA-3 is defined quantitatively, for example, they are saying SHA3-256 provides 256 bits of preimage resistance. How is this number of bits to be interpreted?
The definition of preimage resistance that I know doesn't speak of bits, but of a running time $t$ (and a success probability $epsilon$).
Intuitively, I'd interpret it like this: An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?
Bonus: Is there a (citable) source for this? The SHA-3 standard has shockingly few references, and the Keccak reference doesn't speak about preimage resistance at all.
hash preimage-resistance sha-3
asked Jan 29 at 16:29
MarianMarian
1163
$endgroup$
add a comment |
$begingroup$
In the SHA-3 standard (page 31) the security of SHA-3 is defined quantitatively, for example, they are saying SHA3-256 provides 256 bits of preimage resistance. How is this number of bits to be interpreted?
The definition of preimage resistance that I know doesn't speak of bits, but of a running time $t$ (and a success probability $epsilon$).
Intuitively, I'd interpret it like this: An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?
Bonus: Is there a (citable) source for this? The SHA-3 standard has shockingly few references, and the Keccak reference doesn't speak about preimage resistance at all.
hash preimage-resistance sha-3
asked Jan 29 at 16:29
MarianMarian
1163
$endgroup$
1
$begingroup$
The Keccak reference does talk about preimage resistance... this is part of the "flat sponge claim".
$endgroup$
– Aleph
Jan 29 at 16:38
add a comment |
$begingroup$
In the SHA-3 standard (page 31) the security of SHA-3 is defined quantitatively, for example, they are saying SHA3-256 provides 256 bits of preimage resistance. How is this number of bits to be interpreted?
The definition of preimage resistance that I know doesn't speak of bits, but of a running time $t$ (and a success probability $epsilon$).
Intuitively, I'd interpret it like this: An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?
Bonus: Is there a (citable) source for this? The SHA-3 standard has shockingly few references, and the Keccak reference doesn't speak about preimage resistance at all.
hash preimage-resistance sha-3
asked Jan 29 at 16:29
MarianMarian
1163
$endgroup$
In the SHA-3 standard (page 31) the security of SHA-3 is defined quantitatively, for example, they are saying SHA3-256 provides 256 bits of preimage resistance. How is this number of bits to be interpreted?
The definition of preimage resistance that I know doesn't speak of bits, but of a running time $t$ (and a success probability $epsilon$).
Intuitively, I'd interpret it like this: An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?
Bonus: Is there a (citable) source for this? The SHA-3 standard has shockingly few references, and the Keccak reference doesn't speak about preimage resistance at all.
hash preimage-resistance sha-3
hash preimage-resistance sha-3
asked Jan 29 at 16:29
MarianMarian
1163
asked Jan 29 at 16:29
MarianMarian
1163
edited Jan 30 at 11:20
Marian
asked Jan 29 at 16:29
MarianMarian
1163
asked Jan 29 at 16:29
MarianMarian
1163
asked Jan 29 at 16:29
MarianMarian
1163
1163
1
$begingroup$
The Keccak reference does talk about preimage resistance... this is part of the "flat sponge claim".
$endgroup$
– Aleph
Jan 29 at 16:38
add a comment |
1
$begingroup$
The Keccak reference does talk about preimage resistance... this is part of the "flat sponge claim".
$endgroup$
– Aleph
Jan 29 at 16:38
1
1
$begingroup$
The Keccak reference does talk about preimage resistance... this is part of the "flat sponge claim".
$endgroup$
– Aleph
Jan 29 at 16:38
$begingroup$
The Keccak reference does talk about preimage resistance... this is part of the "flat sponge claim".
$endgroup$
– Aleph
Jan 29 at 16:38
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Aleph's comment and pointer to the Keccak reference goes a very long way to answering this question (p. 9):
The key words here are "workload equivalent to $N$ calls to $mathrm{Keccak-}f[r + c]$ or its inverse." Invocations of the Keccak permutation are being used as the unit of time. Your intuitive take that it's hash function invocations isn't very far off from this, but note that a single SHA-3 call may result in one or more permutation calls, so Claim 1 is more stringent.
In a more abstract setting, where we're talking about the sponge construction in general and not a concrete implementation like Keccak, we talk about the permutation (and its inverse) as an oracle that the adversary can freely call (often people say "query") as they see fit. Then the security of the construction is expressed in terms of how many queries the adversary makes. The oracle calls are treated as outputting the result of a random permutation in constant time.
See also: the Keccak team's more generic treatment of sponge functions.
answered Jan 29 at 19:17
Luis CasillasLuis Casillas
9,74011438
$endgroup$
$begingroup$
but note that a single SHA-3 call may result in one or more permutation calls – this is however in the order of the number of rounds, right? So the success probability would only be slightly higher when allowing $2^n$ hash evaluations?
$endgroup$
– Marian
Jan 30 at 12:25
$begingroup$
But actually my question is more general, how do NIST define their security levels? In the linked standard, they also give numbers for SHA2's preimage resistance (also 256 bits for SHA256), which cannot be defined in terms of Keccak permutation calls. Do they use my $2^n$ definition (justified as in my comment above)?
$endgroup$
– Marian
Jan 30 at 12:28
1
$begingroup$
@Marian NIST defines bits of security in this way
$endgroup$
– Ruggero
Jan 30 at 12:58
$begingroup$
@Ruggero Great, thanks, that was sort of what I was searching for, I was just expecting it to be a little more complicated. So indeed their definition is even looser than mine and they sweep all of our discussion above under the $mathcal O$ carpet ;)
$endgroup$
– Marian
Jan 30 at 16:13
add a comment |
$begingroup$
How is this number of bits to be interpreted?
In Cryptography we talk about the number of bits. 256 bits means that you need to search in $2^{256}$ elements or say 256-bit search space.
Running time is a vague term. What is the CPU, memory, computer, server, hardware are you talking about? This and the other not mentioned ones can change the running time.
The definition of preimage resistance that, but of a running time $t$ (and a success probability $epsilon$).
It is the formalization of running time as done in CS for big-Oh ($mathcal{O}$) notation. We consider polynomial time adversaries so that we set a bound for them otherwise we cannot talk about unbounded adversaries.
So we say a polynomial time adversary with $epsilon$ advantage. If the epsilon is negligible then the adversary has no advantage.
An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?
Again, In Cryptography the running time is not considered while calculating the security. However, when designing people consider fast and secure algorithms are better. But, this has a drawback in hash function since searcing a preimage is shorter. And, similarly for block ciphers,too, shorter brute-force time.
Bonus:
See Rogaway at al. Cryptographic Hash-Function Basic as already you looked and a good Cryptography book as Katz-Lindell's book.
answered Jan 29 at 16:46
kelalakakelalaka
7,30522244
$endgroup$
$begingroup$
I think you got a little caught by that "New contributor" note near my name – My question was a bit deeper than what you replied to. Thank you anyway!
$endgroup$
– Marian
Jan 30 at 11:57
$begingroup$
@Marian Nope, I want to give the answer in that way. I've no idea who you are :). I'll delete this comment.
$endgroup$
– kelalaka
Jan 30 at 12:13
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%2f66885%2fwhat-do-the-security-definitions-of-sha-3-mean-quantitatively%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$
Aleph's comment and pointer to the Keccak reference goes a very long way to answering this question (p. 9):
The key words here are "workload equivalent to $N$ calls to $mathrm{Keccak-}f[r + c]$ or its inverse." Invocations of the Keccak permutation are being used as the unit of time. Your intuitive take that it's hash function invocations isn't very far off from this, but note that a single SHA-3 call may result in one or more permutation calls, so Claim 1 is more stringent.
In a more abstract setting, where we're talking about the sponge construction in general and not a concrete implementation like Keccak, we talk about the permutation (and its inverse) as an oracle that the adversary can freely call (often people say "query") as they see fit. Then the security of the construction is expressed in terms of how many queries the adversary makes. The oracle calls are treated as outputting the result of a random permutation in constant time.
See also: the Keccak team's more generic treatment of sponge functions.
answered Jan 29 at 19:17
Luis CasillasLuis Casillas
9,74011438
$endgroup$
$begingroup$
but note that a single SHA-3 call may result in one or more permutation calls – this is however in the order of the number of rounds, right? So the success probability would only be slightly higher when allowing $2^n$ hash evaluations?
$endgroup$
– Marian
Jan 30 at 12:25
$begingroup$
But actually my question is more general, how do NIST define their security levels? In the linked standard, they also give numbers for SHA2's preimage resistance (also 256 bits for SHA256), which cannot be defined in terms of Keccak permutation calls. Do they use my $2^n$ definition (justified as in my comment above)?
$endgroup$
– Marian
Jan 30 at 12:28
1
$begingroup$
@Marian NIST defines bits of security in this way
$endgroup$
– Ruggero
Jan 30 at 12:58
$begingroup$
@Ruggero Great, thanks, that was sort of what I was searching for, I was just expecting it to be a little more complicated. So indeed their definition is even looser than mine and they sweep all of our discussion above under the $mathcal O$ carpet ;)
$endgroup$
– Marian
Jan 30 at 16:13
add a comment |
$begingroup$
Aleph's comment and pointer to the Keccak reference goes a very long way to answering this question (p. 9):
The key words here are "workload equivalent to $N$ calls to $mathrm{Keccak-}f[r + c]$ or its inverse." Invocations of the Keccak permutation are being used as the unit of time. Your intuitive take that it's hash function invocations isn't very far off from this, but note that a single SHA-3 call may result in one or more permutation calls, so Claim 1 is more stringent.
In a more abstract setting, where we're talking about the sponge construction in general and not a concrete implementation like Keccak, we talk about the permutation (and its inverse) as an oracle that the adversary can freely call (often people say "query") as they see fit. Then the security of the construction is expressed in terms of how many queries the adversary makes. The oracle calls are treated as outputting the result of a random permutation in constant time.
See also: the Keccak team's more generic treatment of sponge functions.
answered Jan 29 at 19:17
Luis CasillasLuis Casillas
9,74011438
$endgroup$
$begingroup$
but note that a single SHA-3 call may result in one or more permutation calls – this is however in the order of the number of rounds, right? So the success probability would only be slightly higher when allowing $2^n$ hash evaluations?
$endgroup$
– Marian
Jan 30 at 12:25
$begingroup$
But actually my question is more general, how do NIST define their security levels? In the linked standard, they also give numbers for SHA2's preimage resistance (also 256 bits for SHA256), which cannot be defined in terms of Keccak permutation calls. Do they use my $2^n$ definition (justified as in my comment above)?
$endgroup$
– Marian
Jan 30 at 12:28
1
$begingroup$
@Marian NIST defines bits of security in this way
$endgroup$
– Ruggero
Jan 30 at 12:58
$begingroup$
@Ruggero Great, thanks, that was sort of what I was searching for, I was just expecting it to be a little more complicated. So indeed their definition is even looser than mine and they sweep all of our discussion above under the $mathcal O$ carpet ;)
$endgroup$
– Marian
Jan 30 at 16:13
add a comment |
$begingroup$
Aleph's comment and pointer to the Keccak reference goes a very long way to answering this question (p. 9):
The key words here are "workload equivalent to $N$ calls to $mathrm{Keccak-}f[r + c]$ or its inverse." Invocations of the Keccak permutation are being used as the unit of time. Your intuitive take that it's hash function invocations isn't very far off from this, but note that a single SHA-3 call may result in one or more permutation calls, so Claim 1 is more stringent.
In a more abstract setting, where we're talking about the sponge construction in general and not a concrete implementation like Keccak, we talk about the permutation (and its inverse) as an oracle that the adversary can freely call (often people say "query") as they see fit. Then the security of the construction is expressed in terms of how many queries the adversary makes. The oracle calls are treated as outputting the result of a random permutation in constant time.
See also: the Keccak team's more generic treatment of sponge functions.
answered Jan 29 at 19:17
Luis CasillasLuis Casillas
9,74011438
$endgroup$
Aleph's comment and pointer to the Keccak reference goes a very long way to answering this question (p. 9):
The key words here are "workload equivalent to $N$ calls to $mathrm{Keccak-}f[r + c]$ or its inverse." Invocations of the Keccak permutation are being used as the unit of time. Your intuitive take that it's hash function invocations isn't very far off from this, but note that a single SHA-3 call may result in one or more permutation calls, so Claim 1 is more stringent.
In a more abstract setting, where we're talking about the sponge construction in general and not a concrete implementation like Keccak, we talk about the permutation (and its inverse) as an oracle that the adversary can freely call (often people say "query") as they see fit. Then the security of the construction is expressed in terms of how many queries the adversary makes. The oracle calls are treated as outputting the result of a random permutation in constant time.
See also: the Keccak team's more generic treatment of sponge functions.
answered Jan 29 at 19:17
Luis CasillasLuis Casillas
9,74011438
answered Jan 29 at 19:17
Luis CasillasLuis Casillas
9,74011438
answered Jan 29 at 19:17
Luis CasillasLuis Casillas
9,74011438
answered Jan 29 at 19:17
Luis CasillasLuis Casillas
9,74011438
9,74011438
$begingroup$
but note that a single SHA-3 call may result in one or more permutation calls – this is however in the order of the number of rounds, right? So the success probability would only be slightly higher when allowing $2^n$ hash evaluations?
$endgroup$
– Marian
Jan 30 at 12:25
$begingroup$
But actually my question is more general, how do NIST define their security levels? In the linked standard, they also give numbers for SHA2's preimage resistance (also 256 bits for SHA256), which cannot be defined in terms of Keccak permutation calls. Do they use my $2^n$ definition (justified as in my comment above)?
$endgroup$
– Marian
Jan 30 at 12:28
1
$begingroup$
@Marian NIST defines bits of security in this way
$endgroup$
– Ruggero
Jan 30 at 12:58
$begingroup$
@Ruggero Great, thanks, that was sort of what I was searching for, I was just expecting it to be a little more complicated. So indeed their definition is even looser than mine and they sweep all of our discussion above under the $mathcal O$ carpet ;)
$endgroup$
– Marian
Jan 30 at 16:13
add a comment |
$begingroup$
but note that a single SHA-3 call may result in one or more permutation calls – this is however in the order of the number of rounds, right? So the success probability would only be slightly higher when allowing $2^n$ hash evaluations?
$endgroup$
– Marian
Jan 30 at 12:25
$begingroup$
But actually my question is more general, how do NIST define their security levels? In the linked standard, they also give numbers for SHA2's preimage resistance (also 256 bits for SHA256), which cannot be defined in terms of Keccak permutation calls. Do they use my $2^n$ definition (justified as in my comment above)?
$endgroup$
– Marian
Jan 30 at 12:28
1
$begingroup$
@Marian NIST defines bits of security in this way
$endgroup$
– Ruggero
Jan 30 at 12:58
$begingroup$
@Ruggero Great, thanks, that was sort of what I was searching for, I was just expecting it to be a little more complicated. So indeed their definition is even looser than mine and they sweep all of our discussion above under the $mathcal O$ carpet ;)
$endgroup$
– Marian
Jan 30 at 16:13
$begingroup$
but note that a single SHA-3 call may result in one or more permutation calls – this is however in the order of the number of rounds, right? So the success probability would only be slightly higher when allowing $2^n$ hash evaluations?
$endgroup$
– Marian
Jan 30 at 12:25
$begingroup$
but note that a single SHA-3 call may result in one or more permutation calls – this is however in the order of the number of rounds, right? So the success probability would only be slightly higher when allowing $2^n$ hash evaluations?
$endgroup$
– Marian
Jan 30 at 12:25
$begingroup$
But actually my question is more general, how do NIST define their security levels? In the linked standard, they also give numbers for SHA2's preimage resistance (also 256 bits for SHA256), which cannot be defined in terms of Keccak permutation calls. Do they use my $2^n$ definition (justified as in my comment above)?
$endgroup$
– Marian
Jan 30 at 12:28
$begingroup$
But actually my question is more general, how do NIST define their security levels? In the linked standard, they also give numbers for SHA2's preimage resistance (also 256 bits for SHA256), which cannot be defined in terms of Keccak permutation calls. Do they use my $2^n$ definition (justified as in my comment above)?
$endgroup$
– Marian
Jan 30 at 12:28
1
1
$begingroup$
@Marian NIST defines bits of security in this way
$endgroup$
– Ruggero
Jan 30 at 12:58
$begingroup$
@Marian NIST defines bits of security in this way
$endgroup$
– Ruggero
Jan 30 at 12:58
$begingroup$
@Ruggero Great, thanks, that was sort of what I was searching for, I was just expecting it to be a little more complicated. So indeed their definition is even looser than mine and they sweep all of our discussion above under the $mathcal O$ carpet ;)
$endgroup$
– Marian
Jan 30 at 16:13
$begingroup$
@Ruggero Great, thanks, that was sort of what I was searching for, I was just expecting it to be a little more complicated. So indeed their definition is even looser than mine and they sweep all of our discussion above under the $mathcal O$ carpet ;)
$endgroup$
– Marian
Jan 30 at 16:13
add a comment |
$begingroup$
How is this number of bits to be interpreted?
In Cryptography we talk about the number of bits. 256 bits means that you need to search in $2^{256}$ elements or say 256-bit search space.
Running time is a vague term. What is the CPU, memory, computer, server, hardware are you talking about? This and the other not mentioned ones can change the running time.
The definition of preimage resistance that, but of a running time $t$ (and a success probability $epsilon$).
It is the formalization of running time as done in CS for big-Oh ($mathcal{O}$) notation. We consider polynomial time adversaries so that we set a bound for them otherwise we cannot talk about unbounded adversaries.
So we say a polynomial time adversary with $epsilon$ advantage. If the epsilon is negligible then the adversary has no advantage.
An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?
Again, In Cryptography the running time is not considered while calculating the security. However, when designing people consider fast and secure algorithms are better. But, this has a drawback in hash function since searcing a preimage is shorter. And, similarly for block ciphers,too, shorter brute-force time.
Bonus:
See Rogaway at al. Cryptographic Hash-Function Basic as already you looked and a good Cryptography book as Katz-Lindell's book.
answered Jan 29 at 16:46
kelalakakelalaka
7,30522244
$endgroup$
$begingroup$
I think you got a little caught by that "New contributor" note near my name – My question was a bit deeper than what you replied to. Thank you anyway!
$endgroup$
– Marian
Jan 30 at 11:57
$begingroup$
@Marian Nope, I want to give the answer in that way. I've no idea who you are :). I'll delete this comment.
$endgroup$
– kelalaka
Jan 30 at 12:13
add a comment |
$begingroup$
How is this number of bits to be interpreted?
In Cryptography we talk about the number of bits. 256 bits means that you need to search in $2^{256}$ elements or say 256-bit search space.
Running time is a vague term. What is the CPU, memory, computer, server, hardware are you talking about? This and the other not mentioned ones can change the running time.
The definition of preimage resistance that, but of a running time $t$ (and a success probability $epsilon$).
It is the formalization of running time as done in CS for big-Oh ($mathcal{O}$) notation. We consider polynomial time adversaries so that we set a bound for them otherwise we cannot talk about unbounded adversaries.
So we say a polynomial time adversary with $epsilon$ advantage. If the epsilon is negligible then the adversary has no advantage.
An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?
Again, In Cryptography the running time is not considered while calculating the security. However, when designing people consider fast and secure algorithms are better. But, this has a drawback in hash function since searcing a preimage is shorter. And, similarly for block ciphers,too, shorter brute-force time.
Bonus:
See Rogaway at al. Cryptographic Hash-Function Basic as already you looked and a good Cryptography book as Katz-Lindell's book.
answered Jan 29 at 16:46
kelalakakelalaka
7,30522244
$endgroup$
$begingroup$
I think you got a little caught by that "New contributor" note near my name – My question was a bit deeper than what you replied to. Thank you anyway!
$endgroup$
– Marian
Jan 30 at 11:57
$begingroup$
@Marian Nope, I want to give the answer in that way. I've no idea who you are :). I'll delete this comment.
$endgroup$
– kelalaka
Jan 30 at 12:13
add a comment |
$begingroup$
How is this number of bits to be interpreted?
In Cryptography we talk about the number of bits. 256 bits means that you need to search in $2^{256}$ elements or say 256-bit search space.
Running time is a vague term. What is the CPU, memory, computer, server, hardware are you talking about? This and the other not mentioned ones can change the running time.
The definition of preimage resistance that, but of a running time $t$ (and a success probability $epsilon$).
It is the formalization of running time as done in CS for big-Oh ($mathcal{O}$) notation. We consider polynomial time adversaries so that we set a bound for them otherwise we cannot talk about unbounded adversaries.
So we say a polynomial time adversary with $epsilon$ advantage. If the epsilon is negligible then the adversary has no advantage.
An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?
Again, In Cryptography the running time is not considered while calculating the security. However, when designing people consider fast and secure algorithms are better. But, this has a drawback in hash function since searcing a preimage is shorter. And, similarly for block ciphers,too, shorter brute-force time.
Bonus:
See Rogaway at al. Cryptographic Hash-Function Basic as already you looked and a good Cryptography book as Katz-Lindell's book.
answered Jan 29 at 16:46
kelalakakelalaka
7,30522244
$endgroup$
How is this number of bits to be interpreted?
In Cryptography we talk about the number of bits. 256 bits means that you need to search in $2^{256}$ elements or say 256-bit search space.
Running time is a vague term. What is the CPU, memory, computer, server, hardware are you talking about? This and the other not mentioned ones can change the running time.
The definition of preimage resistance that, but of a running time $t$ (and a success probability $epsilon$).
It is the formalization of running time as done in CS for big-Oh ($mathcal{O}$) notation. We consider polynomial time adversaries so that we set a bound for them otherwise we cannot talk about unbounded adversaries.
So we say a polynomial time adversary with $epsilon$ advantage. If the epsilon is negligible then the adversary has no advantage.
An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?
Again, In Cryptography the running time is not considered while calculating the security. However, when designing people consider fast and secure algorithms are better. But, this has a drawback in hash function since searcing a preimage is shorter. And, similarly for block ciphers,too, shorter brute-force time.
Bonus:
See Rogaway at al. Cryptographic Hash-Function Basic as already you looked and a good Cryptography book as Katz-Lindell's book.
answered Jan 29 at 16:46
kelalakakelalaka
7,30522244
edited Jan 29 at 16:54
answered Jan 29 at 16:46
kelalakakelalaka
7,30522244
answered Jan 29 at 16:46
kelalakakelalaka
7,30522244
answered Jan 29 at 16:46
kelalakakelalaka
7,30522244
7,30522244
$begingroup$
I think you got a little caught by that "New contributor" note near my name – My question was a bit deeper than what you replied to. Thank you anyway!
$endgroup$
– Marian
Jan 30 at 11:57
$begingroup$
@Marian Nope, I want to give the answer in that way. I've no idea who you are :). I'll delete this comment.
$endgroup$
– kelalaka
Jan 30 at 12:13
add a comment |
$begingroup$
I think you got a little caught by that "New contributor" note near my name – My question was a bit deeper than what you replied to. Thank you anyway!
$endgroup$
– Marian
Jan 30 at 11:57
$begingroup$
@Marian Nope, I want to give the answer in that way. I've no idea who you are :). I'll delete this comment.
$endgroup$
– kelalaka
Jan 30 at 12:13
$begingroup$
I think you got a little caught by that "New contributor" note near my name – My question was a bit deeper than what you replied to. Thank you anyway!
$endgroup$
– Marian
Jan 30 at 11:57
$begingroup$
I think you got a little caught by that "New contributor" note near my name – My question was a bit deeper than what you replied to. Thank you anyway!
$endgroup$
– Marian
Jan 30 at 11:57
$begingroup$
@Marian Nope, I want to give the answer in that way. I've no idea who you are :). I'll delete this comment.
$endgroup$
– kelalaka
Jan 30 at 12:13
$begingroup$
@Marian Nope, I want to give the answer in that way. I've no idea who you are :). I'll delete this comment.
$endgroup$
– kelalaka
Jan 30 at 12:13
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%2f66885%2fwhat-do-the-security-definitions-of-sha-3-mean-quantitatively%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
The Keccak reference does talk about preimage resistance... this is part of the "flat sponge claim".
$endgroup$
– Aleph
Jan 29 at 16:38