======== Path: news.io.com!usenet From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Fenced DES Attack Questioned Date: Mon, 02 Sep 1996 06:04:40 GMT Organization: Illuminati Online Lines: 365 Message-ID: <50dtca$mss@anarchy.io.com> NNTP-Posting-Host: dialup-01-158.austin.io.com X-Newsreader: Forte Free Agent 1.0.82 In message <3220FFAD.27BB@jhuapl.edu> to sci.crypt on 25 Aug 1996, Brian Olson gave an attack on the Fenced DES cipher (described in my pages at http://www.io.com/~ritter/). At first I was happy to agree that Olson had a point, but as it turns out, that may have been somewhat premature. The attack seemed like it ought to work, and I was fairly convinced myself, until I had to explain it in detail. While attempting to prepare a summary for sci.crypt, I was surprised that I could not find an understanding which would make the attack work. Since the only comprehensive description of the attack remains the original message, I regurgitate it here in the hopes that someone can help resolve the issue. THE FENCED DES DESIGN Fenced DES is a "4x" or 256-bit wide block cipher based on DES. It is intended to provide strength far beyond "single" DES, and speed far beyond Triple DES, which is the usual DES replacement. It has the unusual *guarantee* of having no less strength than DES. Related "2x" and "1x" versions are used at most once at the end of an arbitrary-size message, to produce expansion characteristics similar to "single" DES, thus allowing the wide "4x" block to be used in most existing DES applications. S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S ------------------------------mix------------------------------ --------------mix-------------- --------------mix-------------- ------DES------ ------DES------ ------DES------ ------DES------ --------------mix-------------- --------------mix-------------- ------------------------------mix------------------------------ S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S Each "S" represents a separately-shuffled and independent 8-bit substitution table. There are 32 input and 32 output tables across a "4x" 256-bit data block. Each "---DES---" represents a 64-bit-block DES operation. Each will have its own 56-bit key which could be changed with less overhead than re-keying the substitutions. Each "---mix---" represents the mixing of the covered data blocks using wide, linear "Balanced Block Mixing" technology. (This technology also includes byte-wide linear and nonlinear "FFT"-style mixings not used in the original design, but which could be immediately fielded to upgrade the design, if necessary.) THE GENERAL ATTACK In general, sets of 4 bytes of data are mixed together to produce 4 mixed bytes, one of which goes to each DES operation. There are 8 such "mixing sets" so that every input bit is mixed into every DES operation. The goal would seem to be to identify 256 codes (out of the 2**32 4-byte codes in one input mixing set) which would allow us to put any byte value into some DES operation, while leaving the other DES operations unchanged or "fixed." This is "divide and conquer." If we can do this for all 8 bytes into the same DES operation, we can attack that DES. Then we run the same attack on the other DES's and solve the whole system. (We do have to somehow make sure that we get the codes which fix the *same* 3 DES operations. We also may have to do something similar on the output stages, and might have to somehow actually identify the substitution table contents. We ignore all this for now). THE DETAILED ATTACK >In your block mixing functions, it seems that a change of one bit >position in either half of the input can change only the output bit >in the same position and the one to the immediate left (circularly). >Am I wrong on that? If so, the change between a plaintext A and A' >needed to make three of the internal DES applications receive the >same input are not all that "substantial". Even with the >substitutions we could certainly search for them. The fact that these wide mixings are not byte-partitioned may be getting in the way. In the wide mixing, a set of 4 byte-width outputs will have come from 4 inputs, but each of these may have come from two adjacent input bytes. I would suggest considering the same argument in the context of "FFT"-pattern mixing, in which 4 input bytes are mixed to 4 output bytes. It would seem this would be easier to attack, and should be easier to discuss. >I can pick four bytes that will be mixed only with each other in >both levels of pre-DES mixing. Yes, this is the way it works. Especially in the case of "FFT"-pattern mixing, two sub-levels will mix sets of 4 bytes into 4 mixed bytes. Each of the 4 DES operations gets one of the 4 mixed results from each of 8 sets. Thus, each DES is eventually affected by every input bit across a 32-byte block. >In all 2^32 four byte values, there >should be several (maybe 64, I haven't ground it out) pairs of A and A' >that result in a 0 difference for inputs of three of the DES >applications. With the Balanced Block Mixing, we have a mathematical guarantee that the transformation is invertible. This means that each and every input code (across all inputs) translates to exactly one unique output code. In the context of 4-byte the "FFT"-pattern mixing, for *any* set of 3 byte mixed values, there will be exactly 256 codes which will keep the desired 3 output bytes unchanged. We can do this for any possible set of 3 mixed output values. Conversely, *every* 4-byte input code is a part of 4 "match" sets (one for each possible group of 3 fixed DES operations). (The same thing should happen with wide mixing, but is not as obvious. Certainly the wide mixing is invertible; in general, bit-subsets of invertible transformations are not necessarily invertible, but for the simple linear mixing transformation, this might be so.) >I'll call A and A' a "match" if they have that property. Note that for *every* 32-bit A there are 1024 A' codes that "match" in this sense. (There are 256 A' codes that match for each of 4 possible sets of 3 DES operations held fixed.) >You say it "seems unlikely that we could tell from the outside that we >were successful" in finding such a match. If A and A' are a match, I >can immediately find many other matches by changing bytes which don't >interact with the critical four. This does not sound right: Yes, you can change other input bytes, but in general, no, the result will not be another "match." Changing other parts of the block will involve other mixing sets and they will change the formerly fixed DES operations. There are of course values in other mixing sets which will maintain a match, but we would have to find them, which would in no sense be "immediate," were it even possible. This may be THE CRITICAL ISSUE in the attack: The 4 input bytes in one mixing set do "interact" in mixing, and each of the 8 mixing sets is separate. However, all of the input bytes do "interact" in each DES operation. Changing values outside a mixing set will not affect the output of the mixing set, but will still change the input to each of the DES operations and the DES results. >That gives me a good space to search >for any statistical anomaly which would indicate a match. > >So what anomaly do I search for? > >Let's turn our attention to an output of the DES boxes. If I have a >match, three of them are the same under A as under A'. Again, if A and A' produce the same byte values from one mixing set on 3 of the 4 DES operations, we have a "match." Again, considering only one 32-byte input mixing set, for any possible A, we know there will be 256 matching A' values for each group of 3 fixed DES operations, for a total of 1024 A' values which "match" A (out of 2**32 possible A' values). So the probability of finding an A' which "matches" a given A is about one in 2**22. >In your analysis >you assume the output of the fourth will be unrelated between A and A', >and this will make all the outputs appear unrelated. But what if just >some output bits from this S box turn out to be the under A and A', and >in a fortuitous combination. Specifically: > 1. One of the eight bytes (on the byte boundary) > 2. The two most significant bits in the byte to the right of 1. > >If that happens, then all 4 DES outputs will have 10 bits positions >which are the same under A as under A'. I believe this is where things start to get complicated by the wide mixing. Let's not worry about (2), but assume (1). By chance, the critical 8 bits from the single DES which does change under A' turn out to be unchanged from A. This can happen because we consider the changing DES to be a random function, so it may produce the same code value on the 8-bit output subset we consider. It will also change the rest of the output values, and all of the output mixing sets will behave the same way. >The block mixing will preserve >8 of them, lined up with a single substitution at the end. Thus in the >output, we'll see four bytes, each three bytes apart, which are >identical >under A and A'. OK, since three of the DES operations have not changed, if by chance the output of the fourth DES also produces the same byte value (a subset of the DES output), then the associated output mixing sets will be unchanged, and the associated 4 output bytes will also be unchanged. Since we do not know the particular 256 input codes in a "match" set, we might scan A' across 2**32 codes to seek a "match" to A as indicated by an unchanging output mixing set. Now, there are 2**10 match codes (if we don't care which one DES changes) out of the possible 2**32. But even then, we only expect perhaps 16 unchanging outputs between the 256 codes in a "match" set, for each of 8 output sets. And it does not seem possible to separate the 4 different "match" sets that we will run across. We might think to scan across the 2**32 codes once, capture the results, and find all the match pairs. However, there are 2**24 "match" sets (of 256 elements each) overall. (There are 2**22 if we include the four possibilities for the selected changing DES). Indeed, *every* 32-bit value is part of *4* match sets. While any match probably identifies two codes in *some* match set, what we need to do is fill out *one* match set. It is not clear how to do that. >By chance, the four identical bytes I guess the "four identical bytes" are the 4 bytes from a single output mixing set being unchanged between A and A'. >should appear once in 2^24 pairs A >and >A', for each of the 8 byte positions. Well, this *is* the probability of getting 3 particular DES operations to have unchanged values ("matches") under A and A'. But there are 4 ways to do this -- any of the 4 DES operations can be the one changing DES operation. So, say 2**22 instead. But this *only* produces the *internal* "match," and not necessarily unchanged output. The 32-bit output of one mixing set is not unchanged unless the changing DES operation by chance produces the same values into that mixing set. This confusion between "match" and "unchanged output" certainly caused me some problems. >Conditions 1 and two (above) >should >hold about once in 2^10 pairs. Let's forget about (2) and call it once in 2**8 for random values. I didn't understand the next paragraph from the start, and so got another explanation in <3224613B.3BEE@jhuapl.edu>: >> >If they hold under a non-match, then the four-byte coincidence >> >still has the same probability, but if they hold >> >under a match, then the coincidence is a certainty. >> >> ? >> >I was simply pointing out that the 1 in 2**10 shot can >occur whether or not I have a match. It increases the >chances of the visible pattern in the output only if it >holds under a match. And I guess I still don't get it. >So if my four critical bytes do _not_ force a match, I expect to see the >four-byte pattern one in 2^21 pairs. By "four critical bytes" I guess we mean the bytes in a single input mixing group. By "four-byte pattern" I guess we mean that the 4 output bytes representing one output mixing group may not (by chance) change between inputs A and A'. Considering only the 2**32 codes which constitute one input mixing group, every possible A is part of 4 different "match" sets (of 256 codes) which keep a different set of 3 DES operations fixed. The probability of getting A' in one of the "fix 3 DES" sets defined by some A is (2**32 / 2**10) or 2**22. Considering a particular 32-bit output mixing set, of the 256 input codes A in a particular "match" set, perhaps one in 16 will produce the same 32-bit output code as some other in the set. But if we use all 8 possible output mixing sets, we might improve this by a factor of 8, so perhaps half of the 256 codes in a "match" set will fix one of the 8 output mixing sets. It is not clear how any of this helps. Even if we find some "match" values in another input mixing set, it is not clear that we could use them to build up even two known bytes on the same DES. Sure, the mixing sets are independent, but we have no way to know which DES is being selected, and we do not have all 1024 possible matches to play with, because only a subset of these will produce the fixed output signature. >If they are a match, I'll see it >once in 2^7 pairs, where I form the pairs by holding these four input >bytes >constant and varying others (not immediately to their circular right). By "they" I guess we mean the two values A and A' considering only the 4 bytes in a single input mixing group. By "match" I guess we mean the situation where only one of the DES operations has a different input byte (from that mixing group) between A and A'. By "varying others" I guess we mean bits or bytes not in the original mixing group. But if we "vary others," we now (in general) change *all* *4* of the DES operations, which means that we no longer have a "match," in general. If we confine ourselves to one other input mixing group, then, one time in 2**24 we fix the same DES operations as in the original mixing group. I don't see that this helps at all. >So I have to search over a 2^32 space, and run a few hundred pairs for >each to find such a match. Once I've found it, I have a lot of >information about the four permutations which formed my four critical >bytes. Repeating the process to find all the matches over all 32 >permutions, I should be able to break the initial permutations. Looking >at what happens in the output, I can probably infer a lot about the >final >permutations too. But the final stroke depends on the previous step, which I do not see. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ ======== Path: news.io.com!arlut.utexas.edu!geraldo.cc.utexas.edu!cs.utexas.edu!howland.erols.net!newsfeed.internetmci.com!news.campus.mci.net!uky.edu!cpk-news-feed1.bbnplanet.com!netnews.jhuapl.edu!usenet From: Bryan Olson <Bryan_Olson@jhuapl.edu> Newsgroups: sci.crypt Subject: Re: Fenced DES Attack Questioned Date: Mon, 02 Sep 1996 14:27:05 -0400 Organization: Johns Hopkins Applied Physics Lab Lines: 171 Message-ID: <322B26F9.57CA@jhuapl.edu> References: <50dtca$mss@anarchy.io.com> Reply-To: Bryan_Olson@jhuapl.edu NNTP-Posting-Host: snake.jhuapl.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 3.0 (WinNT; I) Terry Ritter wrote: > > In message <3220FFAD.27BB@jhuapl.edu> to sci.crypt on 25 Aug 1996, > Brian Olson gave an attack on the Fenced DES cipher (described in > my pages at http://www.io.com/~ritter/). > Bryan wrote: > >I'll call A and A' a "match" if they have that property. > That is, A and A' are a match if three of the internal DES applications receive the same input plaintext A as they do under plaintext A'. [...] > >If A and A' are a match, I > >can immediately find many other matches by changing bytes which don't > >interact with the critical four. > > This does not sound right: > > Yes, you can change other input bytes, but in general, > no, the result will not be another "match." Changing > other parts of the block will involve other mixing sets > and they will change the formerly fixed DES operations. > > There are of course values in other mixing sets which will maintain > a match, but we would have to find them, which would in no sense > be "immediate," were it even possible. > > This may be THE CRITICAL ISSUE in the attack: The 4 input bytes > in one mixing set do "interact" in mixing, and each of the 8 mixing > sets is separate. However, all of the input bytes do "interact" > in each DES operation. Changing values outside a mixing set will > not affect the output of the mixing set, but will still change > the input to each of the DES operations and the DES results. > Yup, it's critical. Here's an example, and the key question: Using your mod 2 polynomial block mixer, given that: A = 0 0 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 A' = 0 0 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 (A,A') is a match, B = 0 1 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 B' = 0 1 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 what is the chance that (B,B') is also a match? My theory is that (B,B') will always be a match. Maybe there's something I didn't understand. > >That gives me a good space to search > >for any statistical anomaly which would indicate a match. > > > >So what anomaly do I search for? > > > >Let's turn our attention to an output of the DES boxes. If I have a > >match, three of them are the same under A as under A'. > > Again, if A and A' produce the same byte values from one mixing set > on 3 of the 4 DES operations, we have a "match." > > Again, considering only one 32-byte input mixing set, for any > possible A, we know there will be 256 matching A' values for each > group of 3 fixed DES operations, for a total of 1024 A' values > which "match" A (out of 2**32 possible A' values). So the > probability of finding an A' which "matches" a given A is about > one in 2**22. > Agreed. > > OK, since three of the DES operations have not changed, if by > chance the output of the fourth DES also produces the same > byte value (a subset of the DES output), then the associated > output mixing sets will be unchanged, and the associated 4 > output bytes will also be unchanged. > > Since we do not know the particular 256 input codes in a "match" > set, we might scan A' across 2**32 codes to seek a "match" to A > as indicated by an unchanging output mixing set. Now, there > are 2**10 match codes (if we don't care which one DES changes) > out of the possible 2**32. But even then, we only expect > perhaps 16 unchanging outputs between the 256 codes in a "match" > set, for each of 8 output sets. And it does not seem possible > to separate the 4 different "match" sets that we will run > across. > If my (A,A')match -> (B,B') match conclusion is correct, then I think I can recognizing all the matches. > >By chance, the four identical bytes should appear once in > >2^24 pairs A and A', for each of the 8 byte positions. > I don't remember how I got 2^24, but I think it should be 2^32. I'm talking about the output pattern: four bytes which are the same in the ciphertexts of A and A'. The chance of getting this pattern without a match should be about one in 2^32 for each of the 8 byte positions. > > This confusion between "match" and "unchanged output" certainly > caused me some problems. > Perhaps the first thing I should distinguish is "matching", which is a property of a pair of 256-bit plaintexts, from "forcing a match" which a property of a pair of 4-byte vectors and one of the 8 positions in an 8 byte block. In my example, A and A' match; (x1,x2,x3,x4) and (y1,y2,y2,y4) force a match. My theory is that the same pair of four-byte vectors will force a match in many plaintext pairs, (pairs where these four bytes are the only ones which differ in the two members of the pair). Thus if there is some observable pattern in the output which appears with higher probability under a match than under a non-match, I can recognize the values which force a match. When testing a candidate for a pair which forces a match, I fix the byte positions holding the candidate. I vary other bytes to form new pairs. > But if we "vary others," we now (in general) change *all* *4* > of the DES operations, which means that we no longer have a "match," > in general. If we confine ourselves to one other input mixing > group, then, one time in 2**24 we fix the same DES operations as > in the original mixing group. > I guess this wasn't clear. I change bytes outside the mixing group to form new pairs, but I make the identical change in A and A'. Only the the bytes which I'm testing for a forced match vary between the two members of the same pair. In the example, I changed one byte from a 0 in A and A' to a 1 in B and B'. I'm not trying to keep DES inputs constant between A and B, or A' and B'. > >So I have to search over a 2^32 space, and run a few hundred pairs for > >each to find such a match. Once I've found it, I have a lot of > >information about the four permutations which formed my four critical > >bytes. Actaully a pair of 4 critical bytes, as in (x1,x2,x3,x4) (y1,y2,y3,y4). I haven't pushed the attack from where I left it. If any of my steps is impossible, I sure want to know. The key question is whether the concept of "forcing a match" is vacuous. If (x1,x2,x3,x4) (y1,y2,y3,y4) result in a match between A and A', but have no such effect on B and B', then I agree the attack fails. --Bryan ======== Path: news.io.com!usenet From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Fenced DES Attack Questioned Date: Tue, 03 Sep 1996 05:21:29 GMT Organization: Illuminati Online Lines: 118 Message-ID: <50gf7b$c8h@anarchy.io.com> References: <50dtca$mss@anarchy.io.com> <322B26F9.57CA@jhuapl.edu> NNTP-Posting-Host: dialup-01-164.austin.io.com X-Newsreader: Forte Free Agent 1.0.82 In <322B26F9.57CA@jhuapl.edu> Bryan Olson <Bryan_Olson@jhuapl.edu> wrote: > A and A' are a match if three of the internal DES >applications receive the same input plaintext A as they do >under plaintext A'. > Here's an example, and >the key question: >Using your mod 2 polynomial block mixer, >given that: > A = 0 0 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 > A' = 0 0 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 > (A,A') is a match, > B = 0 1 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 > B' = 0 1 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 >what is the chance that (B,B') is also a match? >My theory is that (B,B') will always be a match. I *also* think (B,B') is a "match," but the only "match" involved is the same as it was originally. This means that we can create many different "views" of the same match. This means that we can develop an output distribution which is at least potentially different between a "match" and a non-match. And, if the distribution signature is sufficiently distinct, we can detect a "match." This is *how* we find a "match" in the first place, and also the way we find out which mixing group is involved. (It will be necessary to change values in the various mixing sets to show which one controls the match.) Impressive, of course, but just *part* of the way to a break. >> [...] >> OK, since three of the DES operations have not changed, if by >> chance the output of the fourth DES also produces the same >> byte value (a subset of the DES output), then the associated >> output mixing sets will be unchanged, and the associated 4 >> output bytes will also be unchanged. >> >> Since we do not know the particular 256 input codes in a "match" >> set, we might scan A' across 2**32 codes to seek a "match" to A >> as indicated by an unchanging output mixing set. Now, there >> are 2**10 match codes (if we don't care which one DES changes) >> out of the possible 2**32. But even then, we only expect >> perhaps 16 unchanging outputs between the 256 codes in a "match" >> set, for each of 8 output sets. And it does not seem possible >> to separate the 4 different "match" sets that we will run >> across. >> >If my (A,A')match -> (B,B') match conclusion is correct, then >I think I can recognizing all the matches. Suppose we *can* find all 1024 "match" values A' (for some A, and one of the 8 input mixing sets): Even if we detect *every* match, there are four different "match" sets involved, one for each DES. So we have 1024 "match" values, and will apparently have to separate them into the correct 4 sets so we can work on a single DES. It is not clear how one could do this. Then we need to talk about how one could actually resolve the substitution contents for associated table(s), as this would seem to be necessary to attack the DES. If this *is* necessary, we may have to resolve the output substitutions as well. I'd say there several serious problems left to solve before we have a real break. >I don't remember how I got 2^24, but I think it should be >2^32. I'm talking about the output pattern: four bytes which >are the same in the ciphertexts of A and A'. The chance of >getting this pattern without a match should be about one in >2^32 for each of the 8 byte positions. OK. >> >> This confusion between "match" and "unchanged output" certainly >> caused me some problems. >> >Perhaps the first thing I should distinguish is "matching", >which is a property of a pair of 256-bit plaintexts, from >"forcing a match" which a property of a pair of 4-byte >vectors and one of the 8 positions in an 8 byte block. >In my example, A and A' match; (x1,x2,x3,x4) and >(y1,y2,y2,y4) force a match. Actually, using your "match" terminology, a pair of 256-bit plaintexts can: match, not match, not match, match, match, match, not match, and match; one possibility for each mixing set. This is why I have been trying to restrict the discussion to a 32-bit mixing set, which indeed can only match or not. >I haven't pushed the attack from where I left it. If any >of my steps is impossible, I sure want to know. The key >question is whether the concept of "forcing a match" is >vacuous. If (x1,x2,x3,x4) (y1,y2,y3,y4) result in a match >between A and A', but have no such effect on B and B', then >I agree the attack fails. No, I think we can find matches, if we are willing to do, say, 2**40 messages for each mixing set (a total of, say, 2**43). But the attack needs several additional steps -- which might *each* be pretty tricky -- before we have a real break. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ ======== Path: news.io.com!news.thenet.net!news.supernet.net!news-out.microserve.net!news-in.microserve.net!mr.net!www.nntp.primenet.com!nntp.primenet.com!news.mindspring.com!newspump.sol.net!spool.mu.edu!news.sgi.com!wrdiss1.robins.af.mil!news.monroe.army.mil!info.usuhs.mil!cs.umd.edu!news.umbc.edu!olson From: olson@umbc.edu (olson bryan ( ms cmsc)) Newsgroups: sci.crypt Subject: Re: Fenced DES Attack Questioned Date: 3 Sep 1996 21:58:22 GMT Organization: University of Maryland, Baltimore County Lines: 118 Message-ID: <50i9lu$bvu@news.umbc.edu> References: <50dtca$mss@anarchy.io.com> <322B26F9.57CA@jhuapl.edu> <50gf7b$c8h@anarchy.io.com> NNTP-Posting-Host: umbc8.umbc.edu NNTP-Posting-User: olson X-Newsreader: TIN [version 1.2 PL2] Terry Ritter (ritter@io.com) wrote: : In <322B26F9.57CA@jhuapl.edu> Bryan Olson: wrote: : > A and A' are a match if three of the internal DES : >applications receive the same input plaintext A as they do : >under plaintext A'. : > Here's an example, and : >the key question: : >Using your mod 2 polynomial block mixer, : >given that: : > A = 0 0 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 : > A' = 0 0 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 : > (A,A') is a match, : > B = 0 1 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 : > B' = 0 1 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 : >what is the chance that (B,B') is also a match? : >My theory is that (B,B') will always be a match. : I *also* think (B,B') is a "match," but the only "match" involved is : the same as it was originally. Right. The same four byte positions force the match. I'm calling this two matches. [...] : Impressive, of course, but just *part* of the way to a break. [...] : >If my (A,A')match -> (B,B') match conclusion is correct, then : >I think I can recognizing all the matches. : Suppose we *can* find all 1024 "match" values A' (for some A, and one : of the 8 input mixing sets): Even if we detect *every* match, there : are four different "match" sets involved, one for each DES. So we : have 1024 "match" values, and will apparently have to separate them : into the correct 4 sets so we can work on a single DES. It is not : clear how one could do this. Suppose A = 0 0 0 0 0 0 0 w1 0 0 0 0 0 0 0 w2 0 0 0 0 0 0 0 w3 0 0 0 0 0 0 0 w4 A'= 0 0 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 (A,A') is a match B = 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 0 0 B'= 0 0 0 0 0 z1 0 0 0 0 0 0 0 z2 0 0 0 0 0 0 0 z3 0 0 0 0 0 0 0 z4 0 0 (B,B') is a match C = 0 0 0 0 0 y1 0 w1 0 0 0 0 0 y2 0 w2 0 0 0 0 0 y3 0 w3 0 0 0 0 0 y4 0 w4 C'= 0 0 0 0 0 z1 0 x1 0 0 0 0 0 z2 0 x2 0 0 0 0 0 z3 0 x3 0 0 0 0 0 z4 0 x4 What is the chance that (C,C') is a match? I think it's about 1 in four, and it tells me whether the (A,A') match is based on the same DES boxes as the (B,B') match. I can use the same form to seperate all the match-forcing vectors into the four sets -- not just the 1024 in the same mixing set, but also across mixing sets. : Then we need to talk about how one could actually resolve the : substitution contents for associated table(s), as this would seem to : be necessary to attack the DES. If this *is* necessary, we may have : to resolve the output substitutions as well. I'd say there several : serious problems left to solve before we have a real break. : >Perhaps the first thing I should distinguish is "matching", : >which is a property of a pair of 256-bit plaintexts, from : >"forcing a match" which a property of a pair of 4-byte : >vectors and one of the 8 positions in an 8 byte block. : >In my example, A and A' match; (x1,x2,x3,x4) and : >(y1,y2,y2,y4) force a match. : Actually, using your "match" terminology, a pair of 256-bit plaintexts : can: match, not match, not match, match, match, match, not match, and : match; one possibility for each mixing set. I'll stick with my definition of match. Two plaintexts either match or don't. [...] : No, I think we can find matches, if we are willing to do, say, 2**40 : messages for each mixing set (a total of, say, 2**43). Which is small compared to the work to break DES. : But the attack needs several additional steps -- which might *each* be : pretty tricky -- before we have a real break. Yup. But are you going to change the design? --Bryan ======== Path: news.io.com!usenet From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Fenced DES Attack Questioned Date: Thu, 05 Sep 1996 18:41:25 GMT Lines: 65 Message-ID: <50n6r2$ibu@nntp-1.io.com> References: <50dtca$mss@anarchy.io.com> <322B26F9.57CA@jhuapl.edu> <50gf7b$c8h@anarchy.io.com> <50i9lu$bvu@news.umbc.edu> NNTP-Posting-Host: dialup-01-106.austin.io.com X-Newsreader: Forte Free Agent 1.0.82 In <50i9lu$bvu@news.umbc.edu> olson@umbc.edu (olson bryan ( ms cmsc)) wrote: >Terry Ritter (ritter@io.com) wrote: >: In <322B26F9.57CA@jhuapl.edu> Bryan Olson <Bryan_Olson@jhuapl.edu> >: wrote: >: > A and A' are a match if three of the internal DES >: >applications receive the same input plaintext A as they do >: >under plaintext A'. >: Suppose we *can* find all 1024 "match" values A' (for some A, and one >: of the 8 input mixing sets): Even if we detect *every* match, there >: are four different "match" sets involved, one for each DES. So we >: have 1024 "match" values, and will apparently have to separate them >: into the correct 4 sets so we can work on a single DES. It is not >: clear how one could do this. >Suppose > A = 0 0 0 0 0 0 0 w1 0 0 0 0 0 0 0 w2 0 0 0 0 0 0 0 w3 0 0 0 0 0 0 0 w4 > A'= 0 0 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 > (A,A') is a match > B = 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 0 0 > B'= 0 0 0 0 0 z1 0 0 0 0 0 0 0 z2 0 0 0 0 0 0 0 z3 0 0 0 0 0 0 0 z4 0 0 > (B,B') is a match > C = 0 0 0 0 0 y1 0 w1 0 0 0 0 0 y2 0 w2 0 0 0 0 0 y3 0 w3 0 0 0 0 0 y4 0 w4 > C'= 0 0 0 0 0 z1 0 x1 0 0 0 0 0 z2 0 x2 0 0 0 0 0 z3 0 x3 0 0 0 0 0 z4 0 x4 >What is the chance that (C,C') is a match? My guess: 1 in 4. >I think it's about 1 in four, and it tells me whether the (A,A') >match is based on the same DES boxes as the (B,B') match. I can >use the same form to seperate all the match-forcing vectors into >the four sets -- not just the 1024 in the same mixing set, but >also across mixing sets. This took me some time to understand, but I think it works. It is based on the exact same output distribution signature that found the original matches. Very clever. >: But the attack needs several additional steps -- which might *each* be >: pretty tricky -- before we have a real break. >Yup. But are you going to change the design? You mean, am I ready to concede based on your work so far, plus a hint and a grin? I almost settled for that once! You said you had an effective attack on Fenced DES, and I'm waiting to see it. You specifically wanted credit for breaking Fenced DES, so break it. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ ======== Path: news.io.com!news.thenet.net!news.kei.com!newsfeed.internetmci.com!news.campus.mci.net!service3.uky.edu!cpk-news-feed1.bbnplanet.com!netnews.jhuapl.edu!usenet From: Bryan Olson <Bryan_Olson@jhuapl.edu> Newsgroups: sci.crypt Subject: Re: Fenced DES Attack Questioned Date: Thu, 05 Sep 1996 19:20:21 -0400 Organization: Johns Hopkins Applied Physics Lab Lines: 112 Message-ID: <322F6035.31A9@jhuapl.edu> References: <50dtca$mss@anarchy.io.com> <322B26F9.57CA@jhuapl.edu> <50gf7b$c8h@anarchy.io.com> <50i9lu$bvu@news.umbc.edu> <50n6r2$ibu@nntp-1.io.com> Reply-To: Bryan_Olson@jhuapl.edu NNTP-Posting-Host: snake.jhuapl.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 3.0 (WinNT; I) Terry Ritter wrote: > > In <50i9lu$bvu@news.umbc.edu> olson@umbc.edu (olson bryan ( ms cmsc)) > wrote: > > >Terry Ritter (ritter@io.com) wrote: > > >: In <322B26F9.57CA@jhuapl.edu> Bryan Olson <Bryan_Olson@jhuapl.edu> > >: wrote: > > >: > A and A' are a match if three of the internal DES > >: >applications receive the same input plaintext A as they do > >: >under plaintext A'. > > >: Suppose we *can* find all 1024 "match" values A' (for some A, and one > >: of the 8 input mixing sets): Even if we detect *every* match, there > >: are four different "match" sets involved, one for each DES. So we > >: have 1024 "match" values, and will apparently have to separate them > >: into the correct 4 sets so we can work on a single DES. It is not > >: clear how one could do this. > > >Suppose > > A = 0 0 0 0 0 0 0 w1 0 0 0 0 0 0 0 w2 0 0 0 0 0 0 0 w3 0 0 0 0 0 0 0 w4 > > A'= 0 0 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 > > (A,A') is a match > > > B = 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 0 0 > > B'= 0 0 0 0 0 z1 0 0 0 0 0 0 0 z2 0 0 0 0 0 0 0 z3 0 0 0 0 0 0 0 z4 0 0 > > (B,B') is a match > > > C = 0 0 0 0 0 y1 0 w1 0 0 0 0 0 y2 0 w2 0 0 0 0 0 y3 0 w3 0 0 0 0 0 y4 0 w4 > > C'= 0 0 0 0 0 z1 0 x1 0 0 0 0 0 z2 0 x2 0 0 0 0 0 z3 0 x3 0 0 0 0 0 z4 0 x4 > > >What is the chance that (C,C') is a match? > > My guess: 1 in 4. > > >I think it's about 1 in four, and it tells me whether the (A,A') > >match is based on the same DES boxes as the (B,B') match. > >I can > >use the same form to seperate all the match-forcing vectors into > >the four sets -- not just the 1024 in the same mixing set, but > >also across mixing sets. > > This took me some time to understand, but I think it works. It is > based on the exact same output distribution signature that found the > original matches. Very clever. > Using the polynomial block mixer, I think the matches partition each 4 byte mixing set into groups of 64, not 256, for each DES box. One match set, which holds the input to the first 3 DES boxes constant, seems to contain: 00 00 00 00 (hex) 04 04 04 05 08 08 08 0a 10 10 10 14 20 20 20 28 40 40 40 50 80 80 80 a0 Note that all but the zero vector are the same bit pattern shifted 0-6 positions. It also contains all linear (bitwise mod 2) combinations of these, for a total of 64 members. All other match groups can be formed by adding (bitwise mod 2) some constant to each of the members of this group. We might consider 04 04 04 05 (hex) to be the generator for the groups of this DES box. The list of generators is: 05 04 04 04 06 07 06 06 06 06 07 06 04 04 04 05 > >But are you going to change the design? > > You mean, am I ready to concede based on your work so far, plus a hint > and a grin? I almost settled for that once! > > You said you had an effective attack on Fenced DES, and I'm waiting to > see it. You specifically wanted credit for breaking Fenced DES, so > break it. > You've agreed the attack does what I said it does. Clearly the attack starts on the initial permutations, and you're right if you claim I haven't told how to break them. There's a good reason: your Fenced DES posts don't specifiy how they're generated. At the very least we have a meet-near-the-middle attack since the analyst has a lot of information to test candidate permutations. Sure you can make the key space big enough to beat it, but as you said, the attack is on the structure of Fenced DES. That structure was supposed to provide security proportional to the product of the security of the components. Finally, I think I've kept a respectable achedemic tone. I resent your suggestion that I've been blowing my own horn here. You show me where I claimed to break Fenced DES, or anything else that wasn't justified. I said the attack was "a strong enough toe-hold for the analyst that Fenced DES is dead", and I stand by that. Your a fool if you keep using the same design. --Bryan ======== Path: news.io.com!usenet From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Fenced DES Attack Questioned Date: Fri, 06 Sep 1996 08:18:01 GMT Lines: 259 Message-ID: <50ommd$k9a@nntp-1.io.com> References: <50dtca$mss@anarchy.io.com> <322B26F9.57CA@jhuapl.edu> <50gf7b$c8h@anarchy.io.com> <50i9lu$bvu@news.umbc.edu> <50n6r2$ibu@nntp-1.io.com> <322F6035.31A9@jhuapl.edu> NNTP-Posting-Host: dialup-01-092.austin.io.com X-Newsreader: Forte Free Agent 1.0.82 In <322F6035.31A9@jhuapl.edu> Bryan Olson <Bryan_Olson@jhuapl.edu> wrote: >You've agreed the attack does what I said it does. I have agreed that you have made remarkable progress. I even was willing to agree that your "attack" probably worked. This lasted exactly as long as it took for me to work through your supposed "attack" and find out that it did *not* "work"; that it was not, in fact, a successful cryptanalysis. Subsequently (and with good reason), I expected you to dot your "i's" and cross your "t's." Is an "attack" an "attack" if it does not "break" the cipher, and does not resolve how much work would be necessary to break the cipher? Maybe in your dreams. But if dreams are good enough, we don't need cryptanalysis, do we? I never claim any of my work is unbreakable, and I take the considerable "risk" of completely exposing my designs to public ridicule so they *can* be attacked. If they are weak, I want to know. But if I am going to take comments like yours of Sun, 25 Aug 1996 in message <3220FFAD.27BB@jhuapl.edu>: "I'd like to see fewer proposed ciphers with much more careful analysis." "How carefully did you analyze your own cipher before you proposed it?" . . . I am going to expect that when an attack is said to "work," that it actually *work*, all the way through. Silly me. >Clearly >the attack starts on the initial permutations, and you're >right if you claim I haven't told how to break them. >There's a good reason: your Fenced DES posts don't >specifiy how they're generated. This is *more* than false, it is deliberately *deceptive*. 1. Here is the description from my "Fenced DES" HTML article (http://www.io.com/~ritter/FENCED.HTM): "Each "S" represents a separately-shuffled and independent 8-bit substitution table. This implies the presence of a particular keyed cryptographic RNG to shuffle the tables. The tables are set up and shuffled before ciphering, and then remain static during ciphering." 2. Here is the description from my ASCII article "The Context of the Fenced DES Design" (http://www.io.com/~ritter/NEWS/94070101.HTM): "Each Fenced DES substitution must be shuffled by a cryptographic random number generator (RNG) before ciphering begins (the RNG is not needed during actual ciphering). Presumably, the same RNG will also generate the DES keys. Fortunately, in this application, the cryptographic strength aspects of the RNG can be minimized, because the only RNG exposure is in the arrangement of the values in the substitutions, and if that arrangement is known, the cipher is probably broken anyway. " Perhaps the most efficient basis for such an RNG is the Additive RNG [14:27]. This has become well understood, and is basically a Linear Feedback Shift Register (LFSR) using addition mod 2**n [16] [17]. The Additive RNG is especially suited to fast software implementation. In one version, there are three pointers into a circular queue, and the RNG "step" operation consists of taking two of the pointed-to elements, adding them, and placing the result in the queue through the third pointer. Then the pointers are incremented within the queue, and the result returned. "Thus, an Additive RNG based on a feedback trinomial (a primitive mod-2 polynomial) "steps" an RNG with a huge amount of internal state with just a single addition and a few pointer operations. We can compare this to a Linear Congruential Generator (LCG) which uses a multiply and an add, but involves only a small amount of state. We can also compare it to number-theoretic generators [e.g., 4], which must carry out a very expensive multiple-precision multiplication and division for each RNG step. " A reasonable structure for the Fenced DES RNG is 31 elements of 32 bits each, for a total state of 992 bits. (Recall that DES itself has a 56-bit key.) This state can be initialized easily from a User Key by using an array of 32 deg-31 primitive mod-2 polynomials as Cyclic Redundancy Checks (CRC's). This produces 32 31-bit values which can be re-arranged into 31 32-bit values to become the state for the RNG. This CRC-based initialization has a strong mathematical basis, and allows the User Key to be ASCII or binary, of arbitrary length, and thus provides a strong universal key interface. " Since the Additive RNG is essentially a linear mechanism, it is necessary to "nonlinearize" the sequence. My usual technique [23] is to "drop out" pseudo-random length sections of the linear sequence, leaving pseudo-random length "take" islands, and to "offset" each take sequence with a different pseudo-random offset value. With fairly short "take" islands, this should render the usual linear attacks worthless, at a cost of dropping some moderate fraction of the sequence. Additional isolation is provided by the cheap width of the RNG, since only 8 bits are needed, but 32 bits are calculated. This means that 3/4 of the RNG state is always hidden, but must nevertheless be resolved before the RNG can be completely exposed." 3. Here is the description from my "Fencing and Mixing Ciphers" ASCII article (http://www.io.com/~ritter/NEWS/96011601.HTM): " Each 256-byte substitution table is keyed by shuffling under a cryptographic RNG initialized from a User Key. That RNG also produces 4 separate random DES keys. Normally, the keyspace of this sort of cipher is limited by the size of the RNG used to key the substitutions, and it is easy to have a true keyspace of thousands of bits. "The ability to attack the keying RNG depends upon developing the state in one or more of the substitutions, then inferring the RNG sequence. But inferring the RNG sequence can be made difficult or impossible by double-shuffling each substitution. It is not at all clear how an attacker could develop the correct state of any substitution in the first place. Even a single bit error in any input table is guaranteed to produce avalanche, so the extent of solution of these tables cannot be distinguished." The analyst is obviously free to pick reasonable (primitive) polys for the CRC's and Additive RNG, if necessary to realize an attack. The sequence nonlinearizing component ("jitterizer") is described in both my Penknife (http://www.io.com/~ritter/PENDESN.HTM) and Cloak2 (http://www.io.com/~ritter/CLO2DESN.HTM) design documents, was referred to in my 1991 Cryptologia RNG article "The Efficient Generation of Cryptographic Confusion Sequences" (http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect5.4), and has been discussed on sci.crypt multiple times. Actually, this whole claim is specious, since the substitution contents would be needed to attack the RNG, and if one can get those, the cipher is already broken. >At the very least we have a meet-near-the-middle attack >since the analyst has a lot of information to test >candidate permutations. Until you can say how much work is involved, you really don't know squat about how reasonable it would be to mount such an attack, do you? And this is no ordinary "meet-in-the-middle" attack, for we know neither the exact data in, nor the exact data out, of the DES operation. There are three levels, not two, so there *is* no obvious "middle." >Sure you can make the key space >big enough to beat it, but as you said, the attack is on >the structure of Fenced DES. That structure was supposed >to provide security proportional to the product of the >security of the components. I don't have to make the keyspace anything: Since the attack is not complete, you don't know what level of strength Fenced DES provides. Despite your analysis, the structure *still* *is* protecting DES, because it is not clear how DES can be attacked in this situation. If you think that attacking DES with unknown input and output data values is easy, tell us how, and how much that will cost. >Finally, I think I've kept a respectable achedemic tone. >I resent your suggestion that I've been blowing my own >horn here. You show me where I claimed to break Fenced >DES, or anything else that wasn't justified. On Mon, 26 Aug 1996 in message <32221635.1686@jhuapl.edu> you wrote: "I'd invite anyone who has closely examined Terry's "Fenced DES" to comment on the attack I proposed in another thread of this same topic. If I've understood Terry's algorithm correctly, the attack should work, and I may write up a better exposition for the research group." I claim that an "attack" that solves only half the problem certainly does not "work." And I expect that if someone claims to be able to "attack" one of my designs that they can "put up or shut up" when called on their claim. Once again, on Sun, 25 Aug 1996 in message <3220FFAD.27BB@jhuapl.edu> you gave your *own* opinion of inadequate analysis: "I'd like to see fewer proposed ciphers with much more careful analysis." "How carefully did you analyze your own cipher before you proposed it?" Frankly, I think your own words have defined your requirements for a "successful" cryptanalysis. And on Wed, 28 Aug 1996 in message <3224613B.3BEE@jhuapl.edu> you so kindly quoted the FAQ for my edification: "If you don't have enough experience, then most likely any experts who look at your system will be able to find a flaw. If this happens, it's your responsibility to consider the flaw and learn from it, rather than just add one more layer of complication and come back for another round." [I suggest you apply this to yourself first.] [In contrast, though, I am quite willing to go one more step, one more step, one more step, as long as it takes to get to the truth. Alas, "handwaves" are not truth.] and "I just wanted to make it clear that I can justify calling the attack successful cryptanalysis of 4X Fenced DES (provided I can advance it at a few points)." So how did that go again? >I resent your suggestion that I've been blowing my own >horn here. You show me where I claimed to break Fenced >DES, or anything else that wasn't justified. I think the term "successful cryptanalysis" speaks for itself. >I said the >attack was "a strong enough toe-hold for the analyst that >Fenced DES is dead", and I stand by that. Fine. Show us how. Show us how expensive such an attack will be, and *then* we will see whether or not Fenced DES is "dead." If you were just going to *assert* that Fenced DES is "dead," you could have made *that* clear in a single posting. "Assertion" is not the same thing as a successful "attack," however. Oddly, I expected that you would know that. >Your a fool >if you keep using the same design. Tut, tut: That's "you're" not "your." And, "Nya, nya; takes one to know one." --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ ======== Path: news.io.com!news.thenet.net!news.kei.com!news.mathworks.com!nntp.primenet.com!howland.erols.net!cam-news-hub1.bbnplanet.com!cpk-news-hub1.bbnplanet.com!cpk-news-feed1.bbnplanet.com!netnews.jhuapl.edu!usenet From: Bryan Olson Newsgroups: sci.crypt Subject: Re: Fenced DES Attack Questioned Date: Fri, 06 Sep 1996 17:41:21 -0400 Organization: Johns Hopkins Applied Physics Lab Lines: 162 Message-ID: <32309A81.1BE5@jhuapl.edu> References: <50dtca$mss@anarchy.io.com> <322B26F9.57CA@jhuapl.edu> <50gf7b$c8h@anarchy.io.com> <50i9lu$bvu@news.umbc.edu> <50n6r2$ibu@nntp-1.io.com> <322F6035.31A9@jhuapl.edu> <50ommd$k9a@nntp-1.io.com> Reply-To: Bryan_Olson@jhuapl.edu NNTP-Posting-Host: snake.jhuapl.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 3.0 (WinNT; I) No new tech stuff this time. Sadly, I have to defend my academic honesty now. Terry Ritter wrote: > > In <322F6035.31A9@jhuapl.edu> Bryan Olson <Bryan_Olson@jhuapl.edu> > wrote: > > >You've agreed the attack does what I said it does. > > I have agreed that you have made remarkable progress. But back to the point: You agreed it does what I said it would do. When I say it works, I mean it does what I said it would do. If you at first thought it outright broke the cipher, that was your reading of the attack. > > Is an "attack" an "attack" if it does not "break" the cipher, and does You have "break" in quotes there Terry. Who are you quoting? > I never claim any of my work is unbreakable, and I take the > considerable "risk" of completely exposing my designs to public > ridicule so they *can* be attacked. If they are weak, I want to know. I thought you'd want to know about what you just called "remarkable progress". So I posted it the evening I devised it, carefully showing what I thought it did, asking if there are any points which where impossible, warning that some numbers were probably wrong, calling it a "toe hold for the analyst" and _not_ claiming a complete break. > But if I am going to take comments like yours of Sun, 25 Aug 1996 in > message <3220FFAD.27BB@jhuapl.edu>: > > "I'd like to see fewer proposed ciphers with much more careful > analysis." > > "How carefully did you analyze your own cipher before you proposed > it?" > > . . . I am going to expect that when an attack is said to "work," that > it actually *work*, all the way through. Silly me. > That's the post where I wrote: > If the attack doesn't work, I'd like to know why. and you replied: > I'd like some time to think about it, but I think it probably > works, as far as it goes. Did I claim it went farther than it did? Maybe you had concluded the attack showed even more, but when did the definition of "work" change from doing as much as claimed to requiring an "all the way through" solution? > >Clearly > >the attack starts on the initial permutations, and you're > >right if you claim I haven't told how to break them. > >There's a good reason: your Fenced DES posts don't > >specifiy how they're generated. > > This is *more* than false, it is deliberately *deceptive*. > [Various uderspecified candidates deleted.] Apparently the quality of specification has gone way down. > > >Sure you can make the key space > >big enough to beat it [...] > > I don't have to make the keyspace anything: Since the attack is not > complete, you don't know what level of strength Fenced DES provides. Well, if the keyspace of the permutations is small enough to exhaust, then the attack should actually break it. Just test the keys and see if they produce matches where the cipher reveals matches. Admittedly, except for your Penknife cipher your suggested permutation generators have large keyspaces. > > On Mon, 26 Aug 1996 in message <32221635.1686@jhuapl.edu> you wrote: > > "I'd invite anyone who has closely examined Terry's "Fenced DES" > to comment on the attack I proposed in another thread of this > same topic. If I've understood Terry's algorithm correctly, the > attack should work, and I may write up a better exposition for > the research group." > And you've agreed it does what I thought it should do. Is your whole objecting that someone might interpret "work" to mean that I found a complete break? That quote invites people to read the attack and see exactly what it does. > I claim that an "attack" that solves only half the problem certainly > does not "work." And I expect that if someone claims to be able to > "attack" one of my designs that they can "put up or shut up" when > called on their claim. > If I claim it solves half the problem and it solves half the problem, then it works. If I had said that I get credit for breaking Terry Ritter's cipher, as you said I did and I did not, then you would have a case. > Once again, on Sun, 25 Aug 1996 in message <3220FFAD.27BB@jhuapl.edu> > you gave your *own* opinion of inadequate analysis: > [Before I devised the attack, I had told Terry that I though his results were too speculative. He replied "Fine, what would you like to see.] > "I'd like to see fewer proposed ciphers with much more careful > analysis." > > "How carefully did you analyze your own cipher before you proposed > it?" > > Frankly, I think your own words have defined your requirements for a > "successful" cryptanalysis. > > And on Wed, 28 Aug 1996 in message <3224613B.3BEE@jhuapl.edu> you so > kindly quoted the FAQ for my edification: > > "If you don't have enough experience, then most likely any experts who > look at your system will be able to find a flaw. If this happens, > it's your responsibility to consider the flaw and learn from it, > rather than just add one more layer of complication and come back for > another round." > You bet. Finding a flaw is success in cryptanalysis. But even so I qualified any claim of successful cryptanalysis, with "provided I can advance it at a few points". > If you were just going to *assert* that Fenced DES is "dead," you > could have made *that* clear in a single posting. Just assert? Who's going to use a cipher that allows an amateur to make "remarkable progress" in a few evening's time? Why am I the first to make that progress on a two-year-old cipher? I suspect it's because I'm the first to try. The strongest statement I made that my attack works was while encouraging people to examine what the attack works to do. My strongest claim to successful cryptanalysis was qualified, saying the attack still had to be advanced. Don't get me wrong; I think it's a good attack. The simple mixing functions which preserve the locality of changes were definitely a mistake. But contrary to what you said, I have not been posting that I deserve credit for breaking the cipher, and I sure as hell don't deserve to have my academic character assaulted. --Bryan ======== Path: news.io.com!usenet From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Fenced DES Attack Questioned Date: Tue, 03 Sep 1996 20:35:44 GMT Lines: 120 Message-ID: <50i4pe$bsb@nntp-1.io.com> References: <50dtca$mss@anarchy.io.com> <322B26F9.57CA@jhuapl.edu> NNTP-Posting-Host: dialup-01-161.austin.io.com X-Newsreader: Forte Free Agent 1.0.82 [This is my second attempt at posting this.] In <322B26F9.57CA@jhuapl.edu> Bryan Olson <Bryan_Olson@jhuapl.edu> wrote: > A and A' are a match if three of the internal DES >applications receive the same input plaintext A as they do >under plaintext A'. > Here's an example, and >the key question: >Using your mod 2 polynomial block mixer, >given that: > A = 0 0 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 > A' = 0 0 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 > (A,A') is a match, > B = 0 1 0 0 0 0 0 x1 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 x4 > B' = 0 1 0 0 0 0 0 y1 0 0 0 0 0 0 0 y2 0 0 0 0 0 0 0 y3 0 0 0 0 0 0 0 y4 >what is the chance that (B,B') is also a match? >My theory is that (B,B') will always be a match. I *also* think (B,B') is a "match," but the only "match" involved is the same as it was originally. This means that we can create many different "views" of the same match. This means that we can develop an output distribution which is at least potentially different between a "match" and a non-match. And, if the distribution signature is sufficiently distinct, we can detect a "match." This is *how* we find a "match" in the first place, and also the way we find out which mixing group is involved. (It will be necessary to change values in the various mixing sets to show which one controls the match.) Impressive, of course, but just *part* of the way to a break. >> [...] >> OK, since three of the DES operations have not changed, if by >> chance the output of the fourth DES also produces the same >> byte value (a subset of the DES output), then the associated >> output mixing sets will be unchanged, and the associated 4 >> output bytes will also be unchanged. >> >> Since we do not know the particular 256 input codes in a "match" >> set, we might scan A' across 2**32 codes to seek a "match" to A >> as indicated by an unchanging output mixing set. Now, there >> are 2**10 match codes (if we don't care which one DES changes) >> out of the possible 2**32. But even then, we only expect >> perhaps 16 unchanging outputs between the 256 codes in a "match" >> set, for each of 8 output sets. And it does not seem possible >> to separate the 4 different "match" sets that we will run >> across. >> >If my (A,A')match -> (B,B') match conclusion is correct, then >I think I can recognizing all the matches. Suppose we *can* find all 1024 "match" values A' (for some A, and one of the 8 input mixing sets): Even if we detect *every* match, there are four different "match" sets involved, one for each DES. So we have 1024 "match" values, and will apparently have to separate them into the correct 4 sets so we can work on a single DES. It is not clear how one could do this. Then we need to talk about how one could actually resolve the substitution contents for associated table(s), as this would seem to be necessary to attack the DES. If this *is* necessary, we may have to resolve the output substitutions as well. I'd say there several serious problems left to solve before we have a real break. >I don't remember how I got 2^24, but I think it should be >2^32. I'm talking about the output pattern: four bytes which >are the same in the ciphertexts of A and A'. The chance of >getting this pattern without a match should be about one in >2^32 for each of the 8 byte positions. OK. >> >> This confusion between "match" and "unchanged output" certainly >> caused me some problems. >> >Perhaps the first thing I should distinguish is "matching", >which is a property of a pair of 256-bit plaintexts, from >"forcing a match" which a property of a pair of 4-byte >vectors and one of the 8 positions in an 8 byte block. >In my example, A and A' match; (x1,x2,x3,x4) and >(y1,y2,y2,y4) force a match. Actually, using your "match" terminology, a pair of 256-bit plaintexts can: match, not match, not match, match, match, match, not match, and match; one possibility for each mixing set. This is why I have been trying to restrict the discussion to a 32-bit mixing set, which indeed can only match or not. >I haven't pushed the attack from where I left it. If any >of my steps is impossible, I sure want to know. The key >question is whether the concept of "forcing a match" is >vacuous. If (x1,x2,x3,x4) (y1,y2,y3,y4) result in a match >between A and A', but have no such effect on B and B', then >I agree the attack fails. No, I think we can find matches, if we are willing to do, say, 2**40 messages for each mixing set (a total of, say, 2**43). But the attack needs several additional steps -- which might *each* be pretty tricky -- before we have a real break. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/
And that, folks, is the end, as far as I know. The attack is a "complete cryptanalysis" only in somebody's dreams. Fenced DES, as it stands, unchanged, is not penetrated by this "attack," nor is it even particularly weakened by it. The multi-layer structure of the cipher -- as it was originally proposed -- prevents the attack from succeeding. This sort of incomplete cryptanalysis is what we expect with layered designs: a weakness in one level is blocked by the strength of another. Fenced DES is fine for continued use, although we could add three more mixing sub-levels in each mixing and make all this discussion irrelevant.
Last updated: 1998-01-20