Turing, Tutte & Tunny - Computerphile

we've done one already I think called it mentioning the Toolman break and it's got to the stage now where somebody comes and says remind us what was the tilt Minh break why was it so important and so on the Tilghman break exploited a weakness in any cipher that's based on bitwise exclusive or as indeed all the Tunney traffic exactly was just that I suppose I could very briefly and not using too much notation to frighten computer scientists but just just reminder what happens with exclusive or which I'll denote with a plus in a circle and effectively what happens with it is that if you take a piece of plaintext and you add on to it a key character what you'll end up with is an insightful version of that playing character and it's all done with bitwise exclusive or and if you say well in what code are these characters expressed then in what we're talking about in the middle 1940s it was the International teleprinter code five-hole which have been well known for quite a few years since the twenties I think and it was used for telegrams telex transatlantic communications and so on so what happens then is if you take something and exclusive or it was something else a five whole trade character you will get encrypted text if you look at that and then visit the zig zag decryption video where Sean and I've done of even a simpler example you'll find out how zigzag decryption works you get a bit of plain text one it produces plain text to the plaintext two goes on a little bit further and then that predicts a bit more of plaintext one and you flip flop between the two streams that's why it's called zig zag decryption so using zig zag decryption on all of three thousand characters very early on in this game the Allies really had got an absolute bonanza here because if you then go back and say well look we know the plain text now we know what ciphertext we received exclusive or tells us that plaintext + cipher text gives key we've got three thousand characters worth of key so why was he call the children break well it was called a Tilghman break because Colonel John Tillman who was a mathematician as well as being a military man knew about the properties and the weaknesses of exclusive-or and he knew that under addition like this the key would cancel out and you and you could use this as exactly he did it it took him ten days and he's a German expert as well you had enough mathematics knowledge but was a serious military German expert we do make it painfully easy and we do wave our hands and greatly oversimplify it you've got to remember this in real life what happens issues things agging and then suddenly your German expert says oh dear I can't see that that's the start of a new German word old dear and in the end you might get blocked but not often because what you can then do is look further along the message and see if you can guess another island in the middle it might be geheime that was another good word secret why not drag geheime through the D string with exclusive-or and see if you get something looking like geheime at the same place below it's in the other one so you got islands of decrypted stuff and your job was to link the islands and get everything including the less common German words that had appeared and in the end tilman did it ten days it took him I think it would to train him a lot less if he had to do it the second time obviously because she get the hang of the zigzag technique so tilman has done all this work but it i think for a month or two in the research section nobody could figure out what on earth sort of machine it was that could be generating stuff that look like this so new recruit built her from cambridge and rolled for chemistry degree not mathematics but very keen on recreational mathematics it was given the job and he decided that having loads at cypher school that if you think that there could be a periodicity in the cipher then you better start looking for what period what repetition or age it was on and prior to being put to work on this Tillman break he'd worked on a similar cogs based ciphering machine a Swedish one called the haggling machine and I think it's fair to say that there's enough similarity there that is all yeah maybe it's a cogs machine prime numbers of cogs because we've discovered the prime or relative prime of the numbers of cogs is the magic formula and he said ok the head of the section Jerry Morgan has told me that they have reason to believe that one of the cogs in this machine has got 23 teeth on it so we've covered in another video how we started looking for 23 but accidentally found 41 however there is something following on after that which is intended to randomize it sufficiently well as it will disguise the 41 but it's not being done well enough and occasionally the 41 SOT of this is breaking through the murk and convinces that that's right so he announces this to the rest of the research section and they go mad for several weeks trying to find out what the other streams must be because don't forget it's teleprinter code five streams 1 2 3 4 5 but looks like some kind of two-stage mechanism there's an initial attempt to encroach this but then there's a follow-up that's trying to disguise the periodicity of all these wheels well after a lot of effort by all the research section they cracked it so here is what happens you feed in an order e teleprinter character into this adaptor it goes through the first set of wheels which built up in all the things I read nobody explains why he decided he would call the first will the Chi Will's the Greek character Chi which is written out like that and the second set that follows on afterwards there they are look here's the first set that is then passed on into a second set of wheels which he called the Sai wheels and there's a character saw those Sai wheels were meant to give an extra element of disguise as to exactly what it was the Chi wheels were doing and to make decription that bit harder Chi wheels put out a certain pattern of ones and zeroes which gets exclusive order of the incoming character they then all turn on all the tiles always move in synchrony together but that doesn't get boring because there's different number of teeth on these wheels I mean here on stream one there's the famous 41 next wheel along has got 31 teeth then 29 26 not prime but relatively prime to all the rest 23 that first stage encryption then travels onto the path I wheels but the designers the Machine thought it will make it even harder for the Allies if we make it so that the sails don't always move on with every character let's put in a stutter mechanism or at least that's what the decrypt is came to call it sometimes they move in sometimes they don't okay that will make it harder actually in the end it made it easier as several statisticians pointed out but that was the way it was and the reason that bill Turk was able to prevail and to see 41 was that the purse I wheel patterns were really bad and by really bad I mean they left the second set of wheels not rotating four five six seven characters on end you know they didn't change the pattern at all so you've got this great thing where very clearly it was been exclusive Ward in the second stage with the same thing over and over and over again and if that gets up to six or seven times it's basically saying it's only a single stage machine again because the is varying fast enough built up said he said thank heavens for this we were so lucky in the war number one the tilt Minh break that trap should not have sent that message again and given us three thousand two hundred characters of key potentially but what really finished them was that they failed to disguise the periodicity of the Chi wheels because they had inadequate sigh wheel pans that great long unaltered stretches come through and that's what gave us just enough evidence that we could work out that the sign wheels had got 43 47 51 53 59 and so on so we won't go into the details of precisely how that calamity occurred let's just say that whoever was in charge of side wheel movements really goofed in the early stages and as tested again says it didn't matter that when we came back later they put their error right and made it better in future by that time we knew the periodicity of the wheels so the only worry then was and another of bill touch some colleagues and later his PhD supervisor actually a guy called Sean Wiley who was down the hill in hut 8 with Alan Turing and various other wirless was brought up the hill along with Jack good and Donald Michie people were brought from hut 8 and naval enigma to help out with tummy and Sean Wiley in one of his writings about this says do you know the thing that panicked us straight after finding out this wonderful layout of the machine let's hope these wheels were not interchangeable could you imagine if it's instead of having 4131 so on down here it was possible to pick them out and put them in different slots and permute I'm like on enigma and he said thank heavens after analyzing several weeks of traffic we were convinced these things were fixed it was always going to be 4131 whatever so that's one big worry out of the way so that was more or less the situation that was left then you've got this fabulous break the keys subtracted itself out there was enough indications in there to work out what the periodicity of the wheels was and they're all relatively prime to each other but where do we go from here whenever somebody uses the correct initial and the same initial setting which they shouldn't do their order not to do it if ever this happens again and gives what Bletchley Park calls the depth and you remember the famous absolutely famous indicator setting this is of the tilma brake was H quid Peck cz mug 12 characters yeah well that was how they knew it was worthwhile exclusive oaring them because the operator the next time round when he repeated it sent out this thing saying my my settings are HQ I be PE X YZ n mu G so you know it's worthwhile exclusive o-ring them together seeing what you can find out so they relied absolutely on the factors in the early days and up until mid to late 1942 the operators were told to send out the indicator so the other end knew how to set the wheels relative to one another what they didn't do except very infrequently thank heavens was to change what's called the pattern on the wheels it's probably about time we said a little bit more about that what I've drawn out for you here on that diagram is the simplest wheel of all with the fewest teeth that was 23 here is my notional starting point and you can see I've numbered them not one not two not three not four so just imagine that's after every exclusive all character that contributes this wheel is moving clockwise around from 6 to 7 and then it moves the position 8 and so on the dot means this is contributing or 1 when it comes around to the start position and otherwise it contributes a 0 so these things the the dots are called the patterns on the wheels now again huge stroke of luck for the allies it was such a pain setting up all of these whales all 12 of them with different patterns and you had a little slider to slide and ratchet up and down as well as one is there that the Germans only changed the patterns every month true that meant that you had one month to try and get depths you know things where the person had used the same indicator twice it may not be a writ as a repeat of the same exactly same message that really was an absolute gift from on high typically though an operator I've used H squid pecks easy mo you know that one was about parachute dispositions ensalada curls another one here I've got to send which is about when general Katz ins in the next houses is a leaf break Oh what indication is that oh well let's use this one again they'll never decrypt this it doesn't matter so very often your zigzag was not between two similar messages it was between two very different messages but at least they'd use the same settings but again explain why you needed German experts around to say hello you know yes that is the start of something or other down here so that was the name of the game hope that the lazy operators give you depths by using the same indicators then bill Turk came up with an extra method in late 41 I think I said I know let's try and look for near depths because a slightly less lazy operator would say H quid pecks easy mug we're not here and going to use the same one twice I'll only change one of them is such a faff let me just change one of them now if only one of those settings was changed and if it happened to be on a first stage car wheel built up pointed out that from the other four that you were new the same as the last time and only one is change you can with some mind-bending attention to complexity and the help of German experts sitting next to you say it's not Zima at the end it's our mug so have we got any other messages from earlier on that we part broken which had are in that position who knows that might help so he said typically you might end up with twenty or thirty possibilities one should propagated this are not said through all the morass of stuff that you've got and he said but yeah with the help of some really good German guys that could work and that was more evidence you see because that could be backtracked into working out what the wheel patterns were a bit more so I think the feeling in the research section was this is okay so long as they keep sending out the indicator settings but we need a lot more techniques to get us out of trouble if that isn't the case well everybody knows of course that Turing did everything at Bletchley Park nobody else was of any importance at all and I hope that one of the things that this set of videos may be doing for you is to emphasize that it very important though he was he didn't do absolutely everything one of the problems with the secrecy particularly in the late seventies and early eighties when this new is about Bletchley Park began to trickle out but a lot was still under the Official Secrets Act is that some computer scientists historians and writers Varian cautiously started saying oh well if if Turing took what the poles did for enigma and develop these on and then did naval enigma and got that sorted out he's such a genius it stands to reason it must have been him running the whole tiny Lawrence Colossus show no not true I think our friend and colleague Jack Copeland I was booked you see up there Colossus would be the first to want me to say no Alan Turing did had nothing to do with Colossus Colossus was purely Tommy flowers he did make a contribution towards the decrypting Tony F and it was a very very helpful one here we are in early 42 there's been the Toolman break built art has worked back from that and the research section helped him to find out the disposition of the wheels on this Toni ciphering machine what was the problem because every message sent out on that machine had an indicator showing the start positions of all of the cogwheels the bigger problem was the worry that the patterns on the wheels the patterns of zeros and ones a lot of people spent a lot of brainpower working back through debts where people had used the same you know indicator twice trying to backtrack through the key text into saying what does this mean about what the patterns are and in the end if you gathered enough evidence and certainly with the Tilton brake there was so much evidence there they really did get the whole thing sorted out they managed to work out for that month exactly what all the wheel patterns must have been took a lot of people a lot of effort by hand but it was done but the worry was we're gonna more and more be saying we want to get the patterns at the moment we're saved by the fact that we have a month to build up and analyze evidence before it changes again so you know let's say for a typical example start of August you start collecting evidence as to what this month's patterns must be you look for debts you've got all the indicators and by maybe August the 20th or mid-august if you're very lucky you've got enough evidence to work out what the patterns on the wheels are for this month then you go back to all the stuff that was transmitted earlier in the month that you didn't understand but now you've got the patterns you can go back and see what the messages were and so long as the developments in the war and not happening at a breakneck pace then the fact that this intelligence was two weeks old didn't matter too much because it was high quality intelligence remember this is Hitler's high command talking about strategic things so it was still valuable suddenly I think it was very 42 the moment they'd all dreaded calamity somebody in the German High Command said although it's inconceivable that this is being broken we are idiots if we start sending out stuff we don't need to send out these indicator settings why not distribute a codebook to everybody and say I'm using wheel patents three five six today that's exactly what they did on enigma remember same argument came out oh they would they don't understand it it'll work it'll be all right no no one step you know belt and braces approach to this and don't send information that you don't need to so there they were then all of a sudden they didn't know what the indicator was anymore but they did know when things were being sent in depth because a lazy operator would say to his opposite number I'm using entry number three five six in the codebook and then a little later on I'm still using three five six so you didn't know what three five six was but you knew it was a depth with the same start point so the business about exclusive or addition and being able maybe to do a bit of zigzagging still applied but it was a pain not knowing the settings so this was the time then by this stage max Newman who's one of Turing's tutors remember Cambridge had joined the research section and his brief that he set for himself was to mechanize wherever possible just like they done for enigma built hurt came to him very shyly he says one morning and he was sitting with the other head of section Jerry Morgan I think so max Newman was in charge of mechanization of any food sort and he formed a subset called the Newman rate out of Association and then there needed another much more linguistic space section run by a chap called major ralph testa and that of course became the tester II so the tester II had a few mathematicians and a lot of linguists the Newman rear had people who were really concerned with how do we get machines to be able to help us with this any new technique any variants on the technique was gonna be very helpful so Alan Turing in early 1942 although he wasn't part of the research section then was down in hut 8 doing naval enigma and we're getting to be very successful eventually so he said okay I'm going to take a six week sabbatical with the research section see what I can bring to the party he did contribute venturing to things which were of enormous strategic help actually the first and in the end less useful one was that he said what I'd like to do is to have a rock-solid method that so long as you've got lots of depths which we tend to get every month that you can buy dead reckoning work out and we could train people to work out what the patterns were it was one that he could get to work again you need an expert German speakers with you and built her said you know it was wonderful but I could never get it to work it was it was branching explosion of possibilities and when I said to chirring well which one of those deals with duty oh you take the one that you know in your bones is the right one and and turn said my bones were never good enough I could never get his method to work but he could and his collaborators the idea essentially was that every wheel has got a different repeat cycle so what you're saying is let's presume that at the start position that tooth and the one next one let's presume they were zero and one they were contributing then let's say that on the next wheel along and each start position it was zero or one so you can see the binary explosion beginning to take place but then let's go back and say no no that one was one one and that one was zero one and then work out what happens 23 rotations later on the number five wheel or 41 rotations later on the number one wheel you see it's all perfectly straightforward you'd have to be aware of the possibilities of they were both the same while they were both different on different periodicity for different wheels and you combine it all together and everybody's sort of putting cold compresses on their head but eventually if you're really persistent in your brain works that way they did actually succeed but you had to have enough depths that you knew what the key was but also I think what came from children and Jaco planners book assures me that it was Turing was the general observation in all of this work with the Tunney traffic that it was a good idea not just to consider the characters themselves of plaintext or ciphertext but how about exclusive or ring them with the one ahead now just imagine a stream of five whole characters like this coming down so you know it was H a P P Y now that's your paper tape do another one exactly the same alongside but this time just slip it back by one what would the net effect of that be you are exclusive boring every five bit letter with the one ahead of it to see what happens why would you do that Arthur churring because it will make all of these doubled letter occurrences stand out like a sore thumb we have referred to these in a previous video how did they ever get into this traffic and the answer was its language structure and the nature of exclusive or if you have happy but you slide the second P up against the first one on a separate tape and exclusive all them anything exclusive orders itself gives you five dots five dots is a very unlikely thing to occur by chance but if you do the Delta technique as it was called it doesn't matter what repeats itself it could be double P could be double Zed it could be because I gather them Germantown router operators like my dad were taught to put in a double space after every full stop so a lot of the traffic on Tunney was double spaces and those count as well so can you see that by Delta ring as it was called you are producing a cascade of zeros just because of the way exclusive all works and that message was not lost on Bill touch he said look the Germans are upping their game all the time they're really scuppered us for the moment by not sending the indicator got to be able to work out what the relative settings of these wheels were even without the indicator being given how do we do that and he went in to see max Newman the head of his section at that time and said I've got this bright idea this could work and I think Newman and Jerry Morgan said well yeah but do you need a depth verbal you know don't know this would work on anything so long as it's sufficiently long message full of ciphertext I can use the Delta method and statistics to work out what relative positioning must have been of shall we say the first two wheels looking left to right and well how are you gonna do that well you rely on the fact that when you Delta things together on a per character level you produce far more than probable numbers of five dots which is where two things that are identical have been exclusive all together so on every single stream you're looking at there will be more dots than crosses for ones and that will be particularly magnified if you do the Delta ring first and they said well have you any idea what the skew is between you know he said about 55 to 45 sometimes maybe creeping up to 60 or whatever and I mean they were all good statisticians you can imagine it wasn't bombarded with what well this is all very well bill but as we all know this could show up and look plausible but actually fade away if you yes you're gonna need lots of ciphertext how much and I think the answer when you do the analysis is to be pretty sure that this isn't a freak result that you're getting this ratio of loop whatever it's showing up has 54 to 46 you need about 2,300 characters to be sure so you do need long messages but if you get one that is sufficiently long what it will then ensure for you is that at the right setting relatively it will show the 55/45 split if you presume the wrong setting then randomness takes over it will be closer to 5050 and then to 55 45 or 60 40 or whatever but in order to make sure that that distinction between nearly 50/50 and nearly 55 is really showing up correctly the Bletchley Park rule was don't rely on anything less than 2,000 characters long to show this up but if it does show up then it is odds on correct that that is the relative positioning of those two but just imagine you've got if you take will one will - and the Chi set 41 times 31 1271 relative positions and for each one of those relative positions you got to squirt through at least 2,000 characters of ciphertext several million dots and crosses to be analyzed for even warmer setting of the winds now you realize why mechanization was absolutely essential to first our founding wheel settings correctly so you know Newman was delighted because he more or less said this just proves what I've been saying we must mechanize everything we can electromechanical Heath Robinson and of course later on this really made a huge difference that chewing through three million possibilities for every pair of streams would be pretty slow on an electric and mechanical machine but it would be a heck of a lot faster and of course that is where it ties into Colossus Colossus could port these patents to be searched for on a plug board at the back and basically just look for them the thing the thing that Chuck then asked himself is well it's all about doing these deltas but suppose just suppose that the Germans really get their Chi wheel patterns so good that actually stream one looks like 5050 stream two looks like 5050 they might be able to disguise each individual stream quite well but would our think about it though they're not independent because of the fact that we get five dots a huge amount of time in a delta stream occur at all time every time there's a double letter what it means is that the dot dot combination between one and two will be more common than doc cross cross dot or even cross cross it should be the most common one of the four and they won't be able to disguise that because you know there is a correlation between these things and is particularly so that five dots would be an incredibly uncommon thing to occur by chance but he's actually occurring a heck of a lot because of the nature of exclusive-or so if we do this delta e on whatever the germans might be fiendishly clever enough on any one stream to be able to hide it but the chances that have been able to do it across pairs it's not gonna so basically what you're looking for in stream 1 on stream 2 together is the occurrence of dot two dots really it ought to be 25% but it won't be it'll be 55 over 45 times more common than 25% so it's these little things you can search for and if you think you've got something looking good after 2300 carries a cipher text you then say right let's correlate stream 2 with stream 3 and then we can find the relative settings of 2 to 3 & 3 to 4 so after only five runs on preferably held by Colossus about 12 minutes per run that or you could ZZZ through all of these millions of combinations per relative setting and say that's in the start setting some of the Chi wheels are as follows of course that's only the start of the process so you've got the Chi part of the encryption by their laws of richness of all if you add that back in to the side for stream what will be left over is the Sai wheel contribution now as we found in the early days the silo settings were dreadful and tended to just let things repeat over and over again well again the Germans have learned from a lot of experience oh and by the way of course the number of teeth on the sidewalls was known so actually as a by hand method to follow on from the decaying which Colossus will do then in the first instance a lot of hand effort might go into getting the Sai contribution taken away and revealing the absolute classic plaintext now what's going to happen if you think about him is that by the time you look at the side contribution you might see little bits of plaintext showing through so you need a German expert again and you need lots and lots and lots and by hand efforts to say what must the Sai wheel settings have been which when put correctly will this to look like plaintext if the first set of wheels was taken away the carry contribution decaying what you're now doing is D sighing but of course if it doesn't work it's called deep sighing thank you yes but very largely it was possible to make that final adjustment and get it all backed out and sorted and showing up very clearly but this really highlights again how immensely lucky the Allies were that the wheel patents didn't change very often so by lots of hard effort aided by Colossus we managed to discover the star settings even without the indicator but you'll have got the impression very clear there's still a lot of by hand work had to be done to get the full story to appear and this gave rise to the well-known Bletchley phrase which staggered me one of her so I couldn't understand it he said it just to remember Colossus time is far more valuable than computer time in those days a computer was a person a person who did computation so the computer time was the by hand effort needed to tidy up the story and you you didn't worry that there was hours and hours and hours of that because the will patterns only changed every month why it was vital to use Colossus like finding the star settings was that that changed every single message so there we go then that Colossus time is invaluable for finally the start settings of the wheels and is far more precious to you than mere human computer time it wasn't believed me until the 50s and 60s that the use of computer as a person began to fade away even in the late fifties in the space program people using electronic mechanical calculators were called computers you had to carefully say no no I mean an electronic computer I mean a digital computer it wasn't till the sixties that computer without any prefix came to me a piece of electronic machinery and I should caveat this by saying I'm going we're talking in general terms each operating system with us Windows Linux Mac OS iOS BSD insert your favorite operating system here that you probably

Channel: Computerphile

Views: 149,323

Rating: 4.9419117 out of 5

Keywords: computers, computerphile, computer, science, Turing, Alan Turing, Bill Tutte, Tunny, Tunny Traffic, Lorenze, Encryption, WWII, Professor Brailsford, University of Nottingham, 4K, UHD

Id: pCAKq0JCcdI

Length: 37min 33sec (2253 seconds)

Published: Wed Oct 24 2018