Cryptography-Digest Digest #98, Volume #14 Sat, 7 Apr 01 02:13:01 EDT
Contents:
Block/stream terminology (was Re: Data dependent arcfour...) (David Hopwood)
Re: RC4 test vectors after gigabyte output?. (David Eppstein)
[LOST AND FOUND] Brain cell belonging to Thomas J. Boschloo (Boschloo Tales)
Re: Would dictionary-based data compression violate DynSub? (David Formosa (aka ?
the Platypus))
Re: Dynamic Substitution Question (Terry Ritter)
Re: Would dictionary-based data compression violate DynSub? (Terry Ritter)
Re: patent issue ("Douglas A. Gwyn")
Re: rc4 without sbox swapping/updating (Bill Unruh)
----------------------------------------------------------------------------
Date: Sat, 07 Apr 2001 04:07:23 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Block/stream terminology (was Re: Data dependent arcfour...)
=====BEGIN PGP SIGNED MESSAGE=====
Gregory G Rose wrote:
> In article <MdDx6.1$TH3.79@interramp>,
> Bryan Olson <"nospam"@"nonsuch.org"> wrote:
> >How about CBC-mode Rijndael? Rijndael is of course a block
> >cipher, but CBC-mode Rijndael is a stream cipher. I'll let
>
> I think you meant CFB (Ciphertext Feedback Mode)
> or OFB (Output Feedback Mode). CBC (Cipher Block
> Chaining) is nothing like a stream cipher.
Considering CBC to be a stream cipher is a perfectly reasonable and
self-consistent use of terminology: it encrypts a plaintext stream.
If you exclude this from being a stream cipher, then to be consistent
you would also have to exclude RC4, ISAAC, SEAL, WAKE, etc., since
they operate on elements larger than 1 bit (also CFB and OFB modes
when the feedback length is > 1 bit).
Personally, I prefer to use just 'cipher' for stream ciphers and
modes, and 'block permutation' for what is usually called a "block
cipher" - since a "block cipher" cannot *directly* be used as a
cipher (= encryption scheme). I.e. a mode constructs a cipher from
a block permutation. But this is only a difference in terminology;
I agree with the categories that Bryan Olson appears to be using.
Note that this terminology has the advantage of defining 'cipher'
to include a large category of useful symmetric encryption schemes
that are not clearly either block ciphers or stream ciphers according
to the conventional terminology.
> CFB is plaintext-aware, OFB is not.
CFB is not plaintext-aware.
(AFAIK plaintext awareness has only been formally defined for public
key encryption schemes in the random oracle model, but I can't see
any extension to symmetric schemes that would be satisified by CFB;
certainly CFB is not non-malleable, which should be implied by any
sensible formalisation of plaintext awareness for symmetric ciphers.)
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOs5vXDkCAxeYt5gVAQHLkgf/b9+gBwh+Cd/akHKGvEArDmt5e4ciw5jb
PbW77/YyfW5Tc89HivW/qhxT/J62Fb3aRt/i5Au4N5v9a5uuXWu3Wj4zAGr1eFKl
ZSXNYpSmWGygoNWgZTqB56VHacZ4/i3aNTBwucK5W7mlPdLFagj0LkLAO+GmBkOL
KflGQVQEYn0mM9hByt8AKUZBB7kbeF/sHwHjhB5IWchx3B/To7i0ue9kfhjnis7b
I+GypRMg/gFngdanVvAhiWlDEibv+Bt603TfU5Kwup86q6lp7b8wfVAXDLC88Usa
vnF/EROp4Lcx56HEw7/bJDb/6LmfjODb0Ktjbfb0xehpjmHxNyb0uw==
=yIlo
=====END PGP SIGNATURE=====
------------------------------
From: David Eppstein <[EMAIL PROTECTED]>
Subject: Re: RC4 test vectors after gigabyte output?.
Date: Fri, 06 Apr 2001 21:21:41 -0700
In article <[EMAIL PROTECTED]>,
David Hopwood <[EMAIL PROTECTED]> wrote:
> - From the RC4 entry in SCAN
> (http://www.users.zetnet.co.uk/hopwood/crypto/scan/):
You appear to be missing
M. Robshaw. Security of RC4. Technical Report TR-401, RSA Data Security,
Inc., July 1994.
unless you are deliberately omitting non-publically-available stuff -- I
haven't seen this paper, but it was cited by Robshaw's RSA TR 701,
http://citeseer.nj.nec.com/25566.html, which you might also include, and by
another paper available at http://citeseer.nj.nec.com/zenel98proxy.html)
You might also update your AES section to reflect the fact that an
algorithm has been selected.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
------------------------------
Date: 7 Apr 2001 04:42:10 -0000
From: [EMAIL PROTECTED] (Boschloo Tales)
Subject: [LOST AND FOUND] Brain cell belonging to Thomas J. Boschloo
Crossposted-To: alt.privacy.anon-server,alt.security-pgp
Did somebody find Thomas J. Boschloo's brain cell?
It has been reported missing since
... well ...
a few years ?
birth ?
===============================================
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] (David Formosa (aka ? the Platypus))
Subject: Re: Would dictionary-based data compression violate DynSub?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 07 Apr 2001 04:56:09 GMT
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?)
--
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] (Terry Ritter)
Subject: Re: Dynamic Substitution Question
Date: Sat, 07 Apr 2001 05:20:34 GMT
On Sat, 07 Apr 2001 02:25:14 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt Benjamin Goldberg
<[EMAIL PROTECTED]> wrote:
>Benjamin Goldberg wrote:
>>
>> Leaving the internals of any functions and structures unspecified
>> (except for their names), is the following an accurate model of Dyn
>> Sub?
>>
>> opaque table;
>>
>> datum dynsub( datum d1, datum d2 ) {
>> datum output = substitute( d1, table );
>> table = permute( table, d1, d2 );
>> return output;
>> }
>>
>> We'll ignore *how* substitute works internally, and *how* permute
>> works internally, so long as permute does indeed use both values to
>> change table.
>>
>> Is this a valid representation of dynamic substitution, or isn't it?
>
>Terry Ritter responded that this is a valid example of d.s., but d.s.
>covers much more than this example.
>
>Let's suppose that type "datum" is not an 8 bit value, but a 64 bit
>value, and that "table" isn't a simple table, but the key for a block
>cipher. Does anyone disagree that block ciphers are substitutions?
>
>Does anyone disagree with the idea that a block cipher key represents
>one [very large] substitution (if the block cipher is known/fixed)?
>
>We can further state that ANY change in "table" (the cipher key) will
>result a different substitution, and that the new substitution will be a
>permutation of the one which "table" represented. Well, unless the
>cipher has some equivilant keys, but we'll ignore that.
>
>Lastly, let's suppose that "permute" is a secure hash function. After
>all, it will with high probability produce a new value for "table", and
>that new "table" value will be a permutation of the old one, so it isn't
>invalid to call our hash function "permute."
>
>Let's rewrite this, shall we?
>
>int64 dynsub( int64 d1, int64 d2 ) {
> int64 output = E_table( d1 );
> table = H( table, d1, d2 );
> return output;
>}
>
>Gee, looks like a variant on a cipher in key feedback mode, doesn't it?
Well, gee, what would be your point?
1. Do you imagine that because something *looks* the same it must
*be* the same? Obviously, that logic is somewhat flawed. But it
might happen that a court would determine that Dynamic Substitution is
limited to the substitution means described in the patent, but is
otherwise valid in every way. Yett that would not seem to change
much, since nobody is particularly upset about not being able to use
DES as a cryptographic combiner, and I doubt I would be upset if
someone did. Accordingly, I don't know how such a case would reach
the courts, or how it would be to anyone's advantage to win that
decision.
2. Or, do you imagine that if one could build a cryptographic
combiner out of DES, that no such combiner could be covered by the
Dynamic Substitution patent? That logic is also flawed: A new use
for an old thing is valid patentable material. It may be that a court
would find the idea of a cryptographic combiner based on a changing
substitutions to be novel (in the context of the art as of the date of
invention), *even* *if* those substitutions were block ciphers, which
of course were very well-known art at the time. But, again, since
using DES as a cryptographic combiner is not what people want to do, I
don't know why such a case would reach the courts.
3. Or, do you imagine that "key feedback mode" is "the same" as
Dynamic Substitution? That sounds like a "mode of operation" to me,
and modes of operation were well-known art at the time. But a mode of
operation is a way to use an existing cipher, and generally depends
upon having a strong cipher as a basis: a substitution table is not a
strong cipher. Nor would such a thing be a valid practical
realization of a cryptographic combiner, because it would be far too
expensive to use. It would thus not correspond to the simple logic
device of the Dynamic Substitution patent. One might well question
whether using a full block cipher as a combiner would even be
practical enough to patent on its own. But even if it was, the
advantage of having a combiner which could use small tables instead of
block ciphers would be obvious and probably would distinguish beyond
any impractical approach.
4. Or, do you imagine that DES itself actually has been used as a
cryptographic combiner and thus -- because it acts like a substitution
table even if it is not a substitution table -- would thus be prior
art to the Dynamic Substitution patent? Well, one thing we might
discuss is how a substitution table that was actually a block cipher
would fit into the extractor concept, and, if it did not, how one
could imagine that a block cipher could be "the same" as the
substitution the patent uses in that position.
But even before that argument can be properly formed, we need to have
a real example of published, dated, art of DES being used as a
cryptographic combiner. Again, that is unlikely to correspond to the
simple logic device of the Dynamic Substitution patent, and when one
thing is practical, and another thing impractical, they can scarcely
be called "the same." Then we get to discuss whether that supposed
prior art does in fact represent any part of the invention in the
granted patent, and if so, how much.
All that is not going to be a trivial case to make. Even though the
literature includes a sequence of increasingly complex combiners, I am
aware of no instance where DES was actually used in this manner or
even proposed for such use. And, since the combiners in the
literature are generally non-invertible, the idea that one can even
*have* an invertible and also nonlinear combiner is fairly unique.
But the idea of changing table contents so that weakness is not
accumulated over time reaches beyond simply "unique" to "novel."
Consequently, it seems rather doubtful that the entire patent would
ever be thrown out. And if not, it seems likely to cover everything
that it needs to cover.
I will just note again that Dynamic Substitution was examined -- and
allowed -- in an environment where the Feistel patents were probably
the best-known examples of prior art, and modes of operation were also
well-known. The Dynamic Substitution invention has been found to
distinguish over that Art, and the Claims in the Dynamic Substitution
patent were allowed in that context. There may well be detailed legal
reasoning (which I did not need to know, so the fact that I do not
know it should come as no surprise), which would more clearly and
strongly support those decisions.
However, until a case is actually presented to a court and a decision
reached, the Dynamic Substitution patent remains as it was when
approved. Any statements that the patent is for some reason invalid
are extremely premature, and may be potentially damaging or even
actionable. Until there is an actual court decision otherwise, the
patent says what it says and can be enforced on that basis. Indeed,
its reach actually may extend much farther than I, as inventor and
patent holder, previously expected.
That tiger has been trying to sleep, but there is always some idiot
who wants to poke it with a sharp stick and see what will happen.
---
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 05:29:20 GMT
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.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: patent issue
Date: Sat, 07 Apr 2001 05:39:26 GMT
Tom St Denis wrote:
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote ...
> > Tom St Denis wrote:
> > > Patents are just a way to hold someone liable for being creative.
> > No, they're an incentive for inventors to publish their work
> > instead of keeping it secret while they (possibly) exploit it.
> Ahh, but if money wasn't an issue why hold it secret?
? Did I mention money? And anyway, what do you have against
someone *earning* his keep by inventing useful stuf?
------------------------------
From: Bill Unruh <[EMAIL PROTECTED]>
Subject: Re: rc4 without sbox swapping/updating
Date: Fri, 6 Apr 2001 22:49:05 -0700
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. The claim clearly sets
conditions on when non-invertable tables are claimed.
In the face of a claim, an implication in t he rest carries no weight as
I understand it.
]"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.
]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. 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. That prior art could still be regarded
as covering the patent and that the examiner made a mistake in saying
the patent was different. 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.
]>>> 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.
]>>> 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. 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.
------------------------------
** 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
******************************
