Neural Cryptanalysis of Classical Ciphers

Riccardo Focardi, Flaminia L. LuccioICTCS 2018

TL;DR

This paper introduces a novel approach to cryptanalysis by using neural networks to automate the exploitation of known cipher weaknesses. By training networks on examples of weakened ciphers and their keys, the authors demonstrate a practical method for achieving ciphertext-only attacks on classical ciphers like Caesar, Vigenère, and substitution, including the first neural network-based attack on substitution ciphers.

What Problem Does This Paper Address?

Traditional cryptanalysis often involves identifying subtle weaknesses in cryptographic algorithms and then manually developing methods to exploit them. While these methods can be effective, they are often complex, time-consuming, and may only work on reduced versions of ciphers. The challenge is to automate this process, allowing cryptanalysts to leverage their knowledge of weaknesses without needing to manually craft every step of the attack. This paper tackles this by exploring how artificial neural networks can be trained to "assist" cryptanalysts, effectively learning to exploit identified cipher weaknesses automatically, even in ciphertext-only scenarios.

Methods

The core idea is to train neural networks to recognize and exploit specific statistical properties that reveal weaknesses in ciphers. The authors train networks by providing them with data that links these statistical features to the correct encryption key. The network then learns to generalize this relationship, enabling it to predict the key or estimate its likelihood from a given ciphertext.

  • Caesar Cipher: A neural network is trained to predict the Caesar cipher key by taking the relative frequencies of ciphertext letters as input. This leverages the fact that a Caesar cipher simply shifts the frequency distribution of the plaintext.
  • Vigenère Cipher: The authors adapt the Caesar cipher classifier. They break the Vigenère ciphertext into subtexts based on potential key lengths and apply the Caesar classifier to each subtext. When the classifier consistently identifies a key for all subtexts, it suggests the correct key length and the Vigenère key.
  • Substitution Cipher: For substitution ciphers, which have a vast key space, the authors employ a different strategy. They train a neural network to distinguish between English plaintexts and ciphertexts encrypted with random substitution keys. This network learns to assign a "goodness" score to a potential decryption, indicating how close it is to natural English. An attack strategy then uses this score to iteratively improve a candidate key by swapping letters, aiming to maximize the goodness score.

Datasets

  • British National Corpus: Used for obtaining statistical properties of English text (letter and 3-gram frequencies).
  • Custom Datasets: The authors generated datasets by encrypting plaintexts (extracted from the British National Corpus) with random keys for each cipher type. For instance, they used 5097 ciphertexts of varying lengths (30, 50, 100, 200 words) for the Caesar cipher, and tested the substitution cipher attack on 2500 texts of 200 words.

Key Insights and Ideas

  • Automating Weakness Exploitation: The most significant insight is that neural networks can be trained to automate the exploitation of known cipher weaknesses, acting as a powerful tool for cryptanalysts.
  • Ciphertext-Only Attacks: The paper demonstrates that this approach can lead to effective ciphertext-only attacks, a more challenging scenario than known-plaintext or chosen-plaintext attacks.
  • Leveraging Statistical Properties: The success hinges on identifying and feeding the neural network the relevant statistical features that are distorted by the cipher's weakness (e.g., frequency shifts in Caesar, uniform distribution in Vigenère, preserved but permuted frequencies in substitution).
  • First Neural Network Attack on Substitution Ciphers: This work presents a novel contribution by developing the first neural network-based attack specifically for substitution ciphers, overcoming the challenge of their large key space.
  • Efficiency: The trained neural networks are remarkably fast, with attacks often completing in seconds, even for complex classical ciphers.

Key Results

  • Caesar Cipher: Achieved 100% accuracy in predicting the Caesar cipher key on an independent dataset, with attacks taking almost instantaneous time after training. The accuracy was maintained for texts as short as 30 words.
  • Vigenère Cipher: The attack, leveraging the Caesar classifier, was very efficient. For texts of 400 words, it had about 1% spurious keys, while for 1000-word texts, it was highly accurate with no spurious keys. Cracking was also nearly instantaneous.
  • Substitution Cipher: The attack strategy successfully recovered the correct key in about 58% of cases for 200-word texts. In 93% of cases, the recovered key had at most 2 wrong mappings, easily correctable manually. Interestingly, in about 70% of successful attacks, the correct key was found within the first iteration. The entire attack process for a ciphertext took approximately 3 seconds on average.

Limitations and Future Work

  • Classical Ciphers Focus: The current work is limited to classical ciphers. The authors acknowledge that more sophisticated networks might be necessary for modern, complex ciphers.
  • Generalizability: While promising, the general applicability of this approach to a wider range of ciphers needs further investigation.
  • Future Work: The authors plan to explore the general applicability of their approach by identifying classes of ciphers that can be analyzed using similar techniques. They intend to target already broken ciphers (e.g., in the automotive industry) and reduced-round standard ciphers.

Summary updated

BibTeX
@inproceedings{focardi2018neural,
  author = {Riccardo Focardi and Flaminia L. Luccio},
  title = {{Neural Cryptanalysis of Classical Ciphers}},
  booktitle = {ICTCS},
  year = {2018},
}
Figure