Cryptanalysis of the Enigma

or how i met your mother okay i'm live actually i'm curious all right um if you haven't signed up for skyfall you should because you want to go see the movie i did it's 10 bucks and you get one free drink with that because deviant will set up bar in the parking lot of the movie theater he's going to wear a tux and make you a vodka martini shake in that dirt however if you wear formal dress tonight which is black white or gray until i'm told nothing else is acceptable except for the women in which case anything is acceptable because this is deviant that they're all um it's an open bar what's that something awesome no no no you can't put

on a short skirt okay i'm sorry i just didn't want to know i i said for the ladies the ladies something something is desired i'm not entirely certain of that anyways so uh open bar at that point so please sign up go to the reg desk can over 10 bucks in your name like a business card or a note or whatever uh egyptian hydrogels are not included in that it has to be legible readable that kind of thing um we've still got some food if you're hungry we're not have to talk grab what time is it what time is it i believe it's 8 30 at the cinemark 10 8 o'clock bar opens 8 30 the movie

starts which of course means that it actually starts about 8 45 from nine it's like how many damn previews they put in the movies these days get off my lawn damn kids um but i saw jack daniel i had to go for munching on everybody uh and i hope you're having a good time thank you thank you josh thanks john what if we're not refund too goddamn bad yes right i'll pay you double your money back where is this in the market it's like about a mile away that's two minutes away all right so uh even before i go into the who am i i like the fact that we're all talking feel free to interrupt us at any time

ask questions uh we like the interaction we like to feedback uh so i'm bob weiss pw crack president founder of uh password crackers congoon to my right is benjamin gotti uh benjamin og on twitter he's one of the developers of openvpn and he's a independent consultant type person uh so if turing were alive today uh he would be uh he'd be here uh he'd be messing around with the best uh computing technology uh he would be uh he'd be unconstrained by our social uh problems that he encountered which we don't have today he would be uh uh what was i gonna say about that one i had a line throughout my life nice nice right

yeah exactly line uh so uh you know he would be uh uh this is a guy who uh won world war ii no i got it he won world war ii he invented the computer uh and when he was persecuted for his uh sexual predispositions uh he told the judge i've done nothing wrong and he stood up for himself uh so this is uh this is definitely a guy who would be very welcome in our community uh probably welcome in any community and uh someone who uh we should all be looking up to and uh someone we don't know as much about as we should use a lot of the work that he did with classified until

recently yeah go ahead suicide or was he killed he uh committed suicide after he was chemically castrated by the government and his security clearance was revoked did they kill him or was it really oh no i i assume suicide i think that's the i think his wikipedia article says it was suicide but it's suspected that it could be something else okay so so i haven't heard that that maybe there was foul play involved uh i think suicide's the default position but again clearly i don't know uh so demo time [ __ ] it we're gonna do it live uh yes this is always subject to failure it worked before for con it failed at sky.com and we're gonna switch uh

switch computers why are we doing the demo up front because it takes about 45 minutes to run so we have to get it started right at the beginning and uh all right so don't hit solve yet take a look up top this is our enigma cryptex it's what it looks like coming out of the machine and that is what we're going to attempt to decrypt as it solves we're going to see sort of coming up below that software that we've developed is going to pop up the best guess that it's achieved so far so when we hit solve right away the best guess is going to be very bad right it's going to be completely illegible and not

show anything that's any in any way useful and then it's going to start to get a little bit better right and you might start to see some characters pop up and with any luck if you hit it right yeah yeah it started with any luck uh it finishes before the talk right but you never know it may or may not work so we're going to tell you a little bit about the indigo machine so you have some context for what we are doing uh describe the software that we've created and how it breaks it and uh go back to the demo at some point you may switch back

versus on your pc so um so let me let me get to that all right okay let me talk about what i'll talk about what bletchley did versus what we're doing right because we we are not implementing what bletchley did on the laptop it's not a one-for-one correspondence what we're doing is different uh so why do we care about the enigma i presume many of you have heard of the enigma machine may be somewhat familiar with the history and what's going on there's really two reasons why we care about the enigma the first reason is in the world of cryptography and cryptanalysis this machine and this event occurs at a very interesting inflection point so prior to the enigma you typically

have a series of uh encoding schemes or crypto schemes which are generally pretty trivial right limited uh limited entropy limited complexity and generally the crypt analysts the people trying to break the code are the winners right codes are regularly getting created broken created broken created broken and that's our that's our history up to the odigo machine and the enigma machine comes out and there's this massive spike in complexity right the first sort of real crypto system is really getting complex and it's going to really be hard to break and that's that's sort of right where the enigma comes out and i'll explain that a little bit put that complexity a little bit more perspective a little bit later

