[4178] in cryptography@c2.net mail archive
Re: Strengthening the Passphrase Model
daemon@ATHENA.MIT.EDU (Arnold G. Reinhold)
Wed Feb 10 11:40:05 1999
In-Reply-To: <199902100747.HAA09115@notatla.demon.co.uk>
Date: Wed, 10 Feb 1999 10:18:49 -0500
To: Antonomasia <ant@notatla.demon.co.uk>, cryptography@c2.net
From: "Arnold G. Reinhold" <reinhold@world.std.com>
Cc: Bill Frantz <frantz@netcom.com>, Antonomasia <ant@notatla.demon.co.uk>
>I wrote:
>>2. PGP should burn computer time hashing the passphrase. While you cannot
>>increase the entropy of a passphrase with an algorithm, you can make
>>exhaustive search far more difficult.
At 7:47 AM +0000 2/10/99, Antonomasia wrote:
>
>>From memory, Rivest and Wagner have a paper on crypto time locks where
>repeated squaring is reckoned to be incapable of much parallel computing.
>I think I got it from Rivest's web site in mid-1997.
>
The paper is "Time-lock puzzles and timed-release Crypto," by Ronald L.
Rivest, Adi Shamir, and David A. Wagner and is available at
http://theory.lcs.mit.edu/~rivest/publications.html. It presents a clever
idea that lets you quickly create a problem which takes a long, but roughly
calibrated time to solve and has little opportunity for speed up by
parallelism..
However, I don't see how it applies here. Finding a passphrase by
exhaustive search is an inherently parallel problem. You just let different
engines attack different sets of trial passphrases. And being able to set
up the problem quickly is not much of a win in this case since you only do
that occasionally, when you generate a new key or passphrase, whereas you
must solve the problem each time you use the passphrase. My goal is to use
as much of the hardware in a typical PC as possible to make building each
engine more expensive.
At 11:11 PM -0700 2/9/99, Bill Frantz wrote:
>This technique will be useful against most retail attacks. However, if
>your attacker is snarfing as many secret keys as she can, then she can
>check many keys against each hash, reducing the cost/key. In the limit,
>she has been spending the last year calculating a table of hashes for all
>the words/phrases in her dictionary, and storing them on disk.
Adequate salt is the standard prescription for dictionary attacks and PGP
already uses plenty. Perhaps I should have been more clear and written: "2.
PGP should burn computer time hashing the passphrase along with enough
salt."
Arnold Reinhold
