RE: Protection against offline dictionary attack on static files
Jill's approach to key stretching is not quite the same as the
traditional iterated hash. It imposes no cost at encryption time,
you only have to work at decryption. This might be valuable when you
want to save your files as the Gestapo is breaking down your door.
I've been working on a similar method for use as an anti-censorship
tool. Files would be encrypted with a random key and posted on the
Internet. The key size would be selected to require a long time to
crack: hours, days or even weeks. People in countries behind national
Internet filtering could download these files and crack them,
possibly telling friends the recovered key. Censors would have to
expend a lot of effort trying to learn the files that contained
forbidden ideas. It would be inexpensive to create many different
encryptions of the same file and mirror them in multiple locations or
to flood them on Usenet. The URLs of good stuff could be spread by
word of mouth.
Arnold Reinhold
At 2:26 PM -0500 11/12/03, Steve Wang wrote:
Check PKCS #5: http://www.rsasecurity.com/rsalabs/pkcs/pkcs-5/index.html
Steve
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Arcane Jill
Sent: Thursday, October 23, 2003 3:21 AM
To: [EMAIL PROTECTED]
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 [EMAIL PROTECTED]
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Protection against offline dictionary attack on static files
Arcane Jill wrote: ... a way to make decryption more expensive ... I think it is a neat idea. I think it is best understood as a kind of key-stretching akin to iterated hashing of a password, as in: Secure Applications of Low-Entropy Keys (1998) John Kelsey, Bruce Schneier, Chris Hall, David Wagner http://citeseer.nj.nec.com/kelsey98secure.html I invented it myself at one point, and then subsequently learned that it had already been published. Here are some notes I wrote about it earlier this year: I've learned that Udi Manber, MartÃn Abadi [1], Mark Lomas, and Roger Needham [2] have already published one of my ideas -- that of an extra salt used to hash passwords, erased, and then brute-force-rediscovered when needed. This kind of thing reassures me that my own part-time, self-directed crypto research isn't too far off the mainstream. Manber's paper [3] is earliest, but Abadi's [4] (published as a Technical Report) contains extra goodies such as consideration of off-line brute force attacks on weak keys used in communication protocols and a comparison to the more widely used key- strengthening of iterated hashing. [1] http://www.cse.ucsc.edu/~abadi [2] http://research.microsoft.com/users/needham/ [3] http://citeseer.nj.nec.com/manber96simple.html [4] http://www.cse.ucsc.edu/~abadi/Papers/pwd-revised.ps Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Protection against offline dictionary attack on static files
Check PKCS #5: http://www.rsasecurity.com/rsalabs/pkcs/pkcs-5/index.html
Steve
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Arcane Jill
Sent: Thursday, October 23, 2003 3:21 AM
To: [EMAIL PROTECTED]
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 [EMAIL PROTECTED]
Re: Protection against offline dictionary attack on static files
Yes this is a good idea, and some people thought of it before also.
Look for paper secure applications of low entropy keys or something
like that by Schnieir, Wagner et al. (on counterpane labs page I
think).
Also the PBKDF2 function defined in PKCS#5 used to convert the
password into a key for unwrapping PKCS#12 uses the same idea. The
general approach is called key-stretching.
The approach usually involves some form of iterative hashing so
similar to what you proposed.
Adam
On Thu, Oct 23, 2003 at 08:20:35AM +0100, Arcane Jill wrote:
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 [EMAIL PROTECTED]
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Protection against offline dictionary attack on static files
On Thu, Oct 23, 2003 at 08:20:35AM +0100, Arcane Jill wrote: Hi, It's possible I may be reinventing the wheel here, Not really. You've just come down with a bad case of the PBEs. ;-) Take a look at PKCS #5 (here's a link to version 1.5: ftp://ftp.rsasecurity.com/pub/pkcs/ascii/pkcs-5.asc). Essentially, it's the scheme you just described, with provisions for generating more bits of keying material if the encryption algorithm requires more bits than the hash algorithm provides. (For instance, imagine AES with a 256 bit key, but suppose the hash algorithm is SHA-1, which only produces 160 bits of output.) - Ken - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