the uh the other piece of the aviva machine is it's all tied into it it's not just that there's this crypto history timeline and you have little complexity huge spike massive complexity but that spike happens to happen at a very interesting time in world history right it's world war ii and our ability to break this device or alan turing's ability to break this device changes the course of world war ii and world history and there's a sort of fascinating stories about how it was done and the intelligence that comes out of it it sort of is very interesting in and of itself if you have you know any interest in history so that that's sort of the two

reasons why you know we still care about the enigma today obviously no one's using it for any kind of uh crypto or encoding uh you know on a daily basis today actually after one of our talks about an interesting story i'll completely digress after one of our talks some guy comes up to me and you see that we've just been able to break the enigma and he comes up to me and he says that you know i can't tell you where i work but our company is still using the enigma they're like what because yeah we actually we decided that nobody would know you know as if we just if we use the enigma machine to pass our keys back

and forth nobody would ever guess right because who would use that and i said it's like you have to tell your boss to stop that immediately right first of all we've just broken it but second lawyers like anybody could figure this out right it was like security through obscurity not so good and you must stop that immediately because i know i keep telling him but it's like but he won't listen uh and i'm like here's my card have him call me you know but whatever but you can't keep doing this did he call you no i have not gotten that call i don't know that and i don't know the name of the company i don't know that there's still that

they're still using it right but yeah it's like security throughout security right it'll it'll come back and bite you with the butt at any point in time and it was like you'd be stunned right at what people are still doing so uh so first thing there is no the enigma right there's no single machine that's the enigma boom we're done uh it is a series of machines and a series of upgrades uh there are multiple versions um there are people who collect these machines today and some of the machines are rarer than others um and hence more valuable yeah go ahead did we call it the enting or did they call it the germans that's the commercial the first version

is the commercial versions used in banks in the in the 30s yeah so there are multiple versions there's an army and a navy version they basically work they're interchangeable in terms of cryptography they're they basically work the same the uh one of them has uh letters a through z on the wheels the other one has numbers one through 26 on the wheels but basically they're again interchangeable later on the germans add a fourth wheel so there's three and four-wheel versions there's uh interchangeable router versions or variable reflector versions so so you can look at different machines they basically all work the same most of them are compatible with each other a three wheel is not going to be

compatible with a four wheel though you can stop this doesn't rotate so the four wheel will be compatible with the three wheel but not the other way around uh uh all right so i'm not gonna i can't explain i don't wanna take the time to explain in detail how the machine works right i wanna give you an overview of sort of where the complexity comes from in this device i'm sorry i'm going to run through a real quick okay so this is sort of a gross simplification of the machine there are three wheels uh one two three um out of a total of five at the very beginning of the work they always start off with the three then

later on they had the additional two later very much later they added another three but assume for most of the machines most of the war you're looking at three wheels go into the machine out of a total possible five wheels that gives you 60 combinations of ways to put the wheels in the machine obviously i can't put in wheel one wheel two and wheel one because i only have one of them right so that's where you get the 60s then 60 combinations of ways to put five possible wheels into three possible slots so just a quick point oops i'm sorry can we do that yeah these dots apparently here here and here seem to indicate the wheel the wheel

marker but more importantly is that the data enters the wheel from the right it's this is called the fast wheel because it turns every character this wheel only turns once every 26 characters and this wheel only once every time this turns 26 characters so this is called the slow wheel and then it hits the reflector and very importantly each pin in the reflector is connected to another pin which sends the signal back through the three again and they did this to increase quote the complexity but in doing so they introduced a kind of very important uh mouse hall right and that is that the character starting on the on the right is mixed around each time it goes

through the loop it's bounced back and it can come back as any character with the one exception of the character it started as so when you encrypt the letter d it can come back as any character except d and this this is really uh to answer the other question how do they solve the problem plus you park that's that's the majority of how they solve the problem that flaw um our work really doesn't take that flaw into much account so there was non randomness no quite right it was actually inverse chai if you will right so the most popular letter to come out of the machine would be anything other than the e right all

right the least popular would be that's it and in in modern crypto right a secure crypto system should leave no information right so the fact that i know even the slightest thing about take the first letter in the message right and it's a it's a k right i now know something about the original message right it did not start off with the letter k wow now that may not be all that useful right but in a modern crypto system you would look at you know the first bit zero or one what does that tell you about the message it must tell you absolutely nothing right or it's not secure so uh so each of the wheels has this

little notch in it this is what effectively kicks off that odometer like rolling between the fast wheel kicking off rolling the middle wheel and then the slow wheel that notch can be moved there's a pin in here you pull it down you rotate this whole thing around you let the pin go so you can notch this put the notch at eight or the notch at nine or whatever now that because that notch affects the way the odometer rolls over um it affects when the fast wheel is going to push the medium wheel and it affects when the medium wheel is going to push the slow wheel the slow wheel has nothing to push so i can set the slow wheel notch somewhere

