Cryptography-Digest Digest #289, Volume #10 Tue, 21 Sep 99 19:13:03 EDT
Contents:
Re: frequency of prime numbers? ([EMAIL PROTECTED])
Re: key exchnages (again ;-) (David Wagner)
Re: key exchnages (again ;-) (Peter Gunn)
Re: Comments on ECC (Jerry Coffin)
Re: (US) Administration Updates Encryption Export Policy (Jerry Coffin)
Re: Yarrow: a problem -- am I imagining it? (Anton Stiglic)
Galois field isomorphism? (Paul Crowley)
PART C. 'C' SOURCE FOR CRACKER (JPeschel)
Re: Another bug RE: CryptAPI (Christopher Biow)
Re: key exchnages (again ;-) (David P Jablon)
Re: Yarrow: a problem -- am I imagining it? (Paul Koning)
Re: Comments on ECC (Jerry Coffin)
Re: Q: Is this key-exchange OK? ("Douglas Clowes")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: frequency of prime numbers?
Date: 21 Sep 1999 16:14:02 -0400
Tim Tyler <[EMAIL PROTECTED]> wrote:
> Such statements are neither true nor false *from within the axiom system
> in question*.
But the semantics are important.
The statement:
"For all natural numbers, n, P(n) is true."
May be unprovable. One could take as "part of mathematics" the axiom that
there is no such number or there is such a number and have no
contradictions in the axioms.
But the semantics of the universal quantifier -- the meaning that there
exists or does not exist a counterexample (which has a meaning outside
whether that can be proven or not) forces the statement to be true or
false.
If false, it can be demonstrated (it could be proven false simply by
giving the counterexample). So, if unprovable, it must be true.
(and then, though P(n) is always true, taking as an axiom that there is
*some* number where P(n) is false, would not invalidate the axioms of
number theory, though the new axiom, that there exists an n for which P(n)
is false, is not true given the "meaning" of the existence of
counterexamples)
(and the computer programme:
n=0
LOOP_HERE
Calculate P(n)
If P(n) is false, print "NOT ALWAYS TRUE: END
Else n=n+1: GOTO LOOP_HERE
Is, provided P(n) can be "easily" calculated, partially recursive. Is it
recursive, though (does it get into an infinite loop)? If you can't prove
whether P(n) is always true, you cannot benerally prove when partially
recursive functions are recursive.
If that programme above ends, then there is a counterexample and P(n) is
NOT always true and that programme would eventually show that P(n) is
false for some n ... but would never prove that P(n) is true.)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: key exchnages (again ;-)
Date: 21 Sep 1999 13:04:58 -0700
In article <[EMAIL PROTECTED]>,
Peter Gunn <[EMAIL PROTECTED]> wrote:
> My next idea is to have multiple concurrent DH exchanges
> with a smaller modulous...
>
> (basically split P={P1,P2,...}, X={X1,X2,...},Y={Y1,Y2,...})
>
> A->B: (g^X1)%m[P1],(g^X2)%m[P2],..., R
> B->A: (g^Y1)%m[P1],(g^Y2)%m[P2],..., S
>
> shared key K=H((g^X1Y1)%m[P1],(g^X2Y2)%m[P2])
>
> so, with an array of say 1024 large safe primes of say 512bits
> each, I could combine 3 DH key exchanges to get the shared
> key K utilising upto 2^30 bits for P.
This doesn't work. One can play man-in-the-middle games to learn
the shared secret.
The attack requires 3*1024 online trials, which is much less than
the 1024^3 online trials required to break competing protocols.
Have you looked at SRP (http://srp.stanford.edu/srp/) or SPEKE
(http://www.integritysciences.com/speke.html)?
The attack:
The attacker M guesses P1, sets n = m[guess at P1], tampers with
the first of the concurrent DH exchange (leaving the others unchanged):
A->M: g^X1 mod m[P1], g^X2 mod m[P2], ...
M->B: (g^X1 mod m[P1])^2 mod n, g^X2 mod m[P2], ...
B->M: g^Y1 mod m[P1], g^Y2 mod m[P2], ...
M->A: (g^Y1 mod m[P1])^2 mod n, g^Y2 mod m[P2], ...
If the attacker guessed correctly (i.e., n = m[P1]), then A and B
will calculate the same value of their shared secret, since
(g^{2 X1})^Y1 mod m[P1] = (g^{2 Y1})^X1 mod m[P1].
Thus, the key-exchange will succeed exactly when M guesses P1 correctly.
In this way, after 1024 sessions the attacker can recover P1, and
similarly, after 3*1024 sessions, he learns the entire password (all
of P1, P2, and P3).
------------------------------
From: Peter Gunn <[EMAIL PROTECTED]>
Subject: Re: key exchnages (again ;-)
Date: Tue, 21 Sep 1999 22:15:12 +0100
David Wagner wrote:
> In article <[EMAIL PROTECTED]>,
> Peter Gunn <[EMAIL PROTECTED]> wrote:
> > My next idea is to have multiple concurrent DH exchanges
> > with a smaller modulous...
> >
> > (basically split P={P1,P2,...}, X={X1,X2,...},Y={Y1,Y2,...})
> >
> > A->B: (g^X1)%m[P1],(g^X2)%m[P2],..., R
> > B->A: (g^Y1)%m[P1],(g^Y2)%m[P2],..., S
> >
> > shared key K=H((g^X1Y1)%m[P1],(g^X2Y2)%m[P2])
> >
> > so, with an array of say 1024 large safe primes of say 512bits
> > each, I could combine 3 DH key exchanges to get the shared
> > key K utilising upto 2^30 bits for P.
>
> This doesn't work. One can play man-in-the-middle games to learn
> the shared secret.
>
> The attack requires 3*1024 online trials, which is much less than
> the 1024^3 online trials required to break competing protocols.
>
> Have you looked at SRP (http://srp.stanford.edu/srp/) or SPEKE
> (http://www.integritysciences.com/speke.html)?
>
> The attack:
>
> The attacker M guesses P1, sets n = m[guess at P1], tampers with
> the first of the concurrent DH exchange (leaving the others unchanged):
> A->M: g^X1 mod m[P1], g^X2 mod m[P2], ...
> M->B: (g^X1 mod m[P1])^2 mod n, g^X2 mod m[P2], ...
> B->M: g^Y1 mod m[P1], g^Y2 mod m[P2], ...
> M->A: (g^Y1 mod m[P1])^2 mod n, g^Y2 mod m[P2], ...
> If the attacker guessed correctly (i.e., n = m[P1]), then A and B
> will calculate the same value of their shared secret, since
> (g^{2 X1})^Y1 mod m[P1] = (g^{2 Y1})^X1 mod m[P1].
> Thus, the key-exchange will succeed exactly when M guesses P1 correctly.
>
> In this way, after 1024 sessions the attacker can recover P1, and
> similarly, after 3*1024 sessions, he learns the entire password (all
> of P1, P2, and P3).
Whoops! Yes, of course you're right :-)
I have looked at SPEKE and SRP, and they are very good, but I still think
that there is some mileage in this idea, even if its just to put my mind at
rest.
There would seem to be several 'fixes' for this attack...
1) I could calculate P1,P2,P3,... from H(R,P)
or
2) I could derive P1,P2,P3,.... from E[R](P)
this would seem to make each guess only valid for each possible
value for R (which is bigger than P anyway :-)
All comments welcome :-)
ttfn
PG.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Comments on ECC
Date: Tue, 21 Sep 1999 15:09:00 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> All crypto algorithms I know are in NP, if only for the reason that using the
> private key must take a reasonable amount of time. So a trivial NP solution to
> solving the ECDLP or DLP is guess the correct private key.
I'm assuming you meant to use "P" where you said "NP" above
(otherwise, I can't decipher your statement into anything meaningful).
Keep in mind that "NP" means "modernistic polynomial." IOW, even
assuming that there really is such a thing as an NP-complete problem
(I.e. that P!=NP) there's still a non-deterministic method of finding
the solution to that problem in polynomial time. In most cases, this
means a correct guess at the solution. The question is whether
there's a _deterministic_ method that gives the correct answer in
polynomial time.
At least AFAIK, for quite a few problems (including this one) the
answer is that nobody's ever proven either that there is deterministic
solution that can be carried out in polynomial time or that there
can't be such a thing. In any case, invoking the possibility of a
correct guess means nothing with respect to whether a problem falls
into P or (as far as we know) NP, since it's a non-deterministic
method, which is exactly the definition of NP, showing nothing about
falling inside of P.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: (US) Administration Updates Encryption Export Policy
Date: Tue, 21 Sep 1999 15:08:58 -0600
In article <7s8h7v$9i1$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> The court's decision was that source code could be used for
> communication, and thus any regulations must have the safeguards.
Right. BUT, keep in mind that any particular publication of source
code might NOT be considered speech at all, but a means of taking
action. Since the initial decision by a department might be wrong, it
has to be open to judicial review, but you might ultimately be stopped
from publishing any particular piece of source code.
When/if you're undergoing such a review process, the decision about
whether to allow the export or not has to be based on your INTENT in
publishing -- if you intend to publish source code primarily as a
means of getting a computer to take particular actions, then you have
no protection of the publication as free speech. To be protected as
free speech, you have to be publishing _primarily_ to communicate with
other people, NOT to get a computer to do something.
IOW, when/if you go in front of a court, you'll have to convince the
court that you intended the code primarily as a means of speaking to a
person. If you write code nobody can easily understand, I doubt
they'll be convinced of that.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Yarrow: a problem -- am I imagining it?
Date: Tue, 21 Sep 1999 17:19:07 -0400
>
>
> SHA1 is deterministic, but it is not necessarily one to one.
> It's possible that two consecutive outputs would have
> the same value. Triple-DES can not.
> This was the original 'complaint' I was addressing.
>
Yes, you are right, but this will not give a cycle.
Thus we might even shorten the cycle, not helping at all!
as
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Galois field isomorphism?
Date: 21 Sep 1999 21:52:48 +0100
I'm told that there's really only one GF(2^8), and that all the
irreducible polynomials you can use as bases just give you different
ways of representing it.
How do I convert between different representations, given their basis
polynomials? Are there non-trivial isomorphisms from the set onto
itself? It seems as if it must be a linear mapping by definition,
since addition is the same in any representation and
f(a) + f(b) = f(a + b) ; is that right?
What's the best textbook for this sort of thing?
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: PART C. 'C' SOURCE FOR CRACKER
Date: 21 Sep 1999 21:45:02 GMT
Casimir's essay, "The Cracking of Gregory
Braun's Crypto v3.5," is now complete.
Part A begins the reverse-engineering
process and Part B continues the
analysis and starts the reversal.
Part C is C source code, and includes
a link to an executable cracker.
For some reason Braun included a
"crackme" in the crypto 3.5
distribution. Apparently, he likes
Jabberwocky, by Lewis Carroll.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Christopher Biow <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Another bug RE: CryptAPI
Date: Tue, 21 Sep 1999 16:03:01 -0400
[EMAIL PROTECTED] (Bill Unruh) wrote:
>From what we know now, I cannot see your fraud statement. This does not
>change the strength of any encryption product that may be linked to the
>API at all. All it does is to say that APIs may be linked that are not
>signed by MS. This may be incompetence but in what way is it fraud.
MS did the minimum that would get them gov't approval for a crypto API.
Inherently, a DLL implementation exposes interfaces to external attack--I'm
sure this was not lost on MS. But neither they (nor we) would want this
system to be any stronger than was required for export approval.
No matter what, any Turing machine can run PGP (presuming someone will
write an appropriate C compiler and redo the lower-level routines for
Turing assembler). MS Crypto API does no more than any of the other crypto
export restrictions--makes it mildly inconvenient for foreign users to run
good crypto. As a result, 99% of foreign encryption actually being used out
there is weak, and that seems to be all that the US government wants.
------------------------------
From: [EMAIL PROTECTED] (David P Jablon)
Subject: Re: key exchnages (again ;-)
Date: Tue, 21 Sep 1999 21:59:08 GMT
In article <[EMAIL PROTECTED]>, Anton Stiglic <[EMAIL PROTECTED]> wrote:
>>[Peter Gunn wrote:]
>> EKE does this by encrypting the g^X and g^Y values,
>> SPEKE uses a generator based on P (the weak shared
>> secret), etc. I thought I'd try and create my own version.
>
>sorry for deviating from the initial conversation, but are
>there any refs concerning the description of EKE and
>SPEKE.?
A paper at www.IntegritySciences.com/speke97.html discusses the
EKE and SPEKE protocols, and the .../links.html page points to
many on-line papers in the field.
======================================================
David P. Jablon
Integrity Sciences, Inc.
[EMAIL PROTECTED]
<http://www.IntegritySciences.com>
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Yarrow: a problem -- am I imagining it?
Date: Tue, 21 Sep 1999 17:43:27 -0400
Anton Stiglic wrote:
>
> >
> >
> > 1. Yes, that's true.
> > 2. So what?
> >
>
> I guess my question would be "what does Yarrow suppose to be?"
>
> Is it suppose to be a PRNG? If so, then there is a big problem, it
> would be saying it's something that it's not!
No...
If it's supposed to have ALL the properties of a (true) RNG, that
would be a problem because it clearly doesn't -- it doesn't obey the
birthday rule if not reseeded.
Then again, an old-style PRNG (non-crypto flavor) doesn't either.
Those have cycles, typically 2^n or (2^n)-1 for simple n-bit ones,
longer for more complex ones. Definite a birthday violation.
But so what? My point is that this violation is of NO practical
significance for any interesting application. Or at least as far
as I know, and I haven't seen anyone offer an example of an
application where it does matter.
(Another point is that PRNGs differ from RNGs in other ways that
are far more significant.)
paul
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Comments on ECC
Date: Tue, 21 Sep 1999 16:49:07 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Keep in mind that "NP" means "modernistic polynomial." IOW, even
Danged fool spell-checker. I'd swear I told it NOT to make that
"correction", but apparently not. That should, of course, read "non-
deterministic polynomial." As-is, it's utter nonsense.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: "Douglas Clowes" <[EMAIL PROTECTED]>
Subject: Re: Q: Is this key-exchange OK?
Date: Wed, 22 Sep 1999 08:15:38 +1000
OK, I'll try again ...
Thomas Wu wrote in message ...
>"Douglas Clowes" <[EMAIL PROTECTED]> writes:
>> Are these key-exchanges OK or do I need something else?
>>
>> I want two terminals to practice secure communications after an algorithm
>> negotiation and key exchange phase. I want to mutually authenticate the
>> parties.
>>
>> The pair will initially either share a secret, which may be a
>> password/phrase, or they will have public key certificates signed by a
>> trusted CA. The messages in the key exchange phase are authenticated by
>> HMAC-SHA1-96 or SHA1 with RSA signature, as appropriate.
Note that this represents two alternative scenarios, where each terminal is
pre-provisioned with either
(a) a shared secret - pass word/phrase, or random bit string
(b) a private key and public key certificate signed by a common CA.
>>
>> The question is: can I do this in a two pass exchange, or do I need a
>> challenge-response after DH exchange?
Most of the other protocols show a challenge-response exchange after the
initial DH-exchange.
Is this really necessary if you can convince yourself in other ways?
>> The message exchange for passwords (HMAC authenticated) is:
>>
>> 1:A->B: Id_a, Id_b, Time_a, Rand_a, DH_a, Algorithms_a, HMAC
>> 2:A<-B: Id_b, Id_a, Time_b, Rand_b, DH_b, Algorithms_b, HMAC
>>
The above is for scenario (a) where the two terminals share a common secret.
The message contains:
- the Identity of A and B, which serves to select the correct shared secret
and prevent replay attack against another receiver. The ordering of the
identities prevents reflection attacks.
- a timestamp, which serves to prevent replay attack against the same
receiver.
- a nonce, because everybody else does :)
- The sender's Diffie-Hellman parameters g,P, g^x mod P
- The possible algorithms which the sender supports. Algorithms_b should be
a subset of Algorithms_a.
- A HMAC-xxx-96 computed over the rest of the message and the shared secret.
A receiver should be able to identify the sender, locate the shared secret
(it may share other secrets with other peers), compute the HMAC over the
message and determine that the message is genuine. This should ensure that
the DH parameters are genuine, and not inserted by M (Mallory in the
middle).
If the nonce is really a sequence number, then the receiver can store the
last used timestamp and sequence number of the sender and check that this
one is greater. This assumes that an attacker can't inject a valid message
with a higher sequence number and deny future service to a legitimate sender
using a lower sequence.
>> The message exchange for certificates is the same, but includes the
sender's
>> certificate (which can be checked by the receiver) and is signed with the
>> private key associated with the certificate.
This is for scenario (b), using public key certificates. It is the same as
scenario (a) except that the messages include the senders public key
certificate, signed by a trusted common CA. Instead of computing and
checking the keyed-HMAC, the sender computes the HASH, and encrypts it with
the secret key (SHA1withRSAsignature).
The receiver verifies the received certificate, checks the CRL and all that
stuff, staisfying himself that the certificate is genuine, or uses a stored
certificate it has obtained by other means - his choice.
The receiver computes the same hash, decrypts the received hash using the
public key in the certificate, and compares the values. If they match, the
message is genuine, untouched, and from the sender.
>It's not clear from your description where all these extra private keys
>and certificates come from. Earlier you said there was just a shared
>passphrase.
I hope that this is a little clearer. Two separate scenarios.
>> After message 1, B can ensure that the message came from A, and the DH_a
is
>> A's.
>>
>> The same is true for A after message 2.
>>
>> Is this OK?
In each case, by matching the HMAC/signature, the receiver can determine
from each message:
- that it is unmodified
- that it originated from someone with the shared-secret/private-key
>> Possible variations would include using the HMAC function on the password
>> and DH exchange secret to create the key used in future communications,
as a
>> further assurance that each has the password. Similarly for the
certificate
>> case, B could encrypt DH_b with B's private key, and then A's public
key -
>> for A to recover it, DH_b must be decrypted with A's private key (proving
>> A's possession) and B's public key (proving B's possession of the private
>> key).
These again are the two scenarios above: (a) shared secret, and (b)
public-key.
The purpose of a challenge-response exchange is to ensure that the other
party does indeed have the material claimed, be it the shared secret, or the
private key. We *should* alredy know that from the exchange above. If a
replay were possible, given the identifiers and timestamp, this would help.
I am assuming here that we don't really need to know, after the first
exchange, that the other party has the matching key. We only need to know
that at the next exchange, which will be encrypted with the given key.
Therefore, computing the key based on the possessed material makes it
impossible to come up with a shared key if you don't possess the same
material.
For example: In scenario (a), I compute the HMAC_SHA1 of the DH
exchanged/shared secret, and the passphrase. I use the first 64 bits as the
DES key, and the last 64 bits as the initialization vector.
In scenario (b), B encrypts the DH_b value g^y mod P with his private key,
and then A's public key. For A to recover the same g^y mod P to input into
the key generation, she must use her private key (and therefore must have
it), and B's public key. If either A or B do not have the claimed private
keys, A cannot recreate the same g^y mod P as B and their generated keys
will not be the same.
>> Does this help and it is needed?
>>
>> Does a challenge-response exchange following add anything except
overhead?
>>
>> Is this open to attack? If so, how do I secure it?
>
>These are all slower and less secure than established password methods
>like SRP, SPEKE, and EKE. Read up on them at:
>
>http://srp.stanford.edu/srp/
>http://www.integritysciences.com/~dpj/
These all seem to be four or more messages. My goal is two.
Is the HMAC-SHA1-96 sufficient to secure that the DH_x is genuine?
Does it divulge too much information on the shared secret, which is possibly
a low entropy password?
Would it be better to just encrypt the g^x mod P and g^y mod P, with a key
derived from the passphrase (MD5), rather than signing the whole message?
Why?
Thanks for your response,
Douglas
>Tom Wu * finger -l [EMAIL PROTECTED] for PGP
key *
> E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms
in
> Phone: (650) 723-1565 exchange for security deserve
neither."
> http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
** 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
******************************
