Keygenme (Easy?)

[dila]

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