"What Makes Cryptography Secure" by Eleanor McMurtry, CSides June 2020

all right is that Tim it looks great okay I don't know what's happened but anyway um so I'm a Masters of Science candidate at the University of Melbourne studying applied crypto it's a master of computer science it's all a little bit fuzzy but I'm having a good time and that's the main thing if you want to contact me this is my little CV so you can also reach me on Twitter here so ask cryptographers tend to be a little bit of a theatrical Bunch so I've decided that my talk will be separated into three acts and the first one is a tale of two families two households both alike in dignity in fair Canberra where we lay our scene we have

Ellis and we have Bob they want to talk to each other but their families hate each other so it needs to be a secret am I gonna look at how you can keep a secret in the digital age so they want to say hello to each other but it needs to be a secret so we're gonna hide their message make it look like this hopefully no one else can read that so we're gonna get started what is a crypto system well first you have to generate some keys you may have an asymmetric cryptosystem where one key encrypts and the other decrypt will return to that idea later or you may just have one secret key for

a symmetric system now you also need to be able to encrypt a message with the relevant key and we call an encrypted message a ciphertext finally you need to be able to decrypt that message otherwise it's not a very useful crypto system so you can recover the ciphertext you can recover the message from the ciphertext but only if you have the secret key well hopefully so we would like it if a crypto system can't be broken and we say that a crypto system is information theoretic secure if no one nor adversary can recover the message unless they have the secret key so this is what we would like and let's take a look at one way you can do this

an example you have a secret key not a nor don't use this as your password but just for sake of example if you the secret key ABCDE you can use bitwise XOR you XOR these two strings together and you get an apparently random this is in hexadecimal you're gonna map and an apparently random sequence of bytes as output and it's information theoretic secure this scheme satisfies that really strong notion of security that we'd like and that's because if you don't know the secret key you have no idea what message it is I could if I thought the secret key was this string instead of ABCDE I would get out the string the message frogs but it was not frogs it was hello

so it's information theoretic secure because you have no way to know which actual message was used you have you can only do it if you've got the secret key so that seems pretty nice why don't we all use information theoretic schemes unfortunately first of all no asymmetric cryptosystem can be information theoretic secure now this is a theorem of cryptography I'm not going to go through it is quite quite a long and involved discussion about that but if you want to if you want to have a public key that you don't already agree so if you want to have a public key that everyone knows you don't have to already agree on a secret key you don't have to

meet up somewhere and say hey this is my secret key don't tell anyone so that's that's not ideal you we like and symmetric cryptography and again we'll come back to that later but it gets worse if you want your crypto system to be information theoretic secure the secret key has to be at least as long as the longest message so you can't hurt to have information theoretic security unless your secret key is really really long and I'm sure you can imagine why that's problematic if you want to have if you want to share say a two gigabyte file that maybe some authorities would not like you to share you need a two gigabyte secret key it gets unwieldy and

it's it's not an ideal outcome so unfortunately information theoretic security is not really the goal must at the time you can see these sad faces they are not pleased about this this moves us to Act two and in actually ask are you feeling lucky so what we're going to settle for we can't have security we can never have this situation where no one can recover the message with that the secret key sorry settle for something that's a little bit weaker we call this computational security and a system is computationally secure if no efficient adversary one that runs in a decent amount of time obviously you know if your adversary has given a billion years so we don't really

care if they can break the system because their sons gonna die before them so we say it's computationally secure if you can't do it efficiently unless you're really lucky and this is this is the get-out-of-jail-free that's gonna stop us from running into that problem with information theoretic security unless you're really really lucky there's no way you can recover the secret key and you may be wondering okay well what is extremely lucky mean luckily we've thought of that and this is some massive stuff if you're not from a massive background don't worry about it the idea is we want the probability to be negligible and that means smaller than reciprocal any polynomial in other words it goes to zero zero really really

quickly faster than any polynomial x squared X cubed whatever you like so we're gonna say if you're really lucky sure I guess you can get the message but you have to be extremely extraordinarily lucky and we'll say that's good enough so the next thing that we think about well okay we have this notion of security we've agreed okay we can't have no adversary recover the message we're gonna settle for it being really unlikely that they can grab the message back out how do we prove that a system has this property and you know we can make lots of strong arguments we can say well look it's it has this thing and we know that this is a hard problem to do

so they shouldn't be able to break it right now a cryptography like myself or photographer in training thanks for themselves that's not good enough we need a rock-solid proof we need a strong convincing argument that our system really does have this property otherwise you know you can think of all sorts of schemes that maybe have the property but it's not good enough it's not good enough to protect valuable secrets like your bank account or you know that's really embarrassing drunk party photos that you posted as a teenager we need something better than that so we start to think about games the idea is the Challenger and the adversary are playing a game against each other and the adversary wins this

