Cryptography-Digest Digest #95, Volume #14 Fri, 6 Apr 01 18:13:00 EDT
Contents:
Re: Dynamic Substitution Question (newbie)
Concerning United States Patent 4979832 (Dynamic Substitution) (John Savard)
Re: Dynamic Substitution Question (John Savard)
Re: Dynamic Substitution Question ("John L. Allen")
Delta patching of encrypted data ("Anon")
Re: "RSA vs. One-time-pad" or "the perfect enryption" (John Savard)
Re: Concerning United States Patent 4979832 (Dynamic Substitution) (John Savard)
Re: rc4 without sbox swapping/updating (Terry Ritter)
Re: rc4 without sbox swapping/updating (Terry Ritter)
[NEWS] Thomas J. Boschloo given for adoption (Boschloo Tales)
Re: rc4 without sbox swapping/updating (Terry Ritter)
----------------------------------------------------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: Dynamic Substitution Question
Date: Fri, 06 Apr 2001 16:19:37 -0300
I did not study the idea of Dynamic Substitution but I think (it's just
a feeling) that DS as you explain it give less randomness to the
ciphertext, even if you use large table.
Every enciphered character = 1 switch and it's easy to rebuild the
table.
That is my first impression. I have to think more at that question.
John Savard wrote:
>
> On Fri, 06 Apr 2001 13:40:42 -0300, newbie <[EMAIL PROTECTED]>
> wrote, in part:
>
> >Please give me just a numeric sample.
> >Because I don't see where is the novelty comparing to Vernam Cipher.
> >Addition is not a table?
> >Xor is not a table?
> >I don't see what is specific.
> >I read the article DS written by Ritter.
>
> The OTP -
>
> Plaintext: 43190247
> Keystream: 17098162
> Ciphertext: 50188309
>
> Dynamic Substitution:
>
> Initial state of table:
> 0123456789
> ----------
> 5290713468
>
> Plaintext: 4 3 1 9 0 2 4 7
> Keystream: 1 7 0 9 8 1 6
> Table: 0|5 5 5>7 7>6 6 6
> 1|2>7 7>5 5 5>9 9
> 2|9 9 9 9 9 9>5 5
> 3|0 0>4 4 4 4 4 4
> 4|7>2 2 2 2 2 2>3
> 5|1 1 1 1 1 1 1 1
> 6|3 3 3 3 3 3 3>2
> 7|4 4>0 0 0 0 0 0
> 8|6 6 6 6 6>7 7 7
> 9|8 8 8 8>8 8 8 8
> Ciphertext: 7 0 7 8 7 9 2 0
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Concerning United States Patent 4979832 (Dynamic Substitution)
Date: Fri, 06 Apr 2001 20:19:58 GMT
I was startled to see Terry Ritter claiming a broader interpretation
of his Dynamic Substitution patent than I had imagined had applied.
However, I see even from the abstract of the patent that it does refer
to more than I had associated with the term "Dynamic Substitution":
As I quote from that patent: "Each data value from the first data
source is transformed by substitution using one of potentially
multiple translation tables. The translations within each table can be
changed after each substitution operation using a changes controller.
Commonly, the just-used table is re-arranged or permuted; permutation
retains invertibility, so that the ciphertext may be deciphered. As a
particular design, the just-used substitution element may be exchanged
with some element within the same table, as selected by the second
data source, after every translation."
Thus, the specific design I associated with the term "Dynamic
Substitution" is indicated as simply a *particular design*.
Using the table as the source of keystream bits instead of as the
source of ciphertext is specifically indicated as a possibility.
Changing elements in the table in other ways than by permuting them is
also noted.
Note that an account by Donald Knuth of the MacLaren-Marsaglia random
number generator was noted as a reference in this patent. Since it
works in the manner outlined: an element, after it is used, is
replaced with a new element, in the buffer table, which provides
'substitutes' in a sense for the values generated by the secondary
PRNG, it is directly applicable as prior art. The "Phillips" cipher,
noted in Gaines, also works by rearranging table entries after five
letters are enciphered.
Would the key feedback mode of DES be covered by the Dynamic
Substitution patent?
Not necessarily.
A rotor machine works by combining rotor displacements with plaintext
to produce ciphertext. The rotor displacements, combined with the
rotor wirings, produce a substitution table applied to the plaintext
which changes with each letter.
However, the rotor wirings are still fixed. The rotor displacement is
subtracted from the letter, then the letter is substituted by means of
the rotor, then the rotor displacement is added to the letter.
DES essentially combines the key with the plaintext block in a similar
fashion. Key material is XORed with data from the block; the result is
then used to find an entry in a fixed table, and the result is then
XORed with another part of the block to modify it.
Thus, with both DES and a rotor machine, a substitution is formed that
changes, but this substitution is built from fixed tables and fixed
combination operations such as addition and XOR. Neither the contents
of the tables, nor the definitions of the operations, change over
time.
Dynamic Substitution operates by taking a table, and modifying that
table directly by an operation on its entries. Replacing an individual
entry, adding or XORing a quantity with an entry, or exchanging that
entry with another entry are possibilities. This allows any possible
arrangement of the table to be reached, and therefore has an effect
different from merely producing an effective table from a fixed table
and an operation with a varying quantity such as XOR or addition.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Dynamic Substitution Question
Date: Fri, 06 Apr 2001 20:26:49 GMT
On Fri, 06 Apr 2001 16:01:59 -0300, newbie <[EMAIL PROTECTED]>
wrote, in part:
>Thank you for your useful and clear answer.
>But replacing a keysteam (OTP) by "complicated" combination of two keys
>( keystream and dynamic table) does not give more randomness.
>If you prouve that it is the case, I will agree with you on a novelty of
>DS.
>If not, it's only reinventing the wheel.
Well, if one uses Dynamic Substitution only with a truly random
keystream, as in the OTP, that would be the case.
However, if the keystream is generated by a PRNG, then using the
dynamic table instead of simply adding the PRNG output values to the
plaintext does make the resulting cipher harder to break, because the
PRNG values are now less visible in the ciphertext.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "John L. Allen" <[EMAIL PROTECTED]>
Subject: Re: Dynamic Substitution Question
Date: Fri, 6 Apr 2001 20:15:41 GMT
John Savard wrote:
> On Fri, 6 Apr 2001 16:11:19 GMT, "John L. Allen"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Don't forget to include all the income you made from Dynamic Substitution
> >patent infringement lawsuit victories.
>
> >:-)
>
> That was unkind.
Honest-to-god that's a smiley there. It was meant only in good-natured jest.
I guess I shouldn't quit my day job to become either a comedian _or_ a
cryptologist.
John.
------------------------------
From: "Anon" <[EMAIL PROTECTED]>
Subject: Delta patching of encrypted data
Date: Fri, 6 Apr 2001 21:52:25 -0000
Hi all,
I hope someone can point me at something for this.
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 the file is not encrypted, we can use a delta patcher program, which
picks up insertions, deletions, and alterations to the file and works out a
script. The script and the original file can then be used to generate a
copy of the new file.
With normal encryption this doesn't work. If we use a stream cipher, all
data from the first change onwards is altered. If we use a block cipher
with no feedback any insertion or deletion which is not a multiple of the
block changes all the file from there onwards.
I'm thinking in terms of a self-synchronising cipher based on the previous
plaintext, rather than the previous ciphertext. Obviously this will be
weaker - if for example there is a large sequence of repeated characters the
ciphertext will settle down to a consistent value - however:
Is there a standard solution to this problem?
If not, how weak is the solution I describe?
Thanks
(I'm a commercial software protector - so I'd rather keep my ID slightly
secret from all the crackers out there, hence the missing name)
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Fri, 06 Apr 2001 20:30:51 GMT
On Fri, 02 Mar 2001 14:09:13 GMT, William Hugh Murray
<[EMAIL PROTECTED]> wrote, in part:
>The Diffie-Hellman work changed history and
>Ellis, Cocks, and Williamson will be no more than a footnote.
True, but a footnote that will be remembered with honor none the less.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Concerning United States Patent 4979832 (Dynamic Substitution)
Date: Fri, 06 Apr 2001 20:33:29 GMT
On Fri, 06 Apr 2001 20:19:58 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>Thus, the specific design I associated with the term "Dynamic
>Substitution" is indicated as simply a *particular design*.
It may also be noted that the first claim in the patent notes that the
table is used to find a substitute for a first value, and the change
to the table - of an unspecified type - depends on a second value -
and _possibly_ also on the first value, but not necessarily.
Thus, the claims also support the broader interpretation of the
patent.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: rc4 without sbox swapping/updating
Date: Fri, 06 Apr 2001 21:56:27 GMT
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:
"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.
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
themselves thus testify that invertibility is not assumed in the
independent claim, but is instead specified where it is required.
>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.
>>> 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.
>>> 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.
---
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: rc4 without sbox swapping/updating
Date: Fri, 06 Apr 2001 21:57:22 GMT
On Fri, 6 Apr 2001 17:48:50 +0100, in
<9akroa$9b3$[EMAIL PROTECTED]>, in sci.crypt "Simon Johnson"
<[EMAIL PROTECTED]> wrote:
>[...]
>Hrm, what a mess... Why didn't u define your ideas in maths?
Patents are what they are. I did not invent them. I am not
responsible for things being complicated. This is the real language
of real patents.
>The problem
>here is that only one person understands this patent and that's you....
I doubt that, but certainly nobody else is talking, and that's a
problem. I'm not going to be able to get across about two semesters
of study in a few messages. But, normally, when we encounter people
who do not have background, it is sufficient to say: "Go get some
background." Here, we have people who are simply ignorant in the
field, nevertheless being happy to state that an issued patent is
faulty and imply that it can simply be ignored. That kind of advice
can get people in trouble.
>now
>you say that Ken is making "pronouncements" about patent law.... Well I ask
>you this question:
>
>If patent laws were designed by people to serve for the people, then if
>no-one except a select few can understand them, then are they serving the
>people or themselves?
Really? Do you also expect to be able to defend yourself in court?
Somehow I doubt that mathematics alone would be very helpful. I don't
expect they would put things in mathematical language for you.
Specialized learning is required. A specialized language prevails.
Misunderstanding the process just makes things awkward for everybody.
>If Ken can't understand what he can or can't use in his modifications to RC4
>by just reading your document then it is waste of time.
That is no more true than the idea of having a modest paper in
mathematics, which, frankly, almost nobody can understand "just by
reading." Background is required.
>Its clear, no matter how long we argue about this, no-one really has a clear
>idea what your patent is means and a large fraction of us probably don't
>care wether they infringe on a patent or not...
>
>Luckly, this madness doesn't apply to me... =)
In which case, one wonders why you don't just skip it all. Nobody
makes you read this stuff.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Subject: [NEWS] Thomas J. Boschloo given for adoption
Crossposted-To: alt.privacy.anon-server,alt.security-pgp
From: Boschloo Tales <[EMAIL PROTECTED]>
Date: Fri, 06 Apr 2001 21:59:38 GMT
NOTICE: This message may not have been sent by the Sender Name
above. Always use cryptographic digital signatures to verify
the identity of the sender of any usenet post or e-mail.
His biological parents decided to give up "Thomas J. Boschloo" for adoption.
"We can't cope with his stupidity any more" Dad said.
"We are just humans, you got to be a saint to handle such offspring"
Agency adoption denied having been paid by the family to arrange foster family.
Thomas J. Boschloo is presently in a kernel, waiting for a new life
===============================================
HISTORY:
That Boschloo bozo is a clown and a troll who has been looming around for nearly a
year.
Don't mistake a "regular" (troll) with a knowledgeable person: that self-proclaimed
"security expert" is not even a remailer user. In the past, he proved himself unable
to check a PGP signature, and got ridicule from every single technical topic he wanted
to talk about.
Besides false or inaccurate or misleading technical misinformation, his posts are
about his avowed mental illness, or for bashing remops or real freedom fighters: he
likes to quarrel with every one, and stir shit. Sometimes, it is even pure delirium
(when he misses his pills?)
One of his last actions was to stage a hoax about his own suicide, just to try to grab
some sympathy, after he had been exposed as a troll and technically incompetent.
The worst being his teasing of Script-Kiddie until it triggered a new flood on apas.
Of course, he refuses to apologize.
Actually, the level of contempt he shows for remailer users:
they don't give their names, while he does
that can't do anything against him, without giving their names
is in no way different from what is displayed by Pangborn, Burnore and the like
Ignore him completely, killfile him, respect others' killfiles
KILLFILE:
To put him in your killfile, put "Author: Boschloo"
That will make disappear both him and people who warn about him
If you want to tell him to buzz off, or warn about him,
use a nickname containing "Boschloo" (Boschloo Hater, Boschloo Sucks,...)
to accomodate such killfile for "regulars", and still warn newbies
COURAGE:
Boschloo is getting _no_ answer from apas any more.
He has to crosspost to various newsgroups to try to grab some attention.
In a few months, it will be gone.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: rc4 without sbox swapping/updating
Date: Fri, 06 Apr 2001 22:00:47 GMT
On Fri, 06 Apr 2001 13:00:41 +0200, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>[...]
>Mmm, you are changing your positions? We all know that
>a capable lawyer can often tweak things. Otherwise some
>of them wouldn't be able to make big money. The novelty
>of your patent has been claimed by you many times to lie
>in 'modification' of a 'table'. If that weren't it, then,
>as I said before, you seemed not to know yourself what your
>patent actually IS.
Yes, I am absolutely capable of changing my positions. I try to be
consistent, but if I am inconsistent, then I am. I don't see anybody
else trying to teach even the rudiments of understanding a patent, so
almost half the words moving around here are mine. That means less
time to consider, less time to remember, and always trying to present
things in a way that newbies might understand. There will be
mistakes. There will be omissions.
If you would actually go to the trouble of reviewing some of the first
posts on this topic -- not necessarily to you -- you will see me
saying *repeatedly* that this is ultimately a *legal* issue, not
(just) a technical one. Surely nobody here labors under the delusion
that I am a patent lawyer.
Because I am the inventor, I necessarily see the patent in the context
of the invention in my mind, and as a generalization of that
invention. But the resulting patent is not that, but is instead words
interpreted in a context of law, rules, previous court decisions and
special cases, a background which I only have in part. I am like the
one-eyed man in the kingdom of the blind: I can give the newbie
introduction around the place, but for anything real, you need to see
a patent lawyer. And at least one lawyer seems to be wrong in every
case.
In my personal view, I see Dynamic Substitution as starting with a
table, and having the contents of the table re-arranged. Obviously,
dynamic tables can also be polyalphabetic; that is, we can have a
whole array of them, each changing within itself. But that doesn't
mean that the patent reads on polyalphabetic tables, unless the
contents of the tables change.
Normally I think of the table changing only as permutation, because
that makes more sense in almost every case, but it is a good thing I
considered the alternative, if that prevents some way of practicing
the invention which would not otherwise read on the patent. The whole
point here is for the patent to support a limited-term monopoly for to
protect what the invention really is, a monopoly which cannot be
engineered around. Other combiners are available; if one wants to
obtain the advantage of the invention without taking a license, there
will be some risk, which is as it should be.
>[...]
>If something serves the same or approximately the same
>purpose as a 'table' but is different in nature (as I have
>tried to show with an example in a previous follow-up)
>does that constitute a violation of the patent or not?
I would like to think that the concept of a table of values is
sufficiently general that if something acts like a table, it would be
seen as a table. What we are talking about here is nothing less than
an attempt to avoid the patent monopoly. I hope the patent and the
supporting law would be sufficient to prevent that, but all this is
out of my hands.
>Could you explain? A horse coach acts the same as an
>automobile in transporting persons and goods from one
>place to the other, though with lower speed. Does a
>coach violates the patent of a car because of that? If
>anything, on the contrary, that would be prior art for
>annulating the car patent.
You have an uninformed idea of what "prior art" means, and I somehow
doubt that you will be investing the time necessary to do your own
research and form a more correct understanding. You seem happy enough
to accept my limited knowledge when that agrees with you, and
otherwise you simply ignore it. Well, fine, but don't expect to have
a conversation under such circumstances.
The patent has been strongly examined in the context of the art at
that time. That does not mean that some previously-unknown
publication could not exist. It does mean that Dynamic Substitution
has been found to distinguish beyond the specific prior art mentioned
in the patent, and other well-known things of the time.
>[...]
>This is evading discussions when one's arguments no
>longer get hold of firm ground.
That seems to be a rather tough standard, and one to which you
certainly cannot be held. The actual argument is nothing less than
the full text of the patent, the law, rules, and cases. Every time I
try to present something understandable for newbies (and myself!), it
turns out that I ignore part of what even I should know. I'm sorry if
you find that disconcerting, but the discussions are demanding
something from me which I do not have.
A patent is not a mathematical equation. There is no one solution.
As one edges closer and closer to the claim, there is more and more
risk that the claim will read on the design. The fundamental problem
is the idea that it should somehow be OK to exploit the concept of the
patent without having to license that patent. That is not OK.
>We have seen enough
>of such in disputes in all fields.
I presume you will soon be unveiling a formula to prevent such
disputes. I will wait with bated breath.
---
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
******************************
