Possible overflows and panics in Num256 library

[hannydevelop]

Original Issue

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.

When implementing operations on Uint256 numbers, the library contains two panic! statements here and here, which are implemented via macros and are of the following shape.

let res = a.$method(&b);
if res.bits()  256 {
    panic!("attempt to {} with overflow", stringify!($method));
}

Those macros are used e.g. as follows to implement common operations on numbers:

forward_op! { impl Add for Uint256 { fn add } }
forward_checked_op! { impl CheckedAdd for Uint256 { fn checked_add } }
forward_assign_op! { impl AddAssign for Uint256 { fn add_assign } }


forward_op! { impl Sub for Uint256 { fn sub } }
forward_checked_op! { impl CheckedSub for Uint256 { fn checked_sub } }
forward_assign_op! { impl SubAssign for Uint256 { fn sub_assign } }

The problem with panic statements in a library is that this constitutes an unexpected behavior: the possibility of panics is not documented, and the users don't expect these operations to panic. This also diverges from the standard Rust practice of panicking in debug mode, and wrapping up in release mode. This is not to say that wrapping is better than panicking, but the latter does stop the binary completely, which is not acceptable for the Orchestrator; the preferred way is to use e.g. checked or saturated versions for all operations on numbers.

Orchestrator uses Uint256 pervasively, including additions that can potentially overflow, e.g. in send_to_eth(), TransactionBatch::from_proto(), or should_relay_logic_call(). Due to time constraints, it was not possible to examine all potential overflow (and panicking!) sites.

Problem Scenarios

• A pair of maliciously crafted large Uint256 inputs comes into the Orchestrator:

• their addition triggers a panic;

• Orchestrator stops, possibly casing validators to get slashed for not signing the Gravity Bridge operations.

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, which provides e.g. checked and saturated versions for all operations.

Considering the example of primitive types U256 datatype, presence of such operations as checked_add(), overflowing_add(), and saturating_add() provides enough possibilities for safe usage of a numeric library in many contexts:

• in simple scenarios, replacing simple addition by saturating_add() should work;

• in more complex cases, e.g. when several operations are used in a row using overflowing_add() and combining the returned flags with or should enable both relatively simple usage patterns, and safety;

• in cases where the case analysis is needed (e.g. when the addition happens within an operation returing Result), using checked_add and passing the None option up the stack should be a good design pattern.

[tony-iqlusion]

As with #263, I can suggest crypto-bigint as an alternative:

https://docs.rs/crypto-bigint/

It has well-defined semantics for wrapping and checked arithmetic, achieving the later in constant time.

If need be, saturating arithmetic can also be added.