Results 1 to 15 of 15

Thread: Improving RC4 (MC1 cipher proposal)

  1. #1
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts

    Lightbulb Improving RC4 (MC1 cipher proposal)

    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.

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,422
    Thanks
    222
    Thanked 1,051 Times in 564 Posts
    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.

  3. #3
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    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.

  4. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,422
    Thanks
    222
    Thanked 1,051 Times in 564 Posts
    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.

  5. #5
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts

    Lightbulb

    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.

  6. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,422
    Thanks
    222
    Thanked 1,051 Times in 564 Posts
    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.

  7. #7
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Quote Originally Posted by Shelwien View Post
    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.

  8. #8
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,422
    Thanks
    222
    Thanked 1,051 Times in 564 Posts
    Why don't you post some stats?

  9. #9
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Have no time - I'm under brainstorm on new software...

  10. #10
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    VMPC is cool RC4 modification.

    Firstly, we do an improved KSA:
    Code:
    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:
    Code:
    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;

  11. #11
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    Quote Originally Posted by Shelwien View Post
    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?

  12. #12
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts

    Cool

    Quote Originally Posted by Matt Mahoney View Post
    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...

  13. #13
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    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?

  14. #14
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Quote Originally Posted by Matt Mahoney View Post
    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/

    Quote Originally Posted by Matt Mahoney View Post
    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!

    Quote Originally Posted by Matt Mahoney View Post
    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...

    Quote Originally Posted by Matt Mahoney View Post
    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).

  15. #15
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    BTW, check out some paper on RC, RC4A and VMPC:
    Attached Files Attached Files

Similar Threads

  1. Simple encryption (RC4 like)
    By encode in forum Forum Archive
    Replies: 37
    Last Post: 26th January 2008, 04:05

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •