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
Lanchester; Revsied version of my virtual cipher machine
Topic Started: Jan 31 2015, 12:51 PM (293 Views)
Innovationgame
Member Avatar
Member
[ *  * ]
In setting this challenge I assume that you have a complete knowledge of the operation of the machine, which I have called Lanchester. To this end, I have provided a detailed description of the operation of the machine. The heart of the machine is a processor and two arrays, a 19 element one serving the purpose of a shift register during encryption and decryption and a 256 element index register containing the actual encryption numbers. Both registers are initially populated with the day settings in the form of 8-bit integers have any value from 0 to 255. Thus, there are 2^2048 possible day settings for the index register and 2^152 possible day settings for the shift register. The message is processed one character at a time in sequence. The processor is a set of software subroutines that manipulate the data as follows:

For encryption, each character is converted to an eight bit ASCII value and an XOR operation is carried out with the selected encryption number, which is located in the index register element indicated by element zero of the shift register. An element-wise RIGHT SHIFT LOGICAL is then performed on the shift register and the result of the XOR inserted in place of the most significant element. The result of the XOR is also used for the enciphered character. This is converted to Hex format and added to the output stream, followed by a space.

For decryption, each hex number is converted to an eight bit ASCII value and an XOR operation is carried out with the selected encryption number, which is located in the index register indicated by element zero of the shift register. An element-wise RIGHT SHIFT LOGICAL is then performed on the shift register and the original enciphered ASCII value inserted in place of the most significant element. The result of the XOR is the ASCII value of the plaintext character. This is converted to Character format and added to the output stream.

Each message has a message header that causes the base position of the register to be changed as follows. The message number indicates the number of rotation operations to be carried out from the base day settings. For each rotation, an element-wise ROTATE RIGHT CIRCULAR operation is performed on the shift register. When the message number reaches 19, the shift register rotation begins again from 0 and an element-wise ROTATE RIGHT CIRCULAR operation is performed on the index register. The message header is initially read from the plain language message to be encrypted. It is then written and read in plain language to and from the encryption file in Hex format. It also appears at the head of the plaintext.

I hope I have provided sufficient information for you to get to work on the challenge. Lanchester was written in VB, mainly because it was useful to use a spreadsheet to monitor the effects of code changes during the various stages of development. If you would like a copy of the VB source code, please PM me your Email address and I will Email it to you. The challenge is to decrypt the message contained in the attached cryptic file. Alternatively, I could attach a text file containing the source code.

Attached to this post:
Attachments: cryptic.txt (4.65 KB)
Edited by Innovationgame, Jan 31 2015, 12:56 PM.
Regards
Innovationgame
Offline Profile Quote Post Goto Top
 
mosher
Super member
[ *  *  *  * ]
Hi Innovationgame,

I cannot promise I'll find the time to tackle your Lanchester challenge, but I would guess it is a good, serious challenge. My contribution at this stage is to request from you a step-by-step encryption of a given plaintext into ciphertext. Thus, you should take a real set of initialization parameters, show how the machine is set up, then explain, step-by-step and in detail, how pt(i) get encrypted into ct(i), for i=0, 1, 2. This will allow a potential solover to verify that his/her understanding of the system is complete and correct.

I did this exact step-by-step description when I described how Chaocipher works and never received a question requesting I explain how it worked. The description was enough for someone to know whether he "got it" or "didn't get it".
Offline Profile Quote Post Goto Top
 
Innovationgame
Member Avatar
Member
[ *  * ]
I'm not entirely sure about how to do this. However, I could attach a file with the complete source code, complete with detailed comments. Would that help?
Regards
Innovationgame
Offline Profile Quote Post Goto Top
 
mosher
Super member
[ *  *  *  * ]
If the source code is compilable, and is in a familiar programming language (e.g., C++, Java) then that should be good enough.
Offline Profile Quote Post Goto Top
 
Innovationgame
Member Avatar
Member
[ *  * ]
It's actually in VB, although I intend to write a FORTRAN version eventually. I'll post it in the morning. I've not quite finished the comments yet.
Regards
Innovationgame
Offline Profile Quote Post Goto Top
 
Innovationgame
Member Avatar
Member
[ *  * ]
I have finished commenting the source code. However, my concern is that, if the cipher is as difficult to break as I think it is then, should it appear in the public domain, it could be used by unscrupulous people for unscrupulous purposes. To that end, I have attached a file showing part of the test output in an Excel spreadsheet for a different message with different day settings.

The first five lines represent the encryption process. The top line is the plain language message and the second the ASCII codes for the first line. The 3rd line contains the values in element zero of the shift register and 4th is the value in the index register indicated by element zero of the shift register. The 5th line is the result of the XOR process and that is converted to to Hex for transmission.

The next five lines represent the decryption process. The 6th line is the decimal value of the input Hex character and the 7th line contains the values in element zero of the shift register. The 8th line is the value in the index register indicated by element zero of the shift register, while the 9th line is the result of the XOR process. When converted back to ASCII characters, this reveals the deciphered plain text shown in line 10.
Attached to this post:
Attachments: sample.txt (736 Bytes)
Regards
Innovationgame
Offline Profile Quote Post Goto Top
 
Innovationgame
Member Avatar
Member
[ *  * ]
I notice that the sample.txt file is not too easy to read. I have added a png file here so that you can see a clearer picture.

