HDTenEightyP/NetNews huggingface dataset:
From: Erik.Lindano@ofa123.fidonet.org
Newsgroups: sci.crypt
Subject: New Encryption - a Challenge
X-Sender: newtout 0.02 Nov 17 1992
Date: 18 Nov 92  21:54:24

Writes thompson@sun425.nas.nasa.gov (Keith C. Thompson):
 
 > And, there is one small problem.  The issue is the unicity 
 > distance of the algorithm.  It is impossible to decrypt ciphertext 
 > that is shorter than the unicity distance of the algorithm.  For 
 > instance, the ciphertext DFJUG resulting from a simple 
 > substitution could be any five letter word that had no repeated 
 > letters.  
 
 OK, how many words/letters would you like?
 
 > It is possible that the surrounding context is insufficient to 
 > determine the correct decryption. For instance, it could be a 
 > proper noun that does not appear anywhere else in the plaintext.
 
 We'll give you as much text as you want (within reason - please!). 
 You choose the plaintext. We can guarantee that the unknown word 
 will also be found among the known ones. [But please don't ask 
 for a two-word file then!  :-) ] 
 
 Or you could submit some pattern of your own, such as a numerical 
 or alphabetic progression of any kind, any length. Or a large file 
 consisting of nothing but zeroes, with one set of eight non-zero 
 characters embedded in the middle. (Try that on RSA or DES).  Name 
 your poison. One smart cookie has already asked for a set of
 files incorporating a slowly-changing alphabetic progression...
 
 > The real question, is can you and your friend make a suitable 
 > challenge such that people are willing to take you up on it.  
 > After all, you are essentially asking others to expend a 
 > potentially large amount of effort for little or no reward.  
 > Think of it as a challenge...
 
 Thanks.  WE are going to try.  
 
 > Well, seeing as we have not heard from your friend, there is no 
 > way for us to judge whether he is up on the technology in the 
 > field or not.  You have given us no indication that would suggest 
 > that he is, and one that would suggest otherwise.
 
 We've asked no one to make such a judgement. We only want to know 
 whether the experts here can break an encrypted message where only 
 ONE WORD is not disclosed, under fair terms, or even terms of their 
 own choosing. 
 
 In any case, I can't _force him_ to post anything, but he might 
 very well decide to do so. I sure hope he does, because you guys 
 are beating the bejesus out of me.  I can't take this any more!  
 Aaaarrrgghhh..!!  :-) 
 

--- Maximus 2.00
Newsgroups: sci.crypt,alt.privacy,misc.legal
From: gardner@convex.com (Steve Gardner)
Subject: Re: Registering "Assault Keys"
Date: Mon, 16 Nov 1992 15:45:21 GMT
Organization: Engineering, CONVEX Computer Corp., Richardson, Tx., USA
X-Disclaimer: This message was written by a user at CONVEX Computer
              Corp. The opinions expressed are those of the user and
              not necessarily those of CONVEX.

In article <1992Nov16.144924.7147@inel.gov> whg@inel.gov (Bill Gray) writes:
>I suggest that the first ammendment will stand up no better than the fourth
>and fifth.  The gov't will simply invoke civil forfeiture against those who
>use cryptographic methods to conceal what it wants to see.  There is nothing
>illegal about having a lot of cash on your person,  but that hasn't stopped
>various LE agencies from seizing same.  Just so,  using encryption could be
>seen as justification for forfeiture.
	Clearly you are correct about the effect of civil forfeiture on
	the bill of rights. When do you suppose people will wake up to 
	realize that their constitution has been effectively abolished and 
	do something about it?  When will the (hopefully) bloodless 2nd 
	American revolution happen?  

	Do you think anyone cares about real freedom anymore or is it
	just a pretty word that they talk about?  Do we really believe
	it is necessary to make sacrifices for freedom or is that
	just part of the ceremony on Veterans day?  Are Americans worthy
	of their constitution or have they become too complacent and
	willing to accomodate themselves to any government outrage as
	long as their creature comforts are preserved?

	
