Improving RC4 (MC1 cipher proposal)

[encode]

A few ideas of mine about improving this stream cipher:

Instead of an 8-bit S-box use a 16-bit one. And if we need a byte output, we may apply x&255, or x>>8 to the algorithm output. For key shedule we may use a Unicode string, or a transformed string to affect more bytes at S-Box.

Ulimited password length. We may call it even passphrase. Password can be longer than S-box.

Use password length in key shedule. As example we may Swap the S-Box items according to the password length - adding the length before/after actual password (a la Pascal string)

Drop first N bytes of a keystream according to a password. i.e. not just a fixed number of bytes, say 10000. But some number that will be generated according to a password - say a special hash function, defining a valid range, say, between 5000 to 100000.

Only expert answers please. No flame.

[Shelwien]

1. Depending on actual implementation, this might be risky. I mean, you have to be more careful when randomizing a larger table by permutations.
2. I don't see how your ideas really make it stronger - you might get a slow initialization though.
3. One trick which may be useful is adding random bytes at the start of (preferably, compressed) data - with that plaintext attacks become harder (ie password bruteforce).
4. Unmodified standard algorithms are only necessary for government certification and such (because they've already passed some expensive analysis).
But when you don't have much users, most cryptoalgorithms would work the same - nobody would try to crack them anyway.

[encode]

ENT on RC4-drop10000:

Entropy = 8.000000 bits per byte.
Optimum compression would reduce the size
of this 1073741824 byte file by 0 percent.
Chi square distribution for 1073741824 samples is 253.42, and randomly
would exceed this value 51.62 percent of the times.
Arithmetic mean value of data bytes is 127.4998 (127.5 = random).
Monte Carlo value for Pi is 3.141485397 (error 0.00 percent).
Serial correlation coefficient is 0.000032 (totally uncorrelated = 0.0).

on my version:

Entropy = 8.000000 bits per byte.
Optimum compression would reduce the size
of this 1073741824 byte file by 0 percent.
Chi square distribution for 1073741824 samples is 259.87, and randomly
would exceed this value 40.37 percent of the times.
Arithmetic mean value of data bytes is 127.5005 (127.5 = random).
Monte Carlo value for Pi is 3.141485978 (error 0.00 percent).
Serial correlation coefficient is -0.000044 (totally uncorrelated = 0.0).

SO, not sure about that this WORD stuff really works. We should find other ways to make internal state more complex. Some fellas modified RC4 adding two independed S-Boxes (RC4A) this thing helped but not that much, algorithm was broken either.

[Shelwien]

Btw, did you try compressing it with paq8 (the key sequence)? (especially paq8k,k2)
In theory, good compressors should give a better measure of randomness than simple statistical tests.
Unfortunately, there's no (known) really precise model for that (my bit_guess maybe, but it lacks contexts).
But its only a technical problem, the theory should be the same as with paq.

[encode]

Test keystreams was 1 GB long. Even classic RC4 has long enough period that PAQ* will never catch, but distinguishers and special attacks will catch. Anyway, compressing 1 GB file with PAQ8K is just crazy idea, such PAQ version is ultimately slow.

[Shelwien]

Erm, its not about catching the period, but other correlations.
For example: http://encode.su/threads/1088-Someti...ll=1#post21694
So with simple functions, its often possible to detect indirect correlations, even if the best context is completely different.

Anyway, I don't see why you can't try paq8 on 1Mbytes of the key or something.

[encode]

Anyway, I don't see why you can't try paq8 on 1Mbytes of the key or something.

I do. And I see how a good password is important for RC4.

[Shelwien]

Why don't you post some stats?

[encode]

Have no time - I'm under brainstorm on new software...

[encode]

VMPC is cool RC4 modification.

Firstly, we do an improved KSA:

for (i=0; i<256; ++i)
  s[i]=i;
j=0;
for (i=0; i<768; ++i) { // Three times 256 
  j=s[(j+s[i&255]+key[i%keylen])&255];
  Swap(s[i&255], s[j]);
}

Along with the key (password or password hash) we may use IV.

And actual VMPC (Variably Modified Permutation Composition) stuff:

i=0;
// ...
// The loop:
j=s[(j+s[i&255])&255];
output=s[(s[s[j]]+1)&255];
Swap(s[i&255], s[j]);
++i;

[Matt Mahoney]

4. Unmodified standard algorithms are only necessary for government certification and such (because they've already passed some expensive analysis).
But when you don't have much users, most cryptoalgorithms would work the same - nobody would try to crack them anyway.

I don't care about government certification but I would prefer standard algorithms anyway because I know lots of people have tried to break them and failed. There really is no other way to test security.

RC4 has some known weaknesses. http://en.wikipedia.org/wiki/RC4#Security
But how do I know that these changes fix the weaknesses and don't introduce new ones?

[encode]

RC4 has some known weaknesses. http://en.wikipedia.org/wiki/RC4#Security
But how do I know that these changes fix the weaknesses and don't introduce new ones?

The code I provided well known, and even broken (VMPC, RC4A). I have a few additional ideas. Finally I will post a program along with the source, so anyone will able to test and try to break it.

The program will use RC4/VMPC modification. Instead of a plain password string or IV, ot will use a hash (PRNG) that will be update char-by-char from password:

hash(key[i%keylen]);

// and the hash is something like this:
DWORD hash=-1; // or 0 or some value
DWORD Hash(int c) {
return (hash=(hash^c)*123456791)>>24;
};

Also, at KSA we will do not 256 or 256*3, but, say, 1000 or even more swaps/loop iterations. Of course the first 10000 (or so) first keystream bytes will be discarded.

And of course in main loop we will do the VMPC srtuff...

[Matt Mahoney]

I assume that s is unsigned char s[256]. (Otherwise code won't work, and higher elements and bits are never used).

Also, why output=s[(s[s[j]]+1)&255]; ? Why is this more secure than s[(s[i]+s[j])&255] ?

Original RSA allows a 256 byte key which is plenty. If you want to include the length of the key, then just include the null byte at the end, which is allowed by the original RC4. If you want to increase the hashing of the key, then you get the same effect by throwing away the beginning of the key stream, which you should do anyway.

Does your code remove the bias that appears in RC4 after 1 GB or so? What about XOR of 2 RC4 streams with different keys?

[encode]

Also, why output=s[(s[s[j]]+1)&255]; ? Why is this more secure than s[(s[i]+s[j])&255] ?

Some info:
http://www.vmpcfunction.com/function.htmand
http://www.vmpcfunction.com/

Original RSA allows a 256 byte key which is plenty. If you want to include the length of the key, then just include the null byte at the end, which is allowed by the original RC4.

Good idea, BTW!

If you want to increase the hashing of the key, then you get the same effect by throwing away the beginning of the key stream, which you should do anyway.

Probably, you're right! But, if our password is a key, then it's bytes are too limited (ASCII - >31 ... <12, simple data dependent PRNG can help here. Anyway, all that assumptions and ideas under testing. Currently I'm also finding different ways to test a keystream. Along with ENT program or compressing it with PAQ8K...

Does your code remove the bias that appears in RC4 after 1 GB or so? What about XOR of 2 RC4 streams with different keys?

My code under heavy testing... But original VMPC is notable better than RC4. Two RC4 streams is roughly the same as RC4A, which is apparently the strongest RC4 modification to date (according to some papers, although VMPC is much better than original RC4, it is still not that good as RC4A).

[encode]

BTW, check out some paper on RC, RC4A and VMPC: