ciphersaber-2 human memorable test vectors

[Adam Back]

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 majordomo at wasabisystems.com