Re: work factor calculation for brute-forcing crypto

2009-07-19 Thread David Wagner
Assume for a moment that we have a random number generator which is
non-uniform, and we are using it to generate a key.

What I'd like to do is characterize the work factor involved in
brute-force search of the key space, assuming that the adversary
has knowledge of the characteristics of the random number generator?

You may want to use the guessing entropy.
I've written about it before here:

http://www.cs.berkeley.edu/~daw/my-posts/entropy-measures 

Christian Cachin's thesis is a wonderful introduction to entropy
measures, including the guessing entropy.

By the way, I'll make the obvious recommendation: Try to avoid
using a non-uniform random number generator to generate a cryptographic
key, if you can.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: work factor calculation for brute-forcing crypto

2009-07-19 Thread David Malone
On Fri, Jul 17, 2009 at 01:37:43PM -0500, 
travis+ml-cryptogra...@subspacefield.org wrote:
 I'm curious if there's a way to express this calculation as a
 mathematical formula, rather than an algorithm, but right now I'm just
 blanking on how I could do it.

This has been dubbed the guesswork of a distribution by some authors,
I think originating with:

John O. Pliam. The disparity between work and entropy in
cryptology. http://philby.ucsd.edu/cryptolib/1998/98-24.html,
February 1999

It turns out that its asymoptic behaviour is bit like that of Renyi
entropy, see:

E. Arikan. An inequality on guessing and its application
to sequential decoding. IEEE Transactions on Information
Theory, 42:99105, Janurary 1996.

I did an explanitory writeup of this with some experiments at:

http://www.maths.tcd.ie/~dwmalone/p/itt05.pdf

David.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com