Protection against offline dictionary attack on static files

[Steve Wang]

Check PKCS #5: http://www.rsasecurity.com/rsalabs/pkcs/pkcs-5/index.html

Steve

-----Original Message-----
From: owner-cryptography at metzdowd.com
[mailto:owner-cryptography at metzdowd.com] On Behalf Of Arcane Jill
Sent: Thursday, October 23, 2003 3:21 AM
To: cryptography at metzdowd.com
Subject: Protection against offline dictionary attack on static files

Hi,

It's possible I may be reinventing the wheel here, so my apologies if 
that's so, but it occurs to me that there's a defence against an offline

dictionary attack on an encrypted file. Here's what I mean: Say you have

a file, and you want to keep it secret. What do you do? Obviously you 
either encrypt it directly, or you store it in an encrytped volume 
(thereby encrypting it indirectly). Problem? Maybe an attacker can 
somehow get hold of the encrypted file or volume ... maybe your laptop 
gets stolen .... maybe other people have access to your machine. In 
principle, you're protected by your passphrase, but if an attacker can 
get hold of the file, they can try an offline dictionary attack to guess

your passphrase, so unless you're very good at inventing high entropy 
passphrases /and remembering them without writing them down/, there may 
still be a risk.

Here's the defence:

To encrypt a file:
    Generate a random number R between 0 and M-1 (for some fixed M, a 
power of 256)
    Type in your passphrase P
    Let S = R || P (where || stands for concatenation)
    Let K = hash(S)
K is now your encryption key. R is to be thrown away.

To decrypt the same file:
    Generate a random number r between 0 and M-1
    Type in your passphrase P
    for (int i=r; ; i=(i+1)%M)
    {
        Let S = I || P
        Let K = hash(S)
        Try to decrypt using key K
    }

This places a computational burden on your PC at decrypt-time. The 
larger you choose M, the more CPU time it will take to figure out K. So,

you choose M such that it takes your PC about one second to find K, then

your attacker will experience the same burden - but multiplied a 
squillionfold (a "squillion" being the entropy of your passphrase). This

means that even if your passphrase consists of just two words from a 
dictionary, /and/ your attacker suspects this, it will still take him or

her over a hundred and fifty years to decrypt (assuming your attacker 
has a PC of equivalent power). Even if your attacker has a faster PC 
than you, it will still be relatively easy to pick a 
strong-yet-memorable passphrase, since better tech can only ease the 
attacker's problem, not remove it. All of a sudden, weak passphrases 
turn into strong ones, and strong passphrases turn into computationally 
infeasible ones.

Is this useful?
Has anyone come up with it before? (Someone must have ... but I don't 
recall seeing the technique used in applications)

Jill


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com