Cryptography-Digest Digest #61, Volume #13 Tue, 31 Oct 00 19:13:00 EST
Contents:
Re: Psuedo-random number generator (Terry Ritter)
Re: On introducing non-interoperability (wtshaw)
Re: 3-dimensional Playfair? (Mok-Kong Shen)
Re: Is RSA provably secure under some conditions? (Bryan Olson)
Re: Open Request to Dr. Kaliski, Jr. at RSA Research - looking for your Thesis!
("binary digit")
Re: Give it up? (Mok-Kong Shen)
Re: Is RSA provably secure under some conditions? (John Myre)
Re: Is RSA provably secure under some conditions? (John Myre)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Psuedo-random number generator
Date: Tue, 31 Oct 2000 23:09:32 GMT
On 31 Oct 2000 13:34:03 GMT, in <8tmhob$aad15$[EMAIL PROTECTED]>, in
sci.crypt [EMAIL PROTECTED] (Rob Warnock) wrote:
>Terry Ritter <[EMAIL PROTECTED]> wrote:
>+---------------
>| [EMAIL PROTECTED] (Rob Warnock) wrote:
>| >Actually, synchronization steps are probably the only place in
>| >a computer you *can* get true quantum randomness. ;-} ;-}
>| >... the probability of the
>| >synchronizer "settling" to a definite state (a hard "1" or "0")
>| >during any subsequent discrete interval is a true random process.
>...
>| I have never imagined that anyone would think of *using* metastable
>| operation for something.
>+---------------
>
>Well, here's at least one reference [actually, several abstracts]:
>
> <URL:http://www.imse.cnm.es/~barriga/absdigit.htm>
> ...
> Bellido,M.J., Acosta,A.J., Valencia,M., Barriga, A. and
> Huertas, J.L.: "Simple Binary Random Number Generator".
> Electronic Letters,vol. 28, No. 7, pp. 617-618, Mar. 1992.
> "A random number generator based upon forcing metastable operation
> in a CMOS latch is presented. Sequences produced by this generator
> have passed standard tests, exhibiting a reasonable random behaviour."
>
> Bellido, M.J., Acosta, A., Valencia, M., Barriga, A.,
> Huertas, J.L.: "A simple binary random number generator:
> new approaches for CMOS VLSI". 35 th MIDWEST Symp. on
> Circuits and Systems, pp.127-129, Washington, Aug. 1992.
> "Random number generators (RNGs) based upon metastable operation in
> a CMOS latch are presented. Some different techniques to force
> metastable operation and detect the final state are also reported.
> Many prototypes have been integrated and sequences produced by
> these generator have passed standard tests, exhibiting a good
> random behavior."
> ...
Thank you. You are of course aware that I maintain a literature
survey on physically random generators:
http://www.io.com/~ritter/RES/RNGMACH.HTM
If you have any others, I would love to see them too.
>+---------------
>| First, I am unaware of any parts which have specified and therefore
>| predictable metastable operation.
>+---------------
>
>You must not have looked lately. While it is true that several decades
>ago it was hard to get such information, for at least the last decade
>manufacturers have been characterizing their synchronizer latches and
>publishing the results -- especially for their "metastability-hardened"
>designs. The standard parameters are usually "tau" and "T0" (and sometimes
>"D0" or "T1"), where the failure rate for the latch failing to settle
>within "t" after the clock is given as Pfail(t) = Fd*Fc*T0*exp(-(t-D0)/tau),
>or expressed as an MTBF:
>
> (t-D0)/tau
> e
> MTBF(t) = ------------
> Fd * Fc * T0
>where:
>
> Fd = average frequency of transitions on the data input
> Fc = clock frequency
> T0 = the "real" (as opposed to published!) difference between
> the setup & hold time, that is, the window of vulnerability
> for *entering* the metastable state
> D0 = base constant or irreducible delay in the latch [sometimes
> set to zero by artificially bloating up the value of "T0"]
> tau = how much you have to increase the settling time "t" to
> reduce the failure rate by a factor of 1/e, that is, how
> long it will (probably) take to *exit* the metastable state,
> once entered. [Tau is inversely related to the gain-bandwidth
> product of the core latch, among other things.]
>
>Look in the "synchronizer cell" descriptions in any modern ASIC library,
>and you'll find the above specs (or something similar from which tau & T0
>can be derived).
Interesting.
>+---------------
>| the characterization of particular parts from particular lots from
>| particular manufacturers, who could change that operation at any time.
>+---------------
>
>That's true, but now that the problem is "out in the open" (where it
>wasn't at one time -- manufacturers didn't want to admit that true
>randomness existed!), they keep that info as up-to-date as any of
>the rest of the specs.
>
>+---------------
>| Second, the probability of encountering metastability (other than a
>| deliberate attempt) is very, very low.
>+---------------
>
>The probability is *NOT* "very, very low" if the clock and data rates
>are very, very high!! See the above formula.
I suppose if the logic is operating almost flat out, the metastable
window may loom large. But this is, of course, nowhere near the
normal case of logic design. It instead assumes a special design
specifically intended to emphasize the metastability problem.
>+---------------
>| This is a very inefficient way to encounter quantum randomness.
>+---------------
>
>See what I said above about designing a feedback loop to *force*
>the data edges into the "T0" band. My guess is that you could create
>a metastable event on a high fraction of clock edges, at least 10% if
>not more.
That sounds high to me.
But one implication of that is that noise is causing problems. If
there were no noise, we should be able to enter metastability almost
deterministically, given appropriate stimulation. The implication for
me is that noise *is* a significant issue.
And then we have to consider the effect of feedback on inter-bit
correlations.
>With a 33 Mhz clock (a *low* rate today), that's at least
>3 mega-metastables per second, each of which could produce *at least*
>one random bit (perhaps even two or three). Efficient enough?
Yes, that's a nice data rate. But simply *saying* that metastability
is "random," or simply *measuring* the result with standard randomness
tests is by no means enough.
As far as I can see, either we believe that metastability depends upon
quantum phenomena or not; if so, that must be thermal noise. If not,
there is no quantum source, and we have confusion, not randomness.
>+---------------
>| Third, as I recall, the length of the metastable period is something
>| like a negative exponential:
>+---------------
>
>The exact formula is given above. But the length per se is not a
>negative exponential. Rather, the "metastable exit" probability is
>a *constant*, which means that the probability of exceeding some
>specified length is a negative exponential function of the length.
>[Yes, that's a quibble, but an important one if you're trying to
>extract more than one bit of randomness per metastable event...]
>
>+---------------
>| very long metastable periods are very, very, very rare. Most metastability
>| occurs in short transients and may not cause problems, and so may not be
>| noticed at all by normal circuits.
>+---------------
>
>Not so. All you need is for the decision to be delayed long enough to
>penetrate the critical setup/hold window of the following stage. If your
>design is running close to the limits of propagation time for its clock
>rate (that is, there is very little "timing margin" -- which is almost
>always true for any economical design!), even the slighest additional
>metastability-induced delay can cause the following logic to fail
>catastrophically.
Not necessarily. Probably the main need to latch and re-time truly
asynchronous data occurs in data communications. But if the data are
wrong due to metastability, error-detection generally finds that an
error happened and we try again. This is a system success, not a
failure, let alone a catastrophe. Probably we would not even know the
source of the problem, since legitimate communications errors would
produce the same effect.
I'm not even convinced that metastability is inherent in all
asynchronous interfacing. I could imagine a communications system
with a PLL to track the remote clock. Then I can imagine depending
upon some sort of First-In-First-Out (FIFO) to take data (only when
ready!) from the source, and deliver it (only when ready!) to the
sink. The FIFO itself could be arranged to have "plenty" of time for
every decision, and so to never encounter metastability itself. It
may be that similar or other solutions do in fact exist.
Presumably you are talking about processor instructions, and even in
that case one can very well have a transient error without crashing
the system. A scientist might well prefer that the system actually
crash, of course, but that may not be what they get.
>Consider the output of a synchronizer going into two other inputs, one
>of them through an inverter. A static logic analysis will assume that
>the following inputs *always* have opposite values at the next clock
>edge, but due to metastability-induced delay one input might see a change
>while the other (the one through the inverter) doesn't -- *WHAMMO!*
>Suddenly you have two parts of your logic with inconsistent states in it.
>[This *is* a real problem. I've been bitten by it myself, long ago.]
Well, yes, but real logic analysis is dynamic, not static. There is
*always* a delay through an inverter, and, depending on layout, that
could be larger than one might expect, and it will vary over process,
supply and temperature variations. We don't need to introduce the
metastability bogeyman to see problems. And if we include sufficient
time for each logic chain to stabilize before we latch, we avoid
metastability as well.
Metastability is mostly an issue when we re-time truly asynchronous
data by latching. We rarely allow synchronous timing to get close
enough for metastability to happen, because if we did, we would be
just a slip away from a logic timing failure anyway.
>Allowing enough time for reliable synchronization SLOWS THE LOGIC DOWN,
>so ignorant or skeptical designers unfortunately sometimes try to "cheat
>Mother Nature"... and fail.
>
>+---------------
>| >...but you can never reduce the incidence of synchronizer failure
>| >to zero. [However, modern hardened synchronizers have an MTBF of
>| >many centuries, so for all practical purposes, it's a solved problem.]
>|
>| Right. So why are we talking about it?
>+---------------
>
>Because you can just as easily "unsolve" it, and thereby create a
>source of true random numbers!! Basically, you build a "synchronizer
>failure detector", and use feedback from it to tune a variable delay
>line (or equivalent) so that nearly every data edge falls right *in*
>the critical window. [This is the same kind of circuit that those
>"lab-bench testers" use.] The old Cheney & Molnar papers showed that
>once the metastable state was entered there was a fairly long time
>during which the the probability of exiting was fairly uniform (followed
>by a rapid exponential tail). If you chop up the results from each
>measurement into a bunch of "buckets", you should actually be able
>to get *more* than one random bit per metastability event -- probably
>megabits per second of truly random bits.
How do you *know* they are "truly random"? Where do you think this
true randomness comes from? Where is the linkage between a quantum
event and the resulting random value? What quantum event causes
metastability to terminate? If there is such an event, what could
that be *other* than analog noise? What else is there?
>+---------------
>| >Anyway, the point is that by using a bunch of different frequency
>| >sources and synchronizing data passing through multiple clock domains,
>| >one can *deliberately* generate genuinely random data,
>|
>| At this level of criticality, it is likely that thermal-based noise
>| plays a significant role in allowing or preventing metastability from
>| occurring.
>+---------------
>
>Not quite. Thermal noise does not *prevent* the metastability from
>occurring, though it certainly does have a strong role in helping
>the latch *exit* the metastable state, once entered -- and that's
>exactly what you exploit when creating a metastability-based RNG.
I don't agree at all: Metastbaility *is* the occurrance of a precise
*intermediate* level at a precise time. If there were no noise
involved, we could trigger metastable operation deterministically. I
don't think we can, and if we can't, noise is why.
>+---------------
>| It would be far easier to just work with the noise.
>+---------------
>
>Maybe, maybe not. Normal analog "noise generators" are *very* sensitive
>to coupling of power-supply transients into the noise source, and thus
>contaminating the resulting random stream.
Surely you are aware of my extensive characterization of various noise
generators, using a PC sound card for detection and digitization:
http://www.io.com/~ritter/NOISE/NOISCHAR.HTM
The above has 25 subpages, each of which contains 3 graphs, including
FFT, autocorrelation and normal distribution results. Most common
statistical measures are also computed.
NONE of the noise generator characterization data shows any tendency
toward 60 Hz or 120 Hz signals, and the distribution analysis for the
best designs is entirely consistent with a hypothesis of a quantum
noise source.
When I use a 9 V. battery to run the noise source, and put the whole
thing in a ferrous and conductive "tea tin," I don't expect to see
much interference getting through on that end. No doubt there is some
interference at some level, even if only on the sound card, but the
experimental evidence does not reveal it, and there is no reason to
believe it plays any significant role.
In general, the analog sampling of random noise appears to be a very
attractive approach. I would have to see a great deal of metastable
characterization before I found that nearly as believable.
>While metastability-based RNGs
>are certainly also somewhat susceptible to power-supply coupling, the
>fact is that in a metastability-based RNGs the "thermal noise" is in the
>*time* domain, not the analog voltage domain (at least, not externally),
>and is thus somewhat less bothered by power-supply fluctuations.
I do not agree. Metastability requires *both* a precise level, and a
precise relative time. Thermal noise on the metastable device is
analog noise the way it always was. I expect to see a strong
variation between supply voltage and the position of the metastable
window. I expect supply variations to affect the metastable rate, and
possibly even affect the distribution of metastable results.
Nothing like that is really an issue with a noise-based generator.
>+---------------
>| >- for one thing, you have to
>| >make sure that the different oscillators aren't coupled, or you'll
>| >get "locking" effects -- but it can be done without too much pain.
>| >People who design & test synchronizers do it all the time...
>|
>| But we aren't talking about synchronizers in a test jig, surrounded by
>| precision measuring equipment with repeated stimulation in the
>| critical region. We are talking about ordinary synchronizations, in
>| practice, in a conventional working system.
>+---------------
>
>I addressed that in my other posting, in which I apologized for implying
>that I might have been taken as suggesting using the synchronizers
>that are already "lying around" in a clone PC. I was (and am) really
>talking about synchronizers explicitly *designed* as RNGs, that just
>happen to use metastability as the source of quantum randomness. Today,
>that woul have to be done as an add-on card.
>
>However, if people feel it's important to have large numbers of true
>random numbers available ubiquitously, and lobbied for it enough to
>the clone PC makers, such a logic block *could* be easily stuck in
>a corner of any commodity PC chip set. It would add "zero" (roughly,
>discounting the NRE of the IP) to the cost of the system.
I think there are two issues in any such device:
1) there should be a direct and obvious relationship between some
quantum source and the randomness we collect. Naturally I know noise
generators better, but I think metastability would have to go some to
catch up on this.
2) There should be a way to "turn off" or "hide" the quantum source
from the detection mechanism. It is necessary to be able to show that
the results come from the quantum source, and not from the detection
system itself. Not yet having seen the references, it appears to me
that the metastable system would tend to combine the source with
detection, so we are less sure from where the "randomness" comes. And
if it does not come from a quantum source, we simply don't expect it
to be particularly random. Pseudorandom generators do very well on
statistical tests.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: On introducing non-interoperability
Date: Tue, 31 Oct 2000 16:47:35 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> The idea is to obtain a system that differs from the
> one the opponent has at hand. If the key scheduling
> is modified, he wouldn't be able to do brute force,
> for example.
>
> M. K. Shen
This depends on the real keyspace being greater than the utilized
keyspace. Better use of keyspace is more efficient, i.e., more keys per
size, but better is better potential keyspace to begin with.
--
Pangram: Move zingy, jinxed products; hawk benign quality fixes.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: 3-dimensional Playfair?
Date: Wed, 01 Nov 2000 00:24:43 +0100
John Savard wrote:
>
[snip]
> Something more closely analogous to Playfair would be less secure than
> that, as it wouldn't change which coordinate any digit applied to, and
> so with only three digits, and with the extra complexity, it hasn't
> been tried that I've heard of.
Has Playfair ever been (in modern times) practically applied
to an alphabet of 256, i.e. 8-bit values? I am just curious.
M. K. Shen
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Tue, 31 Oct 2000 23:28:07 GMT
David Wagner wrote:
> Roger Schlafly wrote:
> >Which is why these folks shouldn't be claiming that they have proofs.
>
> Is it acceptable to claim you have a proof when what you really mean
> is that you can prove it secure under the assumption that factoring is
> hard?
>
> - If yes, then why not under other assumptions, too?
>
> - If no, then note that there are no encryption systems with proofs
> (excluding the one-time pad), so your criticism is not specific to
> the random oracle model but applies to a vast field of theoretical
> work in cryptography.
How about: "depends on the audience"? The goal is to
communicate efficiently without deceiving people. When
talking to cryptologists who are familiar with these
reductions, "proof" is appropriate. If they want to know
what problem was reduced to violating what security
property, they'll ask.
Telling a lay audience that Rabin encryption has been proven
secure is cryptologic malpractice. When I've heard people
who actually do these proofs talk to laymen, they've
invariably done a good job of describing the state current
knowledge. I think most of the bad usages come from people
trying to nutshell results that they don't really
understand.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "binary digit" <[EMAIL PROTECTED]>
Subject: Re: Open Request to Dr. Kaliski, Jr. at RSA Research - looking for your
Thesis!
Date: Tue, 31 Oct 2000 23:59:24 GMT
http://theses.mit.edu/Dienst/UI/2.0/Composite/0018.mit.theses%2f1988-88/1?ns
ections=8
"John A. Malley" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Dr. Kaliski,
>
> Can you help me find an electronic/on-line copy of your MIT PhD Thesis,
> "Elliptic Curves and Cryptography: A Pseudorandom Bit Generator and
> Other Tools", dated January 1988? I'm researching an interesting
> problem in PRNG with elliptic curves and my search lead to your thesis.
> Unfortunately MIT did not post an electronic copy of it. And a trip to
> Boston is right out. :-)
>
> No email address is given for you at RSA Labs, hence my appeal via this
> USENET group.
>
> Mr. Silverman, should you read this, would you be so kind as to relay my
> request to Dr. Kaliski?
>
>
> Thank you in advance,
>
> John A. Malley
> [EMAIL PROTECTED]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Date: Wed, 01 Nov 2000 00:58:17 +0100
Tom St Denis wrote:
>
> Here is all you need to know about communication topology.
>
> Secrecy -> Cipher
> Efficiency -> Codec
>
> Codec != Cipher.
Questions: (1) 'Topology' has a time-honoured and well-
established meaning. How does the above conform to that?
(2) Are you saying that one can't extremely increase the
strength of a cipher and yet remain very efficient like
one can't have a racing car at very low price, or do you
want to express some other novel idea? Thanks.
M. K. Shen
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Tue, 31 Oct 2000 16:55:22 -0700
Bryan Olson wrote:
<snip>
> How about: "depends on the audience"?
<snip>
> I think most of the bad usages come from people
> trying to nutshell results that they don't really
> understand.
<snip>
Better answer than mine. Thanks.
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Tue, 31 Oct 2000 16:52:16 -0700
Roger Schlafly wrote:
>
> Shai Halevi wrote:
<snip>
> > Admittedly, this is a contrived example. But it demonstrates that a
> > proof of security in the random oracle model is not an ironclad
> > argument.
>
> Which is why these folks shouldn't be claiming that they have proofs.
> They just sound like the snake-oil peddlers.
That's a little harsh. If you go that far, you might as
well say that no one has a proof of anything: there's no
such thing as a formal system with zero assumptions (there
have to be axioms, at least!).
I suppose you could say that popularizations of proofs are
bound to be misleading, in which case perhaps popularizers
ought to be careful in what they say, but that's not a reason
for blaming cryptographers for publishing proofs in the first
place. The proofs *are* meaningful if you understand the
formalisms, and what is science but the attempt to extend
the boundaries of what is understood?
JM
------------------------------
** 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
******************************
