Exactly what RNG weaknesses endanger (EC)DSA?
RFC 6979 defines deterministic variants of (EC)DSA. It states in introduction
One characteristic of DSA and ECDSA is that they need to produce, for each signature generation, a fresh random value (hereafter designated as $k$). For effective security, $k$ must be chosen randomly and uniformly from a set of modular integers, using a cryptographically secure process. Even slight biases in that process may be turned into attacks on the signature schemes.
How can we characterize what RNG "slight biases" and more generally weaknesses allow attacks on (EC)DSA?
random-number-generator dsa
asked Dec 14 at 5:48
fgrieu
77.7k7162327
add a comment |
RFC 6979 defines deterministic variants of (EC)DSA. It states in introduction
One characteristic of DSA and ECDSA is that they need to produce, for each signature generation, a fresh random value (hereafter designated as $k$). For effective security, $k$ must be chosen randomly and uniformly from a set of modular integers, using a cryptographically secure process. Even slight biases in that process may be turned into attacks on the signature schemes.
How can we characterize what RNG "slight biases" and more generally weaknesses allow attacks on (EC)DSA?
random-number-generator dsa
asked Dec 14 at 5:48
fgrieu
77.7k7162327
1
Does this Q&A answer your question? Also would you prefer the questions to be merged (ie comments and answers would all live under a single question)?
– SEJPM♦
Dec 14 at 14:02
@SEJPM: I had missed this Q&A, and it is definitely very relevant to my question. However the question there is restricted to a particular attack, I'm asking for a characterization of what misguided choices of $k$ allow attack. Yehuda Lindell's answer gives two examples, this Q&A another.
– fgrieu
Dec 14 at 17:49
add a comment |
RFC 6979 defines deterministic variants of (EC)DSA. It states in introduction
One characteristic of DSA and ECDSA is that they need to produce, for each signature generation, a fresh random value (hereafter designated as $k$). For effective security, $k$ must be chosen randomly and uniformly from a set of modular integers, using a cryptographically secure process. Even slight biases in that process may be turned into attacks on the signature schemes.
How can we characterize what RNG "slight biases" and more generally weaknesses allow attacks on (EC)DSA?
random-number-generator dsa
asked Dec 14 at 5:48
fgrieu
77.7k7162327
RFC 6979 defines deterministic variants of (EC)DSA. It states in introduction
One characteristic of DSA and ECDSA is that they need to produce, for each signature generation, a fresh random value (hereafter designated as $k$). For effective security, $k$ must be chosen randomly and uniformly from a set of modular integers, using a cryptographically secure process. Even slight biases in that process may be turned into attacks on the signature schemes.
How can we characterize what RNG "slight biases" and more generally weaknesses allow attacks on (EC)DSA?
random-number-generator dsa
random-number-generator dsa
asked Dec 14 at 5:48
fgrieu
77.7k7162327
asked Dec 14 at 5:48
fgrieu
77.7k7162327
asked Dec 14 at 5:48
fgrieu
77.7k7162327
asked Dec 14 at 5:48
fgrieu
77.7k7162327
asked Dec 14 at 5:48
fgrieu
77.7k7162327
77.7k7162327
1
Does this Q&A answer your question? Also would you prefer the questions to be merged (ie comments and answers would all live under a single question)?
– SEJPM♦
Dec 14 at 14:02
@SEJPM: I had missed this Q&A, and it is definitely very relevant to my question. However the question there is restricted to a particular attack, I'm asking for a characterization of what misguided choices of $k$ allow attack. Yehuda Lindell's answer gives two examples, this Q&A another.
– fgrieu
Dec 14 at 17:49
add a comment |
1
Does this Q&A answer your question? Also would you prefer the questions to be merged (ie comments and answers would all live under a single question)?
– SEJPM♦
Dec 14 at 14:02
@SEJPM: I had missed this Q&A, and it is definitely very relevant to my question. However the question there is restricted to a particular attack, I'm asking for a characterization of what misguided choices of $k$ allow attack. Yehuda Lindell's answer gives two examples, this Q&A another.
– fgrieu
Dec 14 at 17:49
1
1
Does this Q&A answer your question? Also would you prefer the questions to be merged (ie comments and answers would all live under a single question)?
– SEJPM♦
Dec 14 at 14:02
Does this Q&A answer your question? Also would you prefer the questions to be merged (ie comments and answers would all live under a single question)?
– SEJPM♦
Dec 14 at 14:02
@SEJPM: I had missed this Q&A, and it is definitely very relevant to my question. However the question there is restricted to a particular attack, I'm asking for a characterization of what misguided choices of $k$ allow attack. Yehuda Lindell's answer gives two examples, this Q&A another.
– fgrieu
Dec 14 at 17:49
@SEJPM: I had missed this Q&A, and it is definitely very relevant to my question. However the question there is restricted to a particular attack, I'm asking for a characterization of what misguided choices of $k$ allow attack. Yehuda Lindell's answer gives two examples, this Q&A another.
– fgrieu
Dec 14 at 17:49
add a comment |
1 Answer
1
active
oldest
votes
It is well known and trivial to show that if the same random $k$ is used in two different signatures, then the secret key can be extracted. In particular, you have two signatures $(r,s_1)$ and $(r,s_2)$--the $r$ is the same since it is a deterministic function of $k$--where $s_1=k^{-1}cdot(H(m_1)+xcdot r) bmod q$ and $s_2=k^{-1}cdot(H(m_2)+xcdot r) bmod q$. Computing $d = frac{s_1}{s_2} bmod q$ one obtains $d = frac{H(m_1) + rcdot x}{H(m_2) + rcdot x} bmod q$, and so $(d-1)cdot r cdot x = H(m_1) - d cdot H(m_2)$ yielding $x = frac{H(m_1)-dcdot H(m_2)}{(d-1)cdot r} bmod q$.
One could think that this type of thing only happens if the exact same $k$ is used twice. However, if two $k$'s are related in some way, then the same thing can happen. This was shown in an interesting way in the paper Pseudorandom Generation in Cryptographic Algorithms: The DSS Case by Bellare, Goldwasser and Micciancio.
The above paper assumes a strong relation between the nonces. However, the point is that if the same nonce reveals the key, and if knowledge of the nonce reveals the key (trivial to show), then biases in the nonce can reveal information about the key. One would then need more signatures, but this can be done. This is shown in GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures With Single-Bit Nonce Bias.
answered Dec 14 at 7:30
Yehuda Lindell
18.5k3560
Generating the random $k$ using a LCG (as the linked paper considers) is well beyond "slight biases". That's giving up on all true entropy beyond that in the initial state of the LCG, and linking successive values with a simple public transformation, rather than a strong secret one in de-randomized (EC)DSA. I do agree that only good randomness (true or pseudo) should be used, but I find it interesting to investigate "what if" scenarios where it does not. Not all people are as careful as I am with their source of entropy, its monitoring, and post-conditioning...
– fgrieu
Dec 14 at 8:06
1
@fgrieu I have updated the answer to relate to small local biases as well.
– Yehuda Lindell
Dec 14 at 9:02
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%2f64860%2fexactly-what-rng-weaknesses-endanger-ecdsa%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
It is well known and trivial to show that if the same random $k$ is used in two different signatures, then the secret key can be extracted. In particular, you have two signatures $(r,s_1)$ and $(r,s_2)$--the $r$ is the same since it is a deterministic function of $k$--where $s_1=k^{-1}cdot(H(m_1)+xcdot r) bmod q$ and $s_2=k^{-1}cdot(H(m_2)+xcdot r) bmod q$. Computing $d = frac{s_1}{s_2} bmod q$ one obtains $d = frac{H(m_1) + rcdot x}{H(m_2) + rcdot x} bmod q$, and so $(d-1)cdot r cdot x = H(m_1) - d cdot H(m_2)$ yielding $x = frac{H(m_1)-dcdot H(m_2)}{(d-1)cdot r} bmod q$.
One could think that this type of thing only happens if the exact same $k$ is used twice. However, if two $k$'s are related in some way, then the same thing can happen. This was shown in an interesting way in the paper Pseudorandom Generation in Cryptographic Algorithms: The DSS Case by Bellare, Goldwasser and Micciancio.
The above paper assumes a strong relation between the nonces. However, the point is that if the same nonce reveals the key, and if knowledge of the nonce reveals the key (trivial to show), then biases in the nonce can reveal information about the key. One would then need more signatures, but this can be done. This is shown in GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures With Single-Bit Nonce Bias.
answered Dec 14 at 7:30
Yehuda Lindell
18.5k3560
Generating the random $k$ using a LCG (as the linked paper considers) is well beyond "slight biases". That's giving up on all true entropy beyond that in the initial state of the LCG, and linking successive values with a simple public transformation, rather than a strong secret one in de-randomized (EC)DSA. I do agree that only good randomness (true or pseudo) should be used, but I find it interesting to investigate "what if" scenarios where it does not. Not all people are as careful as I am with their source of entropy, its monitoring, and post-conditioning...
– fgrieu
Dec 14 at 8:06
1
@fgrieu I have updated the answer to relate to small local biases as well.
– Yehuda Lindell
Dec 14 at 9:02
add a comment |
It is well known and trivial to show that if the same random $k$ is used in two different signatures, then the secret key can be extracted. In particular, you have two signatures $(r,s_1)$ and $(r,s_2)$--the $r$ is the same since it is a deterministic function of $k$--where $s_1=k^{-1}cdot(H(m_1)+xcdot r) bmod q$ and $s_2=k^{-1}cdot(H(m_2)+xcdot r) bmod q$. Computing $d = frac{s_1}{s_2} bmod q$ one obtains $d = frac{H(m_1) + rcdot x}{H(m_2) + rcdot x} bmod q$, and so $(d-1)cdot r cdot x = H(m_1) - d cdot H(m_2)$ yielding $x = frac{H(m_1)-dcdot H(m_2)}{(d-1)cdot r} bmod q$.
One could think that this type of thing only happens if the exact same $k$ is used twice. However, if two $k$'s are related in some way, then the same thing can happen. This was shown in an interesting way in the paper Pseudorandom Generation in Cryptographic Algorithms: The DSS Case by Bellare, Goldwasser and Micciancio.
The above paper assumes a strong relation between the nonces. However, the point is that if the same nonce reveals the key, and if knowledge of the nonce reveals the key (trivial to show), then biases in the nonce can reveal information about the key. One would then need more signatures, but this can be done. This is shown in GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures With Single-Bit Nonce Bias.
answered Dec 14 at 7:30
Yehuda Lindell
18.5k3560
Generating the random $k$ using a LCG (as the linked paper considers) is well beyond "slight biases". That's giving up on all true entropy beyond that in the initial state of the LCG, and linking successive values with a simple public transformation, rather than a strong secret one in de-randomized (EC)DSA. I do agree that only good randomness (true or pseudo) should be used, but I find it interesting to investigate "what if" scenarios where it does not. Not all people are as careful as I am with their source of entropy, its monitoring, and post-conditioning...
– fgrieu
Dec 14 at 8:06
1
@fgrieu I have updated the answer to relate to small local biases as well.
– Yehuda Lindell
Dec 14 at 9:02
add a comment |
It is well known and trivial to show that if the same random $k$ is used in two different signatures, then the secret key can be extracted. In particular, you have two signatures $(r,s_1)$ and $(r,s_2)$--the $r$ is the same since it is a deterministic function of $k$--where $s_1=k^{-1}cdot(H(m_1)+xcdot r) bmod q$ and $s_2=k^{-1}cdot(H(m_2)+xcdot r) bmod q$. Computing $d = frac{s_1}{s_2} bmod q$ one obtains $d = frac{H(m_1) + rcdot x}{H(m_2) + rcdot x} bmod q$, and so $(d-1)cdot r cdot x = H(m_1) - d cdot H(m_2)$ yielding $x = frac{H(m_1)-dcdot H(m_2)}{(d-1)cdot r} bmod q$.
One could think that this type of thing only happens if the exact same $k$ is used twice. However, if two $k$'s are related in some way, then the same thing can happen. This was shown in an interesting way in the paper Pseudorandom Generation in Cryptographic Algorithms: The DSS Case by Bellare, Goldwasser and Micciancio.
The above paper assumes a strong relation between the nonces. However, the point is that if the same nonce reveals the key, and if knowledge of the nonce reveals the key (trivial to show), then biases in the nonce can reveal information about the key. One would then need more signatures, but this can be done. This is shown in GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures With Single-Bit Nonce Bias.
answered Dec 14 at 7:30
Yehuda Lindell
18.5k3560
It is well known and trivial to show that if the same random $k$ is used in two different signatures, then the secret key can be extracted. In particular, you have two signatures $(r,s_1)$ and $(r,s_2)$--the $r$ is the same since it is a deterministic function of $k$--where $s_1=k^{-1}cdot(H(m_1)+xcdot r) bmod q$ and $s_2=k^{-1}cdot(H(m_2)+xcdot r) bmod q$. Computing $d = frac{s_1}{s_2} bmod q$ one obtains $d = frac{H(m_1) + rcdot x}{H(m_2) + rcdot x} bmod q$, and so $(d-1)cdot r cdot x = H(m_1) - d cdot H(m_2)$ yielding $x = frac{H(m_1)-dcdot H(m_2)}{(d-1)cdot r} bmod q$.
One could think that this type of thing only happens if the exact same $k$ is used twice. However, if two $k$'s are related in some way, then the same thing can happen. This was shown in an interesting way in the paper Pseudorandom Generation in Cryptographic Algorithms: The DSS Case by Bellare, Goldwasser and Micciancio.
The above paper assumes a strong relation between the nonces. However, the point is that if the same nonce reveals the key, and if knowledge of the nonce reveals the key (trivial to show), then biases in the nonce can reveal information about the key. One would then need more signatures, but this can be done. This is shown in GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures With Single-Bit Nonce Bias.
answered Dec 14 at 7:30
Yehuda Lindell
18.5k3560
edited Dec 14 at 9:02
answered Dec 14 at 7:30
Yehuda Lindell
18.5k3560
answered Dec 14 at 7:30
Yehuda Lindell
18.5k3560
answered Dec 14 at 7:30
Yehuda Lindell
18.5k3560
18.5k3560
Generating the random $k$ using a LCG (as the linked paper considers) is well beyond "slight biases". That's giving up on all true entropy beyond that in the initial state of the LCG, and linking successive values with a simple public transformation, rather than a strong secret one in de-randomized (EC)DSA. I do agree that only good randomness (true or pseudo) should be used, but I find it interesting to investigate "what if" scenarios where it does not. Not all people are as careful as I am with their source of entropy, its monitoring, and post-conditioning...
– fgrieu
Dec 14 at 8:06
1
@fgrieu I have updated the answer to relate to small local biases as well.
– Yehuda Lindell
Dec 14 at 9:02
add a comment |
Generating the random $k$ using a LCG (as the linked paper considers) is well beyond "slight biases". That's giving up on all true entropy beyond that in the initial state of the LCG, and linking successive values with a simple public transformation, rather than a strong secret one in de-randomized (EC)DSA. I do agree that only good randomness (true or pseudo) should be used, but I find it interesting to investigate "what if" scenarios where it does not. Not all people are as careful as I am with their source of entropy, its monitoring, and post-conditioning...
– fgrieu
Dec 14 at 8:06
1
@fgrieu I have updated the answer to relate to small local biases as well.
– Yehuda Lindell
Dec 14 at 9:02
Generating the random $k$ using a LCG (as the linked paper considers) is well beyond "slight biases". That's giving up on all true entropy beyond that in the initial state of the LCG, and linking successive values with a simple public transformation, rather than a strong secret one in de-randomized (EC)DSA. I do agree that only good randomness (true or pseudo) should be used, but I find it interesting to investigate "what if" scenarios where it does not. Not all people are as careful as I am with their source of entropy, its monitoring, and post-conditioning...
– fgrieu
Dec 14 at 8:06
Generating the random $k$ using a LCG (as the linked paper considers) is well beyond "slight biases". That's giving up on all true entropy beyond that in the initial state of the LCG, and linking successive values with a simple public transformation, rather than a strong secret one in de-randomized (EC)DSA. I do agree that only good randomness (true or pseudo) should be used, but I find it interesting to investigate "what if" scenarios where it does not. Not all people are as careful as I am with their source of entropy, its monitoring, and post-conditioning...
– fgrieu
Dec 14 at 8:06
1
1
@fgrieu I have updated the answer to relate to small local biases as well.
– Yehuda Lindell
Dec 14 at 9:02
@fgrieu I have updated the answer to relate to small local biases as well.
– Yehuda Lindell
Dec 14 at 9:02
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%2f64860%2fexactly-what-rng-weaknesses-endanger-ecdsa%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
Does this Q&A answer your question? Also would you prefer the questions to be merged (ie comments and answers would all live under a single question)?
– SEJPM♦
Dec 14 at 14:02
@SEJPM: I had missed this Q&A, and it is definitely very relevant to my question. However the question there is restricted to a particular attack, I'm asking for a characterization of what misguided choices of $k$ allow attack. Yehuda Lindell's answer gives two examples, this Q&A another.
– fgrieu
Dec 14 at 17:49