Description

This finding is about issues similar to those for the Keccak padding circuit that were discussed in Finding ref↗ but instead for the native implementation in keccak/periphery.go. For a brief overview of the pad10*1 padding, see Discussion section ref↗.

The following function is intended to calculate the number of blocks that an input to the Keccak hash function of length bitsLen will be padded to:

func GetRoundIndex(bitsLen int) int {
	return (bitsLen + 8) / 1088
}

It has the same issue as the calculation of rounds in Finding ref↗, incorrectly returning the round number for bit lengths 1,080 to 1,086 (modulo 1,088). This function does not seem to be called anywhere, however.

The PadBits101 function is the counterpart to Pad101Bits from Finding ref↗ but for native types:

func PadBits101(api frontend.API, data []frontend.Variable, maxRound int) []frontend.Variable {
	var padBits []frontend.Variable
	padBits = append(padBits, data...)
	var missedLen = 1088 - len(data)%1088
	var zeroBitLen = missedLen - 8*2

	padBits = append(padBits, api.ToBinary(1, 8)...) // 1000, 0000
	for i := 0; i < zeroBitLen; i++ {
		padBits = append(padBits, 0) //00...0000
	}
	padBits = append(padBits, api.ToBinary(128, 8)...) // 0000 0001

	padZeroLen := maxRound*1088 - len(padBits)

	for i := 0; i < padZeroLen; i++ {
		padBits = append(padBits, 0)
	}
	return padBits
}

It has similar problems to Pad101Bits. The padding is incorrect when len(data) % 1088 is between 1,073 and 1,087. In that case, zeroBitLen will be negative, and padding will consist of first 1000 0000 0000 0001, with the final bit always occurring at an incorrect location, and it is then filled with dummy zeroes.

Impact

The functions GetRoundIndex and PadBits101 produce incorrect results for some inputs. Should they be used to calculate Keccak hashes, the result will be incorrect for such inputs.

Among the in-scope code in zk-hash and brevis-sdk, the PadBits101 function is only used in the sdk's SlotOfStructFieldInMapping function in sdk/circuit_api.go, where usage is in such a way that the input will not be of a size that can cause the issue. The GetRoundIndex function is not used.

Recommendations

The function GetRoundIndex should be replaced by a corrected formula:

func GetRoundIndex(bitsLen int) int {
- 	return (bitsLen + 8) / 1088
+ 	return (bitsLen + 1) / 1088
}

Two bits of padding must be added at least, but an exactly full block does not necessitate expanding to another block. Thus, we add 1 and round down on division.

The PadBits101 function should be fixed by adding the correct number of zeroes, similarly to how it is described in Discussion section ref↗:

func PadBits101(api frontend.API, data []frontend.Variable, maxRound int) []frontend.Variable {
	var padBits []frontend.Variable
	padBits = append(padBits, data...)
	var missedLen = 1088 - len(data)%1088
- 	var zeroBitLen = missedLen - 8*2
+ 	var zeroBitLen = (1088 + missedLen - 2) % 1088
- 	padBits = append(padBits, api.ToBinary(1, 8)...) // 1000, 0000
+ 	padBits = append(padBits, 1) // Single bit 1
	for i := 0; i < zeroBitLen; i++ {
		padBits = append(padBits, 0) //00...0000
	}
- 	padBits = append(padBits, api.ToBinary(128, 8)...) // 0000 0001
+ 	padBits = append(padBits, 1) // Single bit 1

	padZeroLen := maxRound*1088 - len(padBits)

	for i := 0; i < padZeroLen; i++ {
		padBits = append(padBits, 0)
	}
	return padBits
}

Remediation

This issue has been acknowledged by Brevis, and a fix was implemented in commit fc8fc444↗. The GetRoundIndex function was removed, with GetKeccakRoundForPaddedBytes to be used instead.