Jeff Hill's new paper on Byrne's machine

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:

Jeff Hill's new paper on Byrne's machine
Topic Started: Nov 1 2009, 06:10 PM (269 Views)
osric	Nov 1 2009, 06:10 PM Post #1
Advanced Member Posts: 50 Group: Members Member #3,254 Joined: March 15, 2009	When I read Jeff Hill’s proposition for a switching mechanism based on logic gates, (see his excellent paper "A Feasible Mechanism for the 1937 Byrne Cryptograph" at TCCH) I immediately thought back to Byrne’s description of splitting words like splitting the atom, and thought Jeff had hit on the solution. But sadly this early promise was not borne out when I built a computer model of Jeff’s commutators and logic gates, and compared the characteristic of the ciphertext output with Chaocipher. In particular, the incidence wave is not replicated, though other features are also awry ( you can read my brief description to Moshe of the incidence wave at http://www.mountainvistasoft.com/chaocipher/CowanDocs/Incidence_Wave.doc ) Now it may well be that I have misunderstood Jeff’s article or indeed am in some other way mistaken. In this case my apologies in advance. But I thought it worthwhile to display the results of my Sunday afternoon’s exercise for, hopefully, your comments, your confirmation or your alternative findings. As ever there are more ways than one of skinning a cat so that even should my conclusions in this note be correct, Jeff’s ideas still will hopefully lead to a positive end result. I for one shall be following up on them. The problem seems to be that the steps of 1,2 and 4 moves are not produced in the correct ratio of 2:1:1 resp. Here are some of the results I found, using two different commutator sets, for 5500 letters enciphered: com1 = 0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1 com2 = 0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,0,1,0,1,1,1,1,1,1,0,0 Nr of 1’s = 1839 2’s = 1625 4’s = 2036 com1 = 0,0,0,1,0,1,1,0,1,0,1,1,0,1,1,1,0,0,1,0,1,1,0,0,0,1 com2 = 0,1,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,1,0,1,1,1,1,1,1,0,0 Nr of 1’s = 2469 2’s = 1461 4’s = 1570 Below are the simple waves for these examples followed by the true wave from Chaocipher. All are for ciphertext from the first 5500 plain letters of Exhibit 1. interval 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 example 0 0 0 0 0 0 0 8 0 16 16 12 0 10 0 0 0 0 2 27 78 24 24 24 0 example 0 0 0 0 0 0 0 0 0 6 4 12 0 50 0 0 0 0 0 0 0 0 56 36 37 Chaocipher 0 0 0 0 0 0 0 0 1 0 5 13 0 34 14 5 4 5 1 0 6 4 12 8 11 I then tried other strategies for using the commutators than the one described in Jeff’s paper. I first tried moving the commutators just one step after each encipherment. I later tried moving just the 26-zone commutator by 1 step after every encipherment and the other 1 step after 26 encipherments. Both these were attempts to ensure every one of the 702 members of the cycle described by Jeff would be used. While both these methods brought the incidence of 1,2 and 4 moves closer to the ratio required the pattern of these moves was very repetitive. The overall effect was still to produce an incidence wave that was far from the one required. Nr of 1’s = close to 2750, as required 2’s = 1320 to 1430, as opposed to 1375 as required; 4‘s = as for the 2’s. Extract from the output stream, which is not random but runs in patterns: 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 2 1 2 1 2 1 incidence wave (simple) interval 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 example 0 0 0 0 0 0 0 0 0 1 19 5 0 9 2 1 53 8 0 0 9 3 8 8 4 Chaocipher 0 0 0 0 0 0 0 0 1 0 5 13 0 34 14 5 4 5 1 0 6 4 12 8 11 My C computer program of Jeff’s commutator model is available to anyone who wants to look at it or try it (caveat my programming style!) The basic problem seems to be to find a way of making the stream of 1’s, 2’s and 4’s to be both in a random pattern and also in an overall ratio of 2:1:1.



jhll	Nov 1 2009, 08:35 PM Post #2
Just registered Posts: 9 Group: Members Member #3,290 Joined: October 8, 2009	Hi osric, Thanks for the analysis. I will look into this, but it may take a few days. Can you make your C program available for download from TCCH? Or just post it to this thread?



