decryption routine - interested in some ideas ...

[joblack]

Some months ago I read about an interesting mind exercise (it was some kind of for job offer in a magazine). I was thinking about it for several days but haven't found another solution than 'brute force' (there is a rotation through the char keys but haven't found an alorithmic solution to exploit that).

#include <iostream>
#include <cstdlib>

using namespace std;

char *key = "????????";
//char secret[] = "ZJ]]_Y2ec%_hXH]P\\%k_eS2OSW4n\\]f+RJincNUS.QU_eLW].Ngn7F^^.IY17XUSZZYmjJ^!";
//char out[100];

void decrypt(char *secret, char *key){
char c;
char *k = key;
while ((c = *secret) != 0){
*secret++ = (c-32) - ((*k)-64) + 32;
k = *(k+1) ? k+1 : key;
}
}

int main(int argc, char *argv[]){


strcpy(secret, "ZJ]]_Y2ec%_hXH]P\\%k_eS2OSW4n\\]f+RJincNUS.QU_eLW].Ngn7F^^.IY17XUSZZYmjJ^!");
decrypt(secret,key);
cout << "SECRET MESSAGE: " << secret << endl;


return EXIT_SUCCESS;
}

Has anybody an idea how to solve this?

[zeta]

do I see it right?
you need to find out the first key and the operator needed to calculate the next key?
did you code this given a general formulation of the problem? if so, this would be nice to see or have!

[joblack]

You have the input data and the formula but you don't have the key (which is most probably 8 chars long).

[zeta]

here is a bit of misunderstanding!
I ment I would like to see the formulation of the formula!
and in this line of code
k = *(k+1) ? k+1 : key;
I don't know what "?" means!

[joblack]

Yes it rotates through the keys for every character and at the end of they it jumps to the beginning.

it means

if (*(k+1)) then k=k+1 else k=key;

Obviously it checks the null-character at the end of the character string (also know as \0).

[zeta]

well I see!

but some things remain:
how do you come to this *secret++ = (c-32) - ((*k)-64) + 32;
and based on what can you make the assumption that the key is 8 chars long? (for me it makes a big difference if it theoretically can be in a certain range)
do you mean by bruteforcing going through all 2^64 possibilities?

[joblack]

The key is 8 characters long because there are eight question marks. You can probably decrease the number of tries by only trying out visible characters but still. A dictionary attack wasn't successful.

I also heart from somebody that there is a weakness in the decryption/encryption algorithm that I can't see at the moment.

[zeta]

The key is 8 characters long because there are eight question marks.

because of this statement, I assume u got the code like this, and I take the key as being 8 chars long.

You can probably decrease the number of tries by only trying out visible characters but still. A dictionary attack wasn't successful.

that would also have been my suggestion, but do you mean trying out visible chars in the key or in the result?
of course only the second would make sense!

[drizz]

commutative rule of addition
-32 +32 = 0;
64 can be aplied to "secret" once on program start;
we then come to: { *secret++ = c - *k };
ps: use "out" buffer so you don't modify "secret"

[zeta]

I had an other thought on this and came to the conclusion that there is the need to know the exact encryption algo!
if I asume this algo to be generic there are some possibilities that make sense, but without the exact encryption algo, the task to check the plain text for validity reveals to be the hardest for me!
so how did you check the results of your dictionary attack?

[Tora]

Maybe I'm missing something, but that seems a caesar cipher with key (secret[i] - K[i%keylen] - 64). If the keylen is known, the common approach is to split the ciphertext into keylen lenght blocks and try to get the K[] ranges that produce decrypted bytes in [a-zA-Z0-9] (plus space and some symbols).

Let's say keylen is 8:

Code: Select all

5A 4A 5D 5D 5F 59 32 65
63 25 5F 68 58 48 5D 50
5C 5C 25 6B 5F 65 53 32
4F 53 57 34 6E 5C 5C 5D
66 2B 52 4A 69 6E 63 4E
55 53 2E 51 55 5F 65 4C
57 5D 2E 4E 67 6E 37 46
5E 5E 2E 49 59 31 37 58
55 53 5A 5A 59 6D 6A 4A
5E 21


For example, the third column (where K[2] will do its job) has three 0x2E values, then we can guess that K[2] would be in the range [115-140 (decrypts to a-z), 147-172(decrypts A-Z), 180-189 (0-9)]. This way and playing with ranges given other values of the same column, you can reduce a lot the bruteforce required, you just need to guess a bit the key's charset.

If keylen is unkown, then you can apply the range trick for every encrypted byte and try to find similar ranges in equal-spaced blocks.

Well, just a few random thoughts that i hope give you some new ideas ;D

[zeta]

but that seems a caesar cipher

nice to know the name!

[Tora]

nice to know the name!

Well, is not exactly a Caesar but it's close to. Let's say a Caesar cipher is an specific case where the key is in the form "AAAA...", "BBBB...", etc. because the offset will be constant.

[joblack]

The problem is that the key isn't known ...

[cronos]

It's only a kind of extended Vigenere with the advantage that some of the characters in the character set probably don't appear in the final text, just use standard Vigenere cracking methods.