[Cryptography] Checking for the inadvertent use of test keys

[Peter Gutmann]

Let's say you've got some key-consuming code that's supposed to be fed random
keys and you want to catch inadvertent use of test keys and nonces, strings
like "012345678" and "\x01\x23\x45...", that sort of thing.  For argument's
sake these can be as short as 64 bits/8 bytes.  Can anyone think of any
reasonably simple tests that will catch keys like this?  Standard tests like
the FIPS ones won't catch them (through a combination of the sample size being
very small and the tests not being able to identify "\x01\x23\x45..." as non-
random).  I was looking at things like edit distances between bytes, but you
rapidly end up in a mess of epicycle-style hacks as you add handling for
special cases.

What I'm after is a simple safety check to warn about inadvertent use of
predictable sequences that might get used as test keys.  I'm after actual
algorithmic tests rather than general advice like "have you looked at
Kolmogorov complexity"...

Peter.