Cryptography-Digest Digest #854, Volume #8 Wed, 6 Jan 99 12:13:02 EST
Contents:
Re: New Twofish Source Code Available (KloroX)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Birthday Attack calculations. ([EMAIL PROTECTED])
Re: symmetric vs various asymmetric [was: DH is "stronger" than RSA?]
([EMAIL PROTECTED])
Re: Help: a logical difficulty (John Briggs)
On leaving the 56-bit key length limitation (Harald Brinck)
Re: Help: a logical difficulty (R. Knauer)
Re: U.S. Spying On Friend And Foe ([EMAIL PROTECTED])
Re: On the Generation of Pseudo-OTP ("Dr.Gunter Abend")
Re: What is left to invent? ("Sam Simpson")
Re: Help: a logical difficulty (John Briggs)
Re: symmetric vs various asymmetric [was: DH is "stronger" than RSA?] (David Crick)
Re: One-time pads not secure ? (NSA's Venona project) (Jerry Leichter)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (KloroX)
Subject: Re: New Twofish Source Code Available
Date: Wed, 06 Jan 1999 12:15:39 GMT
Reply-To: [EMAIL PROTECTED] (this is spam bait)
On Wed, 06 Jan 1999 00:08:11 GMT, [EMAIL PROTECTED] wrote:
[snip]
>scott19u.zip
Right, I could not find it. However, it was easy to find scott16u.zip
on several servers. I did not find the Sun JCE beta 2 either (yes, I
know you can get the beta 1 everywhere). Sometimes it just takes some
waiting, especially for non-glamorous or infrequently-used packages.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Crossposted-To: talk.politics.crypto
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 06 Jan 1999 12:15:37 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 05 Jan 1999 17:40:16 -0600, [EMAIL PROTECTED] (wtshaw) wrote:
>It comes down to whether their is a limit that can be enforced on logic.
>Those that pretend that they can arbitarilly make the world dumb-down to
>their rules are not too bright, as they just as well might try to
>legislate the weather.
Better yet, legislate the value of Pi equal to 3.20 like the Indiana
Legislature did. That way no one could ever use it in a digit
extraction cipher.
>Those is some parts of the world tremble when government speaks; most
>Americans don't. Many would like Americans to fear the law; we don't
>generally. We do obey those things which make sense to us, and thumb our
>noses at those that don't.
You sound like a Texan to me.
Most Americans - not to be confused with Texans - worship the pagan
gods of state authority. Just look who the US has for president.
If War Hero BJ (Bill Jefferson) had been governor of Texas, he would
be in prison by now.
>Politicos like to legislate the truth, to even changing the meanings of
>words, 1984-style, to suit their purpose.
Like War Hero said, "It all depends on what the definition of 'is'
is."
>Those in other countries, they are generally cannot understand American
>dynamics, and many have a history of self-imposed disasters.
We have had our share too, beginning with the War Of Northern
Aggression.
Keep in mind that Texas did not sign the surrender at Appomattox
Courthouse, and continued prosecuting the War well past the end of
hostilities elsewhere.
And the fight for Liberty has never ended for Texans either.
Bob Knauer
"The American Republic will endure, until politicians realize they
can bribe the people with their own money."
--Alexis de Tocqueville
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Birthday Attack calculations.
Date: Wed, 06 Jan 1999 12:54:24 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I would like to thank those who spent time in answering my question.
> It has proven to be very helpful.
>
> Terry Ritter wrote:
> >It might be interesting to know of an application where this sort of
> >precision is useful.
>
> The reason for the needed precision is that I am designing a variable
> length hash function and I want to test it for resistance to
> collision. Since I don't have the resources to do a full test for a
> 256 bit hash I am going to test 8, 16, 24, 32 and maybe 40 bit hashes
> and search for trends. If the algorithm is resistant to collision in
> the smaller sizes and there is no trend away from the "proper" value
> then due to the nature of the algorithm I can be quite confidant that
> the larger hashes are also resistant to collisions.
>
> Fred Van Andel
>
This is a very good idea. Since only if hash is any good will it
have the distribution predicticed by the bithday collision method.
However funny things do happen and though it is a very god idea
to check at the small lengths where more statisitics can be made.
You should always run tests on the final lenght your going to use
or you might get surprised.
david scott
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.security.pgp,comp.security.misc,talk.politics.crypto
Subject: Re: symmetric vs various asymmetric [was: DH is "stronger" than RSA?]
Date: Wed, 06 Jan 1999 13:03:46 GMT
In article <76upj3$14t$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bill Unruh) wrote:
> In <[EMAIL PROTECTED]> Anne & Lynn Wheeler <[EMAIL PROTECTED]> writes:
>
> >one approximation i've seen is that RSA "strength" is roughly
> >10**(sqrt(N))
>
> No!. This was (sort of) the time for the quadratic sieve. However the
> Number Field Sieve is more efficient for long keys.
> The statement is that it is roughly.
> with the coefficient in front and the value of "1.9" are both uncertain.
> e^(1.9 (ln(N)^(1/3) (ln(ln(N)))^(2/3)))
>
> On the other hand all such estimates are very rough and probably should
> not be believed. (eg the 1.9 I have seen postulated to be as low as 1.5
> and high as 1.93. That makes an enormous difference for large keys.)
>
This is why if one is using DH or whatever you should use the
largest that time and space wise is comfortable to your working
environment. Never use the lower limits experts suggest since this
is always a moving target.
David Scott
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: Help: a logical difficulty
Date: 6 Jan 1999 13:44:31 GMT
Reply-To: [EMAIL PROTECTED]
In article <76tmh9$[EMAIL PROTECTED]>, Jonah Thomas
<[EMAIL PROTECTED]> writes:
>[EMAIL PROTECTED] (John Briggs) wrote:
>>Of course, any algorithm worth its salt is going to let you supply
>>an arbitrary Turing machine in the input stream. And so you're looking
>>at a "plus a constant" worst case on the difference between the
>>algorithmic complexity of any two arbitrary input streams as
>>measured against any particular pair of salt-worthy, Turing-computable
>>algorithms.
>
>I may have missed your point here, this is somewhat new to me.
...
>
>In your example, are you saying that you want to measure the
>algorithmic complexity of your algorithm, plus the turing machine in
>its input stream, plus the string in the input stream?
That's not quite it.
Suppose we've got a output string O. Its algorithmic complexity
under algorithm A is x. This means that there is at least one input
string of length x that produces O when presented as input to A.
Call this string i.
And I've got an algorithm B. And I can write an emulator
for A, presenting it as input to B. Call this emulator e. This
emulator has length c.
Then e+i is an input string for B that produces O. Thus the algorithmic
complexity of O under B can be no more than x+c.
Take an example.
Say I've got a project which can be implemented in 1,000,000 lines
of C++. We are required to implement in Fortran. A naive estimate
is that it will take 100,000,000 lines in Fortran. Performance is
not a concern.
So we cheat, write a C++ interpreter in 100,000 lines of Fortran and
present our 1,000,000 lines of C++ as input to this interpreter for a
total of only 1,100,000 lines.
The "algorithmic complexity" of any project under Fortran can be
no more than 100,000 lines greater than the "algorithmic complexity"
of the same project under C++.
(Numbers made up out of whole cloth)
John Briggs
------------------------------
From: [EMAIL PROTECTED] (Harald Brinck)
Subject: On leaving the 56-bit key length limitation
Date: Wed, 6 Jan 1999 14:00:25
> 4. ADDING COMPRESSION
[...]
> g. the plaintext is compressed two times before encipherment, by a
> known algorithm.
> The new unicity calculation begins as the former one:
> H(K) = log2(2^56) = 56 bits
> |M| = log2(2^8) = 8 bits/compressed-character
> while for H(M) we need now to transform units:
> H(M) = log2(English) = 1.2 bits/character (the same as given in 3.)
> 1 character = 1/2 compressed-characters
> H(M) = 1.2*2 = 2.4 bits/compressed-character
One of the effects of compression is that the probability/frequency of
each character is (approximately) the same after compression. Otherwise
one could use Huffman or arithmetic encoding to compress the data even
further.
So not only does the compressed text include all 256 possible
characters, all of these characters have the same probability !
Doesn't that mean that
H(M)=|M|
and the unicity distance in infinite ?
Gruss,
Harald
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Help: a logical difficulty
Date: Wed, 06 Jan 1999 13:54:59 GMT
Reply-To: [EMAIL PROTECTED]
On 6 Jan 1999 13:18:14 GMT, [EMAIL PROTECTED] (John Briggs)
wrote:
>>> Since there does not exist an algorithm to deliver the shortest
>>> string to describe an arbitrarily given random number sequence,
>>> couldn't one say that the problem of determining the shortest
>>> description of a sequence is undecidable?
>>No, because one can simply generate all possible descriptions in
>>increasing order of size until one is found that generates the
>>sequence. (This is obviously not a very efficient algorithm.)
>>It is clear that a suitably defined interpretation architecture
>>can guarantee that such a description won't exceed 2*N+2 bits,
>>where N is the length of the sequence, so the search will terminate
>>within 2^(2*N+2) iterations (of a finite process).
>How do you decide whether a given description produces a given output?
>
>Hint: For most useful description languages, the halting problem is
>buried in there.
See Greg Chaitin's very illuminating discussions about this very
point, namely the connections among Godel's Theorem, Turing's Halting
Problem, and Mathematical Indeterminancy.
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
or when it is up: http://www.umcs.maine.edu/~chaitin/
Bob Knauer
"The American Republic will endure, until politicians realize they
can bribe the people with their own money."
--Alexis de Tocqueville
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: U.S. Spying On Friend And Foe
Date: Wed, 06 Jan 1999 12:59:18 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Mike McCarty wrote:
> > I didn't get in on the who quote, so I may be off base. But I
> > *certainly* find it humo(u)rous to find that someone thinks
> > that a Legislative Act can cause secrets to be kept.
>
> A severe law that is enforced can certainly act as a disincentive
> to disobedience.
>
Actually it can foster and fester disrespect for the rule of
law as a whole. It just drives open opposition under ground
so it later can erupt in more violence.
Bad laws create time bombs.
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Dr.Gunter Abend" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 06 Jan 1999 15:25:54 +0100
Mok-Kong Shen wrote:
>
> In light of the forthcoming 56-bit key length restriction it appears
> valuable to re-contemplate on all available techniques in cryptology
...
thereby sorting them into two classes: those obeying the 56-bit
restriction, and others. OTP violates the bound!
...
> (independent of whether they are favoured in current practice) in order
> to assess their value (even when employed as a minor 'adjuvant') in
> contributing to (combined) encryption schemes that can offer adequate
> security to confidential communications of innocent and law-abiding
> people of the world despite the severe limitation posed by the 56-bit
> key length upper bound. In this thread I propose therefore to discuss
> on the topic of pseudo-OTP.
> ... one needs
> only to record the offsets of the different streams participating
> in the pseudo-OTP that has been arrived at by the previously sent
> messages. The 'key' of the pseudo-OTP consists of the names of the
> texts and their very first starting offsets. (As a variety one could
> introduce some amounts of skips after each message sent). Since one's
> library (computerized to be quickly used) may contain a large number
> of texts, each having the potential of participating in the pseudo-OTP,
> the mere knowledge of the content of the library of the user is
> virtually useless to the analyst. Further, an almost unlimited number
> of pseudo-OTPs can be generated after some having been exhausted in
> actual communications.
The question of the 56-bit bound then refers to the size of the seeds
used for selecting the actual pseudo-OTP out of the common data base.
If you really want to obey the 56-bit bound, this method is as weak as
other techniques.
Of course, if the data base is hidden, i.e. the appointment about the
actual text (retrieved from e.g. the internet) is done along a secure
channel, this method may be safe, but: A program that *allows* the
use of an arbitrarily specified data base with an arbitrary offset as
a pseudo-OTP violates the 56-bit bound in the same way as PGP violates
the bound if it doesn't cut a long key down to the allowed size.
Thus, the real question is: Could there be a simple method of
trespassing the 56-bit bound by a manual action of the actual user of
common software? I guess, this might be possible, e.g. by means of a
java script, or Fortify for Netscape. The proliferation of this kind
of beyond-the-bound software cannot be monitored by the governments,
but it can be found in the computer of the accused. Hence - no good
for law-abiding people.
The only chance I can see is the combination of several encryption
techniques *by hand*, i.e. encrypting the plain text with one method
and sending the intermediate text by a different 56-bit program. If
cryptanalysis of a specific combination shows that one really has a
2^56x2^56 bit key space, then everybody, even the governments, should
grasp that the crypto law is nonsense.
Ciao, Gunter
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: Wed, 6 Jan 1999 13:37:02 -0000
Darren New wrote in message <[EMAIL PROTECTED]>...
>Just out of curiousity, what is the theoretical cutting edge nowadays?
>We already have
>
>provably-secure cryptography (OTP),
>public key cryptography based on known-hard math,
Interesting point. Are there really any PK systems that are provably as
hard as the underlying "hard" problem (e.g. integer factorisation or
discrete log problem) *and* that are practical to use?
Both RSA and Diffie-Hellman / ElGamal could (at least in theory) be broken
without breaking the underlying "hard math":
RSA is not proven to be equivalent to IFP - and indeed a proof may not be
possible [BV98].
Some ground is being made proving that instances of DHP / ElGamal are
equivalent to the underlying DLP [MW96].
All other PK systems based around IFP or DLP have serious shortcomings (e.g.
Rabin etc).
Would be nice to see a general proof that DHP is as hard as the DLP.....
Sam Simpson
Comms Analyst
-- http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption & Delphi
Crypto Components. PGP Keys available at the same site.
[BV98] D.Boneh, R.Venkatesan, �Breaking RSA may not be equivalent to
factoring�, Eurocrypt '98, Lecture Notes in Computer Science, Vol. 1233,
Springer-Verlag, 1998.
[MW96] U.M.Maurer, S.Wolf, �On the Complexity of Breaking the Diffie-Hellman
Protocol�, Institute of Theoretical Computer Science, Switzerland, Apr 1996.
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: Help: a logical difficulty
Date: 6 Jan 1999 13:18:14 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
>Mok-Kong Shen wrote:
>> Since there does not exist an algorithm to deliver the shortest
>> string to describe an arbitrarily given random number sequence,
>> couldn't one say that the problem of determining the shortest
>> description of a sequence is undecidable?
>
>No, because one can simply generate all possible descriptions in
>increasing order of size until one is found that generates the
>sequence. (This is obviously not a very efficient algorithm.)
>It is clear that a suitably defined interpretation architecture
>can guarantee that such a description won't exceed 2*N+2 bits,
>where N is the length of the sequence, so the search will terminate
>within 2^(2*N+2) iterations (of a finite process).
How do you decide whether a given description produces a given output?
Hint: For most useful description languages, the halting problem is
buried in there.
John Briggs [EMAIL PROTECTED]
------------------------------
Date: Wed, 06 Jan 1999 16:05:33 +0000
From: David Crick <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To:
alt.security.pgp,comp.security.misc,talk.politics.crypto,comp.security.pgp.discuss
Subject: Re: symmetric vs various asymmetric [was: DH is "stronger" than RSA?]
Sam Simpson wrote:
>
> Hi David,
>
> Symmetric key sizes shouldn't really be compared in this way
> (at least not for PGP...). Breaking one symmetric key just allows
> an adversary to read a single message - breaking an asymmetric key
> allows the users to read all messages past, current and future
> (and in the RSA allows the adversary to forge sigs).
I know, hence all my disclaimers, caveats, etc.
> Bruce Schneier wrote (to sci.crypt):
>
[snip]
I know he did. I also put a comment regarding this at the beginning
of the post.
> Anyway, this question has also been answered in the FAQ (which is now
> complete but being proof read).
Could I have a copy of it please? This was precisely the point of
my post, so that we could answer this v.faq in the FAQ.
David.
--
+---------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] http://members.tripod.com/~vidcad/ |
| Damon Hill WC '96 Tribute: http://www.geocities.com/MotorCity/4236/ |
| Brundle Quotes Page: http://members.tripod.com/~vidcad/martin_b.htm |
| PGP Public Key: (RSA) 0x22D5C7A9 00252D3E4FDECAB3 F9842264F64303EC |
+---------------------------------------------------------------------+
------------------------------
From: Jerry Leichter <[EMAIL PROTECTED]>
Subject: Re: One-time pads not secure ? (NSA's Venona project)
Date: Wed, 06 Jan 1999 10:23:21 -0500
| I once read in Bruce Schneier's "Applied Cryptography" that one-time
| pads were un-breakable but I saw an article on CNN's web site
| about NSA's VENONA project that seems to contradict this:
|
http://www.cnn.com/SPECIALS/cold.war/experience/spies/spy.gadgets/espionage/one-time.pad.html
|
| So did the russians used pseudo-random number generators to print
| those pads or what? If those pads were breakable does it mean their
| characters sequence was not truly random or generated using a
| reproducible process?
According to various published reports (particularly Spycatcher), the
Russians apparently used human typists with some kind of protocol that
generated excellent random pads. However, the volume of pads required
eventually led to shortcuts. Two attacks resulted:
1. To cut down on the required number of pads, the Russians
started re-using them, sending the same pad to two or
even three different "channels" (military, intelligence,
diplomatic). The Venona attack relied on collecting
huge amounts of ciphertext and searching for such
re-use. The effectiveness of this should serve as a
warning about (a) the amount of effort an intelligence
service is willing and able to apply when the potential
value is high enough; (b) the power of the resulting
brute force.
2. The human typists weren't really capable of producing
truely random numbers, at least not when the demands
got high enough. The result was that the pads had
various internal correlations - e.g., some pairs of
consecutive digits might be easier to type than
others, hence more likely. While I've seen reports
of such correlations, I don't recall seeing any
reports about breaks that resulted from them (which of
course says absolutely nothing about whether such
breaks *did* occur.) It's a good guess that such
correlations helped in the massive effort of the
Venona project, though I haven't seen any indication
of this.
-- Jerry
------------------------------
** 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
******************************
