Xref: utzoo sci.crypt:2740 comp.lang.c:26613
Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!bruce!alanf
From: alanf@bruce.OZ (Alan Grant Finlay)
Newsgroups: sci.crypt,comp.lang.c
Subject: New(?) encryption algorithm
Message-ID: <1877@bruce.OZ>
Date: 6 Mar 90 06:54:33 GMT
Organization: Monash Uni. Computer Science, Australia
Lines: 420

I have written an encription system for personal files on an IBM-PC compatible.
The algorithm is designed to be fast enough for small files and totally secure
if a key is chosen properly.  I mean it should be secure against known plain
text attack but not chosen plain text attack where large numbers of attempts are
permitted.  Included in this article are a source program for the system in C,
a user manual, and a formal description of the algorithm.  This is my first 
non trivial C program so I welcome any constructive criticism.  I would also 
like to know if the formal description is implemented correctly in C.  I am
an amateur at cyphers so I am not certain that my claims about security are
correct.  I would appreciate any comments by those more knowledgeable about
the security of this system.  An archive with all relevant files including
executables will be posted soon in comp.binaries.ibm.pc, included is a challenge
file which is an encription of the source file using a key known only to me.
If anyone would like to attempt a chosen plaintext attack I am willing to use
this same key to encrypt a limited number of files.  I am not sure if I need to
supply a secret file encrypted using this key to make the challenge more 
meaningful.  The program is currently called CRYPT 2.0, I apologise for using a
name that has probably already been used but it's a bit late to change now.

----------------------------------------------------------------------------
                         User manual for Crypt
                         ---------------------

The source code "crypt.c" can be used to produce two  executable  files  which
are  assumed  to be called "encrypt" and "decrypt" by the program itself.  The
source is in Turbo C (Trademark) and can be  compiled  with  the  tiny  memory
model.   Since  use  is  made  of system dependent functions for obtaining the
input file size for encrypt, the program is not portable as is.

To use encrypt and decrypt simply type the command name followed by the source
and  destination  file  names.  You will be prompted for a password and status
information is produced.  The password is  echoed  since  for  the  length  of
password  intended it would be too easy to mess it up.  The password should be
a long sequence of characters such as a sentence with some  strange  words  or
characters  in  it.  The maximum length is the same as the maximum block array
width (100 as supplied).  The password is scrolled off the  screen  after  the
line is terminated.

The algorithm used was inspired by the Rubik's cube.  The core algorithm works
as follows:

   First a fixed block size is determined which is the product of two numbers
   "wide" and "high".  The data is processed in a two dimensional array with
   these dimensions.  If the last block cannot be entirely filled it is
   padded with junk characters.  The password is used to determine a key on
   a column per character basis.  The key value for each column (modulo the
   height) is the amount this column is shifted down.  The part which emerges
   from the bottom is inserted into the top (i.e. a cyclic shift).  The rows
   are similarly shifted but using the values 1,2,3,...,etc.  This two stage
   process is repeated a fixed number of times (10+10) times in the original
   system).  The result is a permutation of the array determined by the
   password alone.

There is one major problem with  this  simple  scheme.   The  use  of  a  pure
permutation  is  compromised by the need to pad the last block.  Especially if
the last block is mostly padding.  It is very difficult to choose padding that
cannot  be  distinguished  from the intentional contents without revealing too
much.  The upshot of all this is that the scheme is  modified  slightly.   For
the first one half of the passes, after the usual column and row shifts, every
second row is replaced by the exclusive-or of  itself  and  the  previous  row
character  by  character.   This  means the shuffling process is now more than
just a pure permutation but alters values according  to  the  history  of  the
shuffle.   As  a  precaution  the rest of the passes are pure permutations.  A
crude  analogy  would  be  shuffling  cards  with  the  printing  still   wet.
Fortunately  the  process  is  reversible when done digitally.  In addition to
this precaution the block size is usually chosen so that the last block is  at
most  a  quarter  padding  (the rare exceptions are reported when they occur).
Finally the padding is  chosen  by  randomly  selecting  bytes  from  the  old
contents of the array (usually bytes from this or a previous pass).

If the input file is smaller than 200 bytes it is rejected.  This may seem  to
be  over cautious but remember that if a password is discovered by cracking an
easy case, every file encoded with that same password  is  available.   It  is
intended  that  users  will  not use many distinct passwords since they should
never be written down and need to be long.  The security of the system is  due
more  to  the choice of password and particularly its length.  Passwords which
are  too  short  are  rejected.   Naturally  the  password  in  not   recorded
permanently  anywhere  by the encryption program.  The easiest way to choose a
good password is to use a whole sentence (spaces and punctuation are  allowed)
with  some  strange  characters  in  it.  It is relatively easy to try out all
short sentences with words from a standard dictionary.  Brute  force  cracking
of  an  encrypted  file  with  n blocks of block size b, a password of p units
chosen from a set of q values and with s shuffles per block requires O(s * b *
(q^p)) operations.  Obviously increasing q and/or p pays great dividends.

For a pure permutation it would also be possible to try all b!  rearrangements
of  a  block.   This  is ruled out by the minimum block size being 100.  It is
clear that increasing s is not an effective way of  improving  security.   The
time  taken by the algorithm is O(s * b * n).  Since (b*n) cannot be changed s
should be chosen as small as is considered safe.  The chosen value is as small
as  seems  secure  but  is  not  chosen  for any real theoretically determined
reason.  Note that s is a compile time constant.

