ForkAE is a NIST lightweight cryptography candidate that uses the forkcipher primitive in two modes of operation – SAEF and PAEF – optimized for authenticated encryption of the shortest messages. SAEF is a sequential andonline AEAD that minimizes the memory footprint compared to its alternative parallel mode PAEF, catering to the most constrained devices. SAEF was proven AE secure against nonce-respecting adversaries.

Due to their more acute and direct exposure to device misuse and mishandling, in most use cases of lightweight cryptography, nonce reuse presents a very realistic attack vector. Furthermore, many lightweight applications mandate security for their online AEAD schemes against block-wise adversaries. Surprisingly, a very few NIST lightweight AEAD candidates come with provable guarantees against these security threats.

In this work we investigate the provable security guarantees of SAEF when nonces are repeated under a refined version of the notion of online authenticated encryption OAE given by Fleischmann et al. in 2012. Using the coefficient H technique we show that, with no modifications, SAEF is OAE secure up to the birthday security bound, i.e., up to\(2^{n/2}\) processed blocks of data, wheren is the block size of the forkcipher. The implications of our work is that SAEF is safe to use in a block-wise fashion, and that if nonces get repeated, this has no impact on ciphertext integrity and confidentiality only degrades by a limited extent up to repetitions of common message prefixes.

1. 1.

   \( \text {OPerm}(n) \) is a countably infinite set, so the notion of a uniform online permutation is not defined.

2. 2.

   We acknowledge that the performance gain of ForkSKINNY comes with a more ambitious security goal for the construction. However the investigation of this trade-off is out of scope of this work.

Authors and Affiliations

1. TU Wien, Vienna, Austria

   Elena Andreeva

2. imec-COSIC, KU Leuven, Leuven, Belgium

   Amit Singh Bhati

3. CSEM, Neuchâtel, Switzerland

   Damian Vizár

Corresponding authors

Correspondence toElena Andreeva,Amit Singh Bhati orDamian Vizár.

Editors and Affiliations

1. University of Haifa, Haifa, Israel

   Orr Dunkelman

2. University of Calgary, Calgary, AB, Canada

   Michael J. Jacobson, Jr.

3. Dalhousie University, Halifax, NS, Canada

   Colin O'Flynn

A Appendix: Proof of Proposition1

We prove the proposition by describing the transformation in the backward direction, i.e. reconstructing SAEF input and output arguments from a block-tuple represented query. This is possible thanks to the sequence of tweak strings\(\textsf {T}^i_1, \ldots , \textsf {T}^i_{\ell ^i}\), which allows to unambiguously determine the boundary between the AD and message blocks, as well as whether the final block of AD and message respectively weren-bit long or not. Given a block-tuple represented query\(((\textsf {T}_j, \varDelta _j, X_j, Y_j)_{j=1}^{\ell }, T)\), we can reconstructN, A, M, C as follows (where\( {\mathsf {unpad10}} (X)\) removes\(10^*\) from the end of stringX) by iterating over the block tuples with current tuple denoted as\((\textsf {T},\varDelta , X, Y)\):

1. 1.

   Parse\(\textsf {T}\) as\(N\Vert 1\Vert F\). If\(F \in \{110, 111, 100, 101\}\) then necessarily\(\ell = 1\), and if

   • \(F = 110\): Set\(A=X, M=\varepsilon \) and\(C=T\) and stop.

   • \(F = 111\): Set\(A= {\mathsf {unpad10}} (X), M=\varepsilon \) and\(C=T\) and stop.

   • \(F = 100\): Set\(A=\varepsilon , M=X\) and\(C=Y\Vert T\) and stop.

   • \(F = 101\): Set\(A=\varepsilon , M= {\mathsf {unpad10}} (X)\) and\(C=Y\Vert T\) and stop.

   If\(F \in \{010, 011\}\) then set\(A=X_1\) respectively\(A= {\mathsf {unpad10}} (X_1)\) and\(M=C=\varepsilon \) (no more AD blocks are expected). If\(F=001\) set\(A=\varepsilon \),\(M=X_1\) and\(C=Y_1\) (no more AD blocks are expected). Finally, if\(F=000\) set\(A=X_1\) and\(M=C=\varepsilon \) (more AD blocks are expected). Set\(F_{last} \leftarrow F\) and go to next tuple.

2. 2.

   Parse\(\textsf {T}\) as\(S\Vert F\). If\(S \ne 0^{n-3}\) abort. If\(F \ne 000\) go to next step. If\(F_{last} \ne 000\) abort. Set\(A = A\Vert X\) and\(F_{last} = 000\). Go to next tuple and repeat this step.

3. 3.

   Parse\(\textsf {T}\) as\(S\Vert F\). If\(S \ne 0^{n-3}\) abort. If\(F \notin \{ 010, 011, 110, 111 \}\) go to next step. If\(F_{last} \ne 000\) abort. If

   • \(F = 110\): Set\(A=A\Vert X, M=\varepsilon \) and\(C=T\) and stop.

   • \(F = 111\): Set\(A=A\Vert {\mathsf {unpad10}} (X), M=\varepsilon \) and\(C=T\) and stop.

   • \(F = 010\): Set\(A=A\Vert X\).

   • \(F = 011\): Set\(A\Vert {\mathsf {unpad10}} (X)\) and stop.

   Set\(F_{last} = F\). Go to next tuple.

4. 4.

   Parse\(\textsf {T}\) as\(S\Vert F\). If\(S \ne 0^{n-3}\) abort. If\(F \ne 001\) go to next step. If\(F_{last} \notin \{ 010, 011, 110, 111 \}\) abort. Set\(M = M\Vert X\),\(C=C\Vert Y\) and\(F_{last} = 001\). Go to next tuple and repeat this step.

5. 5.

   Parse\(\textsf {T}\) as\(S\Vert F\). If\(S \ne 0^{n-3}\) abort. If\(F \notin \{ 100, 101 \}\) or if\(F_{last} \notin \{ 010, 011, 001 \}\) abort. If

   • \(F = 100\): Set\(M=M\Vert X\).

   • \(F = 101\): Set\(M=M\Vert {\mathsf {unpad10}} (X)\).

   Set\(C=C\Vert Y\Vert T\) and stop.

The\(\text {SAEF}[ {\mathsf {F}} ]\) AEAD scheme.

Full size image

Reprints and permissions

© 2021 Springer Nature Switzerland AG

Policies and ethics