Why doesn't the GCM spec use a more efficient multiplication algorithm?
NIST SP 800-38D § 6.3 Multiplication Operation on Blocks describes a multiplication algorithm that, in my testing, appears to be a good amount slower then algorithm 2.40 (arbitrary reduction polynomials) in the Guide to Elliptic Curve Cryptography.
My question is...why? Does the algorithm described in NIST SP 800-38D provide better protection against timing attacks?
encryption aes finite-field gcm ghash
asked Dec 19 at 4:25
neubert
1,2241529
add a comment |
NIST SP 800-38D § 6.3 Multiplication Operation on Blocks describes a multiplication algorithm that, in my testing, appears to be a good amount slower then algorithm 2.40 (arbitrary reduction polynomials) in the Guide to Elliptic Curve Cryptography.
My question is...why? Does the algorithm described in NIST SP 800-38D provide better protection against timing attacks?
encryption aes finite-field gcm ghash
asked Dec 19 at 4:25
neubert
1,2241529
add a comment |
NIST SP 800-38D § 6.3 Multiplication Operation on Blocks describes a multiplication algorithm that, in my testing, appears to be a good amount slower then algorithm 2.40 (arbitrary reduction polynomials) in the Guide to Elliptic Curve Cryptography.
My question is...why? Does the algorithm described in NIST SP 800-38D provide better protection against timing attacks?
encryption aes finite-field gcm ghash
asked Dec 19 at 4:25
neubert
1,2241529
NIST SP 800-38D § 6.3 Multiplication Operation on Blocks describes a multiplication algorithm that, in my testing, appears to be a good amount slower then algorithm 2.40 (arbitrary reduction polynomials) in the Guide to Elliptic Curve Cryptography.
My question is...why? Does the algorithm described in NIST SP 800-38D provide better protection against timing attacks?
encryption aes finite-field gcm ghash
encryption aes finite-field gcm ghash
asked Dec 19 at 4:25
neubert
1,2241529
asked Dec 19 at 4:25
neubert
1,2241529
edited Dec 19 at 18:27
asked Dec 19 at 4:25
neubert
1,2241529
asked Dec 19 at 4:25
neubert
1,2241529
asked Dec 19 at 4:25
neubert
1,2241529
1,2241529
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
My question is... why?
There are a number of different algorithms that perform $GF(2^{128})$ multiplication, all with different trade-offs (speed on specific platforms, program size, memory usage, complexity, side channel resistance, etc). NIST doesn't care which one you use, as long as you get the expected result at the end.
As for why NIST decided to put that specific algorithm as an example in the spec, well, I didn't write the spec, so I can't be certain. My guess is that they decided on the goals of simplicity and clarity, and that algorithm was the best they could find that would meet those goals (whether it is actually simpler or clearer than algorithm 2.40 is, of course, debatable...)
answered Dec 19 at 4:59
poncho
90.2k2139233
add a comment |
GCM uses $GF(2^{128})$, sometimes called a binary finite field, whose elements are polynomials with coefficients in $GF(2)$ (i.e. zero/one bits under the xor operation).
Binary fields are awkward to implement in software, but are easier to implement (and efficient) in hardware. This is probably the reason why NIST picked it up.
According to this NIST website:
GCM was designed to faciliate high-throughput hardware implementations
answered Dec 19 at 14:12
Conrado
2,4101327
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%2f65979%2fwhy-doesnt-the-gcm-spec-use-a-more-efficient-multiplication-algorithm%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
My question is... why?
There are a number of different algorithms that perform $GF(2^{128})$ multiplication, all with different trade-offs (speed on specific platforms, program size, memory usage, complexity, side channel resistance, etc). NIST doesn't care which one you use, as long as you get the expected result at the end.
As for why NIST decided to put that specific algorithm as an example in the spec, well, I didn't write the spec, so I can't be certain. My guess is that they decided on the goals of simplicity and clarity, and that algorithm was the best they could find that would meet those goals (whether it is actually simpler or clearer than algorithm 2.40 is, of course, debatable...)
answered Dec 19 at 4:59
poncho
90.2k2139233
add a comment |
My question is... why?
There are a number of different algorithms that perform $GF(2^{128})$ multiplication, all with different trade-offs (speed on specific platforms, program size, memory usage, complexity, side channel resistance, etc). NIST doesn't care which one you use, as long as you get the expected result at the end.
As for why NIST decided to put that specific algorithm as an example in the spec, well, I didn't write the spec, so I can't be certain. My guess is that they decided on the goals of simplicity and clarity, and that algorithm was the best they could find that would meet those goals (whether it is actually simpler or clearer than algorithm 2.40 is, of course, debatable...)
answered Dec 19 at 4:59
poncho
90.2k2139233
add a comment |
My question is... why?
There are a number of different algorithms that perform $GF(2^{128})$ multiplication, all with different trade-offs (speed on specific platforms, program size, memory usage, complexity, side channel resistance, etc). NIST doesn't care which one you use, as long as you get the expected result at the end.
As for why NIST decided to put that specific algorithm as an example in the spec, well, I didn't write the spec, so I can't be certain. My guess is that they decided on the goals of simplicity and clarity, and that algorithm was the best they could find that would meet those goals (whether it is actually simpler or clearer than algorithm 2.40 is, of course, debatable...)
answered Dec 19 at 4:59
poncho
90.2k2139233
My question is... why?
There are a number of different algorithms that perform $GF(2^{128})$ multiplication, all with different trade-offs (speed on specific platforms, program size, memory usage, complexity, side channel resistance, etc). NIST doesn't care which one you use, as long as you get the expected result at the end.
As for why NIST decided to put that specific algorithm as an example in the spec, well, I didn't write the spec, so I can't be certain. My guess is that they decided on the goals of simplicity and clarity, and that algorithm was the best they could find that would meet those goals (whether it is actually simpler or clearer than algorithm 2.40 is, of course, debatable...)
answered Dec 19 at 4:59
poncho
90.2k2139233
answered Dec 19 at 4:59
poncho
90.2k2139233
answered Dec 19 at 4:59
poncho
90.2k2139233
answered Dec 19 at 4:59
poncho
90.2k2139233
90.2k2139233
add a comment |
add a comment |
GCM uses $GF(2^{128})$, sometimes called a binary finite field, whose elements are polynomials with coefficients in $GF(2)$ (i.e. zero/one bits under the xor operation).
Binary fields are awkward to implement in software, but are easier to implement (and efficient) in hardware. This is probably the reason why NIST picked it up.
According to this NIST website:
GCM was designed to faciliate high-throughput hardware implementations
answered Dec 19 at 14:12
Conrado
2,4101327
add a comment |
GCM uses $GF(2^{128})$, sometimes called a binary finite field, whose elements are polynomials with coefficients in $GF(2)$ (i.e. zero/one bits under the xor operation).
Binary fields are awkward to implement in software, but are easier to implement (and efficient) in hardware. This is probably the reason why NIST picked it up.
According to this NIST website:
GCM was designed to faciliate high-throughput hardware implementations
answered Dec 19 at 14:12
Conrado
2,4101327
add a comment |
GCM uses $GF(2^{128})$, sometimes called a binary finite field, whose elements are polynomials with coefficients in $GF(2)$ (i.e. zero/one bits under the xor operation).
Binary fields are awkward to implement in software, but are easier to implement (and efficient) in hardware. This is probably the reason why NIST picked it up.
According to this NIST website:
GCM was designed to faciliate high-throughput hardware implementations
answered Dec 19 at 14:12
Conrado
2,4101327
GCM uses $GF(2^{128})$, sometimes called a binary finite field, whose elements are polynomials with coefficients in $GF(2)$ (i.e. zero/one bits under the xor operation).
Binary fields are awkward to implement in software, but are easier to implement (and efficient) in hardware. This is probably the reason why NIST picked it up.
According to this NIST website:
GCM was designed to faciliate high-throughput hardware implementations
answered Dec 19 at 14:12
Conrado
2,4101327
answered Dec 19 at 14:12
Conrado
2,4101327
answered Dec 19 at 14:12
Conrado
2,4101327
answered Dec 19 at 14:12
Conrado
2,4101327
2,4101327
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f65979%2fwhy-doesnt-the-gcm-spec-use-a-more-efficient-multiplication-algorithm%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
