I promised you an update to CDX-1, the first implementation of the CDX encryption algorithm, and here it is.
This version is considerably faster (about 16 times faster than CDX-1) and uses S-boxes to enhance security. The S-boxes need a lot more work, but they're better in than out.
Please note that you should not rely on CDX-2 for securing important data. This program is merely illustrative, and I make no great claims for it. Having said that, it hasn't been cracked yet (unless GCHQ or the NSA were feeling particularly bored recently). If you want true security, use a more widely published algorithm. I recommend TwoFish, which claims to be patent-free, and which will probably win the competition to succeed DES. You can find out more about TwoFish here - it's received considerable public scrutiny and, so far, has defeated all known attempts to crack it. (The NSA and/or GCHQ may have cracked it - who knows?)
The above paragraph may be a bit of a let-down, if you were expecting this algorithm to be "unbreakable". I have news for you. Unbreakable algorithms don't exist (except for a correctly-used One Time Pad, which is impractical in large-scale encryption applications). Some people claim their algorithms are unbreakable; and they don't publish those algorithms. (If their algorithms are truly unbreakable, what are they scared of?) Or they do publish the algorithms, only to find that those algorithms are cracked within a week. Or a day. I myself have cracked one unbreakable algorithm within two hours, and another within six hours, despite laying no claims to expertise in cryptanalysis. The best you can hope for is an algorithm which (a) places all the security in the key and (b) cannot be attacked by any method short of brute force. I don't know of any attacks for CDX-2, which is one of the reasons I've published it. If there are such attacks, I want to know about them, and showing the world my algorithm really is the best way to do this, counter-intuitive as it may seem. Much of cryptology is counter-intuitive (sigh).
Now, whilst I don't know of any attacks on CDX-2, I do know of one possible attack. If all the bytes in the plaintext are the same, the ciphertext displays considerable regularity. I don't know how much of a weakness this is, since in "real life", people don't encode this kind of plaintext. Still, it's a possible weakness, which is why I mention it here.
Update 27 November 2003: For details of the CDX-2 challenge, follow this link.
This program comprises two source files. One contains the expression in ANSI C code of the algorithm itself, and the other contains the S-boxes. The S-box source file is around 140 kilobytes in size(!), so it's not displayed here. (It's just loads of numbers anyway.) But you can download it from here together with the other two files you need.
You're about to see two source files. The first is not part of the encryption program itself, but is a preliminary step in the build process. I've already performed this step for you, but you can do it yourself if you like. You should be aware, however, that the decryption process must use exactly the same S-boxes as the encryption process! Running "sbgen" re-creates sb.c with completely new S-boxes each time. So you'll either want to use the existing sb.c (for compatibility with everyone else using the same S-boxes) or generate a new sb.c to provide you with your own personal encryption algorithm. Note: don't rely on your own S-boxes for security. You should assume that an adversary has access to your source code!
One further note about S-boxes: CDX-2 uses randomly generated S-boxes, with no selection at all. This is not a good thing. Decent S-boxes are a bit cleverer than that. When I fully understand the clever bit, I'll incorporate it (presumably into CDX-3!). Until then, these will do.
The other file you'll see contains the encryption code itself. But first, the S-box generator:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#define DEFAULT_NUM_BOXES 8
#define MAX_BOXES 256
int main(int argc, char **argv)
{
unsigned int i;
unsigned int temp;
unsigned int j;
unsigned int S_box[UCHAR_MAX + 1];
unsigned int S_box_reverse[UCHAR_MAX + 1];
int box = 0;
unsigned int seed = 0;
int numboxes = DEFAULT_NUM_BOXES;
if(argc > 1)
{
numboxes = atoi(argv[1]);
if(numboxes <= 0 || numboxes > MAX_BOXES)
numboxes = DEFAULT_NUM_BOXES;
}
seed = (unsigned)time(NULL);
srand(seed);
printf("#include <limits.h>\n\n");
printf("#include <assert.h>\n\n");
printf("int GetSBoxCount(void)\n");
printf("{\n return %d;\n}\n\n", numboxes);
printf("unsigned char Subst(int box, unsigned char ch)\n{\n");
printf(" static unsigned int S_box[%d][UCHAR_MAX + 1] =\n {\n", numboxes);
for(box = 0; box < numboxes; box++)
{
/* initialise box */
for(i = 0; i <= UCHAR_MAX; i++)
{
S_box[i] = i;
}
/* shuffle box */
for(i = 0; i <= UCHAR_MAX; i++)
{
j = (unsigned int)((UCHAR_MAX + 1) * (rand() / ((double)RAND_MAX + 1.0)));
temp = S_box[i];
S_box[i] = S_box[j];
S_box[j] = temp;
}
/* calculate reverse of sbox */
for(i = 0; i <= UCHAR_MAX; i++)
{
S_box_reverse[S_box[i]] = i;
}
printf(" {\n ");
for(i = 0; i < UCHAR_MAX; i++)
{
printf(" %3d,", S_box[i]);
if(i % 8 == 7)
{
printf("\n ");
}
}
printf(" %3d\n }%s\n", S_box[i], box == numboxes - 1 ? "" : ",");
}
printf(" };\n");
printf("\n assert(box >= 0 && box < GetSBoxCount());\n");
printf("\n return S_box[box][ch];\n}\n\n");
srand(seed);
printf("unsigned char UnSubst(int box, unsigned char ch)\n{\n");
printf(" static unsigned int S_box_reverse[%d][UCHAR_MAX + 1] =\n {\n", numboxes);
for(box = 0; box < numboxes; box++)
{
/* initialise box */
for(i = 0; i <= UCHAR_MAX; i++)
{
S_box[i] = i;
}
/* shuffle box */
for(i = 0; i <= UCHAR_MAX; i++)
{
j = (unsigned int)((UCHAR_MAX + 1) * (rand() / ((double)RAND_MAX + 1.0)));
temp = S_box[i];
S_box[i] = S_box[j];
S_box[j] = temp;
}
/* calculate reverse of sbox */
for(i = 0; i <= UCHAR_MAX; i++)
{
S_box_reverse[S_box[i]] = i;
}
printf(" {\n ");
for(i = 0; i < UCHAR_MAX; i++)
{
printf(" %3d,", S_box_reverse[i]);
if(i % 8 == 7)
{
printf("\n ");
}
}
printf(" %3d\n }%s\n", S_box_reverse[i], box == numboxes - 1 ? "" : ",");
}
printf(" };\n\n assert(box >= 0 && box < GetSBoxCount());\n return S_box_reverse[box][ch];\n}\n\n");
return 0;
}
Once you've run this program (or just unzipped sb.c if you prefer), you are in a position to compile cdx2.c - I've not included a makefile because I don't know what operating system or compiler you're using, but it's easy enough to build cdx2 - just compile cdx2.c and sb.c, then link them together. If you're using Linux:
gcc -W -Wall -O2 -ansi -pedantic -o cdx cdx2.c sb.c
Borland compiler:
bcc32 -A cdx2.c sb.c
And without further ado, here's CDX-2 itself:
/*
CDX-2
---- A l g o r i t h m D e t a i l s ------
Here's a summary of the encryption algorithm:
Generate a block of 256 integers, each containing a different
prime number. (Actually, they don't need to be prime, but most
of them should at least be odd, and greater than 50 on average).
Read the plaintext P into a buffer PB.
Read the key K into a buffer KB.
For each byte in the key
Replace each byte in the plaintext with its corresponding S-box value,
each time using the next unused S-box (and starting over when you
run out).
Locate the prime number PN corresponding to this byte of the key
Rotate all the bits in the plaintext by PN bits (left)
For each byte B in the buffer PB
P[B] = P[B] ^ K[B % length(KB)]
roF
roF
Write the plaintext, which is now really ciphertext, to the output file.
The decryption process is of course the reverse. For bit rotation
purposes, the key is read starting at the back.
Complete C source code is provided, which should be taken as
definitive. The text description above is a simple and thus
perhaps inaccurate guide to the algorithm.
*/
/********** Source code starts here ***************/
/*
* cdx2.c
*
* Cryptographic algorithm copyright 1999-2004 Richard Heathfield
*
* Source code copyright 1999-2004 Richard Heathfield
*
* All rights reserved.
*
* You are hereby granted permission to copy this file onto
* one computer only, for the purposes of study and compilation
* and for no other purpose of any kind whatsoever. You are
* not granted permission to amend this source code in any way.
* You may not give copies of this file away, and you may not
* sell copies of this file.
*
* Description:
* This program implements the CDX-2 encryption algorithm.
* (CDX-0 was an internal algorithm which has been discarded
* for being insecure. CDX-1 just sucked.)
*
* Usage:
* Encryption:
* enc plaintextfile ciphertextfile keyfile
* Decryption:
* enc ciphertextfile plaintextfile keyfile -d
*
* Assumptions:
* I'm not sure how this program would fare with sizeof(int) < 4
*
* Portability:
* Code tested on Microsoft Visual C++ 5.0 Pro, Borland C++ 5.02,
* and Delorie C (gcc), all under Windows 95 DOS box.
* Also under Linux/GNU gcc.
*
* I see no reason why it shouldn't work under any platform or
* operating system. If you have problems, let me know the circumstances
* (which OS (name and version), which compiler (name and version)). Thanks.
*
* Credits:
* Bryan Williams (speed!)
* Mathew Watson (debugging!)
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define RETAINMASK(n) ((UCHAR_MAX & ~((unsigned char)0)) >> (n))
#define TOPMASK(n) (~RETAINMASK(n))
#define LOWMASK(n) (~((UCHAR_MAX & ~0) << (n)))
extern unsigned char Subst(int, unsigned char);
extern unsigned char UnSubst(int, unsigned char);
extern int GetSBoxCount(void);
int GetFileLength(FILE *fp)
{
int len = 0;
rewind(fp);
while(fgetc(fp) != EOF)
{
len++;
}
rewind(fp);
return len;
}
void XORBuffer(unsigned char *buffer, int DataLen, unsigned char *Key, int KeyLen)
{
int i;
for(i = 0; i < DataLen; i++)
{
buffer[i] ^= Key[i % KeyLen];
}
}
void RotateBufferLeft(unsigned char *buffer, size_t size, int n, unsigned char *spare)
{
int i;
size_t numbytes;
int numbits;
unsigned char carriedforward = 0;
unsigned char broughtforward = 0;
unsigned char topmask = 0;
n %= (size * CHAR_BIT);
numbytes = n / CHAR_BIT;
memcpy(spare, buffer, numbytes);
memmove(buffer, buffer + numbytes, size - numbytes);
memcpy(buffer + size - numbytes, spare, numbytes);
numbits = n % CHAR_BIT;
topmask = TOPMASK(numbits);
/* erm, get the one mad carry to begin with */
carriedforward = (buffer[0] & topmask) >> (CHAR_BIT - numbits);
for(i = size - 1; i >= 0; --i)
{
/* 1) Store top numbits bits */
broughtforward = (buffer[i] & topmask) >> (CHAR_BIT - numbits);
/* 2) Shift other bits by numbits */
buffer[i] <<= numbits;
/* 3) and in the previously shifted numbits from byte beforehand */
buffer[i] |= carriedforward;
/* 4) carry forward */
carriedforward = broughtforward;
}
}
void RotateBufferRight(unsigned char *buffer, size_t size, int n, unsigned char *spare)
{
size_t i;
size_t numbytes;
int numbits;
unsigned char carriedforward = 0;
unsigned char broughtforward = 0;
unsigned char lowmask = 0;
n %= (size * CHAR_BIT);
numbytes = n / CHAR_BIT;
memcpy(spare, buffer + size - numbytes, numbytes);
memmove(buffer + numbytes, buffer, size - numbytes);
memcpy(buffer, spare, numbytes);
numbits = n % CHAR_BIT;
lowmask = LOWMASK(numbits);
/* erm, get the one mad carry to begin with */
carriedforward = (buffer[size - 1] & lowmask) << (CHAR_BIT - numbits);
for(i = 0; i < size; ++i)
{
/* 1) Store top numbits bits */
broughtforward = (buffer[i] & lowmask) << (CHAR_BIT - numbits);
/* 2) Shift other bits by numbits */
buffer[i] >>= numbits;
/* 3) and in the previously shifted numbits from byte beforehand */
buffer[i] |= carriedforward;
/* 4) carry forward */
carriedforward = broughtforward;
}
}
void Help(char *s)
{
if(!s || *s == 0)
s = "enc";
printf("Usage:\n");
printf("%s inputfile outputfile keyfile [-d]\n", s);
printf("-d specifies decryption\n");
}
unsigned char *GetPass(char *Filename, unsigned int *n)
{
unsigned char *buff = NULL;
FILE *fp;
fp = fopen(Filename, "rb");
if(fp != NULL)
{
*n = (unsigned int)GetFileLength(fp);
buff = malloc(*n);
if(buff != NULL)
{
if(!fread(buff, *n, 1, fp))
{
printf("Read error on key.\n");
exit(EXIT_FAILURE);
}
}
else
{
printf("Memory error - key too big.\n");
}
fclose(fp);
}
return buff;
}
int CheckArgs(int argc, char *argv[])
{
if(argc < 4)
{
Help(argv[0]);
return 0;
}
if(argc > 4 && strcmp(argv[4], "-d"))
{
printf("Syntax error.\n");
return 0;
}
return 1;
}
int encrypt(char *infile, char *outfile, char *keyfile, int decrypt)
{
static unsigned int PN_BLOCK[] =
{
2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89,
97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223,
227, 229, 233, 239, 241, 251, 257, 263,
269, 271, 277, 281, 283, 293, 307, 311,
313, 317, 331, 337, 347, 349, 353, 359,
367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457,
461, 463, 467, 479, 487, 491, 499, 503,
509, 521, 523, 541, 547, 557, 563, 569,
571, 577, 587, 593, 599, 601, 607, 613,
617, 619, 631, 641, 643, 647, 653, 659,
661, 673, 677, 683, 691, 701, 709, 719,
727, 733, 739, 743, 751, 757, 761, 769,
773, 787, 797, 809, 811, 821, 823, 827,
829, 839, 853, 857, 859, 863, 877, 881,
883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997,
1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,
1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459,
1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571,
1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619
};
unsigned char *Spare = NULL;
unsigned char *Key = NULL;
unsigned int KeyLen = 0;
FILE *fpIn = NULL;
FILE *fpOut = NULL;
int DataLen = 0;
unsigned char *buffer = NULL;
int i = 0;
int j = 0;
int numboxes = 0;
int box = 0;
numboxes = GetSBoxCount();
fpIn = fopen(infile, "rb");
if(fpIn == NULL)
{
printf("Can't open input file.\n");
return EXIT_FAILURE;
}
fpOut = fopen(outfile, "wb");
if(fpOut == NULL)
{
fclose(fpIn);
printf("Can't open output file.\n");
return EXIT_FAILURE;
}
DataLen = GetFileLength(fpIn);
buffer = malloc(DataLen);
if(buffer == NULL)
{
fclose(fpIn), fclose(fpOut);
printf("Insufficient memory.\n");
return EXIT_FAILURE;
}
Spare = malloc(DataLen);
if(NULL == Spare)
{
free(buffer);
fclose(fpIn), fclose(fpOut);
printf("Insufficient memory.\n");
return EXIT_FAILURE;
}
if(fread(buffer, DataLen, 1, fpIn) != 1)
{
fclose(fpIn), fclose(fpOut), free(buffer), free(Spare);
printf("Read error.\n");
return EXIT_FAILURE;
}
Key = GetPass(keyfile, &KeyLen);
if(Key == NULL)
{
fclose(fpIn), fclose(fpOut), free(buffer), free(Spare);
printf("Key error.\n");
return EXIT_FAILURE;
}
printf("\nProcessing");
fflush(stdout);
if(decrypt)
{
for(i = 0; i < (int)KeyLen; i++)
{
box = (KeyLen - i - 1) % numboxes;
printf(".");
fflush(stdout);
XORBuffer(buffer, DataLen, Key, KeyLen);
RotateBufferRight(buffer, DataLen, PN_BLOCK[Key[KeyLen - (i + 1)]], Spare);
for(j = 0; j < DataLen; j++)
{
buffer[j] = UnSubst(box, buffer[j]);
}
}
}
else
{
for(i = 0; i < (int)KeyLen; i++)
{
box = i % numboxes;
printf(".");
fflush(stdout);
for(j = 0; j < DataLen; j++)
{
buffer[j] = Subst(box, buffer[j]);
}
RotateBufferLeft(buffer, DataLen, PN_BLOCK[Key[i]], Spare);
XORBuffer(buffer, DataLen, Key, KeyLen);
}
}
if(fwrite(buffer, DataLen, 1, fpOut) != 1)
{
printf("Write error.\n");
}
fclose(fpIn), fclose(fpOut), free(buffer), free(Spare);
return EXIT_SUCCESS;
}
int main(int argc, char *argv[])
{
int rc;
int decrypt = 0;
if(!CheckArgs(argc, argv))
{
rc = EXIT_FAILURE;
}
else
{
if(argc > 4 && strcmp(argv[4], "-d") == 0)
{
decrypt = 1;
}
rc = encrypt(argv[1], argv[2], argv[3], decrypt);
}
printf("\n");
return rc;
}