Cryptography-Digest Digest #583, Volume #11 Thu, 20 Apr 00 06:13:00 EDT
Contents:
Help With PGP's Newest TLS/SSL toolkit for linux..... ("Jeff Hamilton")
Review of CryptoBag (Tom St Denis)
Re: Q: NTRU's encryption algorithm (David A Molnar)
Re: Text File Encryption ("Joseph Ashwood")
Re: GSM Man-in-the-Middle (David Hopwood)
Re: password generator ("Trevor L. Jackson, III")
Re: password generator (Tom St Denis)
Re: diff between Symetric and Asymetric Keys (JPeschel)
Re: Q: NTRU's encryption algorithm (Diet NSA)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (Anthony Stephen Szopa)
----------------------------------------------------------------------------
From: "Jeff Hamilton" <[EMAIL PROTECTED]>
Subject: Help With PGP's Newest TLS/SSL toolkit for linux.....
Date: Wed, 19 Apr 2000 17:23:38 -0700
Has anyone had much luck developing with PGP's Newest TLS/SSL toolkit?
I received a trial version for developers....but it is not intuitive to say
the least. Also, they said it performs RSA Key-Gen and Verification, and I
see RSA referenced in the lib functions....but I can't implement them. If
you have worked with it please let me know. I'm simply trying to create
either a Key-Gen Function or have a simple SSL client to make a connection
and verify a cert.
Thanks,
Jeff
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Review of CryptoBag
Date: Thu, 20 Apr 2000 00:42:42 GMT
I was wondering if some of the people who downloaded CryptoBag could
post a short reply to this message about their impressions? I need some
references that I could use in an introductory letter for university.
Generally what did you think of my coding style, and efficiency,
praticallity.
Thanks,
Tom
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Q: NTRU's encryption algorithm
Date: 20 Apr 2000 00:40:00 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
> I don't remember the discussion a few months ago, but I'm extremely
> skeptical of any claim that lattice-based cryptosystems are necessarily
> secure against quantum computers.
As I understand it, the reasoning goes like this :
* The closest vector problem (CVP) is NP-hard for exact answers, and for
constant approximation factors (not sure what the sharpest factor
is, exactly).
* There are results which show that Grover's algorithm on a quantum
computer, with its sqrt(n) speedup, is optimal in the model of
computation where all you can do is check to see if you have the
right answer. Put another way, if you're not allowed to look at
any "extra structure" beyond the fact that the problem is in NP,
then you can only get sqrt(n) speedup over a classical computer.
Yet another way of saying it might be that there is no "generic"
quantum algorithm which can solve every problem in NP in polynomial
time.
I can't remember the references now, but I think there's a paper due
to Jozsa in the lanl archives on the subject.
* This seems to support a conjecture that BQP != NP -- that is, the
class of languages decidable in a polynomial number of measurements
on a quantum computer isn't the same as NP. It's not conclusive,
because it could still be the case that every NP problem has a
separate fast quantum algorithm tailor made for it.
In fact, we know of at least two NP problems which _do_ have separate
fast quantum algorithms tailor made for them -- factoring and discrete
logarithms. Unfortunately.
* If you could solve the Closest Vector Problem exactly using a fast
quantum algorithm, then you can solve for everything in NP.
This would imply that BQP \superseteq NP, contrary to the conjecture
above.
* Therefore, a "lattice based cryptosystem" which relies on the CVP
probably doesn't have a fast quantum algorithm, right??
* Except one or two things :
- It's not clear to me if a fast quantum algorithm for
CVP would contradict the optimality results on Grover's
algorithm. Why? Because the algorithm + the reduction
from each problem to SVP would clearly use some special
"structure" of the problem which I do not know to be
covered by the optimality results.
Then again, I have _not_ made any kind of comprehensive
study on these results. I just read over a paper or two
last year which mentioned this...
There may be other reasons to believe BQP != NP.
- Solving the SVP exactly is NP-hard. Solving the CVP
to within an error factor of O(2^n) is doable in
polytime by the LLL basis reduction algorithm.
As far as I know, no lattice based cryptosystem has its
security provably based on solving exact instances of
the problem. The best result I know of was for the
Ajtai-Dwork system, which had a reduction from breaking
the scheme to approximating the shortest independent
vector problem. It turned out that this approximation
factor was not good enough; in practice Nguyen and Stern
were able to use LLL to find short enough vectors and
break the scheme.
The real question, then, is "what kind of approximation
is sufficient to break the lattice-based scheme?"
and after that "what is the best approximation to the
SVP which can be produced on a quantum computer?"
(or whatever lattice problem it is ).
I have no idea about this latter question. Anyone?
In the case of NTRU and the first question, I recently
asked that question on a mailing list. Joseph Silverman
(one of the inventors of NTRU) was kind enough to
reply. I'm excerpting his reply here :
<begin>
To answer your last question about how good an approximation is needed,
the information is in the Coppersmith-Shamir paper (at least
qualitatively). Roughly, if you can find several vectors that are 1.5 to
2 times longer than the SVP target vector, then you can recover some or
all of the plaintext. However, based on extensive experiments, lattice
reduction algorithms do not seem able to find such vectors any more
easily than they are able to find the actual target vector. In addition
to experiments, there are various theoretical reasons why this seems to
be true for the NTRU lattices. For example, an NTRU lattice contains a
half-basis of pairwise orthogonal vectors called "q-vectors" that are 4
to 5 times longer than the target vector. These q-vectors are completely
useless for cryptographic purposes, but they look like short vectors to
lattice reduction algorithms such as LLL.
<end>
This seems to suggest (but not prove, of course) that
you need to approximate CVP within a constant factor
to break NTRU. That would be pretty cool if true.
The only problem is figuring out if it's true or not...
Thanks,
-David
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Text File Encryption
Date: Wed, 19 Apr 2000 18:11:52 -0700
I agree, probably. But it really depends on what you want to
do. For example if you want to secure files, I'd suggest
using ScramDisk, and just make it easy on yourself.
Joe
<[EMAIL PROTECTED]> wrote in message
news:8dkgrj$kdq$[EMAIL PROTECTED]...
> Folks,
>
> Is there an encryption application available which can be
referenced
> within code or executed via shell commands to decrypt a
text file for
> import into Access? Maybe a set of dll's or methodology
which would
> work?
>
> TIA
>
> Dave
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
Date: Wed, 19 Apr 2000 01:01:11 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: GSM Man-in-the-Middle
=====BEGIN PGP SIGNED MESSAGE=====
Matt Linder wrote:
> I was reading an old post entilted "Key exchange using Secret Key
> Encryption" in which people were talking about a Man-in-the-Middle
> attack on internet traffic, and it made me think of the recent thread
> about GSM and A5/1.
>
> Would it be possible to do a Man-in-the-Middle type of attack on GSM?
In all the situations where you might be able to do such an attack (e.g.
if you have a piece of equipment that simulates a base station), it
would be much easier to eavesdrop the *cleartext* communications over
microwave links or land lines.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOPz3GTkCAxeYt5gVAQEzswgAgy5BAb7oGHlEozwJs5PvDY2uy0lSW+uQ
GFl3pc186W7K+YzNzL7liXUf05c+TFxFSzOtiykZCAlpPpVDHAuNgmYnLVfPiwgd
jJzuNBnRREpZRBYF74Tmp3EuW7O+FyMPDW4PiOzkLgDtpW6k73aZhQ0x/iqjY281
YvkH5ZsqueyDsM78nhpvxoUHcDHTrUvD2Q/+xVUGt1o/z2SCVpoftw0cbeBYjkAb
M33M8nUIvblOIueT5RdK25Rw1RETrHTsRQhnLSetBae2Jt580lFupO1X++OnIKTC
v/MdQHlVsNV7iLCieVJk/uxxcCSOnQkOxmQ28NUSZpAP1qHHx3rG7w==
=RttP
=====END PGP SIGNATURE=====
------------------------------
Date: Wed, 19 Apr 2000 23:26:24 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: password generator
Tom St Denis wrote:
> "Trevor L. Jackson, III" wrote:
> >
> > Anton Stiglic wrote:
> >
> > > O.k., I'm sorry for the error, I just posted a quick reflexion. No need for all
> > >
> > > that arragance, we already have Bob Silverman here for that.
> >
> > Hmmm. A couple of points.
> >
> > First, arrogance (sic) is partly in the eye of the beholder.
> >
> > Second, everyone who submits is guilty in some degree of insufficient humility in
> > that they consider their writing to be worth reading (c.f., 90% of everything is
>...
> > -- Sturgeon?).
> >
> > Third, Silverman doesn't appear arrogant to me, just forceful (I'm willing to be
> > corrected on this point if he chooses to opine on this topic).
> >
> > Fourth, had you been submitting code of your own you would probably have gotten far
> > more gentle treatment than you got for falsely (arrogantly ;-) criticizing someone
> > else's code.
>
> Not to jump in the middle, but if there are problems with my code I
> would rather know. Basically all the stuff I post to my site and here
> is research. So if I am wrong (98% of the time I am) I want to know.
>
> Similarly, if they are wrong I choose to let them know.
>
> I think some people just have to be a bit more objective and realistic
> when they critic things. Also that they try something before deeming it
> useless.
Well, there are criticisms that could be brought against your example. For instance,
it
does not utilize all of the state available. In particular the number of iterations
has
no effect on the result, only the parity of the number of iterations. If the inner
statement were slightly more complex then the number of iterations would be a useful
input. Second, on some systems the function gettime() may require synchronization,
which
will introduce a regularity into the spin lock that will degrade the results of
multiple
calls to retrieve a result bit.
However, neither of these criticisms are well founded because they may be irrelevant to
the purpose of the example code. Until there is a well defined context or purpose
detailed analysis really impossible.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: password generator
Date: Thu, 20 Apr 2000 03:29:28 GMT
"Trevor L. Jackson, III" wrote:
> Well, there are criticisms that could be brought against your example. For
>instance, it
> does not utilize all of the state available. In particular the number of iterations
>has
> no effect on the result, only the parity of the number of iterations. If the inner
> statement were slightly more complex then the number of iterations would be a useful
> input. Second, on some systems the function gettime() may require synchronization,
>which
> will introduce a regularity into the spin lock that will degrade the results of
>multiple
> calls to retrieve a result bit.
>
> However, neither of these criticisms are well founded because they may be irrelevant
>to
> the purpose of the example code. Until there is a well defined context or purpose
> detailed analysis really impossible.
I know this sounds "bad" but the WinRng really does output statistically
random bits, and I am not sure how. It passes the ENT tests for 512kb
or so of output. Since it has no state I would think it's not
repeating...
I know for a fact that the counter runs at around 9 mhz +/- 1.5mhz on my
k6-II 400mhz with other tasks going. I think the reason it seems random
has todo with unpredictable pipeline stalls and other stalls along the
way. The inner loop only takes a few cycles, and even at a resolution
of 10ms that's 4mhz of cycles. So there is room for errors...
I dunno, if anyone else has a win machine try it out, it works wonders.
Of course on a 'dry' machine with no other tasks or any services running
it's probably not very random, but on a comp like mine (hosting lan,
proxy, web daemon, email, winamp, myself, key proxies going) there is
always something going on here or there...
Tom
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: diff between Symetric and Asymetric Keys
Date: 20 Apr 2000 03:43:04 GMT
Tom St Denis [EMAIL PROTECTED] writes:
>Now if this can be drilled into all
>media press kits about crypto...
The info in a company's press kit is usually thrown
together in such a way that you might consider
the technical data a possible source of a PRNG.
:-)
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
Subject: Re: Q: NTRU's encryption algorithm
From: Diet NSA <[EMAIL PROTECTED]>
Date: Wed, 19 Apr 2000 21:38:08 -0700
In article <
8dljl0$ls5$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]>
wrote:
Put another way, if you're not allowed to
look at
> any "extra structure" beyond the fact that the problem is in
NP,
> then you can only get sqrt(n) speedup over a classical
computer.
Unfortunately, Grover's algorithm only
offers quadratic speedup which means
that quantum computers will have to
become much faster before Grover's
approach can overtake brute force
searching.
> Yet another way of saying it might be that there is no
"generic"
> quantum algorithm which can solve every problem in NP in
polynomial
> time.
>
This appears to be true.
>
>* This seems to support a conjecture that BQP != NP -- that is,
the
> class of languages decidable in a polynomial number of
measurements
> on a quantum computer isn't the same as NP. It's not
conclusive,
> because it could still be the case that every NP problem has a
> separate fast quantum algorithm tailor made for it.
>
No one knows if NP is in BQP but there are
researchers who doubt that it is.
The advantage of parallel computing is
limited against attacking NTRU and also I
don't see any specific way that a quantum
computer would help. If someone wanted
to make a cryptosystem that is
theoretically secure against quantum
computing then they might begin by trying
to invent one-way functions that no
quantum computer can invert better than
random guessing.
P.S. Is BQP equivalent to the problems
having statistical zero-knowledge proof
systems? A: No one knows.
"I feel like there's a constant Cuban Missile Crisis in my pants."
- President Clinton commenting on the Elian Gonzalez situation
=======================================================================
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: Wed, 19 Apr 2000 22:08:02 -0700
"Trevor L. Jackson, III" wrote:
>
> Anthony Stephen Szopa wrote:
>
> ...
>
> > You don't know what you are talking about.
> >
> > You cannot even describe the process of how the final OTPs are
> > created from start to finish.
>
> ...
>
> > None of you have supported anything you have said.
>
> ...
>
> > Have any of you asked Mr. Huuskonen if the output from the random digit generator
> > is used to encrypt messages? No, none of you have. This is
> > because none of you knows what they are talking about.
>
> ...
>
> > "If you don't get it: you don't get it."
>
> This set of statements leads to a an unresolved question. Given your contempt for
>the
> sci.crypt readership, why do you bother posting here?
>
> It appears that there are only two ways to resolve this. Either your
>characterization of your
> respondents is accurate, in which case your contributions to sci.crypt are a waste
>of time, or
> your characterization is inaccurate, in which case your resistance to the ideas
>presented here
> is a waste of time. Why are you wasting your time?
>
> Please reply carefully. Less charitable readers will interpret the conflict as a
>choice
> between "Everyone in sci.crypt is an ignorant, uneducable idiot" or "A.S. Szopa is an
> ignorant, uneducable idiot". Which way do you think they'll decide?
"Why am I wasting my time?"
I am not wasting my time.
------------------------------
** 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
******************************