When choosing block dimensions adequate width is more important than  adequate
height.   If  the  width  is  shorter  than  the password then the tail of the
password is not used.  The minimum block dimensions are approximately 24  *  8
so  that  the  algorithm  has  enough  height  to minimise the chance of short
cycles.  Every shuffle is identical and could contain a small number of  short
cycles  (i.e. a small set of positions whose contents always remain within the
set).  Experiments seem to indicate this is not likely with  reasonably  sized
blocks  (i.e.  >200  bytes).   No  theoretical analysis of this issue has been
attempted.  Note however that the row shifts are chosen as 1..n for  a  column
or row of n+1 positions hence there is never a zero row shift.

So far the algorithm's strength depends critically upon  the  variety  of  the
input.   As  described  so for if you input a file with just space characters,
that is mostly what you will get back.  This applys on a block by block basis.
To  avoid  this  problem  the  algorithm  is  given  one final twist, a simple
substitution is performed before the first shuffle.  This substitution  should
suffice to eliminate most simple patterns.

Some final operational advice.  Confidential documents should be created using
a  ram  disk or a floppy which will be destroyed.  Note that deleting and even
overwriting magnetic media does not prevent the data's  recovery.   Watch  out
for  editors  which keep temporary copies of files which they are working upon
in places of their own choice.  A  deleted  temporary  file  is  often  easily
recovered and you may not even be aware of its existence.

-------------------------------------------------------------------------
/***********************************************************************/
/* (c) Copyright 1989, 1990, Alan Finlay.         Beta version 2.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 <math.h>
#include <dos.h>
#include <time.h>
#include <sys\stat.h>

#define ENCRYPT 1        /* Choose encrypt (1) or decrypt (0) */
#define DEBUG 0          /* Show page after each shuffle if non zero */
#define TRUE -1
#define FALSE 0
#define LIMIT 100
#define SECURE 10

typedef unsigned char line[LIMIT];

char copyright[40] = "(c) copyright 1989,1990, Alan Finlay";

unpat(page,wide,high) /* Simple substitution to avoid 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)%128;
      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*2);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 */
      if (k<SECURE) {
	 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];
            }
         }
      /* 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];
         }
      }
   show(page1,wide,high);  /* For text, user can check for blunders */
   }

#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*2);k++) {  /* Check this times 2 as in shuffle */
#if DEBUG
      show(page1,wide,high);
#endif
      /* 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 */
      if (k>=SECURE) {    /* Note matching code in shuffle */
	 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];
            }
         }
      /* 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 */
   int ch = 0;
   int invers;             /* Version of input file for decrypt */
   int vers = 2;           /* 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: encrypt src dst\n"); exit(1);}
#else
   int blkcnt;
   /* Check the input arguments */
   if (argc!=3) {puts("\nUsage is: decrypt 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<200) {puts("Input file is too small"); exit(1);}
   if (fsize<(LIMIT*LIMIT)) blocksize = (int) fsize;
   else {
      nblocks = (int) (fsize/(LIMIT*LIMIT)+1);
      blocksize = (int) (fsize/nblocks+1);
      }
   wide = ((int) sqrt((double)blocksize))+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) {
         puts("It was necessary to use a short last block");
         puts("To correct this change the input file size");
         puts("Otherwise there is a minor security compromise");
         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) {puts("Input file is version incompatible");exit(1);}
#endif
   /* Get password */
   while(1) {
      puts("\nPlease enter your password");
      gets(code);
      clen = strlen(code);
      if (clen>LIMIT) {puts("Password too long - abort"); exit(1);}
      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 */
   for (i=clen;i<LIMIT;i++) code[i] = code[i%clen] ^ '\152';
   do { /* crypt a page */
#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);
      unpat(page,wide,high);
      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);
      unpat(page,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("\nFinished block number %d\n",blkn++);
      }
   while (ch != EOF);
NOBLOCK:                  /* Jump here to avoid writing an empty block */
   fclose(infile);
   fclose(outfile);
}
----------------------------------------------------------------------------

                   Formal description of the algorithm
                   -----------------------------------
A block size is determined according to the size of the input file.
For small files there will be only one block.  Each block has two dimensions -
wide and high.  The last block usually needs some padding which is chosen from
whatever happens to be in the array already.  The junk is selected randomly 
though the random number generator has only about 30,000 possible seeds.  
This is probably much ado about nothing, the padding could probably be just
null characters without any loss in security.  The password or key is a string
supplied by the user, this is extended to the maximum length (100) by 
repetition however the repeated strings are modified by exclusive-or '\152'
to help extract the maximum information from the supplied string (since later
only the remainder mod high will be utilised).

For each block, let us call it page[x,y] where 0<=x<wide and 0<=y<high.
-----------------------------------------------------------------------
	1) Perform a simple substitution:
           page[x,y] := page[x,y] XOR ((x*high+y)*7 mod 128)

	2) Do 10 special shuffles: (each line is for all x and y concurrently)
           page[x,y] := page[x,(y+key[x]) mod high]
	   if y is odd then page[x,y] := page[x,y-1] XOR page[x,y]
           page[x,y] := page[(x+(y mod (wide-1))+1) mod wide,y]

	3) Do 10 normal shuffles: (each line is for all x and y concurrently)
           page[x,y] := page[x,(y+key[x]) mod high]
           page[x,y] := page[(x+(y mod (wide-1))+1) mod wide,y]

Each step in the process is easily reversible.
-------------------------------------------------------------------------

The encrypted file format is:
	1) three 16 bit integers: program version number (= 2), wide, high.
        3) for each block: 
		one 16 bit integer = number of chars in block (non padding).
		the block of bytes:
			for j:=0..high-1
			   for i:=0..wide-1
			      page[i,j]

----------------------------<end>-------------------------------------