mosher	Nov 2 2009, 08:16 AM Post #3
Member Posts: 41 Group: Moderators Member #3,268 Joined: May 26, 2009	Hi osric, That was pretty fast feedback on jhll's proposed model, and interesting to boot <g>. I'd also like to play with your program, and I'm looking forward to reading comments by jhll, yourself, and others on this model. Moshe P.S. I took the liberty of fixing the formatting problems you encountered in your post. It seems the Zetaboards software converts two or more spaces into a single space. The only solution I have is to insert HTML "&-nbsp;" entities when additional whitespace is required (and to block the text off in a [f-ont]...[/f-ont] block). See my discussion here.



osric	Nov 2 2009, 08:58 AM Post #4
Advanced Member Posts: 50 Group: Members Member #3,254 Joined: March 15, 2009	Hi Moshe, Many thanks for the cosmetic work! and the advice on how to do it. osric



jhll	Nov 2 2009, 11:46 PM Post #5
Just registered Posts: 9 Group: Members Member #3,290 Joined: October 8, 2009	Hi osric, After reviewing your post, it seems to me that the commutators of your second example did a fairly good job of matching Chaocipher up through Interval 15. interval: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 example: 0 0 0 0 0 0 0 0 0 6 4 12 0 50 0 0 0 0 0 0 0 0 56 36 37 Chaocipher: 0 0 0 0 0 0 0 0 1 0 5 13 0 34 14 5 4 5 1 0 6 4 12 8 11 The example shows a frequency of 50 at Interval 14 and Chaocipher shows a combined frequency of 48 at Intervals 14 and 15. The match here might not be as poor as it first appears, since further optimizing might resolve the issue. Again, although the match is not very good beyond Interval 15, and in particular is very poor from Interval 23 through Interval 25, the cause of this may be that the commutator contacts are not yet sufficiently optimized. Comparing the stepping probabilities from the example to the values required by the Markov Model that I have written about, I find the following: Markov Model Requirements: .500 .250 .250 Example 2 Probabilities: .449 .266 .285 It remains to be seen whether the required probabilities can be obtained using optimizing algorithms. Also, for optimizing purposes, there is nothing mandatory about a commutator ratio of 27/26. Ratios such as 37/31 or 53/51 might prove easier to match to Chaocipher data.



jhll	Nov 3 2009, 11:58 PM Post #6
Just registered Posts: 9 Group: Members Member #3,290 Joined: October 8, 2009	Hi osric, I ran optimizing trials today and confirmed that a commutator ratio of 53/51 gives consistently good matches to Chaocipher data on every trial. A ratio of 27/26 occasionally gets good results, but I'm sure that Byrne wasn't just lucky with his choice of commutator ratios. He would have made the commutators as large as he possibly could in order to maximize the number of contacts. He may well have used more contacts than were necessary, but a 53/51 ratio is sufficient to confirm that the commutator design presented in FM1937 is valid. jhll



osric	Nov 7 2009, 11:30 AM Post #7
Advanced Member Posts: 50 Group: Members Member #3,254 Joined: March 15, 2009	Hi Jeff, Quote: but a 53/51 ratio is sufficient to confirm that the commutator design presented in FM1937 is valid. I agree that increasing the commutator size is a step in the right direction to get over the problems pointed out in my initial posting. It increases the randomness of the stream of 1,1,2,4 moves. Whether your 53/51 has gone far enough to match the randomness in Chaocipher is yet to be demonstrated. On a practical point, I wonder what size of commutator disk would be needed to achieve 100% accuracy for 50 or so contacts. It will certainly not be an insignificant size, which bears on a later comment I will make concerning Langan’s observations on Byrne’s machine. But in terms of validity there is another serious problem with the model you propose. As you know Chaocipher Exhibit 1 has no hits at intervals less than 9. On the other hand the machine you propose, with turnover every 500 letters, has a 95% probability of one or more hits at such low intervals. Thus the likelihood that it is Byrne’s machine is very low. Somehow Byrne’s machine was able to avoid these low-interval hits when he so wanted. How he achieved that remains an open question. Byrne claimed that Chaocipher is unbreakable, even if the cryptanalyst was in possession of his machine. Yet if an anlayst had your commutator model I think the task is do-able and that’s something I shall put to the test. Of course Byrne’s judgement may have been at fault since presumably he did not have access to the cryptanalytic skills of someone like Friedman. Incidentally, don’t you think that Langan would have commented on the presence of commutators, and the need for a power supply, had they been part of the design that Byrne revealed to him? The puzzlement expressed by Langan was how just 2 disks could have provided the apparently random ciphertext, and the explanation from Byrne should have been the stream from the commutators. It’s odd that didn’t come out in the discussion. Either Byrne must have obscured it or Langan must have been very much out of his depth to miss it – or there were no commutators! On the basis of what you have presented, I do not believe you have validated your machine. Indeed I do not see that you can claim validation until you have demonstrated you can decipher at least the brief unknown plaintext in the centre of Exhibit 1. In an earlier paper you said that an accurate description of Byrne’s machine may enable analysis to recover the disk alphabets, after which a complete break of Exhibit 1 seems certain. I suggest you proceed and do this to truly validate that the commutator machine is the same as Byrne’s. (For those unfamiliar with Exhibit 1, there are 13,615 characters of plaintext and of ciphertext. In the centre of the plaintext, after the initial 100 repeated sentences of 55 letters each, there are 279 characters of unknown plaintext before the rest of the plaintext continues with the Declaration of Independence and the Gettysburg Address.) I suggest you use the inital 5500 letters of plain and ciphertext to recover the keys using your model, and then continue and decipher the 279 letters of ciphertext whose plaintext we do not know. If you can do that then you have validated your machine. If you can’t then I am afraid I remain unconvinced. osric