game if they can break the system so we're going to play a game hopefully the adversary can't win let's see how we can we'll see how we go now one basic such notion if alice is sending a message that's either zero or one so one bit to bomb someone watching them shouldn't be able to work out which one Alice sent so you know Alice's sent one of the two you shouldn't be able to work out which one she sent that seems like a useful property to have let's look at how we can make that formal we call this the indistinguishability game or indistinguishability under multiple encryptions is an extension the idea is to ciphertexts remember an

encrypted message to ciphertext should be really hard to tell apart or it should be hard to tell what corresponds to one so here's how we're going to do this first of all our challenge and C is gonna run the generation algorithm they're going to generate a secret key and the adversary is going to think of two messages they're going to say to the Challenger you're gonna encrypt one of these two I don't know which but you're gonna encourage one of them and the Challenger says yeah all right I'm gonna flip a coin if it comes up heads I'm gonna send the first one encrypted if it comes up tails I'll send the second one encrypted

and now the adversary has to guess which one the Challenger sent so clearly if they can if they can win this game reliably they have broken this indistinguishability property they can tell whether the challenge an encrypted 0 or 1 they can tell whether Ellis send 0 or 1 - Bob sir the way we're going to think about this you know it's all well and good to think about ok we want this game to be hard to win but again we like to make it formal we like to make it rigorous present a convincing argument so what I'm gonna say if any polynomial time adversary and remember if it's not polynomial time it takes forever so it doesn't matter if

any polynomial time inversor II has a probability of less than 1/2 plus a negligible amount now you might be thinking didn't we wanted it to be negligible well I mean think about it right the adversary could just toss a coin and half the time they're going to happen to toss the same result as the Challenger so as we say instead all right they're always going to do at least I've always got at least a 50/50 chance of guessing so we're gonna say it's barely better than 50/50 and if any adversary no matter was has no it has only a tiny bit better than a 50/50 shot at winning we say it's indistinguishable secure and this is a pretty desirable

property to have it's not it's not the be-all end-all and we'll see an extension of it later but it's a good starting point and you can already see how cryptographers think about security right it's all about these games these chances with these probabilities we model an interaction and we think about how likely is it that we can break it so let's do an example we're gonna pick a simple crypto system this may be one that some of the audience may be familiar with we're gonna pick a number between 0 and 25 and that's gonna be a secret key to encrypt a message we'll rotate the letters right words by that much and if we go off the end we'll just

go back around so if you know if our secret key is 2y and suffered a's and ends up at b and so on otherwise here's an example we take hello we encrypt it and we get this little random looking string you may already be thinking well it's not really random looking right if this double L got maps to this double n here we'll come back to that but for the time being let's think of an even simpler reason that this crypto system is broken what's the probability that you can decrypt a message what's the probability you can get the message without knowing the secret key well ideally you have to guess randomly between 0 and 25 but the problem with

that is a 1 in 25 shot is not that small so this system is already broken but well user to illustrate how to reason about such systems so if we play the game our Challenger is generating a secret key in this case to the adversary is going to send two messages to the Challenger in this case the adversary chooses a B and a C now the challengers gotta toss a coin they got heads so C Challenger is gonna send the encryption of a B which in this case is C D to a alright we've got an encrypted message a B which looks like C D now a goes huh C D the letters are one apart if they get

encrypted AC the letters would be two apart say say a the adversary nor is the Challenger must have chosen the first message so the adversary can just say all right first message and they always win so this system which we call the Caesar cipher because it was at least Apocrypha apocryphally I'm sure some ancient Roman historian is out there cursing my name we call it the Caesar cipher because Julius Caesar used it in ancient Rome and it's not indistinguishable secure it fails this desirable property and it's useful to think about why and the reason we broke this is the relationship between the messages a B and a C the distance between the two letters that

relationship was not broken okay it was preserved when we encrypted it the relationship stuck around and the adversary could use that to break the system now we call this a oh there's a typo here that's that's embarrassing we call this a choice and plaintext attack hence the header right and the idea is the adversary choice what plaintext to use and because they knew it they could break the system now a real world system like a s for example in the Galois counter mode mode or like RSA when it's used in practice where the important part is when it's used in practice real world systems are not vulnerable to choice and plaintiff to tax and it's not too hard to see why

