Break Crypto like a Pro!

hi everyone good afternoon crypto geeks so let's go ahead and get started I hope everybody remembers this about a month ago maybe five or six weeks ago I don't remember exactly but there was a huge vulnerability in Microsoft Windows which was an NSA this time was nice enough to let everybody know about it so vendor could cash it and why am i bringing up today this thing was this an issue with some cryptographic protocol like TLS no was it an issue with some critter graphic algorithm like a yeah so Shaun no not really this was just a this vulnerability that let but that could potential that an attacker do all kinds of bad things was

just the result of one or two stupid coding mistakes and why is that so cryptography is hard right if anybody disagrees with me I want to talk to you after this talk and coding mistakes are bad and we all deal with coding mistakes and coding mistakes in cryptography are especially bad because virtually all the time they lead to some kind of security issue like the one we just mentioned so today we're gonna talk about how to exploit some of these coding mistakes or implementation mistakes I should say we're not gonna talk about any zero days no not today there's not gonna be any complex math everything's gonna be pretty basic we're not gonna talk about

any about the dark future of cryptography which is going to be completely broken by quantum computing and we're not gonna break the internet today which is based on the correctly implemented crypto all right so my name is Alexey I'm a recovering software developer at some point I realized that breaking code was more more fun than writing code so I don't fight much code anymore but I do break some sometimes I currently work for a company few blocks away from here I'm not actually based in San Francisco though I have a couple of industry certs but there is a fine print of this slide now here it is I'm not a cryptographer so and I don't

even know what the definition of cryptography is is it somebody who invented an algorithm or I don't know but anyway so this this is a talk by and non-experts non expert hopefully for non-experts but I hope it will be interesting so a few general recommendations first of all we all need to use well-known and secure algorithms right we don't use md5 anymore or des that's clear and we need to use standard and stable implementations of those algorithms we don't use some obscure libraries who and nobody knows where they were written a very important thing is we need to follow best practices so if somebody's telling you if the book says you gotta use a random IV there's

probably a reason for that right and you heard this advice many many times I'm just gonna give it to you again do not invent your own crypto the mixed a mistakes with cryptographic implementations or code around it can boil down to several categories first there isn't there could be insufficient entropy which means basically means not enough randomness and randomness is really important here second is algorithm choice so we don't use the correct algorithm for the purpose algorithmic considerations are really important because depending on what you're trying to do there are certain things certain tweaks that you need to use to to get what you need and not to make a mistake one thing that we often overlook we

which I we tend to focus on secrecy and we forget about integrity so we yeah okay we hide this message really well but can anybody tamper with it and we forget and the last but not least is you can have a perfect system with very secure keys modern algorithms but as long as you don't handle those keys correctly and they leaked are you broken let's talk about a couple of basics first I hope everybody knows what exclusive-or is but if you don't this is the ultimate crypto weapon for the purpose of this talk and we'll see why and there are and there are a few cool properties of this operation first is anything X or 0 is same thing something

X or the same thing is 0 and if a X or B is C then a X or C is B and B X or C is a so you can move the parameter on either side of the of that equal sign because the second basic thing is randomness there are two big types of random number generators one is to random number generator which is non deterministic and completely unpredictable and those are normally based on some physical characteristics may be ambient temperature or noise or electric current fluctuations or some visual data and there was again there's no way to predict what the next random number from that generator is going to be and there are also pseudo-random

number generators and these are completely deterministic these are algorithms and they based on on a seed so you give it the same seed to time said it's gonna generate the same sequence of random numbers and a lot of times we use the combination of both so we would use the two random for for the seed and then we give it to pseudo-random and then we get a nice a stream that that's looking like completely random speaking of randomness few years ago some smart guys got fed up with all ransomware being written for Windows so they decided to to create one for Linux after all the next runs a lot of stuff right and you could probably monetize

