|
|||
My first reaction to this was that there isn't any way that the value-space for the checksums can be larger than the value space for the clear packets, but that's not correct. Upon thinking about it further, I realized that you do the checksum backwards. To create a 20-bit checksum for a single bit, you create a checksum algorithm which converts that 20-bit value into a single bit (obviously parity would work but something better would be needed). Then when the clear bit is "1", you start selecting random 20 bit values and calculating their checksums until you get one which calculates a "1" and that's what you use. On the next bit if you again need a checksum for "1" you pick a new 20-bit value and again keep doing so until you find one which calculates a "1". For chaff bit of "1" you'd check random 20-bit values until you found one which calculated to '0" (i.e. to the wrong value). What you end up with, then is a big list of ordered pairs, one member of which gives the right answer and one which gives the wrong answer. Could this then be used as a means of searching an algorithm-space, since any algorithm which generates the same answer for both members of any pair in the entire message is obviously wrong? I fear that entirely too much information about the cipher itself is included in the message mixed in with the clear and chaff bits. On the other hand, if the clear sequences are longer this adds a double problem. First, if for example the clear sequences are 10 bits long then it means that randomly checking longer checksums backwards lowers the chance of a hit. On average you'd need to check 512 potential checksums to find one that worked, if the checksums are longer than the clear sequences. If the checksums are equal or shorter, then either you need to use long clear sequences or you face a substantial risk of false positives on the decipher. Once the clear sequences become substantial in length, it may be possible to use statistical analysis of their entropy to differentiate meaningful ones from meaningless ones. May I propose a different form? It would remain a symmetric cipher, which means that a key would have to be communicated between the parties. Both parties agree ahead of time to a random number generation algorithm (which is not secret) which uses an N-bit seed. They then agree ahead of time to N-M bits for the seed, with M being a number on the order of 24 (i.e. the seed is 256 bits and 232 are agreed to ahead of time as the secret key; 24 bits are reserved). If one party wishes to send a message to the other, he selects a rising sequence number of M bits in length and plugs it along with the agreed upon key into the random number generator. Half the number space of "M" would be reserved for one guy and half for the other. (Probably one guy always sets the high bit to 0 and the other guy sets it to 1. It's critically important that no value is ever reused.) This is then used to generate a bit mask, which would presumably be approximately half 1's and half 0's and would be about twice as long as the clear to be sent. Then he plugs in a bit of clear for every "1" in the mask and a random bit for every "0". (So the generated mask length would need to be long enough so that its population of 1's was as long as the clear message to be sent.) The message begins with the selected number (of M bits, which need not be secret) followed by the resulting spread bit sequence. The receiver plugs that number in along with the secret key, regenerates the mask, extracts out and concatanates the critical bits (correlating to 1's in the mask) and discards the others. The communication overhead is just slightly over 50%, which is far more efficient than the algorithm proposed by Rivest, whose overhead is anywhere from 3:1 to 100:1, and this algorithm is computationally efficient, scaling linearly with the length of the clear. If the random number generator is chosen well, then the only attack is brute force to try to guess the secret bits of the seed. If even one of those bits is guessed wrongly, then the resulting bit mask will be about 50% wrong, yielding about 50% true bits and 50% trash bits at random -- which makes it useless. There won't be any near misses. Since the spreading is bit-wise, there's no way to do a statistical analysis of entropy. So the attack would have to be exhaustive search, and since the seed for the random number generator can be arbitrarily large the cipher could be made arbitrarily strong. This cipher has two advantages over the one Rivest proposes; Rivest's cipher is either horribly inefficient in communication overhead or it is inefficient in calculation. My cipher is reasonably efficient at both simultaneously while being no less secure. But there's really no point in doing either of them. They are inefficient the way steganography is at transmission time, but without the advantage of being surreptitious, and they are at best no more secure than existing ciphers while being less efficient in communications bandwidth. They combine the worst features of both. The only possible advantage e 
| |||