All data below is presented in hexadecimal format. Data on the MD5-Colliding Certificates --------------------------------------- The MD5 output IV of the first 4 x 64 bytes of the "to be signed" part of the colliding certificates is IV = FE2BB52F 2807AC73 BE5191B5 97442F78 The MD5 collision on the basis of the above input IV is b1 = CAB9E742 C4B62687 1AB9A524 846B05C1 8895FB93 65E9A69F 480392FF 2C3B3F79\ 41AD3406 FFADB403 4BDF847A 4D37014F DB3283CB 19D46FA8 A765C6B3 F016BF30\ 6AFF7C2E 5773689B 3319B815 64ABE7F5 B9CF66C5 E4FE790C EE047D36 CC77B0AE\ 5D087F30 B560EB88 72B34D40 6778662D D8846467 7DBD9B80 989EF24F B82E0EA3 b2 = CAB9E742 C4B62687 1AB9A524 846B05C1 8895FB13 65E9A69F 480392FF 2C3B3F79\ 41AD3406 FFADB403 4BDF847A 4DB7014F DB3283CB 19D46FA8 A765C633 F016BF30\ 6AFF7C2E 5773689B 3319B815 64ABE7F5 B9CF6645 E4FE790C EE047D36 CC77B0AE\ 5D087F30 B560EB88 72B34D40 67F8652D D8846467 7DBD9B80 989EF2CF B82E0EA3 and their XOR-difference is b1 ^ b2 = 00000000 00000000 00000000 00000000 00000080 00000000 00000000 00000000\ 00000000 00000000 00000000 00800000 00000000 00000000 00000080 00000000\ 00000000 00000000 00000000 00000000 00000080 00000000 00000000 00000000\ 00000000 00000000 00000000 00800300 00000000 00000000 00000080 00000000 The MD5 output IV (on the basis of the above input IV) of these colliding messages is IV = 461A448D CF403F04 3DBADCD8 7214F197 (note that MD5-padding is ignored here). To obtain colliding RSA moduli we append the following bytestring to b1 and b2 b = 2B5864AF 33B8FE86 59B09446 4699F477 A6BFCA34 8C23CF68 1EC0A846 A8B27A29\ 071B563A 1316B05F 3827B82F B1F9DE1F 238F3D12 AD0DDAA9 7DDBCFCE EAD10939\ 5E46E018 AE237CE5 9355AC93 1872284C 3A293FE9 117941A1 AD528364 A0687AFF\ 6083B14B 009DD952 C866CA43 A0F41A7D CE5876C1 6CB346E9 A718091C EC3D57D9 The RSA moduli in the two certificates are n1 = b1 || b and n2 = b2 || b. These moduli have the factorization into primes n1 = p1 * q1 and n2 = p2 * q2, where p1 ( 512 bits) = D8B3DBAE AF3F9ED2 54747D41 97037924 C913CB4F 73AC4C11 F2AAD3A4 66883A21\ E319419A 79F868E1 11A4145F D79CFAC7 5D0F9227 5AA4C334 C488C1BD 751ABA6D q1 (1536 bits) = EF7D3591 84D80249 2794EF3A BA244A62 AB59F028 458994E6 E6A1D353 44684A90\ 3663AE4B 44A3F3EE 1970C468 1BB41961 C7A57D85 446EC541 194B6F00 35C22B9B\ 8045CB8B 872FD26B 793E5B00 9136D92E 57EDAD94 997909E9 1DF7F4CA D0A4D266\ D68F588D 5D091344 2E4B2242 A71C6DC2 4C8FB30B FBD6DA2A E90F86F6 FD56C0C3\ 52BDE399 5D57FF3D 600122F6 18416A4F C9722585 B196F02F 4233AD9C 90D3857A\ EF29ECE2 B47DFDB5 6E8F12C9 DF2CD8DD F34A795F 0C486813 F58EC09A F9BB2F9D p2 ( 512 bits) = E1CD8F82 F7A81818 69A7A134 5B7DAD43 9FC75462 B7C943FE 6397B6DA 66522B03\ C7F1C72D 6A8F4B81 9FCF03AF 76E2FCB0 88DBD7CD DA1BC9FE C6D5164C BAC28FF1 q2 (1536 bits) = E5D64D26 5750BA84 C10573A8 1D93E06D 3F2D276F 388AD26B C11E209C 2A512894\ 3A808EDF 20679DDD BF93196D 25A0DCDF CCBF72DD 27BFB4BF F5459EA5 61F29BEC\ D7D3D549 744F4796 ED138D8E BD47D03D 809BBDCB EE1E207C CE31B06E C28983A3\ 51331B50 6BED1B6D AEE2C429 FE2AFE16 8915D583 2B769EFF 9A998F41 E522CCC5\ 1D47A3C4 211F25FA 5E8FC18C B1592B24 9FFF00F4 CDA86B09 C0EA7B4D 3A2889C1\ 77D7FA64 AF98C949 3A7A926D 7D3C2E60 979072D8 AF24EEEB 650EB3B5 38C32E69 Both RSA key pairs have public exponent e = 010001 but their private exponents are of course different d1 = 1217BF5D 05236092 E43EB74F 68060930 79993127 B98BBDD4 2F602A49 5DD037DD\ 01908CB9 272E8087 5EC92710 A73D867F 7307B21D 7943AD67 76F12D67 B7C0BFF5\ 63E77F97 D5700B14 BD746F5C 9CA597D9 9D0BBCB7 5A98DB17 CDC6EF74 A01B07B9\ 1F27CC80 FDABCFC9 55B80B70 8A6A8D94 14D95FEF C6BF937D 7D469DCC 85CE4D27\ CD0BCEE1 112FF8E0 B931588D 3120143A 59AF84E0 7D8EE22B 708D78FF 4F8C0071\ E3554B21 93E9E920 95A3BB39 B9A383B8 B5737F05 13E1DDC8 6E4D411F 0C51C28F\ BB26AC54 1266E24F 6221CAD8 89AD819C 6198C0A0 FD8EE0B1 F86E1A16 C6AA9D3A\ B1896E63 22236529 0AA49924 E1F23DFA 6A5C3F83 B803334A 0C7CE48A 3ACAF551 d2 = 802F0232 6EAD7A39 0D45FB4C D6C9D10E E96D641F 84DE3374 1D95DCF9 AA1F2068\ 6C85B713 01D1F4B3 ECE2BD22 944735F6 27748E6E FABB1F8B 35A59DA8 B393BE79\ AEAA36C9 C944246D 9EDE7FD1 D5153596 2F6CAD6D 1207E281 A1215BC6 8EE6EC42\ 12398054 256D6995 98C3B0E1 50DE861A 4B48D12D 9667FFE3 28A65018 A103DFE9\ B76F6738 7FCAB958 3486297C 1DC12994 F70EEE25 AC5D8D97 CF0D475B 6575DB42\ FA9D87BA BBEF07F5 9DC552C2 D449E7D0 A8D4410E 3573C9CF 071A9A34 51363595\ 01C9282C 3153ED89 5DD39DFB C949003F F7CF59E0 83F939D2 08F72796 F9808049\ BAEDB6CD 64336CFC 422C8710 39523EBD AA4F5E27 F64F35C8 284005F2 E8F73681 Hash values of the moduli (MD5 compression function output IV's on the basis of the above input-IV, SHA-1 plain with standard IV and padding) MD5(n1) = 7AA79F34 FA7F29A2 158B25B5 B26F66CC MD5(n2) = 7AA79F34 FA7F29A2 158B25B5 B26F66CC SHA1(n1) = 5D4549A8 D9F1D4B8 F3EADDA5 92AB69ED 7C8FBF5E SHA1(n2) = 0B8D4DE6 15E543FC 6E1589E6 CC63F33A 9C468B26 Hash values of the "to be signed" parts of the colliding certificates (plain hashes with standard IV and padding) MD5(tbs1) = 5FA5531B 3FBA6973 FEF68BA5 2D32E617 MD5(tbs2) = 5FA5531B 3FBA6973 FEF68BA5 2D32E617 SHA1(tbs1) = 5544137C 47F9F20A B5FA2B4A D0556884 C4DC1F23 SHA1(tbs2) = 277C0F10 E8DB77B8 5F310985 04CB6845 7B0C93CE The input to raw RSA signing are PKCS#1-padded hashes PKCS#1-padded MD5(tbs1) = PKCS#1-padded MD5(tbs2) = 1FFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF\ FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF\ FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF\ FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF\ FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF\ FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF\ FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FF003020\ 300C0608 2A864886 F70D0205 05000410 5FA5531B 3FBA6973 FEF68BA5 2D32E617 The signature, computed using the CA private key on the PKCS#1-padded hash sig(tbs1) = sig(tbs2) = 1319E6FF 66EF8621 AEAE0CFB D2C067B9 9C3834C0 0BE88E0A 97E60205 BC5ECD85\ 646B6698 BD2E9132 4826C8B1 0E2167EF F264C5E4 5A234FDE 5723A751 EA2B7913\ 06221B54 B4C20E4C D16562D6 98ADE4D6 33F053D6 53F8BE9C 4D402EC9 F92D3630\ 98DD5605 96F7BF09 5AF3C9FE D7EE2B49 21801800 3F5C65F0 511D454E 6E522913\ 2D0494B7 B65EF958 5AA9D433 094FDB4F 9C994610 AFE0F23F B26E5D24 6539AEFF\ B6E0B0DF 35B4D9AE 3CF768C5 AABC9355 8DF87BF4 21288E79 E9ADCBB8 DA236452\ 8E74F813 48FFB9F5 FAC43E97 4F3D79CC A222FD67 5BFD3B80 8A3F6610 4232C806\ A25309A1 87D103D7 50893436 D4A32909 FE5C76B4 5495F52F 29CF66A9 E3DD473F Hash values of the entire certificates (plain hash values with standard IV and padding) MD5(cert1) = 130DF043 02123AD2 44B1AAA9 18AA9B42 MD5(cert2) = 71C7AAA1 C41E1506 77E0BDFF 40265418 SHA1(cert1) = 5A6869E9 6AF82E3F B9B9DF97 2946E0A8 218A125C SHA1(cert2) = E1BB6CCC 9F132A35 63C0F78F FBFF60BF 22CEEAC6 Note that the MD5 hashes of the entire certificates are different. This is due to the fact that the "to be signed" part of the certificate is preceded by a 4 byte ASN.1 header. The SHA1 hashes are shown by Microsoft's Certificate Viewer. The CA public key ----------------- n = CA70FAC4 4006FBB4 1A8EE419 5AA9771F 75917459 D268B930 46035BA1 DCB54A28\ 2A1E2848 B778BAE0 67700ACD 642CB08D 570DBB0F 8956DF23 A0A3C6E5 DFAEEF53\ D8BDC164 F4CBE52E 47AA586E FFF3B29F 0CBD4239 4C646377 EF3DE2F7 BE9B6299\ 37451268 B9516A32 F17BD4A4 EA3BA472 3D2FA1A0 F234420A F95040D3 CE0CED5F\ 60DB0A26 469F0717 9D2BC29F 623A6180 33969FF7 AC6B92A4 94C127A6 1379B317\ ABB72148 6437542D C6D05DA7 14B6D059 CE470CB3 90841349 37485995 A1E8F334\ 9DCFCA31 D618A4FC A487573C 9A426A50 836F9559 BA4DB76A 686095B9 B864DED6\ BDED5345 DBEC3840 DBAC4B0C BACCA014 C5753C28 0585F453 FD520F27 4043A051 e = 010001 The CA certificate is self-signed. ---------------- Arjen Lenstra Xiaoyun Wang Benne de Weger March 1, 2005