Introduction
We present a practical attack on the Panama hash function [1] that generates a collision in 26 evaluations of the state updating function. Our attack improves that of Rijmen and coworkers [2] that had a complexity 282, too high to produce a collision in practice. This improvement comes mainly from the use of techniques to transfer conditions on the state to message words instead of trying many message pairs and using the ones for which the conditions are satisfied. Our attack works for any arbitrary prefix message, followed by a pair of suffix messages with a given difference. We give an example of a collision and make the collision-generating program available. Our attack does not affect the Panama stream cipher, that is still unbroken to the best of our knowledge.
More information can be found in the files available on the right pane.
Bibliography
[1] J. Daemen and C.S.K. Clapp, Fast Hashing and Stream Encryption with PANAMA, Fast Software Encryption 1998, LNCS 1372, S. Vaudenay, Ed., Springer-Verlag, 1998, pp. 60–74 • See also the article in PDF and the reference code.
[2] V. Rijmen, B. Van Rompay, B. Preneel, J. Vandewalle, Producing Collisions for PANAMA, Fast Software Encryption 2001, LNCS 2355, M. Matsui, Ed., Springer-Verlag, 2002, pp. 37–51 • See also here.
Example of collision
The table below shows an example of pair of messages that produce a collision. Each line represents a message block; for each block, the words in hexadecimal must be read from left to right. The first message is given by the hexadecimal digits as in the table, while the second message is obtained by xoring with ffffffff all the underlined words. Both messages hash to 45d935220168bdcde830f65a6e46f3e91bb0bbd63d37a576718f40320c65079f.
| p(0) | 002911b8 f4046c0d 18be4673 67847de2 4ae13b51 3d6c1b7e 2cd6267d 72ae641d |
| p(1) | 69522bd8 5f903d84 25558553 c194e805 1f7427d8 37edf3e4 bc922535 01eb3a6b |
| p(2) | 0e8257d3 2ea67fd6 0682df75 c21387fe caa1b829 ccc994ba 9d03bd1c 00992518 |
| p(3) | 01244898 305e252b 440d462c 491c5b2e 4d061f8b 4db745f9 15473f0e 54de79dc |
| p(4) | 39b355bc 2d1261f0 074d4fca 4dc8390e 6443663d 66bb5f6d 428b7e94 26a61a31 |
| p(5) | 701f5092 5d037474 7a5a4baf 767d758d 450940b5 12383ea4 3b253990 1e1f71d5 |
| p(6) | 6e5d785e 1ad4176a 63cb2040 6bfc19fc 7f965d80 7ff57876 4e455002 323b054b |
| p(7) | 24168c78 d6646fb1 9a2ac8f2 030a45b1 301c3921 e58d996a 56ae7f7d 0732105a |
| p(8) | 69bd59fc 6e3b4bdf 1adc0aac 22ee5482 4062e4cf 85f91c0a 45b21fe0 f25f2094 |
| p(9) | d7992b2c 1a491c5e 8dc2afaf 3bf6154e a8ab7031 797d40fa 475d1ef4 e842e121 |
| p(10) | 4cad0094 314f2b74 5e14301d 4df21075 494469e5 2e405ddc 13667210 1cd05258 |
| p(11) | 366b5346 66c441da 42305df2 7eb75e5b 60327a81 2c3b3ba0 15a12e7f 54220e5c |
| p(12) | 3ef673cb 0822691d 59913a36 409d0de9 12e16f49 798b6174 121f0502 73da3555 |
| p(13) | 58b077d2 26ca08ac 3699151a 09021b0b 7bb90ef7 57724ba9 139d0f26 70494f23 |
| p(14) | 692c4a40 4a80585b 187e5da3 16c57533 689955b9 3cd52635 13e96788 40803068 |
| p(15) | 5db27fad 33ea62e1 23c91a2a 48cc15d5 575331b2 60bf1732 5c674a5d 3cd6190a |
| p(16) | 0fbf7ae5 2f14185a 6ad630dc 047e26e9 422d0f77 54dc195d 368e05eb 0d6662b5 |
| p(17) | 79836169 75ef70c5 2cae43f4 2c49396c 3c613693 e13226d5 5bc5e69d 288f3f57 |
| p(18) | 3a615feb 58d1d14c 00795183 c49baa76 5e9d7604 79f7f59b 19166db2 617207a2 |
| p(19) | 6b723ed5 f5fe7f4e 401d5fa4 9acbcbfe 038420bc e3aac878 202e7da1 5b28d301 |
| p(20) | 440246c3 18d7068f 6be842d6 5039652a 542c5a21 19530314 6bcb5da9 0fc946d4 |
| p(21) | 0e127504 5f1e7011 28336601 78742718 249e328d 2b0c3dae 11f406bb 5dd55373 |
| p(22) | 6ad4001c 5a9f6260 4cd460ca 5fa41c20 205913cf 127e075d 003555d6 07cf042f |
| p(23) | 67322c45 6d225953 1af46629 0ecc37d7 46cf7da8 01d35159 b428c608 3a2d3d0d |
| p(24) | 4fe67839 304d058a 9ffce0a5 09751255 37e6124e 24851e01 591d2784 252a2fd9 |
| p(25) | 23c3189f 3362c465 d6437d3f d4bccbbe 507872ed f78a65dd aaa618d1 556224c8 |
| p(26) | 581ecd2f 305c16ce 83fde1d9 6b9f1da2 7a1f06d4 efbfe9b6 5fdcde8c 018136fc |
| p(27) | 0c7b1785 50052d8e 0c153981 380717b0 773b727d 06334fbf 728245ee 251f74b1 |
| p(28) | 1d1842e4 62705d85 34927fe9 19da7c12 50646f07 4d546b8b 39ce12c6 3bb12fec |
| p(29) | 4c852466 513e15e2 6d697ca3 6a155ef3 4ff85bb9 5c4603f4 486a5290 30046806 |
| p(30) | 17965e32 5e7368b9 470e0ff4 73d95c04 1f163002 182f532d 4d67752c 596871e0 |
| p(31) | 4ad4041e 2cf76301 3f4a3974 0a4a00f8 5ed01d43 4e573590 4f68140b 587675a2 |
| p(32) | 66fa4037 aa864c4d 49bb6092 6f117408 74ad1b53 4eae041c 5d2462b5 05881d37 |
| p(33) | 5579473e 7cfe6737 ebed6b2a 912f3f6a dd8bfb4b 329eae68 96076905 6f3c52cc |
| p(34) | 06e8849c 5f456809 102bfd9d 527ab906 a1d33100 72aa5ea1 8ab21c2b 68f50f55 |
| p(35) | 45c52997 39607312 345919ca 263d7857 3b971002 40276cb6 138a726c 29593908 |