Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Chaocipher as Dynamic Substitution?
Topic Started: Oct 23 2009, 12:43 PM (239 Views)
mosher
Advanced Member
[ *  *  * ]
A couple of weeks ago I correspondenced with osric (aka Mike Cowan) about the possibility of Chaocipher being a form of 'Dynamic Substitution' (DS). A clear exposition of Dynamic Substitution (DS) can be found on Terry Ritter's interesting web site (see below for links). In brief, DS modifies the substitution system (e.g., the enciphering alphabets) each time a letter is enciphered.

I felt it had merit and should be investigated as a possible model for Chaocipher. osric indeed spent time on it and has come to the conclusion that DS is too chaotic for Chaocipher and does not produce the same HMM (Hidden Markov Model) fingerprint found by Jeff Hill.

Here are quotes from the relevant e-mails. Notwithstanding osric's valuable results, I'm wondering if it's possible to devise a DS model which will produce the Chaocipher fingerprint.

Moshe Rubin to osric (11 October 2009)
Quote:
 
Nonetheless, I have been thinking about Chaocipher at odd moments, and am becoming more convinced that the method is akin to Terry Ritter's Dynamic Substitution (http://www.ciphersbyritter.com/GLOSSARY.HTM#DynamicSubstitutionCombiner). I recently read through my entire set of Cryptologia issues, both to rejuvenate the neurons, but with an eye towards Chaocipher-related ideas. While doing it I chanced upon Ritter's article (see also http://www.ciphersbyritter.com/index.html#DynSubTech for the original article as published in Cryptologia). It is actually related to the hypothetical system I proposed in TCCH Progress Report #2 (http://www.mountainvistasoft.com/chaocipher/chaocipher-002.htm).

Ritter's patented idea is that the substitution table(s) can be dynamically changed after each enciphered letter. He recommends permuting the substitution alphabet by swapping the last-enciphered letter with another one. In this way, a sequence of two identical pt letters will result in non-identical ct letters, just what we see in Chaocipher.

I was thinking specifically about the characteristic that pt/ct identities not repeating for a minimum of nine steps. Supposing the following:

  • A system of two disks, one for keying, the other for substituting (e.g., Jeff Hill's C98A)
  • The keying disk has 26 removable/detachable tabs around its circumference, allowing the operator to permute the letters at any time
  • The operator uses a key letter to set up the substitution disk
  • The operator performs the substitution
  • The operator advances the keying disk one position
  • After enciphering one letter, the operator removes the key tab just used (which has shifted one position) and swaps it with another tab at least nine places ahead (by 'ahead' I mean that it would take nine position shifts for that key letter to be used again). Because we're swapping with the last key tab which has already shifted one position, we will never swap a just-swapped key letter back as the next key letter.
  • [Open question: what is the method to determine the swapping distance? This is the crux, and I believe it is related to the plaintext and/or ciphertext letter.]
  • As time goes on, the keying alphabet will become well-mixed. The keying sequence would thus be truly aperiodic, supporting Byrne's claim that it would never, ever repeat.

I'm aware that no one intimates permuting the keying disk, but no one rules it out, either. This could explain why Friedman found it error prone: if the shift is off by one, the keying sequence slowly (!) propagates the error.

BTW, I believe the substitution disk is _not_ being permuted because I have a hunch we would not get the pt/ct identity phenomenon.

The more I think about it, the more I lean towards such a system. It is the only type of system that could explain how 100 encipherments of the same ALLGOOD sentence can result in non-identical, non-isomorphic forms.

osric to Moshe Rubin (16 October 2009)
Quote:
 
After some thought and experimentation I've reluctantly come to the conclusion that Ritter's system is too good at scrambling to be able to produce the incidence wave that is such a strong feature of Chaocipher.

When I requested more information about his results, osric authored an MS Word document explaining the phenomenon called "Incidence Wave". I believe this is an important document for any Chaocipher researcher: any proposed system must conform to the Incidence Wave characteristic.

Dynamic Substitution can explain how a simple system can produce non-pattern and non-isomorphic ciphertext. Producing a DS systen that also displays the Coincidence Wave will be a great step forward. Can anyone think of how to do this?

Moshe
Offline Profile Quote Post Goto Top
 
nullsole
Member Avatar
Just registered
[ * ]
I only wish I was more experienced in such things ... I admire and try and follow all things ... and there is so much great info!!! I read it all!

Someday I hope to contribute to this research/solution ...

As of now, I only read and reread everything and try and follow all that is presented. I find it so very fascinating! Thanks for posting the info in ALL locations. I am following them all.

I wish I had more time. Being in FL keeps me busy .........................

nullsoft/emato
Offline Profile Quote Post Goto Top
 
mosher
Advanced Member
[ *  *  * ]
Hi nullsole,

I'm serious when I say that even knowing that people like you are interested in the material posted, and are reading it, gives us all the necessary shot-in-the-arm to continue. If you find anything that is not clear or readily understandable, please raise a flag and we'll edit whatever it is to make it clearer.

Best regards,

Moshe
Offline Profile Quote Post Goto Top
 
aloos
Just registered
[ * ]
Hello Moshe (and all the others contributing),


first of all: Thank you for maintaining the great chaocipher discussion group and the constant flow of information on the chaocipher website.

I have one question concerning the distribution (Progress Report #7). In the graph

http://www.mountainvistasoft.com/chaocipher/pr07/coincidence-distribution.gif

you are listing what exactly against what? Is it the number of quadrupels (x_i,y_i,x_i+k,y_i+k) with x_i = x_i+k and y_i = y_i+k, where (x_i,y_i) is the plaintext-ciphertext pair at position i, against shift k?

Thank you,
andreas
Offline Profile Quote Post Goto Top
 
mosher
Advanced Member
[ *  *  * ]
Hi Andreas,

Thank you very much for your kind words. I'm sure other participants will agree it's a thrill to see more and more newcomers take an interest in the Chaocipher discussions. We look forward to any contributions or comments you, and others, may have.

Yes, you have it correct. The horizontal 'X' axis is the shift of Exhibit 1 pt+ct against itself, while the vertical 'Y' axis denotes the number of matches of (pt, ct) = (pt, ct). I like your mathematical formulation better than mine <g>!

The exceptional peaks every 55 letters are due, as mentioned, to the fact that every shift which is a multiple of 55 will align the top and bottom such that the plaintexts of the first 100 lines are juxtaposed. The corresponding ciphertext letters will randomly match, leading to an exaggerated number of non-causal matches.

Best regards,

Moshe
Offline Profile Quote Post Goto Top
 
jhll
Member Avatar
Just registered
[ * ]
Hi Moshe,

Since the only pt/ct observations that can be made are those provided by Byrne in a particular Exhibit, the only probabilities that we can directly calculate are those for repeated pt/ct encipherments, which correspond to repeated keys. When these first began to be studied by ACA members, two things were noted: (1) no key repeats in less than nine steps, and (2) the probability that a key repeats is greatest at step 13. Observation (1) did not have an immediate explanation, but observation (2) suggested to analysts that there were two disk alphabets, one which was stationary and a second that was rotating about 2 letters per step on average relative to the first. After 13 steps, a key will have advanced 26 letters on average, bringing it back to where it started and repeating the same pt/ct encipherment.

Although your system of swapping keys can guarantee that no key repeats in less than nine steps, there is still the full range of probabilities to replicate from Step 1 through at least Step 26, as both you and osric are aware. It is hard to see how this could done with a simple swapping procedure, since you must not only replicate observation (1), but somehow arrange for a key to repeat with a specified probability at each Step from 1 to 26. On the other hand, there are several systems based on rotating disk alphabets that can easily replicate the entire range of probabilities.
Offline Profile Quote Post Goto Top
 
mosher
Advanced Member
[ *  *  * ]
Hi jhll,

This new post of yours finds a reformed man :'D . Since my 11 October posting in this thread I have spent some time simulating a Ritter-like system, your C98A system, and writing software to check for the "Incidence Wave". I hope to start a new thread with my findings, but I am now convinced of the following:

  • Chaocipher is duplicated by a Markov Model
  • The stepping vector of (1, 1, 2, 4) is the correct one
  • The absence of intervals of 7 and 8 is not significant; the fact that they did not occur is a statistical 'fluke'

Thanks to osric's document explaining the "Incidence Wave" phenomenon (based, of course, on your classic C:A&M paper), I have gotten a better feeling for what you and he have been saying for a long time: the "Incidence Wave" is a real phenomenon, and any proposed model must produce it.

Ritter's Dynamic Substitution principle is a powerful one, and should certainly merit cryptanalytic research in the future (when we've solved Chaocipher ;) ) However, as you point out, it is too chaotic for our needs, and does not exhibit the Incidence Wave. Indeed, I too cannot see how to swap the tabs and still preserve the wave.

So I'm coming aboard the Markov Model bus. In a way this is a shot-in-the-arm, enabling me to focus my energies on something I can now "feel in my bones".
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · Chaocipher · Next Topic »
Add Reply