Cryptography-Digest Digest #689, Volume #9 Thu, 10 Jun 99 16:13:02 EDT
Contents:
FREE Science and Nature Resource! ("Magnolia Scientific Services, Inc.")
Re: Cracking DES (Alan Braggins)
Does scott19u.zip make full use of it's large key size ? (Tim Redburn)
Re: Algorithms ("John E. Kuslich")
Re: huffman code length ("Mr. X")
RSA patent question ("R. Joosten")
Re: question about original RSA research (Pete)
Re: ATTN: Bruce Schneier - Street Performer Protocol (Bob Silverman)
perl and single substitution cipher (Pete)
Re: Does scott19u.zip make full use of it's large key size ? (Tim Redburn)
Re: Does scott19u.zip make full use of it's large key size ? (Tim Redburn)
----------------------------------------------------------------------------
From: "Magnolia Scientific Services, Inc." <[EMAIL PROTECTED]>
Subject: FREE Science and Nature Resource!
Date: Thu, 10 Jun 1999 10:54:10 -0500
--
When searching for technical information on the
Internet are you tired of the huge number of
irrelevant matches returned by the major search
engines and Web directories?
SciSeek (http://www.sciseek.com) offers a new
solution for those of you who are only interested
in high quality and useful information. This can
not be achieved using traditional online resources
because of the number of websites that they try
to index.
Due to our limited scope, focusing on only science
and nature, SciSeek offers you the opportunity to
easily locate the information that you need. Our
staff of reviewers visit each and every Website
submitted to SciSeek to make sure that it fits
within our guidelines.
SciSeek also offers webmasters the opportunity
to maximize the effectiveness of their listing. We
all know that the sites listed at the top of search
results receive over 80% of all click throughs.
Well, through our Enhanced and Premium listings,
we can guarantee that your website�s link will
appear at the top of the page. This feature alone
will help you to maximize your website�s true
traffic potential!
And remember this valuable resource is FREE
and available Online. Just drop by
http://www.sciseek.com/.
====================================================
Magnolia Scientific Services, Inc.
E-mail: [EMAIL PROTECTED]
URL: http://www.sciseek.com
Telephone Number: (601) 794-2309
Fax Number: (601) 794-2547
* Reach MSSI by ICQ. Our ICQ# is 31009553 or,
* Page MSSI online through our Personal Communication
Center: http://wwp.mirabilis.com/31009553 (go there
and try it!) or,
* Send MSSI E-mail Express directly to our computer
screen [EMAIL PROTECTED]
====================================================
------------------------------
From: Alan Braggins <[EMAIL PROTECTED]>
Subject: Re: Cracking DES
Date: 10 Jun 1999 17:52:34 +0100
Greg Bartels <[EMAIL PROTECTED]> writes:
> machine it represents, the game changes forever. It is not a question
> of whether DES keys can be extracted by exhaustive search; it is a
> question of how cheaply they can be extracted and for what purposes."
[...]
> 3DES may be more secure, but it seems to me that the old claims
> of 1DES would take more time to crack than the universe is old
> and then the reality of a million bucks and a couple hours,
> makes me question any claims about 3DES, which just uses
> the exact same algorithm, and just runs it three times.
But we know exactly how much extra protection that gives against
exhaustive search. Exhaustive search for a key two or three times
as long is not two or three times harder, its 2^56 or 2^112 times
harder. If you think there is a much better attack on triple DES,
then the search result on single DES is irrelevent. If you don't,
this shows DES is too short and triple DES isn't.
(And did anyone ever really claim DES took universe lifetimes to
crack? Dorothy Denning's 1993 review of SKIPJACK
(http://catless.ncl.ac.uk/Risks/14.80.html#subj2) says
"Another way of looking at the problem is by comparing a brute force
attack on SKIPJACK with one on DES, which uses 56-bit keys. Given
that no one has demonstrated a capability for breaking DES, DES offers
a reasonable benchmark. [...] Given the lack of demonstrated
capability for breaking DES, and the expectation that the situation
will continue for at least several more years"
If you want to claim she was wrong you can quibble about how many
years "several more" is, and how many years ahead of the EFF the NSA
could have built a DES cracker if they wanted to, but this isn't a
claim that DES would take human lifetimes to break, let alone the
lifetime of the universe.
> is there no serious contender for a block algorithm that
> would provide security against the next century or so of cracking
> advances?
There are several.
> is there nothing being worked on to replace DES?
See http://csrc.nist.gov/encryption/aes/aes_home.htm, though it
depends on exactly what you mean by "replace DES".
------------------------------
From: [EMAIL PROTECTED] (Tim Redburn)
Subject: Does scott19u.zip make full use of it's large key size ?
Date: Wed, 09 Jun 1999 22:39:50 GMT
>From what I can make out about scott19u.zip (which
granted is not very much), it appears that
one of it's main security features is the
use of an incredibly large S-Box for subtitutions.
>From posts to this news group and the
pages by Horst Ossifrage, I think the
following facts are true about scott19u.zip
(I think they are also true of his earlier ciphers
but I'm only really considering scott19u.zip
because this is the cipher David claims to be the
strongest):
1. The S-Box is guranteed not to have duplicate
entries. This means (when considering only
the substitution phase) that if two 19bit words
of the cipher text are of equal value, then
the corresponding plain text words will both be
of equal value.
2. The algorithm has very few passes.
3. The S-Box is incredibly large. It contains all possible
19bit words.
4. The key for the algorithm is only used for generating
the S-Box. It is not used anywhere else in the
algorithm.
(I hope David will correct any parts of this post that
he considers incorrect - which because of the
difficult nature of finding out about his algorithm,
I'm sure there'll be some)
Most people who would use encryption don't
want or need to encrypt large files.
For scott19u.zip to fully utilise the S-Box (note :
this is less than fully utilizing the key, but that
has been covered before), all entries
in the S-Box must be used by the algorithm.
Any not used, will not be needed to decipher
the message.
However, due to the small number of passes the
algorithm makes, I think that it is very unlikely
that even for files of half the size of the s-box,
all the entries will be used.
For small files of a few K, only a very small proportion
of the S-box will be used.
Ah ! but doesn't it
mean, because the plaintext is shorter than the key
that decryption cannot be possible? You just wouldn't
know which plaintext was correct if you found it?
Well, maybe, but the fact that two identical words
of cipher text can *only* be generated by two
identical words of plaintext at each pass, combined by very few
passes, must give a lot of information away.
Has anybody else looked at this in detail, and who therefore
could determine more accurately if this is a weakness ?
-Tim.
------------------------------
From: "John E. Kuslich" <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Algorithms
Date: Wed, 09 Jun 1999 15:43:15 -0700
> <Snip something...>
Ok, What the heck does AL Gore have to do with crypto???
Let's keep this group free from annoying posts about politics. Who the
heck cares about Al Gore isms any way
Tho thick to the thubject and enough about Al Gore Ithms...
Thuffering Thuckathsth...
:-)
De devil made me do it!
--
CRAK Software (Password Recovery Software)
Http://www.crak.com
[EMAIL PROTECTED]
602 863 9274 or 1 800 505 2725 In the USA
------------------------------
From: "Mr. X" <[EMAIL PROTECTED]>
Crossposted-To: comp.compression,alt.comp.compression,sci.math
Subject: Re: huffman code length
Date: Thu, 10 Jun 1999 11:41:54 -0700
Mok-Kong Shen wrote:
> Recently I posed a question elsewhere concerning Huffman encoding.
> Since I don't yet have any appropriate answer, I like to take this
> opportunity to repost it here:
I actually saw and responded to your earlier post, but since
comp.compression.research is moderated, my post was never actually
posted. This may be because of my anti-spam return addy or whatever,
anyway, I tacked on my original reply onto this thread.
> Question: Given an arbitrary Huffman tree, how can we say something
> useful in quantitative terms concerning the possilbe frequency
> distributions that correspond to it?
From: "Mr. X" <[EMAIL PROTECTED]> 5/26/99 3:21 PM
Subject: Frequency distribution of Huffman encoding tree
Newsgroups: comp.compression.research
Mok-Kong Shen wrote:
>[EMAIL PROTECTED] wrote:
>>Given that Huffman has assigned a length of Hi bits to some symbol i,
>>we can say that symbol definitely had a frequency in the range of
>>
>> 2^(-Hi) <= fi <= 2^(1-Hi)
>> where
>> fi = ni/L
>>
>>For example, if Huffman assigns a length of 1 bit to some symbol 73,
>>that symbol definitely occurs with some frequency in the range
>> 2^(-1) = 1/2 <= f73 <= 2^(1-1) = 1.
>>
>> (This seems wrong for the special case of 2 symbols ...)
>
>My example given for a balanced tree of 4 symbols appears to
>contradict your formula. (Your range is [0.25, 0.5]).
That's because the formula isn't correct. :)
While you may want to believe:
2^(-BitLength-1) <= Freq <= 2^(-BitLength+1)
And this works for even distrabutions sets of [1], [.5], [.33] and [.25]
- unfortunately, it's not that simple as [.1,.9] violates it.
What Huffman gaurentees is that shorter codes are from equal or higher
frequency symbols, but not what those frequencies actually are. You
might have a file with 2^64-1 symbols A and just 1 symbol B. Huffman
will map these both to codes length 1, which is 'supposed' to mean freq
..5 but wait, there's more - a file with ABC will have 3 symbols with the
exact same frequency mapped to 2 different code lengths, neither of
which are actually correspond to the orginal freq. This is why you can't
work backwards to get an absolute freq range. You can get relative freq
ranges, and you know they total 1, but that's it without information
from the actual encoded data.
Some possible symbol sets for code set [0,1]
[.1,.9] [.5,.5] [.9,.1]
Some possible symbol sets for code set [0,10,11]
[.33,.33,.33] [.34,.33,.32] [.8,.1,.1]
X
------------------------------
From: "R. Joosten" <[EMAIL PROTECTED]>
Subject: RSA patent question
Date: Thu, 10 Jun 1999 20:32:01 +0200
Over lunch someone mentioned the following case.
Suppose you are in Europe, and you want to access a US-based database over
the internet. The database owner supplies you with an RSA key, and sends you
database items that are RSA encrypted, and which you could then decrypt
using the aforementioned key. You can then apparently be sued for patent
(yes, patent) infringement. It was said that a case like this was brought to
court only very recently.
This seems weird to me; I would say that there is not necessarily any proof
that RSA is actually executed, but only that an RSA key is sent and RSA
encrypted stuff.
Anybody know details?
------------------------------
From: [EMAIL PROTECTED] (Pete)
Subject: Re: question about original RSA research
Date: 10 Jun 1999 18:42:15 GMT
what i would do in your shoes is to go to my university library and search
all the journals for articles by len rivest, shamir and adleman (don't know
if those spellings are correct).
pete
[EMAIL PROTECTED] wrote:
: I'm a student of computer science and I'm doing a research about
: RSA. If anybody knows were can i find some info about the original!!
: research done to invent RSA, or info about the first product related
: with RSA , or any info about the original research please send me email
: Thanks in Advance
: [EMAIL PROTECTED]
: Sent via Deja.com http://www.deja.com/
: Share what you know. Learn what you don't.
--
NEWS FLASH: Just compiled a new kernel 2.3.0! YEAH!!!
================================================================
http://landau.ucdavis.edu/psalzman [EMAIL PROTECTED]
One world, one web, one program. -- Microsoft Ad Campaign
Ein Volk, ein Reich, ein Fuhrer. -- Nazi Ad Campaign
<=>+/\/-=Prevent world domination, Install Linux today!=-\/\+<=>
================================================================
The best way to accelerate a win95 system is at 9.81 m/s^2
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: ATTN: Bruce Schneier - Street Performer Protocol
Date: Thu, 10 Jun 1999 17:38:47 GMT
In article <[EMAIL PROTECTED]>,
Anonymous <[EMAIL PROTECTED]> wrote:
> Bruce,
> I cannot believe you would put your name to such an outlandish
proposal! If you wanted to
> float a trial balloon you could have done so under a pseudonym. The
proposal on the website
> I just saw is INCREDIBLY NAIVE on your part
<remainder of tirade deleted...>
Might I ask:
What is it that compels people who are ignorant about this subject
area to keep making personal attacks on Mr. Schneier (and others)?
What is that compels people who are *totally* ignorant about the
way the NSA works to continue to post random speculation and slurs
about the agency?
What is it that compels people who are ignorant of cryptography to
continue to post 'I have this terrific new cipher'?
There was a statistical theory which says that if one could get
enough monkeys banging away randomly on typewriters that they would
produce the works of Shakespeare.... I claim that the Internet is
a counter-example to that theory....
--
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] (Pete)
Subject: perl and single substitution cipher
Date: 10 Jun 1999 18:55:09 GMT
dear all,
i'm writing a perl script that helps decrypt single substitution ciphers (i
don't use brute force because the fun is in the solving. it simply
'helps'.
it was more of an excersize in perl than anything else, since i'm in the
process of learning perl right now.
if anyone knows perl and/or has an interest in looking at my perl script,
i'd appreciate the feedback.
thanks!
pete
--
NEWS FLASH: Just compiled a new kernel 2.3.0! YEAH!!!
================================================================
http://landau.ucdavis.edu/psalzman [EMAIL PROTECTED]
One world, one web, one program. -- Microsoft Ad Campaign
Ein Volk, ein Reich, ein Fuhrer. -- Nazi Ad Campaign
<=>+/\/-=Prevent world domination, Install Linux today!=-\/\+<=>
================================================================
The best way to accelerate a win95 system is at 9.81 m/s^2
------------------------------
From: [EMAIL PROTECTED] (Tim Redburn)
Subject: Re: Does scott19u.zip make full use of it's large key size ?
Date: Thu, 10 Jun 1999 19:39:16 GMT
On Thu, 10 Jun 1999 03:45:19 -1000, Horst Ossifrage <[EMAIL PROTECTED]>
wrote:
<snip>
>Yes, memory is cheap. Your computer can easily handle it.
>
That wasn't my reason for mentioning it. The reason I mentioned
it was because it means that it is very unlikely that all entries will
be used for a typical encryption. Hence much of the key
will be wasted.
<snip>
>
>Only in one pass, after all 25 passes, the bricklaying of
>words makes data dependent changes on adjacent words.
>This avalanches with each pass so 25 adjacent words of
>19 bits each influence each other.
>
>
That doesn't make it secure though. I'm sure that substitition
ciphers can be broken even after they have had a chaining
mode applied on top of them.
<snip>
>>
>> For scott19u.zip to fully utilise the S-Box (note :
>> this is less than fully utilizing the key, but that
>> has been covered before), all entries
>> in the S-Box must be used by the algorithm.
>> Any not used, will not be needed to decipher
>> the message.
>
>Other ciphers may have some their s box entries not used.
>It is just less likely than for Scott's.
>
Yes, but most other ciphers use the key in other ways as well,
even if it is just xoring it somewhere along the line. But
I suppose that's not really practical for such a large key.
<snip>
>If you consider only one pass for all algorithms, you can
>find some with that property and some that have more extensive
>round functions. The simpler round functions may be susceptible to
>a Slide Attack, while less comprehensible roundss are not
>susceptible to that attack. That attack can be blunted by
>making each round different. But the large block size of Scott's
>makes the probability of finding a collision between a plaintext
>and a one round cipher too low for usefulness.
>
Assumptions like that allowed the enigma to be broken.
- Tim.
------------------------------
From: [EMAIL PROTECTED] (Tim Redburn)
Subject: Re: Does scott19u.zip make full use of it's large key size ?
Date: Thu, 10 Jun 1999 19:39:15 GMT
On Thu, 10 Jun 1999 02:19:16 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote:
<snip>
> Well by defination the S-box is reverseable so
>how could 2 entries go to the same values. I am
>not sure what you are trying to drive at here. In
>some coding methods where noise added the S-boxes
>might be non reversable but to use the S-box as a
>general encryption device it has to be reversible.
>
Not true. I have just consulted AC2 and the S-Boxes
for DES contain repeated entries. It is the feistel
nature of DES and other similar ciphers that
enables the S-Box, or other functions for that
matter, to be one way. In the case of DES, the
S-Box also does compression (not to a useful
extend though because expansions are done elswhere).
>>
>>2. The algorithm has very few passes.
>
> it has more passes than IDEA but if you
>consider any number less than 100 as small
>for passes then it is small. I felt like I did more
>than necessary.
>
Far point. I misunderstood the specs, but I believe with
25 rounds my point still holds.
Now I know how many rounds that scott19u.zip has,
I will make an attempt at estimating the *maximum* key utilisation
of scott19u.zip when encrypting a 30K file.
30K = 30 * 1024bits = 30720bits of data to be encrypted.
That is 30720 / 19 words = 1617 words (one word is 19bits)
Multiply that by 25 rounds :
1617 * 25 = 40425 substitutions.
This means that there is an *absolute* *maximum* key
entropy utilisation of
40425 * 17.558 = 708407 bits
when encrypting a 30K file. This is far less
than the 1million+ bytes encryption that David shouts about so often.
That is 9205076 - 708407 = 8496669 bits less security than David would
have people believe. (more than 1million bytes less).
This value is based on the assumption that no S-Box entry will
be used twice at all throughout the algorithm. In reality this is
highly unlikely, and the actual utilisation will be even less.
(The value of 17.558 was reached by taking the maximum
entropy of the S-Box if it has been generated by Davids
additional key manipulation program, and dividing it
by 2^19 (ie the number of 19bit entries). This gives the
average entropy of 17.558bits per 19bit s-box entry.It also assumes
that the entropy is evenly distributed throughout the S-Box.)
<snip>
> I am not sure but I would suspect that for files
>approaching even 25% of the size would use all
>the S-table entries.
>
That's still a large file that you would need to encrypt
to be in with a good chance of fully using that
key that you spent so much effort generating.
>>
>>For small files of a few K, only a very small proportion
>>of the S-box will be used.
>
> This is very likely
>
You don't seem concerned. Not using all the
S-Box entries means that only a fraction of the
key is being used. The effective key size used
will not be what the user thinks. So much
for million bit encryption. It's only that large
when encrypting very large files.
<snip>
>
> No I think your missing something here if you take to
>19bit portions of the file before a pass and if they happen
>to be the same before the pass they will most likely be
>diffferent after that pass. And when they go into the next
>passes s-box they will be even less related.
>
I don't dispute that (I haven't looked at your chaining mode yet).
Most block ciphers are usually broken by first considering
simgle rounds. My point is, that because of properties
of the S-Box, a lot of information is available to help
a cryptanalyst. If you ignore the chaining mode altogether,
then because of the known properties of your S-Box,
breaking a single round of scott19u.zip will
be trivial with the use of frequency table (obviously they need
to be modified for 19bits but that's not a hard task).
<snip>
- Tim.
------------------------------
** 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
******************************
