PHP: XOR cypher decryption function doesnt work

Question

Lately, I have been doing some research into cryptography. To get a better understanding of all of it, I have been trying to write a more advanced version of the XOR cypher in PHP. I got the encryption function to work just fine, but the decryption function output is quite strange and totally different from the message inputted.

The idea of the algorithm is to run a XOR operation first on the first and last character, then on the second and one but last character, and so on. After that, it runs a XOR operation on the first two characters and the last two characters, then the third and fourth character and the 2th and 3th to last, and so on once again. This goes on with blocks of 3, 4, 5 and more characters.

The code I have right now:

<?php
function encrypt($message, $key) {
    $output_text = '';

    // Add zeros at the end until the length of the message corresponds with the length of
the key
    $message = str_pad($message,strlen($key),0);

    if((strlen($message) % 2)) {
        // The lenght of the message is odd, add a zero
        $message = $message . 0;
    }

    // Define the final length of the message
    $length = strlen($message);

    // Firstly, take 1 character, then 2, then 3, etc. until you reach half the length of the message
    for($characters=1; $characters<=($length/2); $characters++) {
        // Loop from i til half the length of the message
        for($i=0; $i<=(($length/2)-1); $i += $characters) {
            // Take the first and last character, the the first two and the last two, etc.

            // Stop when it crosses half the length
            if( ($i + $characters ) >= ( $length / 2 ) ) break;

            // firstly, the characters at the beginning
            $beginning = substr($message, $i, $characters);
            for($j=0; $j<$characters; $j++) {
                $position = ( $i + 1 ) + $j;
                $output_text .= chr(ord($beginning{$j}) ^ ord($key{$position}));
            }

            // Then those at the end
            $ending = substr($message, $length-(($i+1) * $characters), $characters);
            for($j=0; $j<$characters; $j++) {
                $position = ( $length - ( ( $i + 1 )* $characters) ) + $j;
                $output_text .= chr(ord($ending{$j}) ^ ord($key{$position}));
            }
        }
    }

    return $output_text;
}
function decrypt($message, $key) {
    $output_text = null;

    // Define the final length of the message
    $length = strlen($message);

    // Firstly, take 1 character, then 2, then 3, etc. until you reach half the length of the message
    for($characters=1; $characters<=($length/2); $characters++) {

        // Loop from i til half the length of the message
        for($i=0; $i<=(($length/2)-1); $i += $characters) {
            // Take the first and last character, the the first two and the last two, etc.

            // Stop when it crosses half the length
            if( ($i + $characters ) >= ( $length / 2 ) ) break;

            // firstly, the characters at the beginning
            $beginning = substr($message, $i, $characters);
            for($j=0; $j<$characters; $j++) {
                $position = ( $i + 1 ) + $j;
                $output_text .= chr(ord($key{$position}) ^ ord($beginning{$j}));
            }

            // The those at the end
            $ending = substr($message, $length-(($i+1) * $characters), $characters);
            for($j=0; $j<$characters; $j++) {
                $position = ( $length - ( ( $i + 1 )* $characters) ) + $j;
                $output_text .= chr(ord($key{$position}) ^ ord($ending{$j}));
            }
        }
    }

    return $output_text;
}

$message = 'sampletextjusttotrythisoutcreatedin2012';
$key = '123';
$output_text = encrypt($message, $key);
echo $output_text . '<br /><hr />';
echo decrypt($output_text, $key);

Thanks in advance for trying to help me!

I'm not sure how your "encryption" algorithm is supposed to work, but it doesn't. It's extending a cleartext of 15 bytes to an ciphertext of 594 bytes, including big chunks of cleartext. — user149341
– user149341, Commented Jan 6, 2012 at 16:42
Its supposed to work like I explained in the post, and once again, its not for practical use, just to get a better understanding ;) — Jeroen
– Jeroen, Commented Jan 6, 2012 at 16:48
Put it this way, I know the encryption isnt functional at all, but if assumed this is the encryption function, what would the correct decryption function be? — Jeroen
– Jeroen, Commented Jan 6, 2012 at 16:49
XOR is a mathematical primitive, not a cipher - when you say "XOR cipher", I presume you mean the vigenere cipher with XOR as the combining operation. You probably won't learn a great deal with this made-up construction, since it doesn't resemble any standard cipher or mode of operation - you'd be better off learning the very basics of how stream or block ciphers work, and writing your own demo cipher based on that. — Nick Johnson
– Nick Johnson, Commented Jan 9, 2012 at 5:56

Tails · Accepted Answer · 2012-01-07 21:13:16Z

Let's start with something a bit simpler - given a message and a key, XOR the message with the key to encrypt it. XOR the encrypted message with the key to decrypt it.

$msg = "The rooster crows at midnight!";
$key = "secret key";

$cipher_text = simple_xor($msg, $key);
$plain_text  = simple_xor($cipher_text, $key);

echo "Original msg: $msg\n";
echo "Supplied key: $key\n";
echo "\n";
echo "Cipher Text: " . base64_encode($cipher_text) . "\n";
echo "  Decrypted: " . $plain_text . "\n";

