alanf@bruce.OZ (Alan Grant Finlay) (05/09/90)
In accordance with advice from various sources I have changed the name
for the next version of my encryption utility from "crypt" to "tangle".
This will hopefully not cause too much confusion with Knuth's tangle
program. Tangle 3.0 is an improved version of Crypt 2.0, and uses a
different algorithm which is not compatible with the old one. Version 2
files are not supported contrary to previous indications. This decision
was taken to avoid an overly complex source for this new version. The
source is tagged on the end of this message. Executables and documentation
are being distributed via "comp.binaries.ibm.pc". The program will run on
an IBM-PC compatible under MS-DOS or similar.
The specific improvements for version 3 are:
1) The password is erased from memory before exit.
(N.B. I use the term password rather than key to emphasise that it is
intended to be a character string.)
2) A password checksum is displayed to reduce the risk of undetected miskeying.
3) The algorithm implements the countermeasure to a chosen plaintext attack
I discovered and discussed in news group "sci.crypt".
4) The 8 bit planes are now no longer independent.
I said that the next version would implement a "pipe" command to avoid the
need to keep typing in a password etc. I have changed my mind since the
security risk to those not familiar with MS-DOS etc were to great. In
particular the fact that MS-DOS "pipes" are really temporary files in
disguise.
I have been told that the previous algorithm was no faster than software DES
implementations however there are still some redeeming properties. Firstly
the key space is huge in comparison, brute force attack is significantly
harder than for DES when for example a 15 character password is used. Secondly
this is an alternative to DES, who knows what progress has been made in
cracking DES? Thirdly this algorithm is easy to implement in parallel with
a speedup proportional to the block size (an advantage in the not too distant
future). Fourth this algorithm is much easier to understand than DES and
the source is distributed so the user can check it, compile it himself, and
not worry about substitution of executables.
For those that can read such things the algorithm is as follows:
For each block, let us call it page[x,y] where 0<=x<wide and 0<=y<high:
(it is understood that each line is for all x<wide and for all y<high)
-----------------------------------------------------------------------
1) Do one shuffle:
page[x,y] := page[x,(y+key[x]) mod high]
if y is odd then page[x,y] := (page[x,y] XOR page[x,y-1])+1 mod 256
page[x,y] := page[(x+(y mod (wide-1))+1) mod wide,y]
2) Perform a simple substitution:
page[x,y] := page[x,y] XOR ((x*high+y)*7 mod 512)
3) Do 9 shuffles:
page[x,y] := page[x,(y+key[x]) mod high]
if y is odd then page[x,y] := ((page[x,y]-1 mod 256) XOR page[x,y-1])
page[x,y] := page[(x+(y mod (wide-1))+1) mod wide,y]
Each step in the process is easily reversible.
-------------------------------------------------------------------------
Step 2 is the countermeasure referred to above. The program source follows:
/***********************************************************************/
/* (c) Copyright 1989, 1990, Alan Finlay. Tangle, Version 3.0 . */
/* This program is intended for Public Domain, and may not be sold or */
/* marketed in any form without the permission and written consent of */
/* the author. I retain all copyrights to this program, in either the */
/* original or modified forms, and no violation, deletion, or change of */
/* the copyright notice is allowed. Every effort has been made to ensure */
/* this product provides a secure encryption system. Mistakes can be */
/* made however both in the theoretical basis and implementation of such */
/* a system. See the associated documentation for a discussion of known */
/* limitations. The source code has been provided so you can inspect it */
/* and use it at your own risk. I will accept no responsibility for any */
/* loss, damage, or compromised data caused directly or indirectly by */
/* this program. It is released on an "as is" basis with no warranty */
/* as to its being fit or suitable for encrypting any form of data. */
/***********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <sys\stat.h>
#define ENCRYPT 1 /* Choose tangle (1) or untangle (0) */
#define DEBUG 0 /* Show page after each shuffle if non zero */
#define TRUE -1
#define FALSE 0
#define LIMIT 100 /* Maximum block size is LIMIT*LIMIT */
#define SECURE 10 /* The number of block transformations */
#define MINB 450 /* Minimum block size - insecure if too small */
typedef unsigned char line[LIMIT];
char copyright[40] = "(c) copyright 1989,1990, Alan Finlay";
unpat(page,wide,high) /* Simple substitution to eliminate simple patterns */
line page[LIMIT]; /* [width,height] */
int wide,high;
{
int i,j,k;
k = 0;
for (i=0;i<wide;i++) for (j=0;j<high;j++) {
k = (k+7)%256;
page[i][j] = page[i][j] ^ k;
}
}
#if ENCRYPT
shuffle(page1,code,wide,high)
line page1[LIMIT]; /* [width,height] */
line code;
int wide,high;
{
int i,j,k,key,shift;
line *mix1,*mix2;
line *oldline,page2[LIMIT]; /* [height,width] */
for (k=0;k<SECURE;k++) { /* See mixup below (2 security phases) */
#if DEBUG
show(page1,wide,high);
#endif
/* Shift columns */
for (i=0;i<wide;i++) {
oldline = page1[i];
key = (int) code[i];
for (j=0;j<high;j++) page2[j][i] =(*oldline)[(j+key)%high];
}
/* Mixup */
for (j=1;j<high;j+=2) {
mix1 = page2[j-1];
mix2 = page2[j];
for (i=0;i<wide;i++) (*mix2)[i] = ((*mix2)[i]^(*mix1)[i])+1;
/* Assume overflow ignored so 255+1==0 */
}
/* Shift rows */
for (j=0;j<high;j++) {
oldline = page2[j];
shift = (j%(wide-1))+1;
for (i=0;i<wide;i++) page1[i][j] = (*oldline)[(i+shift)%wide];
}
/* Eliminate any pattern (after first iteration only) */
if (k==0) unpat(page1,wide,high);
}
}
#else
unshuffle(page1,code,wide,high)
line page1[LIMIT]; /* [width,height] */
line code;
int wide,high;
{
int i,j,k,key,shift;
line *mix1,*mix2;
line *newline,page2[LIMIT]; /* [height,width] */
for (k=0;k<SECURE;k++) { /* Check this times 2 as in shuffle */
#if DEBUG
show(page1,wide,high);
#endif
/* Eliminate any pattern (before last iteration only) */
if (k==SECURE-1) unpat(page1,wide,high);
/* Shift rows back */
for (j=0;j<high;j++) {
newline = page2[j];
shift = wide-(j%(wide-1))-1;
for (i=0;i<wide;i++) (*newline)[i] = page1[(i+shift)%wide][j];
}
/* Reverse mixup */
for (j=1;j<high;j+=2) {
mix1 = page2[j-1];
mix2 = page2[j];
for (i=0;i<wide;i++) (*mix2)[i] = ((*mix2)[i]-1)^(*mix1)[i];
/* Assume underflow is ignored so 0-1==255 */
}
/* Shift columns back */
for (i=0;i<wide;i++) {
newline = page1[i];
key = (int) code[i];
for (j=0;j<high;j++) (*newline)[(j+key)%high] = page2[j][i];
}
}
}
#endif
show(page,wide,high)
line page[LIMIT];
int wide,high;
{
int i,j;
puts("\n");
for (j=0;j<high;j++) {
putc('\n',stdout);
for (i=0;i<wide;i++) {
if (page[i][j]<30) putc('*',stdout);
else putc(page[i][j],stdout);
}
}
}
main (argc,argv)
int argc;
char *argv[];
{
FILE *infile,*outfile;
int wide,high,i,j,k; /* Block width and height, loop counters */
int blkn = 1; /* Block counter */
int clen; /* Password code length */
long chksum; /* Password checksum */
int ch = 0;
int invers; /* Version of input file for decrypt */
int vers = 3; /* Version of this program */
line page[LIMIT],code;
#if ENCRYPT
int chrcnt; /* Character counter */
long fsize; /* Input file size */
int blocksize,nblocks;
struct time t; /* For system time */
struct stat st; /* For input file stats */
/* Randomise the rand() function */
gettime(&t);
srand(t.ti_min*400+t.ti_sec*100+t.ti_hund); /* random seed <30000 */
/* Check the input arguments */
if (argc!=3) {puts("\nUsage is: tangle src dst\n"); exit(1);}
#else
int blkcnt;
/* Check the input arguments */
if (argc!=3) {puts("\nUsage is: untangle src dst\n"); exit(1);}
#endif
if ((infile = fopen(argv[1],"rb")) == NULL) {
printf("\n%s",argv[1]); perror(" "); exit(1);}
if ((outfile = fopen(argv[2],"wb")) == NULL) {
printf("\n%s",argv[2]); perror(" "); exit(1);}
#if ENCRYPT
/* Get input file size */
if (stat(argv[1],&st)!=0) {perror(" "); exit(1);}
fsize = st.st_size;
printf("The input file size is %ld\n",fsize);
/* Choose block size accordingly */
if (fsize<(LIMIT*LIMIT)) blocksize = (int) fsize;
else {
nblocks = (int) (fsize/(LIMIT*LIMIT)+1);
blocksize = (int) (fsize/nblocks+1);
}
if (fsize<MINB) blocksize = MINB; /* Minimum block size enforced */
wide = 0; while (wide*wide<blocksize) wide++; /* Approx square root */
wide = wide+10; if (wide>LIMIT) wide = LIMIT;
high = blocksize/wide+1; if (high>LIMIT) high = LIMIT;
while (1) {
blocksize = wide*high;
if (fsize<(long) blocksize) break;
else {
/* Multiple blocks, check for last block too small */
if (((fsize-1)%blocksize)>(blocksize*3/4)) break;
/* (fsize-1) is used above so perfect fit is accepted! */
high--; wide--; /* Try a smaller block */
}
if (wide<50) break;
}
printf("The width and height are (%d,%d)\n",wide,high);
printf("The last block is %ld bytes\n",((fsize-1)%blocksize)+1);
fprintf(outfile,"%d,%d,%d,",vers,wide,high);
#else
fscanf(infile,"%d,%d,%d,",&invers,&wide,&high);
if (invers!=vers) {
printf("This is version %d of the encryption program.\n",vers);
printf("The input file is for program version %d or invalid.\n",invers);
exit(1);
}
#endif
/* Get password */
while(1) {
puts("\nPlease enter your password");
fgets(code,LIMIT,stdin);
clen = strlen(code);
if (clen>9) break;
puts("Insecure password, try a longer one.");
puts("For security do not use a name or word in any dictionary.");
puts("For example use something like \"Dazed and Konfuzed\"");
}
for (i=0;i<25;i++) puts(" "); /* Clear the screen */
if (clen>wide) puts("Warning: tail of password ignored");
/* Extend password to possible limit, not null terminated */
for (i=clen;i<LIMIT;i++) code[i] = code[i%clen] ^ '\152';
/* Generate a checksum for the characters */
for (chksum=0,i=0;i<clen;i++) chksum += (int) code[i]*i;
printf("The password checksum is %ld. Please wait ...\n",chksum % 1000);
do { /* tangle or untangle a block */
#if ENCRYPT
chrcnt = 0;
#else
if (fscanf(infile,"%d,",&blkcnt)==EOF) goto NOBLOCK;
#endif
for (j=0;j<high;j++) {
for (i=0;i<wide;i++) {
if ((ch = getc(infile)) != EOF) {
page[i][j] = ch;
#if ENCRYPT
chrcnt++;}
else if (i==0 && j==0) goto NOBLOCK; /* EOF at start of block! */
/* Pad the last block with existing junk */
else page[i][j] = page[rand()%wide][rand()%high];
#else
;}
else {puts("Error: unexpected end of file"); goto NOBLOCK;}
#endif
}
}
#if ENCRYPT
fprintf(outfile,"%d,",chrcnt);
shuffle(page,code,wide,high);
for (j=0;j<high;j++) for (i=0;i<wide;i++) putc(page[i][j],outfile);
#else
unshuffle(page,code,wide,high);
for (j=0;j<high;j++) for (i=0;i<wide;i++)
if ((j*wide+i)<blkcnt) putc(page[i][j],outfile);
#endif
printf("Finished block number %d\n",blkn++);
}
while (ch != EOF);
NOBLOCK: /* Jump here to avoid writing an empty block */
for (i=0;i<LIMIT;i++) code[i] = ' '; /* Rubout the password before exit */
fclose(infile);
fclose(outfile);
}