Introduction to Modern Cryptography - Amirali Sanitinia

okay here we are five o'clock last session before the closing ceremonies and of course a reminder we'll have a networking event at John Harvard's pretty much walk through Harvard down a couple blocks takes about five minutes walks down there so hopefully you all can join us there so for our last presentation I'd like to introduce Murali I'm he's a computer science PhD candidate at Northeastern and his research focus was on cyber security and privacy very apropos for today he's been covered in venues such as MIT Technology Review our steps fret posts etc and he's talked at number of different conferences and keys including DEFCON crypto village and Virus Bulletin so without further ado let's give it up

for EM Raleigh first of all thank you everyone for coming and I'm sorry for being the last lucky thing you on the drinking session further ado today we're going to talk about cryptography and especially modern cryptography so cryptography is really nothing new it has been happening for a long time even in ancient times the use of you use the Caesar cipher or just write the secret message on someone's head and then wait for her to grow and then again shave their head and read the message but today we're going to talk about the modern aspect of cryptography where you have your digital communication communication and you use basic the mathematical properties to secure your data not the physical properties as I

said is very ubiquitous ample it it is in your mobile phone when you write your data you store your photos or even when you make a court call for example using GSM 2g or even 3G calls all your communications are encrypted and if you have support for cryptography in every respectable program language these days even further right now the cryptography for example a ES and sha of functionalities are part of CPUs so this means they are part of your hardware there is no suffering implementation of cryptography anymore they're being embedded in your chips right now even the CPU that you have on your laptop your computer email your mobile and it's really not hard to do

cryptography the right way at least the programming but you see a lot of people making mistakes the big ones for example Debian had a problem in the random number generator which made the secrets vulnerable companies like LinkedIn and Adobe and Ashley Madison they store the password in the wrong way that made a lot of people who are vulnerable and put them at risk and other companies such as snapchat were using a wrong kind of cryptography only using one bit wrong letter instead of CBC for example use they use the EBC and made their secrets at risk and even experts such as the Wi-Fi alliances they when they were designing the web standard for Wi-Fi communications they also made a mistake

so it's not only the amateurs even the professionals and experts can make mistake can make them mistake okay now it makes more sense yep and the cryptography we have two kinds of cryptography at the high level one is called symmetric cryptography or shared key cryptography and the other ones public key cryptography or asymmetrical cryptography if you want to thinker and as in the like in your world and not in computers but in real life if you want to give access to your house your friend so you create the same key and you send it to your friends then they would have access to your house this would be the Tomato symmetric or the shared key cryptography but the

public key cryptography is as if you create many locks and you have only one key for that lock and you only hold that lock and if your friends want to send you something secret they can use those physical locks put the secret in the box lock it send it back to you and you only you are the only one who has the key to unlock the box which would be as if you're doing the decryption in digital world so that would be a analogy for the real-world cases as you can see here for the secretive absorption or symmetric you share the same thing and in public you just use two different keys that are attached

which are and binds to each other but they are different and the differences between them as we mentioned see symmetric in a encryption for example your AES is up to thousand times faster even at the software implementation yet alone then you have it embedded in your CP or your hardware but one of the downsides of symmetric encryption is you need to share a secret for example if you want to give your friend the key to your house you have to have a way of transmitting this secret or this valuable information or physical thing that you have so if you can trust the post office to send the key why not just send a secret to a public medium that's

why the symmetric encryption has problems how to share that secret information that's why in real world we have a combination of the public key and the scenic route key encryption you usually encrypt the key to your secret to your symmetric encryption with that public key you share it with the river you share it with the others and then you use the private key to decrypt that key and use the key of the symmetric encryption to do the decryption we looked at some diagrams to make more sense of it but that's why a real-world situation you usually combine the two together the most famous symmetric encryption algorithms nowadays is AES which stands for an advanced encryption

standard it's also known as rainbow which is combination of the last name of to belch and cryptographers who actually introduced or designed this algorithm it was part of the nist competition to design the next generation of crypto standard this is the National Institute of Standards and Technology and are in charge of standardizing different things such as cryptography and they have some requirements that it should be fast both in software and hardware and it should support block size of 128 and different key sizes can anyone name what was the previous standard before AES for encryption yes des so for example des was fast in hardware what extremely slow in software for AES they wanted to be fast in both

software and for and it was designed by these two cryptographers that I'm not going to butcher their names which was because I can not pronounce it right and they publish the design in 98 and with any standardisation it takes long time so it took them about three years to actually standardize this encryption it was published in 2001 the other candidates were Mars rt6 their pen to fish which you still have them today but they are not as popular as as widely used so I've said this cryptography mechanisms such as AES they work on blocks which means you get a chunk of data you do your algorithm on it and you get an output but the charcoal blocks like the limit