function simple_xor($input, $key) {

    # Input must be of even length.
    if (strlen($input) % 2)
        $input .= '0';

    # Keys longer than the input will be truncated.
    if (strlen($key) > strlen($input))
        $key = substr($key, 0, strlen($input));

    # Keys shorter than the input will be padded.
    if (strlen($key) < strlen($input))
        $key = str_pad($key, strlen($input), '0', STR_PAD_RIGHT);

    # Now the key and input are the same length.
    # Zero is used for any trailing padding required.

    # Simple XOR'ing, each input byte with each key byte.
    $result = '';
    for ($i = 0; $i < strlen($input); $i++) {
        $result .= $input{$i} ^ $key{$i};
    }
    return $result;
}

Here you can see intrinsic value of XOR. Given Msg XOR Key = C then C XOR Key = Msg and C XOR Msg = Key.

Now lets return to your approach - it appears you wish to mix more characters together to generate a 'stronger' encrypted result. Before doing that, take a moment to reflect on what creates encryption strength when using XOR in this fashion. During this process, assume the attacker has the above code, but not the $msg or $key.

The attacker will know how long your message and key are, because this algorithm always generates a result that is the same number of bytes as the message and key.

The strongest key will be one where each byte is different - this way the result will not contain patterns. For example, if you encrypt English text with a key containing just one repeated byte, I might notice that the cipher-text contains one byte repeated multiple times. This is probably the letter 'e' in your plain-text, the most popular vowel. If the key contained completely random bytes, then any pattern spotted in the cipher-text would not help me identify the plain-text.

So, is a msg of 'Feet' and key of 'abcd' strong? Well, it's certainly stronger than using a key of '0000', but it could be stronger. The attacker might assume that you used a simple key, containing just lower-case letters. This means to brute force this key, the attacker needs to try 26 ^ 8 possible options. This can be done in less than a second on modern computers. A better key would incorporate upper-case letters, digits, punctuation and other characters. An even better key would include non-printable characters as well, for example: $key = chr(27) . chr(6) . 'q.';

Another interesting element to consider with this algorithm is that it requires the key to be of equal length to the msg. This means to strongly encrypt a large amount of text (such as a novel) requires a key that's completely random that's also as long as the novel. Most mainstream algorithms avoid this requirement by encrypting the message in blocks. There are many different ways to implement block encoding, let me illustrate one known as cipher-block-chaining (CBC).

Simple CBC works by taking the first few bytes of the plain-text, XOR'ing it with the key, which generates the first few bytes of the cipher-text. The next few bytes of the plain-text are encrypted by XOR'ing them with the first few bytes of the cipher-text AND the key. This process repeats until all plain-text is encrypted. This creates a chain, where each block in the cipher text has been created using the prior block and key. To decrypt the last result, you must XOR the cipher-text with the previous cipher-text block and then again with the key.

Strong algorithms incorporate other features to ensure the cipher-text is as random as possible, including features that allow you to determine if an encrypted message has been modified. A good place to read more about block cipher modes is Wikipedia: http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation

The Cryptography page also has a great set of introductory information on different forms of encryption and the process of Cryptanalysis. http://en.wikipedia.org/wiki/Cryptography

Thanks a lot for this extensive answer, you really explained all of it to me very well! (though I had to read it a few times before fully understanding it)

score 1 · Accepted Answer · 2012-01-06 21:01:29Z

1

Right now, the hardest part of "decrypting" a string is figuring out how long the input was. If we take that as an additional parameter, we can nearly decrypt it like this:

function decrypt($cipher, $messagelen, $key) {
    if($messagelen % 2) { $messagelen++; }
    $x = substr($cipher, -$messagelen + 2);
    $y = substr($x, 0, strlen($key) - 1) ^ substr($key, 1);
    $z = substr($x, strlen($key) - 1);
    return $y . $z; 
}

This is made much easier because most of the message appears in the clear at the end of the ciphertext. Oops. The only characters in that repetition which are "encrypted" are the first few, which are just XORed with the key.

The middle two characters are irretrievably lost due to an off-by-one error in encryption. Notes on how to fix this are in my comments below.

edited Jan 6, 2012 at 21:01

answered Jan 6, 2012 at 17:05

user149341

4 Comments

Jeroen Over a year ago

Great! I wonder however how you got to this, would you mind explaining this? If you could also help me fix the two missing characters in the encryption, I will throw in a 100 point bounty :)

user149341 Over a year ago

To fix encryption: change the >= in the conditional for "Stop when it crosses half the length" to >. To decrypt the result, change -$messagelen + 2 (on line 3 of my function) to simply $messagelen.

Jeroen Over a year ago

Thanks, it works perfectly! As for the explanation, I completely understand how your code works, I just would like to know how you got to it?

user149341 Over a year ago

Trial and error. The fact that most of the message was available in cleartext (at the end of the encrypt output) helped a lot.

Collectives™ on Stack Overflow

PHP: XOR cypher decryption function doesnt work

2 Answers 2

1 Comment

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related