Cryptography-Digest Digest #903, Volume #8 Thu, 14 Jan 99 01:13:03 EST
Contents:
Re: What is left to invent? (Alan Braggins)
Re: On the Generation of Pseudo-OTP (John Nagle)
Re: On the Generation of Pseudo-OTP (John Nagle)
On the utility of using Nulls (wtshaw)
RSAREF - Why? jb (Jason Buchanan)
Re: On the Generation of Pseudo-OTP (John Nagle)
Re: Encrypted WordPerfect 5.1-files (DOS) (JPeschel)
Re: Birthday Attack calculations. (Fred Van Andel)
Re: For Matt (Re: coNP=NP Made Easier?) ([EMAIL PROTECTED])
Re: Sarah Flannery and the "Cayley-Purser" Algorithm ("Gabriel Knoy")
Chaitin Omega (Darren New)
Re: For Matt (Re: coNP=NP Made Easier?) (Matt Brubeck)
Re: Session key establishment protocol with symmetric ciphers (Shawn Willden)
Re: coNP=NP Made Easier? (Matt Brubeck)
----------------------------------------------------------------------------
From: Alan Braggins <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: 13 Jan 1999 10:57:07 +0000
[EMAIL PROTECTED] (Jayant Shukla) writes:
> >(For those out there unfamiliar with the term, a random oracle
> >is a mythical device which when presented with a question it
> >gives a truly random answer, with the proviso that if the question
> >has been asked before it gives the same answer as last time.
>
> If I take a rendom data string "S" and XOR it with a data
> string "D", I get a completely random answer and the answer will
> always be the same for a given that data string provided you do not
> change "S". So, is this a rendom Oracle?
No. If you don't change S, then if you change one bit of "D", you
can predict that the result will be the previous answer with one
bit changed. That's not a completely random answer.
------------------------------
From: [EMAIL PROTECTED] (John Nagle)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 14 Jan 1999 03:10:31 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> writes:
>So there is not of much practical value to insist on perfect security,
>on obtaining (ideal) OTP. And one can, for example, consider the
>utility of the non-perfect 'intended approximation to an ideal OTP'.
No. It's quite feasible to generate truly random numbers, using
some source of noise driven by quantum effects like radioactive decay
or thermal noise. That's the only proper way to generate one-time
pad keying material, and that's how it's been done since the 1950s.
Pure XOR is safe only with truly random keying material.
Otherwise, it's a weak cypher, and any nonrandomness in the keying
material can potentially be exploited. Historically, it has been, too.
Witness Venona, etc. Even using the same keying material twice is
deadly - two English texts XORed together can be extracted easily.
As soon as you start talking about psuedo-random keystreams,
you're usually talking about some means of inflating a small initial
key into a long keystream. You now have a cryptosystem with a small
key and a generation algorithm. That is nothing like a one-time pad.
The big trouble with one-time pads is that not only do you need
large amounts of keying material, you need unique keying material
for each pair of stations that communicate. This tends to restrict
its use to hierarchical situations like embassy-to-capital, spy
to HQ, and military unit to higher headquarters where the central
station is highly secure.
John Nagle
------------------------------
From: [EMAIL PROTECTED] (John Nagle)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 14 Jan 1999 03:13:15 GMT
"Tony T. Warnock" <[EMAIL PROTECTED]> writes:
>Peter Wright describes another method of breaking a OTP. MI6 would just break into a
>spy's
>flat and photograph the pad. Details in "Spycatcher."
This is why OTP keying material needs to be stored on a medium that
is readable only once. Special paper tape devices were once used
in this way; I don't know what's being used now.
John Nagle
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: On the utility of using Nulls
Date: Wed, 13 Jan 1999 19:16:35 -0600
With apologies to Terry Ritter about writing off the use of nulls to
improve security, I did avail myself of them in a current cipher
implementation just completed. In particular, output is in base 22, using
any 22 characters of the alphabet. Experience can prove that you are in a
rut, or at least getting prejudiced against that you have not fully
explored.
To disguise the ciphertext from something using a standard alphabet, the
unused four characters are scattered about within the groups. This is key
dependent, so as too make it still more difficult, the nulls can be
different.
As an part of the function, also used in decryption input, unacceptable
characters, other then the essential 22 used in encryption, are stripped
away before the nulls are added. If not happy with the pattern of nulls,
simply run it again. With a few tests, I should be able to properly set
the null frequencies to somewhat match usual ciphertext letter
frequencies.
As an example of the process, consider these lines as it are stripped of
the null characters and resalted with J, Q, W, and X, the defaults in the
program:
(asane ample qofth eproc esscw onsid erwtx hesel inesa sxita xrxes trjip
pedof thejn ullch aract ersan jdres alted ithan dthed efaul tsint hqepr
ogram)
(ajsan eampl eofth epqro cxess conws idjer these qline sajsi tares jtrip
pxejd jofth enull cjhar acter saqnd resal tedit handt hedef aults inthe
progr ajm)
Note that the passages may vary in length, as it is possible that
sequential nulls will be inserted. A different key might have different
nulls. Normally, this would be done to ciphertext rather than text were
spaces are not important at all. As this process screws up normal text
pretty badly, think of the difficulty of attacking nulled ciphertexts.
--
If government can make someone answer a question as they want him to, they can make
him lie, then, punish him for not telling the truth. Such an outrage constitutes
entrapment.
------------------------------
From: Jason Buchanan <[EMAIL PROTECTED]>
Subject: RSAREF - Why? jb
Date: Thu, 14 Jan 1999 02:48:24 GMT
RSAREF? Why? What does it do for me other than make me legal in the US?
------------------------------
From: [EMAIL PROTECTED] (John Nagle)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 14 Jan 1999 03:27:23 GMT
[EMAIL PROTECTED] (R. Knauer) writes:
>> http://www.io.com/~ritter/RES/RNGMACH.HTM
>Why didn't someone tell me about this before!
I'm not quite happy with the way most people use quantum sources
to generate "random" bits. See
http://www.fourmilab.ch/hotbits/how.html
for a radiation-driven random number generator that's free of
some of the problems mentioned in the previous work.
John Nagle
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Encrypted WordPerfect 5.1-files (DOS)
Date: 14 Jan 1999 03:40:09 GMT
> [EMAIL PROTECTED] writes:
>AccessData Corp. can help you. They specialize in password recovery. Check
>out their web site at http://www.accessdata.com.
True -- Thompson's password recovery tools are very good.
The ones on my site, though, are free, and the original poster
may want to try them first.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Fred Van Andel)
Subject: Re: Birthday Attack calculations.
Date: Thu, 14 Jan 1999 04:37:24 GMT
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] (Terry Ritter) wrote:
>>For a value of 1,000,000, i is 1178.
>
>Which seems to compare rather well to the value 1177.9 computed from
>my formula in the earlier posting:
Why do you think I chose the number 1,000,000. Its a good idea to
check your answers before making a fool of yourself in front of the
multitude.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math,comp.theory
Subject: Re: For Matt (Re: coNP=NP Made Easier?)
Date: Thu, 14 Jan 1999 00:07:10 -0500
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Dear Matt,
>
> Main focus: If NDTM is realizable, coNP=NP.
I don't really know if I want to respond in this thread or not, but I
will because the addressee of this message shares my first name and the
question is interesting:
What do you mean by "If NDTM is realizable?".
Let's say we had a "real" NDTM, and I give it an NP-complete problem -- a
3-SAT instance, say, to solve. What are the possible outcomes?
I'm baiting you with this question, and that's somewhat cheap, so I'll
give you my answer first:
It's easy to build an NDTM -- all you need is a source of non-
deterministically random bits. You can get them over the web from
HotBits at Fourmilab. When you feed a 3-SAT instance to the NDTM, it
uses these bits to try to guess a satsifying instance.
The answer, which is guaranteed to come in polynomial time, will be
either "Yes, this instance is satisfiable", or "Perhaps -- this instance
might be satisfiable, but I've failed to prove it".
If the instance is satisfiable, then there is a _real_ possibility of the
NDTM returning "Yes", and if you subscribe to the Evrett interpretation
of QM, it will return "Yes" in some parallel world.
If the instance is unsatisfiable, then the answer will definately be
"Perhaps".
This is one of the hard things to understand about an NDTM -- it never
definitively says "No", and so there remains the question about whether
NP=coNP.
If you have in mind some sort of NDTM that _could_ actually say "No",
then the ability to build such a machine would indeed imply that NP=coNP,
but this is not the type of machine that theorists mean when they say
"NDTM".
------------------------------
Reply-To: "Gabriel Knoy" <[EMAIL PROTECTED]>
From: "Gabriel Knoy" <[EMAIL PROTECTED]>
Subject: Re: Sarah Flannery and the "Cayley-Purser" Algorithm
Date: Thu, 14 Jan 1999 05:20:04 GMT
> Miss Flannery, 16, from Blarney, Co Cork, used matrices to
> formulate an alternative to RSA, the current data protection
> code, devised by three students at the Massachusetts
> Institute of Technology in 1977. The result is an algorithm, a
> mathematical blueprint, that is far faster than the RSA and
> equally secure.
Now, I may be way off target here, as I'm pretty new to this area
of interest (I only got The Book 4 weeks ago), but how secure can it be?
Take a very simplistic brute force attack, where an attempt to decrypt
the message is made using every key in the known key space. I am
assuming that her decryption method is as comparably faster than
RSA's as her encryption method is (and it's a big assumption, I guess).
Since her algorithm (from what little I've read on the BBC page) is
based on matrix math, which is (i think?) computationally simpler
than the math used in RSA's encryption, that would mean that more
keys could be tested in a given period of time than could be if RSA
were used. Additionally, it would probablly be cheaper to build a
dedicated cracking machine (like the EFF built to crack DES),
because I would suppose that the chips needed to do the matrix math
might be less complex.
That's my take on this, please don;t hesitate to tell me if I'm barking up
the wrong tree :)
Gabriel Knoy
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Chaitin Omega
Date: Thu, 14 Jan 1999 05:24:46 GMT
I'm looking at http://www.cs.auckland.ac.nz/CDMTCS/chaitin/belgium2.html
In that lecture, Chaitin talks about Omega, the halting probability. He
says "You have to have a probability associated with each computer
program in order to talk about what is the probability that a computer
program will halt." (Makes sense so far) He continues "One chooses each
bit of the computer program by tossing a fair coin, so that an N-bit
program will have probability 2^-N." Now, which is "the" computer
program? First he talks about "each" computer program, then he talks
about "the" computer program being chosen. He goes on to say "Once
you've chosen the probability measure this way and you choose your
general-purpose computer this will define a specific halting
probability." I'm not following what he's trying to say.
Is he saying that Omega is the probability that any selected program N
bits long will halt? I don't follow why he needs to explain how to
create a random program if he's trying to talk about "one looks at the
ensemble of all possible computer programs."
Perhaps someone here could clarify what Omega is the probability of?
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: [EMAIL PROTECTED] (Matt Brubeck)
Crossposted-To: sci.math,comp.theory
Subject: Re: For Matt (Re: coNP=NP Made Easier?)
Date: Wed, 13 Jan 1999 21:46:55 -0800
[EMAIL PROTECTED] wrote:
> Main focus: If NDTM is realizable, coNP=NP.
This is FALSE, regardless of what you mean by "realizable."
coNP may equal NP, but this is not implied by NDTMs being "real." Read on...
> First, the claim or proof of P!=NP. I believe,
> you know that you can not provide a proof of it.
I have not claimed that P != NP. I do not know whether P ?= NP.
I cannot prove that P != NP. I cannot prove that P = NP. I do not think
that anyone has seriously claimed that P = NP or that P != NP.
P ?= NP is a famous undecided problem. No one knows the answer.
> I repeat here. Thinking about such issues can be in a variety
>of ways. Adopting the notion of P as being defined by the exact
>words in M. et al.'s is just one of such ways.
No. P has a very firm definition in complexity theory. "The Handbook of
Cryptographic Analysis" uses P in the same way that other texts and papers
use it. However, they are slightly imprecise in the wording of their
definition.
M. et al do not mention the mechanism by which "polynomial time" is
defined. This mechanism is the deterministic turing machine.
If you are not familiar with the correct definitions of P and NP, you have
clearly not studied complexity very much, or read many of the important
results in the field.
> I NEVER say it is the only way. I say it is a _consistent_ way.
"Consistent" isn't what's important. "P" has an accepted meaning in
complexity theory. You are not using that accepted meaning.
If you use different definitions from everybody else, you will get
different results.
> You did not quote the def of P from the book you
> said you got the def for NP.
I presented the entry for NP from the _FOLDOC_ dictionary, which included
the definition of P.
>I believe in
>that book, the def is what you and Planar have. Whatever is true is.
>Whatever makes sense does. It does not matter if it is put in a
>volume.
What does matter is that "P" has an accepted meaning in complexity theory.
Ilias, Planar, myself, and other posters have used (and explained) the
accepted meaning.
> Secondly, about NDTM. I do not think you have given a clear
> picture of it. There are a couple of things to talk about,
> and I give it a try.
Here's a clear picture of an NDTM, again from _FOLDOC_ (Denis Howe, 1993):
Nondeterministic Turing Machine:
A normal (deterministic) Turing Machine that has a "guessing
head" - a write-only head that writes a guess at a solution
on the tape first, based on some arbitrary internal algorithm.
The regular Turing Machine then runs and returns "yes" or
"no" to indicate whether the solution is correct.
A nondeterministic Turing Machine can solve nondeterministic
polynomial time computational decision problems in a number
of steps that is a polynomial function of the size of the input
You will get an equivalent definition from any basic text on complexity theory.
Note that NTIME(x), the running time of a nondeterministic turing machine
x, refers to the time that it takes for the deterministic "checking" phase
mentioned in the definition.
> The difference between conceptual, theoretical and hypothetical.
>If one has a well-defined plan for implementing a set of ER diagrams,
>he can implement it on a digital computer. I doubt if anybody doubts
>the possibility of such an implementation. Nobody perhaps will doubt
>the theory behind and none will say: show me a database with 2^100000
>records (loaded) and then I believe the theory behind. I do not think
>anybody can be that smart to point out in that way the flaw of the
>theory behind. Everybody is clear what is truth and what is a concept.
> Now if I have a hypothesized design for which I can not show a single
> realization, I do not think anybody here would send he who wants to
> see a concrete implementation of it to jail. It is NOT illegal to
> wonder about the existence of such a thing. After all, the hypothesis
> can turn out to be false.
Planar provided a very good example of a useful NDTM.
> Tell the readers and the world what the difference between
> NDTM and DTM is in terms of concept, theory and hypothesis.
The important difference between a DTM and an NDTM is this:
Given a DTM which solves a problem in polynomial time, it is always easy
to implement an algorithm on a real computer which solves the same problem
in polynomial time.
However, given an NDTM which solves a problem in polynomial time, it may
be impossible to implement an algorithm on a real computer which solves
the same problem in polynomial time.
This is because the meaning of "solve" is different when talking about
nondeterministic algorithms. This has been explained to you in many
different ways.
To say that a nondeterministic algorithm "solves" a problem with a certain
running time means that a certain phase of that algorithm takes polynomial
time. However, because this phase may have to be run polynomially or
exponentially many times, a nondeterministic polynomial algorithm may not
actually run in polynomial time.
> You mentioned the simulation of NDTM in 'like' manner (or you have
>a better word for simulation?). I do not know how to say better. I
>am not used to bluffing. But let me say this. If NDTM can NOT solve
>NP problems in P time, they can be of both the greatest interest and
>of no interest at all.
NDTMs solve NP problems in polynomial time. This is the definition of NP
("nondeterministic polynomial time").
However, this does not mean that they are solving in P time. "P" refers
only to deterministic polynomial time.
> They then, I believe, exist. You need not simulate.
No Turing machine actually "exists" in the sense that it can be built,
physically, in real life. For one thing, part of the definition of the TM
is that it has infinite memory. This is why I have called turing machines
"theoretical concepts."
However, just because it does not physically exist (this is what I meant
by "theoretical") doesn't mean that it is not well-defined.
Both NDTMs and DTMs "exist," but only on paper. These conceptual Turing
machines can be used to create algorithms for real computers. However, in
the case of the NDTM, these deterministic algorithms do not have the same
order of growth as their nondeterministic counterparts. TIME(x) does not
mean the same thing as NTIME(x).
> There is a hoard of issues besides. For example, in the sense of
> those, what is a NDTM useful for? (A human is useful for a lot of
> things and can solve SS :)). If NDTM's can not (and if actually
> nothing can) solve NP problems in P time, what is this NP thing?
"NP" refers to a NON-DETERMINISTIC complexity class.
Nondeterministic behavior is DIFFERENT from deterministic behavior.
Several people have tried to explain the difference to you. Rather than
repeat myself, I will advise you to read some introductory books on
complexity, or take a basic undergraduate class, or talk to a computer
science professor.
"What is a NDTM useful for?" An NDTM which solves X in polynomial time is
useful for writing a program to solve X in exponential time.
Unfortunately, it is not useful for writing a program to solve X in
polynomial time.
> Dear Matt, it is ok to adopt your notion of P (by DTM). I have
> no problem with that. But if you call it a complexity class, I
> need to make sure polynomial is polynomial and polynomial
> complexity is polynomial complexity and polynomial complexity is
> as complex as polynomial complexity (in complexity theory), AND
> the complexity class of P contains only polynomial complexity
> problems and contains ALL such problems.
P contains all DETERMINISTIC polynomial complexity problems.
P contains only DETERMINISTIC polynomial complexity problems.
NODETERMINISTIC polynomial complexity problems are not necessarily in P.
One thing that may be confusing you is that when people are talking about
deterministic mechanisms or complexity, this is often implied. For
example, when a paper refers to a turing machine, it means specifically a
deterministic turing machine. When a paper talks about "polynomial time,"
it generally means only deterministic polynomial time. It only includes
nondeterministic methods if it explicitly mentions them. "Deterministic"
is implied. I made it explicit above because you seemed not to realise
this.
> I repeat (how many times I did?): if NDTM is realizable, coNP=NP.
I disagree with your assertion.
You have not shown that, given an NP-time algorithm for X, you can
construct an NP-time algorithm for ~X.
Your proof was flawed because it used nondeterministic algorithms as
though they were deterministic.
Note that I don't know whether coNP ?= NP. This may be true; it may not.
I'm just saying that you have failed to show that it is true, and that
whether it is true has nothing to do with whether an NTDM is "realizable."
>You agree or you do not agree or you do not know whether to or not
>to? If you do not, can you give a mechanism that solves SS
>(positively) in P time?
No. But I can give a mechanism that solves it in NP time. Planar has
already presented such a mechanism, so I won't repeat it here.
The mechanism Mr. Planar presented is an nondeterministic turing machine
which solves SS in polynomial time.
This means that it is an NP-time mechanism.
It does NOT mean that it is a P-time mechanism.
------------------------------
Date: Wed, 13 Jan 1999 21:43:25 -0700
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Session key establishment protocol with symmetric ciphers
[EMAIL PROTECTED] wrote:
> Shawn Willden ([EMAIL PROTECTED]) wrote:
> : > >Suppose Alice and Bob share a secret key K and wish to
> : > >establish a session key to be used for encrypting
> : > >messages.. Alice generates a random R_A and Bob generates a
> : > >random R_B. Alice sends R_A to Bob and Bob sends R_B to
> : > >Alice, then both compute:
> : > >
> : > > K_S = E( F(R_A, R_B), K)
> : > >
> : > >to get the session key K_S.
>
> Usually, though, K is called a key-encrypting-key, and a protocol of this
> nature is not used because it is far more straightforward to have K_S
> equal to either E(R_A,K) or E(R_B,K), depending on whether it is A or B
> sending the message.
Right, but that's vulnerable to replay attacks, unless the
contents of the message protect against them, or unless the
participants keep a record of the values that have been used
(or the values are timestamps, counters or somesuch -- all
of which require additional precautions).
> This protocol is not insecure. Some people might have a problem with
> dignifying it by the name 'protocol', but you haven't made an error here.
Okay, I think I'll call it a 'procedure', then.
Shawn.
------------------------------
From: [EMAIL PROTECTED] (Matt Brubeck)
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Wed, 13 Jan 1999 22:03:48 -0800
<[EMAIL PROTECTED]> wrote:
>> Mr. McCarty pointed out that we can implement NDTM-like behavior on real
> Wonder in what sense is this 'like'.
It means that we can implement algorithms based on NDTMs, but with two
differences:
1) They run slower than the NDTM would.
2) The size of their memory is finite.
> Even though you copied the def., how would I know what is you
> understanding of it? I asked and ask you to give a well-defined
> behaviour of such a NDTM. Can you do it? Can you show us, in
> just hypothetical but well-defined and unambiguous way, how
> such an NDTM solves SS positively in P time?
If you didn't understand the table that Planar posted, you are clearly
unfamiliar with the concept of NDTMs, and I question your competence to
even understand any answers we can provide to your questions. Go find a
basic complexity textbook and read it very carefully before asking us to
spend more time answering your questions.
------------------------------
** 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
******************************
