Cryptography-Digest Digest #880, Volume #8 Mon, 11 Jan 99 03:13:04 EST
Contents:
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: coNP=NP Made Easier? (rosi)
Re: Help (How long can a post be seen?) ([EMAIL PROTECTED])
Re: coNP=NP Made Easier? (rosi)
Re: Security through obscurity in the smartcard world (John Savard)
----------------------------------------------------------------------------
Date: Sun, 10 Jan 1999 22:08:29 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> On Sun, 10 Jan 1999 09:32:43 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >Actually, I think this is erroneous.
>
> Nope, it is not.
>
> >The name OneTimePad specifies a single-use key.
>
> That is not all it specifies. It specifies a True Random Number as the
> pad. Otherwise it would not be proveably secure.
>
> >The best possible key is one in which each key element (char
> >or bit) is independent of the others.
>
> The best possible key is one generated by a TRNG, which is a physical
> device capable of outputting all possible sequences of a given finite
> length equiprobably. That includes outputting sequences that have bits
> which are not "independent" of one another, such as in the sequence
> 111...1.
The preceeding statement is sense-free. One cannot infer independence by looking at
the data. One can only fail to find dependence. A sequence of 6 one bits is going
to appear in more than 1% of the six-bit samples from a true random bit generator.
This does not mean the bits are dependent.
> >But having typists pound on keyboards,
> >as the Russians did, does not produce independent key elements. They had a
> >True-OTP until they started reusing keys, but their key quality was nowhere
> >near perfect.
>
> The Russians *thought* they had a random source, and apparently they
> had something that was very close since Venona required the reuse of
> pads to crack their ciphers.
Right. The quality of the key was certinaly "good enough" to qualify that system
and a true OTP in spite of what we would judge as low-quality key material.
> >Thus I believe that a true OTP is one with a single-use key. The quality of
> >the key does not turn a single-use key system into an inferior stream cipher.
> >It is still a true OTP.
>
> Nope. An OTP uses a random pad, otherwise it would not be proveably
> secure.
>
> >It is not that simple. The key phrases you used was "all one needs to do is
> >uncompress it" and "it should be possible to achieve 1 bit of entropy per bit
> >of compressed data." Inside a compressed archive there exists all kinds of
> >structure to guide the decompression process. If you strip out only the
> >compressed text you will not be able to uncompress it without some loss of
> >fidelity.
>
> I suppose that anything that does not result in one bit output would
> fall under that critique. After all, a hash that gives one bit output
> (e.g., parity) has no information whatsoever in it regarding the
> original text.
>
> >I'm not sure 100% entropy density is possible in a lossless system.
>
> You mean strong mixing (see RFC1750) could not increase entropy to
> 100%?
No. I mean a compression/decompression system. Such systems are lossless, and so I
would speculate that they cannot reach 100% information density.
A hash is not lossless. A hash is lossy. E.g., you cannot recreate the source from
the hash value. It should be possible to reach 100% information density with a
hash.
> >Note that
> >a hash is a lossy system to it is easily possible to get 100% entropy density.
> >In fact the statement that there is irreducible structure to text implies that
> >100% entropy density is literally impossible.
>
> Did you mean "irreducible" or its opposite?
I mean irreducible. I was paraphrasing your contention that text cannot be used as
a source of good key material because it always contains correlations thatcannot be
reduced.
> >Now which way do you want to have it?
>
> I would like it to be fundamentally correct, if such a thing is
> possible. It may not be possible if some of the concepts of Greg
> Chaitin are universally applicable to number theory.
>
> >Here you have to provide an example. The claim that a hash contains structure
> >is identical to the claim that the entropy density is less than 100%. Can you
> >show any system with 100% entropy density that is not crypto-secure?
>
> I did not make the original assertion about hash functions, someone
> else who represented himself as an expert cryptographer on sci.crypt
> did. And no one else bothered to challenge him, so I accepted it
> tentatively.
>
> If you can show that a certain class of hash functions are proveably
> secure, please do so.
>
> >I believe that you cannot. 100% entropy density means that the bits are
> >unrelated. Literally unpredictable. I suspect that criticism you got in
> >previous discussions, which I have not reviewed, was based on the claim that
> >you had failed to reach 100% entropy density, rather than the claim that 100%
> >entropy density may be inadequate.
>
> Nope, it was a simple assertion that hash functions could not be
> considered to be cryptographically secure because they are based on
> internal states which can be reproduced.
OK, let's clarify a potential point of confusion. We can discuss the idea of an
algorithmic source of entropy, such as a PRNG, LFSR, etc. Alternatively we can
discuss algorithmic entropy management; i.e., a deterministic mechanism that accepts
some low grade (density) entropy source and produces some high grade (100% density)
entropy representation.
If we are debating the former, we're wasting a lot of time. The very concept is
flawed because the determiism encodes predictability into the output. ANY form of
preditability implies less than 100% entropy density.
If we are debating the latter, let's be specific. It should be possible to define a
deterministic algorithm that accepts 3 inputs:
1. some bit stream
2. a number describing the assumed entropy density of the input stream
3, a number describing the desired entropy density of the output stream
algorithm produces an output stream of the desired entropy density.
I believe this is possible. Do you disagree?
> BTW, what algorithmic method do you propose, besides hash functions,
> to produce 100% entropy from text?
I suspect we'll get to that, but let's set the parameters first.
> >Well, we have no idea whether there are any correlations. This is a far cry
> >from the claim that we can prove that there are none.
>
> The claim is shorthand for: "At the present level of theoretical
> understanding...". Of course, if you believe in Hidden Variables, then
> there are correlations in all quantum processes.
>
> But for today, QM maintains that there are indeed random physical
> processes. For example, the wavefunction for a single particle in free
> space is exp(i(k.r-wt)), where the dot is to be taken as the vector
> dot product operator, k is the wave vector, and w is the angular
> frequency. The latter are related to physical quantities as p=k_bar k
> and E=h_bar w, h_bar being Planck's constant divided by 2 pi. The
> variables r and t are the vector position and time respectively.
>
> If you take the conjugate square of that wafefunction you get a
> constant which says that the probability for finding the particle at a
> particular place at a particular time is the same for all places and
> times.
>
> That means that the particle is capable of existing at any place at
> any time equiprobably. That latter statement is very much the same as
> the the definition of a TRNG. There are quantum mechanical processes
> that are completely random in the same sense as crypto-grade
> randomness.
>
> >It would be nice to force the universe to match our theories, but it just ain't
> >so.
>
> But they are the best we have to go on. If man waited around for the
> Perfect Circle to manifest itself in the physical world, we would
> still be living in caves.
>
> >There is a class of dual emission events in which two high energy
> >particles are emitted in exactly opposite directions. The properties of the
> >particles are related. If you measure one particle its wave function
> >collapses, and so does the other particle!. The interesting thing about this
> >is that the collapse of the second particle's wave function occurs at the same
> >time as that of the first particle. No matter how far apart they are. This
> >appears to violate the speed limit laws.
>
> That is the experiment of Alain Aspect that I was describing earlier.
> It is tied up intimately with Bell's Theorem regarding non-locality of
> hidden variable theories. Best leave that stuff to quantum
> cryptography when it emerges on the scene. Classical crypto is enough
> for us mere mortals right now.
>
> >The technical term for such correlation among particles is entanglement.
> >Entangled particles have correlated behavior. Yet entanglement is created
> >everytime a pair of particles interact. So (I speculate), in theory the entire
> >cosmos may consist of heavily entangled particles. Thus there is room for an
> >arbitrarily large amount of correlation at the quantum level.
>
> I only claimed that there are *some* processes in QM that are
> completely random.
>
> >We just can't prove it or disprove it. Yet.
>
> That is why it is best left to speculation and not brought into
> classical crypto.
>
> >> There is an area where such an apparent violation appear to be
> >> involved with non-local phenomena such as in the experiemnts of Alain
> >> Aspect. But that is still quite contoversial as it is mixed in with
> >> Bell's Theorem and Hidden Variables.
>
> >I do not recognize these references, but that is just my ignorance.
>
> Regardless, you do know something about them as is evidenced by your
> comments above. They are described in Roger Penrose's recent two books
> on physics, to name one reference.
>
> >Raw text sure. But not in text that has been hased to 100% entroy density. By
> >definition, the bits of the hash are independent.
>
> Again, I ask you to provide a class of hash functions which will
> proveably produce 100% entropy from any input.
Here's a key assumption: "from any input". Clearly that's asking a bit much. It
would require an arbitrarily large amount of entropy from the input string "".
> >A perfect OTP used correctly is provably not subject to analysis. This is a
> >much weaker condition than true provable security.
>
> I agree with the first statement, but I do not understand the second
> one. Proveable security is limited to analysis, and does not involve
> protocol. In terms of protocol the OTP system sucks big time. That is
> the reason for this thread - to find a way that gets around the
> problems with key management with the standard OTP system.
>
> >An imperfect OTP (with lousy key quality such as the Russians generated) is
> >still an OTP. It is theoretically breakable.
>
> Then it is not really an OTP, it is just another stream cipher. The
> OTP system is proveably secure.
>
> >An incorrectly used OTP (key recycling) is certainly breakable.
>
> Then it is not an OTP.
>
> >Of course natural text has correlations. Preditable bits. Less than 100%
> >entropy density. However, raw natural text does contain information.
> >Entropy. Unpredictable bits. It is certainly possible to sample text to
> >extract it and use it as a key for an OTP or other cipher. The only hard part
> >about it is judging how much entropy exists in the original text.
>
> I never said otherwise.
>
> In fact I have said (a year ago and repeated here) that one might be
> able to build a secure stream cipher from the least signigicant bits
> of text, after antiskewing and decorrelation. The hangup was on the
> proposed method of decorrelation. Strong mixing of different streams,
> such as recommended in RFC1750 (which includes hashing), is supposed
> to produce a correlation-free stream, but others criticized that
> method and I could not argue against them. Perhaps you are in a
> position to clarify this sticking point.
Rats. I cannot possible debate arguments I have not encountered. I've got to
travel most of this week, so I can't go spelunking in news archives until next week
at the earliest. I'll see how far I get with it.
> >If you can specify the required theoretical density enhancement I believe I can
> >specify a theoretical procedure to realize it.
>
> The OTP system demands that the pad be constructed from a TRNG which
> is a physical device capable of outputting all possible sequences of a
> given finite length equiprobably. If you can come up with a procedure
> that does the same thing in a different manner, then you have come up
> with something that can be used as a substitue for a physical TRNG in
> the OTP system.
>
> We wait with great anticipation, albeit with a proper amount of
> skepticism.
>
> >Well, Newton had a hand in those debates. A nefarious one. He and Leibnitz
> >(sp?) both claimed to have invented the fundamental concepts of calculus.
>
> And both did. That has happened before in the history of science and
> mathematics.
>
> >While Leibnitz had precedence (as seen from history; at the time comm delays
> >provided enough skew to cloud the issue), Newton had a bully pulpit to
> >strengthen his claim.
>
> Newton was a fierce infighter for the glory of fundamental truth
> because he sincerely believed that he was doing the work of God. He
> could not accept a lesser position in the discovery of divine truth. A
> lesser position in the divine plan he believed he was a major part of
> would have crushed his brilliant mind beyond repair.
>
> >He won the PR war. Later in life he stated that he greatly enjoyed "breaking
> >Leibnitz's heart". Feet of clay...
>
> He also tangled with the Englishman Robert Hooke and some other
> geniuses on the continent. To Newton, "Not Invented Here" was
> theologically impossible.
>
> Bob Knauer
>
> "We hold that each man is the best judge of his own interest."
> --John Adams
------------------------------
From: rosi <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Sun, 10 Jan 1999 18:07:49 -0800
Bryan G. Olson wrote:
>
> rosi wrote:
>
> > Maybe, to some other people when NDTM is real, it is trivial
> > that coNP=NP. Once one sees it, it is no longer too difficult. Once one
> > is given a concrete construction, it will not be too difficult for one
> > to see.
>
> Rosi, at your request I copied the definition of a NDTM
> from a text by Lewis and Papadimitriou. It's a four-tuple
> of alphabet, states, transitions and start state. The question
> of whether a NDTM can accept some language is the question of
> whether such a 4-tuple exists.
Believe last sentence is a typo. Do not think I can understand it.
I think I thanked you for the copying. Did I?
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?
>
> Is negative four real? Can you show me -4 of something? I
> don't mean something theoretical like a debt being negative
> money or a step to the left being a negative step to the
> right; I mean -4 real things.
>
> The existence of mathematical entities follows from their
> definitions, not from our ability to manufacture and exhibit
Not sure. How do we know it is well-define?
Not sure. Read Turing's Thesis. Or you can refute that?
> physical objects.
>
> --Bryan
Dear Bryan,
I never asked for a real NDTM. I said I could accept an assumption.
I repeat: If NDTM is real, coNP=NP. If NDTM is not real, there is no
NP which is classified by NDTM. (Please do not get into certificates,
unless you can show us how that can be complexity measure in the
absence of NDTM. I do not mean that you can not classify using
the concept of certificates. I mean such classifications can not be
complexity classifications unless shown to be so). In that case,
the question coNP=NP itself is nonsense, as neither NP nor coNP
exists (when NDTM is in smoke), and we have no work to do.
You show us a (hype) NDTM that solves SS positively, with any
hypothesis you would like to put up but just be careful that they do
not show problems, I will show you why coNP=NP.
--- (My Signature)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Help (How long can a post be seen?)
Date: Mon, 04 Jan 1999 14:43:09 GMT
In article <[EMAIL PROTECTED]>,
rosi <[EMAIL PROTECTED]> wrote:
> 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).
http://www.dejanews.com/getdoc.xp?AN=330634411.8 is the oldest post of yours I
could find. I am posting this directly to give kudo for dejanews. Its great!
Dejanews seems very underutilized. It is better than the FAQ and if more
newbies used it, the groups would not have such inane questions over and over
and over again.
Thanks for asking
Web
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: rosi <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Sun, 10 Jan 1999 18:17:13 -0800
Matt Brubeck wrote:
> [snip]
> deterministic or nondeterministic, are theoretical constructs. The
> original poster seemed a bit confused about the terminology and concepts,
>^^^^^^^^^^^^^^^
Is that referring to me? If it is, I want to say a word. I do not
think I was. Lightly, I never say P!=NP if I do not have the proof. :)
> so I wanted to make it as clear as possible.
>
> Mr. McCarty pointed out that we can implement NDTM-like behavior on real
> ^^^^^^^^^^^^^^^^^^^^^^^^^^
Wonder in what sense is this 'like'.
> computing machines. However, my main point still holds that once an NDTM
> is made deterministic, we can't guarantee the same run-time bounds.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Security through obscurity in the smartcard world
Date: Wed, 30 Dec 1998 18:49:43 GMT
Gary Howland <[EMAIL PROTECTED]> wrote, in part:
>But I don't want to get into the GSM debate. I want comment on
>the priniciple of adding security (i.e. cost and expense) using
>obscurity. My reason for wanting debate, first on the question of
>"is security through obscurity" valid, and second on "how?", is
>because I intend to write a report on the benefits of obscurity,
>and the techniques one should use when creating proprietary
>algorithms. So in addition to comments on the validity of the
>proprietary algorithms, I would also like comments on the best ways
>of creating such proprietary algorithms. I am going to outline a
>few of the techniques in my paper, such as the subtle modification
>of existing algorithms, adding (better than removing) rounds,
>dangers or mixing algorithms that have weak keys etc. Any comments
>on the design of proprietary algorithms based on tried and trusted
>algorithms would be much appreciated.
Mostly, the accepted wisdom is that security through obscurity is
completely invalid, and should be avoided as a snare and a delusion.
I don't go quite that far. I think that with conservative design
practices, one can come up with a proprietary algorithm that is close
enough to one that has been well analyzed to be reasonably safe.
If one wished to base one's cipher on DES, of course, you had better
use larger S-boxes, to avoid needing to do extensive analysis.
But what you must also do is ensure that your design does not *depend*
on obscurity for its security. That the obscurity is only an
additional security measure, not critical to the security of your
design.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
** 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
******************************
