Home

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.

Latest news

  • 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:

    • Nonce reuse resistance.
    • If a nonce is present in the associated data, then a t-bit tag gives t-bit security.
    • Thanks to frame bits, it collapses to a simple MAC if plaintext is not present.
    • Thanks to frame bits, the associated data string is also optional (so for e.g. key wrapping, the mode is efficient).
    • Both the key schedule and static associated data contribution can be precomputed and reused across multiple messages.
    • Fully parallelizable in absorption of associated data and plaintext, expansion of keystream and encryption of plaintext.

    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)
      CP   + F(T||110 ∘ A||00)
    else if |P| > 0 then
      T ← 0^t + F(P||010)
      CP   + 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:

    • Cube-like Attack on Round-Reduced Initialization of Ketje Sr, by Xiaoyang Dong, Zheng Li, Xiaoyun Wang and Ling Qin, presented at FSE 2017 and published in Volume 2017, Issue 1 of ToSC.
    • New MILP Modeling: Improved Conditional Cube Attacks to Keccak-based Constructions, by Ling Song, Jian Guo and Danping Shi, available as Cryptology ePrint Archive Report 2017/1030.
    • State-recovery attacks on Modified Ketje Jr, by Thomas Fuhr, Maria Naya-Plasencia and Yann Rotella, presented at FSE 2018 and published in Volume 2018, Issue 1 of ToSC.

    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[nr=12] to the concatenation of a key and a nonce. The algebraic degree of Keccak-p[nr], for a small number of rounds, is d=2nr, so a straightforward higher-order differential attack would require a data complexity of 2d chosen input blocks (e.g., for nr=6 rounds, the degree is d=64 and the straightforward data complexity is 264). 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.

    • Farfalle is a new generic construction for building a pseudo-random function (PRF) exploiting the parallel evaluation of a cryptographic permutation. The PRF takes as input a key and a sequence of arbitrary-length data strings, and returns an arbitrary-length output. To an adversary not knowing the key, these output bits look like independent uniformly-drawn random bits. Farfalle can readily be used for stream encryption and MAC computation, and we define several modes for authenticated encryption on top of it.
    • Kravatte is a high-speed instance of Farfalle based on Keccak-p[1600] permutations, claimed to resist against classical and quantum adversaries. Modes for authentication, encryption and authenticated encryption are defined accordingly.

    In the last couple of months, we applied some changes to both Farfalle and Kravatte1. 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.

    1To distinguish the latest version of Kravatte from the previous one, we call it Kravatte Achouffe.

  • If SHA-2 is not broken, why would one switch to SHA-3 and not just stay with SHA-2? In this post, we highlight another argument why Keccak/SHA-3 is a better choice than SHA-2, namely openness, in analogy with open-source versus closed-source in software development and deployment.

    Software has two sides: its executable and its source code. The former is used as a black box by the users, while the latter is of interest to developers who want to extend it, to understand its inner workings or to make sure there is no obvious malicious code. As an analogy, we see the specification of the cryptographic primitive, mode or algorithm in a (proposed) cryptographic standard as the counterpart of the software executable: It allows everyone to include the cryptographic object, as is, in his/her project. The counterpart of the source code in cryptography would be the design rationale, preliminary cryptanalysis and evidence of extensive third-party cryptanalysis: These are the elements that give insight into the inner workings and ultimately trust.

    The transition of cryptography from a proprietary activity to a scientific one in the last 50 years can be seen as a move from closed-source to open-source in this analogy. Surprisingly, there are exceptions and we still see closed-source cryptography today.

    The SHA-1 and SHA-2 NIST standard hash functions were designed behind closed doors at NSA. The standards were put forward in 1995 and 2001 respectively, without public scrutiny of any significance, despite the fact that at time of publication there was already a considerable cryptographic community doing active research on this subject. Even the 2015 update of FIPS 180, the standard that specifies SHA-2, does not contain, nor refer to, a design rationale.

    In contrast, SHA-3 is the result of an open call of NIST to the cryptographic community for hash function proposals. There was no restriction on who could participate, so submissions were open in the broadest possible sense. Every submitted candidate algorithm had to contain a description, a design rationale and preliminary cryptanalysis. The authors of the 64 submissions included the majority of people active in open symmetric crypto research at the time. NIST solicited the symmetric crypto community for performing and publishing research in cryptanalysis, implementations, proofs and comparisons of the candidates and based its decision on the results. After a three-round process involving hundreds of people in the community for several years, NIST finally announced that Keccak was selected to become the SHA-3 standard.

    The open effort of the symmetric crypto community did not stop there. Since then, Keccak has remained under public scrutiny and new papers appear regularly. Paper after paper confirms the large safety margin of Keccak. What is important, is that these papers reach a high degree of sophistication as research can start from the preliminary cryptanalysis that we provided in our SHA-3 submission document.

    It is true that cryptanalysis of MD5, SHA-1 and SHA-2 has also reached a high degree of sophistication. However, this took longer to develop due to the absence of rationale and preliminary cryptanalysis, but also due to the adoption of the ARX design methodology.

    SHA-2 is essentially a security patch of SHA-1 while SHA-3 is its open-source alternative, much in the same way that Triple-DES is a security patch for DES and AES the open-source alternative. In retrospect, even if Triple-DES is not broken, would you still recommend not to switch to AES?

News archives