These conversations are basically about stream ciphers. The classic stream cipher is basically a random number generator (RNG), the output of which is exclusive-ORed with the data. The problem with this is that we normally assume our opponents have some amount of known plaintext, plaintext data and the associated ciphertext. That immediately exposes the RNG sequence, and if that can be predicted for future data, the cipher is broken.
Unfortunately, simple RNG's with good properties are linear, and can be broken with only as much known-plaintext as the amount of state in the RNG. These are real breaks, as opposed to academic breaks which need vastly larger amounts of known-plaintext. This is real weakness in practice.
Things would be great if we could could just take a couple of linear RNG's and somehow combine them to produce an unbreakable sequence. But that turns out to be much harder than one might think, see: The Story of Combiner Correlation: A Literature Survey (58K)
The idea that one can take a couple of conventional RNG's and combine them in "Algorithm M" (Knuth II-speak for MacLaren-Marsaglia or M-M) seems to be "in the air," and regenerates itself with every new generation of crypto newbies. The reason for this may be that it is easy to take Knuth's comments out of context:
"On intuitive grounds it appears safe to predict that the sequence obtained by applying Algorithm M will satisfy virtually anyone's requirements for randomness . . . ." (Knuth II, 2nd ed., p. 32)Unfortunately, here Knuth uses "randomness" in the context of statistical randomness, and not the ability to resist prediction of the sequence, as is needed in stream ciphers. When taken out of context and interpreted as unqualified reality, the statement can be very misleading.
To our great loss, the academic literature does not jump on every new cipher construction in an attempt to define weakness, strength, and worth. In the case of M-M in stream ciphers, we have exactly two articles, each of which provides a true practical break for a particular cipher. Of course, any practical break is vastly more discouraging than the usual academic break which may require 2**50 known-plaintext bits.
One of our fundamental problems in cryptography is that we necessarily must argue about strength, absent proof. First, there is no test for abstract cipher strength, nor do we expect any such proof. Next, while we do get proof of weakness from a successful attack, actually doing that can take enormous effort and time, even for those with appropriate aptitude, training and experience.
A big part of the problem is that cryptanalytic results are rarely in a form which lasts: It is all too easy to say, "This new cipher isn't really the same as the broken cipher, so it must be strong!" That takes no effort at all to say, requires another arduous attack to disprove, and if it is disproved, the cipher can easily be changed again. As a result, we can expect that most ciphers will not have a clear break (if there was a clear break, the cipher would not be proposed), so we are necessarily forced to estimate strength on the basis of limited information.
Retter, C. 1984. Cryptanalysis of a MacLaren-Marsaglia System. Cryptologia. 8(2): 97-108.
Retter, C. 1985. A Key-Search Attack on MacLaren-Marsaglia Systems. Cryptologia. 9(2): 114-130.
Subject: Re: Strong stream ciphers besides RC4? Date: Wed, 26 Jan 2000 14:47:47 GMT From: Tom St Denis <stdenis@compmore.net> Message-ID: <86n1eh$bki$1@nnrp1.deja.com> References: <388E366D.5ED1B722@achtung.com> Newsgroups: sci.crypt Lines: 26 In article <388E366D.5ED1B722@achtung.com>, Albert Yang <albert@achtung.com> wrote: > I'm looking for a strong stream cipher that isn't copyrighted. I seem > to see a large choice of block ciphers, but very few stream ciphers... > > Albert > You can use Algorithm M, if you have appropriate underlying RNG's. You could construct a stream cipher in 10 minutes using two Lagged Fibonacii generators [lag >= 50 at least]. The only issue left is the key schedule . The state size is normally large (i.e around 1000 bytes) so you have to expand a smaller key. You could use another LFSR or Generator :) I would suggest if you used this system to dump the first outputs... Also with this construction you can output 32 bits, 16 bits .. .etc whatever your wordsize is on the computer. It's very versatile. Tom Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: Strong stream ciphers besides RC4? Date: Wed, 26 Jan 2000 16:42:42 GMT From: ritter@io.com (Terry Ritter) Message-ID: <388f23f7.2135969@news.io.com> References: <86n1eh$bki$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 36 On Wed, 26 Jan 2000 14:47:47 GMT, in <86n1eh$bki$1@nnrp1.deja.com>, in sci.crypt Tom St Denis <stdenis@compmore.net> wrote: >[...] >You can use Algorithm M, if you have appropriate underlying RNG's. We have been over this several times. Previously, for example: >>On Thu, 08 Jul 1999 02:39:42 GMT, in <7m131d$uti$1@nnrp1.deja.com>, >>in sci.crypt tomstdenis@my-deja.com wrote: >>>[...] >>>The goal is to use the RNG and not reveal the current internal state. >>>Algorithm M is a good example of this (Also in AC just after >>>LFSRs...). >>Hmmm.... >>1. Retter, C. 1984. Cryptanalysis of a MacLaren-Marsaglia System. >>Cryptologia. 8(2): 97-108. >>2. Retter, C. 1985. A Key-Search Attack on MacLaren-Marsaglia >>Systems. Cryptologia. 9(2): 114-130. >>3. Letters to the Editor. 1984. Cryptologia. 8(4): 374-378. You can wish and hope all you want, but Algorithm M is still not secure. Sorry. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Strong stream ciphers besides RC4? Date: Wed, 26 Jan 2000 12:09:08 GMT From: jsavard@domain.ctry (John Savard) Message-ID: <388ee213.15326398@news.prosurfr.com> References: <388f23f7.2135969@news.io.com> Newsgroups: sci.crypt Lines: 32 ritter@io.com (Terry Ritter) wrote, in part: >You can wish and hope all you want, but Algorithm M is still not >secure. Sorry. The attack used in those Cryptologia articles required that the entire pseudo-random output from the linear congruential generator be used. Just use the most significant byte, and a sufficiently large integer to make the required arrays impractical (16-bit arithmetic is no good, but 128-bit arithmetic works nicely) and such attacks on a simple MacLaren-Marsaglia generator fall apart. Use the XOR of the output of two MacLaren-Marsaglia generators with different periods. However, since these attacks were shown against a weak version of MacLaren-Marsaglia, there's been very little study of that method when used properly, so one should perhaps use a better-studied method, if that is how one seeks confidence. Except for the slow Blum-Blum-Shub method, I can't think of anything offhand. Using, for encryption, the _whole integer_ produced by a linear congruential generator, to my mind, is like using a rotor machine that enciphers one letter using all five rotors, the next one using only the first four rotors, and so on until the fifth letter is enciphered using only the first rotor, and *then* steps the rotor mechanism. (Remember, the last bit has period 2, the second-last bit has period 4, and so on.) Which is why I didn't feel that attack really proved much about MacLaren-Marsaglia when used properly. John Savard (jsavard<at>ecn<dot>ab<dot>ca) http://www.ecn.ab.ca/~jsavard/crypto.htm
Subject: Re: Strong stream ciphers besides RC4? Date: Wed, 26 Jan 2000 20:57:03 GMT From: Tom St Denis <stdenis@compmore.net> Message-ID: <86nn2s$tcg$1@nnrp1.deja.com> References: <388ee213.15326398@news.prosurfr.com> Newsgroups: sci.crypt Lines: 27 In article <388ee213.15326398@news.prosurfr.com>, jsavard@domain.ctry (John Savard) wrote: > ritter@io.com (Terry Ritter) wrote, in part: > > >You can wish and hope all you want, but Algorithm M is still not > >secure. Sorry. > > The attack used in those Cryptologia articles required that the entire > pseudo-random output from the linear congruential generator be used. > Just use the most significant byte, and a sufficiently large integer > to make the required arrays impractical (16-bit arithmetic is no good, > but 128-bit arithmetic works nicely) and such attacks on a simple > MacLaren-Marsaglia generator fall apart. Sorry if this is out there, but I don't have access to those papers. See the problem with Terry's response from what I can tell is that... I AM NOT USING A LINEAR CONGRUETIAL GENERATOR. I suggested using sufficiently lagged Fibonacii generators which are not as bad as a LCG. If I could get access to those papers somehow... tom Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: Strong stream ciphers besides RC4? Date: Thu, 27 Jan 2000 20:21:07 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3890a89c.5131447@news.io.com> References: <388ee213.15326398@news.prosurfr.com> Newsgroups: sci.crypt Lines: 126 On Wed, 26 Jan 2000 12:09:08 GMT, in <388ee213.15326398@news.prosurfr.com>, in sci.crypt jsavard@domain.ctry (John Savard) wrote: >ritter@io.com (Terry Ritter) wrote, in part: > >>You can wish and hope all you want, but Algorithm M is still not >>secure. Sorry. > >The attack used in those Cryptologia articles required that the entire >pseudo-random output from the linear congruential generator be used. Well, no. Certainly the first article by Retter (1984) did attack a system with weak generators. But I argue that the whole point of the MacLaren-Marsaglia (M-M) combiner was precisely to provide strength the generators lacked, and M-M failed. The more telling second article (1985) does not assume weak generators. I suppose the best thing to do is to just quote some of it: "The idea of combining multiple pseudo-random number generators in order to produce a more secure keystream sequence has been proposed in various forms [fn]. Most of these methods are intended to create nonlinear sequences by using linear generators, since linear sequences are easily invertible." "The MacLaren-Marsaglia algorithm [fn] is a somewhat more complex method of combining two generators." "It is the purpose of this paper to show that the algorithm can be attacked by searching for the key to one of its generators while ignoring the other." "The MacLaren-Marsaglia algorithm operates as follows: One pseudo-random generator is used to produce the values for the final keystream sequence, but the values are first saved in a table. The second generator is used to produce pointers into the table." "The problem for the cryptanalyst in this case is to find the initial states of the pointer generator and the value generator, given a reasonable amount of keystream sequence." "In evaluating the cryptographic usefulness of the MacLaren-Marsaglia algorithm, it is important to distinguish between the security provided by the pointer and value generators, and the additional security provided by the combining algorithm. A previous paper [fn] described a successful attack against a system which used weak pointer and value generators. This paper considers strong generators. Specifically, the pointer and value generators are assumed to generate sequences which can be broken only by exhaustive search of their keys." "The effectiveness of the algorithm in improving the security of the value and pointer generators can be described in terms of the increase in times required to search all keys. The most effective combining algorithm would require searching all combinations of two keys, which would take a time proportional to the product of the times to search for individual keys. A weak combining algorithm, on the other hand, would allow a search for one key independent of the other, so that the total time required would be proportional to the sum of the individual search times. In either case, the algorithm might also affect the amount of time required to test each key. It will be shown in the following sections that the MacLaren-Marsaglia algorithm is a relatively weak combining algorithm, because it is generally possible to search for the key to the value generator independent of the pointer generator." >Just use the most significant byte, and a sufficiently large integer >to make the required arrays impractical (16-bit arithmetic is no good, >but 128-bit arithmetic works nicely) and such attacks on a simple >MacLaren-Marsaglia generator fall apart. One weakness is that the values produced by the M-M table are constrained in distance within the sequence by the size of the table. Generators have their own constraints, and it may be possible to show that a generator of the known form could not produce values with the known distance relationships. I have zero confidence that that is the only exploitable weakness. >Use the XOR of the output of two MacLaren-Marsaglia generators with >different periods. >However, since these attacks were shown against a weak version of >MacLaren-Marsaglia, there's been very little study of that method when >used properly, so one should perhaps use a better-studied method, if >that is how one seeks confidence. Except for the slow Blum-Blum-Shub >method, I can't think of anything offhand. Note that every M-M system in the literature (that would be 2 systems) has been shown weak. Now, it is obvious that things can be added to weak systems to improve strength. But it is also obvious that simply using M-M does not produce strength. As a consequence, every use needs a serious analysis to assure that M-M is not being "improperly used." >Using, for encryption, the _whole integer_ produced by a linear >congruential generator, to my mind, is like using a rotor machine that >enciphers one letter using all five rotors, the next one using only >the first four rotors, and so on until the fifth letter is enciphered >using only the first rotor, and *then* steps the rotor mechanism. >(Remember, the last bit has period 2, the second-last bit has period >4, and so on.) Which is why I didn't feel that attack really proved >much about MacLaren-Marsaglia when used properly. Personally, I find these attacks telling, and suggest that they reveal fundamental cryptographic weakness in the M-M method. When we find fundamental weaknesses, we can patch them, and then patch the patches and so on, or we can just move on. Further, I doubt the entire range of M-M weakness has so far been exposed, and so doubt that weakness would be avoided in new systems just by reviewing the previous attacks. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Has some already created a DATA DIODE? Date: Sun, 13 Feb 2000 13:35:54 GMT From: Tom St Denis <stdenis@compmore.net> Message-ID: <886bvq$ods$1@nnrp1.deja.com> References: <38A5D341.67A5@worldnet.att.com> Newsgroups: sci.crypt Lines: 133 In article <38A5D341.67A5@worldnet.att.com>, nospam@worldnet.att.com wrote: > I thinking about the problems of using a PRNG for encryption, the > following seems clear.. to attack PRNG encryption you have you > have two options (assuming some of the plain data is known or > knowable (ie. it's english!). > > First a brute force attack can be applied to the encryption key > (the seed) or secondly, knowing the plain data, the attacker can > work back to learn the state of the PRNG. > > It is this second method of attack I would like the group's > comments on. Is there an (easy, quick, simple) way to create > what I call a DATA DIODE. A piece of code that is a one way > check valve, allowing the data to flow from a PRNG but does not > allow the attacker to back up the data path? > AlgM is a good place to start, just don't use LCG's as the underlying PRNG. AlgM with two 'long' Fibonacii generators is secure. > The following illustrates what I an talking about.. > ============================================================ > +----+ +------------------+ +------------------+ > |PRNG|--->| 15 bit integer A |-- + --| 16 bit integer B | > +----+ +-----------------=+ +------------------+ > > Then > > +----------------------+ +---------------------+ > | high 8 bit byte of B |-- + --| low 8 bit byte of B | > +----------------------+ +---------------------+ > > +-----+ > Equals the 8 bit output encryption PAD byte | PAD | > +-----+ This is still a highly linear system if the underlying RNG is linear. It will not make it much more secure. An extension to this idea is Xn = (Yn - Zn) mod m [Knuth vol2]. Where Y and Z are two RNG's at step 'n'. > written in C: > > #include <stdlib.h> > #include <stdio.h> > #include <conio.h> > > int main(void) > { > unsigned char PAD[1]; Not to be picky, but if the array has one element, just store it as so. unsigned char PAD; > int i,rand_num; > union diode { > unsigned int INT_B; > unsigned char byte[2]; > } out; Not to be picky, but who says int is 16 bits? At best you should use 'short' [but that's no gurantee either]. > out.INT_B = 1731; Magic constant? > printf("\nThe pad byte generation:\ > \nINT A,\t\tINT B,\t\tINT B(HEX),\tPAD (HEX) "); > for(i = 0; i < 4; i++) { > rand_num = rand(); > out.INT_B += rand_num ; > printf("\n %d,\t\t%d,\t\t%X, ", rand_num, out.INT_B, out.INT_B); > PAD[0] = (out.byte[0] + out.byte[1]); > printf("\t\t%2.X", PAD[0]); > } > > return 0; > } Another point is that the seed for 'rand()' is often 32 or 16 bits. This is way to short for even a remotely secure program. > As an example, I use the first 4 integers output from the PRNG in > Borland's C, seeded with the number 1, which are: > > 346, 130, 10982, 1090.. > > we will set the starting state of integer B is 1731. So: > > INT A + INT B0 int B1 <HEX> then INT B HI byte + LO byte = PAD > 346 1731 2077 081D 08 1D 25 > 130 2077 2207 089F 08 9F A7 > 10982 2769 13189 3385 33 85 B8 > 1090 3807 14279 37C7 37 C7 FE > > This system has two unknowns, the seed state of th PRNG and the > initial value of INT A. The problem is that the 'rand()' function has detectable patterns. So while this method seems interesting, I doubt it would withstand a serious attack. Also your LCG has to be enormous to avoid brute force keysearches. > My question how does the attacker proceed to learn the state of > the PRNG so as to determine the next PAD byte. My guess would be to 'guestimate' what the lower byte of 'rand()' and proceed from there. Since the lower byte of 'rand()' is what drives the rng essentially. I dunno, I am not much for attacking things [too much else going on now]. My suggestion is to add... PAD = (Byte[0] + Byte[1]) mod m Where m is prime. Or you can turn it into a shrinking generator like so. 1. A = (B1 + B2) mod 521 2. if (A > 255) goto 1 3. Output A. [Where B1 and B2 are two 8-bit values]. Tom Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: Has some already created a DATA DIODE? Date: Sun, 13 Feb 2000 17:15:17 GMT From: ritter@io.com (Terry Ritter) Message-ID: <38a6e675.1594785@news.io.com> References: <886bvq$ods$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 27 On Sun, 13 Feb 2000 13:35:54 GMT, in <886bvq$ods$1@nnrp1.deja.com>, in sci.crypt Tom St Denis <stdenis@compmore.net> wrote: >[...] >AlgM is a good place to start, just don't use LCG's as the underlying >PRNG. I doubt that is nearly enough. >AlgM with two 'long' Fibonacii generators is secure. Really? Care to back that up? We have been through this before, and I have quoted at length from the attack references. As far as I know, MacLaren-Marsaglia techniques have appeared exactly twice in cryptographic literature -- and they have *failed* twice. Yet even with this information you continue to claim strength where there is a damn good reason to suspect that there is no strength. Why do you do it, and why do you do it in response to newbies? --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Has some already created a DATA DIODE? Date: Mon, 14 Feb 2000 13:04:27 GMT From: jsavard@domain.ctry (John Savard) Message-ID: <38a7fbcb.13805991@news.prosurfr.com> References: <886bvq$ods$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 27 Tom St Denis <stdenis@compmore.net> wrote, in part: >AlgM is a good place to start, just don't use LCG's as the underlying >PRNG. AlgM with two 'long' Fibonacii generators is secure. His method doesn't seem to be too different from MacLaren-Marsaglia: here, the choice is between one of many seed values, but the seed values are only advanced when used. LFSRs and LCGs are insecure for the same reason, both being linear, so I don't think it matters which one you use for MacLaren-Marsaglia. The literature references to MacLaren-Marsaglia generators being cracked involved short-period LCGs, where the entire output, including the LSBs, with periods down to two, was used in the output stream, so I don't think they can be used to support a conclusion that the technique ought to be abandoned. However, I would recommend, at a minimum, a technique like this: have _two_ MacLaren-Marsaglia generators, and use the XOR of their output as input to a _third_ buffer. I have little fear that this kind of technique will suddenly be proven insecure. However, the PRNGs used for the three buffers must have rel-prime periods. John Savard (jsavard<at>ecn<dot>ab<dot>ca) http://www.ecn.ab.ca/~jsavard/crypto.htm
Subject: Re: Has some already created a DATA DIODE? Date: Mon, 14 Feb 2000 22:34:02 GMT From: ritter@io.com (Terry Ritter) Message-ID: <38a88287.1759602@news.io.com> References: <38a7fbcb.13805991@news.prosurfr.com> Newsgroups: sci.crypt Lines: 58 On Mon, 14 Feb 2000 13:04:27 GMT, in <38a7fbcb.13805991@news.prosurfr.com>, in sci.crypt jsavard@domain.ctry (John Savard) wrote: >[...] >LFSRs and LCGs are insecure for the same reason, both being linear, so >I don't think it matters which one you use for MacLaren-Marsaglia. Right. Any weak generator may well be attacked at its point of weakness because the M-M combiner leaks information. >The literature references to MacLaren-Marsaglia generators being >cracked involved short-period LCGs, where the entire output, including >the LSBs, with periods down to two, was used in the output stream, so >I don't think they can be used to support a conclusion that the >technique ought to be abandoned. The first system in the literature did use 2 LCG's with an M-M combiner. But if the LCG had been thought strong, there would have been no need for a combiner. The point of the combiner, then, was to add strength. It failed. The *reason* the system failed was because the M-M combiner leaks information. The attacker can use that information in a whole range of attacks, not just the one or two given in the literature. Avoiding those particular attacks simply means that some other attack will have to be devised. But there is no reason to suspect such an attack to be impossible, because THE M-M COMBINER LEAKS INFORMATION! One alternative is to just use strong generators. But if we have strong generators we don't need the M-M combiner. >However, I would recommend, at a >minimum, a technique like this: have _two_ MacLaren-Marsaglia >generators, and use the XOR of their output as input to a _third_ >buffer. But what does M-M bring to the party? Shall we simply XOR two LCG's and claim that system is strong? If we have a weak system and XOR it with another weak system, what do we expect to get? >I have little fear that this kind of technique will suddenly be proven >insecure. Then I think you need to develop more fear. >However, the PRNGs used for the three buffers must have >rel-prime periods. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Has some already created a DATA DIODE? Date: Mon, 14 Feb 2000 16:45:19 GMT From: jsavard@domain.ctry (John Savard) Message-ID: <38a82f84.27046180@news.prosurfr.com> References: <38a88287.1759602@news.io.com> Newsgroups: sci.crypt Lines: 54 ritter@io.com (Terry Ritter) wrote, in part: >On Mon, 14 Feb 2000 13:04:27 GMT, in ><38a7fbcb.13805991@news.prosurfr.com>, in sci.crypt >jsavard@domain.ctry (John Savard) wrote: >>The literature references to MacLaren-Marsaglia generators being >>cracked involved short-period LCGs, where the entire output, including >>the LSBs, with periods down to two, was used in the output stream, so >>I don't think they can be used to support a conclusion that the >>technique ought to be abandoned. >The first system in the literature did use 2 LCG's with an M-M >combiner. But if the LCG had been thought strong, there would have >been no need for a combiner. The point of the combiner, then, was to >add strength. It failed. No; the attack given in the literature was not as trivial as the one against a single LCG. So it did add strength. Since a super-weak LCG was used - all the output, and not just the most significant bits, were used - the attack was possible. >The *reason* the system failed was because the M-M combiner leaks >information. The attacker can use that information in a whole range >of attacks, not just the one or two given in the literature. Avoiding >those particular attacks simply means that some other attack will have >to be devised. But there is no reason to suspect such an attack to be >impossible, because THE M-M COMBINER LEAKS INFORMATION! It is true that the buffer, unlike the one in DynSub or alleged RC4, doesn't consist of all 256 values uniformly. Is this what you mean? If so, the cure is obvious: use a big buffer. >One alternative is to just use strong generators. But if we have >strong generators we don't need the M-M combiner. Ah, but can you be sure the generator is strong? >>However, I would recommend, at a >>minimum, a technique like this: have _two_ MacLaren-Marsaglia >>generators, and use the XOR of their output as input to a _third_ >>buffer. >But what does M-M bring to the party? Shall we simply XOR two LCG's >and claim that system is strong? If we have a weak system and XOR it >with another weak system, what do we expect to get? XOR two LCGs, and you get an LCG. This is not true about an M-M generator. Suddenly, all the leaked information disappears: each byte of output could be produced by many different combinations of input from the generators themselves. John Savard (jsavard<at>ecn<dot>ab<dot>ca) http://www.ecn.ab.ca/~jsavard/crypto.htm
Subject: Re: Has some already created a DATA DIODE? Date: Tue, 15 Feb 2000 01:01:48 GMT From: ritter@io.com (Terry Ritter) Message-ID: <38a8a3f0.2421428@news.io.com> References: <38a82f84.27046180@news.prosurfr.com> Newsgroups: sci.crypt Lines: 77 On Mon, 14 Feb 2000 16:45:19 GMT, in <38a82f84.27046180@news.prosurfr.com>, in sci.crypt jsavard@domain.ctry (John Savard) wrote: >[...] >>The first system in the literature did use 2 LCG's with an M-M >>combiner. But if the LCG had been thought strong, there would have >>been no need for a combiner. The point of the combiner, then, was to >>add strength. It failed. > >No; the attack given in the literature was not as trivial as the one >against a single LCG. So it did add strength. That hardly matters. It was broken. >Since a super-weak LCG >was used - all the output, and not just the most significant bits, >were used - the attack was possible. *That* attack, perhaps. >[...] >It is true that the buffer, unlike the one in DynSub or alleged RC4, >doesn't consist of all 256 values uniformly. Is this what you mean? Only partly: Obviously a combiner must be balanced. Across each possible input value, each particular result must occur the same number of times. But there is more, in that the linear relationships in the driving system must be obscured. >If so, the cure is obvious: use a big buffer. It might have to be a *big* buffer. >>One alternative is to just use strong generators. But if we have >>strong generators we don't need the M-M combiner. > >Ah, but can you be sure the generator is strong? Right. The whole point of using M-M is to protect weakness. It has not worked. There is no reason to believe it will work. >[...] >>But what does M-M bring to the party? Shall we simply XOR two LCG's >>and claim that system is strong? If we have a weak system and XOR it >>with another weak system, what do we expect to get? > >XOR two LCGs, and you get an LCG. Not true: LCG XOR LCG is just that. It happens to be weak, and probably does represent some larger LCG, but we would not know that from its structure. >This is not true about an M-M >generator. We don't know that. >Suddenly, all the leaked information disappears: each byte >of output could be produced by many different combinations of input >from the generators themselves. But the very same statement could be made about LCG's, and you already know they are weak, which also means your argument is weak. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Has some already created a DATA DIODE? Date: Tue, 15 Feb 2000 12:07:02 GMT From: jsavard@domain.ctry (John Savard) Message-ID: <38a93fe3.10479749@news.prosurfr.com> References: <38a8a3f0.2421428@news.io.com> Newsgroups: sci.crypt Lines: 20 ritter@io.com (Terry Ritter) wrote, in part: >Only partly: Obviously a combiner must be balanced. Across each >possible input value, each particular result must occur the same >number of times. But there is more, in that the linear relationships >in the driving system must be obscured. I will admit that the MacLaren-Marsaglia technique doesn't really qualify as a _combiner_. It uses a supplementary keystream to improve and obscure the characteristics of a primary keystream, but the supplementary keystream doesn't participate on an equal footing. Of course a single stage of M-M may be weak by itself, just as an LFSR is definitely weak by itself. Two-round DES is weak too. But every cipher is built up from primitives that, standing alone, are weak. The M-M technique is, I believe, a very useful and powerful primitive that is unjustly neglected at present. John Savard (jsavard<at>ecn<dot>ab<dot>ca) http://www.ecn.ab.ca/~jsavard/crypto.htm
Subject: Re: Has some already created a DATA DIODE? Date: Tue, 15 Feb 2000 20:52:46 GMT From: Tom St Denis <stdenis@compmore.net> Message-ID: <88ceas$vhl$1@nnrp1.deja.com> References: <38a7fbcb.13805991@news.prosurfr.com> Newsgroups: sci.crypt Lines: 46 In article <38a7fbcb.13805991@news.prosurfr.com>, jsavard@domain.ctry (John Savard) wrote: > Tom St Denis <stdenis@compmore.net> wrote, in part: > > >AlgM is a good place to start, just don't use LCG's as the underlying > >PRNG. AlgM with two 'long' Fibonacii generators is secure. > > His method doesn't seem to be too different from MacLaren-Marsaglia: > here, the choice is between one of many seed values, but the seed > values are only advanced when used. > > LFSRs and LCGs are insecure for the same reason, both being linear, so > I don't think it matters which one you use for MacLaren-Marsaglia. > > The literature references to MacLaren-Marsaglia generators being > cracked involved short-period LCGs, where the entire output, including > the LSBs, with periods down to two, was used in the output stream, so > I don't think they can be used to support a conclusion that the > technique ought to be abandoned. However, I would recommend, at a > minimum, a technique like this: have _two_ MacLaren-Marsaglia > generators, and use the XOR of their output as input to a _third_ > buffer. > > I have little fear that this kind of technique will suddenly be proven > insecure. However, the PRNGs used for the three buffers must have > rel-prime periods. The problem I have is, what does this have todo with when you use a LFG? I understand that LCG/LFSRs normally have very little state information, but in a LFG you have n * k bits [n is the number of words, and k is the bits per word]. There are 2^(k-1)(n-1) full length cycles and each cycle is (2^(k-1))(2^n - 1) outputs long. This is much larger, longer and more complex then a LFSR or LCG. Even so you should tap the upper msb's from the LFG when stepping [since they have the longest period]. So I ask again [this is an open question], how do you attack AlgM using two [properly constructed] long period LFG's? [long period would be something over 2^100 outputs...] Tom Sent via Deja.com http://www.deja.com/ Before you buy.
Terry Ritter, his current address, and his top page.
Last updated: 2001-05-09