Cryptography-Digest Digest #219, Volume #10 Sat, 11 Sep 99 00:13:04 EDT
Contents:
Re: Difference between Encryption and scrambling..? ("Joseph Ashwood")
Stream cipher from a hash function ([EMAIL PROTECTED])
Re: "NSA have no objections to AES finalists" (Arthur Dardia)
Re: Looking for Completely-Free Strong Algorithms (Lamont Granquist)
Re: Linear congruential generator (LCG) (William A Moyes)
Re: Counterpane and Mr. Schneier (Paul Rubin)
Re: Stream cipher from a hash function ("Steven Alexander")
Counterpane and Mr. Schneier ("Jae-Yong Kim.")
OTP again ("Ed Severn")
Re: simple key dependent encryption ("Douglas A. Gwyn")
Re: some information theory (Anti-Spam)
Re: Linear congruential generator (LCG) (David A Molnar)
Re: Stream cipher from a hash function ([EMAIL PROTECTED])
Re: OTP again ("Douglas A. Gwyn")
Re: some coder/hacker help please? (Tom St Denis)
Yet another chapter from the Handbook of Applied Cryptography (Alfred John Menezes)
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Difference between Encryption and scrambling..?
Date: Fri, 10 Sep 1999 16:28:02 -0700
I am unconviced by any of the other arguments, so let me pose my own. As
others have pointed out there may be an Analog vs Digital difference, but I
would like to point out that a weak crypto scheme that applies to analog
signals can be created by simply adding PI to the stream (very similar to
Ceasar Cipher), given this I don't see where we can state Analog vs Digital.
About the keyed/keyless argument. Nothing stops me from chosing from K
scrambling methods using a key, but I would not call this encryption because
K is generally so small and so trivial.
I instead would like to call Scrambling a super-set of encryption. As an
example I can scramble an egg, but I feel confident in saying that there is
no way (outside of going down to the cellular level) to unscramble them. I
could also take a file, encrypt the file, and reasonably call it scrambled
(evidence of the original is scattered in all locations so it's not a big
issue).
I also think that the best "definition" of cryptography was given by a
friend of mine: "Cryptography is the art of f^&*ing s!#t up so no one else
can unf^&* it"
It may be a bit vulgar but I think it's pretty accurate.
------------------------------
From: [EMAIL PROTECTED]
Subject: Stream cipher from a hash function
Date: Fri, 10 Sep 1999 19:18:10 -0400
Ok, lets assume that crypto is 100% export restricted, and only lies
within the US (heh, a BIG assumption). Hash functions, on the other
hand, are not export restricted. Is it possible to turn a hash function
into a stream cipher?
My idea falls along the lines of:
SHA-1(password) = 1st output of stream cipher
SHA-1(password + counter) = 2nd output of stream cipher
SHA-1(password + counter2) = 3rd output of stream cipher
...
I was curious, (1) what would you use to make the output non linear (IE,
how would you change the counter variable above), and (2) what would the
security of this cipher be? (This assuming the hash function is not
broken.)
Just curious.
------------------------------
From: Arthur Dardia <[EMAIL PROTECTED]>
Subject: Re: "NSA have no objections to AES finalists"
Date: Fri, 10 Sep 1999 19:32:38 -0400
Reply-To: [EMAIL PROTECTED]
Derek Bell wrote:
>
> pbboy <[EMAIL PROTECTED]> wrote:
> : Area 51 is closed. They moved to an undisclosed location.
>
> The reporter who wrote the article about that apparently took the wrong
> route to the base.
>
> Derek
> --
> Derek Bell [EMAIL PROTECTED] | Socrates would have loved
> WWW: http://www.maths.tcd.ie/~dbell/index.html| usenet.
> PGP: http://www.maths.tcd.ie/~dbell/key.asc | - [EMAIL PROTECTED]
Or is that just what they want you to think.../me ponders.
But then again, we're getting into the - "I made you say made you say made you
say <insert childish word here>..." paradox. I actually got involved with a
discussion on EFNet one day with an immature prick, so I just wrote a script to
just take whatever he said last, and add "made you say" before it. He didn't
stop private messaging me for about 15 minutes until he released he's just
wasting his time. It might be my funniest IRC moment. ;)
Art Dardia
------------------------------
From: [EMAIL PROTECTED] (Lamont Granquist)
Subject: Re: Looking for Completely-Free Strong Algorithms
Date: 11 Sep 1999 00:38:48 GMT
"Gary" <[EMAIL PROTECTED]> writes:
>Old TEA (Tiny Encryption Algorithm) and the new block version of it is worth
>looking at.
>Developed by R M Needham and D J Wheeler.
>http://vader.brad.ac.uk/tea/tea.shtml
How fast is TEA compared with other algorithms? Is the major advantage of
the algorithm just the simplicity and small size of the code?
--
Lamont Granquist ([EMAIL PROTECTED])
ICBM: 47 39'23"N 122 18'19"W
------------------------------
From: [EMAIL PROTECTED] (William A Moyes)
Subject: Re: Linear congruential generator (LCG)
Date: 11 Sep 1999 00:16:28 GMT
I used to 'synchronize' with the LCG used by on-line games to
cheat back when I was in high school. Due to processing limitations (at
the time I only had a 386) I had to use a guess of the system time to
narrow the search (most applications seed their PRNG from the system
time). Once when building a new 486 for someone else I tried an
exhaustive search. Does anyone have a faster method than brute force?
Every now and then I seek out the answer, but so far no one has one.
--
-William Moyes
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Counterpane and Mr. Schneier
Date: 11 Sep 1999 00:45:41 GMT
In article <kmhC3.34$[EMAIL PROTECTED]>,
Jae-Yong Kim. <[EMAIL PROTECTED]> wrote:
>They seems to earn money only by book selling.. as far as I assume..
>their algorithms and PRNGs are all free, unpatented..
>doesn't they..?
See their web page, www.counterpane.com. They have a very good
consulting business.
------------------------------
From: "Steven Alexander" <[EMAIL PROTECTED]>
Subject: Re: Stream cipher from a hash function
Date: Fri, 10 Sep 1999 17:21:27 -0700
> My idea falls along the lines of:
> SHA-1(password) = 1st output of stream cipher
> SHA-1(password + counter) = 2nd output of stream cipher
> SHA-1(password + counter2) = 3rd output of stream cipher
There is a few simple problems with this:
One, it's not safe to use the same password more than once because you are
XORing plaintext with the output of the stream cipher. XOR is not safe if
the key is ever repeated.
Two: Even if the same password is never used twice(save with the increasing
counter) if you recover the plaintext to one block of the message you will
know the output of SHA-1 for that block(the method described would result in
block encryption). You still will not know the output from the others
because the hash is not reversible. However, it gets worse if you have the
hash for several blocks of plaintext because you can guess the inputs to
SHA-1 and if any of the inputs you guess(brute force) produce any of the
known outputs of SHA-1, you can increment and/or decrement the value of that
input just as the counter would to return all of the other blocks.
Three: If it is discovered that collisions can be produced in SHA-1 there
would be serious problems(you wouldn't need the actual key, just one that
collided with it).
-steven
------------------------------
From: "Jae-Yong Kim." <[EMAIL PROTECTED]>
Subject: Counterpane and Mr. Schneier
Date: Sat, 11 Sep 1999 00:28:00 GMT
They seems to earn money only by book selling.. as far as I assume..
their algorithms and PRNGs are all free, unpatented..
doesn't they..?
------------------------------
From: "Ed Severn" <[EMAIL PROTECTED]>
Subject: OTP again
Date: Sat, 11 Sep 1999 01:25:23 GMT
If you XOR the same random pad with two plaintexts, then the lucky attacker
is able to compute the XOR of those plaintexts.
But what if the plaintexts are not so plain?
For example, what if you apply a randomized all-or-nothing transform to your
message (such as Rivest's "package transform") and *then* XOR the result
with your pad? (The result of the AONT is still plaintext in the sense that
no secret key is required to recover your message.)
If the attacker only has the XOR of two "package-transformed" messages, then
how can he proceed?
I realize that it is difficult to generate, distribute, and protect a truly
random pad. My question only concerns the danger of allowing the attacker
to see the XOR of two AONT-ed messages.
...Ed
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: simple key dependent encryption
Date: Sat, 11 Sep 1999 01:51:51 GMT
Kwong Chan wrote:
> If the key is of large period, say longer than the plaintext to be
> encrypted,
> is the polyalphabetic cipher still easy to be crack?
It's not really a *periodic* polyalphabetic in that case,
which does *not* seem to be the one intended in this thread.
Some aperiodic polyalphabetics can be cracked under some
circumstances.
------------------------------
From: Anti-Spam <[EMAIL PROTECTED]>
Subject: Re: some information theory
Date: Fri, 10 Sep 1999 18:34:47 -0700
SCOTT19U.ZIP_GUY wrote:
>
> In article <[EMAIL PROTECTED]>, Anti-Spam
><[EMAIL PROTECTED]> wrote:
> >John Savard wrote:
>
> - Much that I already said, deleted - (ah, the ULTIMATE compression - joking!) -
> John unless you can break new ground your fighting an uphill
> battle. In staic huffman coding you can send just the last
> half of file and it is trivial to reconsturct the underlying message.
> This is not so with "adaptive huffman compression". If you have
> a normal ascii message it would be very hard to even determine
> what the last symbol sent was. Using my file ending method
> the "all zero" weakness is not as weak as you may think. I still
> use a tree with only 256 leaves and one can not even tell by looking
> at the end of the file where the last symbol ended or started.
> If you only have the last half of a file. You don't even know where
> any symbol starts. You may be starting in the fragment of a symbol
> since there is no reference point for the start or end of any symbol.
> To decode you would have to guess the starting position of the first
> complete symbol and then guess its value. This is not a trivail task
> and has been looked at for years. It is not like your multisubsittution
> cipher in that they can be broken by plain text attacks. What you
> have when your looking at the last half of a file compressed with an
> adaptive huffman compressor is unique for that message alone.
> I would say if you can come up with a method to recover what the
> underlying text is in an ascii file that is compressed wiith an
> adaptive huffman compresser having only the last half of the file
> then you should be elevated to the status of Crypto God.
>
> 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
Thanks for the responses, everyone. There is much for me to think
about.
I will continue to mull over the idea of extending an (adaptive)
polyalphabetic cipher analysis to the problem of identifying the encoded
symbols in adaptive huffman coded compressed data/files. Ruling it out
(via proof or some other logical argument/analysis) is as important to
me as showing it works (via proof or some other logical
argument/analysis.) and, ....I haven't even thought about dictionary
codings - what problems would they pose?.... :)
It's a pleasant problem to poke at.
[EMAIL PROTECTED]
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Linear congruential generator (LCG)
Date: 11 Sep 1999 02:25:41 GMT
William A Moyes <[EMAIL PROTECTED]> wrote:
> time). Once when building a new 486 for someone else I tried an
> exhaustive search. Does anyone have a faster method than brute force?
> Every now and then I seek out the answer, but so far no one has one.
Yes, there are faster than brute force methods. They take advantage of the
fact that an LCG has a whole heck of a lot of structure to it. Knuth vol.
2 "Seminumerical Algorithms" has an introduction as to what this
"structure" is.
Klaus Pommerening has written a program which predicts linear
congruential generators. It uses the methods described in :
Inferring a sequence generated by a linear congruence
J. Boyar
Proc. 23rd IEEE Symp. on Foundations of Computer Science, 153-159, 1982.
journal version : Journal of the ACM 36: 129-141, 1989
The program is at
http://www.uni-mainz.de/~pommeren/Kryptologie/Material/lcgcrack.c
Test sequences at
http://www.uni-mainz.de/~pommeren/Kryptologie/Material/zuftab
http://www.uni-mainz.de/~pommeren/Kryptologie/Material/zuftab.{0 ... 5}
Terry Ritter posted a bibliography of papers on breaking LCGs on May 19,
1999. I reproduce it here :
Reeds, J. 1977. "Cracking" a Random Number Generator.
Cryptologia. 1(1). (Also: Cryptology Yesterday, Today, and
Tomorrow. 1987.
Editors: C. Deavours, D. Kahn, L. Kruh, G. Mellen and B.
Winkle. Artech House: Norwood, Mass. 509-515.)
Vahle, M. and L. Tolendino. 1982. Breaking a Pseudo
Random Number Based Cryptographic Algorithm. Cryptologia.
6(4): 319-328.
Frieze, A., R. Kannan and J. Lagarias. 1984. Linear
Congruential Generators Do Not Produce Random
Sequences. Proceedings of the 25th Symposium on the
Foundations of Computer Science. 480-484.
Knuth, D. 1985. Deciphering a Linear Congruential
Encryption. IEEE Transactions on Information Theory.
IT-31(1): 49-52.
Hastad, J. and A. Shamir. 1985. The Cryptographic Security
of Truncated Linearly Related Variables. Proceedings of the 17th
ACM Symposium on Theory of Computing. 356-362.
Reeds, J. 1977. "Cracking" a Random Number Generator.
Cryptologia. 1(1). (Also: Cryptology Yesterday, Today, and
Tomorrow. 1987.
Editors: C. Deavours, D. Kahn, L. Kruh, G. Mellen and B.
Winkle. Artech House: Norwood, Mass. 509-515.)
Vahle, M. and L. Tolendino. 1982. Breaking a Pseudo
Random Number Based Cryptographic Algorithm. Cryptologia.
6(4): 319-328.
Frieze, A., R. Kannan and J. Lagarias. 1984. Linear
Congruential Generators Do Not Produce Random
Sequences. Proceedings of the 25th Symposium on the
Foundations of Computer Science. 480-484.
Knuth, D. 1985. Deciphering a Linear Congruential
Encryption. IEEE Transactions on Information Theory.
IT-31(1): 49-52.
Hastad, J. and A. Shamir. 1985. The Cryptographic Security
of Truncated Linearly Related Variables. Proceedings of the 17th
ACM Symposium on Theory of Computing. 356-362.
Stern, J. 1987. Secret Linear Congruential Generators are
Not Cryptographically Secure. Proceedings of the 28th Annual
Symposium on Foundations of Computer Science. 421-426.
Frieze, A., J. Hastad, R. Kannan, J. Lagarias and A. Shamir.
1988. Reconstructing Truncated Integer Variables Satisfying
Linear Congruences. SIAM Journal on Computing. 17(2): 262-280.
Lagarias, J. and J. Reeds. 1988. Unique Extrapolation of
Polynomial Recurrences. SIAM Journal on Computing. 17(2):
342-362.
Boyar, J. 1989. Inferring Sequences Produced by
Pseudo-Random Number Generators. Journal of the ACM.
36(1): 129-141.
Krawczyk, H. 1992. How to Predict Congruential
Generators. Journal of Algorithms. 13: 527-545.
and to it, I'd add
"Pseudo-Random" Number Generation within Cryptographic Algorithms: The DSS
Case.
M.Bellare, S.Goldwasser, D.Micciancio. Advances in Cryptology (CRYPTO'97)
http://theory.lcs.mit.edu/~miccianc/papers/dss.ps
which is an example of breaking a system where the LCG output isn't
directly available.
-David
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Stream cipher from a hash function
Date: Fri, 10 Sep 1999 22:31:36 -0400
Steven Alexander wrote:
> There is a few simple problems with this:
>
> One, it's not safe to use the same password more than once because you are
> XORing plaintext with the output of the stream cipher. XOR is not safe if
> the key is ever repeated.
Well, this is true for ANY stream cipher. A salt is needed.
> Two: Even if the same password is never used twice(save with the increasing
> counter) if you recover the plaintext to one block of the message you will
> know the output of SHA-1 for that block(the method described would result in
> block encryption). You still will not know the output from the others
> because the hash is not reversible. However, it gets worse if you have the
> hash for several blocks of plaintext because you can guess the inputs to
> SHA-1 and if any of the inputs you guess(brute force) produce any of the
> known outputs of SHA-1, you can increment and/or decrement the value of that
> input just as the counter would to return all of the other blocks.
I see, so it is suseptable to a known plaintext attack. Is there any way to
strengthen this method? (This is just something I'm playing around with, not
something I expect to be totally secure by the way.)
> Three: If it is discovered that collisions can be produced in SHA-1 there
> would be serious problems(you wouldn't need the actual key, just one that
> collided with it).
Well, I was assuming a STRONG hash, but point taken.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: OTP again
Date: Sat, 11 Sep 1999 02:04:14 GMT
Ed Severn wrote:
> But what if the plaintexts are not so plain?
If you're going to all that trouble, you might as well
use a decent encryption system and drop the OTP.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: some coder/hacker help please?
Date: Sat, 11 Sep 1999 02:55:17 GMT
In article <[EMAIL PROTECTED]>,
John <[EMAIL PROTECTED]> wrote:
> How much stuff KB/MB do you have? I could put it up on a site
> I'm not using? Let me know.
>
> http://www.aasp.net/~speechfb
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
> The fastest and easiest way to search and participate in Usenet - Free!
>
It's about 100kb max... I could email the 5 files you need if you want.
BTW thanks for the offer :)
Tom
--
damn windows... new PGP key!!!
http://people.goplay.com/tomstdenis/key.pgp
(this time I have a backup of the secret key)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Alfred John Menezes)
Subject: Yet another chapter from the Handbook of Applied Cryptography
Date: 11 Sep 1999 02:45:40 GMT
In the past few months, we have made available 13 chapters
from our "Handbook of Applied Cryptography" for free download
from our web site: www.cacr.math.uwaterloo.ca/hac/
Our publisher, CRC Press, has generously given us permission
to place yet another chapter on the site. We have just uploaded
Chapter 10 (Identification and Entity Authentication).
We continue to negotiate with our publisher to have the last (!!)
remaining chapter as well as the appendices, bibliography, and index
uploaded to the web site.
We hope that these chapters will be of use to people in their
cryptographic work and study. We hope that by making the chapters
available for free download, the book will be accessible to those
who cannot afford to buy it, and to those who may only have a
cursory interest in the material presented in the book.
- Alfred
==========================================================================
| Alfred Menezes | Email: [EMAIL PROTECTED] |
| Department of C&O | Phone: (519) 888-4567 x6934 |
| University of Waterloo| Web page: www.cacr.math.uwaterloo.ca/~ajmeneze |
| Waterloo, Ontario | Web page for Handbook of Applied Cryptography: |
| Canada N2L 3G1 | www.cacr.math.uwaterloo.ca/hac/ |
| Centre for Applied Cryptographic Research: www.cacr.math.uwaterloo.ca |
==========================================================================
------------------------------
** 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
******************************