and the germans actually have that in their code this is where you put the notch on the slow wheel but it doesn't change anything yeah so so the purpose of that then the code the resulting codes to say that that makes sure that you can't tell the signature of the machine uh now this is going to totally change the setup of the machine which is going to change the encryption um in a pretty significant way with the exception of that slow wheel where i can move that notch in any one of 26 positions and it has no effect so for other reasons they actually identified the senders not the machines so often but the individual doing the

transmissions by the pulsing the the rapidity of the pulsing and so forth it's all handy the results of this would go into ankito into wireless so this should be 26 to the two that's a typo or 676 possible options of where i can set um the notches on the first two wheels again i'm not trying to explain to you how enigma works just want to give you a rough breakdown so then you close the machine up you've got the message settings there's it could be this could be anywhere from a to z a to z a to c 26 to the third options or 17 576 possibilities for message settings all these are multiplying so right now we've got 60

plus times 26 to the 2 times 26 to the 3 complexity now in the commercial version there's no stacker board which is german for plug board these are the plugs from the front of the machine these are the keys on the top and we've been looking down on it now we're looking at it from the front um uh the german uh army and navy at the plug board huge cryptographic advance that's where almost all of the complexity of the machine comes from what this does is as i'm going to press a key it's going to go into the plug board first and i can plug any letter w into any other letter g i have 10 wires to do that so i can make

10 sets of connections for a total of 150 trillion possibilities why if there's 26 letters i could connect 13 right make 13 pairs of connections why would i only have 10 wires right actually leaving some unconnected increases the complexity if i told you that you had to take 13 wires and connect 13 pairs of letters it starts to constrain some of the some of the settings so the maximum complexity is with 11 wires it's only slightly higher than 10 wires so 10 wires being faster simpler and uses less wire because there's almost no difference between 10 and 11. you go 10 wires is really the maximum is the best possible combination of wires to do this so you end up with 26

factorial factorial combinations or 150 trillion and obviously that's a lot bigger than any of the other settings right all these multiplied together to set up the machine once i do this i am going to encrypt my message and it can only be decrypted by someone at the other end who has similar machine and knows all of the settings that i use to set it up uh so the expected complexity of that would be equivalent to 2 to the 77. so in modern crypto world des is breakable by uh multiple different ways a big pile of fpgas would break dez at two to the 56th a distributed system of computers can break theirs at two to the 56

but dez is still going to be hard to break right it'd be hard to get a key out of dez at 2 to 56 but if we're where today 2 to the 56 is going to be a little bit too insecure because it could be broken in a reasonable amount of time aes has a complexity of 2 to the 128. how big is that 2 to the 128th is roughly bigger than all of the atoms in the galaxy right so we were talking the other day someone said oh what if i created an organic computer and i used all the molecules in the ocean on earth to somehow compute the aes key i'm like you'd be really far from even

possibly computing an aes key right using every molecule in the ocean and you're not even close so uh so that's a really big number right so the enigma it clearly would be in terms of complexity pretty sound as a as a crypto system in today's standards right we would not expect because if you can't be a secure version of aes with the complexity of the key reduced down to two to the 77 we would not expect to be able to break down on a laptop all right that two to the 77 to 76 that's going to be very secure for today's standards and that would pass muster with any crypt analysis crypt analysts that you would have

uh so again let me just go through this answer the question earlier rough rough uh history of uh of how this was used right mary rajewski polish cypher bureau the polls in 1932 are the best crypt analysts in the world they are the top mathematicians they get a hold of the one of the enigma machines they're able to figure out and deduce mathematically all of the settings they start decrypting um german uh traffic they create a machine to do so the polish bomb in 1938 uh why is it called a bomb we don't know some people suggest maybe it had a ticking sound but really not sure uh and they keep that all secret uh right up

until the time that poland realizes hitler's probably gonna invade and take over poland right which is not a huge uh logical leap for them because they were probably reading the messages right they kind of knew exactly what he was going to think of so uh so they have a little bit of setback in 1938 the germans had two rotors um that and the polish uh the polls go dark they can't read it this is this is a similar history in um at bletchley park as well when the machine and the germans change the machine there's periods of time when we can't read it but largely uh the germans tend to iterate on the machine right they don't

throw it out and put it on all new machines they modify the machine slightly and that that's a huge deal because that enables us to sort of recover after a certain period of time and get back to the ability to depict the messages so the polls in 1939 just before the uh invasion uh tell the french they're like hi uh you don't know us we're the polish cipher bureau oh by the way we can read all the german messages would that be interesting to you guys uh french sacramento i have no idea what to do i do not know i'm gonna call the british

