[4177] in cryptography@c2.net mail archive
Re: Strengthening the Passphrase Model
daemon@ATHENA.MIT.EDU (Arnold G. Reinhold)
Wed Feb 10 02:08:20 1999
In-Reply-To: <199902091800.TAA11531@replay.com>
Date: Wed, 10 Feb 1999 00:44:42 -0500
To: cryptography@c2.net
From: "Arnold G. Reinhold" <reinhold@world.std.com>
At 7:00 PM +0100 2/9/99, Anonymous wrote:
>Arnold G. Reinhold writes:
>
>> 1. PGP should suggest a passpharse to the user when a new key pair is
>> generated. PGP already has a trusted source of randomness. Why not offer a
>> passphrase? There could be a choice of formats --Diceware words, random
>> syllables, random letters -- and strengths (5 Diceware words provide 64 bit
>> of entropy, 6 words 77 bits, 7 words 90 bits). The user could, of course,
>> choose to enter his own passphrase.
>
>It's not clear that any machine-generated passphrase with this much
>entropy is going to be remembered by the users. Here are a couple of
>examples of passphrases generated with Arnold's diceware tables, based
>on the digits of pi:
>
>gog gail harem full hedge allot rein
>
>gown gas haze fz herb alley rif
>
>You'd have to have an excellent memory to be able to remember these words
>after just a few moments' study.
Russell Nelson suggested memory aids, and I could point out that these are
90-bit passphrases (7 words) while most users would be well served by
64-bit passphrases (5 words), but I agree with you. Strong passphrases are
hard to remember. That's why I recommend that users write their passphrase
down, at least until they memorize it.
>...
>
>> 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.
>
>It does do this. PGP hashes the passphrase + salt repeatedly, until a
>configurable number of bytes has been hashed. The default configuration
>hashes 32768 bytes. You could patch your version of PGP to increase the
>count. The maximum is 65 million. That should take a while to hash.
That is a start, but why not have PGP compute how many interations it can
perform on the user's machine in, say, two seconds?
>
>> One of my pet ideas is a "computational intensive" hash algorithm.
>> Cryptography usually strives for algorithms that are fast and have a small
>> footprint. I propose a hash algorithm tuned to use as much of the resources
>> of a typical PC as possible, consistant with an acceptible user delay. This
>> means lots of memory, 32 bit multplies, maybe even floating point ...
>What's wrong with iterating a cryptographically strong hash algorithm, like
>PGP does?
There are two problems with iterating hash algorithms like MD5 and SHA1 for
this purpose. First they are faster in hardware than in software. All
those non-linear functions that take several instructions on a general
purpose CPU can execute as a single step in custom silicon.
Second, the hash algorithms can be implimented in hardware on very modest
chip real estate, well under 100,000 gates I would guess. Your basic low
end PC or iMac has, maybe, half a billion gates inside. If you can weave
even 10% of those gates into your hash, massively parallel attacks become
much harder.
The reduction in the speed and gate-count advantage of a hardware attack
could yield the equivalent of adding one diceware word to each passphrase.
That might make a four word passphrase strong enough for most users.
Running the hash for two seconds might gain another factor of 100 to 1000,
shrinking a strong passphrase into the comfort zone.
>
>> 3. PGP should be available on a bootable CD-ROM for the major platforms.
>> (This is easy to do on a Mac, I do not know how hard it is on Wondows or
>> Linux.) Running off a CD while performing encryption would make a
>> virus/trojan attack difficult if not impossible. A separate utility could
>> be distributed to do an SHA-1 hash of the CD.
>
>Wouldn't you have to reboot your computer every time you wanted to encrypt
>something? Or will you boot off your CD-ROM all the time? If the latter,
>would you keep all your programs on CD-ROM, or just PGP? If you don't
>keep all your programs on CD-ROM, then if you run a trojan-containing
>word processor, for example, it can leave malicious code in memory which
>will catch your PGP passphrase later.
I am suggesting rebooting your machine with a PGP CD-ROM every time you
want to encrypt or decrypt. Yup, it is a pain and most people won't bother.
They could still install PGP on their hard disks. But the trojan threat to
PGP is real and the CD boot option provides at least one cheap solution for
those who really need security. Got a better one?
While I am asking for features, adding a text editor, or even better a mail
client, to PGP would make the CD option more tolerable. You could dump all
your encrypted mail into a directory or mail box, reboot in PGP mode, read
your mail and generate encrypted replies and new messages. Without some
built in editor, you'd have to reboot a couple of times for each read/reply
cycle.
>...
>> 4. We should reconsider the time honored advice to never write down one's
>> passphrase. I believe most users are more fearful of forgetting their
>> passphrase than of having it compromised. This is a major reason why they
>> choose weak passphrases.
>>
>> One compromise is to suggest that users come up with the best phrase they
>> are comfortable with committing to memory and then add more words chosen at
>> random, with the extra words written down and kept in a safe place. This
>> approach would also be useful for users who need multiple passphrases. The
>> written random ones would differ and the memorized secret would remain the
>> same.
>
>This is not a bad idea, the traditional combination of "something you
>have" (the written, computer generated list of words) and "something you
>know" (your relatively low-entropy, memorized passphrase). If you're
>going to go with computer-generated passphrases this is probably the
>best way to do it.
>
>But it does force you to clarify your threat model. What are the costs to
>an attacker of acquiring a copy of the written passphrase? Where will
>users put the notes? Post-its stuck to the monitor, in many cases,
>no doubt. Any cracker who scams his way into a tour of the area can reap
>useful information.
>
>Such considerations may not be an issue in some applications, but it
>is clear that this method will not work in all cases.
Training users to keep their passphrase out of sight is a heck of a lot
easier than teaching them to make up a strong passphrase on their own and
then memorize it. There are certainly some threats where nothing less than
a memorized strong passphrase will do. But a computer generated passphrase
would be a big step up in security for most users, even if part or all of
it is written down.
Arnold Reinhold
