Shuang Wu, NIST mailing list 2009-07-08 ---------------------------------------------------- We have found semi-free start collision pairs for 12-round Cheetah-256. This is an improved rebound attack when degrees of freedom can be used to implement algebraic message modifications. The complexity of original rebound path is about 2^128, which can be reduced to about 2^24 by message modifications. Collision pairs can be found in a few minutes. Here are two collision pairs: Collision 1: Initial Value= 9F 7A 79 DD BF 76 65 7B 5F CD 0F 5E BA 58 34 61 39 C1 78 BE 9F 42 E4 59 CA 74 FD 4E E9 0F 85 45 message 1= 7E 29 11 1A 6B 42 52 78 FB 15 14 15 9B 9C CF 0C CA 6D 0D 7B F2 01 4B D3 83 07 4B DB 02 F5 83 20 51 AE 1A 1F 84 24 B5 CE C9 E0 03 E3 10 A8 0E A2 80 B2 22 AC E2 BF 0C 72 7B 8A 25 45 8D 52 11 28 E9 1E 01 BA 60 97 18 F1 EF 3E 8A 55 A1 51 60 CB E4 7A 49 E5 52 5D E4 A6 1F 93 D5 0C C7 F3 9D 19 EB 61 C1 72 9E 22 5C 7B 74 A9 3C D9 97 8F BC 13 31 7A 32 03 01 1A 09 8E 13 91 0D 26 8E 52 D3 49 message 2= 7E 29 11 1A 6B 42 52 78 0E 15 14 15 9B 9C CF 0C CA 6D 0D 7B F2 01 4B D3 83 7A 4B DB 02 F5 83 20 51 AE 1A 1F 84 24 B5 CE C9 E0 7B E3 10 A8 0E A2 80 B2 22 AC E2 BF 0C 72 7B 8A 25 36 8D 52 11 28 E9 1E 01 BA 60 97 18 F1 EF 3E 8A 55 A1 5F 60 CB E4 7A 49 E5 52 5D E4 A6 1F 93 D5 0C C7 F3 69 19 EB 61 C1 72 9E 22 5C 7B 74 A9 3C D9 97 8F BC 78 0D 7A 32 03 01 1A 09 8E 13 91 0D 26 8E 52 D3 49 message difference= 00 00 00 00 00 00 00 00 F5 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 7D 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 78 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 73 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0E 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 F4 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 6B 3C 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 hash value= 9B 75 8C B2 B2 F4 D4 9A D4 0D D3 17 95 F3 01 3D BF DA D0 F8 F1 94 6D EF 49 8B 0E 0C 76 36 F9 8B Collision 2: Initial Value= DE A2 87 60 BE 2D 4E 1B B1 55 D4 20 B4 E1 B8 3D 44 0C 97 01 A2 A3 03 DF 8C 1E 49 D9 5C 45 D6 25 message 1= 07 80 F9 D2 4B C2 FB AF A0 F4 40 41 C7 D5 3D 6E 88 69 5B A1 75 4B A9 4B E7 32 48 08 41 A9 A9 65 3A 44 36 E1 F4 18 C1 16 31 DD 3D 8A 8D 4A DD A1 3F A7 EF 22 2D 73 69 07 8F E8 2C EB 06 5D 4B 12 BD DB CF 1A EA A4 AC 02 40 47 04 FE 35 8E E7 C2 CD 8B B9 6D B2 D8 39 6A 01 B8 38 49 B8 75 D4 42 57 E4 AD E3 1A 03 24 40 57 3C 38 70 71 5B 35 A1 47 C6 3E 76 08 09 08 B9 91 84 99 60 85 A4 FB EA message 2= 07 80 F9 D2 4B C2 FB AF 31 F4 40 41 C7 D5 3D 6E 88 69 5B A1 75 4B A9 4B E7 6C 48 08 41 A9 A9 65 3A 44 36 E1 F4 18 C1 16 31 DD 00 8A 8D 4A DD A1 3F A7 EF 22 2D 73 69 07 8F E8 2C 85 06 5D 4B 12 BD DB CF 1A EA A4 AC 02 40 47 04 FE 35 C0 E7 C2 CD 8B B9 6D B2 D8 39 6A 01 B8 38 49 B8 75 30 42 57 E4 AD E3 1A 03 24 40 57 3C 38 70 71 5B 35 0A FB C6 3E 76 08 09 08 B9 91 84 99 60 85 A4 FB EA message difference= 00 00 00 00 00 00 00 00 91 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 5E 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 3D 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 6E 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 4E 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 E4 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 AB BC 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 hash value= 88 92 7A C9 A6 28 A6 98 58 B4 FE B6 4D 14 C6 BD DE E3 C1 92 C4 C0 4B 0A 86 7B 7D 2E 30 DA 88 50 Shuang Wu wushuang@is.iscas.ac.cn State Key Laboratory of Information Security, Institue of Software Chinese Academy of Sciences.