Cryptography-Digest Digest #99, Volume #14 Sat, 7 Apr 01 04:13:01 EDT
Contents:
Re: Data dependent arcfour via sbox feedback ("Bryan Olson")
Re: Dynamic Substitution Question (David Formosa (aka ? the Platypus))
Re: Would dictionary-based data compression violate DynSub? (David Formosa (aka ?
the Platypus))
Re: Delta patching of encrypted data ("Bryan Olson")
Re: rc4 without sbox swapping/updating (Terry Ritter)
Re: Would dictionary-based data compression violate DynSub? (Terry Ritter)
Re: Dynamic Substitution Question (Terry Ritter)
----------------------------------------------------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: Data dependent arcfour via sbox feedback
Date: Sat, 07 Apr 2001 06:24:00 GMT
In article <[EMAIL PROTECTED]>, Terry Ritter wrote:
>
>On Wed, 04 Apr 2001 19:53:09 -0700, in
><[EMAIL PROTECTED]>, in sci.crypt Bryan Olson
><[EMAIL PROTECTED]> wrote:
>
>>Bryan Olson wrote:
>>> > Terry Ritter wrote:
>>
>>> > >The "second data source" is modified by said "result data" before use,
>>> > >but no part of the claims excludes that possibility.
>>> >
>>> > The word "source" excludes the possibility. The sequence of
>>> > y values is in fact a _product_ of the substitution process,
>>> > not a source. If unclear of the interpretation of "source",
>>> > just read the background and look at the diagrams in the
>>> > patent.
>>
>>> Any sequence of data values is "a source." We can see this
>>> throughout the patent, including: "A first data source and
>>> a second data source are combined into a complex
>>> intermediate form or result. . . ." Note the lack of
>>> description about the "ultimate" origin of any data sequence
>>> treated as a "source."
>>
>>It may be any sequence of values, but it must be a source,
>>not a product. Neither does the ultimate origin matter;
>>just that it comes in from the outside.
>
>The ultimate origin is of course outside *the* *combiner*, but not
>necessarily outside the system containing the combiner.
The source in question is produced _from_ the table as the
"combiner" updates it.
>When you present a system which is more than just the combiner, I am
>free to select what signals there are and try to match them to a
>claim. You don't get to decide what signals I select. You can add
>whatever you want around an invention in an attempt to obscure which
>parts actually constitute the invention, but the invention is still
>there somewhere, and I get to find it.
Exactly. The sequence _you_ chose depends upon the dynamic
update of the table. It is necessarily a function of the
combiner, and cannot be outside.
>>> But, if you don't like the word "source," perhaps you would
>>> prefer the word "value": [...]
>>
>>Which is not the word in the claim at issue.
>
>It only takes one claim. Any claim counts.
The one you had cited is claim 1. If you want to instead go
through claim 15, note that it's not only a "value" it's an
"input value". Claim 15 also states one output, and if you
use that value for the output, the cipher cannot function.
>>[...]
>>> > doesn't the following
>>> > algorithm fulfill the description from claim 1? How about
>>> > claims 2, 7 and 8?
>>> >
>>> > Assume a (pseudo) random data source S
>>> >
>>> > initialize T[0..k-1] to hold 0..k-1
>>> > for i in 0..k-2
>>> > j = S.next() scaled/shifted to be in i..k-1
>>> > output T[j]
>>> > swap(T[i], T[j])
>>
>>> I'm not happy with any mechanism claimed to be Dynamic
>>> Substitution being inherently limited to a sequence of a
>>> particular length.
>>
>>Didn't you recently write:
>>
>>| The appropriate way to check for infringement is to take
>>| the actual words from a claim and try to fit them to the
>>| design being checked.
>>
>>What you are happy with doesn't enter into it. Why do you
>>not apply the same standard here that you stated previously?
>
>As far as I can see, the standard is the same.
>From "actual words from a claim" to what you are happy with
is a huge change.
>The body of the patent is used as a dictionary to interpret the
>meaning of words used in the claims. I have quoted several times
>where it does not support your interpretations.
You have quoted such zero times. I never said it couldn't
be used to combine confusion sequences, or the various
things you cited.
>>> It is implied throughout the patent body that there is no such
>>> limitation.
>>
>>What text from claim 1 implies that? How about claims 2, 7
>>and 8? Didn't you also write:
>
>It doesn't matter. Any one claim counts. It is only necessary for
>all aspects of any one claim to be satisfied for a design to read on
>the claim.
Agreed. But you have no such claim.
>Dependent claims further restrict the claim upon which they depend.
>In this way, dependent claim 2 thus further restricts independent
>claim 1.
Of course.
> The reason for this is to accommodate newly-found prior art
>which may invalidate the most inclusive (independent) claim. If that
>happens, one or more of the more restrictive (dependent) claims may
>survive. Dependent claims otherwise have little use, other than
>demonstrating various possibilities to the examiner and reader.
I guess I most agree. I think stating the more specific
versions are also important, either in the claims or
elsewhere, so that others cannot patent them.
>That is straightforward patent interpretation.
Agreed. That's why I noted the more specific claims.
>>| When we check for patent infringement, we don't look at the
>>| whole description and then just somehow form an impression
>>| one way or the other. Instead, we try to match the specific
>>| words of each requirement, phrase by phrase, with the design
>>| being checked,
>>
>>If we do that, we see it matches at least as well as the
>>algorithm you argued to match.
>
>I have no idea what that statement means.
I mean we can go through and show that the claim "fits" at
least as closely as the operations from RC4/proposal did.
>If your implication is that shuffling constitutes prior art, it should
>be quite clear that shuffling was not considered to be any sort of
>combiner -- let alone a cryptographic combiner -- prior to my
>publications on Dynamic Substitution.
Exactly. And RC4/modification is also not a combiner, though
it does have one. That combiner is XOR, not dynamic substitution.
[...]
>>> Thus, I expect that the Dynamic Substitution patent
>>> distinguishes from the described mechanism. I think you can
>>> probably use it without patent implications.
>>
>>That wasn't the question; we both know it's clear of patent
>>protection by now.
>
>I guess that depends on what "it" means.
You used "it" in the last sentence I quoted. Same
antecedent.
--Bryan
------------------------------
From: [EMAIL PROTECTED] (David Formosa (aka ? the Platypus))
Subject: Re: Dynamic Substitution Question
Reply-To: [EMAIL PROTECTED]
Date: Sat, 07 Apr 2001 06:32:53 GMT
On Sat, 07 Apr 2001 05:20:34 GMT, Terry Ritter <[EMAIL PROTECTED]> wrote:
[...]
> I will just note again that Dynamic Substitution was examined -- and
> allowed
By an underfunded patent office whos history of making poor desions
with readerd to what is patanable in the computer field is legionary.
--
Please excuse my spelling as I suffer from agraphia. See
http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Free the Memes.
------------------------------
From: [EMAIL PROTECTED] (David Formosa (aka ? the Platypus))
Subject: Re: Would dictionary-based data compression violate DynSub?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 07 Apr 2001 06:24:53 GMT
On Sat, 07 Apr 2001 05:29:20 GMT, Terry Ritter <[EMAIL PROTECTED]> wrote:
>
> On Sat, 07 Apr 2001 04:56:09 GMT, in
><[EMAIL PROTECTED]>, in sci.crypt
> [EMAIL PROTECTED] (David Formosa (aka ? the Platypus)) wrote:
>
>>On Fri, 06 Apr 2001 13:00:07 +0200, Mok-Kong Shen
>><[EMAIL PROTECTED]> wrote:
>>
>>[...]
>>
>>> I don't understand. If a table is updated, then that's
>>> modification. The patent holder said that's his novelty.
>>> So it clearly turns out that there isn't.
>>
>>I haven't been following this indeep but isn't this just Knuth's
>>Algorithm M? (Which looking at it has a strong resemblance to RC4 is
>>this a co-incedence?)
>
> That Knuth reference is cited in the patent itself as prior art. It
> was thus examined specific detail, and the application found to
> distinguish from it.
How is the application diffrent from Algorithm M?
--
Please excuse my spelling as I suffer from agraphia. See
http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Free the Memes.
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: Delta patching of encrypted data
Date: Sat, 07 Apr 2001 06:39:12 GMT
those who know me have no need of my name wrote:
>>Anon wrote:
>>>We wish to take a file and encrypt it. At a later date we wish to take a
>>>new version of the file and encrypt that. We want to minimise the data sent
>>>to enable updates to the new version.
>if you'd consider this method, you might want to encrypt the delta file
>and deploy a patch program that can accept encrypted data and delta
>inputs and output the updated data (already encrypted).
I agree; that's the obvious solution and the more complex
ones look worse.
Compute the diff on the plaintexts, encrypt and send the
diff. Receive the diff in ciphertext, decrypt and apply to
the old file plaintext to get the new version plaintext.
--Bryan
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: rc4 without sbox swapping/updating
Date: Sat, 07 Apr 2001 07:15:36 GMT
On Fri, 6 Apr 2001 22:49:05 -0700, in
<[EMAIL PROTECTED]>, in
sci.crypt Bill Unruh <[EMAIL PROTECTED]> wrote:
>References: <[EMAIL PROTECTED]> <[EMAIL PROTECTED]>
><[EMAIL PROTECTED]> <[EMAIL PROTECTED]>
><9akroa$9b3$[EMAIL PROTECTED]> <9al0ps$d0i$[EMAIL PROTECTED]>
><[EMAIL PROTECTED]>
>
>In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Terry Ritter) writes:
>
>
>]On 6 Apr 2001 18:10:04 GMT, in <9al0ps$d0i$[EMAIL PROTECTED]>,
>]in sci.crypt [EMAIL PROTECTED] (Bill Unruh) wrote:
>
>]>In <9akroa$9b3$[EMAIL PROTECTED]> "Simon Johnson"
><[EMAIL PROTECTED]> writes:
>]>>>
>]>>> "The combiner can also be used to combine two pseudo-random confusion
>]>>> streams into a more-complex confusion stream. In this case, extraction
>]>>> may be unnecessary and so the combiner substitution tables need not be
>]>>> invertible."
>]>
>]>Ie, ONLY in the case where two pseudo-random streams are combined need it
>]>not be invertible.
>
>]But if we take that position, we find it in conflict with the text,
>]where the possibility that a table may be non-invertible is implied.
>]For example, the 2nd par under the section Dynamic Substitution in
>]General:
>
>
>Claims are what defines the patent. The rest of the text is largely
>irrelevant, except in setting the context.
That is simply false. The text sets how terms in the claims are
interpreted; I *think* the well-known quote is, "the specification is
the dictionary for the claims." The reference I have is PTO rule 75,
part (d)(1):
"The claim or claims must conform to the invention as set forth in the
remainder of the specification and the terms and phrases used in the
claims must find clear support or antecedent basis in the description
so that the meaning of the terms in the claims may be ascertainable by
reference to the description . . . ."
>The claim clearly sets
>conditions on when non-invertable tables are claimed.
No, "the claim" sets *no* conditions on the content of the table, and
that is the point. It is also correct. Here is the text for yet
another time:
"
1. A mechanism for combining a first data source and a second data
source into result data, including:
(a) substitution means for translating values from said first
data source into said result data or substitute values, and
(b) change means, at least responsive to some aspect of said
second data source, for permuting or re-arranging a plurality of the
translations or substitute values within said substitution means,
potentially after every substitution operation.
"
Note that the claim does not, as advertised, "clearly set conditions
on when non-invertible tables are claimed." The invertibility or lack
thereof is simply not mentioned. The correct interpretation is that
any table contents whatsoever will read on this claim.
>In the face of a claim, an implication in t he rest carries no weight as
>I understand it.
But the claim has not taken a position; the option is thus open.
>]"If the substitution table is invertible, any particular ciphertext
>]value may be translated back into plaintext with a suitable inverse
>]substitution table. "
>
>]Note the first phrase of the quoted paragraph: "*IF* the substitution
>]table is invertible," (emphasis mine). That shows a recognition that
>]the table need not, and might not, be invertible. Since that option
>]is being left open in the text, and since the independent claims do
>]not specifically require invertibility, that would seem to be enough.
>
>
>No. claims define the patent. And the claims must be explicit, not
>implicit. Otherwise I could claim that my patent for a paper clip
>actully covered the design of a 747 engine since nothing in the claims
>denied that.
That is both true and false. Claims must be written to distinguish
over all known prior art. So if the unknown art includes 747 engines,
and 747 engines fit in with the rest of the claim, then 747 engines
can read on such a claim. (The use of "747 engines" is clearly
hyperbolic, as no such engine would have been built without lots of
prior art and patent activity, so claims would have to avoid all
that.)
The point is that when there is no art, it may be included, no matter
how much there is. In fact, there can be none at the time, so nobody
will have any idea how much there will be eventually. The first
patent for a vacuum tube "valve" probably covers all possible uses for
that valve. The first patent for a laser probably covers all possible
uses of lasers. The first patent for a cryptographic combiner which
changes values in tables probably covers all possible uses for such
combiners.
>]But we have more: If invertibility must be assumed in the independent
>]claim, it would make no sense to have a dependent claim which does no
>]more than require invertibility. Yet that is the case. The claims
>
>Of course it does. Claims often are used to just spell out things that
>the patentor wants to be clear that they are covered.
>There is no harm in making redundant statements in a patent. There is
>harm in not making statements just because the patentor thinks
>they are obvious., but the courts do not.
>
>]themselves thus testify that invertibility is not assumed in the
>]independent claim, but is instead specified where it is required.
>
>I'm sorry, as I understand it, claims must be explicit.
We should be clear that the Dynamic Substitution patent is not a
proposed application; it is an issued formal patent. Claims like
those in the Dynamic Substitution patent do occur all the time, but in
any case, this patent is an example of what real allowed claims look
like. If they do not appear sufficiently "explicit" to you, then,
obviously, claims need *not* be "explicit" in the sense of your
understanding.
>If you want to
>claim something which is obvious or could be argued is already covered
>that is fine. It is often done just to make sure that the claims cover
>everything even things which some might say are already there in other
>claims.
>
>
>
>]>Also it strikes me that Knuth book on random number
>]>genreation already did this in the 70s
>
>]The patent specifically cites prior art from Knuth: "Knuth, The Art of
>]Computer Programming, vol. II, pp. 31-32, (The MacLaren-Marsaglia
>]Randomizer)."
>
>]The patent also cites what you may know as "Algorithm P" in Knuth as
>]Durstenfeld's Shuffle algorithm, since that appears to be the original
>]source: "Algorithm 235, Random Permutation, Procedure Shuffle, R.
>]Durstenfeld, Communications of the ACM, vol. 7, No. 7, Jul. 1964, p.
>]420."
>
>]The examiner specifically considered this art in particular and
>]Dynamic Substitution has been decided to distinguish from it, as well
>]as from other well-known art at the time. And while it is not
>]impossible that some previously-unknown art could surface, the
>]well-known art already has been considered and a decision rendered.
>
>No. The court has the final say.
Of course the court has the final say. So if and when they render an
opinion which changes the decision, at that time the decision will be
different. However, for the present, and absent court action, the
decision has been made. Someone wishing to challenge that decision
generally must expect to provide new information beyond that already
considered by the examiner.
Even though it is *possible* the examiner did not properly interpret
the law and rules of the PTO, that is normally unlikely, and also
especially unlikely given the experienced examiners in this particular
case. Without something new, it is quite unlikely that the outcome
will be any different, whoever follows those same laws and rules.
>That prior art could still be regarded
>as covering the patent and that the examiner made a mistake in saying
>the patent was different.
Mistakes are always possible.
>Also the question is whether the art as being
>practiced by Joe Bloggs is Knuth or contains the additional items which
>are being claimed over and above Knuth.
For one thing, Algorithm M does not take two distinct input sequences
and combine them into an output result. It is not a combiner.
>]>>> The desirability of having non-invertible substitution tables is thus
>]>>> part of the patent text. Absent a specific restriction otherwise in
>]>>> the claim, that is what it may be. Any interpretation otherwise is
>]>>> just silly.
>]>There is a specific restriction-- "In this case"
>
>]That was one example phrase; other testimony exists in the text and in
>]the claims. Seeing that does of course require actually reading and
>]studying the patent, rather than trying to rely upon some detail of a
>]Usenet posting.
>
>True. What then is the other claim which covers it? Text is irrelevant.
No, the text is not irrelevant: The patent specification is the
dictionary to the terms in the claims.
>]>>> There simply can be no question about whether non-permutations were
>]>>> considered acceptable in tables as part of the patent.
>]>
>]>"In this case"
>]>
>]>>>
>]>>> Since table contents are specifically allowed to be non-permutations,
>]>
>]>ONLY in the case where two or more streams are combined.
>
>]But the text and claims do not support that interpretation.
>
>Peerhaps, but the text of the claims quoted state that explicitly.
Whatever claims you are speaking about and which you think you have
seen are certainly not included here or even specifically referenced.
I have above quoted the first independent claim, and it simply does
not say what you say it does, as anyone can see for themselves.
>If
>you state that other claims cover a case of non-invertability where two or more
>streams are
>not combined, then perhaps you could quote them.
The text repeatedly states and implies that tables may be
non-invertible. There is reference after reference. And when there
is trouble interpreting the claims, the text provides the dictionary
for that interpretation. That is how patents work.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Would dictionary-based data compression violate DynSub?
Date: Sat, 07 Apr 2001 07:29:55 GMT
On Sat, 07 Apr 2001 06:24:53 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David Formosa (aka ? the Platypus)) wrote:
>On Sat, 07 Apr 2001 05:29:20 GMT, Terry Ritter <[EMAIL PROTECTED]> wrote:
>>
>> On Sat, 07 Apr 2001 04:56:09 GMT, in
>><[EMAIL PROTECTED]>, in sci.crypt
>> [EMAIL PROTECTED] (David Formosa (aka ? the Platypus)) wrote:
>>
>>>On Fri, 06 Apr 2001 13:00:07 +0200, Mok-Kong Shen
>>><[EMAIL PROTECTED]> wrote:
>>>
>>>[...]
>>>
>>>> I don't understand. If a table is updated, then that's
>>>> modification. The patent holder said that's his novelty.
>>>> So it clearly turns out that there isn't.
>>>
>>>I haven't been following this indeep but isn't this just Knuth's
>>>Algorithm M? (Which looking at it has a strong resemblance to RC4 is
>>>this a co-incedence?)
>>
>> That Knuth reference is cited in the patent itself as prior art. It
>> was thus examined specific detail, and the application found to
>> distinguish from it.
>
>How is the application diffrent from Algorithm M?
Perhaps you should first try to replace the XOR in a stream cipher or
OTP with Algorithm M, and see what the problems might be.
For one thing, combiners combine two data sequences, if that is not
too circular. Algorithm M randomizes one data sequence.
And of course since there are no distinct sequences of data and
confusion in Algorithm M, there is also no thought about how the
process might be undone or the data extracted on the other end.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Dynamic Substitution Question
Date: Sat, 07 Apr 2001 07:30:03 GMT
On Sat, 07 Apr 2001 06:32:53 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David Formosa (aka ? the Platypus)) wrote:
>On Sat, 07 Apr 2001 05:20:34 GMT, Terry Ritter <[EMAIL PROTECTED]> wrote:
>
>[...]
>
>> I will just note again that Dynamic Substitution was examined -- and
>> allowed
>
>By an underfunded patent office whos history of making poor desions
>with readerd to what is patanable in the computer field is legionary.
Well, I suppose you can believe what you want. In this particular
case I don't see that particular problem.
Nevertheless, a decision has been made. Unless and until it is
reversed, it stands.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
