Practical Key Recovery Attack against Secret IV Edon R

Gaëtan Leurent

Description

Practical Key Recovery Attack against Secret-IV Edon-R Gaëtan Leurent École Normale Supérieure – Département d'Informatique, 45 rue d'Ulm, 75230 Paris Cedex 05, France Abstract. The SHA-3 competition has been organized by NIST to se- lect a new hashing standard. Edon-R was one of the fastest candidates in the first round of the competition. In this paper we study the security of Edon-R, and we show that using Edon-R as a MAC with the secret- IV or secret-prefix construction is unsafe. We present a practical attack in the case of Edon-R256, which requires 32 queries, 230 computations, negligible memory, and a precomputation of 252. The main part of our attack can also be adapted to the tweaked Edon-R in the same settings: it does not yield a key-recovery attack, but it allows a selective forgery attack. This does not directly contradict the security claims of Edon-R or the NIST requirements for SHA-3, since the recommended mode to build a MAC is HMAC. However, we believe that it shows a major weakness in the design. Key words: Hash functions, SHA-3, Edon-R, MAC, secret IV, secret prefix, key recovery. 1 Introduction In 2005, a team of researchers led by X.

• against iterated


• macs based


• based


• hash functions


• secret key


• against many


• secret prefix


• recovery attack against


• mac oracle

Sujets

• Hash function
• Key (cryptography)

Informations

• Publié par: pefav
• Nombre de lectures: 9
• Langue: English

Extrait

PracticalKeyRecoveryAttack againstSecret-IV Edon - R GaëtanLeurent ÉcoleNormaleSupérieure–Départementd’Informatique, 45rued’Ulm,75230ParisCedex05,France [e-mail] Abstract.TheSHA-3competitionhasbeenorganizedbyNISTtose- lectanewhashingstandard. Edon - R wasoneofthefastestcandidates inthefirstroundofthecompetition.Inthispaperwestudythesecurity of Edon - R ,andweshowthatusing Edon - R asaMACwiththesecret- IVorsecret-prefixconstructionisunsafe.Wepresentapracticalattack inthecaseof Edon - R 256,whichrequires32queries,2 30 computations, negligiblememory,andaprecomputationof2 52 .Themainpartofour attackcanalsobeadaptedtothetweaked Edon - R inthesamesettings: itdoesnotyieldakey-recoveryattack,butitallowsaselectiveforgery attack. Thisdoesnotdirectlycontradictthesecurityclaimsof Edon - R orthe NISTrequirementsforSHA-3,sincetherecommendedmodetobuilda MACisHMAC.However,webelievethatitshowsamajorweaknessin thedesign. Keywords:Hashfunctions,SHA-3, Edon - R ,MAC,secretIV,secret prefix,keyrecovery. 1Introduction In2005,ateamofresearchersledbyX.Wangproducedbreakthroughattacks againstmanywidelyusedhashfunctions,includingMD5[12]andSHA-1[11]. ThishasledNISTtocallforanewhashfunctiondesign,andtolaunchthe SHA-3competition[7].Thiscompetitionhasfocusedtheattentionofmany cryptographers,andNISTreceived64submissions.51designswereacceptedto thefirstround. Edon - R wasoneofthefastestcandidatesinthefirstroundofthecompeti- tion.Ithasreceivedsomeattentionfromthecryptographiccommunity,resulting invariousattacksonthecompressionfunction.Thereisalsoapreimageattack onthefullhashfunction,butitrequiresofhugeamountofmemorymakingit debatable. Inthispaperweshowanewattackon Edon - R ,whenusedinthesecret-IV orsecret-prefixMACconstruction.Thismodeofoperationisnotclaimedtobe securebythedesigners,butourattackhasnomemoryrequirement,andiseven practicalattack,whilepreviousattacksarelargelytheoretical.Ourapproach issimilartotheonefollowedbyWangetal.whostudiedasimilarMACused 1