so they're like british uh beat the pulp right you guys and uh they uh they uh furnished you know recognize what they've got they stand up a uh uh encryption or decryption team run by alan turing at bletchley park and what they're doing is using that uh that one flaw that no letter can be encrypted as itself they create crips so i take a message and here's a message that comes out of some weather station in france um it's a german weather station this guy wakes up every morning and he radios back the weather you know it's like it's you know uh nice weather station it's raining right that's my job right weather station however in german is

anyone know whether stationed in germany what pressure no it's one it's really long it's nighttime i'll go with that right so it's like a 20 character work right so well if anybody is in 12 years right so it's a long word something like i don't know what the station would be right right so they uh so this guy's you know broadcasting this every single day right you break it one time you know his his format right for his layout you don't even need you could know what actually what the weather is right because that's public information but um but you don't even need to right all you're trying to do is basically place the word for weather station

somewhere in this message and see and it's going to eliminate a whole series of codes because one of these 12 letters is going to line up with one of the letters that it couldn't have encrypted itself as right so we know that that set of settings cannot be correct right so you goes over when you're you're able to resume just in paper right you can take the crimp text and take the word weather station and start it zero aligned and look at every of the 12 characters if there's an e where there's an e or a g where there's a g or any other characters that match in both cases it's it's a non-match and you index it one

forward and then you do the same check and you index it again one forward and do the same check eventually you find like the one or two places in this medicine for 12 characters could fit without colliding with themselves somewhere in the cryptex no machine at all right and they already can guess where it goes in the machine right so now you have 12 characters in the in the german and 12 in the crypt you take those 12 and you create what they call a menu and it's a little bit complicated it has to do with paired paired characters in other parts of the of the machine but they create this menu um which is like a b tree it's a couple

of options it could be this or this it could be this or this could be this or this very simple logical relay computation uh that's been plugged in with a series of large plugs that handle like 26 characters that ago they connect the f to the a and the g to the r and and then they spin up the machine and essentially they eliminate huge swaths of rotor combinations which collide in other ways um and there's five or six foot which are left they then they go to the actual machine and turn them out and check them and then decipher the code right and the germans use most of the code other than the message settings

most of the code is the same for every unit in the army or the navy for the entire day so once they get the settings for the day the message settings will change for every message right if there's only 17 000 of those once you get the rest of the message of the machine settings for the day you've got the whole army for the whole day so that's what the po that's what the british are doing using crimp based decryption uh that's what alan turing figures out they build these big machines they name them the bomb also after the polish uh because they know about the polish machine as well and uh and then later on at the very end

uh they're doing so much of this stuff they they need more machines and so i think what works good yeah yeah yeah that was encrypted right so i've you know i've given the talks three times i still haven't corrected that typo um so uh so at the very end we help them out by building more of the machines right the the united states comes in as like what yeah we've got a national what becomes national cash register out in dayton ohio um is brought in to said hey here's the plans go build a lot of these and we start shipping them around the world and we're using them so that's our contribution to the message um so ben

so we wanted to approach the problem from a more modern uh crypto analyst point of view what they had done was essentially a side channel attack they most of what they attacked depended on knowing something about the message they knew that it had the word weather station in it for example absent that there was no no assault on the message or the the crypt so we have to run up a lot of tests i mean potentially 277 right that's way too many you cannot brute force the enigma machine so we had to first of all um we switched to opencl to to massively paralyze some of the analysis uh memory was always a problem and we

found you know we had to have a database that could could handle um a large number of tests there's a definitely a large number of tests involved okay so i think now we can talk about what we did to avoid brute force and it should be said that any crypto analysis system essentially should be multiplicative right if you have a single digit password and you add a second digit it should be ten times whatever goal to break and if you add a third and the fourth it should be ten and a hundred times again so the device should be multiplicative and this is the stickers that should be multi that complexity should multiply with the complexity of

the rotor system once it goes through the rotor system it reflects and goes back again through the specker so they appear the stickers appear at the front and they appear in the back and the rotors appear in the middle and it's a sandwich if you will it should be noted and and we actually had a wonderful dinner courtesy of the nsa yeah the nice people of the nsa because they lost the bet and they confused the fact that the plug board is the same is the same plug board on the front and the bob and then in the back but it has a very very very different effect if you this is a caesar cipher essentially it's

a fixed cipher a equals z and it does so for the entire message if you do that on the front in other words if you jumble up your [ __ ] text and you have one of these connect pairs wrong then every time your cryptex is a z you incr incur the error and the air is rerouted into a random part of the rotor goes through randomly and comes out as something quite random but on the other hand on the outbound side and by the way it's the same mistake because there's only one plug but on the outbound side of the plug board a z map to an a results in cryptex in which this is all the z's

are replaced by a it's really quite obvious and it's fairly simple simplistic because uh there's only one character that's missing so if you typed out d 26 times and you had one plugboard wrong you might expect on the outbound side that d would map to an e for example but that isn't really what happens because every time you get the wrong plug on the kryptex that thing is routed to hell and beyond so it incurs the full complexity of the machine so it's important to look at the plug board in the front and the plug board at the bottom as really two separate challenges they're both these are cyphers but they attack them very differently so

