Exetools  

Go Back   Exetools > General > General Discussion

Notices

Reply
 
Thread Tools Display Modes
  #1  
Old 01-13-2018, 23:56
dila dila is offline
Friend
 
Join Date: Jan 2010
Posts: 60
Rept. Given: 12
Rept. Rcvd 32 Times in 14 Posts
Thanks Given: 35
Thanks Rcvd at 74 Times in 20 Posts
dila Reputation: 32
Lightbulb 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!
Reply With Quote
  #2  
Old 01-14-2018, 20:29
UniSoft's Avatar
UniSoft UniSoft is offline
Family
 
Join Date: May 2010
Location: Shenzhen, China
Posts: 124
Rept. Given: 23
Rept. Rcvd 259 Times in 42 Posts
Thanks Given: 23
Thanks Rcvd at 405 Times in 73 Posts
UniSoft Reputation: 200-299 UniSoft Reputation: 200-299 UniSoft Reputation: 200-299
Quote:
Originally Posted by dila View Post
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;
}

Last edited by UniSoft; 01-14-2018 at 21:31.
Reply With Quote
The Following 3 Users Say Thank You to UniSoft For This Useful Post:
dila (01-14-2018), SinaDiR (01-21-2018), Stingered (01-15-2018)
  #3  
Old 01-15-2018, 02:11
dila dila is offline
Friend
 
Join Date: Jan 2010
Posts: 60
Rept. Given: 12
Rept. Rcvd 32 Times in 14 Posts
Thanks Given: 35
Thanks Rcvd at 74 Times in 20 Posts
dila Reputation: 32
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.
Reply With Quote
  #4  
Old 01-16-2018, 16:41
dila dila is offline
Friend
 
Join Date: Jan 2010
Posts: 60
Rept. Given: 12
Rept. Rcvd 32 Times in 14 Posts
Thanks Given: 35
Thanks Rcvd at 74 Times in 20 Posts
dila Reputation: 32
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
Reply With Quote
  #5  
Old 01-17-2018, 01:08
Stingered Stingered is offline
Friend
 
Join Date: Dec 2017
Posts: 256
Rept. Given: 0
Rept. Rcvd 2 Times in 2 Posts
Thanks Given: 296
Thanks Rcvd at 179 Times in 89 Posts
Stingered Reputation: 2
Quote:
Originally Posted by dila View Post
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
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.
Reply With Quote
The Following User Says Thank You to Stingered For This Useful Post:
dila (01-17-2018)
  #6  
Old 01-17-2018, 02:28
dila dila is offline
Friend
 
Join Date: Jan 2010
Posts: 60
Rept. Given: 12
Rept. Rcvd 32 Times in 14 Posts
Thanks Given: 35
Thanks Rcvd at 74 Times in 20 Posts
dila Reputation: 32
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;
    }
  }
}
Reply With Quote
The Following User Says Thank You to dila For This Useful Post:
tonyweb (01-18-2018)
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


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


All times are GMT +8. The time now is 09:29.


Always Your Best Friend: Aaron, JMI, ahmadmansoor, ZeNiX, chessgod101
( 1998 - 2024 )