SHA submission Tweaked version:
270 pages
English

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

SHA submission Tweaked version:

-

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
270 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

SHA-3 submission – Tweaked version: 2009-09-15 SIMD Is a Message Digest Principal submitter: Gaetan Leurent Ecole Normale Superieure Departement d'Informatique 45, rue d'Ulm 75005 Paris France Tel: +33.1.44.32.20.47 Fax: +33.1.44.32.21.51 Auxiliary submitters: Charles Bouillaguet, Pierre-Alain Fouque Algorithm inventors/developers: Gaetan Leurent, Charles Bouillaguet, Pierre-Alain Fouque Backup contact: Pierre-Alain Fouque Ecole Normale Superieure Departement d'Informatique 45, rue d'Ulm 75005 Paris France Tel: +33.1.44.32.20.48 Fax: +33.1.44.32.21.51 Last revision: 2009-09-15

  • start preimage

  • attack has

  • compression function

  • message expansion

  • version simd

  • free- start distinguishers

  • sha designs

  • tweaked version

  • merkle-damg˚ard design


Sujets

Informations

Publié par
Nombre de lectures 12
Langue English

Extrait

SHA3 submission – Tweaked version: 20090915
SIMD Is a Message Digest
Principal submitter:
Gaëtan Leurent ÉcoleNormaleSupérieure Département d’Informatique 45, rue d’Ulm 75005 Paris France
Gaetan.Leurent@ens.fr Tel: +33.1.44.32.20.47 Fax: +33.1.44.32.21.51
Auxiliary submitters:
Charles Bouillaguet, PierreAlain Fouque
Algorithm inventors/developers:
Gaëtan Leurent, Charles Bouillaguet, PierreAlain Fouque
Backup contact:
PierreAlain Fouqu é Ecole Normale Supérieure Département d’Informatique 45, rue d’Ulm 75005 Paris France
PierreAlain.Fouque@ens.fr Tel: +33.1.44.32.20.48 Fax: +33.1.44.32.21.51
Last revision: 20090915
2
About the tweak
3
This document defines the version 1.1 ofSIMD. The following modifications have been made since version 1.0:
(i) The permutationsphave been optimized to provide a better security. (i) (i) The rotationsrandshave been optimized to provide a better security.
We introduce a new family of strengthened versionsSIMD+with more rounds thanSIMD. These versions can be used if strong security margins are needed.
We introduce a new family of reduced versionsSISDwhich can be used in constrained environment when only a short tag is needed. These versions can also be useful to develop cryptanalysis techniques.
TheIVand the test vectors have been updated.
The tweak has essentially no effect on the performances ofSIMD. This tweak is motivated by the discovery of a differential distinguisher on the compression function ofSIMD512This distinguishing attack has complexity1.0 by Nad and Mendel [21]. 427 2 and is a based on a differential trail where no difference is introduced in the message, but a 507 specific difference Δinin the chaining value can go to a difference Δout.with probability 2 The attack is possible because the diffusion in the compression function is relatively slow and the permutations and rotations ofSIMD1.0 have some bad properties that allow good differential paths. The tweak prevents the attack in its current form by removing unwanted properties of the permutations and rotations, but it is possible that future improvements give a distinguisher based on similar ideas. However, we decided to not increase the number of rounds ofSIMDbecause we believe that such distinguishers do not threaten the security ofSIMD. The compression function ofSIMDwas designed with the idea that the message input and the chaining value input of the compression function have a different role. An attacker can easily control the message input, but the chaining value can only be chosen by hashing a previous block. That is why we use a strong message expansion step, and the chaining value undergoes less transformations. Moreover, sinceSIMDis using a widepipe design, attacks on the compression function which require control of the chaining value are very unlikely to be transferable to the full hash function. For instance a freestart preimage attack on the compression compression can not be used to break the hash function, even if it is only has unit cost. Therefore, we believe that it not worth increase the number of rounds to avoid potential free start distinguishers, but we provide a strengthened versionSIMD+for those who feel otherwise.
4
Introduction
5
TheSIMDIt is based onhash function is quite similar to members of the MD/SHA family. afamiliarMerkleDamga˚rddesign,wherethecompressionfunctionisbuiltfromaFeistellike cipher in DaviesMeyer mode. However there are some innovations in this design: the internal state is twice as big as the output size, we use a strong message expansion, and we use a modified feedforward in the compression function. The main design criteria was to follow the MD/SHA designs principle which are quite well understood, and to add some elements to avoid all known attacks. SIMDis particularly efficient on platforms with vector instructions (SIMD) which are available on many processors. Such instructions have been proposed since 1997 and are now widely deployed. Moreover, it is also possible to use two cores on multicore processors to boost the performance with a factor 1.8 by splitting the message expansion function and the hashing process.
6
Contents
1
2
3
4
Algorithm Specification and Rationale 1.1 Mathematical Preliminaries and Notations . . . 1.1.1 The FieldF257. . . . . . . . . . . . . . 1.1.2 The NumberTheoretic Transform . . . 1.1.3 The RingsZ2andZ2. . . . . . . . . 16 32 1.1.4 Superscripts and Subscripts . . . . . . . 1.2 Description of the Algorithm . . . . . . . . . . 1.2.1 Mode of Operation . . . . . . . . . . . . 1.2.2 The Message Expansion . . . . . . . . . 1.2.3 The Feistel Ladder . . . . . . . . . . . . 1.2.4 The Final Compression Function . . . . 1.2.5 Initialization Vector . . . . . . . . . . . 1.2.6 Input and Output . . . . . . . . . . . . 1.3 Rationale . . . . . . . . . . . . . . . . . . . . . 1.3.1 Iteration Mode . . . . . . . . . . . . . . 1.3.2 DaviesMeyer . . . . . . . . . . . . . . . 1.3.3 The Message Expansion . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
Implementation Aspect and Performances 2.1 Software Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 SIMD Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Optimized Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Multicore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 8bit Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Hardware Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Expected Strength 3.1 Security of the compression function . . . . . . . . . . . . . . . . . . . . . . . . .
Security Analysis 4.1 Mode of Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Mode of Operation for the Hash Function . . . . . . . . . . . . . . . . . . 4.1.2 Security Results for Some Hash Based Constructions . . . . . . . . . . . . 4.1.3 Mode of Operation for the Compression Function . . . . . . . . . . . . . . 4.2 Security of the Compression Function . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Resistance to Differential Cryptanalysis . . . . . . . . . . . . . . . . . . . 4.2.2 The Step Update Function . . . . . . . . . . . . . . . . . . . . . . . . . .
7
9 9 9 9 10 10 10 11 12 15 19 21 21 24 24 24 26
27 27 27 28 29 29 30 30
31 31
33 33 33 33 34 34 34 34
8
5
4.3
4.4
CONTENTS
Reduced Versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1SISDn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2SIMDn/2.k. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3SIMDn/k. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Strengthened Versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Advantages and Limitations 5.1 Parallelism . . . . . . . . . 5.2 Security . . . . . . . . . . . 5.3 Performance . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A Test Vectors A.1SIMD224. . . . . . . . . . . . A.1.1 Empty Message . . . . . A.1.2 Oneblock Message . . . A.1.3 Twoblock Message . . . A.2SIMD256. . . . . . . . . . . . A.2.1 Empty Message . . . . . A.2.2 Oneblock Message . . . A.2.3 Twoblock Message . . . A.3SIMD384. . . . . . . . . . . . A.3.1 Empty Message . . . . . A.3.2 Oneblock Message . . . A.3.3 Twoblock Message . . . A.4SIMD512. . . . . . . . . . . . A.4.1 Empty Message . . . . . A.4.2 Oneblock Message . . . A.4.3 Twoblock Message . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
35 35 36 36 37
39 39 39 39
43 44 44 51 64 85 85 92 106 127 127 139 163 198 198 210 234
Chapter
1
Algorithm Rationale
Specification
and
This document defines theSIMDfamily of hash functions. This family is based on two functions SIMD256andSIMD512; we defineSIMDnwithn256 as a truncation ofSIMD256, and SIMDnwith 256< n512 as a truncation ofSIMD512. Each functionSIMDntakes as input a message of arbitrary size, and outputs a digest ofn bits.
1.1
Mathematical Preliminaries and Notations
The design ofSIMDuses a number of different operations with useful mathematical properties. In this section, we introduce the operations that will be used through this document, and detail their properties.
1.1.1 The FieldF257 Since 257 is a prime, the ringZ257of the integers modulo 257 is a fieldF257operations in. The this field are denoted with (mod 257). We chose this field because we can easily map a byte to an element of the field, and the operations inF257can be computed efficiently in software and in hardware.
1.1.2 The NumberTheoretic Transform The Numbertheoretic transform of sizeninF257is defined as:
n n F NTTn:F257 2 57
n1n1 (x)7→(y: j j=0i)i=0
n1 X ij yi=xjω j=0
(mod 257).
wheren256, andωis anth root of unity inF257can see it as a polynomial evaluation:. We P n1 n1j if the sequence (x) is inte s a polynomialP(X) j j=0rpreted a =xjX, then we haveyi= j=0 i P(ω).
9
10
CHAPTER 1.
ALGORITHM SPECIFICATION AND RATIONALE
This transform is identical to the Discrete Fourier Transform but it operates on a finite field n instead of the field of complex numbers. It is a bijection ofF. It can be computed efficiently 257 by the same algorithm as the Fast Fourier Transform, which has a complexity ofO(nlogn) field operations.
1.1.3 The RingsZ2andZ2 16 32 16 32 Z2denotes the ring of integers modulo 2 , andZ2denotes the ring of the integers modulo 2 . 16 32 We useandto represent the modular addition and multiplication in these rings. (Actually, we only useinZ2andinZ2). 32 16 We can represent elements ofZ2by 16bit words, and elements ofZ2by 32bit words. 16 32 Thus, we define the following bitwise boolean functions on 32bit words:
IF(A, B, C) = (AB)(¬AC) MAJ(A, B, C) = (AB)(AC)(BC)
wheredenotes the booleanOR,denotesAND, and¬denotesNOT. We also usefor the exclusive or (XOR).IFacts as a conditional, andMAJThese function areis the majority function. already used in some hash functions because they have good properties: the output is unbiased, and no input bit has a linear effect on the output. We also use bitwise rotations on 32bit words:xrotated to the left bysbits is denoted by s x.
1.1.4 Superscripts and Subscripts (i) Since the compression function consists of the repetition of a simple round function, we useX to denote the variableXassociated with roundimany variable can be seen as. Meanwhile, vectors, and we useX[0..k]to denote the vector [X0, X1, ...Xk] (or its transpose, depending on the context).
1.2
DescriptionoftheAlgorithm
SIMDnentompocniamehT.ngiseddarg˚amDlerkMeheofllwotsitnohttahashfuncterativeiinas p m p ofaMerkleDamga˚rdhashfunctionhis a compression functionC:{0,1{} × 0,1{} → 0,1}. To computeh(M), the messageMis first divided intokchunksMi’s ofmthebits. Then compression function is used to compress the message chunks and the internal state:Hi+1= C(Hi, Mi). There is a padding rule to fill the lastmbit blocks, and the padding usually includes the message size (this is known as the MerkleDamg˚ard strengthening). The initial value of the internal stateHi1is calledIVand is fixed in the description of the hash function. The output p n of the hash function is given by computing a finalization functionD:{0,1} → {0,1}on the last internal stateHk1. The DaviesMeyer mode is a common way to build a compression functionCfrom a block cipherE: it is defined asC(h, m) =Em(h)hhash functions use a custom block cipher,. Many designed with a message expansion step, and a Feistel ladder. TheSIMDfamily uses a similar design, and the size parameters are as follows:
SIMD256 SIMD512
Output sizen 256 512
Message block sizem 512 1024
Internal state sizep 512 1024
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents