Mixing
If someone wanted to pretend to be Satoshi by posting a fake signature to defraud people how could they?
up vote
57
down vote
favorite
If a random fraudster wanted to post a bunch of mysterious ECDSA signatures that the public would believe came from Bitcoin's creator, in order to disrupt the Bitcoin market, extract money from people, or otherwise convince people to listen to them. How could they do that?
ecdsa
asked 2 days ago
G. Maxwell
2,620626
add a comment |
up vote
57
down vote
favorite
If a random fraudster wanted to post a bunch of mysterious ECDSA signatures that the public would believe came from Bitcoin's creator, in order to disrupt the Bitcoin market, extract money from people, or otherwise convince people to listen to them. How could they do that?
ecdsa
asked 2 days ago
G. Maxwell
2,620626
add a comment |
up vote
57
down vote
favorite
up vote
57
down vote
favorite
If a random fraudster wanted to post a bunch of mysterious ECDSA signatures that the public would believe came from Bitcoin's creator, in order to disrupt the Bitcoin market, extract money from people, or otherwise convince people to listen to them. How could they do that?
ecdsa
asked 2 days ago
G. Maxwell
2,620626
If a random fraudster wanted to post a bunch of mysterious ECDSA signatures that the public would believe came from Bitcoin's creator, in order to disrupt the Bitcoin market, extract money from people, or otherwise convince people to listen to them. How could they do that?
ecdsa
ecdsa
asked 2 days ago
G. Maxwell
2,620626
asked 2 days ago
G. Maxwell
2,620626
asked 2 days ago
G. Maxwell
2,620626
asked 2 days ago
G. Maxwell
2,620626
asked 2 days ago
G. Maxwell
2,620626
2,620626
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
57
down vote
accepted
Unfortunately, given the public's limited of understanding of cryptography this is apparently an easy fraud to pull off.
The key trick is that non-technical people are prone to believe things that just sound jargony enough and that technical people tend to think they know a lot more than they actually do-- and so they're easily sent off into the weeds.
In cryptosystems the details are more important than you could possibly imagine. So all you have to do is make a forgery that works for a slightly modified cryptosystem and then lots of people who THINK they understand how ECDSA works will rush out to claim the result holds.
Most modifications that you can think of are sufficient to make the scheme insecure.
So, for example, a couple years ago Craig Wright claimed to 'prove he was Satoshi' by simply copying some pre-existing signatures out of the blockchain and posting somewhat obfuscated instructions on verifying them. It was figured out pretty quickly, but still managed to fool a lot of people-- they were too caught up in the mumbojumbo to think of the obvious. The "modification" in this case was that the message the scammer was claiming to sign just has no relationship to the message that was actually signed.
More recently it appears that someone attempted something similar again, but this time with 'signatures' that weren't from the blockchain... resulting in 'verification' from the developers of some BCH clients to an engineer at RedHat. But it turns out that, again, that the attempt was fake and people's partial but incomplete understanding of crypto burned them.
As Bitcoin developer Pieter Wuille notes "ECDSA signatures where the message isn't a hash and chosen by the "signer" are insecure."-- this time the scammer just published 'hash', r, s tuples. The hash part of ECDSA is integral to the algorithm. If the verifier doesn't run the hash themselves, the security properties of ECDSA don't hold and an existential forgery becomes trivial.
[This same vulnerability was baked into the original OP_DSV opcode in BCH-- it originally didn't hash the incoming data but left that up to the user-- but I reported it and they appear to have fixed it before deploying it.]
If the verifier doesn't perform the hash himself but just accepts a value given by the signer, he becomes susceptible to the following: Given public key P, pick random nonzero values a and b. Compute R=aG+bP. Now (R.x, R.x/b) is a valid signature under key P for "message-hash" (R.x*a/b).
This doesn't compromise the security of real ECDSA because you cannot find a message that hashes to a chosen (R.x*a/b) value.
People should be wary of obfuscated or overly technical 'proofs', -- things that look "like" a secure system but for some reason have people verifying it working with raw numbers or code. Well designed cryptographic software put in a lot of effort to avoid users being fooled by stunts like this. This stuff is tricky and anyone could be confused into accepting a false proof if they were convinced to effectively implement a bespoke cryptosystem themselves. A cryptosystem is not secure simply because you, personally, don't see how to break it.
Here an an example Sage script to produce forgeries that will fool someone that accepts an ECDSA 'signature' without hashing the message themselves. It works with any EC key, including one that the forger hasn't seen a signature from before.
F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
C = EllipticCurve ([F (0), F (7)])
G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
N = FiniteField (C.order())
P = P=-C.lift_x(0x11db93e1dcdb8a016b49840f8c53bc1eb68a382e97b1482ecad7b148a6909a5c) # block 9 coinbase payout key.
def forge(c, a=-1): # Create a forged 'ECDSA' (hashless) signature
# set a to something other than -1 to be less obvious
a = N(a)
R = c*G + int(a)*P
s = N(int(R.xy()[0]))/a
m = N(c)*N(int(R.xy()[0]))/a
print 'hash1 = %d'%m
print 'r1 = %d'%(int(R.xy()[0]))
print 's1 = %d'%s
for c in range(1,10):
forge(c)
This code produces fake forgeries of the sort that was used to trick people recently.
hash1 = 25292222169426362969760742810503101183086560848420849767135309758511048414376
r1 = 61518691557461623794232686914770715342344584505217074682876722883231084339701
s1 = 54273397679854571629338298093917192510492979773857829699728440258287077154636
edited 5 hours ago
Murch♦
34.2k27111321
answered 2 days ago
G. Maxwell
2,620626
14
That's perfectly allowed on this site. Good questions and good answers are always welcome.
– Jannes
yesterday
6
@Jerry Gao: G. Maxwell does not claim that you can fake signatures. He is explaining how someone could be tricked into thinking something was a real signature while it isn't
– Pieter Wuille
yesterday
6
@HenningMakholm: Recently a well-known figure in Bitcoin space has released ECDSA signatures for an unknown message claiming that he'd reveal the message later. They were apparently expecting that people would assume that the signature would convince others of owning the corresponding private key.
– Murch♦
yesterday
3
@HenningMakholm If you think about it, Digital signatures are kind of misnamed. A traditional signature doesn't do anything to bind the document it's written on, besides being written on it. A digital signature works a little more like a wax seal. :) In any case, for some reason an awful lot of people seem to get convinced by the 'signature of something' stated in proximity-- maybe following from a borrowed intuition of traditional signatures.
– G. Maxwell
yesterday
3
@pinhead in no way does OP say that. Belittling accurate, truthful and technical posts by portraying them as offensive is a very common tactic in this space. Don't fall for that. People that don't know something (let alone an "entire community") are in no way being called stupid.
– Jannes
yesterday
|
show 8 more comments
up vote
-5
down vote
The signature verification is the counterpart of the signature computation. Its purpose is to verify the message’s authenticity using the authenticator’s public key. Using the same secure hash algorithm as in the signature step, the message digest signed by the authenticator is computed which, together with the public key Q(x,y) and the digital signature components r and s, leads to the result. Figure 4 illustrates the process.
Signature verification process.
Figure 4. Signature verification process.
Equation 4 shows the individual steps of the verification process. Inputs are the message digest h(m), the public key Q(x,y), the signature components r and s, and the base point G(x,y):
w = 1/s mod n
u1 = (h(m) * w) mod n
u2 = (r * w) mod n
(x2, y2) = (u1 × G(x, y) + u2 × Q(x, y)) mod n (Eq. 4)
The verification is successful (“passes”), if x2 is equal to r, thus confirming that the signature was indeed computed using the private key.
If the verifier doesn't perform the hash himself but just accepts a
value given by the signer, Given public key Q, pick random nonzero
values a and b. Compute R=aG+bQ. Now (R.x, R.x/b) is a valid signature
under key Q for "message-hash" (R.x*a/b).
signature [r,s]
where: r = R.x s = R.x/b
w = 1/s
u1 = h(R.x*a/b) / (R.x/b) mod n
u2 = R.x / (R.x/b) mod n
if h(R.x*a/b) == R.x*a/b
then
u1 == (R.x*a/b) / (R.x/b) == a
else
u1 !== a
this means for u1 == a only valid when Hash(m) == m
since this case can be easily verified. so it's impossible to fake signature.
people who run the code above, please check you Prime number P is correct.
answered yesterday
Jerry Gao
1312
New contributor
Jerry Gao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
8
Your diagram shows exactly the kind of vulnerable thinking that others have been tricked by: It shows the verification process as taking an externally produced 'hash' as input. If someone accepts a 'hash' that isn't a hash, they can be given a forged signature. The hash is integral to ECDSA and cannot be omitted.
– G. Maxwell
yesterday
4
I've downvoted this answer, because it is false and misleading. A cryptographic signature's purpose is to authenticate a message. It is trivial to forge a signature from the public key that doesn't commit to a specific hash, i.e. where the hash is picked to fit the signature. It is impossible to distinguish between a forged signature and a signature for which the original message hasn't been provided.
– Murch♦
yesterday
4
This answer is intentionally deceptive, as others have pointed out, if m is not a hash calculated by the verifier, the system is not validating anything. No competent and non-malicious system uses ECDSA as described in the parent.
– Anonymous
yesterday
I've removed several unrelated comments. Please focus on the post here.
– Murch♦
yesterday
guys, OP_DSV opcode can still be attacked by H(m) == m !
– Jerry Gao
7 hours ago
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
57
down vote
accepted
Unfortunately, given the public's limited of understanding of cryptography this is apparently an easy fraud to pull off.
The key trick is that non-technical people are prone to believe things that just sound jargony enough and that technical people tend to think they know a lot more than they actually do-- and so they're easily sent off into the weeds.
In cryptosystems the details are more important than you could possibly imagine. So all you have to do is make a forgery that works for a slightly modified cryptosystem and then lots of people who THINK they understand how ECDSA works will rush out to claim the result holds.
Most modifications that you can think of are sufficient to make the scheme insecure.
So, for example, a couple years ago Craig Wright claimed to 'prove he was Satoshi' by simply copying some pre-existing signatures out of the blockchain and posting somewhat obfuscated instructions on verifying them. It was figured out pretty quickly, but still managed to fool a lot of people-- they were too caught up in the mumbojumbo to think of the obvious. The "modification" in this case was that the message the scammer was claiming to sign just has no relationship to the message that was actually signed.
More recently it appears that someone attempted something similar again, but this time with 'signatures' that weren't from the blockchain... resulting in 'verification' from the developers of some BCH clients to an engineer at RedHat. But it turns out that, again, that the attempt was fake and people's partial but incomplete understanding of crypto burned them.
As Bitcoin developer Pieter Wuille notes "ECDSA signatures where the message isn't a hash and chosen by the "signer" are insecure."-- this time the scammer just published 'hash', r, s tuples. The hash part of ECDSA is integral to the algorithm. If the verifier doesn't run the hash themselves, the security properties of ECDSA don't hold and an existential forgery becomes trivial.
[This same vulnerability was baked into the original OP_DSV opcode in BCH-- it originally didn't hash the incoming data but left that up to the user-- but I reported it and they appear to have fixed it before deploying it.]
If the verifier doesn't perform the hash himself but just accepts a value given by the signer, he becomes susceptible to the following: Given public key P, pick random nonzero values a and b. Compute R=aG+bP. Now (R.x, R.x/b) is a valid signature under key P for "message-hash" (R.x*a/b).
This doesn't compromise the security of real ECDSA because you cannot find a message that hashes to a chosen (R.x*a/b) value.
People should be wary of obfuscated or overly technical 'proofs', -- things that look "like" a secure system but for some reason have people verifying it working with raw numbers or code. Well designed cryptographic software put in a lot of effort to avoid users being fooled by stunts like this. This stuff is tricky and anyone could be confused into accepting a false proof if they were convinced to effectively implement a bespoke cryptosystem themselves. A cryptosystem is not secure simply because you, personally, don't see how to break it.
Here an an example Sage script to produce forgeries that will fool someone that accepts an ECDSA 'signature' without hashing the message themselves. It works with any EC key, including one that the forger hasn't seen a signature from before.
F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
C = EllipticCurve ([F (0), F (7)])
G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
N = FiniteField (C.order())
P = P=-C.lift_x(0x11db93e1dcdb8a016b49840f8c53bc1eb68a382e97b1482ecad7b148a6909a5c) # block 9 coinbase payout key.
def forge(c, a=-1): # Create a forged 'ECDSA' (hashless) signature
# set a to something other than -1 to be less obvious
a = N(a)
R = c*G + int(a)*P
s = N(int(R.xy()[0]))/a
m = N(c)*N(int(R.xy()[0]))/a
print 'hash1 = %d'%m
print 'r1 = %d'%(int(R.xy()[0]))
print 's1 = %d'%s
for c in range(1,10):
forge(c)
This code produces fake forgeries of the sort that was used to trick people recently.
hash1 = 25292222169426362969760742810503101183086560848420849767135309758511048414376
r1 = 61518691557461623794232686914770715342344584505217074682876722883231084339701
s1 = 54273397679854571629338298093917192510492979773857829699728440258287077154636
edited 5 hours ago
Murch♦
34.2k27111321
answered 2 days ago
G. Maxwell
2,620626
14
That's perfectly allowed on this site. Good questions and good answers are always welcome.
– Jannes
yesterday
6
@Jerry Gao: G. Maxwell does not claim that you can fake signatures. He is explaining how someone could be tricked into thinking something was a real signature while it isn't
– Pieter Wuille
yesterday
6
@HenningMakholm: Recently a well-known figure in Bitcoin space has released ECDSA signatures for an unknown message claiming that he'd reveal the message later. They were apparently expecting that people would assume that the signature would convince others of owning the corresponding private key.
– Murch♦
yesterday
3
@HenningMakholm If you think about it, Digital signatures are kind of misnamed. A traditional signature doesn't do anything to bind the document it's written on, besides being written on it. A digital signature works a little more like a wax seal. :) In any case, for some reason an awful lot of people seem to get convinced by the 'signature of something' stated in proximity-- maybe following from a borrowed intuition of traditional signatures.
– G. Maxwell
yesterday
3
@pinhead in no way does OP say that. Belittling accurate, truthful and technical posts by portraying them as offensive is a very common tactic in this space. Don't fall for that. People that don't know something (let alone an "entire community") are in no way being called stupid.
– Jannes
yesterday
|
show 8 more comments
up vote
57
down vote
accepted
Unfortunately, given the public's limited of understanding of cryptography this is apparently an easy fraud to pull off.
The key trick is that non-technical people are prone to believe things that just sound jargony enough and that technical people tend to think they know a lot more than they actually do-- and so they're easily sent off into the weeds.
In cryptosystems the details are more important than you could possibly imagine. So all you have to do is make a forgery that works for a slightly modified cryptosystem and then lots of people who THINK they understand how ECDSA works will rush out to claim the result holds.
Most modifications that you can think of are sufficient to make the scheme insecure.
So, for example, a couple years ago Craig Wright claimed to 'prove he was Satoshi' by simply copying some pre-existing signatures out of the blockchain and posting somewhat obfuscated instructions on verifying them. It was figured out pretty quickly, but still managed to fool a lot of people-- they were too caught up in the mumbojumbo to think of the obvious. The "modification" in this case was that the message the scammer was claiming to sign just has no relationship to the message that was actually signed.
More recently it appears that someone attempted something similar again, but this time with 'signatures' that weren't from the blockchain... resulting in 'verification' from the developers of some BCH clients to an engineer at RedHat. But it turns out that, again, that the attempt was fake and people's partial but incomplete understanding of crypto burned them.
As Bitcoin developer Pieter Wuille notes "ECDSA signatures where the message isn't a hash and chosen by the "signer" are insecure."-- this time the scammer just published 'hash', r, s tuples. The hash part of ECDSA is integral to the algorithm. If the verifier doesn't run the hash themselves, the security properties of ECDSA don't hold and an existential forgery becomes trivial.
[This same vulnerability was baked into the original OP_DSV opcode in BCH-- it originally didn't hash the incoming data but left that up to the user-- but I reported it and they appear to have fixed it before deploying it.]
If the verifier doesn't perform the hash himself but just accepts a value given by the signer, he becomes susceptible to the following: Given public key P, pick random nonzero values a and b. Compute R=aG+bP. Now (R.x, R.x/b) is a valid signature under key P for "message-hash" (R.x*a/b).
This doesn't compromise the security of real ECDSA because you cannot find a message that hashes to a chosen (R.x*a/b) value.
People should be wary of obfuscated or overly technical 'proofs', -- things that look "like" a secure system but for some reason have people verifying it working with raw numbers or code. Well designed cryptographic software put in a lot of effort to avoid users being fooled by stunts like this. This stuff is tricky and anyone could be confused into accepting a false proof if they were convinced to effectively implement a bespoke cryptosystem themselves. A cryptosystem is not secure simply because you, personally, don't see how to break it.
Here an an example Sage script to produce forgeries that will fool someone that accepts an ECDSA 'signature' without hashing the message themselves. It works with any EC key, including one that the forger hasn't seen a signature from before.
F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
C = EllipticCurve ([F (0), F (7)])
G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
N = FiniteField (C.order())
P = P=-C.lift_x(0x11db93e1dcdb8a016b49840f8c53bc1eb68a382e97b1482ecad7b148a6909a5c) # block 9 coinbase payout key.
def forge(c, a=-1): # Create a forged 'ECDSA' (hashless) signature
# set a to something other than -1 to be less obvious
a = N(a)
R = c*G + int(a)*P
s = N(int(R.xy()[0]))/a
m = N(c)*N(int(R.xy()[0]))/a
print 'hash1 = %d'%m
print 'r1 = %d'%(int(R.xy()[0]))
print 's1 = %d'%s
for c in range(1,10):
forge(c)
This code produces fake forgeries of the sort that was used to trick people recently.
hash1 = 25292222169426362969760742810503101183086560848420849767135309758511048414376
r1 = 61518691557461623794232686914770715342344584505217074682876722883231084339701
s1 = 54273397679854571629338298093917192510492979773857829699728440258287077154636
edited 5 hours ago
Murch♦
34.2k27111321
answered 2 days ago
G. Maxwell
2,620626
14
That's perfectly allowed on this site. Good questions and good answers are always welcome.
– Jannes
yesterday
6
@Jerry Gao: G. Maxwell does not claim that you can fake signatures. He is explaining how someone could be tricked into thinking something was a real signature while it isn't
– Pieter Wuille
yesterday
6
@HenningMakholm: Recently a well-known figure in Bitcoin space has released ECDSA signatures for an unknown message claiming that he'd reveal the message later. They were apparently expecting that people would assume that the signature would convince others of owning the corresponding private key.
– Murch♦
yesterday
3
@HenningMakholm If you think about it, Digital signatures are kind of misnamed. A traditional signature doesn't do anything to bind the document it's written on, besides being written on it. A digital signature works a little more like a wax seal. :) In any case, for some reason an awful lot of people seem to get convinced by the 'signature of something' stated in proximity-- maybe following from a borrowed intuition of traditional signatures.
– G. Maxwell
yesterday
3
@pinhead in no way does OP say that. Belittling accurate, truthful and technical posts by portraying them as offensive is a very common tactic in this space. Don't fall for that. People that don't know something (let alone an "entire community") are in no way being called stupid.
– Jannes
yesterday
|
show 8 more comments
up vote
57
down vote
accepted
up vote
57
down vote
accepted
Unfortunately, given the public's limited of understanding of cryptography this is apparently an easy fraud to pull off.
The key trick is that non-technical people are prone to believe things that just sound jargony enough and that technical people tend to think they know a lot more than they actually do-- and so they're easily sent off into the weeds.
In cryptosystems the details are more important than you could possibly imagine. So all you have to do is make a forgery that works for a slightly modified cryptosystem and then lots of people who THINK they understand how ECDSA works will rush out to claim the result holds.
Most modifications that you can think of are sufficient to make the scheme insecure.
So, for example, a couple years ago Craig Wright claimed to 'prove he was Satoshi' by simply copying some pre-existing signatures out of the blockchain and posting somewhat obfuscated instructions on verifying them. It was figured out pretty quickly, but still managed to fool a lot of people-- they were too caught up in the mumbojumbo to think of the obvious. The "modification" in this case was that the message the scammer was claiming to sign just has no relationship to the message that was actually signed.
More recently it appears that someone attempted something similar again, but this time with 'signatures' that weren't from the blockchain... resulting in 'verification' from the developers of some BCH clients to an engineer at RedHat. But it turns out that, again, that the attempt was fake and people's partial but incomplete understanding of crypto burned them.
As Bitcoin developer Pieter Wuille notes "ECDSA signatures where the message isn't a hash and chosen by the "signer" are insecure."-- this time the scammer just published 'hash', r, s tuples. The hash part of ECDSA is integral to the algorithm. If the verifier doesn't run the hash themselves, the security properties of ECDSA don't hold and an existential forgery becomes trivial.
[This same vulnerability was baked into the original OP_DSV opcode in BCH-- it originally didn't hash the incoming data but left that up to the user-- but I reported it and they appear to have fixed it before deploying it.]
If the verifier doesn't perform the hash himself but just accepts a value given by the signer, he becomes susceptible to the following: Given public key P, pick random nonzero values a and b. Compute R=aG+bP. Now (R.x, R.x/b) is a valid signature under key P for "message-hash" (R.x*a/b).
This doesn't compromise the security of real ECDSA because you cannot find a message that hashes to a chosen (R.x*a/b) value.
People should be wary of obfuscated or overly technical 'proofs', -- things that look "like" a secure system but for some reason have people verifying it working with raw numbers or code. Well designed cryptographic software put in a lot of effort to avoid users being fooled by stunts like this. This stuff is tricky and anyone could be confused into accepting a false proof if they were convinced to effectively implement a bespoke cryptosystem themselves. A cryptosystem is not secure simply because you, personally, don't see how to break it.
Here an an example Sage script to produce forgeries that will fool someone that accepts an ECDSA 'signature' without hashing the message themselves. It works with any EC key, including one that the forger hasn't seen a signature from before.
F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
C = EllipticCurve ([F (0), F (7)])
G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
N = FiniteField (C.order())
P = P=-C.lift_x(0x11db93e1dcdb8a016b49840f8c53bc1eb68a382e97b1482ecad7b148a6909a5c) # block 9 coinbase payout key.
def forge(c, a=-1): # Create a forged 'ECDSA' (hashless) signature
# set a to something other than -1 to be less obvious
a = N(a)
R = c*G + int(a)*P
s = N(int(R.xy()[0]))/a
m = N(c)*N(int(R.xy()[0]))/a
print 'hash1 = %d'%m
print 'r1 = %d'%(int(R.xy()[0]))
print 's1 = %d'%s
for c in range(1,10):
forge(c)
This code produces fake forgeries of the sort that was used to trick people recently.
hash1 = 25292222169426362969760742810503101183086560848420849767135309758511048414376
r1 = 61518691557461623794232686914770715342344584505217074682876722883231084339701
s1 = 54273397679854571629338298093917192510492979773857829699728440258287077154636
edited 5 hours ago
Murch♦
34.2k27111321
answered 2 days ago
G. Maxwell
2,620626
Unfortunately, given the public's limited of understanding of cryptography this is apparently an easy fraud to pull off.
The key trick is that non-technical people are prone to believe things that just sound jargony enough and that technical people tend to think they know a lot more than they actually do-- and so they're easily sent off into the weeds.
In cryptosystems the details are more important than you could possibly imagine. So all you have to do is make a forgery that works for a slightly modified cryptosystem and then lots of people who THINK they understand how ECDSA works will rush out to claim the result holds.
Most modifications that you can think of are sufficient to make the scheme insecure.
So, for example, a couple years ago Craig Wright claimed to 'prove he was Satoshi' by simply copying some pre-existing signatures out of the blockchain and posting somewhat obfuscated instructions on verifying them. It was figured out pretty quickly, but still managed to fool a lot of people-- they were too caught up in the mumbojumbo to think of the obvious. The "modification" in this case was that the message the scammer was claiming to sign just has no relationship to the message that was actually signed.
More recently it appears that someone attempted something similar again, but this time with 'signatures' that weren't from the blockchain... resulting in 'verification' from the developers of some BCH clients to an engineer at RedHat. But it turns out that, again, that the attempt was fake and people's partial but incomplete understanding of crypto burned them.
As Bitcoin developer Pieter Wuille notes "ECDSA signatures where the message isn't a hash and chosen by the "signer" are insecure."-- this time the scammer just published 'hash', r, s tuples. The hash part of ECDSA is integral to the algorithm. If the verifier doesn't run the hash themselves, the security properties of ECDSA don't hold and an existential forgery becomes trivial.
[This same vulnerability was baked into the original OP_DSV opcode in BCH-- it originally didn't hash the incoming data but left that up to the user-- but I reported it and they appear to have fixed it before deploying it.]
If the verifier doesn't perform the hash himself but just accepts a value given by the signer, he becomes susceptible to the following: Given public key P, pick random nonzero values a and b. Compute R=aG+bP. Now (R.x, R.x/b) is a valid signature under key P for "message-hash" (R.x*a/b).
This doesn't compromise the security of real ECDSA because you cannot find a message that hashes to a chosen (R.x*a/b) value.
People should be wary of obfuscated or overly technical 'proofs', -- things that look "like" a secure system but for some reason have people verifying it working with raw numbers or code. Well designed cryptographic software put in a lot of effort to avoid users being fooled by stunts like this. This stuff is tricky and anyone could be confused into accepting a false proof if they were convinced to effectively implement a bespoke cryptosystem themselves. A cryptosystem is not secure simply because you, personally, don't see how to break it.
Here an an example Sage script to produce forgeries that will fool someone that accepts an ECDSA 'signature' without hashing the message themselves. It works with any EC key, including one that the forger hasn't seen a signature from before.
F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
C = EllipticCurve ([F (0), F (7)])
G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
N = FiniteField (C.order())
P = P=-C.lift_x(0x11db93e1dcdb8a016b49840f8c53bc1eb68a382e97b1482ecad7b148a6909a5c) # block 9 coinbase payout key.
def forge(c, a=-1): # Create a forged 'ECDSA' (hashless) signature
# set a to something other than -1 to be less obvious
a = N(a)
R = c*G + int(a)*P
s = N(int(R.xy()[0]))/a
m = N(c)*N(int(R.xy()[0]))/a
print 'hash1 = %d'%m
print 'r1 = %d'%(int(R.xy()[0]))
print 's1 = %d'%s
for c in range(1,10):
forge(c)
This code produces fake forgeries of the sort that was used to trick people recently.
hash1 = 25292222169426362969760742810503101183086560848420849767135309758511048414376
r1 = 61518691557461623794232686914770715342344584505217074682876722883231084339701
s1 = 54273397679854571629338298093917192510492979773857829699728440258287077154636
edited 5 hours ago
Murch♦
34.2k27111321
answered 2 days ago
G. Maxwell
2,620626
edited 5 hours ago
Murch♦
34.2k27111321
edited 5 hours ago
Murch♦
34.2k27111321
edited 5 hours ago
Murch♦
34.2k27111321
34.2k27111321
answered 2 days ago
G. Maxwell
2,620626
answered 2 days ago
G. Maxwell
2,620626
answered 2 days ago
G. Maxwell
2,620626
2,620626
14
That's perfectly allowed on this site. Good questions and good answers are always welcome.
– Jannes
yesterday
6
@Jerry Gao: G. Maxwell does not claim that you can fake signatures. He is explaining how someone could be tricked into thinking something was a real signature while it isn't
– Pieter Wuille
yesterday
6
@HenningMakholm: Recently a well-known figure in Bitcoin space has released ECDSA signatures for an unknown message claiming that he'd reveal the message later. They were apparently expecting that people would assume that the signature would convince others of owning the corresponding private key.
– Murch♦
yesterday
3
@HenningMakholm If you think about it, Digital signatures are kind of misnamed. A traditional signature doesn't do anything to bind the document it's written on, besides being written on it. A digital signature works a little more like a wax seal. :) In any case, for some reason an awful lot of people seem to get convinced by the 'signature of something' stated in proximity-- maybe following from a borrowed intuition of traditional signatures.
– G. Maxwell
yesterday
3
@pinhead in no way does OP say that. Belittling accurate, truthful and technical posts by portraying them as offensive is a very common tactic in this space. Don't fall for that. People that don't know something (let alone an "entire community") are in no way being called stupid.
– Jannes
yesterday
|
show 8 more comments
14
That's perfectly allowed on this site. Good questions and good answers are always welcome.
– Jannes
yesterday
6
@Jerry Gao: G. Maxwell does not claim that you can fake signatures. He is explaining how someone could be tricked into thinking something was a real signature while it isn't
– Pieter Wuille
yesterday
6
@HenningMakholm: Recently a well-known figure in Bitcoin space has released ECDSA signatures for an unknown message claiming that he'd reveal the message later. They were apparently expecting that people would assume that the signature would convince others of owning the corresponding private key.
– Murch♦
yesterday
3
@HenningMakholm If you think about it, Digital signatures are kind of misnamed. A traditional signature doesn't do anything to bind the document it's written on, besides being written on it. A digital signature works a little more like a wax seal. :) In any case, for some reason an awful lot of people seem to get convinced by the 'signature of something' stated in proximity-- maybe following from a borrowed intuition of traditional signatures.
– G. Maxwell
yesterday
3
@pinhead in no way does OP say that. Belittling accurate, truthful and technical posts by portraying them as offensive is a very common tactic in this space. Don't fall for that. People that don't know something (let alone an "entire community") are in no way being called stupid.
– Jannes
yesterday
14
14
That's perfectly allowed on this site. Good questions and good answers are always welcome.
– Jannes
yesterday
That's perfectly allowed on this site. Good questions and good answers are always welcome.
– Jannes
yesterday
6
6
@Jerry Gao: G. Maxwell does not claim that you can fake signatures. He is explaining how someone could be tricked into thinking something was a real signature while it isn't
– Pieter Wuille
yesterday
@Jerry Gao: G. Maxwell does not claim that you can fake signatures. He is explaining how someone could be tricked into thinking something was a real signature while it isn't
– Pieter Wuille
yesterday
6
6
@HenningMakholm: Recently a well-known figure in Bitcoin space has released ECDSA signatures for an unknown message claiming that he'd reveal the message later. They were apparently expecting that people would assume that the signature would convince others of owning the corresponding private key.
– Murch♦
yesterday
@HenningMakholm: Recently a well-known figure in Bitcoin space has released ECDSA signatures for an unknown message claiming that he'd reveal the message later. They were apparently expecting that people would assume that the signature would convince others of owning the corresponding private key.
– Murch♦
yesterday
3
3
@HenningMakholm If you think about it, Digital signatures are kind of misnamed. A traditional signature doesn't do anything to bind the document it's written on, besides being written on it. A digital signature works a little more like a wax seal. :) In any case, for some reason an awful lot of people seem to get convinced by the 'signature of something' stated in proximity-- maybe following from a borrowed intuition of traditional signatures.
– G. Maxwell
yesterday
@HenningMakholm If you think about it, Digital signatures are kind of misnamed. A traditional signature doesn't do anything to bind the document it's written on, besides being written on it. A digital signature works a little more like a wax seal. :) In any case, for some reason an awful lot of people seem to get convinced by the 'signature of something' stated in proximity-- maybe following from a borrowed intuition of traditional signatures.
– G. Maxwell
yesterday
3
3
@pinhead in no way does OP say that. Belittling accurate, truthful and technical posts by portraying them as offensive is a very common tactic in this space. Don't fall for that. People that don't know something (let alone an "entire community") are in no way being called stupid.
– Jannes
yesterday
@pinhead in no way does OP say that. Belittling accurate, truthful and technical posts by portraying them as offensive is a very common tactic in this space. Don't fall for that. People that don't know something (let alone an "entire community") are in no way being called stupid.
– Jannes
yesterday
|
show 8 more comments
up vote
-5
down vote
The signature verification is the counterpart of the signature computation. Its purpose is to verify the message’s authenticity using the authenticator’s public key. Using the same secure hash algorithm as in the signature step, the message digest signed by the authenticator is computed which, together with the public key Q(x,y) and the digital signature components r and s, leads to the result. Figure 4 illustrates the process.
Signature verification process.
Figure 4. Signature verification process.
Equation 4 shows the individual steps of the verification process. Inputs are the message digest h(m), the public key Q(x,y), the signature components r and s, and the base point G(x,y):
w = 1/s mod n
u1 = (h(m) * w) mod n
u2 = (r * w) mod n
(x2, y2) = (u1 × G(x, y) + u2 × Q(x, y)) mod n (Eq. 4)
The verification is successful (“passes”), if x2 is equal to r, thus confirming that the signature was indeed computed using the private key.
If the verifier doesn't perform the hash himself but just accepts a
value given by the signer, Given public key Q, pick random nonzero
values a and b. Compute R=aG+bQ. Now (R.x, R.x/b) is a valid signature
under key Q for "message-hash" (R.x*a/b).
signature [r,s]
where: r = R.x s = R.x/b
w = 1/s
u1 = h(R.x*a/b) / (R.x/b) mod n
u2 = R.x / (R.x/b) mod n
if h(R.x*a/b) == R.x*a/b
then
u1 == (R.x*a/b) / (R.x/b) == a
else
u1 !== a
this means for u1 == a only valid when Hash(m) == m
since this case can be easily verified. so it's impossible to fake signature.
people who run the code above, please check you Prime number P is correct.
answered yesterday
Jerry Gao
1312
New contributor
Jerry Gao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
8
Your diagram shows exactly the kind of vulnerable thinking that others have been tricked by: It shows the verification process as taking an externally produced 'hash' as input. If someone accepts a 'hash' that isn't a hash, they can be given a forged signature. The hash is integral to ECDSA and cannot be omitted.
– G. Maxwell
yesterday
4
I've downvoted this answer, because it is false and misleading. A cryptographic signature's purpose is to authenticate a message. It is trivial to forge a signature from the public key that doesn't commit to a specific hash, i.e. where the hash is picked to fit the signature. It is impossible to distinguish between a forged signature and a signature for which the original message hasn't been provided.
– Murch♦
yesterday
4
This answer is intentionally deceptive, as others have pointed out, if m is not a hash calculated by the verifier, the system is not validating anything. No competent and non-malicious system uses ECDSA as described in the parent.
– Anonymous
yesterday
I've removed several unrelated comments. Please focus on the post here.
– Murch♦
yesterday
guys, OP_DSV opcode can still be attacked by H(m) == m !
– Jerry Gao
7 hours ago
add a comment |
up vote
-5
down vote
The signature verification is the counterpart of the signature computation. Its purpose is to verify the message’s authenticity using the authenticator’s public key. Using the same secure hash algorithm as in the signature step, the message digest signed by the authenticator is computed which, together with the public key Q(x,y) and the digital signature components r and s, leads to the result. Figure 4 illustrates the process.
Signature verification process.
Figure 4. Signature verification process.
Equation 4 shows the individual steps of the verification process. Inputs are the message digest h(m), the public key Q(x,y), the signature components r and s, and the base point G(x,y):
w = 1/s mod n
u1 = (h(m) * w) mod n
u2 = (r * w) mod n
(x2, y2) = (u1 × G(x, y) + u2 × Q(x, y)) mod n (Eq. 4)
The verification is successful (“passes”), if x2 is equal to r, thus confirming that the signature was indeed computed using the private key.
If the verifier doesn't perform the hash himself but just accepts a
value given by the signer, Given public key Q, pick random nonzero
values a and b. Compute R=aG+bQ. Now (R.x, R.x/b) is a valid signature
under key Q for "message-hash" (R.x*a/b).
signature [r,s]
where: r = R.x s = R.x/b
w = 1/s
u1 = h(R.x*a/b) / (R.x/b) mod n
u2 = R.x / (R.x/b) mod n
if h(R.x*a/b) == R.x*a/b
then
u1 == (R.x*a/b) / (R.x/b) == a
else
u1 !== a
this means for u1 == a only valid when Hash(m) == m
since this case can be easily verified. so it's impossible to fake signature.
people who run the code above, please check you Prime number P is correct.
answered yesterday
Jerry Gao
1312
New contributor
Jerry Gao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
8
Your diagram shows exactly the kind of vulnerable thinking that others have been tricked by: It shows the verification process as taking an externally produced 'hash' as input. If someone accepts a 'hash' that isn't a hash, they can be given a forged signature. The hash is integral to ECDSA and cannot be omitted.
– G. Maxwell
yesterday
4
I've downvoted this answer, because it is false and misleading. A cryptographic signature's purpose is to authenticate a message. It is trivial to forge a signature from the public key that doesn't commit to a specific hash, i.e. where the hash is picked to fit the signature. It is impossible to distinguish between a forged signature and a signature for which the original message hasn't been provided.
– Murch♦
yesterday
4
This answer is intentionally deceptive, as others have pointed out, if m is not a hash calculated by the verifier, the system is not validating anything. No competent and non-malicious system uses ECDSA as described in the parent.
– Anonymous
yesterday
I've removed several unrelated comments. Please focus on the post here.
– Murch♦
yesterday
guys, OP_DSV opcode can still be attacked by H(m) == m !
– Jerry Gao
7 hours ago
add a comment |
up vote
-5
down vote
up vote
-5
down vote
The signature verification is the counterpart of the signature computation. Its purpose is to verify the message’s authenticity using the authenticator’s public key. Using the same secure hash algorithm as in the signature step, the message digest signed by the authenticator is computed which, together with the public key Q(x,y) and the digital signature components r and s, leads to the result. Figure 4 illustrates the process.
Signature verification process.
Figure 4. Signature verification process.
Equation 4 shows the individual steps of the verification process. Inputs are the message digest h(m), the public key Q(x,y), the signature components r and s, and the base point G(x,y):
w = 1/s mod n
u1 = (h(m) * w) mod n
u2 = (r * w) mod n
(x2, y2) = (u1 × G(x, y) + u2 × Q(x, y)) mod n (Eq. 4)
The verification is successful (“passes”), if x2 is equal to r, thus confirming that the signature was indeed computed using the private key.
If the verifier doesn't perform the hash himself but just accepts a
value given by the signer, Given public key Q, pick random nonzero
values a and b. Compute R=aG+bQ. Now (R.x, R.x/b) is a valid signature
under key Q for "message-hash" (R.x*a/b).
signature [r,s]
where: r = R.x s = R.x/b
w = 1/s
u1 = h(R.x*a/b) / (R.x/b) mod n
u2 = R.x / (R.x/b) mod n
if h(R.x*a/b) == R.x*a/b
then
u1 == (R.x*a/b) / (R.x/b) == a
else
u1 !== a
this means for u1 == a only valid when Hash(m) == m
since this case can be easily verified. so it's impossible to fake signature.
people who run the code above, please check you Prime number P is correct.
answered yesterday
Jerry Gao
1312
New contributor
Jerry Gao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
The signature verification is the counterpart of the signature computation. Its purpose is to verify the message’s authenticity using the authenticator’s public key. Using the same secure hash algorithm as in the signature step, the message digest signed by the authenticator is computed which, together with the public key Q(x,y) and the digital signature components r and s, leads to the result. Figure 4 illustrates the process.
Signature verification process.
Figure 4. Signature verification process.
Equation 4 shows the individual steps of the verification process. Inputs are the message digest h(m), the public key Q(x,y), the signature components r and s, and the base point G(x,y):
w = 1/s mod n
u1 = (h(m) * w) mod n
u2 = (r * w) mod n
(x2, y2) = (u1 × G(x, y) + u2 × Q(x, y)) mod n (Eq. 4)
The verification is successful (“passes”), if x2 is equal to r, thus confirming that the signature was indeed computed using the private key.
If the verifier doesn't perform the hash himself but just accepts a
value given by the signer, Given public key Q, pick random nonzero
values a and b. Compute R=aG+bQ. Now (R.x, R.x/b) is a valid signature
under key Q for "message-hash" (R.x*a/b).
signature [r,s]
where: r = R.x s = R.x/b
w = 1/s
u1 = h(R.x*a/b) / (R.x/b) mod n
u2 = R.x / (R.x/b) mod n
if h(R.x*a/b) == R.x*a/b
then
u1 == (R.x*a/b) / (R.x/b) == a
else
u1 !== a
this means for u1 == a only valid when Hash(m) == m
since this case can be easily verified. so it's impossible to fake signature.
people who run the code above, please check you Prime number P is correct.
answered yesterday
Jerry Gao
1312
New contributor
Jerry Gao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
answered yesterday
Jerry Gao
1312
New contributor
Jerry Gao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered yesterday
Jerry Gao
1312
answered yesterday
Jerry Gao
1312
1312
New contributor
Jerry Gao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Jerry Gao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Jerry Gao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
8
Your diagram shows exactly the kind of vulnerable thinking that others have been tricked by: It shows the verification process as taking an externally produced 'hash' as input. If someone accepts a 'hash' that isn't a hash, they can be given a forged signature. The hash is integral to ECDSA and cannot be omitted.
– G. Maxwell
yesterday
4
I've downvoted this answer, because it is false and misleading. A cryptographic signature's purpose is to authenticate a message. It is trivial to forge a signature from the public key that doesn't commit to a specific hash, i.e. where the hash is picked to fit the signature. It is impossible to distinguish between a forged signature and a signature for which the original message hasn't been provided.
– Murch♦
yesterday
4
This answer is intentionally deceptive, as others have pointed out, if m is not a hash calculated by the verifier, the system is not validating anything. No competent and non-malicious system uses ECDSA as described in the parent.
– Anonymous
yesterday
I've removed several unrelated comments. Please focus on the post here.
– Murch♦
yesterday
guys, OP_DSV opcode can still be attacked by H(m) == m !
– Jerry Gao
7 hours ago
add a comment |
8
Your diagram shows exactly the kind of vulnerable thinking that others have been tricked by: It shows the verification process as taking an externally produced 'hash' as input. If someone accepts a 'hash' that isn't a hash, they can be given a forged signature. The hash is integral to ECDSA and cannot be omitted.
– G. Maxwell
yesterday
4
I've downvoted this answer, because it is false and misleading. A cryptographic signature's purpose is to authenticate a message. It is trivial to forge a signature from the public key that doesn't commit to a specific hash, i.e. where the hash is picked to fit the signature. It is impossible to distinguish between a forged signature and a signature for which the original message hasn't been provided.
– Murch♦
yesterday
4
This answer is intentionally deceptive, as others have pointed out, if m is not a hash calculated by the verifier, the system is not validating anything. No competent and non-malicious system uses ECDSA as described in the parent.
– Anonymous
yesterday
I've removed several unrelated comments. Please focus on the post here.
– Murch♦
yesterday
guys, OP_DSV opcode can still be attacked by H(m) == m !
– Jerry Gao
7 hours ago
8
8
Your diagram shows exactly the kind of vulnerable thinking that others have been tricked by: It shows the verification process as taking an externally produced 'hash' as input. If someone accepts a 'hash' that isn't a hash, they can be given a forged signature. The hash is integral to ECDSA and cannot be omitted.
– G. Maxwell
yesterday
Your diagram shows exactly the kind of vulnerable thinking that others have been tricked by: It shows the verification process as taking an externally produced 'hash' as input. If someone accepts a 'hash' that isn't a hash, they can be given a forged signature. The hash is integral to ECDSA and cannot be omitted.
– G. Maxwell
yesterday
4
4
I've downvoted this answer, because it is false and misleading. A cryptographic signature's purpose is to authenticate a message. It is trivial to forge a signature from the public key that doesn't commit to a specific hash, i.e. where the hash is picked to fit the signature. It is impossible to distinguish between a forged signature and a signature for which the original message hasn't been provided.
– Murch♦
yesterday
I've downvoted this answer, because it is false and misleading. A cryptographic signature's purpose is to authenticate a message. It is trivial to forge a signature from the public key that doesn't commit to a specific hash, i.e. where the hash is picked to fit the signature. It is impossible to distinguish between a forged signature and a signature for which the original message hasn't been provided.
– Murch♦
yesterday
4
4
This answer is intentionally deceptive, as others have pointed out, if m is not a hash calculated by the verifier, the system is not validating anything. No competent and non-malicious system uses ECDSA as described in the parent.
– Anonymous
yesterday
This answer is intentionally deceptive, as others have pointed out, if m is not a hash calculated by the verifier, the system is not validating anything. No competent and non-malicious system uses ECDSA as described in the parent.
– Anonymous
yesterday
I've removed several unrelated comments. Please focus on the post here.
– Murch♦
yesterday
I've removed several unrelated comments. Please focus on the post here.
– Murch♦
yesterday
guys, OP_DSV opcode can still be attacked by H(m) == m !
– Jerry Gao
7 hours ago
guys, OP_DSV opcode can still be attacked by H(m) == m !
– Jerry Gao
7 hours ago
add a comment |
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%2f81115%2fif-someone-wanted-to-pretend-to-be-satoshi-by-posting-a-fake-signature-to-defrau%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
