Guido Bertoni^{3}, Joan Daemen^{2}, Seth Hoffert, Michaël Peeters^{1}, Gilles Van Assche^{1} and Ronny Van Keer^{1}
^{1}STMicroelectronics - ^{2}Radboud University - ^{3}Security Pattern
Welcome to the web pages of the Keccak Team!
In these pages, you can find information about our different cryptographic schemes and constructions, their specifications, cryptanalysis on them, the ongoing contests and the related scientific papers.
Making sure that our primitives are not susceptible to differential or linear cryptanalysis has been a constant target for us. In this scope, differential and linear trails specify how differences or linear masks propagate through the rounds, so we want to ensure that the only trails that exist are those that are too costly to exploit. Concretely, we are looking for lower bounds on the weight of trails, for a given number of rounds. The higher the weight, the greater the data and/or computation complexity of attacks based on them, so simply put, if no trail of low weight exist, then we are safe.
Bounds on trails do not give guarantees of security, but they can help determine the resistance against some specific attacks. For instance, in the Farfalle construction (used by Xoofff and Kravatte), the expected data complexity to generate internal collisions is directly linked to bounds on the weight of differential trails, see Section 6.3.2 of [Daemen et al., The design of Xoodoo and Xoofff, ToSC 2018].
Bounds on trails do not give guarantees of security as differential and linear attacks are broader than just exploiting trails. For instance, a differential over several rounds (i.e., specifying only the input and output differences) can span many differential trails (i.e., take many different internal differences); this effect is called clustering. Nevertheless, the design strategy of Xoodoo, similar to that of Keccak, is unaligned, and this helps reduce clustering. We studied this and other effects in our recent paper [Bordes et al., Thinking Outside the Superbox, CRYPTO 2021].
Proving lower bounds on trails in unaligned primitives requires the computer-aided exploration of all possible trails. The publication of Xoodoo came with our initial bounds, and we further improved them and reported them in the documentation of Xoodyak. Recently, we revived this effort and further extended our complete search for all 3-round trails up to weight 52 (instead of 50), allowing us to prove that a 6-round trail has weight at least 108 (instead of 104). This is the case for both differential and linear trails.
The completeness of the search for all 3-round trails is now confirmed up to weight 50 thanks to an independent search effort based on SAT solvers, XoodooSat, implemented by Huina Li and Weidong Qiu of Shanghai Jiao Tong University. Actually, they reported to us that two trails of weight 48 were missing, and this was caused by a bug in our program XooTools. After fixing it, we could confirm that XooTools and XoodooSat had produced exactly the same set of trails, independently!
To conclude, we summarize our current trail bounds in Xoodoo in the following table.
# rounds | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 10 | 12 |
---|---|---|---|---|---|---|---|---|---|
Differential trails | 2 | 8 | 36 | 74 | 94 | 108 | 148 | 188 | 222 |
Linear trails | 2 | 8 | 36 | 74 | 94 | 108 | 148 | 188 | 222 |
We often receive questions as to whether Deck-SANSE can be used in a stateless way; that is, for a single message. A common use case for this is a UDP-based VPN. In such an application, sessions are not feasible due to the lossy/unordered nature of UDP. Thanks to its versatility, Deck-SANSE can be used in such applications with virtually no overhead. Deck-SANSE provides the following features:
Deck-SANSE wrap function, taking associated data A and plaintext P, and returning ciphertext C and tag T:
if |A| > 0 and |P| > 0 then T ← 0^t + F(P||010 ∘ A||00) C ← P + F(T||110 ∘ A||00) else if |P| > 0 then T ← 0^t + F(P||010) C ← P + F(T||110) else T ← 0^t + F(A||00) return (C,T)
We released the specifications of two authenticated encryption schemes built on top of Kravatte, namely Kravatte-SANE and Kravatte-SANSE, replacing Kravatte-SAE and Kravatte-SIV, respectively.
The Kravatte-SANE and Kravatte-SANSE schemes both support sessions. Often, one does not only want to protect a single message, but rather a session where multiple messages are exchanged, such as in the Transport Layer Security (TLS) or the Secure Shell (SSH) protocols. Each tag authenticates all messages already sent so far in the session. Examples of session-supporting authenticated encryption schemes include Ketje and Keyak.
The SANE and SANSE variants differ in their robustness with respect to nonce misuse. The former relies on user-provided nonces (one per session) for confidentiality, while the latter is more robust against nonce misuse and realizes this by using the SIV mechanism. Note that we also specify a tweakable block cipher on top of Kravatte in the original article on Farfalle.
Kravatte-SANE and Kravatte-SANSE fix and obsolete Kravatte-SAE and Kravatte-SIV, respectively. Ted Krovetz pointed out a flaw in the Farfalle-SIV mode and we subsequently found one in Farfalle-SAE. The flaw in Farfalle-SAE is related to sequences of messages with empty plaintexts and/or metadata, while that of Farfalle-SIV follows from the lack of separation between the tag and the keystream generation. (More details can be found in the Xoodoo cookbook, Sections 4.1 and 5.1.)
The performance of the new schemes is identical to that of their obsoleted counterparts. Thanks to the high level of parallelism of Kravatte, the SANE and SANSE schemes have excellent software speeds. Optimized code can be found in the extended Keccak code package.
At the rump session of FSE 2018 that took place last week in Brugge, Belgium, we announced the outcome of the Ketje cryptanalysis prize.
There were three submissions:
The first two submissions push the boundaries of cube attacks, or more generally, higher-order differential cryptanalysis of round-reduced Keccak-f. In Ketje, these attacks always target the initialization phase that applies Keccak-p[n_{r}=12] to the concatenation of a key and a nonce. The algebraic degree of Keccak-p[n_{r}], for a small number of rounds, is d=2^{nr}, so a straightforward higher-order differential attack would require a data complexity of 2^{d} chosen input blocks (e.g., for n_{r}=6 rounds, the degree is d=64 and the straightforward data complexity is 2^{64}). By applying some sophisticated tricks, one can peel off one or two rounds resulting in much lower data complexities. The first two submissions achieve this by exploiting specific propagation properties of the round function.
The third submission is the first to attack the encryption/decryption phase of Ketje Jr. In this phase, a known-plaintext attacker gets the value of the first r=16 bits of the state for every round of Keccak-f. Information-theoretically n=200/16=12.5 such blocks would be sufficient to break Ketje by state recovery, but the computational difficulty increases quickly with n. This submission investigates weakened versions of Ketje Jr with increased rates: r=32 and r=40 bits and break the security claim. The attacks confirm that the tweak between Ketje v1 and Ketje v2 results in an increase in safety margin.
These three attacks add to the already substantial amount of cryptanalysis of the Keccak-f permutation in a keyed setting. They enforce the positions of Ketje (and Keyak) as being among the most cryptanalyzed authenticated ciphers.
Given these nice results, we decided to award all three submissions. For practical reasons, the contestants of the first two entries got Belgian chocolates, while those of the latter received Belgian beer.
Everyone's a winner in this contest. Congratulations to all!
We are glad to announce the final version of the Farfalle construction and of the Kravatte pseudo-random function and encryption schemes.
First published in late 2016 on IACR ePrint, an update of our paper Farfalle: parallel permutation-based cryptography was accepted at the journal Transactions on Symmetric Cryptography (ToSC). We will present it at the yearly Fast Software Encryption (FSE) conference in Brugge, Belgium, in March 2018.
In the last couple of months, we applied some changes to both Farfalle and Kravatte^{1}. This was due to prompt third-party cryptanalysis by different researchers. First Ling Song and Jian Guo contacted us with a key recovery cube attack on the (full) previous version of Kravatte. Then a second team of cryptanalysts (who wish to stay anonymous at this point, as their paper is under submission) sent us the description of even more powerful attacks targeting the expansion layer specifically. Consequently, we modified Kravatte by taking 6 rounds for all four permutation instances. And to counteract the attacks of the second team, we made a more fundamental change by adopting a non-linear rolling function in the expansion layer. We realize that switching from a linear rolling function to a non-linear one is a change in philosophy, and we discuss it in the paper.
The optimized code in the KCP and the reference implementation in KeccakTools are in sync.
^{1}To distinguish the latest version of Kravatte from the previous one, we call it Kravatte Achouffe.