Bob is the president of MicroFirm, a company specializing in utilities for small computers. He can be reached at P.O. Box 428, Alief, TX 77411.
Although not a new topic, surprisingly little has been done to secure data in the micro-computer world. The problem is that most encryption systems were developed for high-powered mainframe and super computers that can handle the computationally intensive calculations required for such encryption schemes. Most small computers, on the other hand, cannot reasonably implement algorithms set forth by agencies such as the U.S. National Bureau of Standards.
On the upside, however, most small computer users don't need the heavy security required by such government agencies. And while simple encryption schemes can be easily broken, there is a way to get the best of both worlds. This article presents a new algorithm to ease the production of secure data systems. Although written in ANSI C, the algorithm as presented is adaptable to most high-level languages, assembly, and even hardware implementations. Although usable "as-is," it can also be used as a building block for enhanced security applications.
A typical data encryption system consists of three basic elements: The unencrypted data, referred to as the "plaintext;" an encryption key; and an encryption method (the encryption engine).
The output of the encryption process is called the "ciphertext." Decryption uses three corresponding elements, except that the input is the ciphertext and the output is the reconstructed plaintext.
"Cryptanalysis" is the science of breaking ciphers based on searching for specific patterns in the ciphertext. If the plaintext is unknown, the patterns represent a best guess as to the partial contents of the plaintext. Even better is a known plaintext attack where a known message has been encrypted so both the plaintext and the ciphertext are known.
Most common small computer data encryption schemes are based on either the exclusive ORing of a given text string key with the plaintext (a polyalphabetic substitution cipher as shown in Figure 1), or a software implementation of the Data Encryption Standard (DES) as published by the U.S. National Bureau of Standards. The former is not particularly secure, while the DES is computationally intensive. The exclusive OR method would be perfectly secure if the key were longer than the plaintext (called a "one-time" key) and if the key were perfectly random.
/**********************************************************************/
/* Simple encrypt/decrypt function using exclusive-ORing */
/* NOTE: This is included for demonstration only! Data encrypted */
/* with this code will be subject to simple cryptanalysis. */
/**********************************************************************/
char *cryptext; /* The encryption/decryption key */
void crypt(char *buf)
{
int crypt_ptr = 0;/* Circular pointer to elements of key */
*buf ^= cryptext[crypt_ptr];
if (++crypt_ptr >= strlen(cryptext))
crypt_ptr = 0;
}
Despite the high-tech appeal of DES and public key encryption systems, these systems were developed both in response to, and dependent upon, the general availability of powerful specialized hardware. Keys are typically large numbers and are difficult to memorize. DES requires 16 iterations of nested substitution and permutation ciphers. RSA public key systems involve raising 200 digit numbers to 200 digit powers. Most PC users simply want a secure means of quickly making files unreadable by unauthorized personnel.
The S-CODER algorithm is the core of an encryption "engine" (an S-Box, or substitution cipher module), which is a variant of the exclusive OR method. It differs primarily in that it "scrambles"the key on-the-fly (characteristic of a stream cipher) to approach the security level of using a one-time random key. The complete algorithm is implemented in Figure 2.
/*******************************************************************/
/* S-CODER -- Encrypt/decrypt data */
/* Copyright 1987 - 1989 by Robert B. Stout dba MicroFirm */
/* Originally written by Bob Stout with modifications */
/* suggested by Mike Smedley. */
/* This code may be used freely in any program for any */
/* application, personal or commercial. */
/* Current commercial availability: */
/* 1. MicroFirm Toolkit ver 3.00: LYNX and CRYPT utilities */
/* 2. CXL libraries (MSC, TC, ZTC/C++, PC):fcrypt( ) */
/* dedicated file encryption function */
/* 3. SMTC & MFLZ libraries: crypt( ) function */
/*******************************************************************/
char*cryptext; /* The actual encryption/decryption key */
int crypt_ptr = 0; /* Circular pointer to elements of key */
int crypt_lenght; /* Set externally to strlen (cryptext) */
/* NOTES: cryptext should be set and qualified (to something over
5 - 6 chars, minimum) by the calling program, which should
also set crypt_ptr in the range of 0 to strlen (cryptext)
before each use. If crypt( ) is used to encrypt several
buffers, cryptext should be reloaded and crypt_ptr
reset before each buffer is encrypted. The encryption is both
reversible -- to decrypt data, pass it back through crypt( )
using the original key and original initial value of
crypt_ptr -- and multiple passes are commutative.*/
/**** Encrypt/decrypt buffer datum******************************/
void crypt(char *buf)
{
*buf ^= cryptext[crypt_ptr] ^ (cryptext[0] * crypt_ptr);
cryptext[crypt_ptr] += ((crypt_ptr < (crypt_length - 1))?
cryptext[crypt_ptr + 1]: cryptext[0]);
if (!cryptext[crypt_ptr])
cryptext[crypt_ptr] += 1;
if (++crypt_ptr >= crypt_length)
crypt_ptr = 0;
}
To remain secure from known plaintext attacks and minimize the impact of poorly selected keys, the exclusive OR product is sufficiently complex to thoroughly hide the encryption key, even when encrypting strings of identical characters. By modifying the key according to known rules, the key effectively becomes an array of seed values for a complex random number generator. It is these random numbers, rather than the key text itself, which are exclusive ORed with the plaintext.
S-CODER requires that three global variables are set up by the calling program. The encryption key goes in cryptext, an index into the key goes into crypt_ptr, and the length of the key is set in crypt_length. Although crypt_ptr is usually set to point to the first character of the key, this may be changed in more secure S-CODER applications. The only reason for passing crypt_length in a variable is to avoid repetitively calling the strlen( ) library function. An important point to note is that because the key is scrambled during encryption, to encrypt multiple texts using the same key requires the unaltered key to be reloaded into cryptext before each use, and that crypt_ptr be preset to its initial value.
In examining the S-CODER code, note that both the plaintext and the key are masked by including the exclusive OR of the product of crypt_ptr (changes each character) with the first character of the key (changes each pass). Because the length of the key is unknown and the product is implicitly modulo 256, this simple scheme renders crypt-analysis extremely difficult by searching for key-length cycles. This is especially true if we further assume that crypt_ptr may be preset to some random starting point within the key.
As each character of the key is used, it is modified by summing it with the character, which is logically to its right, thus treating the key data as a circular buffer. Again, this is implicitly a modulo 256 operation. Because the unique character zero or NULL is reserved in C to denote the end of a string, zeros are converted to ones to preserve the key string length and to save the degenerative effects of zero propagation through the mathematical operations on the key.
Listing One (page 110) implements a simple, single file encryption utility using the S-CODER algorithm. For simplicity, crypt_ptr is initialized to zero, and no key qualification or validation is performed. Even this simple application has proven resistant to unknown plaintext attacks.
Listing Two (page 110) demonstrates the use of the S-CODER algorithm as a stream (stdin to stdout) encryptor. It includes a call to a setraw( ) function, which will be different for different compilers. This is necessary to force the stdin and stdout streams into "raw"or binary mode for the duration of the program's execution. Listing Three (page 110) demonstrates a simple setraw( ) function for the Zortech C and C++ compilers. Microsoft and Turbo C users may use the setraw( ) function in their compilers.
Listing Four (page 110) demonstrates a more secure implementation and introduces a cryptqual( ) function to assure that the encryption key contains at least six distinct characters. The S-CODER engine is embedded in an encryption algorithm, where data are read into and out of a 16K data buffer as linear arrays but encrypted as two-dimensional 128 x 128 columnar character arrays with random padding of the final buffer (a modified 16K block transposition cipher).
Also note that crypt_ptr is preset to a computed value rather than the default of zero. This computed value includes the length of the encrypted file, which is written along with the ciphertext. Although the S-CODER algorithm effectively masks the key length, these techniques serve to eliminate residual weaknesses when faced with a known plaintext attack. Using the basic S-CODER engine as a building block, this example suggests some ways to build more secure specific applications.
Listing Five (page 111) shows a simple test program to calculate statistics on test files. The coefficient of variation of these examples asymptotically approaches zero as the size of the file increases. For 100K test files, it has typically been down around five percent.
There are several important issues that S-CODER doesn't address. Key distribution is a historical problem for any encryption scheme. Public key encryption and key-sharing schemes address this issue, but at the expense of hard to memorize keys, authentication problems, and computational complexity. S-CODER's operation is symmetrical and also commutative when used with multiple keys. For example, if data are doubly encrypted with separate keys, the resulting ciphertext may be decrypted by passing it through an S-CODER engine using the original keys in any order. This suggests the use of a hierarchical key distribution scheme.
No data encryption system is unbreakable. But it's important to remember that, for hundreds of years, there have existed relatively simple ciphers, which couldn't routinely be broken before the invention of supercomputers. If your adversaries can't afford anything more powerful than a 80386-based PC, your data would probably be safe with any of these methods. Also, in the world of industrial espionage, it's usually cheaper for an adversary to buy your employees than the computing power to crack your data when encrypted with tools such as S-CODER.
The real purpose of encryption is to make cryptanalysis prohibitively expensive, either in terms of cost or time. A further fact of life is that any encryption process that runs acceptably fast on a small computer is vulnerable to crypt-analysis on much larger and faster machines. The S-CODER algorithm is an effective compromise -- easy to use, reasonably fast on small machines, yet offering effective levels of data security.
Computer Networks by Andrew S. Tannenbaum, ISBN 0-13-162959-X, Prentice Hall.
An Introduction to Cryptology by Henk C.A. van Tilborg, ISBN 0-89838-271-8, Kluwer Academic Publishers.
Security in Computing by Charles P. Pfleeger, ISBN 0-13-798943-1, Prentice Hall.
_S-CODER FOR DATA ENCRYPTION_
by Robert Stout
[LISTING ONE]
/****************************************************************/
/* Simple encrypt/decrypt function using exclusive-ORing */
/* NOTE: This is included for demonstration only! Data encrypted*/
/* with this code will be subject to simple cryptanalysis. */
/****************************************************************/
char *cryptext; /* The encryption/decryption key */
void crypt(char *buf)
{
int crypt_ptr = 0; /* Circular pointer to elements of key */
*buf ^= cryptext[crypt_ptr];
if (++crypt_ptr >= strlen(cryptext))
crypt_ptr = 0;
}
Figure 2: The S-CODER algorithm
/****************************************************************/
/* S-CODER - Encrypt/decrypt data */
/* Copyright 1987-1989 by Robert B. Stout dba MicroFirm */
/* Originally written by Bob Stout with modifications */
/* suggested by Mike Smedley. */
/* This code may be used freely in any program for any */
/* application, personal or commercial. */
/* Current commercial availability: */
/* 1. MicroFirm Toolkit ver 3.00: LYNX and CRYPT utilities */
/* 2. CXL libraries (MSC, TC, ZTC/C++, PC): fcrypt() */
/* dedicated file encryption function */
/* 3. SMTC & SMZT libraries: crypt() function */
/****************************************************************/
char *cryptext; /* The actual encryption/decryption key */
int crypt_ptr = 0; /* Circular pointer to elements of key */
int crypt_length; /* Set externally to strlen(cryptext) */
/* NOTES: cryptext should be set and qualified (to something over
5-6 chars, minimum) by the calling program, which should
also set crypt_ptr in the range of 0 to strlen(cryptext)
before each use. If crypt() is used to encrypt several
buffers, cryptext should be reloaded and crypt_ptr reset
before each buffer is encrypted. The encryption is both
reversible - to decrypt data, pass it back through crypt()
using the original key and original initial value of
crypt_ptr - and multiple passes are commutative. */
/**** Encrypt/decrypt buffer datum ******************************/
void crypt(char *buf)
{
*buf ^= cryptext[crypt_ptr] ^ (cryptext[0] * crypt_ptr);
cryptext[crypt_ptr] += ((crypt_ptr < (crypt_length - 1)) ?
cryptext[crypt_ptr + 1] : cryptext[0]);
if (!cryptext[crypt_ptr])
cryptext[crypt_ptr] += 1;
if (++crypt_ptr >= crypt_length)
crypt_ptr = 0;
}
/****************************************************************/
/* Simple S-CODER file encryptor/decryptor */
/****************************************************************/
#include <stdio.h>
#include <string.h>
#include <assert.h>
#define BUF_SIZ 32768
extern char *cryptext;
extern int crypt_length;
void crypt(char *);
main(int argc, char *argv[])
{
unsigned i, n;
char *buf, *p;
FILE *infile, *outfile;
if (4 > argc)
{
puts("\aUsage: CRYPT input_file output_file key");
abort();
}
assert(buf = (char *)malloc(BUF_SIZ));
assert(infile = fopen(argv[1], "rb"));
assert(outfile = fopen(argv[2], "wb"));
cryptext = argv[3];
crypt_length = strlen(cryptext);
while (n = fread(buf, 1, BUF_SIZ, infile))
{
p = buf;
for (i = 0; i < n; ++i)
crypt(p++);
fwrite(buf, 1, n, outfile);
}
fclose(infile);
fclose(outfile);
exit(0);
}
[LISTING TWO]
/****************************************************************/
/* Simple S-CODER stream encryptor/decryptor */
/****************************************************************/
#include <stdio.h>
#include <string.h>
#include <assert.h>
extern char *cryptext;
extern int crypt_length;
void crypt(char *);
main(int argc, char *argv[])
{
char cch;
int ich;
FILE *infile;
void setraw(void);
if (2 > argc)
{
puts("\aUsage: SCRYPT key");
puts("encrypts stdin to stdout");
abort();
}
cryptext = argv[1];
crypt_length = strlen(cryptext);
setraw(); /* NOTE: setraw() will be compiler-dependent. It is used
to set stdin and stdout to raw binary mode. This is
necessary to avoid CR/LF translation and to avoid
sensing 0x1a as EOF during decryption. */
while (EOF != (ich = getchar()))
{
cch = (char)ich;
crypt(&cch);
fputc(cch, stdout);
}
exit(0);
}
[LISTING THREE]
/****************************************************************/
/* Zortech C routine to set stin and stdout to binary mode */
/****************************************************************/
#include <stdio.h>
extern FILE _iob[_NFILE];
void setraw(void)
{
_iob[0]._flag &= ~_IOTRAN;
_iob[1]._flag &= ~_IOTRAN;
}
[LISTING FOUR]
/****************************************************************/
/* Enhanced security S-CODER file encryptor/decryptor */
/****************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MIN_KEYL 6
extern char *cryptext;
extern int crypt_length;
void crypt(char *);
int cryptqual(void);
long fsize;
union { /* Transposition cipher buffer */
char in[16384];
char out[128][128];
} buf;
FILE *infile, *outfile;
main(int argc, char *argv[])
{
void encrypt(void);
void decrypt(void);
if (5 > argc || NULL == strchr("EeDd", argv[1][0]))
{
puts("\aUsage: HI-CRYPT { E | D } input_file output_file key");
puts("where: E = Encrypt");
puts(" D = Decrypt");
abort();
}
assert(infile = fopen(argv[2], "rb"));
assert(outfile = fopen(argv[3], "wb"));
cryptext = argv[4];
crypt_length = strlen(cryptext);
if (cryptqual())
{
puts("\aHI-CRYPT: Key is not sufficiently complex");
abort();
}
if (strchr("Ee", argv[1][0]))
encrypt();
else decrypt();
fclose(infile);
fclose(outfile);
exit(0);
}
int cryptqual(void)
{
int i, j = 0;
static char found[MIN_KEYL + 1]; /* Statics initialized to zeros */
if (6 > crypt_length)
return -1;
for (i = 0; i < crypt_length; ++i)
{
if (strchr(found, cryptext[i]))
continue;
found[j++] = cryptext[i];
if ((MIN_KEYL - 1) < j)
return 0;
}
return -1;
}
void encrypt(void)
{
unsigned i, j, n;
fseek(infile, 0L, SEEK_END);
fsize = ftell(infile); /* Save size */
rewind(infile);
fwrite(&fsize, sizeof(long), 1, outfile);
srand((unsigned)fsize);
crypt_ptr = fsize % crypt_length;
while (n = fread(buf.in, 1, 16384, infile))
{
while (16384 > n)
buf.in[n++] = rand();
for (i = 0; i < 128; ++i)
for (j = 0; j < 128; ++j)
crypt(&buf.out[j][i]);
fwrite(buf.in, 1, 16384, outfile);
}
}
void decrypt(void)
{
unsigned i, j, n;
fread(&fsize, sizeof(long), 1, infile);
crypt_ptr = fsize % crypt_length;
while (n = fread(buf.in, 1, 16384, infile)) /* Read size */
{
for (i = 0; i < 128; ++i)
for (j = 0; j < 128; ++j)
crypt(&buf.out[j][i]);
if (16384 <= fsize)
fwrite(buf.in, 1, 16384, outfile);
else fwrite(buf.in, 1, fsize, outfile);
fsize -= n;
}
}
[LISTING FIVE]
/****************************************************************/
/* Collect file statistics */
/****************************************************************/
#include <stdio.h>
#include <math.h>
#include <assert.h>
main(int argc, char *argv[])
{
int i, ch, hist = 0;
long n = 0L;
double mean = 0., stdev = 0., ftmp;
static unsigned bins[256];
FILE *infile;
assert(infile = fopen(argv[1], "rb"));
while (!feof(infile))
{
if (EOF == (ch = fgetc(infile)))
break;
bins[ch] += 1;
++n;
}
fclose(infile);
for (i = 0; i < 256; ++i)
{
mean += (double)(bins[i]);
if (bins[i])
++hist;
}
mean /= 256.;
for (i = 0; i < 256; ++i)
{
ftmp = (double)(bins[i]) - mean;
stdev += (ftmp * ftmp);
}
ftmp = stdev / 255.;
stdev = sqrt(ftmp);
printf("%ld Characters were read from %s\n"
"There are an average of %f occurances of each character\n"
"%d Characters out of 256 possible were used\n"
"The standard deviation is %f\n"
"The coefficient of variation is %f%%\n",
n, argv[1], mean, hist, stdev, (100. * stdev) / mean);
}
Figure 1: A polyalphabetic substitution cipher