Announcing the "Chaocipher Clearing House"
mosherubin
House", a web site dedicated to tracking cryptanalytic work related to
John F. Byrne's Chaocipher. The web site's URL is:
http://www.mountainvistasoft.com/chaocipher
The site, meant to be an active public Chaocipher clearing house,
currently offers the following:
* A PDF document containing the entire chapter 21 of Byrne's "Silent
Years". Here you can read the complete challenge presented by Byrne
in his book.
* Carefully checked ASCII files containing all Chaocipher exhibits,
allowing you to analyze the cipher on your own.
* A summary of Chaocipher research to date found in the open
literature.
* The first installment of research I've done on the Chaocipher.
The goal of this site to spur the non-governmental cryptologic
community into finally solving this 56-year old, long-overdue
challenge once and for all. Please feel free to post any comments,
insights, or questions to this forum, or to send me an e-mail at
mos...@mountainvistasoft.com for inclusion on the site (with due
credit).
Historic Background
In 1918 John F. Byrne, a lifelong friend of James Joyce, conceived a
cryptographic invention he called "Chaocipher". Over the next forty
years, Byrne tried to interest numerous agencies in his invention,
including the US State Department, the Signal Corps, the US Navy, Bell
Labs, and others. To his disappointment no one took him up on the
offer.
In 1953 Byrne published his autobiography entitled "Silent Years: An
Autobiography with Memoirs of James Joyce and Our Ireland". It told
much about his relationship with Joyce, but the real reason he wrote
it was to publicize "Chaocipher" to the world at large. The last
chapter comprises a full one eighth of the book. In it Byrne tells
the whole story of how he unsuccessfully tried to market his system.
The last chapter comprises four exhibits with corresponding plaintext
and ciphertext, totaling more than 15,000 plaintext/ciphertext pairs.
The challenge is to decipher several lines in exhibit 4.
The cipher has resisted all efforts to discover the underlying
algorithm. This is amazing given the size of the cribs Byrne provides
in his book.
----------------------------------------------------------------
Moshe Rubin
Mountain Vista Software
Jerusalem, Israel
http://www.mountainvistasoft.com
e-mail: mos...@mountainvistasoft.com
mosherubin
Thank you for your reply and for the list of links to "security by
obscurity" posts. I agree with you that "security by obscurity" is
unacceptable and that Byrne should have revealed the underlying
system, certainly after he extolled Chaocipher's security to the
hilt. I address this exact point in one of my pages (http://
www.mountainvistasoft.com/chaocipher/chaocipher-001.htm):
[quote] =============================
A Thought Before Starting
By and large, John F. Byrne's Chaocipher challenge has been curiously
ignored by the cryptanalytic community. It would be expected that a
system that caught the attention of knowledgeable cryptologists like
Colonel Parker Hitt, William F. Friendman, Major Frank Moorman, Bell
Labs, and various representatives of the State, War, and Navy
departments would catch the fancy of amateur cryptanalysts.
One of the reasons given for not tackling Chaocipher is that, by not
revealing the underlying system, Byrne violated the fundamental
assumption of military cryptography: that the enemy knows the general
system. Continuing this reasoning, it is a waste of time to work on a
system which, if revealed, would probably be easy to solve.
I understand this sentiment, but have several comments to make:
* Several of the professionals mentioned above are quoted by Byrne
as being highly favorable of his system. It would probably not be
trivial to solve even if the underlying system were known.
* There are very few opportunities available today to duplicate
the incredible US effort of breaking the Japanese Purple cipher with
no a priori knowledge. Are we up to a similar challenge?
Although Byrne should have divulged his underlying system, the
challenge is a fine one, well worth the effort to "prove one's
mettle".
[/quote] ================================
Many of us have had experiences similar to the following:
- A friend challenges you with a cipher of his/her making, consisting
of a limited number of characters, no crib
- You eventually solve it (e.g., it turns out to be some inconvenient
simple substitution)
- Undeterred, your friend insists on adding another unnatural
complication, making the system impractical to use
- You again succeed in solving it
- Your friend adds "just one more" unnatural complication, making the
system unusable
- Repeat ad infinitum
As unhappy as we may be with Byrne's behavior, his system seems to be
relatively "simple". Quoting Greg Mellen:
"[Parker] Hitt calls the machine 'undoubtedly a most ingenious and
effective device' and advises Byrne that he can 'safely go ahead with
confidence in the practical indecipherability of the product'. The
ordinary wisdom of ignoring the inventors of unbreakable ciphers I
think does not apply in this case".
Quoting from Deavours and Kruh [1990]:
"... Byrne [Jr.] showed Deavours and Kruh how the Chaocipher worked.
They were quickly impressed by its simplicity, ease of operation and
security."
What gets me is that Byrne provides over 15,000 pt/ct pairs in open
cribs. Given that he invented the principle 90 years ago, given our
superior knowledge of cryptanalytical techniques, and given the
availability of personal computers, why aren't we able to deduce the
system?
You must agree that Byrne's challenge differs from other "security by
obscurity" inventors. Such inventors typically provide ciphertext
message with no plaintext cribs. What other obscure (classical
cryptographic, in contrast with modern public-key) system has provided
such large pt/ct cribs? Byrne's system might not win the "security by
transparency" award, but it does not fit the typical "security by
obscurity" model, either.
Are we using Kerchoff's Principle to avoid stepping up to the plate
and rising to the occasion? Are we afraid of failing?
Moshe
On Feb 20, 3:30 am, Guy Macon <http://www.GuyMacon.com/> wrote:
> mosherubin wrote:
> >The cipher has resisted all efforts to discover the underlying
> >algorithm.
>
> Few if any serious cryptographers will put any effort into discovering
> the algorithm because the general consensus follows Kerckhoffs' Principle,
> Shannon's Maxim, and Raymond's Reformulation -- that a cryptosystem
> should be designed to be secure if everything (including the algorithm)
> is known about it except the key -- as opposed to "security through
> obscurity" hiding of the algorithm. The problem may, however be of
> interest to recreational mathematicians.
>
> To learn more:http://www.schneier.com/crypto-gram-0205.html#1http://slashdot.org/features/980720/0819202.shtmlhttp://en.wikipedia.org/wiki/Kerckhoffs'_principlehttp://en.wikipedia.org/wiki/Claude_Shannon#Shannon.27s_maximhttp://en.wikipedia.org/wiki/Security_through_obscurity
>
> --
> Guy Macon
> <http://www.GuyMacon.com/>
mosherubin
Thanks for focusing the issue. You're assuming that revealing the
system would render it useless from now on. Maybe the Chaocipher's
security _does_ reside in the key, not in the algorithm? The fact
that Byrne was so secretive about it doesn't prove the entire system
would be compromised for eternity once his challenge messages are
broken. This is precisely my point: we need to prove that its
security does or does not lie in the key settings.
We will be able to confidently relegate Chaocipher to the list of
solved systems once we have a general solution to it. Until we've
done that the entire discussion is purely academic with no basis in
the real world.
Call me a pragmatist, but when I encounter a system that has remained
intact for so many years, comes with endorsements (e.g., Deavours and
Kruh), and includes so much crib information, I need to know I haven't
erred in my assessment of it.
I don't agree that the only people interested in the system are puzzle
enthusiasts. That's like saying that studying the Enigma today has no
purpose at all. There is historic and cryptologic value in
understanding a system that was viewed by several cryptologic
luminaries in a favorable light. And who knows, the Chaocipher might
just contain the germ of an idea that could be useful today.
Moshe
On Feb 20, 11:31 am, Guy Macon <http://www.GuyMacon.com/> wrote:
> mosherubin wrote:
>
> >Guy,
>
> >Thank you for your reply and for the list of links to "security by
> >obscurity" posts. I agree with you that "security by obscurity" is
> >unacceptable and that Byrne should have revealed the underlying
> >system, certainly after he extolled Chaocipher's security to the
> >hilt. I address this exact point in one of my pages (http://
> >www.mountainvistasoft.com/chaocipher/chaocipher-001.htm):
> ...
> >You must agree that Byrne's challenge differs from other "security by
> >obscurity" inventors. Such inventors typically provide ciphertext
> >message with no plaintext cribs. What other obscure (classical
> >cryptographic, in contrast with modern public-key) system has provided
> >such large pt/ct cribs? Byrne's system might not win the "security by
> >transparency" award, but it does not fit the typical "security by
> >obscurity" model, either.
>
> While I agree that Byrne has provided a goodly amount of plaintext
> and ciphertext, in my opinion (and it is just an opinion), doing so
> is necessary but not sufficient. My reasoning is as follows:
>
> In any cryptographic system, it is highly desirable to be able
> to recover from severe security breaches. Let's say that you
> are using AES-256 and someone gets *everything*; all of your
> keys all of your previous plaintext and ciphertext, the exact
> software you are using, they get it all. This can happen through
> a break-in or a very high level defector. OK, so you are hosed
> as far as all past information is concerned, but how do you go
> forward from there? Simply generate a new key from a HRNG and
> start using it. Nothing you send after the key change is
> vulnerable even though the attacker got everything the day before.
>
> Now imagine that the same thing happens when you are counting
> on Byrne's algorithm being a secret. Now when an attacker
> gets everything, the only way to move forward is to get a new
> algorithm. Much harder than generating a key.
>
> Of course you would still have the problem in either case of
> having to distribute a key or algorithm to your recipient,
> so in the real world you would be likely to prefer a public
> key system rather than a symmetric cipher, but it would still
> be a lot easier to generate new keys rather than switching
> algorithms.
>
> I was serious when I suggested that Byrne's challenge might be
> of interest to those who like to work on mathematical puzzles.
> This is exactly the sort of thing they love to work on.
James Taylor
> Call me a pragmatist, but when I encounter a system that has remained
> intact for so many years, comes with endorsements (e.g., Deavours and
> Kruh), and includes so much crib information, I need to know I haven't
> erred in my assessment of it.
The fact that some of his contemporaries were nice about his efforts
tells me only that he was well liked.
The fact that Byrne was so secretive about his algorithm suggests to me
that he lacked confidence in its strength if the algorithm became known
to the enemy.
The fact that all the military departments he showed it to failed to
take an interest is a good indicator that they already had better
ciphers in-house.
If there was any reason to believe his cipher was ground-breaking, it
might be worth looking at, but without knowing the algorithm it would be
necessary to dream up ciphers that might produce similar output and see
if they fit. In addition to brute-focing the key, this is at least as
much creative work as inventing the cipher yourself; effort that would
be better applied to inventing a better more modern cipher.
If it ever did succumb to cryptanalysis, then in the same moment that
you discover the secret algorithm, you also discover that it is
insufficiently strong.
For all these reasons, it doesn't seem worth anyone's time and effort
spent trying to reverse engineer the Byrne cipher. It's not as if the
cipher is being used for real to carry military secrets in a time of
war.
Oh, and if you think that an unknown algorithm remaining unguessed is
some kind of accolade, remember that Kryptos has been sitting right
outside the cryptanalytic Mecca of the Western world for 20 years and
still part four remains unsolved. In marked contrast to the Byrne
cipher, the Kryptos ciphers were *supposed* to be analysable and never
supposed to be of military strength. So the survival of the cipher,
given that its mechanism is secret, is hardly unexpected.
The only thing we learn from Byrne's cipher is how *not* to set a
deciphering challenge. He should have described the algorithm, and kept
only the key secret, because only then does it become interesting.
Having said all that, I recognise that I'm talking out of my uninformed
ass, and I feel bad for throwing a dampener on your enthusiasm. I think
it's good that someone keeps up interest in these things, even if only
for the sake of history. I therefore wish you well.
--
James Taylor
mosherubin
> (You might want to consider not top-posting...)
>
> mosherubin wrote:
>
> >Guy,
>
> >Thanks for focusing the issue. You're assuming that revealing the
> >security _does_ reside in the key, not in the algorithm? The fact
> >that Byrne was so secretive about it doesn't prove the entire system
> >would be compromised for eternity once his challenge messages are
> >broken. This is precisely my point: we need to prove that its
> >security does or does not lie in the key settings.
>
>
> [1] Assume that if we knew the algorithm, not knowing the key
> makes the ciphertext indistinguishable from random data through
> cryptanalysis.
>
> Conclusion: We don't know the algorithm or the key, so
> cryptanalysis will fail.
>
> [2] Assume that if we knew the key, not knowing the algorithm
> makes the ciphertext indistinguishable from random data through
> cryptanalysis.
>
> Conclusion: We don't know the algorithm or the key, so
> cryptanalysis will fail.
>
> [3] Assume that if we know the algorithm but not the key,
> cryptanalysis can derive the plaintext, but can not do so
> if we know neither.
>
> Conclusion: We don't know the algorithm or the key, so
> cryptanalysis will fail.
>
> [4] Assume that if we know the key but not the algorithm,
> cryptanalysis can derive the plaintext, but can not do so
> if we know neither.
>
> Conclusion: We don't know the algorithm or the key, so
> cryptanalysis will fail.
>
> [5] Assume that it is possible to derive both that algorithm
> and the key through cryptanalysis.
>
> Conclusion: At last there is a point to doing the cryptanalysis,
> but we know ahead of time that the cipher is particularly weak.
>
> >I don't agree that the only people interested in the system are puzzle
> >enthusiasts. That's like saying that studying the Enigma today has no
> >purpose at all. There is historic and cryptologic value in
> >understanding a system that was viewed by several cryptologic
> >luminaries in a favorable light. And who knows, theChaociphermight
> >just contain the germ of an idea that could be useful today.
>
> plaintext/ciphertext/key examples, not just plaintext/ciphertext.
> That would give us a good chance of reverse-engineering his
> algorithm. Better still would be someone who has the algorithm
> giving us ciphertext for various keys and plaintext of our own
> choosing. This could be done by one of the people who know how
> it works putting up a "black box" simulation on the web. Once
> we had the algorithm, we could create as many plaintext/
> ciphertext/key examples as we wish, and thus be able to try
> and break his cipher using chosen-text-cryptanalysis. Trying
> to figure out the algorithm and the key at the same time using
> only a finite amount of known plaintext and no possibility of
> a chosen-plaintext attack makes it very difficult to figure
> out even a weak cipher.
>
> It is indeed a fascinating subject (at least it is to me) but
> I also understand why most cryptographers have little interest
> in it. I myself find reverse-engineering an algorithm to ba a
> lot more interesting than cryptanalysis, but then again I am
> an engineer, so a certain amount of weirdness should be expected. :)
>
> What are the chances that one of the people who know how it works
> will someday reveal the algorithm so that it becomes interesting
> to cryptographers?
Guy,
No problem re the top-posting. Although a modern Usenet service like
Google Groups displays everything in logical order and hides previous
content, I'm always willing to mend my erring ways. ;-)
I found your "proof" quite interesting. What I meant to say is,
_after solving_ the Chaocipher challenge and determining its
algorithm, we can _then_ assess whether or not it is a sufficiently
secure system (by pre-1950s standards), and whether its security lies
solely in the key chosen.
You're way ahead of me with logic, but I don't agree with statements
like "Assume ... makes the ciphertext indistinguishable from random
data through cryptanalysis. Conclusion: cryptanalysis will fail".
It's way too fatalistic for me. That's what cryptanalysis is all
about. It _is_ magic, coaxing some faint pattern out of seemingly
random ciphertext and cracking the system. As someone wrote (I don't
remember who at the moment, I believe David Kahn), cryptanalysts would
have been burned at the stake in the Middle Ages for using black
magic.
Your attempt to use pure logic to prove either (a) the futility of
even trying to solve it or (b) its worthlessness reminds me of David
Kahn's description of the common fallacy of "proving" a simple
substitution cannot be solved because there are 26! =
403,291,461,126,605,635,584,000,000 different possible cipher
alphabets. "If the cryptanalyst tried one of these every second, he
would need six quintillion years, or longer than the known universe
has been in existence, to run through them all. Yet most
monoalphabetics are solved in a matter of minutes." As Shannon has
shown, the cryptanalyst does not go after these possibilities one by
one. He eliminates millions at a time.
Based on clearly discernable statistical patterns performed on the pt/
ct cribs, I believe Chaocipher is solvable without a priori knowledge
of the algorithm. I also believe that the algorithm, although not as
secure as modern number theoretic cryptosystems, might not be as weak
as we think.
Reading the above thread I think I can say that there are two types of
opinions on Chaocipher: the functional versus the historic/academic.
(*) The functional camp believes that Chaocipher can never be as
strong as modern day crypto systems (e.g., AES-256). It is most
probably not as strong as older machine ciphers (e.g., Enigma,
Geheimschreiber) and certainly not as strong as modern number
theoretic cryptosystems. Therefore it is a waste of resources to even
consider it.
(*) The historic/academic camp believes there is value in working on a
system that will definitely not impact modern cryptology but will
illuminate a period of time or history.
There is no right or wrong here, just personal, subjective
preferences. The world is a better place for having both camps. In
the end, the historic/academic camp will get a very satisfying feeling
when the system is solved, will understand more about Byrne, Hitt, and
Friedman in the historic context, and will be able to sleep well again
at night <g>. The functional camp will be able to read about it,
acknowledge whatever the concept is, and move on to the next great
challenge awaiting us all.
Just a humorous quote from Nick Pelling's enjoyable "Cipher Mysteries"
site (http://www.ciphermysteries.com/about):
"If you don't find some romance and mental adventure in uncracked
ciphers, you must surely have a heart of lead, right?" <g>
Regarding when the algorithm will be made public, Deavours and Kruh
described how John Byrne Jr. is still trying to commercialize the
system, so it might not be any day soon. For his sake, it would be
better to make the algorithm public, implementing your idea of an on-
line simulation to allow chosen plaintext and ciphertext attacks, and
let the crypto community pass its judgement. Given the powerful
number-theoretic cryptosystems we have today, I doubt if there is any
commercial value in marketing Chaocipher.
Regards,
Moshe