Cryptography-Digest Digest #886, Volume #8 Mon, 11 Jan 99 21:13:05 EST
Contents:
Re: On the Generation of Pseudo-OTP (Paul L. Allen)
Practical OTP for secure two-person emailing (Anonymous)
Re: Practical True Random Number Generator (R. Knauer)
Re: On the Generation of Pseudo-OTP (Patrick Juola)
Re: Practical True Random Number Generator (John Curtis)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On leaving the 56-bit key length limitation ([EMAIL PROTECTED])
Re: Comments & note for Bryan (Re: coNP=NP Made Easier?) (Planar)
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: Help: a logical difficulty (Darren New)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul L. Allen)
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 23:25:07 +0000
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>
[EMAIL PROTECTED] (R. Knauer) writes:
> On Mon, 11 Jan 1999 18:49:55 +0000, [EMAIL PROTECTED] (Paul L.
> Allen) wrote:
>
> >Then take it from me that parts of your specification are ridiculous.
>
> Aha! An ad-hominem.
No, if I were using an ad hominem (in the sense you mean it, which isn't
what it really means), I'd have called you a bloody idiot.
> Must mean you do not have the confidence necessary to present your
> points reasonably.
No, I just know the folly of trying to explain complicated things to
fucking idiots. As it happens, I tried explaining the simpler stuff
to you in the same post. Your response was to snip it all out because
you were too fucking stupid to comprehend it and then leap on what you
called an ad hominem in order to try to con people into thinking you
had justification to ignore everything I wrote without them thinking
you had shit for brains.
--Paul (who's just given a demonstration of what a *real* ad hominem
looks like but doubts Knauer has the wit to comprehend the difference
between that and telling him that parts of his specification are
ridiculous).
--Paul
------------------------------
From: Anonymous <[EMAIL PROTECTED]>
Subject: Practical OTP for secure two-person emailing
Date: 12 Jan 1999 01:38:34 +0100
(Forgive me if someone already posted an idea like this.)
Following on the thread of the "Practical TRNG," if Alice filled a 660mb
file with a stream of true random bits, burned one CD-ROM copy for herself
and one copy for Bob, then met Bob to give him the CD-ROM OTP, it seems
like they could exchange years worth of personal email (textual at least)
before needing to generate a new OTP and meet again to swap it.
Alice starts at offset zero, Bob starts at offset halfway through the CD,
and if Alice hits Bob's offset or Bob hits the end of the CD (or say, they
come within 10% of their ends), then they begin to make provisions to
create and exchange a new OTP. Each message contains an offset number to
avoid synchronization problems.
Each party could send ~330mb of data before the pad would be used up.
This is quite a decent amount of text, certainly more text than I write to
any single person in my lifetime.
This seems to make an OTP-based TSCS quite feasible in real life, as long
as you make sure you never re-use any portion of the pad, and that the pad
(and original file) are securely deleted after use. Obviously the
strongest attack would be to recover either Alice or Bob's pad.
Protocol concerns such as Bob being assured that Alice REALLY made good
TRNs for the OTP could be addressed by each of them burning their own OTP
CD-ROMs and trading them, then agreeing to use XOR-ed data combining one
byte from each CD-ROM to create one key byte.
Muse, muse, muse...
K
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 00:43:49 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 16:48:45 -0500, Nicko van Someren
<[EMAIL PROTECTED]> wrote:
>Another method is to time the two intervals between three decay
>events. If the first interval is longer than the second then emit a
>zero and if the second is longer than the first emit a one. If your timer
>says that they are the same do it again. This has as little bias as
>you can get.
That is the preferred method because it cancels any slowly varying
systematic errors, such as clock errors or detector errors - as long
as the the interval lengths are shorter in duration than the time
constants for the errors.
It was my understanding that you needed to measure each interval
independently, that is, you need to time the two intervals between 4
decay events, not 3.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: On the Generation of Pseudo-OTP
Date: 11 Jan 1999 16:41:29 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 11 Jan 1999 10:03:05 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>First, there's no demonstration or proof that any given trancendental
>>number is suitable for use as a stream cypher.
>
>How about specific constants like ln(c) or c^1/2, etc.? Can these be
>show to be random like pi on a case by case basis?
Yes. But on a case-by-case basis. It's *NOT* the case that
all transcendental numbers are "random" in a cryptographic
sense.
>>In particular,
>>if you've only got a finite number of starting points, then you'll only
>>generate a finite number of streams and you're back to breaking the
>>cypher by seed enumeration. Just think of each possible starting
>>position as a seed.
>
>Indeed, just like a conventional crypto key that would be communicated
>to a correspondent on a secure channel.
>
>>And if you *don't* accept that there are only
>>a finite number of possible starting points....
>
>Why would I believe that there are only a finite number of starting
>points when pi is an infinitely long number?
Because you're running on a machine with finite memory, for one
thing....
It's actually fairly easy to make a PRNG-based cryptographic protocol
provably secure, in the same sense as the proof for the one-time pad.
Just make the seed to the PRNG as long as the message you want to
send (and use any decent PRNG). In this case, then the PRNG *is*
a one-time pad.
But in a real system, people aren't willing to do that. For most
trancendental numbers and most bases, it takes time and effort to
calculate increasingly long strings of digits. So for engineering
reasons, it's a lot faster to calculate the first thousand digits
than the second thousand (and so forth, progressively). Thus my
question :
>
>>well, just how much
>>work are you willing to do to compute the 2^128'th digit of pi as
>>the first bit of your stream cypher?
>
>Actually I had just that in mind. How much work does it take, compared
>to the construction of a certified TRNG, creation and distribution of
>pads, etc. ?
The cost of creating and distributing a pad is actually pretty constant,
irrespective of the length of the pad and also irrespective of the pad
itself. This is *NOT* the case for generating successive digits of
a trancendental numbers -- each digit costs marginally more than the
last, which means that there's one digit that costs more to generate
than it would cost to generate and distribute random pages. At this
point, it is no longer cost-effective to consider trancendental-based
computation. You might as well print the pads and be done with it.
So this provides an effective upper bound to the number of keys you
could have.
However, even psychologically, most people aren't going to think
of huge numbers such as that. The time of generating even a
hundred-thousand digit pad will keep most people from using (for instance),
a offset greater than hundred thousand. But this is the size of
offset that a determined cryptanalyst could simply keep around on
a floppy disk....
-kitten
------------------------------
From: [EMAIL PROTECTED] (John Curtis)
Subject: Re: Practical True Random Number Generator
Date: 11 Jan 1999 23:31:17 GMT
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>
>I guess that every random number isn't really random, since everything in the
>world can be calculated or predicted (chaos theory). Almost-perfect random
>numbers are generated by systems with a lot of factors and a low rate of
>collisions between those factors. Real random numbers are only theorical.
>
>dA
>
Hmmm. Not sure a physicist would agree. Some types of
radioactive decay are modelled as quantum tunnelling out
of an energy well. This is dependent upon the Psi function
of the particles and is not predictable in a pretty deep
fashion. Chaos theory really describes macro-scale events.
I think that a smoke detector is probably modifiable into
a very good TRNG, as the decay particles are detectable as
individual events and the time series of these is tied
directly into quantum decay. Should be possible to isolate
the system from outside influences much more easily than a
"noise" source, as you are sensing a highly amplified discrete
event, rather than trying to highly amplify a continuous
signal.
Got to be careful, though. Strange things, like microphonics
can introduce correlations to other signals in the system.
Much easier to demonstrate that these are eliminated in a
discrete system, still requires careful validation.
deep waters.
ciao,
jcurtis
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 01:16:02 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 21:03:31 +0000, [EMAIL PROTECTED] (Paul L.
Allen) wrote:
>> There is something about your entropy that is not quite right here. In
>> one of his papers, Chaitin dismisses such "low-entropy" sequences as
>> being "non-random" for purposes of his algorithmic information theory,
>> of which his algorithmic complexity theory is a subset. He dismisses
>> such sequences because they are reducible.
>Then his algorithmic information theory appears to have flaws.
To be fair to Greg Chaitin, you should read his papers for yourself
and not trust my evaluation. I am not trained in this field (although
I am not a complete neophyte either), so it is entirely possible I
misconstrued what he was saying.
His papers are at:
http://www.umcs.maine.edu/~chaitin/
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
>Any sequence
>you like to specify in advance is reducible and, with the right input data,
>will result in good compression.
I don't understand what you just said. Are you saying that ANY
sequence can be compressed further to a significant extent? Small
reductions are not of significance in algorithmic complexity theory.
>Build a Huffman compression table for
>ordinary English text and use it to compress the same text that's been
>rot-13ed and you'll get something that's larger than the original. The
>sequences Chaitin claims are reducible are only reducible in some
>circumstances and those circumstances do not apply to TRNGs.
We decided that Chaitin's algorithmic complexity theory has no direct
immediate application to crypto (private communication). But it is
interesting to note that he proves that random numbers cannot be
characterized as such formally. He does that by appealing to Godel's
Theorem, Turing's Halting Problem and his own Mathematical
Indeterminancy Theorem.
>Essentially the mistake is to take a finite sequence and apply thinking
>that is only meaningful for infinite sequences. Like asking if "6" is
>a random number - it's a meaningless question because you the term "random
>number" only applies to something which is taken from a (potentially) larger
>sequence of numbers.
I am not sure I follow that. It is a tenent of both crypto and
Chaitin's theory that one cannot characterize a number as random on a
formal basis by looking at the number by itself. In crypto, one has to
decide randomness based on the nature of the generator. In Chaitin's
theory, randomness is decided if one cannot further reduce the number
algorithmically.
>This is true (except you mean "sequence" again). For very large sequences
>and selections of sequences we can determine the probability that those
>sequences would have the statistical properties they have by chance.
It is not the statistical properties of the sequence per se, but the
statistical properties of the generator that make a number truly
random for crypto purposes. I am not trying to nitpick, just be as
clear as possible that it is the generator that counts, not any
particular sequence itself.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: On leaving the 56-bit key length limitation
Date: Tue, 12 Jan 1999 01:21:40 GMT
In article <779mcu$t5s$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Ed Gerk wrote:
> [...]
> > As an estimate for the (small) plaintext space one may need if only
> > 3-characters are used, one can start with the maximum number of 2^18
> > cases if one includes all upper and lower case letters, space,
> > pucntuation and numbers in a 64-character alphabet (to simplify
> > calculations). Of course, one should now rate the entries according to
> > trigram linguistic frequencies for English -- taken from general text
> > or (better) from former texts of similar sources (e.g., electrical
> > engineering, computer science, social, medical, etc.). Looking at
> > usual trigram tables [Sha49], [Bek82], I would assume one can thus
> > reduce the plaintext space to probably 12,000 cases for the most
> > relevant English trigrams (the, ing, and, her, ere, ent, tha, nth,
> > was, eth, for, dth, hat, she, ion, int, his,...) [Bek82]. The
> > probability of occurrence decreases rapidly along such a list. For
> > example, "the" is approximately 8x more probable than "his".
> >
> > But, it may get better (i.e., worse). Since most cipher systems begin
> > with a "magic number" or a message begins with the usual "Received",
> > "To:", "From:", etc., then it may be possible to further reduce the
> > 3-character list, for the message beginning. Perhaps, down to 1,000
> > cases as I can evaluate from 10x the variety in my own messages.
> >
> [...]
> > Of
> > course, the less entries one has, the less false alarms one may
> > encounter.
>
> The unicity distance is the least number of characters for
> which we do not expect any false alarms.
>
Unfortunately still, what you define as "unicity" is not even slightly
equivalent to the fundamental concept of unicity. And, note. You cannot just
define things at will -- there is a reason why definitions are as they are:
because they work as they are written. They correspond to some reality.
To help you see the difference, if you write "maximum" for "least", "false
messages" and not "false alarms" and if you change "do not expect" to "expect
one" then with these changes what you wrote can be chnaged to be numerically
equal to Shannon`s unicity definition -- even though it is also not the same.
So, please verify. To help, see section 6 in http://www.mcg.org.br/unicity.txt
However, unicity has nothing to do with my argument above, which deals with
letter frequencies, digram frequencies and so on. These quantities have to do
with false alarms -- for unfit messages. Not with false messages. Two
entirely different things. In the first you detect as a correct message what
you should not, in the later you cannot disambiguate what is false from what
is correct. In other words, the first has to do with reliability, the second
with accuracy -- two entirely different concepts.
> > However, the less entries one has the more misses one may
> > suffer. Given the cost of a false alarm, the cost of a miss, and their
> > probabilities, which can be translated in detection theory in terms of
> > accuracy and reliability [Ger98], one can calculate the best threshold
> > (in terms of number of trigram entries) that will minimize costs.
>
> Actually carrying out some calculations shows that 3 characters
> will not resolve the DES key. Let's use Ed's estimate of 1000
BZZT! My estimate of "1,000" was NOT of "reasonably probable 3-character
messages" as you say. As I **wrote** above, that number provides an order of
magnitude estimate for the number of needed trigrams, in one particular case
-- that would be applied to 8-character messages (a DES block).
> reasonably probable 3-character messages, encoded into 3 bytes.
> Decryption with an incorrect key results in a random three-byte
> string, and 1000 of the 16777216 three byte strings we recognize
> as English. Thus an incorrect key has a one in 16777.216 chance,
> equivalent to a probability of 0.00005960464477539, of inducing
> English plaintext. Of the 2^56 DES keys, we therefore expect
> about 4294967296000 of them to decrypt a given three byte
> ciphertext into three bytes of English plaintext.
Your estimate is incorrect. The correct number is:
out of the 2^56 DES possible plaintexts, that may be tentatively deciphered
from an 8-byte DES ciphertext block, approximately 3 (three) 8-byte blocks
will resemble English. Not "4294967296000" for 3-bytes, to be sure.
> The claim
> that 20 bytes is the maximum possible unicity distance for a
> cipher with a key of 56 bits and language of compressed
> English is incorrect. The unicity distance estimate for a
> random cipher H(K)/D is a lower bound, not an upper bound on
> unicity distance.
I see that you are not used to mathematical terminology. Actually, it is
quite simple. To repeat, Shannon`s unicity is the least amount of plaintext
which can be uniquely deciphered from the corresponding ciphertext. Thus,
Shannon`s unicity is the greatest lower bound of distinguished (ie,
unambiguous) text that can be deciphered, in one particular system. However,
as a function of compression for *different* systems, this "greatest lower
bound" can be maximized -- and that is what I mentioned. Since 20 bytes do
not compress well, the estimate of 2x compression is already very favorable
for such short text and I may rightly say that 20 bytes is the *maximum*
expected value for unicity in all systems that I may consider, for 8-bit
characters and 56-bit keys.
Cheers,
Ed Gerck
______________________________________________________________________
Dr.rer.nat. E. Gerck [EMAIL PROTECTED]
http://novaware.com.br
--- Meta-Certificate Group member -- http://www.mcg.org.br ---
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Planar <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: Comments & note for Bryan (Re: coNP=NP Made Easier?)
Date: 12 Jan 1999 01:27:23 GMT
>From: rosi <[EMAIL PROTECTED]>
> If anybody wants to point out anything wrong, do it consistently; if
>anybody wants to point out something right, do it consistently. Do NOT
>do it just for the purpose of promoting your reputation, self interest,
>ego, etc. Do NOT do it simply because you feel like it. Do NOT just pick
>one out simply based on the extremely high probability of being not
>on the wrong side.
You don't seem to understand Usenet very well. People are (mostly)
free to post anything on any subject they like, and (this is
important) people are free to NOT post if they don't feel like
posting.
> This Planar seems to me, I say 'seems to me' and I can be wrong,
>lurking out there, letting pass of any mistakes as he wishes, waiting
>for something in what I say that he can find fault with. Then he jumps
>on to it with an 'Aha', thinking that can turn him into a complexity
>theory super guru instantly without working hard with his brains.
Working hard with my brains is what I do all day long. I just thought
I could help you. If it's not the case I'm sorry, but if you want to
tell me what I must and must not post, and when to work hard with my
brains (and on what subject), that'll cost you $100000 per year.
Moreover, I already worked hard for you: I posted a NDTM that solves
the SS problem. There'll be no charge for that.
>Reminder: if he "aha'd" all over the place, I would never say this.
If I did, I'd look silly most of the time. I only post when I feel I
have something interesting (and true) to say. It's true, I only post
when I'm very sure of being right.
> It would be a real nice patch, I think, to agree with Planar and
>do 'P by DTM'. (That's from a book? It must make perfect sense! Be
>it in some volume, but is it God's creation or creation by God's
>creation?)
I didn't get it from a book, but it was from someone who holds a
doctorate in computer science. Does that count ?
> Look at the originating post of mine, the argument is simple:
> If NDTM is real, coNP=NP.
I'm honestly trying to help you sort this out. Would you please
answer this genuine question: what do you mean by "real" in the above
sentence ?
> If there is any mechanism, including a piece of magic
> rock, that solves SS positively in P, then coNP=NP.
(This is mostly the same question as above.) Do you have a
mathematical definition of "mechanism" ? Would you mind posting it ?
> Lastly for you Bryan. If you want to discuss the issue, you need
>to commit to getting this to the end responsibly and give me _YOUR_
>NDTM (you can copy from anywhere you care to) and show us exactly
>how _YOUR_ NDTM solves SS in polynomial time. Remember, I say if
>NDTM is realizable (that can bein hypo way), coNP=NP (in likewise
>hypo way). (How many times have I repeated?)
I posted one yesterday to sci.math and comp.theory. Do you realize
this is largely off-topic for sci.crypt ?
--
Planar
------------------------------
Date: Mon, 11 Jan 1999 20:35:24 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Mok-Kong Shen wrote:
> Trevor Jackson,III wrote:
> >[snip]
> > For purposes of this discussion, I propose that we stipulaed that
> > "unbiased" means that whatever bias is present falls below some epsilon
> > value that we can adjust as necessary. This assumption is almost
> > mandatory when dealing with large volumes of numbers because the
> > probability of getting first order perfection (exactly the same number
> > of zeros and ones) is fairly small, even from a theoretically "perfect"
> > source.
> [snip]
> You certainly neglect the fact that any physical oberservations
> need be done through some apparatus and these can have measurement
> errors. I am not a physicist, but I guess(!) a principle of
> Heissenberg means that one can't get absolutely exact measurements.
This is why I suggested the use of an epsilon to described the limits of our
knowledge.
------------------------------
Date: Mon, 11 Jan 1999 20:41:53 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> On Mon, 11 Jan 1999 13:53:55 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >If you accept that a good pseudo-OTP can be useful on PRACTICAL
> >grounds, then we don't have to argue.
>
> First I do not accept that there is such a thing as a "pseudo-OTP". A
> stream cipher is either an OTP or it is not an OTP. The term
> "pseudo-OTP" is an oxymoron, and is very misleading. That's why
> cryptographers reserve the term OTP to mean one and only one thing.
>
> Just look at the extensive confusion that is caused by misusing the
> term "random". By not bastardizing the term OTP, we avoid such a
> situation as that which has befallen the term "random". Maybe the way
> to emphasize this is to call the OTP a "crypto-grade OTP", like we are
> now forced to call a "crypto-grade random number" to distinguish it
> from all other uses of the term "random".
>
> But that is really not necessary, since there is only one proper use
> of the term "OTP" and that is the one all cryptographers agree on, as
> described in Schneier's main book. Nowhere in that book do you see the
> term "pseudo-OTP" - at least I have never seen it - because such misue
> is not tolerable to cryptographers.
Do yo believe it proper to describe the cipher system attacked in the
Venona project as an OTP or not? Both the Russians who operated the
system and the attackers considered it to be an OTP. Probably becauseit
was supposed to be based on single-use keys. The quality of the keys is
irrelevant to the classical term OTP.
Your very narrow definition does not match the classical definition of an
OTP.
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Help: a logical difficulty
Date: Tue, 12 Jan 1999 01:47:12 GMT
> I would side with Mike on this. Computer scientists should serve the
> wider community, not dictate to them. If this make their sorting
> algorithms a bit harder, so be it.
Amusingly enough, it became obvious when the local Blockbuster video
store switched to computerizing their videos for sale (as well as the
rented ones), as movies like "The 4th Protocol" moved from the "F's" to
the beginning of the section (as in ASCII). Bleh.
--
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."
------------------------------
** 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
******************************
