Non-canonical signatures: looking for detectives

[Pieter Wuille]

Hello everyone,

as some of you may know, Bitcoin uses DER-encoded signatures. However, at least the reference client supports any signature encoded in the less strictly defined BER encoding (and even allows some deviations from that). There are several inconveniences associated with allowing multiple encodings, and even some very weak attacks (there's no risk of losing money, in any case). To prevent this, we'd like to at first make non-canonical signatures non-standard, and maybe at a (much) later time, propose a BIP to make them invalid entirely.

There are still some sites/software which produces non-canonical signatures, so we can't make them non-standard yet. My question for you is finding who creates them.

Here is a list of transaction id's my node saw recently, which use a particular type of DER violation (excessive padding):


2229be0a6b3342d5dc3443be9b8b5306e6531f177434b5111247c0155995ba58
284c7971387d1a049aee8bd693fe2dfbad69521c0e43224bd5263529f0002744
35c0819290fd7bdfd48e7a20ea8260a0805993d714a7d7e21892d93e6e7c2f7b
5b74b9b294769be261a9caa1310bb648dd6dd530ac75cee9b7c6bfb6d160d07d
6009f0ef333e81c15a3818fc18b728e7b37881e665ae2b2e6d71b2337219f3da
63c310454e0a23d2543548a4cf7500557a2c632a84fbeb20bee47a3b16bd37b9
72dd12b8451298f316a8b687766e399f397e81e4c1c318f87548725bc95aadf5
82f37114f752865b1520eae888913b02f68aea740d830d1afe9487efd6bfa6d0
83abc9588b7a5c6084398f92c88c485e025773c567745b125c977aa1a502bc88
8a1fae8c8dbb96d1f6b879830f4df948b11ea10806564a60e0197c28f7718d52
95b5b109b744c04369e4d122bb86f3cce951088ab641fe7c6dc35c91a66ffc5b
ae216d17d68fef69b53fbc283f60efd342509f36b51c8740bdf149c319a516b1
c0f852f402f1a9989cc4c8b4921461ec850d8c4b8a9c5733a6273429523f066a
cfd4fce2d88967fdbe089b455169b683503576f69faaa1e9da636ccd62196b05


Anyone knows who/what created these?

[twobitcoins]

Transaction 5b74b9b294769be261a9caa1310bb648dd6dd530ac75cee9b7c6bfb6d160d07d sends 3 BTC to address 1A1SnqhiTVJ1YqtQZJ7SCr2iRxjsvJaQwf which are then sent to SatoshiDice.  The owner of that address is registered with CoinWorker (see http://coinworker.com/activity/1A1SnqhiTVJ1YqtQZJ7SCr2iRxjsvJaQwf).  Registration on CoinWorker requires an email address.  So by contacting the operator of CoinWorker, user WargeGeoshington on bitcointalk, it may be possible to get in touch with the owner of that address and ask where the 3 BTC came from.

Transaction 82f37114f752865b1520eae888913b02f68aea740d830d1afe9487efd6bfa6d0 was sent by the owner of address 17jruemRwRU2NKZhN7UgPkNDbiDE7rZ9q7.  That address receives payouts from the Deepbit mining pool.  Deepbit registration requires an email address.  So by contacting the operator of Deepbit it may be possible to get in touch with the owner of that address and ask what software or wallet service they are using.

Similarly, transaction 83abc9588b7a5c6084398f92c88c485e025773c567745b125c977aa1a502bc88 was send by the owner of address 1M2bLtPGNCxufR1eX38z23q1NZYoXkvgw2 which is a Deepbit payout address.

Transaction 8a1fae8c8dbb96d1f6b879830f4df948b11ea10806564a60e0197c28f7718d52 spends what appears to be the change from transaction 469e9d456da07abbeffbc7c94e68fcf33dfe850ef50dae1e58647a9c1223bd52, which paid 2 BTC to address 1EQfkKVZndiesJcwThRe5AAq15dZ56mZku.  That address belongs to user theboss on bitcointalk.  By contacting theboss it may be possible to find out where those 2 BTC came from.

[Pieter Wuille]

gmaxwell has since found out that at least some of the non-DER signatures are created by Armory, and etotheipi has already told me he'll change it for the next release.

[etotheipi]

They're probably all Armory signatures.  It's a shortcut I took early on in armoryengine when creating transactions, and I left it because the network didn't seem to care.  Now Armory is getting 1,500 downloads a month, and even if 10% of those downloads are producing transactions, you're bound to run into dozens of them.  I'm surprised there aren't more...

On that note, I specifically remember mentioning it to roconner on IRC (or rather, he asked me about it), and was amazed when I told him that it works.  Maybe he went and started doing it, too...?  Heh, probably not.  Just blame it on me, for now.

[Pieter Wuille]

On that note, I specifically remember mentioning it to roconner on IRC (or rather, he asked me about it), and was amazed when I told him that it works.  Maybe he went and started doing it, too...?  Heh, probably not.  Just blame it on me, for now.

Actually, no. Here's a list of signatures that use excessive padding, and are certainly not created by Armory (I checked its source code):


f7b8c8aa8a7bb0863646dadb2a2ec549d852ef7b76e486edad98ceebbbcacd7c
9dd9eaffe8862b2c50306322f1c91e1a0e6680bec504ec47ba3ec8dde1500273
3754b02a582375f4bba91ad42837c71e666a109ea0cdaa5b8b118530e47fb139
5199802d027d689a17340e9eab7816ddab44bf2c56b9d9bcc53a0cd6819c915d
50998e3c9036099cb8868a91e13f8067ef20b07822bb359e8025fadd5a6aff85
d84258850dfbbbdfd97b0d8ef16cdbb7104130626b207c4b2df8b5a7716e421b
a165c2467873303b1da4348ca5a314d32d6c7a0bd03f64e40439f0b9f93101db
f0b7592f35cf51eddbb6cb32cefb870db7d33ce21253c75ffe4c9cdd4feaa57a
ce5c306f6dad7bf291fe536e026930f58e2779c37c4db1e7651d83e61b657c47
28680b34764f83a7dd31cb88a27e377602d79c89ef762611af32a548b5fb229f
76491e456827d304f5766276d896a060ef511b85cafb1336239d6b3e2af05fed
263107307a774a60f50f80ae997edb21b58944267b5d1db13675b455eb114143
9ce2dd7a13f9183128a410d777341ff09b407c0e09c46cc5986c05546c893d49

[Pieter Wuille]

This one in particular is strange: 9ce2dd7a13f9183128a410d777341ff09b407c0e09c46cc5986c05546c893d49.

Its second input has an R value that is 9 million times smaller than its maximum, which is unlikely to happen purely by chance...

[etotheipi]

This one in particular is strange: 9ce2dd7a13f9183128a410d777341ff09b407c0e09c46cc5986c05546c893d49.

Its second input has an R value that is 9 million times smaller than its maximum, which is unlikely to happen purely by chance...

Are you talking about the 5 hex zeros leading the R value?  That's not incorrectly padded, is it?  Aren't all R and S values supposed to be padded out to 32-bytes, or 33 only if it would be interpretted as negative?

It is suspicious that the R value has such leading zeros, I just want to make sure I implement it correctly myself (if Armory (r,s) values are low, I still pad out to 32 bytes, right?).

I suppose someone could keep signing their transaction over and over (with a different random k every time) until they get the leading zeros.  It might take a while, though...

[Pieter Wuille]

It's certainly incorrectly padded (according to DER).

Neither R and S can start with a zero byte, unless the value would otherwise represent a negative value, in which case exactly one zero byte is required.

So if R would be the (improbably low) number 10000000 (decimal), it'd be encoded as 0x00989680.

[etotheipi]

It's certainly incorrectly padded (according to DER).

Neither R and S can start with a zero byte, unless the value would otherwise represent a negative value, in which case exactly one zero byte is required.

So does that mean that I need to check for leading zero bytes and remove them, in the case that the R or S values happen to be that small by chance? 

So R and S are not always supposed to be 32 or 33 bytes?

[Pieter Wuille]

So does that mean that I need to check for leading zero bytes and remove them, in the case that the R or S values happen to be that small by chance? 

Exactly.

So R and S are not always supposed to be 32 or 33 bytes?

Certainly not, but fewer bytes becomes exponentially less probable.

[etotheipi]

So does that mean that I need to check for leading zero bytes and remove them, in the case that the R or S values happen to be that small by chance? 

Exactly.

So R and S are not always supposed to be 32 or 33 bytes?

Certainly not, but fewer bytes becomes exponentially less probable.

Well then, the fix I just committed to Armory master branch is wrong...

[Gavin Andresen]

We should avoid saying "canonical" -- I just peeked at the ASN.1/BER/DER spec, and there's a "canonical" encoding that is different from the "distinguished" encoding:

   http://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf

(international standards committees seem to be completely incapable of adhering to the Keep It Simple, Stupid principle).

[Mike Hearn]

I checked BouncyCastle/bitcoinj and AFAICT it's doing the right thing here. The R and S components are written out as BigInteger.toByteArray which will encode in twos-complement notation with a leading zero byte appended only if necessary. At least that's what it's supposed to do.

[etotheipi]

I checked BouncyCastle/bitcoinj and AFAICT it's doing the right thing here. The R and S components are written out as BigInteger.toByteArray which will encode in twos-complement notation with a leading zero byte appended only if necessary. At least that's what it's supposed to do.

I'm sure you checked it, but does it produce smaller encodings if the integer values are smaller?  Armory uses cryptopp which will spit out 32-byte (r,s) value pairs regardless.  I have to manually trim the leading zero bytes.  

[Jan]

Hello everyone,

as some of you may know, Bitcoin uses DER-encoded signatures. However, at least the reference client supports any signature encoded in the less strictly defined BER encoding (and even allows some deviations from that). There are several inconveniences associated with allowing multiple encodings, and even some very weak attacks (there's no risk of losing money, in any case). To prevent this, we'd like to at first make non-canonical signatures non-standard, and maybe at a (much) later time, propose a BIP to make them invalid entirely.
...

Sorry for reviving this old thread, but can someone confirm whether non-canonical signatures are now non-standard or even invalid.

[gmaxwell]

Sorry for reviving this old thread, but can someone confirm whether non-canonical signatures are now non-standard or even invalid.

Signatures which are non-canonical in the manners mentioned in this thread are non-standard now. There are several more restrictions which must be imposed before the malleability attacks will be gone, however.

[Jan]

Sorry for reviving this old thread, but can someone confirm whether non-canonical signatures are now non-standard or even invalid.

Signatures which are non-canonical in the manners mentioned in this thread are non-standard now. There are several more restrictions which must be imposed before the malleability attacks will be gone, however.

... such as ambiguous chunk encoding.

Do you remember which version started enforcing those rules?

[Pieter Wuille]

Do you remember which version started enforcing those rules?

v0.8.0

[justusranvier]

My btcd node has been seeing transactions with strange signatures recently.

# grep -R -C1 signature /var/log/everything
08:31:46 2013-12-14 [WRN] SCRP: can't parse signature from string: signature R is negative
08:31:46 2013-12-14 [WRN] CHAN: validate of input 0 failed: signature R is negative
08:31:46 2013-12-14 [WRN] CHAN: tx b5043a18e3833907d4e92d00cbfdd220f5f953a07d26699ad7470c719c91cc65 failed input 0, err signature R is negative
08:31:46 2013-12-14 [ERR] BMGR: Failed to process transaction b5043a18e3833907d4e92d00cbfdd220f5f953a07d26699ad7470c719c91cc65: signature R is negative
08:31:46 2013-12-14 [WRN] SCRP: can't parse signature from string: signature R is negative
08:31:46 2013-12-14 [WRN] CHAN: validate of input 0 failed: signature R is negative
08:31:46 2013-12-14 [WRN] CHAN: tx 03154590218aa7067e8177cec4e565dc283c74bea5fedc17048578b4860a32e2 failed input 0, err signature R is negative
08:31:46 2013-12-14 [ERR] BMGR: Failed to process transaction 03154590218aa7067e8177cec4e565dc283c74bea5fedc17048578b4860a32e2: signature R is negative
08:31:48 2013-12-14 [WRN] SCRP: can't parse signature from string: signature R is negative
08:31:48 2013-12-14 [WRN] CHAN: validate of input 0 failed: signature R is negative
08:31:48 2013-12-14 [WRN] CHAN: tx b5043a18e3833907d4e92d00cbfdd220f5f953a07d26699ad7470c719c91cc65 failed input 0, err signature R is negative
08:31:48 2013-12-14 [ERR] BMGR: Failed to process transaction b5043a18e3833907d4e92d00cbfdd220f5f953a07d26699ad7470c719c91cc65: signature R is negative
08:31:49 2013-12-14 [WRN] SCRP: can't parse signature from string: signature S is negative
08:31:49 2013-12-14 [WRN] CHAN: validate of input 0 failed: signature S is negative
08:31:49 2013-12-14 [WRN] CHAN: tx ceaa241316a03719e997105996d033c2a856f999e4ccf637b79c8cd2ea98dc65 failed input 0, err signature S is negative
08:31:49 2013-12-14 [ERR] BMGR: Failed to process transaction ceaa241316a03719e997105996d033c2a856f999e4ccf637b79c8cd2ea98dc65: signature S is negative
08:31:49 2013-12-14 [WRN] SCRP: can't parse signature from string: signature R is negative
08:31:49 2013-12-14 [WRN] CHAN: validate of input 0 failed: signature R is negative
08:31:49 2013-12-14 [WRN] CHAN: tx 6f322d83070091e237fc6eaa12933575dd87933513ce68205014e751eaa0ffe5 failed input 0, err signature R is negative
08:31:49 2013-12-14 [ERR] BMGR: Failed to process transaction 6f322d83070091e237fc6eaa12933575dd87933513ce68205014e751eaa0ffe5: signature R is negative
08:31:52 2013-12-14 [WRN] SCRP: can't parse signature from string: signature R is negative
08:31:52 2013-12-14 [WRN] CHAN: validate of input 0 failed: signature R is negative
08:31:52 2013-12-14 [WRN] CHAN: tx d814630684cc1c63a363f5be8c2efb6858a1221e9b1b61c4c8432c13e63cd811 failed input 0, err signature R is negative
08:31:52 2013-12-14 [ERR] BMGR: Failed to process transaction d814630684cc1c63a363f5be8c2efb6858a1221e9b1b61c4c8432c13e63cd811: signature R is negative
08:31:52 2013-12-14 [WRN] SCRP: can't parse signature from string: signature R is negative
08:31:52 2013-12-14 [WRN] CHAN: validate of input 0 failed: signature R is negative
08:31:52 2013-12-14 [WRN] CHAN: tx 6f322d83070091e237fc6eaa12933575dd87933513ce68205014e751eaa0ffe5 failed input 0, err signature R is negative
08:31:52 2013-12-14 [ERR] BMGR: Failed to process transaction 6f322d83070091e237fc6eaa12933575dd87933513ce68205014e751eaa0ffe5: signature R is negative
08:31:52 2013-12-14 [WRN] SCRP: can't parse signature from string: signature R is negative
08:31:52 2013-12-14 [WRN] CHAN: validate of input 0 failed: signature R is negative
08:31:52 2013-12-14 [WRN] CHAN: tx ac22ed3db9ff16664c144f7c5aa71f296c7e87b3a9e3c03624d7dfdc124125ac failed input 0, err signature R is negative
08:31:52 2013-12-14 [ERR] BMGR: Failed to process transaction ac22ed3db9ff16664c144f7c5aa71f296c7e87b3a9e3c03624d7dfdc124125ac: signature R is negative
08:31:53 2013-12-14 [WRN] SCRP: can't parse signature from string: signature S is negative
08:31:53 2013-12-14 [WRN] CHAN: validate of input 0 failed: signature S is negative
08:31:53 2013-12-14 [WRN] CHAN: tx ceaa241316a03719e997105996d033c2a856f999e4ccf637b79c8cd2ea98dc65 failed input 0, err signature S is negative
08:31:53 2013-12-14 [ERR] BMGR: Failed to process transaction ceaa241316a03719e997105996d033c2a856f999e4ccf637b79c8cd2ea98dc65: signature S is negative
08:31:54 2013-12-14 [WRN] SCRP: can't parse signature from string: signature R is negative
08:31:54 2013-12-14 [WRN] CHAN: validate of input 0 failed: signature R is negative
08:31:54 2013-12-14 [WRN] CHAN: tx ac22ed3db9ff16664c144f7c5aa71f296c7e87b3a9e3c03624d7dfdc124125ac failed input 0, err signature R is negative
08:31:54 2013-12-14 [ERR] BMGR: Failed to process transaction ac22ed3db9ff16664c144f7c5aa71f296c7e87b3a9e3c03624d7dfdc124125ac: signature R is negative
08:37:24 2013-12-14 [INF] BMGR: Processed 1 block in the last 8m12.4s (207 transactions, height 274809, 2013-12-14 08:37:06 +0000 UTC)

[Mike Hearn]

Logging a tx hash of a transaction that isn't relaying isn't very useful (bitcoind has the same problem though). There's no way to figure out what kind of transactions these are or where they come from based on those logs.

My node sees a handful of such transactions every few days. They can be created by old versions of bitcoinjs, a javascript library. I think after we fixed blockchain.info the number of such transactions has dropped off dramatically.