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[0] 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