Register article on using non-randomness of encrypted file content to reduce time needed to decrypt by brute force
Peter Fairbrother
zenadsl6186 at zen.co.uk
Thu Aug 15 18:41:28 BST 2013
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
More information about the ukcrypto
mailing list