Using AI to perform Cryptanalysis

Question

If given a large set of examples of cyphertext and corresponding plaintext, could AI be trained to decrypt a cyphertext as the examples provided?, and if so, are there any examples online demonstrating this?

For example, lets imagine out cypher is a simple 7-shift ceaser shift, and we have a list of thousands of examples like so

olssv,hello 
ifl,bye
dvysk,world

Could a neural network be trained on these examples, and then shown a new cyphertext, not in the training set, such as "isbl" and correctly infer the result as "blue"?

Answer 1

Yes it could work for simple ciphers. Here's a quick example:

# dependencies
import numpy as np

# machine learning
from keras.models import Sequential
from keras.layers import Dense

# constants
BASE = 97
MAX = 26

# let's assign a = 1, z = 26, ciphertext x and decrypted value y
y = np.arange(0,MAX,1)
x = np.roll(y,-7)

model = Sequential()
model.add(Dense(256, input_dim=1, activation='relu'))
model.add(Dense(128, activation='relu'))
model.add(Dense(64, activation='relu'))
model.add(Dense(32, activation='relu'))
model.add(Dense(MAX, activation='softmax'))

model.compile(optimizer='adam', loss='sparse_categorical_crossentropy', metrics=['accuracy'])

history = model.fit(x, y, epochs = 500, verbose=0)

for x_test in [['o', 'l', 's', 's', 'v'], \
               ['i','f','l'], \
               ['d', 'v', 'y', 's', 'k']]:
  x_test = list(map(lambda x: ord(x) - BASE, x_test))
  # print (x_test)

  pred = model.predict_classes(x_test)
  print(list(map(lambda x: chr(x + BASE), pred)))

Predicted output: link here

['h', 'e', 'l', 'l', 'o'] ['b', 'y', 'e'] ['w', 'o', 'r', 'l', 'd']

Answer 2

The best example of black-box, end-to-end learning of the type you describe in the literature is probably Greydanus' work on Learning the Enigma With Recurrent Neural Networks. They achieve functional key recovery for the restricted version of Enigma they study, but require much more data and computing power than traditional cryptanalysis of the same mechanism would. The paper itself freely points this out; black-box, end-to-end learning to decrypt just is hard.

Links:

Paper Blog post Code

Outside the black box setting, one can however do a lot better. At the time of writing, the best reference I am aware of is my CRYPTO 2019 paper Improving Attacks on Round-Reduced Speck32/64 Using Deep Learning. The main attack of the paper breaks 11-round Speck32/64 roughly 200 times faster than the best previous cryptanalysis:

Paper Talk Code

The code also contains (and the paper describes in a footnote) an easily practical attack on 12-round Speck using the same methods.

Finally, AI is not the same as machine learning and does not necessarily have to even use machine learning. With that in mind, e.g. Using SMT Solvers to Automate Chosen Ciphertext Attacks by Beck, Zinkus and Green would I think count as "using AI techniques for cryptanalysis" as well:

Paper WAC2 talk

Answer 3

That depends on the encryption. But for all simple monoalphabetic substitutions the answer is yes. And to don't need a neutral net, but the most simple classifier works. You train it on the letters of the cipher-texts, with the cleartext-letters being the classes. To apply the decryption to an unknown text, just let it classify each letter of the cipher independently and then concatenate the results to get the cleartext.

Answer 4

For weak ciphers, sure, for somewhat modern ciphers, e.g enigma, short of possible but not as efficient as other methods. for modern cryptography? No

Machine Learning is a very broad field so obviously I can't give conclusive statements about what can't be done. But in general if we think of gradient decent techniques we need a notion of getting close to a solution without finding it.

If for example we explore the key space of a modern cipher if we get even one bit off it should make the output totally unrelated.

We don't know how to smoothly transition between a function which decrypts a modern cipher with a key to random noise and rate how good are the partial results.

If you show how to do this for a modern cipher, that would enable gradient decent approaches and allow breaking the cipher. it would be quiet a feat.

Answer 5

I'm surprised nobody has mentioned the theoretical connection here. I'm unfortunately unqualified to provide this precise answer, but can mention what I've heard from my colleagues.

A significant development in the last roughly twenty years in complexity theory has been the "Hardness vs Pseudorandomness" paradigm. This is based on formalizing the following heuristic:

If you have some "universal learner" for a circuit class, meaning some black box algorithm that (via purely observing input/output behavior) can learn the underlying function, then you cannot have pseudo-random functions in this class.

This is for "obvious" reasons --- the universal learner would become a distinguisher! The perhaps more surprising part of this connection is that it goes in both ways --- if there exist "truly hard to compute functions", they can be used to create pseudorandom generators (which then can be used to do complexity-theoretic things like derandomize BPP or whatever).

Here "learn" is fairly vague (and I am not well-read enough to know the precise definition), but the underlying heuristic may still be useful for this question --- either you have some "universal black box learner", or you can have pseudo-random generators. This isn't to say that AI-based cryptanalysis can never work, just that if you believe PRGs exist it (necessarily) cannot work in all cases, and it is sufficient for "any hard problems to exist" for PRGs to exist. Of course any particular PRG used in practice may be "weak", so this isn't a statement that learning theory results must fail in any particular cryptanalytic task.

As mentioned before, I don't know the literature in this area, but routinely hear people talking about Nisan, Wigderson, and Impaglazzio's work in the 90's, so if you want more info those are probably good authors to look into.