A tour through the magical wonderful world of crypto land

Stockton's hi everybody my name is Ben ager and this talk is choose your own adventure through crypto land or we are the choices we make I take back Who am I I played with some crypto systems I've actually worked on some algorithms which was nb6 I do re I've worked on CTF what's up okay No No please keep area because of that I'm gonna throw you the ball you get to be my first victim so during this talk there will be a ball that will be flying around so you may not want to stare at your laptops this entire time and that person will choose where we go next this talk is very breath heavy depth

light I will try and make explain intuitions I'm not gonna go any too deep into one perfect I'm gonna hit as many topics as I can and essentially do a whole freshman crypto course and or well a whole crypto course in about an hour if you have any questions for what I'm talking about if you have the concho you can ask me about anything on the slide anything in the day anything anywhere as long as you give me 30 seconds on Wikipedia to try and remember it so we're going to be voting by beachball because majority rule I've had major problems with because you can never distinguished between option A and B this slide deck is long and it's about

250 to 260 slides you're not going to see all of it this was on purpose so that this way everyone goes a little bit different but that also means this is going to be a little bit choppy I don't actually know what transitions you're going to pick which makes my life a little bit harder we're going to do this DFS so if we do BFS essentially go top all the way down top all the way down we end up incurring the large overhead instead it's going to be top go up a subject top go up so subject pop off the stack at the end at the end of each section you can do whatever the hell you want you can tell

me you start at the beginning you tell me you click one of the links and or you can ask me any question good luck and thank you for playing with me so you're walking into a forest and an old gray cryptographer comes to find you in order to survive you must choose what we would like to know about to keep the secrets in cryptography or tomorrow who's got the ball you got choose me burn the world ok give the ball to someone else just chop it now the wizard stops at you and brings out DJ Jazzy Jeff who asks a fun question of would you like to know about algorithms or asymmetric protocols bar algorithms so you're gonna go way

deep and now choose an attack you I know about do you want to know about like diffusion and confused you like to learn about differential cryptanalysis XSL replied whoever has the ball has to choose what they want to know now differential cryptanalysis so this is going to be fun because we talked nothing about anything and starting in the middle of the it's ticklin time differential Cryptologic at axe were called off were originally called tickle attacks because if you tickled the bike's in just the right way you get something unexpected out you see something you weren't supposed to and essentially what it the way I think about it is ciphers are supposed to violently change 50/50 chance of

changing the output of any bit essentially at random we ascent do we attend instead what we try and do is we late try and link to invocations of what we do with that once those two are linked we can actually figure out something wrong here's a simple cycler this is actually a three round cipher that was used in a CTF and what we can see is it consists [Applause] asuras were in the act now it's an SP cipher and what you're actually seeing is this guy showed that it only mapped to these 1 2 3 4 5 5 separate subjects so you can actually isolate and look at the differences now what that means is

when you're isolating it it would start to detail information it would start to leak up information about the key because those [ __ ] didn't propagate all the way down to keep on going and looking at the tiny tiny differences because the propagation doesn't flow the entire which makes confusion harder anyway so we can make guesses on that and we can understand so just looking at the differences but there's another type of differential cryptanalysis these are called missing the middle or impossible differential crypt analysis this was what was actually used to break a good chunk of an in ever actually decrypt to that same level so this may greatly decrease the entire space of what you

had to search to break a Meninga and this magical little attack this magical little thing rigidly found in the early forty's essentially disappeared for all literature until it was rediscovered in 1994 fifty years a group of people knew about this and the rest of the world didn't and just you have to keep in mind throughout all of this everything's related and you're just looking for relationships where things don't change as much as they should Finn okay who has the ball sweet would you okay we'll go all the way back to there's a lot of them will go all the way back to the start because I forgot to hyperlink that slide and we'll go with you you want learning about secrets

are burning the world down you want to keep the secrets okay so the old man strokes his beard drunken bad et impersonation asking the light is what binds us it's what makes us whole wondering what you would like to know about do you want to learn about touching your own internal light or touching others legs cool so so asymmetric cryptography is essentially when two people try and talk to each other

a little bit of asymmetric cryptography for encryption key exchange is how do we get to the point where we can get [Music]

promised this guy said this that's all so now we must ask which type of light would you like to know about would you like to share this world here of others he espies you like to go old school the new cool damn it the new school so I'm going to give a little bit of history on this talk for 30 seconds this was originally given at summer con so there will be references to drinking games in kursi I've scrubbed most of them but there are few that are still there so I'm going to use my yeah so there's two terms at the top of this can I show the a give me 30 seconds while I look

for a slide cool here we go we're gonna just ignore otherwise yeah so essentially diffie-hellman is three separate problems decision which says I have these three numbers can I tell if they are related in a specific way then computation cannot give in two numbers can I find the third number these are all the groups of size G with order Q doesn't matter and then there's the discrete logarithm problem which we think just because this is at least disappearing which takes these are in order of hardness decision diffie-hellman is easier than computational diffie-hellman computational diffie-hellman is but we cannot say in this as parks does that make more sense sort of now you got three numbers and you're trying

to relate them first question are they

