Register article on using non-randomness of encrypted file content to reduce time needed to decrypt by brute force

[Peter Fairbrother]

On 15/08/13 11:00, Brian Morrison wrote:
>
> Not seen this mentioned anywhere else yet:
>
> http://www.theregister.co.uk/2013/08/14/research_shakes_crypto_foundations/
>
> Any opinions from those with direct knowledge of such techniques?


Lot of hot air. Maybe useful for coding theorists, but nothing new 
relevant to cryptography. I don't think the authors are crypto mainstream.

"Abstract—Consider the situation where a word is chosen
probabilistically from a finite list. If an attacker knows the
list and can inquire about each word in turn, then selecting
the word via the uniform distribution maximizes the attacker’s
difficulty, its Guesswork, in identifying the chosen word. It is
tempting to use this property in cryptanalysis of computationally
secure ciphers by assuming coded words are drawn from a
source’s typical set and so, for all intents and purposes, uniformly
distributed within it. By applying recent results on Guesswork,
for i.i.d. sources, it is this equipartition ansatz that we investigate
here. In particular, we demonstrate that the expected Guesswork
for a source conditioned to create words in the typical set grows,
with word length, at a lower exponential rate than that of the
uniform approximation, suggesting use of the approximation is
ill-advised."


Well that's all very interesting, but sensible cryptographers just know 
better than to use that approximation.


Actually that's maybe not altogether true - sometimes bad cryptographers 
do. For instance, consider debit/credit card PIN numbers.

A pickpocket gets three chances at guessing a PIN number for a card, and 
maybe 12 guesses if a) the stolen wallet has 4 cards in it, and b) the 
person uses the same PIN for all the cards.

So, if the pickpocket chooses 12 PINs at random he has about a 1% chance 
of correctly guessing a PIN.

However, PINS are not evenly distributed - people use 1234 more often 
than 6948. If our pickpocket uses the 12 most commonly-used PINs he has 
a better than 17% chance of guessing a correct PIN for the 
4-card/same-PIN wallet.

Now the banks may say that the chance of guessing a PIN is 1 in 10,000 
or one in 3,333 for a card or 1 in 833 for a wallet -- when the real 
chance is about 1 in 20 overall for a wallet -- but that's just bad 
cryptography, and using the uniform equipartition assumption when it is 
ill-advised.



Real cryptographers don't do that.

Look at a cryptographer's theoretical brute-force attacks on ciphers - 
though ciphertext-only attacks are sometimes considered, typically we 
start with a known-plaintext attack, and go to via chosen plaintext 
attacks to adaptive chosen ciphertext attacks. No assumptions about 
equipartition or uniformity there.


BTW, I also don't think they in any way say that Shannon was wrong, just 
that some assumptions some people (I assume coding theorists and bad 
cryptographers) make about Shannon aren't always correct.

-- Peter Fairbrother