Sha 3

Orange Labs
Issy-les-Moulineaux, France

SHA-3 Proposal: ECHO

Ryad Benadjila Olivier Billet Henri Gilbert Gilles Macario-Rat Thomas Peyrin Matt Robshaw Yannick Seurin

Version 2.0 July 20, 2010

Overview
This document provides an update to the original description of echo that was submitted to NIST. echo embodies the goal of reusing—and thereby echoing— as many aspects of the AdvancedEncryption Standard (AES) [58] as possible. This is not just in terms of operations, though only AES operations are used in echo, but also in terms of simplicity and analysis. echo replicates the structure of the AES in several ways and has the following features: 1. The smooth support—using the same implementation—of any hash output of length from 128 to 512 bits. 2. The smooth support—using thesame implementation—of both the singlepipe and double-pipe strategy. Update: Some SHA-3 submissions use single-pipe constructions. While we prefer the security provided by a double-pipe construction, we note that echo can easily be adapted to support a single-pipe construction giving a significant performance improvement at the same time. 3. Avoiding a key schedule. It is well-known that thedesign of a “key schedule” or some form of “message mixing” for a hash function is deceptively difficult. This has been the problem at the root of the MD/SHA family and has even been reported as a potential problem for the AES itself [13, 12]. Update: Any NIST SHA-3 submission with a key schedule needs to substantiate its resistance to such attacks. It was a deliberate design decision to not have a keyschedule in echo and the opportunity to interfere with a compression function computation once it has begun has been eliminated. 4. An established design approach with attendant security arguments. This allows a particularly accurate differential security analysis and gives a very significant–and independently analysed–margin for security. Update: Many different sophisticated analysis have beenrecently conducted on echo. The best distinguishing attack for the echo compression function covers 4.5 rounds (out of 8) for the 256-bit hash output (which can be improved to 7 rounds if the salt can be controlled by the attacker) and covers 7 rounds (out of 10) for the 512-bit hash output. Concerning collision resistance, the best free-start collision attack for the echo compression function covers 3rounds (out of 8) for the 256-bit hash output and covers 3 rounds (out of 10) for the 512-bit hash output. The best collision attack for the echo hash function covers 4 rounds (out of 8). 5. The ability to reuse AES implementation advances, whether these offer improved performance or improved resistance to side-channel analysis. Also echo can directly exploit AES-inspired processor developmentssuch as Intel’s AES instruction set for Westmere chips [29].

1

Update: Benchmarks on the recent AES-NI capable Intel Core i5 CPU give 6.8 cycles/byte for the 256-bit version of echo and 12.6 cycles/byte for the 512-bit version (resp. 5.8 cycles/byte and 8.4 cycles/byte for the single-pipe construction). We note that echo is the only SHA-3 candidate to support both a double-pipe mode and thepossibility to exploit the AES instruction set. In this updated version of the original submission document, we keep a full description of echo and an overview of our design considerations. However we have added some new and improved performance figures for all implementations, and we provide some additional information that will help to provide points of comparison with other submissions.

2CONTENTS

Contents
I Specifications 5
6 7 8 8 9 10 11 12 13 13

1 Notation and Conventions 2 Domain Extension 2.1 Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Message Padding . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Compression for 128 ≤ Hsize ≤ 256 3.1 BIG.SubWords(S, salt, κ) . . . . . . . . . . 3.2 BIG.ShiftRows(S) . . . . . . . . . . . . . ....