### Re: work factor calculation for brute-forcing crypto

```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

```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

```

### work factor calculation for brute-forcing crypto

```Hi folks,

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?

The algorithm for this is simple:

Let the array X represent the probabilities of the outcomes of the
random number generator, sorted by probability, with x being the
probability of the most probable value.

Then, for a given fraction of the messages n (0  n = 1):

i = 0
m = 0
while (m + x[i])  n:
m = m + x[i]
i = i + 1
return (i - 1) + (n - m) / (m + x[i])

This return value represents the average number of decryption attempts
required to guess the right key.  If one wanted to round up, one could
just return i instead of the last expression above, because the second
term is always in (0, 1]

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.
--
Obama Nation | My emails do not have attachments; it's a digital signature
that your mail program doesn't understand. |
http://www.subspacefield.org/~travis/
If you are a spammer, please email j...@subspacefield.org to get blacklisted.

pgpJ4gqi6vQJo.pgp
Description: PGP signature

```