Some block ciphers handle data blocks of dynamically variable size. These are not stream ciphers, but are instead true block ciphers, in which each and every input bit affects each and every output bit in a balanced way. But in a large block, bits which are far apart must somehow produce similar effects, which exposes the possibility that mixing could be more effective for near bit positions than for far ones. We can explore possible locality in mixing by injecting data changes at different points across the plaintext data block, and counting the resulting bit-changes at multiple points across the ciphertext. Accumulated bit-change counts can be organized in a "contingency table" for a test of independence. Experiments conducted on Mixing and Variable Size Block Cipher constructions with 16-byte, 64-byte and even 512-byte (that is, 4096-bit) blocks show no evidence of mixing locality.

- Terry Ritter: Measured Distant Avalanche in Large Block Ciphers, the original article.
- Gary Ardell: "...I don't see the reasoning behind focusing on changes in individual bytes rather than on individual bits."
- Terry Ritter: "If we want to detect problems in 8-bit mixing, 8-bit values seem the appropriate size to address."
- Gary Ardell: "...run it through Diehard to see what if any failures show up."
- Terry Ritter: "...it would be wrong to simply throw ciphertext into a file and expect general tests to somehow derive information from the result."
- John Savard: "LUCIFER ... with its 128-bit blocks, was intended to handle blocks containing 64 bits of data, with identifying information and a serial counter (for randomization) in the other 64 bits."
- Terry Ritter: "What I call a dynamic keying field is indeed described in one of the Feistel patents (now expired). But it is not particularly useful when there are only 64 bits in a block..."

