Cryptographic competitions

CAESAR call for submissions, draft 1 (2013.04.16)

This document is draft 1 of a call for CAESAR public submissions. Please check http://competitions.cr.yp.to for newer drafts.

Call

CAESAR (Competition for Authenticated Encryption: Security, Applicability, and Robustness) will identify a portfolio of authenticated ciphers that offer advantages over AES-GCM and that are suitable for widespread adoption. Cryptographic algorithm designers are invited to submit public proposals of authenticated ciphers to CAESAR.

Deadlines

First-round submission PDF files must be received by the caesar-submissions email address between 2013.12.01 and 2014.01.15 23:59 GMT. This email must have subject line precisely round 1 submission: NAME where NAME is replaced by the cipher name. After 2014.01.15 the CAESAR secretary will publish all first-round submissions received, except that the CAESAR secretary may exclude submissions that do not meet the requirements below.

Reference software implementations must be received by the caesar-submissions email address between 2013.12.01 and 2014.02.15 23:59 GMT. This email must have subject line precisely round 1 software: NAME where NAME is replaced by the cipher name.

Functional requirements

An authenticated cipher is a function with five byte-string inputs and one byte-string output. The five inputs are a variable-length plaintext, variable-length additional data, a fixed-length (possibly 0-bit) private message number, a fixed-length (possibly 0-bit) public message number, and a fixed-length key. The output is a variable-length ciphertext. The first four inputs have different security purposes, as indicated in the following table:

	integrity	confidentiality	may impose single-use requirements
plaintext	yes	yes	no
additional data	yes	no	no
private message number	yes	yes	yes
public message number	yes	no	yes

It must be possible to recover the plaintext and the private message number from the ciphertext, additional data, public message number, and key.

Bytes are integers between 0 and 255 inclusive. Authenticated ciphers defined in terms of higher-level objects must specify the relationship between those objects and byte strings: for example, little-endian encoding of 32-bit integers.

Submitters are advised that many existing applications use 80-bit, 128-bit, or 256-bit keys; 96-bit or 104-bit public message numbers; 0-bit private message numbers; and 32, 64, 96, 128, or 160 extra bits (used for authentication) in ciphertext compared to plaintext. However, submissions are not required to support these sizes, and are not limited to these sizes.

Each submission specifies a family of authenticated ciphers. Family members may vary in external parameters such as key length, and may vary in submission-defined parameters such as the number of "rounds". However, a submission is also permitted to specify a family containing just 1 authenticated cipher. Each submission must include a list of at most 10 recommended parameter sets.

Software requirements

Each first-round submission must be accompanied by a portable reference software implementation to support public understanding of the cipher, cryptanalysis, verification of subsequent implementations, etc. This implementation must cover all recommended parameter sets. This implementation is expected to be optimized for clarity, not for performance; the official CAESAR benchmarks will report the fastest implementation on each platform, and will thus disregard the reference implementation on any platform where it is superseded by faster implementations. Submissions without working reference software implementations will not be selected for the second round.

A minimal reference implementation of (e.g.) AES-128-GCM consists of two files: crypto_aead/aes128gcm/ref/api.h and crypto_aead/aes128gcm/ref/encrypt.c. There are three levels of directory names:

• The first-level directory name crypto_aead is the same for all authenticated ciphers.
• The second-level directory name is a lowercase version of the cipher name, including a specification of the parameter set. A reference implementation covering 3 different parameter sets has 3 different second-level directories. Dashes, dots, slashes, and other punctuation marks are omitted; the directory name consists solely of digits (0123456789) and lowercase ASCII letters (abcdefghijklmnopqrstuvwxyz).
• The third-level directory name is ref for the reference implementation. Other implementations of the same cipher (with the same parameter set) use other third-level directory names.

The file api.h has four lines:

     #define CRYPTO_KEYBYTES 16
     #define CRYPTO_NPRIVBYTES 0
     #define CRYPTO_NPUBBYTES 12
     #define CRYPTO_ABYTES 16

This indicates that the AES-128-GCM key has 16 bytes, that the private message number has 0 bytes, that the public message number has 12 bytes, and that the ciphertext is at most 16 bytes longer than the plaintext. (A typical authenticated cipher has a constant gap between plaintext length and ciphertext length, but the requirement here is to have a constant limit on the gap.)

The file encrypt.c has the following structure:

     #include "crypto_aead.h"

     int crypto_aead(
       unsigned char *c,unsigned long long *clen,
       const unsigned char *m,unsigned long long mlen,
       const unsigned char *ad,unsigned long long adlen,
       const unsigned char *npriv,
       const unsigned char *npub,
       const unsigned char *k
     )
     {
       ...
       ... the code for the cipher implementation goes here,
       ... generating a ciphertext c[0],c[1],...,c[*clen-1]
       ... from a plaintext m[0],m[1],...,m[mlen-1]
       ... and additional data ad[0],ad[1],...,ad[adlen-1]
       ... and private message number npriv[0],npriv[1],...
       ... and public message number npub[0],npub[1],...
       ... and secret key k[0],k[1],...
       ...
       return 0;
     }

     int crypto_aead_open(
       unsigned char *m,unsigned long long *mlen,
       unsigned char *npriv,
       const unsigned char *c,unsigned long long clen,
       const unsigned char *ad,unsigned long long adlen,
       const unsigned char *npub,
       const unsigned char *k
     )
     {
       ...
       ... the code for the cipher implementation goes here,
       ... generating a plaintext m[0],m[1],...,m[*mlen-1]
       ... and private message number npriv[0],npriv[1],...
       ... from a ciphertext c[0],c[1],...,c[clen-1]
       ... and additional data ad[0],ad[1],...,ad[adlen-1]
       ... and public message number npub[0],npub[1],...
       ... and secret key k[0],k[1],...
       ...
       return 0;
     }

