First Flight #8: Math Master
First Flight #8
Beginner FriendlyFoundry
100 EXP
View results
Previous Next
Submission Details
Severity: high
Valid

Incorrect bitwise comparison can lead to calculation errors

ceseshi

Summary

The sqrt() function incorrectly compares bit values, which will result in an incorrect calculation for certain input values.

Vulnerability Details

The function compares whether the shifted value is less than 16777002, which corresponds to 1111_1111_1111_1111_111111_0010_1010, but the correct value would be 16777215, or 1111_111111_111111_111111_111111_1111_111111_1111. This will cause incorrect calculations with certain input values.

// This segment is to get a reasonable initial estimate for the Babylonian method. With a bad
// start, the correct # of bits increases ~linearly each iteration instead of ~quadratically.
let r := shl(7, lt(87112285931760246646623899502532662132735, x))
r := or(r, shl(6, lt(4722366482869645213695, shr(r, x))))
r := or(r, shl(5, lt(1099511627775, shr(r, x))))
// Correct: 16777215 0xffffff
@> r := or(r, shl(4, lt(16777002, shr(r, x))))
z := shl(shr(1, r), z)
​
// There is no overflow risk here since `y < 2**136` after the first branch above.
z := shr(18, mul(z, add(shr(r, x), 65536))) // A `mul()` is saved from starting `z` at 181.```

Impact

The function will return incorrect calculations, which may lead to loss of funds if used in monetary transactions.

Tools Used

Foundry, Manual review

Recommended Mitigation

Correct the comparison value.

// This segment is to get a reasonable initial estimate for the Babylonian method. With a bad
// start, the correct # of bits increases ~linearly each iteration instead of ~quadratically.
let r := shl(7, lt(87112285931760246646623899502532662132735, x))
r := or(r, shl(6, lt(4722366482869645213695, shr(r, x))))
r := or(r, shl(5, lt(1099511627775, shr(r, x))))
// Correct: 16777215 0xffffff
- r := or(r, shl(4, lt(16777002, shr(r, x))))
+ r := or(r, shl(4, lt(16777215, shr(r, x))))
z := shl(shr(1, r), z)
​
// There is no overflow risk here since `y < 2**136` after the first branch above.
z := shr(18, mul(z, add(shr(r, x), 65536))) // A `mul()` is saved from starting `z` at 181.```
Updates

Lead Judging Commences

inallhonesty Lead Judge over 1 year ago
Submission Judgement Published
Validated
Assigned finding tags:

Sqrt yields incorrect results for certain inputs because 16777002 doesn't represent the maximum value resulting from a right shift

Support

FAQs

Can't find an answer? Chat with us on Discord, Twitter or Linkedin.