[CTF Series #5] Long Integer Overflow?

This is a very interesting challenge for me as it involves integer overflow and extended Euclidean algorithm which i had learnt during my cryptography class in university. It was so excited !!

Objectives:

1. Find the long integer that match to the equation.
2. Convert the correct integer into flag by using the function given.

Topics Covered:

1. Find the multiplicative inverse of long integer with modulo n.
2. Using Integer overflow to find the correct solution for the formulae given.

Descriptions:

Visit the link below to see the source code for the question given.

https://gist.github.com/ghoulgy/1749da21f6351f3f9df9cf3c4ccbd759

From the source code it can see that the arrayOfString and creator function just a troll to confuse us. Just… Delete them!
Important functions left: securing_fsecure, getHexString, hexToASCII and main.

getHexString()

Retrieve the characters in the paramString and rearrange them in correct order that will decode by hexToASCII() into flag.

hexToASCII()

Convert the arranged hex value it into readable ASCII value which is where the flag generated.

main()

There is a if statement there to validate the results of securing_fsecure() whether is true or false.

securing_fsecure()

It has a hex value that passed into the function, therefore, convert it into ascii text and it shows replac3th1s. Hmm… It gives the hint that the answer to get flag is here. There is a if statement inside the function which contains a simple mathematic formulae with long integer.

if (42L + -37L * Long.parseLong(paramString) == 17206538690L) {
          bool = true;
          getHexString(paramString);
          System.out.println("\nYay! I think I got it!? The flag is here somewhere...");
        }

The missing one (paramString) is the value that passed into the function.
Rearrange the formulae:

-37L * Long.parsedLong(paramString) = 17206538648L

It is impossible to find the exact long value of the paramString as the division of the ANS and -37L will rounded to the nearest decimal value.

Long integer will not store any floating point value

In order to find the exact value, maybe it can be solved by integer overflow?

After some google-fu, i found that extended Euclidean algorithm can be used to find out the correct value that gives the correct solution by compute the modular multiplicative inverse.

This link will explain more on this type of question.

In Java, long is a signed 64-bit type which can stored up to 2⁶⁴ values.

Finding the inverse multiplication of 37 modulo 2⁶⁴ by using this link.
Results: 1495681951922396077L

Validate the value by checking 1495681951922396077L is inverse of 37 in mod 64.

37L * 1495681951922396077L == 1L 

Multiply the inversed value of 37 with the original value to be compared to get the correct paramString value.

Validate again with the original formuale.

42L + -37L * -4487045856232229816L == 17206538648L

Bam!!! Jackpot!!!

In context of Java signed 64-bit long integer -4487045856232229816L is the correct solution.

Now we got the correct value of paramString to be passed into the function.
To print out the flag, i modify the type of getHexString() from void to String which returns a String value. Then, write a print out line in the securing_fsecure() and run it.

Flag Get. Cheers!

Personal Thoughts

The overall walkthrough is finding the multiplicative inverse of 37L mod 2⁶⁴ and then using the integer overflow flaws to get the correct value of the formulae.

References:

https://www.youtube.com/watch?v=shaQZg8bqUM
https://brilliant.org/wiki/extended-euclidean-algorithm/
https://dsri.github.io/modinverse/
https://math.stackexchange.com/questions/2172758/impossible-math-number-needs-to-be-divisible-and-greater-than-an-end-result/2172777