[Next] [Up] [Previous] [Index]

From 45 bits to a Permutation of 16 Items

A rotor machine produces a different alphabet for each letter enciphered. Most stream ciphers operating on binary data merely produce an output of bits which are simply XORed with the plaintext to produce ciphertext. Such systems are vulnerable to a 'bit-flipping' attack, and thus precautions need to be taken to authenticate messages.

One way to provide a cipher with intrinsic protection against this is noted here; obviously, using a different alphabet for the encoding of each symbol would also accomplish this. More importantly, an attacker in posession of a quantity of ciphertext and corresponding known plaintext would now only have limited information about the output of a stream cipher that generated permutations rather than values.

However, a cipher scheme designed specifically to generate permutations might be too simple, or have its own weaknesses. Could the output of a binary keystream generator be converted easily to a series of permutations?

Let's try to produce small permutations.

A permutation of 16 items, suitable for encrypting one nybble of a stream of binary data, can have any of

16! = 16 * 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2

possible values. How many bits are required to specify such a permutation?

If we squeeze out all the factors of two, which can be produced directly from bits, so as to minimize the amount of arithmetic coding that needs to be done, we get:

16! =  1 * 15 *  7 * 13 *  3 * 11 *  5 * 9 * 1 * 7 * 3 * 5 * 1 * 3 * 1
    * 16 *  1 *  2 *  1 *  4 *  1 *  2 * 1 * 8 * 1 * 2 * 1 * 4 * 1 * 2
or
16! = 638,512,875
    * 2^15

Unfortunately, 2^30 is 1,073,741,824, which is not very close to the remaining part of this. However, one can still generate permutations relatively efficiency by using the methods noted in the section on Keystream Base Conversion; after taking 15 bits to decide the exact binary portion of the permutation, then take 30 bits to produce a number from 0 to 1,073,741,823. If that number is from 0 to 638,512,874, one's work is done. If it has one of the 435,228,949 values from 638,512,875 to 1,073,741,823, then take one more bit, and so on.

Since there is quite a bit of elbow room, however, it might be worth investigating if the number 638,512,875 should be left split up into its factors, so that only arithmetic on smaller numbers is required.

Thus, 9 * 7 is 63, one less than 64, so one could use 6 bits of a starting 45-bit value to obtain the values for those items. 5 * 5 * 5 is 125, not much less than 128.

16! = 16 * 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2
    = 16 *  1 *  2 *  1 *  4 *  1 *  2 * 1 * 8 * 1 * 2 * 1 * 4 * 1 * 2
       *         *         *         *       *       *       *       *
       *                   *                 *               *
       *                                     *
       *
    *      15 *  7 * 13 *  3 * 11 *  5 * 9 *     7 * 3 * 5 *     3
    = 2^15
    *       3 *  7 *       3 *           9 *     7
    *       5 *                      5 *                 5
    *                13 *      11 *                  3 *         3
    = 2^15
    * 63 * 63
    * 125
    * 1287

The last few factors still don't tie up too neatly. Take 45 bits, then, use 15 for the factors of two; two groups of 6, if they have values from 0 to 62, are usable, and only have to be replaced with a new one if the value is 63; one group of 7 is usable if its value is from 0 to 124, with the values 125 through 127 being unusable. This consumes a further 19 bits, so we have 34 bits; the remaining 11 bits have 2048 possible values; so we haven't really lost anything by this simplification.

If each of the remaining factors was handled independently: two bits for each 3, four bits for the 11 and the 13, we would lose a bit. But 9 * 13 is 117, which consumes seven bits, leaving four bits for the 11, so we can split up 1287 to an extent.

Thus, using a 128-bit block cipher in a form of cipher feedback mode, one could do the following:

Incomplete cipher feedback is known to have weaknesses, however, these should not be applicable to this kind of encryption.

This mode, however, does not have good error-propagation characteristics. Always using, for the next shifted feedback step, the original output of the block cipher, not, as described above, the output of the last unshifted feedback step if any are required, although it might seem to improve them, actually does not change what has to be done to recover from an error; all the other possible values for the first erroneous nybble have to be tried until the plaintext once again makes sense from that point. Thus, output feedback, counter mode, or a combination of the two is needed, but after 128 bits are enciphered, then that expanse of ciphertext can be fed back all at once while retaining the ability to recover easily from errors.


[Next] [Up] [Previous] [Index]

Next
Table of Contents
Home Page