Cryptography-Digest Digest #786, Volume #10 Thu, 23 Dec 99 12:13:01 EST
Contents:
Re: "Variable size" hash algorithm? (Gregory G Rose)
Classic Cryptanalysis Tools Needed ("Leslie Wagner")
Re: QPK (Mok-Kong Shen)
Re: Schoof's algorithm ("Michael Scott")
Re: More idiot "security problems" (SCOTT19U.ZIP_GUY)
Forged PGP Key ([EMAIL PROTECTED])
Re: Classic Cryptanalysis Tools Needed (Boaz Lopez)
Re: Classic Cryptanalysis Tools Needed (Tom St Denis)
Re: Classic Cryptanalysis Tools Needed (JPeschel)
Re: Of one time pads, plaintext attacks, and fantasy (Dave Hazelwood)
Re: More idiot "security problems" ("Trevor Jackson, III")
Re: Implementing ElGamal (Anton Stiglic)
Re: More idiot "security problems" ("Trevor Jackson, III")
Re: Forged PGP Key (Johnny Bravo)
Re: Classic Cryptanalysis Tools Needed (John Savard)
Re: More idiot "security problems" ("Trevor Jackson, III")
Re: More idiot "security problems" ("Trevor Jackson, III")
Re: Of one time pads, plaintext attacks, and fantasy (Scott Fluhrer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: "Variable size" hash algorithm?
Date: 22 Dec 1999 19:59:18 -0800
In article <[EMAIL PROTECTED]>,
Dan Day <[EMAIL PROTECTED]> wrote:
<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).
<
<Is there such an animal? Or do most cryptographically
<useful hash algorithms generally produce a fixed-size output,
<without an option to specify the desired output hash size?
I believe "HAVAL" is your answer. It's a variable
length hash algorithm from well-respected authors
(Pieprzyk, Seberry, ...). Published in one of the
Springer-Verlag journals some years ago.
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: "Leslie Wagner" <[EMAIL PROTECTED]>
Subject: Classic Cryptanalysis Tools Needed
Date: Wed, 22 Dec 1999 23:37:57 -0500
Does anyone have any crib dragging and shotgun hill climbing routines or
programs thay can share?
Thanks you,
Les Wagner
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: QPK
Date: Thu, 23 Dec 1999 11:03:29 +0100
Ian Goldberg wrote:
>
> Medical Electronics Lab <[EMAIL PROTECTED]> wrote:
> >Mok-Kong Shen wrote:
> >> But I do like to know what is your definition of 'probabilistic
> >> encryption'. Do you mean a process where at some step a decision
> >> is made depending on the output of a (deterministic) pseudo-random
> >> generator or else on a truly random event which even the legitimate
> >> receiver of the encrypted message can't know/predict? The first
> >> case would only be an application of PRNG (I used it in one of my
> >> schemes), while in the second case the receiver has no easier job
> >> than the analyst, or do I miss something?
> >
> >You encrypt with something that does not have a unique inverse.
> >If you know the key, there may be 4 or 8 "decryptions". By checking
> >all of them, you can figure out which is the correct one by some
> >other item in the data. The recipient does not know which one
> >is right a priori, they have to check them all.
> >
> >In this case, you add 2 or 3 bits to the the analyst's task over
> >finding the key. For the receiver, checking 8 possible decryptions
> >is trivial.
>
> Hmm. I don't think that's the _usual_ definition of "probabilistic
> encryption". What you describe is more like the differential workfactor
> stuff used in, for example, the export version of Lotus Notes. The
> sniffer needs to try 2^64 keys to break the message, but the "intended"
> recipient (the NSA) is told 24 of them, so they only need to try 2^40
> keys (easy!). :-)
>
> What I usually call "probabilistic encryption" is where the space C of
> ciphertexts is partitioned into a number of subsets, each corresponding
> to an element of the space P of plaintexts. This partitioning and
> corresponding is key-dependent, of course. The output of an encryption
> of a given plaintext is a *random* element of the subset of C which
> corresponds to that plaintext. So _encryption_ of a message can take on
> a large number of values. In contrast, _decryption_ is unique; given
> any element of C, it is in exactly one of the partitions, which
> corresponds to exactly one element of P.
>
> This notion is most commonly used in public-key cryptography, where
> *anyone* can calculate the encryption function. Without it, for example,
> decrypting a message which is known to be either "yes" or "no" would be
> trivial; just encrypt both of those messages, and see which matches.
> With probabilistic encryption, there are too many possibilities for the
> encryption to try them all.
>
> The simplest way to do probabilistic encryption is just to pad the
> message with some randomness before encrypting it. Exactly how you do
> this, though, is algorithm-dependent, and, it turns out, subtle.
I don't think that my question has been answered, namely whether
the legitimate receiver has less work to do to decrypt the message
than the analyst. If yes, I like to know why this is so. My point
was that there has to be shared by the communication partners some
secret (deterministic) information equivalent to certain key bits.
In other words, 'probabilistic' has to be 'deterministic' to be useful
in crypto at all.)
M. K. Shen
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Schoof's algorithm
Date: Thu, 23 Dec 1999 11:25:21 -0000
Scott Contini <[EMAIL PROTECTED]> wrote in message
news:83s1do$5r2$[EMAIL PROTECTED]...
>
> 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".
>
Actually I was quoting some-one else. This is the received wisdom, but the
received wisdom is wrong. In fact Schoof's algorithm is quite usable
assuming one only wants to find one suitable curve on which to implement
one's cryptographic scheme. And this is interesting, as for hyper-elliptic
curves only schoof-type algorithms are available. But of course the SEA
algorithm is always superior for elliptic curves.
> 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.
>
I said awkward to use, not awkward to implement. But in fact Schoof's
algorithm is also simpler to implement. Try it and see! On a modest 32Mb
machine it runs quite smoothly and memory requirements are not in fact
excessive. Download ftp://ftp.compapp.dcu.ie/pub/crypto/schoof.exe to your
kids home PC (its less than 150,000 bytes), and type for example
schoof -f 65112*2#144-1 -3 49
> 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.
>
Not my intention! Didn't want to use excessive bandwidth. If you look at the
comments at the start of ftp://ftp.compapp.dcu.ie/pub/crypto/sea.cpp you
will find complete timings for the SEA algorithm, which are comparable with
your own.
>..snip
Mike Scott
=====================
Fastest is best.
MIRACL multiprecision C/C++ library for big number cryptography
http://indigo.ie/~mscott
> David Kohel
> (and Scott Contini)
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: More idiot "security problems"
Date: Thu, 23 Dec 1999 13:25:25 GMT
In article <83rs69$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (David
Eppstein) wrote:
>[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?
You could just shuffle the order of the items and check if they are in
order. If not shuffle again.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
"The road to tyranny, we must never forget, begins with the destruction of the
truth."
------------------------------
From: [EMAIL PROTECTED]
Subject: Forged PGP Key
Date: Thu, 23 Dec 1999 12:58:48 GMT
http://www.securitywatch.com/scripts/news/list.asp?AID=1707
A key for sending e-mail to CERT was forged.
csybrandy
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Boaz Lopez <[EMAIL PROTECTED]>
Subject: Re: Classic Cryptanalysis Tools Needed
Date: Thu, 23 Dec 1999 05:40:38 -1000
Leslie Wagner wrote:
>
> Does anyone have any crib dragging and shotgun hill climbing
> routines or programs thay can share?
>
> Thanks you,
>
> Les Wagner
Yes, there is a click and drag crib spreadsheet available from
ATRA Corp. The multidimensional sorting utility is automatic.
The so called "shotgun hill climbing" is implemented using
an expandable disk-cache scheme, with unlimited volume. Based on
the Koligranikova-Samolian Recursion, the hill-climbing is
the matrix expansion while the shotgun section depletes the
candidate list. It was $129 when I bought by Crypto-Pak for
Windows 98.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Classic Cryptanalysis Tools Needed
Date: Thu, 23 Dec 1999 14:24:35 GMT
In article <83s8ol$9dh$[EMAIL PROTECTED]>,
"Leslie Wagner" <[EMAIL PROTECTED]> wrote:
> Does anyone have any crib dragging and shotgun hill climbing routines
or
> programs thay can share?
What on earth are you talking about? Just saying 'cryptanalysis' tools
is like saying classic medical tools... Kinda ambigous
What are you trying to evaluate/break?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Classic Cryptanalysis Tools Needed
Date: 23 Dec 1999 15:10:51 GMT
Tom St Denis [EMAIL PROTECTED] writes:
>In article <83s8ol$9dh$[EMAIL PROTECTED]>,
> "Leslie Wagner" <[EMAIL PROTECTED]> wrote:
>> Does anyone have any crib dragging and shotgun hill climbing routines
>or
>> programs thay can share?
>
>What on earth are you talking about? Just saying 'cryptanalysis' tools
>is like saying classic medical tools... Kinda ambigous
>
>What are you trying to evaluate/break?
>
Looks like he was fairly specific to me: he asks for
crib dragging and shotgun hill climbing routines
or programs. These are tools to mount a known-plaintext
attack, often against classical ciphers. Sometimes
"known-plaintext" isn't known, it's guessed.
A while ago, Gillogly posted such a crib dragging routine.
Maybe he will again and you can play with, and change,
his code.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Dave Hazelwood <[EMAIL PROTECTED]>
Subject: Re: Of one time pads, plaintext attacks, and fantasy
Date: Fri, 24 Dec 1999 00:06:47 +0800
[EMAIL PROTECTED] (John Savard) wrote:
>On Wed, 22 Dec 1999 00:51:35 GMT, [EMAIL PROTECTED] wrote:
>
>>I know that in general, that was a technique sometimes used during
>>wartime to break enemy ciphers. But the more I thought about it, I don't
>>see how that would work with a one-time system.
>
>You're right, it couldn't.
>
>>The system in question was based on generating a pseudo-random sequence
>>(using a Riemann-zeta function) and then adding it mod(26) to the
>>plaintext.
>
>But that isn't a one-time system. So it could work there, because a
>cryptanalyst might recognize the mathematical pattern in the _pseudo_
>random sequence.
But are there not an infinite number of pseudo-random pads that will
yield different readable text when xor'd with any message ? How can
you ever know when you have recognized the "right" one ?
A clever approach might be to wrote an innocuous message and then
encrypt it with a recognizable mathematical patterened key and then
create another pad that deciphers it into your real message?
I still think this is the best form of crypto. Each message stands
alone and must be broken and you can never be sure you have the right
answer.
Algorithmic encryption on the other hand yields the answer to all
messages when it is factored, can be brute forced or otherwise
compromised.
If I were the NSA, I would not only hope everyone would use
algorithmic techniques but would go out of my way to discredit
the alternative. No?
------------------------------
Date: Thu, 23 Dec 1999 11:13:46 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
Dan Day wrote:
> On 19 Dec 1999 00:18:36 GMT, [EMAIL PROTECTED] (Xcott Craver) wrote:
> >
> > Now, if the program is capable of decrypting the data too,
> > then you have a problem.
>
> But I believe that that's the case under discussion here. Eric
> was talking about copy-protection schemes, wherein a program keeps
> part of itself encrypted or otherwise "locked", but the program
> itself knows how to "unlock" itself when it thinks it's running
> on an authorized machine.
>
> By definition, it seems to me, such a program "is capable of
> decrypting the data" that it needs.
>
> Eric's point is that such a system can always be broken just
> by "looking over its shoulder" as it does its dirty work on itself.
The analysis process may require access to the original machine, so a simple
copy of the program is not enough. If the attacker can perform the attack on
a legitimate machine the program can always be modified to suit. But if the
attacker has only the program (binary), it is not always possible.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Implementing ElGamal
Date: Thu, 23 Dec 1999 11:18:38 -0500
==============7F576D7F5238A15302CA980F
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
For a little example, say we are working with p = 7.
What is 2^{-1} (that is, what is the inverse of 2) mod 7.
Well, it's the integer X such that X*2 mod 7 = 1.
In this case, we know that 4*2 mod 7 = 1, so the answer
is X = 4. That is, 2^{-1} = 4.
To compute it in a general way, you may use the extended
Euclidean algorthm as mr. Stell said.
Anton
==============7F576D7F5238A15302CA980F
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<pre>For a little example, say we are working with p = 7.</pre>
<pre>What is 2^{-1} (that is, what is the inverse of 2) mod 7.</pre>
<pre>Well, it's the integer X such that X*2 mod 7 = 1.</pre>
<pre>In this case, we know that 4*2 mod 7 = 1, so the answer</pre>
<pre>is X = 4. That is, 2^{-1} = 4.</pre>
<pre>To compute it in a general way, you may use the extended</pre>
<pre>Euclidean algorthm as mr. Stell said.</pre>
<pre></pre>
<pre>Anton</pre>
</html>
==============7F576D7F5238A15302CA980F==
------------------------------
Date: Thu, 23 Dec 1999 11:50:25 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
Dan Day wrote:
> On Thu, 16 Dec 1999 20:12:38 -0500, "Trevor Jackson, III" <[EMAIL PROTECTED]>
> wrote:
> >This problem is rampant, esp with sort(). About a dozen years ago someone, a
> >magazine I think, ran a contest for the worst fielded sort routine. Last I heard
> >the winner was an O(N^6) algorithm.
>
> Good GOD!
>
> 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 literally don't think I could write a sort algorithm that bad if I tried to.
It has been a while and I do not recall the details. I do recall that it was a
multi-level deal. Some storage mechanism automatically sorted items (poorly) using
default criteria. A programmer wanted to extend the sort criteria, and did so on top
of the default sort. Both the original sort and the modified sort were supposed to
work on "a few" elements, which is defined by the Bible as eight. Since the IO for
the elements completely dominated the time required for the sort, nobody noticed.
Then someone made another modification that raised the count to 50 or 100, and the
problem surfaced.
I wish I could remember how the result got to O(N^6). The only way I could
reconstruct this would be by stacking a pair of O(N^3) sorts. That might happen if
the second programmer reused the O(N^3) algorithm created by the first, but I don't
recall the details that well. Sorry.
I've seen O(N^3) routines used in visual layout tools that are based on lists (which
don't support random access) instead of arrays. The excuse was "to avoid the
performance penalty of dymanic memory management" caused by resizing arrary. Of
course this works when a user put a dozen objects in a layout region. But when
someone pastes 3,000 objects the performance advantages of dynamic memory management
become apparent ;-)
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Forged PGP Key
Date: Thu, 23 Dec 1999 11:44:35 GMT
On Thu, 23 Dec 1999 12:58:48 GMT, [EMAIL PROTECTED] wrote:
>http://www.securitywatch.com/scripts/news/list.asp?AID=1707
>
>A key for sending e-mail to CERT was forged.
>
>csybrandy
Or more properly, faked. It has neither the correct fingerprint or
the keyid of the actual CERT key. Unless someone is intercepting mail
going to CERT, the only effect will be that CERT won't be able to read
or verify the signatures on messages sent to them with that key.
The most likely reason for this is so that someone can spread a fake
virus warning and appear to be signed with the CERT key.
This is why you verify your keys before you accept them as valid.
One such way would to get the key directly from CERT
http://www.cert.org/contact_cert/encryptmail.html
Best Wishes,
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Classic Cryptanalysis Tools Needed
Date: Thu, 23 Dec 1999 09:46:16 GMT
Boaz Lopez <[EMAIL PROTECTED]> wrote, in part:
>Leslie Wagner wrote:
>> Does anyone have any crib dragging and shotgun hill climbing
>> routines or programs thay can share?
>Yes, there is a click and drag crib spreadsheet available from
>ATRA Corp. The multidimensional sorting utility is automatic.
>The so called "shotgun hill climbing" is implemented using
>an expandable disk-cache scheme, with unlimited volume. Based on
>the Koligranikova-Samolian Recursion, the hill-climbing is
>the matrix expansion while the shotgun section depletes the
>candidate list. It was $129 when I bought by Crypto-Pak for
>Windows 98.
I saw a recent reference in another thread to the power of the
"shotgun hill-climbing" technique. Web sites describing it?
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Thu, 23 Dec 1999 11:56:06 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
David Eppstein wrote:
> [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?
Well, it's possible that I'm repeating a Programming Legend kind of story, but
the contest was definitely restricted to fielded systems. Otherwise you'd have
the time penalties of spacially abusive algorithms included.
One such is to generate all possible permutations on one pass and evalute them on
a second pass. This is O(N*N!) I think, but the space usage is also O(N!) which
is guaranteed to cause thrashing on any existing architecture.
------------------------------
Date: Thu, 23 Dec 1999 11:58:29 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
SCOTT19U.ZIP_GUY wrote:
> In article <83rs69$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (David
>Eppstein) wrote:
> >[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?
>
> You could just shuffle the order of the items and check if they are in
> order. If not shuffle again.
I suppose this would be worse than O(N!). More like O(2^(N-1)).
Let's see, if we use a universal compression mechanism on the elements does it raise
the work
factor to O(2^N) ?
(I know this is a cheap shot, but we're so far off topic I'm stretching for relevance
;-)
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Of one time pads, plaintext attacks, and fantasy
Date: Thu, 23 Dec 1999 17:07:35 GMT
In article <83p7al$kut$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>Towards the end of "Cryptonomicon" by Stephenson (interesting
>novel by the way, anybody know of any others that use crypto as a plot
>device??)
_The_Gold_Bug_, Poe
_A_Fire_upon_the_Deep_, Vinge
--
poncho
------------------------------
** 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
******************************
