handling weak keys using random selection and CSPRNGs

[Travis H.]

Hi all,

It occured to me that there is a half-decent way to avoid weak keys in
algorithms
when it is undesirable or impossible to prompt the user for a
different passphrase.
It is even field-upgradable if new weak keys are found.

Basically, instead of using the hash of the passphrase up front, you do a PRNG
expansion of the passphrase.  For example,
k_1 = hash(1||passphrase)
k_2 = hash(2||passphrase)

and so on.

The important thing here is that it is not something like the following:

k_1 = hash(passphrase)
k_2 = hash(k_1)
...
k_n = hash(k_(n-1)

In that method, the number of input states is limited by the hash size, whereas
the former algorithm has a number of states that the k sequence can be in
is limited by the size of the passphrase.  I suppose that a running hash
would be limited by the size of the hash state (chaining variables).

Next you construct k = k_1 || k_2 || ... k_n

The computation can be done incrementally on an as-needed basis.

Then, you read in the number of weak keys, and perform a random selection
on the number of valid keys using the algorithm I posted earlier, with k as
the source of unpredictability.  This leaves you with a random number between
0 and the number of non-weak keys minus one.  Then you iterate over the weak
keys in numerical order, incrementing the value from the previous step
by one if it exceeds the weak key's numerical value.  This part runs in
time linear with the number of weak keys, not the size of the non-weak keyspace.

You are left with a value that has a uniform distribution over the
non-weak keys.

The random selection algorithm may run indefinitely, but the chances of
that are infinitesimal.  If there are a huge number of weak keys, then it
may take longer, but I'd be willing to bet that CPU speed increases faster
than discovery of weak keys, and if it doesn't the user might be
inconvenienced enough to upgrade to a less broken cipher algorithm.
-- 
"The obvious mathematical breakthrough would be the development of an
easy way to factor large prime numbers.'' [sic] -- Bill Gates  -><-
<URL:http://www.lightconsulting.com/~travis/>
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com