[dm-crypt] luksFormat Password Entropy

Arno Wagner arno at wagner.name
Sat Aug 21 19:41:06 CEST 2010


On Sat, Aug 21, 2010 at 09:30:25AM +0200, Heinz Diehl wrote:
> On 19.08.2010, Arno Wagner wrote: 
> 
> > > So if you choose base64, P will always be 64, 
>  
> > No, actually, the input can restrict P to something smaller.
> 
> I don't think you're right. If the input doesn't lead to the use of 
> all of the chars available in base64, so does it "choose" from this pool 
> anyway. P is the amount of possibly available chars and is unrelated 
> to how many different ones out of this pool actually are used. 

You entropy formula assumes equal propbability and independence 
between the positions. 

> To
> bruteforce the password, you'll have to try all the 64 possibilities for
> each position (ok, statistically you'll have to try 50% of the whole
> headroom).
> 
> If you e.g. build a password which uses 5 numbers, P is 10 [0-9].
> A password out of 5 capital letters, P = 26 [A-Z]. For each of the
> positions ("slots") in the password, there are 10 different possibilities 
> related to the first, and 26 to the second password.

Assume independendce and uniform distribution, you are right.
Hiowever with non-independence and/or nonuniformness, you
are wrong. Example:

String of 10 "0"/"1" randomly, entropy is 10 bit:
   "1001010010"

base64("1001010010"): 
    "MTAwMTAxMDAxMAo"

15 chars, 7 different ones, still 10 bit entropy. Why?
a) the positions are not independent anymore and b)
the chars have nonuniform distribution. The formula for
the entropy here is a bit more complicated...

To comne back to my original argument, P is also restiricted
to something smaller, in addition to you entropy formula being
invalid for the second form.

The thing to remember here is that 1:1 mappings (Isomorphisms)
do not change the entropy of the whole object. Examples are 
compression, decompressions, encryption, decryption, base64
encoding or decoding, ...

Arno
-- 
Arno Wagner, Dr. sc. techn., Dipl. Inform., CISSP -- Email: arno at wagner.name 
GnuPG:  ID: 1E25338F  FP: 0C30 5782 9D93 F785 E79C  0296 797F 6B50 1E25 338F
----
Cuddly UI's are the manifestation of wishful thinking. -- Dylan Evans

If it's in the news, don't worry about it.  The very definition of 
"news" is "something that hardly ever happens." -- Bruce Schneier 


More information about the dm-crypt mailing list