is very limited 128 bits if you have a longer message you need to find a way to increase these blocks separately and somehow mix them together so that's why we call the mods of operation for a block cipher and there are many different kind of them but these three are the most well known the ECB is completely broken if you never use it so for example if you do a cold activity of your program you just search for keywords ECB if you find it somewhere there is something definitely wrong with your code so you have to do something CBC is secure in terms of just the mode of operation but it has its own shortcomings the same as CTR that's what

you have to make there are more secure than EVC there is no way to make ECB secure but CVC and CTR door based make them secure so this is the ECB pattern can anyone like spot what can be a problem with easily

so that's somehow correct it what to put it accurately for example if you have the same plain text it will produce the same ciphertext so it kind of reviews the pattern in your file or the order secret that you're encrypting because it is some message of something is being repeated in your message even the encryption is going to be the same in your ciphertext so that's something that we don't want to reveal a pattern because it would be used as a side channel you want something that kind of gets rid of this so if you use a look at the CBC whenever you encrypt something you just use that encrypted value and pass it to the next block and you XOR

them together so even if the two block 1 and block 2 are the same the encryption of block 1 and block 2 is going to be different and to make sure if you're using the same message multiple times with the same key we introduced this notion of IV or initialisation vector which is a random value to make sure even if you are increasing the same message with the same key each time you're going to get a different ciphertext because of that IV that's being X or in your value the CTR uses the same notion of IV but they call it the counter and announcement so you have a counter that each block what one block

to block free block n that is the counter of the block and the nonce U is being acted as lucky IV or the random value that you're using can anyone spot a benefit of CTR over CBC specially in speed exactly so here for example if you look at CBC if you do not include block one you wouldn't be able to include blocks to or blocks free you everything need to be in serial C which means it can be slow maybe twenty years ago it was okay because we didn't have that much of luck multi-core CPUs multiple processing programming nowadays CTR would be more better and one of the other advantages CTRs and support n is anything such as

PRP or butt CBC News on these prf this is more advanced oh it's not important but most important is their parallelization so to put it in pictures if your original pictures with a linked Linux penguin if you encrypt it using something does this ECB so here we just get the values of the PNG format and then include those values you see you can see the pattern you won't see the actual image but you can see what was the pattern and here you can select it this is good enough for you to know what was being transmitted but in CBC everything just looks like a garbage you want to be able to distinguish anything so and that's

there snakes like intro of the symmetric encryption as we said we also need a public use cryptography or asymmetric the most famous one is RSA which is the combination of the letters of the first three people who have first letter of the last name of the people who created it the Ron Rivest Adi Shamir and learn or other men both of them very famous in crypto community and Ron Lewis is actually a professor just in MIT if you want to go visiting and they publish their standard exactly forty years ago so it's now being 40 years that we have this group so and for spatter 92102 thousand and now the pattern is in the public so this is the public crypts of

ibrutinib and the mathematical idea behind it is the hardness of factoring prime as a composite number so what are the prime numbers prime numbers are the numbers that are only divisible by themselves and one for example 5 is a prime number because you can always go in 5 and 1 but something like 6 is a composite number because it's a multiplication or a result of 2 times 3 and factoring some number like 6 2 2 & 3 is very hard in large numbers when I'm talking to like three four hundred digits of number nor two LEDs so this would be a overview of the textbook RSA the details are not that important but P and Q are the two numbers or the two

prime numbers that you generate and the size of them is something like three hundred digits or larger and when you do the multiplication you get that N which you would be using for your private and public key and that is something that's hard to factor so when you get n it's really hard to find out P and Q but that's the open problem that's what we believe to be a hard problem but no one has a proof that you cannot do it within the like the p-type as part of the complexity classes it believed to be secure so to give you an example for example you take two primes again here is just an example you

should never use these numbers which should be three hundred digit I repeat that one more time five and eleven your end would be the combination fifty-five your fry-up and would be four times ten forty and if you choose your public key is usually either three or two to rot 60 minus one because the way that the binary representation has some properties which makes the encryption much faster that they're all one the public is known you can just use some value like three and you calculate the private key or D based on your e in this case it would be 27 because the multiplication of 2 would be 81 and 81 module four D is one eight 40 times 2 is