The crypto_aead_open function must return -1 if the ciphertext is not valid, i.e., if the ciphertext does not equal the encryption of any (plaintext,private message number) pair with this additional data, public message number, and secret key. The crypto_aead and crypto_aead_open functions may return other negative numbers to indicate other failures (e.g., memory-allocation failures).

The file crypto_aead.h is not included in the reference implementation; it is created automatically by the benchmarking framework.

A reference implementation can use names other than encrypt.c. It can split its code across several files *.c defining various auxiliary functions; the files will be automatically compiled together. Instead of encrypt.c it can include encrypt.cc or encrypt.cpp in C++.

The reference implementation is packaged into a tarball, such as aes128gcm.tar.gz for AES-128-GCM.

Hardware requirements

Each submission selected for the second round will also be required to include a reference hardware design (i.e., a reference implementation in the VHDL or Verilog languages) by 2015.03.15. Details of the hardware API have not yet been specified.

Submission requirements

Each submission consists of a single PDF file with the following sections:

• First page: Cipher name, name of designer/designers, name of submitter/submitters (usually the same as the designer/designers), one contact email address for submitter/submitters. The cipher name is required to include a version number (e.g., "v1") to avoid confusion in case the cipher is tweaked for subsequent rounds of the competition.
• Specification: A complete definition of the family of authenticated ciphers. This definition must include the complete parameter space defining the family, and must include a list of at most 10 recommended parameter sets. The cipher definition is required to be self-contained, including all information necessary to implement the cipher from scratch, except that the following functions are free to be used without being defined: AES-128 with 128-bit key, 128-bit input, and 128-bit output; AES-256 with 256-bit key, 128-bit input, and 128-bit output.
• Security goals: A table quantifying, for each of the recommended parameter sets, the intended number of bits of security (i.e., the logarithm base 2 of the attack cost) in each of the following categories:
  • confidentiality for the plaintext;
  • confidentiality for the private message number (omit if the private message number has length 0);
  • integrity for the plaintext;
  • integrity for the additional data;
  • integrity for the private message number (omit if the private message number has length 0);
  • integrity for the public message number (omit if the public message number has length 0); and
  • any additional security goals and robustness goals that the submitters wish to point out.
  This section must clearly state either
  • that users are required to treat the concatenation of the private message number and the public message number as a nonce, i.e., that the cipher may lose all integrity and confidentiality if the legitimate key holder uses the same (private message number,public message number) pair to encrypt two different (plaintext,additional data) pairs under the same key; or
  • that the cipher is designed to provide the maximum possible robustness against message-number reuse, i.e., that the cipher maintains full integrity and confidentiality, except for leaking collisions of (plaintext,additional data,private message number,public message number) via collisions of ciphertexts; or
  • that the cipher is designed to provide some intermediate level of robustness against message-number reuse, in which case this section must specify what that level of robustness is.
  This section may also state goals that accommodate variations in attack resources, such as software side channels, hardware side channels, large numbers of active keys, large numbers of legitimate messages encrypted, etc.
• Security analysis: An explanation of why the submitter expects this family of ciphers, with each of the recommended parameter sets, to meet the stated security goals and robustness goals.
• Features: A detailed list of cipher features that the submitter wishes to emphasize, including explanations of what each feature means and why the feature is of interest. This section is expected to include discussion of performance, potential applications, advantages over previous ciphers, etc. This section must explain, in particular, why users should prefer this cipher over AES-GCM.
• Design rationale: An explanation of the choices made in the cipher design. This section must include an analysis of how a weakness could be hidden in the cipher, and must include the following statement: "The designer/designers have not hidden any weaknesses in this cipher."
• Intellectual property: Full disclosure of all known patents, patent applications, planned patent applications, and other intellectual-property constraints relevant to use of the cipher. This section must include the following statement: "If any of this information changes, the submitter/submitters will promptly (and within at most one month) announce these changes on the crypto-competitions mailing list." Note that intellectual-property status will be taken into account in cipher evaluation; patented submissions are permitted, but submitters are advised that patenting a cipher is likely to reduce the level of interest in the cipher.
• Consent: The following statement: "The submitter/submitters hereby consent to all decisions of the CAESAR selection committee regarding the selection or non-selection of this submission as a second-round candidate, a third-round candidate, a finalist, a member of the final portfolio, or any other designation provided by the committee. The submitter/submitters understand that the committee will not comment on the algorithms, except that for each selected algorithm the committee will simply cite the previously published analyses that led to the selection of the algorithm. The submitter/submitters understand that the selection of some algorithms is not a negative comment regarding other algorithms, and that an excellent algorithm might fail to be selected simply because not enough analysis was available at the time of the committee decision. The submitter/submitters acknowledge that the committee decisions reflect the collective expert judgments of the committee members and are not subject to appeal. The submitter/submitters understand that if they disagree with published analyses then they are expected to promptly and publicly respond to those analyses, not to wait for subsequent committee decisions. The submitter/submitters understand that this statement is required as a condition of consideration of this submission by the CAESAR selection committee."