Help me look for sites/software that produces non-standard signatures

Mike Hearn

legendary

Activity: 1526

Merit: 1134

I made a little Android app that generates random keys and signs random data in a loop, then ran it on a Froyo emulator. I couldn't make it spit out negative r/s values unfortunately. So perhaps my theory is incorrect.

It sounds like maybe bitcoinjs could do this:

https://github.com/bitcoinjs/bitcoinjs-lib/blob/master/src/ecdsa.js

Unfortunately I don't see any way the results can be negative with that code either. I do see a minor difference between the Bouncy Castle implementation and ecdsa.js which is that Bouncy Castle will keep retrying the signing process until s is not zero, whereas ecdsa.js won't. Otherwise they look the same.

The serialization code in bitcoinjs looks OK too.

https://github.com/bitcoinjs/bitcoinjs-lib/blob/master/src/ecdsa.js#L302
https://github.com/bitcoinjs/bitcoinjs-lib/blob/master/src/util.js#L43

Other than a bug in the underlying platform math libraries or bogus serialization code, what explanations exist for negative r/s values? None of the underlying BigInteger operations can result in negative numbers.

gmaxwell

staff

Activity: 4242

Merit: 8672

I contacted several forum users who had used addresses in the list in their signatures.

I've received a couple responses:

1Pq7zKpZHLaT9yheWyHqQp8XUtvTmt7VTm - blockchain.info / iPad app
18ix3ikc51sKTwmfho5fjmfqe2miJBQR2c - blockchain.info / chrome (no code pinning/extension, I asked)

Mike Hearn

legendary

Activity: 1526

Merit: 1134

I suspect the negative R/S values can be generated by Android wallet users who are running on Froyo. This old version of Android is known to be unable to reliably calculate signatures due to a buggy BigInteger class. Andreas didn't want to cut off support for these users entirely as it still makes up a few percent of the Android userbase, so he implemented a hack whereby signatures are checked after generation, and if the signature doesn't verify it's generated again!

Unfortunately this leads to a problem. Preventing Bitcoin Wallet from being installed on Froyo is easy. But the existing users would still be creating bad signatures from time to time. It may be that we need to change bitcoinj to use r.abs() and s.abs() instead of r and s, even though that should have no effect on normal platforms.

TheButterZone

legendary

Activity: 3038

Merit: 1032

RIP Mommy

Quote from: gmaxwell on December 26, 2012, 03:59:54 PM

This is the prior output addresses of these transactions inputs— the owners of these addresses are the likely parties operating the software which creates these non-standard signatures is on this webpage. I moved it off the forum so you could easily see which links were already visited for you (the default forum color scheme gets in the way of that).

I also included google links so you can go searching deeper. So far, people on IRC were able to identify TheButterZone as 1TBZYXjrGjXCEN1SprpF66Jzy5uN3GiLS.

I'm also 1TBZjmXho6mdGhoESaMV2svtqJXYtWfEp on here http://people.xiph.org/~greg/non-standard-signatures.html - this is also the address involved at https://bitcointalksearch.org/topic/519704-received-at-1tbzjmxho6mdghoesamv2svtqjxytwfep-lost-and-found-133122 - but as that is just about random unexplained received TXs at that address, it's probably just a coincidence.

I send TXs for both these addresses with an Oct 1 2012 copy of brainwallet.org - and they're both vanities, found by http://silverthreadsoftware.com/bitcoin/vanity/VanityAddress.jar - discussion about the JAR here: https://bitcointalksearch.org/topic/simple-vanity-address-generator-v04-76038

Trifecta?

Pieter Wuille

legendary

Activity: 1072

Merit: 1181

Added gmaxwell's link to the top post.

gmaxwell

staff

Activity: 4242

Merit: 8672

This is the prior output addresses of these transactions inputs— the owners of these addresses are the likely parties operating the software which creates these non-standard signatures is on this webpage. I moved it off the forum so you could easily see which links were already visited for you (the default forum color scheme gets in the way of that).

I also included google links so you can go searching deeper. So far, people on IRC were able to identify TheButterZone as 1TBZYXjrGjXCEN1SprpF66Jzy5uN3GiLS.

Since people are missing it:
This link has addresses instead of txids.

Pieter Wuille

legendary

Activity: 1072

Merit: 1181

Hello everyone,

since it was discovered that Bitcoin accepts transactions whose signatures are not formatted entirely according to the DER standard, we've been wanting to fix this, by making the rules somewhat more strict (this would make it easier for new implementations for example, as they now have to mimic exactly what OpenSSL does, in case they use a different crypto library).

This is however hard to just change, as there is apparently still software out there that (probably unknowingly) violates the strict specification "as it worked anyway". Some time ago we already identified some "offenders", and the frequency of non-DER signatures dropped significantly since then. In the past few days, only 0.2%-0.5%. Still, I'd like to see this drop closer to zero before releasing software that doesn't relay it anymore. (Note: in time, this may become a network rule, but in this first stage the question is just whether to relay them or not - blocks with such transactions remain valid).

Here is a full list of all offending transactions the past 4 days. If can help identify their source, perhaps we can make the percentage drop further.

EDIT: here is a page with addresses from which non-standard transactions have originated.

Transactions with (at least) a signature with an "excessively padded R value":

Transactions with (at least) an "excessively padded S value":

Transaction with (at least) a "negative R value":

Transactions with (at least) a "negative S value":

Thanks!

Topic: Help me look for sites/software that produces non-standard signatures (Read 1674 times)