A poorman's stream encryption algorithm
in [Cryptography]
|
From: David Eather on 24 Mar 2010 16:32 On 25/03/2010 3:49 AM, unruh wrote: > On 2010-03-24, Maaartin<grajcar1(a)seznam.cz> wrote: >> On Mar 24, 5:02?pm, unruh<un...(a)wormhole.physics.ubc.ca> wrote: >>> 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. >> >> You surely means word = 16 bits, this is quite common (Intel and > > Yes, so that requires a mixing matrix of 2^16 entries, which is approx > 60000. Um 2^16 entries 2^17 bytes (131072 bytes) - just a nit pick > >> Microsoft use it this way), but others (IMHO including MKS) use it to >> denote the most natural (efficient) unit of CPU. Expanding RC4 to 16 >> bits has at least two drawbacks: The initial mixing needs to be much >> longer, so the overhead for short messages is too high. The speed on > > Agreed. >> 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. >> AFAIK, expanding RC4 to 32 bits is quite impossible. > Not impossible, but having a 4GB matrix will definitely produce caching > missing every time. (And running the initial mix to get rid of the small > initial biases will take a while, I agree). > > > >> >> That said, I fully agree with you (and state that you surely know much >> more about the subject than I do). >> >> MKS: Do you think your description is easy to memorize and to >> implement? Assume there're 10 people implementing what you described >> here, how many different implementation do you get? One? Ten? > >
From: Jonathan on 24 Mar 2010 20:30 On Mar 21, 7:15 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > The scheme to be described processes the plaintext P[*] (in units of > computer words) in a user-chosen number of rounds. Each round consists > of two passes, one going in the forward and the other in the backward > direction, increasing the length of the result by one word in each pass. > We assume the availability of a PRNG, whose "current" outputs are > denoted by R below, i.e. different occurences of R are not of identical > values. (For a proposed PRNG of mine, see the thread "Update of my old > idea on random number generation" of 20.03.2010). We explain only the > encryption of a forward pass of a round (input="plaintext", > output="ciphertext"), for the backward pass is quite similar. The > function NLC(x,y) denotes a nonlinear combination of x and y. (For a > proposed NLC of mine, see the thread "Nonlinear combination of streams" > of 13.03.2010, for it's result plausibly contains more "entropy" than > either x or y.) > > h = R; > > for (i=0; i<plaintextlength; i++) > { > C[i] = P[i] ^ h ^ R; > h = NLC(h, C[i]); > } > > C[plaintextlength] = h ^ R; > > C[plaintextlength], the additional element created, can serve the > purpose of authentication. A viable variant is using h = NLC(h, P[i]); > Of course, one could choose, if one likes, to employ only one single > (forward) pass and do nothing no more. > > Note that there is unfortunately a little inconvenience in decryption. > For all the R's that will be needed have to be computed and stored > before the decryption process begins (an exception is the case with one > single pass only, mentioned above). > > Thanks, > > M. K. Shen > ------------------------------------------------------------------------------------ > > PS: I personally consider classification of ciphers to be no more than > of secondary importance. Please don't blame me, if you deem the scheme > should properly belong to block, instead of stream, algorithms. Certainly an interesting approach to a basic encryption system. The system I developed 25 years ago on the BBC Micro was comparable and I'd love to see how the two methods stand up against each other in terms of actual strength and/or performance. The method I developed was simple enough. You have a 64-bit key, which is converted into 4 16-bit keys. The first key is used to seed the PRNG. The first byte read from the PRNG is the number of bytes to be encrypted using this PRNG setup. Each subsequent byte from the PRNG is XORed with the input stream. Once you reach the end of the block, you read a new 16-bit number and replace the first key. You then use the second key for another random-length block, and so on until all four keys are used and replaced. You then repeat the whole process with the new keys. This continues until all data is read and encrypted. The process then stops. This means that for short input streams, there is a possibility that not all of the original key is used. There is a heavy reliance on the random size of the block (which can potentially be zero bytes) to effectively hide which keys are used where. A later version used additional random data to alter behaviour - for example, reversing the bytes in a block, swapping alternative bytes, etc. The idea was that it wasn't going to be hard to plough through all of the possible key values for a block, but if you didn't then know how to read the data, you would have a hard time knowing if you got the right key. Compared to modern crypto methods, the method I used was childishly simple. In fact, I was a child at the time so this is very understandable. I certainly wouldn't consider it secure and wouldn't dream of pitting it against any serious crypto method by any real crypto expert. However, it would be very interesting to compare it to other trivial crypto systems that use methods not vastly different.
From: Mok-Kong Shen on 25 Mar 2010 09:35 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. Thanks, M. K. Shen
From: Mok-Kong Shen on 25 Mar 2010 09:35 Maaartin wrote: > MKS: Do you think your description is easy to memorize and to > implement? Assume there're 10 people implementing what you described > here, how many different implementation do you get? One? Ten? My opinion is unevitably "subjective". Since you asked, I would nonetheless answer Yes. For in my scheme of compound PRNG there is practically nothing "special" at all to be memorized. The only thing is the criteria for achieving full cycle of the permutation polynomials. But that is so "regular" in form that it should be trivial to have it long time being kept in memory without fear of deterioration. Everting else is just either "simple" knowledge from school or computer programming (concept of a polynomial, modulo math, Horner's scheme, applying a bit mask, cyclical bit-shift). So, given a choice, my "personal" perference is clear. Certainly many stuffs could be memorized, if one has the will. I school I did not too poorly in the task of learning by heart some passages from books of ancient philosophers and reproducing these in class on paper. Once I even saw a spetacular demostration, in which the exhibitor could tell for any arbitrarily chosen day in the past 10 years from the audience the headlines of a local newspaper on that day. But I have to once again stress the probability of my "subjectivity" in the above. (There is a saying in Asia that one's own writings are the best and wives of other people are more beautiful :) ) Thanks, M. K. Shen
From: Mok-Kong Shen on 25 Mar 2010 09:35
Jonathan wrote: [snip] > The method I developed was simple enough. You have a 64-bit key, which > is converted into 4 16-bit keys. The first key is used to seed the > PRNG. The first byte read from the PRNG is the number of bytes to be > encrypted using this PRNG setup. Each subsequent byte from the PRNG is > XORed with the input stream. Once you reach the end of the block, you > read a new 16-bit number and replace the first key. You then use the > second key for another random-length block, and so on until all four > keys are used and replaced. You then repeat the whole process with the > new keys. This continues until all data is read and encrypted. The > process then stops. This means that for short input streams, there is > a possibility that not all of the original key is used. There is a > heavy reliance on the random size of the block (which can potentially > be zero bytes) to effectively hide which keys are used where. Thank you for telling your design. As to comparison I am unfortunately not in a position to do and have to leave it to the experts, since my knowledge is poor, expecially on issues of analysis. Thanks, M. K. Shen |