Cryptography-Digest Digest #25, Volume #9 Tue, 2 Feb 99 19:13:03 EST
Contents:
Re: Random numbers generator and Pentium III (R. Knauer)
Re: Metaphysics Of Randomness (R. Knauer)
New PKI System or just old hat?
Re: Foiling 56-bit export limitations: example with 70-bit DES ([EMAIL PROTECTED])
Re: *** Where Does The Randomness Come From ?!? *** (Seisei Yamaguchi)
Final CFP: Crypto 99 ("Don Beaver")
Re: Random numbers generator and Pentium III (Jim Felling)
Re: Truth, theoremhood, & their distinction (Nicol So)
Re: Truth, theoremhood, & their distinction (Nicol So)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random numbers generator and Pentium III
Date: Tue, 02 Feb 1999 22:16:11 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 02 Feb 1999 11:42:23 -0600, Jim Felling
<[EMAIL PROTECTED]> wrote:
>I, having not read the references being referred to (as of yet) concede the point
>for now but I do reserve the right to at a later time after having read the work in
>question to quibble with your conclusions. ( it just sounds wrong -- this may be due
>to my intuition misleading me though - so I accept yield the point to you
Quibble away - I am not an expert at this stuff. I am just giving my
best shot at my understanding, which is always subject to refinement.
I will mention that either this book by Li and Vitanyi is extremely
interesting, just like Chaitins papers on the Web, or I am missing the
whole point and it could just be more dry, dull, boring mathematics.
The authors put just enough spin on their exposition to make me think
this is exciting stuff, but it could all be just a bunch of hype that
I am not qualified to see thru.
>I feel that, while it may not be as reliable as the above tests, it is still
>something worth doing. Every tool I use to test such a system can only add to my
>confidence in the system. There is no excuse for not testing such a system in every
>way possible so as to avoid an unanticipated weakness from 'breaking' your system.
Would you still make that statement if the test were shown to be
meaningless, or even counterproductive? If I told you that only TRNGs
made in cubic boxes will give good results and appealed to your sense
of symmetry to justify it, would you use that as a criterion for
proving up a TRNG?
>I feel that such analysis is necessary, but not sufficient to 'certify' such an
>instrument. I want to test the output and not merely rely on the 'fact' that this
>was a professionally designed machine made to rigorous standards, etc. and unless
>things have changed the only tools I have for such testing are statistical.
What if the tests are meaningless, and can give false results?
>I disagree -- how about changing that statement to: That confidence is based upon
>rigorous design, thorough review of the design, skilled calibration of the system,
>not merely statistical tests.
Testing the output does not fall into any of those categories. Testing
the output is not "skilled calibration of the system". There is no
calibration possible with meaningless tests.
>I feel that any testing that can be done should be done.
Even if it is meaningless, and can give false results that are
detrimental?
>And if a generator fails
>such a test it should be immediately pulled from service thoroughly examined,
>calibrated, etc. and then retested and if it passes then allowed back into service.
The only tests I would use on the output are ones that can be traced
back to known hardware malfunctions, like a shorted or grounded
output. All other strings are acceptable outputs for a TRNG.
>Ok, then how do you test your device as it runs? How would you determine whether
>your device is a working TRNG, and not a poor substitute( whether due to design
>flaw, sabotage, miscalibration, or accident)?
By running diagnostics on the subsystems, not the output.
Lets say someone did sabotage your TRNG in such a way that it put out
strings that passes our tests on the output. Now what are you gonna
do?
>I agree one should not reject any strings (either use or do not use the device) --
>but one should still evaluate the device.
The only evaluations are those that have a known reason for a
malfunction. Since a TRNG is not necessarily malfunctioning when it
fails a statistical test, that cannot be used to diagnose it reliably.
>Wrong. I agree that rejecting strings based upon criteria is bad, but there are
>methods that can be used to correct possible bias. that are of use.
Lack of bias is not a valid criterion deciding the randombess of
finite strings.
If you understand the specification for a TRNG, and why it results in
proveable security, you will see why it is meaningless to use
statistical tests on the output - no matter what the results of those
tests are, they are meaningless.
Statistical tests which purport to give results based on "good" and
"bad" strings is meaningless. The only two strings that are "bad" are
all 1s (open output) and all 0s (shorted output).
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Tue, 02 Feb 1999 22:21:15 GMT
Reply-To: [EMAIL PROTECTED]
On 2 Feb 1999 19:41:28 GMT, "John Feth" <[EMAIL PROTECTED]>
wrote:
>I'm going to give you a method to create
>reams of certifiable radom strings whenever you want.
Just wait until quantum computers come online. :-)
That system is not proveably secure. One cannot generate crypto-grade
random numbers algorithmically.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: <[EMAIL PROTECTED]>
Subject: New PKI System or just old hat?
Date: Tue, 2 Feb 1999 22:28:44 -0000
Patent 5864667
Anyone got any views on this?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Foiling 56-bit export limitations: example with 70-bit DES
Date: Tue, 02 Feb 1999 22:03:41 GMT
In article <797igo$jo7$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <794ruh$a7k$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > In article <78t64b$61o$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] wrote:
> > > In article <78ss2c$s4b$[EMAIL PROTECTED]>,
> > > [EMAIL PROTECTED] wrote:
> > [snip]
> > > > Have you considered doing both (i.e., Ci = rndblock_X XOR DES(Pi XOR
> > > > rndblock_X), where rndblock_X is the block you chose out of 2^M blocks)?
> > > >
> > >
> > > Yes, but it is worse.
> >
> > Why?
>
> Because if the plaintext is encrypted with an unknown-key (the choice I am
> considering) then the intended recipient will gain less in comparison to the
> attacker.
I don't understand. If you choose a different "whitener block" for each
message, then you could send the same message twice, with the same DES key,
and your security would be better of you "whiten" the plaintext before
DES-encryption, and then "whiten" the DES ciphertext before transmission.
Your contention that this is not necessary because one can use a different
DES key for each message is good, but I understand cryptography to be the art
of ameliorating even very unlikely risks. If a simple change makes it secure
even if you use the same DES key to send the same message, then you might as
well make the change.
[snip]
> 1. That is not what WA says -- it is the amount of secret-key that is
> controlled. And, M-DES only defines a secret-key that is 56-bit wide Please
> read the WA.
I think I was clear that I was describing US export law. If you really want
your 56-bit algorithm to be strong, try the following:
1) Prepend a block of all zeros for Alice to use in brute-forcing. P' = 0,P
2) Encrypt with 3-DES EEE CBC, with 3 random keys and a random IV C =
3DES(P') 3) Mask off M bits of the middle key. K2' = mask(K2) 4) Append the
three keys and the IV to the ciphertext C' = C,K1,K2',K3,IV 5) Encrypt DES
PCBC using the key you agreed on with Alice (by PCBC, I mean Ci = DES(Pi XOR
Pi-1 XOR Ci-i). C'' = DES(C')
Now, Alice has to decrypt the entire message, with the agreed upon key, and
then she must brute-force the missing M bits in K2. This adds a cost to the
attacker and not to Alice (since she had to decrypt the whole message anyway,
and she knows the DES key).
[snip]
> I must ask again, as I dis two msgs ago -- did you read the paper? This is
> discussed, along with other possibilities. The cure is simple -- change DES
> session-key for each message -- there is no shortage of them. As another
> cure, you can change the unknow key. Or, even, change BOTH, as the text
> recomemnds, if your security needs so justify.
It's better to make it so you don't need to change the DES key every time.
Then, you can still change the DES key every time anyway, if you so desire.
--
Peter
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Seisei Yamaguchi)
Crossposted-To: sci.skeptic,sci.philosophy.meta
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: 2 Feb 1999 18:51:28 GMT
Hi, this is Seisei.
Ron Cecchini <[EMAIL PROTECTED]> wrote:
>The first step is to try to *define* "true randomness"!
That's right.
Randomness and unforeseeableness are not identical.
And, I think it's non existent randomness.
--
Seisei Yamaguchi (name( first( 青星 ), last( 山口 ) ))
http://hp.vector.co.jp/authors/VA010205/
Text imparts all
今日は残りの人生の最初の日 ---from BH90210
I want your indication (君の意見をきこう瘢雹. ガツンと言ってくれ)
I want to hug with you each other
This message is copylefted (see GPL)
68 lovers capable
------------------------------
From: "Don Beaver" <[EMAIL PROTECTED]>
Subject: Final CFP: Crypto 99
Date: Tue, 2 Feb 1999 17:48:08 -0500
CRYPTO '99
August 15-19, 1999, Santa Barbara, California, USA
CALL FOR PAPERS
Original papers on all technical aspects of cryptology are solicited for
submission to Crypto '99, the Nineteenth Annual IACR Crypto Conference.
Crypto '99 is organized by the International Association for Cryptologic
Research (IACR), in cooperation with the IEEE Computer Society Technical
Committee on Security and Privacy, and the Computer Science Department
of the University of California, Santa Barbara. For more information,
access http://www.iacr.org/
INSTRUCTIONS FOR AUTHORS
Authors are strongly encouraged to submit their papers electronically. A
detailed description of the electronic submission procedure can be found at
http://www.iacr.org/conferences/c99/submit.html
Electronic submissions must conform to this procedure and be received by
February 8, 1999, 17:00 EST in order to be considered. Authors unable
to submit electronically are invited to send a cover letter and 22
copies of an anonymous paper (double-sided copies preferred) to the
Program Chair at the postal address below. Submissions must be received
by the Program Chair on or before February 8, 1999 (or postmarked by
January 31, 1999, and sent via airmail or courier). Late submissions and
submissions by fax will not be considered. The cover letter should
contain the paper's title and the names and affiliations of the authors,
and should identify the contact author including e-mail and postal
addresses.
Submissions must not substantially duplicate work that any of the
authors have published elsewhere or have submitted in parallel to any
other conference or workshop that has proceedings. The paper must be
anonymous, with no author names, affiliations, acknowledgments, or
obvious references. It should begin with a title, a short abstract, and
a list of key words, and its introduction should summarize the
contributions of the paper at a level appropriate for a non-specialist
reader. The paper should be at most 12 pages excluding the bibliography
and clearly marked appendices, and at most 20 pages in total, using at
least 11-point font and reasonable margins. Committee members are not
required to read appendices; the paper should be intelligible without
them. Submissions not meeting these guidelines risk rejection without
consideration of their merits. Notification of acceptance or rejection
will be sent to authors by April 22, 1999. Authors of accepted papers
must guarantee that their paper will be presented at the conference.
CONFERENCE PROCEEDINGS
Proceedings will be published in Springer-Verlag's Lecture Notes in
Computer Science and will be available at the conference. Clear
instructions about the preparation of a final proceedings version will
be sent to the authors of accepted papers. The final copies of the
accepted papers will be due on May 28, 1999.
SUBMISSION: February 8, 1999
ACCEPTANCE: April 22, 1999
PROCEEDINGS VERSION: May 28, 1999
PROGRAM COMMITTEE:
Daniel Bleichenbacher, Bell Laboratories, USA
Don Coppersmith, IBM Research, USA
Ivan Damgaard, Aarhus University, Denmark
Ronald Cramer, ETH Zurich, Switzerland
Rosario Gennaro, IBM Research, USA
Andrew Klapper, University of Kentucky, USA
Lars Knudsen, University of Bergen, Norway
Xuejia Lai, r3 security engineering, Switzerland
Arjen Lenstra, Citibank, USA
Andrew Odlyzko, AT&T Labs - Research, USA
Kazuo Ohta, NTT Lab., Japan
Bart Preneel, Katholieke Universiteit Leuven, Belgium
Jean-Jacques Quisquater, Universite Catholique de Louvain, Belgium
Matt Robshaw, RSA Laboratories, USA
Phillip Rogaway, University of California at Davis, USA
Daniel Simon, Microsoft Research, USA
Serge Vaudenay, Ecole Normale Superieure, France
Michael Wiener (chair), Entrust Technologies, Canada
Moti Yung, CertCo, USA
ADVISORY MEMBERS:
Mihir Bellare, Crypto 2000 program chair,
University of California at San Diego, USA
Joe Kilian, Electronic submissions, NEC Research Institute, USA
Hugo Krawczyk, Crypto '98 program chair, Technion, Israel and IBM, USA
ADDRESS FOR NON-ELECTRONIC SUBMISSIONS:
Michael Wiener, Program Chair, Crypto '99
Entrust Technologies
750 Heron Road
Ottawa, Ontario
Canada K1V 1A7
Phone: (1) 613-247-3185 Fax: (1) 613-247-3690
E-mail: [EMAIL PROTECTED]
FOR OTHER INFORMATION CONTACT:
Donald Beaver, General Chair, Crypto '99
CertCo
55 Broad St.
New York, NY 10004 USA
Phone: (1) 212-709-6719 Fax: (1) 212-709-6754
E-mail: [EMAIL PROTECTED]
STIPENDS: A limited number of stipends are available to those unable
to obtain funding to attend the conference. Students whose papers are
accepted and who will present the paper themselves are encouraged to
apply if such assistance is needed. Requests for stipends should be
addressed to the General Chair.
------------------------------
Date: Tue, 02 Feb 1999 11:42:23 -0600
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Random numbers generator and Pentium III
"R. Knauer" wrote:
> On Mon, 01 Feb 1999 17:44:52 -0600, Jim Felling
> <[EMAIL PROTECTED]> wrote:
>
> > On the other hand the odds of
> >such a thing happening will be very low as over a sufficiently long run a TRNG
> >should have nearly perfect properties if E is small enough it will reject very
> >few TRNG's.
>
> It is not so much rejecting properly working TRNGs that is the concern
> as it is not rejecting improperly working ones.
Accepted. ( I just wished to point out that proper testing will reject comparatively
few working generators by chance)
>
>
> >This is also true. You can end up accepting an insufficient generator if it
> >just happens to have really great properties in the run being examined. The
> >probability of this can also be made very low by selecting an appropriate E
> >before running this.
>
> As I read further in Li and Vitanyi's book on Kolmogorov Complexity, I
> am finding that random numbers have all sorts of regularity in their
> substrings.
>
> And the authors point out that characterizing numbers as random using
> stochastic tests only works for algorithmic complexity randomness,
> which is not suitable for proveably secure crypto. Now I am finding
> out that only prefix complexity, K, is strong enough to characterize
> complexity randomness. The usual complexity randomness, C, has
> deficiencies.
>
I, having not read the references being referred to (as of yet) concede the point
for now but I do reserve the right to at a later time after having read the work in
question to quibble with your conclusions. ( it just sounds wrong -- this may be due
to my intuition misleading me though - so I accept yield the point to you
>
> >Also agreed. However, a physical generator is also vulnerable to the
> >arguments being made.
>
> The generator must meet the specifications for a TRNG, or it is not a
> TRNG.
>
> >How can one be certain that one's physical process based
> >generator is not mis calibrated slightly,
>
> By calibrating it carefully.
>
> >or subject to EF noise being leaked
> >into it from another part of the system,
>
> By designing it carefully.
>
> >or doesn't have some internal
> >components being weakly coupled by some electromagnetic effect.
>
> By testing the design carefully.
>
> >One can only
> >state, Based on what I know of equipment and design and the rigorous physical
> >testing process I performed,
>
> That you must do.
>
> >and the rigorous statistical testing of the
> >outputs generated
>
> That is not reliable compared to the tests described above.
I feel that, while it may not be as reliable as the above tests, it is still
something worth doing. Every tool I use to test such a system can only add to my
confidence in the system. There is no excuse for not testing such a system in every
way possible so as to avoid an unanticipated weakness from 'breaking' your system.
>
>
> >that the probability of this device being flawed is less than
> >some arbitrary E.
>
> That value is not a probability which is based on statistical tests of
> the output. The proper analysis is based on the instrument itself.
I feel that such analysis is necessary, but not sufficient to 'certify' such an
instrument. I want to test the output and not merely rely on the 'fact' that this
was a professionally designed machine made to rigorous standards, etc. and unless
things have changed the only tools I have for such testing are statistical.
>
>
> >All we really have for any generator are confidence limits.
>
> That confidence is based on something other than inappropriate
> stochastic theory.
>
I disagree -- how about changing that statement to: That confidence is based upon
rigorous design, thorough review of the design, skilled calibration of the system,
not merely statistical tests.
I feel that any testing that can be done should be done. And if a generator fails
such a test it should be immediately pulled from service thoroughly examined,
calibrated, etc. and then retested and if it passes then allowed back into service.
I would rather pull legit generators every so often for servicing that they don't
need than not pull generators needing servicing. I am also not saying watch the
output constantly and the moment it fails test X pull it I am saying every so often
pull some data for testing, test that data, and if the system fails, service it and
retest. If it consistently fails discard it as the statistical tests are spotting
correlation in its output and I don't want that in my 'secure' bit stream.
>
> >Trusting that one has thought of all possible attacks in the testing and design
> >phase for either a physical or an algorithmic device is self deception.
>
> That's why there are standards committees and beta tests.
>
> >( it is often the unanticipated flaw that gets you)
>
> Then you have to make sure that such flaws do not get into your TRNG.
By definition you will not anticipate the existence of such a flaw. I agree that
design rigor and testing will catch many flaws, but I know from practical
experience, that nothing will catch 100% of them.
>
>
> >and the fact that there is a 1 in
> >1000000 chance that your system is flawed in way X always leaves you vulnerable
> >to drawing the 'lucky' millionth system.
>
> I'll take those odds any day.
>
So will I, but give a choice between 1 in a million and one in a billion chance of
failure I know which I'd choose.(assuming that the associated costs were reasonably
close)
>
> Anyway, the TRNG can be designed to fail into a known state if it acts
> out of specification.
Always?!??
How is this accomplished with 100% reliability?
I agree such a mechanism can be implemented for many failures, but I would be very
surprised if such a mechanism existed which would drive the system to a known state(
or set of known states) in the event of any failure.
>
>
> >No system should be regarded as
> >secure without a thorough exam of its components, and a thorough testing and
> >evaluation process having been performed on its outputs.
>
> Characterizing the proveable security of a TRNG using statistical
> tests is not part of that evaluation.
Ok, then how do you test your device as it runs? How would you determine whether
your device is a working TRNG, and not a poor substitute( whether due to design
flaw, sabotage, miscalibration, or accident)?
>
>
> >> Unfortunately algorithmic conplexity is unsuited for crypto-grade
> >> randomness..
>
> >Why? I agree that it is harder to make use of than other forms, but that still
> >does not make it useless.
>
> In a uniform distribution there are "regular" and "complex" strings.
> Algorithmic complexity rejects "regular" strings - and that rejection
> is not permitted in the specification for a TRNG.
I agree one should not reject any strings (either use or do not use the device) --
but one should still evaluate the device.
>
>
> The fact that the fraction of regular strings that are rejected is
> very small for long strings does not change the fact that for a
> proveably secure system you cannot reject any strings.
>
> >Depends on your filtering methodology. Any bijection can be applied to random
> >values without destroying randomness
>
> I do not understand the term "bijection". Is it a typo?
No. A bijection is a function that maps a space to itself in a 1 to 1 and onto
manner.
>
>
> Whatever the terms meand, any filtering of strings is unsuitable for
> the OTP system. The output of the TRNG must not be filtered.
>
> >and there are information reducing
> >methods (such as take n bits of output, compute the parity (m) of that n-bit
> >value, output the m, discard the n bits -- or discarding every non-prime
> >numbered bit of output ) that will also preserve randomness while potentially
> >strengthening your system against certain potential avenues of attack.
>
> Any tampering with the strings is not permitted if you are to be
> compliant with the TRNG specification. It is that specification which
> is necessary for proveable security.
if i use either of the two methods shown above, in what way is my output going to
be made less random? How do either of the above methods fail to preserve randomness?
>
>
> >I agree that if you modify the probability of any string showing up in the
> >output this exposes you to potential attacks, but not all filtering will do
> >so.
>
> Any filtering has the potential to do so and is therefore not
> permitted.
>
Wrong. I agree that rejecting strings based upon criteria is bad, but there are
methods that can be used to correct possible bias. that are of use.
>
> Bob Knauer
>
> "Sometimes it is said that man cannot be trusted with the government
> of himself. Can he, then, be trusted with the government of others?"
> --Thomas Jefferson
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: Truth, theoremhood, & their distinction
Date: Tue, 02 Feb 1999 18:30:38 -0500
R. Knauer wrote:
>
> On Tue, 02 Feb 1999 13:37:25 -0500, Nicol So <[EMAIL PROTECTED]>
> wrote:
>
> >There is no technical definition for correctness of interpretation,
>
> I would ask you to comment on Solomonoff's induction model. I am
> working my way towards an exposition of that in Li and Vitanyi's book
> on Kolmogorov Complexity, and the authors have hinted that they will
> show that Solomonoff's system of inference yields "correct"
> interpretations (hypotheses), much more correct than those obtained by
> by other systems of inductive reasoning, like Occam's Razor or
> Bayesian inference.
I'm not familiar with Solomonoff's induction model, so I can't comment
on it intelligently. But judging from what you wrote, it seems that we
are using the term "interpretation" to mean very different things.
Sometimes the same term is used in different branches of knowledge to
mean different things, and I suspect that this is a case of it. The
subject matter of this thread (and of my earlier messages) is about the
distinction between truth and theoremhood in relation to sentences. It
is not about inductive reasoning. Actually, you can say that our
subject matter is more related to the other kind of reasoning,
deduction, since proof systems are tools for making logical consequences
of axioms explicit by means of symbolic manipulation. Another hint that
we're talking about different things: you mentioned hypotheses alongside
interpretations. "Interpretation", as the concept occurs in
mathematical logic, is not related to any "hypotheses", not in any
obvious way, and certainly not in the way what you seemed to have
suggested in your writing.
I'm under the impression that when it comes to mathematical logic,
different groups of people use slightly different terminologies and
notations, although they deal with aspects of the same subject matter.
By different groups, I mean people like philosophers, mathematicians,
and computer scientists. Despite the diversity, the term
"interpretation" as I used it is very standard.
Nicol
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: Truth, theoremhood, & their distinction
Date: Tue, 02 Feb 1999 18:58:31 -0500
Vladimir Patryshev wrote:
>
> > Again, this has nothing to do with the distinction between truth and
> > theoremhood, but let me ask: how do you define the concept of a set (or
> > the concept of set membership)? You can, of course, define concepts in
> > terms of simpler ones, but eventually the process needs to "bottom out"
> > and you need to use some other means to capture the essence of a
> > primitive concept. The notion of a set is a prime example of a concept
> > not defined in terms of simpler ones.
>
> Why? It is defined as an element of a model of a set theory.
I guess our difference in opinion, if any, is whether that constitutes
"defintion in terms of more primitive concepts", which is the crux of
the question.
Nicol
------------------------------
** 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
******************************