the bottom is a pretty standard caesar cipher this is right next to your plain text you simply look at the most frequent letter that's your e the second most frequent letter is probably your t and so on that is really um pretty effective at this point but on the front end that is not effective at all so what we did in the front is rather interesting and this is really where most of the complexity disappears and that is we took all the characters um in the crypt text and split them up by by their number so we've got all the e's in a basket all the bees in a basket all the s ends in the basket wherever they lined

up and detect it's kind of like sampling a barrel of wine you put your spoon in you pull it out you taste the wine well wherever you sample the wine is going to taste pretty much the same in other words if you have a basket of characters produced by ease in the first position in the 32nd position in the 47th position in your message at the end of the day you should have if it's properly solved a bucket of letters that represents a distribution of language not random noise so you can take individual channels if you will and and these stackers being in the channel and analyze them by themselves and you should get chai if you if you've

got a match on that channel and not try if you don't so let me interrupt two things you need to explain chai and then just so that everyone can watch that just so you guys are calling hi right just so that you can watch the train wreck happening we should when you're done with this slide let's go back to the thing okay if we're gonna demo fail you know and embarrass ourselves you guys want to be in on it right so yeah yeah all right so the train wreck is what it's well yeah it's well underway all right it's okay so i think the next slide actually has an image of sort of chai so what you can see here is

that if you sort the distribution of frequency and put the largest one at the front it's going to be e t and a and so on right so what you do is you take all of the buckets it doesn't matter how they come out it doesn't matter what you label them at the bottom you just sort them by popularity and you compare this distribution distribution so this is the letter distribution of all the letters in the alphabet right e being the most common and so it has the highest frequency of occurring right chi uh is a measure of how well the text that you're measuring matches the expected letter frequencies of english or it could be german we don't really

care right or it could be any language etc but uh what you're looking for is you know if i had a high chi there'd be a clear uh signal that this is starting to look like language and it's starting to match english right uh if you have a loci there's a lot of randomness and it's looking like noise right so as we test each one kai is the test that we're using to uh to say you know well do these settings start are these settings starting to look like what we would expect to see in a message what uh body how big does the sample have to be before it breaks down to the exact

perspective that's a good question nobody asked us that at skydock.com they did ask it for at work so the larger a sample we use the better a better performance we get out of the test right so to get this done in uh in under 45 minutes we're using a fairly large sample of 2000 we could probably get this down into the 500 character range and still get a signal to just take a little bit longer probably take us you know six or eight hours to break a message instead of 45 minutes because we also using the software uh has a does a lot of sort of multi-threaded attempts so it's it's not only multi-thread on

the computer but we're assigning the work to the gpu and the cpu based on sort of where we can get the best bang for the buck so that as we identify a setting it might look good we want to explore that a little bit more in depth we give that a higher ranking within the software we spent some time doing that so that ranking kind of pops faster if we use a larger sample but eventually it would occur real quick before this like refreshes uh we start at the bottom of what we call gross high and this is running now right right and we bucket the results right based on the on the high value that comes out we

have 14 candidates at 4.4 16 000 candidates and 4.3 and you know the bulk of them are in the 4.1 category right so then we skim off the top of these uh you know these candidates then roll up into the next uh into the next age stage uh so this is gross kite now what is gross kai based on what what actually gets through the machine when it's completely befuddled um if the stickers if they've gone all the way to 13 stackers and plugged every character to some every other character there's a very good chance that we couldn't do this we couldn't do this exploit because really the only day that's making it through in the first

pass are the six characters that are unstackered those go through the caesarean caesar cipher unaffected so six is a percent of 26 like one out of four five one out of six i think something in that range so every sixth letter is essentially going through uh shall we say all the t's all the all the r's all the s's you know pick any six right in the cryptex those characters are going through the rotors as they should and at least getting through the rotors correctly if the rotors are in the right position we still have a lot of spinning of the rotors to do but if we do get the rotors in the right position

six six characters out of 26 characters will have gone through correctly and that's just enough to eke out some difference of kai in the first pass right it can give you a hint basically it's going to leak a hint that you've gotten close to the right setting ignoring the stackers right so you still have to run millions of tests which is why we're using the gpu but we're going to get a hint that doesn't necessarily always work as i say it it can demo fail definitely we're definitely taking some risks but um where's the fun in not taking any risk right but uh but it will based on the fact that six of these letters are not

stacker that is enough to leak some sort of a message very interesting i don't know how many of you guys know uh uh dave shoots who's a darth vader on twitter he's also a crypto guy and i asked him i said hey david i got a i got a crypto system that uh sort of a leaks enter me it's like what do you mean and i said well when i run a test it kind of tells me am i getting warmer or colder right from the correct setting and he's like what do you mean i kept trying to explain this to him i was like i was looking for is the name i wanted to know what to call it on the slide

