This massive set of discussions was triggered by my retrospective article about Dynamic Transposition, a serious cipher in which the known weaknesses of transposition have been identified and eliminated. The result is a practical, fairly-simple and believable block cipher based on fundamentally different principles than conventional block ciphers like DES.
A Dynamic Transposition cipher is conceptually simple:
Dynamic Transposition operates at practical speeds, if generally slower than conventional ciphers. The bit-balancing time is probably less than the shuffling time, and data expansion from bit-balancing can be limited to 25 percent, worst case.
In Dynamic Transposition, a bit-balancing process assures that each and every plaintext block has the same count of 1's and 0's. As a result, every possible plaintext or ciphertext block is just a bit-permutation away from every other block. So if an opponent has a ciphertext, that block could be produced from any possible plaintext block, given the right permutation. At least potentially, this is Shannon-style, Latin square, perfect secrecy, albeit on a block-by-block basis.
Actually using keys large enough to select from among all possible block bit-permutations (for any single block) is a realistic possibility with smaller blocks. But even with smaller keys, the generator which shuffles the block can and should have sufficient internal state to make two uniform, unbiased selections among all possible bit-permutations. By double-shuffling the block, we can assure that any particular bit-permutation can be produced by unsearchably many different generator sequences, and so protects the actual sequence from exposure.
In a conventional block cipher, a key selects a particular emulated huge Simple Substitution "table," and each block ciphered thereafter potentially exposes part of that table.
Dynamic Transposition operates by re-arranging the bits in a data block which has equal counts of 1-bits and 0-bits. Because there are many different 1's and many different 0's, unsearchably many re-arrangements will take exactly the same plaintext block to exactly the same ciphertext block. So even if the plaintext and ciphertext blocks are both known, the actual re-arrangement (permutation) used is still not exposed. Ciphering ambiguity would seem to be the primary strength of Dynamic Transposition. The problem of finding which one of all possible ciphering permutations actually occurred is central to every discussion of strength.
In general, Dynamic Transposition uses a different ciphering transformation for each ciphered block. Thus, there simply is no one particular transformation to find. The closest remaining possibility would seem to be recovering the internal state of the generator which shuffles the block. But that seems to require knowing each actual ciphering permutation, and they are not exposed.
In contrast, a conventional block cipher is keyed once, which selects a particular emulated "table," and then used repeatedly. The emulated "table" is a fixed solution, and if that can be found, it will last until the next keying.
Dynamic Transposition is also keyed, but the ciphering transformation is ambiguous and each block gets a new one. Consequently, each particular permutation must be resolved independently, because different blocks are only distantly related.
With a conventional block cipher, just one or two known-plaintext pairs are generally sufficient to exclude every possible key but the right one. Since we do assume that some amount of plaintext will be available, there generally is sufficient information for a unique solution, if only someone was clever enough to find it. Cipher users thus find themselves in the position of continually betting that nobody is that smart.
In contrast, a Dynamic Transposition bit-permutation is a complete implementation of the permutation model. Having a known-plaintext pair only reduces the uncertainty in knowing the ciphering permutation to within a particular unsearchably-large subset. That subset consists of all possible permutations which will produce the given result.
If the opponent could assume that the same permutation was used on the next block, different data might further reduce the set of possible permutations, thus eventually resolving the particular permutation involved. But since different permutations are used for different blocks, apparently the only thing which might be resolved is the shuffling sequence. And when we shuffle each block twice, unsearchably many different sequences will produce any particular permutation.
Dynamic Transposition supports any possible permutation of the data block. As a result, what we know about the mathematical distribution of random permutations should apply directly to a Dynamic Transposition cipher.
In contrast, conventional block ciphers seek to emulate huge Simple Substitution "tables," but can implement only a tiny part of their potential keyspace. (For example, DES has a potential keyspace of 2**(10**21) keys, of which 2**56 keys are actually selectable.) The result is that what we know about the distribution of random substitution tables probably can not be applied to a conventional block cipher.
One of the main arguments against Dynamic Transposition in these conversations is that transposition can be considered a limited subset of all possible substitution transformations. So it is argued that Dynamic Transposition is also limited to a subset of transformations, supposedly "just like" conventional block ciphers.
But Dynamic Transposition is not intended to produce general substitutions, so there should be no surprise when it does not do that. Dynamic Transposition is limited to using bit-permutations, and does indeed implement every one of those. In contrast, conventional block ciphers implement almost none of the potential keyspace available to them. And while they also do not intend to do better, the mathematical implications of using some pre-selected subset, as opposed to every possibility, are distinctly different. That is not "just like" Dynamic Transposition.
In essence, the use of bit-balanced blocks represents a particular coding of information, and Dynamic Transposition ciphering can indeed transform any element to any other element of that same code. So far, one could say something similar about exclusive-OR (although that is not a keyable transform), but even this is by no means guaranteed in a conventional block cipher. There is no reason to believe that we can always find a key which will take one arbitrary block to another in a conventional block cipher.
By using only a tiny selection for the actual ciphering operation, a conventional block cipher becomes potentially solvable with a practical amount of known-plaintext.
Dynamic Transposition may have tiny original keys, but the keyspace actually involved in ciphering is large enough to permit any possible permutation. Only the knowledge of a sequence of permutations would seem to address the hidden internal shuffling sequence. But since Dynamic Transposition ciphering permutations are not exposed, and since unsearchably many different sequences produce the same permutation, the sequence is protected.
Another issue touched-on here is -- yet again -- the One-Time Pad (OTP). Many people find it difficult to accept what should be obvious: in general, the OTP which is proven secure probably cannot exist in practice, and so cannot be used to hide any real data.
It is indisputable that if an OTP pad or sequence is predictable, the system is insecure. Here, OTP proponents may protest that no system with a predictable sequence can be called an OTP. But our problem with any real system is how to know whether or not any particular sequence is predictable. If distinguishing between an "OTP" and something less requires knowing what we cannot know, the whole concept is a joke.
The unpredictability of a sequence cannot be guaranteed by test. And, even though some sequence generators may be based on fundamental physical randomness, they must be implemented in a world in which unexpected problems often exist. Since the unpredictability of a generator also cannot be guaranteed by test, it is generally impossible to prove that any implemented generator is as perfectly unpredictable as one might hope.
The conditions assumed for the theoretical OTP security proof generally cannot be met in practice, so I offer Dynamic Transposition as one example of a superior cipher in practice. In any reasonable cipher, the keying sequence need not be unpredictable in the same way as an OTP, and is in any case deliberately hidden by layers of strong puzzles.
In contrast, the OTP sequence is immediately exposed by known-plaintext, so that any predictability in that sequence (whether known to our side or not) is also exposed, and that is a very dangerous situation. Using an OTP is dangerous because the strength proof we want does not apply exactly when we need it most.
Subject: Dynamic Transposition Revisited (long) Date: Thu, 18 Jan 2001 23:02:31 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3a67737e.15537635@news.io.com> Newsgroups: sci.crypt Lines: 483 Terry Ritter 2001 Jan 18 ABSTRACT A novel approach to block ciphering is remembered for relevance to modern ciphering issues of strength, analysis and proof. A rare example of a serious transposition cipher, it is also an unusual example of the simultaneous use of block and stream techniques. INTRODUCTION Over a decade ago, before the web, before PGP, and before "Applied Cryptography," I began to study the different forms of ciphering. (Actually I was re-kindling a technical interest from my Army years: in 1968 I was a cipher machine repairman at the Nha Trang AUTODIN site.) A decade ago there were a few -- but only a few -- crypto books, and virtually nothing on serious computer crypto. Research often involved reading the original academic literature, from Shannon on, references which I later included in my articles. One of the things which caught my interest was an apparent dichotomy between substitution and transposition. (Currently, I have a different view: I came to see transposition as a limited, algorithmic form of substitution. More precisely, "transposition" can be seen as a way to form a permutation using a sequence of exchanges: literally "transpositions." But a mere permutation of the existing symbols is a very limited subset of substitution. And it is exactly those limitations which form the characteristics of transposition we know so well.) Emulated huge substitution (in DES) had been the dominant basis for ciphering, but no comparable transposition-based designs existed (at least in the open literature). That begged the question of whether transposition was simply unsuitable for secure ciphering, and if so, why. Subsequent investigations and development produced an article titled "Transposition Cipher with Pseudo-Random Shuffling: The Dynamic Transposition Combiner," published in the January 1991 issue of "Cryptologia" (see: www.io.com/~ritter/ARTS/DYNTRAN2.HTM ). With continuing sci.crypt discussions on stream ciphering, the one-time-pad (OTP) and cipher security proofs, it may be worthwhile to re-visit Dynamic Transposition to see if it has something to offer. As described here, Dynamic Transposition is a block cipher without S-boxes or rounds, and which neither has nor needs avalanche or diffusion. Like a stream cipher, it uses a keyed random number generator (RNG) to perform ciphering on a block-by-block basis. Dynamic Transposition is notable for design clarity, ease of understanding and analysis, and scalability for testing. The general concept of Dynamic Transposition could be expanded into a stand-alone secret-key cipher, or used as the data-ciphering component of a public-key cipher. TRANSPOSITION Specifically, a "transposition" is the simple exchange of the positions of two symbols within a message or ordered array or vector. A sequence of such exchanges can form any possible mathematical "permutation" of the message or array. This is the simple re-arrangement of the existing data symbols. Classically, a transposition cipher re-positions plaintext, letter-by-letter, to produce ciphertext. As a result, every letter of the plaintext is also visible in the ciphertext. And that invites an opponent to re-position or "anagram" the ciphertext letters in an attempt to find the relatively few plaintexts which would make sense. In contrast, modern transposition need not work on whole character units, but can instead permute each binary-coded character bit-by-bit. This is significant because vastly more messages which make sense -- all but one wrong -- can be created from a heap of bits than from a pile of letters. Classically, one of the problems with transposition has been that it does not change the values of the data, and that can leak information. Consider a plaintext block of all-0's: No permutation will change that block at all, so it will be fully-exposed as ciphertext. Clearly, classic transposition has a hidden strength requirement that plaintext data contain a range of different values. In contrast, modern computer processing can create blocks with an exact balance of 1's and 0's (by adding balancing values to the plaintext). Only as much plaintext as can be balanced is accepted for a block, which is then filled with balancing values. The result is that there will be no weak blocks. Classical transposition is often limited to simple processes consistent with hand application, and so tends to traverse only a small subset of all possible permutations. That is a limited keyspace which may support attack. But in a modern computer implementation, efficient permutation algorithms allow us to produce any of the immense number of different permutations with equal probability, provided we have a random sequence to drive the algorithm. One immediate result is a vastly-expanded keyspace. Classically, each block or message of a transposition cipher is permuted in exactly the same way. So if an opponent acquires multiple messages, it may be possible to find a single permutation which makes both ciphertexts readable, and thus identifies the correct permutation. That attack is called "multiple anagramming." But a modern version of transposition may simply permute each block independently. That is the "dynamic" part of Dynamic Transposition, and it completely voids the multiple anagramming attack. Overall, the resulting block cipher is a novel combination of both stream and block ciphering technology. DYNAMIC TRANSPOSITION A Dynamic Transposition cipher is conceptually very simple: (1) We collect plaintext data in bit-balanced (or almost bit-balanced) blocks. (2) We shuffle the bits in those blocks under the control of a keyed pseudorandom sequence. (The cipher designer decides exactly how the sequence is generated and keyed. A complete design will use message keys or other techniques to prevent sequence re-use.) The resulting scrambled blocks are the final ciphertext. When every plaintext block is exactly bit-balanced, any possible plaintext block is some valid bit-permutation of any ciphertext block. So, even if an opponent could exhaustively un-permute a ciphertext block, the result would just be every possible plaintext block. No particular plaintext block could be distinguished as the source of the ciphertext. This is a form of balanced, nonlinear combining of the confusion sequence and data block: as such, it is related to XOR, Latin squares, Shannon "perfect secrecy," and the one-time-pad (OTP). The inability to distinguish a particular plaintext, even when every possibility is tried, is basically the advantage claimed for the OTP. It is also an advantage which the OTP cannot justify in practice unless we can prove that the OTP keying sequence is unpredictable, which generally cannot be done. That makes the practical OTP exceedingly "brittle": if the opponents ever do gain the ability to predict the sequence, they may be able to attack many messages, both future and past. That would occur in the context of a system supposedly "proven" secure; as usual, the user would have no indication of security failure. Dynamic Transposition does not need the assumption of sequence unpredictability, because the sequence is hidden behind a multitude of different sequences and permutations which all produce the same result. And if the sequence itself cannot be exposed, exploiting any predictability in the sequence will be difficult. (This of course does not mean that Dynamic Transposition cannot be attacked: Brute-force attacks on the keys are still imaginable, which is a good reason to use large random message keys.) In particular, shuffling the bits in a bit-balanced block means that a huge number of different permutations will produce exactly the same ciphertext result. Where one ciphertext may have a '1' coming from the start of the plaintext block, another may have a '1' from near the end, both of which produce exactly the same ciphertext result. So, even if the opponents have the plaintext and the associated ciphertext, the ciphering permutation is still not revealed, and that protects against attacks on the pseudorandom sequence and the RNG. Bit-permutation does have, of course, a substantial execution cost. Dynamic Transposition is conceptually as simple as, say, "simply" exponentiating a value modulo the product of two large primes. Of course, actual the implementation details in any real cipher can be complex. But the feeling of complexity often goes away after running through a couple of designs where the problems are all fully solved. And testing the implementation may be easier with Dynamic Transposition. A Dynamic Transposition system is far more transparent than most alternatives. The components are all well-known cryptographic technology, each of which can be independently understood, evaluated, tested -- and even upgraded, when necessary. And the simple 8th-grade combinatorics involved in Dynamic Transposition analysis (which, alas, I occasionally get wrong anyway) support more believable conclusions than graduate-level number-theoretic asymptotic "proofs." DYNAMIC TRANSPOSITION CIPHERING Most of the components used in Dynamic Transposition have been discussed many times; see, for example: http://www.io.com/~ritter/KEYSHUF.HTM and http://www.io.com/~ritter/CLO2DESN.HTM One of the needed components which has not been described is the bit-balancing process. Bit-Balanced Blocks Some of the analytic and strength advantages of Dynamic Transposition depend upon having the same number of 1's and 0's in each block, which is called "bit-balance." Exact bit-balance can be achieved by accumulating data to a block byte-by-byte, only as long as the block can be balanced by adding appropriate bits at the end. Then the block is ciphered, and another block filled. We will always add at least one byte of "balance data," at the end of a block, and only the first balance byte, immediately after the data, will contain both 1's and 0's. We can thus transparently remove the balance data by stepping from the end of the block, past the first byte containing both 1's and 0's. In general, bit-balancing may expand ASCII text by as much as 1/3. We can reduce that if we have random-like data. A pre-processing data compression step would not only reduce plaintext size, it would also reduce the expansion factor. Approximate or statistical bit-balance can be achieved by creating a sort of Vernam cipher to "randomize" the plaintext. The result is almost balanced blocks with no expansion at all. Bit Shuffling This is ordinary cryptographic shuffling -- algorithmic permutation -- of bits. It is of course necessary that this be done properly, to achieve a balanced probability for each result, but that is well-known cryptographic technology. (Again, see: http://www.io.com/~ritter/KEYSHUF.HTM .) The usual solution is the well-known algorithm by Durstenfeld, called "Shuffle," which Knuth II calls "Algorithm P (Shuffling)," although any valid permutation generator would be acceptable. We can treat the accumulated and balanced block as a bit vector and walk through it, shuffling just like we might do with an array of bytes. If we shuffle each block just once, an opponent who somehow knows the correct resulting permutation can use that information to reproduce the shuffling RNG sequence, and thus start to attack the RNG. And even though we think such an event impossible (since the correct permutation is hidden by a plethora of different bit-permutations that each produce exactly the same ciphertext from exactly the same plaintext), eliminating that possibility (by shuffling each block twice) is probably worthwhile. This does not produce more permutations, it just hides shuffling sequence. Deciphering We can easily return an encrypted block to plaintext by applying Shuffle in reverse order. The keyed pseudorandom sequence used for encryption is accumulated in a buffer and used last-value-first. And if we shuffle twice to encipher, we must unshuffle twice to decipher. ANALYSIS Dynamic Transposition is clearly a block cipher: Data must be accumulated into blocks before ciphering can begin. It is not, however, a conventional block cipher. It does not emulate a large substitution. Unlike conventional block ciphers, Dynamic Transposition has no data diffusion, nor is that needed. It has no S-boxes, and so has no weak S-boxes. The only mixing involved is the single mathematically uniform distribution of permutations, so there is no weak mixing. And whereas conventional block ciphers need "modes of operation" to randomize plaintext and thus minimize the ability to mount codebook attacks, Dynamic Transposition does not. While conventional block ciphers generally do not scale down to exhaustively testable size, Dynamic Transposition scales well. Presumably, it could be made to operate on blocks of variable size on a block-by-block basis. Each component also can be scaled down and tested independently. It is easy to sink into a morass of arithmetic in the strength argument. Rather than do that here, I will just highlight the major issues: The main idea is to hide the RNG sequence (actually the nonlinear sequence of jitterized values), so an opponent cannot attack the deterministic RNG. Strength is provided by the block size and guaranteed bit-balance, since, when shuffled, a plethora of different permutations will take the plaintext block to exactly the same ciphertext block. There simply is no one permutation which produces the given ciphertext. Since a plethora of different permutations will produce the given ciphertext, trying them all is impractical. So the opponents will not know the permutation -- even with known plaintext -- and will not have the information to attack the RNG. If the first level of strength fails and the ciphering permutation is discovered, more strength occurs in the fact that another plethora, this time different RNG sequences, will create that exact same permutation. When each block is shuffled twice, this prevents an opponent from finding the sequence needed to attack the RNG. Then, of course, we get to whatever strength is in the RNG system itself. That includes having an internal state which significantly exceeds the amount of information used for any block permutation. It also includes the unknown strength of nonlinear filtering (e.g., "jitterizing") of the raw RNG data. Large Numbers It is common, in cipher analysis, to disdain the use of large-number arguments. That is because, in practice, opponents do not even attempt to attack well-designed ciphers by straightforward brute force, because such an approach would be hopeless. Ciphers are instead attacked and broken by finding some pattern which will discard huge numbers of possible keys with every test. But such patterns generally occur in the context of complex iterative cipher systems which *can* have defects. In contrast, here we use mathematically-correct permutation algorithms, and no such defect should be present. In the current Dynamic Transposition design, even with RNG nonlinear processing, we do expect correlations to exist in the RNG shuffling sequence. But if the sequence is hidden and cannot be isolated, it would seem to be very difficult to find and use such relationships. In a real sense, using a combiner more complex than XOR provides protection against the disaster of a predictable sequence -- protection which is simply unavailable in conventional OTP designs. The simple structure of the Dynamic Transposition combiner (a simple selection from among all possible bit-permutations) would seem to not lend itself as well to statistical attack as conventional complex block cipher designs. Key Re-Use and Message Keys In any real system which uses a RNG confusion sequence, it is important that any particular encrypting sequence "never" be re-used. It is also important to be able to use a master key to send multiple messages without reducing the security of the system. This issue is known as "key re-use." We can solve both issues by introducing "message keys." One way to support the re-use of a master key is to create some large, random unknowable value which we call a "message key" and use as the key for data ciphering. Because this can be a completely arbitrary random value (e.g., from a noise generator source), we can repeatedly use the same master key securely. We send message key values to the other end by enciphering each under an unchanging master key. At the other end, the message key is first deciphered, and the exposed random value is used as the key to decipher the data. This is standard stream-cipher technology. The necessary advantage of a message key is to support key-reuse. Another advantage is to prevent attacks which depend upon having the same key across multiple messages. But an even greater advantage is to skip past the small and (probably) structured master or user key to a large, flat-distributed message key. For the past decade I have often used random 992-bit message keys. The concept of a message key pre-dates the similar if more published term "session key." But a "session" refers to the establishment of logical connection in a network or system, a concept which is both unnecessary and extraneous to ciphering per se. And even when a logical session exists, we might be wise to use different message key on every transmission in a potentially-long session. Thus, the term "session key" simply does not capture the cryptographic essence of the problem. ATTACKS Complex and hard-to-refute conventional block-cipher attacks, such as Differential and Linear Cryptanalysis, would seem to be completely irrelevant to ciphers of the Dynamic Transposition type. Where there are no S-boxes, there are no linear or differential relations in S-boxes. And where there is no Feistel structure, there is no ability to peel off Feistel layers. All this is a serious advantage. The classic attack on transposition, "multiple anagramming," is avoided by having a different permutation for every block. The use of random message keys forces each message to use a different encryption sequence. This also prevents the "bit flipping" sort of defined-plaintext attacks which attempt to reveal the permutation. The classic sort of codebook attack is avoided first by having a huge block size, and next by not attempting to re-use permutations. Note that conventional block ciphers have the first advantage only to a lesser extent, and the second advantage not at all, which is why they need "modes of operation." Known-plaintext attacks would be a first step in an attempt to attack the RNG as in a stream cipher. But with Dynamic Transposition, known-plaintext does not disclose the enciphering permutation, because a plethora of different bit-permutations will produce exactly the same ciphertext from exactly the same plaintext. A successful attack would thus require some way to distinguish more probable permutations from less probable ones. Such an attack would seem to be avoided by proper shuffling. And should the opponents somehow find the correct permutation, attempts to find the shuffling RNG sequence would be thwarted by double-shuffling. SUMMARY A novel, relatively easy-to-design and easy-to-analyze type of cipher has been presented. There would seem to be ample reason to consider Dynamic Transposition to be yet another "unbreakable" cipher, when properly implemented. In marked contrast to most "unbreakable" ciphers, Dynamic Transposition strength arguments are exactly the same sort of arguments we use for keys: A correct key exists, but is safe when hidden among many others just like it. These arguments are simple, fundamental to all keyed ciphers of every type, and do not depend upon unproven assumptions. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 19 Jan 2001 01:07:18 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3a678cf2.21708539@news.powersurfr.com> References: <3a67737e.15537635@news.io.com> Newsgroups: sci.crypt Lines: 19 I thank you for an interesting post. Some people will be quite shocked at the unconventional nature of transposition, though. I will just content myself with noting that, particularly if the units being transposed are larger than a bit, if one relies exclusively on transposition, some aspects of the plaintext are preserved in the ciphertext. (Even if one transposes single bits, the output has the same number of 1 bits as the input.) Hence, I am going to recommend what you probably realize quite well in any case for the benefit of other readers: that while transposition is a worthy encipherment method that is unjustly neglected, it should not be used completely alone; it is worthwhile to use it in combination with substitution. John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 19 Jan 2001 03:41:40 GMT From: Benjamin Goldberg <goldbb2@earthlink.net> Message-ID: <3A67B775.D599976A@earthlink.net> References: <3a678cf2.21708539@news.powersurfr.com> Newsgroups: sci.crypt Lines: 28 John Savard wrote: > > I thank you for an interesting post. > > Some people will be quite shocked at the unconventional nature of > transposition, though. > > I will just content myself with noting that, particularly if the units > being transposed are larger than a bit, if one relies exclusively on > transposition, some aspects of the plaintext are preserved in the > ciphertext. (Even if one transposes single bits, the output has the > same number of 1 bits as the input.) You seem to be ignoring that before shuffling, the data is accumulated into bit-balanced blocks. Did you read the whole paper? > Hence, I am going to recommend what you probably realize quite well in > any case for the benefit of other readers: that while transposition is > a worthy encipherment method that is unjustly neglected, it should not > be used completely alone; it is worthwhile to use it in combination > with substitution. > > John Savard > http://home.ecn.ab.ca/~jsavard/crypto.htm -- Most scientific innovations do not begin with "Eureka!" They begin with "That's odd. I wonder why that happened?"
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 19 Jan 2001 05:21:13 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3a67c966.290789@news.powersurfr.com> References: <3A67B775.D599976A@earthlink.net> Newsgroups: sci.crypt Lines: 88 On Fri, 19 Jan 2001 03:41:40 GMT, Benjamin Goldberg <goldbb2@earthlink.net> wrote, in part: >You seem to be ignoring that before shuffling, the data is accumulated >into bit-balanced blocks. Did you read the whole paper? I admit that I only skimmed through it. I saw the word 'bit-balanced', but didn't look closely. Upon looking again, I see that he indeed explicitly mentioned this point. However, I note that details of bit-balancing were not given. If the data is *not* pre-processed or compressed or whatever, and if the point at which a block is cut off depends on what bits are in the block (and the extent of the need for balancing) then that has to be indicated somehow, and the indications need to be encrypted... this could get quite messy. Of course, a *simple* way of dealing with this problem would be to code 6 bits of binary input to an 8-bit byte in a 4 of 8 code, using 64 of the 70 possible values. This would be a brute-force approach, but it would mean that one would not have a data-dependent concern with the block lengths. They could be uniform, or chosen randomly. I suppose even with a substitution phase, if one ensures bit balance, the transposition phase is made maximally strong; but _then_ one has a redundancy problem (since after transposition, any simplistic scheme of ensuring bit balance wouldn't be preserved - i.e. after a bit transpose of bytes in a 4 of 8 code, each byte of the result would not necessarily have exactly four 1 bits). Of course, data already _encrypted_ by a substitution phase could be assumed or hoped to have good enough bit balance, or failing that the substitution could be strong enough to ensure security. (If the substitution is on short blocks, then the key for the substitution must vary with each short block, else a plaintext consisting of identical short blocks could send a signal through the transposition...) Basically, the problem is that bit-balanced binary data and raw arbitrary binary data aren't a good fit to each other. Six bits of arbitrary binary data -> 8 bits of 4 of 8 coded data -> 8 bits of binary data having an overall bit balance means that the 8 bits of finally-encrypted data can't be compressed all that much. Of course, the initial means of achieving bit-balance needn't be as inefficient as a 4 of 8 code, but it still *won't* be fully optimal over the entire transposition block length. Whatever means of obtaining bit-balance is used, it will need a smaller "window" than a whole transposition block to be reasonably efficient. This expansion of the data will, I fear, like the autokey nature (making for poor error-recovery properties) of Dynamic Substitution, condemn Dynamic Transposition in the specific form described here to marginality. The market does not want to hear of encryption methods that are awkwards - that can't be used, for example, to encrypt a sector of a disk and fit the encrypted result in a sector of a disk. Combining substitution and transposition - and using a Feistel-like structure to make the transposition key for one half of a block depend on the contents of the other half (thus obtaining the variability Mr. Ritter rightly notes as essential to avoid multiple anagramming) - is capable of producing a much more well-behaved and "conventional" cipher. This is not to say, however, that the concepts presented here are not useful. Terry Ritter has shown how one _could_, even at the cost of inconveniences people aren't usually willing to bear, make a secure cipher based on transposition alone. This is of theoretical significance, and that, all by itself, is genuinely valuable. (It might also be noted that the requirement that each transposition step must uniformly be capable of producing all N! permutations of bits is likely to make the transposition steps computationally inefficient, so I think that this is another unfashionable aspect of the specific proposal given. Although in this case, unfashionable does not mean unsound: that is a desirable ideal.) The fact that bit balancing is not going to produce, by any reasonable algorithm, all N!/(N/2)!^2 possible bit-balanced blocks as input to the transposition, my earlier objection to this scheme, also impinges on the value of this... John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 19 Jan 2001 06:26:38 GMT From: Benjamin Goldberg <goldbb2@earthlink.net> Message-ID: <3A67DE08.A9B31B76@earthlink.net> References: <3a67c966.290789@news.powersurfr.com> Newsgroups: sci.crypt Lines: 173 John Savard wrote: > > On Fri, 19 Jan 2001 03:41:40 GMT, Benjamin Goldberg > <goldbb2@earthlink.net> wrote, in part: > > >You seem to be ignoring that before shuffling, the data is > >accumulated into bit-balanced blocks. Did you read the whole paper? > > I admit that I only skimmed through it. I saw the word 'bit-balanced', > but didn't look closely. > > Upon looking again, I see that he indeed explicitly mentioned this > point. However, I note that details of bit-balancing were not given. > If the data is *not* pre-processed or compressed or whatever, and if > the point at which a block is cut off depends on what bits are in the > block (and the extent of the need for balancing) then that has to be > indicated somehow, and the indications need to be encrypted... Not quite. Let's assume that we are using 128 bit blocks. The front of the block contains data, the end of the block contains balancing bits. If the balancing bits are all 1s, then all 0s (or vice versa), and we fill in as many bytes of data as we can into the front of the block, only one of the balancing bytes will contain both ones and zeros, and that will be the first balancing byte. All of the rest of the balancing bytes, from there to the end of the file, will contain all ones, or all zeros. No external data is needed to indicate where the balancing bytes begin. > > this could get quite messy. > > Of course, a *simple* way of dealing with this problem would be to > code 6 bits of binary input to an 8-bit byte in a 4 of 8 code, using > 64 of the 70 possible values. This would be a brute-force approach, > but it would mean that one would not have a data-dependent concern > with the block lengths. They could be uniform, or chosen randomly. Huh? I don't get what you're saying. > I suppose even with a substitution phase, if one ensures bit balance, > the transposition phase is made maximally strong; but _then_ one has a > redundancy problem (since after transposition, any simplistic scheme > of ensuring bit balance wouldn't be preserved - i.e. after a bit > transpose of bytes in a 4 of 8 code, each byte of the result would not > necessarily have exactly four 1 bits). We have a nice big 128 bit block. We shuffle all the bits in it. We are not shuffling the bytes in it. If bits were balanced before shuffling the bits, they will certainly be balanced after we shuffle the bits. [snip] > Of course, the initial means of achieving bit-balance needn't be as > inefficient as a 4 of 8 code, but it still *won't* be fully optimal > over the entire transposition block length. Whatever means of > obtaining bit-balance is used, it will need a smaller "window" than a > whole transposition block to be reasonably efficient. bal = (# bits in block) / 2 while( (unfilled bytes - 1) can be used to balance the block ) get a byte, put it in the block z = num 0s in block o = num 1s in block z = b - z // num 0s needed to balance block o = b - o // num 1s needed to balance block assert( (z<8) || (o<8) ); if( o < z ) { assert( o > 0 && o < 8 ) put the value (0xFF >> o) in block z = z - (8 - o) fill rest of byte with z/8 0xFF values } else if( z < o ) { assert( z > 0 && z < 8 ) put the value (0xFF >> (8-z)) in block o = o - (8 - z) fill rest of byte with o/8 0x00 values } else { assert( z == 4 && o == 4 ) put the value 0xF0 in block } > This expansion of the data will, I fear, like the autokey nature > (making for poor error-recovery properties) of Dynamic Substitution, > condemn Dynamic Transposition in the specific form described here to > marginality. Only if you try to balance very small blocks using the method which you invented, rather than using normal sized blocks (128 or 256 or 512 bits). If one compresses first, there's almost no data expansion, since with any good compression scheme, the output is almost always nearly bit-balanced. > The market does not want to hear of encryption methods > that are awkwards - that can't be used, for example, to encrypt a > sector of a disk and fit the encrypted result in a sector of a disk. Well, considering that with Ritter's scheme for bit balancing, which I described above, there is *always* one byte of message expansion per block, we almost certainly would not want to use this to encrypt disk sectors -- simply because, for disk sector encryption, we want little or no expansion. However, for encrypting a stream, or a file [at user level], this is not as much of a problem. One byte of expansion for every 32 bytes of message is acceptable. > Combining substitution and transposition - and using a Feistel-like > structure to make the transposition key for one half of a block depend > on the contents of the other half (thus obtaining the variability Mr. > Ritter rightly notes as essential to avoid multiple anagramming) - is > capable of producing a much more well-behaved and "conventional" > cipher. The "transposition key," which you speak of as if it were the key to a normal block cipher, is actually the key of a PRNG, whose output is fed into a function which shuffles bits. The PRNG is not rekeyed between blocks. > This is not to say, however, that the concepts presented here are not > useful. Terry Ritter has shown how one _could_, even at the cost of > inconveniences people aren't usually willing to bear, make a secure > cipher based on transposition alone. The inconvenience is that of the expansion due to bit balancing blocks. With his scheme for doing this, there is very little expansion, and thus little inconvenience. Expansion is minimized if one compresses before encrypting, which is done anway with most good schemes. > This is of theoretical significance, and that, all by itself, is > genuinely valuable. > > (It might also be noted that the requirement that each transposition > step must uniformly be capable of producing all N! permutations of > bits is likely to make the transposition steps computationally > inefficient, so I think that this is another unfashionable aspect of > the specific proposal given. Although in this case, unfashionable does > not mean unsound: that is a desirable ideal.) for( i = N-1; i > 0; --i ) { swap( bit[i], bit[ PRNG_ranmod(i+1) ] ) PRNG_ranmod *can* be made unbiased and fairly efficient, and if it is, then we will have an unbiased selection of all N! transpositions. > The fact that bit balancing is not going to produce, by any reasonable > algorithm, all N!/(N/2)!^2 possible bit-balanced blocks as input to > the transposition, my earlier objection to this scheme, also impinges > on the value of this... I thought that the number of bit balanced, N bit blocks was (N/2)!(N/2)! Of course, I haven't done combinatorics in a while, so I might be wrong. Anyway, since every bit-balanced block is a permutation of any other bit-balanced block, it doesn't matter. If all encryption permutations are equally likely (which they are), your point is invalidated. Your statement is akin to saying that since all 2^N plaintexts are not equally likely, OTP is insecure. My response is analogous to saying that if all pads used in OTP are equally likely, then it doesn't matter if the plaintexts are biased. If a Truly Random string of bits is used instead of a PRNG, (and this string is used once), then, informationwise, this system is precisely as secure as OTP, AFAIKS. -- Most scientific innovations do not begin with "Eureka!" They begin with "That's odd. I wonder why that happened?"
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 19 Jan 2001 08:56:50 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3a67fe34.1042739@news.powersurfr.com> References: <3A67DE08.A9B31B76@earthlink.net> Newsgroups: sci.crypt Lines: 81 On Fri, 19 Jan 2001 06:26:38 GMT, Benjamin Goldberg <goldbb2@earthlink.net> wrote, in part: >only one of the balancing bytes will contain both ones and zeros, and >that will be the first balancing byte. All of the rest of the balancing >bytes, from there to the end of the file, will contain all ones, or all >zeros. Yes, you're right. I disliked simple padding enough not to think through whether or not it might be workable. quoting me: >> Of course, a *simple* way of dealing with this problem would be to >> code 6 bits of binary input to an 8-bit byte in a 4 of 8 code, using >> 64 of the 70 possible values. This would be a brute-force approach, >> but it would mean that one would not have a data-dependent concern >> with the block lengths. They could be uniform, or chosen randomly. >Huh? I don't get what you're saying. I considered just balancing each byte as I went along, simply because it was more straightforwards. >We have a nice big 128 bit block. We shuffle all the bits in it. We >are not shuffling the bytes in it. If bits were balanced before >shuffling the bits, they will certainly be balanced after we shuffle the >bits. That wasn't the problem I was thinking of. I was thinking of the data expansion needed to balance the bits - and an additional data expansion caused by the transposition messing up any shortcuts we took to do the balancing, so that I couldn't take the balanced output and convert it to the same number of unbalanced bits as I got as input. >> The fact that bit balancing is not going to produce, by any reasonable >> algorithm, all N!/(N/2)!^2 possible bit-balanced blocks as input to >> the transposition, my earlier objection to this scheme, also impinges >> on the value of this... >I thought that the number of bit balanced, N bit blocks was (N/2)!(N/2)! >Of course, I haven't done combinatorics in a while, so I might be wrong. Here, I know I'm right. Arrange the characters of the string abcd1234 in all possible ways, and there are 8! possibilities. Now, replace each of the characters abcd by zeroes. You have eliminated the 4! different ways of arranging those letters, so the number of different possibilities is now 8!/4!. Replace each of 1234 by 1, and you have divided by 4! yet again. Thus, 8*7*6*5/4*3*2*1 = 2*7*5 = 70, the number of characters in a 4 of 8 code. (Which is why I can change 6 bits to 8 bits, get guaranteed bit balance, and not have to do anything funny, at the cost of extra redundancy.) >If a Truly Random string of bits is used instead of a PRNG, (and this >string is used once), then, informationwise, this system is precisely as >secure as OTP, AFAIKS. This is true, if the input is fully balanced, not just approximately, because the method calls for all N! permutations to be equally likely in this case. That's why I agree it is important from the theoretical standpoint, it shows that transposition can be used alone to create a cipher of serious strength. I still ask, would anyone want to do it, because it appears to me this has a bandwidth cost that people will see no need to incur. I assumed that bit-balancing is done over smaller extents than transposition, because in the practical non-OTP case, the largest possible transposition block improves security. John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 26 Jan 2001 14:08:19 -0700 From: "Tony T. Warnock" <u091889@cic-mail.lanl.gov> Message-ID: <3A71E743.8F710ACB@cic-mail.lanl.gov> References: <3a67fe34.1042739@news.powersurfr.com> Newsgroups: sci.crypt Lines: 39 The efficiency of the balanced pre-substitutions can be improved by taking more bits. Of course a table-lookup gets too big rather quickly. Output Input Size Length Expansion 6 4 50.0% 8 6 33.3% 10 7 42.9% 12 9 33.3% 14 11 27.3% 16 13 23.1% 18 15 20.0% 20 17 17.6% 22 19 15.8% 24 21 14.3% 26 23 13.0% 28 25 12.0% 30 27 11.1% 32 29 10.3% 64 60 6.7% 128 124 3.2% 256 251 2.0% 512 507 1.0% 1024 1018 0.6% The 17 bit input is probably the largest that could be done by table lookup. I haven't tried to see if there is a function to do the mappings (which would make things more feasible.) If one could live with a 1-bit bias, then the odd-sized outputs could be used. It's more efficient. A 15 bit input block then maps to a 17 bit output block. Or one could use the evenly balanced and 1-off blocks to improve efficiency. Then 15 bit input blocks map to 16 bit output blocks with 7,8, or 9 bits.
Subject: Re: Dynamic Transposition Revisited (long) Date: Thu, 18 Jan 2001 21:46:47 -0800 From: "John A. Malley" <102667.2235@compuserve.com> Message-ID: <3A67D4C7.C6F79499@compuserve.com> References: <3a67737e.15537635@news.io.com> Newsgroups: sci.crypt Lines: 98 Terry Ritter wrote: [snip] > > One of the needed components which has not been described > is the bit-balancing process. > > Bit-Balanced Blocks > > Some of the analytic and strength advantages of Dynamic > Transposition depend upon having the same number of 1's > and 0's in each block, which is called "bit-balance." > Exact bit-balance can be achieved by accumulating data to > a block byte-by-byte, only as long as the block can be > balanced by adding appropriate bits at the end. Then the > block is ciphered, and another block filled. > > We will always add at least one byte of "balance data," > at the end of a block, and only the first balance byte, > immediately after the data, will contain both 1's and 0's. > We can thus transparently remove the balance data by > stepping from the end of the block, past the first byte > containing both 1's and 0's. I had a few immediate hunches about cryptanalysis of dynamic transposition but realized they may spring from misunderstanding of the algorithm. May I paraphrase the description of block balancing to make sure I understand the mechanism as envisioned? And please, correct me if I got this wrong. Given plaintext P, 1) divvy P into bytes as P[1], P[2], P[3] ... P[n], 2) build up (one at a time) blocks of size k bytes, B[1], B[2], B[3] ... B[m] where m < n, and sequential plaintext bytes are assigned to a given block B[i] where B[i] is the concatenation of a few plaintext bytes, followed by a special byte that has 0s and 1s in it, followed by bytes of all zeros or all ones - like P[1] | P[2] | ... | P[L] | a block of 1s and 0s | 00000000 | 11111111 | ... 00000000 = B[i] or P[1] | P[2] | ... | P[L] | a block of 1s and 0s | "0" | "255" | ... "0" = B[i] Is this an accurate description of the proposed bit balancing? I'm curious about fixed bit patterns or expected bit patterns (if any) that end up in the appended plaintext, for they may serve as the chink in the armor for cryptanalysis. For example, consider 11111000 | 11111000 | as plaintext, which is then followed by a "signal byte" 11111000 | 11111000 | 00110011 | to "balance out" the 1s and 0s in the first two bytes of plaintext, a then followed by two bytes of all 0s and all 1s to round off the block as 11111000 | 11111000 | 00101010 | 00000000 | 11111111 or, also acceptable, 11111000 | 11111000 | 00101010 | 11111111 | 00000000 Can that "signal" byte take on only certain values when it "balances" the preceding bytes, and can the bytes of "0" and "255" value following occur in any order, or is it a fixed order? Uh-oh. I just realized I must have this wrong. I came up with an example that won't balance the way I described above - 10000000 | 00000000 | there is no value I can plug into the "signal" byte that's a mixture of 1s and 0s, to follow these, that gets followed by all 0 and all 1s bytes, that balance the resulting block. 10000000 | 00000000 | XXXXXXXX | 00000000 | 11111111 Please help, how does the bit-balancing work? John A. Malley 102667.2235@compuserve.com
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 19 Jan 2001 07:23:29 GMT From: Benjamin Goldberg <goldbb2@earthlink.net> Message-ID: <3A67EB6C.E9E2CD64@earthlink.net> References: <3A67D4C7.C6F79499@compuserve.com> Newsgroups: sci.crypt Lines: 118 John A. Malley wrote: > > Terry Ritter wrote: > [snip] > > > > One of the needed components which has not been described > > is the bit-balancing process. > > > > Bit-Balanced Blocks > > > > Some of the analytic and strength advantages of Dynamic > > Transposition depend upon having the same number of 1's > > and 0's in each block, which is called "bit-balance." > > Exact bit-balance can be achieved by accumulating data to > > a block byte-by-byte, only as long as the block can be > > balanced by adding appropriate bits at the end. Then the > > block is ciphered, and another block filled. > > > > We will always add at least one byte of "balance data," > > at the end of a block, and only the first balance byte, > > immediately after the data, will contain both 1's and 0's. > > We can thus transparently remove the balance data by > > stepping from the end of the block, past the first byte > > containing both 1's and 0's. > > I had a few immediate hunches about cryptanalysis of dynamic > transposition but realized they may spring from misunderstanding of > the algorithm. > > May I paraphrase the description of block balancing to make sure I > understand the mechanism as envisioned? And please, correct me if I > got this wrong. > > Given plaintext P, > > 1) divvy P into bytes as P[1], P[2], P[3] ... P[n], > > 2) build up (one at a time) blocks of size k bytes, B[1], B[2], B[3] > ... B[m] where m < n, and sequential plaintext bytes are assigned to > a given block B[i] where B[i] is the concatenation of a few plaintext > bytes, followed by a special byte that has 0s and 1s in it, followed > by bytes of all zeros or all ones - like > > P[1] | P[2] | ... | P[L] | a block of 1s and 0s | 00000000 | > 11111111 | ... 00000000 = B[i] > > or > > P[1] | P[2] | ... | P[L] | a block of 1s and 0s | "0" | "255" | ... > "0" = B[i] > > Is this an accurate description of the proposed bit balancing? Almost. It's more like if( P[1..L] has more 0s than 1s ) { P[1] | P[2] | ... | P[L] | XXXXXXX | 00000000 | 00000000 = B[i] Where XXXXXXXX is some number of 1s and 0s. } else { P[1] | P[2] | ... | P[L] | XXXXXXX | 11111111 | 11111111 = B[i] Where XXXXXXXX is some number of 0s and 1s. } Only when the plaintext reaches EOF does it look at all like your example. Here's some C code, to [hopefully] make things clear: unsigned char balanced[16]; // 128 bits unsigned int bp = 0; // pointer to balanced data. unsigned int z = 0, o = 0; // zeros, ones. extern unsigned h(unsigned); // hamming weight do { unsigned char rnext = peekc(); unsigned int zn = z+h(rnext); unsigned int on = o+8-h(rnext); if( abs(zn-on) >= 64 ) break; balanced[bp++] = getc(); z = zn; o = on; } while( bp < 15 ); z = 128 - z; o = 128 - o; // change from how many 0s and 1s are there, to how many are needed? if( o < z ) { balanced[bp++] = 0xFF << (8-o); while( bp < 16 ) balanced[bp++] = 0x00; } else { balanced[bp++] = 0xFF >> z; while( bp < 16 ) balanced[bp++] = 0xFF; } Thus, blocks are either raw data, balance byte, 0 or more 0xFF bytes or raw data, balance byte, 0 or more 0x00 bytes. To reverse the transform, we do the following: if the last byte is 0x00, then we remove all 0x00 bytes from the end, and the first non-0x00 byte. if the last byte is 0xFF, then we remove all 0xFF bytes from the end, and the first non-0xFF byte. otherwise, we simply remove the last byte. The data near the EOF is handled slightly differently, of course, but I'm not going to write code for it now (if ever). > I'm curious about fixed bit patterns or expected bit patterns (if any) > that end up in the appended plaintext, for they may serve as the chink > in the armor for cryptanalysis. Do expected bit patterns/fixed bit patterns in plaintext provide a chink in the armor of OTP? -- Most scientific innovations do not begin with "Eureka!" They begin with "That's odd. I wonder why that happened?"
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 19 Jan 2001 18:44:20 +0100 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3A687CF4.F4897FBE@t-online.de> References: <3A67EB6C.E9E2CD64@earthlink.net> Newsgroups: sci.crypt Lines: 45 Benjamin Goldberg wrote: > > John A. Malley wrote: > > May I paraphrase the description of block balancing to make sure I > > understand the mechanism as envisioned? And please, correct me if I > > got this wrong. > > > > Given plaintext P, > > > > 1) divvy P into bytes as P[1], P[2], P[3] ... P[n], > > > > 2) build up (one at a time) blocks of size k bytes, B[1], B[2], B[3] > > ... B[m] where m < n, and sequential plaintext bytes are assigned to > > a given block B[i] where B[i] is the concatenation of a few plaintext > > bytes, followed by a special byte that has 0s and 1s in it, followed > > by bytes of all zeros or all ones - like > > > > P[1] | P[2] | ... | P[L] | a block of 1s and 0s | 00000000 | > > 11111111 | ... 00000000 = B[i] > > > > or > > > > P[1] | P[2] | ... | P[L] | a block of 1s and 0s | "0" | "255" | ... > > "0" = B[i] > > > > Is this an accurate description of the proposed bit balancing? > > Almost. It's more like > if( P[1..L] has more 0s than 1s ) { > P[1] | P[2] | ... | P[L] | XXXXXXX | 00000000 | 00000000 = B[i] > Where XXXXXXXX is some number of 1s and 0s. > } else { > P[1] | P[2] | ... | P[L] | XXXXXXX | 11111111 | 11111111 = B[i] > Where XXXXXXXX is some number of 0s and 1s. > } [snip] I am certainly confused. What if, say, the block size is 4 bytes and one has (1) two bytes and (2) three bytes of information which are all 0's? Thanks. M. K. Shen
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 19 Jan 2001 21:53:33 GMT From: Benjamin Goldberg <goldbb2@earthlink.net> Message-ID: <3A68B75C.1FD8DA8D@earthlink.net> References: <3A687CF4.F4897FBE@t-online.de> Newsgroups: sci.crypt Lines: 59 Mok-Kong Shen wrote: > > Benjamin Goldberg wrote: > > > > John A. Malley wrote: > > > > May I paraphrase the description of block balancing to make sure I > > > understand the mechanism as envisioned? And please, correct me if > > > I got this wrong. > > > > > > Given plaintext P, > > > > > > 1) divvy P into bytes as P[1], P[2], P[3] ... P[n], > > > > > > 2) build up (one at a time) blocks of size k bytes, B[1], B[2], > > > B[3] ... B[m] where m < n, and sequential plaintext bytes are > > > assigned to a given block B[i] where B[i] is the concatenation of > > > a few plaintext bytes, followed by a special byte that has 0s and > > > 1s in it, followed by bytes of all zeros or all ones - like > > > > > > P[1] | P[2] | ... | P[L] | a block of 1s and 0s | 00000000 | > > > 11111111 | ... 00000000 = B[i] > > > > > > or > > > > > > P[1] | P[2] | ... | P[L] | a block of 1s and 0s | "0" | "255" | > > > ... "0" = B[i] > > > > > > Is this an accurate description of the proposed bit balancing? > > > > Almost. It's more like > > if( P[1..L] has more 0s than 1s ) { > > P[1] | P[2] | ... | P[L] | XXXXXXX | 00000000 | 00000000 = B[i] > > Where XXXXXXXX is some number of 1s and 0s. > > } else { > > P[1] | P[2] | ... | P[L] | XXXXXXX | 11111111 | 11111111 = B[i] > > Where XXXXXXXX is some number of 0s and 1s. > > } > [snip] > > I am certainly confused. What if, say, the block size is > 4 bytes and one has (1) two bytes and (2) three bytes of > information which are all 0's? Thanks. A 4 byte block is really small. If you have two bytes of 0x00s, then one byte goes into the first block, one balance byte 0x00 is added, and two balance bytes 0xFFFF are added. The next 0x00 byte goes into the next block. With 3 0x00s it's similar. A 5 byte block is better. Two 0x00 bytes go in, then a 0x0F byte, then 0xFFFF. With three 0x00s, two bytes go into the first block, then one into the next. Fortuneatly, we won't be likely to be using 4 byte blocks, but much larger, perhaps 15 or 16 bytes. -- Most scientific innovations do not begin with "Eureka!" They begin with "That's odd. I wonder why that happened?"
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 19 Jan 2001 22:05:48 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3a68b916.9441029@news.io.com> References: <3A68B75C.1FD8DA8D@earthlink.net> Newsgroups: sci.crypt Lines: 74 On Fri, 19 Jan 2001 21:53:33 GMT, in <3A68B75C.1FD8DA8D@earthlink.net>, in sci.crypt Benjamin Goldberg <goldbb2@earthlink.net> wrote: >Mok-Kong Shen wrote: >> >> Benjamin Goldberg wrote: >> > >> > John A. Malley wrote: >> >> > > May I paraphrase the description of block balancing to make sure I >> > > understand the mechanism as envisioned? And please, correct me if >> > > I got this wrong. >> > > >> > > Given plaintext P, >> > > >> > > 1) divvy P into bytes as P[1], P[2], P[3] ... P[n], >> > > >> > > 2) build up (one at a time) blocks of size k bytes, B[1], B[2], >> > > B[3] ... B[m] where m < n, and sequential plaintext bytes are >> > > assigned to a given block B[i] where B[i] is the concatenation of >> > > a few plaintext bytes, followed by a special byte that has 0s and >> > > 1s in it, followed by bytes of all zeros or all ones - like >> > > >> > > P[1] | P[2] | ... | P[L] | a block of 1s and 0s | 00000000 | >> > > 11111111 | ... 00000000 = B[i] >> > > >> > > or >> > > >> > > P[1] | P[2] | ... | P[L] | a block of 1s and 0s | "0" | "255" | >> > > ... "0" = B[i] >> > > >> > > Is this an accurate description of the proposed bit balancing? >> > >> > Almost. It's more like >> > if( P[1..L] has more 0s than 1s ) { >> > P[1] | P[2] | ... | P[L] | XXXXXXX | 00000000 | 00000000 = B[i] >> > Where XXXXXXXX is some number of 1s and 0s. >> > } else { >> > P[1] | P[2] | ... | P[L] | XXXXXXX | 11111111 | 11111111 = B[i] >> > Where XXXXXXXX is some number of 0s and 1s. >> > } >> [snip] >> >> I am certainly confused. What if, say, the block size is >> 4 bytes and one has (1) two bytes and (2) three bytes of >> information which are all 0's? Thanks. > >A 4 byte block is really small. If you have two bytes of 0x00s, then >one byte goes into the first block, one balance byte 0x00 is added, and >two balance bytes 0xFFFF are added. The next 0x00 byte goes into the >next block. With 3 0x00s it's similar. > >A 5 byte block is better. Two 0x00 bytes go in, then a 0x0F byte, then >0xFFFF. With three 0x00s, two bytes go into the first block, then one >into the next. > >Fortuneatly, we won't be likely to be using 4 byte blocks, but much >larger, perhaps 15 or 16 bytes. When I think of Dynamic Transposition, I think of 512-byte / 4096-bit blocks. This stuff scales almost linearly, and 512 bytes is just a small buffer. I suspect that if we run the numbers, some modest minimum size -- perhaps 128 bits / 16 bytes -- is required for serious strength. We can scale it down to look at, of course, but we can't expect strength there as well. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Dynamic Transposition Revisited (long) Date: Wed, 24 Jan 2001 02:24:00 GMT From: AllanW <allan_w@my-deja.com> Message-ID: <94lebq$2gj$1@nnrp1.deja.com> References: <3a68b916.9441029@news.io.com> Newsgroups: sci.crypt Lines: 97 ritter@io.com (Terry Ritter) wrote: > When I think of Dynamic Transposition, I think of 512-byte / 4096-bit > blocks. This stuff scales almost linearly, and 512 bytes is just a > small buffer. > > I suspect that if we run the numbers, some modest minimum size -- > perhaps 128 bits / 16 bytes -- is required for serious strength. We > can scale it down to look at, of course, but we can't expect strength > there as well. Really? I think your original paper made a good case for allowing short block sizes. Although the 4-byte block seems to be stretching things too far, a 16-byte block would work well. In degenerate cases such as all 0's, this would allow 7 bytes of data followed by 9 bytes of filler. For typical ASCII data this would allow 10 bytes of data and 6 bytes of filler. For data that's already balanced or very nearly so, we could put 15 bytes of data into a 16-byte block. Larger block sizes would help to make the overhead smaller, though. The best case will always require 1 byte of filler, while the worst case will always require N/2+1 bytes of filler (for N-byte blocks). As I understood the filler bits to work, the data would look like this before the transposition begins: if the data had more 0-bits than 1-bits, it would take the form XX....XX 00..00 11..11 where X bits represent the data, and then there are 1-8 0-bits followed by 1 or more 1-bits. If the data has more 1-bits than 0-bits, simply reverse the filler: XX....XX 11..11 00..00 this time using 1-8 1-bits and then 1 or more 0-bits. Another way to say this is to show what the filler would look like for various imbalances. Here I'll assume that the data has more 0-bits than 1-bits; use the complement if the opposite is true. If there are B more 0-bits than 1-bits, then the filler looks like (in hex): B=0 0F B=2 1F B=4 3F B=6 7F B=8 0FFF B=10. 1FFF B=12. 3FFF B=14. 7FFF B=16. 0FFFFF B=18. 1FFFFF B=20. 3FFFFF B=22. 7FFFFF B=24. 0FFFFFFF ...and so on. (Note that the number of data bits is always divisible by 8 and therefore an even number. This means that the number of 0-bits, minus the number of 1-bits, must also be an even number.) In the worst case for a 16-byte (128-bit) block, the data would be 56 0-bits. Then the program would add 8 more 0-bits and 64 1-bits. In the obvious best case, the data has 60 0-bits and 60 1-bits in any order. Then the filler is 0F -- 4 0-bits and 4 1-bits. The best case (15 bytes in a 16-byte block) is also achieved when there are up to 6 more 1-bits than 0-bits or vice-versa -- the filler still fits in one byte. If there is any weakness at all to this scheme, it's that even though you're using a fixed-size block, you cannot predict in advance how many blocks the message will need because each block contains between N/2-1 and N-1 bytes of data. On the other hand, this could be considered a strength because of the flip side of this observation: once you know how long the ciphertext is, you can calculate how many fixed-size blocks were used, but this does not tell you how long the original plaintext was. The larger the blocksize, the more true this is. Other than that, if there's any reason why a 16-byte block is less secure than a 512-byte block, it sure isn't obvious to me! (For whatever that's worth) -- Allan_W@my-deja.com is a "Spam Magnet," never read. Please reply in newsgroups only, sorry. Sent via Deja.com http://www.deja.com/
Subject: Re: Dynamic Transposition Revisited (long) Date: Wed, 24 Jan 2001 06:37:41 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3a6e77ff.11155622@news.io.com> References: <94lebq$2gj$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 166 On Wed, 24 Jan 2001 02:24:00 GMT, in <94lebq$2gj$1@nnrp1.deja.com>, in sci.crypt AllanW <allan_w@my-deja.com> wrote: >ritter@io.com (Terry Ritter) wrote: >> When I think of Dynamic Transposition, I think of 512-byte / 4096-bit >> blocks. This stuff scales almost linearly, and 512 bytes is just a >> small buffer. >> >> I suspect that if we run the numbers, some modest minimum size -- >> perhaps 128 bits / 16 bytes -- is required for serious strength. We >> can scale it down to look at, of course, but we can't expect strength >> there as well. > >Really? I think your original paper made a good case for >allowing short block sizes. Although the 4-byte block >seems to be stretching things too far, a 16-byte block >would work well. Which is what I just suggested. >In degenerate cases such as all 0's, >this would allow 7 bytes of data followed by 9 bytes of >filler. For typical ASCII data this would allow 10 bytes >of data and 6 bytes of filler. For data that's already >balanced or very nearly so, we could put 15 bytes of >data into a 16-byte block. Right. >Larger block sizes would help to make the overhead >smaller, though. Right. >The best case will always require 1 byte >of filler, Right. >while the worst case will always require N/2+1 >bytes of filler (for N-byte blocks). Looks right. >As I understood the filler bits to work, the data would >look like this before the transposition begins: if the >data had more 0-bits than 1-bits, it would take the form > XX....XX 00..00 11..11 >where X bits represent the data, and then there are 1-8 >0-bits followed by 1 or more 1-bits. If the data has >more 1-bits than 0-bits, simply reverse the filler: > XX....XX 11..11 00..00 >this time using 1-8 1-bits and then 1 or more 0-bits. That does not seem to be the way I did it. I don't understand having both 0's and 1's balancing bytes. If we have an excess of 0's, we want any full balancing bytes to be all 1's, with the mixed byte being what it needs to be. Since the mixed byte must be mixed to be a flag, it cannot balance a full 8 bits, but at most 6 (1000 0000 is an excess of 6 0's). >Another way to say this is to show what the filler >would look like for various imbalances. Here I'll >assume that the data has more 0-bits than 1-bits; use >the complement if the opposite is true. > > If there are B more 0-bits than 1-bits, then the > filler looks like (in hex): > > B=0 0F > B=2 1F > B=4 3F > B=6 7F > B=8 0FFF > B=10. 1FFF > B=12. 3FFF > B=14. 7FFF > B=16. 0FFFFF > B=18. 1FFFFF > B=20. 3FFFFF > B=22. 7FFFFF > B=24. 0FFFFFFF > ...and so on. Looks right. >(Note that the number of data bits is always divisible >by 8 and therefore an even number. This means that the >number of 0-bits, minus the number of 1-bits, must also >be an even number.) Right. In a fixed-size array of bits, changing a '1' to a '0' is to decrease the 1's-count by 1, and increase the 0's-count by 1, a difference of 2. >In the worst case for a 16-byte (128-bit) block, the >data would be 56 0-bits. Then the program would add 8 >more 0-bits and 64 1-bits. > >In the obvious best case, the data has 60 0-bits and >60 1-bits in any order. Then the filler is 0F -- 4 >0-bits and 4 1-bits. The best case (15 bytes in a >16-byte block) is also achieved when there are up to >6 more 1-bits than 0-bits or vice-versa -- the filler >still fits in one byte. Right. Thus the advantage of this particular balancing scheme: The flag byte is not wasted (or even counter-productive), but instead can participate in balancing. >If there is any weakness at all to this scheme, it's >that even though you're using a fixed-size block, you >cannot predict in advance how many blocks the message >will need because each block contains between N/2-1 and >N-1 bytes of data. Yes, but I think that's a strange thing to do anyway. Why would we predict the size in advance, when we obviously will traverse it soon? One might, I guess, allocate a buffer to hold the whole thing, but an alternative is to allocate big enough chunks as needed to make the allocation computation a nit. >On the other hand, this could be >considered a strength because of the flip side of this >observation: once you know how long the ciphertext is, >you can calculate how many fixed-size blocks were used, >but this does not tell you how long the original >plaintext was. The larger the blocksize, the more true >this is. Yes, I think so. >Other than that, if there's any reason why a 16-byte >block is less secure than a 512-byte block, it sure >isn't obvious to me! (For whatever that's worth) Right now, I don't see the issue as security. My main reason for using a large block would be to minimize balancing overhead, which would here be 1 byte in 16, or over 6 percent, minimum. Even 5 balancing bytes out of 512 would be under 1 percent. Also the larger block tends to reduce relative variation in balance, which is especially useful with random-like data. Another reason might be to reduce OS overhead in manipulating data. We certainly don't want to be asking the OS for 16-byte blocks, but of course we might well have a tight local buffering system. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Dynamic Transposition Revisited (long) Date: Fri, 26 Jan 2001 20:49:45 GMT From: AllanW <allan_w@my-deja.com> Message-ID: <94snt5$da4$1@nnrp1.deja.com> References: <3a6e77ff.11155622@news.io.com> Newsgroups: sci.crypt Lines: 87 > AllanW <allan_w@my-deja.com> wrote: > >As I understood the filler bits to work, the data would > >look like this before the transposition begins: if the > >data had more 0-bits than 1-bits, it would take the form > > XX....XX 00..00 11..11 > >where X bits represent the data, and then there are 1-8 > >0-bits followed by 1 or more 1-bits. I see now that I should have said, 1-7 0-bits and then 1 or more 1-bits. > >If the data has > >more 1-bits than 0-bits, simply reverse the filler: > > XX....XX 11..11 00..00 > >this time using 1-8 1-bits and then 1 or more 0-bits. And here I should have said: 1-7 1-bits and then 1 or more 0-bits. > >ritter@io.com (Terry Ritter) wrote: > That does not seem to be the way I did it. That's what I got out of it. Not word-for-word, of course. > I don't understand having both 0's and 1's balancing bytes. Surely you do...? It is so that we can always remove the balancing bytes without removing any meaningful data. What if the block has 16 more 0-bits than 1-bits, but the last byte of plaintext is 0x0F? You could balance the block by adding 2 more bytes of 0xFF, but then after decryption we could not identify the first byte of filler (as you say below: the mixed byte must be mixed to be a flag). > If we have an excess of 0's, we want any full balancing bytes to > be all 1's, with the mixed byte being what it needs to be. Since > the mixed byte must be mixed to be a flag, it cannot balance a > full 8 bits, but at most 6 (1000 0000 is an excess of 6 0's). Yes, exactly. And then following this, we have bytes with all 1-bits. I suppose that what I wrote above (1-7 0-bits, followed by 1 or more 1-bits) was stronger than absolutely needed. The mixed byte could be randomly mixed as well, so instead of using 1000-0000 we could just as easily have used 0001-0000. Is there any reason to do this randomly? If not, then my description fits the same pattern but is easier to describe. > >Another way to say this is to show what the filler > >would look like for various imbalances. Here I'll > >assume that the data has more 0-bits than 1-bits; use > >the complement if the opposite is true. > > > > If there are B more 0-bits than 1-bits, then the > > filler looks like (in hex): > > > > B=0 0F > > B=2 1F > > B=4 3F > > B=6 7F > > B=8 0FFF > > B=10. 1FFF > > B=12. 3FFF > > B=14. 7FFF > > B=16. 0FFFFF > > B=18. 1FFFFF > > B=20. 3FFFFF > > B=22. 7FFFFF > > B=24. 0FFFFFFF > > ...and so on. > > Looks right. Good, because in every case the first balance byte starts with 1-4 0-bits followed by 1-7 1-bits. -- Allan_W@my-deja.com is a "Spam Magnet," never read. Please reply in newsgroups only, sorry. Sent via Deja.com http://www.deja.com/
Subject: Re: Dynamic Transposition Revis