6.857 Homework Problem Set 1 # 1-3 - The SHA-3 CompetitionAnonymous March 12, 20091 SkeinThe Skein Hash Function Family, proposed by Ferguson et Al., uses the ThreeFish block cipheras its compression function and the UBI (unique block iteration) chaining mode. The authorsintroduce a key element that they call a tweak. For each block of the plaintext, the tweak containsthree fields: two flags that indicate if the current block is the first or the last one of the plaintextand a value indicating the number of bits compressed so far. The tweak is meant to protect againstcut-and-paste attacks. Each ThreeFish invocation, thus, receives as input the cyphertext from theprevious compression block in the chain xor-ed with the plaintext for that block, the tweak andthe plaintext for this block.Although the authors claim security for the ThreeFish cipher, only the compression function claimsare substantiated with proofs. The authors have compiled the proofs in a separate paper [1] (seesecond-to-last paragraph on page 30) and just provided discussions or sketches of proofs in thisreport. For each of the following security claims, the authors state that they provided proofs in [1].• Indifferentiability from a random oracle (top of page 32),• Pseudorandomness of the keyed Skein (page 31)• Collision resistance (bottom of page 30)• Preimage resistance (page 28 and bottom of 29)The authors also prove the following• Based on the assumption that ThreeFish is PRP, Skein in the keyed mode for a MAC is notsubject to length extension attack (page 31)• If the compression function is PRF, so is Skein in HMAC mode (page 32).• When used as a stream cipher, Skein is indistinguishable from random and when used as aPRNG it is forward secure, if ThreeFish is PRP (top of 33).• Resistance against r-collisions (page 28).It seems that the authors are proving resistance to computing near misses, that is finding twomessages whose hashes have small Hamming distance (they claim resistance on the top of 29 andstate it is backed by proofs on bottom of 29).Although the authors present empirical results, they do not prove the following• Preimage resistance and collision resistance of the ThreeFish compression function. It is usualto assume the security of the atomic primitive when proving results about the overall scheme.1• Resistance to differential and linear cryptanalysis. They provide an attack example in Section9.3.4 (starting on page 54) to show how unlikely linear and differential attacks are to besuccesful by explaining that Skein maximizes the amount of diffusion which has been a causeof previous such attacks on old tools.[1] M. Bellare, T. Kohno, S. Lucks, N. Ferguson, B. Schneier, D. Whiting, J. Callas, and J. Walker”Provable Security Support for the Skein Hash Family”2 ECHOECHO is a hash function that is built off of AES. The paper mostly proves properties regarding itsmodes of operation:• It is built using the Merkle-Damgard construction, which means that it has collision-resistanceand preimage-resistance provided that the compression function has these properties. [p. 40]• It uses the HAIFA framework, which makes the construction resistant to length-extensionattacks when used for a MAC [p. 40].• It uses a “double-pipe” strategy (the chaining value is twice as long as the output value).They claim that this makes the scheme resistant to multi-collision attacks (assuming thecompression function is sufficiently secure), as well as herding attacks. [p. 41] (They do notprove these claims, although they reference the literature about double-pipes.)The paper proves some claims about its resistance to certain forms of cryptanalysis [pp. 28-32],though not for the algorithm as a whole.The paper offers empirical rather than mathematical arguments for resistance to linear cryptanalysisand differential crytanalysis [p25]. They base these claims on the general agreement that AESis a good source of confusion and diffusion, so that AES is resistant to differential and linearcryptanalysis, and thus that the hash function (which is based on AES) is also resistant.3 Dynamic SHA2The main principle for Dynamic SHA2 is “When the message is changed, the calculation will bedifferent” [pg 2]. Overall, the author uses parts of SHA-2 and introduces this design principle inorder to strengthen the design. Some of the main features are• Dynamic SHA2 uses the G, R and ROTR functions from SHA2• Dynamic SHA2 does not use any constants. The author claims that this is because it isalready “secure enough”[pg 11]. Yet later the author claims that Dynamic SHA2 would bemore secure with the use of a constant(s).[pg 19]• Dynamic SHA2 is preimage resistant since the probability of an attacker being able to guessthe individual parts and parameters used is the same as the probability of the attacker beingable to randomly guess the preimage. [section 3.3 pg 12]2• Dynamic SHA2 is second preimage resistant. [section 3.4 pg 12]• Dynamic SHA2 is collision resistant. Even an birthday attack will be a workload O(2112) forthe 224-bit version. [section 3.5 pg 14]• It is resistant to multi-block collision attacks and generic length extension attacks. [pg 34, noconcrete proof]• The author demonstrates a much better cipher by way of the paper itself, since it is impossibleto understand the paper because of many English and logic errors. [all pages]Example: “So the probability of find out a message that has the given given output is2−512× 2128= 2384.” [pg 19]4 ESSENCEESSENCE is a hybrid cryptographic hashing algorithm based on Merkle hash trees combined withMerkle-Damgard iterative hashing structures. It is designed to be flexible and attempts to balanceease of implementation and security concerns.The ESSENCE algorithm’s cryptographic security receives a fairly complete treatment in the NISTsubmission, concentrating mostly on the security of its compression functions. ESSENCE claimsthe following security properties:• In order to prevent cache-timing attacks, The ESSENCE algorithm can be implemented withconstant execution times (at a cost of performance).• To protect from side-channel attacks such as memory leaks or fault analysis, ESSENCEcompression functions can also be implemented entirely within the register file of a processor.• ESSENCE uses a so-called “G” Function as its compression function. It consists of twoapplications of the “E” permutation with an “F” feedback function.
View Full Document
Unlocking...