Cryptography-Digest Digest #255, Volume #9 Fri, 19 Mar 99 23:13:02 EST
Contents:
Re: One-Time-Pad program for Win85/98 or DOS (R. Knauer)
Re: Random Walk (R. Knauer)
Re: a little math please ([EMAIL PROTECTED])
Re: What is MAC ? -2nd ([EMAIL PROTECTED])
Re: Random Walk ("karl malbrain")
Re: CRYPTOGRAPICALLY USEFUL HUFFMAN COMPRESSION ("karl malbrain")
Re: pRNG that is "predictable to the left"? (Scott Fluhrer)
Re: a little math please (Scott Fluhrer)
Re: PGP Protocol question (Robert Munyer)
Re: Tuxedo and Bowtie (wtshaw)
Re: Testing Algorithm (hash) (dan)
Re: SCOTT ADAPTIVE COMPRESSION SUITABLE FOR ENCRYPTION ([EMAIL PROTECTED])
Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED ("Douglas A. Gwyn")
Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED ("Douglas A. Gwyn")
Re: a little math please ("Trevor Jackson, III")
Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Crossposted-To: alt.security,alt.privacy
Subject: Re: One-Time-Pad program for Win85/98 or DOS
Date: Fri, 19 Mar 1999 22:13:01 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 19 Mar 1999 21:33:13 GMT, [EMAIL PROTECTED] (Jim
Dunnett) wrote:
>>Anyway guessing does not count for the OTP system. Do you know why?
>No.
Then you should learn why.
HINT: Why is the OTP system proveable secure?
>But with OTP systems, the bytes only need to be sufficiently
>random, not 100% random.
Define "sufficiently random" in a non-circular manner.
HINT: It depends on how many messages of what length you plan to send.
Bob Knauer
"Every government always exercises the maximum amount of power its
rulers feel the people will stand for without revolting."
-- Alongside Night
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Fri, 19 Mar 1999 22:19:02 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 19 Mar 1999 21:34:29 GMT, [EMAIL PROTECTED] wrote:
>Pretty deep stuff man. Too bad I don't understand half of it. Seems like
>something I should look into later (say when I finish high school..)
At least you are being honest. That means you will not get snooked on
snake oil statistical testing.
Bob Knauer
"Every government always exercises the maximum amount of power its
rulers feel the people will stand for without revolting."
-- Alongside Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: a little math please
Date: Fri, 19 Mar 1999 21:30:50 GMT
> If I understand your question correctly it has to be 2^255.
>
> To see this, remove one square, fill the remaining 255 squares as you
> wish. No there are even 0 bits and odd 1 bits _or_ odd 0 bits and even
> 1 bits. Fill the last square so that your restriction is satisfied.
2^255 makes sense. I would think it's from 2^128 * 2^127.
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: What is MAC ? -2nd
Date: Fri, 19 Mar 1999 23:11:42 GMT
<[EMAIL PROTECTED]> wrote:
> ZinHa wrote:
> > Of course, I didn't know about Message Auth. Code.
> > I think it is not that I have to get.
> > I read the MAC in smart card site.
> > It is for higt speed modulation(?) and operation.
[...]
> In DSP circles a mac == multiply-accumulate in single cycle.
> So you can perform the operation y = a*x + b in one step.
Yup, MAC is an acronym collision, and both "message
authentication code" and "multiply-accumulate" are
important to cryptographers.
The most useful form of the MAC (multiply-accumulate)
operation for large unsigned integer arithmetic actually
has a fourth input - a one-word carry. It looks
something like:
(carry, y) = a*x + b + carry
If each parameter is an unsigned word of W bits, then
a*x+b+carry can take all and only the values that fit in
2W bits, or two words. The most significant word becomes
the carry for the next MAC.
Suppose we have a MAC operation that takes three
arguments, as in MAC(a, x, b), and returns the low word
of a*x+b+carry and places the high word back into carry.
Now suppose we need to multiply an m-word value u[0..m-1],
and an n-word value v[0..n-1] to form an m+n word product
w[0..m+n-1]. Assume the least significant word is at the
zero index. Using the MAC operation, the procedure for
classic O(n^2) multiplication is remarkably simple:
for i in 0..n+m-1
w[i] = 0
for i in 0..m-1
carry = 0
for j in 0..n-1
w[i+j] = MAC(u[i], v[j], w[i+j])
w[i+n] = carry
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Fri, 19 Mar 1999 15:30:38 -0800
R. Knauer wrote in message <[EMAIL PROTECTED]>...
>For all of those who worship at the altar of statistical testing (...) you
>must get the 3rd edition if you request it from the library.
( . . . <<even bigger snip>> . . . )
>"Every government always exercises the maximum amount of power its
>rulers feel the people will stand for without revolting."
The CONSEQUENT to your opening sentence <<For all>> is another PREPOSITION
<<if you request, you must get>> which does not follow as a matter of
COURSE.
As to your quote <<du jour>>, you need look no farther for a COUNTER example
than the SOCIAL DEMOCRATS who were expected to win (in Germany and Hungary)
after the 1918 cease-fire. Their <<constitution/makeup>> sought out the
opposite with miserable results. Karl M
------------------------------
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: CRYPTOGRAPICALLY USEFUL HUFFMAN COMPRESSION
Date: Fri, 19 Mar 1999 15:44:25 -0800
[EMAIL PROTECTED] wrote in message <7cjspf$h90$[EMAIL PROTECTED]>...
>
>
> At my website (...) I take an
>existing adaptive huffman compression program and mod it to
>make it useful with ENCRYPTION
David, you must be CAREFUL with your usage of MATHEMATICAL terms in our OPEN
newsgroup. <<Mod>> is a REMAINDER function -- the fractional portion that
is LEFT-OVER under the similar DIVISION operator. Karl M
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: pRNG that is "predictable to the left"?
Date: Sat, 20 Mar 1999 00:09:15 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] ("Steve Myers") wrote:
>
>It is an easy theorem to prove that a generator is unpredictable to the left
>iff the generator is unpredictable to the right iff the generator is
>pseudo-random. Therefore, you have a generator which is predictable in both
>directions, you're just no aware of the predictibility in one direction. As
>a direct corollary your construction must fail, and so must all further
>attempts.
Either you are using an odd definition of unpredictable, or this statement is
false (or, there are no one-way functions).
As a counterexample, consider the generator:
X(n+1) = SHA( X(n) )
where "SHA" is a one-way function (not necessarily the Secure Hash Algorithm).
Now, this generator is predictable to the right (one way functions are easy
to perform, by definition), but unpredictable to the left (one way functions
are hard to invert, by definition).
Note: this generator is not an answer to the original poster's question, unless
he can compute the whole series in advance, and then reverse it.
BTW: what's the proof of the easy theorem? Also, what definition of
"pseudo-random" are you using in your statement?
--
poncho
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: a little math please
Date: Sat, 20 Mar 1999 00:18:55 GMT
In article <7cu326$ami$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>What I would like to know, given a grid of 16x16, filled with an even number
>of 0 and 1 bits, how many combinations are there?
>
>Not 2^256, because remember that they have to be even.
Other posters gave you the correct number assuming that by "even", you mean
that the number of 0's (and the number of 1's) must be an even number.
However, if you mean the numbers of 0s must be the same as the number of 1s
(that is, there are precisely 128 0's and 128 1's), then there are:
256!
-----------
128! * 128!
combinations, which is approximately:
2^251.672843
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Robert Munyer)
Subject: Re: PGP Protocol question
Date: 19 Mar 1999 18:36:28 -0600
Jeffrey, your understanding of PGP is correct. If you encrypt a
message to 4 recipients, you'll end up sending 4 identical messages:
ABCDM, ABCDM, ABCDM, ABCDM
where A through D are encryptions of the session key, and M is the
message content encrypted by that session key.
In article <7cpsj4$hf5$[EMAIL PROTECTED]>,
Jeffrey Haas <[EMAIL PROTECTED]> wrote:
> Does distributing a given encrypted message with a common session
> key to multiple recipients, each with their own public key, via
> separate messages rather than a single large message weaken the
> security?
It sounds like you want to send these four messages instead:
AM, BM, CM, DM
where A through D and M are the same as in the example above.
Notice that if an enemy intercepts ANY ONE of the messages sent by
the "normal" mode, he could easily regenerate ALL of the messages
sent by your "optimized" mode, by simply removing data. Therefore
your strategy is at least as strong as the normal one.
> What order of complexity are the IDEA and RSA ecryption computations?
> Is it worth attempting to save the computer cycles by using a
> common session key?
That depends on the key length and message length. If your messages
are very large, it would be worth while to avoid using the symmetric
cipher more than once. You could find out by getting the PGP source
and adding a few lines of timing code, so you could check the actual
time spent in symmetric vs. asymmetric encryption, on whatever you
consider to be a "typical" message and key for your mailing list.
> I want to hack majordomo or some other mailing list to handle
> encrypted mailing lists. I'm trying to see if its worth doing
> some tricks to lower the load on the machine.
Here's a trick that could help reduce the load. Suppose users B
and C have the same ISP; in that case you could send the messages
AM, BCM, BCM, DM
with the middle two messages being delivered in a single SMTP
transaction. This way you minimize both processing and bandwidth
(for the server) at the expense of message expansion for some of
the subscribers.
If you're desperately short on processing power, you could consider
a system with a single symmetric key that's shared by everyone.
The cryptographic load on the server would be virtually zero. All
the cryptography would be done by the subscribers' machines, except
for the distribution of the key, which would only happen when a
new subscriber joins or the key is changed. Of course this is no
longer quite as strong as PGP, but that might be OK depending on
your trust-and-threat model.
Good luck!
-- Robert Munyer <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Tuxedo and Bowtie
Date: Fri, 19 Mar 1999 16:55:36 -0600
Oops.
>
> Actually, we have one already, Granville 14/28/42/64, with plaintext in
> 100, and ciphertext in 64.
That should have been Wharton 18/36/54. Granville has output in base 57.
>
--
It's a game within a game within a game.--Gen. Odom
------------------------------
From: dan <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithm (hash)
Date: Sat, 20 Mar 1999 02:41:14 GMT
In article <7cquec$hsb$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> What other tests can I perform on my algorithm?
Bob Jenkins has some nice tests. Although they're not specifically for
secure hash algorithms, they test things that all hash algorithms need.
Also, to make sure your output is sufficiently random, DIEHARD is the
sci.crypt standard.
http://ourworld.compuserve.com/homepages/bob_jenkins/blockcip.htm
http://stat.fsu.edu/~geo/
By the way, if you want to do some reading, search for "hash" here:
http://www.cryptosoft.com/html/secpub.htm.
And if you want to read others' code on hashing, download Wei Dai's Crypto++.
http://www.eskimo.com/~weidai/cryptlib.html
I'm not sure where you're going with TH1, presumably it's just for your own
edification. FWIW, here are some comments after examining the algorithm a
bit:
It looks rather slow - 24 rounds per byte, each with 6 data dependent rotates,
which are among the slowest operations on WORD's. By comparison, the SHA
processes 1.25 rounds per byte, each with only two rotates of a fixed
distance. So one improvement might be to introduce the data a WORD at a time
instead of byte by byte. That's what SHA does, and it would probably improve
other characteristics of the hash function as well. What kind of performance
are you getting? For comparison, my naive implementation of SHA did about .25
MB / sec on a 486/33, according to my notes in the source code.
You could probably improve the "mixing" by relying more on (nonlinear?)
boolean functions and relying less on rotates. Then you could reduce the
number of rounds to something more reasonable. This is the traditional
approach to hash functions, MDx related ones anyhow. (Unfortunately, the
choice of boolean functions is not trivial, cf the paper on HAVAL, and others
by Zheng, Zhang, and Seberry at the cryptosoft site above. And you need to
choose your functions to defend against both linear and differential types of
attacks, which they don't address.)
Hope this helps!
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: SCOTT ADAPTIVE COMPRESSION SUITABLE FOR ENCRYPTION
Date: Sat, 20 Mar 1999 02:45:34 GMT
In article <7cnnk7$sro$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I made some random test cases and added a new case to remove
> a bug on the old version. My main criteria is that any file
> can be uncompressed by my code and then when recompressed
> you get same file back. This is needed for encryption so that
> the enemy can't tell immediately that the file is of a form
> that would not have resulted from a compression.
> The way I choose to do it was look at the compressed file
> and start decompressing. The problem occurs on last byte
> where the boundaries don't line up. Basically I used the
> all 00's as a stop symbol.
You mark the end of a compressed file with all zeros. This may
give information to your enamigos. It seems better to use no
end of file marker.
Your product seems useful: it will be usable with any crypto
algorithm. Compress a plaintext with ScottCompress and it has
no header and no trailer and no end of file. Then encrypt it.
Then the enamigos will not see any headers, etc. to see that
they succeeded with a cryptanalysis.
How much can I buy a copy for? I offer $12.
poiubnm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED
Date: Sat, 20 Mar 1999 03:49:08 GMT
John Savard wrote:
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
> >... If I were king, nobody would be allowed to work on creating
> >crypto systems until after he has cracked several really tough ones.
> But that might leave us bereft of possible solutions -
What sort of "solutions" would they be if the designers didn't know
how they could be successfully attacked?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED
Date: Sat, 20 Mar 1999 03:52:20 GMT
wtshaw wrote:
> In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
> <[EMAIL PROTECTED]> wrote:
> > If I were king, nobody would be allowed to work on creating crypto
> > systems until after he has cracked several really tough ones.
> You present too high a barrier. It is best to promote thought in all
> areas of crypto than to limit people to following in someone else's wake.
I didn't suggest that future cryptosystems necessarily ought to be
based on past ones. However, they certainly ought to avoid the
*weaknesses* of past ones. The only way I know to obtain a good
appreciation for the weaknesses is to discover them for yourself.
------------------------------
Date: Fri, 19 Mar 1999 22:57:26 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: a little math please
[EMAIL PROTECTED] wrote:
>
> What I would like to know, given a grid of 16x16, filled with an even number
> of 0 and 1 bits, how many combinations are there?
>
> Not 2^256, because remember that they have to be even.
>
This problem can be solved with elementary combinatorics. The layout of
the cells does not matter, only that there be some ordering; numbering
from 1..256 will work as well.
IF the 0/1 ratio is even there are 128 ones. Starting with all cells
empty (zero), pleace each of the 128 ones in any free cell. The first
placement gooes into one of 256 cells, the second into one of the
remaining 255, the third into one of 254. The last (128th) one goes
into one of the remaining 129 cells.
Thus the odds are 256 * 255 * 254 * ... * 129, which is 256! / 128!
That's your numerator.
The denominator accounts for the fact that the ones are
indistinguishable. IF the first one goes into the first cell, and the
second one the second cell you get the same result as if the first one
wentinto the second cell, and the second one went into the first cell.
The resulting patterns are identical.
Thus, for every distribution of ones there are many ways to reach that
pattern. For any given pattern there are 128! sequences by which that
pattern can be reached.
So the total number of sequences is 256!/128! and the total number of
distinct final patterns is sequences / 128!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED
Date: Sat, 20 Mar 1999 04:09:06 GMT
Jim Gillogly wrote:
> ... A lot of people have worked on the Zendian Problem,
> which includes a number of what I would consider pretty tough ones.
> So far as I can tell nobody has put up a web site that spoils these
> problems, so <lots> of people can crack them and gain the requisite
> experience.
I've considered setting up an "official" Zendian Problem web site,
but haven't figured out a good way to offer hints and solutions.
Perhaps each system could be hinted via encryption in a previously
cracked system, in some logical order of attack.
> If those aren't deemed tough enough, similar training
> sets could be created based on more modern crackable systems
> or their analogues...
The "more modern" systems generally known to the public (DES,
RSA, etc.) tend to not have publicly known methods of attack.
I suppose we could make examples of some known failures, such
as the knapsack system.
We could use the equivalent of a new volume of MilCryp, starting
where the others left off. (LDC's MC Pt. III covers pretty much
the same old systems.) But I don't think anyone is in a position
to publish such a document.
------------------------------
** 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
******************************