and we actually used to believe that CDH is really important then we'll go back to the next topic at that so when many people actually say diffie-hellman those three little things so the entire thing is given these two numbers how can we both find a third [Applause] we can agree to start talking and start working together that's what diffie-hellman is so the actual how do of it is lowercase G is important because uppercase G means something different P is some large safe Prime with some order that's big then G is a generator of P which literally means you if you multiply it by itself and then mod it P all of these the actual agreement about

Alice chooses a Bob chooses be about Allison's Bob GA you essentially do module mod mo which is multiple I'm sorry Pam I'm not model that was really wrong because computational diffie-hellman is still friggin hard and so we actually can agree on a secret while everyone's looking at it now the reason why I took that is cuz we're going back to new school where we go more into computational and decision diffie-hellman I know you're all really happy about that so in this world decision diffie-hellman is easy computational there are two groups uppercase G up this g1 up kiss g2 they can be the same you thought you choose something which mat you have a magical function called a wheel

pairing that maps elements from G 1 into G 2 essentially that says you can go from here to here and some magical thing happens so map G to the a G to the B is equivalent to G this CG because you can multiply them outside of it you can actually multiply the exponents you're raising G 2 and have them actually map to each other so yeah now BLS we have our magical mapping function we have all those fun things and you have some point that's our generator we can actually make a signature scheme that's extremely small out of this so someone chooses a random number less than Q where Q is about 152 bits and

just publishes it and that's my public key so normally I went how public users are like 4096 bits because as a 4096 bit key I think it might be 400 bits somewhere around there I can never get the numbers right you can google it after me so in order to sign what we actually just do is take the hash of M multiply and you'll get Sigma and then you just multiply its it you send out Sigma and M this is because Sigma is essentially X M so everyone making my life super friggin easy that's why it's the new school cool because it's so easy to do and starting to enter into all of our lives sorry man I'm only twenty minutes

in you got another half an hour cool who has the ball cool keep the secrets for 200 Alex

symmetric yay so entirely out of order fashioned symmetric cryptography that will take e of my messages secret key in the M Prime which looks like an anime up and then giving me a decryption function and D of M Prime and K gives me my original message back literally all it is make magic happen here so now what do you want to know about do you wanna know about like the ideal model of ciphers and how we think they should work how ciphers actually work or what we think the world should actually do so like what would make a good say how ciphers actually work fun so the wizard strokes is beard knowingly and longingly these

were cracking like puns that I decided to put in here I'm sorry how many of me feistel ciphers so here we go back so the wizard offers you a riddle I do I can give you a magical box that can take a random Oracle the most magical boxes and give you a random output yet I cannot go back give me [Music] [Applause]

how do I make a psych around this and we have the feistel network so the facial network is actually how a lot of

essentially what they say is I start I take my message I split it in half in the middle I then have my magical key function I saw that with the left half put it on the right and move the right half together to the left keep doing that so essentially sort keep going around and if you do this three times you will have a strong cypher four times you can have a stronger cypher and it's a very simple construction because it's really easy to program and you can take these pseudo-random functions and actually do it and here's a little bit of pseudocode for those so inclined because this is the entirety of it like a feistel network in cipher except for

magic function where magic function is a 31 or lo 300 line magical thing in the middle that's all feistel networks are decryption is quite literally you saw that one wheeze or below it instead very very sneaky now why do you care so we've been moving away from them do to speed concerns lately but by and large a lot of modern crypto is still based on but network feistel networks from so many years ago why do people do this well first encryption and decryption are almost the exact same operation so it's really really small second it's really easy to build yes sir

[Music]

now why do you need three rounds cause with one I do one round feistel cipher with one two three four five six seven eight and secret I get five six seven eight in my output probably not a good thing so one round you can patently see is [ __ ] why not two rounds I asked you I good friends so you have to keep in mind that each round right those two left those two still have a very strong correlation left and right go essentially go our prime and our prime is essentially left will equal X sort the left half sword with itself or with the right half will equal the will equal the inverse of

itself which is really really bad and so why three well that's where Ruby Lakoff comes in

feel free to google it I'm not actually going to go into it except a state that you actually get to even weaker if you do which is why people love this construction for so long yeah now the wizard goes and congratulate you for listening to him babble on and he gets in an argument where he splits into his other stuff an S shall we play a game or would you like to know ya know des is I think eight maybe twelve I can double-check in general you take whatever you think you'll need and you double it because you're never it's never as good as idea you can google it I might be wrong on that I know it's

more than sorry triple des also is encrypt decrypt encrypt which is all weird and funky and annoying not going into that one right now cool so who has the ball you want to the beginning would you like to play a game or would you like to learn about modes Moe's cool a la mode so you have to keep in mind that's where it gets into [ __ ] so modes are actually very complex in an active area of research and there are many modes we're going to look at four of them electronic codebook cipher block I'm gonna go to the next slide because I actually say what they all are in the next four slides so instead of just

babbling on so 100 comes encrypt them each without any chaining together and padding must be applied to the last block so when you're encrypting them you get one two three four if you encrypt let's say 1 2 3 4 1 2 3 1 2 3 you get the same thing and you can actually see that blocks are identical inside of it metadata is leaking things are horrible I can rearrange blocks and nothing bad happens I can twiddle and bad things happen but yeah and so the obligatory penguin picture this

[Applause] [Music]

don't use ECB I'm sorry that was a little bit angrier than should have been now CBC so you can start with an IV you get a ciphertext and you actually chain it into the next cypher text at each top

this is a good thing but why does it suck it can't be

[Music]

Zor insight into the output which is bad counter mode so what counter mode does essentially turns a block cipher into a stream cipher I had water highway so what this means is I just get a stream of bytes I can just store it it does that by taking account and literally you just count one by one by one and you get a cipher you get a stream that you can actually soar into and where you choose why this sucks the ciphertext is extremely mad sorry I'm from you drink water and the rest of the text will decrypt without issue such as think of changing admin equals zero to admin equal one something I've done before it's bad so now we're going to

this the decrypted text should look like this so it's just saying you cannot actually screw sorry problem will be it will be incorrect so it's really easy to see now if you ever end up building something with crypto we strongly suggest

next is the most popular a atmo it is beautiful it is greatest the worst thing in the world I think Gianna that destroys the entire security and integrity of the program this is a problem however we're going to talk about OCD mode so OCB mode essentially says encrypt the number encounters Zordon twice so zorina messaging cribs or ahead and get counter out you got a set of ciphertext and then you essentially just Zoar them both in at the end and add to the end which means it's paralyze abaut it's easy to use it's really fast technically it's friggin awesome the guy you're a photographer Lucy B was your kinky play three sports and be on his

way to harbor you'd brag about him to all your friends technically it's amazing it sucks cuz of packs OCB is patented so no one friggin uses it sorry Finn have a ball sweet I'm always good with burning a little bit of the world algorithms or asymmetric protocols I agree Oh note that ah damn sorry it's hard for me and click XSL cool now throw the ball to someone else so instead of doing it as I do step one I do step two I do step three think about it as a series of tubes just like the quadratic equation except there 800,000 of them and there's 16 under variables that being said in the general case of a multivariate

quadratic equation send e-cards thinking about these things in sets of equations and relating them together to slowly prune key space fin what the original the original audience for this talk it was a special group of people I said if you get a chance I strongly suggest summer calm cool who's got the ball around the world would you like to know about padding or timing okay so padding sucks bees crime crap was the other one Hartley is not heartbleed some Berkeley sort of all come down to it's a [ __ ] to pad your message so the first ever padding bug and this is my favorite so in raw RS egg you choose an easy exponent three works we met we never go

above the RS al modulus so if I have like my RSA key is this this is my secret which I think says this is a secret m to the e is actually significantly less than n so it never wraps around having sucks yeah sometimes it depends on which group of padding you let's see I think I'm a ap somewhere yeah give me five minutes and so if I take the third root I get em he's too small I get screwed so now let's say instead we pad and it's deterministic that means I can actually distinguish between different states to them that means that it's in CCA when we decrypt if you screw with things if

padding's screwed up and it throws a message that tells me something about your kids if we decrypt headbang in padding doesn't screw up that tells me something about your key we can keep guessing the last letter due to how certain padding seams work and eventually get it out in symmetric ciphers because oh my god we know what the pad is and you gave me an Oracle this is essentially the court of Beast I just keep guessing the last letter so one of the good padding schemes though is oae p o AE p essentially is a pattern that is randomized so that this time every time I encrypt it I actually get a different amount of data it looks

something like this I have a message bunch of freaking zeros and a random number take the message I put the random number through it I sort with the message I take that output or it with that rate and mass number now you have two messages that can happen to one so what this does is the random number every bit of the random number [ __ ] with every bit sorry messes with every bit of app every bit of that message that came out with directly influences that random number so if any of those bits change it messes up the entire message and the padding is done and gone there's also RSA P SS and several

hundred other things if you want to you can look on Wikipedia and get a lot about this this is a sore spot for many cryptographers fin so this is how I feel about Patton okay so let's go back who's gotten the ball okay no it's fine I couldn't care less did you like to keep the secrets or burn the world burn the world God want out of topic soon in this one so DJ Jazzy Jeff is still wondering what you want I should have been cool I've got five minutes so do you want me to go down this thing or is there any questions you'd like me to answer about crypto in general what's cool

what do you want to see we're gonna burn the world algorithms are asymmetric you don't care you know what then I'm going to talk about timing attacks he absconded I'm allowed to so timing not joking so timing is borderline impossible to get right at everywhere so multiplications are pain in the ass and if you don't do constant time multiplication it really screws your things up like it give me your RSA public key oh how do we screw with timing well let's just push the RSA key into the magical freaking thing of random data it'll fix something no it won't no it won't so but because everything needs are on the same time means everything has to run in the slowest

you're giving me things then see about because the intuition ORS a timing is I get a number and a key Brown and timing attacks and essentially what this is is but if I can if there's ever any David I can destroy tell me things I shouldn't friggin now so I've got two minutes left so I'm gonna stop talking thank you all you've been a great audience hopefully I didn't bore you to tears

oh do you talk to these people I did