Discussion:
SC1 stream cipher as a free alternative to ARCFOUR/RC4
(too old to reply)
Franz Scheerer
2004-06-17 13:33:44 UTC
Permalink
Raw Message
I designed a stream cipher comparable to ARCFOUR. Like in ARCFOUR a pseudo
random bit sequence is xor-ed with the input stream. Encryption work exactly
like decryption. The only difference to ARCFOUR is the PRNG.

My idea is to provide a freely available cipher without any trademark or
patent at least as secure as ARCFOUR, which can be implementated with a few
lines of code using almost every programming language.

The PRNG is based on CRC-32. It uses a 256-bit key. The key is padded by 0xF0,
0xF0, ...

random-sequence = CRC-32(key),CRC-32(key,key'),CRC(key,key',key''), ...

key' isobtained by replacing 4 Bytes from key (offset = 0,1,..251,0,1 bytes)

The state of the PRNG are the 256 byte = 2048 bit of the key value (changed in
4 bytes each iteration) and the current 32 bit output from CRC-32
calculation. The period length is therefore expected to be about 2^2080.

Regards

Franz Scheerer (http://www.scheerer-software.de/sc1.html)

C-Implementation:

#include <stdio.h>
#include <string.h>

void make_crc_table(void);
unsigned long update_crc(unsigned long crc, unsigned char *buf, int len);
int sc1(unsigned char *keyString, char * fnam, char *fnam_out);


/* Table of CRCs of all 8-bit messages. */
unsigned long crc_table[256];

/* Flag: has the table been computed? Initially false. */
int crc_table_computed = 0;

/* Make the table for a fast CRC. */
void make_crc_table(void)
{
unsigned long c;
int n, k;
for (n = 0; n < 256; n++) {
c = (unsigned long) n;
for (k = 0; k < 8; k++) {
if (c & 1) {
c = 0xedb88320L ^ (c >> 1);
} else {
c = c >> 1;
}
}
crc_table[n] = c;
}
crc_table_computed = 1;
}

unsigned long update_crc(unsigned long crc, unsigned char *buf, int len)
{
unsigned long c = crc ^ 0xffffffffL;
int n;

if (!crc_table_computed) make_crc_table();
for (n = 0; n < len; n++) {
c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
}
return c ^ 0xffffffffL;
}

void printHelp(){
printf("\n\nStream Cipher Version 1.0 (sc1) - "
"Copyright (c) Scheerer Software 2004\n\n");
printf("usage: sc1 <filename_in> <filename_out> <password>\n");
printf(" if you need more help see http://www.scheerer-software.de\n");
printf(" or send a mail to ***@scheerer-softwre.de\n");
}

int sc1(unsigned char *keyString, char *fnam, char *fnam_out){
FILE *fp;
FILE *fp_out;
unsigned char key[256];
int len,i;
int val, lc, cnt;

memset(key, 0xF0, sizeof(key));
len = strlen(keyString);
if (len<8) {
printf("ERROR key too short (8-256 byte) \n");
exit(-1);
}
if (len>sizeof(key)){
printf("WARNING: key too long (8-256 byte) is truncated \n");
len = sizeof(key);
}
memcpy(key, keyString, len);

if ( !(fp = fopen(fnam,"rb")) ){
fprintf(stderr, "ERROR *** open file %s \n",fnam);
printHelp();
exit(-1);
}
if ( (fp_out = fopen(fnam_out,"rb")) ){
fprintf(stderr, "ERROR *** file %s already exists\n",fnam_out);
printHelp();
exit(-1);
}
if ( !(fp_out = fopen(fnam_out,"wb")) ){
fprintf(stderr, "ERROR *** open file %s \n",fnam_out);
printHelp();
exit(-1);
}
cnt=0; lc=0;
while ((len = fread(&val,1,4,fp))>0){
lc = update_crc(lc, key, sizeof(key));
val ^= lc;
fwrite(&val,len,1,fp_out);
memcpy(key+cnt, &lc, 4);
cnt = (cnt+1)%252;
}
printf("wrote file %s\n",fnam_out);
fclose(fp);
fclose(fp_out);
}

main(int argc, char **argv){
if (argc<4){
printHelp();
} else {
sc1(argv[3], argv[1], argv[2]);
}
}
Gregory G Rose
2004-06-18 02:37:13 UTC
Permalink
Raw Message
Post by Franz Scheerer
The PRNG is based on CRC-32. It uses a 256-bit key. The key is padded by 0xF0,
There are (at least) two problems with this.

It's entirely linear, so key bits can be recovered
using gaussian reduction from any known plaintext.

The way you use more and more of the key as you
get further into the stream makes it a sucker for
divide-and-conquer attacks. Basically, ignoring
the fact that you can derive the key, you can
attack it by guessing the key 32 bits at a time,
for a total complexity of 8*2^32, not 2^256.

Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
David Wagner
2004-06-19 05:50:14 UTC
Permalink
Raw Message
I designed a stream cipher comparable to ARCFOUR. [...]
The PRNG is based on CRC-32. It uses a 256-bit key. The key is padded by 0xF0,
0xF0, ...
random-sequence = CRC-32(key),CRC-32(key,key'),CRC(key,key',key''), ...
key' isobtained by replacing 4 Bytes from key (offset = 0,1,..251,0,1 bytes)
[...]
while ((len = fread(&val,1,4,fp))>0){
lc = update_crc(lc, key, sizeof(key));
val ^= lc;
fwrite(&val,len,1,fp_out);
memcpy(key+cnt, &lc, 4);
cnt = (cnt+1)%252;
}
1. This cipher looks likely to be quite slow, slower than accepted
modern ciphers (such as AES-CTR).

2. The cipher seems to be totally insecure. Everything in sight is
completely linear. In particular, every bit of output is a known linear
function of the key. Therefore, if I obtain 256 bits of known keystream
(e.g., in a known-plaintext attack), I obtain 256 linear equations in
256 unknowns, and I can use linear algebra to recover the key and
decrypt everything else encrypted with that key. If I did not make
any mistakes, that's an unacceptable vulnerability; modern ciphers don't
share this kind of weakness.

Loading...