Improper optimization in Keccak implementation
Description
For the inputs with zero, the Keccak implementation returns the precalculated hash in order to optimize in common cases:
const EMPTY_KECCAK: u256 = 0x70A4855D04D8FA7B3B2782CA53B600E5C003C7DCB27D7E923C23F7860146D2C5;
// ...
#[derive(Copy, Drop, Serde, starknet::Store, Debug, PartialEq)]
pub struct ByteData {
pub value: u256,
pub size: usize
}
// ...
fn keccak_cairo_words64(words: Words64, last_word_bytes: usize) -> u256 {
if words.is_empty() {
return EMPTY_KECCAK;
}
// ...
}
// ...
pub fn compute_keccak(bytes: Span<ByteData>) -> u256 {
if (bytes.is_empty()) {
return keccak_cairo_words64(array![].span(), 0);
}
if (*bytes.at(0).value == 0) {
return keccak_cairo_words64(array![].span(), 0);
}
// ...
}
If the value
field of the first element of the input array is zero, the function returns the Keccak hash of the empty data. However, it should be noted that this optimization is incorrect, because of these two reasons:
One,
ByteData
represents thesize
-byte data withvalue
, andvalue
can be zero in the case the data is not zero-byte. For example, the data0x0000
is represented witharray![ ByteData { value: 0_u256, size: 2 } ]
.Two,
ByteData
may contain other elements that will be concatenated and hashed together, such asarray![ ByteData { value: 0_u256, size: 0 }, ByteData { value: 1_u256, size: 1 } ]
.
Impact
This bug may cause incorrect Keccak hash derivation, which may lead to the failure of message dispatching and processing.
Recommendations
Consider adding the conditions for the optimization to be triggered.
Remediation
This issue has been acknowledged by Pragma, and fixes were implemented in the following commits: