karl@ddsw1.UUCP (Karl Denninger) (04/04/88)
This is a 'C' rewrite of a publically-available encryption utility we've had
in the woodwork for a while. It works on a rather simple, but surprisingly
effective principle. The output while encrypted has a nearly perfect random
byte distribution from 1 -- 255.
Without the password, which can be up to 80 characters in length (ie: a
sentence; in fact this is recommended) you're in a for a *long* search.
I'm all ears on methods of attacking this, it's been through some reasonably
concerted attempts to break it and no one has yet succeeded.
Basic operation:
The cipher is a substitution cipher executed by the 'XOR'
instruction, with an interesting twist.
Picture a key and plaintext, as thus:
Key > a b c d e f g h i j
Plain> z x y c d s f g h t
The cipher proceeds down the line, from left to right, XORing the
bytes one by one. This would be trivially easy to break, except for
one feature:
A checksum is kept of the bytes processed before and after
XOR; when this checksum reaches a value the entire KEY
string is XORd with the checksum value; the checksum value
is then normalized to reflect the remainder from the
'preset' value.
This combination makes for a cipher which produces a near-random
distribution. For binary files, this is probably enough. For text, though,
there is a small window in the very front of the file in which it might be
possible to perform pattern-analysis to produce the password. To forestall
these attempts, 768 bytes of randomly-generated garbage are prepended to the
file before encryption takes place, and are removed on decryption. These
random bytes serve only to provide a 'seed' for the encryption function to
prevent pattern analysis. In addition, three "FF"s are added during
encryption at the VERY END of the file; this facilitates location of the
actual file end point if the encrypted file should be transmitted via
Xmodem or any other protocol which pads received data.
Of course, I welcome any comments on the implementation; those of you who
believe it should be trivial to break are welcome to try - a sample text
file is enclosed in the 'shar' which follows, encoded with a reasonably
simple password. The only hint I will give you is that it is prose, and
in English. The first person (and only the first one) who can send the
plaintext of this to me by email will receive $25.00 (just to make it
worth your while). The file is called 'text.uue' in the SHAR, it's a
uuencoded copy of the encrypted text file.
This code should run on any reasonable UNIX-based system.
---- Code begins below ----
#!/bin/sh
# shar: Shell Archiver
# Run the following text with /bin/sh to create:
# encrypt.c
# text.uue
sed 's/^X//' << 'SHAR_EOF' > encrypt.c
X/* Encrypt: encrypt or decrypt a file. */
X/*
X This code and associated documentation is Copyright 1988 MCS, Inc.
X Non-profit distribution authorized.
X Please send modifications, etc. to ....ihnp4!ddsw1!karl.
X
X NOTE: If your system uses unsigned characters, you need to change
X the define below for MARKER to be '255' instead of '-1'.
X
X*/
X
X#include <stdio.h>
X#include <fcntl.h>
X#include <sys/types.h>
X
X#define MARKER -1 /* Marker for EOF (unsigned uses 255) */
X
Xchar key[80]; /* Keep the keyspace global */
X
Xenchar(ch) /* Process one character */
Xchar ch; /* Current character */
X
X{
X static int kptr = 0; /* Key pointer */
X static int chsum = 0; /* Key checksum */
X char outch;
X int kx;
X int xkey;
X
X chsum += ch; /* Add before encryption */
X outch = ch ^ key[kptr++]; /* Encrypt */
X chsum += outch; /* And add after */
X if (key[kptr] == 0) /* Restart if at end */
X kptr = 0;
X if (chsum >= 4096) { /* If > 2^^12 - 1 */
X chsum -= 4096; /* Roll checksum... */
X kx = 0;
X xkey = chsum && 255; /* And XOR key */
X while (key[kx] != 0) {
X key[kx] = key[kx] ^ xkey;
X if (key[kx] == 0)/* Insure we don't stop early */
X key[kx] = key[kx] ^ xkey;
X kx++;
X }
X }
X return(outch); /* Return encrypted/decrypted */
X}
X
Xmain()
X{
X
X char infile[80]; /* Path buffers */
X char outfile[80];
X char buffer[256], bufout[256]; /* Block buffers */
X char key2[80]; /* Verification space */
X int fi, fo; /* Two fd's */
X long posit, outpos, pst, oldpos; /* file offsets */
X int jcount; /* Count of skips */
X char encdec[5]; /* Operation flag */
X int ctback, blocks, remain; /* Temp storage */
X int encrypt = 0, decrypt = 0; /* Two flags */
X int outch; /* Outbound character */
X int x, y; /* Two temps */
X
X fputs("Encrypt/Decrypt : ", stdout);
X gets(encdec); /* See what the user wants */
X if ((*encdec == 'e') || (*encdec == 'E'))
X encrypt++;
X else {
X if ((*encdec == 'd') || (*encdec == 'D'))
X decrypt++;
X else {
X puts("Invalid encrypt/decrypt, exit");
X exit(1);
X }
X }
X fputs(" Input filename : ", stdout);
X gets(infile);
X fputs("Output filename : ", stdout);
X gets(outfile);
X fputs(" Enter key : ", stdout);
X gets(key);
X fputs(" Validate : ", stdout);
X gets(key2);
X if (strcmp(key, key2) != 0) {
X puts("Key validation failed.");
X exit(1);
X }
X puts("\nStand by, working...");
X if ((fi = open(infile, O_RDONLY)) == MARKER) {
X perror("Input");
X exit(1);
X }
X if ((fo = open(outfile, O_WRONLY|O_CREAT, 0660)) == MARKER) {
X perror("Output");
X exit(1);
X }
X posit = lseek(fi, 0L, 2); /* Seek EOF */
X posit--; /* Last byte is 1 less */
X if (decrypt != 0) { /* Find marker if decrypt */
X puts("Searching for marker");
X oldpos = posit;
X posit -= 2;
X while (posit >= 0) {
X lseek(fi, posit, 0);
X read(fi, buffer, 3);
X if ((buffer[0] == MARKER) && (buffer[1] == MARKER) && (buffer[2] == MARKER)) {
X oldpos = posit - 1;
X printf("Found marker at location %d\n", oldpos);
X posit = 0;
X }
X posit--;
X }
X if (posit < 0) /* Adjust file pointer */
X posit = oldpos;
X }
X if (encrypt != 0) { /* Add scrambling on encrypt */
X posit += 768; /* Do 3 256-byte records */
X srand(time(0L)); /* Seed random generator */
X puts("Adding seed data (768 bytes)");
X for (x = 0; x < 768; x++) {
X y = (char) rand();
X outch = enchar(y); /* Add 768 random bytes */
X lseek(fo, posit, 0);
X write(fo, &outch, 1);
X posit--;
X }
X }
X if (encrypt != 0)
X puts("Encrypting...");
X else
X puts("Decrypting...");
X if (decrypt != 0)
X jcount = 768; /* Strip 768 on decrypt */
X else
X jcount = 0;
X blocks = ((posit + 1) / 256); /* Number of full blocks */
X remain = ((posit + 1) - (blocks * 256)); /* Remainder */
X lseek(fi, (long) (blocks * 256), 0); /* Seek to start of remainder */
X read(fi, buffer, remain); /* Get remainder */
X remain--;
X for (x = remain; x >= 0; x--) /* Build remainder buffer */
X bufout[x] = enchar(buffer[x]);
X if (jcount == 0) {
X lseek(fo, (long) (blocks * 256), 0);
X write(fo, bufout, (remain + 1)); /* Write remainder */
X } else
X jcount -= (remain + 1); /* Ditch it */
X blocks--; /* Compute # of blocks */
X for (x = blocks; x >= 0 ; x--) {
X lseek(fi, (long) (x * 256), 0);
X read(fi, buffer, 256); /* Read block */
X for (y = 255; y >= 0; y--) /* Encrypt/decrypt block */
X bufout[y] = enchar(buffer[y]);
X lseek(fo, (long) (x * 256), 0);
X if (jcount != 0) { /* Write/count block */
X if (jcount > 256)
X jcount -= 256;
X else {
X write(fo, bufout, (256 - jcount));
X jcount = 0;
X }
X } else
X write(fo, bufout, 256);
X }
X if (encrypt != 0) {
X buffer[0] = MARKER;
X buffer[1] = MARKER; /* Make 3 255's */
X buffer[2] = MARKER;
X lseek(fo, 0L, 2); /* Seek EOF */
X write(fo, buffer, 3);
X }
X close(fo);
X close(fi);
X puts("Complete.");
X exit(0);
X}
SHAR_EOF
sed 's/^X//' << 'SHAR_EOF' > text.uue
Xbegin 660 text.enc
XM9SX53U,O-UU43DL!05Q=%$`<5T)C8C8\2408%59N*C8`%T<>#155'@XR1QH!
XM"@%23S]/!@<,%#1%4P0)&D!*"P$!``%810@.$E@#&F=;'`M84A8-%40&!@@1
XM,%(2#@U424)/$$@03PI(#1YK1!L<,EP<#0Q4&P`(#E,',A%C4Q<)!1E8#0H,
XM11I)#`$(%1!$$!IG3AH7%T\63A)/4T0+&"<`!AE(`TE8!T14'08*#$P.%%1X
XM'"]`%@I86!P;1TD34`!4)TX<#4D&3@T7"E14!AE7"$T!`1`&)T`6"EE!!D\'
XM``!*!1DN``$,'Q522$%N*C8`%U0-#Q4`/RT4`U0G%D)=3@584D,(%2I-4@<;
XM55="!P9$5!X03@,)040''2]`$D\;50$&"$4`5$0=+54!&D@55`Q'5Q%'1W(4
XM6UM-&4I?=P-4`0H!!0<&`1=+!!TO`1,<25T/`T`,21H>30$("!)70TXM3P<#
XM4`Y23R]&4UX+`&)!`0Q(`$A)3R)H)CTL*QT($E(<`&=8'`%84Q8>"%,&544`
XM+`$'&TD"25@'1$$;3QQ8#0\5`!$`-E=5`!\`!@</4U-!#1DG`%H-``%)2!Q%
XM408'%E4("4!.`60B0A4'%$073A-.4E,,$&)!$08>$0!-"P!2$!P*"4P5#E52
XM&"]"&4\+11$*#E<7!D%&=@]"6&-_:$,-"500"QP!!`-`51L'-`\2!Q1$4@X4
XM15-4"Q@G```<!1E!7A9$4P$.#4D?&`A#`4\G31L;#`$<&Q4!`5\6`"9,4@<?
XM$%,-&@U$?@(94AE-!D4%3R)/#!Q901P+1D%32P$!-D4!21\<24\'1%<4'%A,
XM#`0,1!=.,T!4'1=,%DX.3P9#%Q$P51<,205$7@$7`!1/#D4)!VM/`$\U054-
XM&$,95$94&T(7$&)!`0U)'$]9"PM%$0I83@,!&0$'`6=-`0<415,:#T1250T/
XM)P`<#T@`2$E/`DD9"EE4`TP`*@`*)UT:`1A"'@I&31=0`!AM`5(_!@!-20!"
XM5509&4\9311.4P,F1!%.$512&PE/4T(%!CL`'`=(#4]93PM5`4\-2`D>!`QX
XM&"A:&`I85A91;2M?"TA9;@$P#0X<3PT(#$T8"PH!0$!-#%YD3!9!6TP04A\'
XM1Q8'!Q0A2!9)`!U47V5$`%5>2AA?7$%0$@DB#Q</&TD63@I(`54`!TD!4DA)
XM50$-7D51!@$;4DT>%T`#'B)+5`<6*U-.1P%2!D5$8U$`!PH&`5X9!%$$"QP!
XM`A@4*U)/9A]&5TH04@D/3!94'08V11Y)&!5'24\6110+"BI,34`!4TYV'%0=
XM#T`#3@93%T=%!")&%T@;$$!)'6\!5$Y8`4Q?4@`!&"=>50X+11-/%D$40D0"
XM,$D'#!M^``Q/1`!"74$!'0P'1`!.-4H7`AE('@L#`114"AEC1P`-#%5-1!T1
XM*U5/2!547E$14A\G21`<65,:#A1%%P<``"<`!P9(%T]<%TA.&D,/4P09!0$5
XM`35$?DY8`5-.1P%+!A45)$0!2!H=0%X*```1&AP`&`-!0Q,,+DM5!Q!4`65&
XM`%,14T)U$%,:`!532`I%414)'5)-#@]1&@LC)51<0!-&7%804E8$$R8!%`D=
XM&%1?940`1UA,%EY504,"&F9-&@$-10H;1E,$3A`6*T0!8DE$&1U:5QA,3E!/
XM`@-`0A\!)$1=3AQ$!0<$1%)."@$G4@$<&`!3)D]$$T=62Q!:3!52$Q\U)$1>
XM215`6E$34E4<!S=$'T@*%$U!'6\K5$Y8`3@D)`%33A=F,$Y8<2,F(@!39$15
XM8@`@/2$Y90P[,'E53RUI(2E!8STB"V\[*W,`4TX,0`!*145W&$5>2405%%U7
XM`51>6!-?5U,825Y_#U1>2@%27UP10`=+`#%27`L!&@]:!D0/!1T/#P<-$TQ=
XM02=<`08;319.;0$!7Q85)TQ22%],$A].10%46DH!351`$$M4=!I.7$H`4E]7
XM`%,>7D1Z```0&P!!6$]N`%5/$D$>`$$11E9U'%5/6`%'74<!0@971GD22E)<
XM10$-7E<!5%Y"$5Q-34H`!F<E5$Y82A(="@!"$E=`<@!"6E]`$0Q;70!'74,5
XM7E93$E)/=AU53TD:0EQ&5QL&$ATM3Q<:27\!#4X.0`8"6!!865,04U]R'$%>
XM6!=*3E0221)13W,34TE81P`,7UX014\)4TQ!`$043TPD-`$=`!-/%$$<0@H9
XM8W47$!U52$,-"50'!Q=/3&=J:1I.,T<1'!P!>&4G3!\'"Q-B61P<2!Q!6@I$
XM4A`>#$4?&`1$4@8I21L<%4`'!PA/4DD+5"Q4`$@(`%5"#`14$$Y?1@D8%5E5
XM3S1+!0,80Q<"`TX'+104(4L2#@U:``PG`5(020L!&04%`1`;-5T:"PP!&@`!
XM3EX&!`=C5A=(`1172$X,5$]E<T],)14`$QHA0Q`!#5-2(@]#`4@4&C!45!I(
XM$T19&AP-5`\614T)#T0`3BE``$X=3P<'%40>7T4&)E`?"`L1`$4;2@!5-A95
XM9DQ!50$*9EH=!@H`'0$#`!Q)1`TL5`!(#1Q`00<+`1@'%D0>0VI.4SHO2E08
XM'5,`!PE.4V4-&2X`)0@"'P!9'`%350<84TP.!$4<3S5;!0H*4A8*`D5>!A(=
XM-TE2`00%4T(8`$5^3EA"#!T!0QH"+UH<"@H.4D]L3U-N$%4K4U,('A5)0`X&
XM3!!/&%1,`P\!$`8F71,+6$``3@8!`E0`&2I4'T@>'%5%3A%)$4\)51X/"4$!
XM"F9!$T\-2!=E1@`52`@9+5<:!P]44%\!`507&@L;9V0/`3(E!'Q41A=4`4X%
XM0P$&%ALE504)&Q$/808'4AH?%E(80$$3$%YI'1==6092/"5O4W\!&RM84CY`
XM?RA"3C%@,$Y0<@X"0'D6`"Y75#A83AT"'@AX+PI4`D\+2"0<0E\!%4X&&EAT
XM(R0X`1P<9WPW(5AY%@`/6%-!$1DN```0&P!%04]N*55/44D)5D%D%QEF?0P<
XM60M2/1-.!TX)$&)/`4D+&TU<`P%4$$9S*C\)$4$`#C-*&!=4`0<&`@$1218`
XM8T@!2$U`$0->50]43C%530X/3!8<9ED<&Q$`$T\52!Q5$%4F10`*&AU06`8+
XM3E4`'P!G`A!$`0\S1AL`6$`="D=('%41!C9"!@$&&U(-1A=%%`,564!,"%12
XM!BA=`0X53`%/#TY3%408*TX&'0T'`1=#3"M^)QX!&@A`0A(`9TT13A='4P8"
XM30(&`1LM!@9(`1!311L%5!!/#4],!`Y,'@HT#W]E4P!:/"5O4W\!&RM84@$:
XM54`-&A=`$`L50!\&0$X53C-'$4XK0!T:!@$Q5!$/8F\##!H55$4`"@!33S1)
XM#QX.4QT),@=_3UD(/P8%4AQ7"P<V`"8G(2P`11Q$054;"T$("0Q!``1F01-/
XM.'14.T9B%DL(52Y!$1I(4@!A!@=2&A\64AA`06D<#&@'?W3Q=*<;;L-O@M/6
XM@D)Y]MAKL)9@#"ZKWHU)GP@9:..`>E@`M`DHQIM:8\&I_$Z3J))2@F4(Q!-*
XM:5')CI_?NL4:TE$*PRAE'HC?/'^*,?1*1F1VD+6S@$J++V0,H%7'[!9BMM"@
XM_\N1)Y'6"0S%+<D.?4(Y+T^?QAZ\!^7.`-';"+!)XV1)QC#.>,/SDX##<4FX
XMHV#E27L!`+(L\'B9._T#^6^>#H[75IY31Y=(F3>L[IOF;J.\<4AO0,-_C:NQ
XMR\-I>[HGW-F4\L3#)KH??C86C>ZF?#<!&H!?(X,K1?X,*WT*/K/.&H3WC/T:
XMY,Z7=`+Q-%T:P(*0-,*2V68IJFVL<O(10&N;BQ9(^NZMI[O9Q-6O](<E?"$(
XMN5LI9`1QH&MG-O2JV'Q6::OW7DJ*TK,Q8FV,S,AHWR]`M;E>J&*6H1&=N,BY
XM=Y*D8,:WE:*M=I<D@#"&JY=ME,R$='U^WJGED<:<5WGE+7OL6VA7>."]<H?E
XMJLCHY)#>U447!A^8C]I-Y;&A@05K6*8.BO";MJ_-9/]$M]2)D:8?L\$9(![&
XM@K/!7\>&XG#Y[(1*WG"+E]2C6,:KZ^F?!>X4,T4F%3V'1+CAF^ORVL[R/>"=
XMAI4UUD3=`\\V\V_$U-IHDC-7N2,4.N=ZNS?JVQ7ZL[^$2J-H277K(+?RW-&$
XMPZ23YD5IV5?#^&7_O@[+4MN=N^$:%F^;%YK@,W:&!Y/\YR(L_A@GR3TXO]/C
XMZ081L&(`L&;8]!\$&3(C)%W2,!"S'$E_H37^AL+\MMZ7"R+XQ@V5#QUAMN8#
XMY"\\Q4CX$5,8PC-PC[WNM&G,+:H7C[PPBS_$K0SAB,47C_74>33#A]0JOW21
XMU/H]HV=9<0T/$)5A-@HE?#(G6FO@R:^HR!3>^,I7<RP*JVI&BV6N\DF_FOXJ
XMI1%3>_I[2C3U'DQ$XN!)7,82N<:LB/E9UCLHZQ5\?)NK7WRFOTLQ]7G;\D"`
XH`_1.*Q')UTO%)&T-B+</<;823G?'*]]1`T?CFM*UI&DM-*TNL/___WG;
X`
Xend
SHAR_EOF
exit