Cryptography-Digest Digest #151, Volume #14 Sun, 15 Apr 01 14:13:01 EDT
Contents:
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: There Is No Unbreakable Crypto (John Savard)
Re: Concerning US.A.4979832 (John Savard)
Re: Remark on multiplication mod 2^n (Chris Monico)
Re: There Is No Unbreakable Crypto (Mok-Kong Shen)
Password tool! ("Logan Raarup")
Re: Dynamic Substitution Question ("B. E. Busby")
Re: Function other than xor? (newbie)
Re: Password tool! (Mok-Kong Shen)
Re: AES poll ("Roger Schlafly")
Re: AES poll ("Tom St Denis")
Re: Concerning US.A.4979832 ("B. E. Busby")
Re: Password tool! ("Logan Raarup")
Re: please comment (Ichinin)
Re: LFSR Security (David Wagner)
Re: There Is No Unbreakable Crypto (David Wagner)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sun, 15 Apr 2001 17:26:38 +0200
Tom St Denis wrote:
>
> "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> >
> >
> > Tom St Denis wrote:
> > >
> >
> > > Ok you can't even tell when someone is being sarcastic....
> > >
> > > *PLUM*
> >
> > We have discussed in another thread about desirability
> > of being serious in posts to this group. Not everyone has
> > the IQ needed to detect different forms of sacarcism
> > or other similar stuffs and foreigners of English
> > may have more difficulties in that. Others may not have
> > the time to do so. To avoid misunderstandings etc. it
> > is highly desirable in my view to keep to the proper
> > discussions. Please kindly re-read my follow-up in the
> > thread 'I got accepted' of sci.crypt of Fri, 13 Apr 2001
> > 10:56:40 +0200.
>
> I don't have that message any more but I appreciate the "serious"ness
> desired. But it has to work both ways (well multi-ways when you consider we
> are not the only users...). If I (or anyone else) posts a serious question
> they deserve a serious reply, not some quable over penis sizes.... seriously
> that's all this thread is good for sometimes...
In that case I am sending you a copy via mail. To the
above point, which is covered there, I like to repeat
that no post, however well written or well deserving,
has a 'right' of getting answers. Analogy: One may
be a very competent man in a certain profession yet
fails to get an employment (there may be a huge number
of different reasons).
If everybody tries a bit, as far as possible/convenient,
to maintain a good atmosphere, then with time the chance
of your getting answers that you hope for will naturally
enhance, for there will be more good people joining the
group. Letting that atmosphere to deteriorate, in that
the group acquire the 'appearance' of being not serious,
is certainly not contributive to your goal.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: There Is No Unbreakable Crypto
Date: Sun, 15 Apr 2001 15:44:37 GMT
On Sun, 15 Apr 2001 09:30:02 +0200, Frank Gerlach <[EMAIL PROTECTED]>
wrote, in part:
>Although this doesn't sound scary, I would just suggest than every
>non-OTP crypto will be easily (w/o exhaustive keyspace search) broken at some
>point in the future. Might take 100 years for DES or maybe just 10 years (or
>maybe somebody has already solved it :-)), but that depends mainly on the
>number of good cryptanalysts multiplied by the time they are working on it.
I don't agree. However, I am not confident that the point at which
this becomes untrue _necessarily_ includes such ciphers as the AES
candidates. But because it's essentially trivial to go far beyond them
- if one is willing to waste the time, and isn't using public-key
methods to exchange keys, which *would* make it a total waste of time,
because they are unavoidably limited in security - a categorical
'anything can be broken' is, I belive, wrong too.
Super-duper-strong crypto is possible, even if the 'conventional
wisdom' is almost always right in saying there is no point to it.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Concerning US.A.4979832
Date: Sun, 15 Apr 2001 15:56:05 GMT
On Sun, 15 Apr 2001 04:11:26 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
in part:
>Algorithm M does not read on the claims and so is not covered by the
>patent. When Algorithm M grows another input (or more) and is used to
>combine streams, it has mutated beyond being Algorithm M into
>something else which is Dynamic Substitution territory.
My understanding of "Algorithm M", or MacLaren-Marsaglia, is that as
it stands, it _does_ combine two streams.
Specifically, it functions as follows:
Stream 1 is the output of one conventional PRNG.
Stream 2 is the output of a second conventional PRNG.
A table is filled with N outputs of stream 1.
Then, output PRNG values are generated as follows:
A value is taken from Stream 2. This value is used to indicate a
position in the table. The value in the table in that position is used
as the output value, and it is replaced by a new value from Stream 1.
Thus, if the output values are viewed as 'substitutes' for the values
from stream 2, this _is_ Dynamic Substitution. But it doesn't indicate
or embody the general idea, because (of one among many reasons) the
information content of stream 2 is truncated - there are only N
elements in the table, but the PRNG outputs are allowed to have many
more than N possible values.
So although Stream 1 and Stream 2 are combined, the combination looks
more like an interruption of Stream 1 than a substitution acting on
Stream 2, and is more often thought of in that manner. Only after you
invented Dynamic Substitution did it become visible that Algorithm M
was an example of that general class, which is why I view its impact
as limited.
>But I think the patent would cover attempts to circumvent the claims
>by introducing transformations which act like as a table but which are
>said to not *be* a table. That is the sense in which I would reach
>beyond a table per se.
I have no problems with that.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Chris Monico)
Subject: Re: Remark on multiplication mod 2^n
Date: Sun, 15 Apr 2001 15:56:42 GMT
On Sun, 15 Apr 2001 15:12:02 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
>
>Mok-Kong Shen wrote:
>>
>> Tom St Denis wrote:
>> >
>> [snip]
>> > Unless you use a field (instead of a ring) multiplication is a not a good
>> > diffusion primitive at all. Preferably if you use GF(2^W) with a secret
>> > multiplicand... :-)
Ah, but it depends on the ring! Certainly the ring Z/(2^nZ) is bad,
but what about, say Z_2[x]/<f>, where f(x) is not irreducible mod 2.
Or, Mat_{n\times n}(F)?
Or worse yet,
F[x_1,...,x_k]/I, where 'I' is a zero-dimensional non-prime ideal? (Of
course, I'm cheating since this one can actually be embedded in a ring
of matrices, but you get the point).
I know I'm taking your comment out of context and you were referring
to the particular ring Z/(2^nZ), but I just thought that I'd put it
out there.
Cheers,
Chris
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: There Is No Unbreakable Crypto
Date: Sun, 15 Apr 2001 18:17:47 +0200
John Savard wrote:
>
> Frank Gerlach <[EMAIL PROTECTED]> wrote:
>
> >Although this doesn't sound scary, I would just suggest than every
> >non-OTP crypto will be easily (w/o exhaustive keyspace search) broken at some
> >point in the future. Might take 100 years for DES or maybe just 10 years (or
> >maybe somebody has already solved it :-)), but that depends mainly on the
> >number of good cryptanalysts multiplied by the time they are working on it.
>
> I don't agree. However, I am not confident that the point at which
> this becomes untrue _necessarily_ includes such ciphers as the AES
> candidates. But because it's essentially trivial to go far beyond them
> - if one is willing to waste the time, and isn't using public-key
> methods to exchange keys, which *would* make it a total waste of time,
> because they are unavoidably limited in security - a categorical
> 'anything can be broken' is, I belive, wrong too.
>
> Super-duper-strong crypto is possible, even if the 'conventional
> wisdom' is almost always right in saying there is no point to it.
I think that it is also useful to keep in mind that, while
theoretical issues can be extremely valuable/illuminating,
all what the users need is 'practical' security to protect
his privacy for a limited finite time. Barely anyone is
planning on the scale of centuries. The constraints posed
by reality can be very hard and one has in life to be
satisfied with compromises/trade-offs. No surgical threatres
are (and can be) absolutely free from potential dangerous
microorganisms. No airplane is built entirely free of
possible technical problems. Even if the engineers could
have done that and money were not an issue, there may be
other unexpected factors that could cause a crash, e.g. a
collision as we learned recently in newspapers.
M. K. Shen
------------------------------
From: "Logan Raarup" <[EMAIL PROTECTED]>
Subject: Password tool!
Date: Sun, 15 Apr 2001 18:23:38 +0200
Hello!
I need a password tool for my AIX server. It should do following:
The program should have 2 arguments:
programname [username] [new password]
1) Open /etc/security/passwd . The content of the file would maybe look like
this (In the structure. Theres at least 15 users in the actual file):
username1:
password = [encrypted password]
lastupdate = 623078865
flags = ADMCHG
username2:
password = [encrypted password]
lastupdate = 623078865
flags = ADMCHG
2) Encrypt the new password entered. I've got the following code, for the
encryption:
#include <stdio.h>
int main(int argc, char* argv[])
{
printf ("%s\n",crypt(argv[1], argv[2]));
}
3) Write the new encrypted password to /etc/security/passwd instead of the
old, at the user name entered. Like this:
username1:
password = [new encrypted password]
lastupdate = 623078865
flags = ADMCHG
I really hope someone can help me make this tool!
Thanks in advance!
/logan
------------------------------
From: "B. E. Busby" <[EMAIL PROTECTED]>
Subject: Re: Dynamic Substitution Question
Date: Sun, 15 Apr 2001 09:26:40 -0700
"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> On Fri, 13 Apr 2001 08:22:55 -0700, in
> <RREB6.2$[EMAIL PROTECTED]>, in sci.crypt "B. E. Busby"
> <[EMAIL PROTECTED]> wrote:
> >
> >Statutory rejection requires written publication.
>
> I think the statement is arguable.
>
> I know that "written publication" is interpreted liberally, because I
> have had a *verbal* academic presentation -- in an overseas venue --
> upheld by a PTO crypto-group examiner against my application, even
> though the printed proceedings did not appear until over a year later.
> Maybe I could have fought that, but I expect they know far better than
> I what is likely to prevail in court.
That's why the response had a copy of 35 USC �102 attached.
The vaguer version runs like this (based on various case law):
"If the publication is in writing (there's been decisions on both sides
as to whether web sites can be construed as 'written') and indexed
so that the material can be searched for and subsequently studied
(I think this cam from whether a written master's thesis was considered
a 'publication' if it was never sent to the University's library) it is
considered
a 'written' publication."
That said, I know I'd hate to spend the $$$ to argue that this venue
constitutes publication, google nee deja notwithstanding.
As to proceedings, there's good precendence for this and, as I recall,
it actually comes down to the date on which the publication of a talk
is first put in print and delivered to the hands of someone other than
the proceedings organizer. Note that this included pre-pub copies
that often float around technical symposia.
>
> Newsgroup publication definitely *is* "written," and one might argue
> that anything causing letters to be displayed is "printed." Newsgroup
> publication is open to the public, worldwide, and available in
> libraries. The only legal problem I see is that the publication date
> in an article may not be reliable in a legal sense.
>
> But for dates, archives may exist, and responses to the original
> publication also have dates and authors who can testify when they
> responded. So the original article logically must have occurred prior
> to that time. In this way, the publication date at least potentially
> can be bounded in a legal sense, and established in court.
>
> I actually have submitted articles from sci.crypt as prior art in
> crypto patent application which was allowed. And sooner or later some
> anticipating prior art will be found from a newsgroup archive and used
> in court.
Publication is one form of prior art. Citation from the Net more
importantly
may represent public use evidence... another part of 102(b).
>
> ---
> Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
>
>
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: Function other than xor?
Date: Sun, 15 Apr 2001 12:22:07 -0300
No. This function does not meet my specification. I'm looking for
function with a lot of properties.
Additive, multiplicative, distributive etc...other than modulo,
permutation or inverse.
New, simple and logical function.
Thank you for your answer.
"Douglas A. Gwyn" wrote:
>
> newbie wrote:
> > Has someone created this kind of function?
>
> I'm not sure what you're really after. f(any_bit_string) =
> Rotate_right_1_place(any_bit_string) seems to meet your
> specification. but what good does that do you?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Password tool!
Date: Sun, 15 Apr 2001 18:40:57 +0200
Logan Raarup wrote:
>
> I need a password tool for my AIX server. It should do following:
The operating system normally provides aging mechanism
of passwords. It is not apparent why you want to mess
with the system, which could be problematical. (I guess
you want to study the behaviour of users in updating their
passwords.)
M. K. Shen
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: AES poll
Date: Sun, 15 Apr 2001 16:36:14 GMT
"Lars Ramkilde Knudsen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Cast your vote on
> http://www.ii.uib.no/~larsr/
I vote that you polling software is already broken. (Eg, the popup doesn't
come to the top with my MSIE 5.5, and it refuses votes if cookies are
turned off.)
Meanwhile, why don't you also ask if DES is broken? You'll get different
answers for that.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: AES poll
Date: Sun, 15 Apr 2001 16:52:21 GMT
"Roger Schlafly" <[EMAIL PROTECTED]> wrote in message
news:26kC6.846$[EMAIL PROTECTED]...
> "Lars Ramkilde Knudsen" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Cast your vote on
> > http://www.ii.uib.no/~larsr/
>
> I vote that you polling software is already broken. (Eg, the popup doesn't
> come to the top with my MSIE 5.5, and it refuses votes if cookies are
> turned off.)
>
> Meanwhile, why don't you also ask if DES is broken? You'll get different
> answers for that.
Why would he post that? Trying to convince people to not trust a cipher
chosen as AES for no reason is not generally a good idea.
Tom
------------------------------
From: "B. E. Busby" <[EMAIL PROTECTED]>
Subject: Re: Concerning US.A.4979832
Date: Sun, 15 Apr 2001 10:10:44 -0700
"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> On Mon, 9 Apr 2001 22:54:07 -0700, in
> <CexA6.196$[EMAIL PROTECTED]>, in sci.crypt "B. E. Busby"
> <[EMAIL PROTECTED]> wrote:
>
> >Two things come to mind reading the claims --
> >
> >1) They're in "means plus function" format which has the
> > (at least in current practice) effect of narrowing the claims
> > to the means taught in the disclosure; and
>
> There certainly is some hubub. Anyone can look into it by searching
> for "means plus function" at www.google.com
>
> One of the most recent examples is:
>
> http://www.kilstock.com/site/print/detail?Article_Id=590
<text of above ref clipped for bandwidth>
> In the case of the Dynamic Substitution patent, I view "substitution
> means" as a description of the complete structure needed to perform
> the substitution function: the substitution table as described in the
> specification. The original intent was to cover tables specifically
> implemented in ways to try to get around a limitation of "tables."
Unfortunately, decisions with phrases like "sufficiently" are not good,
dispositive things -- it means you're going to have to sell a judge
at the Markman hearing.
>
>
> >2) There's no prosecution history here (an expensive thing to
> > buy unless you're seriously considering licensing the patent),
> > but the recent Festo decision has had the claims-narrowing
> > effect of precluding the use of the Doctrine of Equivalents
> > in reading claims that were amended to overcome issues
> > of patentability.
>
> I don't know enough to even respond to that.
What it means is, if you know how the patent went through the
examination process _and_ if the claims were amended _for
the purpose of patentability_ (i.e., not to remove informalities),
the Festo precedent says DOE cannot be used (theory being
that most amendments for the purpose of patentability involve
a narrowing of the claims and the application of the DOE would
unfairly re-broaden the claim).
>
> I suppose the result possibly might bear on the idea of creating a
> "table" out of a mass of apparently-distinct equations. But I
> continue to believe that if something acts like a table it will be
> seen as a table in the PTO and in the courts. Protecting against that
> sort of thing is, of course, why we have the phrase "substitution
> means" in the first place.
>
>
> >That said, my guess is the scope covers lookup tables wherein
> >entry swapping is performed in order to dynamically change the
> >mapping function.
>
> That would seem to be all it needs to be. It would disallow the use
> of whole block ciphers as "substitution means," but that is not
> something I wanted anyway.
>
> On the other hand, perhaps you could comment on the main areas of
> controversy:
>
> * whether the claims cover combining two RNG streams,
If the nature of the combine is a simple operation (e.g., XOR),
claim 1 (that's all I recall -- this _was_ a cursory examination)
would not seem to apply.
>
> * whether an "input" to Dynamic Substitution can be taken from the
> dynamic substitution table itself,
To the degree that an output of the process is used, subsequently,
as an input simply adds elements and would change nothing
concerning the patentability or scope of the claims. If, in a conservative
interpretation invoking �112�6, you stick to:
"combiner substitution 12 translates combiner substitution input 10
data into combiner output 14 data. The result would be a simple
substition, except that the substitution 12 will change. A substitution
or inverse substitution would typically be implement [sic] as addressable
storage,
and realized with an electronic memory device, or an addressable area of
memory hardware in an electronic digital computer or microprocessor. "
... I don't know how else to interpret your query.
>
> * whether the claims assume the table to be invertible, and
"Still another object of this invention is to provide an efficient
inverse mechanism or process by which previously-combined
data can be separated or extracted, suing [sic] the confusion
data involving in the original combination. Since deciphering is
normally required, an efficient mechanism can make the whole
system practical."
coupled with:
"A substitution or inverse substitution would typically be implement as
addressable storage..."... to me this (again assuming invoking �112�6)
says, "yes" to the instant query.
>
> * whether "Algorithm M" (ironically, prior art actually described in
> the patent itself and examined prior to allowance) limits the claims.
If I understood the thread, your claims were distinguished over
Algo-M. This is not a limitation. Again, I've not seen the
prosecution history -- you, as the inventor, have relevant
data here that I don't have.
It doesm however, imply that using Algo-M as described in the
literature cannot infringe your patent.
>
>
>
> >This ain't advice, but it's worth every penny you paid for it!
The above line applies to this bumph as well.
>
> Yup, same here.
>
>
> >"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
> ><snippage...>
> >>
> >> As I recall, in the USPTO there is a later patent line which includes
> >> the words "dynamic substitution," but those words describe a clearly
> >> different mechanism.
> >>
> >> And even if later US patents have further developed my form of Dynamic
> >> Substitution, manufacturers and users will need a license from me to
> >> practice such an invention.
> >>
> >> Since I am not aware of any other "dynamic substitution" patent in the
> >> original sense, or of any other patents which bear on this invention,
> >> perhaps you could reference what you do mean.
>
> Note the unusual situation of an odd lack of disagreement with the
> quoted statements.
>
> Again, I am aware of no prior art which anticipates the invention.
>
> ---
> Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
>
------------------------------
From: "Logan Raarup" <[EMAIL PROTECTED]>
Subject: Re: Password tool!
Date: Sun, 15 Apr 2001 20:01:52 +0200
Yes, there is a password changer in AIX. But that tool works like this:
$ passwd
Enter user's password:
Enter user's password again:
Enter user's new password:
And I wan't to make a web based application, which can change users
passwords. But this web based application can't enter any text in these
inputs!
Thats why i need a program, which can do this but with som arguments
instead.
I hop you can help me with this.
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Logan Raarup wrote:
> >
> > I need a password tool for my AIX server. It should do following:
>
> The operating system normally provides aging mechanism
> of passwords. It is not apparent why you want to mess
> with the system, which could be problematical. (I guess
> you want to study the behaviour of users in updating their
> passwords.)
>
> M. K. Shen
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: please comment
Date: Sun, 15 Apr 2001 20:00:16 +0200
Tom St Denis wrote:
> My post was to suggest that it's insecure and not worthy of consideration.
> Sure, if you want to purchase a license for a stupid product after people
> warn you otherwise.... go ahead.
Geez... You cannot judge a program by it's copy protection system(!)
Anyhow, i think one have nothing to worry about, considering people who
crack + distribute applications would never caugh up the money anyway
for a license, you'd be amased on how many private people use, for
example, Autodesk's products for home use (i.e. learning the program and
playing around with it.) noone of those would buy Autodesk 3d because
it's too expensive for a private persons.
Regards,
Ichinin
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: 15 Apr 2001 18:04:58 GMT
Trevor L. Jackson, III wrote:
>David Wagner wrote:
>> I haven't see any evidence either way
>> (short of "well, I can't see how to do it" -- which isn't very convincing).
>
>There is more to it that that. Consider the collections of unknowns: the taps,
>the gap positions, the gap values, and the initial state.
As I suggested before, the gap positions seem likely to be known in all
scenarios that matter. So, your argument doesn't apply.
My question is: Given known keystream at some known but irregular
positions, is there a general algorithm to find the taps and initial fill?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: There Is No Unbreakable Crypto
Date: 15 Apr 2001 18:08:30 GMT
Mok-Kong Shen wrote:
>Very dumb question: It seems that your argument hinges
>on the block size being larger (double) than the key.
No, it doesn't: It is very general. If E(k,x) is a block cipher with
128-bit key and 128-bit block, then set F(k) = <E(k,0), E(k,1)> and note
that this is a length-doubling PRG. Moreover, F is secure if E is secure
against all attacks that use at most two blocks of chosen plaintext.
This same idea can be extended to work for any key and block sizes.
------------------------------
** 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
******************************
