Description

In sdk/host_circuit.go, the function commitOutput handles padding before calculating the Keccak hash of the output bits. See Discussion section ref↗ for a description of the padding used for Keccak. In the code, the implementation is as follows:

func (c *HostCircuit) commitOutput(bits []frontend.Variable) OutputCommitment {
	if len(bits)%8 != 0 {
		panic(fmt.Errorf("len bits (%d) must be multiple of 8", len(bits)))
	}

	rounds := len(bits)/1088 + 1
	paddedLen := rounds * 1088
	padded := make([]frontend.Variable, paddedLen)
	copy(padded, bits)

	// pad 101, start from one bit after the
	padded[len(bits)] = 1
	for i := len(bits) + 1; i < paddedLen-1; i++ {
		padded[i] = 0
	}
	padded[len(padded)-1] = 1

    // ...
}

The padding is incorrect whenever len(bits) % 1088 == 1087. In this case, only a single bit is left available in the last unfilled block, which is insufficient for the padding, as the shortest possible padding consist of two bits, 11. Thus, the correct padding would consist of the bit 1, followed by 1,087 bits 0, and finally another bit 1. The implementation appends only the single bit 1, however.

Let us go through the code in the concrete example of len(bits) = 1087 to illustrate this. Then len(bits) / 1088 = 1087 / 1088 will be zero, so we will have rounds = 1, and thus paddedLen = 1088. The lines padded[len(bits)] = 1 and padded[len(padded)-1] = 1 will then set the same bit to 1, and the padding will only consist of this single bit 1.

Impact

For bits satisfying len(bits) % 1088 == 1087, the computed padding will be incorrect, making the hash calculated by commitOutput different than the one calculated by the user's contract on chain.

However, in practice, the length of bits should always be divisible by 8. As long as this is satisfied, the edge case of len(bits) % 1088 == 1087 cannot occur. The main output type of concern would be Uint248, which has functions OutputUint taking a user-provided bit length, and OutputBool, which could plausibly be outputted as a single bit. However, the former checks that the bit size chosen is divisible by 8:

func (api *CircuitAPI) OutputUint(bitSize int, v Uint248) {
	if bitSize%8 != 0 {
		panic("bitSize must be multiple of 8")
	}

    // ...
}

and the latter uses an eight-bit representation:

api.addOutput(api.g.ToBinary(v.Val, 8))

Should these implementations be changed or another output type be added, so that output bitstrings that are of length not divisible by 8 become possible, then the discussed padding error could occur.

Recommendations

The computation of rounds should be replaced by the following formula (or an equivalent one):

rounds := ((len(bits) + 1) / 1088) + 1

Remediation

This issue has been acknowledged by Brevis, and a fix was implemented in commit be28c8e2↗.