6.857 Homework Problem Set 1 # 1-3 - SHA-3 CompetitionVictor WilliamsonTrevor RundellOliver Yeh March 12, 20091 Analysis of SHA-3 Hash Functions1.1 OverviewThe four hash functions that we analyzed are as follows...• FSB• Lesamnta• SHAvite-3• JH1.2 FSBMode of Operation The Merkle-Damgard domain extender is the mode of operation. Its securityis proved sufficient by noting that the Merkle-Damagard domain extender, despite weaknesses, isbelieved to propagate the main security features from the compression function to the hash function(pg. 6). A final compression function is used to obtain birthday bound compatible brute forcesearch protection. Whirlpool is used as the final compression function because it is non-linear andrelatively complex enough to be deemed a safe choice. It is insisted that the final compressionfunction itself does not have to be collision resistant or hard to invert for the hash to be (pg.6). The security of the FSB parallels the security of the Markle-Damgard domain extender whichgives complexities 2size2for collision resistance, 2sizefor preimage resistance and 2size−kfor secondpreimage resistance. (pg. 10)Collision Resistance The proof is based on difficult computation problems from coding theory(pg. 14), particularly the syndrome primitive where computation syndrome decoding and codewordfinding is NP-hard. The proof states that finding a collision for the FSB compression function isat least as difficult as finding a codeword of weight two times the Hamming weight generated bythe compression function. (pg. 19)Preimage-resistance Similarly, the proof states that inverting the FSB compression function isat least as difficult as solving the syndrome decoding problem using the Hamming weight w asinput. (pg. 19)Second preimage resistance aka Weak Collision Resistance The proof states that finding asecond preimage for the FSB compression function using Hamming weight w is at least as difficultas finding a codeword of weight ≤ w in code whose parity check matrix is a defined submatrix ofH, where H is the binary r × n matrix produced by the syndrome primitive. (pg. 19)11.3 LesamntaMode of Operation The domain extension scheme consists of Merkle-Damgard iteration of thecompression function and an output function to achieve Merkle-Damgard securities as well assecurity against extension attacks. For the compression function Lesamnta uses one of the twelvePGV modes called Matyas-Meyer-Oseas (MMO) which is one of the more secure of the PGV modesin terms of collision resistance and preimage resistance. The security of MMO is reducible to thesecurity of the underlying block cipher in terms of proof-based and attack-based security. MMOmode prevents an attacker from exploiting poor key scheduling to gain control of the block cipherkey (pg. 51).Indifferentiability from a random oracle This is proven using the assumption that the blockciphers named E and L used for the compression function and ouput function respectively areindependent ideal ciphers. It is shown that Lesamnta is indifferentiable from a VIL random oraclein the ideal cipher model and resists attacks for fewer than 2n/2(pg. 62).Collision Resistance This is proven using the assumption that the compression function h and theoutput function g are ideal ciphers and collision resistant. The proof that MMO mode is collisionresistant is referenced to Black et al.’s “Black-box analysis of the block-cipher-based hash-functionconstructions from PGV” which concludes an adversary must make 2n/2queries to find a collision,where n is the block length of the block cipher (pg. 60, 61).Preimage Resistance This is proven using the assumption that the block cipher E is in place ofthe ideal cipher. The ideal cipher model is analyzed to show that the pre-advantage of an attackeris minimal and equal to12n−q(pg. 60).Pseudorandomness The proof holds under the assumption that the block ciphers E and L areindependent pseudorandom permutations. It is shown that if E is a secure cipher then Lesamntais a pseudorandom function by showing that the prf-advantage and prp-advantage of an adversaryis within bounds of the advantage obtained with a secure block cipher (pg. 61).HMAC Lesamnta supports HMAC as specified in FIPS 198 by showing that HMAC security isreducible to the security of the underlying block ciphers E and L as used in the compression functionand output function respectively. The proof of pseudorandomness ensures the security of HMACusing Lesamnta requires an adversary to make 2n/2queries which is infeasible because Lesamntaonly operates with n ≥ 224. The proof by Bellare in “New proofs for NMAC and HMAC: Securitywithout collision-resistance” is referenced as part of the proof (pg. 62).Length-extension attacks It is shown that the output function makes length-extension attacksimpossible. Furthermore it is stated that already proven indifferentiability from a random oracleimplies security against length-extension attacks (pg. 63).Multicollision Attack If Joux’s multicollision attack as outlined in “Multicollisions in iteratedhash functions. Application to cascaded construction,” is used on Lesamnta to find 2tcollisions itrequires complexity O(t2n/2), which is infeasible for an attacker (pg. 64).Kelsey-Schneier Attack for Second-Preimage-Finding If Kelsey-Schneier’s “Second preim-ages on n-bit hash for much less than 2n” is used to attack, Lesamnta has second-image securityresistance approximately n − k bits for messages shorter than 2k(pg. 64).Differential and Linear Attacks It is stated that the maximum differential characteristic prob-2ability for 12 rounds in Lesamnta-256 is less than 2−256and message block space size 256-bit, bothof which are not adequate for Wang et al. differential attacks which require higher differential char-acteristic probability and a larger block space size. This was shown by abstracting exact differencesas patterns of active S-boxes, applying the wide trail strategy, and making experiments with theViterbi algorithm (pg. 67).Interpolation Attack The proof expresses Lesamnta-256 using the AES S-box as a polynomialof degree 254 over GF(28). After a few rounds, Lesamnta can be expressed as a polynomial with32 variables, and after 10 rounds the output depends on all 32 variables. From the high degree ofthe S-box it is expected that the number of coefficients reaches the maximum sometime after the10th round. Thus it is believed the full 32 rounds of Lesamnta is
View Full Document
Unlocking...