[106502] in cryptography@c2.net mail archive
Re: Password vs data entropy
daemon@ATHENA.MIT.EDU (Ben Laurie)
Sat Oct 27 11:34:46 2007
Date: Fri, 26 Oct 2007 23:56:05 +0100
From: Ben Laurie <ben@links.org>
To: Alex Pankratov <ap@poneyhot.org>
CC: cryptography@metzdowd.com
In-Reply-To: <000c01c81786$f807b3d0$6601a8c0@lenovo>
Alex Pankratov wrote:
> Say, we have a random value of 4 kilobits that someone wants
> to keep secret by the means of protecting it with a password.
It would assist understanding, I feel, if we thought about 4 kilobits of
entropy, rather than a 4 kilobit value. I want to make this distinction
because I'd like to talk about secret keys, which have to be rather
larger than 4 kbits to have 4kbits of entropy for modular arithmetic stuff.
> Empirical entropy estimate for an English text is 1.3 bits of
> randomness per character, IIRC.
>
> Assuming the password is an English word or a phrase, and the
> secret is truly random, does it mean that the password needs
> to be 3100+ characters in size in order to provide a "proper"
> degree of protection to the value ?
>
> Or, rephrasing, what should the entropy of the password be
> compared to the entropy of the value being protected (under
> whatever keying/encryption scheme) ?
>
> I realize that this is rather .. err .. open-ended question,
> and it depends on what one means by "protected", but I'm sure
> you can see the gist of the question. How would one deem a
> password random enough to be fit for protecting an equivalent
> of N bits of random data ? Is it a 1-to-1 ratio ?
Given the above, it seems there's an obvious formulation.
Let's say the cost of a brute force attack on the secret itself is 2^xn
for n bits of entropy in the secret (it seems that this is actually the
interesting definition of entropy in this case, somewhat circularly).
Similarly, the cost of a brute force attack on the encryption protecting
the secret is 2^ym, where y is the entropy in the password.
So, when 2^ym < 2^xn, it is worth attacking the password.
So, ym < xn and hence m < xn/y.
In other words, your password needs to be x/y times the size of the
secret (in bits), where x and y are the costs of attacking the secret
and the password respectively.
--
http://www.apache-ssl.org/ben.html http://www.links.org/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
