My responses below were made with the assumption that you were talking about integrity check (hashing), not keyed hash or message authentication code (must use a secret key).
From: <[email protected]<mailto:[email protected]>> Date: Mon, Jan 9, 2017 at 12:28 PM Subject: SHA-1 and Message Authentication Code To: Cryptographic competitions <[email protected]<mailto:[email protected]>> Message M: 1 |6C 69 63 65 6E 73 65 20 31 39 32 2E 31 36 38 2E 2 |32 33 39 2E 31 32 39 20 31 33 6A 61 6E 32 30 31 3 |37 20 63 70 73 6D 2D 63 2D 75 20 63 70 73 62 2D 4 |6E 70 6D 20 63 70 73 62 2D 65 70 6D 20 63 70 73 5 |62 2D 6C 6F 67 73 20 63 70 73 62 2D 6D 6E 74 72 6 |20 63 70 73 62 2D 70 72 76 73 20 63 70 73 62 2D 7 |75 64 69 72 20 63 70 73 62 2D 77 6B 66 6C 2D 31 8 |30 30 20 63 70 73 62 2D 77 73 20 63 70 73 62 2D 9 |6D 70 74 6C 20 63 70 76 70 2D 73 6E 78 2D 75 2D 10 |6E 67 78 20 63 70 73 62 2D 73 77 62 20 63 70 73 11 |62 2D 61 64 6E 63 2D 6D 20 63 70 73 62 2D 72 70 12 |72 74 2D 75 20 63 70 73 62 2D 65 76 63 72 2D 75 13 |20 63 70 73 62 2D 63 6F 6D 70 2D 75 20 63 70 73 14 |62 2D 73 73 6C 76 70 6E 2D 6D 6F 62 6D 61 69 6C 15 |2B 35 30 30 30 20 63 6B 2D 39 62 31 35 64 65 61 16 |39 30 39 32 64 0A Tag1 1 |07 31 5F CE F8 E6 92 03 Need to run SHA-1 hash of the message M above to see if Tag1 is a part of the hash value ( 160-bit output). Tag1 is 64 bits here. Tag2 1 |B5 03 6C A3 1E 03 C4 5F C3 CE E3 F5 3C AE 46 04 2 |EA FD 71 17 5D 69 31 AC D1 37 86 E3 D0 25 A0 1B 3 |EB 9E 1C ED 1B 99 16 0E D3 B3 DD 89 B1 93 3C 24 4 |51 79 FC 7B 41 E2 EC 7B 16 3A 8F 34 CB 95 90 80 5 |15 F6 01 67 85 72 40 2D EC 83 6E 95 6E 5C 37 BF 6 |03 44 15 7D 3D 21 F3 71 CF F6 19 23 2A 31 A3 D7 7 |64 86 13 E6 58 80 71 93 2E DD E5 30 3A 8F 04 99 8 |00 26 C7 E4 04 51 82 07 B0 B2 9B 1D 89 19 D4 9F 9 |00 Should call Tag2 as Message M’. When calling something a tag, a tag of what ? An unknown pre-image (message) or a known one. A tag is normally not longer than the output of the hash function. SHA-1(M||Tag2) 1 |07 31 5F CE F8 E6 92 03 9C 43 28 C6 F0 38 57 43 2 |D3 2C D9 34 Need to run SHA-1 (M || Tag2) to see if the result here is correct. Assuming the result here is correct and Tag1 is the leftmost 64 bits of the SHA-1(M) above, the chance for the leftmost 64 bits of SHA-1 ( M || Tag2) = Tag1 is 1/2^64 if SHA-1 is run only twice: one with M and the other with M || Tag2. Scenario: I have Message M (bytes) as above. In order to authenticate the message, I was provided Tag1 and Tag2. From the result of SHA-1(M||Tag2), we can see that the first 8 bytes is exact same as Tag1, that means the message M is authenticated. If Tag1 is a part of SHA-1 (M), then that is all we can say. It is easy to find 2 messages whose SHA-1 hash values have the same 64 bits including the case of the 64 leftmost bits of the 2 hash values being the same. The attacker needs to run SHA-1 over about 2^32 messages. Tag1 being the same with the 64 leftmost bits of SHA-1(M||Tag2) does not authenticate M as explained above. My questions: I don't know how tag1 and tag2 were generated but can ensure that they will be relevant to message M. If Tag1 is a part of SHA-1 (M), then we can say that Tag1 is a part of SHA-1 (M) and Tag1 can be also a part of hash values of other messages (64-bit collisions: the cost for finding 3 messages whose hash values have the same 64 bits is about 2^32 + 2^64 which is very doable today). Which possible algorithm / model they used to generate Tag1 and Tag2 that can make SHA-1 result as expected (matched Tag1) As explained above, an attacker can generate 2 messages M and M’ whose hash values have the same 64 bits. , as I know SHA-1 is one-way hashing that we can't predict the input that can genrate expected output. With a given 64-bit hash value, finding a (not the) pre-image is about 2^64 executions of SHA-1. With given fixed M and Tag1, the attacker keeps changing Tag2 and runs SHA-1 (M || Tag2) about 2^64 times until finds one output which has the 64 leftmost bits being the same with Tag1. Quynh. -- You received this message because you are subscribed to the Google Groups "Cryptographic competitions" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]<mailto:crypto-competitions%[email protected]>. To post to this group, send email to [email protected]<mailto:[email protected]>. Visit this group at https://groups.google.com/group/crypto-competitions. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Cryptographic competitions" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/crypto-competitions. For more options, visit https://groups.google.com/d/optout.
