Exetools - Find the secret key for this function

Exetools (https://forum.exetools.com/index.php)

- General Discussion (https://forum.exetools.com/forumdisplay.php?f=2)

- - Find the secret key for this function (https://forum.exetools.com/showthread.php?t=17619)

dila	06-02-2016 07:36

Find the secret key for this function

Code:

bool check(uint64_t key)

{

    return key * key * key * key * key * key * key == 0x90de757572b51cd3;

}

It returns true for the the correct key, but what is it and how do you find it?

Conquest

06-02-2016 13:30

find the 7th root of the value. Any mathematics solver program should be good enough

SmilingWolf

06-02-2016 14:36

Quote:

Originally Posted by Conquest (Post 105587)

find the 7th root of the value. Any mathematics solver program should be good enough

Yeah... except that the 7th root of that value is not an integer while the input to the function is.
You have to find an x such that (x^7 & 0xFFFFFFFFFFFFFFFF) == 0x90de757572b51cd3

anon_c

06-02-2016 14:52

@Conquest
Not exactly. Bear in mind the Int64 precision.

Say you work in 16 bits
You want X^7 == 8680
Solve for the 7th root and you will get in decimal 4.44712��
But a valid solution would be for instance: 4A (74 dec) because the result of 4A ^ 7 is 8680 in 16bit

@Dila
I don��t see any other option than brute force

AC

Kerlingen

06-02-2016 16:41

E80E9AAC619831FB

And no, I didn't bruteforce 20.000 years, it's just simple math.

Just as a small hint:
If "x^7" is supposed to end on the digit "3", could "x" ever be a multiple of "2"?
Answer: No.
You've reduced the number of possible values for "x" by 50%.

Syoma

06-02-2016 21:13

It is the standard x^y mod n = c like RSA uses but with bad modulo N.

UniSoft

06-02-2016 23:14

Code:

#define EXP7(x)  ((x) * (x) * (x) * (x) * (x) * (x) * (x))



uint64_t res = 0x90de757572b51cd3ULL;

uint64_t key = 0;

uint64_t mask = 1ULL;



while (mask)

{

    if ((EXP7(key) ^ res) & mask)

    {

        key |= mask;

        if ((EXP7(key) ^ res) & mask)

            break;

    }

    mask <<= 1;

}



if (mask)

    printf("not found");

else

    printf("found: 0x%llX", key);

Kerlingen

06-02-2016 23:14

RSA is x^y with known x and unknown y.
This is x^y with unknown x and known y.
Two completely different things.

niculaita

06-02-2016 23:38

try this 0xFFFFFFFFFFFFFE0B or this 0xFFFFFFFFFFFFFE0C

anon_c

06-03-2016 00:21

@Kerlingen
��just simple math��
What is the mathematical solution then? (I know it is not a difficult key to find��)

I believe everybody knows you don��t have to try all numbers! Indeed, simple math can be used to avoid nonsense bases. But I am curious to know your definition of brute force. Do you really believe trying all possible solution is the only definition? Dictionary attack over a WPA key for instance, is still a kind of Brute-force attack��

AC

Syoma

06-03-2016 03:35

Quote:

Originally Posted by Kerlingen (Post 105602)

RSA is x^y with known x and unknown y.
This is x^y with unknown x and known y.
Two completely different things.

RSA powmod primitive is
c = m^e mod N, where c is ciphertext, m - message, e - public exponent, N - modulus
m = c^d mod N, where d is private exponent

our case is
0x90de757572b51cd3 = key^7 mod (max_uint64+1)

UniSoft

06-03-2016 12:15

Quote:

Originally Posted by Syoma (Post 105606)

This is not the RSA !!!
In RSA N = p * q, where p and q are prime numbers!!!
max_uint64+1 = 0x10000000000000000 is not the product of two prime numbers, therefore the equation m = (m^e mod N)^d mod N will not work (mainly because of the large number of collisions).

Syoma

06-03-2016 16:42

Quote:

Originally Posted by UniSoft (Post 105607)

This is not the RSA !!!

Did you ever read the topic? I wrote
It is the standard x^y mod n = c like RSA uses but with bad modulo N.
I did not write it is RSA. My suggestion was there may be simple math solution in number theory.

Just reviewed most popular directions. Do not see any simple solution.
x^7 = 3*3*31*4129*1499933*6041353 mod 2^64

DARKER

06-03-2016 17:29

0x90de757572b51cd3 = 10438910133587483859

10419912285387762041 = 521 ^7
10438910133587483859 = ~521,136 ^7 <- this is your number
10560719825892021888 = 522 ^7

but your key is uint64, so this is not possible because ~521,136 is not integer

PS: Other solution can be some another integer, it's case when you strip result to uint64 (last bytes of result are 0x90de757572b51cd3 - it's just end of some big number)

dila	06-05-2016 17:58

In textbook RSA, you compute phi(n) from (p-1)(q-1), but that formula does not work if the modulus contains repeated prime factors. Here we have n = 2^64, so there are repeated 2's.

The requirement for modular exponentiation to be reversible is that gcd(e, phi(n)) = 1. If that turns out to be true, then a private exponent exists, which can "decrypt" the magic constant into the value of key.

@UniSoft: How does your solving code work?? :)

mr.exodia

06-05-2016 18:43

My code for solving (see here on how to install z3py):

Code:

from z3 import *



key = BitVec('key', 64)

solve((key * key * key * key * key * key * key) == 0x90de757572b51cd3)

Output:

Code:

[key = 16721472531635646971]

0xE80E9AAC619831FB

dila	06-05-2016 20:59

Here is my solution based on solving it as an RSA problem:

key^7 = x (mod 2^64)
x^d = key (mod 2^64)

Where d is the private exponent, calculated by finding the multiplicative inverse of 7 modulo phi(2^64) = 2^63, which turns out to be 0x6db6db6db6db6db7.

Raising the magic constant to this private exponent, and taking modulo 2^64, produces the seret key 0xe80e9aac619831fb, as found by Kerlingen, UniSoft, and mr.exodia.

Code:

#include <iostream>

#include <stdint.h>

 

uint64_t modexp(uint64_t a, uint64_t b) {

  uint64_t y = 1;

  uint64_t tmp = a;

  for (int i = 0; i < 64; ++i) {

    uint64_t mask = uint64_t(1) << i;

    if (b & mask) {

      y *= tmp;

    }

    tmp *= tmp;

  }

  return y;

}

 

int main() {

  uint64_t in = 0x90de757572b51cd3;

  uint64_t tmp = modexp(in, 0x6db6db6db6db6db7);

  uint64_t out = modexp(tmp, 7);

  if (in == out) {

    std::cout << "Success: " << std::hex << tmp << std::endl;

  } else {

    std::cout << "Error" << std::endl;

  }

  return 0;

}

aliali

06-07-2016 06:03

Quote:

Originally Posted by dila (Post 105628)

Here is my solution based on solving it as an RSA problem:

key^7 = x (mod 2^64)
x^d = key (mod 2^64)

Code:

#include <iostream>

#include <stdint.h>

 

uint64_t modexp(uint64_t a, uint64_t b) {

  uint64_t y = 1;

  uint64_t tmp = a;

  for (int i = 0; i < 64; ++i) {

    uint64_t mask = uint64_t(1) << i;

    if (b & mask) {

      y *= tmp;

    }

    tmp *= tmp;

  }

  return y;

}

 

int main() {

  uint64_t in = 0x90de757572b51cd3;

  uint64_t tmp = modexp(in, 0x6db6db6db6db6db7);

  uint64_t out = modexp(tmp, 7);

  if (in == out) {

    std::cout << "Success: " << std::hex << tmp << std::endl;

  } else {

    std::cout << "Error" << std::endl;

  }

  return 0;

}

An enhanced version of modexp function

Code:

uint64_t modexp(uint64_t a, uint64_t b)

{

        uint64_t y = 1;

        uint64_t tmp = a;

        while( b )

        {

                if( b & 1 )

                        y *= tmp;

                tmp *= tmp;

                b >>= 1;

        }

        return y;

}

Seth333

06-21-2016 21:28

Quote:

Originally Posted by mr.exodia (Post 105626)

My code for solving (see here on how to install z3py):

Code:

from z3 import *



key = BitVec('key', 64)

solve((key * key * key * key * key * key * key) == 0x90de757572b51cd3)

Output:

Code:

[key = 16721472531635646971]

0xE80E9AAC619831FB

I still don't get it :confused:

Can anyone explain me the mathematical way to calculate this ?

I always come up to a different result.

Like:

0xE80E9AAC619831FB ^7 = 0x80BE33B7E7E4CB02B42B9C6FDF0D774CC0645D8992D29738EC470B848F80CFA482BA62D01E70C65E397E7EFE6F190D1990DE757572B51CD3

or something like that

Where is my "think failure" ?

- Seth

chessgod101

06-21-2016 23:47

We are calculating this with a 64 bit precision constraint. Since you overload the numerical capacity of 64 bits, the rest of the information is lost as a result. Since you are calculating this with full precision, you need to and your result by 0xFFFFFFFFFFFFFFFF.
0x80BE33B7E7E4CB02B42B9C6FDF0D774CC0645D8992D29738EC470B848F80CFA482BA62D01E70C65E397E7EFE6F190D1990DE757572B51CD3 <- 64 bit value

All times are GMT +8. The time now is 07:48.