11
$\begingroup$

When assuming a block cipher primitive is secure, or a number theoretic problem is hard, this assumption is usually based on how far we are from breaking the primitive or solving the problem using known techniques - using known algorithms and hardware.

But, from a meta-cryptographic point of view, how do we justify the assumption that there doesn't exist any significantly more efficient algorithms, or any significantly better hardware? I am not asking for opinions on the matter (or for arguments that fix the algorithms and prove that the necessary hardware would be physically impossible) but for justifications based on e.g. the sociology of cryptography or economics of cryptography, using scientific (justified and repeatable) methods and based on the premise that all research is done in the context of pre-existing research.

  • How likely is it that a single small team, basing their research solely on the state of the public research and their own results, would come up with results years or decades ahead of everyone else in the field?
  • Is it possible for large organizations to internally accumulate enough research, to give the researchers within that organization a significant head start over independent researchers in the field?
  • If "yes" on the previous question, are there ways to reliably tell if an organization has such significant amounts of secret accumulated knowledge? Is it possible to use the numbers of papers and patents the organization outputs, as a reliable indication that it doesn't have a strategy of accumulating knowledge only internally? What about flows of personnel between organizations, i.e. people changing jobs?
  • What is the likelihood that an organization exploiting weaknesses it has found in cryptographic primitives, would be caught in the act? If the organization is only using the weaknesses for intelligence gathering? Does it matter if the weaknesses require passive attacks or active attacks to be conducted?
