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 [EMAIL PROTECTED]
