Subject: long passphrases

From: "Joel N. Weber II" <[email-masked]>
Date: Fri, 18 Jul 2003 13:46:05 -0400

I got thinking about the problems with long passphrases.

One problem is how much you can memorize.  But I once managed to
memorize the sentence ``When an official document records voluntary
manifestations of popular sentiment under a despotic government, a
certain suspension of belief may be safely recommended.''  wc tells me
that has 167 characters.  Schneier seems to say that you get 1.0 to
1.5 bits per character of entropy there, which suggests 167 to about
250 bits of entropy in that phrase.  (I'm counting the spaces and
newlines and perhaps shouldn't be, and perhaps you actually get a bit
less entropy than that, with that particular phrase.)

I'm sure that most people have to write such a phrase down in a secure
place and frequently refamiliarize themselves with it for a while
(perhaps over the course of a few weeks) before they memorize it, but
I do think it can be done.

Then there's the problem of entering the phrase.  One issue is that
two and a half lines is kind of long; I'm not sure if it's possible to
get people to accept the time and effort involved or not.

Another issue is typos.  It's not exactly uncommon for someone to type
a password multiple times to get it right.  My track record on
entering passwords is probably one typo every 20 or 30 characters.  It
is likely that there are certain typos I make rather consistently
(such as screwing up the timing of hitting the shift key).

One idea that comes to mind is that a client could keep track of each
attempt at entering the passphrase.  If you compare two or more
attempts, and they have different typos, the client can try iterating
over different ways to combine the typos.  For example, if my password
is Foo3bAr and I enter foo3bAr and Foo3bar, a client could guess that
it should try foo3bar and Foo3bAr.  Such logic is probably a bad idea
for short passwords, but may be valuable in making long passphrases
possible.

Another thing to consider is that people are likely to make the same
typos repeatedly.  If I have 167 bits of passphrase, and I have a half
dozen different typo keys that the KDC has remembered it will accept
the same way it will accept the original passphrase, I bet even after
you consider the birthday problem on the typo keys, I have something
substantially better than a 128 bit key.  (Logic that only adds a typo
key after it's been found to be used consistently, etc, is probably a
good idea.)

---

From: Sarad AV <[email-masked]>
Date: Sat, 19 Jul 2003 00:10:12 -0700 (PDT)

hi,

> less entropy than that, with that particular

We can reduce the skew as in  RFC 1750 by mapping as
(if the bits are independent)
group the bits into pairs
if the pair is 00 map it to 0 
if the pair is 11 map it to 1
if the pair is 01 map it to 0
if the pair is 10 map it to 1

Another way is redcue skew by xor 

let p(0) be the probability of occurance of 0
and p(1) be the probability of occurance of 1.

let 
p(0)=0.5+e
p(1)=0.5-e

where e is the bias of the bit towards 0 or 1
ideally e=0 & P(0)=P(1)=0.5(no bias condition,ideal)

For any  2 independent bits 

so all the possible combinations are

P(i=1, ii=1) =(0.5-e)(0.5-e)
P(i=1, ii=0) =(0.5-e)(0.5+e)
P(i=0, ii=1) =(0.5+e)(0.5-e)
P(i=0, ii=0) =(0.5+e)(0.5+e)

but if we XOR (i) and (ii) together, then
(i=1, ii=1) = 0
(i=1, ii=0) = 1
(i=0, ii=1) = 1
(i=0, ii=0) = 0

collecting identical outputs allows us to say
 
P(0)=P(i=1, ii=1)+P(i=0, ii=0) =
(0.5-e)(0.5-e)+(0.5+e)(0.5+e)

P(1) P(i=1, ii=0) + P(i=0, ii=1) =
(0.5-e)(0.5+e)+(0.5+e)(0.5-e)

p(0)=(0.5+e)^2+(0.5-e)^2=0.5+2*(e^2)

Similarly xoring 4 bits together we get,

P(0)=0.5+((8*(e^4))

As long as the bits are independent reducing bias from
the original sentence is not difficult.

A more time consuming method would be data
compression.

> get people to accept the time and effort involved or

It appears that it dependents on how much is at
stake.If your data is valuble you might need to use a
good multi pass shredder,as the one peter gutmann
proposed in
http://www.usenix.org/publications/library/proceedings/sec96/full_papers/gutmann/
or even set up a faraday cage to stay safe from
optical tempest.

Regards Sarath.

__________________________________
Do you Yahoo!?
SBC Yahoo! DSL - Now only $29.95 per month!
http://sbc.yahoo.com