Numbers turned weapons: DoS in Osmosis’ math library

Malware News
1

By Sam Alws

Trail of Bits is publicly disclosing a vulnerability in the Osmosis chain that allows an attacker to craft a transaction that takes up a disproportionate amount of compute time on Osmosis nodes compared to the amount of gas it consumes. Using the vulnerability, an attacker can halt the Osmosis chain by spamming validators with these transactions. After we informed the Osmosis developers about this bug, they performed a hard fork that fixed the vulnerability, avoiding the attack.

Osmosis is a Cosmos chain with native functionality for swap pools. Users exchange hundreds of thousands of dollars of value daily on Osmosis’ pools. Naturally, these pools need to perform a significant amount of fairly precise calculations, and that’s where our bug comes in.

The vulnerability

We found the vulnerability in Osmosis’ math library, which is used to give approximate answers to mathematical functions. In particular, the bug affected their exponentiation function. A Taylor series approximation was used to calculate ab:

Note the “…” at the end: since we’re working with computers and have only a finite amount of time to do this calculation, we need to choose when to stop. An intuitive choice here would be to stop when the terms we’re adding onto the end are sufficiently small; once that happens, we know we’re “close enough” to the real answer. This is exactly what the Osmosis developers did. Here’s a pseudocode version of their implementation:

// calculate a^b
// assumption: a is between 0 and 2, b is between 0 and 1
fn PowApprox(a,b) {
  total <- 1
  i <- 0
  term <- 1
  const precision = 0.00000001
  // (the real implementation took precision as a function parameter rather than a constant)
  while abs(term) >= precision {
    i <- i + 1
    term <- term * ((b-(i-1)) / i) * (a-1)
    total <- total + term
  }
  return total
}

However, there’s a problem with this implementation. The while loop runs until term is sufficiently small, but it does not have a bound on the maximum number of iterations. If we hand-pick values of a and b, we can make this loop take a very large number of iterations to terminate. In particular, calculating 1.999999999999990.1 using PowApprox takes over two million iterations, running for over 800 milliseconds on an M1 processor.

This very long runtime is not accounted for in the gas costs of transactions that use the PowApprox function. This means that if an attacker can craft a transaction that calls PowApprox(1.99999999999999, 0.1), they can take up just under a second of runtime on an Osmosis node without having to pay very much gas in exchange. By doing this repeatedly, they can bring the whole chain to a halt.

Luckily for the attacker, such a transaction does exist. There is a call to PowApprox in the following piece of code, used in Osmosis to calculate the amount of shares to give when someone deposits tokens into a swap pool:

shares_to_give = current_total_shares * (1 -
PowApprox(((current_total_tokens + tokens_added) /
current_total_tokens), token_weight))

(Note: the real implementation uses a different function called Pow, which is essentially just a wrapper around PowApprox that makes sure that all the inputs are in the correct range)

So if an attacker makes a pool where tokenA has a weight of 0.1, initializes it with 1.0 tokenA, and then deposits 0.99999999999999 more of tokenA, they can trigger the long calculation in PowApprox. By repeatedly depositing and withdrawing this 0.99999999999999 tokenA, they can get the Osmosis nodes stuck calculating PowApprox over and over, and halt the chain!

A simple solution

Luckily, the fix for this problem was very simple: limit the number of loop iterations, and revert the transaction if the limit is reached. Osmosis’ recent hard fork pushed this fix, preventing the attack. As for how to prevent similar bugs from popping up elsewhere, our recommendation is simple: fuzzing. Testing the PowApprox function with a 100ms timeout using gofuzz would’ve quickly detected the bug. Go’s native fuzzer also detects the bug when a 10ms timeout is used instead.

We reported the vulnerability to the Osmosis team on September 6, 2023. A PR containing the fix was merged on October 6, 2023, and a hard fork applying this fix was performed on October 23, 2023.

We would like to thank the Osmosis team for working swiftly with us to address these issues.

Article Link: Numbers turned weapons: DoS in Osmosis’ math library | Trail of Bits Blog