decodeBytes is susceptible to an overflow bug sneak and can incur an OOM or runtime panic due to unproperly checked size on both 32-bit and 64-bit architectures

[odeke-em]

Reading through the code in encoding.go, we've got this interesting pattern of code

iavl/encoding.go

Lines 15 to 25 in f5c104d

	size, n, err := decodeUvarint(bz)
	if err != nil {
	return nil, n, err
	}
	if int(size) < 0 {
	return nil, n, fmt.Errorf("invalid negative length %v decoding []byte", size)
	}
	if len(bz) < n+int(size) {
	return nil, n, fmt.Errorf("insufficient bytes decoding []byte of length %v", size)
	}
	bz2 := make([]byte, size)

In that code block, you'll notice that:
a) size, n, err := decodeUvarint(bz []byte) (uint64, int, error) --> size is a uint64 containing the size aka length of the buffer to be allocated
b) To check for overflows, we use int(size): which checks if uint64->int returns a negative value
c) Unfortunately: make([]byte, size) uses the plain uint64 value unfettered and unchecked

Point b) masks a problem with overflows; Point c) is where the problem is, and to cause this disruption, I can Uvarint encode any size larger than 32-bit ranges, the overflow will wrap around to it and given the fallacious check yet naked transmission to make, it'll panic with out of memory

Implications

Given that int's range is (-2147483648 to 2147483647) on 32-bit systems, and (-9223372036854775808 to 9223372036854775807) on 64-bit systems, on 32-bit systems, any value with a wrap around of greater than (1<<32), e.g. (int32(uint64(1<<32)+2)) == 2; will return that value so to falsely make all those checks pass and then poison the code with an OOM or runtime panic, I can do this

package iavl

import (
        "encoding/binary"
        "testing"
)       
        
func TestDecodeBytesBlow(t *testing.T) {
        // Attack works on a 32-bit computer, and causes an OOM.
        buf := make([]byte, 1<<63-1)
        _ = binary.MaxVarintLen64
        n := binary.PutUvarint(buf, (1<<33)+2)
        // n:    ~> 5
        // size: ~> 2, given that on a 32-bit computer: int(uint64(1<<33)+2) == 2 :-(
        nx := copy(buf[n:], "abcde")
        println("n+nx", n+nx)
        if _, _, err := decodeBytes(buf); err == nil {
                t.Fatal("Failed to decode bytes")
        }
}

Recommendation

For robust checks we can do the following:
a) Ensure that size never exceeds the max value of int on either of 32-bit or 64-bit architecures
b) Ensure that make receives the same truncation used, so size is passed in as int(size) -- in fact just the lone change would have masked the problem

diff --git a/encoding.go b/encoding.go
index 27c10fe..40c9d73 100644
--- a/encoding.go
+++ b/encoding.go
@@ -19,10 +19,14 @@ func decodeBytes(bz []byte) ([]byte, int, error) {
 	if int(size) < 0 {
 		return nil, n, fmt.Errorf("invalid negative length %v decoding []byte", size)
 	}
+	// ^uint(0) >> 1 will help determine the max int value variably on 32-bit and 64-bit machines.
+	if size >= uint64(^uint(0)>>1) {
+		return nil, n, fmt.Errorf("invalid out of range length %v decoding []byte", size)
+	}
 	if len(bz) < n+int(size) {
 		return nil, n, fmt.Errorf("insufficient bytes decoding []byte of length %v", size)
 	}
-	bz2 := make([]byte, size)
+	bz2 := make([]byte, int(size))
 	copy(bz2, bz[n:n+int(size)])
 	n += int(size)
 	return bz2, n, nil

I believe this is a high value DOS vector that can take down various components

[odeke-em]

Kindly /cc-ing @alessio @alexanderbez @aaronc @erikgrinaker.

[erikgrinaker]

Good catch, thanks! Opened #340 for this.

[odeke-em]

Thank you for the fix @erikgrinaker! Actually I just re-ran some thoughts and also fuzzed and alas identified a vector that crashes as well with the same runtime out of range error when the length is saved as 9223372036854775806 and it cleverly circumvents the checks given that the code

 if len(bz) < n+int(size) { 
 	return nil, n, fmt.Errorf("insufficient bytes decoding []byte of length %v", size) 
 } 

n+int(9223372036854775806) on 64-bit systems --> -X
e.g. if n = 9, we get size 9223372036854775806 int(size) 9223372036854775806 n 9 len(bz) 9 -9223372036854775801.

However, the PR #340 does fix this problem, thus I'd like to retitle this bug as for both 32-bit and 64-bit systems aka agnostic and we should perhaps issue updates to code using this ASAP.

For reference: it took me 10min-1hr(writing repros, examining call sites) to mentally calculate through this problem but it took the fuzzer less than 1 second to find it, thus more reason to fuzz our code :-) You'll like this @okwme

[erikgrinaker]

You're right, thanks again for this.

This bug was introduced with 0.15.0, which was released three weeks ago, and is not used in any stable Cosmos SDK releases. Also, this can only be exploited via ValueOpDecoder and AbsenceOpDecoder, and the Cosmos SDK no longer uses these (it uses commitment proofs instead). The other uses of decodeBytes() are only for internal database data, and can only be exploited by a user with write access to the database file.

I've submitted updated release notes in #346, and pinged the SDK team.

[odeke-em]

Thank you @erikgrinaker for the proactive, fast action, and for all your work!

[erikgrinaker]

Sigh, the previous "fix" for decodeBytes() overflow had another overflow bug. 🤦‍♂️ Specifically the left-hand addition here:

if uint64(n)+s >= uint64(^uint(0)>>1) {
	return nil, n, fmt.Errorf("invalid out of range length %v decoding []byte", uint64(n)+s)
}

Which of course can overflow such that the sum is less than both n and the max integer. This then causes an out of bounds error where we're taking a slice of e.g. bz[n:n+(-3)].

Submitted another fix in #347, would appreciate a review.

[odeke-em]

Sounds good, thank you @erikgrinaker. For testing we can do:
a) binary.PutUvarint(1<<63-2), bz=9 random bytes
b) The seed I provided in the original bug report above