Exetools

Exetools (https://forum.exetools.com/index.php)
-   Source Code (https://forum.exetools.com/forumdisplay.php?f=46)
-   -   Keygenme (Easy?) (https://forum.exetools.com/showthread.php?t=16947)

dila 07-19-2015 05:00
Keygenme (Easy?)
 
Hi, I made a keygenme for you all to try. I am very interested to see how you solve it. Perhaps it is very easy for you!

Code:
/*
  ::::::::::::::::::::::
  :: Keygenme by dila ::
  ::    July 2015    ::
  ::::::::::::::::::::::
*/

#include <iostream>
#include <stdint.h>

uint64_t rol(const uint64_t value, const int places) {
  return (value<<places)|(value>>(64-places));
}

uint64_t ror(const uint64_t value, const int places) {
  return (value>>places)|(value<<(64-places));
}

bool stringToInteger(const std::string& input, uint64_t* r) {
  static const std::string lut = "0123456789abcdef";
  if (input.length() == 16) {
    *r = 0;
    for (size_t i = 0; i < input.length(); ++i) {
      size_t digit = lut.find_first_of(input[i]);
      if (digit == std::string::npos) {
        return false;
      }
      *r |= digit << (60 - i * 4);
    }
    return true;
  }
  return false;
}

uint64_t h0(const std::string& name) {
  uint64_t r = ~0x3141592653589793ULL;
  for (size_t k = 1; k <= 16; ++k) {
    for (size_t i = 0; i < name.length(); ++i) {
      int c = (13 + i * k) % 64;
      r ^= rol(uint64_t(name[i]), c);
    }
  }
  return r;
}

uint64_t h1(const uint64_t x) {
  return x ^ ror(x, 13);
}

bool check(const std::string& name, const std::string& serial) {
  uint64_t s;
  if (stringToInteger(serial, &s)) {
    if (h0(name) == h1(s)) {
      return true;
    }
  }
  return false;
}

int main() {
  std::string name;
  std::cout << "Name: ";
  std::getline(std::cin, name);

  std::string serial;
  std::cout << "Serial: ";
  std::getline(std::cin, serial);

  if (check(name, serial)) {
    std::cout << "Success! Thank you for registering." << std::endl;
  } else {
    std::cout << "Error. Invalid name/serial combination." << std::endl;
  }

  return 0;
}
To make sure that it is solvable, I generated one working serial for you:

Code:
Name: exetools
Serial: f7fb22fb6d474cb3

atom0s 07-19-2015 11:27
Compiled with VS2013, the given name/key you posted does not work with this.

QuakeGamer 07-19-2015 16:59
Quote:
Originally Posted by atom0s (Post 100663)
Compiled with VS2013, the given name/key you posted does not work with this.
Compiled with g++ under linux. Serial worked for me.

dila 07-19-2015 18:59
@atom0s I'm sorry, I have fixed the problem. The problem is the use of size_t as the return value on line 24 and not using uint64_t.

The full code tested on both Windows with MSVC 2013 and Linux with g++ is here, and now it accepts the original serial:

Code:
/*
  ::::::::::::::::::::::
  :: Keygenme by dila ::
  ::    July 2015    ::
  ::::::::::::::::::::::
*/

#include <iostream>
#include <stdint.h>
#include <string>

uint64_t rol(const uint64_t value, const int places) {
  return (value<<places)|(value>>(64-places));
}

uint64_t ror(const uint64_t value, const int places) {
  return (value>>places)|(value<<(64-places));
}

bool stringToInteger(const std::string& input, uint64_t* r) {
  static const std::string lut = "0123456789abcdef";
  if (input.length() == 16) {
    *r = 0;
    for (size_t i = 0; i < input.length(); ++i) {
      uint64_t digit = lut.find_first_of(input[i]);
      if (digit == std::string::npos) {
        return false;
      }
      *r |= digit << (60 - i * 4);
    }
    return true;
  }
  return false;
}

uint64_t h0(const std::string& name) {
  uint64_t r = ~0x3141592653589793ULL;
  for (size_t k = 1; k <= 16; ++k) {
    for (size_t i = 0; i < name.length(); ++i) {
      int c = (13 + i * k) % 64;
      r ^= rol(uint64_t(name[i]), c);
    }
  }
  return r;
}

uint64_t h1(const uint64_t x) {
  return x ^ ror(x, 13);
}

bool check(const std::string& name, const std::string& serial) {
  uint64_t s;
  if (stringToInteger(serial, &s)) {
    if (h0(name) == h1(s)) {
      return true;
    }
  }
  return false;
}

int main() {
  std::string name;
  std::cout << "Name: ";
  std::getline(std::cin, name);

  std::string serial;
  std::cout << "Serial: ";
  std::getline(std::cin, serial);

  if (check(name, serial)) {
    std::cout << "Success! Thank you for registering." << std::endl;
  } else {
    std::cout << "Error. Invalid name/serial combination." << std::endl;
  }

  return 0;
}

ketan 07-20-2015 07:33
another one is: 804DD0492B8B34C ;-)

arnix 07-21-2015 03:39
1 Attachment(s)
Quote:
Originally Posted by dila (Post 100655)
Hi, I made a keygenme for you all to try. I am very interested to see how you solve it. Perhaps it is very easy for you!
Thanks for the keygenme, here is a dirty brute-force based keygen.

arnix 07-21-2015 05:32
1 Attachment(s)
There was a small bug in the previous version. The keygenme wants keys with exactly 16 bytes long, so the smaller keys must be leaded with zeros (this is the reason why ketan's key won't be accepted by the keygenme (also must be in lowercase)). Here is a fixed version.

ketan 07-22-2015 04:20
http://pastebin.com/yQpTykRx

dila 07-25-2015 20:43
The objective was to take the input name and generate a working serial. Here is my analysis of the problem:

In general, a keygen must always be possible, since the software author has a means to generate working serials. And as I showed you, I had generated a key for the name "exetools", proving that I have a working keygen.

The core of the checking routine comes down to this comparison:

h0(name) = h1(serial)

A bt of algebra lets us transform this:

h1^-1(h0(name)) = h1^-1(h1(serial)

And the inverse functions cancel to give:

h1^-1(h0(name)) = serial

So to solve the keygenme is to find the inverse of the h1 function, then evaluate the above expression to produce a serial number from a given name.

I talked to João Marques on the Skype group about this (which you should join, incidentally), and he gave me his brilliant insight into the workings of the h1 function which allow you to solve it.

h1(x) := x ^ ror(x, 13)

He observed that this expression corresponds to a linear system of equations in the bits of x. Specifically, the following system:

x_0 + x_13 = y_0
x_1 + x_14 = y_1
x_2 + x_15 = y_2
: : :
x_n + x_([n+13]%k) = y_n

Now take a look at a simplified with a word length of 3 bits and rotate count of 1

x_0 + x_1 = y_0
x_1 + x_2 = y_1
x_2 + x_0 = y_2

The XOR behaves like carry-less addition modulo 2, and the system is completely determined once a single value has been chosen. So we start by setting any x_i to either 1 or 0, then all equations are solvable by back substitution.

Let x_0 = 0 then:

0 + x_1 = y_0
x_1 + x_2 = y_1
x_2 + 0 = y_2

implies that

x_1 = y_0
x_2 = y_2

Alternatively, let x_0 = 1, and arrive at the second solution to the system.

This is the solution implemented by ketan, requiring only word-length iterations to build up the solution key.

The h0() function can be implemented as-is and doesn't require any analysis.

So my question to you is this:

What is the smallest possible modification of the h1 function that will make the problem much harder, yet still possible, to solve.

If you start a new thread with your own problem of the form f(name) = g(serial), and I would be very interested in solving it with you :cool:


All times are GMT +8. The time now is 10:42.

Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2026, vBulletin Solutions, Inc.
Always Your Best Friend: Aaron, JMI, ahmadmansoor, ZeNiX