I recently learned the Japanese Foreign Ministry adopted Bolton's Telegraph Code (1871) in 1880. It was about the time when major cities in Japan came to be connected by telegraphy.
I added this note to "Nonsecret Code: An Overview of Early Telegraph Codes" and "日本の電信暗号".
According to John McVey's website, a copy of the codebook is in the British Library.
21/07/2024
Three Unknown Chinese Codebooks (ca. 1905)
I came across a reference to three Chinese codebooks used around 1905: 「密電秘鑰」（Midian Miyao）、「中国密電簡明表」（Zhongguo Mi dian Jianming Biao）、「行軍電報」（Xingjun Dianbao）. Their format seems to be similar to that of known codebooks. I added a note on this in "中国の暗号：1871-1945" and its abridged version in English: "Chinese Cryptography: 1871-1945".
19/07/2024
Ciphertext-only Attack on Classical Ciphers by Using AI
Even Chat GPT-4 could not tell me about papers about codebreaking with AI, but once I came across one paper (see the previous post), googling with its title returns a number of relevant papers. (That is, my question did not include relevant key words.)
My interest is in a ciphertext-only attack on homophonic ciphers or syllabic ciphers, which are the most common ciphers in the early modern period. Although I have not found a work on neural network approach on these, two (also cited by Closa (2023) mentioned in the previous post) are interesting in dealing with ciphertext-only attack on the Caesar (shift) cipher, the Vigenere cipher, and (monoalphabetic) substitution cipher.
Focardi et al. (2018) claims to be the first to provide a ciphertext-only attack on substitution ciphers based on neural networks (Abstract). It assumes a weakness of the cipher is given and the neural network exploits it.
(i) In the case of the Caesar cipher (a.k.a. the shift cipher), the key is a single number (e.g., up to 26). The frequencies of symbols generally reflects the frequency of letters (e.g. of English-language text). Thus, a neural network is trained to predict a key from the frequencies. The trained neural network can "recognize" the key without actually trying shifts to see whether readable text is obtained.
(ii) For the Vigenere cipher, a key length (m) is assumed and the Caesar classifier is applied to subtexts composed of symbols taken from the ciphertext at distance m. This is like a conventional method by using brute force but employs the Caesar classifier from (i).
(iii) For general (monoalphabetic) substitution ciphers, an overall framework is similar to conventional hill climbing. Starting from a random key, a "goodness" value is computed. After changing the key a little bit, the "goodness" value is computed again. If it has improved, the change is kept; otherwise the change is discarded. By iteration, the key is improved step by step. Again, the authors' method does not need to actually try intermediate keys to see whether a plausible plaintext is obtained. Instead, a neural network is trained with 3-grams of both plaintexts and ciphertexts. Although they "have no guratantees that this will provide a good classifier which is able to tell 'how' similar is a text to a plaintext and, consequently, how good is a key, but experimental results have confirmed that the method is effective." It will be interesting to see whether this works for homophonic ciphers or syllable ciphers.
Ahmadzadeh et al. (2021) seems to achieve what I thought impossible: training with plaintext/ciphertext pairs (Table 4) allows deciphering a ciphertext with an unknown key. The decryption function is learned "regardless of the cipher complexity or key length" (IV D). While experiments were done with Caesar, Vigenere, and (monoalphabetic) substitution, the authors consider their approach "has the potential to crack modern ciphers" (IV H).
To learn the decryption function from the plaintext/ciphertext pairs, they used an attention-based LSTM encoder-decoder model (Fig. 3). To quickly recall the terminology, a class of neural networks that can have "memory" is a recurrent neural network (RNN). A class of RNN that solves its problem (vanishing gradients in deep networks: "A small gradient value does not contribute very much to learning") is LSTM. A problem with LSTM ("a lengthy input sequence causes LSTM to forget important information along the sequence") is solved by an attention mechanism, which allows "dynamically highlighting important features of the input data" (III A).
As a prerequisite, they assume the ciphertext has "punctuation" and can be readily parsed into words (Fig. 4). It will be interesting to see whether their work can be generalized to ciphertext without punctuation.
References:
Riccardo Focardi and Flaminia L. Luccio (2018), "Neural Cryptanalysis of Classical Ciphers", Italian Conference on Theoretical Computer Science (ICTCS 2018), Urbino, Italy, September 18-20, 2018 (CEUR-WS.org).
Ezat Ahmadzadeh, Hyunil Kim, Ongee Jeong, and Inkyu Moon (2021), "A Novel Dynamic Attack on Classical Ciphers Using an Attention-Based LSTM Encoder-Decoder Model", IEEE Access, 2021, vol.9, pp.60960-60970, DOI: 10.1109,ACCESS.2021.3074268 (IEEE Xplore)
My interest is in a ciphertext-only attack on homophonic ciphers or syllabic ciphers, which are the most common ciphers in the early modern period. Although I have not found a work on neural network approach on these, two (also cited by Closa (2023) mentioned in the previous post) are interesting in dealing with ciphertext-only attack on the Caesar (shift) cipher, the Vigenere cipher, and (monoalphabetic) substitution cipher.
Focardi et al. (2018) claims to be the first to provide a ciphertext-only attack on substitution ciphers based on neural networks (Abstract). It assumes a weakness of the cipher is given and the neural network exploits it.
(i) In the case of the Caesar cipher (a.k.a. the shift cipher), the key is a single number (e.g., up to 26). The frequencies of symbols generally reflects the frequency of letters (e.g. of English-language text). Thus, a neural network is trained to predict a key from the frequencies. The trained neural network can "recognize" the key without actually trying shifts to see whether readable text is obtained.
(ii) For the Vigenere cipher, a key length (m) is assumed and the Caesar classifier is applied to subtexts composed of symbols taken from the ciphertext at distance m. This is like a conventional method by using brute force but employs the Caesar classifier from (i).
(iii) For general (monoalphabetic) substitution ciphers, an overall framework is similar to conventional hill climbing. Starting from a random key, a "goodness" value is computed. After changing the key a little bit, the "goodness" value is computed again. If it has improved, the change is kept; otherwise the change is discarded. By iteration, the key is improved step by step. Again, the authors' method does not need to actually try intermediate keys to see whether a plausible plaintext is obtained. Instead, a neural network is trained with 3-grams of both plaintexts and ciphertexts. Although they "have no guratantees that this will provide a good classifier which is able to tell 'how' similar is a text to a plaintext and, consequently, how good is a key, but experimental results have confirmed that the method is effective." It will be interesting to see whether this works for homophonic ciphers or syllable ciphers.
Ahmadzadeh et al. (2021) seems to achieve what I thought impossible: training with plaintext/ciphertext pairs (Table 4) allows deciphering a ciphertext with an unknown key. The decryption function is learned "regardless of the cipher complexity or key length" (IV D). While experiments were done with Caesar, Vigenere, and (monoalphabetic) substitution, the authors consider their approach "has the potential to crack modern ciphers" (IV H).
To learn the decryption function from the plaintext/ciphertext pairs, they used an attention-based LSTM encoder-decoder model (Fig. 3). To quickly recall the terminology, a class of neural networks that can have "memory" is a recurrent neural network (RNN). A class of RNN that solves its problem (vanishing gradients in deep networks: "A small gradient value does not contribute very much to learning") is LSTM. A problem with LSTM ("a lengthy input sequence causes LSTM to forget important information along the sequence") is solved by an attention mechanism, which allows "dynamically highlighting important features of the input data" (III A).
As a prerequisite, they assume the ciphertext has "punctuation" and can be readily parsed into words (Fig. 4). It will be interesting to see whether their work can be generalized to ciphertext without punctuation.
References:
Riccardo Focardi and Flaminia L. Luccio (2018), "Neural Cryptanalysis of Classical Ciphers", Italian Conference on Theoretical Computer Science (ICTCS 2018), Urbino, Italy, September 18-20, 2018 (CEUR-WS.org).
Ezat Ahmadzadeh, Hyunil Kim, Ongee Jeong, and Inkyu Moon (2021), "A Novel Dynamic Attack on Classical Ciphers Using an Attention-Based LSTM Encoder-Decoder Model", IEEE Access, 2021, vol.9, pp.60960-60970, DOI: 10.1109,ACCESS.2021.3074268 (IEEE Xplore)
13/07/2024
Codebreaking with AI
In 2016, the public was made aware of how AI (artificial intelligence) dramatically improved the quality of machine translation (Google's release in Japanese). It naturally raises a question: is codebreaking possible with AI?
For a long time, I couldn't find a positive answer to this question. Although my search was half-hearted, even Copilot with Chat-GPT-4 did not give a relevant answer to my question: "Are there papers about codebreaking by using AI?" Then, I noticed a poster abstract in HistoCrypt 2024: Oriol Closa, "Polyalphabetic cipher decryption function learning with LSTM networks", which seems to be based on her master thesis, Closa Oriol (2023), "LSTM-attack on polyalphabetic cyphers with known plaintext: Case study on the Hagelin C-38 and Siemens and Halske T52" (KTH). It teaches that "the application of Machine Learning to extract key information from intercepts is not a well researched area yet." (Abstract) and there are even "many authoritative opinions within the field" against utility of machine learning in classical cryptography (p.57).
Machine "learns" by finding a best parameter set for a model, which is like a very complex filter that receives an input and produces an output. In an example of machine translation, the input is a sequence of words in English and the output is a sequence of words in Japanese. In order to train a machine in this example, bilingual corpus of corresponding texts in the two languages is fed to the computer, whereby the computer learns an English-Japanese translation model. Given a new text in English, the trained computer can apply the model (filter) on the input to produce a text in Japanese as an output.
By analogy, given a corpus of ciphertext/plaintext pairs, AI may learn to decipher a new ciphertext into a plaintext. However, it should be limited to the case where the new ciphertext is based on the same cipher key used for training -- that's what I thought. But the thesis taught me machine learning can do more than that. (The key is included in the training data (p.39).)
Remember that the output of a trained model need not be similar to the input. For example, when the input is a text in English, the output may be some classification or labelling of the text rather than a text in another language. In Oriol (2023), in my understanding, the input is ciphertext, a crib (known plaintext, presumably corresponding to the ciphertext), and a null key (a placeholder in the input vector), and the output is plaintext (which should match the crib and is included only for analysis) and the extracted key (p.34). Thus, this seems to receive a maching ciphertext/plaintext pair to produce its key ("extract the external key given a combination of plaintext and ciphertext without the use of the internal setting" p.51).
The thesis deals with four ciphers: Vigenere, Playfair, Hagelin C-38, and Siemens and Halske T52 with LSTM networks (a kind of neural network). Main differences among them are the decipher function reflecting the cipher scheme (I guess this means the cipher algorithm is known and only the key is to be found out), the crib length (e.g., 15, 25), and the size of the hidden layer (e.g., 256, 2048) (p.33, 40). The author says LSTM networks can extract key information given a crib (in my understanding, this is a matching plaintext/ciphertext pair) for Vigenere, Hagelin C-38, and Siemens and Halske T52, but not Playfair.
(16 July 2024) Ajeet Singh, Kaushik Bhargav Sivangi, and Appala Naidu Tentu (2024), "Machine Learning and Cryptanalysis: An In-Depth Exploration of Current Practices and Future Potential", Journal of Computing Theories and Applications (JCTA, DOI: https://doi.org/10.62411/jcta.9851), Vol. 1 No. 3 (2024) also says "the integration of machine learning, and specifically deep learning, into cryptanalysis has been relatively unexplored."
For a long time, I couldn't find a positive answer to this question. Although my search was half-hearted, even Copilot with Chat-GPT-4 did not give a relevant answer to my question: "Are there papers about codebreaking by using AI?" Then, I noticed a poster abstract in HistoCrypt 2024: Oriol Closa, "Polyalphabetic cipher decryption function learning with LSTM networks", which seems to be based on her master thesis, Closa Oriol (2023), "LSTM-attack on polyalphabetic cyphers with known plaintext: Case study on the Hagelin C-38 and Siemens and Halske T52" (KTH). It teaches that "the application of Machine Learning to extract key information from intercepts is not a well researched area yet." (Abstract) and there are even "many authoritative opinions within the field" against utility of machine learning in classical cryptography (p.57).
Machine "learns" by finding a best parameter set for a model, which is like a very complex filter that receives an input and produces an output. In an example of machine translation, the input is a sequence of words in English and the output is a sequence of words in Japanese. In order to train a machine in this example, bilingual corpus of corresponding texts in the two languages is fed to the computer, whereby the computer learns an English-Japanese translation model. Given a new text in English, the trained computer can apply the model (filter) on the input to produce a text in Japanese as an output.
By analogy, given a corpus of ciphertext/plaintext pairs, AI may learn to decipher a new ciphertext into a plaintext. However, it should be limited to the case where the new ciphertext is based on the same cipher key used for training -- that's what I thought. But the thesis taught me machine learning can do more than that. (The key is included in the training data (p.39).)
Remember that the output of a trained model need not be similar to the input. For example, when the input is a text in English, the output may be some classification or labelling of the text rather than a text in another language. In Oriol (2023), in my understanding, the input is ciphertext, a crib (known plaintext, presumably corresponding to the ciphertext), and a null key (a placeholder in the input vector), and the output is plaintext (which should match the crib and is included only for analysis) and the extracted key (p.34). Thus, this seems to receive a maching ciphertext/plaintext pair to produce its key ("extract the external key given a combination of plaintext and ciphertext without the use of the internal setting" p.51).
The thesis deals with four ciphers: Vigenere, Playfair, Hagelin C-38, and Siemens and Halske T52 with LSTM networks (a kind of neural network). Main differences among them are the decipher function reflecting the cipher scheme (I guess this means the cipher algorithm is known and only the key is to be found out), the crib length (e.g., 15, 25), and the size of the hidden layer (e.g., 256, 2048) (p.33, 40). The author says LSTM networks can extract key information given a crib (in my understanding, this is a matching plaintext/ciphertext pair) for Vigenere, Hagelin C-38, and Siemens and Halske T52, but not Playfair.
(16 July 2024) Ajeet Singh, Kaushik Bhargav Sivangi, and Appala Naidu Tentu (2024), "Machine Learning and Cryptanalysis: An In-Depth Exploration of Current Practices and Future Potential", Journal of Computing Theories and Applications (JCTA, DOI: https://doi.org/10.62411/jcta.9851), Vol. 1 No. 3 (2024) also says "the integration of machine learning, and specifically deep learning, into cryptanalysis has been relatively unexplored."
12/07/2024
George Lasry's Paper on Syllabic Cipher Released
Last year, I reported George Lasry's solution of syllabic ciphers. Syllabic ciphers are ciphers with many symbols for syllables as well as those for single letters.
Details of his algorithm are now published in George Lasry, "Deciphering Historical Syllabic Ciphers" (HistoCrypt 2024).
One might be tempted to say extension of a homophonic solver to a syllabic solver only involves enlarging the search space for, say, 25 letters of the alphabet by adding variables for 25*25=625 syllables. However, since last year, I've been wondering how to design a scoring function for intermediate decipherments. In typical homophonic solvers, 4-grams or 5-grams are used in computing a score. For example, if an intermediate decipherment abounds in plausible 5-grams (e.g., "ISION", "EMENT", "ETLES" for the French language), it receives a high score. But when symbols represent syllables such as "SI", "ON", "EM" "EN", just random assignment of these syllables might result in a relatively high score.
The answer to my year-long question turned out to be very simple. The scoring function is based on 4-grams, composed of not only single letters but also syllables. Thus, a 4-gram may be "E-S-T-A" or "CO-N-TRO-L" (p.177).
While it is easy to say this, it is quite another to implement it, because this involves re-constructing the whole language model. A language model represents frequency characteristics of all possible 4-grams (or 5-grams etc.) in a large corpus of text in the language in question. For a language model for conventional homophonic solvers, creating a language model amounted to simply counting letter groups. For a syllabic solver, it is necessary to first break text in the corpus into syllables, but there can be many ways to split a word. For example, the word ESTABLISHED may be broken into E-S-TA-B-LI-S-HE-D (using only CV syllables), ES-TA-B-LI-S-H-ED (using CV and VC), E-STA-BLI-S-HE-D (allowing also CCV), or the like (p.174). Naturally, success of the algorithm depends on the choice of the set of syllables used and the decomposition scheme, which required "extensive trial-and-error to fine tune" (p.176, 179).
And of course, the more than ten-fold increase in the number of variables (which more than exponentially expands the search space) means "extensive computing power" is required. George used a 64-core Windows 10 Pro PC with 256 Gbytes of RAM memory (p.176), whereas one commercial PC I see on the web has 4-core and up to 3.40 GB of memory.
His groundbreaking new scheme has proven its merits by breaking ten ciphertexts (including five with known keys).
Details of his algorithm are now published in George Lasry, "Deciphering Historical Syllabic Ciphers" (HistoCrypt 2024).
One might be tempted to say extension of a homophonic solver to a syllabic solver only involves enlarging the search space for, say, 25 letters of the alphabet by adding variables for 25*25=625 syllables. However, since last year, I've been wondering how to design a scoring function for intermediate decipherments. In typical homophonic solvers, 4-grams or 5-grams are used in computing a score. For example, if an intermediate decipherment abounds in plausible 5-grams (e.g., "ISION", "EMENT", "ETLES" for the French language), it receives a high score. But when symbols represent syllables such as "SI", "ON", "EM" "EN", just random assignment of these syllables might result in a relatively high score.
The answer to my year-long question turned out to be very simple. The scoring function is based on 4-grams, composed of not only single letters but also syllables. Thus, a 4-gram may be "E-S-T-A" or "CO-N-TRO-L" (p.177).
While it is easy to say this, it is quite another to implement it, because this involves re-constructing the whole language model. A language model represents frequency characteristics of all possible 4-grams (or 5-grams etc.) in a large corpus of text in the language in question. For a language model for conventional homophonic solvers, creating a language model amounted to simply counting letter groups. For a syllabic solver, it is necessary to first break text in the corpus into syllables, but there can be many ways to split a word. For example, the word ESTABLISHED may be broken into E-S-TA-B-LI-S-HE-D (using only CV syllables), ES-TA-B-LI-S-H-ED (using CV and VC), E-STA-BLI-S-HE-D (allowing also CCV), or the like (p.174). Naturally, success of the algorithm depends on the choice of the set of syllables used and the decomposition scheme, which required "extensive trial-and-error to fine tune" (p.176, 179).
And of course, the more than ten-fold increase in the number of variables (which more than exponentially expands the search space) means "extensive computing power" is required. George used a 64-core Windows 10 Pro PC with 256 Gbytes of RAM memory (p.176), whereas one commercial PC I see on the web has 4-core and up to 3.40 GB of memory.
His groundbreaking new scheme has proven its merits by breaking ten ciphertexts (including five with known keys).
04/07/2024
Reconstructed Ciphers related to Mary, Queen of Scots, preserved in Scottish Catholic Archives (SCA)
Fourteen ciphers used in the correspondence of James Beaton, Archbishop of Glasgow, and reconstructed by Bishop Kyle in the nineteenth century are preserved in the Scottish Catholic Archives (SCA). I now added mention of these in "Ciphers of Mary, Queen of Scots".
03/07/2024
Early French Figure Ciphers
An early specimen of a French figure cipher (digit cipher, numerical cipher) is discussed in Camille Desenclos and George Lasry, "An early French digit cipher: deciphering a letter from the King of France to the Duke of Nevers (1592)" (HistoCrypt 2024).
It is used in a letter from Henry IV to Duke of Nevers, 12 September 1592 (BnF fr.3620, f.70-71)(p.47). The cipher employs variable-length figures written continuously, but the authors could parse the ciphertext into cipher symbols by assuming three-digit figures always start with "1" (p.48; see also my articles from 2017-2019 and 2018-2019). After the key was reconstructed, the authors found the original cipher table among Nevers' collection of keys in BnF fr.3995, fol.140 (p.49).
Many cipher letters between Henry IV and the Duke of Nevers have been known but they used conventional symbol ciphers in BnF fr.3995, fol.67 rather than numerical ciphers (p.49-50, 46; see also my article). The authors point out that the 1592 letter in question is countersigned by Martin Ruzé de Beaulieu, while all the other letters in cipher from the king to the duke from 1591 to 1594 are counstersigned by Louis Potier de Gesvres (p.49-50). The 1592-cipher was also used in letters in 1591 to Henry IV (two from Duke of Biron, one from sieur de Guitry, baron de Salagnac, and marquis de Pisani) (p.51).
The papers is also valuable in citing many examples of exclusively digit ciphers in the 1580s/1590s (p.50; see also other figure ciphers mentioned in my articles: Henry III etc., Buzenval).
(5 July 2024) I now remembered another French ciphertext in variable-length figures (1, 2, or 3 digits) written continuously (ca.1620?) is discussed in here.
(24-25 August 2024) The paper points out at least 23 letters sent to the Duke of Nevers in 1589-1591 use only digits (p.50). To this list may be added another ciphertext in digits continuously written without break (since it is not deciphered, we cannot tell whether it employs variable-length symbols). The ciphertext is in an Italian letter from Lodovico Birago to the Duke of Nevers, 13 November 1571 (BnF fr.3251, f.119), which I mentioned here some years ago.
It is used in a letter from Henry IV to Duke of Nevers, 12 September 1592 (BnF fr.3620, f.70-71)(p.47). The cipher employs variable-length figures written continuously, but the authors could parse the ciphertext into cipher symbols by assuming three-digit figures always start with "1" (p.48; see also my articles from 2017-2019 and 2018-2019). After the key was reconstructed, the authors found the original cipher table among Nevers' collection of keys in BnF fr.3995, fol.140 (p.49).
Many cipher letters between Henry IV and the Duke of Nevers have been known but they used conventional symbol ciphers in BnF fr.3995, fol.67 rather than numerical ciphers (p.49-50, 46; see also my article). The authors point out that the 1592 letter in question is countersigned by Martin Ruzé de Beaulieu, while all the other letters in cipher from the king to the duke from 1591 to 1594 are counstersigned by Louis Potier de Gesvres (p.49-50). The 1592-cipher was also used in letters in 1591 to Henry IV (two from Duke of Biron, one from sieur de Guitry, baron de Salagnac, and marquis de Pisani) (p.51).
The papers is also valuable in citing many examples of exclusively digit ciphers in the 1580s/1590s (p.50; see also other figure ciphers mentioned in my articles: Henry III etc., Buzenval).
(5 July 2024) I now remembered another French ciphertext in variable-length figures (1, 2, or 3 digits) written continuously (ca.1620?) is discussed in here.
(24-25 August 2024) The paper points out at least 23 letters sent to the Duke of Nevers in 1589-1591 use only digits (p.50). To this list may be added another ciphertext in digits continuously written without break (since it is not deciphered, we cannot tell whether it employs variable-length symbols). The ciphertext is in an Italian letter from Lodovico Birago to the Duke of Nevers, 13 November 1571 (BnF fr.3251, f.119), which I mentioned here some years ago.
01/07/2024
Cross-Cipher Errors - A New Modality of Communication Analysis
Errors in ciphertext may be caused by another cipher concurrently in use. The phenomenon, called cross-cipher errors, is discussed in our new coauthored paper:
Norbert Biermann, Satoshi Tomokiyo, and George Lasry, "What Encryption Errors Can Reveal: Cross-Cipher Errors in Mary Queen of Scots' Letters" (HistoCrypt2024).
When a ciphertext includes a significant amount of systematic errors, it may be worthwhile to look for a cipher causing the errors. It can reveal that correspondence in that other cipher was going on at the time, even if no letters are extant. This can be a new modality of traffic analysis.
Subscribe to:
Posts (Atom)