========
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