Re: Encryption ??

Klas Engwall wrote:
Bill,
After having studied the original paper on TEA by Wheeler and Needham
(http://www.cl.cam.ac.uk/ftp/users/djw3/tea.ps) and looked at a number
of implementations from various places on the web I have noticed that
just about every implementation except O'Dwyer's
(http://www.contrib.andrew.cmu.edu/~ajo/free-software/tea-example.c)
passes exactly eight bytes of source (plus 16 bytes of encryption
key), once, to the encryption function, and that the handling of
longer strings is left for the caller to take care of. Eight bytes is
what the algorithm requires, and when it is done that way the problem
you have observed does not exist. So there is nothing wrong with the
algorithm itself, at least not in this area. It is the implementation
that has a problem.

Klas,
We are in complete agreement on this; the problem is not in the algorithm but in it's implementation. The algorithm expects 64-bit blocks so you must give it 64-bit blocks. I agree that copying 1-7 bytes unencrypted is not wise. I stripped out the memcpy() function in O'Dwyer implementation since it shouldn't be there and is hiding what I was trying to show. I stated, not very clearly, that the algorithm as implemented had a potential buffer overflow problem when it was used correctly i.e. when the text was an exact multiple of 8. Now the stripped version doesn't have the memcpy function to copy any extra bytes.

(As an aside, the memcpy function is the only function that requires the llibce library. Without this funciton, you can compile the routine with Digital Mars C compiler. In an earlier post, I stated that this compiler was not compatible with clipper. I was wrong. I download the 3 MB file and wrote a couple of routines not requiring llibce and they worked in Clipper. It seems to be a good free compiler and much smaller download than djgpp DOS port of the GNU c/c++ compiler. I ran this test using both the Digital Mars compiler and Borland's bcc32 v5.5 and got the same results. The dmc executable was 41,500 and bcc32 was 53,248 but bcc32 is a 32-bit compiler (I don't know if dmc was running in 16 or 32 bit mode). I'm not sure if it can be used when you need library functions. It's incompatible with ms libs.)

I also modifed the test program to show the problem more clearly. If you compile the program as written it shows on my machine that although enc is allocated a size of 81 bytes including the '\0' byte, it's size has expanded to 84 bytes (strlen = 83). You might get values other than strlen 83 depending on what's in memory when you run it. We have buffer overflow for the exact condition that the algorithm is supposed to work. Now add or delete a character in the test string so that it's not an exact multiple of 8; an invalid use of the function.

Notice now that not only don't we have buffer overflow, but it still seems like we encrypt and decrypt the entire string even though I removed the memcpy function that was supposed to copy these extra characters. This is an illusion, the characters are resident memory garbage and the encoded string doesn't have the original characters in an encrypted form. You will see this if you save the encoded text (can't use c's string functions though or it could get even worse) and try to decode it later when memory changes. You don't have the buffer overflow problem though. Hence, my comment somewhat restated is that the algorithm as implemented only works when you use it incorrectly.

In a previous message in this thread, I posted a Clipper port of
O'Dwyer's test function with padding added. The method I used (Method
#3 from http://www.di-mgt.com.au/cryptopad.html) on the Clipper level
adds a pad of nulls except the last byte which is the chr() of the
total number of pad characters, for example replicate(chr(0),4)+chr(5)
if the remaining size of the last block of data is three characters.
Also, if the original data is an exact multiple of eight characters
already, a whole block of eight pad characters is created (seven nulls
and a chr(8) at the end). This ensures that the last character found
in a decrypted string is a pad character and not something that
belongs to the string itself. And that removes the uncertainty about
how to handle a chr(1) in the last position, for example.

Using this approach with the Clipper port of O'Dwyer's TEA
implementation should remove both risks (non-encrypted characters and
buffer overrun), but the fact remains that his code is not perfect.
Perhaps you should report to him what you found?

True, but fixing a c-problem in another language doesn't give me a lot of confidence that the patch will always work. Since I haven't receive a new release of Clipper recently, I believe that your patch will always work; but I may forget to implement the fix every time I implement the function.

The way the TEA algorithm is called:

TEA_encode( dec, enc, sizeof test, key, 16 );

leads me to believe that Dwyer originally had sizeof key instead of 16 and noticed that this didn't work. Then changed it to strlen(key) and when this didn't work either, gave up and hardcoded 16 into the function call.

Further evidence of this is in the TEA_Encode and TEA_Decode when he puts in the following:
/* Paranoia: check key size */
if (keylen != 16)
return -1;

There seems to be a some confusion between sizeof and strlen in the implementation. The easiest way to fix the buffer overflow problem at the c-level is to change the enc & dec allocation to

char enc[sizeof test+7];
char dec[sizeof test+7];

This is a poor fix, but now the buffer over-run problem goes away in the c-program and you don't have to fix it in Clipper. But you still have the padding problem which Klas has discussed. The padding problem is both easy and necessary to implement in the algorithm. If anyone is interested, code is provided below to show the problem.

After running it as is, change the test string so that it has exact and inexact multiples of 8 characters and look at the results. The results of the test can be a little misleading for anyone unfamilar with c-strings.

The strlen of the encoded string can be reported less that it really is thanks to the c-string feature of encoding a '\0' character to signal the end of a c-string. The algorithm can generate a '\0' character anywhere within the encoded string. Given enough text, the algorithm is guaranteed to generate a '\0' character. Hence, you can't use the common string functions to move the encrypted file around as freely as you might wish. However, the converse isn't true. The strlen function can't report a value greater than it is. If the strlen function reports a value equal to or greater than the true buffer length (remember the '\0' at the end), you have buffer overflow. Now change 'char enc[sizeof test]' to 'char enc[sizeof test+7]' and watch the buffer overflow problem disappear. The dec[] just below end[] should be changed as well.

/* -------------------------------------------------------
* tea-example.c
*
* This code copyright Arthur O'Dwyer 2004. Freeware
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#if CHAR_BIT != 8
#error CHAR_BIT must be 8!
#elif ULONG_MAX != 0xFFFFFFFFuL
#error 'unsigned long' must be 32 bits!
#endif

/*
* Tiny Encryption Algorithm
*
* D.J. Wheeler & R.M. Needham
*/

#define ITERATIONS 32

static void encode(unsigned long *plain,
unsigned long *key,
unsigned long *enc)
{
unsigned long y = plain[0];
unsigned long z = plain[1];
unsigned long sum = 0;
unsigned long delta = 0x9E3779B9;
int i;

for (i=0; i < ITERATIONS; ++i)
{
sum += delta;
y += (z << 4) + (key[0] ^ z) + (sum ^ (z >> 5)) + key[1];
z += (y << 4) + (key[2] ^ y) + (sum ^ (y >> 5)) + key[3];
}
enc[0] = y;
enc[1] = z;
}

static void decode(unsigned long *enc, unsigned long *key, unsigned long *dec)
{
unsigned long y = enc[0];
unsigned long z = enc[1];
unsigned long delta = 0x9E3779B9;
unsigned long sum = delta * ITERATIONS;
int i;

for (i=0; i < ITERATIONS; ++i)
{
z -= (y << 4) + (key[2] ^ y) + (sum ^ (y >> 5)) + key[3];
y -= (z << 4) + (key[0] ^ z) + (sum ^ (z >> 5)) + key[1];
sum -= delta;
}
dec[0] = y;
dec[1] = z;
}


int TEA_encode(void *plain, void *crypt, size_t len,
void *key, size_t keylen)
{
unsigned long *lplain = (unsigned long *) plain;
unsigned long *lcrypt = (unsigned long *) crypt;
int npairs = len/8;
int i;

/* Paranoia: check key size */
if (keylen != 16)
return -1;

for (i=0; i < npairs; ++i)
encode(lplain+2*i, (unsigned long *) key, lcrypt+2*i);

return 0;
}

int TEA_decode(void *crypt, void *plain, size_t len, void *key, size_t nkey)
{
unsigned long *lcrypt = (unsigned long *) crypt;
unsigned long *lplain = (unsigned long *) plain;
int npairs = len/8;
int i;

/* Paranoia: check key size */
if (nkey != 16)
return -1;

for (i=0; i < npairs; ++i)
decode(lcrypt+2*i, (unsigned long *) key, lplain+2*i);

return 0;
}


/* -----------------------------------------------------------------------------------
Test TEA
---------------------------------------------------------------------------------*/
int main(void)
{
char key[] = "1234567890123456";
char test[] = "Having been some days in preparation\n"
"A splendid time is guaranteed for all.12345";
char enc[sizeof test]; // Make this enc[sizeof test + 7]
char dec[sizeof test]; // ditto to prevent buffer over run

int nLen = strlen( test ) % 8;

// enc & dec have correct size for test and '\0'
*dec = '\0';
strcat( dec, test );

TEA_encode( dec, enc, sizeof test, key, 16 );
TEA_decode( enc, dec, sizeof test, key, 16 );

printf("\nString Used for this test:\n%s\n", test);

printf("\nSize of enc[] %d Size of dec[] %d", sizeof( enc ), sizeof(dec));
printf("\nString Length of Test: %d", strlen( test ) );
printf("\nSize of String Test : %d", sizeof( test ) );
printf("\nString Length of Key : %d", strlen( key ) );
printf("\nSize of String Key : %d", sizeof( key ) );

printf("\n\n%s", enc );
printf("\n\n%s", dec );
printf("\n\nLength of Enc: %d" , strlen( enc ));
printf( "\nLength of Dec: %d\n", strlen( dec ));

return 0;
}
.

Relevant Pages

  • Re: Beginners Algorithm
    ... > For fun I decided to whip up an encryption algorithm using Java. ... > character map technique so I could choose the valid input/output characters. ... > characters in the encrypted string ... If you want to encrypt in Java, implement any of the five AES finalists. ...
    (sci.crypt)
  • Re: Generate Unique Identifier
    ... There is no "standard algorithm" to do what you want, ... string fields. ... "Jan Hyde " wrote: ... Alphanumeric Code like I mentioned which is 6 Characters wide and on ...
    (microsoft.public.vb.general.discussion)
  • Beginners Algorithm
    ... For fun I decided to whip up an encryption algorithm using Java. ... character map technique so I could choose the valid input/output characters. ... characters in the encrypted string ...
    (sci.crypt)
  • Re: Generating strings based on pattern
    ... That's an algorithm question, not a C question. ... construct a string which lists each of the ... allowed characters at that position. ... allow the next iteration of the inner loop ...
    (comp.lang.c)
  • Re: Whither VMS?
    ... up a string while reading it in one line at a time. ... algorithm is O. ... for C programmers.) ... naturally lead to buffer overflow. ...
    (comp.os.vms)
Loading