something like this really easy the problem was they used predictable encryption keys when they were encrypting the data and researchers found it pretty quickly and and released a decrypter which anybody could use to decrypt their data without paying any ransom and I have a demo so let's see how it works so I have a small document which says not all random functions were created equal and I have my encrypter which encrypted my file with some key that it just created and actually it forgot about the key I don't even have it but if I look at this document ransom it's looking completely like some random binary data and I have no idea what the keys again and what the what the what is

document is but I can use my Decrypter script to if I can type it correctly and it decrypted that file because in this particular case it could just get the timestamp of the file modification timestamp and give it to the to the generator here and and that's it that's very very easy so before I move on I wanted to mention that all the code that I'm using today is on github and you'll get a link at the end of this talk and you'll be able to download it play with it do whatever you want

cool yeah so it's a great advice right of course he if you md5 current time you you're gonna get predictable random non random whatever don't do that well let's talk about some encryption algorithms there is a very very secure extremely secure an extremely simple algorithm called one-time pad and it works like this suppose you have a message m and a key K and the encryption would be a simple XOR operation of message with the key that's it and decryption is a similar basic operation you just XOR ciphertext with the key here's an example it's very secure because it was again I think there is a theorem of some kind that that says that it's secure and it was

proven but there is a one-one issue with this algorithm is if the key has to be as long as the data so if you encrypt a gigabyte of data you gotta have a gigabyte long key and you gotta store it somewhere you gotta share it with someone so it's very impractical another issue with this algorithm is in the name it's called one-time pad but why so let's see what happens when we encrypt two messages with the same key message 1 and message T now if we XOR these two ciphertext the DTO to the properties of XOR operation these two keys will cancel out and XOR of ciphertext is equal to the XOR of the original plaintext

messages and this is obviously not very good we cannot reuse keys and the more messages we the more ciphertext we can intercept the more data we can gather from something like this so since the key for one time pad well what the pad is in practical because of its key a requirement we use stream ciphers stream cipher is using a short key or a lot relatively short maybe 16 bytes and it's giving it to a key stream generator function G that takes that key as basically as a seed and generates as a stream of pseudo-random data and our encryption operation is the same as a one-time pad is just XOR and decryption is XOR so it's basically one-time paired

with a different kind of key but it's it's much better because we can manage short keys but again we cannot reuse these keys with stream ciphers well there is an asterisk here because in some modern implementations of of modern key stream ciphers you can actually reuse the keys because they introduce randomness through some other means but in in its pure implementation and with old algorithms like rc4 this was the case you cannot reuse keys so let's see what happens when when you reuse the key

I have a couple example but I have an image of me cool picture and another cool picture of a smiley face there's both images are the same dimensions and I'm gonna encrypt them both with the same key using a stream cipher called rc4 and let's see what happens after that hi my cool script so I've got you this is the result of one picture being encrypted and this is the other pink picture encrypted completely random right can gather any data from here well what if we give the feed these two images the encrypted images to graphics editor so this graphics editor lets me do a pretty cool thing I can add I can overlay the two images as layers right

and then I can select see if I can make a little larger I can select select a layer operation and one of them is XOR so if we just exported two layers it doesn't align really well but you know as a as humans we can immediately see that something is wrong with this encryption right now what what if we as attacker know one of these plaintext messages so let's let's say when we know that one of these messages was was a that smiley face so I'm gonna give it to my editor I'm gonna add that smiley face as another layer and I'm going to XOR it with that so having these two layers of seemingly

random stuff and a smiley face I get a picture of me how cool is that all right well I don't know so in real world though this is this might not be as simple right you might have to do some kind of really smart analysis but you get the idea reusing the key is not good thing okay let's talk about block ciphers unlike stream ciphers that operate with bytes or maybe even bits block cipher operates with blocks so you feed it a block of data normally it's maybe 16 bytes it does a permutation based on the key and it it gives you another block so that's how the primitive works but your data is not always as short as the block

