5
$\begingroup$

Chaocipher was invented by John F. Byrne in 1919. The algorithm was recently revealed – see Moshe Rubin's Chaocipher Revealed, the Algorithm (PDF).

While a known plaintext attack successfully finds the keys, nobody has been able to put forward a general solution to this cipher. Is that possible?

$\endgroup$
  • 5
    $\begingroup$ Any cipher than suffers key-recovery under known plaintext is horrifically weak under modern requirements. Nowadays, we tend to require that an attacker cannot even recognise the ciphertext (compared to random data), even if they can choose the plaintext to encrypt and even ask for the decryption of some messages of their own choice $\endgroup$ – Cryptographeur Apr 8 '14 at 9:40
  • 1
    $\begingroup$ Ciphertext-only attacks virtually always assume some a priori distribution of plaintexts; otherwise all keys are equally probable. $\endgroup$ – Dmitry Khovratovich Apr 8 '14 at 10:20
  • $\begingroup$ Thank you both form your responses. I have a follow-up for figlesquidge please. Given that the cipher text from Chaocipher shows some deviation from randomness in one respect (which it does!) how then does the cryptanalyst go about solving the cipher? He knows the algorithm, but has no idea of the two 26-character keys. $\endgroup$ – user2256790 Apr 8 '14 at 13:26
  • $\begingroup$ Because the key is relatively large [ $2\log_2(26!)>176\text{ bits}$ ], and since the cipher is not trivially bad, a ciphertext-only attack can only be carried with significant amount of ciphertext corresponding to redundant plaintext. If we consider there is 2 bit/letter of exploitable redundancy in English text, and IF the cipher was perfect, we would need about 90-letter ciphertext to have any hope of solving it. Are there large Chaocipher challenges around? (or course it is easy to make some). $\endgroup$ – fgrieu Apr 9 '14 at 8:24
  • $\begingroup$ There are some lengthy Chaocipher ciphertexts here: mountainvistasoft.com/chaocipher/Chaocipher-ASCII-versions.htm I (and several others) have broken some of these with a known plaintext attack. But nobody (to my knowledge) has developed a method to solve using a ciphertext attack. Such a method would be of great interest. $\endgroup$ – user2256790 Apr 27 '14 at 15:55
6
$\begingroup$

While a known plaintext attack successfully finds the keys, nobody has been able to put forward a general solution to this cipher. Is that possible?

You really have to go back in time to learn that ChaoCipher has been subject to some cryptanalysis before the description of the algorithm/device was published. As an example: Here’s one of the oldest papers I found related to the cryptanalysis of the ChaoCipher which was first published in 2003… long before the algorithm was published in 2010 and long before the cipher was subject to a complete break.

If you do a bit of research, you’ll find a few more papers. Most cryptanalytic looks at ChaoCipher have shown ample weaknesses in the distribution, producing anomalies which could be exploited.

Having used the algorithm description to code a C version, I quickly discovered it works somewhat like a substitution cipher that incorporates a primitive version of an which scrambles the S-box. Nothing you would want to use in times of modern cryptography. It’s more like a most-primitive rotor machine.

Anyway… getting back to the core of your question: is it possible that no one has created a general “this breaks it from every side” solution?

Sure! One reason can be found in the fact that a counts as a complete break (and in this case, a practically feasible one too). Finding additional attack vectors can be fun as a hobby, or it may be something you might want to check on while writing a thesis about ChaoCipher… but it’s not that interesting for most cryptanalysts to dive in deeper when a cryptographic algorithm already was subject to a complete break. Instead, cryptanalysts will be more interested in finding weaknesses in more modern (currently used) ciphers. Compared to modern cryptography, ChaoCipher can’t hold up.

On the other hand, there are ample websites that talk about its internals… leaving the chance that one day, someone may find ways to break it from all sides – after investing enough time and efforts.

| improve this answer | |
$\endgroup$
  • $\begingroup$ To be historically accurate, Jeff Hill's paper entitled "Chaocipher: Analysis and Models" was written in 2003, but was not made public in any forum until 2009. When The Chaocipher Clearing House (www.chaocipher.com) was created in early 2009, the maintainer (Moshe Rubin) tracked down former Chaocipher researchers, among them Jeff Hill. Rubin was able to convinced Hill to publish his important paper. Although the models presented in the paper were analytically proven not to be the true Chaocipher model, it provided valuable direction to the ongoing research. $\endgroup$ – Moshe Rubin May 21 '19 at 8:09
3
$\begingroup$

In 2013, I visited the National Cryptologic Museum and researched/photographed the donated materials on the Chaocipher from the Byrne family. As it pertains to your question regarding the security of the cipher, it is true that while the original algorithm has been now been known for several years, to date no known cipher-text only decryption has yet been accomplished or announced.

One discovery I made in the museum was an early draft of Kruh and Deavour's 1990 Cryptologia challenge article on the Chaocipher. While their published "Exhibit 5" in Cryptologia also went unsolved for 23 years (until, during my visit, I found their solution), this earlier draft (now christened "Exhibit 6") still has not been solved and poses a true challenge for the modern cryptanalyst looking to test their skills against the Chaocipher.

In Exhibit 6, you will find 50 short lines enciphered 'in depth'; the actual encipherment algorithm is not Byrne's classic alogorithm, nor has it proven to be the advanced variant that K&D used for their published "Exhibit 5". No plaintext is provided (unlike Byrne's own Exhibits 1-4), no source for the plaintext has been given (unlike K&D's Exhibit 5). The cryptanalyst who might solve this challenge (published in Cryptologia 2014, Vol 38 Issue 1) would be the first on record to have 'cracked' a Chaocipher encipherment.

A cursory overview of Exhibit 6 may be found here: http://www.chaocipher.com/chaocipher-024.htm. Additional information on the various classic and advanced algorithms noted may also be found at www.chaocipher.com.

After 5 years of Chaocipher research, I believe the cipher remains far stronger than many would believe. Relative to modern computer-based ciphers, it is indeed 'simple'... but 'simple' is relative, and until proven otherwise - as demonstrated by a full solution for a ciphertext only encipherment - it continues to stand as an early example of what, today, we would call 'dynamic substitution', its incredible number of left/right alphabet permutations of 26!x26! defying both modern-day brute-force attack capabilities and, so far, any other decryption efforts.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Jeff, you were a valuable member of the Chaocipher research group back in the heady pre-disclosure days :-) It was your finding of Exhibit 6 that spurred George Lasry to break it. The readers can find a complete description of Lasry's cryptanalysis of Exhibit 6 in his Ph.D. thesis available for free online in "A Methodology for the Cryptanalysis of Classical Ciphers with Search Metaheuristics" (uni-kassel.de/upress/online/OpenAccess/…, chapter 8). $\endgroup$ – Moshe Rubin May 21 '19 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.