Crypto: Classic RSA with a Twist (ParsonsCTF)

[Music] what's going on everybody my name is John Hammond and in this video I want to showcase one of the challenges from parson CTF or their capture the flag a few months ago that was just classic RSA like the simple crypto system except for one small technique and trick at the very very end so I know I've done this video at least RSA many times before but I do want to highlight and showcase really the trick at the very end because it's easy to forget we're gonna be just doing simple decryption with RSA and we're given the factors of N and the modulus which are built like to create the actual public key so those prime numbers P and Q are actually given to us and that is what you would normally use for n in the modulus so I've covered this again in other videos if I do a failure of some justice to actually present it to you in this video there are plenty others but I want to showcase really just the trick at the very very end so let's go ahead and look through it I have my terminal open here and I'll showcase the prompt it says little dirty johnny has a filthy mouth he never watched his P's and Q's in fact when he encrypted a flag for us he left them lying around can you clean up his P's and Q's and figure out the flag so again as I said we have these factors here and we can go ahead and calculate N and since we really have P and Q we know the factors we can determine D which is that decryption private key here so I'll scroll down again and actually showcase some of that let's fire up a script I don't actually have the flag encrypted here and that's just a encrypted one so we'll have to read that in but let's go ahead and create a script to do all this with it let's say just get flag PI and I will have the Wikipedia page visible down there let's go ahead and have a shebang line to work with us here let's open up that flag Inc because that's going to be our cypher text so I'm just gonna call handle and I'll use a context manager because people yell at me handle C equals handle dot read and then let's actually verify that we have the C that we want okay cool so that looks like nonsense I want to go ahead and actually convert that into a number so I'm gonna use been ASCII because I think that's pretty well in line with the Python 3 rendition of doing these things I will go ahead and hexif I this and then I'll consider that to be an integer so we can go ahead and convert that as in it's a 16 if someone can tell me a better way to do that but that will go ahead and get a decimal or write an integer value for me for Python to work with so let's just say C equals all of that great now let's go ahead and actually grab those P and Q values from the original prompt we're just kind of copy and paste those in here okay so now we can determine n just by simply multiplying P and Q and that will be handy for the rest of the evaluation but when you really determine fee or Phi or the totient that is what's noted here in the Wikipedia article as kind of the least common multiple but with prime numbers it's actually just simple P minus 1 and Q minus 1 so that's simple VI or however you want to say that P minus 1 times the quantity of Q minus 1 now now that we know fie and we can assume let's just use classic standard RSA numbers here II will go ahead and be that 6 5 5 3 7 or and X 0 X 0 0 0 1 I like to remember that a little bit easier it's I think it's simpler to remember than the 6 5 5 3 5 but whatever so now we have those values and we can go ahead and determine D D is the modular inverse because of the way that the RSA cryptography works we're putting together some modulus and arithmetic if we actually want to determine the private key it is secure because of its modular components here we can go ahead and determine that Python offers a nice built-in way to actually calculate that with its PI cryptography module if you don't have that I think it's pseudo pip install PI crypto I might be wrong in that and people have told me before don't use pseudo when you're trying to go ahead and pip install stuff you either use pip install TaxACT user or just work at a virtual environment so all right let's go ahead and actually use that module though it's import crypto capital c dot util krepo you capital u number import inverse so sorry from that package important this so now we can go ahead and calculate D so deal equal the inverse of e and then Phi I remember that because because of e becomes before P in the alphabet that's how I just remember those arguments so now we should be able to determine D is if I we want it to be it's a number cool I'll trust it let's go ahead and calculate now M equals the power of C raised to the all mod n great because that's how you go ahead and do decryption if I scroll down here C raised to the D all mod and is equal to M so if I go ahead and run this I didn't print anything out so we're not going to see anything if we were to print something out you can see we have M here and I'm gonna go ahead and convert this into a hexam hexadecimal value so let's do hex of that and let's go ahead and try and convert that to ASCII so what I'm gonna do is gonna first cut off that 0x so it's at the front and go all the way to the end here that L at the end I don't care about so I'm gonna go negative 1 and I have full hexadecimal value now so let's go ahead and decode that with then ask I'm gonna ask you dot unhex Allah Phi then we'll pass that in and the error that we get here is we have an odd length string this is the stumbling block that I think a lot of people kind of didn't get when they went through this challenge and I actually stumbled with it for way too long too long then I'm more longer than I should have more longer I don't know what I'm doing I'm bad with words today so what you can do here is keep in mind if you have an odd length string the text you can work with it in a similar way as you would begin with hex already right so if I had 0x a that's the numeric value 10 right and that string of hex characters - the 0x is just a right but that's an odd length string there's only one character here that one is not an even number that's an odd number if I want it to have an even number here would need to be a multiple of 2 right so why not like what stop us from using 0x0 a and hexadecimal is still the exact same value it's still 10 but that's string now if I were to consider it zero a that's an even length string there are two values there so if you ever see that error odd length string when you're trying to decode hex that's totally fine just go ahead and tack on a 0 either at the front or sometimes you might need at the end and maybe some some CTF challenges will mess with you like that I had some extra parentheses in there weird okay I can wait let's let's try and print this out now and I will use that technique I do need to add the zero in here and remember that whole thing is what's being passed to hexadecimal or unhex if I so if I print that out now you have a lot of nonsense the very very top and beginning but the flag is there ncx dirty jokes so it's hidden and we want to be able to carve it out if you for some reason you do with their processing I tend to wrap string around that but you shouldn't really need to all that often because hex is going to be what has the 0x and you need a slice to begin with but that works I think I'm thinking of it the wrong way because I'd like to use that string and then like a dot decode or something when I was using Python - but Python 3 is what I would advocate for now and that means using been asked you don't know hexa Phi so you don't need that string wrap okay that's that right and if you did if you would actually add the 0x on at the end though sorry add the new 0 character on at the very very end that's when you would certainly need to use SCR to create a string and slice from that but you would probably want to do that after you've removed the L if the L is there so sometimes you don't really have to trust or you wouldn't want to trust that the negative 1 will cut an L if it's not a long value in that case I just use 2 sliced and then I just replace the L with nothing it's a string so you can do that right okay that was a lot of talk but really the technique and the trick that I wanted to show you is do not forget to do that if you ever see awed length string Python ole will tell you that it might be read and angry but it's not the end of the world so be sure to zero just tack that on and totally fail when I forget to remove the L okay I want to showcase this with katana just to kind of I don't know prove that it's doing cool and good things and it's slowly coming together I know I get anxiety a lot of people get angry when I try and showcase katana but I think it's neat so I have these two files included in the test directory that katana is using so let me get actually get into that directory and I will go ahead and enter my virtual environment because I have been developing and I want to be in a virtual environment when I'm developing not just doing simple CTS script code so I'll showcase the code for this unit it's in katana units and it's crypto RSA I have some baseline things for energy attack that I don't need to show you I'm using something called fine variables now a function that I put together to kind of track down and scan a given file for kind of the variables that would be needed in an RSA challenge so if they ever tell you any Qusay equals that Q equals that D blah blah blah it uses some regular expressions pulls that out and then returns them and is able to determine them I tracked down some extra cases in case it spells out the word modulus and Phi or fee because it starts with a P or an M and I don't want to be to be confused between the words message or the factor P right so those are those extra odd cases I also have a little bit of notion to go ahead and cracked and and determine the N and E values from a given public key file like an opus open SSL certificate or that PEM key sort of thing so that's handy and I'll showcase that another video but that's the neat little code to do that and parse int is what we'll go ahead and first try and determine if is already a number the value that we find following the string and then if it's hex try and unhex off' i it or whatever or determine it and blah blah blah that seems to be working pretty well actually protecting a real value in getting a returned as an integer and then we have a lot of arguments that could potentially pass to it i do this now to actually supply RSAC or they create the cipher text because that will be needed if you are passing in the target or the real first argument as the file with actual information in there so we try and determine whether or not we could actually have a cipher text and do these things in the check or really the constructor function and then a in the evaluate function or what it's actually going to try and do it goes ahead and determines whether or not we have given e if we don't we'll just kind of use the baseline one as I suggested earlier we'll check if we have a little D attack because I have support for that I also have a support for a cube root attack that I'll show case because of a little bit of picot CTF 2018 and I determine n if it's not already given try and track out track down factors by calculating it or passing it to factor D be determined fee I I don't know I keep saying that determine the totient go ahead and calculate D and then what I do is actually go ahead and do what I just showed you where I'm using that zero plus the hex value because I don't want to forget about that so because katana is able to process this and locate the flag in whatever data is passed to it it finds this relatively easily and look pretty well so what I'll do to run this is Z shell is already Auto completing it for me thanks go ahead and run katana passing in the flag format we would expect for the CTF so NC X in this case and the dirty Johnny test file that has those P and Q values that I need in there and then it will determine the actual C and ciphertext value from reading in that flag Inc so when I run this it will go ahead and solve the challenge for me so that was that super easy is super simple and all we need to do the beauty of katana and scimitar coming along too so thank you guys for watching I hope you enjoyed this I know it's classic say and I've done it way too often but I hope that last trick and technique is a worthy foot stomp or something that I really want to drive home and not have you forget about when you play other competitions or when you see that error don't hesitate and just try and tinker add some zeros in there at the beginning or the end if you want to see if something might have been missing so if you did like this video please do like comment and subscribe I would love to see you guys the discord server we have an awesome community link is in the description I would be incredibly grateful to see you on patreon PayPal and any support that you're willing to offer I am just thankful thankful thankful I can't say it enough thanks for watching guys see you the next video [Music]

Channel: John Hammond

Views: 10,195

Keywords: cryptography, rsa, asymmetric encryption, crypto, capture the flag, ctf, linux, programming, python, scripting, hacking, hack the box, binascii, hexlify, decode, decrypt, modulus, exponent, factor, modular arithmetic, john hammond, hammond, hammond ctf, cyber security, software development, computer science, information assurance, ctf katana, katana, scimitar

Id: JI-9rDjMAsQ

Length: 14min 47sec (887 seconds)

Published: Mon Jun 03 2019