Who is creating non-DER signatures?

(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!

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

On Sun, Apr 7, 2013 at 5:34 PM, Pieter Wuille <pieter.wuille@gmail•com>wrote:

> (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
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>

On Sun, Apr 07, 2013 at 06:01:13PM +0200, Mike Hearn wrote:

> 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).

On Sun, Apr 7, 2013 at 5:34 PM, Pieter Wuille <pieter.wuille@gmail•com>wrote:

> 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.

On Sat, Apr 13, 2013 at 2:43 PM, Pieter Wuille <pieter.wuille@gmail•com> wrote:

> 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.

On Sat, Apr 13, 2013 at 02:58:21PM -0700, Gregory Maxwell wrote:

> 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,