Exetools - Can you solve this keygen problem?

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

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

- - Can you solve this keygen problem? (https://forum.exetools.com/showthread.php?t=18601)

Can you solve this keygen problem?

Code:

bool check_key(uint64_t x) {

  uint64_t r = x;

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

    for (size_t j = 0; j < 6; ++j) {

      r ^= (((x >> (1 << j)) & (i >> j) & 1) << i);

    }

  }

  return (x && r == 0);

}

The objective is to find valid 64-bit input keys that make the function return 'true'.

1. How many valid input keys are there?
2. Can you make a generator to enumerate all valid keys?

Z3 (or other SMT/SAT) tools are not allowed as solutions!

Quote:

Originally Posted by dila (Post 111867)

The objective is to find valid 64-bit input keys that make the function return 'true'.

1. How many valid input keys are there?

A lot...

Code:

#include <stdlib.h>

#include <stdio.h>

#include <stdint.h>

#include <stdbool.h>

#include <time.h>



bool check_key(uint64_t x) {

  uint64_t r = x;

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

    for (size_t j = 0; j < 6; ++j) {

      r ^= (((x >> (1 << j)) & (i >> j) & 1) << i);

    }

  }

  return (x && r == 0);

}



uint64_t generate(void) {

  uint64_t r, x;



  do {

    x = (((uint64_t)rand() * rand()) * rand()) ^ rand();

    r = 0;

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

      for (size_t j = 0; j < 6; ++j) {

        r ^= (((x >> (1 << j)) & (i >> j) & 1) << i);

      }

    }

  } while (r == 0);

  return r;

}



int main(int argc, char *argv[])

{

    uint64_t r;

    srand((unsigned)time(NULL));



    r = generate();

    if (check_key(r))

        printf("%016llu => OK\n", r);

    else

        printf("%016llu => FAIL\n", r);



    //_getch();

    return 0;

}

Thank you for the solution. It was interesting to see how you solved it.

The list of keys is actually very small. I will post them here if nobody finds them first.

There are only 63 valid keys (shown below). I won't post my generator, since you pretty much solved it already.

Actually, 0x0000000000000000 (the all-zero key) is also accepted by the loop, but the check routine explicitly disallows this as a solution at the end.

I would not say that 64 keys out of a 2^64 input space is "a lot". The challenge was deliberately created to have only a few solutions.

Code:

aaaaaaaaaaaaaaaa

cccccccccccccccc

6666666666666666

f0f0f0f0f0f0f0f0

5a5a5a5a5a5a5a5a

3c3c3c3c3c3c3c3c

9696969696969696

ff00ff00ff00ff00

55aa55aa55aa55aa

33cc33cc33cc33cc

9966996699669966

ff00ff00ff00ff0

a55aa55aa55aa55a

c33cc33cc33cc33c

6996699669966996

ffff0000ffff0000

5555aaaa5555aaaa

3333cccc3333cccc

9999666699996666

f0ff0f00f0ff0f0

a5a55a5aa5a55a5a

c3c33c3cc3c33c3c

6969969669699696

ffff0000ffff00

aa5555aaaa5555aa

cc3333cccc3333cc

6699996666999966

f00f0ff0f00f0ff0

5aa5a55a5aa5a55a

3cc3c33c3cc3c33c

9669699696696996

ffffffff00000000

55555555aaaaaaaa

33333333cccccccc

9999999966666666

f0f0f0ff0f0f0f0

a5a5a5a55a5a5a5a

c3c3c3c33c3c3c3c

6969696996969696

ff00ffff00ff00

aa55aa5555aa55aa

cc33cc3333cc33cc

6699669999669966

f00ff00f0ff00ff0

5aa55aa5a55aa55a

3cc33cc3c33cc33c

9669966969966996

ffffffff0000

aaaa55555555aaaa

cccc33333333cccc

6666999999996666

f0f00f0f0f0ff0f0

5a5aa5a5a5a55a5a

3c3cc3c3c3c33c3c

9696696969699696

ff0000ff00ffff00

55aaaa55aa5555aa

33cccc33cc3333cc

9966669966999966

ff0f00ff00f0ff0

a55a5aa55aa5a55a

c33c3cc33cc3c33c

6996966996696996

Quote:

Originally Posted by dila (Post 111904)

Code:

aaaaaaaaaaaaaaaa

cccccccccccccccc

6666666666666666

f0f0f0f0f0f0f0f0

5a5a5a5a5a5a5a5a

3c3c3c3c3c3c3c3c

9696969696969696

ff00ff00ff00ff00

55aa55aa55aa55aa

33cc33cc33cc33cc

9966996699669966

ff00ff00ff00ff0

a55aa55aa55aa55a

c33cc33cc33cc33c

6996699669966996

ffff0000ffff0000

5555aaaa5555aaaa

3333cccc3333cccc

9999666699996666

f0ff0f00f0ff0f0

a5a55a5aa5a55a5a

c3c33c3cc3c33c3c

6969969669699696

ffff0000ffff00

aa5555aaaa5555aa

cc3333cccc3333cc

6699996666999966

f00f0ff0f00f0ff0

5aa5a55a5aa5a55a

3cc3c33c3cc3c33c

9669699696696996

ffffffff00000000

55555555aaaaaaaa

33333333cccccccc

9999999966666666

f0f0f0ff0f0f0f0

a5a5a5a55a5a5a5a

c3c3c3c33c3c3c3c

6969696996969696

ff00ffff00ff00

aa55aa5555aa55aa

cc33cc3333cc33cc

6699669999669966

f00ff00f0ff00ff0

5aa55aa5a55aa55a

3cc33cc3c33cc33c

9669966969966996

ffffffff0000

aaaa55555555aaaa

cccc33333333cccc

6666999999996666

f0f00f0f0f0ff0f0

5a5aa5a5a5a55a5a

3c3cc3c3c3c33c3c

9696696969699696

ff0000ff00ffff00

55aaaa55aa5555aa

33cccc33cc3333cc

9966669966999966

ff0f00ff00f0ff0

a55a5aa55aa5a55a

c33c3cc33cc3c33c

6996966996696996

I'd actually like to see the code, if you are so inclined. I'm fairly weak in this area and could use any example to walk through.

Posting the code, since you expressed interest in it. Here we have the "encoder" which encodes a 6-bit integer (between 1 and 63) into the full serial. Note that we skip i=0 (and start at i=1) because the all-zero key is rejected by the routine, even though it is technically valid. There are no other valid keys.

I will spend some time thinking of a new challenge that is not so easy for UniSoft to solve next time :)

Code:

uint64_t generate(uint64_t x) {

  uint64_t y = 0;

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

    uint64_t u = x & i;

    uint64_t k = 0;

    for (size_t j = 0; j < 6; ++j) {

      k ^= (u >> j) & 1;

    }

    y |= k << i;

  }

  return y;

}



void print_keys() {

  for (size_t i = 1; i < 64; ++i) {

    uint64_t key = generate(i);

    if (check(key)) {

      std::cout << std::hex << key << std::endl;

    } else {

      std::cout << std::hex << key << " (BAD)" << std::endl;

    }

  }

}