Cryptographic competitions

CAESAR call for submissions, draft 4 (2013.11.23)

This document is draft 4 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 (1) offer advantages over AES-GCM and (2) are suitable for widespread adoption. Cryptographic algorithm designers are invited to submit proposals of authenticated ciphers to CAESAR. All proposals will be made public for evaluation.

Deadlines

First-round submission PDF files must be received by caesar-submissions at competitions.cr.yp.to between 2014.01.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 requirements stated in this call.

Reference software implementations must be received by caesar-submissions at competitions.cr.yp.to between 2014.01.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. The CAESAR secretary may eliminate any submission that does not comply with the reference implementation requirements or other requirements stated in this call.

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 associated data, a fixed-length secret message number, a fixed-length 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 by the following table:

	integrity	confidentiality	may impose single-use requirements
plaintext	yes	yes	no
associated data	yes	no	no
secret message number	yes	yes	yes
public message number	yes	no	yes

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

Bytes are integers between 0 and 255 inclusive. Authenticated ciphers defined in terms of objects other than bytes (e.g., 32-bit integers) must specify the relationship between those objects and byte strings (e.g., little-endian encoding of 32-bit integers).

A cipher is permitted to specify a maximum plaintext length, but this limit must not be smaller than 65536 bytes. A cipher is permitted to specify a maximum length of associated data, but this limit must not be smaller than 65536 bytes. Ciphers must accept as keys, message numbers, plaintexts, and associated data all byte strings that meet the specified lengths of keys and message numbers and any specified maximum lengths of plaintexts and associated data. Cipher designers are advised that some applications do not break files into separately encrypted packets, and that there is occasional criticism of, e.g., existing ciphers with length limits of 68719476736 bytes; submissions are expected to include justification for any length limits.

Ciphers are not required to support secret message numbers: i.e., ciphers may specify the length of the secret message number as 0 bits. Ciphers are not required to support public message numbers: i.e., ciphers may specify the length of the public message number as 0 bits. Ciphers are expected to maintain security no matter how users choose message numbers of the specified lengths: ciphers should not ask users to choose message numbers randomly, or to choose message numbers in sequence, or to follow any other message-number rules. Exception: ciphers are permitted to lose all security if a user reuses a single (secret message number,public message number) pair for two encryptions with the same secret key; but ciphers must document this loss (see "Security goals" below), and ciphers that do not lose security in this way may advertise this as an extra feature.

Ciphers are permitted to leak the plaintext length via the ciphertext length, for example by having the ciphertext length be the plaintext length plus a specified constant. The ciphertext length must be determined by the plaintext length; i.e., it must not leak any information other than the plaintext length. Ciphers are permitted to have several plaintext lengths map to the same ciphertext length, but decryption must still recover the plaintext with the correct original length. Designers are advised that minimizing ciphertext length is generally considered more valuable than hiding plaintext length: an application can compensate for public lengths by padding and splitting plaintexts, whereas an application cannot compensate for ciphertext overhead.

Designers 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 secret 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 prioritized list of recommended parameter sets: a primary recommendation, a secondary recommendation, etc. This list is permitted to be as short as 1 recommendation. This list must not be longer than 10 recommendations. Submitters are advised that 10 parameter sets are widely considered to be too many, and that the "Features" section of the submission (see below) is expected to justify each recommendation.

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, and must compute exactly the function specified in the submission. 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.

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_NSECBYTES 0
     #define CRYPTO_NPUBBYTES 12
     #define CRYPTO_ABYTES 16

This indicates that the AES-128-GCM key has 16 bytes, that the secret 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_encrypt(
       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 *nsec,
       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 associated data ad[0],ad[1],...,ad[adlen-1]
       ... and secret message number nsec[0],nsec[1],...
       ... and public message number npub[0],npub[1],...
       ... and secret key k[0],k[1],...
       ...
       return 0;
     }

     int crypto_aead_decrypt(
       unsigned char *m,unsigned long long *mlen,
       unsigned char *nsec,
       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 secret message number nsec[0],nsec[1],...
       ... from a ciphertext c[0],c[1],...,c[clen-1]
       ... and associated 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 outputs of crypto_aead_encrypt and crypto_aead_decrypt must be determined entirely by the inputs listed above and must not be affected by any randomness or other hidden inputs.

The crypto_aead_decrypt function must return -1 if the ciphertext is not valid, i.e., if the ciphertext does not equal the encryption of any (plaintext,secret message number) pair with this associated data, public message number, and secret key. The crypto_aead_encrypt and crypto_aead_decrypt 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++.

A reference implementation may specify limits on plaintext length and associated-data length, but these limits must not be smaller than 65536 bytes.

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 secret message number (omit if the secret message number has length 0);
  • integrity for the plaintext;
  • integrity for the associated data;
  • integrity for the secret message number (omit if the secret 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 use the concatenation of the secret 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 (secret message number,public message number) pair to encrypt two different (plaintext,associated 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,associated data,secret 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, relationships among 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.; and justification for each recommendation of a parameter set. 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 is expected to include an analysis of how a weakness could be hidden in the cipher. This section 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."

Changes from draft 3

Narrower window of dates for submissions, with same deadline. Previous window was 2013.12.01 through 2014.01.15 23:59 GMT; new window is 2014.01.01 through 2014.01.15 23:59 GMT.

Specify email address receiving submissions.

Add paragraphs allowing limits on plaintext length and associated-data length in (1) cipher definitions and (2) reference implementations. However, do not allow limits below 65536 bytes.

Change CRYPTO_NPRIVBYTES to CRYPTO_NSECBYTES.

Change submission of "public proposals" to submission of "proposals", but emphasize that all proposals will be made public for evaluation.

Clarify "requirements stated here" as "requirements stated in this call".

Clarify little-endian example.

Various minor wording tweaks.