Any practical uses of machine learning for cryptography?

Question

I am about to go study for my masters in machine learning, data mining and high performance computing, but have recently become very interested in cryptography after taking Dan Boneh's Cryptography course on coursera.com.

I was wondering if there are any practical applications for machine learning in cryptography? A quick google search didn't seem to reveal much for me so i was wondering if someone here knows something.

My first impression would be that machine learning techniques could be used to learn the inverse function for some cipher and passphrase given enough plaintext/ciphertext pairs, but i am not sure how capable things like neural networks are at learning functions which are not linearly separable.

Answer 1

I would personally be very surprised if machine learning was of any use in a known plaintext attack.

We design our ciphers to look a lot like random functions; you give the black box an input, and an output spits out. You give it a second input (possibly the same input in the case of nondetermanistic encryption), and a second output spits out. What we try to achieve is that no one can determine whether the black box was our cipher (with an unknown key), or whether it's just spitting out random outputs.

Now, we assume that the attacker has the complete design of our input (apart from the 'key'); in a successful cipher, he still cannot determine it. In fact, we design things so that the attacker can submit inputs of his own choosing; he still cannot determine whether he's giving inputs to the cipher or a random function.

Now, what machine learning would be trying to do is essentially this, except that you would be ignoring the design (because there's no way to give the design to the machine learning process), and you are limited to a known plaintext attack (because your machine learner has no way to generate the chosen inputs). In addition, your machine learner would also not have the best asset a cryptanalyst has (which is his cleverness; programs aren't good at 'clever').

Now, I don't know enough about machine learning to say that it can't be used elsewhere (or that a clever cryptanalysis couldn't use a machine learning program to help with his cryptanalysis); however it certainly sounds to me that machine learning would not be enough to do the entire cryptanalysis job.

Answer 2

Yes, machine learning has applications in cryptography. Probably not in a way that is applicable to your work, though. In the last couple decades cryptographers have been examining machine learning as a source of cryptographic hardness assumptions. The gist of it is that we can use the assumed hardness of learning certain distributions to make new primitives, which form the basis of new protocols.

Ron Rivest wrote a paper on the subject in 1993 called Cryptography and Machine Learning, but a lot of work has happened in the field since then.

More interesting to the OP is Regev's 2005 paper On lattices, learning with errors, random linear codes and cryptography. His results in that paper were really important in developing lattice cryptography and especially the 'learning with errors' assumption. I can't even pretend to understand the results in this area, but Wikipedia can give you a good start.

Answer 3

One possible research topic, appropriate to a Masters level, might be to look at the increase of randomness of common cipher algorithm(s) based of Feistel network, as you progress from round 1 to round n.

The machine learning aspect in this would be to try to find some correlation between input and output of the first round, and see if the machine can extend that knowledge to subsequent rounds. You can play with large datasets, may be with a variety of keys, trying to find data patterns that will help you tune the machine. If you are interested in neural networks, some input / key tuning attempts to minimize output randomness may weed out bad values that would also be useful for cryptanalysts.

I would bet, as poncho stated above, that as you go up the rounds, you will reach to a stage where you can not find I/O correlation anymore (the stage + some safety margin where that cipher becomes a useful tool of the trade). However, if you manage to pull that proposal off, your device would be a useful tool to help determine the min required numbers of rounds in order for a solid Feistel cipher algorithm to be declared "reasonably good".

Answer 4

Attacks against established cryptography of their modern time have rarely if ever succeeded without exploiting knowledge about the cryptographic system they attacked (I do not know any exception since WWII; Enigma, Purple.. are not; and I'd be surprised to learn of any since 1970 in the open literature).

This applies to machine learning: my advise is that it won't solve interesting cryptographic problems if it does not know the structure of the cryptographic system under attack.

I do believe in automated cryptanalysis:

• from output of weak (including some poorly studied) cryptosystems and random number generators;
• or from a description of the cryptosystem.

Machine learning can be useful towards these goals.

Answer 5

Machine learning and decision tree models are being used and improved everyday to break ciphers.

Quantum computing coupled with machine learning is nowadays one of the most sophisticated tools for decryption.