Overflowing while reading can create "phantom numbers" which can possibly cause corrupt/incorrect output

[luavixen]

I'm currently using leb128 to read LEB128-encoded numbers from a stream of data (TcpStream) and I encountered a serious bug that caused my application to generate corrupt/incorrect output and could possibly allow for a DoS attack (in my case).

To describe this bug, assume that cursor is my TcpStream and that I am attempting to read TWO (2) LEB128-encoded numbers from it.

Without an overflow, this library works fine:

let mut cursor = std::io::Cursor::new(vec![
  0b1000_0011, 0b0010_1110,              // 5891
  0b1110_0100, 0b1110_0000, 0b0000_0010, // 45156
]);

for call in 1..4 {
  println!("Call #{}: {:?}", call, leb128::read::unsigned(&mut cursor));
}
// Call #1: Ok(5891)  // Number one
// Call #2: Ok(45156) // Number two
// Call #3: Err(IoError(Custom { kind: UnexpectedEof, error: "failed to fill whole buffer" }))

However, when an overflow occurs while reading a very long LEB128 value, a phantom 3rd number appears!

let mut cursor = io::Cursor::new(vec![
  0b1111_1111, 0b1111_1111, 0b1111_1111, 0b1111_1111,
  0b1111_1111, 0b1111_1111, 0b1111_1111, 0b1111_1111,
  0b1111_1111, 0b1111_1111, 0b0111_1111, // Overflow!
  0b1110_0100, 0b1110_0000, 0b0000_0010, // 45156
]);

for call in 1..5 {
  println!("Call #{}: {:?}", call, leb128::read::unsigned(&mut cursor));
}

// Call #1: Err(Overflow) // Number one
// Call #2: Ok(127)       // Where did you come from??
// Call #3: Ok(45156)     // Number two
// Call #4: Err(IoError(Custom { kind: UnexpectedEof, error: "failed to fill whole buffer" }))

This happens because both leb128::read::signed and leb128::read::unsigned exit early if an overflow occurs:

pub fn unsigned<R>(r: &mut R) -> Result<u64, Error>
where
    R: io::Read,
{
    let mut result = 0;
    let mut shift = 0;

    loop {
        let mut buf = [0];
        r.read_exact(&mut buf)?;

        if shift == 63 && buf[0] != 0x00 && buf[0] != 0x01 { // <<<<<<<<<<<<<<<<
            return Err(Error::Overflow);                     // <<<<<<<<<<<<<<<<
        }                                                    // <<<<<<<<<<<<<<<<

        let low_bits = low_bits_of_byte(buf[0]) as u64;
        result |= low_bits << shift;

        if buf[0] & CONTINUATION_BIT == 0 {
            return Ok(result);
        }

        shift += 7;
    }
}

The condition that causes return Err(Error::Overflow); to execute can evaluate to true before the entire LEB128 value has been read, leaving behind extra bytes that can cause serious issues.

[philipc]

For most uses, it is expected that overflows are abnormal and if they occur then that is an indication that the input data is corrupted and cannot be reliably read anyway. That is, if the corruption caused an overflow, how can you be sure where the LEB128 value really ends? If your TCP sender is deliberately producing values that overflow, then it might be better to change that behaviour instead.

I don't think your DoS concern is a valid reason to change this. If an attacker can cause this situation to occur, then they could just as easily cause a situation where there are more numbers than you expect. You should be designing your application to handle this anyway.

The error handling could be changed to keep reading bytes until the continuation bit is clear, but I'm unsure what the behaviour should be if a read error then occurs while doing that.

[luavixen]

You should be designing your application to handle this anyway.

You're right! I'm currently trying to un-f**k a webservice that someone wrote and its filled with bugs and hacks, so better designed applications will hopefully fail much more gracefully.

For most uses, it is expected that overflows are abnormal and if they occur then that is an indication that the input data is corrupted and cannot be reliably read anyway.

My application is receiving values from a Node.js service (which is receiving it's value from the client's browser), and on the JavaScript side all the numbers are stored as BigInts, which do not overflow (apparently the limit is a few gigabytes worth of bits?) and all the LEB128 intercommunication on that side works fine. These numbers may be larger than u64::MAX, but they are still valid LEB128 integers and produce correct output when used with other libraries/languages. It would make sense to read the entire LEB128 value instead of cutting it up and potentially causing issues.

The error handling could be changed to keep reading bytes until the continuation bit is clear, but I'm unsure what the behaviour should be if a read error then occurs while doing that.

I think that a good approach would be to store the "overflow state" in a boolean variable and then to continue processing the entire LEB128 value as if there was no overflow. The overflow boolean can then be checked when the function is about to return.

[luavixen]

I've come up with a new solution that involves a simple while loop that reads until the end of the LEB128 value, meaning that valid LEB128-encoded values cannot be accidentally split in half, even if they are too big to fit into a u64. See my pull request here: https://github.com/gimli-rs/leb128/pull/15