Cryptography-Digest Digest #657, Volume #9 Fri, 4 Jun 99 13:13:02 EDT
Contents:
Re: OTP Problems (Andrew Haley)
Re: Is SSL CPU intensive? (Paul Rubin)
Re: Cryptography CENSORED on web site? (Mok-Kong Shen)
Re: bareface ratio (Rich Lafferty)
Re: PGP probability of choosing primes? (Bob Silverman)
Re: SHA-1 output random? (Lincoln Yeoh)
Re: Challenge to SCOTT19U.ZIP_GUY (Lincoln Yeoh)
Re: Finding a 192 bit hash (Was: Using symmetric encryption for hashing) ("Thomas J.
Boschloo")
Re: Schoof's Algorithm ([EMAIL PROTECTED])
Re: Challenge to SCOTT19U.ZIP_GUY ([EMAIL PROTECTED])
Re: New Computer & Printer for Dave Scott (Lincoln Yeoh)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Andrew Haley)
Subject: Re: OTP Problems
Date: 4 Jun 1999 14:21:28 GMT
Matthias Bruestle ([EMAIL PROTECTED]) wrote:
: [EMAIL PROTECTED] wrote:
: > A case in point. I'm pretty impressed with the specs of the iButton
: > device. The current (initial) version stores about 2^10 bits in a
: > physical device that is reasonably easy to deal with, yet is probably
: > secure against anything less than "national technical means". Certainly
: I doubt it can withstand a skillfull student. (See papers of Kuhn&Anderson)
Is this assertion based on any knowledge?
The last time that I saw Markus Kuhn he recommended something like an
iButton to counter his methods of attack.
Andrew.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Is SSL CPU intensive?
Date: Fri, 4 Jun 1999 15:16:40 GMT
Thierry Moreau <[EMAIL PROTECTED]> wrote:
>Establishing a session requires public key computations on the server,
>at a bare minimum one full Diffie-Hellman exponentiation each time a new
>client comes to the server. Your actual requirements might exceed this.
>Fisrt approximation, a 20MHz 68030 may take in the order of 1 to 20
>seconds to set up a brand new SSL connection.
Diffie-Hellman is a relatively new feature of SSL and is only present
in recent versions. SSL is in practice almost always done with RSA,
which is faster than DH for the same modulus size. A really careful
implementation on the 20 MHz 68030 should be able to do 1024 bit RSA
in maybe one or two CPU seconds. (The bnlib implementation included
with SSLEAY/OpenSSL is just about as good as can be done). Of course
if you only have 30% of the cpu available, that increases the number of
elapsed seconds it takes to get the needed CPU cycles.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cryptography CENSORED on web site?
Date: Fri, 04 Jun 1999 17:09:48 +0200
[EMAIL PROTECTED] wrote:
>
> I had finally intended to get around to adding a proper discussion of the
> one-time system to my web site. But I didn't want to change the numbering
> of the sections to chapter 6 - the one on miscellaneous topics. So I
> looked at the page on polyalphabeticity, and found that the one-time pad
> was not mentioned, even though in preceding pages, the straddling
> checkerboard was described - but with no mention of what it was used with.
>
> Then, in chapter 4, I find I mention the two-tape system as insecure - but
> not even a hint is given that Vernam went on from that to produce a
> one-time tape machine.
Perhaps my English knowledge is not good engough, but I don't
clearly (unambigiously) understand what you wrote. However, your
title line suggested that someone has illegally modified your
HTML file. I don't think that could happen with any high probability.
Unless your page contains really top secrecy, nobody is likely to
be motivated to take the trouble to cause damage to your file.
The chance I can see is that you might have different versions of the
HTML file and you unintentionally uploaded the wrong version.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Rich Lafferty)
Crossposted-To: comp.lang.perl.misc
Subject: Re: bareface ratio
Date: 4 Jun 1999 15:12:46 GMT
Jerome O'Neil <[EMAIL PROTECTED]> wrote:
>
> I have derived a new unit of measurement for measuring usenet threads
> called the 'pedant.' A long thread's length is guaranteed to be at least
> two pedants long.
>
> O'Neil's corollary to Goodwin's Law: "The length of a thread needed to
> prove Goodwin's Law is inversely proportional to it's pedant measure."
Godwin, dammit. Godwin.
(You wanted it. :-)
-Rich
--
Rich Lafferty -----------------------------------------------------
IITS/Computing Services | Carpe canum!
Concordia University |
[EMAIL PROTECTED] -------------------------------------[McQ]--
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: PGP probability of choosing primes?
Date: Fri, 04 Jun 1999 14:52:00 GMT
In article <[EMAIL PROTECTED]>,
Geoff Thorpe <[EMAIL PROTECTED]> wrote:
> Hi there,
>
> Bob Silverman wrote:
>
<snip>
> > In article <7iq213$k7$[EMAIL PROTECTED]>,
The upshot of that work was that there are
> theoretical results which say it is not that "critical" a problem. Ie
> the entropy arguments say (in my words, not the author's) that the
> entropy in sequential primality searching for primes of size "x" bits
> equivalent to the entropy in a true random primality search for primes
> of size "y" bits where I think y was x*2/3
This should be x^(2/3)....
... this is from the deep
> recesses of my memory so I could be WAAAY off here.
Actually, it is fairly easy to show that the entropy must be a
fractional power of x, but AFAIK, the exact power is not known.
>
> prime). Does anyone know what the distribution of distances between
> > > primes is for numbers of lenth L/2?
> >
> > No. Noone does. It is an unsolved, open, mathematical problem.
> > It is known, however, that most of the prime gaps will be about
> > log(L/2) (the Prime Number Theorem would be false, otherwise).
>Exceptions are rather rare. It is known, for example, that as L -->oo
> > the set of primes which are preceeded by a gap less than any fixed
> > power of loglog L have density 0. It is not known, however,
> > how many primes are preceded by a gap of about (log L)^delta
> > for delta < 1.
>
> I'm not so sure ... I'm pretty sure I agree that there's no conclusive
> result that answers all the questions, but I think there was some work
> done on the probability distribution of "gaps" ... the mean of which
> as you say, about log(L/2).
Actually, it is the case that not only do we not have a PROOF, but that
the distribution is NOT known. Cramer's conjecture states, for example,
that there is always a prime between x and x + (log x)^2. Recent
work by Hildebrand and Maier on the distribution of primes in short
intervals suggests that Cramer's conjecture MAY be false. But noone
really knows. The true answer might be x + (log x)^(2 + epsilon)
for any epsilon > 0, or it might be x + (log x)^2(loglog x) or
Cramer's conjecture might be true. The exact answer isn't KNOWN.
>And because the gaps do vary in a
> non-trivial distribution, entropy is lost when doing a sequential
> primality search for precisely the reason you mentioned ... so, in
> theory, it is equivalent to searching for primes randomly (ie.
> "properly") of a smaller size - but I don't think anyone's published
> exploitation of this ... and given the best current factoring methods,
> it's hard to imagine them developing in a direction that allows them t
> suddenly start "checking out primes with big gaps before them" in
> preference [;-)
General factoring methods don't care. Only special methods like P-1
would care. And the work of Canfield,Pomerance, and Erdos suggests
that the distribution of smooth numbers in short intervals will
conform to what probability says it should based on the distribution of
PRIMES in short intervals. This comment was a bit sloppy. Basically,
there is no reason to believe that if p and p + k are prime and
k is small relative to p that either p-1 or p+k-1 should be more
smooth than randomly chosen odd numbers of the same size.
>
> As it turns out, I came up with a workaround for this
Does the workaround extend to finding primes in an A.P? Sometimes
one wants to restrict to finding primes p such that p-1 and p+1
have particular prime factors. This means a sequential search
over primes in the A.P. such that p = 1 mod p1 and p = -1 mod p2.
>I don't think
> anybody knows if this issue is a big deal at all, even the known
entropy
> loss is not disastrous
As I said, it is TINY. (a fractional power of x is small relative
to x for x in the range being considered [512 bits]). If the exponent
is (2/3), then the loss in entropy is 2^(2/3 * 512)/2^512 i.e.
about 1 part in 2^170.
> and it hasn't even been demonstrated to be usable yet).
It won't be usable by GNFS or QS under any conditions.
> > > How much does this weaken PGP?
> >
> > Zero. In fact, the question assumes that an attack would depend on
the size
> > of the keyspace and that somehow an incremental search procedure
(as used by
> > PGP) reduces the size of that space in a measureable way. It would
be
> > impossible to measure exactly the reduction in keysapce caused by an
> > incremental search procedure, but it would be TINY. Firstly, the
procedure
>
> Nope, it's definately been quantified using an entropy argument,
But saying that the entropy reduction is (say) O(x^2/3) really
doesn't measure it exactly, except to verify that it is indeed tiny.
> > really doesn't reduce the keyspace. It simply makes some keys more
likely
> > that others. Secondly, there are ~ 3.7 x 10^151 512 bit primes.
The set of
> > primes which have a low probability of being selected are only a
very tiny
> > fraction of these.
>
> That depends on the distribution of the gaps ... I think it's more
than
> you think - Log(L/2) is just the mean, there's no reason the
> distribution should be "thin".
Gaps are bounded by [2, (log L)^k] for some k. It is known
that small gaps have density zero. However, the density of gaps
of the size (log L)^delta for delta < 1 is not known. It is
known that the density of gaps which are bounded by C log L is 1.
(PNT would be false otherwise).
> > > Do primes which have a large distance from the next smallest
prime have any
> > > peculiar features that might make them more susceptible to being
> > > cracked?
>
> That happens to be my main concern with this "problem" ... I really
have
> no worries AT ALL that normal factoring techniques might speed up
> algorithmically if its known that the prime factors are more likely to
> have "big gaps" in front of them. What I AM a little worried about is
> that primes that have extremely abnormal length blocks of non-primes
in
> front of them, exhibit desirable (for the cryptanalyst) properties.
What are those properties??? Please specify.
> Nobody has managed (as far as I know) to put a non-trivial upper-bound
> on the size of "gaps" for numbers of "x" bits,
False. It is fully proven that there is always a prime between
x and x + x^(11/20 + eps). GRH would lower this to x + x^1/2 log x.
Even if Cramer's conjecture is a little bit wrong, there is
certainly always a prime between x and x + (log x)^k for some
reasonably small k (even though a proof is lacking and we don't
know the true value of k)
so it's possible that
> there's a large number (proportionally) of primes out there with
REALLY
> BIG gaps in front of them.
No. This would make PNT false. The set of primes preceded by very
large gaps must have density 0 for PNT to be true.
>This makes them (a) likely to turn up in
> people's keys with a much higher probability than perhaps they should,
Impossible on PNT
>
> and (b) dangerous if they exhibit special properties
What are these properties to which you refer? One property
(smoothness of p-1 or p+1) is no more likely than for uniformly
random integers.
>
> > What did you have in mind? The Number Field Sieve (the fastest
> > factoring attack) only depends on the size of the number being
> > factored. That the size of the modulus does not depend on
> > how the primes were selected. Other, special purpose attacks
> > are worse than useless on numbers of this size.
>
> True - and I'm not really worried about the (slim) possibility of
> factoring speedups from this phenomena.
>
> > And the short answer to your question is: NO. They have
> > no special features.
>
> That is definately less certain ... People have discussed at length
> prime pairs (??) where two sequential odd numbers are both prime (eg
3 &
> 5, 11 & 13, 17 & 19, 29 & 31, etc). Considering the opposite
properties,
> namely where there is a large block of sequential odd numbers that are
> NOT prime would seem to me just as worth-while
It HAS been considered. The work on Cramer's conjecture is just this.
> Or get a surprise visit from the NSA [;-)
Please. Even with the smiley, comments like that have no place
in a discussion such as this.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: SHA-1 output random?
Date: Fri, 04 Jun 1999 16:25:48 GMT
Reply-To: [EMAIL PROTECTED]
On 01 Jun 1999 19:45:08 +0200, Florian Weimer
<[EMAIL PROTECTED]> wrote:
>I don't think so, because the data you get from /dev/urandom is
>generated based on an entropy pool using SHA-1. That's the reason why
Ok.
>Are there any one-way hash functions which could be used instead?
MD5, but there are some weaknesses. There are a few others as well.
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Fri, 04 Jun 1999 16:50:02 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 03 Jun 1999 18:58:37 +0100, David Crick <[EMAIL PROTECTED]> wrote:
>> maybe I helped with explaning the above cut of code as you
>> can see it made perfect since to me.
>>
>> It is readable!!
>
>*sigh*. You really don't get it do you? The whole point is for
>it to be immediately obvious to OTHER people who may wish to
>verify/develop your code.
He is probably be better at reading and writing code than English. So what
is immediately obvious to you is not to him, and vice versa.
I have long suspected he may have some sort of dyslexia or reading
disability that makes it difficult for him to write/type out stuff
accurately. Not sure if this is true, but so far it seems a likely
explanation.
Anyway, a few people have attempted to look at his code:
Andrew Carol
<[EMAIL PROTECTED]>
Anonymous
<[EMAIL PROTECTED]>
Still I think the main problem is he has difficulty seeing other people's
point of view as well.
I'm not sure if Scott has tried reading OTHER people's obscure uncommented
code, like he said he has difficulty with long variable names so he
probably would have problems too.
So think about it Scott, they have difficulty with short variable names
without any comments, you have difficulty with long variable names. A
compromise would be for you to add comments to sections of your code, I'm
sure they wouldn't mind a few speeling errors, as long as it's easier to
figure out what each section is trying to achieve.
Analogy you are giving a recipe in terms of "A" "B" and "C".
Do Xyz on A, Do Izz on B etc.
Of course you know exactly what you are cooking, and why you are doing
certain things halfway. But they obviously don't.
What would help is if you comment things
Do Xyz on A
# Here's where I break the cooked potato into small bits
Do Izz on B
# Here's where I mix the broken up potato and cheese together
# We'll heat them up later but meanwhile we will do the following first...
I hope you understand what I mean.
It's a lot more work, but if you do it your code will definitely be read
AND understood by far more people. And maybe even appreciated as well.
Good luck,
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: "Thomas J. Boschloo" <[EMAIL PROTECTED]>
Subject: Re: Finding a 192 bit hash (Was: Using symmetric encryption for hashing)
Date: Fri, 04 Jun 1999 18:28:03 +0200
[EMAIL PROTECTED] wrote:
>
> > Thanks for answering my question! But now I have a new problem; If I
> > want to use something like Rijndael-192 for symmetric encryption, how do
> > I hash my conventional passphrase. Surely there are some solutions for
> > this?!
>
> For passphrase hashing you simply want to perform some kind of
> costly processing to turn the passphrase into the key (costly
> so that it thwarts dictionary attacks but not too costly that
> it becomes a burden on the legitimate user) and you also want
> it to be "unpredictable" (in the sense that it can't easily be
> bypassed - e.g. partial info on the passphrase giving partial
> info on the key).
That is where my original suggestion failed )-;
> These things usually take the form of an iterated hashing mechanism
> of some kind, but as I've never actually looked into the pros and
> cons of what to do in this situation, I'll refrain from suggesting
> any kind of ad-hoc mechanism and hope that somebody else knows of
> a good way of doing it instead :-)
The experts in this group seem awefully silent, so I guess my questions
are just too boring for them to reply to :-( But I did a websearch on
'192' and 'hash' and found out that HAVAL can be run in 192 and 256
mode! I guess that this answers my question if I ever get in the mood
for writing a "K.I.S.S." public key crypto product (which uses and
reveals as less info as possible).
Regards & so long everybody,
Thomas
BTW K.I.S.S. [equ] Keep It Simple Stupid!
--
"The early worm gets eaten by birds"
PGP key: http://x11.dejanews.com/getdoc.xp?AN=453727376
Email: boschloo_at_multiweb_dot_nl
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Schoof's Algorithm
Date: Fri, 04 Jun 1999 15:16:28 GMT
I will look at the code. I was wondering if there are any papers/faqs
on the use of elliptic curves in cryptography. Certicom has a bunch of
white papers but I have only gotten thru a few. I think I saw a e.c
faq somewhere... any pointers?
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Fri, 04 Jun 1999 15:12:32 GMT
> I have been a programmer for over 30 years. I could give a dam what
> they say about style. Style is just a tem used so that programmers
> who can' program waste a lot of paper and then management is under
> the illusion that they porduces something. Style is used to force
creative
> programs in a mold that they don't need.
So what. They mean the following
1. Comments, in algorithm comment any non-trivial line
2. Variable names which are realistic (longer then two vars). You are
correct in assuming simple indexing can be done with short vars (I
personally use 'i', 'i2' etc...) but actuall algorithm related counters
should have names.
3. Modular. Use functions to make source that is conceptually easy to
follow.
If you have been programming for '30 years' you would know this (I have
been programming for only five...)
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: New Computer & Printer for Dave Scott
Date: Fri, 04 Jun 1999 16:52:25 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 02 Jun 1999 16:06:11 GMT, "Gus James" <[EMAIL PROTECTED]> wrote:
>not hampered by the primitive hardware he works on, he could perhaps improve
>the legibility of his code. It would certainly inspire him to make the next
Legibility/illegibility of his code has little to do with his computer.
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
** 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
******************************
