Shahram Khazaei, NIST mailing list 2009-02-24 ---------------------------------------------------- Hi all, We have found a collision for the MD6's main compression function f_Q reduced to r = 16 rounds. This function is parametrized by a 15-word constant Q and maps a one-word node ID U, a one-word control word V, an 8-word key K and a 64-word message block M into a 16-word compressed value. We consider the actual constant Q used in MD6 and for simplicity we set U = V = K = 0. The two colliding 64-word messages are then: M1 = {0x5361E9B8579F7CD1, 0x8B29C52CA2AB51E4, 0x0BCF2F1E1B116898, 0x022C254B88191A11, 0xF0F1CE9D9A7F63B8, 0x9FB5B2CE87B7D7F5, 0xE7C78F28EEB4F5C7, 0xC5E8C19CEFC07365, 0xF88B84529ED90209, 0x8FACF593AE7390CF, 0x03A93466247C6B54, 0xB12C70C10904143D, 0xD92EE67244C300D6, 0x35EEA586ECCC8A77, 0x9DCF031C64B528F8, 0xC84807607ADCD418, 0x367E95EE3CB0FC67, 0x578A2C716FCC5016, 0xB0C30EA5521F61EF, 0x7F665B24762D5894, 0x4196BAF0596A7784, 0xED5F9A8F183B4BCC, 0x6077463601FCFE46, 0x495366B1273E119B, 0x6E11A21AE5B3A48F, 0x38082264A0F68F93, 0x4ED510C2DFA9FF98, 0x35C5ACEC5E9A1756, 0x1F6731C861879ECD, 0x8CECD7B4F761CE82, 0x332A50854FDA8FE6, 0x588498B1021E9C23, 0xCB1FFA21CF89C7A5, 0x63A6871C77848410, 0x92A550CB4607F31C, 0x97024803F162E055, 0xE2D6EA5A57D2DBF3, 0xAEB418A0F1F01CC5, 0x090A9304040038C1, 0x5417960E3D9A06A5, 0x714215C196813F35, 0xBABAD7A4C154F2C3, 0x71AF3FD02B543940, 0xFA08624B825648DD, 0x730D61FF48759275, 0xCF85BA5A06D6AED4, 0x2E12B3150452C65A, 0x93C7A9FC314220B4, 0x81B128A4EF361456, 0xBFE652098170C212, 0x77540989DC246845, 0x796F353D07721071, 0xD82776A3CBFEC586, 0x1132E4391152F408, 0xCE936924CFFB22AA, 0xD338852F80450282, 0x4F41AB82E790EEF6, 0xF05378CB6BD36203, 0x5E506F47C6EC4617, 0xFE6FB5A03BDE8E1C, 0xAB33EA511EEBAEDC, 0x7D40F8D4F0C62BF4, 0x1174E2B748B9CC2E, 0x1EB743671A31547D} and M2 = M1 XOR D, where D = {0 0 0xF6D164597089C40E 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0x2000000000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0}; This provides a collision for r = 16 rounds, and near collisions for r = 17, 18 and 19 with 63, 144 and 270 bit differences respectively. Note the compressed output is 1024 bits long. The computational effort is about 2^30 with negligible memory. We would like to thank the MD6 design team for verifying a similar colliding message pair. Best regards Shahram and Willi