C-52 (cipher machine)

Transcription

This is the structure of the machine. Each letter of the message would be divided into 5 bits, and those would be XOR'd with the value coming from the corresponding K wheel. These wheels would rotate with each letter, and at each position they either had a 0 or a 1, depending on whether there was a pin in that position or not. Each wheel had a different size. The last one had 23. The first one had 41. They were different-sized wheels. This would also be XOR'd with the result from the S wheels, which worked similarly. They also had positions that were either 0s or 1s around the wheels. The different was the K wheels turned every character. The S wheels only turned conditionally on the result of 2 other wheels, which were the M wheels. The M1 wheel would turn every time. The M2 wheel would rotate depending on the value of the M1 wheel and depending on the XOR of those, either all the S wheels would rotate by 1 or none of them would. Then the result of all these XORs is the cipher text. The is similar to the idea behind a one-time pat. We're XORing message with key. But the key is not a perfectly random sequence. It's the key generated by this machine. To break the cipher, once you knew the structure of the machine, that's not enough. You need to know the initial configuration. Here's the intercepted message that was intercepted over the radio. We can think of all the characters in the message. The important thing to remember about the Lorenz cipher is that the message encoding each character--each character is encoded into 5 bits, using the Baudot code. The cipher text is in these same sequences where each cipher text bit corresponds to one bit of that letter. The next one corresponds to the next bit of that letter. We can think of the cipher text being broken into channels corresponding to each part of the letter. That means each channel would be the sequences that repeat every 5. This would be part of the first letter, part of the first letter. This would be the second part of the first letter. This would be the second part of the second letter. And this would be the third part of the first letter. This would be the third part of the second letter and so on. We can think of each of these as a separate channel. What we're going to do is use a new notation. We're going to subscript Z by channel and the letter for that channel. Zc sub i is the ith letter for channel c. In terms of this mapping, if we look at channel 0, that's going to be Z0, Z5, Z10. We can just break the cipher text up into channels. The key reason for doing this is because of this weakness that was noticed in the cipher. The key weakness is that all these S wheels move in turn. Either when we advance one position they're the same for all the channels or they advance by one for all the channels. The value of each of these depends on the message. It also depends on the outputs of the K wheels, and it is also XOR'd without outputs of the S wheels. By separating it into those three pieces, we're going to be able to take advantage of the properties that they have. The key insight is that the S wheels don't always turn. If we look at subsequent characters, there's a good chance that the S wheels have not changed. We're going to define ΔZ sub c, i as the difference between 2 subsequent characters in the cipher text for that channel. That's XOR'd with Zc of i plus 1. Now because this is for that channel, these are five-characters apart in the intercepted cipher text, but they're adjacent for that channel. What happens when we look at these values for two different channels? We're going to look at channel 0, and we're going to XOR that with the delta value for channel 1. Plugging in the definitions, that's just the result of Z XORing all of these values. Where this becomes valuable is because we can break these down into the three parts. Let's break them own into parts, separating the M, the K, and the S parts that combined into this cipher text. What we get is these three things. For the message bits we have the XORs of all the message bits for the two channels adjacent and the key bits XOR'd with the message bits. Then we have this for the S bits as well. I want to ask a brief quiz here. For each of these combinations--this is Δm, ΔK, and ΔS. Supposing we could separate each of those, the question is which of these inequalities are likely to be true. Each one we're asking whether the probability of that part being 0 is greater than 1/2. If it was a uniform distribution, the probability would be equal to 1/2. If it's not uniformly distributed, then the probability could be less than or greater than 1/2. I'm asking here are there any of these that we can be confident-- or at least have a good likelihood --that the probability of the delta for the component is equal to zero. Let me remind you what the components are. The message is text in a language, and in this case it's in the language German. These are the K wheels. Each wheel rotates with every character. They have pins around the wheels deciding if it's a 0 or a 1. These are the S wheels. The S wheels rotate only when the output of the M wheels is a 1. Sometimes they don't rotate at all. Sometimes they all rotate at the same time.