For the brute force approach to work you would need a very, VERY fast computer. Assuming it could carry out 2^32 program instructions per second, which would require a clock speed in the order of tens of gigahertz, it would take a long time. There are about 2^25 seconds in a year, so the computer would be able to carry out 2^57 instructions per year. As there are 2^2048 possible combinations for the day settings of index register alone, so you would have to be VERY lucky to hit on the right sequence in a year. So another approach is definitely required.
Attached to this post:
Attachments: Sample.png (33.62 KB)
Regards
Innovationgame
Offline Profile Quote Post Goto Top
 
Innovationgame
Member Avatar
Member
[ *  * ]
There is a chink in the algorithm of the Mk II version of Lanchester, which could lead to a break in the code by using one or more inspired cribs. However, it would still require a considerable amount of brute force, but nothing like trying all the possible day settings. I have used the following notation to describe the process:

The subscript i = the ith encrypted character;
CTi = the ith transmitted cipher text Hex pair
Ci = the decimal value of CTi;
Ri = the value of the index register element used for encrypting or decrypting the ith character
R(j) = the value of the jth element of the index register;
S(j) = the jth element of the shift register;
Si = the value in S(0) for the ith character;
Pi = the ASCII value of the ith plaintext character;
PTi = the ith plaintext character.

The chink lies in the fact that S(18) is topped up with the enciphered character (or at least its ASCII value) after the down shift. So, after 19 or more characters have been transmitted, we know the contents of the S(0)i = Ci-19. Now, at first sight, this does not appear to compromise the cipher because Ci = Pi XOR Ri. However, Ri = R(S(0)i). Now from a crib, we can reverse engineer the value of Ri via Pi (from the crib) XOR Ci. We can then establish that, if the crib is correct, Ri from the crib = R(S(0)i), with S(0)I known. Thus, every time we find that value of S(0)i in the trial solution, the value used to encrypt the original plain language message was Ri from the crib. So it is possible to search through the trial solution and insert the value of Pi and, thus, PTi that would have occurred if the crib was correct. By using this technique, we can punch holes in the encryption, like making holes in a Swiss cheese.
I have attached two example PDF files. These are from the same example that I posted in my last two posts. In each case, the message is displayed as six lines across the page, row after row, with increasing i. The top line is CTi, the next Ci, the third is Si, the fourth Ri, the fifth Pi and the sixth PTi. Both documents are 7 pages long. The crib I have used is “ Lanchester ”, including the spaces before and after the word. You can see in Example 1 that I have used the crib at the first opportunity, starting at CT20. When the results are extrapolated throughout the cipher, there are too many symbols, numbers and unusual letters in the plaintext, suggesting that the position of the crib is incorrect. In Example 2, I have moved on through the cipher text, positioning the start of the crib at CT42. The result now produces realistic values for the plaintext, so it is consistent with the correct positioning of the crib. Trying another crib, such as another occurrence of the word “Lanchester” may reveal further characters in the plaintext. Eventually, sufficient plaintext would be revealed to suggest yet more cribs. However, a considerable amount of brute force is still required.

Note that the sample message is not the challenge and has been encrypted using different message settings, so the solution to the example will not help with the challenge, other than suggesting possible cribs.
Attached to this post:
Attachments: Example_2.pdf (341.1 KB)
Attachments: Example_1.pdf (344.25 KB)
Edited by Innovationgame, Feb 5 2015, 08:22 AM.
Regards
Innovationgame
Offline Profile Quote Post Goto Top
 
Innovationgame
Member Avatar
Member
[ *  * ]
I have addressed the chink in Lanchester MkII and, in any future challenge, I will use Lanchester MKIIA. The difference is that instead of S(18)i+1 = Ci, I have modified the algorithm to S(18)i+1 = Pi XOR S(0)i. This means that the value to be used as S(0)i+19 cannot be determined until Pi has been decrypted. Cribs for Lanchester MkIIA will be much more difficult. However, the current challenge is susceptible to cribs. I tried making progress using “Lanchester” as a crib for the example that I quoted previously, but it I found it difficult to find more cribs. However, as I have already posted the encrypt and decrypt values for the first 60 characters of the example, it is certainly possible to make progress using this. After extrapolating the values of R(S(0)) from the first 60-character crib, I found that several other cribs emerged. The first was “r-g-st-r”, so I used the crib “register”. Others were “ele-en-”, where  represents a space (ASCII 32 decimal) with the crib “element” and “comp—y” with the crib “company”. As more cribs were used to populate the example, yet more cribs emerged until it became clear that it would be possible to decrypt the whole message. A knowledge of past cipher machines helped with “B-D610” knowing that ALVIS was BID 610. This helped with occurrences where “ALVIS” could be used as a crib. So, if you pursue the example that I have already given, it may help get a feel for the technique of using the cribs to decrypt Lanchester messages. To that end, I have re-attached the example as a PDF file with the first two lines filled in as a 60-character crib. Good luck!
Attached to this post:
Attachments: Example_3.pdf (343.8 KB)
Edited by Innovationgame, Feb 7 2015, 11:29 AM.
Regards
Innovationgame
Offline Profile Quote Post Goto Top
 
Innovationgame
Member Avatar
Member
[ *  * ]
I have now posted a full plaintext challenge on my website at http://www.innovationgame.com/cipher/index.html, with a full set of zip files at http://www.innovationgame.com/cipher/source.htm.
Regards
Innovationgame
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
DealsFor.me - The best sales, coupons, and discounts for you
« Previous Topic · Challenges · Next Topic »
Add Reply