HackTheBox Challenge: Weak RSA

This challenge was very important to breaking me into crypto and handling of binary data. The intended way, due to it being an easy level challenge, was to read up on wikipedia about RSA, find out about the existence of the wiener attack, then download a script to run on the given ciphertext to extract the flag. I however assumed it was intended to be exploited from scratch, so I ended up spending far more time than was expected on creating my own python script (with help of a guide on how the wiener attack works) to complete the challenge, and I’m glad I did! The process introduced me to a lot of new concepts that I’ve then been able to use to make harder crypto challenges much easier, and will undoubtedly be useful for future programming projects.

The challenge itself simply gives you a ciphertext and an ascii armored public key, you have to figure out the rest. To me at the time this was quite a lot, as I didn’t really understand the differences between the three major crypto functions (symmetric, asymmetric, one-way compression) to begin with, let alone the details on how they worked. Luckily in comparison to the others, RSA has fairly straight forward internal workings, as it just relies on a small system of equations, rather than a large internal and complicated process like block ciphers or hash functions.

Using a package called pyCrypto I could import the given public key and print it’s public exponent and modulus. I created a small script just to have handy so I could quickly reread the values whenever needed.

After becoming familiar with the fundamentals of RSA and getting a way to access the public key’s elements directly, I started looking into common attack methods on wikipedia. The first was about how that for encryption carried out with a small public exponent (e), say around 3, the original plaintext could be retrieved from the ciphertext by simply taking it’s e’th root. Now as we can see, the public exponent used here was very large, and so this attack wouldn’t be feasible, however this did strike me as odd - how can you take the root of a text file? Well, in the same way RSA itself is applied to any type of text – by breaking it down into one single number and applying the mathematical equations on it, and this was the first time I really realized the know seemingly obvious fact that everything is just a bunch of numbers. Furthermore, with a bit of research and asking around, I also learnt about the algorithms OS2IP (octet stream to integer primitive) and I2OSP (integer to octet stream primitive) which can take either strings of text or whole numbers respectively and convert them from one to the other, which are obviously vital in an RSA encryption and decryption process.

Armed with this new knowledge the next challenge was dealing with encoding and decoding of text data using Python. This was again a new area to me but obviously very important in crytpo and programming generally. A big hurdle was simply realizing that data is actually ‘encoded' when it’s in raw byte form, and ‘decoded’ when in ascii/unicode, at least by python’s definitions anyway. Figuring out when to work with bytes and when to work with characters, when to use little or big endian (another concept I only came across due to this challenge) and also how to encode bytes back to unicode correctly in a preserving format – it turns out printing or piping from stdout to say the base64 utility will discard all non-printable characters and thus alter the data you’re working with. This happens with both Python and C! So, to get around that you also have to encode your bytes to base64 while they’re still in the memory of the program itself, rather than piping through stdout to the base64 tool, and then all your data will be preserved and can be reopened in the same way. This is all unrelated from crypto directly, but if you’re to write programs to carry out exploits from scratch is still vital knowledge that I had no idea about before attempting this.

Eventually I came across the wiener attack and realized that must be the one, as nothing else had worked so far. Learning about the maths was fun, and implementing it in python was fairly trivial.

Though messy, the output of our script contains our flag!

I came out of this now knowing about the internal workings of RSA, how encryption carries out mathematical operations on text, and how to properly handle encoded data to be manipulated or outputted in a program. Even though it was the ‘easiest of the challenges I’ve done, it probably took the longest and taught me the most!