NESSIE

Call for Cryptographic Primitives

Version 2.2, 8th March 2000

 

Introduction

NESSIE (New European Schemes for Signature, Integrity, and Encryption) is a project within the Information Societies Technology (IST) Programme of the European Commission. The participants of the project are
 
Participant name Country
Katholieke Universiteit Leuven Belgium
École Normale Supérieure France
Fondazione Ugo Bordoni Italy
Royal Holloway, University of London U.K.
Siemens Aktiengesellschaft Germany
Technion – Israel Institute of Technology Israel
Université Catholique de Louvain Belgium
Universitetet i Bergen Norway

NESSIE is a 3-year project, which started on 1st January 2000. Further information about NESSIE is available at http://cryptonessie.org.

The main objective of the project is to put forward a portfolio of strong cryptographic primitives for a number of different platforms.  These primitives will be obtained after an open call and evaluated using a transparent and open process.  They should be the building blocks of the future standard protocols for the information society.

The deadline for the submission of primitives will be 29th September 2000.  A workshop will be organised for submitters to present their primitives on 13-14 November 2000 in Leuven, Belgium.
 

 

Background

In the information society, cryptology has become a key enabling technology to provide secure electronic commerce and electronic business, secure communications, secure payments, and the protection of the privacy of the citizen.  Cryptology is a field that evolves quickly, and society needs robust primitives that provide long term security (15 to 20 years or more), rather than ad hoc solutions that need to be frequently replaced.  With the current state of the art in cryptology, it is not possible to have provably secure solutions, although there is a trend to prove more and more security properties of primitives.  However, for use in real applications, sufficient confidence in a primitive can only be achieved when primitives have been subjected to an open and independent evaluation for a sufficient amount of time.

The procedure of an open call followed by an evaluation process has been previously used in the selection process for the DES, the RIPE project, and the AES.  The scope of this call for primitives is wider than the NIST call for AES.  The information society needs other cryptographic primitives than just block ciphers.  Thus the NESSIE call seeks cryptographic primitives in many areas, such as:

Furthermore, there is a wide range of environments in which cryptographic primitives are used.  Thus the NESSIE project will consider primitives designed for use in specific environments (though flexibility is clearly desirable).  The NESSIE call also asks for testing methodologies of these primitives (such as statistical tests).

The results of this call will then be subjected to a thorough and open evaluation process.  In addition to the responses to the call, the project will also consider a selection from existing standards containing such primitives.  The main selection criteria will be long-term security, market requirements, efficiency (performance), and flexibility.

It is also a goal of the project to disseminate widely the results of the project, and to build a consensus based on these results.  In order to achieve this, an Industry Group has been established.  The Industry Group consists of about twenty leading European companies in this area and will be consulted on a regular basis throughout the project.  It is expected that the Industry Group will provide input concerning the nature of the final call (requirements and definitions for primitives), the relevance of the selection criteria, and the standardisation strategy.  An important part of the dissemination will be the introduction of these primitives into standardisation bodies (ISO, ISO/IEC, CEN, IEEE, IETF), based in part on the consensus achieved within the project.  It is anticipated that the results of the project will also be published in scientific publications.
 

 

General Requirements

This section discusses the general selection criteria, the type of primitives required, and the security requirements for each primitive.
 

Selection Criteria

The main selection criteria will be long-term security, market requirements, efficiency (performance) and flexibility.

Type of Primitives

The NESSIE project is seeking submissions of strong cryptographic primitives in the categories given below.  The NESSIE project is particularly interested in receiving submissions in categories that have not received much standardisation effort.
  1. Block ciphers
  2. Synchronous stream ciphers
  3. Self-synchronising stream ciphers
  4. Message Authentication Codes (MACs)
  5. Collision-resistant hash functions
  6. One-way hash functions
  7. Families of pseudo-random functions
  8. Asymmetric encryption schemes
  9. Asymmetric digital signature schemes
  10. Asymmetric identification schemes
Definitions are broadly as given in the Handbook of Applied Cryptography(ISBN: 0-8493-8523-7).
 

 

Security Requirements for Each Primitive

Symmetric Primitives (Primitives 1-7)

There are two main security levels for symmetric primitives.  These are named normal and high.  For block ciphers, normal-legacy is also provided.  The minimal requirements for a symmetric primitive to attain a security level are given below.
  1. Block ciphers.

  2. a) High.  Key length of at least 256 bits.  Block length at least 128 bits
    b) Normal.  Key length of at least 128 bits.  Block length at least 128 bits.
    c) Normal-Legacy.  Key length of at least 128 bits.  Block length 64 bits
     
  3. Synchronous stream ciphers.

  4. a) High.  Key length of at least 256 bits.  Internal memory of at least 256 bits.
    b) Normal.  Key length of at least 128 bits.  Internal memory of at least 128 bits.
     
  5. Self-synchronising stream ciphers.

  6. a) High.  Key length of at least 256 bits.  Internal memory of at least 256 bits.
    b) Normal.  Key length of at least 128 bits.  Internal memory of at least 128 bits.
     
  7. Message Authentication Codes (MACs).

  8. The primitive should support all output lengths (in multiples of 32 bits) up to the key length (inclusive).
    a) High.  Key length of at least 256 bits.
    b) Normal.  Key length of at least 128 bits.
     
  9. Collision-Resistant Hash functions.

  10. a) High.  Output length of at least 512 bits.
    b) Normal.  Output length of at least 256 bits.
     
  11. One-Way Hash functions.

  12. These hash functions shall be preimage resistant and second preimage resistant.
    a) High.  Output length of at least 256 bits.
    b) Normal.  Output length of at least 128 bits.
     
  13. Families of Pseudo-random functions.

  14. Fixed block length of at least 128 bits.
    a) High.  Key length of at least 256 bits.
    b) Normal.  Key length of at least 128 bits.

 

