6.857 Homework Problem Set 1 # 1-3 The SHA-3 CompetitionAnonymous March 12, 2009We felt that out of KECCAK, LUX, AURORA, and TIB3, AURORA was the best one becauseof breath and depth of the security analysis provided. The AURORA submission provided proofsof resistance against several attacks as well as proofs of pseudo-randomness and indifferentiabilityfrom a random oracle.Security Properties of KECCAKBackground on sponge function: The KECCAK[r,c,d] sponge function, with parameterscapacity c, bitrate r, and diversifier d, is obtained by applying the sponge construction to KECCAK-f[r+c] and by applying a specific padding ot the input (page 3) [?].Shortcut attack: In the KECCAK specifications, shortcut attack is defined as an attack on thesponge function yielding higher expected success probability than the same attack on a randomoracle, for a given workload. (page 4)Workload: The workload of an attack on a sponge function is expressed in terms of the numberof calls to the underlying function. The workload of an attack on a random oracle is the sum of theworkload of all queries sent to the random oracle by the attacker. For KECCAK[r,c,d], the workloadof a single query with input length l and requesting n output bits is given by b8bl8c+24rc + dnre calls.(page 4)Flat sponge claim: Given the capacity c (and possibly a limitation on the input and/or outputsizes), the success probability of any attack should be smaller than or equal to the maximum of thatfor a random oracle and 1 − e(22y−(c+1)), with N = 2ythe number of calls to the round function (orits inverse). For each supported parameter values of the sponge function, the authors make such aflat sponge claim. (page 12) [?]Claim regarding shortcut attack: The expected success probability of any shortcut attackagainst KECCAK[r,c,d] (the sponge function) with a workload equivalent to N calls to KECCAK-f[r+c] (the underlying function) or its inverse shall be smaller than or equal to 1−e(−N(N +2)2−(c+1)).(page 4)Claim regarding representation: The authors also acknowledge weaknesses of KECCAKsponge functions due to the fact that these functions can be described compactly and can beefficiently executed, e.g., the so called random oracle implementation impossibility. (page 4)1Security Properties of LUXThe security properties of LUX are discussed section 4, “Resistance to Attacks”, of the supportingdocumentation for LUX [?]. No rigourous proofs are provided.The authors provide arguments about the resistance of LUX to attacks that require collitions,specifically the multicollision attack, herding attack, and second preimage attack (pages 10-13).However, the attacks discussed were designed against Merkle-Demgrad constructions, and LUXis not such a construction. The arguments provided draw an analogy between LUX and Merkle-Demgrad, but by the author’s own admission these results are preliminary.The authors claim to have analyzed LUX’s resistance to two types of differential trials attacks:a truncated differential attack and an extension to this attack with structures (page 13). Theauthors do not provide any details on their analysis other than a very brief description of howLUX’s internal transformations relate to the probabilities in a differential trial attack.The authors provide a brief argument as to why LUX is resistant to a specific type of preimageattack called a Meet-in-the-middle attack (page 13). They argue that for LUX-224 and LUX-256this attack would require 2384effort and that for LUX-384 and LUX-512 would require 2768effort.In both cases they state that this is higher than for brute-force.2Security Properties of AuroraThe security properties of AURORA are discussed in section 4, “Security of AURORA” (page67-92), in the file ”AURORA-updated” [?].Proofs of mode of operation security• Indifferentiability from a random oracle The sMD transform with the finalization func-tion is chosen to preserves CR and indifferentiability (PRO) of the underlying compressionfunction. (page 55) The underlying compression function has no differential paths with highprobability that are exploitable in collision-finding attacks or distinguishing attacks. (page59)• Pseudo-randomness HMAC-AURORA-224/256 is proved to be a good PRF. (page 67).HMACAURORA-384/512 is proved to be a good PRF when keyed via the IV. (page 68)HMAC-AURORA-224M/256M is deduced to be a good PRF. (page 68)• Collision resistance AURORA is proved to have a good resistance to existing collisionattacks because of its secure message scheduling. (page 85-87)• Preimage-resistance AURORA is proved to be preimage-resistance. Three preimage at-tacks are analyzed, including Meet-in-the-middle approach, Correcting impossible messages,and SAT-solver approach. (page 88-89)• Second Preimage-resistance AURORA is proved to be second preimage-resistance. Twosecond preimage attacks are analyzed, including “Using collision differentials”, and “Usingmulti-near-collision differentials”, as well as the “Generic long-message second preimage at-tacks”. (page 89-90)• Multi-collision-resistance Multi-collision attack is unlikely to be applicable to AURORA-224M/256M. However, finding K collision for AURORA-224/256/384/512 is not much harderthan finding ordinary collisions. (page 90)• Slide attack-resistance The slide attacks are deduced not to be applicable to AURORA.(page 90)Provable resistance to differential cryptanalysis• Differential attacks can be improved through Diffusion Switching Mechanism (DSM). (page61-63)• The AURORA structure is based on an 8-bit S-box, matrices and a byte diffusion BD design,and all components are byte-oriented. Thus, it is natural for evaluating the immunity againstdifferential cryptanalysis by counting the minimum number of active S-boxes of AURORAstructure using a block cipher evaluation method. (page 82-83)Provable resistance to linear cryptanalysis: Linear attacks can be improved through DiffusionSwitching Mechanism (DSM). (page 61-63)Provable resistance to length-extension attacks: AURORA is proved to be resistant tolength-extension attacks. (page 90)3Security Properties of TIB3The security properties of TIB3 are discussed in section 5, “Security”, of the supporting documen-tation [?].Collision resistance in the black-box modelThe TIB3 hash function uses block ciphers. Given a collision resistant hash function, the authorsshow that TIB3’s integrated scheme, i.e. it’s mode of operation with it’s compression
View Full Document
Unlocking...