Figuring out correct user input key from final key + generated buffer

Question

I've recently gotten into reversing crackmes, and I seem to always fail at the ones similar to this.

The final key that the program uses for comparison is not the key that should be used as input, the key used as input is used in an algorithm with another set of data to check if it generates the final key. Here is the code so it makes a bit more sense.

signed __int64 __fastcall ValidateSerials(unsigned int *generatedData, unsigned int *finalCorrectSerial, unsigned int *UserInputSerial)
{
  signed int i; // [rsp+0h] [rbp-18h]
  signed int j; // [rsp+4h] [rbp-14h]
  signed int currentUserInputsr; // [rsp+8h] [rbp-10h]
  int v7; // [rsp+Ch] [rbp-Ch]

  for ( i = 0; i < 4; ++i )
  {
    v7 = 0;
    currentUserInputsr = UserInputSerial[i];
    for ( j = 6; j >= 0; --j )
    {
      v7 += generatedData[j] * (currentUserInputsr & 1);
      currentUserInputsr >>= 1;
    }
    if ( v7 != finalCorrectSerial[i] )
      return 0i64;
  }
  return 1i64;
}

if I know generatedData and finalCorrectSerial, how can I generate the correct UserInputSerial? I've tried to reverse the entire functions logic but I always get it wrong. I'm fairly new into solving keygens such as this but not reverse engineering in general.

Thanks

Answer 1

I wrote a function, that generates a valid input from given generatedData and finalCorrectSerial. The function calculates a subset that, when summed up, equals the corresponding value in finalCorrectSerial. It then creates a valid input from that. (The function subsetSum() is taken from here and was modified to return just one subset and that by it's indices):

bool subsetSum(unsigned int* set, unsigned int* subSet, int n, int subSize, int total, int nodeCount ,int sum, int* outN) {
   if( total == sum) {
       *outN = subSize;
      return 1;
   } 
   else {
      for( int i = nodeCount; i < n; i++ ) {     //find node along breadth
         subSet[subSize] = i;
         if (subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum, outN)) return 1;     //do for next node in depth
      }
   }
   return 0;
}

bool genInput(unsigned int* generatedData, unsigned int* finalCorrectSerial, unsigned int* out) {
    for (int i = 0; i < 4; i++) {
        unsigned int subs[7];
        int size = 0;
        subsetSum(generatedData, subs, 7, 0, 0, 0, finalCorrectSerial[i], &size);

        std::cout << "finalCorrectSerial[" << i << "] (" << finalCorrectSerial[i] << ") has " << (size ? "a" : "no") << " subset (indices): ";
        for (int j = 0; j < size; j++ ) {
            std::cout << subs[j] << " ";
        }
        std::cout << "\n";

        if (!size) return 0;

        for (int j = 0; j < size; j++) {
            out[i] |= (1u << (6 - subs[j]));
        }

    }
    return 1;
}

A test run (with arbitrary numbers):

int main()
{
  unsigned int genData[] = { 10, 55, 1, 3, 7, 98, 1};
  unsigned int key[] = { 66, 5, 4, 5};
  unsigned int input[4] = { 0 };

  std::cout << "Generating Input was " << (genInput(genData, key, input) ? "successfull\n" : "unsuccessful\n");
  for (int j = 0; j < 4; j++) {
            std::cout << input[j] << " ";
    }
    std::cout << "\n";

  std::cout << (ValidateSerials(genData, key, input) ? "true" : "false");

  return 1;
}

returns

finalCorrectSerial[0] (66) has a subset (indices): 0 1 2 
finalCorrectSerial[1] (5) has a subset (indices): 2 3 6 
finalCorrectSerial[2] (4) has a subset (indices): 2 3 
finalCorrectSerial[3] (5) has a subset (indices): 2 3 6 
Generating Input was successfull
112 25 24 25 
true

Answer 2

This function simply checks each input number (UserInputSerial[i]) whether it is correct and it's doing so by summing up generatedData[j] * (UserInputSerial[i] & (1 << (6 - j))), so it's basically iterating through UserInputSerial[i]'s 7 least significant bytes and if some of them is 1 the relevant number from generatedData will be taken into the sum (v7).

Since, I suspect, the author of this crackme wants to accept only one input, v7 has to get different values for all possible inputs, so for each a = UserInputSerial[i1], b = UserInputSerial[i2], if a != b, then v7 counted for a has to be different than v7 counted for b. In other words, if v7 is function taking UserInputSerial[i] and generatedData, it has to be injection.

The easiest way to generate such a function is to initialise generatedData in such a way, that generatedData[j] > sum(generatedData[i<j]). So for example it could be that generatedData[j] = 2^j or generatedData[j] = 3^j. So, knowing the correct v7 value for each UserInputSerial[i] and generatedData, you should be able to easily obtain the x such that v7(x, generatedData) = finalCorrectSerial[i] in a way similar as you would convert finalCorrectSerial[i] to binary.

So, assuming that indeed generatedData[j] > sum(generatedData[i<j]), you can write something like this:

char bits[7]; // bits of the correct UserInputSerial[i]
int a = finalCorrectSerial[i];
for (j = 6; j >= 0; j--)
{
    if (a >= generatedData[j])
    {
        a -= generatedData[j];
        bits[j] = 1;
    }
    else
        bits[j] = 0;
}

If it's not the case, you can just check v7(x, generatedData) for all possible numbers having less or 7 bytes and check which one will cause v7 to produce the desired value (finalCorrectSerial[i]).