jhll	Nov 9 2009, 12:10 AM Post #8
Just registered Posts: 9 Group: Members Member #3,290 Joined: October 8, 2009	Hi osric, I thought that I had made it clear in my paper that my purpose was to model a device that is functionally equivalent to Byrne's device, "without necessarily making it an exact duplicate". I left open the possibility that Byrne's machine might be significantly different from the model that I presented, but I also left open the possibility that it might not be significantly different when all is said and done. My paper basically outlines the thought process that I followed in order to (1) identify the challenges facing Byrne in 1937, (2) identify the electro-mechanical resources available to Byrne at that time, and (3) develop a model that explains how the challenges could be met using 1937 technology. I also made it clear that I did not consider the model that I presented to be "a complete blueprint for engineering purposes". In my paper, I discussed the 27/26 ratio in the context of "composite cycles". My reason for doing so was to make the point that even two relatively short cycles can combine with the 55-character plaintext cycle in Exhibit 1 to guarantee that no row of ciphertext repeats in Exhibit 1. The model presented in FM1937 requires each commutator to generate a series of ON/OFF signals in which the probabilities of ON and OFF are as close to equal as it is mechanically possible to achieve. The mathematical ideal is prob(ON) = prob(OFF) = 1/2. As it turned out, a 53/51 ratio does a much better job of randomizing the commutator signals, S1 and S2, than 27/26. Further research is no doubt needed to refine this model. As far as my response to you on this forum on 11-03-09, I stated that "a 53/51 ratio is sufficient to confirm that the commutator design presented in FM1937 is valid". What I meant by this was that as the ratio is extended beyond 27/26 to 53/51, the output signals, S1 and S2, approach closer to the mathematical ideal of prob(ON) = prob(OFF) = 1/2. Thus the commutator model is a valid approach to designing a device that is functionally equivalent to Byrne's device, but again "without necessarily making it an exact duplicate". You point out that "Chaocipher Exhibit 1 has no hits at intervals less than 9". This was noted in TCCH Progress Report #11 on 04-22-09 by Moshe and my response at that time was that, "Byrne's device may itself cause at least some of the distortion by having a keystream that is biased in some, as yet unexplained, way". I believed then and I believe now that to have an exact duplicate of Byrne's device, it will be necessary to explain why there are no hits at intervals less than 9. Since I do not know the reason for the discrepancy at this time, I issue disclaimers, such as the ones found in the concluding paragraph of FM1937. You also ask, "don’t you think that Langan would have commented on the presence of commutators, and the need for a power supply, had they been part of the design that Byrne revealed to him?" Unfortunately, the only thing that we know for sure is that Byrne did not show the actual machine to Langen, but instead brought the 1919 blueprint to the meeting. When discussing that blueprint, I always place it in the context of the cost estimates that Byrne received for the actual construction of that machine, which (based on the prices provided by Byrne), would be in the range of $54,000 to $216,000 today when adjusted for inflation. There is no evidence that Byrne was able to build this particular machine and for that reason I do not believe that Byrne's 1937 device necessarily resembled the machine shown in the blueprint. jhll



