Message Shuffling to Prevent Hash Extension AttacksOutlineHash ReviewDesirable PropertiesImplementation Merkle-Damgård Extension AttackExisting Solutions to Extension AttackOur IdeaOur ContributionHigh Level IdeaHow it works ComponentsHow it works InitializeHow it works Determine e valuesHow it works Step 1How it works Step 2How it works Step 3How it works Step 4How it works … continueHow it works End stateHow it works FinalizeImplementation & ResultsImplementationPerformance ResultsConclusionMessage Shuffling to PreventHash Extension AttacksElizabeth Reid, Chris Wilkens, Christina WrightOutline` Hash Review` Properties` Implementation & Issues` Our Solution` Proof of Security` Implementation & ResultsHash ReviewMDigestMOne way (preimage resist.)M xNon-malleabilityM’ x’Desirable PropertiesMSecond preimage resist.M’Implementation` Compression Function` Fixed length input` Ideal hash properties` Collision resistance` Psuedo-random function` Random oracle` Hash Domain Extension` Arbitrary length input` Preserves hash propertiesIV Hm IV H H H … Hvam1m2m3mnMerkle-DamgårdMerkle-Damgård Extension Attack` H(A) = H(B) Æ H(A||C) = H(B||C)IV H H H … H Xvaluea1a2a3anIV H H H … H Xvalueb1b2b3bmH H H … H YvalueH H H … H Yvaluec1c2c3ckc1c2c3ckidenticalExisting Solutions to Extension Attack` Double Hashing` h1(h1(M)||M)` Requires reading data twice` Prefix-free` Restrict input messagesOur IdeaOur ContributionGOALS` Prevent extension attacks` Improve collision resistance` Particularly multicollisions` Only read message onceACHIEVEMENTS` Proved secure against extension attacks` Hypothesized increased collision resistance` Practical speed and space requirementsHigh Level IdeaNORMALHASHhMIX( M )h1h2How it worksComponentsm1m2m3m4… mnFeeder1 2 3 4 5 6 7 8MixerIV H H H H … HvalueHasherHow it worksInitializeFeederMixerIV H H H H … HvalueHasherm1m2m3m4… mn11 : 022 : 033 : 044 : 055 : 066 : 077 : 088 : 04 m12m26m32m4…1mnHow it worksDetermine e valuesFeederMixer11 : 022 : 033 : 044 : 055 : 066 : 077 : 088 : 0IV H H H H … HvalueHasherh1(m1m2… mk) = e1|| e2||…|| eKe1e2e3e4K44 : 022 : 066 : 022:m211:?11 : 022 : 033 : 044 : 055 : 066 : 077 : 088 : 0How it worksStep 14 m12m26m32m4…1mnFeederMixer44:m1IV H H H H … HvalueHasherΓ =…44 : 022 : 066 : 022:m211:?11 : 022 : 033 : 044:m155 : 066 : 077 : 088 : 0How it worksStep 22m26m32m4…1mnFeederMixerHasher22:m2IV H H H H … HvalueHasherΓ =…11 : 022:m233 : 044:m155 : 066 : 077 : 088 : 044 : 022 : 066 : 022:m211:?How it worksStep 36m32m4…1mnFeederMixerIV H H H H … HvalueHasher66:m3Γ =…11 : 022:m233 : 044:m155 : 066:m377 : 088 : 044 : 022 : 066 : 022:m211:?How it worksStep 4M1 M26M32m4…1mnFeederMixerIV H H H H … HvalueHasher22:m4Γ =…11 : 022:m233 : 044:m155 : 066:m377 : 088 : 044 : 022 : 066 : 022:m211:?How it works… continueM1 M26M32M4 …1mnFeederMixerIV H H H H … HvalueHasherΓ =…11 : ?22 : ?33 : ?44 : ?55 : ?66 : ?77 : ?88 : ?11 : ?22 : ?33 : ?44 : ?55 : ?66 : ?77 : ?88 : ?44 : 022 : 066 : 022:m211:?How it worksEnd stateM1 M26M32M4 …1mnFeederMixerIV H H H H … H valueHasher11:mnvalueΓ =…How it worksFinalizevalue H HH HH HHH hMIX(M)Γ = …11:mn22 : ?33 : ?44 : ?55 : ?66 : ?77 : ?88 : ?Implementation & ResultsImplementation` We implemented hMIXin C` We used SHA-1 for both h1and h2` Expect runtime ~2.2 times SHA-1` All bits of the message are hashed twice` Extra time to move blocks` The e values add ~20% to the hashed materialPerformance ResultsConclusion` Theory – with one pass through M,` hMIXis not provably secure against message extension attacks (see paper)` hMIXis not immediately vulnerable to known multicollisionattacks` Practice` hMIXis computationally equivalent to hashing M twice while reading the file once and using 0.5 KB of internal
View Full Document
Unlocking...