Having 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 onto this new type of traffic which
eventually needed Colossus to help the decoding of. This was what later
became called the Lorenz cipher traffic. We covered that it was an
Exclusive-OR kind of cipher
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 with 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-OR.
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
5-hole teleprinter code, as discussed in our video on 5-hole paper tape. Let us take
the letter 'A' and add to it the letter 'Q'. 'A' is 11000
'Q' is 11101. And remember the plus inside a circle means "do a bitwise Exclusive-OR".
So what we'll get is the following, that 1 Exclusive OR'd
with that 1. Exclusive-OR 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: 1 with 1 - another zero - 0 with a 1 and that's 1 ... 0 ... 1
So in fact what's actually happened - and at this stage you have to look back in your handy teleprinter code
sheet - which we'll be putting out a link to this. What on earth is 00101 and the answer is
yes that's right, it's 'H'. That then, if you like, that's one of your plaintext
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 you 'E'. What's happening then here, as 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
plaintext stream. This, of course, is the key stream. In the case of the Lorenz 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 ciphertext stream. 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 an Exclusive-OR
cipher. We've generated a ciphertext character called 'E'
by adding together, under Exclusive-OR conditions, a character 'T' with a character 'Z'.
And you might say well what would happen if I were to add the key character 'Z'
to that once again? OK, so you've got the ciphertext character but deliberately again you
re-key it with the same character 'Z'. You will end up back with 00001 which, of
course, is 'T'.
So in other words this thing almost cycles around. You get 'T' Exclusive-OR'd
with 'Z' gives you an 'E'. 'E' Exclusive-OR'd with 'Z' will give you back 'T', 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 'P' - it's not in single quotes - It's just the plaintext stream: 'A', 'B', 'C', 'T' whatever
- that gets Exclusive-OR'd with the key stream, which I'm going to call K. and we get C, the ciphertext stream. Now - special cases within those
streams that you have to bear in mind: when you come to look at the detail for any
particular plaintext stream, key stream ciphertext stream - one or two very special
cases are so important and here's one of them. If you take any plaintext
character - I'll take 'A' but it could be anything - and you Exclusive-OR it with itself.
Anything Exclusive-OR'd with itself, if it matches, gives zero. 'A' with 'A', or 'B' with 'B, or 'Z' with 'Z' will always give you five beautiful zeroes,
That, nowadays is called the NUL character. Many of you will know even ASCII has got a NUL character. What happens to your terminal if
you send it a NUL character? Well mine just ignores it and I think that's the way most terminals are set up these
days but, yeah, NUL characters were there in teleprinter streams as well. Bletchley
Park certainly did not want a NUL character that was generated to be
ignored and so they invented their own notation, which you have to remember, which says the NUL character is always signalled 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 /
character, the NUL. If you think about it - Exclusive-ORing 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
onto the NUL character is 'A' ; 'K' added on to the NUL character is 'K'. Anything added onto the
NUL character remains itself. So, I'll 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 - Numberphile stuff this! Hope we're not allergic to equations. What I
can do, look, is this: treat it just like a mathematical equation. P + 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 your teacher
used to say "Add x to both sides", or whatever. So, fine, but look what we've just found: any individual
character Exclusive-OR'd with itself gives a NUL.
Any time you combine a NUL 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 NULs Those stream of NULs, when added to the
plaintext just gives you back the plaintext. It doesn't alter anything in the plaintext.
So it's almost like - Exclusive-OR's like a minus 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 carry; it's like
subtraction without borrowing. It's symmetric. So, fine, the K + K cancels out, so in other
words what we can say is if you add the key back to the ciphertext you get the
plaintext. We did an example of that, So far what could be wrong with this? Haha! here's the problem:
suppose Sean sends me the first plaintext message, P1. So instead of P = C + K
I'm gonna write P1 gives me ciphertext one [C1] plus K, and if there was a
second plaintext then that, when added onto K,
gives the second ciphertext. So I'm just rearranging the equation like that P1, P2,
ciphertext one [C1] ciphertext two [C2] gives K on that side. Now do yet another Exclusive-OR
addition between left-hand sides and right-hand sides and what you get is P1 + P2
- Exclusive-OR plus - equals C1 Exclusive-OR'd with C2, Exclusive-OR'd with K, Exclusive-OR'd with K.
Now as we've just discovered that cancels out
K + 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 received and intercepted - don't worry about the key, so long as you know it's the same
key, somehow or other. Just Exclusive-OR the two pieces of ciphertext together.
We'll do that - let's call it D. So C1 Exclusive-OR'd with C2 is D and that must be exactly the same as the two
plaintexts Exclusive-OR'd with each other. So essentially then, it's like a mashup
It's like an Exclusive-OR mashup of two ciphertexts give you exactly the same mashed-up
characters as you would have got by mashing up the two plaintexts together with
Exclusive-OR. Therefore it follows if P1 + P2 is the same as this D, I've invented,
then by shuffling around and adding P2 to both sides, what I'm saying is
if I can guess a piece of plaintext called P2 and I push it through Exclusive-OR with
this D thing - which I'll do for you in a minute - I get a piece of P1 back. So if I get some
plausible plaintext from message number two and if it gives me plausible
plaintext from message number one, then I'm winning because, although they 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.
Sean sent me a 21-character email message with the challenge to break this top
secret cipher but I knew he'd done it like this and I experienced just like in the
war-time incidents - sort of phone him up and say: "Sean my reception apparatus, and my program, wasn't working properly
that ciphertext you just 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 before, that Sean does
not send exactly the same message again but sends a slightly different one,
because that makes things much much simpler, as we'll see later. So if we concentrate
now on this top block of stuff here. Here is
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, it makes it so much easier to read things if it's
broken up in this way, So these spaces that you see, between every five, they're not
really there. They're just to help you read. If you ever do get a genuine word-space
character, and that does exist in the 5-hole code, then Bletchley Park had their
teletypes all wired up to display a 9. And that 9 meant a word-space. Here's the first
ciphertext "W + X A E blah, blah blah blah". Twenty-one characters of it and then I say to Sean "Ooh! Ooh!, I didn't
get it - send it again"
W M J O G D W O and so on. What I can tell from that, straight away, is
that since both ciphertexts started 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 I've shown, of course, that 'W' Exclusive-OR'd with 'W' - a thing with itself - gives the forward
slash [/], the NUL character, So what I've done here between C1 and C2 is what I've just been through
on the theory. Exclusive-OR them and get this magical thing called D - the mashup
that's what I always call it - of the two ciphertexts. 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-OR through the D string and see if anything
sensible comes out for the other plain text. Now, I'm going to start here on this
second block down on P2 - plaintext 2. I'm assuming that Sean was really fed up
with plaintext two, when he had to re-transmit 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 plaintext
two he might have said "Hi space Dave" or something like that. So here you see the 9 for the word-space,
H I 9 D A 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 you see this is where the cryptographers, y'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 HI9DAV
comes back as being HELLO9 in other words HELLO followed by a space. Ah! so in the first one he probably
calls 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 HELLO9DAV push that through the Exclusive-OR and the answer is then
P2 will be HI9 - HI, DAVE, 9 - another space This is looking good so he
was being all informal! He said "Hi Dave" in plaintext 2 and it looks like the start of another
word here - S, But we don't know anything about that yet.
Right, now you have - well, in the 1940s - 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 plaintext 1 ?
"Hello David" - how about that. So we do that -
Hey! look at this! The bottom then comes out to be HI DAVE SEE - S double E
Could it be "See you soon" ? "See you later" ? Who knows? But what we can do is, if we believe
the SEE is right, and is a correct word, we promote that up to the top line and make it be: HELLO DAVID SEE
put through an Exclusive-OR it comes down on the lower line, on the second plaintext line
HI DAVE SEE YOU Wahay!! 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 through 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 L so almost certainly that 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 ciphertext 2. We've worked out plaintext 2, Plaintext 2
plus ciphertext 2 will give you the key. And here it is. Was it generated by a machine? No - I made it up!
But here it is and that's the moment at which you say "That's fantastic, we can start to work out.
now, exactly what that wretched machine might be doing that's generating this
pseudo-random key."