if you're looking at HTTP connection a secure connection encrypted with a nice symmetric key the first message a lot of the time is going to start something like gets slash HTTP slash 1.1 so you already know a little bit of a message that's being sent if your system is not if your system is vulnerable to a chosen plaintext attack that's not a very practically useful algorithm because a lot of the time either you know the whole plaintext or you know at least a little bit of it so we ask a little bit more of our systems yeah if you use them properly okay so unfortunately as I'm sure if you've ever experienced experimented in the space you might know

it's very easy to mess up some of the assumptions made so for example AES asks you in the CBC mode AES asks you give me a random set of values to initialize with if you forget to give it a random set of values it will be hopelessly broken so they don't they're not vulnerable to these attacks but you need to make sure that you follow the assumptions made by the systems alright we'll come back to that at the end of the talk so x3 as promised we're returning to public keys so if you're not familiar with the idea of a public key the first widespread use of it was in the 70s when Rivest Shamir rivet

Rivest Shamir and Adleman I always miss their name so invented the RSA algorithm and this is the classic algorithm use for public key cryptography it's still used alone at the time today there are differing opinions and whether that's a good thing but it is a vitally important historical algorithm now the idea is Alice and Bob can talk to each other without having agreed on a secret key and that works they have boated they have public keys so Alice has a key a and she tells everyone the key everyone knows this public key a and similarly Bob has his public key B which everyone knows but only Alice knows the funding secret key or private key that

can decrypt those messages so anyone can send a message tell us anyone can send a message to Bob but only Alice can decrypt her messages and only Bob can decrypt his messages so for example Alice may send the message how are you encrypted with Bob's key Bob can decrypt that read it and send the response good thanks you encrypted with Alice's key now this is a different cryptographic model it has its its advantages and disadvantages over symmetric cryptography notably that this is usually a lot more computationally intensive but they both have their uses now I'm gonna focus on public key cryptography because I think it's more interesting I'm biased here I think it's more interesting symmetric encryption is

super interesting too but there's a lot less theoretical depth behind it so here's a better game remember last time that the adversary won because it knew something about the plain text and I'm gonna argue this is a better game because we're gonna encode that into the system we're gonna make the assumption the adversary can always encrypt a message they are always able to take whatever message they want and discover what its encryption is and if we're if our system is secure with this stronger assumption well it's a stronger system so it's exactly the same you might notice is the indistinguishability game with one little addition the Challenger runs the generation algorithm they get a public

key and it's secret key the Challenger gives the adversary the public key and also it gives it access to the encryption algorithm so we're not even assuming how it works as a secret we're telling the adversary hey here's the algorithm if you want to encrypt a message knock yourself out now the adversary with this information is going to send two messages whatever it likes to the Challenger challenge is going to encourage one of them according to a coin flip and the adversary is going to try to guess which one got encrypted and again we say exactly the same thing if they have if they have only a tiny bit better than a 50 a shot at winning it's in CPA

indistinguishable chosen plaintext attack huh secure all right so it's a stronger guarantee if we if we can prove our system is secure by this these terms then we've got a stronger system and this is something I want you to think about if you're not a cryptographer we have different guarantees different types of security some of them are stronger than others so you know there is no one definition of security it depends a lot on your model just like anything else in cyber security all right so we're gonna end by seeing how to prove a system satisfies this chosen plaintext attack security but first we're gonna have a little bit of maths if maths isn't your forte I apologize

you don't need it to follow the essence but if you're curious and read on so modular arithmetic it works like Locke you've got a clock it points at five o'clock you add eight hours you end up at one o'clock and the way that works is we do our addition and then take the remainder modulo 12 all right so this mod thingy here if you use to programming a lot of programming languages use the percent here the modular operation says divide by 12 and take the remainder so divide 13 by 12 if you get one I saw you get zero with one remainder that remainder is 1 so our result is one o'clock we call this

addition modulo 12 it's just fancy name and it turns out that raising things to powers is one way if you do it right so if you make the right choices raising powers is one way you know gee you know q and you know that Y is equal to G to the power of it oh that should be P Y is equal to G to the power of X mod P that should be hard to guess X so you know all of the ingredients you know you know this this base number G you know the final result Y you know what we're taking the modulo of but you don't know X it's hard to we call this the discrete log problem

and it's the basis of a lot of modern systems it's not too hard to grasp so it's a nice one that I thought I would choose so with the right numbers is a little explanation of what I mean by that down here there is a lot of complicated reasons why that is the case so hard to guess again that's that's a pretty loose term and we want to define what that means formally we want to have a convincing argument for what that's supposed to mean so we call this the decisional diffie-hellman game and the reason for that is because as a system DV Hellman or th which is used to agree on keys and it relies on this assumption so recall

