N out of M
December 25, 2023•1,068 words
The Audit
In one of our most recent security reviews at Inference, we run into an interesting situation, which is discussed in this blog post.
The premise is that of a smart contract with a simple access control mechanism:
In order to change a storage variable, you have to be in possession of at least N out of M passwords
This is a gigantic simplification of the original situation, however, it will help to discuss the interesting bug without getting lost in unnecessary details.
The Smart Contract
A basic version of the contract, stripped out of all other complications and anonymized, is shown here:
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;
contract nOutOfM {
//the variable any user can change, provided they have at least N out of M passwords
uint256 public variable_to_change;
//the list of allowed passwords
bytes[] passwords;
//the number N < M such that a user is allowed to change the first variable
uint256 public minimum_passwords_required;
constructor(uint256 start_value, uint256 min_req ) {
//first, let's populate the passwords array
passwords.push(bytes("password"));
passwords.push(bytes("home"));
passwords.push(bytes("123456"));
passwords.push(bytes("h4ck3r"));
passwords.push(bytes("s3cur3"));
//additionally, let's set a starting value for the variable, and the number of required passwords
variable_to_change = start_value;
minimum_passwords_required = min_req;
}
//this functions allows to modify the `variable_to_change`, provided a user submits enough passwords
function modify(uint256 new_proposed_value, bytes[] calldata submitted_passwords) public {
uint256 number_of_passwords = 0;
uint256 param_length = submitted_passwords.length;
uint256 allowed_length = passwords.length;
for(uint i = 0; i < param_length; ++i){
for(uint j = 0; j < allowed_length; ++j){
if(keccak256(passwords[j]) == keccak256(submitted_passwords[i])) number_of_passwords++;
}
}
if(number_of_passwords >= minimum_passwords_required) variable_to_change = new_proposed_value;
}
}
The comments and the very simple code should be fairly clear. However, the briefest of summaries could be that:
- there is a storage variable that can be changed
- in order to change the variable, it is necessary to submit enough (N out of M) passwords, from a list of known passwords that (for simplification) is stored in the contract
So, what is wrong with this?
The Bug
Note: the bug has nothing to do with the length of the various arrays, or with the fact that everything on the blockchain is readable. Any issue related to these is due to the gigantic simplification applied to present this smart contract in a brief, understandable manner.
So, if you want to take some more time, do not read the next line ;)
So, the bug.
What if I told you that this access control mechanism does not require N out of M passwords, but just ONE?
Indeed, it does.
If you look again at the check before updating the value, you can quickly notice that it checks, for each element submitted by the user, if it is contained in the list of allowed passwords: if it is, it increments the counter.
So what happens if a smart user submits N times the same password? Right, the counter is updated N times, meaning the smart user is now allowed to change the variable even though they did not know enough passwords!
This mechanism is shown in the test suite shown here.
You can see a first test, to check the expected behavior of the contract, in case a user submits enough (diverse) passwords.
After that, the malicious test is implemented, where the user submits enough passwords, except...they are all the same one!
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;
import {Test, console2} from "forge-std/Test.sol";
import {nOutOfM} from "../src/nOutOfM.sol";
contract nOutOfMTest is Test {
nOutOfM public example_contract;
//the list of passwords to submit
bytes[] passwords;
function setUp() public {
//create a new example contract, whose starting value is 0.
//the contract requires at least 3 passwords in order to change the value
example_contract = new nOutOfM(0, 3);
//we initialize this list with three passwords, so that they are enough to change the value in the contract
passwords.push(bytes("home"));
passwords.push(bytes("h4ck3r"));
passwords.push(bytes("s3cur3"));
}
function test_ValidChange() public {
example_contract.modify(10, passwords);
assertEq(example_contract.variable_to_change(), 10, "Value was not correctly updated");
}
function test_BypassCheck() public {
passwords.pop();
passwords.pop();
//now, passwords only contains a single password, home
passwords.push(bytes("home"));
passwords.push(bytes("home"));
//after these two additions, it contains 3 passwords, but they are all the same!
example_contract.modify(10, passwords);
assertEq(example_contract.variable_to_change(), 10, "Value was not correctly updated");
}
}
Sure enough, if we run the tests with forge test, both of them pass with flying colors. Which is nice for the first one, very much less nice for the second one...
forge test
[⠢] Compiling...
No files changed, compilation skipped
Running 2 tests for test/nOutOfM.t.sol:nOutOfMTest
[PASS] test_BypassCheck() (gas: 76976)
[PASS] test_ValidChange() (gas: 68160)
Test result: ok. 2 passed; 0 failed; 0 skipped; finished in 664.76µs
Ran 1 test suites: 2 tests passed, 0 failed, 0 skipped (2 total tests)
The Fix
One potential fix is to use a mapping that keeps track of used passwords, to avoid that the same password can be used multiple times to increase the counter.
An example, using a storage mapping called used (mapping (bytes => bool) used), is shown here:
function modify(uint256 new_proposed_value, bytes[] calldata submitted_passwords) public {
uint256 number_of_passwords = 0;
uint256 param_length = submitted_passwords.length;
uint256 allowed_length = passwords.length;
for(uint i = 0; i < param_length; ++i){
for(uint j = 0; j < allowed_length; ++j){
if(keccak256(passwords[j]) == keccak256(submitted_passwords[i])) {
if(!used[submitted_passwords[i]]) {
used[submitted_passwords[i]] = true;
number_of_passwords++;
}
}
}
}
if(number_of_passwords >= minimum_passwords_required) variable_to_change = new_proposed_value;
//clean up the used mapping, for the next use
for(uint i = 0; i < param_length; ++i){
if(used[submitted_passwords[i]]) used[submitted_passwords[i]] = false;
}
}
With this change in place, re-running the test shows that attempting to use the same password multiple times will not bypass the check, meaning the variable does not change its original value:
forge test -vvvv
[⠢] Compiling...
No files changed, compilation skipped
Running 2 tests for test/nOutOfM.t.sol:nOutOfMTest
[FAIL. Reason: assertion failed] test_BypassCheck() (gas: 80483)
Logs:
Error: Value was not correctly updated
Error: a == b not satisfied [uint]
Left: 0
Right: 10
...
The Lesson
N out of M is a construct widely used in smart contracts and DeFi, for an infinite amount of reasons. However, it is not always safely implemented.
In a more complex contract, it is also less easy to spot, while you go through hunting for the million dollar, crazy bug that requires 12 cross-contract interactions and the alignment of 6 planets of the Solar System.
Do not overlook these situations, and thank you for reading this.
Merry hacking ;)