# Number of combinations required to brute force

I am trying to encrypt a password in a program. Here is the process:

Let us assume that I have a string $p$ ($n$ characters long) which contains the password. Now the program reverse the string and stores it in string $r$. After that it takes each character of $p$ and $r$ applies the XOR operator and stores it in string $e$.

Next time the user want to access the file he/she will be asked to enter the password. The entered password will go through the process explained above and will be compared to string $e$. If both are not equal access will be denied.

I want to know the number of combinations of it will take a computer to brute force the password ("just to show if the encryption is mathematically effective or not, during the presentation"). Thanks

• Hints: 1) If ASCII encoding of characters is used and the password is BAT (42h 41h 54h), the password red (72h 65h 64h) will work just as well. 2) People choose easy to remember passwords, and that can be used to reduce the number of combinations it will take a computer to brute force the password. 3) If the string comparison is per the standard operator of most languages, a timing attack might make brute force linear with the number of characters, rather than exponential, even assuming random choice of password. – fgrieu Oct 11 '16 at 10:58
• ... 4) If the file itself is not encrypted etc., the attacker can access it directly instead of using the program. – deviantfan Oct 11 '16 at 11:52

## 1 Answer

You're actually describing a use case for cryptographic hash function (not encryption). A cryptographic hash is a one-way-function that is collision-resistant. Meaning that it is hard to guess a pre-image (input to the function) that will generate a given result (called a hash).
Cryptanalysis of schemes like this assume that there is some structure or predictable property of the plaintext, such as letter frequency or word choice. Let's assume that all of your users pick 4 words as their password (xkcd pass). And they choose it out of reasonable words in /usr/share/dict (about 50k words).
This is a strong password selection method, so if this scheme doesn't hold up under this plaintext pattern, it is most likely breakable under other password schemes.
Iterate through each word in the file, reverse it, and XOR it with the start of the password. We then take the result and do a look up in the sorted dictionary file (sorted during pre-computation). If this is a match, we've discovered two of the words and can recurse on the inner portion of the hash to find the last two words. This attack method assumes that all of the words are the same length, but I believe it can be easily adapted for various word lengths.
This attack will only take $$\Omega(n*logn)$$ steps of precomutation (for sorting the words file). And then $$2*n*logn$$ time for 100% guaranteed reversal of each hash. For a cryptographic hash (or one-way-function), you want a hash scheme to be secure in an exponential ratio to the number of bits, such as $$\Omega(2^n)$$, so this scheme is insecure.