[Bitcoin-development] Who is creating non-DER signatures?

[Pieter Wuille]

(cross-post from bitcointalk.org)

Hello all,

as some may know, Bitcoin uses DER-encoded signatures in its transactions.
However, OpenSSL (which is used to verify them) accepts more than just the
strict DER specification (it allows negative numbers, extra zero padding,
extra bytes at the end, and perhaps more). As we don't like the de-facto
specification of the Bitcoin block validity rules to depend on OpenSSL,
we're trying to introduce a rule to make such non-standard signatures
invalid. Obviously, that can't be done as long as any significant amount of
clients on the network is creating these.

I've monitored all transactions the past weeks (1.4M transactions), and it
seems 9641 of them contain at least one non-standard signature. See
https://bitcointalk.org/index.php?topic=169620.0 for a list of the top
addresses that had coins used as inputs in such transactions. If you
recognize any of these addresses, or have an idea of who owns them or what
software they are using, please let me know.

Thanks!

[Mike Hearn]

It'd help to know how the signatures are invalid.

Post by Pieter Wuille
(cross-post from bitcointalk.org)
Hello all,
as some may know, Bitcoin uses DER-encoded signatures in its transactions.
However, OpenSSL (which is used to verify them) accepts more than just the
strict DER specification (it allows negative numbers, extra zero padding,
extra bytes at the end, and perhaps more). As we don't like the de-facto
specification of the Bitcoin block validity rules to depend on OpenSSL,
we're trying to introduce a rule to make such non-standard signatures
invalid. Obviously, that can't be done as long as any significant amount of
clients on the network is creating these.
I've monitored all transactions the past weeks (1.4M transactions), and it
seems 9641 of them contain at least one non-standard signature. See
https://bitcointalk.org/index.php?topic=169620.0 for a list of the top
addresses that had coins used as inputs in such transactions. If you
recognize any of these addresses, or have an idea of who owns them or what
software they are using, please let me know.
Thanks!
--
Pieter
------------------------------------------------------------------------------
Minimize network downtime and maximize team effectiveness.
Reduce network management and security costs.Learn how to hire
the most talented Cisco Certified professionals. Visit the
Employer Resources Portal
http://www.cisco.com/web/learning/employer_resources/index.html
_______________________________________________
Bitcoin-development mailing list
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Pieter Wuille]

Post by Mike Hearn
It'd help to know how the signatures are invalid.

The majority (~90%) is negative R or S values (which are just interpreted as
unsigned by OpenSSL, but if the top byte has its highest bit set, it must be
preceeded by a 0x00 accordinging to DER). A smaller number uses excessively
padded R or S value (with a 0x00 in front when it's not necessary). Finally
there are 4 signatures with an incorrect length marker in the beginning
(which likely means they contain some garbage at the end).

[Pieter Wuille]

Post by Pieter Wuille
I've monitored all transactions the past weeks (1.4M transactions), and it
seems 9641 of them contain at least one non-standard signature. See
https://bitcointalk.org/index.php?topic=169620.0 for a list of the top
addresses that had coins used as inputs in such transactions. If you
recognize any of these addresses, or have an idea of who owns them or what
software they are using, please let me know.

Without significant effort, I don't think we're going to be able to get
that number down. I'd like to stress that without making these non-standard
encodings effectively invalid on the network, pretty much every full node
implementation needs to depend on OpenSSL to guarantee compatibility (and
that is hoping OpenSSL doesn't change its supported encodings), or make
assumptions about which deviations are allowed.

The next question, I guess, is at which transaction frequency it's
acceptable to move forward with this? The first step is definitely just not
accepting them into memory pools, but leaving them valid inside blocks.
Actual network rules will need to come later. However, even just not
accepting them into memory pools will it make very hard (if not impossible)
for the buggy clients that create transactions to get any confirmations.
I'm not sure... 0.6% isn't much, but 9600 transactions is.

[Gregory Maxwell]

Post by Pieter Wuille
Actual network rules will need to come later. However, even just not
accepting them into memory pools will it make very hard (if not impossible)
for the buggy clients that create transactions to get any confirmations. I'm
not sure... 0.6% isn't much, but 9600 transactions is.

Without knowing how they're getting created it's hard to say what the
damage is... are they being created by people using old cached JS
transaction generators? If so— the harm is insignificant. Are they
being created by hardware wallets with the keys baked inside that
can't be changed? If so— the harm would be more significant.

I think the latter is unlikely right now— but if the network doesn't
stop relaying these transactions it seems inevitable.

In all cases these transactions can be currently be mutated to an
acceptable form— the malleability being one of the arguments for
removing support for non-canonical encodings. So we could easily post
a transaction normalizer tool that someone with unrelayable
transactions could pass their transactions through to fix them, even
without coming to the developers for help.

[Pieter Wuille]

Post by Gregory Maxwell
I think the latter is unlikely right now— but if the network doesn't
stop relaying these transactions it seems inevitable.

A patch was just merged in git head to enforce strict encodings for accepting
transactions into the memory pool. As miners and other nodes don't upgrade
immediately (and 0.8.2 isn't even released yet), this means such transactions
will likely still make it into blocks, but will have an increasingly harder
time doing so.

When the rate of non-standard encodings in the block chain has dropped far
enough, we can attempt scheduling a soft forking change to make it required.
At that point, the network rules will no longer depend on OpenSSL's parsers.

As a summary, here are the rules now enforced for acceptance into the memory
pool:
* 0. These rules are only applied for _evaluated_ scripts, as there is no
guaranteed way to know which data is supposed to be interpreted as a
public key or signature before actually evaluating the script. This
means that for example a 1-of-2 multisig can have an incorrectly-
encoded public key, but still be redeemed if a valid (and correctly
encoded) signature is given for the other key.
* 1. Public keys are either compressed (0x02 + 32 bytes, or 0x03 + 32 bytes)
or uncompressed (0x04 + 64 bytes). The non-standard "hybrid" encoding
supported by OpenSSL is not allowed.
* 2. Signatures are strictly DER-encoded (+ hashtype byte). The format is:
0x30 <lenT> 0x02 <lenR> <R> 0x02 <lenS> <S> <hashtype>
* R and S are signed integers, encoded as a big-endian byte sequence.
They are stored in as few bytes as possible (i.e., no 0x00 padding in
front), except that a single 0x00 byte is needed and even required
when the byte following it has its highest bit set, to prevent it
from being interpreted as a negative number.
* lenR and lenS are one byte, containing the length of the R and S
records, respectively.
* lenT is one byte, containing the length of the complete structure
following it, starting from the 0x02, up to the S record. Thus, it
must be equal to lenR + lenS + 4.
* The hashtype is one byte, and is either 0x01, 0x02, 0x03, 0x81, 0x82
or 0x83.
* No padding is allowed before or after the hashtype byte, thus lenT
is equal to the size of the whole signature minus 3.
* 3. These rules also apply to testnet.

Cheers,

--
Pieter