osric	Nov 11 2009, 02:22 PM Post #9
Advanced Member Posts: 50 Group: Members Member #3,254 Joined: March 15, 2009	Hi jhll, Thanks very much for your response to the issues I raised. Just a few further comments. Quote: I thought that I had made it clear in my paper that my purpose was to model a device that is functionally equivalent to Byrne's device, "without necessarily making it an exact duplicate”. I am afraid I don’t follow what you mean by ‘functionally equivalent’. The vital question for me is: have you proposed a design that can produce the same ciphertext as Byrne’s machine, and the answer is no. I say this because your machine doesn’t give the same results as Byrne’s (the hits at interval <9 problem) so either there is something important missing or, more likely, the whole principle is wrong. In either case your machine is not Byrne’s machine and I think that needs making clear, because the conclusion is that the hunt is still on. Quote: I left open the possibility that Byrne's machine might be significantly different from the model that I presented, but I also left open the possibility that it might not be significantly different when all is said and done. Well you’ve backed the horse both ways here! I would say you have designed a machine that gets close to a Markov machine using 1937 technology, and that is a very interesting achievement in itself. But the Markov machine is not Byrne’s, for reasons I have pointed out. What you haven’t done, in my opinion, is to meet the claim in your paper: Quote: ... an electro-mechanical cryptograph can be built, using 1937 technology, that would replicate the statistical signiature of Byrne’s machine, as was derived from Byrne’s Exhibit 1. Your machine produces hits at intervals less than 9 and thus does not produce the statistical signiature of Byrne’s machine as far as Exhibit 1 is concerned. I have had a look again at Langen’s reported meeting with Byrne in 1954 and I see nothing there to suggest they discussed the 1919 blueprint. Unless you have evidence to the contrary I suggest it is far more likely that Byrne brought the plans of the latest (1937) machine he built – he didn’t bring the machine itself because, as he said, it was too heavy to carry. Thus my surprise, mentioned in my earlier posting, at the lack of reported commutators or power supply from this meeting, and my speculation that maybe there were none. osric Edited by osric, Nov 11 2009, 02:26 PM.



mosher	Nov 13 2009, 10:26 AM Post #10
Member Posts: 41 Group: Moderators Member #3,268 Joined: May 26, 2009	I read Jeff's recent paper with great interest and have been following this thread. I do have some questions and comments to make. As I lag behind you guys on this discussion, I apologize up front if I make any uninformed comments or remarks. () At least to me it was obvious that jhll's recent paper "A Feasible Mechanism for the 1937 Byrne Cryptograph" would not be revealing Chaocipher's true mechanism, and jhll made that quite clear. We've all been in this business long enough to know that there are too many variables for a 'lucky guess' to be correct. I see jhll's paper as a theoretical study, meant to stimulate intelligent thinking all round. I believe he succeeded in showing that a system (not necessarily Chaocipher) could be constructed with 1930's technology that would produce Markov Model statistics, exhibit an incidence wave similar to Exhibit 1, produce a random keying sequence, and enable enciphering "ALLGOOD..." one hundred times without repetitions. () I would not expect jhll's proposed commutator setting to jibe 100% with the observed Chaocipher incidence wave (IW) as found in Exhibit 1. That is because Exhibit 1 and jhll's proposed model are both statistical 'aberrations' of some 'ideal' theoretical distribution and IW. Even the observed Exhibit 1 IW differs from the 'ideal' IW. When assessing the output of one of jhll's models we would expect it to similar to, but not identical with, the observed Exhibit 1 IW. () I ran osric's C implementation of jhll's new model using the 53/51 ratio, checking the keying stream for repetitions. In general the frequencies of 1's, 2's, and 4's is close to 2:1:1. The keying sequence is not repetitive, but the first time I ran it the entire cycle repeated itself after 5239 = 13 x 13 x 31 steps. I would have expected it to repeat itself after 53 x 51 = 2703 steps. Can anyone explain this observation? () osric's implementation uses two half-rotors to encrypt, but I don't see a provision in the code for moving disk-2. Is disk-2 meant to move at some point? If so, when and how? () The proposed system is not dependent on the plaintext or ciphertext. The keying sequence is totally deterministic and does not change for specific plaintext or ciphertext. In other words, there is no pt or ct autokeying involved. Progress Report #5 on TCCH (http://www.mountainvistasoft.com/chaocipher/chaocipher-005.htm#observations) uses the Kappa Test to deduce that the keying sequences of the three "in-depth" messages in Kruh and Deavours's Exhibit 5 are different after the starting characters. Any model, including jhll's last one, that does not use the pt/ct in generating the keying stream cannot explain Exhibit 5. Is this correct? Is somehow getting in pt/ct autokey a requirement? () Regarding osric's comment about Langen's not mentioning salient details: I never met Langen, and I assume he was a very capable cryptanalyst, but he did not know what questions to ask Byrne during the latter's visit. Langen was baffled by what was presented and could not find a coherent description about what he had seen. J. F. Byrne, whatever his other characteristics were, was a most capable communicator and could have clarified any question had Langen just asked them. I feel Langen was way over his head when Byrne showed him his blueprints, did not know what to ask, and probably listened passively throughout the meeting. If Langen did not write about technical details like commutators, it is probably because he didn't know what was flying and was totally lost. I'd like to remind everyone that any proposed model can be checked against all observed intervals (from 9 to 19) in Exhibit 1 (see http://www.mountainvistasoft.com/chaocipher/general/all-pt-ct-identities-distance-9-to-19.txt). For example, there are four (4) cases in Exhibit 1 where a pt/ct pair repeats itself after nine steps: 4207(p): [UMP] OVERLAZYDO [GTO] 4207(c): [QFK] EHGUTNFVTE [UOQ] 7800(p): [EWO] ULDRELINQU [ISH] 7800(c): [BVD] BFBWYZLOYB [SST] 7864(p): [NES] TIMABLETOT [HEM] 7864(c): [IGY] ARLTYSNDFA [LTT] 9838(p): [THE] SECOLONIES [VFO] 9838(c): [VZN] XYPJKPVESX [NUD] In the first example, (O/E) repeats after nine (9) steps. The strings are at offset 4207 within Exhibit 1, the plaintext string is preceded by the characters "UMP" and followed by "GTO", etc. These are my first-impression comments. How would you guys suggest proceeding from here? There are just too many variations and possibilities for trying to guess how the mechanism works. In the early days of TCCH someone replied the following on sci.crypt: Quote: 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. Short of having the model revealed to us, how can one proceed to deduce the model? Regards, Moshe



