Re: Evolving algorithm for faster brute force key searches?
At 8:01 PM 7/5/96, jack wrote:
I got an idea last night, maybe this has already been thought of and tried, but I thought I would give a quick outline of the program I was thinking of:
-Specify a maximum key size (assume 1024bits or something) -Start with an arbitrary key "aaaaaaaaaaaaaa"
Start a loop
-create five mutations of the key -use each key to try and decrypt a few bytes of the message -run a (or some) statistical analysis tests and come up with a value for how 'random' the decrypted bits are -Pick the key that produced the least random ouput
Schneier actually used my explanation of why this won't work in the Second Edition of his book. Basically, with any strong. modern cipher, there is no concept of "getting closer" to a solution. Thus, the "fitness landscape" for a brute-force-needed cipher looks like a flat plain (if portrayed in two dimensions), with the solution/key being a single-point spike rising from the plain. No hill-climber can find this spike except by landing right on it, which means evolutionary programming, genetic algorithms, simulated annealing, and neural net sorts of approaches are worthless. With some weak ciphers, this might work. I think Schneier makes some comments about who's looked at this. But weak ciphers are not too interesting. --Tim May We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."
Adam Shostack <adam@homeport.org> [...]
Weak systems are thus useful for research and training purposes. I suspect Tim is on the money with a genetic algorithim having a flat `fitness landscape,' but there may be something that a human misses which an evolved algorithim finds.
Also, it may be possible to evolve something against a reduced round version of a cipher (using a training space that is not flat) that will still work better than brute force against a full system. If you have cycles to spare, it might be an interesting avenue of research.
While a well-designed algorithm has a flat search space in the case of a single instance of a particular ciphertext/plaintext, this is not necessarily the case for repeated encryptions using the same key and possibly for other examples (hence differential cryptanalysis, etc.) If there is a way to break a system that is less than a brute-force search of all possible keys then the landscape is not flat. The hard part with making such discoveries using evolutionary methods is that even if the landscape is not completely flat the positive and negative reinforcement needed to perform selection in such an environment almost always necessitates that the fitness function be crafted with this in mind by the researcher and few evolutionary programming researchers know anything about crypto. While there are a few strikes against such research (as the oft repeated "flat landscape" phrase shows) I would not let the current state of the art in this area disuade anyone interested. Most of the research done so far has been done by people who either knew little about crypto or little about evolutionary programming. There are also other areas of crypto relevance which may prove more amenable to evolutionary programming methods, like factoring... jim
Timothy C. May wrote: | With some weak ciphers, this might work. I think Schneier makes some | comments about who's looked at this. But weak ciphers are not too | interesting. At the most recent Crypto, someone mentioned that FEAL is useful because just about any new attack you can think of works well against it. I think it was Susan Langford. Weak systems are thus useful for research and training purposes. I suspect Tim is on the money with a genetic algorithim having a flat `fitness landscape,' but there may be something that a human misses which an evolved algorithim finds. Also, it may be possible to evolve something against a reduced round version of a cipher (using a training space that is not flat) that will still work better than brute force against a full system. If you have cycles to spare, it might be an interesting avenue of research. Adam -- "It is seldom that liberty of any kind is lost all at once." -Hume
participants (3)
-
Adam Shostack -
Jim McCoy -
tcmay＠got.net