uh he's like i don't know of any system like the head right we can't come up with a name for it so we're using the hotter colder game but basically the enigma plays hotter colder with us you know we guess the setting and it tells us whether or not you're you know warmer or colder which is very interesting i mean we're not i'm not aware of any other system that acts like that yeah so you you want to go so we take the next the spectral isolation is the next stage and in this case we break the crypt text down letter by letter and analyze the results for each letter so it's 26 times more complicated than

the first pass uh but only 26 times it's more compromised right it's not trillions of times more complicated as it could be because we analyze them each and still types and and that yields even better results into the third stage which is where i think we bottle those results back up so in the third stage when we combine the stackers meaning to say we take if if the relationship between a and k scored well and the relationship between q and r scored well in the risk and z and y squared well now we can combine those together we need about 10 of those we take the top the best 10 maybe the best 12 recombine them get rid of some of the

bad ones try that in a couple of different ways and and then we get the results out of the third stage that usually gets us pretty close the final stage is fairly cosmetic meaning it's a stage that was often done oops look at that yeah so this is not uh this is not entirely readable right y and other one got caught today id of all over the papers teen agers teenager so we definitely have text here right i mean this is this is getting close right but it's not it's not exactly done uh now based on this does anyone know what that is jack what damn kids right all right no one no one knows exactly what

the text is yet biography who portrays his biography so now so uh so we'll go back to them so very funny i want to joke all day that's right i want you guys to see this as it's happening right so we're sleeping at lunch right petraeus is going to spend some time in the same box with uh manning right bradley

all right so again i i wanted you to see that sort of in process right here it's not done yet but clearly it's figuring out where we are and what it's looking for so at that point it's basically crack what really is going to happen is if the second wheel is off by one notch and this gets into the middle of actually the next slide um i think it's called diagonal and so this is going to be second isolation to explain again of the the e's right they all in the encrypt they all amount to some different letter uh when you decrypt them but the ease if you just took the characters from the e's and attached them together

you still have a collection of letters that look like language rather than a collection of letters that looks like alphabets yeah so if i add can you go back one i can do so uh so i have a group of settings i put my crypt text in my settings i decrypt i end up with this this is my d my test decryption and i go through and i just take for instance i bucket up all the e's then i [ __ ] it up you know a b c d whatever i make 26 buckets if i take these letters t-o-u and so on and i line them all up and i calculate the chi of that combination of letters

is does does that seem to match language right does it seem to match with what i would expect to see in english if it does i'm on the right trail with this so it does imply that it looks like a word even though you could say this word um it doesn't matter that word order or anything like that it's simply the letter frequency but by the way when you put english letters together and the frequency is proper it often makes things that looks like words because it's just the right number of characters are there so this is really important slide right i mean last time we gave the top we decided we didn't spend time here but

this is the bit of math right and if you contemplate this map it's kind of interesting this is the double factorial 26 which is all the possible ways you could stacker a stacker board excellent um there are six uh wires missing so we take those out of the complexity but that's a huge number uh 26 to the the cubed is what we have left that's only 16 000 70 000 options so it's a huge reduction in the complexity so this is really where again the commercial grade do not have a second board right so like by by pawning the complexity that they added to the second board we've essentially reduced the machine down to its commercial grade machine change

just the rotors and those are pretty easy to spin up i mean we can spin them really quickly we have because of this and other things we have to do it an awful lot of times but it doesn't take very much time to spin the rotors diagonal completion kind of touched on this with a knot right i mean you move the notch but you haven't really changed very much um so yes it has almost nothing to do with the first wheel the second wheel will roll over one click in the wrong space so if you're off by one then every 26 characters you'll lose one character but then you'll get it back in the next go right

so if i take something i encryp i put set the notches to aaa i set the message setting to aaa and i encrypt that and i encrypt this is a sample sentence right um and then i'm going to decrypt it uh at aaa so i get the exact same sentence right back everything looks good but what if i decrypt it but i guess wrong i guess aad and aad right again this is a sample sentence but this is screwed up right b z b showing diagonal conflation and these two are wrong actually a third one would be wrong here and then it would go back there's always 26 characters between these questions because this is three different than

this in the same place which means that i don't need to test aaa aab aac and so on um i i can test every fifth one or so and i'm going to get enough of these coming out right to be able to test for kai i'm doing this strictly by capture ciphertext right you're not you don't have any

so we only have about 10 minutes the subtitle of our talk is how i met your mother this is i think why we should know your mother so this is a very similar machine to the enigma you see the wheels again um rather than digits or characters you see a bunch of tabs in here uh and actually these can go up or down you can flip them into position or out of position so there's a lot of complexity that you can represent the machine this is the machine that strategic command was using for strategic larger messages it's obviously a heavier machine power is required to buy it it's not portable then it's not it's not field messages

