Cryptography-Digest Digest #422, Volume #12 Fri, 11 Aug 00 22:13:00 EDT
Contents:
Re: 1-time pad is not secure... ([EMAIL PROTECTED])
Re: chap authentication scheme? (Cryptocol)
Re: chap authentication scheme? (Cryptocol)
BBS and probabilistic proofs (David Hopwood)
Re: 1-time pad is not secure... ("Douglas A. Gwyn")
Re: OTP using BBS generator? (lcs Mixmaster Remailer)
Re: 1-time pad is not secure... ("Douglas A. Gwyn")
Re: 1-time pad is not secure... ("Douglas A. Gwyn")
Re: 1-time pad is not secure... ("Douglas A. Gwyn")
Re: 1-time pad is not secure... ("Douglas A. Gwyn")
Re: 1-time pad is not secure... ("Douglas A. Gwyn")
Re: idear for new cipher ("Douglas A. Gwyn")
Re: Explain S-boxes please (tomstd)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 1-time pad is not secure...
Date: Sat, 12 Aug 2000 00:19:21 GMT
Over 80 messages in this thread in less than 2 days. I'm really
stunned. Am I breaking a record?
In article <8n13up$l6f$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> In article <8mth1u$vpt$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Here's a different viewpoint.
>
> Thank you for this "viewpoint". I think the rest of the world
> will see it for what it is; hand waving gibberish.
If you call it gibberish, that means I have to explain it to you in
more details.
I'm not the only saying this. Putting all else aside, the security of
OTP is based on how well you can generate random numbers.If, for any
reason, from advanced physics to careless workers, that the key
generation process is biased, OTP is the LEAST secure (among those
used) because of the huge key. No one seems to deny that!
> Fortunately, mathematics does not depend upon what *you* think, but
> upon what can be proved.
Mathematics depends on a bunch of AXIOMS. That's the first thing I
learned in the first course of Mathematics.
> > But can you prove that random numbers really exist? No.
>
> False. Read any book on probability theory.
Also false. Any probability thoery book does not prove that random
numbers exist. Randomness is assumed to exist; and then an entire field
is built on top of this assumption.
> > Can you generate truely random numbers? No.
>
> False. Radioactive decay and quantum processes are truly random.
> So is e.g. thermal noise from a diode.
If you look at each individual event, it seems random. But if you look
at a large group of events, they follow a certain pattern. That's not
random.
>So are distribution of quadratic residues of a large prime.
But you can't prove it...
> Furthermore, for a OTP to be secure it isn't necessary to generate
> a sequence of 'truly' random numbers. It is only necessary to
> generate a sequence which *CAN NOT BE DISTINGUISHED FROM TRULY RANDOM
> by a COMPUTATIONALLY UNBOUNDED ADVERSARY*.
That's what I'm saying all along. OTP is only computationally secure,
based on how well you can generate random numbers. If you are the
resourceful ones using obscure methods to generate random numbers, you
may be safe for a long while until someone figures out how to break it.
If you are not, better not trust OTP with all your heart.
> > It's like 1/x tends to zero but you'll never get zero, if you use
> > enough bytes to hold the number.
>
> This is gibberish.
Not everyone understands my jokes or analogies. I don't blame you. :)
What I mean is you'll never get a truely random number, like you'll
never get an x large enough so that 1/x is zero. For example, one day
we'll move on to nanocomputers, then current RNGs will not be random
any more.
Side Note: Somebody mentioned that infinity will be reached if we count
all the matters/substance to exhaustion. I'm just curious: If all the
"substance" is used to encrypt a message, then how do you decrypt it?
Another side note: How come nobody has brought up anti-matters yet?
It's so cool. :) Light -- photon -- is an anti-matter. Our
understanding on antimatters is at the beginning stage. Maybe be some
antimatters can travel faster then others. And then some smart kids,
probably genetically-engineered, will show that antimatters have
sub-antimatters...
> > One-time pad is only computationally secure, no difference than any
> > other systems. The key-generating process may be duplicated, if not
> > exactly, to some probability.
>
> "some probability" here is exponentially small in the length of the
key,
> i.e. you can duplicated a k-bit key with probability no more than
> 1/2^k. This is indistinguishable from 'truly random' even by an
> unbounded adversary.
>
> > Get the picture? You can duplicate the key-generating parameters:
> > computer model, OS, PRNG, date, time, location, hardware, software,
> > room temperature, humidity, magnetic field... The list goes on and
on.
> > Then the longer the key, the higher possibility that you'll get
> > something right.
>
> Yes, there is a significant probability that you can guess some
> sub-portion of the key. The problem with this is that even if you do,
> you can not know that you HAVE GUESSED CORRECTLY.
With OTP, you can try it on the ciphertext at different locations.
You'll get meaningful plaintext if it's in ascii. If not, you'll have
to do more work, but it still gives you an advantage over pure
guessing. See that's another problem with OTP. The verification process
is too simple!
BTW, I'm moving on to the next chapter. Has RSA been broken yet? (If
you're the real Bob Silverman, maybe you can tell me some first-hand
info? :) ) And Somebody please update the FAQ asap! The current one is
like a century old. Thank you!
--Sisi
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Cryptocol)
Date: 12 Aug 2000 00:30:47 GMT
Subject: Re: chap authentication scheme?
David Hopwood wrote:
>Taekyoung Kwon wrote:
>> [protocol run]
>> 1. Server sends his random challenge to Client.
>> ALICE <--- g^x --- BOB
>>
>> 2. Client responds to Server
>> ALICE --- g^y, (g^xg^v)^y ---> BOB
>
> ALICE --- 1, 1 ---> BOB
>
>> [how it works]
>[...]
>> Step 2.4: BOB computes {(g^xg^v)^y}^X and compares it to g^y.
>
> BOB computes 1^X and compares it to 1.
>
>> [for the amplified password proof]
>> http://eprint.iacr.org/2000/026
>
> I think you must have missed something out from the protocol (a check
> that g^y is of large order, maybe?)
>
>- --
>David Hopwood <[EMAIL PROTECTED]>
Yes. ;) I missed several things such as a safe guard but I think we don't need
it at least for g^y if we make h(g^y) rather than g^y. --> it must reduce the
communication cost too. By the way, the above protocol, so-called A-CHAP, is
not secure at all. I already posted it in the morning. Yesterday, I just
proposed it abruptly for Mr. Unruh who was struggling against the restricted
environment but I think it was not a good proposal. A-CHAP is totally useless
if BOB is not really BOB. Morevoer, it makes salt useless. I just thought that
making a secure password protocol using two messages is just similar to making
a safe car using two wheels. :) Can we do it? ;)
(For the details of AMP not for the above protocol, please read the paper at
http://eprint.iacr.org/2000/026, whenever you can get around to it.)
------------------------------
From: [EMAIL PROTECTED] (Cryptocol)
Date: 12 Aug 2000 00:40:51 GMT
Subject: Re: chap authentication scheme?
Addition to the above message:
Sorry, Mr. David Hopwood was right. A safe guard is necessary even for h(g^y)
:)
h(1) or not...
------------------------------
Date: Sat, 12 Aug 2000 13:34:09 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: BBS and probabilistic proofs
"Trevor L. Jackson, III" wrote:
> It may indeed be a terminology issue. Since the issue is an interesting one it
> would be worth clarifying the terminology in order to eliminate terminological
> artifacts of the discussion. To that end, permit me to suggest a scenario into
> which you may poke holes.
>
> For discussion purposes only I'll use simple numbers. Feel free to correct
> them if they are not adequately representative.
>
> Assume the existence of a BBS generator that has a large number of cycles
> (~2^256) but (simplifying) a bimodal distribution of sequence lengths such that
> the cycles are either long (>2^128 length) or short (<2^32 length). Assume
> also that the long cycles far outnumber the short cycles, having a ratio of
> 2^224:1.
Do you mean 2^224 distinct long cycles for each short cycle, or 2^224 elements
that are on long cycles for each element that is on a short cycle? I'll assume
the latter.
> Hopefully this elementary example captures the nature of BBS usage.
>
> Now if a key is selected from the total space of possible keys it will produce
> a long cycle with odds 2^224:1. Certainly those odds are good enough for any
> use I can imagine. Given some samples from the sequence, the BBS proof shows
> that it is not possible to predict the sequence.
Yes.
> However, if I happen to select one of the few short cycles then it will be
> possible to predict the sequence by traversal.
Yes, this happens with probability 2^-224 (which I assume everyone can agree is
negligable?)
> Thus if I select a key and do not check it for shortness I'm vulnerable to a
> prediction by traversal.
With probability 2^-224 (for each key selection).
> Thus the opponent with not have to use a technique that requires
> QR decidability.
The assumption in the 1982 BBS paper is that the Quadratic Residuosity Problem
cannot be feasibly solved with probability significantly greater than chance [*]
for some non-negligable proportion of seeds. That is what "deciding quadratic
residuosity" means. Therefore, the fact that with negligable probability, an
attacker can factor (whether by looking at cycles or more directly), and hence
decide QR, does not contradict the assumption.
Note that it can be easily proven that seeing the output or partial output of
BBS as generated by a user, does not help the attacker to factor with any
higher probability than he/she would have been able to do otherwise, since
the user need not use any knowledge of the factors in generating the sequence.
[*] The answer to any particular QR problem can be guessed with probability
1/2; roughly speaking, the problem that BBS is shown to be polynomially
reducible to in the 1982 paper, is to be able to find the answer with
higher probability than this. A Crypto '84 paper by Vazirani and Vazirani
strengthens this to show that predicting BBS is reducible to the Integer
Factorisation Problem (which also has an inherently probabilistic definition).
> Resolved: one can conclude that the odds [against] selecting such a key are
> enormous,
Yes.
> but one cannot conclude that predicting a BBS sequence requires QR decidability
> if the sequence to be predicted can be predicted using an alternate mechanism
> (traversal).
This seems to be a terminological issue as to the definition of decidability.
--
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
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Date: Fri, 11 Aug 2000 21:17:34 -0400
jkauffman wrote:
> ... Future research may show the apparent randomness in QM to be
> explainable in terms of hidden variables, ...
The current state of our knowledge about this is that any hidden
variables that might "exist" must produce exactly the same effects
as true randomness. Which operationally is the same as saying
that there are no hidden variables. This has been subjected to
experimental test (Bell, Aspect, and all that).
> and your measuring equipment was absolutely perfect,
> measured the underlying phenomenon to arbitrary precision,
> and introduced no bias to the results due to manufacturing
> imperfections whatsoever?
It is absolutely standard scientific procedure to take into
account the characteristics of the apparatus. Perfection is
not necessary, and it is insane to require it. There are also
well-understood (provable) procedures for removing stationary
bias from a random bit stream.
Basically, the fellow who said we couldn't get genuine
randomness from physical phenomena was mistaken. Unless
he has deeper insight than the people who do this for a living.
Does that really seem to be the case?
------------------------------
Date: 12 Aug 2000 01:20:18 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Trevor Jackson wrote:
> lcs Mixmaster Remailer wrote:
> > Consider two RSA creators. One chooses an RSA modulus and lets the
> > attacker try to factor it. The other chooses an RSA modulus and then
> > sends random large integers to the attacker, which the attacker may
> > use to try to help him with factoring.
>
> Up to this point I follow your argument, but at this point there's a gap. It
> sounds to me that the "random larger integers" sent to the second attacker
> are, for exampe, RSA ciphertexts produced by the second creator. Is this
> correct or did you mean "random large integers" literally?
No, "random large integers" was meant literally. That's exactly what the
BBS seed is. It's not chosen with knowledge of the factors of the RSA
modulus. You can do BBS just fine by forgetting the factors as soon as
you've generated the modulus. All this worry about seeds "leaking" the
factors is absurd, which the present analysis is intended to show.
To reiterate, users need not worry about a random integer leaking their
RSA factors. For the same reason, they need not worry about a random
BBS seed leading to a short cycle, or to a predictable sequence.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Date: Fri, 11 Aug 2000 21:20:07 -0400
Guy Macon wrote:
> Speaking as someone who does this kind of measuring for a living,
> I can with confidence set an upper bound for such non-random
> environmental interference.
Indeed, even with systematic and environmental factors active,
the randomness is quite striking.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Date: Fri, 11 Aug 2000 21:36:05 -0400
Simon Johnson wrote:
> I query this...... Radioactive decay can be described by a
> Expodential Curve, and is therefore is not strictly speaking
> random.
Exponential, and you are confused about the meaning of "random";
maybe you're thinking of "uniform random". The inter-event time
for radioactive decay, which is a random variable, is described
by an exponential probability distribution. The key word here is
"probability". The actual issue is whether or not that stems
simply from incomplete knowledge of all the detailed causal
factors versus whether complete knowledge of that kind is
unattainable even in principle. (Of course it is unattainable as
a practical matter.)
Have you seen the TV commercial where the price of a car is
represented by a long balloon, with different segments labeled
"trade-in allowance", "dealer markup", "finance charges", etc.?
The idea is that by squeezing down on one item you automatically
inflate some other item(s). There is a similar physical principle
(named after Heisenberg) wherein increasing knowledge of one aspect
of a physical system automatically reduces knowledge of some other
aspect of the system. This uncertainty is fundamental (basically
it can be seen mathematically as a property of Fourier transforms)
and unavoidable. It's basically what is behind randomness at the
quantum level, or at least it's essentially the same feature.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Date: Fri, 11 Aug 2000 21:39:10 -0400
Guy Macon wrote:
> So why haven't you published it yourself on the Internet?
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: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Date: Fri, 11 Aug 2000 21:46:53 -0400
"Trevor L. Jackson, III" wrote:
> The speed of propagation of electromagnetic energy is derived from
> the two fundamental properties that describe electromagnetic fields
> in space. IIRC its permeability and permittitivity. Are you
> claiming the exact match of the speed of light and the limit
> velocity for mass is a coincidence?
No, it's certainly not a coincidence. In fact, if you consider
photons to be "pure energy", i.e. no rest mass, it follows
immediately from simple special relativity that they have to
move with speed 1 (in natural units, c to the uninitiated) and
furthermore must have that speed in every frame of reference.
You're confusing what is fundamental and what is due merely
to the history of the way physical understanding evolved.
Vacuum permeability and permittivity are consequences of more
fundamental phenomena.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Date: Fri, 11 Aug 2000 22:02:16 -0400
[EMAIL PROTECTED] wrote:
> Mathematics depends on a bunch of AXIOMS. That's the first thing I
> learned in the first course of Mathematics.
That's not really relevant. Mathematics involves the *logical
connections* among things. The "things" can be specific precise
assumptions, but the connections are still subject to proof.
> Any probability thoery book does not prove that random numbers
> exist. Randomness is assumed to exist; and then an entire field
> is built on top of this assumption.
You should define what is meant by "exist". (No, this is not
a Clintonism.) In this context, the properties of randomness
(which has an exact characterization in order to allow proven
connections to be derived mathematically) might or might not
apply to some specified process. That is then a matter for
science (which includes observation and experiment) to determine.
> If you look at each individual event, it seems random. But if you
> look at a large group of events, they follow a certain pattern.
> That's not random.
Sure "it" (the process) is. The pattern is called a "probability
distribution".
> For example, one day we'll move on to nanocomputers, then current
> RNGs will not be random any more.
Sure they will. What grounds do you have for saying otherwise?
> Another side note: How come nobody has brought up anti-matters yet?
> It's so cool. :) Light -- photon -- is an anti-matter. Our
> understanding on antimatters is at the beginning stage. Maybe be some
> antimatters can travel faster then others. And then some smart kids,
> probably genetically-engineered, will show that antimatters have
> sub-antimatters...
That does not correspond to "antimatter" as understood by physicists.
> With OTP, you can try it on the ciphertext at different locations.
> You'll get meaningful plaintext if it's in ascii. If not, you'll have
> to do more work, but it still gives you an advantage over pure
> guessing.
Only if you have some procedure for duplicating the key with
better than random odds. But with a genuinely random key you
cannot do that.
> Has RSA been broken yet?
Sure, for sufficiently small parameters.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: idear for new cipher
Date: Fri, 11 Aug 2000 22:03:34 -0400
tomstd wrote:
> Try doing a few million 1024 bit adds per second and tell me
> bignum libs are practical.
They're not only practical, they're used all over the place.
------------------------------
Subject: Re: Explain S-boxes please
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 11 Aug 2000 19:01:29 -0700
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
>Because DS hasn't figured things out completely yet. I think
you showed up
>after he left for a long time. Just keep reminding yourself
that he's the
>lesser of several evils. Who knows maybe he, Szopa, and aernt
(or whatever
>his e-mail is) will start arguing, that should at least be
entertaining, in
>uninformative.
> Joe
They need to learn humility... Heck I am wrong from time to time
but I don't start being a rude loud mouth about it. They seem
to have their set views and limited open mindness.
Too bad really.
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
** 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
******************************