Xref: sparky sci.crypt:5161 comp.theory:2503 sci.math:15352
From: ramsay@math.ubc.ca (Keith Ramsay)
Newsgroups: sci.crypt,comp.theory,sci.math
Subject: Re: Cryptography and P=NP
Date: 21 Nov 92 23:30:24 GMT
Distribution: inet
Organization: University of British Columbia, Vancouver, B.C., Canada
NNTP-Posting-Host: gauss.math.ubc.ca

In article <By2tv0.BDn.2@cs.cmu.edu> sgall+@CS.CMU.EDU (Jiri Sgall) writes:
>1. I have an explicit algorithm for factoring which is polynomial if P=NP. 
>(No matter if you prove that nonconstructively.)

This is correct: it depends upon the factorization problem being in NP
and co-NP. On input n, the algorithm applies assorted other algorithms
to the number n, in parallel, occasionally adding new ones to the
"pool", and scans the output for a factorization of n, together with a
proof that the factors are prime. There *always* exists a short such
factorization *and* short proof that it is correct. The only problem
is with finding it.

If P=NP, then one of the algorithms out there is a "smart" one which
solves the problem in time polynomial in the length of n (log n). One
will eventually add it to the pool. Of course, you won't know which
one it is, but it will give you the factorization with proof. This
algorithm is hopelessly slow, however, as the constant in the time
required for it to run depends upon the number of algorithms one would
have to search through, one by one, before encountering the magic
algorithm which factorizes quickly.

>2. I have an explicit algorithm that finds a satisfying assignement of a 
>satisfiable formula (but may run forever on an unsatisfiable one) if P=NP.

This is also true, and if P=NP the algorithm can be made to find the
satisfying assignment in polynomial time. Note that this is not the
same as having an algorithm which solves the satisfiability problem,
since you don't know how long you might have to wait for the program
to find the assignment.

*If* you knew what the polynomial was, which bounded the length of
time required to find the assignment, then you *would* be able to make
it into a genuine algorithm for solving the satifiability problem, by
making it stop with a negative result once the time limit has been
passed.

Not having a limit on the size of the algorithm required, and on the
polynomial bounding the length of time it would require to operate, is
the essential reason why one might (so far as we can tell) have a
non-constructive proof of P=NP.

Keith Ramsay
ramsay@unixg.ubc.ca
From: leichter@zodiac.rutgers.edu
Newsgroups: sci.crypt
Subject: Re: Triple DES
Date: 19 Nov 92 20:06:11 GMT
Organization: Rutgers University Department of Computer Science

In article <1992Nov19.150019.19072@news.nd.edu>, scharle@lukasiewicz.cc.nd.edu
(scharle) writes:
| || The recently demonstrated fact that DES is *not* a group indicates that
| || a double encryption *is* stronger than single encryption.
| 
|     Excuse me, for I am really an amateur in this subject, but I
| don't see the chain of reasoning here.  If I am just being particularly
| dense, please keeps the flames low, and I'll shut up.
| 
|     What has been shown is that iteration of DES with different keys 
| results, in general, in encryption which is different from DES.  I 
| believe that that is different from showing that iteration results
| in something _stronger_.  As far as I can see, it is consistent
| with someone discovering that two applications of DES could result
| in a encryption which is in fact easier to break -- for example,
| there could be some interaction between keys, that would result in
| an easy cipher to break, so that there would have to be some care
| in choosing keys.  It is also consistent with it being discovered
| that iterations of DES are _equally_ difficult to break as single 
| uses, perhaps just a different method has to be used.

This situation provides an excellent way to demonstrate a fundamental
approach for reasoning about cryptosystems.

Can double DES encryption be weaker than single DES encryption?  The
answer is, in general, no - and I can prove this knowing nothing at all
about DES.