Asymmetric Primitives (Primitives 8-10)

The security parameters should be chosen such that the most efficient attack on the primitive requires a computational effort of the order of 280 3-DES encryptions. Furthermore, a table giving the security levels in terms of the security parameters should be provided.
  1. Asymmetric encryption schemes (deterministic or randomised).

  2. The minimal computational effort for an attack should be of the order of 280 3-DES encryptions.
  3. Asymmetric digital signature schemes.

  4. The minimal computational effort for an attack should be of the order of 280 3-DES encryptions.
  5. Asymmetric identification schemes

  6. The minimal computational effort for an attack should be of the order of 280 3-DES encryptions. The probability of impersonation should be smaller than 2-32.

 

Evaluation of Proposals

Detailed Evaluation Criteria

Security Criteria

Implementation Criteria

Other Criteria

Licensing Requirements

 

The Evaluation Process

The NESSIE project reserves the right to reject submitted primitives that are not clearly specified and easily comprehensible or that fail to meet the NESSIE requirements in some way.

The NESSIE evaluation process is an open process.  Thus as part of the evaluation process, the NESSIE project welcomes comments about both submitted primitives and the evaluation process, including evaluation methodologies.  To facilitate this process, three NESSIE workshops will be organised; the first will be on 13-14 November 2000, shortly after the deadline for submission of primitives.  As part of the evaluation process, the NESSIE partners will give security and performance assessments of the submitted primitives.  At the end of the evaluation process, the NESSIE project may recommend certain submissions for standardisation.  The NESSIE project is to have two phases.  A timetable for the NESSIE project is given below.
 

2000  January Beginning of first phase of NESSIE
2000 January Creation of Industry Board
2000 March Call for Cryptographic Primitives
2000 September Submission deadline
2000 November First NESSIE workshop
2001 June Preliminary assessment of submissions
2001 June End of first phase of NESSIE
 
2001 July Beginning of second phase of NESSIE
2001  September Second NESSIE workshop
2002 February Preliminary selection of submissions
2002 February Standardisation Plan
2002 October Third NESSIE workshop
2002 December Final selection of submissions
2002 December Final report of NESSIE project
2002 December End of second phase of NESSIE

 

Formal Submission Requirements

The following are to be provided with any submission:

A. Cover sheet with the following information:

  1. Name of submitted algorithm
  2. Type of submitted algorithm, proposed security level, and proposed environment.
  3. Principal submitter's name, telephone, fax, organization, postal address, e-mail address
  4. Name(s) of auxiliary submitter(s)
  5. Name of algorithm inventor(s)/developer(s)
  6. Name of owner, if any, of the algorithm (normally expected to be the same as the submitter)
  7. Signature of submitter
  8. (optional) Backup point of contact (telephone, fax, postal address, e-mail)

B. Primitive specification and supporting documentation

  1. A complete and unambiguous description of the primitive in the most suitable forms, such as a mathematical description, a textual description with diagrams, or pseudo-code.  The specification of a primitive using code is not permitted.  Input and output should be in the form of binary strings.  For asymmetric algorithms, a method for key generation and parameter selection needs to be specified.
  2. A statement that there are no hidden weaknesses inserted by the designers.
  3. A statement of the claimed security properties and expected security level, together with an analysis of the primitive with respect to standard cryptanalytic attacks.  Weak keys should also be considered.
  4. A statement giving the strengths and advantages of the primitive.
  5. A design rationale explaining design choices.
  6. A statement of the estimated computational efficiency in software.  Estimates are required for different sub-operations like key setup, primitive setup, and encryption/decryption (as far as applicable).  The efficiency should be estimated both in cycles per byte and cycles per block, indicating the processor type and memory. If performance varies with the size of the inputs, then values for some typical sizes should be provided.  Optionally the designers may provide estimates for performance in hardware (area, speed, gate count, a description in VHDL).
  7. A description of the basic techniques for implementers to avoid implementation weaknesses.

C. Implementations and test values

  1. A reference implementation, in portable C. For symmetric primitives, NESSIE has specified an API, published on the NESSIE web site. For asymmetric primitives, it is allowed to use a `standard’ library for mathematical functions, such as multi-precision arithmetic (e.g., Lydia). See here for more information.
  2. A sufficient number of test vectors. The NESSIE project will supply software to generate test vectors for symmetric primitives.
  3. Optionally, an optimized implementation for some architectures, a JAVA implementation, an assembly language implementation.

D. Intellectual property statement

A statement that gives the position concerning intellectual property position and the royalty policy for the primitive (if selected).  This statement should include an undertaking to update the NESSIE project when necessary.

Requirements:

An acknowledgment will be sent by email and by regular mail within 5 working days.

General questions for clarification of the formal submission requirements and of the evaluation criteria can be sent.  Answers to questions that are relevant to other submissions will be made available at www.cryptonessie.org.  The NESSIE project will endeavour to answer all relevant questions in a timely manner.

 

Call for Evaluation Criteria


In addition to the criteria given above, the NESSIE project also invites suggestions for Evaluation Criteria, such as testing methodologies (eg. statistical testing).

 

Further Information

Website: http://cryptonessie.org.