Blog Post
Nethermind ModExp Out of Memory Consensus Issue
December 2, 2022
## Introduction
On 14 October 2022, [Jason Matthyser](https://twitter.com/pleasew8t), a security researcher at iosiro, identified a bug within the Nethermind client that could lead to a consensus failure. The issue was reported to the Ethereum Foundation, who worked with the Nethermind to fix the bug before it was released into production, ensuring that no funds were at risk. Both the Ethereum Foundation and Gnosis awarded bounties for the bug.
## ModExp Precompile
The `ModExp` (modular expression) precompile, callable at address `0x05`, allows EOA’s and smart contracts to compute the formula `(base ^ exponent) % modulus` using values for `base`, `exponent`, and `modulus` of very large sizes.
### How does it work?
As with all Ethereum precompiles, the `calldata` does not contain any function signatures, and is simply a byte array that gets parsed to extract the values for `base`, `exponent`, and `modulus`. An example payload for the `ModExp` precompile looks something like this:
```markdown
00000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100020205
```
Let’s dissect this. So, the first 96 bytes (the header) of the payload are three `uint256` values indicating the length, in bytes, of `base`, `exponent`, and `modulus`. Applying this to the above payload, we get:
```markdown
base length = 0x02
exponent length = 0x01
modulus length = 0x01
```
For `base length`, this means the 2 bytes succeeding the 96-byte header (the body) represents the `base`. Similarly, `exponent` would then be represented by the first byte after `base`, and `modulus` the first byte after `exponent`. Applying this to the last 4 bytes of the payload yields:
```markdown
payload body = 00020205
base = 0x0002 = 2
exponent = 0x02 = 2
modulus = 0x05 = 5
(base^exponent) mod modulus = (2^2) mod 5 = 4
```
### And gas costs?
As properties like `base length`, `exponent length`, and `modulus length` eventually lead to allocation of memory, and can present varying complexity, there is a dynamic cost associated with executing the `ModExp` precompile. The calculation in itself is a bit lengthy, but for the purpose of this write-up, it can roughly be described as:
```markdown
complexity = ( ceil( max(baseLength, modulusLength)/8 ) )^2
iterations = max(f(exponentLength, exponent), 1)
gas = max( complexity * iterations, 200 )
```
As can be seen above, complexity is a function of `base length` and `modulus length`, whereby the larger of the two is divided by 8 and then squared. The amount of iterations is then calculated as the maximum between some function of `exponent length` and the `exponent` itself, and 1. The exact function `f(exponentLength, exponent)` is a bit of a mouth full to type out here, but can be read at [ModExpPrecompile.cs#L202](https://github.com/NethermindEth/nethermind/blob/220cc8a077c99ce304f08fce7769872259588f87/src/Nethermind/Nethermind.Evm/Precompiles/ModExpPrecompile.cs#L202).
The gas calculation is important, as will become evident soon.
## Bug Details
At a high level, any EVM instruction or precompile that gets executed will first have the gas cost associated with the operation calculated, the gas deducted from the account that launched the transaction, and then executed. The gas calculation function for the `ModExp` precompile in Nethermind can be found [here](https://github.com/NethermindEth/nethermind/blob/220cc8a077c99ce304f08fce7769872259588f87/src/Nethermind/Nethermind.Evm/Precompiles/ModExpPrecompile.cs#L56), and the actual implementation [here](https://github.com/NethermindEth/nethermind/blob/220cc8a077c99ce304f08fce7769872259588f87/src/Nethermind/Nethermind.Evm/Precompiles/ModExpPrecompile.cs#L118). We’ll ignore the gas calculation for now.
### Memory Allocation
An excerpt of the implementation, the `ModExp` `Run` function, is shown below. The function calls `GetInputLengths()`, supplying it `inputData`, the `calldata` to the precompile. This extracts `baseLength`, `expLength`, and `modulusLength`. It then calls `SliceWithZeroPaddingEmptyOnError()`, which accepts the `offset` into `inputData` as its first argument, and then the `length` of bytes to copy from `inputData` into a newly-created buffer of size `length`.
```csharp
(int baseLength, int expLength, int modulusLength) = GetInputLengths(inputData);
// omitted for brevity, but does the same for base and mod that it does for exponent:
byte[] expData = inputData.Span.SliceWithZeroPaddingEmptyOnError(
96 + baseLength, expLength);
using mpz_t expInt = ImportDataToGmp(expData);
if (gmp_lib.mpz_sgn(modulusInt) == 0)
{
return (new byte[modulusLength], true);
}
```
Within the `SliceWithZeroPaddingEmptyOnError()` function (shown below), an interesting thing happens. First, if there is at least 1 byte to copy from `bytes`, `codeFragmentLength` will be `> 0`, passing the first `if-statement`. Second, if the if-statement is passed, it creates a new `byte` array of length `length`.
```csharp
public static byte[] SliceWithZeroPaddingEmptyOnError(
this byte[] bytes,
int startIndex,
int length)
{
int copiedFragmentLength = Math.Min(bytes.Length - startIndex, length);
if (copiedFragmentLength <= 0)
{
return Array.Empty<byte>();
}
byte[] slice = new byte[length];
Buffer.BlockCopy(bytes, startIndex, slice, 0, copiedFragmentLength);
return slice;
}
```
This is interesting for two reasons, the first being `length` is controllable by passing large enough values for either `baseLength`, `expLength`, or `modulusLength` in the precompile payload. If a large enough value is specified, this will result in an `Out of Memory` exception, which will be caught in the Nethermind precompile execution loop, and return empty data as the call result and set the success of the call to false. This can be seen at [VirtualMachine.cs#L587](https://github.com/NethermindEth/nethermind/blob/220cc8a077c99ce304f08fce7769872259588f87/src/Nethermind/Nethermind.Evm/VirtualMachine.cs#L587).
The second, which is also the bug that was reported to Ethereum Foundation, is that the `Run` function executes the allocation logic before a very crucial early-exit condition, `if (gmp_lib.mpz_sgn(modulusInt) == 0)`. This condition checks if the `modulus` supplied is zero and, if so, returns with an empty buffer of size `modulusLength` and a success status of true. This order differs from other clients, such as Geth (see [contracts.go#L363](https://github.com/ethereum/go-ethereum/blob/fb75f11e87420ec25ff72f7eeeb741fa8974e87e/core/vm/contracts.go#L363)
) and Besu (see [BigIntegerModularExponentiationPrecompiledContract.java#L57](https://github.com/hyperledger/besu/blob/e9f979ebd3ab338682c603bfa31e162c741eee43/evm/src/main/java/org/hyperledger/besu/evm/precompile/BigIntegerModularExponentiationPrecompiledContract.java#L57)
), which won’t throw exceptions before reaching their first early-exit condition.
As a result, if a payload can be created that triggers the overflow in Nethermind, and triggers the early-exit in other clients, the results will be as follows:
- Nethermind returns empty data, but `success = false`
- Other clients return empty data, but `success = true`
In this condition, a split occurs whereby Nethermind reaches a different conclusion, and thereby breaking consensus between it and other clients.
## Exploitation
Consider the calculation of gas for various inputs that might cause an `Out of Memory` exception. `baseLength`, `modulusLength` or `expLength` would need to be sufficiently high. The gas required for any of these three cases could be calculated as follows:
- Assume `baseLength = 0xffffffff, modulusLength = 0, expLength = 0`, which would result in `gas = 288230376151711744`, which would require too much gas, and exploitation is prevented.
- Assume `baseLength = 0, modulusLength = 0xffffffff, expLength = 0`, which would result in `gas = 288230376151711744`, which would require too much gas, and exploitation is prevented.
- Assume `baseLength = 0, modulusLength = 0, expLength = 0xffffffff`, which results in `complexity = 0`, and as a result `complexity * iterations = 0`, and therefore the `gas` is only `200`.
In the third case, a very large value can be specified for `exponent length`, but keeping `base lengh` and `modulus length` zero would result in a gas cost of `200`. This is perfect for exploitation, as `base length` and `modulus length` being zero would definitely trigger the early-exit in other clients, and trigger the `Out of Memory` exception in Nethermind for as little as `200` gas.
Hold up! The Ethereum tests, used to ensure compliance across the different Ethereum clients, has a test case for exactly this [here](https://github.com/ethereum/tests/pull/220). So what gives? Well, an important caveat of the memory allocation is that memory allocation only occurs if there are bytes to copy from the input. Consider the test case from the Ethereum tests repo:
```
000000000000000000000000000000000000000000000000000000000000000080000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
base length = 0
exponent length = 0x8000000000000000000000000000000000000000000000000000000000000000
modulus length = 0
```
The total payload size is 96 bytes. This means that there are no bytes succeeding the header, and despite a really large value for `exponent length`, with no actual bytes to copy, the `SliceWithZeroPaddingEmptyOnError()` will simply return an empty array.
So to anticlimactically remedy this and have a working payload, we can simply add an additional byte to the end of the payload:
```
00000000000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000041
```
## Remediation
This vulnerability was remediated in [this]([https://github.com/NethermindEth/nethermind/pull/4774/files](https://github.com/NethermindEth/nethermind/pull/4774/files)) PR. It makes some changes, bringing it in-line with other clients. Most importantly, the fix defers allocation of memory until after certain early-exit conditions. It also adjusts the maximum memory allocated for the exponent to .NET’s `Array.MaxLength` to avoid an `OutOfMemory` exception.
## Impact
The most notable networks using Nethermind as an official client are Ethereum and Gnosis Chain.
### Ethereum
If the issue were to be exploited on Ethereum, stakers running the vulnerable version of Nethermind would fall out of sync with the canonical chain and likely be penalized as they would fail to participate in validation or generate any new blocks.
The official channel for reporting bugs in Ethereum clients is through the Ethereum Foundation. The Ethereum Foundation uses the [OWASP risk rating model]([https://owasp.org/www-project-risk-assessment-framework/](https://owasp.org/www-project-risk-assessment-framework/)) to determine risk levels. The impact is determined based on the impact to the Ethereum network, which is based on current network conditions, including network share. The payouts for the various risk levels are given below.
According to the OWASP risk rating model, the Ethereum Foundation rated the consensus bug as:
- High likelihood - as it very likely to enter production and was trivial to exploit.
- Low impact - due to Nethermind’s relatively small network share of 6.2% of Ethereum mainnet at the time of reporting.
As a result, an overall rating of *medium* was given and a bounty of $10,000 paid.
### Gnosis Chain
Nethermind is currently the [only client on the Gnosis Chain network]([https://ethstats.gnosischain.com/](https://ethstats.gnosischain.com/)). An interesting note here is that nodes appear to run various versions of Nethermind.
This means that while there is only one client type, a well-timed attack could very likely have led to a chain split between different versions of the client. Given all the variables involved, it would be hard to quantify the economic impact of such an event, but some factors to consider would be:
- Downtime of the network until a hard-fork to correct the state is developed and rolled out.
- Potential [inactivity leak]([https://ethereum.org/en/developers/docs/consensus-mechanisms/pos/rewards-and-penalties/](https://ethereum.org/en/developers/docs/consensus-mechanisms/pos/rewards-and-penalties/)) that would penalize all nodes in the network.
- Second-order effects from protocols running on top of Gnosis Chain, e.g. double-spend bridge withdrawals or delays in time sensitive functionality (e.g. Oracle updates).
- The reputational damage to the brand of Gnosis and the effect thereof on GNO.
Gnosis Chain runs [their bug bounty program]([https://immunefi.com/bounty/gnosischain/](https://immunefi.com/bounty/gnosischain/)) through the popular bug bounty platform [Immunefi]([https://immunefi.com/](https://immunefi.com/)). The rewards are structured as follows:
The scope of their program is currently limited to a few of their smart contracts, without specific mention of whether attacks on their client software would be considered in-scope. After reaching out to the Gnosis team, they acknowledged the issue and awarded a bounty of $5,000.
## Conclusion
We are grateful to the Ethereum Foundation and Nethermind for handling the report with immediate urgency and keeping us updated along the way (*especially given our unfortunate timing of disclosing the issue during DevCon* 😅). We are also thankful to Gnosis for awarding an additional bounty, as well as [Immunefi](https://immunefi.com/) for helping us get in contact with them.