Suppose it were true that double encryption was weaker, and suppose I'm
a cryptanalyst with access to E(C,k), where E is DES encryption, C is
cleartext, and k is the unknown key.  Rather than attack the "hard"
problem of single DES encryption, I'd simply choose my own k' and do my
own double encryption:  I'd attack the "easier" encryption E(E(C,k),k').
It cannot possibly hurt me that I *know* k'!

Conclusion:  While it may be that for SOME values of k', some kind of
cancellation takes place, if they are at all common, then SINGLE DES
encryption is *already* weak, since looking for such a k' would amount
to an easy attack against it.

General principle:  Anything the cryptanalyst can already do for himself
cannot weaken the cryptosystem significantly - since if it did, he WOULD
do it for himself.

Note that this approach cannot prove that double encryption is HARDER to
break than single encryption - it can only show that it cannot be EASIER.
Whether DES forms a group or not, it is possible that double encryption is
stronger, and it's possible that double encryption is equally strong.
Without further work, we just don't know.  (Actually, "meet in the middle"
attacks show that double encryption, done this way, cannot be MUCH stronger
than single encryption - though it may be SOMEWHAT stronger.)

							-- Jerry
From: cme@ellisun.sw.stratus.com (Carl Ellison)
Newsgroups: sci.crypt
Subject: Re: RSA FAQ & Differential Cryptanalysis
Date: 23 Nov 92 18:53:11 GMT
Organization: Stratus Computer, Software Engineering
NNTP-Posting-Host: ellisun.sw.stratus.com

In article <1992Nov20.195655.147884@watson.ibm.com> uri@watson.ibm.com writes:
>How can it be possible, that the expected time to succeed is 
>not dependent on how often I change keys?


If you know that there's a stereotyped plaintext, you can build a file of
all possible encryptions of it then sort that file by the ciphertext
(record just ciphertext and key in the file).

You would have to change keys faster than I could look up plaintext.  (This
is possible.  The file would be huge (6E17 bytes, or so) and it might take
many seconds to look up a key.)

Of course, if you have a PRNG-driven key change algorithm and use a
different key for every 8 byte round of DES (in CBC mode, of course), then
even my break into the crib at the beginning won't tell me what you're
using for the second key and second 8 bytes.  You could use DES itself (or
IDEA) in CFB mode as the PRNG for generating your keys.

This gets expensive.  The DES key scheduling algorithm takes more time than
a round of encryption.  However, if all you're doing is encrypting text at
human typing speed and have a Sparcstation to do it with....

-- 
-- <<Disclaimer: All opinions expressed are my own, of course.>>
-- Carl Ellison						cme@sw.stratus.com
-- Stratus Computer Inc.	M3-2-BKW		TEL: (508)460-2783
-- 55 Fairbanks Boulevard ; Marlborough MA 01752-1298	FAX: (508)624-7488
From: leichter@zodiac.rutgers.edu
Newsgroups: sci.crypt
Subject: Re: Cryptography and P=NP
Date: 19 Nov 92 19:25:10 GMT
Followup-To: sci.crypt
Distribution: inet
Organization: Rutgers University Department of Computer Science

In article <1992Nov19.102822.1@zodiac.rutgers.edu>, I said:
| Yes.  Programs in class P are defined as those for which, for any input of
| length n, we can prove they halt after taking no more than p(n) steps, where
| p is some polynomial.

This is poorly stated.  Whether a program is in P or not is a fact, whether we
can prove if or not.  A program is in P if there exists a polynomial p such
that, for any input of length n, the program will, in fact, halt in most p(n)
steps.  If proving that things were or were not in P were trivial, then the
question of whether P equals NP would be trivial, too:  Because, say, 3-SAT
is complete for NP, if we could prove 3-SAT was in P, we'd know P=NP; if we
could prove 3-SAT was NOT in P, then P!=NP.  As it is, we simply don't know.

