If a cryptanalytic breakthrough is made, what process should be followed?

Question

If a researcher manages to make a cryptanalytic breakthrough on a cryptographic algorithm or protocol that is in use, what should they do?

Has this ever happened before? What are the implications for release and how do those relying on such systems ensure they are not caught in a situation where the crypto-system on which they depend is trivially broken?

Specifically:

• What details would you make available online?
• Who would you release full details to?
• How are affected parties notified?

Answer 1

Well, first off, the question doesn't arise that often in practice. People do find cryptographical weaknesses; however, generally they are purely of theoretical interest, or if they could be used in a real attack, it may take quite a while before someone figures out how to use it. As an example of the second case, Ms. Wang announced an efficient way to create MD5 collisions; this is a severe break of the MD5 security properties, but it took people quite a while to figure out how to translate that into being able to obtain a bogus certificate (by asking for an innocuous one from a CA).

On the other hand, it does happen on occasion; one example that springs to mind is WEP and the key recovery attack.

Now, in my opinion, the ethical thing to try to do is to get people to stop using the broken protocol, and switch to something which doesn't have known weaknesses. However, in practice, that appears to be difficult. Once they have a system in place, quite a lot of people are loathe to update it. In addition, when cryptographical hardware is involved, sometimes the fix involves hardware modification, and so updating things would involve real money (rather than just a software update). One example of someone ignoring an announced attack would be the TJX credit card breach; this attack was done using the WEP key recovery attack that was announced 5+ years earlier.

So, what should we do? Well, I don't see any good options. Not publishing the result doesn't appear to work (we leave the weaknesses in place for the blackhats to find and exploit). Publishing the result does mean that some will update, but others won't bother. Publishing the fact that we have a result will generally mean that you won't be taken seriously (unless you're already a cryptographical Big Name), and the blackhats will be alerted that there is a weakness.

My personal feeling is that publishing the result is the "least worse".

[Hmmmm, we're supposed to avoid statements based on opinions; for a question about ethics like this, I don't see how I can avoid it]

Answer 2

I landed on this question having been struggling with a narrower version, and associated conundrum: What should a number theorist do is she discovers a fast factorization algorithm? By "fast", I had been considering, the specific case of being able to factor $n = p \times q$ (where $p$ and $q$ are each 2048 bit primes) in about 1 week using a single Intel Core Ultra 9 285K.

It seems to me that the solutions offered by @JonRB (on a now-closed question at SE Security) are not ideal. Every significant nation state, and every significant criminal organization, will want access to the algorithm and will also want to keep the algorithm secret for as long as possible. The discoverer will potentially be in significant danger.

Note Method 1 (which was in my original unedited answer) is actually flawed, as pointed out by @poncho in the comment below. I have given a corrected method after this flawed one, but I think it is useful to leave the flaw ... because it shows how easy it is to slip up!

Method 1

Assuming that the discoverer's intent is one of altruism rather than self-interest I suggest the following approach:

• Use a service that incorporates Tor to announce the discovery without disclosing the method (e.g., one of the secure submission methods of some well-respected newspaper).
• Invite submissions, prior to some closing date, of 4096-bit products as challenges for factorizing.
• Factor the challenges and post the results.

At that point, the crypto community will take serious notice because you will have provided a zero knowledge proof of the existence of the algorithm. Advantageously, you will not have revealed your identity, or location, or the algorithm but you will have time to do all those things when it appears safe to do so.

Method 2

The critical difference between this, and my flawed method above, is that this is zero knowledge. I was too much focused in Method 1 on not revealing the factorization method, and forgot that my "proof of possession of a method" could be used as an oracle.

So ...

1. Use a service that incorporates Tor to announce the discovery without disclosing the method (e.g., one of the secure submission methods of some well-respected newspaper).
2. Offer to engage, with your readers, up to some stated closing date, in a statistical zero-knowledge protocol of the kind described in an open access conference paper by Poupard and Stern (2000).
3. Make public the details of the interactions at stage 2