osric	Nov 14 2009, 08:10 AM Post #11
Advanced Member Posts: 50 Group: Members Member #3,254 Joined: March 15, 2009	A few facts (as opposed to speculation) about Henry E. Langen: Langen was an undercover agent during World War 2. Afterwards he was employed as a Store detective. Before becoming Editor of the American Cryptogram Association's Journal 'The Cryptogram' in 1953 he built up one of the largest code and cipher libraries in the US, writing and publishing numerous articles in both popular and technical magazines. He was appointed by the American Acadamy of Criminology as Instructor to train Chinese police in cryptography and cryptanalysis in 1946. He was 36 years of age in 1954 when he met Byrne. He sounds to me like a competent guy who would ask the right questions and spot a couple of commutators and a power supply if he saw them. Edited by osric, Nov 14 2009, 12:56 PM.



mosher	Nov 14 2009, 04:06 PM Post #12
Member Posts: 41 Group: Moderators Member #3,268 Joined: May 26, 2009	Hi osric, Now that is a real scoop about Langen! How did you uncover this information? Regards, Moshe



osric	Nov 15 2009, 06:23 PM Post #13
Advanced Member Posts: 50 Group: Members Member #3,254 Joined: March 15, 2009	I spent an interesting hour today playing with a machine that uses the plaintext as the key to generate the 1,1,2,4 moves. I had previously built a computer model of such a machine with 3 disks -- 1 control disk (Jeff calls this his KY disk) and 2 enciphering disks. Today I added a 4th disk after a useful discussion with Moshe on GMail chat this morning. This 4th disk moves according to the plaintext just enciphered, and the letter opposite a mark dictates whether the control disk is to move 1,2 or 4 places. The interesting thing is that by judicious selection of the mixed alphabet on the 4th disk, the first 5500 letters of Exhibit 1 can be enciphered without repetition and analysis of the IW of the ciphertext shows no hits at intervals < 9. That's the good news. The bad news is that when trunc is enciphered there are hits < 9 which of course should not be there. I've not yet had time to check whether other key aspects of Chaocipher are duplicated or not. Nor have I had a chance to try modifications to get over the deficiency mentioned. But the purpose of this posting is to illustrate two things: (1) the value of collaboration and (2) that possibly there's mileage in the plaintext key model.



1 user reading this topic (1 Guest and 0 Anonymous)


« Previous Topic · Chaocipher · Next Topic »