Cryptography-Digest Digest #72, Volume #9 Fri, 12 Feb 99 01:13:03 EST
Contents:
Re: Some more technical info on Pentium III serial number (John Nagle)
Re: On a Method of Session Key Generation (revised) (Hal Finney)
Re: Some more technical info on Pentium III serial number (John Nagle)
Re: HELP!: seeking algorithms for coding theory problem (Markus Grassl)
Re: 2048-bit block cipher (wtshaw)
Re: Metaphysics Of Randomness (Patrick Juola)
Re: Clarification on PGP. pls ("Wm. Toldt")
Re: Transforming RC4 into a one-way hash function (Bauerda)
The Hunt is On @ PAWS ! ! (Richard Goldman)
Program Idea ("John Doe")
Re: Clarification on PGP. pls ("Trevor Jackson, III")
Re: Two simple questions about RSA
Re: RNG Product Feature Poll (Dave Knapp)
Web Site Problems, Quadibloc III
----------------------------------------------------------------------------
Crossposted-To: talk.politics.crypto,comp.sys.intel
From: [EMAIL PROTECTED] (John Nagle)
Subject: Re: Some more technical info on Pentium III serial number
Date: Fri, 29 Jan 1999 08:03:27 GMT
[EMAIL PROTECTED] (Brad Templeton) writes:
>I don't get it. How does a web server "request" the ID of a client?
>A web server can't make any requests of a client. The client makes
>requests of the server. The server can send back things like Redirects
>and Authentication responses that make the client do more, but there
>is nothing in any web browser or the HTTP protocol to send these
>serial numbers or play the games described.
>Has Intel been proposing extensions to HTTP or other protocols?
>Where are those extensions documented?
>Has any browser vendor or the W3C given even the slightest indication
>they would support such extensions?
Now that's the right question. How were remote sites supposed
to get this info? Or is Intel assuming that browsers will be
designed to be "advertiser-friendly"? If browsers are going to
spy on their users, there's far more interesting stuff they can
access than the CPU serial number.
John Nagle
------------------------------
From: [EMAIL PROTECTED] (Hal Finney)
Subject: Re: On a Method of Session Key Generation (revised)
Date: 11 Feb 1999 22:32:36 GMT
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>Over 50 years of mathematical cryptography has yet to produce any such
>proof. Systems which even get close to such claims (e.g., BB&S, RSA,
>DH) still get a great deal of jaundiced scrutiny. If we limit
>cryptography to only provably-secure ciphers, we will not be sending
>many messages: There are no such ciphers.
>
>And with all this work and *no* examples of ultimate success, one
>might be tempted to think that there is some inherent reason.
>Personally, I suspect that a provably secure cipher simply cannot
>exist.
Of course, "provably secure" is relative to a specific set of axioms.
It is common, these days, for cryptographic proofs to in effect assume
a stronger set of axiomatic assumptions, else, as you say, there would
not be much work which could be done. The net result is that most work
in cryptographic security is in the form of reductions, with one
protocol's security being shown to have a specified relationship
(implied by, equivalent to, implies, independent of...) to some other
problem. BB&S is provably secure if we assume the hardness of
quadratic reciduosity, etc.
The work of Greg Chaitin suggests viewing mathematics as a more
exploratory discipline. Rather than taking our axioms as given, we
explore what fundamental assumptions are necessary to produce various
proofs. Over time those assumptions may then become generally
accepted. It may well be that eventually axioms will become well
accepted which allow proving that P <> NP and that various mathematical
cryptographic systems are secure.
Hal
------------------------------
Crossposted-To: talk.politics.crypto,comp.sys.intel
From: [EMAIL PROTECTED] (John Nagle)
Subject: Re: Some more technical info on Pentium III serial number
Date: Fri, 29 Jan 1999 08:05:33 GMT
[EMAIL PROTECTED] (Paul Rubin) writes:
>It sounds to me like Intel is going to release browser controls
>(Netscape plug-in and Explorer ActiveX control) that read the serial
>number. They could distribute the controls through their own web
>site, or possibly get Micro$oft to include the controls in Windoze
>N+1. DHTML script on random web pages could then invoke the controls
>to put the numbers into hidden form fields that would be sent as part
>of the next GET or POST. The controls could even open their own IP
>connections back to the web server. This is all quite possible even
>today, without any participation from browser vendors or W3C. The
>main problem is social-engineering the users to accept the plug-ins.
>It looks like Intel has failed at this pretty badly already.
Is there some procedure for revoking Intel's code-signing key?
Probably not; anybody with a D&B number can get a code-signing key,
and anybody with a business name can get a D&B number from www.dnb.com.
John Nagle
------------------------------
From: Markus Grassl <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.math.research
Subject: Re: HELP!: seeking algorithms for coding theory problem
Date: 11 Feb 1999 21:52:35 +0100
In addition to the article <79v7dm$[EMAIL PROTECTED]>, here is the
reference:
Anne Canteaut and Florent Chabaud.
A New Algorithm for Finding Minimum-Weight Words in a Linear Code:
Application to McEliece's Cryptosystem and to Narrow-Sense BCH Codes
of Length 511.
IEEE Transactions on Information Theory, vol. 44, no. 1, January
1998, pp. 367-378.
(I have the journal on my shelf, but hadn't noticed that paper.)
Furthermore, a good reference on the hardness of finding small weight
words and subset sums is
Alexander Vardy.
The Intractability of Computing the Minimum Distance of a Code.
IEEE Transactions on Information Theory, vol. 43, no. 6, November
1997, pp. 1757--1773.
--
Markus Grassl
IAKS, Fakultaet fuer Informatik
Universitaet Karlsruhe, Am Fasanengarten 5, 76 128 Karlsruhe, Germany
e-mail: [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: comp.security.misc
Subject: Re: 2048-bit block cipher
Date: Wed, 10 Feb 1999 07:46:37 -0600
In article <79palq$1cq$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (wtshaw) wrote:
> > All seems simple enough, all wrapped around this Alex chained algorithm.
>
The question of whether a particular algorithm, including all steps, is as
good as it could be, and what might be done to strengthen it if desired,
should have more weight than a generalization concluding that it should be
disregarded since it is not perfect or is not the next killer crypto
application.
The importance of noting the strengths of a design should be on a par with
noting weak areas. Personally, I shy away from chaining thus far in my
own designs; I have felt that the basic core strength of an algorithm is
poor if chaining is required for usefulness. Therefore, my comment, that
the core algorithm is still the most important area of this cipher.
In defense of the use of chaining, it can add just another layer of
strength, but it should not be the easily solved link that in solution
unmasks the weakness of the core. On the otherhand, such an algorithm,
one most dependent on chaining for strength, can be used as a vehicle to
evaluate the usefulness of the chaining method, many of which are
insufficient in my opinion. It may well be that the core algorithm may be
replaced with something better once the strength of the chaining step is
fully appreciated.
--
A much too common philosophy:
It's no fun to have power....unless you can abuse it.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 10 Feb 1999 08:39:42 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 8 Feb 1999 08:41:28 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>Opinions, from experts, cost money. Truthful opinions tend to
>>cost even more.
>
>Hmm... that must mean that the book I am now reading by Li and Vitanyi
>is just a bunch of falsehoods - because it costs me nothing to read it
>(I got it from the library).
Or that you're a tax-dodging scoundrel. I'll leave you to guess
which.
>Thanks for warning me.
>
>>>What makes you think that tests for bias are conclusive? What if a
>>>PRNG passes such tests, and yet is not secure at all?
>
>>That's a separate question.
>
>Yes, but it is a valid question - and a most important one at that. Do
>you have an answer?
Well, the key thing about the PRNG is that it's *PROVABLY* biased
for lengthy strings; this is why the key-enumeration or brute force
attacks work.
So if you are serious enough in your testing, you'll catch this
bias.
Or, you could simply analyze the design and catch the PRNG, which I
recommend instead.
>>>You have reduced the whole question of using statistical tests down to
>>>testing for bias. I find that inadequate.
>
>>That's because all there *is* is bias. "Capable of generating all
>>finite-length strings equiprobably", remember?
>
>How could I forget.
>
>>If there's some string
>>that is less (or equivalently, more) probable than the norm,
>>then that's a bias against (for) that string.
>
>What is that norm? The probability of generating any string of length
>N is 2^{-N} for each and every string. Is that what you are talking
>about?
Yup. So if there's some string that appears *more* often than 2^-N,
there's a bias for the string.
>
>>You may be thinking of bit-bias, which *is* too limiting a case. But
>>bias comes in a lot more flavors than that.
>
>Actually I was thinking of k-bit group bias, with the "bit-bias" you
>are talking about being the case k=1.
>
>What other properties of numbers than k-bit group bias do you propose
>to measure statisitcally to certify that a RNG is suitable for use
>with the OTP cryptosystem in a secure manner?
There isn't anything. Group bias is basically all there is.
-kitten
------------------------------
From: "Wm. Toldt" <[EMAIL PROTECTED]>
Subject: Re: Clarification on PGP. pls
Date: Thu, 11 Feb 1999 17:29:26 -1000
Trevor Jackson, III wrote:
>
> fungus wrote:
>
> > "Wm. Toldt" wrote:
> > >
> > > I said I could "factor large primes" and you posted a composite number.
> > > Composite numbers are much harder to factor than prime numbers.
> >
> > I would have said it was the other way round - in my experience, prime
> > numbers are among the most difficult numbers to factor.
>
> This is an interesting question. I propose to solve it by using the runtime
> of GCD() as the metric of difficulty. Clearly faster means easier. Is there
> a systematic difference in run times bewteen GCD applied to primes versus
> composites?
These question have inspired several possible areas of research
over the last few hours. The conjecture which most interests me
is that it is systematic, and it is not random. Consider using
Euclid's algorithm to compute the GCD of consecutive primes vs.
consecutive composites. Here is an example: consecutive primes
are 97 and 101. Consecutive composites are 100 and 102. Find
the GCD (greatest common divisor) of both pairs:
102 = 100*1 + 2
100 = 2*50 so (100,102)= 2 = GCD
101 = 97*1 + 4
97 = 4*24 + 1
4 = 1*4 so (97, 101)= 1
My conclusion is that if consecutive numbers are used, it is
(apparently) slower to find the GCD of primes. So next I will
examine randomly chosen primes and composites with the same
number of digits (2 digits). Here are the primes I can use:
11 13 17 19 23
29 31 37 41 43 47 53 59 61
67 71 73 79 83 89 97
89 = 31*2 + 27
31 = 27*1 + 4
27 = 4*6 + 3
4 = 3*1 + 1 so (89, 31) = 1 for primes
91 = 42*2 + 7
42 = 7*6 so (91, 42) = 7 for composites
So it usually takes longer to compute the GCD of primes
than for composites. However, finding the GCD is not
best way to judge the difficult of factoring numbers.
There is a shortcut for factoring certain types of
numbers, such as primes and factorials. I can
factor those two types of numbers in
BIG O of a billion steps. Using a
pencil, this takes me under
36 hours.
Wm. Toldt
------------------------------
From: [EMAIL PROTECTED] (Bauerda)
Subject: Re: Transforming RC4 into a one-way hash function
Date: 12 Feb 1999 02:03:26 GMT
>I'm not sure about what you're meaning with your question, David, but after
>some serious thinking, I revised the scheme to add some more security:
By asking my question I was trying to avoid saying outright that I saw no point
at all to the XORing of the bytes at the end since they would be have no impact
on security. By puting these 'salt' bytes in before the string is hashed, they
have an effect on the final value which can not be trivially removed.
>
>1. Generate 20 random bytes (as random as possible)
>2. Process the e-mail address in 2-byte chunks by XORing them together, then
>XORing the results of this with one of the random bytes, selected using a
>nonlinear function of the e-mail address' contents, keeping the other byte
>unchanged in the output (i.e. n@ might turn up to be something like F@ or nP,
>but never xQ - only one byte is changed out of the two)
>3. Concatenate this scrambled e-mail address to the real one. Call this K.
>4. Walk through K, starting five bytes in front of the middle (L/2-5), and
>XOR
>K[i] with one of the random bytes, for a maximum of i==16, or until we runs
>out of e-mail address
>5. Load this generated K as the encryption key
>6. Generate 20 random bytes that are in no way related to those generated in
>step 1 (i.e. reinitialize the generator with other input)
>7. Encrypt these bytes
>8. Use the output as the hash
>
>Any comments would be appreciated.
I once again find steps 6 and 7 to be useless. An attacker just XORs the hash
value with those bytes and it is as if they were never there. Steps 1 - 5 are
fine, but I wonder if some of them are of too little value to be uselful (
steps 1 - 4).
David
------------------------------
From: Richard Goldman <[EMAIL PROTECTED]>
Subject: The Hunt is On @ PAWS ! !
Date: Thu, 11 Feb 1999 18:06:47 -0800
Reply-To: [EMAIL PROTECTED]
The Barbary Coast Armchair Scavenger Hunt and Trivia Contest is on at
PAWS. It takes place on Sunday, March 14th, 1999 on the internet from
your home from 12 til 4pm. Challenges are published on The Hunt website,
http://www.unexpected.com every 30 minutes for four hours. Your team
will compete with other teams by solving these obscure brain teasers and
challenges to win fabulous prizes while raising money for Pets Are
Wonderful Support. Registration is $15.00 per person with no maximum
number of participants per team, 100% of all registration fees goes
directly to PAWS. The more people on your team, the more likely you
will be to answer challenges correctly and win fabulous prizes. Check
out The Hunt website at http://www.unexpected.com for sample
challenges and lists of prize donors. Register your team early online
or at (415)-863-3506, as this event will fill up quickly. Remember the
more people that register on a team, the more money you can raise for
PAWS and have a good time doing it!
------------------------------
From: "John Doe" <[EMAIL PROTECTED]>
Subject: Program Idea
Date: Fri, 12 Feb 1999 04:43:39 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
I am not aware of any program that functions in the manner that I am
thinking of.. So here is my idea:
While watching a defragmentation program run, I realised that my files were
being scattered all over the place. Files that I would later wipe would
still leave traces on other parts of the disk. Would it be possible to write
a defragmentaion program that wipes as it defrags?
Thank you for your time
//||\\Jacob.Dav(no spam)@Usa.net//||\\
=====BEGIN PGP SIGNATURE=====
Version: PGP 6.0.2
iQA/AwUBNsOx5dep1OgOEI6NEQKwpgCdFXSV83oYp5M1IeBkxwTt9MTQJzwAoNnd
rmUVCpU/qvMWIkKf8M3f/nBO
=9i4U
=====END PGP SIGNATURE=====
------------------------------
Date: Thu, 11 Feb 1999 22:52:40 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Clarification on PGP. pls
Wm. Toldt wrote:
> Trevor Jackson, III wrote:
> >
> > fungus wrote:
> >
> > > "Wm. Toldt" wrote:
> > > >
> > > > I said I could "factor large primes" and you posted a composite number.
> > > > Composite numbers are much harder to factor than prime numbers.
> > >
> > > I would have said it was the other way round - in my experience, prime
> > > numbers are among the most difficult numbers to factor.
> >
> > This is an interesting question. I propose to solve it by using the runtime
> > of GCD() as the metric of difficulty. Clearly faster means easier. Is there
> > a systematic difference in run times bewteen GCD applied to primes versus
> > composites?
>
> These question have inspired several possible areas of research
> over the last few hours. The conjecture which most interests me
> is that it is systematic, and it is not random. Consider using
> Euclid's algorithm to compute the GCD of consecutive primes vs.
> consecutive composites. Here is an example: consecutive primes
> are 97 and 101. Consecutive composites are 100 and 102. Find
> the GCD (greatest common divisor) of both pairs:
>
> 102 = 100*1 + 2
> 100 = 2*50 so (100,102)= 2 = GCD
>
> 101 = 97*1 + 4
> 97 = 4*24 + 1
> 4 = 1*4 so (97, 101)= 1
>
> My conclusion is that if consecutive numbers are used, it is
> (apparently) slower to find the GCD of primes. So next I will
> examine randomly chosen primes and composites with the same
> number of digits (2 digits). Here are the primes I can use:
> 11 13 17 19 23
> 29 31 37 41 43 47 53 59 61
> 67 71 73 79 83 89 97
>
> 89 = 31*2 + 27
> 31 = 27*1 + 4
> 27 = 4*6 + 3
> 4 = 3*1 + 1 so (89, 31) = 1 for primes
>
> 91 = 42*2 + 7
> 42 = 7*6 so (91, 42) = 7 for composites
>
> So it usually takes longer to compute the GCD of primes
> than for composites.
I reasoned that gcd() of two arbitrarily chosen primes has to get all the way to 1,
while gcd() of two arbitrarily chosen composites has a shorter path in that it
stops before it gets to 1. While this cursory analysis ignores the variations in
the decrement step size I saw no reason to assume that the decrement step size
would be systemacially different.
> However, finding the GCD is not
> best way to judge the difficult of factoring numbers.
> There is a shortcut for factoring certain types of
> numbers, such as primes and factorials. I can
> factor those two types of numbers in
> BIG O of a billion steps. Using a
> pencil, this takes me under
> 36 hours.
How do you feel about factoring complex numbers whose terms are integral?
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Two simple questions about RSA
Date: 12 Feb 99 05:33:51 GMT
Gustavo ([EMAIL PROTECTED]) wrote:
: 1. On many books it is shown that, given the key pair (d,e),
: the modulus n=pq and a message m, RSA works thanks to the Euler
: theorem, provided that (m,n)=1. What if (m,n)!=1 (i.e. p or q
: divide m)?
It still works, but you just can't prove it as easily, perhaps.
: 2. What if the modulus n has more than two prime factors
: (apart from the obvious fact that factoring is easier)?
If n = pqrst, then (p-1)(q-1)(r-1)(s-1)(t-1) has to be used to derive d
from e and vice versa. (pqr-1)(st-1), for example, won't work.
John Savard
------------------------------
From: Dave Knapp <[EMAIL PROTECTED]>
Subject: Re: RNG Product Feature Poll
Date: Fri, 12 Feb 1999 05:56:40 GMT
R. Knauer wrote:
>
> On 11 Feb 1999 09:24:30 -0000, Paul Crowley
> <[EMAIL PROTECTED]> wrote:
>
> >>"Equidistributed" does not
> >> necessarily mean independent. "Independent" does not necessarily mean
> >> equidistributed.
>
> >unbiased?
>
> Equiprobable. Lack of bias is a necessary but not sufficient
> condition.
There are already a couple of good words for this: "white" and
"uniform." They have the additional advantage of fewer syllables.
A random uniform generator is what you are looking for.
-- Dave
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Web Site Problems, Quadibloc III
Date: 12 Feb 99 05:40:28 GMT
The Xoom site, lately, has had some internal delays: it keeps giving 404
errors on pages that not only are present, but will show up on a second
try.
Notwithstanding that, it contains the up-to-date version of my site. The
other location, though, gives faster responses - although I've had
accessibility problems reported from some areas.
I'm going to make *one more* change to Quadibloc III: during the Mishmash
rounds, when I subject one half of the block to four (original) Quadibloc
rounds, I will now take _not_ the four f-function outputs, but the four
intermediate results (after XORing in the second subkey) of the four
f-functions as inputs to the four f-functions which use subkeys from the
"extra 48" to produce the 32 bit control word for the complicated
encipherment of the other half of the block (choosing one of 32 subkeys
for each of the five steps, and using seven bits to choose an order for
the five steps).
John Savard
------------------------------
** 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
******************************
