Cryptography-Digest Digest #855, Volume #11 Wed, 24 May 00 22:13:00 EDT
Contents:
Re: Crypto patentability (Mok-Kong Shen)
Re: Modulu arithmetic additive stripping? (Mok-Kong Shen)
Re: Encryption within newsgroup postings (Paul Rubin)
Re: Crypto patentability ("Paul Pires")
Re: Chosen Plaintext Attack (David A. Wagner)
Re: Yet another block cipher: Storin (David A. Wagner)
Re: OAP-L3 for T Huuskonen (Anthony Stephen Szopa)
Re: safer style sboxes (zapzing)
Re: Smooth numbers (Scott Contini)
Re: how do you know your decyption worked? (David A. Wagner)
Re: bamburismus (David A. Wagner)
Re: safer style sboxes (tomstd)
Re: Patent state of Elliptic Curve PK systems? (Scott Contini)
Re: Yet another block cipher: Storin (tomstd)
Re: safer style sboxes (zapzing)
Re: Encryption within newsgroup postings (stanislav shalunov)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Date: Thu, 25 May 2000 02:08:11 +0200
Lyalc wrote:
> A couple of thoughts.
> 1. Can anyone define where crypto starts and stops? An awful lot of fields
> of mathematics come into the field of crypto, so the lines are very blurred.
I suppose you have asked a very hard question. Maybe many patent
problems stem from this very issue.
> 2. An idea can't be patented. A patent describes an implementation of an
> idea. e.g. Rotations are an obvious idea - but a specific use of them can
> be patented.
Are you saying that, for example, rotation by 5 bits is patentable but
rotation by n bits, with n dynamically determined, is not patentable?
Or do you mean that rotation CAN be one element in a specific sequence
of operations that is a patentable?
> 3. Just be cause a technique or process is patented does not mean that
> another patent cannot include that technique in another process. It does
> mean that the 2 patent holders must agree (or not) to share their rights to
> use their respective IP in some manner - an issue outside the realm of the
> patent office. This is simply business, and allows companies to define what
> is 'theirs'.
I don't know for sure but I suppose that the second patent must in any
case explicitly mention the first patent and acknowledge the inclusion.
> 4. Not all patent owners are rich, or held by big companies.
I was told that some patent holders were even ruined because of their
patents. But what was your point?
> In an information based enconomy, money is made on ownership of information.
> If information has no value, then why pay to ship it around, why pay to
> receive it or to create it in the first place?
How do you predict which information has what value? A patent can
have value only after it has been granted.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Modulu arithmetic additive stripping?
Date: Thu, 25 May 2000 02:12:34 +0200
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > Is 'non-carrying addition or subtraction' a synonym for 'xor'? What
> > do the terms 'stripping' and 'additives' mean? Could you provide
> > some examples or analogies? Thanks.
>
> Those are all standard terms from classical (WWII era) cryptanalysis
> and are explained in MilCryp, for example.
In the part you snipped I acknowledged my poor knowledge. Would
you please help to explain the terminologies? (Unfortunately I don't
have the literature you mentioned.)
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Encryption within newsgroup postings
Date: 25 May 2000 00:02:08 GMT
In article <392a8e7a$[EMAIL PROTECTED]>,
Dave Jones <[EMAIL PROTECTED]> wrote:
>Dear All,
>
>I have found a variety of newsgroup postings which have part of the text
>encrypted. There are no numbers or special characters used, it looks
>something like the following:
>
>yytjk y pltra........etc
>
>Has anyone come across this, and if so, can you please explain the
>encryption/decryption process used.
You might be talking about the Hipcrime posts, which were garbage posted
by a malicious spammer attempt to screw up a number of newsgroups.
The content was gibberish designed to defeat spam filters by avoiding
repeatedly posting the same content (i.e. it was different gibberish
every time), and it took a number of forms as the "contest" with
filter implementers escalated. A sorry episode in Usenet history.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Date: Wed, 24 May 2000 17:38:08 -0700
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
<snip>
> I suppose you have wrongly interpreted what I wrote in my original
> post, i.e. read out something between the lines that actually doesn't
> exist.
>
> M. K. Shen
I don't know, I thought I was doing alright. I believe I understand you and
I don't intend to trivialize your position. We are just coming from really
different perspectives and I don't think were going to get close enough to
bond any time soon. Debating world politics from two different planets.
Thank you for the lively discussion. I'll just be getting back to the wall
now.
Paul
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Chosen Plaintext Attack
Date: 24 May 2000 17:53:36 -0700
Mark Wooding wrote:
> David A. Wagner <[EMAIL PROTECTED]> wrote:
> > This is the point where it is probably best to refer you to Biham and
> > Shamir's book, Differential Cryptanalysis of the Data Encryption
> > Standard, which gives all the gory details.
>
> This is now out of print (at least, according to Amazon it is). Where
> could I get a copy from?
Ahh, that's unfortunate. Well, you can still get a good technical
introduction from a few of Eli Biham's online papers. I recommend
the following as a nice starting point:
http://www.cs.technion.ac.il/~biham/Reports/Weizmann/cs90-16.ps.gz
If you got through that one and are still dying for more, here's
a more advanced paper that describes some important techniques:
http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0708.ps
I'm sure there must be other "survey"-style introductions to
differential cryptanalysis on the net, but I can't think of them
off the top of my head.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Yet another block cipher: Storin
Date: 24 May 2000 18:01:35 -0700
In article <8ggv2a$h5c$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> Blowfish avoids this problem by setting the max key length to be 14
> words instead of 18.
Well, ok, but I believe even in Blowfish you can find a 448-bit key
that will force the first 14 round subkeys to be zero; the last four
remain uncontrolled. In any case, the probability of hitting a weak
key is so small that I think it is probably negligible in most scenarios.
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3 for T Huuskonen
Date: Wed, 24 May 2000 18:05:10 -0700
tomstd wrote:
>
> In article <[EMAIL PROTECTED]>, Anthony Stephen
> Szopa <[EMAIL PROTECTED]> wrote:
> >T. Huuskonen says:
> >"My observation shows that for a large class of keys (those
> that
> >involve a non-trivial amount of processing before the
> generation
> >of the pseudo random digit stream) there is a faster attack
> against
> >OAP-L3 than brute forcing the whole key. Hence, your "security
> >level" calculations are wrong. Of course, an attack requiring
> >10^100 tries is just as impossible in practice as one requiring
> >10^1000 tries. In other words, I know that your "security
> level"
> >numbers are wrong, but I don't know whether the mistake has any
> >practical consequences whatsoever."
> >
> >Your observation is not an observation. It is your fantasy.
>
> Prove it.
>
> Tom
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
> The fastest and easiest way to search and participate in Usenet - Free!
TH says that the random digit generator used in OAP-L3 is insecure.
You cannot logically or reasonably just pluck out a component from
software and make an assertion completely out of context.
I have proved it in the post you have just replied to yet you still
haven't got a clue.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: safer style sboxes
Date: Thu, 25 May 2000 00:57:44 GMT
In article <8gfn3j$8b9$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> In article <8gfjlh$ib5$[EMAIL PROTECTED]>, zapzing
<[EMAIL PROTECTED]> wrote:
> > I just wonder why cipher desighners don't start
> > using larger s-boxes.
>
> Performance. A 8x8 (or 8x32) S-box fits in the L1 cache.
> A 16x16 S-box doesn't, and so lookups will be considerably slower.
>
> > I was also wondering about this method for
> > "generating" sboxes that are key dependent.
> > What about
> > s(x)=(((x+k1)^k2)+k3)^k4 ...
>
> The high bits of x never affect the low bits of s(x).
> You'll probably want better diffusion...
>
Oh, yeah, That's pretty obvious i guess.
Perhaps we could reverse the bits
every now and then:
s_1(x)=(x+k1)^k2
s_2(x)=(R(s_1(x))+k1)^k2 (repeat as necessary)
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Smooth numbers
Date: 25 May 2000 01:09:32 GMT
>Eric Hambuch wrote:
>>
>> Does anybody know the number of primes n, where n-1 is "smooth" (n has
>> only small prime factors p_i of size O(log n)) ?
>>
>> Any hints (or better proofs and references) are welcome !
>>
>> Eric
>
I think the paper by Knuth and Trabb Pardo answers this.
It's entitled "Analysis of a simple factoring algorithm".
Scott
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: how do you know your decyption worked?
Date: 24 May 2000 18:08:55 -0700
In article <[EMAIL PROTECTED]>,
Dan Day <[EMAIL PROTECTED]> wrote:
> Instead, I think he's asking how a cryptanalyst can tell when
> he has correctly "broken" the encryption and recovered the
> original plaintext, given that the "plaintext" may not be text,
> or very "plain", and it may be difficult for the cryptanalyst to
> distinguish the desired plaintext from the gibberish that
> results from an improper decryption.
In that case, there are many statistical tests available.
See especially the classical literature on cryptanalysis of
pre-computer cryptosystems.
If you like, you can also read a paper Steve Bellovin and
I wrote that examines the question of how to build a
ciphertext-only custom-hardware DES-cracker:
http://www.cs.berkeley.edu/~daw/papers/recog.ps
Basically, you can use log-likelihood measures to the
digraph statistics of the plaintext and do quite a good
job of recognizing plaintext without increasing the size
of the DES-cracker chip too much, for many text sources.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: bamburismus
Date: 24 May 2000 18:12:12 -0700
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> John Savard wrote:
> > With proper use of modern algorithms, and the power of the computer
> > as an encryption tool, though, one can probably suspect that
> > cryptanalysis itself (and not just the kappa test in particular) is
> > obsolete or close to obsolete.
>
> Hardly. The main problem is a shortage of qualified analysts in
> the face of a proliferation of cryptosystems. My estimate is
> that roughly half of the major practical cryptosystems of the
> modern era *that have been seriously tackled* have been successfully
> cryptanalyzed (under favorable circumstances, not necessarily 100%
> of the time).
Nonetheless, if we interpret "proper use of modern algorithms"
as "use 3DES" and we interpret "cryptanalysis" as "analysis of
block (or stream) ciphers", John Savard's comment seems to stand
up pretty well -- it seems that potential weaknesses in the
higher-level aspects of the system will dominate the assurance
level of the low-level primitives, no?
------------------------------
Subject: Re: safer style sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 18:13:46 -0700
In article <8ghtq0$8id$[EMAIL PROTECTED]>, zapzing <zapzing@my-
deja.com> wrote:
>In article <8gfn3j$8b9$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (David A. Wagner) wrote:
>> In article <8gfjlh$ib5$[EMAIL PROTECTED]>, zapzing
><[EMAIL PROTECTED]> wrote:
>> > I just wonder why cipher desighners don't start
>> > using larger s-boxes.
>>
>> Performance. A 8x8 (or 8x32) S-box fits in the L1 cache.
>> A 16x16 S-box doesn't, and so lookups will be considerably
slower.
>>
>> > I was also wondering about this method for
>> > "generating" sboxes that are key dependent.
>> > What about
>> > s(x)=(((x+k1)^k2)+k3)^k4 ...
>>
>> The high bits of x never affect the low bits of s(x).
>> You'll probably want better diffusion...
>>
>
>Oh, yeah, That's pretty obvious i guess.
>Perhaps we could reverse the bits
>every now and then:
>
>s_1(x)=(x+k1)^k2
>s_2(x)=(R(s_1(x))+k1)^k2 (repeat as necessary)
Then it would be slow and still fail SAC not to mention BIC.
You would have to rotate the word, or perform some affine
mapping etc...
Take a look at SAFER's usage of the PHT matrices and Rijndael's
Affine Mapping for some good examples.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Patent state of Elliptic Curve PK systems?
Date: 25 May 2000 01:16:10 GMT
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
>Scott Contini wrote:
>> There is a patent held on elliptic curves over GF(p) where p is
>> a special form. I believe the form is 2^n +/- c where c is
>> a small integer. This is a patented that should really be fought,
>> since the ideas of doing fast arithmetic on these primes have been
>> well known for a long time. (I think this patent is held by Apple).
>
>That's Crandall's patent on EC-DH over GF(p^m) for p of special form.
>The form is correct, - is the choice to make things fit in machine
>words.
>
Hmmmmmmmmmm it was my understanding that the patent covers GF(p)
also (prime field - not just prime powered). At least that's what I
was told...
Scott
------------------------------
Subject: Re: Yet another block cipher: Storin
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 18:15:15 -0700
In article <8ghu1f$c4g$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
>In article <8ggv2a$h5c$[EMAIL PROTECTED]>, <matthew_fisher@my-
deja.com> wrote:
>> Blowfish avoids this problem by setting the max key length to
be 14
>> words instead of 18.
>
>Well, ok, but I believe even in Blowfish you can find a 448-bit
key
>that will force the first 14 round subkeys to be zero; the last
four
>remain uncontrolled. In any case, the probability of hitting a
weak
>key is so small that I think it is probably negligible in most
scenarios.
Not to mention that 448-bit keys are a tad excessive anyways.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: safer style sboxes
Date: Thu, 25 May 2000 01:11:35 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> In article <8gfjlh$ib5$[EMAIL PROTECTED]>, zapzing <zapzing@my-
> deja.com> wrote:
> >In article <8gfc0q$d86$[EMAIL PROTECTED]>,
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> >> I have tested all possible sboxes in GF(257) of the form
> >>
> >> S(x) = x^b mod 257
> >> and
> >> S(x) = b^x mod 257
> >>
> >> (fixed 'b' value)
> >>
> >> And haven't found one that is ideally non-linear. Which
> makes me ask,
> >> how come ciphers like SAFER or E2 (uses x^255 right?) can get
> away
> >with
> >> that?
> >>
> >> I use the WT to measure non-linearness and typically see -
> 44/44 as the
> >> WT output... I would expect at least -32/32, and at best -
> 16/14
> >> (matsui's sboxes do that well).
> >>
> >> Tom
> >>
> >> Sent via Deja.com http://www.deja.com/
> >> Before you buy.
> >>
> >
> >I just wonder why cipher desighners don't start
> >using larger s-boxes. From what I understand, if
> >an s-box is large enough, say 16 bits, then just
> >about any randomly generated s-box will perform
> >adequately. With hardware improving by leaps
> >and bounds, this seems like it might be the
> >way to go.
>
> Not true, a 16x16 sbox would still have to be designed according
> to CAST (or similar) to be secure. While it is possible to
> make 'more' secure 16x16 sboxes then say two parallel 8x8 sboxes
> you have to be careful.
>
I was going by what I read in "applied cryptography"
section 14.10 seems to say that a 16X16 randomly
generated s-box would probably be very secure.
> >I was also wondering about this method for
> >"generating" sboxes that are key dependent.
> >What about
> >
> >s(x)=(((x+k1)^k2)+k3)^k4 ...
> >where + (now) indicates addition modulo whatever
> >and ^ indicates xor. One could also imagine
> >using other operations in this way, such as
> >the exponentiation you mentioned above.
>
> Hmm, it's linear, it has good input-output xor pairs, has no SAC
> or BIC... not a good idea.
>
> Just because you use add/xor doesn't automatically make it non-
> linear. Take the lsb for example, it's perfectly xor-linear.
> So given
>
> S(x) = (x + K1) xor K2
>
> for example, that's the same as
>
> S(x) = x xor K1 xor K2
>
> For the lsb, or essentially just
>
> S(x) = x xor K'
> K' = K1 xor K2
>
> Once I find that little bit, the next bit becomes perfectly xor-
> linear, etc...
>
> In all about 2n plaintexts are needed and about the same in time
> (to find the keys). It's not a good sbox at all.
>
> Tom
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion
Network *
> The fastest and easiest way to search and participate in Usenet -
Free!
>
>
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Encryption within newsgroup postings
From: stanislav shalunov <[EMAIL PROTECTED]>
Date: Thu, 25 May 2000 01:43:06 GMT
"Dave Jones" <[EMAIL PROTECTED]> writes:
> I have found a variety of newsgroup postings which have part of the text
> encrypted. There are no numbers or special characters used, it looks
> something like the following:
>
> yytjk y pltra........etc
It's not a ciphertext. Spam canceling bots look for a lot of
identical messages and cancel them.
Adding random junk to spam bodies and subjects attempts to defeat
BI computations. Spam cancelers usually get around it.
One can bet that the arms race on this arena will continue for a long
time.
--
stanislav shalunov | Speaking only for myself.
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
