Cryptography-Digest Digest #455, Volume #12 Wed, 16 Aug 00 01:13:00 EDT
Contents:
Re: Unauthorized Cancel Messages ([EMAIL PROTECTED])
Choosing parameter sizes (was Re: OTP using BBS generator?) (David Hopwood)
Re: 215 Hz five-qubit quantum processor (Paul Rubin)
Re: Crypto Related Professional Attitude ([EMAIL PROTECTED])
Re: Diehard Troll detector. ("Adam Smith")
Re: 1-time pad is not secure... (Guy Macon)
Re: OTP using BBS generator? (Terry Ritter)
Re: OTP using BBS generator? (Terry Ritter)
Re: OTP using BBS generator? (Terry Ritter)
Re: OTP using BBS generator? (Terry Ritter)
Re: OTP using BBS generator? (Terry Ritter)
Re: BBS agreement? (Terry Ritter)
Re: OTP using BBS generator? (Terry Ritter)
Re: Quick Question ("John A. Malley")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Unauthorized Cancel Messages
Date: Wed, 16 Aug 2000 02:03:39 GMT
In article <[EMAIL PROTECTED]>,
Ron B. <[EMAIL PROTECTED]> wrote:
> It appears to me that someone is sending bogus cancel messages to
> sci.crypt and the alt.security.* groups. My newsreader shows several
> "This message is no longer available" messages for several legitimate
> messages. This are clearly not anti-spam cancels as they are new
> responses to postings. Has anyone else seen this?
>
You can read the cancelled messages from deja.com, whether it's
authorized or unauthorized.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Wed, 16 Aug 2000 08:45:36 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Choosing parameter sizes (was Re: OTP using BBS generator?)
=====BEGIN PGP SIGNED MESSAGE=====
Mok-Kong Shen wrote:
> Mark Wooding wrote:
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > > My point is that at any given time, e.g. now, we'll have difficulty of
> > > rigorously quantifying the 'difficulty' in question? Should we measure
> > > it in terms of cpu-time of factoring the given numbers by a
> > > 'particular' algorithm, or what? (The choice of the algorithm would be
> > > an issue.)
> >
> > Cost of the cheapest implementation, in dollars, normalized according to
> > running time (and probability of success, for special-purpose
> > algorithms). This takes into account the heavy memory requirements and
> > other similar issues raised by algorithms such as the number field
> > sieve.
>
> I am afraid that such a measure tends to be rather inaccurate
> or dependent on factors that are not ubiquitously present
> and hence more or less vague for the reader.
Yes, and that's why a fairly generous "fudge factor" should be added to the
key lengths predicted to be necessary from cost, time, and/or space estimates.
Fortunately this is quite practical, because the time needed to perform a
cryptographic operation for a modulus of length k bits only increases as
roughly k^c, where c is typically between 2 and 3. Hence we can choose
parameter sizes that hopefully compensate for any inaccuracies in the model
(and to a certain extent for algorithmic improvements in factoring, if they
are not too large).
- --
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
iQEVAwUBOZpGbzkCAxeYt5gVAQGt6ggAqP7t1QKGNHhbHH0cumnzBc5U4e8ufX7n
YfirTO8wPGi5rrD74zYz7e4rXsufD59eaGvESz5+0dFQwMEThtEJk+u73EagcMI3
BChOnpyjN4bsVfWP4zs84lt0wFB2yhtLDrdhrbxrBxVCdzC4eX//8gb1WyyfhjZ2
0V8QndeR9Mc27IGojz5gFhUegpeIaCkcpUk0hjQM6dI67EinalBzqJ7Dpiy9/TLZ
0ssbZQSRfQhvOIfg6R/kvIKIGr7S9dnJLXcnfRmHzQDM1XL8F5nCtiySEr/S6cmh
dCpCc6g4EKPRny+cM4VNJ86wgjjYGUWDHh+muul6H0bW3JH1d3bltQ==
=7+oi
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: 16 Aug 2000 02:15:05 GMT
In article <[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
> Wow .. this technology is moving fast! In 2Q98 there were still
>many physicists doubting that anyone could ever make a model that
>could remain coherent for more than one or two operations at a time,
>and now here's IBM in 3Q00 demo'ing a 215 Hz system!
Do they say that it can run for longer than 0.01 seconds? Where did
you see the 215 hz figure? I haven't found it on any of those links yet.
> Seems to me that if a quantum computer like IBM's can solve the
>period of an arbitrary function in P time (indeed, in O(1) time),
>then it might also be able to solve the halting problem in P time...
The class of problems a quantum computer can probablistically solve in
P-time is called QBP. It's believed to be larger than P but it still
is no larger than NP. Factoring and other search-type problems sit
inside QBP, but sorry, the classical halting problem is still undecidable.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Crypto Related Professional Attitude
Date: Wed, 16 Aug 2000 02:08:21 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> It is natural that the top experts are hardly experiencing
> 'oppositions' because they are almost always doing right
> and as a result tend to be with time no longer accoustomed
> to hearing differing opinions. But a genuinely great (as
> against half-great) scientist should have no problems of
> any kind, I believe, of encountering and appropriately
> dealing with counter-arguments, if these do have some
> weight from the view point of science.
>
> A problem of having a big name is of course that one
> becomes a centre of big attraction and that could be a
> disadvantage. Being a nobody, I can at any time leisurely
> walk down the main streets in my city and enjoy looking
> at the shop-windows. But a film star would have been
> impossible to do the same. This could be one, though I
> would say a comparatively fairly minor, reason why a
> number of the lustrous scientists in crypto never visit
> our group.
>
> M. K. Shen
The real reason is that if the big names have something interesting in
mind, they won't discuss it here for everyone to see. If the topic is
not interesting to them, they won't participate. Another reason is that
if they say something wrong here, they will be held responsible. They
don't write something for EVERYONE to see without re-checking 100 times.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Adam Smith" <[EMAIL PROTECTED]>
Subject: Re: Diehard Troll detector.
Date: Wed, 16 Aug 2000 02:20:54 GMT
Nice creativity though! : )
"Paul Pires" <[EMAIL PROTECTED]> wrote in message
news:r5Zl5.32257$[EMAIL PROTECTED]...
>
> Paul Pires <[EMAIL PROTECTED]> wrote in message
> news:bYYl5.32184$[EMAIL PROTECTED]...
> > I have an Idea!
>
> Never mind. I got it. don't know what the problem was Probably a dead
short
> between the keyboard and the chair.
>
> Paul
>
>
>
>
>
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: 1-time pad is not secure...
Date: 16 Aug 2000 02:32:24 GMT
Douglas A. Gwyn wrote:
>
>
>Guy Macon wrote:
>> I was just responding to his comment that
>> he wishes that it was on the Internet ...
>
>I didn't say that.
*****************************************
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Date: 11 Aug 2000 00:00:00 GMT
Message-ID: <[EMAIL PROTECTED]>
Newsgroups: sci.crypt
And yes, I know about "tachyons" -- in 1970 I wrote a paper
showing that tachyons are actually tardyons being perversely
interpreted. (Couldn't get the paper published, however.)
*****************************************
From: [EMAIL PROTECTED] (Guy Macon)
Date: 11 Aug 2000 00:00:00 GMT
Message-ID: <8n19bo$[EMAIL PROTECTED]>
Newsgroups: sci.crypt
So why haven't you published it yourself on the Internet?
*****************************************
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Date: 11 Aug 2000 00:00:00 GMT
Message-ID: <[EMAIL PROTECTED]>
Newsgroups: sci.crypt
I haven't had time to set up a Web site. Whenever I get
a round tuit, that will be one of the things I'll include.
*****************************************
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: OTP using BBS generator?
Date: Wed, 16 Aug 2000 03:21:26 GMT
On Tue, 15 Aug 2000 21:21:28 +0200, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>
>> I would say that I do have such an analysis, and it does back me up:
>> If we use the BB&S construction, we are *guaranteed* not to use a
>> short cycle. If we don't, then we are just very, very *unlikely* to
>> use a short cycle. To me, the distinction is the essence of what we
>> want from a proof of strength. If we were willing to accept a little
>> weakness here and there, it seems unlikely that we would have much
>> interest in cryptographic proof.
>
>Please correct me if I am wrong. I guess that you have
>investigated the cycle lengths of the direct output of
>the congruence relation but not the cycle lengths of
>the LSB, which could be comparatively much shorter.
>Further there seems to be no 'apriori' reason that there
>should exist a neat and simple relation between these
>two types of cycle lengths.
No correction is needed, since you are right. I have no special
information on the LSB question.
---
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: OTP using BBS generator?
Date: Wed, 16 Aug 2000 03:22:35 GMT
On 15 Aug 2000 16:54:32 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>Terry Ritter <[EMAIL PROTECTED]> wrote:
>
>> That's a wrong answer: The construction as described in BB&S first
>> guarantees that cycles of a given length must exist, and then shows
>> how to check that x0 is on such a cycle. The check is thus absolute
>> proof that a short cycle has not been selected.
>
>No, it only shows the cycle length for the sequence <x_i>, not the
>sequence of parity bits.
Yes. I got carried away on the old issue. Sorry.
---
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: OTP using BBS generator?
Date: Wed, 16 Aug 2000 03:30:16 GMT
On Tue, 15 Aug 2000 21:21:38 +0200, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Mark Wooding wrote:
>>
>> Terry Ritter <[EMAIL PROTECTED]> wrote:
>>
>> > That's a wrong answer: The construction as described in BB&S first
>> > guarantees that cycles of a given length must exist, and then shows
>> > how to check that x0 is on such a cycle. The check is thus absolute
>> > proof that a short cycle has not been selected.
>>
>> No, it only shows the cycle length for the sequence <x_i>, not the
>> sequence of parity bits.
>
>Sorry, I am really confused. 'Parity bits' or 'LSB'? Thanks.
The "parity" property to which BB&S refers is "odd vs. even," which is
also the least-significant-bit (LSB) in binary representation. We
might call it <x_i> mod 2.
BB&S mathematical "parity" is different from the usual coding and
data-communications usage, where "parity" represents whether the
number of 1-bits in a code or data value is odd or even.
---
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: OTP using BBS generator?
Date: Wed, 16 Aug 2000 03:32:41 GMT
On Tue, 15 Aug 2000 21:21:32 +0200, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> [EMAIL PROTECTED] (Mark Wooding) wrote:
>>
>> >Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>> >[...]
>> >> (3) Does the 'check' being disputed really prevent a certian
>> >> lower bound of the cycle lengths of the LSB sequences
>> >> (not the direct output of the congruence relation) of
>> >> being inadvertently 'under-run' or does the check only
>> >> do that in a probabilistic sense (i.e. with certain
>> >> probability not equal to 1)? What is that lower bound
>> >> actually (in relation to p and q)?
>> >
>> >It doesn't do anything of the kind.
>>
>> That's a wrong answer: The construction as described in BB&S first
>> guarantees that cycles of a given length must exist, and then shows
>> how to check that x0 is on such a cycle. The check is thus absolute
>> proof that a short cycle has not been selected.
>
>Excuse me for being hardnecked in asking questions. Does
>the phrase 'cycles of a given length' refer to cycles of
>the direct output of the congruence relation or does it
>refer to cycles of LSB. If it is the former case, then
>the fact mentioned by David Hopwood implies that one
>doesn't get results applicable to the cycles of LSB and
>one would have a problem.
My mistake, I was answering the old question.
---
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: OTP using BBS generator?
Date: Wed, 16 Aug 2000 03:44:02 GMT
On Wed, 16 Aug 2000 06:57:40 +0100, in
<[EMAIL PROTECTED]>, in sci.crypt David Hopwood
<[EMAIL PROTECTED]> wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>Terry Ritter wrote:
>> In BB&S we don't get the full state output, but we do get a bit of it,
>> and if we record that sequence and compare it to the incoming data,
>> presumably we can find a match. (There is a potential lead-in prior
>> to getting on a cycle, but I think that is limited to a single step.)
>
>There is no potential lead in. If x is the seed then the first bit output
>is the LSB of x^2 mod N, not the LSB of x. Since x^2 is a quadratic
>residue, it falls on a cycle.
Right.
---
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: BBS agreement?
Date: Wed, 16 Aug 2000 03:56:09 GMT
On Tue, 15 Aug 2000 13:49:04 -0500, in
<[EMAIL PROTECTED]>, in sci.crypt Doug Kuhlman
<[EMAIL PROTECTED]> wrote:
>Hey all! I'd like to try to bring some of the BBS discussion to some
>sort of agreed-upon conclusions. I *think* everyone has agreed to the
>following:
>
>1. Finding a cycle (any length) in BBS allows factoring the modulus
>2. Long cycles *do* exist with properly chosen BBS primes
I note that "properly chosen BB&S primes" means the "special primes"
construction, and not the far more casual reduced BB&S which just uses
Blum primes.
>These two are a large part of the BBS paper.
>
>3. Short cycles exist
>4. The chance of landing on a short cycle is microscopic [1]
>5. This chance is so small as to be unimportant in practice
>
>I think we have agreed to:
>
>6. Using BBS with no cycle check gives an attacker no advantage in
>factoring
I would say that distorts the issue beyond recognition.
The point is that the user selects and uses the cycles. If the user
selects a short cycle, the system as it exists is far weaker than when
a long cycle is used. The system without cycle length checks thus has
a known potential weakness which is not eliminated. Not only is this
an example of bad cipher practice, it is also an indication that what
remains of a proof may not be what users have in mind.
>What is not agreed upon is the terminology to be used.
One thing not agreed upon is that taking the construction from the
BB&S article, reducing it, thus allowing the short cycle weakness to
occur in practice, should be seen as BB&S. It is not BB&S, and does
not have the same guarantee; clearly, it is something less.
---
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: OTP using BBS generator?
Date: Wed, 16 Aug 2000 04:19:52 GMT
On Tue, 15 Aug 2000 13:40:38 -0500, in
<[EMAIL PROTECTED]>, in sci.crypt Doug Kuhlman
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> On Thu, 10 Aug 2000 13:51:58 -0500, in
>> <[EMAIL PROTECTED]>, in sci.crypt Doug Kuhlman
>> <[EMAIL PROTECTED]> wrote:
>>
>> >Terry Ritter wrote:
>> >>
>> ><SNIP>
>> >>
>> >> No; a "negligable probability" means that some probability remains.
>> >> And with random selection, that result will eventually occur.
>> >>
>> >You should know better than that. The probability that the sound of air
>> >coming through a naturally shaped tunnel will play the entire
>> >VeggieTales collection is non-zero, but it's not gonna happen in the
>> >lifetime of the universe. Same thing applies here.
>>
>> Sorry, but *you* should know better than that. None of this is about
>> weakness in practice, it is about falsely appearing to claim strength
>> on the basis of mathematical proof. The short-cycle weakness is a
>> theoretical weakness in the sense that it almost never occurs in
>> practice. But it is a practical weakness in the sense that the reason
>> to use BB&S in practice is to achieve the results of the theoretical
>> claim. But theoretically, if long cycle operation is not guaranteed,
>> short cycle operation will occur, and the "proven secure" system will
>> be insecure, sooner or later.
>> <SNIP>
>> Nope, that seems to be *your* problem: Possibility and probability
>> are statistical terms. If something is *possible* under random
>> selection, it eventually *will* *happen*. This concept is important
>> and you need to understand it. The same concept occurs in computer
>> programming.
>>
>>
>First you argue that you're not claiming it's a weakness in practice and
>less than a page later, you're trying to claim that it will happen.
>Which is it?
Both.
>Can you pick the right atom of the Earth in the exact millisecond of the
>day? Your odds of landing on a short cycle are worse. "Can happen" is
>not the same as "will happen". Lots of things can happen, very few
>actually do or even will happen.
I guess we need to step back a bit and take a look at the larger
context of all this:
One of the advantages of analysis is to address things which are too
infrequent to be detected reliably from experiment. But even low
probability things do in fact happen; if not, they would be
"impossible," instead of "rare."
We typically think of cryptographic strength as the minimum effort
needed for any possible attack to expose the protected information or
keys. Cryptographic strength is thus concerned with statements about
guaranteed minimum strength, instead of strength on average. Such
statements are not usually available with conventional ciphers, which
is a major motivation for mathematical proofs of strength.
It now appears that current cryptographic proofs do not give us
realistic lower bounds on strength even in the best possible case.
But short cycles present a clear and known weakness. Any system which
allows use of short cycles cannot be guaranteed to have any more
strength than a short cycle, no matter what other theoretical advances
may occur.
So, "merely" by arranging to not use a short cycle, we can at least
say that we know of no weakness significantly lower than the strength
we get from long cycles. In the context of grasping for whatever
guarantees we can get, a guarantee to not use short cycles, and so not
have a known weakness at that level, is a serious advantage.
>> <SNIP>
>> So, basically, you are fine with changing the current description of
>> "proven secure," to "proven to have a negligible likelihood of
>> weakness." That's not as straightforward as "almost always secure,"
>> but it is an improvement.
>>
>Sure! Always a chance of weakness. Maybe some hotshot will figure out
>how to factor arbitrarily large numbers in constant time. All kinds of
>things are potential weaknesses. The possibility of landing on a short
>cycle is the least of my concerns (about BBS).
Because short cycles are typically very hard to find, they probably do
not represent a significant weakness in practice.
However, allowing the possibility of using short cycles in BB&S does
represent a lack of will to address a known weakness and prevent that
from happening. The best possible guarantee of strength for such a
system is the weakness of a short cycle.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Quick Question
Date: Tue, 15 Aug 2000 21:29:41 -0700
Steven Knight wrote:
>
> I know encryption uses algorithms but what are they?
Knuth says it best in Fundamental Algorithms, vol 1 of the Art of
Computer Programming:
an Algorithm is a finite set of rules which gives a sequence of
operations for solving specific types of problems.
Algorithms possess five characteristics:
1. finiteness - an algorithm always terminates after a finite number of
steps.
2. definiteness - the actions to be carried out at each step must be
rigorously and unambiguously specified for each case.
3. input - an algorithm gets zero or more quantities given to it before
it begins.
4. output - an algorithm generates one or more quantities upon
termination which have a specific relationship to the input quantities.
5. effectiveness - all of the operations performed in the algorithm must
be sufficiently basic that they can in principle be done exactly and in
finite time by a human with pencil and paper (or other implements. )
>
> And can anyone give me a SIMPLE example of one.
Euclid's Algorithm: Given two positive integers m and n, find their
greatest common divisor (GCD) - the largest integer evenly dividing
both m and n.
Input: Let A = m and let B = n.
Step 1: Divide A by B and let r be the remainder. 0 <= r < n.
Step 2: If r = 0, terminate (stop.) Current value of B is the GCD of m
and n. Output B.
Step 3: Let A = B and let B = r. Now go to step 1.
Check out Mr. Knuth's web site at
http://sunburn.stanford.edu/~knuth/index.html
There are many algorithms used in cryptology - the Handbook of Applied
Cryptography is an invaluable source of cryptographic and cryptanalytic
algorithms. It's online at http://cacr.math.uwaterloo.ca/hac/.
John A. Malley
[EMAIL PROTECTED]
------------------------------
** 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
******************************
