Incorrect splitting of a number in Keccak implementation
Description
This project implements the Keccak function, which receives an array of input chunks that would be concatenated and hashed. The following is the function concatenate_input, which concatenates the given input array:
pub const FELT252_MASK: u256 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;
// ...
#[derive(Copy, Drop, Serde, starknet::Store, Debug, PartialEq)]
pub struct ByteData {
pub value: u256,
pub size: usize
}
// ...
fn concatenate_input(bytes: Span<ByteData>) -> ByteArray {
let mut output_string: ByteArray = Default::default();
let mut cur_idx = 0;
loop {
if (cur_idx == bytes.len()) {
break ();
}
let byte = *bytes.at(cur_idx);
if (byte.size == 32) {
// in order to store a 32-bytes entry in a ByteArray, we need to first append the upper 1-byte part , then the lower 31-bytes part
let up_byte = (byte.value / FELT252_MASK).try_into().unwrap();
output_string.append_word(up_byte, 1);
let down_byte = (byte.value & FELT252_MASK).try_into().unwrap();
output_string.append_word(down_byte, 31);
} else {
output_string.append_word(byte.value.try_into().unwrap(), byte.size);
}
cur_idx += 1;
};
output_string
}It can be observed that the 32-byte chunk is split into two values and appended separately. This is because the function append_word receives the values as felt types, which can only safely store 31-byte data.
The most significant byte of the 32-byte chunk is obtained by dividing the chunk by FELT256_MASK. However, this method may result in an incorrect result in specific cases. For example, the most significant byte of 0x01FFFF(...total 32 bytes...)FFFF is 0x01, but the result using the above method would be 0x02.
Impact
This bug may cause incorrect Keccak hash derivation, which may lead to the failure of message dispatching and processing.
Recommendations
Consider changing the logic obtaining the most significant byte of the 32-byte chunk.
Remediation
This issue has been acknowledged by Pragma, and a fix was implemented in commit d9152fc4↗.