being sent to mobile units uh wirelessly this was a device that would have been used for digital command often by a ground wire and it was automated ascending machine is a you know spinning wheel and it sends the codes automatically to a machine that punches it out on paper on the other end it's pretty sophisticated process um they also pond this machine in bletchley park with alan turing and the way they did this is really remarkable but it's important to understand this machine is that it uses xor so five bits will give you a full alphabet right so teletime machines at that time would punch tape five bits at a time this machine would xor one of those bits

um and it would actually be all the bits well it would actually roll it up with a key these wheels rotated in order to generate the key and then it would be xor and you get the results and the wheels would index once every time uh the message was was advanced now interestingly enough it has two sets of wheels i'm not sure if it's the left pair or the right pair or if there's another one behind but there's essentially two wheels one indexes and every time you make a character the second wheel indexes occasionally like sometimes it indexes and sometimes it doesn't very interesting um what they did was they got two messages that were it was repeat right it's like it

didn't hear you the first time can you send it again and so they said sure i can send it again no problem so they round the machine back and they send it sent the message through again essentially the same key space but it was not quite right and when you do that it's called the depth and in an xor technology you can take one from the other and you can peel out the two messages and basically you zipper them together you know for each bit that it's going to produce because you have two messages you have to produce two strings of english two words that spell check if you will on each side so you can take the letters

and letters that i could i have two crips and i have a common key i can pick which way the bit would have gone because it only went one of two ways one way produces two letters that are in that spell check the other way does not produce two letters of spell check so that's the magic of unraveling a key so this is from a double from a double sentence so the lorenzo machine is is important in two ways right it's uh here here comes binary right we don't have a computer yet but here comes your first binary zeros and ones making an alphabet as opposed to typing an a and a b which is the median

predecessor the enigma machine you're actually typing in a b c d the second thing that is happening at the lorenz level is your first introduction to nextor which as you will go forward in cryptanalysis you realize all cryptanalysis is based on xor right not the xor where that's the only part of the cryptanalysis right but based on the security of xoring one-time pad with a piece of text right there a text and a key that are the same length so uh so this is uh in that one machine at that one point in time at bletchley park you have the beginning right this is your mother right this is the beginning of computing and cryptanalysis all coming together in the

same place the same time so what does this machine do it's very complicated it's actually very simple this can be thought of as not much more than a counter it has a series of light banks roughly in this region and they count as a decade counter it counts up to like 10 000 or something like that it's incredibly simplistic um what they did is they took the key and they put it into this paper tape in the back and you'll see here and initially they had two paper tapes one was the key literally and the other was the message and they would run them round about like this right and they would xor the two together and they made

one of the tapes one character shorter than the other take so that every time you go around it would be indexed you know the index would change and it would try to message advanced uh one into the key space uh and then we just loop this until and then we count every time they would check the key against the message they would count the number of times and this is important they would count the number of times the characters were the same the lawrence machine was very good about mixing up the characters but remember it had two wheels they essentially owned the first wheel they had the key space sequence of the first wheel but the second wheel was still

a mystery so to break the second wheel they were looking at messages which had a lot of repetitious characters why because control characters repeated return return right space space dot dot there's a lot of repetition in the style of the time and that repetition would show up as a compare again with the xor but for a different reason if two characters were the same in comparison we would end up as being a zero so they were called the knots and they were counting the knots essentially every time they got it five minutes so we need to yeah well they're basically done so they had uh they would count the knots whichever offset of the initial key

space produced the most repetitive characters that's how they applied the key on the first wheel and then they had to kind of play with the second wheel to uh to get it to break they did develop some tricks maybe added on to here some more logic to better break the second wheel and various things some of the additional complexity is that they made it kind of made it five times so it has five counters and it counts five offsets at one go but that's not really cryptographically significant um yeah i love this idea of yankee and king arthur's court right so alan turing leaves blessy park winston churchill has told them they have to take their toys and break them

into pieces the size of a man's hand the secret is kept very well they do use a colossus or two for testing the randomness of one time pads they understand the importance of one-time pads and um but there's this explosion right because alan turing leaves bloody park and enters the post-war england having met the future he's been to the future he's used the computer nobody has used the computer they're all essentially walking around on their knuckles uh in terms of technology and here's this god who just returns from the future and knows about the computer so he sets about immediately to reinvent the computer and people are kind of wondering how uh technology explodes in the post-war

england and of course it's because tommy flowers in particular who sets up the first telephone exchanges in england with tubes really introduces alan turing to the notion that tubes can be a reliable computing device and without that and the poles deciding to approach this problem with mechanicals you know the computer would not have made the leaps and downs that it did during the war conrad zeus was sitting in germany in his mom's basement literally with a beautiful computer and it went nowhere during the war there was no use for it and at the end of the war the computer had not advanced any more than at the beginning the story was completely opposite in england and this kind of sets it