(And, yes, there are all sorts of philosophical - and mathematical! - com-
plexities to the question of what "actually does halt" means!  Since it is
known that there are oracles relative to which one can prove P=NP, and others
relative to which one can prove P!=NP, in a sense there are "plausible worlds"
(or very slightly more general notions of computation) in which P=NP, and
other "plausible worlds" in which P!=NP.)
							-- Jerry
From: mathew <mathew@mantis.co.uk>
Newsgroups: sci.crypt
Subject: Re: PGP and real criminals
Date: Thu, 19 Nov 92 14:47:53 GMT
Distribution: world
Organization: Mantis Consultants, Cambridge. UK.

prz@sage.cgd.ucar.edu (Philip Zimmermann) writes:
[ Assorted examples of extremist viewpoints deleted ]
> If we are to prevent the electorate from backing legislation that
> will make cryptography a crime, we must have articulate agruments
> that will reach normal people with normal values.  Some of what I've
> seen lately does not meet that requirement.

Well, I tend to argue the case for legal cryptography by using two arguments
which I think anyone can understand and sympathise with.

The first is:  Does the person arguing for a ban on cryptography trust the
government completely?  Is he happy to let the government eavesdrop on *his*
communications whenever *they* (not the populace) decide there's a good
reason?

If the answer is "Yes, I trust the government", then I give up.  You can't
argue with positions like that.

The second argument is:  Does the person arguing for a ban on cryptography
have any idea how this ban might be enforced?  Given that it is possible to
disguise encrypted data as plain text, how will the ban be enforced? 
House-to-house searches?  Polygraph tests?   Informants?  House Cryptographic
Activities hearings?


mathew
-- 
"Even the most bizarre of the unions (probably that between a cat's gall
 stone and a single note 'G' from CNN's ident theme) managed to convey a
 sense of rampant impropriety."  -- 'Fortran Five', Simon G. Lawrence Leonard
From: jbs@watson.ibm.com
Date: Thu, 19 Nov 92 19:24:51 EST
Newsgroups: sci.crypt
Subject: Triple des

         William Hugh Murphy said (regarding triple des encryption)
>If you were not trying to solve the special problem of backward
>compatibility, you would likely use two encrypt steps.  This would
>give the same protection and only double the time.

         Actually there is a "meet in the middle" attack against double
des encryption which takes time 2**56 (albeit using space 2**56).  So
far as I know, there is no similar way of attacking IBM's triple des
scheme.  So in this respect at least the triple scheme is stronger.
                          James B. Shearer
Newsgroups: sci.crypt
From: dionc@ireq.hydro.qc.ca (Claude Dion ETUDIANT sept-dec 92)
Subject:  Help with a problem 
Organization: Institut de recherche d'Hydro-Quebec, Quebec, Canada
Date: Tue, 17 Nov 1992 14:24:47 GMT

A friend of mine resently sent me the following message:

   NCPUCNNYHCSD
   FSNCYFMYSNTN
   OSTAKOYNHWFK
   QMHWMUNSHQKQ
   EFBADNKMDUYD
   NCSFGRTQFKRE
   BYNSDXRHDSSD
   EFZTFZNYBANT
   NSAMSNCUFZMK
   FLJTDXHQSDYS
   KRNSFDAISVSB
   TIONJKPSFYNS

