Encryption is less secure than we thought
mit.edu
mit.edu
Many proofs in cryptography start with the following assumption: assume x is a bitstring of length N drawn from a uniformly random distribution of bit strings. This assumption is then used as the basis of the proof of the cryptographic construct.
For instance in a provably secure stream cipher you start with that assumption then proceed to show that if weak one-way-functions exist then you can construct a secure pseudo random number generator that is polynomially indistinguishable from a true random source. You then use your assumed random bit string, x, as the key to the psuedo random number generator to generate a one time pad to XOR with your message.
Since the secure psuedo random number generator is indistinguishable from a true random number generator (by a polynomial attacker) the message is secure (from a polynomial attacker). However, this is all predicated on the key being drawn from a uniform distribution. If the key is NOT drawn from a uniform distribution than there may be a potential speed-up available to the attacker.
What the paper shows is that often it is assumed that words drawn from an IID distribution of letters can be treated as if the distribution of words is uniform (given a sufficiently large word size). However, this distribution while very flat is not quite uniform. They show how this can be exploited using the "Guesswork" framework to come up with a tighter bound on the time it would take to guess a chosen word. This bound is much better than the traditional bound used.
What this means is that there needs to be more margin given than previously thought when dealing with keys derived from non-uniform distributions. Such keys include passwords.
Is this assumption really that common? It seems like a strange assumption to make, since even biased coin flips with P(Head) = 0.99 would be independent and identically distributed.
On the surface it seems like this only really effects things which rely on treating these types of distributions. It is difficult for me to say how this effects the analysis of primitives when using keys derived from user input. In practice I don't think it makes much difference as we are already getting quite good at exploiting the distributions from which people seem to draw passwords. However, it may have some important implications for the theoretical side of cryptography.
You will see this called a 'PPT' in the literature, where PPT = Probabilistic Polynomial Time.
Technically this treats O(n^2) and O(n^10000) as the same effort.
By it being very flat but not uniform, what do you mean? I'm not clear on this point.
If you alter your keyspace to exclude that one null key, the proof no longer works.
I still feel like sitting down and staring at the wall when I think about it.
That one makes sense, in a way: If you see a S in cyphertext, you know the plaintext did not have an S in that position. That eliminates 4% of all possible plaintexts, and by extension 4% of all private keys. That's kind of a metric ass-ton of entropy you just lost right there, for every single character.
My guess is, your proof works by a qualitatively similar principle: Restricting the keyspace, no matter how trivially, gives the attacker information. And encryption is all about magnifying information.
On the other hand, the proof shows that leaving the null key out of sample space means the adversary would have 1/2^48 (arbitrary number) to distinguish the ciphertext from a random function, which means that it's "insecure" in the context of the proof.
It seems to me that this notion of secure would still be stronger than our common sense idea of "secure".
> However, this is all predicated on the key being drawn from a uniform distribution
So, we're talking about the generation of the key? Are you trying to say that /dev/random isnt secure (i.e. the source when using algos like SSL)?
> Traditionally, information-theoretic analyses of secure schemes have assumed that the source files are perfectly uniform. In practice, they rarely are, but they’re close enough that it appeared that the standard mathematical analyses still held.
After reading your comment, I'm confused. Are they talking about the entropy of the key or of the plaintext?
The paper is talking about the distribution of plain-texts. As you say, that the IID distribution of letters cannot be treated as if the distribution of words is uniform
This is not a common assumption in cryptography(typically because we assume the attacker knows the real distribution of the plain-texts, the idea being they learn no more about the distribution given the ciphertext) and the papers cited that make this assumption are from sub-par conferences. So it would be more accurate to say some people made a mistake that is neither that common nor a core tenant of cryptography.
for a real world example of failed uniformity assumptions, see cryptocat.
(not that "slightly less secure than we had hoped" is enough reason to panic.)
When cryptographers talk about a "break," they mean anything faster than brute force search. So a break of a 128-bit algorithm that allows key recovery in 2^115 is a "break," but still completely impractical.
But as Bruce Schnier says: "attacks only get better." So a break is a good reason to look for a fix or a better algorithm now before the crack widens.
In my understanding Shannon entropy is not very useful for crypto reasoning for more trivial reasons. A password that has a half chance of being "foo", and half chance of being completely random has good Shannon entropy, but it's clearly not a good password.
The MIT press office has a habit of writing press releases that go beyond the usual hype to be so over-the-top they actually make the work sound crackpot. Happens most often in AI, but I guess in crypto now too. Not the scientists' fault, so I usually try to read the original paper to see their own claims, and invariably they are much more specific and legitimate.
Maybe I'm missing something, but this seems like a known and fairly trivial result.
I read that as basically saying that if you don't pick the letters in your passwords from an uniform distribution, they are easier to guess.
I don't see what that adds when people are already using Markov chains and dictionary attacks to brute force passwords, and I see no implication at all for secure keys chosen by good PRNGs.
I guess it could have some use in entropy estimation for PRNG state, but assuming uniform distribution of input seems like a naive mistake to make. Is there some application of this that I'm missing?
Incidentally, it's also clear that if the encryption schema is large relative to the compressed data then it will also be harder to decrypt (of course if the encryption schema is public, e.g. a public key, then this is decidedly not true).
So, none of this should be terribly surprising. What it does suggest is that you should compress data before (or while) encrypting it, and the better your compression algorithm, the more entropy there will be in your data, and the more secure your encryption.
Got any source for that? Closest I can find is a Polish cryptologist facetiously adding "Heil Hitler!" to ENIGMA encrypted messages he sent to Britain.
"we relied on the fact that the greater number of messages began with the letters ANX—German for "to", followed by X as a spacer"
http://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma
Compressed files (indeed ANY files) having predictable headers is, of course, a major problem, and the argument that you could just omit the common stuff won't work very well either. (Let's suppose you leave off all the static parts until you get to a length stamp -- lengths are a classic example of not-very-random numbers (more significant digits are prone to be lower-valued).
In general, you want your cryptographic system to be reasonably foolproof when used by bored, careless people. For this reason rolling compression and encryption into a single implementation is probably the best option.
What are you going to pad it with? Random values? In that case, I'll just make two requests for the same information and clip it where they differ. Some sort of value based on the message? That also has issues, see link below. So far it doesn't seem like there are any obvious crypto ideas that are not also wrong.
So, byte 0? You're not really using ECB, are you?
At least I can point to it as another example of someone not expert in the field making a stupid statement about crypto...
I think the general problem of padding with random values resulting in non-determinism would still matter in some cases, but IANAC.
It took decades for programmers to come to the awareness of the importance of human factors and user interfaces to reach today's levels. (Really, how useful is computing, if only a very few want to use it?) Yet we're really just beginning to truly get it as a field. (Or as a "not-quite-a-field," to give a nod to Alan Kay.)
It's probably going to take just as long for us to figure out how to account for human factors and economics when it comes to security. Yet, if you are really savvy about security, it should leap out at you that human factors and economics are just about the biggest two determining factors in security.
The big problem is not what algorithm you use to encrypt A or B. It's the employee's and programmer's lack of knowledge about security and key management. It's the secretary who clicks on the phishing link. It's management's misconception that a dozen of BigCo's employees with insufficient peer review can take on the reverse engineering resources of the entire Internet.
The big problems in security have to do with organizational awareness and economics. If you're not accounting for those, you are misallocating your resources, probably by an order of magnitude.
Maybe another way to phrase it is something like encrypting plain text english is now mathematically proven to be not as secure as encrypting a zip (or other format) compressed version of the same english text. (edited to add that its early in the morning and the specific example of a zip file is a great known plaintext attack 0x04034b50 and all that, but "compressing in general" is a good idea. The mistake I made was like calling all photocopiers, "Xerox machines", or all nose tissues "Kleenex").
Crypto is very well taught for algorithms, classes of algos, history, couple other things, but the classes of apps of crypto technology is (intentionally?) very poorly documented and taught. Something that screws up screws up digital sigs probably has little to do with the issues in encryption or authentication or whatever. Its an area ripe for someone to write a book, or a startup to do "something" probably something educational.
Unless there is any opportunity for the attacker to control part of the plaintext?
Password breakers (when having the hash result) do not assume that the passwords are random strings, they use several assumptions that greatly reduce the time they need to break the passwords.
On the other hand, it is the case that most long bit strings sampled from a maximally entropic source have roughly the same number of 0s and 1s.
Nearly all random strings of sufficient length have different numbers of 0s and 1s. So if your argument were true, your compression scheme would reduce the average length of completely random strings, which is impossible.
log(201 choose 100) / log(2) = 196.843
Order the 201 choose 100 strings on 201 bits with exactly 100 0s lexicographically, write down the index in that list of your particular message in 197 bits in a completely ordinary fashion ;P.
But to be clear, I don't disagree with what you mean at all.
Edit: You can do better than this by counting the number of 201 bit messages with 100 0's which is well below 2^201 and then encoding which of those corresponds to the original message. Aka if you had an 8 bit message with one zero 11111101 you have a total of 8 options which means you can encode it as 3 bits.