2

I am beginner in cyber security. Now I am participating on Facebook Catch the Flag contest. I have to solve following task:

There is a key. But the first four characters of the key are missing:

_ _ _ _ U3xn3Gk9y

This is the algorithm:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    FILE *fi, *fo, *fk;
    int i, r;
    char key[20], text[100];

    fi = fopen("flag.txt", "r");
    fo = fopen("encrypted.txt", "w");
    fk = fopen("key.txt", "r");

    fscanf(fi, "%s", text);
    fscanf(fk, "%s", key);



    srand(key[0] * key[1] * key[2] * key[3]);
    for(i = 0; i < strlen(text); ++i)
    {
        r = rand();
        putc(r ^ key[(r % strlen(key))] ^ text[i], fo);
    }

    fclose(fi);
    fclose(fo);
    fclose(fk);
    return 0;
}

Encrypted text:

РY‘ґЊЈZц‚…Jщ,PvPw#ѓЗfыbаЁ+dИ?ѕцiЃyЛSBШ“¦ЕiЈ;иb—щьХЗ*]ЋOЛ,O™µEкЧи–ББш}

I need to decypher the ecrypted text.

First of all, I am not asking for solution or answer. I am asking for some hints:

  1. From where should I start to solve: to find first 4 characters of key or random number?

  2. How does rand() algorithm work?

  3. If r ^ key[(r % strlen(key))] ^ text[i] = encrypted[i] is true, what will be formula for text[i]=?

  4. Is there any mathematical way to solve this problem? If there is could you name it?

  5. Could you give any hint (not solution) to solve this problem?

  • Looks like you basically need to bruteforce the last 4 characters of the key. Given the rest of the key it looks like alpha numeric those characters probably are too. As to the working of rand(), this is implementation dependant and just means can I have a pseudo-random number between 0 and 1, and srand is used to seed it. Now this means it will give the same order of numbers with a given seed assuming the same implementation. Did they say it is to be compiled with GCC against GCC libraries and executed on a Linux machine or anything? – ewanm89 Jun 12 '16 at 16:34
  • Oh, should be worth noting, algorithm is not secure in any way as pseudo-random number generators being used are not secure, rand() is for simulations rather than secure RNG generation. – ewanm89 Jun 12 '16 at 16:37
  • 1
    Do you have a link to the CTF? I couldn't find it online, looks like fun. – Polynomial Jun 12 '16 at 19:08
  • 1
    This question specifically asks for a mathematical solution, that is not opinion based. Even asking for hints can be a good question – Neil Smithline Jun 13 '16 at 0:24
  • 1
    @bayo15 to me it looks like someone else is hosting the Facebook CTF that was openly released a couple of weeks ago :) – yzT Jun 13 '16 at 5:41
4

A few hints:

  1. The letters in the key are likely to be within the ASCII printable range.
  2. The decoded text is likely within the ASCII printable range.
  3. It's not very hard to bruteforce a 32-bit number, even less hard if you can reduce the key space down.
  • Given rest of the known key are within alphanumeric range rather I would probably just try that first before adding in the rest of the printable range. – ewanm89 Jun 13 '16 at 6:43
1

Yes, you can brute force this rather quickly, but in case you are curious, you don't need to brute force this entire solution. There is a mathematical approach. You might even require pieces of this anyway since this seems to be a hashing algorithm and not an encryption algorithm (I.e. it is not reliably reversible).

Does it make you curious that a repeatable encryption algorithm uses random number generation? That can only work when the random seed (look up srand) is set consistently for the same input, meaning consecutive calls to rand() will return the same ordered sequence of results.

Q. How is the random seed set in this case?

A. By the product of the character codes of the first four characters, the ones that happen to be missing.

We know from the code that the resulting encrypted text will have the same length as the plaintext input. We also know that each encrypted output character is generated by the original character at its index like this: (random number generated from the seed at the n'th pass where n is the current index + 1) ^ (that same random number mod the key length of 13 in your example) ^ (the character code at the current index).

From that you can derive a simple mathematical formula to find r at a given pass through encryption based on an output character code and index.

I couldn't find an official source for free, but several places like here show how the c rand function is implemented:

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

Notice that the seed is adjusted each time a number is generated. You can build another formula based on the rand implementation to find what possible values next can when rand returns the character code associated with the 5th character of the output (the first one associated with a key character that you know). Take each of those possibilities and filter them down by running subsequent passes through rand based on the code above and the encryption code using the rand output as the r value and checking the results against the next characters of the output until you are left with only a single valid possible option for next at the 5th pass.

Once you know that, reverse that one time for each of the previous characters to get the first 4 values of r. Once you have solved for those values of r, all that's left is to reverse output[i] = r ^ key[(r % strlen(key))] ^ text[i] to solve for text[i]. It will be useful to recall that the inverse of y = a ^ x is y = log base a (x). Plug in the r values you solved for previously in the right order to get the character codes associated with that pass through the encryption. Add those to the beginning of the key and check your work by reversing the encryption algorithm and passing in your new key with the encrypted text and seeing if the output makes sense. If it does, you've completed the challenge without brute force (except perhaps in your filtering).

Of course, since the key space is small enough to bruteforce, you can always do that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.