PUBLISHED: Ritter, T. 1991. Transposition Cipher with Pseudo-Random Shuffling: The Dynamic Transposition Combiner. Cryptologia. 15(1):1-17.
ADDRESS: Blue Jean Software, 2609 Choctaw Trail, Austin, Texas 78745.
ABSTRACT: Extensions are made to a class of transposition cipher based on continued shuffling. These ciphers permute plaintext into ciphertext by swapping every message element with some message element selected at pseudo-random; elements can be characters (e.g., bytes) or bits.
Extensions include operation on very large data blocks, cryptographic shuffling variations, and the efficient extraction of plaintext from ciphertext. In addition, selected extra data can be adjoined to the plaintext to eliminate the data-dependent weak encipherings otherwise inherent in transposition. This bit- balancing data is supposed to completely eliminate all normal usage-frequency statistics from bit-transposition ciphertext.
The same mechanism can also be viewed as a cryptographic combiner, and, with sequence-to-block and block-to-sequence conversions, can generally replace the exclusive-OR combining function used in Vernam stream ciphers.
KEYWORD LIST: cryptography, computer cryptography, cipher, block cipher, permutation, transposition, dynamic transposition, combiner, cryptographic combiner, mixer, shuffle, data balancing, bit-balancing
This paper extends an existing cryptographic mechanism which can be described as dynamic transposition. This mechanism combines two data sources into a complex result; one data source is accumulated into a block, and the other is used to re-arrange that block. A related inverse mechanism can extract the accumulated data from that result.
Any form of transposition would seem to require some accumulation of data. Since data accumulation and serialization are easy with modern technology, dynamic transposition can be used to replace the Vernam exclusive-OR combiner in stream ciphers. The various techniques used in Vernam ciphers can also be applied to dynamic transposition; any cryptographic advantage of the resulting cipher is thus due to the additional strength of the new combiner.
This paper develops a particular form of dynamic transposition; a related paper develops a form of dynamic substitution. Advantages of the transposition form include an interesting level of secrecy in the resulting ciphertext and the virtual elimination of meaningful statistical analysis measurements. These advantages are purchased at the cost of some inherent increase in processing effort, and the need to encipher data in blocks instead of individual characters.
For a general background in cryptology see Kahn [14], and for details on the classical systems and their analysis see Gaines [12]. More modern statistical approaches are given by Sinkov [26] and Deavours [7]. A good partly-technical anthology is Deavours et. al. [6]. There is a nice but older survey by Mellen [19], a major effort by Diffie and Hellman [9], and a newer one by Massey [18] (also see the other papers in that issue). A rigorous but not always applicable theoretical base starts with Shannon [25] and is extended by Hellman [13]. A relatively modern technical reference is Beker and Piper 1982 [1], although the generally more introductory Beker and Piper 1985 [2] is a major reference for this paper, and will henceforth be referred to as B&P 85. Denning [8] and Pfleeger [23] present cryptography in the broader context of computer security issues.
A transposition cipher re-orders or permutes plaintext elements into ciphertext [12, 26]. If a single transposition can be thought of as a simple exchange in the positions of two elements, it is the simplest form of permutation; moreover, any possible permutation can be constructed (in many different ways) with sequences of transpositions. Permutation has been used for entire ciphers (mainly in an era of pencil-and-paper operations), and, in a limited form, is still in common use inside substitution-permutation networks [11] of the sort from which the U.S. Data Encryption Standard [e.g., 21] is built.
Most previous descriptions of transposition or permutation ciphers have generally concerned fixed or static permutations. However, B&P 85 [2] does give the basis for dynamic permutations, in the sense that each overall permutation is newly created (one transposition at a time) by a continuing pseudo-random sequence. (To some degree, the paper by Costas [3], and comments by Klingler [15] and Costas [4] anticipate some of this work.) Although not stated in B&P 85, this means that every block is likely to be permuted differently, no matter how many blocks there are (within reason). Moreover, dynamic transposition mechanisms can be made to handle very large blocks, as well as dynamic changes in block size.
The execution time of the shuffle process (in a software implementation) is generally proportional to the number of elements being shuffled. Consequently, the shuffle algorithm gives us no particular reason to encipher plaintext in units of small blocks. And, since the complexity of the result would seem to increase with the number of elements in any particular permutation, there is a strong motivation to use large blocks. Indeed, in most cases, each message could probably be enciphered as a single large block, or even a sequence of variable-size, yet sizable, blocks; the shuffle process takes about the same amount of work however organized.
Mathematically, a cryptographic transposition process generates a permutation of the input data; that is, the data are simply re-arranged. The shuffle algorithm is a convenient way to construct one of the many possible re-arrangements at random. How many possible arrangements are there? Suppose the block has n different elements; the first element can be positioned in n possible places, the second in (n - 1), the third in (n - 2) and so on, for a total of (n)(n - 1)(n - 2)...(1), or n! (n factorial) possibilities. So the probability of getting the correct deciphering at random would seem to be 1 out of n!. This is very encouraging, since factorials can yield some really remarkable values. For example, a 64-element block would be considered rather small, yet the probability of correctly deciphering such a block at random would seem to be 1 out of 64!, or about 1 in 10^89.
Unfortunately, the usual situation is somewhat more complex, since a data block is not constrained to have just one occurrence of any particular data value. But when there are multiple occurrences of the same value, it surely cannot matter which of those goes in which position when deciphering. So multiple reverse permutations will each generate a correct deciphering (though most of these will yield no information about how the block was permuted). There are k! different permutations which produce the same deciphering for k occurrences of any particular value. Consequently, there are (k1!)(k2!)...(ki!) equivalent decipherings, for ki occurrences of each value. So the probability of getting one of the correct decipherings is the product (k1!)(k2!)...(ki!) out of a total of n! possible decipherings (for block size n). Note that all but one of the correct decipherings represent an incorrect permutation, so even if the correct deciphering is known, finding the particular permutation involved should be exceedingly difficult.
Suppose there are 26 different characters in a 26-element block; there are 26! (about 4 x 10^26) different ways to permute that block. Since each element is different there can be only one correct deciphering, so there is only one chance in 10^26 of finding this permutation at random. But if the 26 characters in the block are all the same value, no permutation of any kind will cause any apparent change. Accordingly, there is no way to hide a block of similar data values with a pure transposition cipher.
The realization that the cryptographic strength of transposition depends upon the data to be enciphered is both an unexpected and serious complication. It seems only reasonable that a cipher should be able to protect any possible sequence of plaintext data. For example, one user may wish to encipher computer machine code, and another may wish to encipher graphics images. Such computer-oriented data may be very complex, yet still contain long sub-sequences of identical values. It is up to the cipher system to handle these sequences in a strong manner. Classical transposition cannot do this.
From one point of view, the shuffling process converts a confusion sequence into an enciphering permutation. We know that there are n! such permutations in an n-bit block, but how many confusion sequences are there?
The confusion sequence must select one of the n block elements as an "exchange partner" for each element in the block. Accordingly, there are n possibilities for the first partner, n again for the second, and so on, for a total of (n)(n)...(n) or n^n possible different selection-sequences. But there are only n! possible permutations, so each enciphering permutation is created by (n^n / n!) different sequences, on average.
Suppose we are shuffling that same 26-element block. We need 26 pseudo-random values, each of which selects one of the 26 possible block elements; there are 26^26 such sequences, about 6 x 10^36 of them. But there are only 26! enciphering permutations (about 4 x 10^26), so about 1.5 x 10^10 (15 billion) different sequences will create each permutation. So, even if the correct permutation is somehow known, finding the particular pseudo-random sequence which created it should be exceedingly difficult.
Consider a byte-shuffling block cipher: The plaintext will be collected into a block, then a controller will walk through the block, byte-by-byte, exchanging each byte with "partner" bytes selected by a random number generator. For cryptographic purposes it may be reasonable to generalize the shuffle process: For example, it is unnecessary to visit bytes in sequential order, nor need the shuffling stop after exactly one pass [15], as long as the deciphering system follows similar rules.
Letter (byte) frequency statistics are obviously unchanged by the shuffling process. But the frequency distribution statistics do not seem to aid deciphering nearly as much as they would on a simple substitution cipher. Block transposition ciphertext might be compared to a set of alphabet tiles: A particular message can be built from those characters, but once they go back into the storage box, how can anyone decide what particular message they once represented? Indeed, unordered letters on their own cannot represent any one particular message; instead, they stand for all the possible messages which can be made from them.
Actually, since the message is expected to be a correct grammatical example, with correctly-spelled words, on an expected subject, which exactly covers the ciphertext letters, cryptanalysis may not actually be impossible. The normal cryptanalytic technique for transposition ciphers consists of obtaining two messages of the same length, both of which are presumably permuted in the same way. By anagramming both messages in the same way, the correct permutation is found when both messages read clearly [14, pp. 225-226]. Some assistance is available in the form of letter digram and trigram counts, which can support a particular inverse transposition by indicating the presence of statistical plaintext [13, p. 402]. But dynamic transposition need not generate any similar permutations, even for consecutive blocks of similar size.
Because a character or byte transposition combiner can provide good performance only when given a block containing different values, it could be useful to place a Vernam system (an exclusive-OR operation with a pseudo-random stream) before the transposition data input. In this way the plaintext data could be "randomized," and thus need "never" produce a stream of identical values which would compromise the strength of the transposition encipherment.
B&P 85 [2, pp. 93-96] describes a multi-step process of explicitly defining the permutation, finding the inverse, and then un-permuting the block according to the inverse permutation. It may be surprising that there is an easier way.
The shuffling process destroys no data; elements are just repositioned. The values involved in any particular exchange could easily be replaced, simply by exchanging them again, if those values had not been moved by later processing. So the last pair exchanged can be exchanged back into their previous positions. Once that pair has been replaced, the next previous pair can be undone, and so on. Thus, to decipher the shuffled data, the exact same element pairs need only be exchanged in reverse order.
During enciphering, the exchange pair is generally selected by a counter or other process, and a pseudo-random value. It is easy enough to run a counter in reverse, or the desired number of values could be collected in a buffer, and then simply accessed in reverse sequence; the pseudo-random sequence can be "reversed" in the same way. This provides all the information needed for deciphering. (In practice, very long sequences can be accommodated by writing filled buffers to a disk file; the file- stored buffers can easily be recovered for use in reverse order.)
In the same way that letters or bytes can be shuffled, individual bits [2, p. 93] can also be shuffled. In this way the elements of any particular character or byte might be spread throughout the ciphertext. Since any particular bit looks remarkably like any other, how is a cryptanalyst to select those bits which belong to any particular plaintext byte? Of course, the cryptanalyst does not have to find the particular bits corresponding to a particular byte, since any bit of a given value is exactly the same as any other. But this also means that there can be no way to tell which bits belong together.
Byte-level frequency statistics are destroyed by bit-level permutation; only bit-level statistics are left. The cryptanalyst can know how many ones and how many zeros there are in the block (these are the same as in the original plaintext), but this does not seem to help much. Since virtually any message can be constructed from those bits, how is the cryptanalyst to select the correct one?
One interesting implication of bit-level exchange operations is that they are often ineffective. When byte values are being exchanged, the exact same value is "exchanged" (for zero net effect) about one time in 256 (assuming an even distribution). But, when working on bits, the other bit is exactly the same about half the time, for no net effect, and when the bits are different, exchanging them simply changes both bits. Even though half of the exchange operations will have no effect, the number of effective bit-changes is still on the same order as the number of bits (two bits change on every effective exchange). And if this turns out not to be enough, each block could be additionally shuffled, perhaps twice or more. In the end, some bits may always remain unchanged, others will be changed, while still others will be changed and changed back again.
Suppose we continue working with that same small block of 26 character-elements, each of which we assume to have 5 bits (perhaps a Baudot coding); thus the block contains 130 bit-elements. There may be multiple occurrences of some characters in the block, but for a bit-level analysis this is irrelevant. Suppose we have an even number of ones and zeros (the best possible case), 65 of each: Since any one-bit could substitute for any other one-bit, and any zero-bit substitutes for any other zero-bit, there would then be (65!)(65!) deciphering permutations, out of the 130! possible.
The direct evaluation of expressions like these is far beyond the capabilities of a scientific calculator or most computer languages. But it is possible to build such numbers in logarithmic form, and once into logs we use addition and subtraction instead of multiplication and division. For the factorials 65! and 130!, we want the sum of the logs of the integers 2 through 65, and 2 through 130, respectively. There are approximations for the log factorial, but with a computer (and for the values here), it is probably about as easy to sum the logs explicitly.
By actually doing each log and the sum we get ln(65!) = 209.34, and ln(130!) = 506.13, approximately. These values are exponents or powers of e (the base of natural logarithms), and would lead to results too large (or small) to evaluate. It seems reasonable to change to the more-familiar base 2, so that we can think of these huge values as the number of bits it takes to represent them. Dividing by ln(2) = 0.6931, we get log2(65!) = 302.01 and log2(130!) = 730.19; these exponents thus represent some binary values which are 303 and 731 bits long, respectively.
For the 130-bit block, 130^130 or about 2^913 possible confusion sequences will generate 130! or 2^730 possible enciphering permutations: The number of possible permutations is huge, and this hides the plaintext. About (65!)(65!) or 2^604 different permutations will encipher a plaintext block into a particular ciphertext block: The number of deciphering permutations is huge, and this hides the correct permutation (even from known plaintext). An average of 130^130 / 130! or about 2^183 different sequences will create any particular permutation: The number of possible sequences is huge, and this hides any particular sequence (even from a known permutation). Thus, the classical attacks of brute force and known plaintext would seem to be wrong ways to penetrate dynamic transposition.
A seemingly different approach would be a bit-by-bit defined-plaintext attack, since this might (if the rest of the system does not prevent it) succeed in building up a complete description of a particular enciphering permutation. Of course, this would mean that the cryptanalyst had that plaintext already (indeed, was generating the plaintext), so the attack would be on the pseudo-random sequence. But 2^183 different sequences could have created that permutation (and those sequences are distributed among 2^913 possible sequences), so there would seem to be no way for a cryptanalyst to select the correct one.
If all data to be enciphered and deciphered are already in the form of blocks, then each block is (obviously) already full and can simply be handled as a unit. But whenever variable amounts of data are to be enciphered as blocks, the last block is unlikely to be completely filled, and the unused area must then be filled or padded [21] with extra data. On average, half a block of padding is required for each message, thus expanding the ciphertext; this is a motivation for limiting the block size. This may not be a particularly significant motivation, however, considering the amount of data which may be easily stored and quickly communicated by computer, and padding is unnecessary when variable-sized "blocks" are available.
A more significant complication is that any padding must be in some way distinguished from the plaintext data, so that it may be removed in deciphering. In general, a particular data value cannot be used as a separator, because "binary" data (such as computer object code) may be enciphered, and such data may contain every possible byte value. The conventional solution is to include some sort of length value along with the padding, which is then removed with the padding when deciphering.
Another complication of data blocking, at least for dynamic transposition, is that the block size defines the value range needed on the "random number" input (as well as the number of values required). Thus, if dynamic transposition is to accept variable block sizes, the random number range must be able to cover an arbitrary block size. And even fixed size blocks, if they are large, can demand a fairly large random number range. For example, a 256 kilobyte block contains 2,097,152 bits, which implies a 21-bit random value to select between them. Shuffling that block requires 2,097,152 of those 21-bit values (and about 6 megabytes of temporary disk storage to reverse that sequence when deciphering).
At first glance, it seems reasonable to pad with random data, since this should help to obscure the data in the block. This idea can be extended: Instead of completely filling each block (except the last) with message data, each block can instead be partially filled with plaintext data and then padded with random data [22]. Naturally, this causes some ciphertext expansion, but the random data should help to dilute the remaining bit statistics, and bit statistics seem to be the only statistics left.
But instead of just hoping that the random data will smooth out the bit statistics, steps can be taken to guarantee this result. In particular, the number of one-bits and zero-bits in the plaintext data can actually be counted. Then the message can be extended (or a block filled out) with non-random data so as to balance the bit distribution exactly. (Of course we might deliberately vary the bit-balance somewhat from block to block.) After bit-shuffling the extended message, there seems to be very little statistical frequency information left: no word statistics, no letter statistics, and no bit statistics. If some statistical relationship remains which might assist in entry, it is certainly not clear what that might be.
With data balancing, the best possible situation for a transposition cipher can be guaranteed. Blocks which might be all ones or all zeros can be balanced and enciphered in a strong way; without balancing, it would be impossible for transposition to provide any effective enciphering of such blocks. And, while the normal block (not heavily weighted one way or the other) may not seem to need additional strength, such blocks also require only a minimum amount of balancing.
Bit-balancing does cause some ciphertext expansion (perhaps 25% to 33% on text files). Naturally, this expansion could be mostly eliminated if the input data had an even bit distribution, and a good distribution might be enforced by passing the data through a Vernam system before transposition. Alternately, modern data compression processing can reduce the size of typical text files by an amazing 60% while simultaneously improving their value distribution. Subsequent expansion due to final bit-balancing should be less than 10% of the resulting smaller file. Thus, if data expansion is a problem, that problem can be managed (at some expense); in many cases, a modest amount of data expansion is not a problem.
The fact that the strength of the transposition can now be guaranteed, independent of the input data, is very significant. Without such a guarantee, it might be necessary to monitor the input to a transposition module and make special provisions for alternate ciphering when strongly-unbalanced data are encountered. With a guarantee of strength, the transposition module can stand alone and handle any arbitrary data sequence before passing it along to another module.
Bit-balancing also provides the basis for an analysis of the strength of the resulting cipher. Since every block is to be balanced, each block should have the same permutation possibilities: one permutation is correct, others are incorrect but still decipher the block, and others are simply incorrect.
When working with blocks, there is some difficulty deciding how much space to leave for bit-balancing. A good distribution might need only a little extra data to achieve an exact balance, but some plaintext sequences might be all ones or all zeros, and those would require as much balancing data as plaintext data.
By counting data bits while filling the block, we need only leave space for exactly the number of bytes needed for bit- compensation. But there must be some way to isolate and remove the bit-compensation when deciphering. One way might be to enter bit-compensation data, of the least-used bit type (all-zeros or all-ones bytes), backwards from the end of the block. This continues until the bit counts are within a byte of balance. Then exact balance can be achieved with a single byte containing at least one bit of the most-used bit type. Because the previous balancing bytes have contained only the least-used bit type, the last balancing byte is a contrasting byte.
This means that the first byte (from the far end) that is a contrasting value is also the identifiable last byte (from the far end) of the bit-compensation data. Thus, the bit-compensation area can be as large or small as needed, and there need be no special code or count to delimit it. Moreover, all but one of the bits of the minimum two balancing bytes can participate in balancing. Since most data distributions will need at least two balancing bytes anyway, the average overhead for defining the balancing data area (beyond that required for simple balancing) would seem to be less than one byte. The same technique can be applied to huge or dynamically-variable blocks, and some added computation can produce similar results for complete message permutations.
All fixed-size-block ciphers which support variable-length data need a mechanism for padding the last block. But if bit- compensation is already supported, it is possible to bit-balance the filled portion of the last block, and then complete the block with particular bit-balanced byte values. After deciphering, proceeding from the end of the block, all the particular bit-balanced byte values can be skipped. Then, if there are all-ones or all-zeros bytes they can also be skipped, along with the next byte (which is the contrasting byte). In this way, the same mechanism which is used to delimit the bit-compensation can also remove the padding at little or no extra cost.
For a modest block of 512 bytes by 8 bits (the size of a single MSDOS logical disk sector) the block size is 4096 bits. (In actuality there will be a minimum of two balance bytes, so there will be at most 4080 data bits, and may actually be many less.) Assuming an even bit distribution (which we can now enforce), there are (2048!)(2048!) decipherings out of 4096! possible permutations. In logs, ln(2048!) = 13571.95, and ln(4096!) = 29978.65; so there are about e^29979 or 2^43250 possible permutations, a 43251-bit binary value, and only one of these permutations is "correct." (In ordinary terms, "many" other permutations would be "readably close," but in comparison to numbers like these, these possibilities pale to insignificance.)
The total number of deciphering permutations is e^27143 or 2^39160, a 39161-bit binary value; so finding the one correct permutation would seem to be a difficult task. And the average number of sequences which create any particular permutation is e^4091 or 2^5902, a 5903-bit binary value. Of course, instead of 1/2 K (byte) blocks, we might well do entire files of 10K, 100K, or perhaps even 350K in length.
These probability calculations have a strange other-world character to them. While the results do imply a sort of fundamental secrecy for the dynamic transposition mechanism itself, they do not imply that a cipher using this mechanism is necessarily secure; any cipher is only as secure as its weakest link. Basically, these results are useful only to say that an exhaustive search of permutations and sequences, for even a modest (correctly constructed) block, is completely out of the question. Then, if no other part of the cipher has an easy "shortcut" attack [21, p. 137], the cipher may be secure in practice.
A simple cipher module like this actually may be much more valuable than a complex one, for it may eventually be possible to understand its exact limitations, and then answer those limitations completely in other modules. Although it is elegant to have a single complex framework handle all aspects of secrecy, such systems usually cannot be completely understood in a deep way. For example, there has been suspicion of a DES "backdoor" for over a decade, and great strides have been made in factoring large numbers like those used in RSA. A reasonable alternative is the selection of simple mechanisms which can be deeply understood.
Note that a shuffle permutation of a 512-byte block requires 512 12-bit pseudo-random values. Thus, to encipher 4096 bits we need 49,152 pseudo-random bits, for a "key stream" expansion of 12:1. Since a Vernam cipher needs only a single random bit to encipher each data bit, shuffling dynamic transposition is seen to be relatively demanding of the random- number resource. But the expansion of this resource may be only a small part of the cost of a complete cryptosystem, and what it buys, hopefully, is cryptographic strength.
When transposing bit-balanced fixed-size blocks--each of exactly the same length and with exactly the same number of one-bits and zero-bits--in some sense there is only one block, and all of our different ciphertext blocks are only permutations of that same aboriginal balanced block. Moreover, all of the bit-compensated plaintext blocks and all possible decipherings are just other permutations of that same primitive block. Various decipherings include all the possible bit-balanced messages which will fit in the block, including a huge number of cases in which the messages differ only in their crucial words. There would seem to be no way for a cryptanalyst to distinguish the correct message from all possible decipherings. So brute-force methods would seem to be useless, as well as impractical.
The dynamic transposition combiner may be considered to be a black box, with two input data ports ("Data In" and "Random In"), and one output port ("Combiner Out"). Because the block size can vary, the "Random In" range must also vary. Evidently the mechanism inside the box in some way combines the two input streams to produce the output stream. It seems reasonable to analyze the output statistically, for various input streams.
For these tests, the "Data In" stream was a sizable text file (a book chapter) with all spaces and punctuation deleted, and lower case converted to upper, leaving a 26-element alphabet of 18,135 capital letters.
The black box test results can be summarized in the form of standard "delta IC" [20], and "Z-coefficient" [7, 17] computations. In both cases, we count the number of occurrences of each element value in the stream being analyzed.
The index of coincidence (IC) is conceptually "the sum of the squares" (of the element counts) "over the square of the sum" (or total count); the IC is normalized to a delta IC by multiplying by the size of the alphabet. A delta IC value of 1.0 indicates a random distribution.
A Phi value is conceptually "the sum of the squares of the element counts," and an "expected" value of Phi and a statistical variance value can be derived for a random data stream. The Z-coefficient is just the difference between the actual and expected Phi values, normalized by dividing by the variance. A value of 0 would be expected, and a value between -2 and 2 would be most probable for a random sequence.
The results are summarized in Table 1.
Table 1.
TRANSPOSITION DISTRIBUTION STATISTICS (delta IC / Z-coefficient)
Data In Random In Combiner Out
The Data are 26-Letter Text
Byte Transposition 1.66 / 1684 1.00 / -0.9 1.61 / 1593
Bit Transposition 1.66 / 1684 1.00 / 1.8 1.32 / 257.5
Bit Balanced Trans. 1.66 / 1684 1.00 / 0.8 1.00 / -0.2
The Data are One Value Repeated
Bit Balanced Trans. 26.0 / 36199 1.00 / 1.0 1.00 / 0.8
Apparently the bit-balanced bit transposition creates output with good random characteristics, even when the data input is just a repeated constant value. (If the data input is random, then clearly the resulting block must also be random, even if the random input is a constant value.)
In general, a cryptographic combiner can be expected only to increase (albeit greatly) the complexity of a cryptanalysis. Nevertheless, bit-balanced dynamic bit-transposition seems to have some interesting characteristics.
If a bit-balanced ciphertext block carries information, it does so only in its bit arrangement, and any bit-balanced block can obviously be re-arranged into any other. Since any message we can possibly encipher must produce one or more bit-balanced ciphertext blocks, any ciphertext block can obviously be re-arranged into any part of any possible message; all except one of these is a meaningful false solution, or "spurious message decipherment" [13, p. 290]. Hellman defines the number of spurious message decipherments as nm, and writes: "If nm takes on large values with probability close to one, then the system will be secure even if the cryptanalyst is allowed unlimited computation." A cryptanalyst would seem to be unable to tell which of all possible message blocks was sent.
Enciphering a block with bit-shuffling implies the existence of some sort of confusion sequence which may itself be penetrated; if the confusion sequence could be analyzed and replicated, the cipher would be broken. In mounting such an attack, the cryptanalyst's first problem would be to determine the correct deciphering permutation. Even an exact copy of the original plaintext block would seem to be of little help: There are a multitude of deciphering-but-incorrect permutations (too many to try them all), with apparently no way to identify the correct one. (Hellman calls this "spurious key decipherment.") The cryptanalyst's next problem would be to identify the particular confusion sequence which produced the known permutation. But since the shuffle process could produce any particular permutation from a host of different confusion sequences, there would seem to be no way to identify the one original confusion sequence so that it might be analyzed. (This would seem to be another level of "spurious key.")
Shannon [25, p. 680], defines PM(E) as the conditional probability of ciphertext (block) E if message block M is chosen, and P(E) as the probability of obtaining ciphertext E from any cause. If the selected permutation process does indeed map an arbitrary (balanced) block to every possible (balanced) block, it certainly seems plausible that PM(E) = P(E), which is a necessary and sufficient condition for perfect secrecy. That is, if any message block could generate any ciphertext block with about equal probability, then the probability of obtaining any particular ciphertext block cannot depend on the message; Shannon writes, "PM(E) must be independent of M."
An implication of this is that "the number of different keys is at least as great as the number of M's." In this analysis, the number of "keys" is the number of possible permutations, or n! (for an n-bit block), and the number of possible messages (blocks) is under 2^n, which is far less. It appears that this does not necessarily imply that the number of user-keys must be n!, or even 2^n, because the confusion sequence is isolated by the strength of the dynamic transposition mechanism. But, as always, the number of user-keys must be sufficient to prevent a key-search attack.
Of course, a fully-detailed strength analysis probably depends upon a deeper understanding of the shuffle process. Of particular interest is the effect of the confusion sequence on permutation distribution. But the simplicity and intuitive generality of shuffling would seem to bode well for such an analysis, and shuffling is just the basis for this particular form of dynamic transposition.
One use for dynamic transposition would be as a combining or mixing function for data blocks. With some stream-to-block conversion, and vice versa, such a combiner could be used to replace the exclusive-OR logic function in a Vernam stream cipher. Alternately, it could be used to combine two pseudo-random sequences, to produce an even more complex sequence. Or it could be applied in a product cipher [25] as one part of a chain or network of cipher operations.
Dynamic transposition may be slower, but perhaps also more secure than some other alternatives. Consequently, it might well be used for key delivery as opposed to general data encipherment.
Transposition--normally difficult to apply and potentially insecure--becomes substantially stronger when transposing bits within bit-balanced blocks, and driven with a pseudo-random sequence. Dynamic transposition combiners seem very protective of their pseudo-random sequence (a significant problem with a Vernam [27] combiner), can frustrate a statistical frequency-analysis of the ciphertext, and can guarantee strong mixing performance even with an input of unbalanced plaintext distributions.
My thanks to the referees, whose questions about the utility of this mechanism led to the inclusion of material on numerical and theoretical secrecy, and to Edward Rupp for conversations about potential attacks.
1. Beker, H. and F. Piper. 1982. Cipher Systems.
New York: John Wiley & Sons.
2. Beker, H. and F. Piper. 1985. Secure Speech
Communications. London/Orlando: Academic Press.
3. Costas, J. 1981. The Hand-Held Calculator as a Cryptographic
Machine. Cryptologia. 5:94 - 117.
4. Costas, J. 1981. Letter to the Editor. Cryptologia.
5:210-212.
5. Davies, D. and W. Price. 1984. Security for Computer
Networks. New York: John Wiley & Sons.
6. Deavours, C, D. Kahn, L. Kruh, G. Mellen, and B. Winkle. 1987.
Cryptology Yesterday, Today, and Tomorrow. Norwood, Mass:
Artech House.
7. Deavours, C. 1987. Cryptanalytic Programs for the
IBM PC. Laguna Hills, CA: Aegean Park Press.
8. Denning, D. 1982. Cryptography and Data Security.
Reading, Mass: Addison-Wesley.
9. Diffie, W. and M. Hellman. 1979. Privacy and Authentication:
An Introduction to Cryptography. Proceedings of the IEEE.
67: 397-427.
10. Durstenfeld, R. 1964. Algorithm 235, Random Permutation,
Procedure SHUFFLE. Communications of the ACM. 7: 420.
11. Feistel, H. 1973. Cryptography and Computer Privacy.
Scientific American. 228: 15-23.
12. Gaines, H. 1956 (original 1939). Cryptanalysis.
New York: Dover Publications.
13. Hellman, M. 1977. An Extension of the Shannon Theory Approach
to Cryptography. IEEE Transactions on Information Theory.
IT23: 289-294.
14. Kahn, D. 1967. The Codebreakers. New York: Macmillan.
15. Klingler, L. 1981. Letter to the Editor. Cryptologia.
5:209-210.
16. Knuth, D. 1981. The Art of Computer Programming,
Vol. 2, Seminumerical Algorithms. 2nd ed. Reading, Mass:
Addison-Wesley.
17. Kullback, S. 1976 (original 1938). Statistical Methods in
Cryptanalysis. Laguna Hills, CA: Aegean Park Press.
18. Massey, J. 1988. An Introduction to Contemporary Cryptology.
Proceedings of the IEEE. 76: 533-549.
19. Mellen, G. 1973. Cryptology, computers, and common sense.
Proceedings of the National Computer Conference.
42: 569-579.
20. Mellen, G. 1983. Cryptanalysts' Corner. Cryptologia.
7: 371.
21. Meyer, C. and S. Matyas. 1982. Cryptography: A New
Dimension in Data Security. New York: John Wiley & Sons.
22. Michener, J. 1985. The "Generalized Rotor" Cryptographic
Operator and Some of Its Applications. Cryptologia.
9: 97-113.
23. Pfleeger, C. 1989. Security in Computing.
Englewood Cliffs, New Jersey: Prentice Hall.
24. Rubin, F. 1987. Foiling An Exhaustive Key-Search Attack.
Cryptologia. 11: 102-107.
25. Shannon, C. 1949. Communication Theory of Secrecy Systems.
Bell System Technical Journal. 28: 656-715.
26. Sinkov, A. 1966. Elementary Cryptanalysis.
Washington, DC: The Mathematical Association of America.
27. Vernam, G. 1926. Cipher Printing Telegraph Systems.
Transactions of the AIEE. 45: 295-301.
Terry Ritter is a registered Professional Engineer, a member of
IEEE and ACM, with a background in computer architecture, hardware,
and software. He has enjoyed spending the past few years being
Blue Jean Software and Blue Jean Computer Engineering.
BIOGRAPHICAL SKETCH
Terry Ritter, his
current address, and his
top page.
Last updated: 1995-11-11