10
$\begingroup$

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?

$\endgroup$

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
  • 7
    $\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
  • $\begingroup$ Never trust news that does not even run over https. The article is most likely being MITMd and edited on the fly to manipulate and scare you. $\endgroup$ – michnovka Apr 27 at 16:44
  • $\begingroup$ @michnovka lolwut $\endgroup$ – forest Apr 29 at 0:46
20
$\begingroup$

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.

$\endgroup$
  • $\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
5
$\begingroup$

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.

"OK."

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.

$\endgroup$
2
$\begingroup$

Suppose you draw a password at random from a distribution $D$, such as ten-letter passwords with each letter chosen independently at random according the English letter frequencies (y'know, ETAOIN SHRDLU, etc.). If I'm trying to guess the password by some guessing algorithm like JtR, what's the expected number of guesses—that is, the average number of guesses weighted by the probability that I guess the word after that many guesses using my method? This is a proxy for the expected cost of breaking a system that uses $D$.

If every word had equal probability, the answer would be easy: if there are $n$ words, each guess independently has probability $1/n$ of being correct, so if I make $g$ distinct guesses then I have probability $g/n$ of guessing your password, and the expected number of guesses is $(n - 1)/2$. In this case, it happens that the Shannon entropy $H$ of the distribution is $\log_2 n$ bits, and the expected number of guesses coincides almost exactly with $2^H/2$.

What the authors of the paper observed is that when the distribution $D$ on passwords is not uniform, the cheapest expected cost is not $2^H/2$, where $H$ is the Shannon entropy of $D$, but can be much cheaper. (Illustration of a guessing game with small numbers.)

This is not a surprise to cryptographers. Although the term entropy sometimes appears in cryptography, for decades cryptographers have understood that Shannon entropy is only about average information rate which matters more for telegraph operators than for cryptographers, while min-entropy is about the worst-case predictability which is what matters for cryptography. (Example of how bad things can get even if you have high Shannon entropy.)

This paper has no consequences whatsoever for any serious cryptography of the past half century. The blog post from the MIT News Office, which is the university's marketing department and not an academic publication, is overblown nonsense. They didn't cite a single instance where any serious cryptographer has ever been confused about this, which reflects more on familiarity with the cryptography literature than with the security of modern cryptography. This is not to say the paper itself is bad—it is likely that the audience of the paper is intended not for cryptographers but for designers of physical systems who are familiar with the language of information theory and coding but not with cryptography.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\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 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.