misc

# Sdctf 2021

## Alternative Arithmetic

Solved By : Ava and choco

• After connection we are given a java questions which we have to research for and solve
``````Question 1 :

1. Find a nonzero long x` such that `x == -x`, enter numbers only, no semicolons
``````
• answer for 1st question is `-9223372036854775808`
• Explanation :-

The first question given is to find long x such that `x == -x` Here we will need to exploit the use of 2’s compliment of binary representation of long. example: in a 4 bit representation of 1, the binary is `0001` but to represent -1, the binary will take 2’s compliment so it will be `1111` The MSB here represents the sign of the binary the limitation of 2’s compliment is that, the number that has reached the minimum negative limit (i.e. the maximum 2’s compliment value), it’s positive counter part will be the same binary value as it’s two’s compliment. Let’s take the one for 4 bit representation again, the minimum value in this will be -8, i.e, `1000` if you take +8 here, the binary will also be `1000` So we got the concept for the answer. But now, the data type is long (8 bytes) The answer must be `-9223372036854775808`

``````Question 2 :

Find 2 different `long` variables `x` and `y`, differing by at most 10, such that `Long.hashCode(x) == Long.hashCode(y)`
``````
• answer for 2nd question is `x = -1 & y = 0`
• Explanation :-

For the second one the given algorithm for Long.hashCode() is

``````public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
``````

As we see here, the hash code for long compresses the value to an int from 64 bits to 32 bits. The hash values of positive long values are itself (hashcode of 8 is 8) The exploitation here is that negative numbers behaves different. let’s take -12. it’s binary representation is

``````1111111111111111111111111111111111111111111111111111111111110100
``````

after it got shifted to the right by 32 bits it will be

``````0000000000000000000000000000000011111111111111111111111111111111
``````

this value is xor with the original value giving

``````1111111111111111111111111111111100000000000000000000000000001011
``````

when we convert it to int only the first 32 from LSBs are taken i.e.,

``````00000000000000000000000000001011
``````

Hence, the Hash value of -12 will be 11 So

``````Long.hashCode(i) = i for i >=0 and
(-i)-1 for i < 0
``````

but the question is asking for x and y where `x - y <=10`

Hence using the advance stages of arithmetic mathematics, we can take answers as

``````{0,-1},{1,-2},{2,-3},{3,-4} and {4,-5}
``````

Courtesy of https://www.devdiaries.net/blog/Java-Recruitment-Questions-HashCode/for Hashcode algorithm.

``````Question 3 -

Enter a `float` value `f` that makes the following function return true
``````
``````// code given along with Q3 :

boolean isLucky(float magic) {
int iter = 0;
for (float start = magic; start < (magic + 256); start++) {
if ((iter++) > 2048) {
return true;
}
}
return false;
``````
• answer for 3rd Question is `2.14E9`
• Explanation:-

The third question is a little tricky We need to find float value magic such that we need to break the loop The other catch is that it have to be less than 7 characters

The trick here is that we need to exploit the precision error in java

in java, the floating points can go upto `3.4 * 10^34` but the secret is that it will take a precision of 8 digits. i.e., if the value in decimal points is more than 8 digits. It will round them off to 8 digits itself. so for example ‘345678’ in float will be 345678.0 but if digits has reached 8 like ‘`12345678`’, float will save the value as `1.2345678E7` The maximum digits in float is actually 10 (1999999999) if you want to represent a number higher than that, you must make it in `2.45E10` like format

now, for the exploit, if you add any number that is negligibly small to a float value, this will not affect the float value at all. In fact, float values can only consider changes made in the first 8 most significant digits. In other words, if converted in decimal, only the first 7 digits will be considered, rest all are static Rather, it is interesting to note that the remaining digits will face binary accuracy error (when you convert some numbers to IEEE754 and back to the number, it won’t be the same. This will be addressed in the next question)

example for `123456789 + 1` it will be written as ```(1.23456792 + 0.00000001)*10^8``` you see that one is negligent when converted to this form hence the answer will be `1.23456792*10^8` (binary rep error in last digits)

now if we take `123456789 + 100` it will be written as ```(1.23456792 + 0.00000100)*10^8``` you see that 100 falls under the 8 digit range hence the answer will be `1.23456892*10^8` We got the idea about the exploit. but keep in mind, we need to select a number such that incrementing it will not affect the value but adding 256 to it should So we can discard numbers that are 7 digits or less since incrementing it affects the value Also we can discard numbers that are 10 digits or above since adding 256 won’t affect the value

Hence, we can only take numbers are that 8 and 9 digits long.

The question says, we can only use 7 characters or less.

We can simply represent the float value as `1.0E8` too

hence, the answer is within the range of `1E8 to 9.999E9`

Published on : 10 May 2021
misc