Cryptography-Digest Digest #378, Volume #10 Fri, 8 Oct 99 20:13:02 EDT
Contents:
Re: David A. Huffman, "father" of compression died yesterday (Sundial Services)
Re: US Crypto Policy: free speech? (Medical Electronics Lab)
Re: books about elliptic curves (Medical Electronics Lab)
Re: DES breaker Technique? (Paul Koning)
Re: Using PGP as a source of random numbers (SCOTT19U.ZIP_GUY)
Re: Is 128 bits safe in the (far) future? (SCOTT19U.ZIP_GUY)
Re: Compression of encrypted data ("ashwood")
UPDATE: ACM CCS'99 (Rump Session, Registration and Program) (ACM Conference on
Computer and Communication Security)
----------------------------------------------------------------------------
Date: Fri, 08 Oct 1999 11:46:41 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: comp.compression
Subject: Re: David A. Huffman, "father" of compression died yesterday
Only the Internet would allow any of us to know that Mr. (Dr.?) Huffman
had died, or prompt any of us to see him as -- not just a figure in a
textbook we all read in college, but a human being who lived and
breathed... and thought, in ways that no one else did at the time.
Only the Internet would prompt us to ... offer our condolences to David
Huffman's nephew. :-/
SCOTT19U.ZIP_GUY wrote:
>
> In article <gnnL3.96$ET5.1587@client>, "Ken Huffman" <[EMAIL PROTECTED]> wrote:
> >My uncle, David A. Huffman, creator of Huffman coding, died yesterday of
> >pancreatic cancer.
> >
> I did not know his name was David A. Huffman. But since my name is
> David A. also I liked this letter.
> >While getting his masters degree, a professor gave his students the option
> >of solving a difficult problem instead of taking the final exam. Opting for
> >what he thought was the easy way out, my uncle tried to find a solution to
> >the "smallest code" problem. What his professor DIDN'T tell him is that no
> >one at that time knew the best solution. As the term drew to a close, David
> >realized he'd have to start studying for the exam and starting throwing away
> >his scratchings on the problem. As one of the papers hit the trash can, the
> >algorithm came to him.
> Did he solve the ending problem so that it could stop nicely in an 8 bit
> file. I think I have and I will not patent it either. But my mods to adaptive
> huffman coding make a compression program that maps any 8-bit byte binary
> file to a 8-bit byte binary file in such a way that any file can be considered
> a compressed or uncompressed file. This is of great use in things like
> encryption where other compresssion techniques leave clues to one trying
> to break the encryption.
> >
> >He published the paper "A Method for The Construction of Minimum Redundancy
> >Codes" describing his algorithm in 1952. This became known as Huffman
> >coding. At the time he didn't consider copyrighting or patenting it,
> >because was just an algorithm, and he didn't make a penny off of it.
> >Because of its elegance and simplicity, it is described in may textbooks and
> >several web pages. I just saw a posting on this newsgroup of a description
> >of Huffman coding: http://www.astraware.com/program/vbhuffman.html. Today
> >derivative forms of Huffman coding can found in household appliances
> >(VCRPlus+ codes) and web pages (the Jpeg image file format).
> >
> >He eventually became a professor at UCSC School of Engineering. In recent
> >decades, his interest turned to the complex mathematical properties of
> >zero-curvature surfaces. "Proofs" of his concepts led to elegant paper
> >foldings (http://www.sgi.com/grafica/huffman/) which belie their complex
> >mathematical origins. Some of them have even been displayed in art museums.
> >
> >He received several awards for his contributions to computer science during
> >his career, most recently he was awarded the 1999 IEEE Richard W. Hamming
> >Medal (http://www.ucsc.edu/oncampus/currents/98-99/05-17/huffman.htm),
> >recognizing his exceptional contributions to information sciences and
> >systems. Unfortunately he was not able to receive the award in person, due
> >to his ill health.
> >
> >He was a great person to be around; always good-natured and thought
> >provoking. Conversations with him kept you on your toes, because you
> >couldn't always tell if was joking or serious, but always with an apropos
> >story. As an school-aged kid, I remember playing the game of Nim
> >(http://www.journey.sunysb.edu/Wise/Games/Nim.html) with him on the living
> >room floor and being amazed, and frustrated, that he ALWAYS won. He later
> >wrote out the strategy, in a detailed long-hand note to me, explaining the
> >concepts of binary exclusive-or arithmetic. A bonding moment with a fellow
> >geek, of sorts. Partly because of his interest in computers, I followed his
> >footsteps into software engineering.
> >
> >He stayed active until cancer spread through his body this past year. To an
> >Ohioan, he seemed to be a typical Californian. A surfer and scuba diver
> >into his 70s. He married his girlfriend of a few decades last week in the
> >hospital. Although I was not there, I was later told it was beautiful
> >ceremony. His new bride and close family were with him at the hospital when
> >he died. He was loved and will be missed.
> >
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: US Crypto Policy: free speech?
Date: Fri, 08 Oct 1999 12:46:33 -0500
entropy wrote:
> I'm aware that U.S. laws consider strong crypto algorithms a
> munition, and thus regulate their export. However, when these
> algorithms (source code) are printed, it is protected as free speech,
> so it can be freely exported.
>
> Would the same be true for other, conventional munitions? If I
> printed out the schematics of an F-16 fighter jet, or an advanced
> machine gun, would that also be protected under free speech, and thus
> exportable? Is this only true for non-classified munitions?
It depends on where the schematics came from. Many such things
are "born secret", meaning they were developed in a US government
lab and given to a manufacturer who has signed an agreement not
to release the info because it's covered by national security laws.
If the schematics are in the public domain, then yes, you can
export the plans on paper. If they are supposedly "secret", then
no, you can't.
There is one case where the US government can stop free speech.
This is under the Atomic Energy Act of 1954 which makes all
descriptions of nuclear weapons "born secret", no matter who thinks
of it or where. There was a case here in Madison where a local
(communist type) magazine was going to print an article describing
nuclear weapons in some detail. The feds told them they couldn't
and it started to go thru the court process, before the article was
printed! A lot of shenanigans ensued on both sides, and finally the
magazine went and printed it anyway. So the case became moot and
forgotten. The AEA of '54 still stands, but it'll never be
enforced (I hope!).
At this point, the feds won't touch anything on paper. Paper is
a pretty slow transmission mechanism, so they are working hard
at maintaining some control over electronic discourse. Both
Junger and Bernstien are attacking that front, so it should be
interesting over the next year or so to see how that all works out.
In any event, descriptions of weapons that are created secret
remain secret and any dissemination method will get you into
deep doo-doo.
(I think the name of that magazine is the Progressive, and it
may still be in print)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: books about elliptic curves
Date: Fri, 08 Oct 1999 12:50:24 -0500
jerome wrote:
> i am not but i like to read books i don't understand :)
> in fact i especially like the moment when i understand, at last.
> the joy of learning :)
Yeah, me too :-)
> The meneze's book is sold 120 $us. The one of blake et al is sold 40 $us.
> I read 'handbook of applied cryptography' by A.Meneze et al. It is
> very clear and understandable. I suppose that his book about elliptic
> curves is as good.
> But 120$us is indeed overpriced especially if it is a bit outdated.
> i will try it if i don't understand the blake et al.
Get the Menezes book from the library, or thru interlibrary loan then.
It's not worth 3 times the other!
> i already read it and want a more 'in-depth' approach.
Cool :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: DES breaker Technique?
Date: Fri, 08 Oct 1999 16:22:21 -0400
Andrew Brydon wrote:
>
> Once upon a time, UBCHI2 <[EMAIL PROTECTED]> wrote
> >When the group won the RSA challenge and cracked the DES message, how did they
> >know when they found the right key? Did they have to search for english words
> >after trying out the right key? Or did they just wait until they had factored
> >the key?
> >
> >
> Format of the first part of the message was 'known plaintext'.
Was it really?
The DES cracker doesn't depend on that, it can do probable
plaintext (e.g., if you know it's plain english text). See
the book.
paul
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Using PGP as a source of random numbers
Date: Fri, 08 Oct 1999 22:20:10 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>nosehat wrote:
>>
>> I'm making a OTP for communication between just two parties. So I need
>> lots (several CDs) of random numbers. Could I get these by encrypting
>> very large files with PGP's conventional encryption, then grabbing big
>> chunks out of the middle of these files? I guess I'm asking if PGP
>> encrypted files (minus header) are good noise, or if there are patterns
>> there (perhaps related to the block size??) Sure would be easier than
>> taking apart my smoke detector. :)
>
>
>The numbers you would produce would be unpredictable -- but no more
>unpredictable than those produced by considerably easier means, and in
>fact, perhaps much less so.
>
>The fact that a set of numbers was produced by "difficult" computational
>methods does not mean that they are more random or less random.
>
>The PGP source-code does provide clues to cryptographically secure
>PRNG's which might be useful in your quest.
The random numbers generated by PGP may not be cryptographically
secure. Same with any keys generated by this. I say this becasue of
post I have stumbled across that talk about using the Noise Sphere plots
of the numbers that PGP makes when it tries to make random files. You
can search the web your self to find this information since I doubt most
would belive me anyway.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Is 128 bits safe in the (far) future?
Date: Fri, 08 Oct 1999 22:13:23 GMT
In article <7tle9f$a7s$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>There *are*, however, records kept of who mothered whom -- and who
>is believed to have fathered whom. Sometimes these are a matter of
>public record; often, these are private records. For example, the
>Mormons have a huge geneological database.... I shudder to think of
>the use our hypothetical dictator could make of the Mormon database.
>
The morman use the data only to keep there people busying and to
give them selves an inflated ego. Like to say my dad was head of the CIA
or whatever. They also use it to find people in the past so they can claim
that George Washington and Tomas Jefferson where mormans since you can
contact your dead ancestors and make them members. I wonder what they
teach in history classes in Utah. I don't think a dictator would care about
the Morman data base unless the Mormans take control of the country and
decide to use it as an excuse to kill all non mormans. After all the Catholics
did that in the middle ages and the mormans are not that different than what
the catholics where a few centuries ago. I use to work with a Bishop of the
morman church and he admitted that if the President of the Morman Church
siad kill all outsiders He knowing that the president of there church is
not capable of making a mistake would have to carry the orders out. To
me that is the sign of a cult far more dangerous than the Waco people every
was. But since many FBI and CIA and NSA agents are morman this is one
cult that has nothing to fear from our government. But us non mormans just
have to hope as there group ages that more mormans become like catholics
and relize that there leader is just a man. But that is not the case today and
governemnt for some strange reasom seems not to care.
>> Look
>>at even today there are large questions of who actually fathered dianas kids.
>
>Which, in addition to being rude, is completely irrelevant. You really
>think that this dictator would order DNA tests before shipping people
>off to firing squads?
Yes that was rude of her. But then again she is British.
And no I don't think that they would order DNA tests just before
shipping people off to firing squads. But the british and americans
are not to far off from requiring this kind of information in some
sort of data base. Of course we can trust our governemnts to
only use the data base for wholesome puposes. Or can we?
>
> -kitten
>
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: "ashwood" <[EMAIL PROTECTED]>
Subject: Re: Compression of encrypted data
Date: Fri, 8 Oct 1999 16:07:35 -0700
Crossposted-To: comp.security.pgp.discuss,alt.security.pgp
Douglas A. Gwyn (IST/CNS) <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Actually, substitution of syllables, words, and/or phrases by shorter
> code groups has been done for many centuries.
But those all required prior knowledge of what would be encoded, Huffman
does not, although to build the tree does require some knowledge.
> Obviously, machine compression of encoded data wasn't a particularly
> relevant research area before the advent of modern computers.
But as you pointed out in your last paragraph, there has been a desire to
decrease the size of a message for many centuries, which takes knowledge of
the expected set of words
> > by other methods). Now assuming that it takes a mere 50 years of time to
> > develop a good huffman encoding for something the complexity of English
...
>
> Why on Earth would we make such an erroneous assumption in the first
> place?
The statement I made was not erroneous, even now, even after having
computers around for a significant amount of time, we are still finding
better huffman trees for encoding english, albeit very rarely (and we've
been looking for over a decade). It also takes a significant body of text to
provide for the efficient coding, something we do not have enough of yet to
compress modern encrypted blocks, and something that has taken a larger
amount of time than I have indicated, and of course as English changes so
will the occurance of characters/words/phrases, which means that the most
optimal coding will change over time. But even if it takes .01 second, and
takes linearly more time for each block, adding the complexity needed for
even DES would mean 2^64/(size of English language) seconds, since the size
of the english language is significantly less than 1,000,000 words the
complexity is still in the millenium timeframe (in fact about the 140
millenium range). This of course only applies at the block by block level,
but the analysis of DES that has been performed should long ago have
uncovered if any smaller repeat occurances were more likely.
> This general subject goes by the name "source coding", and there is
> abundant information about it on the Internet.
The biggest problem is not finding a way to do the encoding, the ways to do
it are quite well known. The two biggest problems are in fact getting a
large enough body of text to do an efficient encoding of many differing
texts, and finding the time to execute the program. Neither of which did you
even bother to consider, you simply _assumed_ (quite wrongly) that I am
purely uneducated in all matters of language and compression, and taht I
would simply accept your statements as correct, when in fact you provide no
references to support your concept. Now if you can present any relevant
information that does anything besides support my point I welcome it, but
all you have shown so far is an ability to say something like "well I think
your wrong, and my proof in on the internet" when in reality even the
internet resources I have found would indicate that it takes a finitely
small amount of time, using a finitely small amount of text to build even
the most rudimentary tree, having to multiply these by large exponents of 2
results in fairly large numbers for the time.
Basically I think what I failed to make clear is that fact that there is a
very basic rule of compression, a single static compression tree can only
compress 1/2 of the texts, the other half will be enlarged by it. Only by
having a large body of text can you hope to make your tree compress the
majority of used strings (eg I would not expect a method of compressing
English to be optimal for Chinese). As of this moment it is the large body
of text that is difficult to come by for encrypted blocks, but also once we
have this body, we will be able to create probability trees to aid in the
decryption. If one were to find a perfect encryption method (including
perfect RNG, and many others), the compression tree would be of no use
because there would be a perfectly equal probability of any of the potential
ciphertexts, regardless of the input stream. Hmm, maybe I was wrong in my
first post, I hadn't thought of my last point there. Of course if we put
forth the effort to attempt to build this tree, we might be able to
determine, to a degree, the actual strength on the cipher.
Joe
------------------------------
From: [EMAIL PROTECTED] (ACM Conference on Computer and Communication Security)
Subject: UPDATE: ACM CCS'99 (Rump Session, Registration and Program)
Date: 8 Oct 1999 14:15:22 -0700
UPDATE: ACM CCS'99 (Rump Session, Registration and Program)
6th ACM Conference on Computer and Communications Security
November 1-4, 1999
Kent Ridge Digital Labs
Singapore
Conference Home Page: http://www.isi.edu/ccs99/
Registration: http://homex.s1.net.sg/user/jyzhou/ccs99.html
E A R L Y R E G I S T R A T I O N D E A D L I N E !!!
=========================================================================
Early registratuion deadline is approaching fast! To obtain a lower
registration fee, please register on or before October 10.
=========================================================================
R U M P S E S S I O N
For the first time, there will be a rump session at the upcoming ACM CCS.
The rump session is intended to be an informal venue for short presentations
on recent results, work in progress, and other topics of interest to the
research community. This includes presentations that are not purely
technical in nature. The rump session will take place on Wednesday afternoon,
November 3.
Those wishing to give a talk at the rump session must submit a short
abstract, no more than one page long, to the rump session chair, Giuseppe
Ateniese.
Submissions can be emailed in ASCII only (one page at most) to
[EMAIL PROTECTED] by Thursday, October 28, or handed in person at the
conference before 5pm on Tuesday, November 2. All talks will be at most
5 minutes long.
=========================================================================
PROGRAM UPDATE: panel on November 3
Panel topic: On The Importance Of Provable Security
Panel Chair: Dan Boneh, Stanford
Panelists:
- Christian Cachin, IBM Research Zurich
- Cynthia Dwork, IBM Research Almaden
- Ari Juels, RSA Labs
- Guillaume Poupard, ENS
=========================================================================
------------------------------
** 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
******************************
