Does GCM (or GHASH) only provides 64-bit security against forgeries?
$begingroup$
In a recent comment a doubt was voiced about my answer, which claims GCM to requires $2^{128}$ for a successful forgery. The doubt was that the square root needs to be taken meaning the security would be $2^{64}$.
So of course I immediately checked the relevant security theorem (corollary 4):
$$mathbf{Adv}^{text{auth}}_{operatorname{GCM}[operatorname{Perm}(n),tau]}(mathcal A)leq frac{0.5(sigma+q+q'+1)^2}{2^n}+frac{q'(l_A+1)}{2^tau}$$
with $sigma$ being the total plaintext size in blocks, $q$ being the total number of encryption queries, $q'$ being the total number of decryption queries, $n$ being the size in bits of the underlying permutation, $l_A$ being maximum authenticated input length in blocks and $tau$ being the tag size in bits.
Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break.
Now my question is:
When talking about "n-bits of security" or "needs $2^n$ operations to break", do we usually talk about "online" security, ie queries to an oracle can be done and cost $1$ or "offline" security where no oracles are available or do we need to make this decision depending on the situation?
TL;DR: Does GCM offer 64 or 128 bit security?
terminology security-definition
asked 5 hours ago
SEJPM♦SEJPM
28.8k556135
$endgroup$
add a comment |
$begingroup$
In a recent comment a doubt was voiced about my answer, which claims GCM to requires $2^{128}$ for a successful forgery. The doubt was that the square root needs to be taken meaning the security would be $2^{64}$.
So of course I immediately checked the relevant security theorem (corollary 4):
$$mathbf{Adv}^{text{auth}}_{operatorname{GCM}[operatorname{Perm}(n),tau]}(mathcal A)leq frac{0.5(sigma+q+q'+1)^2}{2^n}+frac{q'(l_A+1)}{2^tau}$$
with $sigma$ being the total plaintext size in blocks, $q$ being the total number of encryption queries, $q'$ being the total number of decryption queries, $n$ being the size in bits of the underlying permutation, $l_A$ being maximum authenticated input length in blocks and $tau$ being the tag size in bits.
Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break.
Now my question is:
When talking about "n-bits of security" or "needs $2^n$ operations to break", do we usually talk about "online" security, ie queries to an oracle can be done and cost $1$ or "offline" security where no oracles are available or do we need to make this decision depending on the situation?
TL;DR: Does GCM offer 64 or 128 bit security?
terminology security-definition
asked 5 hours ago
SEJPM♦SEJPM
28.8k556135
$endgroup$
$begingroup$
And, I've noticed from this answer
$endgroup$
– kelalaka
5 hours ago
1
$begingroup$
The theorem only states an upper bound on the advantage. From this alone one should not conclude ``Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break. ''.
$endgroup$
– LeoDucas
2 hours ago
add a comment |
$begingroup$
In a recent comment a doubt was voiced about my answer, which claims GCM to requires $2^{128}$ for a successful forgery. The doubt was that the square root needs to be taken meaning the security would be $2^{64}$.
So of course I immediately checked the relevant security theorem (corollary 4):
$$mathbf{Adv}^{text{auth}}_{operatorname{GCM}[operatorname{Perm}(n),tau]}(mathcal A)leq frac{0.5(sigma+q+q'+1)^2}{2^n}+frac{q'(l_A+1)}{2^tau}$$
with $sigma$ being the total plaintext size in blocks, $q$ being the total number of encryption queries, $q'$ being the total number of decryption queries, $n$ being the size in bits of the underlying permutation, $l_A$ being maximum authenticated input length in blocks and $tau$ being the tag size in bits.
Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break.
Now my question is:
When talking about "n-bits of security" or "needs $2^n$ operations to break", do we usually talk about "online" security, ie queries to an oracle can be done and cost $1$ or "offline" security where no oracles are available or do we need to make this decision depending on the situation?
TL;DR: Does GCM offer 64 or 128 bit security?
terminology security-definition
asked 5 hours ago
SEJPM♦SEJPM
28.8k556135
$endgroup$
In a recent comment a doubt was voiced about my answer, which claims GCM to requires $2^{128}$ for a successful forgery. The doubt was that the square root needs to be taken meaning the security would be $2^{64}$.
So of course I immediately checked the relevant security theorem (corollary 4):
$$mathbf{Adv}^{text{auth}}_{operatorname{GCM}[operatorname{Perm}(n),tau]}(mathcal A)leq frac{0.5(sigma+q+q'+1)^2}{2^n}+frac{q'(l_A+1)}{2^tau}$$
with $sigma$ being the total plaintext size in blocks, $q$ being the total number of encryption queries, $q'$ being the total number of decryption queries, $n$ being the size in bits of the underlying permutation, $l_A$ being maximum authenticated input length in blocks and $tau$ being the tag size in bits.
Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break.
Now my question is:
When talking about "n-bits of security" or "needs $2^n$ operations to break", do we usually talk about "online" security, ie queries to an oracle can be done and cost $1$ or "offline" security where no oracles are available or do we need to make this decision depending on the situation?
TL;DR: Does GCM offer 64 or 128 bit security?
terminology security-definition
terminology security-definition
asked 5 hours ago
SEJPM♦SEJPM
28.8k556135
asked 5 hours ago
SEJPM♦SEJPM
28.8k556135
asked 5 hours ago
SEJPM♦SEJPM
28.8k556135
asked 5 hours ago
SEJPM♦SEJPM
28.8k556135
asked 5 hours ago
SEJPM♦SEJPM
28.8k556135
28.8k556135
$begingroup$
And, I've noticed from this answer
$endgroup$
– kelalaka
5 hours ago
1
$begingroup$
The theorem only states an upper bound on the advantage. From this alone one should not conclude ``Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break. ''.
$endgroup$
– LeoDucas
2 hours ago
add a comment |
$begingroup$
And, I've noticed from this answer
$endgroup$
– kelalaka
5 hours ago
1
$begingroup$
The theorem only states an upper bound on the advantage. From this alone one should not conclude ``Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break. ''.
$endgroup$
– LeoDucas
2 hours ago
$begingroup$
And, I've noticed from this answer
$endgroup$
– kelalaka
5 hours ago
$begingroup$
And, I've noticed from this answer
$endgroup$
– kelalaka
5 hours ago
1
1
$begingroup$
The theorem only states an upper bound on the advantage. From this alone one should not conclude ``Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break. ''.
$endgroup$
– LeoDucas
2 hours ago
$begingroup$
The theorem only states an upper bound on the advantage. From this alone one should not conclude ``Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break. ''.
$endgroup$
– LeoDucas
2 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
According to the references, AES-GCM offers roughly 64-bit authenticity security (i.e., against forgery attacks) for 128-bit block size and long-enough (>=64-bit) tag size. When the number of queries appears in the security bounds, "online" security should always be the case. The word "query" corresponds to an oracle, and an oracle cannot be attacked offline.
answered 3 hours ago
Shan ChenShan Chen
1,450612
$endgroup$
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%2f67261%2fdoes-gcm-or-ghash-only-provides-64-bit-security-against-forgeries%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$
According to the references, AES-GCM offers roughly 64-bit authenticity security (i.e., against forgery attacks) for 128-bit block size and long-enough (>=64-bit) tag size. When the number of queries appears in the security bounds, "online" security should always be the case. The word "query" corresponds to an oracle, and an oracle cannot be attacked offline.
answered 3 hours ago
Shan ChenShan Chen
1,450612
$endgroup$
add a comment |
$begingroup$
According to the references, AES-GCM offers roughly 64-bit authenticity security (i.e., against forgery attacks) for 128-bit block size and long-enough (>=64-bit) tag size. When the number of queries appears in the security bounds, "online" security should always be the case. The word "query" corresponds to an oracle, and an oracle cannot be attacked offline.
answered 3 hours ago
Shan ChenShan Chen
1,450612
$endgroup$
add a comment |
$begingroup$
According to the references, AES-GCM offers roughly 64-bit authenticity security (i.e., against forgery attacks) for 128-bit block size and long-enough (>=64-bit) tag size. When the number of queries appears in the security bounds, "online" security should always be the case. The word "query" corresponds to an oracle, and an oracle cannot be attacked offline.
answered 3 hours ago
Shan ChenShan Chen
1,450612
$endgroup$
According to the references, AES-GCM offers roughly 64-bit authenticity security (i.e., against forgery attacks) for 128-bit block size and long-enough (>=64-bit) tag size. When the number of queries appears in the security bounds, "online" security should always be the case. The word "query" corresponds to an oracle, and an oracle cannot be attacked offline.
answered 3 hours ago
Shan ChenShan Chen
1,450612
answered 3 hours ago
Shan ChenShan Chen
1,450612
answered 3 hours ago
Shan ChenShan Chen
1,450612
answered 3 hours ago
Shan ChenShan Chen
1,450612
1,450612
add a comment |
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%2f67261%2fdoes-gcm-or-ghash-only-provides-64-bit-security-against-forgeries%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$
And, I've noticed from this answer
$endgroup$
– kelalaka
5 hours ago
1
$begingroup$
The theorem only states an upper bound on the advantage. From this alone one should not conclude ``Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break. ''.
$endgroup$
– LeoDucas
2 hours ago