Despite numerous hours of work on the probleme, I was not able
de decypher it (I am not an expert, or even an amateur, at this
sort of thing).  I would appreciate if anyone could decypher this
message and explain to me how I could decypher any other message
coded the same way (don't worry, this is only for fun).
Warning:  the decrypted message may be in English but it MAY
ALSO be in French.


Please e-mail answer to dionc@ireq.hydro.qc.ca

Thank you.

Claude Dion
Newsgroups: sci.crypt,sci.math,comp.theory
From: phr@telebit.com (Paul Rubin)
Subject: Re: Cryptography and P=NP
Organization: Telebit Corporation; Sunnyvale, CA, USA
Date: 15 Nov 92 21:52:02

Factoring is in both NP and co-NP; unless there's been some stunning
recent developments, nobody knows if factoring is NP-hard.  So
even if P!=NP, factoring might be in P.  Most theorists think
P!=NP, but some very sharp mathematicians think factoring is in P.
I don't understand the nature of the evidence.  But RSA might
indeed be in worse trouble than cryptography in general.

On the other hand, I've heard that serious crypto spooks mostly
laugh at all public key systems, other than RSA with very large
keys (500 digit primes and 1000 digit modulus--that's -decimal- digits).
Crypto schemes based on NPC problems have been broken.

    Remember that polynomial could be x^(10^10), in which case we still
    don't have much to worry about.

Depends on the model of computation that you use.
Xref: sparky sci.crypt:4879 alt.privacy:2300
From: sysevm@nsrvan.vanc.wa.us
Newsgroups: sci.crypt,alt.privacy
Subject: Re: Limits on the Use of Cryptography?
Date: 16 Nov 92 18:40:39 GMT
Article-I.D.: nsrvan.1992Nov16.104039.54
Organization: National Systems & Research, Vancouver WA


	Let's just jump ahead and to thwart the attempt to limit freedoms of
speech and security in papers. How?

	Lets get as many of the people of all places using strong crypto
systems as we can. RSA is licensed for personal use to individuals by my
reading of the FAQ.

	So, lets implement on an individual level RSA into the E-mail system.
First to encrypt mail as it comes in (to prevent unauthorized disclosure). And
later to authenticate the sender and the content of E-mail. Both are usefull
and of benifit to society.

	I think I'll start on my personal copy of mail in place encryption
software. I'll be happy to discuss this with anyone (not that I have a clue)
directly.

Regards, Ethan
Newsgroups: sci.crypt
From: phr@telebit.com (Paul Rubin)
Subject: Re: Triple DES
Organization: Telebit Corporation; Sunnyvale, CA, USA
	<1992Nov20.094321.1@zodiac.rutgers.edu>
Date: 20 Nov 92 18:39:32

    A pure chosen-plaintext attack against DES would not move directly
    to double DES.  But that only says something about ONE PARTICULAR
    ATTACK; it says nothing about the inherent strength of the
    cryptosystem.

It's worse than this.  We don't even know that double DES is much 
stronger than single DES against exhaustive search.  (We know it's
at least a little bit stronger).

We know that DES is not a group; however, we don't know that DES
doesn't *contain* a large group.  It might be that only a few of
the possible DES keys generate elements outside of DES.  Anyone
know better?
Newsgroups: sci.crypt
From: sloan@cis.uab.edu (Kenneth Sloan)
Subject: Re: Attack Methods
Organization: CIS, University of Alabama at Birmingham
Date: Wed, 18 Nov 1992 19:05:13 GMT

In article <1992Nov18.134243.24089@qiclab.scn.rain.com> Leonard.Erickson@f51.n105.z1.fidonet.org writes:
>jdailey@dadd.ti.com (Jim Dailey) writes:
>
>>So what are some of the methods used to attack an encrypted text, when the
>>encryption method is unknown?
>
>First you run frequency tests. This will tell you *immediately*
>if a "reasonably sized" text was encrypted via *any* character
>transposition cipher. 

This thread is at about my speed - so I'll toss in a question.  I'm sure
that this is hopelessly naive - but I hope someone will tolerate the
question long enough to answer it.

Suppose that I have a character transposition cipher.  Will the
following scheme make it appreciably stronger (or weaker?):

To encrypt:

    0) compose the message
    1) add (to both the front, and the back) additional characters,
       chosen to produce a flat histogram.  Pseudo-randomize, as needed.
       Perhaps also pad to a standard size block?
       Perhaps randomize the positioning of the message within the block? 
       Perhaps break the original message into bite-sized pieces and
       include additional material between bites as well as at the
       beginning and end?
    2) apply the character transposition cipher.

