News archives 2018

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