$\endgroup$
  • $\begingroup$ Nice questions – which won't get perfect answers because they'll include opinions/guesses. (1) We can only guess, but it is likely to be possible as it happened before, (2) yes, practically seen it happen, (3) depends on the organization; but generally there is no reliable way to tell because you can't look deep enough into some governmental institutions and their blacksites, (4) That's the Snowden question rebooted. You're safe until someone notices… the more resources you have to counteract intelligence gathering, the less likely someone will be able to point the finger without losing it. $\endgroup$ – e-sushi Feb 20 '14 at 15:44
  • 1
    $\begingroup$ These kinds of things are very similar to what is studied in social sciences and economics. In principle, we don't have to guess. However, if no such research has been done, either due to lack of interest or lack of opportunity to collect the necessary data, that would also be an interesting answer. $\endgroup$ – Henrick Hellström Feb 20 '14 at 15:48
  • 1
    $\begingroup$ Also, it would be possible to formulate a valid hypothesis based on anecdotal experience, either if it demonstrates that no such study could ever eliminate a significant amount of inherently unknown hidden statistics, or, conversely, if it indicates exactly what kind of evidence should be collected to reach a reliable answer. $\endgroup$ – Henrick Hellström Feb 20 '14 at 15:53
  • 1
    $\begingroup$ I agree, and I'm already looking forward to the answers this gets. Scientific papers handling the points you mentioned are rare and not always easy to find. Especially in relation to cryptography, I'm personally not aware of any scientific paper that really answers all your questions. Yet, I may well be corrected in one of the answers. Alike papers are surely nice to have – not only for reference purposes. (To be honest: first thing that popped up in my mind when I saw your question, was the hope that you may be asking because you're thinking about starting a related research paper yourself… ) $\endgroup$ – e-sushi Feb 20 '14 at 16:19
5
+100
$\begingroup$

But, from a meta-cryptographic point of view, how do we justify the assumption that there doesn't exist any significantly more efficient algorithms, or any significantly better hardware?

From a cryptographic point of view, the best answer is usually modularity: we want to design schemes which can be based on "instantiation-oblivious" hypothesis (i.e., hypothesis that we can instantiate over a large variety of objects sharing some mathematical structure). For instance, we know that the discrete logarithm problem is hard in a generic group (a group with no additional structure). Therefore, if a scheme based on the discrete log is broken on a given structure, it will likely remain secure if it is instantiated on another group, with less additional structure (notwithstanding the advent of quantum computers, ofc).

From a meta-cryptographic point of view, once a specific system is deployed, our confidence comes essentially from two considerations:

  • How long has the underlying problem been studied
  • How many people are actively doing research in cryptography (both in academia and companies)

For example, the factorization problem already has a very long history, hence it seems more likely that our understanding of it is more advanced - put otherwise, there is less chance that we missed a simple approach that would allow for fast factoring. However, the second consideration remains probably the most important one. In the 90's, it was plausible for a powerful intelligence agency (such as the NSA) to hire enough mathematicians, and to give them access to a huge computing power, so as to be competitive with what the rest of the world could do. With the evolution of cryptography in the past decades, that does not seem plausible anymore. Thousands of researchers are actively working on cryptography, hence an agency could, at best, hire a very small fraction of these researchers. I see no strong reason to believe that all the best researchers could end up working for the same agency (especially since cryptographic research is spread worldwide). Assuming that the researchers an agency can hire are sufficiently representative samples among good researchers, this implies that the probability that a cryptographic breakthrough comes from a given agency is reasonably small. The same observation holds with respect to computational power: nowadays, even an agency as powerful as the NSA cannot mount cryptographic attacks that would require way more computational power than what, e.g., Google, Apple, or Microsoft have access to.

How likely is it that a single small team, basing their research solely on the state of the public research and their own results, would come up with results years or decades ahead of everyone else in the field?

It is not impossible. It appeared in the past: Clifford Cock had essentially discovered RSA five years before its introduction by Rivest, Adleman, and Shamir, while working for the GCHQ. In the 70's, the NSA had apparently already discovered differential cryptanalysis (see this post by Bruce Schneier), which could break many seemingly secure schemes, and was only 'publicly' discovered in the 90's. However, at the time, the amount of people working in this field was considerably smaller than today. Nowadays, the probability of such an event happening should probably be close to (number of people working for the agency)/(number of researchers working on area related to what the agency works on). Hard to precisely estimate, but likely small.

Is it possible for large organizations to internally accumulate enough research, to give the researchers within that organization a significant head start over independent researchers in the field?

Again, it is not impossible, but it requires luck more than anything else. But that was assuming the question was about finding breakthrough results on cryptanalysis of deployed schemes. In fact, other types of attacks can be found, and they seem way more likely.

  • the agency can find an attack, not on a primitive, but on a protocol. Due to their highly complex structures, the landscape of possible attacks in considerably increased. Unlike cryptanalysis of primitives, breaking a protocol is not about finding advanced mathematical methods, it's only about thinking about something that people did not consider before. A good example of it is the recent logjam attack, or 3SHAKE. It is not completely unlikely that some agencies are already aware of attacks of this type that have not yet been publicly revealed.
  • Even more likely, the agency can directly find flaws in a specific implementation (either of a cryptographic primitive/protocol, or at a higher level). Those flaws are usually devastating, conceptually very simple, and seem considerably more easy to identify than, say, a new factoring algorithm (such flaws are discovered routinely). One can think for example about the recent heartbleed. Here again, it seems quite likely that some agencies are already aware of security issues that have not been yet publicly revealed.

If "yes" on the previous question, are there ways to reliably tell if an organization has such significant amounts of secret accumulated knowledge? Is it possible to use the numbers of papers and patents the organization outputs, as a reliable indication that it doesn't have a strategy of accumulating knowledge only internally? What about flows of personnel between organizations, i.e. people changing jobs?

If the organization is small and keeps everything it does secret, there is no way to tell. Intelligence agencies will obviously not write patents or publish papers about their most critical discoveries. However, if the organization is small, it has also a very small probability of being the one from which a cryptographic breakthrough originates.

On the other hand, if an organization is large, then there is a standard way to know what it is working on: leakages. If the organization works with many people, on sensible subjects of crucial importance, something will end up leaking - human flaws are the only one that an agency cannot cope with. This happened with Snowden, and can happen again.

What is the likelihood that an organization exploiting weaknesses it has found in cryptographic primitives, would be caught in the act? If the organization is only using the weaknesses for intelligence gathering? Does it matter if the weaknesses require passive attacks or active attacks to be conducted?

That completely depends on the particular scenario: it could be that an active attack will remain undetected, or that it will be detected with noticeable probability. In the field of secure computation, which an important and active research area in cryptography, this fact has been acknowledged by considering three types of adversarial behaviors: passive, covert, and active. Passive and active attacks are the types you already know; a protocol secure against covert adversaries can be broken by an active attack, but it is not possible to break its security without being caught (with good probability). The rationale behind this was that in practice, an important company/agency would likely want to attack cryptographic protocols, but cannot afford being caught when doing so.

If the weaknesses requires only passive attacks, and the agency is only gathering information, there is no way to tell (except internal leakages): a passive attack can be mounted offline, on the transcript of some interaction, hence there is no reason why anyone could discover about the outcome of the attack, unless that person is already part of the agency.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.