Home > Research > Code-based cryptography > Code-based cryptosystems : implementations > Efficient implementation of a CCA2-secure variant of McEliece using (...)

Efficient implementation of a CCA2-secure variant of McEliece using generalized Srivastava codes

Monday 5 March 2012, by Cayrel, Gerhard Hoffman

Efficient implementation of a CCA2-secure variant of McEliece
using generalized Srivastava codes

(by Pierre-Louis Cayrel, Gerhard Hoffmann and Edoardo Persichetti)

Part 0: Introduction.

This document will outline the details for the source codes of the above
publication. It is our hope that it might help people interested in code-based
cryptography to put this subject further by another step.

NOTE: At the moment, we do not plan to provide free access to the source codes. However, that does not mean that access is completely restricted.

Anyone seriously interested in code-based cryptography, who can outline why he or she needs the sources codes, please feel free to contact us.

The source consists basically of two parts. The first one is running on the PC, producing the necessary Generalized Srivastava (GRSV) codes, secret support etc. The second one is run on a microcontroller, simulated by AVRStudio, version 5. It contains the decrypting part of the McEliece system based on GSRV codes. That means, the matrices representing the secret code have been copied manually to the device.

A note about the simulator in AVR Studio:
Debugging takes a very long time. Running the program in the simulator might take more than two hours, whereas the actual runtime in hardware would be under a second. The reason for this huge gap is that the graphical window of the debugger will be updated for each cycle the simulated processor is doing.
As there is no way to turn off graphics under Windows, there seems to be only one way around this restriction: the use of some sort of real hardware (JTAG etc.).

For the parameters we have used, please see the above paper. The actual memory layout for the device has to be set inside AVRStudio itself, which unfortunately means that it does not show up directly in source code. For convenience, we will give the various settings when discussing the two source code versions for the microcontroller sources.

For the assembler implementation of Keccak code made public by the Keccak team has been used (with some minor modifications). Otherwise, the code has been written in C.

Part 1: The PC part for generating the codes. (avr_gen_code.tgz)

The most important files are:

The source also contains an implementation of Paulo’s algorithm for generating the necessary codes.

Part 2.1: The microcontroller sources for the above publication.
(avr-version-paper.tgz).

Header files:
* asf.h           /* AVR specific file                                       */
* AVR8-rotate64.h /* Declarations used for Keccak                            */
* AVR-StDK.h      /* Declarations for exp/anti-log tables and H and G        */
* base_sram.h     /* Exp/anti-log tables for base field.                     */
* binpoly.h       /* Declarations of data structure for binary polynomials   */
* c_sram.h        /* Used for debugging purposes. c for codeword.            */
* cca2_mceliece.h /* Not used. Functionality contained in grsv.c.            */
* e_sram.h        /* Memory for the error vector.                            */
* eexp.h          /* exponential table for the extension field.              */
* elog.h          /* anti-log table for the extension field.                 */
* G.h             /* The public generator matrix.                            */
* global_defines.h/* Global definitions and macros.                          */
* gsrv.h          /* declarations for encoding and decoding using GSRV codes */
                  /* including the CCA2-functionality.                       */
* H0.h
  H1.h
  H2.h
  H3.h            /* The private parity check matrix H                       */
  H4.h            /* The private parity check matrix H has been distributed  */
  H5.h            /* across several header files. The reason is, that the    */
  H6.h            /* AVR-Studio built-in editor handles bigger files badly.  */ 
