On Sat, Mar 30, 2002 at 08:27:02AM -0800, Jeff Cours wrote: > On Fri, 29 Mar 2002, Adam Back wrote: > > > Any takers on ciphersaber-2 test vectors which are also topical > > and amusing english phrases? > > Is there a faster way to search the test vector space than brute > force? Only certain output values from the PRNG will transform > alphanumeric characters into other alphanumerics, so that's one way to > constrain the search, but are there other, more effective ones?
The code on the web page makes that optimization. http://www.cypherspace.org/adam/csvec/ Here's what it does: - from the word sets you feed it equal length word pairs are first XORed and stored for fast lookup with the lookup key being the xor of the word pair, and the value stored being a list of word pairs (you get quite often multiple word pairs that xor to the same value) - brute force by human readable key and iv meeting constraints given by user - first test if key output is 7 bit clean (xor of two 7 bit clean values is 7 bit clean). - if so lookup successive word lengths from the set of word lengths the user requested in the pre-computed word-pair database I use Dan Bernstein's amazingly fast and compact CDB (Constant DataBase) to store the xor pairs in -- if you have enough RAM, or a small word set the lookups will anyway be cached, but the CPU to lookup ratio is such that it's fast enough. (I don't try to keep the CPU busy while waiting for disk, the disk isn't exactly buzzing even with fairly short plaintext / ciphertext words -- if you cared about that small improvement you could start a few clients in parallel or fix the code). Those seemed like the obvious speedups, perhaps there are others. But the current approach may be "fast enough", the frequency with which it finds words goes down as you request longer plaintext - ciphertext words due to the rate of English, but I presume will become more CPU bound as a higher proportion of RC4 PRNG outputs will not be 7-bit clean and so will be rejeced without before getting to the database lookup for. Adam -- http://www.cypherspace.org/adam/ --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]