FYI -------- Forwarded Message -------- Subject: RE: SHA1 collision found Date: Thu, 23 Feb 2017 15:00:05 -0500 From: Robert J. Hansen <rjh@sixdemonbag.org> To: gnupg-users@gnupg.org (I originally sent this off-list by mistake. Peter was kind enough to respond off-list and to suggest we take it back on-list. This email is a distillation of three different emails: my original, Peter's response, and a response to Peter.) =====
I already answered that here[1]. The use of SHA-1 in fingerprints is not susceptible to a collision attack, so it's still safe. SHA-1 in fingerprints is only susceptible to a second-preimage attack which is much harder than a collision attack and unheard of for SHA-1.
To which I said, "Create two keys with the same fingerprint. Sign a contract with one, then renege on the deal. When you get called into court, say "I never signed that, Your Honor!" and present the second key. This collision pretty much shatters the nonrepudiability of SHA-1 signatures." To which Peter quite reasonably answered that the other person has a copy of the public key which was used to sign the document originally. Why should the fraudster's denial be believed? The answer is that to enforce a contract (at least here in the United States) you must be able to prove, based on a preponderance of the evidence, that the other person entered into a contract with you. So imagine this conversation: PLAINTIFF: "Your Honor, the defendant reneged on a $10,000 contract. Make him pay up." DEFENDANT: "I never signed anything, Your Honor." PLAINTIFF: "I have his key, it's right here." DEFENDANT: "That's not my key. This is my key." PLAINTIFF: "Of course that's what he claims! They have the same SHA-1 fingerprint! He did that in order to deny his signature!" JUDGE: "So these keys are uniquely identified by the fingerprint?" (both parties agree) JUDGE: "And you have two keys that are identified by the same fingerprint?" (both parties agree) JUDGE: "And there's no way to tell which key is real?" (both parties agree) JUDGE: "Then we're stuck. There's no reason to prefer one key over another. Plaintiff, you have failed your burden of proof in establishing the defendant signed the contract." Now, you could establish proof some other way: let's say you made a videotape of the defendant signing the document. If you could introduce other supporting evidence (which might include other signatures on keys) you might be able to convince the judge the signature is enforceable. But there's nothing intrinsic to the signature itself which could convince the judge. So Peter is completely right to say "but there's no reason to believe one person over the other." Completely, absolutely right. But the person asking the court to enforce a contract must present a reason to believe them over the defendant. I hope this clarifies my answer! (Peter also rightly remarked that he thought nonrepudiability in OpenPGP was kind of iffy anyway. He and I are in complete agreement on this. OpenPGP has always had very iffy nonrepudiability. With this SHA-1 attack, I feel the threshold has been crossed and we need to consider it repudiable.) _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
On 02/23/2017 04:09 PM, Mirimir wrote:
FYI
-------- Forwarded Message -------- Subject: RE: SHA1 collision found Date: Thu, 23 Feb 2017 15:00:05 -0500 From: Robert J. Hansen <rjh@sixdemonbag.org> To: gnupg-users@gnupg.org
(I originally sent this off-list by mistake. Peter was kind enough to respond off-list and to suggest we take it back on-list. This email is a distillation of three different emails: my original, Peter's response, and a response to Peter.)
=====
I already answered that here[1]. The use of SHA-1 in fingerprints is not susceptible to a collision attack, so it's still safe. SHA-1 in fingerprints is only susceptible to a second-preimage attack which is much harder than a collision attack and unheard of for SHA-1.
To which I said, "Create two keys with the same fingerprint. Sign a contract with one, then renege on the deal. When you get called into court, say "I never signed that, Your Honor!" and present the second key. This collision pretty much shatters the nonrepudiability of SHA-1 signatures."
To which Peter quite reasonably answered that the other person has a copy of the public key which was used to sign the document originally. Why should the fraudster's denial be believed?
The answer is that to enforce a contract (at least here in the United States) you must be able to prove, based on a preponderance of the evidence, that the other person entered into a contract with you. So imagine this conversation:
PLAINTIFF: "Your Honor, the defendant reneged on a $10,000 contract. Make him pay up." DEFENDANT: "I never signed anything, Your Honor." PLAINTIFF: "I have his key, it's right here." DEFENDANT: "That's not my key. This is my key." PLAINTIFF: "Of course that's what he claims! They have the same SHA-1 fingerprint! He did that in order to deny his signature!" JUDGE: "So these keys are uniquely identified by the fingerprint?" (both parties agree) JUDGE: "And you have two keys that are identified by the same fingerprint?" (both parties agree) JUDGE: "And there's no way to tell which key is real?" (both parties agree) JUDGE: "Then we're stuck. There's no reason to prefer one key over another. Plaintiff, you have failed your burden of proof in establishing the defendant signed the contract."
Now, you could establish proof some other way: let's say you made a videotape of the defendant signing the document. If you could introduce other supporting evidence (which might include other signatures on keys) you might be able to convince the judge the signature is enforceable. But there's nothing intrinsic to the signature itself which could convince the judge.
So Peter is completely right to say "but there's no reason to believe one person over the other." Completely, absolutely right. But the person asking the court to enforce a contract must present a reason to believe them over the defendant.
I hope this clarifies my answer!
(Peter also rightly remarked that he thought nonrepudiability in OpenPGP was kind of iffy anyway. He and I are in complete agreement on this. OpenPGP has always had very iffy nonrepudiability. With this SHA-1 attack, I feel the threshold has been crossed and we need to consider it repudiable.)
What does it take to create 2 keys with the same SHA-1 sum ? My limited imagination thinks it would take a long time or a huge amount of processing power. --- Marina
_______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
On Feb 23, 2017, at 10:18 PM, Marina Brown <catskillmarina@gmail.com> wrote:
What does it take to create 2 keys with the same SHA-1 sum ? My limited imagination thinks it would take a long time or a huge amount of processing power.
— Marina
"Who is capable of mounting this attack? This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.” via https://shattered.io/
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 02/25/2017 04:29 PM, bbrewer wrote:
On Feb 23, 2017, at 10:18 PM, Marina Brown <catskillmarina@gmail.com> wrote:
What does it take to create 2 keys with the same SHA-1 sum ? My limited imagination thinks it would take a long time or a huge amount of processing power.
— Marina
"Who is capable of mounting this attack? This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.”
Or in other words, just 110 GPUs can find the same collision in a year; 40,000 can do it in a day. When one's threat model includes State and Corporate actors, that's not so good. In the context of security as a spending contest, weighing the cost of defending an asset vs. the cost of compromising the asset, SHA1 is not broken except in a few cases involving very value assets and very motivated attackers. But the security of SHA1 will continue to decline over time as number crunching gets cheaper, and a tipping point is coming. I figure bits are cheap and so is the "authorized users" end of crypto maths; bigger hashes (and keys) are harmless at worst and /may/ defeat attacks one does not suspect an adversary has. So rolling in SHA-2 could be a "now" thing. Figuring out when to deprecate then EOL SHA-1 is the remaining open question. :o) -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (GNU/Linux) iQEcBAEBAgAGBQJYsf/wAAoJEECU6c5XzmuqmsEH/30NhOD76o48atYKy+d6c7so z10oTDkJGZNzQvXdNiK2NMixFzJLkv1f/e/2Xr8aa+ml+jIQ+V6P+Ct7m+3FLrN9 XG8jlOPTsjdfgAZF97d6tti7qCVJWF5eBO/8zKdIT29BX4THE4zd7btUxiJmgFUi tIwYHqewKA5aZbKcGrPskcF2RkvY8O2M7T8oRaRSLW/H8xlkT0TR7s3cjh9sSeTq AzD+NHnfjrMiEEoV8+r4IxCxUeyeDTSASiKME6iYcU/JLj0vfG3dECmPcXofaKh9 I5sEFaYq93dz6J/huf5aph86TaPxMYJjDHJhmJeMtKBSFb6rt/sOZwoqaQIRPmU= =rcPW -----END PGP SIGNATURE-----
On Sat, Feb 25, 2017 at 05:06:40PM -0500, Steve Kinney wrote:
Or in other words, just 110 GPUs can find the same collision in a year; 40,000 can do it in a day. When one's threat model includes State and Corporate actors, that's not so good.
Are you sure about this claim? The wording on shattered.io doesn't suggest so and the google blog writes "the second phase took 110 GPU years". As I read it, this is the second phase and the first phase is necessary too. Probably the Bitcoin network will break it very efficiently if it were general purpose computing. In 2013 Bitcoin scored 10^18 ~ 2^60 FLOPS and IIRC todays figures are significantly higher. The SHA1 attack did 2^63 SHA1 sums according to the announcements.
participants (6)
-
Aivon Gnaiden -
bbrewer -
Georgi Guninski -
Marina Brown -
Mirimir -
Steve Kinney