RC2 source code
Anonymous
/**********************************************************************\
* To commemorate the 1996 RSA Data Security Conference, the following *
* code is released into the public domain by its author. Prost! *
* *
* This cipher uses 16-bit words and little-endian byte ordering. *
* I wonder which processor it was optimized for? *
* *
* Thanks to CodeView, SoftIce, and D86 for helping bring this code to *
* the public. *
\**********************************************************************/
#include <string.h>
#include <assert.h>
/**********************************************************************\
* Expand a variable-length user key (between 1 and 128 bytes) to a *
* 64-short working rc2 key, of at most "bits" effective key bits. *
* The effective key bits parameter looks like an export control hack. *
* For normal use, it should always be set to 1024. For convenience, *
* zero is accepted as an alias for 1024. *
\**********************************************************************/
void rc2_keyschedule( unsigned short xkey[64],
const unsigned char *key,
unsigned len,
unsigned bits )
{
unsigned char x;
unsigned i;
/* 256-entry permutation table, probably derived somehow from pi */
static const unsigned char permute[256] = {
217,120,249,196, 25,221,181,237, 40,233,253,121, 74,160,216,157,
198,126, 55,131, 43,118, 83,142, 98, 76,100,136, 68,139,251,162,
23,154, 89,245,135,179, 79, 19, 97, 69,109,141, 9,129,125, 50,
189,143, 64,235,134,183,123, 11,240,149, 33, 34, 92,107, 78,130,
84,214,101,147,206, 96,178, 28,115, 86,192, 20,167,140,241,220,
18,117,202, 31, 59,190,228,209, 66, 61,212, 48,163, 60,182, 38,
111,191, 14,218, 70,105, 7, 87, 39,242, 29,155,188,148, 67, 3,
248, 17,199,246,144,239, 62,231, 6,195,213, 47,200,102, 30,215,
8,232,234,222,128, 82,238,247,132,170,114,172, 53, 77,106, 42,
150, 26,210,113, 90, 21, 73,116, 75,159,208, 94, 4, 24,164,236,
194,224, 65,110, 15, 81,203,204, 36,145,175, 80,161,244,112, 57,
153,124, 58,133, 35,184,180,122,252, 2, 54, 91, 37, 85,151, 49,
45, 93,250,152,227,138,146,174, 5,223, 41, 16,103,108,186,201,
211, 0,230,207,225,158,168, 44, 99, 22, 1, 63, 88,226,137,169,
13, 56, 52, 27,171, 51,255,176,187, 72, 12, 95,185,177,205, 46,
197,243,219, 71,229,165,156,119, 10,166, 32,104,254,127,193,173
};
assert(len > 0 && len <= 128);
assert(bits <= 1024);
if (!bits)
bits = 1024;
memcpy(xkey, key, len);
/* Phase 1: Expand input key to 128 bytes */
if (len < 128) {
i = 0;
x = ((unsigned char *)xkey)[len-1];
do {
x = permute[(x + ((unsigned char *)xkey)[i++]) & 255];
((unsigned char *)xkey)[len++] = x;
} while (len < 128);
}
/* Phase 2 - reduce effective key size to "bits" */
len = (bits+7) >> 3;
i = 128-len;
x = permute[((unsigned char *)xkey)[i] & (255 >> (7 & -bits))];
((unsigned char *)xkey)[i] = x;
while (i--) {
x = permute[ x ^ ((unsigned char *)xkey)[i+len] ];
((unsigned char *)xkey)[i] = x;
}
/* Phase 3 - copy to xkey in little-endian order */
i = 63;
do {
xkey[i] = ((unsigned char *)xkey)[2*i] +
(((unsigned char *)xkey)[2*i+1] << 8);
} while (i--);
}
/**********************************************************************\
* Encrypt an 8-byte block of plaintext using the given key. *
\**********************************************************************/
void rc2_encrypt( const unsigned short xkey[64],
const unsigned char *plain,
unsigned char *cipher )
{
unsigned x76, x54, x32, x10, i;
x76 = (plain[7] << 8) + plain[6];
x54 = (plain[5] << 8) + plain[4];
x32 = (plain[3] << 8) + plain[2];
x10 = (plain[1] << 8) + plain[0];
for (i = 0; i < 16; i++) {
x10 += (x32 & ~x76) + (x54 & x76) + xkey[4*i+0];
x10 = (x10 << 1) + (x10 >> 15 & 1);
x32 += (x54 & ~x10) + (x76 & x10) + xkey[4*i+1];
x32 = (x32 << 2) + (x32 >> 14 & 3);
x54 += (x76 & ~x32) + (x10 & x32) + xkey[4*i+2];
x54 = (x54 << 3) + (x54 >> 13 & 7);
x76 += (x10 & ~x54) + (x32 & x54) + xkey[4*i+3];
x76 = (x76 << 5) + (x76 >> 11 & 31);
if (i == 4 || i == 10) {
x10 += xkey[x76 & 63];
x32 += xkey[x10 & 63];
x54 += xkey[x32 & 63];
x76 += xkey[x54 & 63];
}
}
cipher[0] = (unsigned char)x10;
cipher[1] = (unsigned char)(x10 >> 8);
cipher[2] = (unsigned char)x32;
cipher[3] = (unsigned char)(x32 >> 8);
cipher[4] = (unsigned char)x54;
cipher[5] = (unsigned char)(x54 >> 8);
cipher[6] = (unsigned char)x76;
cipher[7] = (unsigned char)(x76 >> 8);
}
/**********************************************************************\
* Decrypt an 8-byte block of ciphertext using the given key. *
\**********************************************************************/
void rc2_decrypt( const unsigned short xkey[64],
unsigned char *plain,
const unsigned char *cipher )
{
unsigned x76, x54, x32, x10, i;
x76 = (cipher[7] << 8) + cipher[6];
x54 = (cipher[5] << 8) + cipher[4];
x32 = (cipher[3] << 8) + cipher[2];
x10 = (cipher[1] << 8) + cipher[0];
i = 15;
do {
x76 &= 65535;
x76 = (x76 << 11) + (x76 >> 5);
x76 -= (x10 & ~x54) + (x32 & x54) + xkey[4*i+3];
x54 &= 65535;
x54 = (x54 << 13) + (x54 >> 3);
x54 -= (x76 & ~x32) + (x10 & x32) + xkey[4*i+2];
x32 &= 65535;
x32 = (x32 << 14) + (x32 >> 2);
x32 -= (x54 & ~x10) + (x76 & x10) + xkey[4*i+1];
x10 &= 65535;
x10 = (x10 << 15) + (x10 >> 1);
x10 -= (x32 & ~x76) + (x54 & x76) + xkey[4*i+0];
if (i == 5 || i == 11) {
x76 -= xkey[x54 & 63];
x54 -= xkey[x32 & 63];
x32 -= xkey[x10 & 63];
x10 -= xkey[x76 & 63];
}
} while (i--);
plain[0] = (unsigned char)x10;
plain[1] = (unsigned char)(x10 >> 8);
plain[2] = (unsigned char)x32;
plain[3] = (unsigned char)(x32 >> 8);
plain[4] = (unsigned char)x54;
plain[5] = (unsigned char)(x54 >> 8);
plain[6] = (unsigned char)x76;
plain[7] = (unsigned char)(x76 >> 8);
}
Richard Outerbridge
96/01/29 19:06:06 EST
So: is this for real?
> Subject: RC2 source code
> From: anon-r...@utopia.hacktic.nl (Anonymous)
> Newsgroups: sci.crypt
> Date: 29 Jan 1996 06:38:04 +0100
> Organization: Hack-Tic International, Inc.
> Lines: 182
> Sender: rema...@utopia.hacktic.nl
> Message-ID: <4ehmfs$6...@utopia.hacktic.nl>
> NNTP-Posting-Host: utopia.hacktic.nl
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBMQ1hEdNcQg4O6q8hAQE4rgP+Jx3+WaBETDVgeANS+6OObLFYN35pNJO8
cl732KR5rv1HSNjjFXfHx73JFcxQC7V+wrhqFNsUtrBMyrQk1PWN+Chjb4Kf+GR6
Wz9PBGW66xWi/UC87SUAfw7+VCKxbcFZFedhwB+746FJoXRv6PHMFCNFaYuIiKzY
QcGbjnXqQcA=
=yJNf
-----END PGP SIGNATURE-----
--
<ou...@interlog.com> :
"Just an eccentric soul with a curiosity for the bizarre."
Stephen Kapp
match?
Stephen Kapp.
-----------------------------------------------------------------
E-mail: sk...@cix.compulink.co.uk, sk...@sourcery.demon.co.uk
Http: http://www.phantom.com/~skapp/
PGP fingerprint: 78 1C CD F4 A4 44 D2 CB DD A5 CF EF F1 DD D8 6A
-----------------------------------------------------------------
Bruce Schneier
Don't know. It's not obviously a lousy algorithm, which says something.
It is similar in design to MD2, which is a rumor I have heard. Rivest
has said nothing; RSADSI has said nothing.
Does anyone have a legal copy of the BSAFE toolkit who can try to decrypt
messages encrypted with this thing?
Bruce
**************************************************************************
* Bruce Schneier APPLIED CRYPTOGRAPHY, 2nd EDITION is
* Counterpane Systems available. For info on a 15%
* schn...@counterpane.com discount offer, send me e-mail.
**************************************************************************
Stephen Kapp
to get a license from RSADSI. Or a least so I'm told, I suppose they
will probably do the same.
Bruce Schneier
Stephen Kapp <sk...@cix.compulink.co.uk> wrote:
>Has anyone managed to try this out with some known RC2 to see if they
>match?
I herad from someone who did; it matches.
Bruce
Bruce Schneier
Bruce Schneier <schn...@parka.winternet.com> wrote:
>In article <outer-29019...@outer.interlog.com>,
>Richard Outerbridge <ou...@interlog.com> wrote:
>>
>>So: is this for real?
According to people I have spoken to, RSADSI has all but admitted it is
real. They are preparing another letter threatening legal action against
anyone using what was once their trade secret. You'd think they would have
had a letter already prepared after RC4.
Bruce
**************************************************************************
* Bruce Schneier
* Counterpane Systems For a good prime, call 391581 * 2^216193 - 1
* schn...@counterpane.com
**************************************************************************
John Kelsey
[ To: sci.crypt ## Date: 01/29/96 09:18 pm ##
Subject: RC2 source code ]
>From: anon-r...@utopia.hacktic.nl (Anonymous)
>Newsgroups: sci.crypt
>Subject: RC2 source code
>Date: 29 Jan 1996 06:38:04 +0100
This was interesting. Is this another "S1," or another
"alleged-RC4?" The whole thing looks pretty believeable, i.e., it
doesn't have any obviously dumb parts that I can see.
Note that alleged RC2's block encryption function looks an awful lot
like one round of MD5 performed on 16-bit sub-blocks, using the
bitwise selection function as the nonlinear function, and a
key-derived constant table. Additionally, in rounds four and
eleven, there are four lookups into the expanded key array.
The encryption function could be rewritten as
for(i=0;i<16;i++){
a = rotl(a + bsel(d,c,b) + *sk++, 1);
b = rotl(b + bsel(a,d,c) + *sk++, 2);
c = rotl(c + bsel(d,c,b) + *sk++, 3);
d = rolt(d + bsel(c,b,a) + *sk++, 5);
if((i==4)||(i==11)){
a += xk[d&0x3f];
b += xk[a&0x3f];
c += xk[b&0x3f];
d += xk[c&0x3f];
}
}
If this is accurate, it may give us some insight into Rivest's
development of MD4 and MD5, which were radically different than MD2.
What are the dates on this? Did Rivest do MD4 or RC2 first? This
may be the first block cipher in the commercial/academic world to
use a UFN structure. One interesting part of this is the use of the
subkey array as an S-box twice during the encryption process. I'm
curious as to why this would be used only twice, rather than each
round, i.e.
a += bsel(b,c,d) + *sk++ + s[d&0x3f];
Sticking a very different internal transformation in may have been
an attempt to make iterative (i.e., differential) attacks harder,
since there's no longer a single round function through which you
can pass differential characteristics. This depends upon when RC2
was developed and released.
Note that the claim that "RC2 is not an iterative block cipher"
seems to be based on the fact that it has two instances where a
different round function is thrown in. (Essentially, it's actually
an 18-round cipher with two different round functions, one of which
is used only twice.) This other round function isn't very
impressive, since it uses only six bits of the source block to
affect the target block.
A one-bit change in a randomly-distributed input block looks
look like it will propogate pretty quickly: There's a roughly 0.5
probability that it doesn't make it through the bsel function. If
it does, then there's about a 0.5 probability that it will cause a
change in the carry bit. This happens four times per "round," so a
one-bit change should have about a 2^{-8} chance to make it through
one round as a one-bit change, and so about a 2^{-128} chance to
make it through all sixteen rounds, assuming no impact from either
of the two S-box lookups. Does this look right, or am I missing
something? (This is a first approximation--if our bit is in the
high-order position anywhere, then it *can't* cause a carry bit, but
there's no obvious way to keep it there for long.) By choosing the
input block, I can ensure that one-bit XOR difference makes it
through the first step or two, but that doesn't do too much for an
actual attack.
Other XOR differences can help with the first round or so, but stop
being helpful afterward. It generally looks hard to prevent
diffusion by choosing other values, at least using XOR differences,
because each subblock is rotated a different amount in each round.
(The bits don't keep lining up.)
We can also try to do a differential attack based on subtraction
modulo 2^16, based partially on Tom Berson's attempt to
differentially attack MD5 using subtraction modulo 2^32. This gets
complicated because of the rotations and the bit selection
operations, but it ought to be tried if it hasn't already.
The key scheduling is also interesting, and somewhat reminiscent of
MD2's internal operations. Each expanded key byte after the first N
(where N is the number of bytes in the user's key) is determined by
two bytes--the previous expanded key byte, and the expanded key byte
N positions back. This means that we probably don't get ideal
mixing of the key bytes in the early expanded key bytes, but it
isn't clear to me that there will be a lot of problems with
reasonable key lengths. (Note that a reasonable key length would be
128 bits=16 bytes, and that it should come from the output of a good
one-way hash function.) I wouldn't recommend using the key schedule
to hash passphrases, since long passphrases would leave us with many
very low-entropy subkey values. In general, I think that really
large user keys will leave us vulnerable to a variety of related-key
attacks and other nasty stuff. I'm a little curious as to the
purpose of phase 2 of the key schedule, but since it's only used
when a watered-down version of the algorithm is wanted (right?), I
haven't spent much time looking at it.
Does alleged RC2's key schedule use the same permutation table as
MD2 does? For small systems, this might have been a reasonably nice
space savings. (On the other hand, if you have a hash function
available at the same time, it makes sense to go ahead and use it in
your key schedule, which isn't done here.)
The algorithm looks like it will have reasonable performance on
16-bit machines like the 8086, which was almost certainly one of the
requirements for the algorithm, given the times it was used.
Comments?
--John Kelsey, jmke...@delphi.com / kel...@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBMQ43Q0Hx57Ag8goBAQG0LQQAiohrNSPvKzSIJjMeWjrK/r7HZOWp0Mhg
zcq60rIyPMpsDnxuk7VlLrU2XBy0Aff4QpO8jORS3VFKtaLH5XJehc7WTZF+1En1
ux4prro+Gpvn99HToTqKa6igxlEGYShskoF/aBIkszZAg6m/P92BPyZ/PW3tnMtp
MoMcdNGcO0I=
=ttGl
-----END PGP SIGNATURE-----
Robert Salesas
>/**********************************************************************\
>* To commemorate the 1996 RSA Data Security Conference, the following *
>* code is released into the public domain by its author. Prost! *
>* *
>* This cipher uses 16-bit words and little-endian byte ordering. *
>* I wonder which processor it was optimized for? *
>* *
>* Thanks to CodeView, SoftIce, and D86 for helping bring this code to *
>* the public. *
>\**********************************************************************/
I heard that RC4 was also mentioned at the conference. Did they
finally acknowledge the released code?
- Robert Salesas, Eschalon Development Inc.
Visit our web site at www.eschalon.com
Peter Gutmann
>According to people I have spoken to, RSADSI has all but admitted it is
>real. They are preparing another letter threatening legal action against
>anyone using what was once their trade secret.
Given that the code was (going from the origin and the comments in it)
reverse-engineered in Europe, and that reverse-engineering is legal in Europe
and has been upheld by the Supreme Court in the US, do they have any basis for
threatening someone? Based on the debate which followed the RC4 release I
would have thought that RC2 is effectively in the public domain now.
Peter.
Ian S. Nelson
>If you use the RC4 derived from the infamous sci.crypt post your supposed
>to get a license from RSADSI. Or a least so I'm told, I suppose they
>will probably do the same.
I think that that is for the courts to decide. All the legal advice I have
heard says that RSADSI got screwed and you can do what you want with RC4.
I know RSADSI has said things to people who were planning on using it though.
It's really a matter of how brave you are and if you are willing to play
ball if they don't like what you're doing. They might not be able to sue you
or stop you from using it but they can make your life difficult, it is
probably just easier for most people to switch to some other cipher.
Mutatis Mutantdis
>Given that the code was (going from the origin and the comments in it)
>reverse-engineered in Europe, and that reverse-engineering is legal in Europe
>and has been upheld by the Supreme Court in the US, do they have any basis for
>threatening someone? Based on the debate which followed the RC4 release I
>would have thought that RC2 is effectively in the public domain now.
Maybe... but if you're sued by someone with a hell of a lot more
money, you may end up with a phyrric legal victory.
I think "RC2" and "RC4" are still trademark names, though. You might
be able to use the algorithm, but not necessarily the name.
Rob.
Bruce Schneier
Peter Gutmann <pgu...@cs.auckland.ac.nz> wrote:
>schn...@parka.winternet.com (Bruce Schneier) writes:
>
>>According to people I have spoken to, RSADSI has all but admitted it is
>>real. They are preparing another letter threatening legal action against
>>anyone using what was once their trade secret.
>
>reverse-engineered in Europe, and that reverse-engineering is legal in Europe
>and has been upheld by the Supreme Court in the US, do they have any basis for
>threatening someone? Based on the debate which followed the RC4 release I
>would have thought that RC2 is effectively in the public domain now.
RSADSI doesn't need any basis to threaten someone, just need a lawyer willing
to do the threatening. I expect that whatever the reality of the situation
is, RSADSI will make it cheaper for a company to license than to fight them
in court.
Bruce
Ralf Brown
}According to people I have spoken to, RSADSI has all but admitted it is
}real. They are preparing another letter threatening legal action against
}had a letter already prepared after RC4.
sed s/RC4/RC2/g RC4-letter >RC2-letter
Right? I suppose they didn't learn anything from the RC4 incident....
--
My employer will | Internet: ra...@pobox.com | "If carried too far, virtues
deny knowing of | Fido: Ralf Brown 1:129/26.1 | can evolve into various
this message... | http://www.pobox.com/~ralf | faults." -- Eugene T. Maleska
Colin Plumb
Mutatis Mutantdis <wlkn...@unix.asb.com> wrote:
> I think "RC2" and "RC4" are still trademark names, though. You might
> be able to use the algorithm, but not necessarily the name.
I have never seen any trademark claim by RSADSI on "RC2" or "RC4". If
it were, it would probably be on the netscape startup banner that has
the RSADSI section and mentions RC2.
If anyone has received a nastygram from RSADSI over use of RC4
(I assume it's too new for RC2), the legal claims advanced might
inform this discussion.
--
-Colin
Mutatis Mutantdis
>[ To: sci.crypt ## Date: 01/29/96 09:18 pm ##
> Subject: RC2 source code ]
>>From: anon-r...@utopia.hacktic.nl (Anonymous)
>>Newsgroups: sci.crypt
>>Subject: RC2 source code
>>Date: 29 Jan 1996 06:38:04 +0100
>This was interesting. Is this another "S1," or another
>"alleged-RC4?" The whole thing looks pretty believeable, i.e., it
>doesn't have any obviously dumb parts that I can see.
>Note that alleged RC2's block encryption function looks an awful lot
[..]
>Comments?
The reliance on addition with anding of the plaintext doesn't inspire
much confidence for me. It looks like by using the cipher to encrypt
a block of zeros and other chosen plaintexts one could derive the
skey, (which is all that one needs for decryption, really).
That in mind, does anyone else see a good possibility for chosen or
known plaintext attacks? (or did I read the algorithm wrongly...)
Rob.
Robert Baldwin
WARNING NOTICE
It has recently come to the attention of RSA Data
Security, Inc. that certain of its confidential and
proprietary source code has been misappropriated and
disclosed. Despite such unauthorized use and disclosure,
RSA Data Security reserves all intellectual property rights
in such source code under applicable law, including without
limitation trade secret and copyright protection. In
particular, RSA Data Security's RC2 (TM) symmetric block
cipher source code has been illegally misappropriated and
published. Please be advised that these acts, as well as
any retransmission or use of this source code, is a
violation of trade secret, copyright and various other state
and federal laws. Any person or entity that acquires,
discloses or uses this information without authorization or
license to do so from RSA Data Security, Inc. is in
violation of such laws and subject to applicable criminal
and civil penalties, which may include monetary and punitive
damages, payment of RSA's attorneys fees and other equitable
relief.
RSA Data Security considers misappropriation of its
intellectual property to be most serious. Not only is this
act a violation of law, but its publication is yet another
abuse of the Internet. RSA has begun an investigation and
will proceed with appropriate action against anyone found to
have violated its intellectual property rights.
Anyone having information about the misappropriation
identified above is encouraged to contact RSA directly.
Robert Baldwin
Anthony Naggs
: pgu...@cs.auckland.ac.nz (Peter Gutmann) writes:
: >Given that the code was (going from the origin and the comments in it)
: >reverse-engineered in Europe, and that reverse-engineering is legal in Europe
Sorry Peter, I didn't see your original post (yet) ...
Reverse engineering in Europe is not legal, it is a quite flagrant breach
of copyright. The European directive on software copyright does allow
'reverse engineering' only to the extent of discovering a software interface
to allow interoperability. I think my interpretation is in line with
current legal opinions, vis: Stacker's reverse engineering of the API
between MS-DOS 6 kernel & DoubleSpace would be allowed, (this reverse
engineering is clearly with the intent of using the API). But actually
reverse engineering how DoubleSpace works internally probably isn't.
: >and has been upheld by the Supreme Court in the US, do they have any basis for
: >threatening someone? ...
They certainly have a basis for threatening whoever broke the trade
secret agreement, and probably anyone who a misappropriates theirt trademark.
: ... Based on the debate which followed the RC4 release I
: >would have thought that RC2 is effectively in the public domain now.
: Maybe... but if you're sued by someone with a hell of a lot more
: money, you may end up with a phyrric legal victory.
: I think "RC2" and "RC4" are still trademark names, though. You might
: be able to use the algorithm, but not necessarily the name.
I agree. I don't think they are registered trademarks, but they quite
clearly are in normal use to refer to the specific products of a specific
company. This I believe is the criteria by which trademark cases in the
USA & Europe (dunno about anywhere else) are judged, use by another company
is generally regarded as "passing off".
--
Anthony Naggs - Computer Security & Anti-Virus Engineer, CSIR, South Africa
Disclaimer: these are my personal views and opinions, and do not represent
my employers; past, present or future.
Robert Salesas
>Despite such unauthorized use and disclosure,
>RSA Data Security reserves all intellectual property rights
>in such source code under applicable law, including without
>limitation trade secret and copyright protection.
If a trade secret is revealed by an individual having contractual
agreement with RSA, and a unrelated 3rd party uses that information,
RSA cannot prosecute the 3rd party. Since they didn't patent the
algorithm, they can't prevent the 3rd party from using it. What they
can prevent is a copyright violation, but even that depends on how
many ways the algorithm can possibly be represented. If there is only
one way to implement the algorithm, or it is an obvious way, they
cannot pursue. It will be interesting to see how they react when
someone stands up to them.
Arthur Chance
tna...@zibbi.mikom.csir.co.za (Anthony Naggs) writes:
> Reverse engineering in Europe is not legal, it is a quite flagrant breach
> of copyright. The European directive on software copyright does allow
> 'reverse engineering' only to the extent of discovering a software interface
> to allow interoperability. I think my interpretation is in line with
> current legal opinions, vis: Stacker's reverse engineering of the API
> between MS-DOS 6 kernel & DoubleSpace would be allowed, (this reverse
> engineering is clearly with the intent of using the API). But actually
> reverse engineering how DoubleSpace works internally probably isn't.
and then signs
> Anthony Naggs - Computer Security & Anti-Virus Engineer
which triggered off the following thoughts:
By your logic European law would make it illegal to reverse engineer a
virus to see how it works internally. Although malicious dissemination
of computer viruses is illegal in the UK and possibly other places,
AFAIK the copyright on the code still exists. Thus we end up with the
interesting and disturbing idea that (European) manufacturers of
anti-virus measures are law breakers should they develop their
software by examining the target viruses rather than by divine
revelation. (This may quite possibly be true, given the way our
legislators have problems with computer related matters.) On
utilitarian grounds I'd rather see RSADSI lose their trade secret than
have all antivirus measures made illegal.
There is also the possibility that if the code was derived by reverse
engineering, the act was carried out in a location where such an act
was perfectly legal. (I believe a boat in the middle of the North Sea
would be such a location, although you'd need a hacker with a cast
iron stomach and very warm clothing right now. :-)
> They certainly have a basis for threatening whoever broke the trade
> secret agreement
RSADSI claim their source has been ripped off:
> It has recently come to the attention of RSA Data
> Security, Inc. that certain of its confidential and
> proprietary source code has been misappropriated and
> disclosed. <deletions> In
> particular, RSA Data Security's RC2 (TM) symmetric block
> cipher source code has been illegally misappropriated and
> published. Please be advised that these acts, as well as
The anonymous poster (who presumably has not signed any trade secret
agreement with RSADSI) implicitly claims the source code was written
by him/her/it after reverse engineering an executable, so the source
code is not in any way a breach of trade secret agreement:
> * To commemorate the 1996 RSA Data Security Conference, the following *
> * code is released into the public domain by its author. Prost! *
<deletions>
> * Thanks to CodeView, SoftIce, and D86 for helping bring this code to *
> * the public. *
The only thing we can be certain of is that it cannot be the case that
both parties are telling the truth. Attributions of truth and falsehood
in the inevitable flame war will undoubtedly follow lines predictable
to any regular reader. Sadly we cannot simply reference the equivalent
debate on RC4 and do a global edit.
--
You cannot hope to bribe or twist/thank God! the British journalist.
But, seeing what the man will do/unbribed, there's no occasion to.
-- Humbert Wolfe 1886-1940
were...@io.org
>
>WARNING NOTICE
>
> It has recently come to the attention of RSA Data
>Security, Inc. that certain of its confidential and
>proprietary source code has been misappropriated and
Well I guess that answers the question as to how legitimate the posting
of the code was :>
============================================================
For PGP Public Key, Send E-Mail To: pgp-pub...@swissnet.ai.mit.edu
In Subject Line, type: GET WEREWOLF
PGP Fingerprint: 02 54 67 39 AE 86 2E 63 C4 83 EF 3F F1 6D 96 BB
============================================================
Tim Smith
>If a trade secret is revealed by an individual having contractual
>agreement with RSA, and a unrelated 3rd party uses that information,
>RSA cannot prosecute the 3rd party. Since they didn't patent the
I'd be careful with such sweeping statements. I seem to recall that in
at least some states, the 3rd party could be in trouble if the 3rd party
knew that the information was obtained inappropriately.
--Tim Smith
Tim Smith
>> Reverse engineering in Europe is not legal, it is a quite flagrant breach
>> of copyright. The European directive on software copyright does allow
>> 'reverse engineering' only to the extent of discovering a software interface
>> to allow interoperability. I think my interpretation is in line with
>By your logic European law would make it illegal to reverse engineer a
>virus to see how it works internally. Although malicious dissemination
>of computer viruses is illegal in the UK and possibly other places,
>AFAIK the copyright on the code still exists. Thus we end up with the
>interesting and disturbing idea that (European) manufacturers of
>anti-virus measures are law breakers should they develop their
>software by examining the target viruses rather than by divine
>revelation. (This may quite possibly be true, given the way our
But the antivirus manufacturer would be reverse engineering the virus in
order to discover how to make the antivirus program interoperate with the
virus, which would be allowed.
--Tim Smith
D. J. Bernstein
Tim Smith <t...@coho.halcyon.com> wrote:
> I'd be careful with such sweeping statements. I seem to recall that in
> at least some states, the 3rd party could be in trouble if the 3rd party
> knew that the information was obtained inappropriately.
Here we go again. (cat ~/News/rc4* | sed 's/RC4/RC2/g')
First, although it's _possible_ that the RC2 description was illegally
sent out by a disgruntled RSADSI licensee, the most _plausible_ scenario
is that it was reverse-engineered from published RC2 object code. In the
USA, at least, this is perfectly legal. So we have no reason to believe
that RC2 was obtained illegally.
Second, now that RC2 has been published, any state trade secret law that
tries to prevent further distribution will be preempted by federal
copyright law.
Third, RC2 has been generally available to the public for years; in most
states (e.g., CA) this means that it wasn't a trade secret anyway.
---Dan
Arthur Chance
I've always understood "interoperate" to mean "work with in a
harmonious and compatible fashion", rather than "eliminate from the
disk or prevent from operating by any means possible". Of course,
there's the way Microsoft's Internet software "interoperated" with
Netscape to back up your viewpoint. :-)
Olaf Titz
> sent out by a disgruntled RSADSI licensee, the most _plausible_ scenario
> is that it was reverse-engineered from published RC2 object code. In the
And some parts of the code don't look like a good C programmer would
write it that way. There's a distinct smell of automatically-generated
assembly language (look at the key scheduling function, and how the
expansion stuff could be collapsed into significantly less code).
olaf
--
___ Olaf...@inka.de or @{stud,informatik}.uni-karlsruhe.de ____
__ o <URL:http://www.inka.de/~bigred/> <IRC:praetorius>
__/<_ >> Just as long as the wheels keep on turning round
_)>(_)______________ I will live for the groove 'til the sun goes down << ____
luckyp...@gmail.com
> /**********************************************************************\
> * code is released into the public domain by its author. Prost! *
> * This cipher uses 16-bit words and little-endian byte ordering. *
> * I wonder which processor it was optimized for? *
> * *
> * the public. *
>
> #include <string.h>
> #include <assert.h>
>
> /**********************************************************************\
> * Expand a variable-length user key (between 1 and 128 bytes) to a *
> * 64-short working rc2 key, of at most "bits" effective key bits. *
> * The effective key bits parameter looks like an export control hack. *
> * For normal use, it should always be set to 1024. For convenience, *
> * zero is accepted as an alias for 1024. *
> \**********************************************************************/
>
> void rc2_keyschedule( unsigned short xkey[64],
> const unsigned char *key,
> unsigned len,
> unsigned bits )
> {
> unsigned char x;
> unsigned i;
> /* 256-entry permutation table, probably derived somehow from pi */
> static const unsigned char permute[256] = {
> 217,120,249,196, 25,221,181,237, 40,233,253,121, 74,160,216,157,
> 198,126, 55,131, 43,118, 83,142, 98, 76,100,136, 68,139,251,162,
> 23,154, 89,245,135,179, 79, 19, 97, 69,109,141, 9,129,125, 50,
> 189,143, 64,235,134,183,123, 11,240,149, 33, 34, 92,107, 78,130,
> 84,214,101,147,206, 96,178, 28,115, 86,192, 20,167,140,241,220,
> 18,117,202, 31, 59,190,228,209, 66, 61,212, 48,163, 60,182, 38,
> 111,191, 14,218, 70,105, 7, 87, 39,242, 29,155,188,148, 67, 3,
> 248, 17,199,246,144,239, 62,231, 6,195,213, 47,200,102, 30,215,
> 8,232,234,222,128, 82,238,247,132,170,114,172, 53, 77,106, 42,
> 150, 26,210,113, 90, 21, 73,116, 75,159,208, 94, 4, 24,164,236,
> 194,224, 65,110, 15, 81,203,204, 36,145,175, 80,161,244,112, 57,
> 153,124, 58,133, 35,184,180,122,252, 2, 54, 91, 37, 85,151, 49,
> 45, 93,250,152,227,138,146,174, 5,223, 41, 16,103,108,186,201,
> 211, 0,230,207,225,158,168, 44, 99, 22, 1, 63, 88,226,137,169,
> 13, 56, 52, 27,171, 51,255,176,187, 72, 12, 95,185,177,205, 46,
> 197,243,219, 71,229,165,156,119, 10,166, 32,104,254,127,193,173
> };
>
> assert(len > 0 && len <= 128);
> assert(bits <= 1024);
> if (!bits)
> bits = 1024;
>
> memcpy(xkey, key, len);
>
> /* Phase 1: Expand input key to 128 bytes */
> if (len < 128) {
> i = 0;
> x = ((unsigned char *)xkey)[len-1];
> do {
> x = permute[(x + ((unsigned char *)xkey)[i++]) & 255];
> ((unsigned char *)xkey)[len++] = x;
> } while (len < 128);
> }
>
> /* Phase 2 - reduce effective key size to "bits" */
> len = (bits+7) >> 3;
> i = 128-len;
> x = permute[((unsigned char *)xkey)[i] & (255 >> (7 & -bits))];
> ((unsigned char *)xkey)[i] = x;
>
> while (i--) {
> x = permute[ x ^ ((unsigned char *)xkey)[i+len] ];
> ((unsigned char *)xkey)[i] = x;
> }
>
> /* Phase 3 - copy to xkey in little-endian order */
> i = 63;
> do {
> xkey[i] = ((unsigned char *)xkey)[2*i] +
> (((unsigned char *)xkey)[2*i+1] << 8);
> } while (i--);
> }
>
> /**********************************************************************\
> * Encrypt an 8-byte block of plaintext using the given key. *
> \**********************************************************************/
>
> void rc2_encrypt( const unsigned short xkey[64],
> const unsigned char *plain,
> unsigned char *cipher )
> {
> unsigned x76, x54, x32, x10, i;
>
> x76 = (plain[7] << 8) + plain[6];
> x54 = (plain[5] << 8) + plain[4];
> x32 = (plain[3] << 8) + plain[2];
> x10 = (plain[1] << 8) + plain[0];
>
> for (i = 0; i < 16; i++) {
> x10 += (x32 & ~x76) + (x54 & x76) + xkey[4*i+0];
> x10 = (x10 << 1) + (x10 >> 15 & 1);
>
> x32 += (x54 & ~x10) + (x76 & x10) + xkey[4*i+1];
> x32 = (x32 << 2) + (x32 >> 14 & 3);
>
> x54 += (x76 & ~x32) + (x10 & x32) + xkey[4*i+2];
> x54 = (x54 << 3) + (x54 >> 13 & 7);
>
> x76 += (x10 & ~x54) + (x32 & x54) + xkey[4*i+3];
> x76 = (x76 << 5) + (x76 >> 11 & 31);
>
> if (i == 4 || i == 10) {
> x10 += xkey[x76 & 63];
> x32 += xkey[x10 & 63];
> x54 += xkey[x32 & 63];
> x76 += xkey[x54 & 63];
> }
> }
>
> cipher[0] = (unsigned char)x10;
> cipher[1] = (unsigned char)(x10 >> 8);
> cipher[2] = (unsigned char)x32;
> cipher[3] = (unsigned char)(x32 >> 8);
> cipher[4] = (unsigned char)x54;
> cipher[5] = (unsigned char)(x54 >> 8);
> cipher[6] = (unsigned char)x76;
> cipher[7] = (unsigned char)(x76 >> 8);
> }
>
> /**********************************************************************\
> * Decrypt an 8-byte block of ciphertext using the given key. *
> \**********************************************************************/
>
> void rc2_decrypt( const unsigned short xkey[64],
> unsigned char *plain,
> const unsigned char *cipher )
> {
> unsigned x76, x54, x32, x10, i;
>
> x76 = (cipher[7] << 8) + cipher[6];
> x54 = (cipher[5] << 8) + cipher[4];
> x32 = (cipher[3] << 8) + cipher[2];
> x10 = (cipher[1] << 8) + cipher[0];
>
> i = 15;
> do {
> x76 &= 65535;
> x76 = (x76 << 11) + (x76 >> 5);
> x76 -= (x10 & ~x54) + (x32 & x54) + xkey[4*i+3];
>
> x54 &= 65535;
> x54 = (x54 << 13) + (x54 >> 3);
> x54 -= (x76 & ~x32) + (x10 & x32) + xkey[4*i+2];
>
> x32 &= 65535;
> x32 = (x32 << 14) + (x32 >> 2);
> x32 -= (x54 & ~x10) + (x76 & x10) + xkey[4*i+1];
>
> x10 &= 65535;
> x10 = (x10 << 15) + (x10 >> 1);
> x10 -= (x32 & ~x76) + (x54 & x76) + xkey[4*i+0];
>
> if (i == 5 || i == 11) {
> x76 -= xkey[x54 & 63];
> x54 -= xkey[x32 & 63];
> x32 -= xkey[x10 & 63];
> x10 -= xkey[x76 & 63];
> }
> } while (i--);
>
> plain[0] = (unsigned char)x10;
> plain[1] = (unsigned char)(x10 >> 8);
> plain[2] = (unsigned char)x32;
> plain[3] = (unsigned char)(x32 >> 8);
> plain[4] = (unsigned char)x54;
> plain[5] = (unsigned char)(x54 >> 8);
> plain[6] = (unsigned char)x76;
> plain[7] = (unsigned char)(x76 >> 8);
> }
does this code work??
rossum
wrote:
>On Monday, January 29, 1996 1:30:00 PM UTC+5:30, Anonymous wrote:
>> /**********************************************************************\
>> * To commemorate the 1996 RSA Data Security Conference, the following *
>> * code is released into the public domain by its author. Prost! *
>> * *
>> * This cipher uses 16-bit words and little-endian byte ordering. *
>> * I wonder which processor it was optimized for? *
>> * *
>> * Thanks to CodeView, SoftIce, and D86 for helping bring this code to *
>> * the public. *
>> \**********************************************************************/
>>
>> ... snip ...
>> }
>
>does this code work??
Test it for yourself. There are test vectors at:
https://tools.ietf.org/rfc/rfc2268.txt
All quantities are given in hexadecimal notation.
Key length (bytes) = 8
Effective key length (bits) = 63
Key = 00000000 00000000
Plaintext = 00000000 00000000
Ciphertext = ebb773f9 93278eff
Key length (bytes) = 8
Effective key length (bits) = 64
Key = ffffffff ffffffff
Plaintext = ffffffff ffffffff
Ciphertext = 278b27e4 2e2f0d49
Key length (bytes) = 8
Effective key length (bits) = 64
Key = 30000000 00000000
Plaintext = 10000000 00000001
Ciphertext = 30649edf 9be7d2c2
Key length (bytes) = 1
Effective key length (bits) = 64
Key = 88
Plaintext = 00000000 00000000
Ciphertext = 61a8a244 adacccf0
Key length (bytes) = 7
Effective key length (bits) = 64
Key = 88bca90e 90875a
Plaintext = 00000000 00000000
Ciphertext = 6ccf4308 974c267f
Key length (bytes) = 16
Effective key length (bits) = 64
Key = 88bca90e 90875a7f 0f79c384 627bafb2
Plaintext = 00000000 00000000
Ciphertext = 1a807d27 2bbe5db1
Key length (bytes) = 16
Effective key length (bits) = 128
Key = 88bca90e 90875a7f 0f79c384 627bafb2
Plaintext = 00000000 00000000
Ciphertext = 2269552a b0f85ca6
Key length (bytes) = 33
Effective key length (bits) = 129
Key = 88bca90e 90875a7f 0f79c384 627bafb2 16f80a6f 85920584
c42fceb0 be255daf 1e
Plaintext = 00000000 00000000
Ciphertext = 5b78d3a4 3dfff1f1
rossum