Cryptography-Digest Digest #785, Volume #10 Wed, 22 Dec 99 22:13:01 EST
Contents:
Re: Question about SSL and Java (Eric Murray)
Re: More idiot "security problems" (David Eppstein)
Re: "Variable size" hash algorithm? (Scott Nelson)
Re: Thanks for the recommend! (William Stallings)
Re: Schoof's algorithm (Scott Contini)
Re: NEW PROGRAM = FREEDOM (Steve K)
Re: Of one time pads, plaintext attacks, and fantasy (Legrange)
----------------------------------------------------------------------------
Subject: Re: Question about SSL and Java
From: [EMAIL PROTECTED] (Eric Murray)
Date: 22 Dec 1999 16:42:22 -0800
In article <83rnkj$e0a$[EMAIL PROTECTED]>, Greg <[EMAIL PROTECTED]> wrote:
>I am trying to learn about SSL and how it works with Java
>scripts on a web server. Please tell me if I am incorrect
>with the following assumptions:
>
>The SSL code runs as a layer above the socket software and
>runs more like a driver than anything else.
On Windows it might look like a "driver". On Unix it can be
a shared library or linked statically with the application
or it could be linked into the driver stack on SVR4 Unixes
or even built into the kernel (I haven't seen the last two
done but I wouldn't be suprised if someone has done them).
>The Java script can manipulate the SSL, but SSL itself is
>not written in Java (usually).
Usually. There are some Java implementations but the majority
are in C.
>This last fact has no impact on the OS platform that Java
>runs on.
The ability to do SSL does not determine the platforms that Java runs on.
--
Eric Murray www.lne.com/~ericm ericm at the site lne.com PGP keyid:E03F65E5
------------------------------
From: [EMAIL PROTECTED] (David Eppstein)
Subject: Re: More idiot "security problems"
Date: 22 Dec 1999 16:59:53 -0800
[EMAIL PROTECTED] (Dan Day) writes:
> Do you recall what the bone-headed algorithm was? Most "first try" sort
> algorithms are O(N^2). A few common "seemed like a good idea at the time"
> algorithms are O(N^3). But what on EARTH would generate a O(N^6) runtime??
I'd like to know that, too.
My favorite bad sorting algorithm (which I've used on exam questions a
couple times) involves recursively sorting the first 2/3 of the items,
the second 2/3, and the first 2/3, but that's only O(n^{2.71}) or so.
It's also possible to get exponential or worse time if you really work
at it e.g. go through all the permutations until you find one in the
right order. But O(n^6)? In a fielded algorithm?
--
David Eppstein UC Irvine Dept. of Information & Computer Science
[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: "Variable size" hash algorithm?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 23 Dec 1999 01:19:21 GMT
On Wed, 22 Dec 1999 22:26:45 GMT, [EMAIL PROTECTED] (Dan Day) wrote:
>I'm still new to a lot of this, so bear with me if
>there's a simple, well-known answer to this question.
>
>I'm looking for a hash algorithm that can easily be
>"set" to produce hash values of practically any size.
>For example, given M bits of input, I'd like to have
>a "general" hash algorithm that can be used to
>produce any desired number of bits of output (or at
>least up to M bits of output).
>
[snip]
There are several non-secure ones,
http://www.helsbreth.org/random/nbitcrc.html
would be ok for some of things you mention.
It's not to hard to construct a large hash out of
a "small" one. You can for example use an SHA1 hash
of 1 and <thing_being_hashed> for the first 160 bits,
2 and <thing_being_hashed> for the next 160 and so on.
The security of such a composite hash won't necessarily
be any better than the pieces themselves, but the
"spread" will be ok, and it's easy to generalize to
N bits.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (William Stallings)
Subject: Re: Thanks for the recommend!
Date: Wed, 22 Dec 1999 21:04:02 -0500
In article <83rjpa$b23$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> >
>
> Thanks for the recommendation. Quite a few? How do you find them? I know
> there are plenty of "spy" novels and "espionage thrillers", but of the
> ones I've read, few really circle around crypto as a major plot device.
>
My all time favorite is "Talking to Strange Men" by Ruth Rendell. It is a
psychological thriller rather than a spy or espionage novel, but crypto is
important to the plot.
Bill
| | Descriptions, errata sheets and discount order info |
| | for my current books and info on forthcoming books: |
| Bill Stallings | WilliamStallings.com |
| [EMAIL PROTECTED] | |
| | Visit Computer Science Student Support site: |
| | WilliamStallings.com/StudentSupport.html |
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Schoof's algorithm
Date: 23 Dec 1999 02:29:12 GMT
In article <IRQ74.1949$[EMAIL PROTECTED]>,
Michael Scott <[EMAIL PROTECTED]> wrote:
>Our implementation of Schoof's algorithm for counting points on an elliptic
>curve over GF(p) has been improved.
>
>When originally announced it took 100 minutes on a 180MHz Pentium Pro to
>count the points on a 160-bit curve - now it takes less than 20 minutes. It
>takes about 6 hours for a 256 bit curve.
>
>Our implementation of the always-superior Schoof-Elkies-Atkin algorithm
>originally took more than 27 hours to count the points on a 512-bit curve,
>now it averages about 7.5 hours. Note that the SEA algorithm is always
>superior, but a little more awkward to use.
>
>See the URL below for details.
>
>Mike Scott
>---------------------
>Fastest is best.
>MIRACL multiprecision C/C++ library for big number cryptography
>http://indigo.ie/~mscott
>
>
Reading your posting, we thought we would make some comments
on point counting over elliptic curves.
The original algorithm of Schoof is a theoretical achievement
in providing a polynomial time algorithm for point counting on
elliptic curves, but, as you note on your web page, should be
considered "far too inefficient", and "unacceptably slow".
As a further note, it is not clear what makes an SEA implementation
"awkward to use". Rather, an implementation of the original Schoof
ought to be very awkward. Since the size of the polynomials grow
quite large, running an actual implementation should rapidly
exceed the memory modest memory size of contemporary computers.
Here we give timings for the SEA implementation in Magma
(see http://www.maths.usyd.edu.au:8000/u/magma/). By presenting
timings for a naive Schoof implementation, you present an unduely
pestimistic picture of the current state of the art for point
counting algorithms on elliptic curves.
For the sake of comparison, our timings are on a 333MHz Sun
workstation. Over a 160-bit prime field, our SEA timings are
in the range of 30-60 seconds. Over a 256-bit field we find
times on the order of 5-10 minutes, rather than hours. One
random example over a 512-bit field took three hours, of the
same order of magnitude of your 7.5 hour average for the true
SEA algorithm. These are all rough timings, but give a scale
of comparision (a log file is below).
Magma has optimized algorithms for finite fields, for polynomial
rings over fields, and for addition on elliptic curves, all of
which are prerequisites for a fast point counting algorithm.
It should be expected, however, that all modern computer algebra
libraries (like Pari, LiDIA, NTL, or your own package) provide
support for this basic infrastructure.
David Kohel
(and Scott Contini)
===================================================================
1) Random ~160-bit Examples.
> p := RandomPrime(160);
> p;
98385727204771019581977249435985531212484757717
> Ceiling(Log(p)/Log(2));
157
> FF := GF(p);
> E := EllipticCurve([Random(FF),Random(FF)]);
> E;
Elliptic Curve defined by y^2 = x^3 + 71231904108825305625747450970146130348035\
686972*x + 36787795904004393278742743161463067404438921357 over
GF(98385727204771019581977249435985531212484757717)
> time #E;
98385727204771019581976995436121456741017140037
Time: 43.420
> p := RandomPrime(160);
> Ceiling(Log(p)/Log(2));
160
> FF := GF(p);
> E := EllipticCurve([Random(FF),Random(FF)]); E;
Elliptic Curve defined by y^2 = x^3 +
55868440463846583647057731675550110178100779747*x +
397934072922895001958337901696294160221069008467 over
GF(938063601340019173054477818729520907228403164791)
> time #E;
938063601340019173054477587961909528494322480962
Time: 53.340
> p := RandomPrime(160); FF := GF(p); Ceiling(Log(p)/Log(2));
160
> E := EllipticCurve([Random(FF),Random(FF)]); E;
Elliptic Curve defined by y^2 = x^3 +
351783051870960138898679691087906633837476642585*x +
202180755323225145750459698245869852592649420353 over
GF(1093538118232638385349847977804906439636928172831)
> time #E;
1093538118232638385349849358956326103449112176485
Time: 37.139
> p := RandomPrime(160); FF := GF(p); Ceiling(Log(p)/Log(2));
160
> E := EllipticCurve([Random(FF),Random(FF)]); E;
Elliptic Curve defined by y^2 = x^3 +
254333964416091265060085141020840397902022755973*x +
779403335311622566573649766805154572963450506864 over
GF(1080731695309159906748458354265553463923055755781)
> time #E;
1080731695309159906748459943545795241770307236876
Time: 53.350
2) Random 256-bit Examples.
> p := RandomPrime(256); FF := GF(p); Ceiling(Log(p)/Log(2));
256
> E := EllipticCurve([Random(FF),Random(FF)]); E;
Elliptic Curve defined by y^2 = x^3 +
33137765376849177908424892557119984288036597130186948944001887169389886819510*x +
77704226333709730919629709785188768728782755778861636002420024289850094170895
over GF(911526381380662270574322732111966035946743316523724146292911383398728679\
14267)
> time #E;
91152638138066227057432273211196603594808600743975696280361389273480519424835
Time: 384.170
> p := RandomPrime(256); FF := GF(p); Ceiling(Log(p)/Log(2));
256
> E := EllipticCurve([Random(FF),Random(FF)]); E;
Elliptic Curve defined by y^2 = x^3 +
31917786511342852248155691939025899839093934672739061327787107543613338911874*x +
31513172549555844404302323311578240635703912146092123675870567285541544494247
over GF(551581664134894229319335540039964014387607035595814779363852634380191452\
75279)
> time #E;
55158166413489422931933554003996401438492605414408171981109615799442554314386
Time: 603.180
> p := RandomPrime(256); FF := GF(p); Ceiling(Log(p)/Log(2));
256
> E := EllipticCurve([Random(FF),Random(FF)]); E;
Elliptic Curve defined by y^2 = x^3 +
46314632544840934632212974298772764899193126268291473007976836511218594921108*x +
62728462024751125822985747172719665293153367277882127891806247767944531506720
over GF(99533370662997727349826939640400686698533008088347009936204452732416031\
986137)
> time #E;
99533370662997727349826939640400686698201608094276045150354874873194970249505
Time: 378.470
> p := RandomPrime(512); FF := GF(p); Ceiling(Log(p)/Log(2));
> E := EllipticCurve([Random(FF),Random(FF)]); E;
Elliptic Curve defined by y^2 = x^3 +
37909824427643803444378525927928276232433424298251795396485851553638739352775\
29687870973486173564150034308766534388238524699512502359183096420469328375370*x +
48603809394571873178158124749873236395937851477790328999383162209132531912331\
60298232605466645436380544832779261247369871904279534125102380158538407796076
over
GF(490494250779005874282861218618113108919633808016639539096745396850379407898\
6239966292281116545671599374883854704279625110239385338569417843369601251520391)
> time #E;
4904942507790058742828612186181131089196338080166395390967453968503794078986294\
346445050083460625284648906411346837125029373612086766681045780469235752094
Time: 10700.969
------------------------------
From: [EMAIL PROTECTED] (Steve K)
Crossposted-To: alt.privacy.anon-server
Subject: Re: NEW PROGRAM = FREEDOM
Date: Thu, 23 Dec 1999 02:47:39 GMT
On Wed, 22 Dec 1999 18:11:03 +0100, "Thomas J. Boschloo"
<[EMAIL PROTECTED]> wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>[late reply, but I didn't think of this earlier]
>[also cross-posted to sci.crypt, as there was a similar post by Steve K
>on the disfuncioning of freedom together with AtGuard (lost the
>'references' header to that post]
>
>Steve K wrote:
>>
>> 1. Freedom can not co-exist with a PC firewall. It thinks it is a
>> firewall, and will fight with a real firewall for the right to control
>> port assignments. I confirmed this with their tech support. The
>> performance of this "firewall" feature is not documented, and since
>> Freedom does not provide any of the monitoring or logging options one
>> would expect of a firewall, I am inclined to call this "feature" a
>> giant glaring security hole.
>
>Maybe this cannot be avoided, as freedom (unlike jbn) filters mail and
>everything at a very low OS level.
It can easily be avoided, just re-write the network component of
Freedom to function as a proxy, and have the user apply proxy settings
in their browser and mail clients. Why they did not do this, is a
great mystery to me. So is the absense of criticism from government
agencies... nah, that's just the paranoia talking.
>And it wouldn't do their reputation
>much good if it was discovered that freedom keeps logs of everything you
>did!
I paid about 50 bucks for Private Desktop, and one of the most
important things it does is provide me with a log of everything that
comes and goes, or is prevented from so doing, on my network
connection. Once burned twice shy; I just happen to be paranoid about
trojans.
>Maybe this could become a feature that is normally 'unchecked' in
>future versions of freedom, but then there is the extra code which will
>allow for *more* security holes in the product itself due to a larger
>'bug probability' (more code=more bugs). I would not like freedom with
>logging capabilities and run my firewall on a seperate computer, like
>you really should to be secure (I think).
I would be happy to accept the (more code = more bugs) proposition, in
exchange for a clear view of what my network transport layer is doing.
As it is, Freedom is a blindfold: "Trust me."
>The other thing is that the software runs at such a low level that it
>just captures all low level internet traffic and doesn't allow any other
>processes to send their own stuff across the internet.
I hope so, becuase if it doesn't do that, and do it well, people will
start complaining very loudly when their over-confident "protected"
surfing nets them a rack of trojans. And see below on that...
>Allowing the
>firewall on your local machine to take over traffic and send it's own
>stuff would be even a bigger security breach! It is just a 'hostile'
>application to freedom and so it should be.
A PC firewall is supposed to take over all network port assignments on
your machine, and apply a rule set you have chosen, as to what is and
is not allowed to communicate. It is the opposite of a security
breach. It is positive user control.
The only real security breach I see here, is an application that
should function as a local proxy, but instead functions as a firewall
killer.
>The other way around, freedom is a hostile application to AtGuard
>because it bypasses the firewall. And so this should be again. They just
>can't coexist, even if they wanted to. It's against their nature.
Right. And that's a bug in Freedom. A fundamental design flaw,
seemingly based on the assumption that the users will prefer instant
ease of use, to having to set their browsers, mail, and news clients
to use Freedom as a proxy. If Freedom was a proxy, it would co-exist
easily with a PC firewall.
In their own paper, at
http://www.freedom.net/info/freedompapers/Freedom-Security.pdf,
the word "firewall" does not occur, and the word "trojan" only occurs
once, in this paragraph:
"Hackers will generally use search engines, trojan horse software, and
network monitoring (much like a sysadmin) to gather information about
someone. Depending on their level of interest, they have also broken
into credit reporting agencies, police computers, and other places
with crappy security to gather information."
Elsewhere it says:
"Back Orifice, WhoWhatWhere, NetBus, Systems Management Server, PC
Anywhere, and other remote management tools totally compromise your
privacy if the administrator so chooses. Freedom does not contain
defenses against these, because they are inherent to Windows, and we
can not protect you against them."
Not only is this incorrect, it contradicts what the tech support folks
told me about Freedom "being" a firewall. I guess they interpret the
word broadly. That goes along with saying that credit agency and
police computers have "crappy" security.
>> 2. Comparing Freedom to PGP is like comparing apples to lug nuts.
>> Their missions are totally different. Freedom adds *no* security to
>> the contents of email, it only obscures the sender's identity. And
>> might I add, Freedom does not obscure the sender's identity as well as
>> conventional remailers.
>
>You should compare Freedom with nym servers, as it allows people to
>reply to messages you have send. But still nym servers combined with 3
>chained mixmaster remailers would probably win. Although I guess freedom
>will be plenty more reliable (and I for one don't like my mail server to
>lose messages).
Ya got me there. Not having used Freedom as a nym server when I was
checking it out, I don't have any idea of its reliability. But I did
read the release notes, where it mentions that the Freedom mail system
is vulnerable to traffic analysis. Good of them to say so!
>> But Freedom is not a "real" security utility; it is closed source, so
>> we have to take their word for its cryptographic strength; and it
>> prevents the user from running a real firewall, which is really bad,
>> because network intrusions are the number one method for defeating
>> cryptographic software.
>
>Worth quoting, but I would like to add that freedom offers
>'pseudonimity/anonimity', not 'security' as pgp does (although both use
>encryption).
Right you are, and if the crypto is broken, so is the anonymity. It
probably isn't broken, but read their documents: It looks like the
marketroids are in charge over there, and that bodes ill for the
health of programming efforts aimed at security.
For my own part, I find that I can get quite adequate pseudonymity or
anonymity without resort to Freedom.
I'm not really down on Freedom, it certainly has its place: Lots of
people are willing to pay for a hassle free improvement in their
expectation of privacy on the Internet. And compared to a default
Windows configuration without accessories, I am sure that Freedom is a
*tremendous* improvement.
Steve K
---Continuing freedom of speech brought to you by---
http://www.eff.org/ http://www.epic.org/
http://www.cdt.org/
------------------------------
Date: 23 Dec 1999 02:58:48 -0000
From: [EMAIL PROTECTED] (Legrange)
Subject: Re: Of one time pads, plaintext attacks, and fantasy
>Of course trying to break a cipher is very difficult! But that's not
>the same thing as impossible.
Actually, as the problem was laid out in the original message, its not
just "difficult"...... it really is impossible. The only way around it
is the brut force attack outline in the "PS". At least, that's all I
can see.
------------------------------
** 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
******************************
