Shared Secret Algorithms

Phrase Substitution

Throughout the centuries, leaders of large military forces have shared a common problem: how to direct troops and subordinates from long distances without risking that if the message courier is captured by the enemy, their plans are revealed. Even today, with advanced computerized encryption and instantaneous satellite communication, army soldiers will refer to targets and resources by code names or false labels so that only friendly forces will understand the message correctly: "Meet me at the disco when the frog jumps" might mean "Start the attack when the sun rises."

Implementing a phrase-substitution algorithm in PHP is as simple as creating an array to hold the code phrases and calling str_replace() to perform the substitution:

<?php
  $codebook = array(
    'start the attack' => 'meet me at the disco',
    'sun' => 'frog',
    'rises' => 'jumps'
  );
  $message = 'Start the attack when the sun rises.';
  $encoded_message = str_ireplace(array_keys($codebook), array_values($codebook),
                                  $message);
  $decoded_message = str_ireplace(array_values($codebook), array_keys($codebook),
                                  $encoded_message);
?>

In the preceding example, we've defined a set of words or phrases that will be translated by our substitution algorithm in $codebook. Ordinarily we'd expect $codebook to be a much larger dictionary, but for this example these few should be enough.

$encoded_message = str_ireplace(array_keys($codebook), array_values($codebook),
                                $message);

In our first call to str_ireplace() we're using the keys of our codebook as the search values and their corresponding values as the replacements.

$decoded_message = str_ireplace(array_values($codebook), array_keys($codebook),
                                $encoded_message);

In our second call to str_irepace() we're reversing the process by using the values of the codebook as search terms and the keys of the codebook as the replacement values. Because we're using the same codebook and the same operation (albeit in a different order) for both the encryption and decryption phases, we'd call this a shared secret encryption method.

Character Substitution

Although phrase substitution is handy for speaking in code, it's mechanically ill-suited to computer-based cryptography because of some fundamental principles of language. First off, not only must a massive translation dictionary be maintained by both parties, but factors such as pluralization and dialect localization have to be taken into account, causing the size and complexity of the dictionary to grow even larger when placed in a computational context. A much simpler substitution dictionary for a computer to understand is one that operates only on single characters. For single-byte encodings, that means no more than 256 possible search/replace pairs; further, if we concern ourselves only with translating English word characters with no concern for case, we're reduced to only 26 search/replace pairs.

PHP provides a faster and simpler replacement function for single-character substitutions such as this. Let's take a quick look at an encryption algorithm for making a message look like it was touch-typed on a Dvorak keyboard.

<?php
  $qwerty = 'qwertyuiopasdfghjklzxcvbnm' . 'QWERTYUIOPASDFGHJKLZXCVBNM';
  $dvorak = 'abcdefghijklmnopqrstuvwxyz' . 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  $message = "Start the attack when the sun rises.";
  $encoded = strtr($message, $qwerty, $dvorak);
  $decoded = strtr($encoded, $dvorak, $qwerty);
?>

As with our phrase substitution algorithm, we start by defining a translation dictionary. The way strtr() works, the first character in the source map (the first parameter to strtr()), will map to the first character in the destination map (the second parameter to strtr()).

$encoded = strtr($message, $qwerty, $dvorak);

In our first call, the characters in $message get remapped to "Lekde epc keekvr bpcy epc lgy dhlcl". Notice that the spaces and period were not remapped and appear in their original form. The next call to strtr() maps the message back to its original form.

Taking It Further

Perhaps, for one reason or another, we don't want to keep track of a substitution alphabet, what other types of simple character substitution options are open to us? We might decide to implement a phase shift substitution: Advance the ordinal value of every character by one or more to encrypt, and decrease it back down to decrypt. We also might try applying a bitmask to our original text through the XOR operator, once to encrypt, twice to decrypt. Try out a few ideas on your own and see what you come up with.

NOTE The most important thing to bear in mind about the algorithms mentioned thus far is that they are not generally considered to be secure. In fact, they are so easy to crack that many puzzle books include encrypted messages as games for children to solve.

Stronger Encryption Algorithms

