Genetic Algorithms

[mala]

A while ago, some friends wrote about GA-based reversing (a great article on codebreakers, and something else on http://www.anticrack.de/ if I remember well) and we spoke about them for a while on anticrack forum. Well, I haven't stopped working on them, nor I have finished :)... in the meanwhile I've collected a "webography" for the paper I'm preparing, which is about GAs applied to cryptanalysis.

My final idea is that, even if GAs are very powerful for function optimization, it's still a hard task to use them for well designed algorithms such as real hashes, while classic ciphers such as monoalphabetic and polialphabetic substitutions should work fine. The most interesting thing, anyway, is that some programmers use "home made hashes" which are easily crackable with a GA (I experimented with some and it's a real fun). An interesting work could be trying to understand how many of them do this :)

Anyway, no more words, here are the links: enjoy!

== Generic papers about GAs ==

* Pacman using genetic algorithms and Neural Networks
http://www.ece.umd.edu/~adityak/Pacman.pdf

* A Genetic Algorithm Tutorial
http://citeseer.nj.nec.com/29471.html

* An Introduction to Genetic Algorithms
http://www.coyotegulch.com/coyotica/GAIntr...ro/genetic.html (http://www.coyotegulch.com/coyotica/GAIntro/genetic.html)

* Melanie Mitchell: "An Introduction to Genetic Algorithms" reviews
http://www.coyotegulch.com/reviews/Books/IntroGA.html
http://www.generation5.org/content/2000/ga...ga_mitchell.asp (http://www.generation5.org/content/2000/ga_mitchell.asp)

== Generic papers about crypto ==

* Prof. Danilo Gligoroski's web site
http://www.pmf.ukim.edu.mk/~danilo/

* ZIP Attacks with Reduced Known-Plaintext
http://www.woodmann.com/fravia/mike_zipattacks.htm

* A Known Plaintext Attack on the PKZIP Stream Cipher
http://citeseer.nj.nec.com/122586.html

* Self-Study Course in Block Cipher Cryptanalysis
http://www.schneier.com/paper-self-study.html

* A Fast Method for the Cryptanalysis of Substitution Ciphers
http://www.ioi.dk/Homepages/thomasj/public...ations/subst.ps (http://www.ioi.dk/Homepages/thomasj/publications/subst.ps)

* Statistical Techniques for Language Recognition: An Introduction and Guide for Cryptanalysts
http://citeseer.nj.nec.com/ravi93statistical.html

* Cryptologia
http://www.dean.usma.edu/math/pubs/cryptologia/

== Papers about GAs and crypto ==

* Cryptanalysis, Almost by Aimlessly Thrashing About
http://home.ecn.ab.ca/~jsavard/crypto/co040502.htm

* Attack On the Polyalphabetic Substitution Cipher Using a Parallel Genetic Algorithm
http://www.pmf.ukim.edu.mk/~danilo/Researc...cSCOPES2003.pdf (http://www.pmf.ukim.edu.mk/~danilo/ResearchPapers/Crypto/AttackPolyalphabeticSCOPES2003.pdf)

* The Cryptanalysis of a Three Rotor Machine Using a Genetic Algorithm
http://citeseer.nj.nec.com/162166.html

* The Applications of Genetic Algorithms in Cryptanalysis
http://citeseer.nj.nec.com/bagnall96applications.html

== GA libraries ==

* Perl - AI::Genetic
http://search.cpan.org/~aqumsieh/AI-Geneti...0.01/Genetic.pm (http://search.cpan.org/~aqumsieh/AI-Genetic-0.01/Genetic.pm)

* GAlib: A C++ Library of Genetic Algorithm Components
http://galib.sourceforge.net/

== GA Websites ==

* Generation 5
http://www.generation5.org

* ''Re: coding and nnet's'' thread
http://cypherpunks.venona.com/date/1995/11...1/msg00609.html (http://cypherpunks.venona.com/date/1995/11/msg00609.html)

[Evilcry]

Hi,
yeah these are real nice links. I'm intersted on this genre of algorithms, especially on "how can develop a generation of good solutions for 'crypto". Its nice to see in reversing how can be possible to solve some challenges, as "81 bits problem" (you readed codebreak and you surely know what i mean :wink:). Finally i just wanted to report here a nice crackme's solution of +Q,
this can be founded on www.crackmes.de and crackme is called Sliders

Actually i'm coding a genetic bruteforcer for a crackme, finally i will post here a link to this :wink:


Ciao Da Evilcry

[mala]

Yeee!

I've read sliders tut: I've been searching around a lot after I decided to work seriously on GAs and this was one of the few code-reversing oriented ones, so it immediately became a must for me :)

And of course your work on the genetic bruteforcer will become a must too! Hey, what language/libraries are you using to develop it? I'm working with gcc and GAlib (http://galib.sf.net) and, while on one side the library is OK for me (it has many useful features), on the other side I'm so accustomed to perl that going back to code in C is a real pain in the ass ^__^

For what concerns crypto, I've been searching fitness functions for a while and, while on the real hashes field I've found almost nothing (well it's quite easy to know why: it's HARD, if not IMPOSSIBLE sometimes), I've seen many different evaluations for mono/polyalphabetic ciphers, such as:

(well, first of all your genes are possible keys/alphabets and you use them to decrypt the text, then you want to see how correct is the decrypted text)

- counting the letter frequencies (trivial and not working fine)
- counting the sizes/frequencies of vowel/consonant clusters (better but still not useful alone)
- counting the frequencies of digrams (better)
- counting the frequencies of trigrams (still better, but heavier to compute)
- searching for words inside a dictionary (heavy to compute for large text, maybe better results for small ones, not 100% accurate anyway)

A nice thing I've seen is an evaluation function which takes into account many of these checks, giving them different weights. If i remember well, the weights were hardcoded but worked fine anyway.

What I'd like to do now is working on the same idea, making the weights evolve themselves with a neural network. I've seen something like this in the "pacman" paper and it seemed to yield good results. The strange thing, anyway, is that I find many, many papers about GAs used to evolve weights for NNs and not vice versa! So I'm back collecting information around and ideas, and this project is taking me SO much time without even being a thesis (well, everything for glory as usual ;))

[Evilcry]

Ciao mala,
i use mainly VC++ and (GAGS- EO Evolutionary Computation Framework),
sometime i'v used also your same pattern (gcc+GALib).

I'm really intersted in GA applied to reverse 'n crypto. I agree with you, homemade hashes could be solved or at least could be obtained a good "Generation of solutions". For monoalphabetics cipher the solution is to create a generation of solution, and the using the params that you listed (letter frequencies, ect) to make a good Natural Selection inside our Generation :wink:.

A nice thing I've seen is an evaluation function which takes into account many of these checks, giving them different weights. If i remember well, the weights were hardcoded but worked fine anyway.


Great!, this is an intersting thing to study better.
Well when i finish my code, i will send you a copy :)

Ciao By Evilcry

[mala]

Well when i finish my code, i will send you a copy :)

Thank you very much, I'll be glad to read it ^__^