6.857 Homework Problem Set 1 # 1-3 - The SHA-3 CompetitionElette BoyleDavid HarvisonRodrigo IpinceBenjamin Switala March 12, 2009Overall AnalysisOut of the four hash functions assigned to our group (ECHO, CRUNCH, SIMD, Dynamic SHA),we selected ECHO as the strongest. The ECHO paper addressed the most security issues, andwas the only one to actually prove resistance in certain cases. They exhibited an ideal resistanceof the function against preimage, 2nd preimage, collision, and k-multi-collision attacks. They alsorigorously show resistance to differential cryptanalysis. In comparison, CRUNCH and DynamicSHA have been found vulnerable to length-extension attacks.CRUNCHThe CRUNCH algorithm is comprised of four stages: preprocessing, encryption permutation, com-pression function and hash computations. Preprocessing is just padding the message and settinginitial values. The encryption permutation stage is based on an unbalanced Feistel scheme. Thenthe compression function is constructed by XORing two permutations from the encryption stageand selecting the number of bits depending on the message length required. The hash computationinvolves using the the compression function and the Merkle-Damgard construction together.In general the author’s arguments are based on previous work in testing designs similar to whatCRUNCH uses but hand wave away the differences between the algorithms.They argue for pseudorandomness based on the symmetric Feistel schemes, while utilizing an un-balanced Feistel scheme. In addition they argue that when the internal functions used in the Feistelscheme are secret they can achieve a proven level of security, though their internal functions arenot secret and they admit that this changes the security bounds. They hand wave and say thatdoing more rounds should increase the security but do not show bounds.In citing collision resistance they cite a paper which studied a hash functions whose compressionfunctions use two permutations of fixed key block ciphers. Using this they claim collision resistanceup to the birthday problem.In claiming preimage resistance they cite they same paper as collision resistance. Using this theymake a claim on the bound of security.They do not mention resistance to differential cryptanalysis, linear cryptanalysis or length extensionattacks. Though according to the SHA-3 Zoo, CRUNCH has been shown vulnerable to lengthextension attacks.Overall, CRUNCH does not seem like a strong competitor in the SHA-3 competition because the1majority of their proofs are hand waved and they have already been shown vulnerable to lengthextension attacks.SIMDThe SIMD algorithm uses a Merkle-Damg˚ard mode of operation. Each compression step is com-puted as:Hi= P (Hi−1, EM0i(Hi−1⊕ Mi)),where• Hiis the ith chaining variable,• Miis the ith message block,• M0iis the result of sending Mithrough a Reed-Solomon-like expansion,• Ek() is a Feistel ladder block encryption with key k, and• P (a, b) is a few extra Feistel rounds, using a as a key to encrypt b.The final compression stage is slightly different from the previous, and the final output is truncatedto the desired output length.The paper cites proofs which show the Merkle-Damg˚ard iteration structure utilized is indifferen-tiable from a random oracle if the compression function is a random oracle. (These papers are[Chang, Nandi], [Lucks], and [Maurer et al].) These papers apparently prove security up to 2nqueries (where n is the length of the hash function), and conclude there are no generic collision,second-preimage, or preimage attacks on this mode of operation. It is important to note that themaintained internal state Hiin SIMD is twice as large as the output, to strengthen against attackslaunched after some number of rounds. This internal-state chaining variable is only truncated inthe final step.The paper includes a discussion of MAC constructions based on SIMD. The first case is using SIMDin the HMAC construction. They state this method can be proved secure by the security proofof [Bellare]. The second case is just taking MACk(M) = SIMD(k||M ); ie, taking SIMD of theconcatenation of they key together with the message M . They assert there are no generic short-cut attacks on this construction, based on the security proof in “the indifferentiability frameworkpaper.”They also consider the application of SIMD as a key derivation function. If the compressionfunction is a pseudorandom function, then SIMD is a PRF. In this case, they assert SIMD is a“good” randomness extractor, based on results in [Fouque, et al].The encryption portion of the compression function is very similar to that of MD5 (and othermembers of the MD/SHA family). Unfortunately, instead of proving or citing proofs of securitystrengths of the function, the paper just quickly mentions the fixes they introduced in attempt toprotect against particular attacks faced by MD5. For instance, they avoided a particular differentialpattern attack by adding an extra rotation in the function design.2They briefly address general differential cryptanalysis in the paper, arguing that the expansion stageprotects against differential attacks by making small changes in inputs yield significant changes inthe outputs. The message expansion algorithm acts like an error-correcting code with high minimumdistance: in their case, any two nonidentical messages will have expansions that vary in at least520 bits in SIMD-256 (or 1032 in SIMD-512). These expanded values are used as the keys tothe encryption steps, and differences between keys will propagate in the nonlinear portion of theencryption. The paper does not, however, provide a rigorous analysis or proof of resistance.This is the extent of the security discussion in the paper. There is no mention of other vulnerabili-ties, such as linear cryptanalytic attacks on potential weaknesses in the encryption nonlinearity, orpotential side-channel attacks on the substitution tables in the Feistel encryption.Dynamic SHADynamic SHA is based on SHA-2, with a twist: the compression function on a so-called “datadependent” function. In the author’s words, “when the message is changed, different rotate rightoperations may be done.” This is unlike old frameworks.Collision resistance and and preimage resistance are claimed, but the proofs are hand-waved. In-differentiabiliity from a Random Oracle is not directly mentioned, but the author admits that somehashes are more probable than
View Full Document
Unlocking...