* Keccak-avr8.h   /* Keccak header file                                      */
* Keccak-avr8-settings.h /*Keccak default setting. 1024 bits per squeeze step*/
* Keccak-avr8-utils.h    /* Utilities for Keccak.                            */
* KeccakF-1600-avr8.h    /* Interface to KeccakF, the workhorse of Keccak.   */
* L.h                    /* Declaration of the secret support.               */
* secrand.h       /* Secure pseudo random generator.                         */
* univset.h       /* Utility used for pseudo random generator.               */
* msg_sram.h      /* Message used for encoding.                              */
* mtab_sram.h     /* Multiplication table. Used in field multiplication.     */
* syn_sram.h      /* Memory for syndrome s.                                  */
Assember and source files:
* AVR8-rotate64.s /* Assembler code (bit rotations) for Keccak               */
* AVR-StDK.c      /* Definitions for exp/anti-log tables and H and G         */
* binpoly.c       /* Implementation of binary polynomials                    */
* cca2_mceliece.c /* Not used. Functionality contained in grsv.c             */
* gsrv.c          /* Encoding and decoding using GSRV codes plus CCA2 mode.  */
* Keccak-avr8.c   /* Keccak. Two settings are available: a more conventional */
                  /* c-implementation plus an optimized version with the     */
                  /* Keccak rounds written in assembler (see the assembler   */
                  /* file KeccakF-1600-avr8asm1.s                            */
* Keccak-avr8-utils.s    /* Utilities for Keccak written in Assembler.       */
* KeccakF-1600-avr8asm1.s/* KeccakF, the workhorse of KeccakF written in     */
                         /* assembler.                                       */
* main.c          /* Entry point into program.                               */
* secrand.c       /* Secure pseudo random generator.                         */
* univset.c       /* Utility used for pseudo random generator.               */

The memory layout for the matrices H and G, the exp/log-tables and the support has been defined as follows:

Note that the names of the segments show up in source code. They serve as a convenient way for definition and reference.

Part 2.2: The microcontroller sources for some setting, which did not make it into the paper (avr-version-excluded.tgz).

Header files:
* asf.h           /* AVR specific file                                       */
* AVR8-rotate64.h /* declarations used for Keccak                            */
* binpoly.h       /* declarations of data structure for binary polynomials   */
* eexp.h          /* exponential table for the extension field               */
* elog.h          /* anti-log table for the extension field                  */
* globals.h       /* global declarations for H, G and global macros.         */
* gsrv.h          /* declarations for encoding and decoding using GSRV codes */
* G.h             /* The public generator matrix                             */
* H0.h
  H1.h
  H2.h
  H3.h
  H4.h            /* The private parity check matrix H                       */
  H5.h            /* The private parity check matrix H has been distributed  */
  H6.h            /* across several header files. The reason is, that the    */
  H7.h            /* AVR-Studio built-in editor handles bigger files badly.  */ 
* Keccak-avr8.h   /* Keccak header file                                      */
* Keccak-avr8-settings.h /*Keccak default setting. 1024 bits per squeeze step*/
* Keccak-avr8-utils.h    /* Utilities for Keccak.                            */
* KeccakF-1600-avr8.h    /* Interface to KeccakF, the workhorse of Keccak.   */
* L.h                    /* Declaration of the secret support.               */
* secrand.h       /* Secure pseudo random generator.                         */
* univset.h       /* Utility used for pseudo random generator.               */
Assember and source files:
* AVR8-rotate64.s /* Assembler code (bit rotations) for Keccak               */
* binpoly.c       /* Implementation of binary polynomials                    */
* globals.c       /* Definition of H, G and exp/log-tables                   */
* gsrv.c          /* Encoding and decoding using GSRV codes                  */
* Keccak-avr8.c   /* Keccak. Two settings are available: a more conventional */
                  /* c-implementation plus an optimized version with the     */
                  /* Keccak rounds written in assembler (see the assembler   */
                  /* file KeccakF-1600-avr8asm1.s                            */
* Keccak-avr8-utils.s    /* Utilities for Keccak written in Assembler.       */
* KeccakF-1600-avr8asm1.s/* KeccakF, the workhorse of KeccakF written in     */
                         /* assembler.                                       */
* main.c          /* Entry point into program.                               */
* secrand.c       /* Secure pseudo random generator.                         */
* univset.c       /* Utility used for pseudo random generator.               */

The memory layout for the matrices H and G, the exp/log-tables and the support has been defined as follows:

Note that the names of the segments show up in source code. They serve as a convenient way for definition and reference.