Computational load attacks via Num256 parsing

[andrey-kuprianov]

Surfaced from @informalsystems audit of Althea Gravity Bridge at commit 19a4cfe

severity: High
type: Implementation bug
difficulty: Unknown

Involved artifacts

• Orchestrator
• num256 library

Description

Orchestrator uses the num256 library in many places, both directly, and indirectly via the Deep Space library, web30 library, or Clarity library, all developed by Althea.

A typical usage of the num256 library library is as follows:

let valset_nonce_data = &input.topics[1];
let valset_nonce = Uint256::from_bytes_be(valset_nonce_data);
if valset_nonce > u64::MAX.into() {
    return Err(GravityError::InvalidEventLogError(
        "Nonce overflow, probably incorrect parsing".to_string(),
    ));
}
let valset_nonce: u64 = valset_nonce.to_string().parse().unwrap();

What num256 library is supposed to do, is to introduce 256-bit types, namely Uint256 and Int256, and to provide operations on them. There are several problems with the library implementation though, that we outline below:

Unbounded representation

The first problem is how e.g. Uint256 is implemented:

pub struct Uint256(pub BigUint);


impl Uint256 {
    pub fn from_bytes_le(slice: &[u8]) -> Uint256 {
        Uint256(BigUint::from_bytes_le(slice))
    }
    pub fn from_bytes_be(slice: &[u8]) -> Uint256 {
        Uint256(BigUint::from_bytes_be(slice))
    }
    pub fn from_str_radix(s: &str, radix: u32) -> Result<Uint256, ParseBigIntError> {
        BigUint::from_str_radix(s, radix).map(Uint256)
    }
    /// Converts value to a signed 256 bit integer
    pub fn to_int256(&self) -> Option<Int256> {
        self.0
            .to_bigint()
            .filter(|value| value.bits() <= 255)
            .map(Int256)
    }
}

As can be seen Uint256 is just a wrapper around big (unbounded) integers; this is very misleading when reading and analyzing the code, and may lead to serious bugs.

Computational attacks possible

The unbounded representation, combined with possible parsing from unbounded strings via e.g. the function from_bytes_be(), which is used in the Gravity Bridge to parse Ethereum logs, this can lead to the computational load explosion when parsing the numbers.

We have tested and confirmed that parsing Uint256 using from_bytes_be() takes quadratic time wrt. the input length. This can open the way to attacks on Orchestrator via crafted big inputs.

It is still the open question whether all inputs are restricted in length or not (we have not been able to verify this due to the time constraints), but the possibility of unbounded inputs does seem to exist; see the code sample above.

Problem Scenarios

• A maliciously crafted input with very large number representation comes into the Orchestrator, where Uint256 is expected:
  • it is parsed using Unit256::from_bytes_be() or a similar function, with quadratic computation costs wrt. input size
  • Processing takes such amount of time, that Orchestrator becomes too slow to process other requests;
  • this may also result in the whole validator node failing to participate in consensus.

Recommendation

• Rework the num256 library library to make it safe;
• Alternatively (and preferably) switch to one of the established and well-designed libraries to deal with 256-bit numbers, such as primitive-types.