it the decisional diffie-hellman problem and the idea is Challenger chooses three powers a B and C tells the adversary G to the power of a and G to the power of B and then either G to the power of a B or G the power of C is sent to a the adversary a-- and then the adversary has to guess which one was sent so the idea is if you if you could guess X if you could undo this exponentiation then it's easy right just undo the exponent if it's a be sweet if it's not then well you know which is which so given that exponentiation is hard it should be hard to do this so if it's hard to do this we

say all right this is a strong basis for our security and some of you might be thinking well why do we have to assume that this is this is hard how do we prove that the answer is I don't know and neither does anyone else it's quite difficult to figure out whether problems are hard in computer science quite a fundamental problem that we keep running into so a lot of the time we just assume something like this is hard and if someone manages to break it well you know there's quite a big incentive to break it so summer manages to break it then we'll move on to something else but for now this seems pretty sacrosanct

if you make the right number choices it is very hard to undo exponentiation now we can turn this into a cryptosystem go a one-way function something that's hard to undo if you don't know the secret so gonna pick a random number X that's gonna be our secret key another random number well take G or the power of X we end up with Y which is the public key and remember it's really hard to undo this right if you don't know X it's really hard to guess what it might be so we can tell everyone what weighs and it'll just look like a random number to them if we're gonna encrypt a message and add some

details pick a random number I'll put this thingy which is a pair of numbers we're gonna decrypt it well because we know X we can take the first thing raise it to the power of X and then we can just divide through and we end up with a message so crucially we had to know X if we didn't know X we couldn't raise this the right power to make it cancel out the Y all right so this is the el-gamal cryptosystem it's one that I'm quite familiar with and quite fond of I'm using it a lot in my research so here's the grand finale we're going to show if you break out Gumbel's security then you

can break decisional diffie-hellman and that might sound a little bit strange isn't isn't decisional diffie-hellman meant to be hard exactly the point is if you could break El Gamal then you can break decisional diffie-hellman but you can't break decisional diffie-hellman so you can't break out Gamal so proof by contradiction so we're going to try to break decisional diffie-hellman knowing that we can already magically break El Gamal we have been given G to the power of Ag the power of B and we're given one of these two things is a change with a B or G to the C but we don't know which one our job is to work out which one was sent to us so we're gonna we're gonna

grab Alice hello you're part of this now we're gonna play the indistinguishable cpa game with ellis but instead of letting her encrypt things were secretly gonna give her this fiddled function right I should have put what are M times y is the power of B here right should have given her that but I'm gonna give her X which is either G to the power of a B or see and she's gonna be none the wiser and notice this in this case if I secretly was a then well G ^ a B is the same thing as public key ^ B which is what it should be so if we were really were given G ^ a B this really is

encryption but if we're given G ^ C that's some random number so this isn't encryption Alice doesn't marry but it's just complete garbage so if Alice wins the game if Alice can decrypt this message recover decrypt the ciphertext recover the message we're gonna guess that we got cheated the power of C I got that backwards we're gonna just guess that she got we got G the power of AV otherwise Anna guessed gene for power maybe I don't see so remember we're gonna be given Alice this fake encryption function and she's gonna try to break it if x equals power achieved of the power of see Alice doesn't see a real encryption so she has no hope of winning best she can do is

guess randomly so we're also just gonna guess randomly but if X is GU the power of a B Alice sees a real encryption of her message that means she wins more often than not write a little bit more than a half and we said that Alice could break algum well we assumed that we could break out Gamal but decisional diffie-hellman is hard so there's no way that Alice can win more than a tiny percentage of the time of other half right the fundamental idea is if Alice could break the system then we could break decisional diffie-hellman but we can't so she can't and that means that the el-gamal system is into CPA secure if we assume this deep this difficult

assumption which is it's pretty high so quite a lot of empirical data to back it up by this point so the conclusions that I want you to take away especially if you're not a cryptographer if you're not a math C type cryptography in most of the time in practice is probabilistic so we're not saying you can't break it but we're saying you can't break it in reasonable amount of time unless you're really really lucky now another thing is we're really sensitive to the assumptions that we make I already said that a s in CBC mode you have to give it a random bunch of data to start with if it's not random then you're busted

similarly if you can solve DDH if you choose the numbers wrong such that you can guess the difference between the two things our gamma was completely broken right we only proved it was secure if you assume this property and also you need to reread the specification carefully it's gonna tell you exactly what is and isn't allowed you're gonna be like you're gonna be told okay well you have to pick a particular prime number with this certain property and make sure that if you're GU don't pick a dumb number and so on and so forth right so make sure you read the spec really carefully and don't try to implement it yourself this is why we say there are so

many hiddenness of not hidden but there are so many difficult assumptions and fiddly details don't try to do it yourself if you can avoid it and perhaps the most important thing crypto is really interesting the details of how all these things work and how we convince ourselves that they actually work is super fascinating and it's worth a read even if this isn't your main area because we rely on it screw much TLS HTTP DNS security so many things rely on cryptography and if you're interested here are some cool references that I can highly recommend and that is all I hope you learned something I'm going to turn off the slides in a sec

well thank you very much ellen:oh for that out just like through we do have a couple of questions we have one from the slack and just a reminder for everyone we do have a slack channel Patsey science on the baselines campus like there are the webpage for c slides these ones chemical that i you and you'll be able to get the details along into that slide but the question on the slack was what are your thoughts on first quantum cryptography and what are your thoughts and experiences is it gonna change the bold are we gonna do we are we safe are we safe in these yeah we're here it's our that's obviously a really hot topic at the moment both

inside krypter and outside crypto everyone's everyone's interested a quantum computers gonna steal my credit card the answer is maybe they're probably not yes so the the reason if you're not familiar quantum computers use a different approach to your computing or we think it's different at least no one knows for sure yet there's a different approach and that means that there is actually an efficient algorithm that can break RSA and there is an efficient algorithm a variant of it can also break out Gamal for example so the question is asking you know Kate can we use this to a role our secret student yes well not yet and the reason is you need a really big really stable quantum

computer to affect effectively run these algorithms last I read they were able to factor I think eight to ten bit Keys was the best anyone's done and modern RSA uses 2048 bit keys they've got a while to go yet and classical computers actually much better at breaking RSA the quantum computers at the moments bus if we have a sudden breakthrough in large-scale quantum computers become a reality then we need to shift we need to shift our thinking come up with other ideas and the good news is a lot of really clever people people much smarter than myself run Steinfeld on what ash is one of them they've done a lot of work on systems that are safe even

with a quantum computer if you interested the keyword is lettuce cryptography lettuce Li la TT IC e foods like a follow-on to that question just sort of this is why maybe it's quite a broad question I suppose I think EC cryptographic research now as sort of you know not much research is happening or is it like a period of lots of research and I mean he talked about asymmetric crypto in the 70s being introduced as you know we Buccaneer block ciphers upstream slightly very symmetric crypto is it all over well we've got a new world of crypto that's waiting to be invented and a vitally important question um so the way I see it is symmetric crypto is mostly a

solved problem from my perspective symmetric AES works fine no one's found really good at attack against it not very interesting similarly diffie-hellman works really well unless you have a corner computer RSA that works fine we have better algorithms using elliptic curves nowadays but you know all of that stuff the fundamentals fine sold problem um where it gets really interesting is applying these ideas so in the last decade or so there's been a huge amount of research on what I call zero knowledge proof and the idea is I know some secret value I'm gonna prove to you that I know the secret like it I'm gonna prove that I know the secret key but I'm not gonna

I'm not going to tell you anything about the secret key so that's one really active field of research at the moment how do I prove more and more complex things it's relevant to I I fear to say the word but it's relevant to blockchain research as well because well how do you verify a Bitcoin blockchain you start from the beginning check the first hash check the second hash check the third hash it takes forever and the blockchain is huge I think it was like multiple terabytes when I last heard so a lot of research is focusing how can we prove facts how can we prove things a legitimate in more efficient and more flexible ways so that's one thing the

other thing post quantum crypto as a huge flurry of people working on what are some what are some future future proof one of mechanisms sorry future proof crypto mechanisms that might replace the ones we've got so I'd say it's a very active field but we've moved away from a lot of the more foundational stuff there was an extra question on the slack from maybe here asking if Eleanor has any favorite PQ systems that are cool and all should win

so I hopefully have I am woefully under ed in the area but a lot of systems are really exciting the idea behind it is you have a linear algebra problem so you've got a matrix and you've got a matrix equation and the idea is you've got to find a solution to the matrix equation but not just any solution it has to be a solution and remember it's my solving for a vector so a list of numbers has to be a solution with a really small magnitude so if you add all the numbers up it has to be has to stay quite small and that's interesting to me because without Gamal it's like well if you

guess the secret key the game's up with a with a letter system it's not you can't just guess one possible answer you have to guess an efficient answer and I think that's really exciting that there are lots of possible secret keys in from one perspective I think that's really interesting and shows a lot of promise but um I wanna be stupid on the area so don't quote me that was great that was great and I think there are any white legs on a slow-mo black but I think a lot of people clapping and cheering and talking about your talks they probably had good there if you can and could keep clapping so thanks for yeah