10
$\begingroup$

The initial Keccak submission used 18 rounds, which was bumped up to 24 rounds for the final version after distinguishers were found for a reduced 16 round variant. However, the Keccak team has recently released a spate of cryptographic primitives based on a twelve-round variant of Keccak.

I've seen scattered references which give the impression that new bounds were found and that even 18 rounds is overkill. However, I can't grok the research and I need a canonical answer.

What led them to feel comfortable with 12 rounds for K12?

$\endgroup$
  • 2
    $\begingroup$ I think the big reason is that it only claims 128-bit security, one of my possible recommendations for SHA-3 was to reduce the round count where a lower security was claimed, and that is exactly what they have done here $\endgroup$ – Richie Frame Apr 12 '17 at 6:53
  • $\begingroup$ Hash functions allow an attacker more control than keyed primitives $\endgroup$ – CodesInChaos Apr 12 '17 at 7:02
  • $\begingroup$ @Indolering, I updated my answer. $\endgroup$ – Biv Apr 12 '17 at 14:02
  • $\begingroup$ @RichieFrame but SHA-3 only claims to provide 128-256 bits of security. $\endgroup$ – Indolering Apr 13 '17 at 21:44
  • 2
    $\begingroup$ that is collision security, there is also preimage security, distinguisher security, etc $\endgroup$ – Richie Frame Apr 14 '17 at 1:11
8
$\begingroup$

I. Intuition: collision only on 6 rounds.

KangarooTwelve aims at fast hashing but also claims 128-bits security. This can be seen in the fact that the capacity is set to 256 allowing a rate of 1344 for a faster absorption.

Note that while the base sponge construction uses only the 12 finals rounds of Keccak, it is applied twice on each bit in the case of a message longer than 8129 bytes. You compute first the CVs values and then hash it with the first string (see bellow).

KangarooTwelve(M,C):  S_0 || S_1 || ... || S_n = M || C
  F = Sponge[Keccak-p[1600,nr=12],r=1344,c=256] (or mini Keccak)

                          +------------+
                          |    S_0     |
                          +------------+
                               ||
                          +----------+
                          |  `110*`  |
                          +----------+
                               ||
+-----------------+   F   +----------+
|     S_1  ||`110`|------>|   CV_0   |
+-----------------+       +----------+
                               ||
+-----------------+   F   +----------+
|     S_2  ||`110`|------>|   CV_1   |
+-----------------+       +----------+
                               ||
       ...                    ...
                               ||
+-----------------+   F   +----------+
|     S_n  ||`110`|------>|  CV_n-1  |
+-----------------+       +----------+
                               ||
                          +----------+
                          | r_e(n-1) |
                          +----------+
                               ||
                          +------------------+   F
                          |  0xFFFF  || `01` |------>  output
                          +------------------+

Other reasons that lead to consider K12 safe are the current absence of collisions for more than 6 rounds, implying a security margin of 100%. This same round-reduced approach is also used in Keyak and Ketje.

If you want to have more security, you can use Marsupilami 14, it is Kangaroo 12 but with the last 14 rounds of Keccak instead of 12 and a capacity of 512 bits.

II. The complexity arguments.

Joan pointed this to me: in this note, it is noted that the complexity of the zero-sum distinguisher are

  • for 18 rounds: $2^{1370}$
  • for 14 rounds: $2^{257}$
  • for 12 rounds: $2^{129}$

In the case of KangarooTwelve, the capacity is 256 bits. A generic attack on a sponge with such capacity leads to a complexity of $2^{128}$, thus the complexity of the zero-sum distinguisher for 12 rounds is higher, rendering the efficiency of this attack worse than bruteforce.

As for the 14 rounds of MarsupilamiFourteen and its capacity of 512 bits, the arguments is the same.

Also to generate the zero-sum structure, one need to start in the middle of the iterations. This attack surface is reduced by the way KangarooTweleve operates due to all the fixed constants.

$\endgroup$
  • 2
    $\begingroup$ That note was written in response to those attacks but recent research seems to have improved those bounds: paper, slides. $\endgroup$ – Indolering Apr 13 '17 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.