PHP includes an extension that wraps the popular Mcrypt library and provides the programmer with access to several moderate-strength shared key-encryption algorithms, including DES, Triple DES, Blowfish, 3-WAY, SAFER-SK64, SAFER-SK128, TWOFISH, TEA, RC2, GHOST, RC6, and IDEA. Mcrypt also supports a pluggable encryption system that allows new encryption algorithms to be added without having to recompile mcrypt or PHP. The underlying implementation of each algorithm differs, but the scripting interfaces from PHP are all alike. Let's look at an example:

<?php
$plaintext = "The crow flies at midnight";
$password = "enigma";
$iv_size = mcrypt_get_iv_size(MCRYPT_BLOWFISH, MCRYPT_MODE_ECB);
srand();
$iv = mcrypt_create_iv($iv_size, MCRYPT_RAND);
$ciphertext = mcrypt_encrypt(MCRYPT_BLOWFISH, $password, $plaintext,
                             MCRYPT_MODE_ECB, $iv);
file_put_contents('secret_message.txt', $iv . $ciphertext);
?>

In the preceding code block, we're encrypting a small chunk of data ($plaintext) into $ciphertext using the Blowfish algorithm and a secret password of "enigma." $iv represents the initial value used to seed the encryption algorithm and is populated with random data.

<?php
$messagedata = file_get_contents('secret_message.txt');
$iv_size = mcrypt_get_iv_size(MCRYPT_BLOWFISH, MCRYPT_MODE_ECB);
$iv = substr($messagedata, 0, $iv_size);
$ciphertext = substr($messagedata, $iv_size);
$password = "enigma";
$plaintext = mcrypt_decrypt(MCRYPT_BLOWFISH, $password, $ciphertext,
                            MCRYPT_MODE_ECB, $iv);
?>

Here we read the initial value and encrypted text back from the file and pair it with our secret password to recover our plain text. Depending on your implementation, you may choose to make $iv a constant string, a hash based on the passphrase, or just include it inline with the encrypted data, as shown. No method is significantly more or less secure than the other so long as the passphrase is kept secret. If the initial value is not provided, PHP will assume an initial value of zero. Although this is technically as secure as any other initial value, it has the drawback of being the first combination tried by most strongarm attacks and thus, in practice, becomes less secure than providing a sufficiently randomized initial value.

In the preceding example, we specified a built-in cipher by using one of the predefined constants. Mcrypt also supports dynamically loaded ciphers by way of the Mcrypt generic API. Let's try the same example again, this time using Mcrypt generic:

<?php
$plaintext = "The crow flies at midnight";
$password = "enigma";
$cipher = mcrypt_module_open('blowfish', '', 'ecb', '');
$iv_size = mcrypt_enc_get_iv_size($cipher);
srand();
$iv = mcrypt_create_iv($iv_size, MCRYPT_RAND);
mcrypt_generic_init($cipher, $password, $iv);
$ciphertext = mcrypt_generic($cipher, $plaintext);
mcrypt_generic_deinit($cipher);
mcrypt_module_close($cipher);
file_put_contents('secret_message.txt', $iv . $ciphertext);
?>

In this version we've accomplished the same goals; however, we've loaded a dynamic cipher algorithm ('blowfish') and mode ('ecb') from the directories pointed to by the php.ini enTRies mcrypt.algorithms_dir and mcrypt.modes_dir, respectively. If we had a special algorithm cipher and encryption mode located in an alternative directory, we could have specified those directories in the second and fourth parameters.

$cipher = mcrypt_module_open('mycipher', '/home/jdoe/ciphers/', 'mymode',
                             '/home/jdoe/mcrypt-modes/');

Decrypting using this alternative API also parallels the first version with only minor differences:

<?php
$messagedata = file_get_contents('secret_message.txt');
$cipher = mcrypt_module_open('blowfish', '', 'ecb', '');
$iv_size = mcrypt_enc_get_iv_size($cipher);
$iv = substr($messagedata, 0, $iv_size);
$ciphertext = substr($messagedata, $iv_size);
$password = "enigma";
mcrypt_generic_init($cipher, $password, $iv);
$plaintext = mdecrypt_generic($cipher, $ciphertext);
mcrypt_generic_deinit($cipher);
mcrypt_module_close($cipher);
? >