sets the race off and remember the americans americans are aware of this effort right this is part of our intelligence history as well they understand uh you know what becomes the nsa knows about the computer they know about how the they know about the lorenz and the colossus they know about the enigma they know about the vulnerabilities and when ibm submits as the first digital encryption standard the lucifer cipher nsa says you might want to tweak that a little bit we have a suggestion why don't we do this and then we'll call it dez right if that effort is informed no one knows at that point why because at that point we're all completely clueless about the enigma

lorenz uh the colossus uh we don't know any of this history until 1977 but when dez comes out it is informed by this and the government does know about that so uh so back to the demo this is not uh completely breaking in the context of this talk however i'll go back to that uh thank you the perez if i had a t-shirt uh go back another one got caught today uh it's all over the papers teenager arrested that is the hacker manifesto i leave you with a little piece of hacker culture any questions gallop so there's a couple periods of time where uh bletchley park and you know the poles go dark when the germans

throw two new wheels into the mix um the british go dark as well when three new wheels get dropped into the mix and later on they are able to steal one of them so as long as the two of the three three new ones are not in the mix they can decrypt but if one of those other new ones they don't have the wiring pattern for the inside of the wheel so they don't know that um so you know there's a big intelligence effort you know it's like hey all you agents right you gotta go steal me some more wheels right we need to know how they're wired we need to know what's going on

and there's a period of time when all of a sudden we can't read what's going on right and the u-boats are all of a sudden have their way they start blowing up more ships right because we don't know where they are then we get the wheels back we know where they are all of a sudden the ships are safer right occasionally we drive you know something like the lusitania or what's the one we what's the one big passenger ship right that we we drive through there and you know we kill off 500 passengers to make it look like we don't know what's going on right now yeah they're they're sacrificed right occasionally we drive a ship in we blow

up some people because we can't let the germans onto the fact that we know but uh so yeah so there's a one of the interesting narrative stories is uh bletchley park is dark they can't read it they need the wheels um one of our uh cruisers blows up uh some submarine uh does it actually well it doesn't the sailor is like oh my god everybody leaves the trap right get the hat off yeah including the cap because it's going to be a head-on right and uh two british sailors uh dive off the boat swim into the into the sub while everyone else is swimming away go in they find the uh the cipher room uh the guy hands the

the machine and the wheels up to the other guy and first guy in the boat goes down with the sub right he risks his life and you know this these are the stories about how we win world war ii and why we're here today so this is victor of bletchley park um and other yeah this as well i mean we went and considered it it's kind of interesting the psychotic architecture on this building it's like it's even worse it's like the winchester right it's like a combination it's like it's like a lego thing and it's like we it's all stuck together so uh anyone else have any questions yeah yeah could you use your um

your application that you wrote to actually add in some known plain text to speed up the encryption so we didn't do that there's a couple of operational security things that the germans do for a period of time they're double sending the message key so so message key gets set for every message so how if you're the germans how do you set it right so i uh i pick um a message a key i pick let's say abc all right i send abc and clear text to ben now all the other settings we both have in the code book right i send him abc and clear text he sets his machine to abc my machine's on abc i then pick another

message setting for this message right i pick um x y z i rotate my machine no i'm sorry i send with abc as the setting xyz xyz and it comes out as cryptex right he gets something completely different so it doesn't come out as qry qry it comes out as q r y z y right but he types those in and what does he get out he gets x y z x y z we then both stop i change my settings to xyz he changes his settings to xyz i sent him the clear text right well that that double sending of the message thing only occurs for a short period of time at the beginning of the

war because it's obviously you know crypto failed um and we could have just written this piece of software that attacked that it would have been trivial simple stupid simple and it it's not worth the talk right it's not worth your time right because it's too freaking simple and and it's a special case right it only occurs for a period short period of time at the beginning of the war um but uh so there were a bunch of things like that later on they just send it once shout out this guy actually will repair your your enigma machine if you need it so right that's our vendor pitch she's a sponsor uh yeah exactly so uh so there were a couple of

operational things we made a decision not to try to take the right software to take advantage of these little little things that you know that yeah they come up we wanted to write something that really worked on the real complexity of the enigma right not sort of take advantage of some little thing that occurred at some point or some operational problem that somebody might have had so so that's we made a decision to focus on the hard problem that's why it's perhaps interesting that the colossus which is alan turing's you know next work does a kind of frequency analysis right it is is the character the same or not so it's counting one bucket what we're counting is 26 buckets but

it's not a huge leap from counting one frequency to counting 26 although to build the colossus to do that seriously uh problematic so we're we're getting the uh right that the is we don't have one minute to go

all right thank you thank you very much