馃攳
Zig Zag Decryption - Computerphile - YouTube
Channel: Computerphile
[0]
having first of all been to Bletchley
[2]
Park I hope most of you have seen that
[4]
episode which is out there already we
[6]
also recorded some stuff about how the
[10]
listening services the Y stations got on
[13]
to this new type of traffic which
[15]
eventually needed Colossus to help the
[18]
decoding off this was this what later
[21]
became called the Lorentz cypher traffic
[24]
we covered that it was an exclusive all
[26]
kind of cypher and that lots of it was
[29]
picked up at listening stations and sent
[31]
back to Bletchley Park they knew that
[36]
this kind of cipher was very vulnerable
[37]
to attack if any of the German operators
[41]
ever disobeyed orders and sent out more
[45]
than one message using exactly the same
[47]
key settings on this Lorenz cipher
[51]
machine and preferably it would be good
[53]
if the naughty German operator sent out
[58]
two long messages were the same key
[60]
because then a very special technique
[62]
could be used to try and disentangle
[66]
what these messages were without even
[68]
needing to know the key at all now
[70]
that's an amazing property of exclusive
[72]
all you could perhaps even say it was a
[75]
weakness or a flaw but in wanting to
[78]
explain to you exactly how this worked
[80]
I thought we'd better do it first of all
[83]
with a simple example if I take the
[86]
letter A and don't forget we're using
[88]
five whole teleprinter code as discussed
[91]
in our video on five l paper to let us
[96]
take the letter A and add to it the
[100]
letter Q a is 1 1 0 0 0 Q is 1 1 1 0 1
[108]
and remember the plus inside a circle
[111]
means do a bitwise exclusive all so what
[115]
we'll get is the following that one
[117]
exclusive order that one exclusive all
[120]
says if it's the same thing you're
[122]
combining then the answer is 0 if
[125]
they're different it's a 1 so what this
[127]
comes out to be then one with one
[130]
another 0
[132]
zero with a 1 that's 1 0 1 so in fact
[138]
what actually happened and at this stage
[141]
you have to look back in your handi
[144]
teleprinter code sheet which will be
[146]
putting out a link to this what on earth
[148]
is zero zero 101 and the answer is yes
[151]
that's right it's H that then if you
[154]
like that's one of your plain text
[156]
characters this could be a key character
[159]
supplied by the Lorenz machine it's been
[161]
randomly generated somehow it goes
[164]
without saying that people at Bletchley
[165]
Park doing this stuff didn't even need
[168]
to deliberately commit this stuff to
[170]
memory they just knew it after hours and
[173]
hours and hours they just knew that T
[175]
combined with Z gave Yui what's
[179]
happening then here if you take
[181]
successive plaintext letters successive
[183]
randomly generated you hope key letters
[186]
is that you're ending up with a sequence
[188]
of plaintext letters I'll call this the
[190]
plain text stream this of course is the
[194]
key stream in the case of the lorentz
[196]
cipher machine it's pseudo randomly
[199]
generated it was not mathematically
[202]
totally random of course there would be
[203]
a repeat cycle but good enough to be
[206]
called pseudo-random out here of course
[208]
you end up with a shaft extreme one
[211]
thing that perhaps I should remind you
[215]
of if you're not aware of it already is
[218]
the sort of self reciprocal nature of an
[224]
exclusive or system and exclusive or
[226]
cipher we've generated a cipher text
[229]
character called e by adding together
[231]
under exclusive all conditions a
[233]
character T with a character Zed you
[236]
might say well what would happen if I
[238]
were to add the key character Z to that
[244]
once again okay so you've got the
[247]
subjects character but deliberately
[249]
again you rekey it with the same
[251]
character Zed you will end up back with
[253]
0 0 0 0 1 which of course is T so in
[260]
other words this thing almost cycles
[262]
round you can add T exclusive all is Zed
[265]
give you an E
[266]
he exclusive order where Zed would give
[268]
you bhakti and so on what we can now say
[271]
is let's try and find the weakness in
[274]
this cipher because it's been known
[276]
about ever since Victorian times since
[278]
the late 19th century you start off
[280]
saying the following I'm just going to
[283]
call the plaintext stream of characters
[285]
P it's not the character B it's not in
[287]
single quotes it's just the plain text
[289]
string ABC T whatever that gets
[293]
exclusive Ord with the key stream which
[296]
I'm going to call K and we get C fine
[299]
the cipher text string now special cases
[302]
within those streams that you have to
[305]
bear in mind when you come to look at
[307]
the detail for any particular plant
[309]
extreme key stream shaft extreme one or
[312]
two very special cases are so important
[314]
and here's one of them if you take any
[317]
plain text character I'll take a it
[319]
could be anything and your exclusive or
[321]
it with itself anything exclusive order
[324]
itself if it matches gives zero a with a
[327]
or B with B or said with said will
[329]
always give you five beautiful zeros
[333]
that nowadays is called a null character
[336]
many of you will know even ASCII has got
[338]
a null character what happens to your
[340]
terminal if you send it to null
[341]
character well mine just ignores it I
[343]
think that's the way most journals are
[345]
set up these days but ya know characters
[347]
were there in teleprinter streams as
[349]
well Bletchley Park certainly did not
[351]
want a null character that was generated
[354]
to be ignored and so they invented their
[357]
own notation which you have to remember
[359]
which says the null character is always
[361]
signaled by a forward slash what's the
[364]
other special case then the other
[365]
special case is if you ever get to a
[368]
situation of combining shall we say the
[371]
letter A with the slash character than
[376]
now if you think about it exclusive or
[379]
wearing any of those zeros with whatever
[381]
pattern a is it's like adding 0 in other
[385]
words it leaves the a totally unchanged
[387]
so a added on to the null character is a
[390]
K added on to the null character is K
[393]
and
[394]
thing added on to the null character
[396]
remains itself so I put a box around
[398]
these and let's just bear those in mind
[400]
for later on where's the problem come
[403]
then ok let's first of all take this
[406]
equation number file stuff this hope
[410]
we're not allergic to equations what I
[412]
can do look is this treated just like a
[414]
mathematical equation B plus K on the
[417]
left I'm now going to add on another K
[420]
to that and that doesn't matter it won't
[423]
change anything so long as I also add on
[426]
K to the right basically like you teach
[428]
you to say add X to both sides and or
[431]
whatever so fine but look what we've
[436]
just found any individual character
[438]
exclusive o'red with itself gives a know
[441]
anytime you combine a null with any
[443]
character
[444]
it gives any character back again in the
[447]
more general case therefore K plus K
[450]
adding together identical cipher key
[453]
letters will give you a stream of nulls
[455]
those stream of nulls when added to the
[457]
plaintext just gives you about the
[459]
plaintext it doesn't alter anything in
[461]
the plaintext so it's almost like
[465]
exclusive always like a - sometimes it's
[467]
like K minus K it's a zero it cancels
[470]
out yeah exclusive or is weird like that
[473]
it's like addition without Cary it's
[475]
like subtraction without borrowing its
[478]
symmetric so fine the k plus K cancels
[481]
out so in other words what we can say is
[483]
if you add the key back to the cipher
[486]
text you get the plaintext we did an
[488]
example of that so far what could be
[490]
wrong with this haha here's the problem
[493]
suppose Shawn sends me the first
[498]
plaintext message
[499]
p1 so instead of P is C plus K I'm going
[502]
to write p1 gives me ciphertext 1 plus K
[507]
and if there was a second plaintext then
[510]
that when added on to K gives the second
[513]
ciphertext so I'm just rearranging the
[515]
equation like that p1 p2 suffix 1 suffix
[520]
to okay
[521]
on that side now do yet another
[524]
exclusive or addition between left hand
[528]
sides and right hand sides and what you
[532]
get is p1 plus p2 exclusive or plus
[537]
equals c1 exclusive or with c2 exclusive
[545]
or with K exclusive water with K now as
[550]
we've just discovered that cancels out k
[554]
plus K you can ignore it so the net
[556]
result of all of this is as follows if
[559]
you send two separate messages using
[562]
exactly the same key the key cancels out
[566]
and what you end up with is something
[569]
where if you were to take the ciphertext
[572]
that you've received and intercepted
[574]
don't worry about the key as long as you
[577]
know it's the same key somehow or other
[578]
just exclusive or two pieces of
[581]
ciphertext together we'll do that let's
[584]
call it D so C 1 exclusive or C 2 is d
[587]
and that must be exactly the same as the
[594]
two plain texts exclusive Ord with each
[597]
other so essentially then it's like a
[600]
mashup
[601]
it's like an exclusive or mash-up of two
[603]
cipher texts gives you exactly the same
[605]
mashed-up characters as you would have
[608]
got by mashing up the two plaintext
[610]
together with exclusive or therefore it
[614]
follows if p1 plus p2 is the same as
[618]
this D I've invented then by shuffling
[622]
around and adding P 2 to both sides what
[625]
I'm saying is if I can guess a piece of
[628]
plain text called p2 and I push it
[630]
through exclusive or with this D thing
[633]
which I'll do for in a minute I'll get a
[635]
piece of p1 back so if I get some
[638]
plausible plain text from message number
[640]
2 and if it gives me plausible plain
[643]
text for message number 1 then I'm
[646]
winning because well then it might be
[647]
slightly different a piece of good sense
[650]
in one of them might give you something
[652]
you recognize in
[652]
the other well there's nothing like a
[654]
real-life example to make this come
[656]
alive and make you believe it really
[658]
does work sure sent me a 21 character
[662]
email message with a challenge to break
[665]
this top-secret cipher but I knew he'd
[667]
done it like this and I experienced just
[670]
like in the water I'm incident sort of
[672]
phone him up and sent Shawn my reception
[674]
apparatus and my program wasn't working
[676]
properly that ciphertext user sent me
[679]
didn't seem to work at all something's
[681]
gone wrong can you send it to me again
[683]
and once again you hope like in the war
[687]
that Shawn does not send exactly the
[690]
same message again but since it's
[691]
slightly different one because that
[693]
makes things much much simpler as well
[695]
see later so if we concentrate now on
[698]
this top block of stuff here here's
[702]
ciphertext one just as in good old
[704]
wartime Morse code tradition I'm
[706]
breaking this string of characters up
[709]
into blocks of five that was traditional
[712]
because of course he makes it so much
[713]
easier to read things if it's broken up
[715]
in this way
[716]
so these are spaces that you see between
[718]
every five they're not really there they
[720]
just to help you read if you ever do get
[723]
a genuine word space character and that
[726]
does exist in the five whole code then
[729]
Bletchley Park had their teletypes all
[730]
wired up to display a nine and that nine
[734]
men a word space here's the first
[736]
ciphertext W plus X a a blah blah blah
[740]
21 characters of it and then I say to
[742]
Sean oh whoa I didn't get it send it to
[744]
game wmj OG d wo and so on what I can
[749]
tell from that straightaway is that
[751]
since both cypher text starting with a w
[754]
and since they use the same key then I
[757]
don't at the moment know what the
[758]
plaintext letter was that started them
[760]
but I know it was the same in both cases
[762]
now as shown of course look W exclusive
[766]
order W thing with itself gives the /a
[770]
null character so what I've done here
[771]
between c1 and c2 is what I've just been
[773]
through on the theory exclusive all of
[776]
them and get this magical thing called D
[780]
mashup that's what I always call it of
[783]
the two ciphertex now successively on
[787]
either side of the mashed up ciphertexts
[789]
write down what you think is a plausible
[792]
piece of plain text and push that back
[797]
with exclusive all through the D string
[800]
and see if anything sensible comes out
[802]
for the other plain text now when to
[805]
start here on the second block down on P
[809]
to plain text - I'm assuming that Sean
[812]
was really fed up with plain text - and
[814]
he had to retransmit it and all of his
[816]
politeness will have left him he will
[818]
have started the second email message
[822]
with either a grunt or maybe just a
[824]
brief hi that's my guess anyway so I'm
[828]
guessing that in plain text - he might
[830]
have said hi space Dave or something
[832]
like that so here you see the nine for
[834]
the word space hi9 da V push all of that
[838]
line upwards through the corresponding
[840]
character combining them with exclusive
[843]
or what comes out and the answer is
[845]
hello oh I like that
[848]
now see this is where the cryptographers
[850]
you know heartbreak and joy if you get
[853]
it right it's wonderful but if you make
[855]
the wrong guess you've got to back off
[857]
and try something different very
[858]
frustrating strangely in this example I
[861]
seem to be making all the right guesses
[863]
so high nine Daffy comes back and be
[865]
hello nine in other words hello fall no
[867]
space ah so in the first one he probably
[870]
called me Dave as well maybe not sure
[873]
but we can at least take the DAV here
[876]
and promote it to the top line and next
[879]
time around we say if p1 is hello 9
[883]
Daffy push that through the exclusive-or
[886]
and the answer is then pizza will be hi9
[889]
hi Dave 9 another space this is looking
[893]
good sir we was being all informal is
[896]
then hi Dave in text oh honey looks like
[899]
the start of another world here yes but
[901]
we don't know anything about that yet
[903]
right now you have well in 1940 several
[907]
cigarettes many more cups of coffee now
[909]
where do we go from here
[910]
could it be the case that Sean is
[912]
using formal language in plain text one
[915]
hello David how about so we do that Hey
[919]
look at this the bottom then comes out
[921]
to be hi Dave
[922]
see SWE could it be see you soon see you
[925]
later
[926]
who knows but what we can do is if we
[929]
believe that C is right and is a great
[931]
word we promote that up to the top line
[934]
and make it be hello David
[936]
see but through an exclusive all comes
[939]
down on the lower line on the second
[941]
plain text Ben hi Dave see you weigh
[945]
bingo you he did he said hi Dave see you
[949]
now there's a well-known English phrase
[952]
see you later so we try of course late
[954]
down here propagate that back up to
[958]
exclusive-or and you get the word you
[960]
separated with spaces this is a fabulous
[962]
method of course it will only work for
[964]
as long as the shorter message doesn't
[967]
run out I can only guess that at the top
[970]
message which is a bit longer it starts
[972]
with our so almost certainly about one
[974]
would have said later as well but we've
[976]
triumphed and where the real triumph
[978]
comes is for these 21 characters you can
[981]
now go back to one of the equations I
[984]
wrote down for you and say we've got
[985]
cipher text - we've worked out plain
[988]
text to plain text 2 plus cipher text 2
[991]
will give you the key and here it is was
[994]
it generated by machine no I made it up
[997]
but there it is
[998]
and that's the moment of what you said
[1000]
oh that's fantastic we can start to work
[1003]
out now exactly what that wretched
[1006]
machine might be doing that's generating
[1008]
the pseudo-random key you start trying
[1013]
to run two tapes simultaneously through
[1016]
a piece of bespoke electronics which
[1018]
they invented which will do the merging
[1020]
but you must keep them in exact sync you
[1023]
do not want differential stretching
[1025]
between the two things
Most Recent Videos:
You can go back to the homepage right here: Homepage