From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Measured Distant Avalanche in Large Block Ciphers (LONG!) Date: Thu, 05 Mar 1998 01:24:44 GMT Lines: 403 Message-ID: <34fdfea7.1999205@news.io.com> MEASURED DISTANT AVALANCHE IN LARGE BLOCK CIPHERS Terry Ritter ritter@io.com Ritter Software Engineering http://www.io.com/~ritter/ 1998-03-04 (Army Day) ABSTRACT Some block ciphers handle data blocks of dynamically variable size. These are not stream ciphers, but are instead true block ciphers, in which each and every input bit affects each and every output bit in a balanced way. But in a large block, bits which are far apart must somehow produce similar effects, which exposes the possibility that mixing could be more effective for near bit positions than for far ones. We can explore possible locality in mixing by injecting data changes at different points across the plaintext data block, and counting the resulting bit-changes at multiple points across the ciphertext. Accumulated bit-change counts can be organized in a "contingency table" for a test of independence. Experiments conducted on Mixing and Variable Size Block Cipher constructions with 16-byte, 64-byte and even 512-byte (that is, 4096-bit) blocks show no evidence of mixing locality. INTRODUCTION The ideal block cipher is a keyed simple substitution table of sufficient size. Unfortunately, with 128-bit blocks, there would be 2**128 entries in that table, which is completely out of the question. So the modern block cipher is a *construction* intended to *simulate* a keyed substitution of the desired size. At issue is the effectiveness of the construction technology; in particular, the ability of the mixing to handle distant bits equally well. A more fundamental question might be *why* one would *want* a large block cipher. The short answer is that there can be real advantages to large blocks: 1. Large blocks support an unsearchable amount of "uniqueness" or "entropy" in each plaintext block, which allows us to avoid randomization by block chaining. This means we can use electronic code book (ECB) mode, and avoid the need to generate and transport (or save) an initial value (IV). ECB mode also supports the ciphering of independent blocks, both in-parallel for high speed, and out-of-order as occurs in packet-oriented applications. 2. A large block has room for information other than data. For example, an authentication field can avoid a separate authentication pass across the data at a higher level, and thus speed overall operation. And a dynamic keying field can provide ultra-high-speed keying. That same field also can be seen as a strength-producing homophonic "mode," a useful block cipher mode which is simply impractical in ciphers which only have small blocks. Note that a cipher which supports blocks of dynamically *variable* size can handle "legacy" 64-bit blocks, "modern" 128-bit blocks, and even "independent" 64-byte blocks in a single unchanged program. Thus, when large blocks are inappropriate, legacy blocks are always available. And when large blocks are used, we can always "step down" the block size at the end of a message, and so limit data expansion to that of legacy ciphers. This means that there is little or no "down side" to using ciphers which have a dynamically variable block size. Here we seek to investigate the quality of the mixing in some large block constructions by experiment. AVALANCHE The term "avalanche" comes from Feistel [1], and refers to the observed property of a block cipher constructed in "rounds" with respect to a tiny change in the input. The change of a single input bit generally produces multiple bit-changes after one round, many more bit-changes after another round, and so on, until about half of the block will change. An analogy is drawn to an avalanche in snow, where a small initial effect can lead to a dramatic result. Feistel writes: "As the input moves through successive layers the pattern of 1's generated is amplified and results in an unpredictable avalanche. In the end the final output will have, on average, half 0's and half 1's . . . ." [p.22] In any block cipher we expect every input bit to affect every output bit: If we change an input bit, we expect about half of the output bits to change, and we expect this to be independent of input or output bit position. This is in fact inherent in the concept of a large invertible substitution, but when we *simulate* such a table, it becomes necessary to somehow force the "mixing" of every input bit into every output bit in a balanced way. We might use the term "distant avalanche" to refer to bit changes in a block position far removed from the input change. NEW MIXING TECHNOLOGIES Over the past decade of my full-time work in this field, I have had the rare privilege to introduce to cryptography two new and original forms of mixing for block cipher construction: Balanced Block Mixing and Variable Size Block Ciphers. These technologies mix more data, better, and with less effort than earlier techniques. For example, Mixing ciphers http://www.io.com/~ritter/CRYPHTML.HTM#BBMTech have a known mixing effort of n log n for n-bit blocks of any power-of-2 size. Further, each input byte is known to participate in each mixed result byte exactly once, and with the same significance. On the other hand, VSBC's http://www.io.com/~ritter/CRYPHTML.HTM#VSBCTech have a mixing effort which is *linear* in n for blocks of any size (to the byte), so these are often faster than Mixing designs. And the dynamically random block sizing available in VSBC designs can add a level of strength which is simply unavailable to *any* fixed-width cipher. The better quality mixing in these technologies allows diffusion and confusion operations to be optimized and applied separately. The result is cipher designs which are relatively simple, thus easier to understand and model, and which also scale down to experimental size. The worth of cipher *scalability* can hardly be overstated, since only with a tiny version can we hope to approach a block cipher experimentally in comprehensive ways. But the sampling of mixing locality does not require scalability and so can be applied to even conventional designs. PROBING LOCALITY We wish to capture any locality of mixing present in large block constructions. Presumably we could try to capture the effect of every input bit or byte on every output bit or byte, although we would then be overwhelmed with data. But it seems that we might capture most of the significance of mixing locality by injecting changes in just a few widely separated block positions, and also probing for changes at a few selected block positions. Surely, if there is a problem mixing in either direction, we should find it when we change a value at one end of the block and sense the result at the other. In particular, we construct a random key, and use it to initialize the cipher tables; this gives us a particular large substitution as an emulation. Then we construct a random data block, save that, encipher it, and also save the result. We produce a random byte as the change to be used at each change position. Then we copy the saved data block, XOR the random byte at the selected block position, and encipher. In general, we will see about half the bits change across the block, but we only probe a few output byte positions. For each input change position, we accumulate the number of bit-changes seen at each output probe position over many random data blocks. We place the results in a contingency table, and compute a chi-square statistic which is small when the results are independent. Each different random key will produce a different analysis and a different chi-square value. RESULTS If there is some locality weakness in mixing, it should express itself most clearly in measurements on large blocks. Accordingly, we start with 512-byte (4096-bit) blocks, noting that these are fully 64 times as large as "legacy" blocks. The Mixing cipher results are given in Figure 1. Bit Changes in 1000 Plaintexts of 512-byte Mixing Cipher Fig. 1 [ 0] [169] [340] [511] [ 0] 3986 0.00 3932 0.72 4087 0.32 4050 0.04 [169] 3941 0.36 4013 0.24 4039 0.02 4049 0.06 [340] 3984 0.01 4008 0.18 4016 0.23 4029 0.00 [511] 3981 0.20 3952 0.00 4024 0.00 3981 0.17 In figure 1 we have a single trial of 1000 different plaintext blocks, each processed 5 times: first without change, then once each with bytes 0, 169, 340, or 511 changed; these are the rows. In each case, the number of ciphertext bits which change in byte positions 0, 169, 340 and 511 are accumulated in separate column elements. For example, the value 4050 in the top row and rightmost column means that over the 1,000 times when input byte 0 was changed, output byte 511 had a total of 4050 bit changes. The value 0.04 is the chi-square contribution for that particular element. In statistics, the structure of figure 1 is called a "contingency table" (e.g. [2: 240]). In many ways this is similar to the common one-dimensional chi-square test for comparing distributions. Here we are asking whether the columns (probe positions across the ciphertext block) are independent of the rows (change positions across the plaintext block). That is, if there is locality in mixing, it should affect close bit positions more strongly than distant bit positions, so we should see more changes for close bit positions than for distant ones. Here we are measuring the number of output bit changes for each possible case, to see whether output probe position is independent of input injection position. In a contingency table, independence is the null hypothesis. The expected value for a contingency table element is the sum of the values in that row, times the sum of the values in that column, divided by the total of all values, so each element may have a slightly different expected value. The sum of all chi-square values is interpreted with the chi-square statistic and the degree of freedom which is the number of rows minus one, times the number of columns minus one. This is a "one-tail" statistical test, in that no value can be too small; we are only concerned with values which repeatedly show a tendency to be unexpectedly large. If we sum all the individual chi-square values in figure 1, we get a chi-square total of 2.56, which can be interpreted with figure 2 as being a very low and thus a very good value. Chi-Square Critical Values, for DF = 9 Fig. 2 1% 5% 25% 50% 75% 95% 99% 2.0879 3.3251 5.8988 8.3428 11.3888 16.9190 21.6660 In the same way as figure 1, we can collect a set of 20 such trials, as shown in figure 3. Chi-Square Totals for 512-byte Mixing Cipher Fig. 3 2.56 5.54 3.11 6.86 1.52 4.64 7.01 2.24 2.34 1.77 3.75 6.61 8.10 2.77 2.23 7.24 3.08 5.86 3.77 4.38 Figure 3 was the first set in the sequence recorded for this article, but does seem rather tight, so we might take another look. A somewhat wider range was recorded next, as shown in figure 4. Chi-Square Totals for 512-byte Mixing Cipher Fig. 4 9.00 3.87 5.41 5.31 1.22 2.03 8.47 10.31 8.14 1.58 3.34 11.61 3.24 4.70 7.87 5.70 5.70 4.77 4.50 6.13 The chi-square value of 11.61 in figure 4 corresponds to just over a probability of 0.75, and so might be said to reject the hypothesis that rows and columns are independent at the 0.25 level of significance. Of course, scientific results normally require a 0.05 or 0.01 level of significance, which is never approached here. And in cryptography we can generally afford to do a great number of experiments and so place the level of significance even higher. As usual, we expect high chi-square values to occur occasionally by chance, and so expect to be concerned about only repeatable and significant indications of problem. VSBC results are generally similar, as shown in figure 5. Bit Changes in 1000 Plaintexts of 512-byte VSBC Fig. 5 [ 0] [169] [340] [511] [ 0] 4008 0.06 3997 0.01 4006 0.03 3993 0.03 [169] 3953 0.61 4027 0.19 4003 0.14 4059 0.52 [340] 3959 0.00 3911 0.46 4028 0.57 3960 0.01 [511] 4043 0.24 4018 0.02 4023 0.04 3996 0.18 In figure 5, the chi-square total is 3.11, which corresponds to a probability of 0.04, which is very good. (Actually, we should say only that the value is insufficient to cause us to reject the hypothesis of independence.) The full 20 trials in the first VSBC set are shown in figure 6. Chi-Square Totals for 512-byte VSBC Fig. 6 3.11 2.18 3.15 4.50 3.67 6.23 3.96 6.23 5.40 4.26 4.10 1.97 3.63 2.34 4.31 4.14 1.92 4.04 5.15 5.06 Subsequent tests on smaller blocks are remarkably similar. The test results on 64-byte block ciphers (still fully 8 times as large as "legacy" blocks) with 1,000-plaintexts are shown in figures 7 and 8. In these tests, block elements are both changed and probed at positions 0, 20, 41, and 63. (Probing the changed element always provides a contrast to more distant elements, and should make it easier to detect mixing locality effects if they exist.) Chi-Square Totals for 64-byte Mixing Cipher Fig. 7 2.53 6.24 3.09 2.15 3.86 3.26 2.76 4.91 5.59 5.52 5.51 5.65 3.17 0.98 3.23 2.20 5.79 2.86 10.26 7.92 Chi-Square Totals for 64-byte VSBC Fig. 8 6.31 3.55 3.32 3.70 6.65 3.47 4.17 5.81 3.24 5.20 2.31 3.31 5.85 3.25 3.77 2.48 7.82 3.21 6.16 2.98 The test results on 16-byte block ciphers with 1,000-plaintexts are shown in figures 9 and 10. In these tests, block elements are changed and probed at positions 0, 4, 9 and 15. Chi-Square Totals for 16-byte Mixing Cipher Fig. 9 3.63 5.27 4.76 5.45 4.97 3.35 6.50 2.82 4.60 2.70 4.92 2.61 2.21 7.89 4.39 12.60 3.58 5.28 2.73 6.27 Chi-Square Totals for 16-byte VSBC Fig. 10 1.84 9.69 5.30 4.13 2.02 5.27 5.01 6.19 1.12 4.13 4.69 7.13 6.39 4.98 5.50 0.87 5.30 1.79 6.02 7.31 When tests are going well, the outcomes can seem pretty boring. But make no mistake: If these tests had *not* gone well, they would have become very interesting very fast. About the only thing remaining is to see whether the distribution gets noticeably more severe in larger trials, so we run some trials with 10,000 plaintexts in figures 11 and 12. Bit Changes in 10,000 Plaintexts of 512-byte Mixing Cipher Fig. 11 [ 0] [169] [340] [511] [ 0] 39613 0.29 40010 0.16 40027 0.83 39666 0.60 [169] 39702 0.01 40029 0.25 39780 0.10 39802 0.01 [340] 39882 0.36 39925 0.05 39847 0.04 39829 0.03 [511] 39734 0.00 39802 0.46 39776 0.15 40036 1.08 In figure 11 we have a chi-square total of 4.43 for a probability of 0.119, which is fine. Bit Changes in 10,000 Plaintexts of 512-byte VSBC Fig. 12 [ 0] [169] [340] [511] [ 0] 40165 0.76 39948 0.00 39876 0.34 39913 0.05 [169] 39988 0.12 39878 0.00 39880 0.04 39871 0.01 [340] 39836 0.77 40101 0.37 40094 0.16 39954 0.02 [511] 40074 0.12 40011 0.25 40225 0.16 40202 0.20 In figure 12 we have a chi-square total of 3.38 for a probability of 0.052, which is also fine. All of these results seem very representative of the endless data which can be collected in repeated tests. CONCLUSIONS These results resoundingly fail to reject the null hypothesis. We thus conclude that the null hypothesis is correct, and output position is in fact independent of input position, with respect to bit changes, for both Mixing cipher and Variable Size Block Cipher designs of 512-byte (4096-bit) width. By supporting the idea that some effective large block designs can exist, the results also support the viability of large block cipher design in general. REFERENCES [1] Feistel, H. 1973. Cryptography and Computer Privacy. Scientific American. 228(5): 15-23. [2] Huntsberger, D. 1967. Elements of Statistical Inference. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM From: ardell@DESPAMpipeline.com (Gary Ardell) Newsgroups: sci.crypt Subject: Re: Measured Distant Avalanche in Large Block Ciphers (LONG!) Date: Fri, 06 Mar 1998 21:44:26 GMT Lines: 17 Message-ID: <350066aa.9625060@news.pipeline.com> References: <34fdfea7.1999205@news.io.com> Terry, I enjoyed your post. Thanks. I may be missing something obvious here but I don't see the reasoning behind focusing on changes in individual bytes rather than on individual bits. Why not flip all single input bits and check all single output bits (using your same basic sampling approach)? Regards, Gary From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Measured Distant Avalanche in Large Block Ciphers (LONG!) Date: Fri, 06 Mar 1998 23:58:35 GMT Lines: 70 Message-ID: <350087b5.5283891@news.io.com> References: <34fdfea7.1999205@news.io.com> <350066aa.9625060@news.pipeline.com> On Fri, 06 Mar 1998 21:44:26 GMT, in <350066aa.9625060@news.pipeline.com> in sci.crypt ardell@DESPAMpipeline.com (Gary Ardell) wrote: >I enjoyed your post. Thanks. And thank *you*. >I may be missing something obvious here but I don't see the >reasoning behind focusing on changes in individual bytes >rather than on individual bits. Why not flip all single >input bits and check all single output bits (using your same >basic sampling approach)? There seem to be two parts to this question: bits vs. bytes, and all vs. some. With respect to "bits vs. bytes," the systems under test both have a fundamental mixing size of 8-bits. If we want to detect problems in 8-bit mixing, 8-bit values seem the appropriate size to address. In this way, we can at least hope that a problem will be easier to see in the context of byte results, rather than a necessarily smaller difference in 8 contiguous but otherwise unremarkable bits. With respect to "all vs. some," the point is to achieve insight, rather than data. If we have already covered the worst case (the nearest possible locality compared to the most distant locality in both directions), it is hard to see how more data would help. And the amount of data could be tremendous: Instead of having 4 * 4 = 16 counters, we would have, for the 512-byte case, 4096 * 4096 = 16,772,216 counters. We could confine ourselves to small blocks that we *could* test this way, but the whole point is to investigate mixing across *very* *large* blocks. We are necessarily limited to devising tests that are not only revealing, but also practical. When I began measuring large block constructions a number of years ago, one of the first things I did was to investigate what one should expect in terms of random bit-change totals (which everyone will now agree should be binomial, although there was some discussion about it at the time). I like the binomial reference distribution because it makes a very strong statement about the probability of a rare occurrence. In the context of a large block we get a relatively small range which is reasonable, and values out of that range have a computable probability which we can understand directly: if a 1-in-a-million event occurs twice in a few tests, we pretty well know the story *without* a great deal of deliberation about chi-square statistics, confidence levels, and so on. In that sense, the test has the potential to give a clearer and more definitive statement than a single average value or even chi-square results of a nominally flat distribution. Of course we do want a wide range of tests in any event. In actual large block tests using the binomial reference, I have constructed random keys, random data, and changed each input bit, or changed random numbers of random bit positions. And my experience is that, while this can give one a general feel for the cipher (and certainly make a loud statement of significant fault), it is pretty general. In the case of the distant avalanche tests, I was looking to specifically address the criticism that "large blocks are bad because they are obviously hard to mix." Hopefully the results are food for thought, which is the best I could hope for anyway. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM From: ardell@DESPAMpipeline.com (Gary Ardell) Newsgroups: sci.crypt Subject: Re: Measured Distant Avalanche in Large Block Ciphers (LONG!) Date: Mon, 09 Mar 1998 16:10:55 GMT Lines: 42 Message-ID: <3504131a.6688407@news.pipeline.com> References: <34fdfea7.1999205@news.io.com> <350066aa.9625060@news.pipeline.com> <350087b5.5283891@news.io.com> Terry, Clearly, passing the chi-squared test on the number of flips gets the most fundamental question about the degree of avalanche: "Are changes in each byte fully propagating to all the output bytes?" This is all you intended and it seems that your test accomplish this mission given some assumptions about the nature of possible problems. (For example, if cipher failures are rare but spectacular, then the sample size could have to be huge.) However, having passed the test, numerous pathologies still seem possible e.g. that output flips are not independent. (I don’t say likely.) As you know better than I, numerous very poor random number generators can easily pass the chi-squared test but fail more strident tests. Therefore, it would seem useful to me to exploit the rich battery of tests that have been designed to test for weaknesses in random number generators. For example, here is one procedure. Randomly draw a 20 MB of plain text (better yet, 3-DES a 20 MB file). Call that file, PLAIN. Encrypt that file without chaining with your test cipher and store the results to another file, CYPERBASE. Let’s focus on input-bit one for the second. Make a copy of PLAIN and flip bit one in every input block. Now encrypt this new file without chaining and xor it against CYPERBASE. This file should look to all the world like 20 MB of random numbers. So, run it through Diehard to see what if any failures show up. Doing this once for every input bit comprehensively tests the notion that there is a statistically obvious exploitable weaknesses in the cipher. Doing this with truncated rounds should help identify the pathologies that crop up and the tests that best flag these problems. (Note: Diehard may have a weakness in detecting patterns in really long blocks. I don’t know. If this is a worry, we can make PLAIN big enough to allow us to pull 32-bit chunks out of each output block and still get the required 20 MB file.) This seems to me like a manageable statistical protocol with the potential to produce even more comfort in the power of the test cipher. Yes? No? Maybe? Regards, Gary From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Measured Distant Avalanche in Large Block Ciphers (LONG!) Date: Tue, 10 Mar 1998 20:05:03 GMT Lines: 70 Message-ID: <35059c24.9942152@news.io.com> References: <34fdfea7.1999205@news.io.com> <350066aa.9625060@news.pipeline.com> <350087b5.5283891@news.io.com> <3504131a.6688407@news.pipeline.com> On Mon, 09 Mar 1998 16:10:55 GMT, in <3504131a.6688407@news.pipeline.com> in sci.crypt ardell@DESPAMpipeline.com (Gary Ardell) wrote: >Terry, > >Clearly, passing the chi-squared test on the number of flips gets the most >fundamental question about the degree of avalanche: >[...] > >However, having passed the test, numerous pathologies still seem possible >e.g. that output flips are not independent. (I don’t say likely.) As you know >better than I, numerous very poor random number generators can easily pass >the chi-squared test but fail more strident tests. Therefore, it would seem >useful to me to exploit the rich battery of tests that have been designed to >test for weaknesses in random number generators. >[...] First, let me just state the obvious: RNG's are inherently different than block ciphers. When we ask whether each works right, we worry about completely different things. For example, RNG's generally iterate some fixed and often small amount of internal state; block ciphers do not. With RNG's we worry about correlations between adjacent or delayed values; there is nothing like this in block ciphers. And I expect that most RNG tests have been (explicitly or implicitly) designed to detect RNG-style problems, rather than block cipher style problems. >[...] >This file should look to all the world like 20 MB of random numbers. So, >run it through Diehard to see what if any failures show up. Doing this once Let me point out that in each of my 10,000 plaintext tests of one 512-byte cipher, we are looking at 4 * 10,000 * 512 = 20.48 MB of output. So we are seeing a substantial sample. But it would be wrong to simply throw ciphertext into a file and expect general tests to somehow derive information from the result. The Diehard tests, for example, expect 32-bit integer values, not 512-byte blocks. If we put in wider values, the tests lose their meaning, and if we only take 32 bits of the ciphertext, we are not testing what we want to test. These tests simply are not oriented toward block cipher testing. >[...] >This seems to me like a manageable statistical protocol with the potential to >produce even more comfort in the power of the test cipher. On the contrary, I think it is usually far more important to test for particular qualities, based on an analysis of the system under test. Aiming at a specific quality gives us the basis for tests which selectively expose that quality while filtering out much of the inevitable noise. This seems by far the best way to find tiny problems. And unless we first define what we are testing for, and then test for that, our results will not deliver much of a conclusion. If we use a general approach to testing, the best we could say is "we didn't find anything," without being able to describe either what we did not find *or* what was tested, in any real sense that relates to the mechanism itself. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM From: jsavard@teneerf.edmonton.ab.ca (John Savard) Newsgroups: sci.crypt Subject: Re: Measured Distant Avalanche in Large Block Ciphers (LONG!) Date: Fri, 06 Mar 1998 22:13:34 GMT Lines: 10 Message-ID: <35007452.8557955@news.prosurfr.com> References: <34fdfea7.1999205@news.io.com> ritter@io.com (Terry Ritter) wrote, in part: > 2. A large block has room for information other than data. Seeing that comment, I can't resist a historical note. LUCIFER, grandaddy of block ciphers, with its 128-bit blocks, was intended to handle blocks containing 64 bits of data, with identifying information and a serial counter (for randomization) in the other 64 bits. John Savard From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Measured Distant Avalanche in Large Block Ciphers (LONG!) Date: Sat, 07 Mar 1998 07:12:08 GMT Lines: 36 Message-ID: <3500f316.32703452@news.io.com> References: <34fdfea7.1999205@news.io.com> <35007452.8557955@news.prosurfr.com> On Fri, 06 Mar 1998 22:13:34 GMT, in <35007452.8557955@news.prosurfr.com> in sci.crypt jsavard@teneerf.edmonton.ab.ca (John Savard) wrote: >ritter@io.com (Terry Ritter) wrote, in part: > >> 2. A large block has room for information other than data. > >Seeing that comment, I can't resist a historical note. LUCIFER, >grandaddy of block ciphers, with its 128-bit blocks, was intended to >handle blocks containing 64 bits of data, with identifying information >and a serial counter (for randomization) in the other 64 bits. Thank you for reading the article. What I call a dynamic keying field is indeed described in one of the Feistel patents (now expired). But it is not particularly useful when there are only 64 bits in a block; this is a feature which *depends* upon having something better than DES and IDEA. Many tears are shed when constructing standard designs, but the inability to use such a field in DES may have been an especially bitter loss. Surely dynamic keying will be at least *possible* with 128-bit blocks, but a 64-bit key would be fully half of such a block. That would *double* ciphering overhead, which may not be acceptable in many commercial applications. A 64-bit dynamic key is only 1/64th of a 512-byte block, however, which seems a far more acceptable overhead. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM

*Terry Ritter, his
current address, and his
top page. *

*Last updated:* 1998-05-03