size right in most cases it's not so what do we do in this case the pretty like straightforward thing to do is to encrypt each one of the blocks individually and you get a ciphertext everything is cool well apparently it's not and you can guess that the same plaintext block well if it's somewhere in the file we will encrypt to the same ciphertext so by looking at the ciphertext you can see the patterns which is not good as we know that good encryption will result in in data that indistinguishable from random noise and this is not random noise anymore and let's see how how non-random that is okay I have another visual example this is an image screenshot of my title slide

so I'm going to encrypt it so this script encrypts it twice one it's using that ECB mode that we just talked about and it all it's also used in CBC mode which we have not discussed yet so let's see how they differ visually this is the image encrypted with CBC mode completely random and this is the image included with encrypted with ECB mode where each block encrypts individually and although it's not looking like exactly like the original image again we as humans can immediately see you can immediately get information from here you know you can read the text because it's an image I was cheating but you know so not a good idea so what's

what's the CBC mode so CBC mode introduces randomness and it doesn't matter what the blocks of plaintext aren't going to repeat does really matter because everything is going to look like random after encryption so the previous ciphertext block is XOR with current plain text before encryption and that's how that randomness is propagated all the way through the data we the first block though we don't have that previous ciphertext so what we use is a thing called initialization vector or IV and IV is just a random just just some random data just which is equal to the size of the block and it's not secret we transmit it with the ciphertext openly but we just need it for the for this

randomness the decryption is the opposite operation so when we decrypt the first block we first apply that primitive reach the crypts and then we XOR it with IV the second block we decrypt that block and XOR it with c1 and so on this one we XOR with c2 some people think that have an idea since I already know the key and whoever is going to decrypt this message later knows the key why cannot can I just can't I just use the key as IV I don't have to transmit it right because it's known to both to encrypt and decrypt I'll just feed it here and it will definitely introduce randomness well it's not a good idea because under some

assumptions this kind of stuff is easily broken and broken to the point that you get the original encryption key not just original data so suppose we intercept a message of three ciphertext blocks or maybe more ciphertext block doesn't really matter because we only use the first one you see one we put it here then the next block we just put all zeroes 16 zeroes or eight zeros whatever your cipher is and the third block will repeat c1 again well this looks funny but here's how it works if we have an assault if we if we assume that we can give this to the Decrypter and they'll try to decrypt it and tell us the result then see what happens the

first block is decrypted and X sort with IV and IV happens to be the key so it's XOR with the key the second block is decrypted to garbage and we don't care about it the third block is decrypted and X sort with the previous block which is all zeros so on the right side here we have the result of the decryption of Block C 1 and here is the same thing exhort K so if we now XOR these two plaintext we get the encryption key okay let's see I actually have a web application for this so this application is giving you a session cookie which is encrypted JSON and let's suppose the the source is open

we can see how it works and what's doing but we did we have no idea about what the encryption key is right so here's our encrypted cookie let me so first thing we need to do is feed that cookie to our first first step is to build that that funny message with zeros in the middle which are represented by a a in base64 now we give it back to the application and since it's a session cookie it expects a good stuff from us i refresh the page and it says bye data isn't valid I could not decrypt it sorry here is what you gave me here is what I was able to to get this is the

result of the encryption great we say great let's just use that our second step is this this script analyzed this message and told us the cook encryption key is this well let's check it now the server is running on the same machine obviously so I can see its session key which is stored in the file and of course I should use something other than cat and the key is exactly C 4 F 1 is 0 and B and so on so we broke the encryption key alright so don't use key as IV now not only your message is normally not as short as blog it's normally not the length of it is normally not a multiple

of the block so what do you do in this case and because the block cipher only parades on this fixed length in this case this V is padding so let's say we have 10 bytes we want to encrypt we cannot just give it to the block cipher we need to Pat it and pattern is just adding the missing number of bytes at the end in this case we we are missing 6 bytes and we adding 6 of them each one of them is 636 that's the convention cool and so this can be encrypted and this can be later decrypted and what usually on the decryption side the program or the L or the implementation of the algorithm checks whether the

