The Art of Cryptanalysis: A Step-by-Step Guide to Decoding Ciphers

The story begins with a seemingly innocuous task - decoding a ciphertext. The sender, Sean, had sent an encrypted message to the recipient, using a cipher that seemed straightforward enough. However, as the recipient delved into deciphering the code, they realized that it was more complex than initially thought. The message consisted of 21 characters, with each character being a combination of the exclusive-or (XOR) operation and a word space.

The first step in decoding the message was to understand the properties of the cipher text. As Sean pointed out, both ciphertexts started with a "W" and used the same key, indicating that they were derived from the same plaintext. The recipient realized that this meant that they could use a process called "exclusive all" to combine the two ciphertexts into a single, mangled message.

By applying the exclusive all operation, the recipient was able to identify a pattern in the message. They noticed that certain characters, such as the letter "W", were repeated and seemed to be used as null characters to separate different words or phrases. The recipient then applied another technique called "D-mashing" - combining two ciphertexts in a way that allowed them to extract meaningful information from the mangled text.

Using this process, the recipient was able to generate several plausible pieces of plaintext. They started with the first block and guessed that Sean had used informal language in his email. The result was a message that read "hello Dave". However, as they continued working on the second block, it became clear that Sean was using more formal language. The correct output for this part of the ciphertext was "see you soon".

The recipient's success with decoding the message led them to apply their new technique to an even longer ciphertext. They successfully decoded a phrase that read "hello David see". However, they realized that they needed to be cautious in their assumptions and consider alternative explanations.

As the recipient continued working on the longer ciphertext, they began to suspect that Sean might have used more formal language in his email from the beginning. The result of this new attempt was a message that read "see you later". This phrase is well-known, and the recipient realized that it was likely what Sean had intended to convey.

The real breakthrough came when the recipient applied their decoding technique to an equation they had written earlier. By using the decoded plaintext from one part of the ciphertext, they were able to deduce the key used in the cipher. The result was a pseudo-random key, which was generated by machine - although it was not clear if the actual machine used in Bletchley Park's cryptanalysis efforts was identical.

The recipient realized that their technique had limitations and would only work for shorter messages. However, they had successfully decoded a significant portion of the ciphertext using exclusive all and D-mashing. This marked an important milestone in the development of cryptanalysis techniques and paved the way for further research into deciphering complex ciphers.

