Cryptography-Digest Digest #837, Volume #8 Sun, 3 Jan 99 22:13:04 EST
Contents:
Re: Encryption questions..... (James Pate Williams, Jr.)
Re: On leaving the 56-bit key length limitation (wtshaw)
Graph Isomorphism (Alan Martin)
Re: coNP=NP Made Easier? (ilias kastanas 08-14-90)
Help (How long can a post be seen?) (rosi)
Re: Help (How long can a post be seen?) (Tom McCune)
Re: Strange Code Floating About (William Barwell)
A good method? -finding the cheater in the sharing scheme
([EMAIL PROTECTED])
TinyIDEA update (2nd attempt) (Mark Andreas)
TinyIDEA update (fwd) (Mark Andreas)
Bitslice Implimentation of Crypt(3) ("Christopher Abad")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Crossposted-To: alt.sources.crypto,alt.2600.hackerz
Subject: Re: Encryption questions.....
Date: Sun, 03 Jan 1999 20:24:41 GMT
Reply-To: [EMAIL PROTECTED]
lordstar <[EMAIL PROTECTED]> wrote:
>I'm writing a term paper on how encryption could be the key to privacy.
>I'm looking for info on the basic on encryption.
See _Electronic Privacy Papers_ by Bruce Schneier and David Banisar.
For basic information on cryptography see _Applied Cryptography_ by
Bruce Schneier or _Handbook of Applied Cryptography_ by Alfred J.
Menezes et al. Use your favorite search engine and search for
"Bruce Schneier". Also, you might try the USENET newsgroup sci.crypt.
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: On leaving the 56-bit key length limitation
Date: Sun, 03 Jan 1999 15:17:34 -0600
In article <76mj9l$o1p$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> The current concept of "unicity distance" leads to wrong results and it is not
> practical....
I'll agree to that. Perhaps the term distance suggests too much that a
mathematical constant can be defined. Consider that this term is the
product of mathematicians who are expected gloss over things by lumping
them into some quantity that they do not define. Maybe, we should think
more of unicitiy distance as a interlocked factor with other things, not
to settling to those who want to isolate things into independent factors
either.
When things are rather difficult to pin down, the temptation is to speak
in terms of probability, but I don't find this a pleasing alternative
either. Perhaps it is best to speak of algorithms in terms of solvability
and the various factors that determine that.
We do know that some ciphers can be solved with less ciphertext, but some
cannot be conclusively solved with too little, which quantity might be
different depending on the insights of the solver. A clever ACA solver
like Honey Bee knows more subtile linguistic patterns than almost
anybody. She can pick up clues that most of us would miss. For her,
perhaps that unicity distance would consistently seem smaller than it
would for others; and given the same amount of ciphertext others could
solve, she might solve it faster for the same reasons.
>From a probability prospective, a good analysist can cut the alternatives
to a lesser number, so there are fewer alternatives left to choose from.
With mechanized solving, you might miss some subtile hints; indeed, you
must program in all of what you know if you do not simply want to brute
force the whole thing and list all the possibile plaintexts.
>From this, it might be infered that unicity distance is hardly an easily
defined constant at all, but more or a Rod Serling type twilight zone
without sharp edges, in the midst of which reality, plaintext, is
reasonably indistingishable from the noise of alternative interpretations.
--
An interesting year is ahead of us, enjoy.
------------------------------
From: [EMAIL PROTECTED] (Alan Martin)
Subject: Graph Isomorphism
Date: Sun, 03 Jan 1999 18:48:32 GMT
Is graph isomorphism still considered to be a hard problem suitable
for use in cryptography?
It is mentioned in the second edition of Applied Cryptography.
According to the errata, although it is not known to be NP-complete,
it may be useful in cryptography.
If so, how large should the graphs be, and what special properties
should they have, to resist isomorphism-finding algorithms?
--
Alan Martin
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (ilias kastanas 08-14-90)
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: 3 Jan 1999 23:38:19 GMT
In article <[EMAIL PROTECTED]>, rosi <[EMAIL PROTECTED]> wrote:
@[EMAIL PROTECTED] wrote:
@> [snip]
@
@ Dear Ilias, I believe you are reknowned and respected. For the
@people posting in this thread know you are a professor and addressed
@you by Dr. I nevertheless would never know from your name or e-mail
@address (which is not a real one). I wonder if I could ask a favor
Hmm, the name "rosi" is not real either... Just kidding. Actually
the dejanews address above _is_ valid; the "uucp" one, on the other hand,
(which you may have seen), protects my "real" address admirably -- zero junk
email.
@of you. Could you get one of the experts involved? Papadimitriou was
@mentioned more than once. Could you, or any who is following this
@thread, get one or more of that caliber to say either:
@ The argument of ROSi is total trash, or
@ The argument of ROSi deserves a brief look, or
@ The arguemnt of ROSi (even without looking at it) is not
@ worth wasting time on?
But what is the argument? I asked for a precise description of the
proposed machine for coSS, but never saw one.
In article <[EMAIL PROTECTED]>, rosi <[EMAIL PROTECTED]> wrote:
@Dear Ilias,
@
@ I see that you see that M behaving as described in 26 is NOT
@fine.
@
@ But you said there exists such a mechanism, NDTM to be exact,
@that behaves as described in 26 (and you do not need to show its
@construction and it simply exists). I seem to have the impression
I've _shown_ the construction of K. Behavior: for any S,i, if i is
a subset-sum, THERE EXISTS some computation of K (among the many possible for
that S and that i) printing YES#. And there exists none if i isn't.
_This_ behavior is called "accepting SS in ND pol. time".
You want to think about other behaviors? Good. But they don't
affect the definition of NP.
@from your that the only valid type of NDTM are those behaving as
@described in 26 (as you would not take anything but your K).
@ Now things are simpler. As there can only be NDTM behaving as
@described in 26, the answer to my FIRST crucial question should be
@NO. Because obviously, your K (a representative of those NDTM's
@behaving as described in 26) can halt with things other than YES#
@on its output tape, your K is not the mechanism I am asking for.
You are asking for "FOR ALL" instead of "THERE EXISTS" above.
A different behavior. Of course K doesn't have it.
@And according to you, unless I am wrong, that the only halting and
@output behaviour of an NDTM is as described in 26, so no NDTM can
@be the one I am asking for. So the answer should be simply NO. I
I believe the correct answer will turn out to be NO... but that
is belief, not proof.
@do not understand why always such fuss. Just as for the simple
@answer to the simple question about a mechanism that solves SS
@in finite time, I can not understand why the fuss about NDTM and
@DTM. If there exists one (DTM or NDTM), just say YES. A primary
@school kid would do so.
And then, in junior high, the kid would be shocked to realize it's
presently _unknown_ what the answer is... YES?... or NO?
Why so? Imagine a ND TM such that, given S,i as above (i subset sum)
ALL computations print YES#, and given i non-subset-sum no computation prints
YES#. If such exists, you can cut it down to deterministic by eliminating
alternative transitions... and thus get a D TM that accepts SS! So your
question is equivalent to: is P = NP ? Sorry, Yes or No to _that_ is a bit
of a fuss... not exactly "simple"... for kids, and even for grownups.
@ We are slowing down. Let me speed up by asking the crucial
@question once more (and this time in full to save us one round of
@posts):
@ 41. Does there exist a mechanism MM (ANY mechanism) that,
@ when S, a finite set of integers, i', a subset sum of S,
@ and n the size of the input/problem) are given as input,
@ _ALWAYS_ HALTS within a polynomial bound (or in other
@ words: whose complexity is bounded by some polynomial
@ function f(n) where n is the input/problem size) and
@ _ALWAYS_ ANSWERS POSITIVELY (or our version to be specific:
@ prints YES# on its output tape on halt); AND that, when S,
@ a finite set of integers, i", an integer that is NOT a
@ subset sum of S, (and n the size of the input/problem) are
@ given as input, _NEVER_ prints YES# on its output tape?
To be sure, it is a crucial question: is P=NP?. Not exactly a new one,
but... hey.
@ Repetition and details do not bore everybody every time. So
@here we go again:
@ If MM(S, i', n) EVER prints anything other than YES# at halt,
@it is NOT the mechanism I am asking for.
@ *** IMPORTANT: it seems that your K is obviously ruled out,
@ *** and you should have realized this long, long ago. A high-
@ *** school kid would. So please do not bring it back to create
Ah!... The light dawns.
@ *** further headache. I am asking for one that ALWAYS prints
@ *** YES# at halt AND halts within polynomial bound. If you can
@ *** not think of one or can prove that in this whole wide
@ *** world there is none, you can simply say "NO" to the question.
@ *** If you are right, you will be right. The world is watching us).
Why ask me?!... Ask the high-school kid.
@ If MM(S, i', n) EVER prints YES# only after exp time, it is
@NOT the mechanism I am asking for. (This means if there is ever an
@instance with the tuple <S, i', n> that results in MM printing YES#
@only after exp time, it is NOT the mechanism I am asking for.)
@ If ALWAYS MM(S, i', n) < f(n) and prints YES# at halt, and
@ALWAYS MM(S, i", n) < g(n) for some polynomial g and NEVER prints
@YES#, it _IS_ the mechanism I am asking for (am not implying in
@any way that it exists).
@ If ALWAYS MM(S, i', n) < f(n) and prints YES# at halt, and
@MM(S, i", n) NEVER halts and NEVER prints YES#, it _IS_ the
@mechanism I am asking for.
@ If MM(S, i", n) EVER prints YES#, it is NOT the mechanism I
@am asking for.
@ I repeat, there is no multiple run issue. This mechanism should,
@if one exists at all, _ALWAYS_ halt within polynomial bound and
@print YES# at halt after it is started (or the "START" button is
@pushed).
The mechanism's existence (i.e. P=NP) trivially implies NP=coNP.
A clean sweep, what.
@ As far as I can see, there are only three meaningful answers to
@41 (or 42):
@ YES, THERE IS (or I ASSUME THE EXISTENCE)
@ NO, THERE IS NONE (or I ASSUME THE NON-EXISTENCE)
@ I DO NOT KNOW
@
@ Please provide straight and clear answers. Please do not evade.
Oh. Anything else?
@ When answer other than "I DO NOT KNOW" to 41 (or 42) is provided,
@I will evaluate the answer and bring this boring topic to an end
@(hopefully).
It's good to end on a hilarious note.
@ As to "I DO NOT KNOW", I can close the chapter right here.
@ You do not know what you have been talking about. You have
@wasted people's time and bandwidth.
Don't worry, the chapter is closed already.
Look, Rosi, it's nice you've just re-discovered P=NP? is an open
question. My postings are out there for everyone to see and judge. Your
new tone and attitude you can practice with somebody else.
Ilias
------------------------------
From: rosi <[EMAIL PROTECTED]>
Subject: Help (How long can a post be seen?)
Date: Sun, 03 Jan 1999 12:55:33 -0800
Hi,
This is not related to any cryptographic topic.
I would like to know how often and when old posts are purged. It
seems to be used to staying longer than now (I can be very wrong).
Any idea about this is appreciated. (If you prefer to e-mail me,
my e-mail address: [EMAIL PROTECTED]).
Thank you very much in advance.
--- (My Signature)
P.S.
Understand that the purge is necessary for maintanence and other
purposes. Am not complaining at all. Just want to have an idea so
that I do not miss any replies to posts and would not have to go
to the archive. Thanks.
------------------------------
From: [EMAIL PROTECTED] (Tom McCune)
Subject: Re: Help (How long can a post be seen?)
Date: Mon, 04 Jan 1999 01:02:08 GMT
=====BEGIN PGP SIGNED MESSAGE=====
In article <[EMAIL PROTECTED]>, rosi <[EMAIL PROTECTED]> wrote:
> This is not related to any cryptographic topic.
>
> I would like to know how often and when old posts are purged. It
>seems to be used to staying longer than now (I can be very wrong).
>
> Any idea about this is appreciated. (If you prefer to e-mail me,
>my e-mail address: [EMAIL PROTECTED]).
That is determined by whoever is providing you your newsgroup service.
Typically this is not long because all the thousands of newsgroups
(esp. the binary ones) take up huge amounts of space.
=====BEGIN PGP SIGNATURE=====
Version: PGP Personal Privacy 6.0.2
Comment: http://www.Tom.McCune.net
iQEVAwUBNpATDWR4bNCQMh9JAQFJWAf/a6CqGULJhYFxglw8yxR/5RCIY1PNmrZm
tNzQYIkSEWh1ybFkhpRKDIVliHx9cxJuRMLzdEFfaiXoDhI65RzHj5BJEjVVwVll
XYOZEyNUUFZMmQ+uR0UsPFHmR1b8TkvjrzcLbZ6skBAV7+eFV0LY9A+6yO6TKnxk
o77314LbuehqUX1IyDsKCWRnuxCz0Cuj4QPCjhgq5QxYo/CWavmZY6K5BkfASc9e
L/qdyidUyAGhLvaR872qh575IJid5rLFS+pxTQGGGCdVoeK4piHz7cg5BT4nveBY
+aMw5vJ1EJ2zPJkm8+Hs5WyBGvwYZ1fBmt0FG+K45yG5bjYiSvTukg==
=HL4O
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (William Barwell)
Crossposted-To: tx.guns
Subject: Re: Strange Code Floating About
Date: 3 Jan 1999 19:47:51 -0600
In article <[EMAIL PROTECTED]>,
Mark Terka <[EMAIL PROTECTED]> wrote:
>On 2 Jan 99 00:20:36 GMT, [EMAIL PROTECTED] wrote:
>
>>Mark Terka ([EMAIL PROTECTED]) wrote:
>>: I'm enclosing another poster's message. Anybody know what this might
>>: be, or is it just gibberish?
>>
>>It's one of the "Hipcrime" messages, part of an attack on USENET that's
>>been going on for some time, but which has been shifting between different
>>newsgroups. Shades of the "poetry festival" that I encountered on Deja
>>News and mentioned a while back...
>>
>>It is, apparently, just gibberish.
>
>I guess I'm kinda out of the loop, but what is "Hipcrime"????
>
A malicious piece of bot software distributed by some net vandals
to harrass newsgroups because they were unhappy that people cancel
spam. It was designed to make net vandalism easy and not demand
much hacker skill. The idea was to try to make cancels useless
thus defeat spam cancellers.
See news.admin groups to keep up with this nonsense.
Pope Charles
SubGenius Pope Of Houston
Slack!
------------------------------
From: [EMAIL PROTECTED]
Subject: A good method? -finding the cheater in the sharing scheme
Date: Mon, 04 Jan 1999 02:14:52 GMT
A guy told me a method on finding the cheater in the sharing scheme.
He said
when we calculate the shadow S(i) and get it to user U(i),
we calculate H(S(i)) and make H(S(i)) public for all the user,
where H(.) is a hash function.
Then, when a group of users want to reconstruct the secret,
each of them give out his shadow S*(i), and each other
calculate H(S*(i)). If it is not equal to the H(S(i)),
then the user U(i) is a cheater.
Is it a good method? I do not think so.
Can you help me to give the guy some reason.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Mark Andreas <[EMAIL PROTECTED]>
Subject: TinyIDEA update (2nd attempt)
Date: Sun, 03 Jan 1999 20:19:13 -0600
This is my second attempt at posting this. Several people have reported
that the first message was garbled at their newsfeed, and it didn't even
show up at my own. I checked DejaNews, and it showed up just fine
there.
=====BEGIN PGP SIGNED MESSAGE=====
Announce: New version of TinyIDEA
This is announcing the release of an upgrade to TinyIDEA. TinyIDEA,
currently available in idea3a.zip, is a very small DOS program which
performs 128-bit IDEA in CFB feedback mode - after hashing a keyboard
passphrase using Tandem Davies-Meyer. TinyIDEA encrypts the file
in-place, meaning there is no need to secure-wipe the plaintext after
encryption, and there is no risk of out-of-diskspace errors.
I have continued size optimizations on this program, and have
released the upgrade. The new version can be downloaded at:
http://www.sky.net/~voyageur/tinyidea.htm
Unfortunately, my program must be export restricted. The predecessor
version can be downloaded from Fauzan Mirza's page:
http://www.cs.rhbnc.ac.uk/~fauzan/tinyidea.html
The upgraded program does have a few extras, including:
* Smaller size. The current idea3a.com is 503 bytes. The upgrade
contains a program 100% compatible with idea3a.com, with a size
of only 366 bytes.
* Assembler source code is switched from TASM over to A86, which
can be downloaded at http://www.eji.com
* Passphrase can be put on the command line.
* Includes several varations, with different combinations of
features. These features may introduce incompatibility with
idea3a.com, but were introduced in an attempt to improve
security.
* More
The most important change in the new version of TinyIDEA is getting
rid of the initialization of the feed back with all 0x00's.
Previously, if you always used the same passphrase, this caused all
files with similar beginnings to have similar beginnings to their
ciphertext. You could XOR both first-blocks together and get the
same result as if you XOR'ed both first-block plaintexts together.
However, once any bit difference occurs, no such relationship exists
for later blocks.
Encryption-in-place without changing the filesize is one crucial
element in keeping the program's filesize small. The encryption
subroutine is actually a very small part of the program. A good
portion of the program is involved with file-handling and hashing the
text passphrase down to a 128-bit value.
For the encryption key to change while using the same text
passphrase, I had to use information about the file which would be
available to the person decrypting the file. This means using the
filesize and filename as part of the process which generates the
encryption key.
For the main upgrade version, I am only combining the filesize with
the passphrase. TinyIDEA uses older Interrupt function-calls, which
means those who are using Windows 95 may try to encrypt
LongFilename.TXT, with TinyIDEA seeing LONGFI~1.TXT. Unfortunately,
at time of decryption, the shortname isn'g guaranteed to be the same,
and could be LONGFI~2.TXT, or something else.
The main TI.COM will combine the filesize with the passphrase, and an
additional TISN.COM will combine the filesize and the filename with
your text passphrase.
Combining the filesize will greatly reduce the odds that 2 messages
will have the same encryption key, and using TISN.COM would further
reduce the odds - especially if your practice is to always use
different filenames for each message.
Double encryption with the same passphrase will still result in
decrypting the first block. Even though the initialization will no
longer be 0x00's, you will be encrypting the same block twice, and
the feedbacks will cancel each other out. However, you shouldn't be
doing double-encryption, but rather encrypt/decrypt/encrypt, with 2
or 3 different keys.
If you need to email me, my RSA-2048 key is:
- -----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.2
mQENAzFbXkoAAAEIAJkM0XM00Kobwpq2QdiIxe1kpj54zB7LKQTM7ZtXgldluiKR
uwSLKaGqE1TApj4xVHxI3HolxFlIWhIRHf2bZe7dUf3m7hT83d4UmzuEZ3OYETek
kpBcc0n71vkBbbITUlHivBj/2Eg6HO5cRvoO8UmOibJbKn31uZyf/Cuiwr/yYGVA
b42QmOlXVAY6spFjv3KkpqHEz75bxNEjIv4FFq5AsvIOgmHtdqpzG6R5qwIldO5d
dqrz+6yjPfBBYw0NZMFObWU/DYWrQe7W/jumMgsUTiE7H06jC6clD7TN6NaIY44d
6hBneGfIf2LKQHLPr5iR/8sLoAnax0tkWnfvdrEABRG0H01hcmsgQW5kcmVhcyA8
dm95YWdldXJAc2t5Lm5ldD6JARUDBRAxYFTKx0tkWnfvdrEBAWDhB/wLI71EGTcz
vjjqliFrnVXUV443hCioX7n6X8pHPYEpfeB8Ux6J4p9irj85C8Mlep2pFlHGkP6A
gQXjkHD7x9h8uTL9+/VQ1m88lXCSUML+SKM5A/EPWt+h40gjp5SEVTPVplU+MLi0
vTCHWMGyrFwShVabYe4Ar5JGGSo1tBIBgxp1nack/f3YB9xrS0y8MSz+rsARPIq7
p88te2Gjt9kMcwtOJwC9DDkwBA5SHO4FBapjJvJ0iaHzSw33K2b9DcN2QZc6LfDa
GDcgtYDR7NqM+nRGR8EVuorFNtigVMlFTI2qLE6+bQAUQAHl13Fs7bSvkvjcN+GD
6sUD//nFad1I
=qoJc
- -----END PGP PUBLIC KEY BLOCK-----
=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/
Mark Andreas <[EMAIL PROTECTED]> http://www.sky.net/~voyageur
PGP key 77EF76B1 available via key server, finger or webpage
=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
Comment: 2048-bit RSA key at: http://www.sky.net/~voyageur/crypto.htm
iQEVAwUBNo7ku8dLZFp373axAQFzLQf/Yn+wam1RYm34qoGV+pSaas7ET5s2YjDZ
dlS3cPgv6yLzW2dohcH1T5GwQebnK2JI/X8WAkshiAWhdX0CSh9uWztEMlBtyb6A
VglR3YIqxVAVc9tTZzD9qPgXpuxbzs3mD6iQ+evwtkX11mRFZY71yrtInn5PDd55
MCtFW9ikinqVbtQ1RLLWnAaDfCh8dCqUFOyL1pYFXOAiMdeF9ETk/n8ozQyf7wsA
gj4oqJR9fw5hBrHywoNbqVEf9qj8ptjXgMeYqtz78BPJteqaHfyUTSkUytSoIfaV
/+H//V/qbUmGxsU7ZT4dOsi496rqve5TLSwUfHTOsIkEsG4/vR63WA==
=vFYq
=====END PGP SIGNATURE=====
------------------------------
From: Mark Andreas <[EMAIL PROTECTED]>
Subject: TinyIDEA update (fwd)
Date: Sun, 03 Jan 1999 20:27:53 -0600
I have reposted the message again. Please let me know if it *doesn't*
show up. I didn't repost to any of the other newsgroups this replay was
posted to, since I hadn't posted to them in the first place.
Thanks again.
--
=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/=/
Mark Andreas <[EMAIL PROTECTED]> http://www.sky.net/~voyageur
PGP key 77EF76B1 available via key server, finger or webpage
=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\
------------------------------
From: "Christopher Abad" <[EMAIL PROTECTED]>
Subject: Bitslice Implimentation of Crypt(3)
Date: Sun, 3 Jan 1999 18:36:24 -0800
I am looking for a bitslice implimentation of the crypt(3) DES function used
in LibDES for hashing passwords
------------------------------
** 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
******************************
