21 September 2016

Ketje and Keyak for CAESAR round 3

Ketje and Keyak are authenticated encryption schemes based on Keccak-p. Both were accepted in round 3 of the CAESAR competition. We slightly modified Ketje (now v2) in a way that encourages cryptanalysis, while we kept Keyak unchanged (still v2) but updated and improved its documentation.

Ketje v2

Compared to Ketje v1, we now specify a different placement for the outer (input/output) part of the state. This is done by adding a change of coordinates (“twist”), so as to put the outer part on a diagonal and to limit its interaction with the preceding χ and following θ step mappings.

The motivation is to encourage cryptanalysis. Cryptanalysis usually starts by reducing the number of rounds to see at which point a given primitive becomes insecure. In the case of Ketje, one cannot decrease the step calls further than 1 round. Instead, a cryptanalyst can increase the rate to more than 2 lanes to determine at which point Ketje breaks. However, the lanes of the outer part are located in the same plane (i.e., same y coordinate) and contain the result of χ. The knowledge of too many lanes in the same plane could mean that χ is easily inverted on that part of the state. Also, we should not place the outer part on a sheet (i.e., same x coordinate) as this would help the adversary influence the parity computed in θ. Instead, the twist places the outer part on a diagonal.

We illustrate the usage of this twist with two new instances, Ketje Minor and Ketje Major, that have a rate of 4 lanes (instead of 2) and larger permutations (800 and 1600 bits).

The primary recommendation remains Ketje Sr. Both Ketje Jr and Ketje Sr keep their rate of 2 lanes and otherwise remain unchanged modulo the twist.

Keyak v2

Compared to round 2, River, Lake, Sea, Ocean and Lunar Keyak remain unchanged.

We nevertheless worked on improving the description of the Motorist mode of operation by simplifying the definition of the Piston, Engine and Motorist algorithms. We also updated the security rationale. These changes are available in version 2.2 of the documentation (see change log in Appendix A).

The definition of Motorist now restricts the tag length to the capacity. As pointed out by Seth Hoffert, a legitimate adversary could, in a session, submit a tag as next block of metadata. If the tag is as long as the rate, this allows the adversary to force the outer part to a constant value, hence increasing the multiplicity. This would not break Motorist but it would prevent it to reach near-capacity generic security.