"WEBVTTKind: captionsLanguage: enhaving first of all been to Bletchley Park I hope most of you have seen that episode which is out there already we also recorded some stuff about how the listening services the Y stations got on to this new type of traffic which eventually needed Colossus to help the decoding off this was this what later became called the Lorentz cypher traffic we covered that it was an exclusive all kind of cypher and that lots of it was picked up at listening stations and sent back to Bletchley Park they knew that this kind of cipher was very vulnerable to attack if any of the German operators ever disobeyed orders and sent out more than one message using exactly the same key settings on this Lorenz cipher machine and preferably it would be good if the naughty German operator sent out two long messages were the same key because then a very special technique could be used to try and disentangle what these messages were without even needing to know the key at all now that's an amazing property of exclusive all you could perhaps even say it was a weakness or a flaw but in wanting to explain to you exactly how this worked I thought we'd better do it first of all with a simple example if I take the letter A and don't forget we're using five whole teleprinter code as discussed in our video on five l paper to let us take the letter A and add to it the letter Q a is 1 1 0 0 0 Q is 1 1 1 0 1 and remember the plus inside a circle means do a bitwise exclusive all so what we'll get is the following that one exclusive order that one exclusive all says if it's the same thing you're combining then the answer is 0 if they're different it's a 1 so what this comes out to be then one with one another 0 zero with a 1 that's 1 0 1 so in fact what actually happened and at this stage you have to look back in your handi teleprinter code sheet which will be putting out a link to this what on earth is zero zero 101 and the answer is yes that's right it's H that then if you like that's one of your plain text characters this could be a key character supplied by the Lorenz machine it's been randomly generated somehow it goes without saying that people at Bletchley Park doing this stuff didn't even need to deliberately commit this stuff to memory they just knew it after hours and hours and hours they just knew that T combined with Z gave Yui what's happening then here if you take successive plaintext letters successive randomly generated you hope key letters is that you're ending up with a sequence of plaintext letters I'll call this the plain text stream this of course is the key stream in the case of the lorentz cipher machine it's pseudo randomly generated it was not mathematically totally random of course there would be a repeat cycle but good enough to be called pseudo-random out here of course you end up with a shaft extreme one thing that perhaps I should remind you of if you're not aware of it already is the sort of self reciprocal nature of an exclusive or system and exclusive or cipher we've generated a cipher text character called e by adding together under exclusive all conditions a character T with a character Zed you might say well what would happen if I were to add the key character Z to that once again okay so you've got the subjects character but deliberately again you rekey it with the same character Zed you will end up back with 0 0 0 0 1 which of course is T so in other words this thing almost cycles round you can add T exclusive all is Zed give you an E he exclusive order where Zed would give you bhakti and so on what we can now say is let's try and find the weakness in this cipher because it's been known about ever since Victorian times since the late 19th century you start off saying the following I'm just going to call the plaintext stream of characters P it's not the character B it's not in single quotes it's just the plain text string ABC T whatever that gets exclusive Ord with the key stream which I'm going to call K and we get C fine the cipher text string now special cases within those streams that you have to bear in mind when you come to look at the detail for any particular plant extreme key stream shaft extreme one or two very special cases are so important and here's one of them if you take any plain text character I'll take a it could be anything and your exclusive or it with itself anything exclusive order itself if it matches gives zero a with a or B with B or said with said will always give you five beautiful zeros that nowadays is called a null character many of you will know even ASCII has got a null character what happens to your terminal if you send it to null character well mine just ignores it I think that's the way most journals are set up these days but ya know characters were there in teleprinter streams as well Bletchley Park certainly did not want a null character that was generated to be ignored and so they invented their own notation which you have to remember which says the null character is always signaled by a forward slash what's the other special case then the other special case is if you ever get to a situation of combining shall we say the letter A with the slash character than now if you think about it exclusive or wearing any of those zeros with whatever pattern a is it's like adding 0 in other words it leaves the a totally unchanged so a added on to the null character is a K added on to the null character is K and thing added on to the null character remains itself so I put a box around these and let's just bear those in mind for later on where's the problem come then ok let's first of all take this equation number file stuff this hope we're not allergic to equations what I can do look is this treated just like a mathematical equation B plus K on the left I'm now going to add on another K to that and that doesn't matter it won't change anything so long as I also add on K to the right basically like you teach you to say add X to both sides and or whatever so fine but look what we've just found any individual character exclusive o'red with itself gives a know anytime you combine a null with any character it gives any character back again in the more general case therefore K plus K adding together identical cipher key letters will give you a stream of nulls those stream of nulls when added to the plaintext just gives you about the plaintext it doesn't alter anything in the plaintext so it's almost like exclusive always like a - sometimes it's like K minus K it's a zero it cancels out yeah exclusive or is weird like that it's like addition without Cary it's like subtraction without borrowing its symmetric so fine the k plus K cancels out so in other words what we can say is if you add the key back to the cipher text you get the plaintext we did an example of that so far what could be wrong with this haha here's the problem suppose Shawn sends me the first plaintext message p1 so instead of P is C plus K I'm going to write p1 gives me ciphertext 1 plus K and if there was a second plaintext then that when added on to K gives the second ciphertext so I'm just rearranging the equation like that p1 p2 suffix 1 suffix to okay on that side now do yet another exclusive or addition between left hand sides and right hand sides and what you get is p1 plus p2 exclusive or plus equals c1 exclusive or with c2 exclusive or with K exclusive water with K now as we've just discovered that cancels out k plus K you can ignore it so the net result of all of this is as follows if you send two separate messages using exactly the same key the key cancels out and what you end up with is something where if you were to take the ciphertext that you've received and intercepted don't worry about the key as long as you know it's the same key somehow or other just exclusive or two pieces of ciphertext together we'll do that let's call it D so C 1 exclusive or C 2 is d and that must be exactly the same as the two plain texts exclusive Ord with each other so essentially then it's like a mashup it's like an exclusive or mash-up of two cipher texts gives you exactly the same mashed-up characters as you would have got by mashing up the two plaintext together with exclusive or therefore it follows if p1 plus p2 is the same as this D I've invented then by shuffling around and adding P 2 to both sides what I'm saying is if I can guess a piece of plain text called p2 and I push it through exclusive or with this D thing which I'll do for in a minute I'll get a piece of p1 back so if I get some plausible plain text from message number 2 and if it gives me plausible plain text for message number 1 then I'm winning because well then it might be slightly different a piece of good sense in one of them might give you something you recognize in the other well there's nothing like a real-life example to make this come alive and make you believe it really does work sure sent me a 21 character email message with a challenge to break this top-secret cipher but I knew he'd done it like this and I experienced just like in the water I'm incident sort of phone him up and sent Shawn my reception apparatus and my program wasn't working properly that ciphertext user sent me didn't seem to work at all something's gone wrong can you send it to me again and once again you hope like in the war that Shawn does not send exactly the same message again but since it's slightly different one because that makes things much much simpler as well see later so if we concentrate now on this top block of stuff here here's ciphertext one just as in good old wartime Morse code tradition I'm breaking this string of characters up into blocks of five that was traditional because of course he makes it so much easier to read things if it's broken up in this way so these are spaces that you see between every five they're not really there they just to help you read if you ever do get a genuine word space character and that does exist in the five whole code then Bletchley Park had their teletypes all wired up to display a nine and that nine men a word space here's the first ciphertext W plus X a a blah blah blah 21 characters of it and then I say to Sean oh whoa I didn't get it send it to game wmj OG d wo and so on what I can tell from that straightaway is that since both cypher text starting with a w and since they use the same key then I don't at the moment know what the plaintext letter was that started them but I know it was the same in both cases now as shown of course look W exclusive order W thing with itself gives the /a null character so what I've done here between c1 and c2 is what I've just been through on the theory exclusive all of them and get this magical thing called D mashup that's what I always call it of the two ciphertex now successively on either side of the mashed up ciphertexts write down what you think is a plausible piece of plain text and push that back with exclusive all through the D string and see if anything sensible comes out for the other plain text now when to start here on the second block down on P to plain text - I'm assuming that Sean was really fed up with plain text - and he had to retransmit it and all of his politeness will have left him he will have started the second email message with either a grunt or maybe just a brief hi that's my guess anyway so I'm guessing that in plain text - he might have said hi space Dave or something like that so here you see the nine for the word space hi9 da V push all of that line upwards through the corresponding character combining them with exclusive or what comes out and the answer is hello oh I like that now see this is where the cryptographers you know heartbreak and joy if you get it right it's wonderful but if you make the wrong guess you've got to back off and try something different very frustrating strangely in this example I seem to be making all the right guesses so high nine Daffy comes back and be hello nine in other words hello fall no space ah so in the first one he probably called me Dave as well maybe not sure but we can at least take the DAV here and promote it to the top line and next time around we say if p1 is hello 9 Daffy push that through the exclusive-or and the answer is then pizza will be hi9 hi Dave 9 another space this is looking good sir we was being all informal is then hi Dave in text oh honey looks like the start of another world here yes but we don't know anything about that yet right now you have well in 1940 several cigarettes many more cups of coffee now where do we go from here could it be the case that Sean is using formal language in plain text one hello David how about so we do that Hey look at this the bottom then comes out to be hi Dave see SWE could it be see you soon see you later who knows but what we can do is if we believe that C is right and is a great word we promote that up to the top line and make it be hello David see but through an exclusive all comes down on the lower line on the second plain text Ben hi Dave see you weigh bingo you he did he said hi Dave see you now there's a well-known English phrase see you later so we try of course late down here propagate that back up to exclusive-or and you get the word you separated with spaces this is a fabulous method of course it will only work for as long as the shorter message doesn't run out I can only guess that at the top message which is a bit longer it starts with our so almost certainly about one would have said later as well but we've triumphed and where the real triumph comes is for these 21 characters you can now go back to one of the equations I wrote down for you and say we've got cipher text - we've worked out plain text to plain text 2 plus cipher text 2 will give you the key and here it is was it generated by machine no I made it up but there it is and that's the moment of what you said oh that's fantastic we can start to work out now exactly what that wretched machine might be doing that's generating the pseudo-random key you start trying to run two tapes simultaneously through a piece of bespoke electronics which they invented which will do the merging but you must keep them in exact sync you do not want differential stretching between the two thingshaving first of all been to Bletchley Park I hope most of you have seen that episode which is out there already we also recorded some stuff about how the listening services the Y stations got on to this new type of traffic which eventually needed Colossus to help the decoding off this was this what later became called the Lorentz cypher traffic we covered that it was an exclusive all kind of cypher and that lots of it was picked up at listening stations and sent back to Bletchley Park they knew that this kind of cipher was very vulnerable to attack if any of the German operators ever disobeyed orders and sent out more than one message using exactly the same key settings on this Lorenz cipher machine and preferably it would be good if the naughty German operator sent out two long messages were the same key because then a very special technique could be used to try and disentangle what these messages were without even needing to know the key at all now that's an amazing property of exclusive all you could perhaps even say it was a weakness or a flaw but in wanting to explain to you exactly how this worked I thought we'd better do it first of all with a simple example if I take the letter A and don't forget we're using five whole teleprinter code as discussed in our video on five l paper to let us take the letter A and add to it the letter Q a is 1 1 0 0 0 Q is 1 1 1 0 1 and remember the plus inside a circle means do a bitwise exclusive all so what we'll get is the following that one exclusive order that one exclusive all says if it's the same thing you're combining then the answer is 0 if they're different it's a 1 so what this comes out to be then one with one another 0 zero with a 1 that's 1 0 1 so in fact what actually happened and at this stage you have to look back in your handi teleprinter code sheet which will be putting out a link to this what on earth is zero zero 101 and the answer is yes that's right it's H that then if you like that's one of your plain text characters this could be a key character supplied by the Lorenz machine it's been randomly generated somehow it goes without saying that people at Bletchley Park doing this stuff didn't even need to deliberately commit this stuff to memory they just knew it after hours and hours and hours they just knew that T combined with Z gave Yui what's happening then here if you take successive plaintext letters successive randomly generated you hope key letters is that you're ending up with a sequence of plaintext letters I'll call this the plain text stream this of course is the key stream in the case of the lorentz cipher machine it's pseudo randomly generated it was not mathematically totally random of course there would be a repeat cycle but good enough to be called pseudo-random out here of course you end up with a shaft extreme one thing that perhaps I should remind you of if you're not aware of it already is the sort of self reciprocal nature of an exclusive or system and exclusive or cipher we've generated a cipher text character called e by adding together under exclusive all conditions a character T with a character Zed you might say well what would happen if I were to add the key character Z to that once again okay so you've got the subjects character but deliberately again you rekey it with the same character Zed you will end up back with 0 0 0 0 1 which of course is T so in other words this thing almost cycles round you can add T exclusive all is Zed give you an E he exclusive order where Zed would give you bhakti and so on what we can now say is let's try and find the weakness in this cipher because it's been known about ever since Victorian times since the late 19th century you start off saying the following I'm just going to call the plaintext stream of characters P it's not the character B it's not in single quotes it's just the plain text string ABC T whatever that gets exclusive Ord with the key stream which I'm going to call K and we get C fine the cipher text string now special cases within those streams that you have to bear in mind when you come to look at the detail for any particular plant extreme key stream shaft extreme one or two very special cases are so important and here's one of them if you take any plain text character I'll take a it could be anything and your exclusive or it with itself anything exclusive order itself if it matches gives zero a with a or B with B or said with said will always give you five beautiful zeros that nowadays is called a null character many of you will know even ASCII has got a null character what happens to your terminal if you send it to null character well mine just ignores it I think that's the way most journals are set up these days but ya know characters were there in teleprinter streams as well Bletchley Park certainly did not want a null character that was generated to be ignored and so they invented their own notation which you have to remember which says the null character is always signaled by a forward slash what's the other special case then the other special case is if you ever get to a situation of combining shall we say the letter A with the slash character than now if you think about it exclusive or wearing any of those zeros with whatever pattern a is it's like adding 0 in other words it leaves the a totally unchanged so a added on to the null character is a K added on to the null character is K and thing added on to the null character remains itself so I put a box around these and let's just bear those in mind for later on where's the problem come then ok let's first of all take this equation number file stuff this hope we're not allergic to equations what I can do look is this treated just like a mathematical equation B plus K on the left I'm now going to add on another K to that and that doesn't matter it won't change anything so long as I also add on K to the right basically like you teach you to say add X to both sides and or whatever so fine but look what we've just found any individual character exclusive o'red with itself gives a know anytime you combine a null with any character it gives any character back again in the more general case therefore K plus K adding together identical cipher key letters will give you a stream of nulls those stream of nulls when added to the plaintext just gives you about the plaintext it doesn't alter anything in the plaintext so it's almost like exclusive always like a - sometimes it's like K minus K it's a zero it cancels out yeah exclusive or is weird like that it's like addition without Cary it's like subtraction without borrowing its symmetric so fine the k plus K cancels out so in other words what we can say is if you add the key back to the cipher text you get the plaintext we did an example of that so far what could be wrong with this haha here's the problem suppose Shawn sends me the first plaintext message p1 so instead of P is C plus K I'm going to write p1 gives me ciphertext 1 plus K and if there was a second plaintext then that when added on to K gives the second ciphertext so I'm just rearranging the equation like that p1 p2 suffix 1 suffix to okay on that side now do yet another exclusive or addition between left hand sides and right hand sides and what you get is p1 plus p2 exclusive or plus equals c1 exclusive or with c2 exclusive or with K exclusive water with K now as we've just discovered that cancels out k plus K you can ignore it so the net result of all of this is as follows if you send two separate messages using exactly the same key the key cancels out and what you end up with is something where if you were to take the ciphertext that you've received and intercepted don't worry about the key as long as you know it's the same key somehow or other just exclusive or two pieces of ciphertext together we'll do that let's call it D so C 1 exclusive or C 2 is d and that must be exactly the same as the two plain texts exclusive Ord with each other so essentially then it's like a mashup it's like an exclusive or mash-up of two cipher texts gives you exactly the same mashed-up characters as you would have got by mashing up the two plaintext together with exclusive or therefore it follows if p1 plus p2 is the same as this D I've invented then by shuffling around and adding P 2 to both sides what I'm saying is if I can guess a piece of plain text called p2 and I push it through exclusive or with this D thing which I'll do for in a minute I'll get a piece of p1 back so if I get some plausible plain text from message number 2 and if it gives me plausible plain text for message number 1 then I'm winning because well then it might be slightly different a piece of good sense in one of them might give you something you recognize in the other well there's nothing like a real-life example to make this come alive and make you believe it really does work sure sent me a 21 character email message with a challenge to break this top-secret cipher but I knew he'd done it like this and I experienced just like in the water I'm incident sort of phone him up and sent Shawn my reception apparatus and my program wasn't working properly that ciphertext user sent me didn't seem to work at all something's gone wrong can you send it to me again and once again you hope like in the war that Shawn does not send exactly the same message again but since it's slightly different one because that makes things much much simpler as well see later so if we concentrate now on this top block of stuff here here's ciphertext one just as in good old wartime Morse code tradition I'm breaking this string of characters up into blocks of five that was traditional because of course he makes it so much easier to read things if it's broken up in this way so these are spaces that you see between every five they're not really there they just to help you read if you ever do get a genuine word space character and that does exist in the five whole code then Bletchley Park had their teletypes all wired up to display a nine and that nine men a word space here's the first ciphertext W plus X a a blah blah blah 21 characters of it and then I say to Sean oh whoa I didn't get it send it to game wmj OG d wo and so on what I can tell from that straightaway is that since both cypher text starting with a w and since they use the same key then I don't at the moment know what the plaintext letter was that started them but I know it was the same in both cases now as shown of course look W exclusive order W thing with itself gives the /a null character so what I've done here between c1 and c2 is what I've just been through on the theory exclusive all of them and get this magical thing called D mashup that's what I always call it of the two ciphertex now successively on either side of the mashed up ciphertexts write down what you think is a plausible piece of plain text and push that back with exclusive all through the D string and see if anything sensible comes out for the other plain text now when to start here on the second block down on P to plain text - I'm assuming that Sean was really fed up with plain text - and he had to retransmit it and all of his politeness will have left him he will have started the second email message with either a grunt or maybe just a brief hi that's my guess anyway so I'm guessing that in plain text - he might have said hi space Dave or something like that so here you see the nine for the word space hi9 da V push all of that line upwards through the corresponding character combining them with exclusive or what comes out and the answer is hello oh I like that now see this is where the cryptographers you know heartbreak and joy if you get it right it's wonderful but if you make the wrong guess you've got to back off and try something different very frustrating strangely in this example I seem to be making all the right guesses so high nine Daffy comes back and be hello nine in other words hello fall no space ah so in the first one he probably called me Dave as well maybe not sure but we can at least take the DAV here and promote it to the top line and next time around we say if p1 is hello 9 Daffy push that through the exclusive-or and the answer is then pizza will be hi9 hi Dave 9 another space this is looking good sir we was being all informal is then hi Dave in text oh honey looks like the start of another world here yes but we don't know anything about that yet right now you have well in 1940 several cigarettes many more cups of coffee now where do we go from here could it be the case that Sean is using formal language in plain text one hello David how about so we do that Hey look at this the bottom then comes out to be hi Dave see SWE could it be see you soon see you later who knows but what we can do is if we believe that C is right and is a great word we promote that up to the top line and make it be hello David see but through an exclusive all comes down on the lower line on the second plain text Ben hi Dave see you weigh bingo you he did he said hi Dave see you now there's a well-known English phrase see you later so we try of course late down here propagate that back up to exclusive-or and you get the word you separated with spaces this is a fabulous method of course it will only work for as long as the shorter message doesn't run out I can only guess that at the top message which is a bit longer it starts with our so almost certainly about one would have said later as well but we've triumphed and where the real triumph comes is for these 21 characters you can now go back to one of the equations I wrote down for you and say we've got cipher text - we've worked out plain text to plain text 2 plus cipher text 2 will give you the key and here it is was it generated by machine no I made it up but there it is and that's the moment of what you said oh that's fantastic we can start to work out now exactly what that wretched machine might be doing that's generating the pseudo-random key you start trying to run two tapes simultaneously through a piece of bespoke electronics which they invented which will do the merging but you must keep them in exact sync you do not want differential stretching between the two things\n"