# [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:**

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

**Topics Covered:**

- Find the multiplicative inverse of long integer with modulo
*n***.** - 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,

longis 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