Cryptography-Digest Digest #77, Volume #14 Wed, 4 Apr 01 15:13:00 EDT
Contents:
Re: quick LFSR question (really simple question) (Mike Rosing)
Re: Data dependent arcfour via sbox feedback (Terry Ritter)
----------------------------------------------------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: quick LFSR question (really simple question)
Date: Wed, 04 Apr 2001 13:06:46 -0500
Tom St Denis wrote:
> Well the program I found asks the size in bits, I entered 12....
>
> I think you ignore the 0 and move everything down one so it becomes
>
> tmp[x - 11] ^ tmp[x - 9] ... etc
That is pretty confusing. The basic idea is to xor each bit (but you're storing
each bit as a byte?) and create the new zeroth bit, then slide everything over.
You're posted code didn't have a slide for one thing. You just need a primitive
polynomial of the order you want (in this case 13 or 12 - I'm confused) which
will give you 2^n-1 total steps. If the polynomial isn't primitive you won't
get the full cycle, just the order of the polynomial.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Data dependent arcfour via sbox feedback
Date: Wed, 04 Apr 2001 19:08:54 GMT
On Wed, 04 Apr 2001 13:14:20 +0200, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>> >
>> >My worry stems on the one hand from your claims of general
>> >coverage in previous posts and on the other hand from
>> >a diagram on you web page, which in my view seems to cover a
>> >quite general feedback scheme.
>>
>> Which diagram, on what page?
>
>Right at the section on 'Dynamic Substitution' there is on
>the left a diagram. The box labelled 'Changes Controller'
>has an input from above. I understand that that input is
>a quantity that results from the current processing state
>(otherwise why 'dynamic' in the name of the scheme?).
You should know very well why "dynamic" is in the name of the scheme,
since I have explained that specifically several times. "Dynamic"
means "changing," not "feedback." The heart of Dynamic Substitution
is a substitution table whose contents change.
>Hence that's feedback control in the ordinary sense.
It is certainly *not* "feedback" in any sense I use. When I hear the
term "feedback" I expect some result of computation to feed back into
the computation itself and modify the computation. To me, "feedback"
means a "circular" path or "loop," where the output goes back the
input which produces an output and so on. In a digital system I
suppose the computation might be delayed, but for "feedback," the
output has to go back to the input.
>> >That's why I wanted to know
>> >explicitly whether using feedback as such is or is not
>> >violating your patent. Incidentally, feedback is a mechanism
>> >that has interested me for some time. (A couple of my humble
>> >crypto designs employ feedback.)
>>
>> Well, feedback has long been a very basic part of hardware circuit
>> design (analog, or "linear" design). Most Op Amp (operational
>> amplifier) circuits use extensive negative feedback, often to make the
>> gain effectively independent of the active device, and to reduce
>> distortion. Most oscillator circuits use some form of positive
>> feedback to replace any loss in the frequency-selective section.
>> There is also a concept of "feedforward," often used to cancel
>> distortion without using feedback. Feedback is fairly old (70
>> years?), very common stuff, and very often treated in the technical
>> literature.
>>
>> With respect to cryptographic feedback, autokey stream ciphers are
>> also quite old. The PK-Zip cipher (from a decade ago?) is a modern
>> example. I don't think we can draw a useful feedback analogy to
>> Dynamic Substitution per se, although the inverse process (the
>> extractor) might be more like it. There is no intent in the Dynamic
>> Substitution patent to control feedback per se.
>>
>> I cannot even imagine trying to get a general patent on feedback now,
>> because it is a widely-understood part of technology; there is massive
>> prior art. But even now, there might be particular ways to control or
>> use feedback which might be patentable.
>
>I can't exclude misunderstanding. But the 'dynamics'
>in your scheme must in my view necessarily be derived
>from the current (ongoing) processing state and hence goes
>hand in hand with feedback. Otherwise the word 'dynamic'
>in the name would be misleading.
Wrong, specifically addressed above, and also several times in
previous messages.
>> >Oh yes, it could certainly impose its laws onto foreign
>> >countries and do the said 'prosecutions' through the help of
>> >its mighty military forces. The day of the scenario you
>> >described may in fact be nigh. Who knows the future for sure?
>>
>> I did not say "impose its law," I said "prosecute . . . in foreign
>> countries"; that would be in their PTO, or the EPO. One problem for
>> the US is that when inventors choose to only patent in the US, only US
>> industry is controlled by the patent, which then may not be able to
>> compete worldwide. It is hard to compete with companies who do not
>> have to pay for the research which resulted in the product.
>
>Patents apply only to the countries where these have
>been submitted and granted and paid for (fees for the
>patent offices). There is no free lunch. If you think
>that protecting your invention in another country is
>worthwhile from a business point of view, then it is
>wise to spend some money to get a patent in that country.
>It might be a good idea to have a single patent office
>for the entire world. I am not sure. But that's totally
>unrealistic before the United Nations succeed to unite
>the nations in the real sense of the word.
For years now, there has been a "point of view" which recommended
changing US patent law to "conform" to mainly Japanese law, but also
European law, and the name given to these changes was "world-wide
convergence," as in joining into a common body of law. Many of these
proposed changes would weaken US patent law considerably, reduce the
advantages of patenting, and increase the risks. Nevertheless it is
still discussed. I think we could reasonably expect similar
discussion on the other side.
The problem is not the manufacturers who get the patent, but instead
the other manufacturers in the US who then appropriately pay for the
research they are using, versus manufacturers in other countries, who
reap the rewards from patent publication, but do not pay for that
research, and so can undercut US prices. That could largely be
avoided if the US government took each US application and prosecuted
it in each foreign country. I don't seriously expect that to happen,
of course, but the problem remains. Once consequence may be the
growth of overseas manufacturing for our domestic companies, who thus
hope to avoid domestic patents.
>> >On the other hand, in another post you seemed to claim that
>> >generation of a very large table statically for later use
>> >(through choice of columns analogoug to selection with key
>> >in polyalphabetic substitution) would be considered as in
>> >conflict with your patent, even though there is no dynamic
>> >creation of table. This point is non-trivial as far as the
>> >coverage goes and it is important to have a clarification of
>> >that.
>>
>> There have been many points in the past few days. The best match for
>> this that I recall was that if someone wanted to get around the
>> Dynamic Substitution patent by saying they did not have "a
>> substitution table" and then produced some sort of logic structure --
>> one element at a time -- which in effect *was* a table, we should
>> expect that to infringe as well. It is not that easy to get around a
>> patent.
>>
>> I don't understand your point about "generation of a very large static
>> table," since the Dynamic Substitution issue is not about size
>> (although it must be small enough to be realized). The whole point of
>> Dynamic Substitution is to re-arrange the contents of the table. That
>> is not done in polyalphabetic substitution, which I believe I gave as
>> prior art in the patent itself. In general, if the contents of the
>> tahle are not re-arranged, it is not Dynamic Substitution.
>
>What I meant is sort of this stuff: I construct a
>polyalphabetic substitution table with a very large number
>of columns (each being a permutation). I can address the
>columns with a numerical key which is a function of the
>output of a PRNG and some value obtained in the current
>state of processing (e.g. the sum of the last plaintext
>and ciphertext character being processed). Now, what I
>understand as dynamic would be constructing at the very
>moment of use (i.e. in the middle of encryption processing)
>one or more new columns for substitution based on some
>value obtained in the current state of processing.
OK, maybe that's the problem. You are not understanding the word
"dynamic": "Dynamic" only means "changing," and does not imply either
instantaneous change or feedback change; it is just change.
>The
>table I just described is static.
In which case it is not Dynamic Substitution. End of story.
>It is not that
>flexible/universal (hence perhaps performing less well
>from crypto point of view) as the dynamic one, but comes
>very near to it for the intended purposes, because fairly
>randomly picking one substitution column from a huge number
>of the statically determined ones provides almost the same
>'randomness' (benefit) as creating a substitution column
>dynamically (on the fly). Now allow me the explicit
>question: Does such use of huge static substitution tables
>violate your patent, where tables are dynamically generated/modified (if
>I don't err) and, if yes, why?
No. So now what you will want is "if no, why?"
Well, I could include an actual claim again (which would include the
answer you want), or talk about the phrase which causes this, but the
bottom line is that if the contents of the table are not changing, you
don't have Dynamic Substitution.
>> >I don't have problems with the purposes of the patent laws,
>> >nor with copyright. I think that they both have merits in
>> >principle. Inventors should be rewarded. What worries me is
>> >the 'practice' of having very general claims in the patent
>> >documents, which, even if these are actually largely
>> >restricted by (eventually present) other clauses of the same
>> >documents, may cause undesirable confusions to other
>> >practioners or potential inventors, mistakingly thinking
>> >that all what they intend to do falls already in the domain
>> >of these general claims. That I think would be very bad.
>>
>> The only solution I can offer is the same one you have been
>> essentially calling unfair, and that is to learn about patents,
>> claims, and patent law. What other solution could there possibly be?
>>
>> Not everybody learns in school every skill they need in real life. I
>> think technical people should know how to read a patent, and how to
>> interpret claims, and thus exhibit less of a tizzy when they are
>> confronted with such a monster. If someone considers patents
>> important enough to potentially disturb their work, they may need
>> patent skills just to do their work.
>
>Even skilled people can err. Otherwise why do we have
>patent lawyers and patent courts at all?
Of course. Often it is not so much an error, as it is a legal
possibility that might go either way, or perhaps a deliberate strategy
of delay and impede. But many cases do not get to the courts.
>What I was saying
>is that patent documents should be clear-cut, exactly
>restricted (as tightly as possible) in coverage to the
>ideas that are really novel. These should never be 'coated'
>in such general terms that they at least seem (even if not
>intended so) to cover things that they shouldn't cover.
What patents "shouldn't cover" is called prior art. We can't
abstractly say what patents should or should not cover otherwise.
>Let
>me give a 'hypothetical' analogy. Let's turn the clock back
>and imagine that there are yet no automobiles. Someone
>invents a car, driven by an engine. Clearly he deserves
>very well a patent. That patent document should neatly
>describe the invention as such, namely a vehicle with
>wheels and so on and with a certain kind of engine and
>other relevant technical details. But the patent shouldn't
>lay any general claims about vehicles that serve to
>transport persons and goods. For such a general formulation
>could be interpreted to cover not only automobiles but also
>coaches, boats, ships, airplanes and (in future) rockets.
But if the "car" was rocket-powered, one might very well have claimed
any form of transport using rocket power, using the car as realistic
example. It would not take much innovation from someone to take the
idea of a rocket-powered car and make a rocket-powered boat; they get
the details of how to really do rocket power for free, thus not paying
for the research they use. Avoiding that is why we have patents. Of
course the more appropriate name for such a patent might have been:
"Rocket Powered Transportation" instead of "Automobile."
>If you look at the claim in your patent about combining
>two streams to produce a more complex stream, I suppose
>you'll understand what I mean here.
Not at all. You have consistently misunderstood what the Dynamic
Substitution patent covers, and so have consistently misrepresented
the implications. I have said over and over again that you either
need the background to understand this, or you have to trust someone
with that background, and you have been unwilling to do either. The
result is just raw paranoia, and has little to do with reality.
The Dynamic Substitution patent is appropriately restricted by the
prior art as it existed at the time.
Dynamic Substitution is a cryptographic component, not a cipher. It
can be used in various situations and in various ways, just as a
transistor is used in electronic circuits. A patent on the transistor
would apply to each particular device, not where or how it is used.
And if "everything" needs a transistor, then "everything" will need a
license, or will need already-licensed transistors. There was an
alternative and that alternative was to use tubes or "valves." I note
that there was in fact a patent on transistors. This is what happens
at the beginning of new technology.
When we put a transistor in a radio, we might call the result "a
transistor radio," and if we use Dynamic Substitution in a cipher, we
might call it "a Dynamic Substitution cipher." That name does not
mean the whole cipher is covered by a patent, only that it uses the
technology with that name.
>> >I am not sure whether the term nonlinear combiner couldn't be
>> >'interpreted' to encompass e.g. modular multiplication of two
>> >entities, use of F-functions of DES, rotation of one entity
>> >with modular addition of another, and use of a nonlinear PRNG
>> >to process a bit stream. These are however in my view all prior
>> >art.
>>
>> All of which is fine with me. Dynamic Substition is the *name* of the
>> patent; it does *not* imply that anything which is "dynamic" and which
>> includes some form of "substitution" is covered.
>>
>> Dynamic Substitution is just shorthand for the claims. You seem to
>> find this misleading for some reason, but the precise alternative
>> would be to call it by the full claim description, and avoiding that
>> horror is the reason we have names.
>
>It is the 'generality' of the individual claims (of not
>only your patent but also of plenty others) that actually
>worries me. But certainly the title of you patent provides
>some amount of relevant context. I think that it correctly
>conveys the idea that the substitution is not predetermined
>(fixed) but is dependent on the 'runtime'. Could you
>also say something about the topic of nonlinear combiner?
>My view is that, if you come up with a specific new type
>of combiner that is entirely distinct from what one knows
>in literature and you can show that it has specific
>crypto-beneficial properties, then you deserve very well
>a patent. But such a patent should not lay claims on
>combiners that are nonlinear 'in general', for others
>have invented some such before you and will invent
>some after you that are distinct from your specific
>combiner yet these are ALL nonlinear in nature. Have I
>explained my point sufficiently understandably?
Well, you have explained, but as far as I can see, it has nothing to
do with Dynamic Substitution. The Dynamic Substitution patent does
not attempt to cover every possible nonlinear combiner. You would
already know that, of course, if you understood that the claims define
and limit what the patent covers.
>> >If something is completely new, it could hardly be 'general',
>> >but, in contrary, singular/special/particular.
>>
>> That sounds odd to me. It is the new work which has little prior art,
>> which thus imposes few limitations on a new patent.
>
>My point is that a 'completely new' mechanism (or whatever)
>has by definition little in common with existing ones.
>Consequently it could not properly (and should not) be
>formulated in such (general) terms that the existing
>(commonly known) entities are also covered. See also above.
Well, your point is just wrong. The limitations on a scope of a
patent are, very properly, the prior art. Any sufficient advance in
that art is what the inventor trades for patent protection, and the
larger that advance is, the better off everybody is. When someone can
take the information in a patent, and with little or no additional
innovation produce something not covered by the patent, the patent has
been written incorrectly.
>> >I don't have any personal plans to earn money in any field.
>> >There is hence no personal 'problem' for me at all. Others
>> >have raised though the point that the good intended purposes
>> >of patent laws would be undermined, if the practice of granting
>> >patents is improper, allowing persons to get patents without
>> >actual novelty or with much more coverage than the underlying
>> >ideas deserve. I guess that many people in this group have
>> >a common (and unfavourable) opinion about e.g. Hitachi's
>> >rotation patents.
>>
>> I have long thought you were making far too much of the Hitachi
>> claims. Haven't there been several messages on sci.crypt, each with a
>> pretty good technical analysis, which told you that this was not the
>> problem you claimed? Did you not read those? Did you forget them?
>> How many times must you be told before you will accept reality? From
>> what dark recesses does this strange fear continue to re-emerge and
>> infest all the newbies with this baseless dark foreboding?
>
>Sorry. I didn't notice any good technical analysis of
>the Hitachi patent in the group. All I learned is the
>fact that the rotation does not use an amount of rotation
>that is static (fixed) but dynamic (variable). What
>essentially more did you read out from the posts?
I thought the analysis was clear that it was not an issue, so I moved
on. Maybe those posts will come back.
---
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
******************************
