Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
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.