padding was correct which may lead to attack hold pairing Oracle so if we receive ciphertext and decrypt it and some people assume that decryption with the wrong key will fail it's not gonna fail the krypter will decrypt anything you throw at it you can throw garbage ciphertext garbage key it will produce something it's just it's just a permutation but then you check your pairing and it's wrong so in this case it's feels like the right thing to do would be to let user know that the message was corrupted maybe so you produce an error message if the pairing was wrong and that leads to an attack called parent Oracle and this attack is out of I'm not gonna explain how it

works it's out of scope of this talk but basically you modify bit by bit 256 tries per byte and you can decrypt the entire message and although we're not gonna go into many details I have a demo that which is really cool I think so here's another application that accepts a message from the user encrypted message and it gives me an example here I don't know what it's really rude though I don't have the key so I cannot decrypt it well if I try to refresh the page it gives me a new message every time actually the same message is just it's using a random IV so that's why it's looking different so if I click

here it's an example the application accepted that message told me thank you very much okay what if I try to modify that last bite of that message it was - I'm gonna set it to 1 and I sent it an application gave me an error cool which tells me that I could probably run my padding Oracle against it let's see

here's Michael exploit I'm just given it this exploit script this URL and it has no other information it just is just gonna go to this server and try to send different things it's gonna try many things and here is the server log it's basically accepting hundreds maybe thousands of requests but at the end just in a few seconds it was able to decrypt the entire message so this stuff is real you know when we read about these things with sometimes we think you know yeah these are theoretical attacks well no you can you can actually use them sometimes so yeah just wanted to show you what what's happening on the back end is just processing the message is doing the

decryption and then this padding stuff and then it's just catching the error I mean this is like normal way to do things so if there's a errors of some kind this probably user is giving us garbage and they not authorized to perform operations so normal to give an error like this or I'll be careful okay so a few examples so far were based on the fact that our vulnerable applications were not checking the integrity so I can pet an Oracle attack we modified that message bit by bit and we threw it at the application it was trying to decrypt them which apparently is not a good idea it should have just rejected because it should have somehow determined that the

message has been modified well yeah we give it garbage it process it but what about not giving a garbage but giving it something that you control so for example you know that somebody is sending someone a message sign $1.00 to Alice and they encrypt it and all you have is that encrypted thing the ciphertext what if you can modify that ciphertext without knowing the key so when the other person decrypts it they get what you that what you want the message to be so instead of sending hundred dollars to Alice the poor Bob will send hard dollars to Mallory apparently this is possible and a simple example of this is with stream cipher using a bit flippant attack suppose our

message is guest it's a string so our encryption looks like this remember right the attacker will modify these cipher text that they intercepted by XOR innovate with original plaintext and XOR in it with the new message that they that they want to that to be so when this is decrypted so yeah yeah one this is decrypted this is the decryption operation which expands to this right and it further expands to this and guests and guests cancel out gia K and GK castle out and the resultant message is admin so it seems like a silly example but what if this message is used to make access control decision and this is like your again session cookie

let's take a look me refresh this all right so in this case again we assume that the source is open we can see it we just don't know the key we know that this application is using a stream cipher in this case it's also 20 which is a pretty strong modern cipher which is using a random nonce so the key we use is no longer possible and we know the value of the of this user cookie which is printed right here but we could have guessed it too easily all right so I have my bit flippant exploit I'm giving it that ciphertext I'm giving it the original value and I want to give it a new value if I analyze

the code though I see that the date parameter is not even used by this application so I can completely skip it I'm just going to remove it it doesn't really matter I mean we could keep it but I'm just gonna do it like this and here is my new encrypted cookie again I mean my exploit script didn't do anything it was just exploring stuff so I'm given that cookie back to the app refresh and I'm in the admin interface well awesome all stream ciphers are easy sometimes what about block ciphers apparently bit flipping attack is possible in block ciphers as well although it might not seem as straightforward but let's say our messages guest and it happens to be

