#1
|
|||
|
|||
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); } 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! |
#2
|
||||
|
||||
Quote:
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; } Last edited by UniSoft; 01-14-2018 at 21:31. |
#3
|
|||
|
|||
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. |
#4
|
|||
|
|||
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 |
#5
|
|||
|
|||
Quote:
|
The Following User Says Thank You to Stingered For This Useful Post: | ||
dila (01-17-2018) |
#6
|
|||
|
|||
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; } } } |
The Following User Says Thank You to dila For This Useful Post: | ||
tonyweb (01-18-2018) |
Thread Tools | |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
XP Startup - Must be simple because I can't solve it! | hobferret | General Discussion | 13 | 07-09-2005 07:44 |