[614] in cryptography@c2.net mail archive
Re: The unmentionable algorithm
daemon@ATHENA.MIT.EDU (Adam Back)
Mon Apr 21 13:35:41 1997
Date: Sun, 20 Apr 1997 08:59:04 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: jamesd@echeque.com
CC: smb@research.att.com, coderpunks@toad.com, cryptography@c2.net
In-reply-to: <199704200502.WAA07323@proxy2.ba.best.com> (jamesd@echeque.com)
James Donald <jamesd@echeque.com> writes:
> At 11:24 PM 4/19/97 -0400, Steven Bellovin wrote:
> > > Similarly, if used by itself there's no
> > > standard way to take advantage of an IV to disguise common prefixes.
> >
> > Huh? Rephrase.
> >
> > If you use a block cipher (such as DES) in CBC mode with a different
> > IV for each message, then the resulting ciphertext will be different,
> > even if the plaintext is identical. This is because each block of
> > ciphertext depends on both the current block of plaintext and the
> > previous block of ciphertext. That propagate back to ``block 0'' of
> > ciphertext -- the IV.
>
> I am well aware of what a CBC mode is, but I see no connection to
> "failure to disguise common prefixes".
>
> It is possible that what you actually meant to say, were you speaking
> in plain english, is that if someone uses the same RC4 key twice,
> they are screwed.
>
> So what. Big deal. People do not use symmetric keys twice.
I think what Steven is saying is that if you know a section of
plaintext you can replace it with another chosen piece of plaintext
without knowing the key. This feature does not apply to DES in CBC
mode (or other modes).
This is because RC4 is basically a strong PRNG, the RC4 key is the
seed to the PRNG, and the PRNG output is XORed with the plaintext.
So, say that for our key rc4_k, the output of the RC4 PRNG is
r_1, r_2, ..., r_n, and the plaintext is p_1, p_2, ..., p_n.
Then the ciphertext is:
c_1 = p_1 ^ r_1
c_2 = p_2 ^ r_2
:
c_n = p_n ^ r_n
This is why you should not use the same key twice, so so far we agree.
However the other implication of this is that Mallory can replace
sections of plaintext with other chosen sections of replacement
plaintext for those portions of the original plaintext which Mallory
knows.
Say this is a transaction protocol, and p_1 and p_2 are say DE for
deposit, and WI for withdrawl. Mallory knows this, and Mallory would
like to change a DE to a WI. So she calculates:
c_1' = c_1 ^ D ^ W;
c_2' = c_2 ^ E ^ I;
c_3' = c_3
:
c_n' = c_n
Using an IV does not help because the encryption process does not
involve the plaintext in the PRNG as happens with DES.
People worry about related problems with DES in ECB mode. For
instance that you can move blocks around even if you don't know the
key. However the solutions used in DES (CBC mode with random IV)
can't be applied to solve this problem in RC4.
> I can write down RC4 in five lines of pseudo code containing nothing
> but simple well defined arithmetic operations.
>
> To write down DES in terms of simple well defined arithmetic operations
> would require several pages of pseudo code.
>
> If you could write down DES in five lines of pseudo code you would have
> already done so.
I'd vote that RC4 is simpler to implement also.
Here's RC4 in 4 lines of C:
#define S,t=s[i],s[i]=s[j],s[j]=t /* rc4 key <file */
unsigned char s[256],i,j,t;main(c,v)char**v;{++v;while
(s[++i]=i);while(j+=s[i]+(*v)[i%strlen(*v)]S,++i);for(
j=0;c=~getchar();putchar(~c^s[t+=s[i]]))j+=s[++i]S;}
RC4 in perl:
#!/bin/perl -p0777-- export-a-crypto-system-sig -RC4-in-3-lines-perl5
@k=unpack'C*',pack'H*',shift;for(@t=@s=0..255){($y+=$k[$_%@k]+$s[$x=
$_])%=256;&S}$x=$y=0;for(unpack'C*',<>){($y+=$s[($x+=1)%=256])%=256;
&S;print chr($_^=$s[($s[$x]+$s[$y])%256])}sub S{@s[$x,$y]=@s[$y,$x]}
DES in perl:
#!/bin/perl -s-- DES in perl5
$/=" ";sub u{$_=<DATA>;s/\s//g;map{-33+ord}/./g}$"='';$[=1;@S=map{[u]}1..8;@I=
u;@F=u;@C=(split//,unpack B64,pack H16,$k.0 x16)[u];@D=splice@C,29;@p=u;$_=11 .
2222221 x2;for$l(/./g){map{push@$_,splice@$_,1,$l}\@C,\@D;$K[++$i]="@{[(@C,@D)
[@p]]}"}@E=u;@P=u;%a=map{unpack(B8,chr$_),$_}0..63;while(read STDIN,$b,8){@L=(
split//,unpack B64,$b."\0"x7)[@I];@R=splice@L,33;for$i(1..16){$i=17-$i if$d;@t
=@R[@E];$j=1;$n=0;for(($K[$i]^"@t"|0 x48)=~/.{6}/g){($n<<=4)+=${$S[$j++]}[$a{
"00$_"}+1]};@t=(split//,unpack B32,pack N,$n)[@P];@X=split//,"@L"^"@t"|0 x32;
@L=@R;@R=@X}print pack B64,join'',(@R,@L)[@F]}__END__~printunpacku,'$2F%P:```'
/!%0.("%#/0#,.)"$++''--,&**&!$()%0"-/))#.%'*#",(0&-,*$(/$++!&'!. 0$".)%/('0,#$
)%/*-(!#".+-'!*&,+&!./)(+,"+$%0.%"#&,)'-('-*!$&#/0* +.!(*!/*'$$%0'&+"#.)-&(/,-
%,#0)"."'+%.*!)'0*$)!(,%"0#/-$&,+&/#(- (..)/,$&!''0*!+$"%#()#&-,"-+%/0*+$'0*!!
'-+,"(..)0*"%$&/,&-#()#%/ #/-,%#"-(%+(,.'")&&!$00+.$!*/)*'%,#)"-,(+"./(#).0'*0
-!&*'+$%!&/$ -+"0+%0#*(#-'*)&!'."$.%//!(,&$,)*%/$0#&-#*)&-0$+(,!/%"+("'.!,)'.
%.,!#,/(0%!*)".+$/-$*&(-&#+0')"'"'%,,..)-"$%(+/(+*0&'!)0!/&#*$#- ."#0).%)'+0$,
("%+-*&$'/,&!!/-*(#(#,"%/"(*%-+/)#.!0'-+*.!0$$&&'), [SKC;3+#]UME=5-%_WOG?7/'aY
QIA91)ZRJB:2*"\TLD<4,$^VNF>6.&`XPH@80( I)Q1Y9aAH(P0X8`@G'O/W7_?F&N.V6^>E%M-U5]
=D$L,T4\<C#K+S3[;B"J*R2Z: ZRJB:2*"[SKC;3+#\TLD<4,$]UME`XPH@80(_WOG?7/'^VNF>6.&
=5-% /2,9"&$=0'6+84-%;)1(<5.#JU@FPX?ITNBQMRHYCVOKSE>A A"#$%&%&'()*)*+,-.-./012
12345656789:9:;<=>=>?@A" 1(56>-=2"08;&3@+#)9/A<$*4.?'7,%: <<< DES in perl >>>
As you can see, DES is considerably larger. The DES is by John Allen
<allen@gateway.grumman.com> and is optimised for size (and
obfuscation).
Adam
--
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
