Exetools - Encryption cracking challenge

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

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

- - Encryption cracking challenge (https://forum.exetools.com/showthread.php?t=19422)

Encryption cracking challenge

Can someone help find the key?

Code:

/*

 * poly.c crackme january 2020

 * dilabox at gmail dot com

 */



#include <stdint.h>

#include <stdio.h>



uint64_t poly(uint64_t a, uint64_t b) {

  uint64_t r = 0;

  while (b) {

    r ^= a & -(b & 1);

    uint64_t m = -((a >> 63) & 1);

    a <<= 1;

    a ^= m & 0x307fdb4d20abf247;

    b >>= 1;

  }

  return r;

}



uint64_t encrypt(uint64_t data, uint64_t key) {

  data ^= key;

  uint64_t out = 1;

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

    if ((0x61e261e161e261e2 >> i) & 1) {

      out = poly(out, data);

    }

    data = poly(data, data);

  }

  out ^= key;

  return out;

}



uint64_t decrypt(uint64_t data, uint64_t key) {

  return encrypt(data, key);

}



int main() {

  uint64_t key = 0;

  scanf("%lx", &key);

  if (encrypt(0xe9eec16478534a39, key) == 0xf3201dcbbeefe53a) {

    printf("GOOD\n");

  } else {

    printf("BAD\n");

  }

  return 0;

}

some lines don't make sense !

uint64_t m = -((a >> 63) & 1);

how do you assign a negative value to an unsigned int64 ?

-x is the same as ~x + 1

In this case the code is extracting the most-significant bit (MSB) from a and then creating a 64-bit mask from it.

If MSB(a) == 0, the result is 0x0000000000000000
Otherwise, if MSB(a) == 1, the result is 0xFFFFFFFFFFFFFFFF

Some compilers might warn or even generate an error over that. But as said it's just a 2s compliment and the sign but is merely interpreted differently as a cast occurred to signed and back to unsigned. This challenge is interesting need to look for a crypto weakness in the inner function perhaps. Brute force won't work with 2^64...