A poorman's stream encryption algorithm
in [Cryptography]
|
From: unruh on 25 Mar 2010 13:25 On 2010-03-25, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: > unruh wrote: > >> The swap rules ( two lines of code) of rc4 are a lot easier to remember >> than any reasons for those rules. Some things are far easier to just >> memorize. Your "rules" for your complicated mess have no unique >> implimentation so you have to memorize a bunch of pretty complicated >> stuff. >> And what in the world is this "word" stuff? If you really want to >> impliment RC4 on words you just need a 60000 entry mixing matrix. And >> some have argued that this is less biased than is the simply RC4. > > Since I found the scheme of RC4 to be fairly nice, I once thought of > the its generalization to 16 bits. However, besides the issue of the > large matrix you mentioned, I suppose one should also consider what > the swapping operation should be in that case. Apparently doing only > one swapping of two elements as in the case of 8 bits would seem to be > farily insufficient. But how many times and which pairs to pick for > swapping to achieve optimal results? It was from here that I asked > myself the already mentioned question of mine concerning the rationale > of the particular swapping in RC4. I stronly surmise that RC4's success > is at least in part due to the good choice of the swapping operation, > but unfortunately we don't know the excellent and ingeneous insight of > its author in that issue. AFAIK, there is nothing wrong with the current swapping function, except that for the the first X operations, the regular initial setup of the matrix creates biases. That is why you should throw away the first X outputs ( where X is something like 16, or 200 to play it safe). Exactly what X is for the 2^16 bit RC4 I do not know. but it is liable to be large. One could always hash the password, and use that to populate the matrix "randomly" instead of the well ordered initial population it now uses. But I have no idea why you want to extend it to "words" anyway. AFAIK it buys you nothing except slowness and implimentation complexity. Two ( or 4) bytes IS a word, so you just run RC4 4 times to get a word. > > Thanks, > > M. K. Shen
From: Mok-Kong Shen on 25 Mar 2010 15:09 unruh wrote: > AFAIK, there is nothing wrong with the current swapping function, except > that for the the first X operations, the regular initial setup of the > matrix creates biases. That is why you should throw away the first X > outputs ( where X is something like 16, or 200 to play it safe). Exactly > what X is for the 2^16 bit RC4 I do not know. but it is liable to be > large. One could always hash the password, and use that to populate the > matrix "randomly" instead of the well ordered initial population it now > uses. But I have no idea why you want to extend it to "words" anyway. > AFAIK it buys you nothing except slowness and implimentation complexity. > Two ( or 4) bytes IS a word, so you just run RC4 4 times to get a word. But do you consider it is sufficient to do one single swapping of two elements in the 16-bit case, when one output is created, as is done in the 8-bit case? (For the percentage change would be comparatively tiny.) I became interested in the 16-bit case, because I surmise (I might be wrong, of course, I don't know) that for a similar 16-bit case the period would be very greately increased. Thanks, M. K. Shen
From: Maaartin on 25 Mar 2010 17:55 > But do you consider it is sufficient to do one single swapping of > two elements in the 16-bit case, when one output is created, as is done > in the 8-bit case? (For the percentage change would be comparatively > tiny.) That's true, but is there a better way? You need 2**16 memory writes, so you could do only a small factor better, whatever you try. You simply need to do a lot of shuffling at the beginning. > I became interested in the 16-bit case, because I surmise (I > might be wrong, of course, I don't know) that for a similar 16-bit > case the period would be very greately increased. The period? I've just found "The random permutation that implements RC4 is likely to have a period larger than 10**100". Do you need more? I wrote "The speed on general purpose CPUs may be in fact lower than when using 8 bits - you obviously win a factor of 2 but may get a lot of L1 cache misses." but I was thinking about the 16-bit variant using 64kB memory, which is wrong by a factor of 2. The L1 cache of my processor is 64kB, so there'd be (under this wrong assumption) only a few cache misses when the only thing the CPU is doing was encryption. With 128kB needed, you get a cache miss every second memory access, which makes it slower than the 8-bit variant. > Not impossible, but having a 4GB matrix will definitely produce caching > missing every time. Just a nit pick: 16GB which is a problem for most computers. On my computer it would mean getting 4 bytes every couple of milliseconds.
From: unruh on 25 Mar 2010 18:00 On 2010-03-25, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: > unruh wrote: > >> AFAIK, there is nothing wrong with the current swapping function, except >> that for the the first X operations, the regular initial setup of the >> matrix creates biases. That is why you should throw away the first X >> outputs ( where X is something like 16, or 200 to play it safe). Exactly >> what X is for the 2^16 bit RC4 I do not know. but it is liable to be >> large. One could always hash the password, and use that to populate the >> matrix "randomly" instead of the well ordered initial population it now >> uses. But I have no idea why you want to extend it to "words" anyway. >> AFAIK it buys you nothing except slowness and implimentation complexity. >> Two ( or 4) bytes IS a word, so you just run RC4 4 times to get a word. > > But do you consider it is sufficient to do one single swapping of > two elements in the 16-bit case, when one output is created, as is done > in the 8-bit case? (For the percentage change would be comparatively > tiny.) I became interested in the 16-bit case, because I surmise (I > might be wrong, of course, I don't know) that for a similar 16-bit > case the period would be very greately increased. Period? I guess I would not worry about 2^(2^11). > > Thanks, > > M. K. Shen >
From: Mok-Kong Shen on 26 Mar 2010 05:07
unruh wrote: >> But do you consider it is sufficient to do one single swapping of >> two elements in the 16-bit case, when one output is created, as is done >> in the 8-bit case? (For the percentage change would be comparatively >> tiny.) I became interested in the 16-bit case, because I surmise (I >> might be wrong, of course, I don't know) that for a similar 16-bit >> case the period would be very greately increased. > > Period? I guess I would not worry about 2^(2^11). I still miss your answer to my question of how many swaps need to be optimally done. M. K. Shen |