80 and 81 is only one number larger than 8 so it's 1 because E and D should be 1 mod product and for example your message is a 2 and if you have a text message you can just represent as ascii code so that's why everything if you consider everything as a number we can just include numbers here and for example for character you can just convert it to ascii code and include that number so you just use your ear or the public key to exponent to the N and you get your ciphertext and again if you use your D eight times 27 would produce V 4 for the same message for you or your message but

one of the problems it's a RSA that takes RSA or the example that we showed it's not secure can anyone spot again what could be the problem is something like the ECB so insecurity or cryptically the Inc CPA secure which means if your message 1 and message 2 are equal your encryption of message 1 our message 2 would be equal as well because here if you're just raising one number to power it's always going to be the same so 2 to the power 3 is always 8 not no matter how many times you do it and this is again something that we don't like we want to some level of randomness if you include 2 one time and

the other times you want to get different psychotic that's why we use for real-world cryptography problems uses OAP mechanism it's again something like the mode of operation if I use for your AES it's how you use your your base or primitive crypto and here you just add that or a random value and those G and H are rendered to hash functions for example sha-1 or something like that and you XOR those values and you get a value the R or the randomness is an important part here that from two same messages you can get two different psychotics that's the reason we're using door and that would be a conclusion of our asymmetric cryptography so unhide

functions anyone can give an example where do you see hi hi function we use okay exactly digital signatures or even something very simpler whenever you want to fight download the file if you notice they usually give you a md5 sha-1 or short we take some of the fight to make sure the thing that you download it has nothing corrupted the property of hash functions you get a very long input message and you produce a short or constant size output for example your file is 1 gigabyte you're out you still 1 can be 1/2 and 80s we want to exist be 60 bits you don't want you want this constant small value and you wanted to

have three properties one of them is it would be hard to produce the number or the value that created this hash for example if I know this hash of 2 is XYZ I want it to be very hard from XYZ you would be able what was the actual thing that hash to so that's called the preimage property the second preimage is if you have message m and another one M Prime you want it to be very hard to find another message that has hashes to the same value one this hashes to be different and the third value is to it would be hard to find any two messages that will produce the same hash for example if you

produce one for hash of any file it would still very constant size small and fast but it doesn't have any of these properties because it's obviously the same values and all messages will produce the same thing you have collision there are famous examples of hash functions right now - - and high street shall one used to be good but trying to phase out but as of now it's broken or as they call it shattered because the Google team team could find a collision of sha-1 value that's why we don't it's not we going to use it anymore it's now in practice also broken and if you go to the shattered data of website you can read more on how they produce

these cohesion values and to just give you an tabular conclusion of hashing function to give you some very basic example how easy it is to actually use cryptography in program languages this is an example in Python the first two are the inputs for example if you familiar with C Java this would be like your include or your import of Java you just define the libraries that you are using inside your program you just define object hash object and you say what kind of hashing you want to use here before now we are using short - that produces 256 bit digest for you and you say the value that you want to create a hash for example here besides

bus and 2017 will produce that hash for you and this value is at least base64 encoding of the bytes values which means you only get 64 values here but that's why they always look so random looking when you haven't like proper text like this I Boston you just random value there so that would be to produce our hash - in the program language for AES is again the same T to get random values we use the U random Linux platform you can just use the Python it's supporting different program different environments but just a curated random value one of the securities use the U random or inside your limited with the devil you Randall and you get a random byte array of

sixteenth and you use as IV and a is because if you remember we said in CBC mode we need to use IV for providing what the randomness right so that's why you get your IV and your key and you pass this cipher message that you need and if you remember we said a AES works on blocks of size here you don't need to pad your message because the length of b-side 2017 is actually 16 and 16 is 128-bit this is by chance if it was shorter or longer you had pad to pad your message and make it a multiple of 16 bytes then you would be able to encrypt it otherwise you get an error

for example in CBC mode and the Decrypter is exactly the same thing you just define your functions and you pass with your ciphertext and IV and you get the decryption for RSA again the key size 248 this is the to 48 bits for that private key that is that p and q the prime numbers that we are talking about they would be about 500 digits of number for example 100 is the three digit number so 500 digits would the digit number is a large large number and as we said for public exponent or e you can use values like 3 or to the power of 16 plus 1 because of the property that they have in binary format they provide some

fast modification and some fast explanation functionality that's why these are you can usually use these fixed values and from the private key you can calculate your public key but from the public key is not possible to get the private key and that's the whole property from the public you won't be able to calculate the privacy and for encryption if you notice this is the Oh a P we are talking about when you want to creep create your RSA you want to say what kind of RSA you want to using or the standard or the protocol of the RSA you want to use it you want to use the OAP to produce that in CPA security property

