CubeHash: a simple hash function |
|
CubeHash securityCubeHash offers an array of fast variants as targets for third-party cryptanalysis. Cryptanalysts can vary not only the number of rounds (first try to break CubeHash1, then try to break CubeHash2, etc.) but also the number of bytes per input block (first break CubeHash1/128, then CubeHash1/127, etc.). This web page will track the results of cryptanalysis.CubeHash12008.12.23: Dai reports collisions in CubeHash1/57.2008.12.26: Dai reports collisions in CubeHash1/45: "In an approximation of CubeHash where addition is replaced with XOR, an initial 4-bit difference at the least significant bits of (0-based) state bytes 1 and 9 and the fourth least significant bits of state bytes 18 and 26 eventually leads to zero differences if, after each round, all differences in the first 45 state bytes are eliminated using the next input block. In actual CubeHash, this occurs with high enough probability that a few seconds of unoptimized computation found a pair of colliding messages for CubeHash1/45." 2009.01.02: See below regarding CubeHash2/12; presumably similar comments apply to CubeHash1/12. 2009.01.06: See below regarding CubeHash2/4; presumably similar comments apply to CubeHash1/4. 2009.01.09: See below regarding CubeHash2/3; presumably similar comments apply to CubeHash1/3. 2009.01.12: See below regarding CubeHash2/3; presumably similar comments apply to CubeHash1/3. 2009.02.03: See below regarding CubeHash2/2; presumably similar comments apply to CubeHash1/2. Suggested target for cryptanalysis: CubeHash1/1. Suggested target for practical attacks: CubeHash1/2. CubeHash22008.12.04: Aumasson reports collisions in CubeHash2/120. "No particular computation effort was necessary." For comparison, the standard generic attacks would need to try about 2^32 input messages.2008.12.05: Aumasson reports that a similar technique easily finds collisions in CubeHash2/114. 2008.12.24: Dai reports collisions in CubeHash2/89. 2009.01.02: Dai reports collisions in CubeHash2/12. 2009.01.06: Peyrin reports collisions in CubeHash2/4. 2009.01.09: Brier and Peyrin estimate that collisions in CubeHash2/3 can be found in 2^46 simple operations. 2009.01.12: Dai reports collisions in CubeHash2/3. 2009.02.03: Brier, Khazaei, Peyrin, and Meier estimate that collisions in CubeHash2/2 can be found in 2^196 simple operations. 2009.08.10: Brier, Khazaei, Meier, and Peyrin estimate that second preimages in CubeHash2/2 can be found using 2^221 simple operations, and that collisions in CubeHash2/2 can be found using 2^179 simple operations. Suggested target for cryptanalysis: CubeHash2/1. Suggested target for practical attacks: CubeHash2/2. CubeHash32009.02.03: Brier, Khazaei, Peyrin, and Meier report a collision in CubeHash3/64.2009.08.10: Brier, Khazaei, Meier, and Peyrin estimate that second preimages in CubeHash3/4 can be found using 2^478 simple operations, and that collisions in CubeHash3/12 can be found using 2^153 simple operations. Suggested target for cryptanalysis: CubeHash3/11. Suggested target for practical attacks: CubeHash3/63. CubeHash42009.01.09: Brier and Peyrin estimate that collisions in CubeHash4/4 can be found in 2^189 simple operations, and that collisions in CubeHash4/3 can be found in 2^207 simple operations.2009.07.06: Brier, Khazaei, Peyrin, and Meier report a collision in CubeHash4/48. 2009.08.10: Brier, Khazaei, Meier, and Peyrin estimate that second preimages in CubeHash4/3 can be found using 2^195 simple operations, and that collisions in CubeHash4/3 can be found using 2^163 simple operations. Suggested target for cryptanalysis: CubeHash4/2. Suggested target for practical attacks: CubeHash4/47. CubeHash52009.08.10: Brier, Khazaei, Meier, and Peyrin estimate that second preimages in CubeHash5/64 can be found using 2^205 simple operations, and that collisions in CubeHash5/64 can be found using 2^71 simple operations.2009.11.25: Khazaei, Meier, and Stefan give an example of a collision in CubeHash5/96. Suggested target for cryptanalysis: CubeHash5/63. Suggested target for practical attacks: CubeHash5/64. CubeHash62009.08.10: Brier, Khazaei, Meier, and Peyrin estimate that second preimages in CubeHash6/4 can be found using 2^478 simple operations, and that collisions in CubeHash6/16 can be found using 2^222 simple operations.2010.05.06: Khazaei, Knellwolf, Meier, and Stefan estimate that collisions in CubeHash6/32 can be found using 2^180 simple operations, that collisions in CubeHash6/64 can be found using 2^132 simple operations, and that collisions in CubeHash6/96 can be found using 2^51 simple operations. Suggested target for cryptanalysis: CubeHash6/15. Suggested target for practical attacks: CubeHash6/64. CubeHash72009.08.10: Brier, Khazaei, Meier, and Peyrin estimate that second preimages in CubeHash7/64 can be found using 2^447 simple operations (slower than the standard generic preimage attack), and that collisions can be found in CubeHash7/64 using 2^203 simple operations.Suggested target for cryptanalysis: CubeHash7/63. Suggested target for practical attacks: CubeHash7/64. CubeHash82010.05.06: Khazaei, Knellwolf, Meier, and Stefan estimate that collisions in CubeHash8/96 can be found using 2^80 simple operations.Suggested target for cryptanalysis: CubeHash8/64. Suggested target for practical attacks: CubeHash8/64. CubeHashr for large rThe original CubeHash specification mentions a standard generic "narrow-pipe" attack that breaks CubeHashr/112 by trying about 2^64 input messages, that breaks CubeHashr/96 by trying about 2^128 input messages, and that breaks CubeHashr/64 by trying about 2^256 input messages.The attack is described in more detail in another part of the CubeHash submission, namely "CubeHash appendix: complexity of generic attacks." The analysis concludes that a fantasy-universe attacker capable of 2^511 bit operations would still have only a 2^(-8) chance of breaking CubeHash1/4 with this attack. For comparison, Grover's algorithm finds preimages in only about 2^256 quantum operations. 2008.11.18: Nikolic, Khovratovich, and Weinmann say "we have found preimage attacks on CubeHash512-r/4 and CubeHash512-r/8." Their paper, "Preimage attacks on CubeHash512-r/4 and CubeHash512-r/8," states (without credit) exactly the same generic narrow-pipe attack that was already stated in the CubeHash submission. The paper does make a new claim, namely 2^496 "computations" to break CubeHash512-r/4; but the discrepancy between the paper's 2^496 and the original more-than-2^511 comes entirely from the paper's vague notion of "computations." 2008.11.18: Aumasson, Meier, Naya-Plasencia, and Peyrin ("Inside the hypercube," Section 2) suggest an "improved" version of the attack, invoking the round function somewhat fewer times (about 2^(513-4b) times instead of (512/b-4)2^(512-4b) times) but using extremely expensive high-memory table-based collision search instead of low-memory parallel collision search. Perhaps the communication costs can be reduced; in any event, this attack isn't useful against CubeHashr/b unless b is large. Aumasson, Meier, Naya-Plasencia, and Peyrin ("Inside the hypercube," Section 4) outline another improvement, searching for symmetric states. The resulting attack complexity is on the scale of 2^256 for b between 33 and 64, 2^384 for b between 17 and 32, 2^448 for b between 9 and 16, and 2^480 for b between 5 and 8. Aumasson, Meier, Naya-Plasencia, and Peyrin ("Inside the hypercube," Section 3) also discuss a way to extend internal collisions to internal multicollisions. Of course, CubeHash is designed to make internal collisions hard to find; the attacks don't find internal collisions in the first place, let alone multicollisions, unless b is large. 2010.05.10: Ferguson, Lucks, and McKay ("Symmetric states and their structure: improved analysis of CubeHash") work out details of the improvements outlined by Aumasson, Meier, Naya-Plasencia, and Peyrin. Ideas2008.11.18: Aumasson, Meier, Naya-Plasencia, and Peyrin ("Inside the hypercube," Section 5) show that a particular 864-bit input difference to the CubeHash round function, with 96 bits fixed and 32 bits varying, produces 5 detectably biased bits in the 1024-bit state after 8 rounds.VersionThis is version 2010.05.11 of the security.html web page. |