Cryptography-Digest Digest #569, Volume #10 Mon, 15 Nov 99 09:13:05 EST
Contents:
Re: Ultimate Crypto Protection? ("Douglas A. Gwyn")
Re: Ultimate Crypto Protection? ("Douglas A. Gwyn")
Re: Schneier's how to be a cryptanalyst paper ("Adam Durana")
Re: EncryptedChat V2 Dead ? (Jerry Coffin)
Re: EncryptedChat V2 Dead ? (JPeschel)
Re: intelligent brute force? (Keith Monahan)
Re: Proposal: Inexpensive Method of "True Random Data" Generation ("Trevor Jackson,
III")
Re: Proposal: Inexpensive Method of "True Random Data" Generation ("Trevor Jackson,
III")
Question about ElGamal ("Mark Trade")
Session Key by SCI ("wheelie")
Re: Elliptic-curve cryptography (Pascal Nourry)
Re: Ultimate Crypto Protection? (Johnny Bravo)
New NSA patent explicity mentions machine transcription (Peter Tonoli)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Ultimate Crypto Protection?
Date: Mon, 15 Nov 1999 04:37:28 GMT
HJS wrote:
> But only by 'practical cryptanalysis' i.e. theft, and not by
> pure cryptanalysis.
Nope.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Ultimate Crypto Protection?
Date: Mon, 15 Nov 1999 04:37:44 GMT
"Trevor Jackson, III" wrote:
> Sure. Copy the pad or substitute a known pad.
Nope.
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: Schneier's how to be a cryptanalyst paper
Date: Mon, 15 Nov 1999 01:05:33 -0500
Heh 2 32bit sub keys to a cipher with a 64bit key size. I don't know what I
was thinking, possibly I wasn't at all. I would still like to know what
attack I should be using though.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: EncryptedChat V2 Dead ?
Date: Sun, 14 Nov 1999 23:09:53 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> [EMAIL PROTECTED] (Jerry Coffin) writes in part:
>
> >287895462580028491
> >5832864341798915401
> >
> >Found in less than 30 seconds on a 400 MHz Pentium II, using
> >factor.exe, a free factoring program available from:
> >ftp://ftp.compapp.dcu.ie/pub/crypto/factor.exe
>
> I used Pollard-Rho on the other number and found an answer pretty quickly,
> but the program is still chewing on the composite number you factored.
>
> What method does factor.exe use?
It actually has a number of different methods - brute force, Pollard's
p-1, Brent's, William's p+1, Lenstra's elliptical curve and MPQS. It
basically starts with the easy ones and progresses to the more complex
ones if the earlier ones don't succeed (or at least leave large
composite factors).
In this case, it found the factors courtesy of Bob Silverman, so to
speak -- I.e. using MPQS.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: EncryptedChat V2 Dead ?
Date: 15 Nov 1999 06:25:36 GMT
[EMAIL PROTECTED] (Jerry Coffin)
>It actually has a number of different methods - brute force, Pollard's
>p-1, Brent's, William's p+1, Lenstra's elliptical curve and MPQS. It
>basically starts with the easy ones and progresses to the more complex
>ones if the earlier ones don't succeed (or at least leave large
>composite factors).
>
>In this case, it found the factors courtesy of Bob Silverman, so to
>speak -- I.e. using MPQS.
I downloaded it, and is it fast! Thanks for the link.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Keith Monahan <[EMAIL PROTECTED]>
Subject: Re: intelligent brute force?
Date: Mon, 15 Nov 1999 01:24:09 -0500
Douglas,
Thanks for the response.
Douglas A. Gwyn wrote:
> Keith A Monahan wrote:
> > Has anyone written a paper or a chapter in a book describing methods of
> > brute forcing intelligently, before resorting to a full-scale search?
>
> That's a contradiction in terms. A "brute force" attack *means*
> simply trying every possible decryption key and testing the result
> to see if it has plaintext characteristics.
Ok. Sure. Perhaps I phrased the question incorrectly. But the basicquestion
remains, what are some effective ways of sequence guessing
a passphrase? Dictionary attacks have certainly proved themselves
worthwhile. Are there other methods? If you've seen Alec Muffet's
Crack or PCL (Password Cracking Language), there are some
other alternatives prior to a full search. I'm looking for a reference
(if one exists) which might outline various possibilities.
> How you test the
> plaintext is relatively unimportant, since for most cryptosystems
> and most plaintext sources, correct plaintext will have high
> coherence by almost any sensible statistical test and incorrect
> "plaintext" will have low coherence ditto.
>
Well, sure, but that's not the question at hand - assuming a functionexists
which takes a passphrase as input, and returns either a
correct or incorrect answer. In my situation, a function like that IS
available, so I don't have to worry about testing the resultant plaintext.
My mentioning of digrams/trigrams in the previous message was
for the purpose of constructing test passphrases with them, not
testing the decrypted output for statistical properties.
> A better question would be, what are some more clever means of
> cryptanalysis than a brute-force attack?
Agreed, that is a better question. Now what are some answers? :)
Keith
P.S. I'm looking for smarter ways to construct test passphrases.
Although it shouldn't matter, the algorithm involved is 256 bit
Blowfish in CBC mode. Brute forcing the passphrase is
computationally difficult due to its length and composition.
------------------------------
Date: Mon, 15 Nov 1999 02:14:11 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
[EMAIL PROTECTED] wrote:
> Trevor Jackson, III ([EMAIL PROTECTED]) wrote:
> : This confusion exists because within your definition of randomness as
>incompressibility you
> : are using the term randomness with a different meaning, specifically, that of
>being selected
> : or generated unpredictably.
>
> I should join in, since in another branch of this thread, I made a similar
> suggestion.
>
> Of course, randomness means what you say: generated unpredictably.
>
> However, there is a general intuition that an incompressible sequence is
> random-looking. (Assuming it's being compared to something random with a
> uniform distribution, of course.)
There is certainly sense in which indistinguishable entities are equivalent. If a
sequence (Pi
starting at the hex digit corresponding to my age in seconds) appears haphazard it
matters not how
it was generated. The haphazardness is an intrinsic property of the sequence. We
expect a
sequence generated stochasitcally to have this haphazard quality, and most instances
from a
uniform distribution have it. But some do not.
Thus there are distinguishing characterisitics of incompressible sequences vs
stochastic
sequences. Claiming one type as a synonym for the other is fundamentally flawed.
>
>
> And that intuition has some validity.
>
> An incompressible sequence can be safely used as the key for a
> one-time-pad...because if it is incompressible, that means that it can't
> be "easily guessed". Actual random means of generation are simply used to
> ensure incompressibility...because a sequence can be compressible without
> that being easy to determine.
This verges on the claim that RNG outputs should be filtered for compressibility prior
to use.
The definition of incompressible as random contributes to this suggestion.
How would you address the following issue? An incompressible string used once is no
more
compressible than prior to use. But an unpredictable sequence (shorthand for a
sequence generated
stochastically) is no longer unpredictable after use.
> 14159 26535 89793... compresses to "the decimal part of pi", but any
> sequence of numbers can compress to "the contents of the one-time-pad that
> I secretly photographed"...
By this definition all [sufficiently long] strings, even infinite ones, are
compressible. What
ever mechanism specifies/describes/locates the string is a compressed reference to the
string
>
>
> There _is_ a sense in which true incompressibility means "as good as
> random", since it does mean haphazard, not generated by a simple rule.
What is the disctinction between "true" incompressibility and (I suppose) "pseudo"
incompressibility? Are references to sequences pseudo-compressions?
Is there an instance of a truly incompressible sequence?
------------------------------
Date: Mon, 15 Nov 1999 02:24:38 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Coen Visser wrote:
> "Trevor Jackson, III" wrote:
>
> > Coen Visser wrote:
>
> > > I thought that the arbitrary large but constant factor O(1)
> > > was understood. [...]
>
> > Your constant (the degree of compression of strings containing repeated "01")
>
> That is not what the constant *additional* term +O(1) means.
> The words "constant factor" might falsely suggest that it is something
> multiplicative; I've got to be more careful with what I write.
I was not referring to your constant O(1). I believe it to be irrelevant to the
claim you made of compressing all strings of the form "01"*.
Your proposal was to prepend a code bit to every possible string indicating whether
the remainder should be interpreted literally or as a repeat count for "01". You
claimed that this constituted compression of the set of strings of the form "01"*.
I observed that the cost of any such compression distributed over the universe of
all strings was larger than the space saved. Only by considering the probabalistic
properties of the source would compression be useful.
This distinction is based on the difference between compressing one string and
compressing a set of strings. The single string compresses to nothing. A set of
strings worst case compression (uniform distribution) is logarithmic on the
cardinality of the set. A set of strings best case compression (probabalistic
model) is identical to the Shannon Information contained in the set of strings.
Thus, unless you amplify your treatment of compressibility to include sets of
strings, you are only dealing with the degenerate case of single strings. And
there are no incompressible single strings.
------------------------------
Reply-To: "Mark Trade" <[EMAIL PROTECTED]>
From: "Mark Trade" <[EMAIL PROTECTED]>
Subject: Question about ElGamal
Date: Mon, 15 Nov 1999 07:57:00 GMT
I have a question about ElGamal encryption, more specially about the private
key. As far as I understand it is composed by P (prime), G (G < P) and Y
(Y=G^X mod P where X is the private key and X < P).
In "Applied Cryptography" I read that P and G can be shared among a group of
users, but what about Y? Should the public key be PG or PGY?
I tried it with simple numbers and found out that a message can't be decoded
with PG of the sender and X of the receiver, but I am afraid I missed
something...
Thanks for your help
-Mark
------------------------------
From: "wheelie" <[EMAIL PROTECTED]>
Subject: Session Key by SCI
Date: Mon, 15 Nov 1999 10:07:31 +0100
I stumbeld over crypto cards from SCI called Sesion Key does anyone know if
there are drivers available and what the card is compatible with?
------------------------------
From: Pascal Nourry <[EMAIL PROTECTED]>
Subject: Re: Elliptic-curve cryptography
Date: Mon, 15 Nov 1999 11:00:43 +0100
The book of M. Rosing is a reference for me
http://www.browsebooks.com/Rosing/
This book include a complete crypto library in C
I have adapted it to a SSL3.1 protocol and it's working very well :-)))
(SSL3.0 = is the mostly secure protocol used on Internet).
You can also look to Certicom White paper
http://www.certicom.ca/ecc/index.htm
There is a IEEE draft which discribed ECC :
http://grouper.ieee.org/groups/1363/index.html
Be careful, Elliptic Curve theory is not easy.
If you have any pb, i think you can ask on this newsgroup.
Yours,
P.N.
--
********************************************************
Pascal NOURRY
email : [EMAIL PROTECTED]
page personnelle : http://www.gmm.insa-tlse.fr/~nourry
********************************************************
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Ultimate Crypto Protection?
Date: Mon, 15 Nov 1999 06:32:52 GMT
On Sat, 13 Nov 1999 17:58:21 GMT, [EMAIL PROTECTED]
(HJS) wrote:
>But you know, OTP key only needs to be unpredictable, not high
>quality random. Rolling dice is a good way of generating
>highly random numbers, but the range of numbers is restricted
>and the process is very slow. The dice COULD also be loaded!
Slow yes, restricted no. You can get any possible output you want
from dice (even without counting the commonly available 4, 8, 10, 12,
20, 30 and 100 sided dice)
Roll dice, 1 to 3 is equal to 0, 4 to 6 is equal to 1. Instant
binary representation, convert to whatever base you need. And it
need not be that slow (for small text messages anyway). Roll the dice
64 at a time, drop them into a frame that is 8x8 and just read off the
values.
Best Wishes,
Johnny Bravo
------------------------------
From: Peter Tonoli <[EMAIL PROTECTED]>
Subject: New NSA patent explicity mentions machine transcription
Date: 15 Nov 1999 11:42:31 GMT
In today's Indy:
http://www.independent.co.uk/news/Digital/Features/spies151199.shtml
By Suelette Dreyfus
15 November 1999
The US National Security Agency has designed and patented a new
technology that could aid it in spying on international telephone
calls. The NSA patent, granted on 10 August, is for a system of
automatic topic spotting and labelling of data. The patent
officially confirms for the first time that the NSA has been
working on ways of automatically analysing human speech.
The NSA's invention is intended automatically to sift through human
speech transcripts in any language. The patent document
specifically mentions "machine-transcribed speech" as a potential
source.
Bruce Schneier, author of Applied Cryptography, a textbook on the
science of keeping information secret, believes the NSA currently
has the ability to use computers to transcribe voice conversations.
"One of the holy grails of the NSA is the ability automatically to
search through voice traffic. They would have expended considerable
effort on this capability, and this indicates it has been
fruitful," he said.
To date, it has been widely believed that while the NSA has the
capability to conduct fully automated, mass electronic
eavesdropping on e-mail, faxes and other written communications, it
cannot do so on telephone calls.
While cautioning that it was difficult to tell how well the ideas
in the patent worked in practice, Schneier said the technology
could have far-reaching effects on the privacy of international
phone calls.
"If it works well, the technology makes it possible for the NSA to
harvest millions of telephone calls, looking for certain types of
conversations," he said.
"It's easy to eavesdrop on any single phone call, but sifting
through millions of phone calls looking for a particular
conversation is difficult," Schneier explained. "In terms of
automatic surveillance, text is easier to search than speech. This
patent brings the surveillance of speech closer to that of text."
The NSA declined to comment on the patent. As a general policy, the
agency never comments on its intelligence activities.
Yaman Akdeniz, director of Cyber-Rights & Cyber-Liberties UK,
warned that with the new patent and a proposed AT&T and BT joint
venture, which will allow US law enforcement agencies to tap the
new communications network: "We might have a picture in which all
British communications are monitored by the NSA."
The revelation of the NSA's patent is likely to cause tensions with
the European Parliament. Over the past two years, the Parliament
has commissioned several reports which examined whether the NSA has
been using its electronic ears for commercial espionage,
particularly in areas where US corporations compete with European
and other companies.
The NSA relies on an international web of eavesdropping stations
around the world, commonly known as Echelon, to listen into private
international communications. The network emerged from a secret
agreement signed after the Second World War between five nations
including Australia, New Zealand, Canada, Britain and the US. Two
of the NSA's most important satellite listening stations are
located in Europe, at Menwith Hill in Yorkshire and Bad Aibling in
Germany.
Julian Assange, a cryptographer who moderates the online Australian
discussion forum AUCRYPTO, found the new patent while investigating
NSA capabilities.
"This patent should worry people. Everyone's overseas phone calls
are or may soon be tapped, transcribed and archived in the bowels
of an unaccountable foreign spy agency," he said.
One of the major barriers to using computers automatically to sift
through voice communications on a large scale has been the
inability of machines to "think" like humans when analysing the
often imperfect computer transcriptions of voice conversations.
Commercial software that enables computers to transcribe spoken
words into typed text is already on the market, but it usually
requires the machine to spend time learning how to understand an
individual voice in order to produce relatively error-free
text. This makes such software impractical for a spy agency which
might want automatically to transcribe and analyse telephone calls
on a large scale.
It is also difficult for computers to analyse voice conversations
because human speech often covers topics that are never actually
spoken by name. According to the NSA patent application, "much of
the information conveyed in speech is never actually spoken
and... utterances are frequently less coherent than written
language".
US Patent number 5,937,422 reveals that the NSA has designed
technology to overcome these barriers in two key ways. First, the
patent includes an optional pre-processing step which cleans up
text, much of which the agency appears to expect to draw from human
conversations. The NSA's "pre-processing" will remove what it calls
"stutter phrases" associated with speech based on text.
Second, the patent uses a method by which a computer automatically
assigns a label, or topic description, to raw data. If the method
works well, this system could be far more powerful than traditional
keyword searching used on many Internet search engines because it
could pull up documents based on their meaning, not just their
keywords.
Dr Brian Gladman, former MoD director of Strategic Electronic
Communications, said that while he doubted the NSA had deployed the
patented system yet, the new technology could become a "potent
future threat" to privacy.
"If the technology does what it says automatically finding and
extracting the meaning in messages with reasonable accuracy then it
is way ahead of what is being done now," he said.
The best way for people to protect their private communications was
to use encryption, he said. Encryption software programs scramble
data to prevent eavesdropping. "I'm afraid widespread interception
is a fact of life and this is what makes encryption so important,"
he said.
"The problem in the UK is that our government is working with the
US to prevent UK citizens defending themselves using encryption,"
he said, referring to the continuing use of export controls to
hamper the widespread availability of encryption products.
The NSA's current spy technology may be more advanced than methods
described in the patent because the application is more than two
years old. The US Patent Office approved the patent on 10 August
this year, but the NSA originally lodged the application on 15
April 1997. The US Patent office keeps all applications secret
until it issues a patent.
------------------------------
** 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
******************************
