A friend shared with me the following link: Encryption is less secure than we thought

I'm not a security expert and could understand great part the article, except the section about noise, but what I haven't figured out is the impact of that research in real life.

What does it mean for mortals, in practice?


migrated from security.stackexchange.com Aug 15 '13 at 20:44

This question came from our site for information security professionals.

  • $\begingroup$ In practice it will mean nothing for any of us here except Ursas Major and Minor. The amount of effort slightly changes, but our tools remain the same, with replacement algorithms developed as needed. $\endgroup$ – Rory Alsop Aug 15 '13 at 20:44
  • 4
    $\begingroup$ As far as I can tell, the paper contains nothing that hasn't already been accounted for in modern cryptography, since, well, at least the 1970's. $\endgroup$ – Henrick Hellström Aug 16 '13 at 1:21

So the article is fluff, the details can be found in the linked paper. The just of it is a refutation of the following assertion: if you have a set of symbols chosen with identical independent distributions and subject to some kind of coding, the result can be approximated as a uniform distribution.

The paper asserts, with a few citations to some examples, that this is a common cryptographic assumption. It is, as far as I can tell from reading the literature and talking to other practitioners, not a common assumption at all. In fact, in standard encryption systems, we assume that the plaintext is chosen with a known distribution that can be arbitrary(indeed, attacker chosen), and keys are chosen randomly.

In practice, keys are not chosen randomly, they are chosen using cryptographically secure random number generators. Those can fail, but not in the way the paper is talking about.

Certain papers, such as maybe the cited ones about biometrics and passwords, might make this erroneous assumption, but it's not common and certainly doesn't relate to what most non-practitioners would consider "encryption."

Moreover, it appears that you still can't make guesses about messages in polynomial time with this technique, you can just make them in faster exponential time. It depends highly on how the assumption was used if this maters in practice. Not having read the papers which do make this assumption, I can't say for sure, but if doing this breaks those systems in a practical sense, the schemes likely had other issues.

A better title for the article is: a few cryptographers made some dumb mistakes. Mistakes neither pervasive or of massive consequence.

  • $\begingroup$ Out of ALL the answers, this is the only one that actually approaches the subject, and the only that successfully answers the question and successfully critique the original article. Thank you. $\endgroup$ – Adi Aug 16 '13 at 13:52
  • 1
    $\begingroup$ Great answer. Gets my upvote. Thanks for taking the time to dig in to the paper as well. $\endgroup$ – AJ Henderson Aug 16 '13 at 14:26

The crux of the article is that more thorough correlation of seemingly random data may be possible.

While interesting, it's not really directly applicable at the moment to existing cryptosystems, or indeed in the immediately foreseeable future. The argument that the paper is making is that it may be possible at some point in the future to develop some system which can somehow use some new application of statistics to break some encryption scheme.


Indeed, quantifying the randomness of the output of a system based on a measure of Shannon entropy is an interesting datapoint, but that single datapoint isn't the core of cryptography as this article seems to suggest.

The suggested measures present there aren't attacks against any particular cryptosystem, but rather a potential means of refuting the the proofs of security potentially proposed for some theoretical cryptosystem.


Use a truly random password. The summary wasn't very good, but basically it seemed to indicate that certain cases result in faster failures because of low entropy input, which basically falls in to the realm of proving what we've known for years. I don't really see how this is big news. It's just a (maybe) better way of modeling the reduction of entropy due to a lack of true randomness in any aspect of the system. I don't see any immediately practical implication of the paper, at least from the information presented in the summary.

  • $\begingroup$ Thank you! Some of what you said came to my mind as I read the article, but I wasn't sure. It seems they're trying to give weight to their research. The information is somewhat vague. $\endgroup$ – utluiz Aug 15 '13 at 20:47
  • 5
    $\begingroup$ This in no way should be the accepted the answer. $\endgroup$ – Adi Aug 15 '13 at 20:48
  • 4
    $\begingroup$ this in no way should be the accepted answer especially because it didn't read the paper. Standard key generation is uniform random(absent PRNG failure, which does not have have an i.i.d. distribution). Certain things with password and biometric key derivation might $\endgroup$ – imichaelmiers Aug 16 '13 at 3:53
  • $\begingroup$ Sorry for accept a wrong answer, but I thought it was a reasonable answer for my question, even though I could not judge if it was correct. $\endgroup$ – utluiz Aug 16 '13 at 13:11
  • 1
    $\begingroup$ @imichaelmiers - updated to clarify my initial intent that it was talking about finding weaknesses based on any lack of ideal randomness since it only needs to find worst cases rather than average cases. Also agree it shouldn't be the accepted answer though. I responded quickly simply to indicate there was nothing major to see here and honestly didn't bother giving it much thought beyond that since it's a fluff paper without much in the way of significant merit from what I could tell. It was intentionally a minimal first answer and I fully agree that others have done better since I posted. $\endgroup$ – AJ Henderson Aug 16 '13 at 14:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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