What is the origin of insecure 64-bit nonces in signatures in the Bitcoin chain?
In Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies Joachim Breitner and Nadia Heninger use a lattice based algorithm to recover private keys from signatures in the Bitcoin chain that were produced by insecure signers that generated biased nonces.
One large category of insecure signature that they discovered were 5,863 signatures between July 26, 2014 and June 1st, 2015 that were used in multisignature scripts where the nonces were only 64-bits in size. In the paper when a single key was used multiple times to sign multiple messages (which could be multiple inputs on a single transaction) with a small difference between the nonces their algorithm was able to determine the actual nonces used and the private keys with high probability.
Using a small nonce in multiple signatures is just an especially simple case of having a small difference. Small nonces could also be attacked with simpler brute force search approaches without requiring multiple signatures but the paper's approach was much faster than brute force. Their approach was also able to attack a number of 110 - 160-bit nonces which were used, a range that would have made a brute force search less realistic.
The authors were unaware of the origin of the 64-bit nonces but "hypothesize that this may be a faulty implementation intended for multifactor security, such as a hardware token".
What do we know about the actual origin of these signatures?
security cryptography ecdsa bitcore copay
add a comment |
In Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies Joachim Breitner and Nadia Heninger use a lattice based algorithm to recover private keys from signatures in the Bitcoin chain that were produced by insecure signers that generated biased nonces.
One large category of insecure signature that they discovered were 5,863 signatures between July 26, 2014 and June 1st, 2015 that were used in multisignature scripts where the nonces were only 64-bits in size. In the paper when a single key was used multiple times to sign multiple messages (which could be multiple inputs on a single transaction) with a small difference between the nonces their algorithm was able to determine the actual nonces used and the private keys with high probability.
Using a small nonce in multiple signatures is just an especially simple case of having a small difference. Small nonces could also be attacked with simpler brute force search approaches without requiring multiple signatures but the paper's approach was much faster than brute force. Their approach was also able to attack a number of 110 - 160-bit nonces which were used, a range that would have made a brute force search less realistic.
The authors were unaware of the origin of the 64-bit nonces but "hypothesize that this may be a faulty implementation intended for multifactor security, such as a hardware token".
What do we know about the actual origin of these signatures?
security cryptography ecdsa bitcore copay
add a comment |
In Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies Joachim Breitner and Nadia Heninger use a lattice based algorithm to recover private keys from signatures in the Bitcoin chain that were produced by insecure signers that generated biased nonces.
One large category of insecure signature that they discovered were 5,863 signatures between July 26, 2014 and June 1st, 2015 that were used in multisignature scripts where the nonces were only 64-bits in size. In the paper when a single key was used multiple times to sign multiple messages (which could be multiple inputs on a single transaction) with a small difference between the nonces their algorithm was able to determine the actual nonces used and the private keys with high probability.
Using a small nonce in multiple signatures is just an especially simple case of having a small difference. Small nonces could also be attacked with simpler brute force search approaches without requiring multiple signatures but the paper's approach was much faster than brute force. Their approach was also able to attack a number of 110 - 160-bit nonces which were used, a range that would have made a brute force search less realistic.
The authors were unaware of the origin of the 64-bit nonces but "hypothesize that this may be a faulty implementation intended for multifactor security, such as a hardware token".
What do we know about the actual origin of these signatures?
security cryptography ecdsa bitcore copay
In Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies Joachim Breitner and Nadia Heninger use a lattice based algorithm to recover private keys from signatures in the Bitcoin chain that were produced by insecure signers that generated biased nonces.
One large category of insecure signature that they discovered were 5,863 signatures between July 26, 2014 and June 1st, 2015 that were used in multisignature scripts where the nonces were only 64-bits in size. In the paper when a single key was used multiple times to sign multiple messages (which could be multiple inputs on a single transaction) with a small difference between the nonces their algorithm was able to determine the actual nonces used and the private keys with high probability.
Using a small nonce in multiple signatures is just an especially simple case of having a small difference. Small nonces could also be attacked with simpler brute force search approaches without requiring multiple signatures but the paper's approach was much faster than brute force. Their approach was also able to attack a number of 110 - 160-bit nonces which were used, a range that would have made a brute force search less realistic.
The authors were unaware of the origin of the 64-bit nonces but "hypothesize that this may be a faulty implementation intended for multifactor security, such as a hardware token".
What do we know about the actual origin of these signatures?
security cryptography ecdsa bitcore copay
security cryptography ecdsa bitcore copay
edited 1 hour ago
G. Maxwell
asked 2 hours ago
G. MaxwellG. Maxwell
3,5481630
3,5481630
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Based on the time-frame and my impression of the capabilities of the various groups developing wallet software during that period my initial guess was that the Bitpay copay software might be the source of these signatures. Copay is a multi-signature wallet which was initially released around that time.
As I'm not a javascript developer it took me a bit of effort to dig through the historical dependencies to find the code that was applicable at that time, but I believe my suspicion is likely confirmed:
[If there exists some tool to go grab all of the dependencies of a JS application as of some date that would have been super useful.]
return new bignum(SecureRandom.getRandomBuffer(8));
This code chooses an 8-byte (64-bit) nonce. I'm unclear as to how exactly this mistake came about--sending 32 to a function that took bits as a size argument, for example, would have made sense--but however it happened it wasn't caught in review and appears to have been shipped.
The pull-request that introduced the vulnerability was making the javascript cryptography implementation faster by switching the underlying EC operations to a different library, 'elliptic'. At the time elliptic featured its own signing functions which included RFC6979 deterministic nonce generation. I don't see why bitcore wasn't changed to use the elliptic signing function even with the author of elliptic commenting in support of the PR but since there was pre-existing 'home rolled' signing code it just may not have occurred to anyone to switch to the library routines. There isn't a lot of discussion on the pull-request.
The vulnerability was subsequently fixed but weak signatures continued being created for some time. Because Bitpay's bitcore was promoted as an all purpose Bitcoin library it's possible that other software than copay had adopted it.
I'm unable to find any announcement of or discussion about this vulnerability other than the fix in the repository.
Though I haven't carefully analyzed it, I noticed that prior to switching to elliptic that codebase previously used "bitcoin-js" which--at least in some versions--used a random number generator which was weak due to a review-evading subtle type error so it may well be the case that the error-introducing change simply changed the software from one form of weakness to another.
It's also possible that although bitcore had exactly the right vulnerability introduced at the right time that it was coincidental and the bad signatures found in the paper were created by some other implementation. If so, I think the parallel breakage is still informative.
I think the research and the relevant code make for a fine example of how difficult it is to get these things wrong, how even small errors can result in total security breaks, and that the mere fact that something is open source does not automatically ensure that it has received adequate review.
Nice find! I presume you've informed the authors of the paper?
– Nate Eldredge
1 hour ago
Indeed, I have.
– G. Maxwell
1 hour ago
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "308"
};
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%2fbitcoin.stackexchange.com%2fquestions%2f83559%2fwhat-is-the-origin-of-insecure-64-bit-nonces-in-signatures-in-the-bitcoin-chain%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
Based on the time-frame and my impression of the capabilities of the various groups developing wallet software during that period my initial guess was that the Bitpay copay software might be the source of these signatures. Copay is a multi-signature wallet which was initially released around that time.
As I'm not a javascript developer it took me a bit of effort to dig through the historical dependencies to find the code that was applicable at that time, but I believe my suspicion is likely confirmed:
[If there exists some tool to go grab all of the dependencies of a JS application as of some date that would have been super useful.]
return new bignum(SecureRandom.getRandomBuffer(8));
This code chooses an 8-byte (64-bit) nonce. I'm unclear as to how exactly this mistake came about--sending 32 to a function that took bits as a size argument, for example, would have made sense--but however it happened it wasn't caught in review and appears to have been shipped.
The pull-request that introduced the vulnerability was making the javascript cryptography implementation faster by switching the underlying EC operations to a different library, 'elliptic'. At the time elliptic featured its own signing functions which included RFC6979 deterministic nonce generation. I don't see why bitcore wasn't changed to use the elliptic signing function even with the author of elliptic commenting in support of the PR but since there was pre-existing 'home rolled' signing code it just may not have occurred to anyone to switch to the library routines. There isn't a lot of discussion on the pull-request.
The vulnerability was subsequently fixed but weak signatures continued being created for some time. Because Bitpay's bitcore was promoted as an all purpose Bitcoin library it's possible that other software than copay had adopted it.
I'm unable to find any announcement of or discussion about this vulnerability other than the fix in the repository.
Though I haven't carefully analyzed it, I noticed that prior to switching to elliptic that codebase previously used "bitcoin-js" which--at least in some versions--used a random number generator which was weak due to a review-evading subtle type error so it may well be the case that the error-introducing change simply changed the software from one form of weakness to another.
It's also possible that although bitcore had exactly the right vulnerability introduced at the right time that it was coincidental and the bad signatures found in the paper were created by some other implementation. If so, I think the parallel breakage is still informative.
I think the research and the relevant code make for a fine example of how difficult it is to get these things wrong, how even small errors can result in total security breaks, and that the mere fact that something is open source does not automatically ensure that it has received adequate review.
Nice find! I presume you've informed the authors of the paper?
– Nate Eldredge
1 hour ago
Indeed, I have.
– G. Maxwell
1 hour ago
add a comment |
Based on the time-frame and my impression of the capabilities of the various groups developing wallet software during that period my initial guess was that the Bitpay copay software might be the source of these signatures. Copay is a multi-signature wallet which was initially released around that time.
As I'm not a javascript developer it took me a bit of effort to dig through the historical dependencies to find the code that was applicable at that time, but I believe my suspicion is likely confirmed:
[If there exists some tool to go grab all of the dependencies of a JS application as of some date that would have been super useful.]
return new bignum(SecureRandom.getRandomBuffer(8));
This code chooses an 8-byte (64-bit) nonce. I'm unclear as to how exactly this mistake came about--sending 32 to a function that took bits as a size argument, for example, would have made sense--but however it happened it wasn't caught in review and appears to have been shipped.
The pull-request that introduced the vulnerability was making the javascript cryptography implementation faster by switching the underlying EC operations to a different library, 'elliptic'. At the time elliptic featured its own signing functions which included RFC6979 deterministic nonce generation. I don't see why bitcore wasn't changed to use the elliptic signing function even with the author of elliptic commenting in support of the PR but since there was pre-existing 'home rolled' signing code it just may not have occurred to anyone to switch to the library routines. There isn't a lot of discussion on the pull-request.
The vulnerability was subsequently fixed but weak signatures continued being created for some time. Because Bitpay's bitcore was promoted as an all purpose Bitcoin library it's possible that other software than copay had adopted it.
I'm unable to find any announcement of or discussion about this vulnerability other than the fix in the repository.
Though I haven't carefully analyzed it, I noticed that prior to switching to elliptic that codebase previously used "bitcoin-js" which--at least in some versions--used a random number generator which was weak due to a review-evading subtle type error so it may well be the case that the error-introducing change simply changed the software from one form of weakness to another.
It's also possible that although bitcore had exactly the right vulnerability introduced at the right time that it was coincidental and the bad signatures found in the paper were created by some other implementation. If so, I think the parallel breakage is still informative.
I think the research and the relevant code make for a fine example of how difficult it is to get these things wrong, how even small errors can result in total security breaks, and that the mere fact that something is open source does not automatically ensure that it has received adequate review.
Nice find! I presume you've informed the authors of the paper?
– Nate Eldredge
1 hour ago
Indeed, I have.
– G. Maxwell
1 hour ago
add a comment |
Based on the time-frame and my impression of the capabilities of the various groups developing wallet software during that period my initial guess was that the Bitpay copay software might be the source of these signatures. Copay is a multi-signature wallet which was initially released around that time.
As I'm not a javascript developer it took me a bit of effort to dig through the historical dependencies to find the code that was applicable at that time, but I believe my suspicion is likely confirmed:
[If there exists some tool to go grab all of the dependencies of a JS application as of some date that would have been super useful.]
return new bignum(SecureRandom.getRandomBuffer(8));
This code chooses an 8-byte (64-bit) nonce. I'm unclear as to how exactly this mistake came about--sending 32 to a function that took bits as a size argument, for example, would have made sense--but however it happened it wasn't caught in review and appears to have been shipped.
The pull-request that introduced the vulnerability was making the javascript cryptography implementation faster by switching the underlying EC operations to a different library, 'elliptic'. At the time elliptic featured its own signing functions which included RFC6979 deterministic nonce generation. I don't see why bitcore wasn't changed to use the elliptic signing function even with the author of elliptic commenting in support of the PR but since there was pre-existing 'home rolled' signing code it just may not have occurred to anyone to switch to the library routines. There isn't a lot of discussion on the pull-request.
The vulnerability was subsequently fixed but weak signatures continued being created for some time. Because Bitpay's bitcore was promoted as an all purpose Bitcoin library it's possible that other software than copay had adopted it.
I'm unable to find any announcement of or discussion about this vulnerability other than the fix in the repository.
Though I haven't carefully analyzed it, I noticed that prior to switching to elliptic that codebase previously used "bitcoin-js" which--at least in some versions--used a random number generator which was weak due to a review-evading subtle type error so it may well be the case that the error-introducing change simply changed the software from one form of weakness to another.
It's also possible that although bitcore had exactly the right vulnerability introduced at the right time that it was coincidental and the bad signatures found in the paper were created by some other implementation. If so, I think the parallel breakage is still informative.
I think the research and the relevant code make for a fine example of how difficult it is to get these things wrong, how even small errors can result in total security breaks, and that the mere fact that something is open source does not automatically ensure that it has received adequate review.
Based on the time-frame and my impression of the capabilities of the various groups developing wallet software during that period my initial guess was that the Bitpay copay software might be the source of these signatures. Copay is a multi-signature wallet which was initially released around that time.
As I'm not a javascript developer it took me a bit of effort to dig through the historical dependencies to find the code that was applicable at that time, but I believe my suspicion is likely confirmed:
[If there exists some tool to go grab all of the dependencies of a JS application as of some date that would have been super useful.]
return new bignum(SecureRandom.getRandomBuffer(8));
This code chooses an 8-byte (64-bit) nonce. I'm unclear as to how exactly this mistake came about--sending 32 to a function that took bits as a size argument, for example, would have made sense--but however it happened it wasn't caught in review and appears to have been shipped.
The pull-request that introduced the vulnerability was making the javascript cryptography implementation faster by switching the underlying EC operations to a different library, 'elliptic'. At the time elliptic featured its own signing functions which included RFC6979 deterministic nonce generation. I don't see why bitcore wasn't changed to use the elliptic signing function even with the author of elliptic commenting in support of the PR but since there was pre-existing 'home rolled' signing code it just may not have occurred to anyone to switch to the library routines. There isn't a lot of discussion on the pull-request.
The vulnerability was subsequently fixed but weak signatures continued being created for some time. Because Bitpay's bitcore was promoted as an all purpose Bitcoin library it's possible that other software than copay had adopted it.
I'm unable to find any announcement of or discussion about this vulnerability other than the fix in the repository.
Though I haven't carefully analyzed it, I noticed that prior to switching to elliptic that codebase previously used "bitcoin-js" which--at least in some versions--used a random number generator which was weak due to a review-evading subtle type error so it may well be the case that the error-introducing change simply changed the software from one form of weakness to another.
It's also possible that although bitcore had exactly the right vulnerability introduced at the right time that it was coincidental and the bad signatures found in the paper were created by some other implementation. If so, I think the parallel breakage is still informative.
I think the research and the relevant code make for a fine example of how difficult it is to get these things wrong, how even small errors can result in total security breaks, and that the mere fact that something is open source does not automatically ensure that it has received adequate review.
edited 1 hour ago
answered 2 hours ago
G. MaxwellG. Maxwell
3,5481630
3,5481630
Nice find! I presume you've informed the authors of the paper?
– Nate Eldredge
1 hour ago
Indeed, I have.
– G. Maxwell
1 hour ago
add a comment |
Nice find! I presume you've informed the authors of the paper?
– Nate Eldredge
1 hour ago
Indeed, I have.
– G. Maxwell
1 hour ago
Nice find! I presume you've informed the authors of the paper?
– Nate Eldredge
1 hour ago
Nice find! I presume you've informed the authors of the paper?
– Nate Eldredge
1 hour ago
Indeed, I have.
– G. Maxwell
1 hour ago
Indeed, I have.
– G. Maxwell
1 hour ago
add a comment |
Thanks for contributing an answer to Bitcoin 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.
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%2fbitcoin.stackexchange.com%2fquestions%2f83559%2fwhat-is-the-origin-of-insecure-64-bit-nonces-in-signatures-in-the-bitcoin-chain%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