ietf-openpgp
[Top] [All Lists]

Re: [openpgp] Deprecating SHA1

2020-10-24 20:01:27
I'm reading this with a good deal of exasperation. I apologize in advance for 
my tone, and I am not at all sorry about the content.

In 2004, the mathematician Wang Xiaoyun published a thing that possibly doesn't 
need mentioning. She broke, where "broke" means found collisions, in a mess of 
hash functions including MD5, SHA0, and a lot more. Her original publication is 
one of the most badass things I've ever seen in cryptography: she just 
published the collisions. H(X) == H(Y) for the suitable X and Y in enough 
number to show it's not a fluke (two is a good number for this) and across 
appropriate hash functions. This sent everyone into a tizzy. Did she know some 
underlying mathematical secret that we didn't?

Weeks and weeks went by, on to CRYPTO in Santa Barbara, and there was a lot of 
stress, speculating, and hand-wringing going on. At CRYPTO, Wang gave a talk on 
the work[1], and the rest of us found out that she didn't have any new 
mathematical insight, she was merely the best cryptanalyst on the planet, 
someone who had seen order trails of flipping bit that no one else on the 
planet had seen. At dinner that evening, I was talking to Ron Rivest and he 
said, "I used to think that hash functions were the cryptographic primitive 
that we understand best, now I know that they're the primitive we understand 
least."

Between those times, coming out of a session where we all got to talk to Wang 
in person, I walked out into the UCSB quad, got out my phone and called my 
friend and colleague, Will Price, who was VPE at PGP; I was CTO. We talked as I 
explained what had gone on in the session. I remember hearing the clack of Will 
typing as we talked. Twenty minutes later, he had a download link for me of a 
version of PGP that didn't use MD5 at all, used SHA256 by default (much of our 
conversation was whether it should be that or SHA512) and didn't outright 
prevent using SHA1 (which wasn't broken yet, but the betting on when was pretty 
furious), but it was pretty much stuck in the "advanced" preference UI in a 
disused lavatory with a sign on the door reading "beware of the leopard." That 
software went through our normal release QA, and shipped right after that, 
total time less than a week.

I know that hindsight is 2020, but why is this being discussed?

I'm sure that some readers of that paragraph saw through the little magic trick 
I did. I implied it took twenty minutes to make changes. Those same readers 
will realize that in fact we'd been discussing what to do and had a number of 
contingency plans based on what we found out about what Wang had discovered. 
That phone call was us deciding what to write in icing on the cake that had 
been baked weeks before. We're not geniuses, we just thought ahead and made 
some bold contingency plans. You can think ahead. You can be bold. Come on, get 
yourself an outfit and be a cowboy, too[2].

I get the impression that most people here think that the map is the territory. 
That RFC4880 and anything else is the definition of what one does. Here are a 
number of options possible.

* You could stop creating signatures that use SHA1. Just stop. Ditto for any 
other compromised aspect of SHA1.

* You could resolve a signature with SHA-1 in a creative way. For example, 
signatures have a number of states. There's the obvious case of a signature not 
computing correctly, say if the message has been damaged. That one's easy. 
There's the case of a correct signature from a trusted key. That's also easy. 
There are other cases that you have to take care of that are in the middle. You 
have to deal with a correct signature from an untrusted key. You have to deal 
with a signature made by a key that you don't have and so you can tell if it's 
correct or not. There are other edge cases, too.

Thus, you could consider a SHA1 signature to be incorrect and let the user 
know. You could consider it to be like a signature for a key you don't have. 
You could let the user know that it's mathematically correct but untrusted. (We 
did things like this in PGP; yes, this can be complex.)

You could consider a self-signature done with SHA1 to be non-existent, and 
handle it appropriately. You could even take special knowledge you have and do 
some reasonable thing. For example, let's suppose you know that this 
self-signature was created before the Shatter attack, and so you'll let is 
slide by. 

* You could also do helpful things for the user -- for example, when you have 
the key unlocked (by which I mean that you have the user's passphrase and thus 
the private key in your hot little RAM), you could go rewrite their 
self-signature with some other hash function and give them a new one just like 
the old one. (We did that in PGP, too.)

* You can do other helpful things for users like writing preferences in their 
self-signature that you, as implementor, think are helpful. You could do 
something like change key expiry automatically, as well. Just as text editors 
help users with things like autocorrect, you can help users in proper crypto 
management.

* You could compute primitives in any way that a naïve partner will handle 
correctly, as well. All the way back to when PGP started doing DSA (because in 
those days, there were patent issues with RSA), we were concerned with the 
issue with DSA that losing a single random number exposes the key. So when we 
computed the DSA random value, we took the raw nonce and then ran it through a 
keyed hash with the DSA private key. If you use N' = H(K+N) in DSA, you protect 
the nonce; learning the nonce requires either breaking the hash function or 
knowing the private key. (These days, you'd likely HMAC the nonce with the 
private key as that's today's idiom. In those days, there was no HMAC.) It's 
been that way for like ever, and no one ever noticed. We even discussed 
deterministic constructions using the private key with NIST and they said, no, 
we couldn't get that approved, but they liked the keyed hash.

* You can do plenty of other things. The standard is not a straightjacket. 
Implementers do not have to be fundamentalists nor textualists about it, either.

Particularly in the case where the OpenPGP support is built into some context, 
like an email client, there's nothing wrong with building something that only 
does a few things.

I'm flabbergasted because it seems to me that people are waiting for the 
working group to give permission to use (or not use) features of the OpenPGP 
standard. On the other hand, it seems that there's this expectation that if the 
standard says (e.g.) "MUST NOT use SHA1" that that will somehow magically make 
all the software get updated. 

Yeah, sure, there's nothing wrong with the standard noting that SHA1 is broken 
for collisions, act accordingly. That's neither necessary nor sufficient. 
Implementors can all decide that they're not going to use SHA1, and that makes 
it *really* happen. I'm grouchy about guidance in standards because 
implementation guidance for cryptography changes over time and often has a lot 
of nuance in it. There's guidance in 4880 that is just flat wrong. It's there 
despite being wrong because it was the consensus of the working group and the 
area directors that these wrong things are there. The one I'm thinking of is 
also not bad advice, but it's still wrong. Sorry for getting carried away 
there. My point is that the standard is not gospel and neither is it a 
bottleneck. It is a description of how the bits are laid out for the purpose of 
interoperability. 

Summing up, yes, stop using SHA1! How many bits must a cryptography write down 
before this is an issue. PGP, a reference implementation for OpenPGP stopped in 
2004. NIST said to stop using it by the end of 2010. Highlight is 2020. Putting 
some appropriate text in OpenPGP about it is a fine thing. You don't have to 
wait for that. Be bold! 

Thanks for reading.

        Jon


[1]: The Wikipedia article on Wang is dreadful. In it, it says, "At the rump 
session of CRYPTO 2004, she and co-authors demonstrated..." This statement is 
100% true and yet paints a picture that is totally false. It implies that the 
penny was dropped in the rump session when that was the closest thing to an 
official coming-out. It had been discussed in mailing lists, chat rooms, and 
the like before.

[2]: https://www.youtube.com/watch?v=dCeelWFO56Y

_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp

<Prev in Thread] Current Thread [Next in Thread>