and those gnf function that we are talking about here we are saying that use sha-1 for that functions GNH and then you just pass that hashing algorithm and you include the message for decryption it's the same property but you only using the private key instead of your public key so the final takeaways for this talk is don't invent your crypto algorithms for almost every functionality that you need dark crypto front of libraries and algorithms that have been developed by cryptographers being tested for a long time and we are not we know they're secure also never implement your own crypto library because it might be look very easy to implement all these functionalities but you need to think about side-channel

attacks for example one of these concept that time comparison if you want to make sure two values are not the same if you use the normal life normal comparison as soon as two things are not equal it was going to say false and return but in a constant time you go through the whole message and then if they are not equal you return back so base if they're just return unfair if two things are not equal at the first life and it returns it takes a shorter time that if they're not the same at the last bite so we by using this simple comparison side-channel attacks you can actually get a key or even the decryption of a

message so that's why is to get the actual implementation of crypto library is very hard and even still people get it wrong even the expert for example openness or so from the time you see there are some voluntary T's because it is because they made a very simple mistake that they will realize that it has these consequences and there are experts who make this mistake so even the amateurs will make much more mistakes doing the crypto using the libraries is not that hard as we saw it's just simple statements in every programming language but we still see people get wrong it's because whenever you find it source most of them might be wrong or updated for example if you look at the

internet on RSA a lot of people use these values the small single digits values of P and Q so if you don't know that these value should be hard to see this way this is the example it makes sense to me it encrypts the message you decrypt the message you should be good so you might be using that and they're having examples of using this wrong numbers inside real libraries for example you go to get out of something called salt and you look at their first evaluation you can see that they actually make made this mistake of importance in the crypto library and if you have a data in transit missing meaning going from point

one to point D on the network you can simply just use the SSL protocol or and there is a function library for it to encrypt that transmit your data and if you want to have some data at risk for example it's going to include the file and store it on your computer you can use come something called the PGP protocol it's a combination of the public key private key and hashing functions to make sure whatever file you encrypting is secure is you can transfer it to other people and no one else can tweak something your message without you noticing so these are set of protocols that using all these three primitives of cryptography that we talked about you

can use any of these two at these two and you don't even have to implement them there is already an implementation of all of them available and actually thank you store any questions yes

yes perfect so to just to repeat the question the question self things or to consider when you want to generate random number so on Linux platforms there are two sources the entropy or randomness you have it's a dev slash random and you random but the problem is random is blocking it music there is not enough entropy inside your computer and if this entropy comes from the from the temperature of the computer the mouse clicks that you do all of these things run from the physical sources it produces a random number and if there is not enough it would block but you random a is not non blocking and for cryptographic mechanism is as secure and

for example in the Python programming language we can use the OSU random and always use the cryptographic safe random number generators not the random random number and inks that you have encrypted in your normal libraries because you also have the random number in your libraries but the office have a constant seat always use this cryptographic secure and open if you use the operating system random number generator or usually safe

so that point will be smaller it's not like some of the exact cryptographic properties in mathematical if you go to a cryptographic stackoverflow you can get the perfect example expert not me that they have there but the reason they're using these two constant numbers is because the both of them are all the values are 1 and that makes the exponential function functionality much faster when you want to do something to to external and sub to something yes yes so the ideas or death they have something called the privacy differential analysis attack that was first I think released by IBM but they had to hold on to it the history I'm not sure exactly what who know who first and

then they realized but if I'm not mistaken some special research labs knew about this functionality before it was publicized and after it was publicized they realize it's not as secure anymore and the other things was the key size the key sizing ves is much smaller which makes it easier to brute force especially nowadays you be have the heart horror capability probably anyone with not even large amount of money you can buy these dead crackers that's what was one of the problem the other most was this differential analysis attack which reduces even these key states that you have to search for and that's why they have these Triple DES to make the key size larger but again because the

budget was that differential analysis problem yes please

and no even right now if you look at the for example some pita nsab suit or even at their new CN sa form they always recommend using some like just GCM at the base it uses the CTR but the things it's also authenticated which means you don't need to do the hash or H Mac the H Mac or something like for your fight but GCM is more involved and to introduce it here will make people more confused that's one of the problems also it has some signs limit but they recorded recorded bass definitely GCM and it's for Galois counter mode so they use this Galois field multiplication to generate these tags of whatever message you increase so

you make sure that your fight hasn't the middle bit or tweet on the way of transient or whatever and it's also using this counter mode as a encryption mechanism and it's also pass but they also provides this authentication property under setup than the AE ad the authenticated encryption something any other questions thank you again a real [Applause]