to decrypt:

    0) reverse the transposition
    1) rely on the reader (either human or otherwise) to recognize
       the start and end of the original message (or the multiple starts
       and ends of message bites).

One weakness which springs to mind is that absolutely flattening the
character histogram may cause an unacceptable increase in the size of
the transmitted message.  Perhaps this is what was intended by the
qualification ``"reasonably sized"'' above?

A (probably foolish) complication which springs to mind is to:

    *restrict words in the message to a pre-defined lexicon
    *break up the original message on word boundaries
    *add "histogram-flattening" characters between words (instead of
     whitespace?) 
    *ensure that no "allowed words" are generated accidently
    *have the decrypting process find the "allowed words" among
     the random garbage (after reversing the transposition)

Assuming that the message has been appropriately un-transposed, it
should be simple enough for the intended receiver to find the allowed
words, and hence the original message.  The question is: does this give
the enemy too large a lever on cracking the transposition cipher?





-- 
Kenneth Sloan                   Computer and Information Sciences
sloan@cis.uab.edu               University of Alabama at Birmingham
(205) 934-2213                  115A Campbell Hall, UAB Station 
(205) 934-5473 FAX              Birmingham, AL 35294-1170
Newsgroups: sci.crypt
Subject: Re: Registering "Assault Keys"
From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
Date: 17 Nov 92 19:47:24 GMT
 <lg5gu8INN1m9@exodus.Eng.Sun.COM> <1992Nov13.190219.24894@dg-rtp.dg.com>
Organization: Beckman Instruments, Inc.

In <1992Nov13.190219.24894@dg-rtp.dg.com> meyers@leonardo.rtp.dg.com (Bill Meyers) writes:

>In article <lg5gu8INN1m9@exodus.Eng.Sun.COM> williamt@athena.Eng.sun.com (Dances with Drums) writes:
>[ ... ]
>>	As for registering keys...why do law enforcement officials think
>>they have a right to know what I am saying to another person.  It seems
>>like this is an infringement on *freedom* of expression -- if my expression
>>to another person *must* be subject to monitoring, is it really free?


>Well, I've had a closer look --

>        AMENDMENT I
>        Congress shall make no law respecting an establishment
>        of religion, or prohibiting the free exercise thereof;
>        or abridging the freedom of speech, or of the press;  [etc.]
>                         ^^^^^^^ ^^ ^^^^^^
>-- and it's perfectly clear that what they _meant_ was your freedom
>to make a speech, e.g., when trying to get elected to public office.
>There's nothing in there about other modes of communication, and
>_certainly_ nothing about keeping secrets from the Government!  BTW,
>the Amendment only limits Congress.  Individual states may further
>limit your means of running for public office, and many of them do.

Other posts have commented on what "freedom of speech" means; I would like
to add that the 14th Amendment has been considered to have extended the
First Amendment to apply to State governments, as well; not only the
Federal government.

>--------
>This brief entertainment has been brought to you on behalf
>of the Second-Amendment-is-about-the-National-Guard twits.   :-)
--
Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
My opinions are my own, and do not represent those of my employer.
My interaction with our news system is unstable; please mail anything important.
Newsgroups: sci.crypt
From: keith@decuac.dec.com (Keith Fisher)
Subject: popcount
Reply-To: gertler@decuac.dec.com (Dave Gertler)
Organization: Digital Equipment Corp., Washington ULTRIX Resource Center
Date: Fri, 20 Nov 1992 17:52:52 GMT

Does anyone recall a discussion concerning popcount, parity bit matrix
multiply & other special instructions?  I've been told that there was
a dialog concerning how these instructions were being used in certain
applications.  Can someone forward me a copy or give me a pointer to
this information?  Thanks.

gertler@hobble.dco.dec.com
Xref: sparky sci.crypt:5155 alt.privacy:2391 talk.politics.guns:24357