in the first block of our encrypted message so our ciphertext is the encryption of that message X sort IV and due to X or properties these are true as well so in this case what we need to do is to modify the IV we don't modify this ciphertext modify the IV which is not secret again it was it's transmitted along with the ciphertext in open so we modify it like this very I mean there's a V right we've seen it before when it's decrypted the that block is XOR with our new IV and which expands to this the two IVs cancel out expensive this two guests cancel out and we get our admin again

all right let's see if it works yeah so here's our new encrypted cookie

and I need to give it that ciphertext again I need to give it the original data well actually in this case I'm only concerned about the first block and this happens to be exactly 16 bytes I'm so lucky today so I'm going to change this to admin so it's only modifying IV which will only go into effect the first block and when I give it back to the application I'm the admin again well this was I mean pretty I mean we got really lucky here right but in real world you can still do a lot of damage even if you're if something you try to modify it's not exactly the first block it's somewhere else yeah there are there

are ways to do real harm so integrity is extremely important in cryptography we have a thing called authenticated encryption which means in addition to encryption the message in hide in it making it secret we also authenticate it so when somebody is trying to decrypt it they are able to determine whether it has been tampered with or not so during the encryption we just we just provide plaintext and the key and the output of such authenticated encryption will be our cipher text and some kind of authentication tag and decryption will validate that authentication tag and if it sees something weird like it doesn't match what it calculated it should just reject the message completely not even try to

decrypt it okay and the last thing for today I want to talk about is storing passwords we have a couple of rules rule number one no plaintext passwords yes rule number two no decrypt able passwords right because no matter how well you do it sooner or later your keys are gonna be leaked or gonna get to the wrong hands and somebody's gonna get the passwords rule number three no one way hash right I mean what I thought everybody was saying that one way hash is the way to do it well yes but some people take it literally and they use it use a hash function so they use something like Chateau which is not a good idea because

of its speed so hash functions are cheap they're fast which makes brute-force attacks possible in contrast key derivation function Zork ADF's are expensive they take a lot of time maybe a lot of memory or maybe both and they when you implement them when you use them you want them to be as slow as possible like whatever slowness you can get is the way to go and I just wanted I mean some people yeah kind of standard but they don't really appreciate how huge the difference is between something like chateau and KDF so I just wanted to run a very short demo here this script generates a password hash and first it does using sha and I can use John the

Ripper to to brute-force that using a using a dictionary boom took a fraction of a second my password is Pink Floyd and John the Ripper tells me that it was able to try 60,000 passwords per second not bad let's repeat this with pbkdf2 function which is by the way not the best key duration derivation function these days but I'm using it here just because it was easy so let's try to brute-force it now and as you can tell it's taken much longer now it ran open threads eight eight open eight frets and okay well it was able to crack it the password is Pink Floyd but it was only able to process 85 passwords per second versus 60,000 passwords per

second so I'm in this case it would be really impractical if your password is strong and maybe not in the dictionary file at all which is what we should all strive for so takeaways if you're a breaker you need to understand the cryptographic concept not just in general terms but on technical level you might want to go a little deeper to really understand what's going on examining the industry guidelines and understanding them and understanding why they were given at some point in time is very important to you know things like again not using keys IV right there's probably a reason for that expand on other people's work there are some tools there is my really bad demo software

that you can try if you are a builder again you need to understand the concepts and your tasks so you need to know what to use when and with what parameters because if you use a hammer where you you need to use a chainsaw it's probably not going to work really well follow the guidelines you don't have to understand them but those fibs check about check box boxes sometimes are useful although I'm smiling and learn from other people's mistakes and don't make them again so for further learning I just wanted to give you a couple of recommendations I'm not affiliated with this at all but there is a really nice course on Coursera called cryptography

one it's awesome awesome awesome course highly recommended the and the second one is crypto 101 online book it's basically a PDF that you can download it and read it still needs some work but most of the great stuff is already there so like I promised my code is on github feel free to fork it clone it give it a try let me know if it doesn't work and you can contact me and thank you very much and I guess we have time for questions [Applause] any questions no questions online questions these slides the question is whether the slides online not right now but I out put them up thank you all right thank you [Applause]