Legend of the Cyber King: Challenge 2
=====================================

I reversed engineered the verification code in the x86_64 shared library
provided in the apk using radare2. The reverse engineered code can be
found in re.c.

After identifying constraints a total of 1920 possible keys can be
generated. Out of the 1920 only 8 are valid and only one is accepted. This
is probably due to the application sending all keys that pass verification
to a server where only one key is sought after.

To test the solution first build the binaries by running `make`. Then you
can generate keys via `./keygen`. You can then verify the generated keys
by passing them to `verify-key` like so:

	make
	./keygen | ./verify-key


Constraints
-----------

Valid keys must consist of characters whose values add to 1337, blocks
seperated by '-', Characters within the range of 0x1f <= c <= 0x7a, must
have a set amount of bits with some in predefined indexes, a set amount of
symbol and number characters and have a total length of 21 bytes.

The starting point is first constructing a skeleton key out of the
predefined bit positions which we get from `requiredSetBits`. From here we
can compare this against `numSetBits` to find which characters are missing
bits.

This also reveals that some characters are constant and will never change
across each and every possible key. From here I decided to look at the
characters missing bits and see which ones could possibly become '-', by
looking at character index and value within the specified range I could
see that only some indexes can be dashes. These indexes just happened to
form valid blocks so thats another few characters that are static.

From here there are still quite a few characters which are undetermined
and this is where the generator comes in. I first defined a constraint for
each character, based on their initial value and missing bits, I defined
the only valid bit values which could be OR'd to the initial value and
still remain within range.

Now we just check if the total character sum adds to 1337. Which out of
1920 permutations only 8 matched, these 8 also happened to pass the other
verification checks which was unexpected but a pleasant suprise. This is
also where I discovered that the challenge is seeking one particular key
which is odd but we still win so I'm satisfied :D

Files
-----

        re.c: reversed engineered verification code. Messy.
    keygen.c: key generator. Will generate 8 valid keys which are written to
              stdout.
verify-key.c: Reads keys from stdin which are then verified. Displays
              which verification checks the key passes.
    common.h: Contains recreations of verification checks and shared
              components.
    Makefile: Small recipe to compile the binaries.