From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1YE9Dk-0000ZU-MG for bitcoin-development@lists.sourceforge.net; Thu, 22 Jan 2015 04:18:16 +0000 X-ACL-Warn: Received: from resqmta-po-01v.sys.comcast.net ([96.114.154.160]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:AES128-SHA:128) (Exim 4.76) id 1YE9Di-0003Oq-Lw for bitcoin-development@lists.sourceforge.net; Thu, 22 Jan 2015 04:18:16 +0000 Received: from resomta-po-06v.sys.comcast.net ([96.114.154.230]) by resqmta-po-01v.sys.comcast.net with comcast id isHJ1p0094yXVJQ01sJ9ya; Thu, 22 Jan 2015 04:18:09 +0000 Received: from crushinator.localnet ([IPv6:2601:6:4800:47f:1e4e:1f4d:332c:3bf6]) by resomta-po-06v.sys.comcast.net with comcast id isJ71p00R2JF60R01sJ8M1; Thu, 22 Jan 2015 04:18:08 +0000 From: Matt Whitlock To: Rusty Russell Date: Wed, 21 Jan 2015 23:18:07 -0500 Message-ID: <2955914.eNECdfYQmZ@crushinator> User-Agent: KMail/4.14.3 (Linux/3.16.5-gentoo; KDE/4.14.3; x86_64; ; ) In-Reply-To: <87egqnwt7g.fsf@rustcorp.com.au> References: <87egqnwt7g.fsf@rustcorp.com.au> MIME-Version: 1.0 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" X-Spam-Score: 0.0 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/, no trust [96.114.154.160 listed in list.dnswl.org] 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1YE9Di-0003Oq-Lw Cc: bitcoin-development@lists.sourceforge.net Subject: Re: [Bitcoin-development] [softfork proposal] Strict DER signatures X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 22 Jan 2015 04:18:16 -0000 To be more in the C++ spirit, I would suggest changing the (const std::vector &sig, size_t &off) parameters to (std::vector::const_iterator &itr, std::vector::const_iterator end). Example: bool ConsumeNumber(std::vector::const_iterator &itr, std::vector::const_iterator end, unsigned int len) { // Length of number should be within signature. if (itr + len >= end) return false; // Negative numbers are not allowed. if (*itr & 0x80) return false; // Zero bytes at the start are not allowed, unless it would // otherwise be interpreted as a negative number. if (len > 1 && (*itr == 0x00) && !(*(itr + 1) & 0x80)) return false; // Consume number itself. itr += len; return true; } On Thursday, 22 January 2015, at 11:02 am, Rusty Russell wrote: > Pieter Wuille writes: > > Hello everyone, > > > > We've been aware of the risk of depending on OpenSSL for consensus > > rules for a while, and were trying to get rid of this as part of BIP > > 62 (malleability protection), which was however postponed due to > > unforeseen complexities. The recent evens (see the thread titled > > "OpenSSL 1.0.0p / 1.0.1k incompatible, causes blockchain rejection." > > on this mailing list) have made it clear that the problem is very > > real, however, and I would prefer to have a fundamental solution for > > it sooner rather than later. > > OK, I worked up a clearer (but more verbose) version with fewer > magic numbers. More importantly, feel free to steal the test cases. > > One weirdness is the restriction on maximum total length, rather than a > 32 byte (33 with 0-prepad) limit on signatures themselves. > > Apologies for my babytalk C++. Am sure there's a neater way. > > /* Licensed under Creative Commons zero (public domain). */ > #include > #include > #include > > #ifdef CLARIFY > bool ConsumeByte(const std::vector &sig, size_t &off, > unsigned int &val) > { > if (off >= sig.size()) return false; > > val = sig[off++]; > return true; > } > > bool ConsumeTypeByte(const std::vector &sig, size_t &off, > unsigned int t) > { > unsigned int type; > if (!ConsumeByte(sig, off, type)) return false; > > return (type == t); > } > > bool ConsumeNonZeroLength(const std::vector &sig, size_t &off, > unsigned int &len) > { > if (!ConsumeByte(sig, off, len)) return false; > > // Zero-length integers are not allowed. > return (len != 0); > } > > bool ConsumeNumber(const std::vector &sig, size_t &off, > unsigned int len) > { > // Length of number should be within signature. > if (off + len > sig.size()) return false; > > // Negative numbers are not allowed. > if (sig[off] & 0x80) return false; > > // Zero bytes at the start are not allowed, unless it would > // otherwise be interpreted as a negative number. > if (len > 1 && (sig[off] == 0x00) && !(sig[off+1] & 0x80)) return false; > > // Consume number itself. > off += len; > return true; > } > > // Consume a DER encoded integer, update off if successful. > bool ConsumeDERInteger(const std::vector &sig, size_t &off) { > unsigned int len; > > // Type byte must be "integer" > if (!ConsumeTypeByte(sig, off, 0x02)) return false; > if (!ConsumeNonZeroLength(sig, off, len)) return false; > // Now the BE encoded value itself. > if (!ConsumeNumber(sig, off, len)) return false; > > return true; > } > > bool IsValidSignatureEncoding(const std::vector &sig) { > // Format: 0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash] > // * total-length: 1-byte length descriptor of everything that follows, > // excluding the sighash byte. > // * R-length: 1-byte length descriptor of the R value that follows. > // * R: arbitrary-length big-endian encoded R value. It cannot start with any > // null bytes, unless the first byte that follows is 0x80 or higher, in which > // case a single null byte is required. > // * S-length: 1-byte length descriptor of the S value that follows. > // * S: arbitrary-length big-endian encoded S value. The same rules apply. > // * sighash: 1-byte value indicating what data is hashed. > > // Accept empty signature as correctly encoded (but invalid) signature, > // even though it is not strictly DER. > if (sig.size() == 0) return true; > > // Maximum size constraint. > if (sig.size() > 73) return false; > > size_t off = 0; > > // A signature is of type "compound". > if (!ConsumeTypeByte(sig, off, 0x30)) return false; > > unsigned int len; > if (!ConsumeNonZeroLength(sig, off, len)) return false; > > // Make sure the length covers the rest (except sighash). > if (len + 1 != sig.size() - off) return false; > > // Check R value. > if (!ConsumeDERInteger(sig, off)) return false; > > // Check S value. > if (!ConsumeDERInteger(sig, off)) return false; > > // There should exactly one byte left (the sighash). > return off + 1 == sig.size() ? true : false; > } > #else > bool IsValidSignatureEncoding(const std::vector &sig) { > // Format: 0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash] > // * total-length: 1-byte length descriptor of everything that follows, > // excluding the sighash byte. > // * R-length: 1-byte length descriptor of the R value that follows. > // * R: arbitrary-length big-endian encoded R value. It must use the shortest > // possible encoding for a positive integers (which means no null bytes at > // the start, except a single one when the next byte has its highest bit set). > // * S-length: 1-byte length descriptor of the S value that follows. > // * S: arbitrary-length big-endian encoded S value. The same rules apply. > // * sighash: 1-byte value indicating what data is hashed (not part of the DER > // signature) > > // Accept empty signature as correctly encoded (but invalid) signature, > // even though it is not strictly DER. This avoids needing full DER signatures > // in places where any invalid signature would do. Given that the empty string is > // always invalid as signature, this is safe. > if (sig.size() == 0) return true; > > // Minimum and maximum size constraints. > if (sig.size() < 9) return false; > if (sig.size() > 73) return false; > > // A signature is of type 0x30 (compound). > if (sig[0] != 0x30) return false; > > // Make sure the length covers the entire signature. > if (sig[1] != sig.size() - 3) return false; > > // Extract the length of the R element. > unsigned int lenR = sig[3]; > > // Make sure the length of the S element is still inside the signature. > if (5 + lenR >= sig.size()) return false; > > // Extract the length of the S element. > unsigned int lenS = sig[5 + lenR]; > > // Verify that the length of the signature matches the sum of the length > // of the elements. > if ((size_t)(lenR + lenS + 7) != sig.size()) return false; > > // Check whether the R element is an integer. > if (sig[2] != 0x02) return false; > > // Zero-length integers are not allowed for R. > if (lenR == 0) return false; > > // Negative numbers are not allowed for R. > if (sig[4] & 0x80) return false; > > // Null bytes at the start of R are not allowed, unless R would > // otherwise be interpreted as a negative number. > if (lenR > 1 && (sig[4] == 0x00) && !(sig[5] & 0x80)) return false; > > // Check whether the S element is an integer. > if (sig[lenR + 4] != 0x02) return false; > > // Zero-length integers are not allowed for S. > if (lenS == 0) return false; > > // Negative numbers are not allowed for S. > if (sig[lenR + 6] & 0x80) return false; > > // Null bytes at the start of S are not allowed, unless S would otherwise be > // interpreted as a negative number. > if (lenS > 1 && (sig[lenR + 6] == 0x00) && !(sig[lenR + 7] & 0x80)) return false; > > return true; > } > #endif > > #define COMPOUND 0x30 > #define NOT_COMPOUND 0x31 > > // Len gets adjusted by check() to be actual length with this offset. > #define LEN_OK 0 > #define LEN_TOO_BIG 1 > #define LEN_TOO_SMALL 0xff > > #define INT 0x02 > #define NOT_INT 0x03 > > #define MINIMAL_SIGLEN 1 > #define MINIMAL_SIGVAL 0x0 > > #define NORMAL_SIGLEN 32 > #define NORMAL_SIGVAL(S) S, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, \ > 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, \ > 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, \ > 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f > > // 33 bytes is possible, with 0 prepended. > #define MAXIMAL_SIGLEN 33 > #define MAXIMAL_SIGVAL(S) NORMAL_SIGVAL(S), 0x20 > > #define OVERSIZE_SIGLEN 34 > #define OVERSIZE_SIGVAL(S) MAXIMAL_SIGVAL(S), 0x21 > > #define ZEROPAD_SIGLEN (1 + NORMAL_SIGLEN) > #define ZEROPAD_SIGVAL(S) 00, NORMAL_SIGVAL(S) > > #define SIGHASH 0xf0 > > static bool check(const std::vector &sig) > { > std::vector fixed = sig; > > // Fixup length > if (fixed.size() > 1) > fixed[1] += fixed.size() - 3; > return IsValidSignatureEncoding(fixed); > } > > #define good(arr) assert(check(std::vector(arr, arr+sizeof(arr)))) > #define bad(arr) assert(!check(std::vector(arr, arr+sizeof(arr)))) > > // The OK cases. > static unsigned char zerolen[] = { }; > static unsigned char normal[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char min_r[] = { COMPOUND, LEN_OK, > INT, MINIMAL_SIGLEN, MINIMAL_SIGVAL, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char min_s[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, MINIMAL_SIGLEN, MINIMAL_SIGVAL, > SIGHASH }; > static unsigned char max_r[] = { COMPOUND, LEN_OK, > INT, MAXIMAL_SIGLEN, MAXIMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char max_s[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, MAXIMAL_SIGLEN, MAXIMAL_SIGVAL(0x2), > SIGHASH }; > // As long as total size doesn't go over, a single sig is allowed > 33 bytes > static unsigned char wierd_s_len[] = { COMPOUND, LEN_OK, > INT, OVERSIZE_SIGLEN, OVERSIZE_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char wierd_r_len[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, OVERSIZE_SIGLEN, OVERSIZE_SIGVAL(0x2), > SIGHASH }; > static unsigned char zeropad_s[] = { COMPOUND, LEN_OK, > INT, ZEROPAD_SIGLEN, ZEROPAD_SIGVAL(0x81), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char zeropad_r[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, ZEROPAD_SIGLEN, ZEROPAD_SIGVAL(0x82), > SIGHASH }; > > > // The fail cases. > static unsigned char not_compound[] = { NOT_COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char short_len[] = { COMPOUND, LEN_TOO_SMALL, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char long_len[] = { COMPOUND, LEN_TOO_BIG, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char r_notint[] = { COMPOUND, LEN_OK, > NOT_INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char s_notint[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > NOT_INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char s_oversig[] = { COMPOUND, LEN_OK, > INT, OVERSIZE_SIGLEN, OVERSIZE_SIGVAL(0x1), > INT, MAXIMAL_SIGLEN, MAXIMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char r_oversig[] = { COMPOUND, LEN_OK, > INT, MAXIMAL_SIGLEN, MAXIMAL_SIGVAL(0x1), > INT, OVERSIZE_SIGLEN, OVERSIZE_SIGVAL(0x2), > SIGHASH }; > static unsigned char s_negative[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x81), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char r_negative[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x82), > SIGHASH }; > static unsigned char zeropad_bad_s[] = { COMPOUND, LEN_OK, > INT, ZEROPAD_SIGLEN, ZEROPAD_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char zeropad_bad_r[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, ZEROPAD_SIGLEN, ZEROPAD_SIGVAL(0x2), > SIGHASH }; > static unsigned char missing_sighash[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2) }; > static unsigned char extra_byte[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH, 0 }; > > // Bad signature lengths > static unsigned char zerolen_r[] = { COMPOUND, LEN_OK, > INT, 0, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char zerolen_s[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, 0, > SIGHASH }; > static unsigned char overlen_r_by_1[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN + 1 + 1 + NORMAL_SIGLEN + 1 + 1, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char overlen_s_by_1[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN+1+1, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char underlen_r_by_1[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN-1, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x2), > SIGHASH }; > static unsigned char underlen_s_by_1[] = { COMPOUND, LEN_OK, > INT, NORMAL_SIGLEN, NORMAL_SIGVAL(0x1), > INT, NORMAL_SIGLEN-1, NORMAL_SIGVAL(0x2), > SIGHASH }; > > int main() > { > good(zerolen); > good(normal); > good(min_r); > good(min_s); > good(max_r); > good(max_s); > good(wierd_s_len); > good(wierd_r_len); > good(zeropad_s); > good(zeropad_r); > > // Try different amounts of truncation. > for (size_t i = 1; i < sizeof(normal)-1; i++) > assert(!check(std::vector(normal, normal+i))); > > bad(not_compound); > bad(short_len); > bad(long_len); > bad(r_notint); > bad(s_notint); > bad(s_oversig); > bad(r_oversig); > bad(s_negative); > bad(r_negative); > bad(s_negative); > bad(r_negative); > bad(zeropad_bad_s); > bad(zeropad_bad_r); > bad(zerolen_r); > bad(zerolen_s); > bad(overlen_r_by_1); > bad(overlen_s_by_1); > bad(underlen_r_by_1); > bad(underlen_s_by_1); > bad(missing_sighash); > bad(extra_byte); > > return 0; > } > > > > ------------------------------------------------------------------------------ > New Year. New Location. New Benefits. New Data Center in Ashburn, VA. > GigeNET is offering a free month of service with a new server in Ashburn. > Choose from 2 high performing configs, both with 100TB of bandwidth. > Higher redundancy.Lower latency.Increased capacity.Completely compliant. > http://p.sf.net/sfu/gigenet > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development