Cryptography-Digest Digest #948, Volume #8 Fri, 22 Jan 99 14:13:03 EST
Contents:
Re: Metaphysics Of Randomness (Dorina Lanza)
Re: Pentium III... (R. Knauer)
Re: Metaphysics Of Randomness (Dorina Lanza)
Re: Pentium III... (Guy Dawson)
Re: Metaphysics Of Randomness ([EMAIL PROTECTED])
Re: Metaphysics Of Randomness (R. Knauer)
Re: Metaphysics Of Randomness (Dorina Lanza)
Re: Metaphysics Of Randomness (Dorina Lanza)
Re: Help: Which secret key cipher? (Terry Ritter)
Multiple key cipher bit strength? ([EMAIL PROTECTED])
Re: Metaphysics Of Randomness (Patrick Juola)
USENIX Security Symposium Call; Papers due March 9 (Jennifer Radtke)
----------------------------------------------------------------------------
Date: Fri, 22 Jan 1999 11:28:39 -0500
From: Dorina Lanza <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>,
> Dorina Lanza <[EMAIL PROTECTED]> wrote:
> >> > You are making the mistake of trying to characterize a number as
> >> > random on the basis of some inherent property, like lack of
> >> > correlation or bias or somesuch. But we know that a characterization
> >> > like that will not properly characterize crypto-grade random numbers.
> >> > Only the characterization of the generation process is proper.
> >>
> >> Holy Cow Bob, if I give you a certifiably random string (say, with a
> >> gorgeous Allan Deviation plot) and present it to you as crypto-grade, and
> >> you give me one of your crypto-grade strings, I'll be able to test and
> >> certify that your crypto-grade string is random, but you have no way of
> >> knowing that I fibbed to you about the string I gave you because there is
> >> no test to distinguish between crypto-grade strings and random strings. We
> >> have discovered a distinction without a difference!
> >
> >I think it's worse than this. The statement that the output of a filtered
> >random source is non-random is false. If, for crypto purposes, we exclude
> >pathological values such as zero from a TRNG we still have an equiprobable
> >selection from a pool of possible values. The fact that the pool is slightly
> >smaller does not reduce the randomness because the selection process is the
> >same. The entropy would be slightly less, but not the independence of the
> >samples.
>
> "The entropy would be slightly less" is sufficient to make the
> resulting system less than perfectly secure. At this point it's
> just Yet Another stream cypher.
False. A filtered pad is not less secure than an unfiltered pad. (Now, before we
spin lock on yes/no/yes/no..., please give a summary of your reasons for
concluding the filtering weakens an OTP.
My reasons for concluding the opposite are contained in this gedanken experiment.
Consider a manual system in which pads of paper are covered with the message
keys. Through the miracle of carbonless ditto processing, anything you write on
the top sheet is encrypted with the key printed on the second sheet, and imprinted
on the initially blank third sheet. You mail the third sheet as the ciphertext.
The middle sheets are generated by an unfiltered, perfect, hardware TRNG. So far
so good.
Now, the filtering is applied by stenographers who are instructed to check the
middle sheet before use and throw away any pad that is all ones or all zeros.
They do so. The messages they send using the non-homogeneous pads are not less
secure.
In fact, the operators could be instructed to discard any sheets where the bit
bias exceeded a given ratio without compromising the security of the system.
> As to whether or not the loss of entropy is significant to make a
> practical difference -- that depends on the degree of filtering.
> What you do really buy by doing the filtering? Not much --- and
> every time the filter triggers introduces a weakness.
Among other things, a crypto system needs to inhibit the identity operation on
plaintext. I.e., the idea of a crypto system that includes the possibility that
ciphertext == plaintext has a flaw. Mathematically, the system including the
possibility is infinitesimally "stronger" due to the larger search space, but
that's not the unit of measure for crypto strength.
Consider a related problem. Perhaps every message should look like a false one.
I.e., every plaintext should be enciphered not so it looked like garbage, but that
it looked like a letter from long lost Aunt Jane. This could be implemented by
defining a search path through the available OTP pad space. Given a plaintext one
searches for an appropriately formatted ciphertext. Is this less secure that
plain-in-garbage-out? Not that I can see.
The above description is silly not because it would be ridiculously slow, but
because every message would need a prefix of the form "pad number N" to enable the
receiver to recover the original message. The width of the pad number is of the
same size as the length of the entire message *space*. So the prefix size would
exceed the size of the actual cipher text. But it would be secure. (Let's see,
it's provable, obscure, and inefficient; best of all worlds!)
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Pentium III...
Date: Fri, 22 Jan 1999 16:32:53 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 22 Jan 1999 14:21:15 +0000, Guy Dawson <[EMAIL PROTECTED]>
wrote:
>This makes it much easier (well, possible) to determine if a chip
>is one of a batch of stolen chips.
>There have been quite a number of raid on truck carrying Intel CPUs.
>They're currently easy to sell on the black market as they are
>commodity items that can't be traced.
>The rated CPU speed can also be recorded against the serial number
>and this used to determine if a supplier is re-rating CPUs. That is,
>taking a 333Mhz Celeron and passing it off as a 400MHz one.
I guess the next thing is to keep a database on your DNA so you can be
followed everywhere you go. <jeez>
Bob Knauer
"It is not the function of our government to keep the citizen from
falling into error; it is the function of the citizen to keep the
government from falling into error."
--Justice Robert H. Jackson
------------------------------
Date: Fri, 22 Jan 1999 11:40:16 -0500
From: Dorina Lanza <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
R. Knauer wrote:
> On Fri, 22 Jan 1999 08:12:34 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
> wrote:
>
> >Like most things to do with knowledge, randomness is contextual.
>
> That is crucially imporant to understand in Quantum Mechanics. Until a
> context is posited, particles behave completely randomly. Once the
> context is posited where an interaction with the environment can
> occur, you get effects that are not random.
>
> >The key is not "random" *with respect to the ciphertext it was
> >used to produce*. You can easily demonstrate that by using it
> >to with confidence decipher the ciphertext (to a highly coherent
> >plaintext), something a number "chosen at random" has little
> >chance of doing.
>
> Indeed! The random number has interacted with something in a given
> context, namely it has interacted with the message to produce the
> ciphertext. As soon as it did that, it lost its randomness.
>
> The fact that the key lost its randomness when it was used to produce
> the ciphertext gives it the property that it can decipher that
> particular ciphertext.
Next you will posit that the key has become "entangled" with both the
plaintext and the cipher text such that no one should ever use any of them
again. Clearly we need a global registry of such entangled values and
their relationships.
But let me try a question. Given that the key has become non-random, can
I reuse the ciphertext if I want to send the same message? I.e., will
reusing the ciphertext to represent the same plaintext, thus using a
non-random key, compromise the system so much that an attacker can
revcover the key?
------------------------------
From: Guy Dawson <[EMAIL PROTECTED]>
Subject: Re: Pentium III...
Date: Fri, 22 Jan 1999 14:21:15 +0000
Reply-To: [EMAIL PROTECTED]
fungus wrote:
>
> Intel has announced that the Pentium III will have a built in hardware
> random number generator, and individual serial number on each chip.
This makes it much easier (well, possible) to determine if a chip
is one of a batch of stolen chips.
There have been quite a number of raid on truck carrying Intel CPUs.
They're currently easy to sell on the black market as they are
commodity items that can't be traced.
The rated CPU speed can also be recorded against the serial number
and this used to determine if a supplier is re-rating CPUs. That is,
taking a 333Mhz Celeron and passing it off as a 400MHz one.
Guy
-- --------------------------------------------------------------------
Guy Dawson I.T. Manager Crossflight Ltd
[EMAIL PROTECTED] 0973 797819 01753 776104
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Metaphysics Of Randomness
Date: Fri, 22 Jan 1999 15:21:05 GMT
Organization: DECUServe
Lines: 39
In article <[EMAIL PROTECTED]>, Darren New <[EMAIL PROTECTED]>
writes:
>> Any NDTM can be constructed by taking a DTM and adding an RNG. Yes.
>
> Ummm, not really. For a NDTM to be ND, it has to have multiple
> transitions out of the same state into different states (on the same
> input). A DTM by definition has no such transitions.
Yes, really. A DTM that has an RNG input grafted on can take transitions
based on the RNG input.
You can graft the RNG onto the TM just like any other oracle.
>> If you look at an NDTM so constructed, you could say "any randomness
>> in the output came from the RNG, not the DTM".
>
> You're kind of mixing up the mathematics of what things are with
> possible implementations of what things are. For example, one possible
> definition for an NDTM is one in which it always choses the state
> transistion that is going to make it halt, if any will.
No. That's an NDTM plus an oracle. In an NDTM, the set of available
transitions is purely a function of current state and current tape
symbol. You don't get to disallow certain transitions based on tape
content not currently under the read/write head.
Oracles for the halting problem tend to be difficult to realize.
>> It is no sleight of hand to treat the NDTM as a black box and say that
>> "any randomnes in the output came from the NDTM". The RNG is part and
>> parcel of the NDTM.
>
> It is?! You'd have to show me a definition of NDTM that includes
> something about a random number generator. I don't remember ever seeing
> such a definition.
An NDTM is not _defined_ as a DTM+RNG. It is merely equivalent to
a DTM+RNG.
John Briggs [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Fri, 22 Jan 1999 14:36:58 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 21 Jan 1999 22:15:48 -0600, "R H Braddam"
<[EMAIL PROTECTED]> wrote:
>It seems to me that the random number lost its
>"randomness" as soon as you selected it from the pool
>of available random numbers. Until you selected the
>number, each number in the pool had equal probability
>of being the one to encrypt/decrypt the message. After
>you selected it, all the other numbers' probabilities
>went to zero, and the selected number's probability
>became a certainty.
That is exactly why I am saying that in a metaphysical
(meta-mathematical) sense the randomness was lost. Of course, it
hasn't fully lost it for crypto purposes until you actually use it in
an encryption.
You could in principle select it but never use it, in which case its
loss of randomness is not relevant for purposes of crypto. But that is
just a nitpick - you are absolutely right when you say that the act of
selection destroys the randomness *from your point of view*. After
all, that's why you have to keep your selection secret - keep it
obscure - because the number you selected is no longer random.
IOW, if the number used to encrypt the message were still random, you
would not need to keep it secret. We keep coming back to the fact that
all cryptography is "security through obscurity" in a metaphyscial
sense - even for the OTP once the key is selected from the TRNG
output.
>All that won't make it any easier for an attacker to
>select the same random number (it will still be random
>to them, unless and until they select it). Maybe that
>means that randomness depends as much on where you are
>as it does on the properties of that of which you are
>considering the randomness.
Indeed! That is one interpretation of how quantum mechanics works.
Until you consider the particle-observer environment, the particle
behaves in a random manner. But when the particle-observer environment
is taken into account, there is a new interpretation.
For example, we know from QM that an electron with precise momentum
has a wavefunction that is a superposition of states which describes
the electron as being everywhere in space equiprobably. But once the
electron interacts with its environment, that wavefunction "collapses"
and the electron is located somewhere in the immediate vicinity of the
observation point.
>All pretty complicated. I don't think I'll ever get it.
Nobody gets it. It's all a deep mystery well above our capability to
comprehend.
If you want to understand the mysteries of QM, stare at the output
sequence of a TRNG for eternity. Maybe one of them has the answer in
it.
Bob Knauer
"It is not the function of our government to keep the citizen from
falling into error; it is the function of the citizen to keep the
government from falling into error."
--Justice Robert H. Jackson
------------------------------
Date: Fri, 22 Jan 1999 11:31:27 -0500
From: Dorina Lanza <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
R. Knauer wrote:
> On Thu, 21 Jan 1999 13:26:52 -0500, Dorina Lanza <[EMAIL PROTECTED]>
> wrote:
>
> >I think it's worse than this. The statement that the output of a filtered
> >random source is non-random is false. If, for crypto purposes, we exclude
> >pathological values such as zero from a TRNG we still have an equiprobable
> >selection from a pool of possible values. The fact that the pool is slightly
> >smaller does not reduce the randomness because the selection process is the
> >same. The entropy would be slightly less, but not the independence of the
> >samples.
>
> >This idea of post-processing contaminating the source is fallacious.
>
> What you have just said is completely incorrect for crypto-grade
> random numbers.
>
> If you do what you have just proposed, you will be vulnerable to a
> Bayesian Attack.
No. The filtered key stream is not biased. Every entry in the pool is equally
probable. The fact that the poll contains 2^N - 2 entries instead of 2^N entries
does not create a vulnerability.
Please indicate otherwise if you are able.
------------------------------
Date: Fri, 22 Jan 1999 11:35:58 -0500
From: Dorina Lanza <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
R H Braddam wrote:
> R. Knauer wrote in message
> <[EMAIL PROTECTED]>...
> >On Wed, 20 Jan 1999 08:48:15 -0500, "Trevor Jackson,
> III"
> ><[EMAIL PROTECTED]> wrote:
> >
> >>Here's what is wrong. There is no lower limit on the
> triviality of the operation
> >>you can perform on the number K to "remove" its
> randomness. For example, (bad) L
> >>= K + 1. K is the only number that produces L when
> one is added, thus K is no
> >>longer random.
> >
> >>(Worse). K = K + 0. K is the only number that
> produces K under additive
> >>identity, thus K is not random.
> >
> >>(Worst) K = K. K is the only number with the value
> K, thus it is not random, it
> >>is K, thus K is not random.
> >
> >In each of those examples, producing a result that is
> unique destroys
> >the randomness of the key K. If I tell you what a
> number Y is, and
> >tell you that it was created, say by adding the number
> one to it like
> >above, then K is no longer random - it is a unique
> number given the
> >value of Y and the method of computing Y. Similarly
> for the identity
> >operation above.
> >
> >What I am trying to get across is that is appears (and
> this is only a
> >speculation on my part) that once a random number K is
> used in an
> >encryption operation, it loses its randomness because
> then it becomes
> >unique in the context of that operation.
> >
> >There is only one key possible that will reproduce the
> message, and
> >that makes K unique, not random since it is no longer
> just one of the
> >possible outputs from a TRNG. Only the key K can do
> that, and that
> >makes it special, not random.
> >
> >The fact that you may not know what K is, is not a
> measure of
> >randomness but a measure of obscurity. And we all know
> that obsurity
> >has nothing to do with true randomness per se -
> although obscurity is
> >confused with randomness all the time.
> >
> >Before K is used to encrypt the message, it is totally
> random - it can
> >be any sequence out of a pool of equiprobable
> sequences of given
> >length. But once you use it to form the ciphertext, it
> loses that
> >characteristic of randomness by virtue of its
> uniqueness in the new
> >context in which it has become entangled. And when the
> inverse
> >operation of decryption takes place, it is returned to
> the pool of
> >random numbers, because it is no longer entangled in
> any context.
> >
> >
> >Bob Knauer
> >
> I am not a mathematician or a cryptographer, and find
> all that very confusing. On the one hand, you start
> with a random number and a plaintext, and encrypt the
> plaintext by XORing it with the random number. Then the
> random number looses its random property because it can
> be used to recover the plaintext?
>
> How about the fact that the plaintext can be used to
> recover the random number in the same way? Doesn't that
> make the random number "computable" because you can get
> it by XORing the cipertext with the original plaintext?
>
> It seems to me that the random number lost its
> "randomness" as soon as you selected it from the pool
> of available random numbers. Until you selected the
> number, each number in the pool had equal probability
> of being the one to encrypt/decrypt the message. After
> you selected it, all the other numbers' probabilities
> went to zero, and the selected number's probability
> became a certainty.
Correct. The number has no special properties. The selection or
generation process does. Mucking about with the number does not change
the selection process/
> All that won't make it any easier for an attacker to
> select the same random number (it will still be random
> to them, unless and until they select it). Maybe that
> means that randomness depends as much on where you are
> as it does on the properties of that of which you are
> considering the randomness.
>
> All pretty complicated. I don't think I'll ever get it.
I believe you already have it. Like the limerick purported to have
driven Pascal mad:
Those we caught we threw away;
Those we didn't catch we kept.
What are they hunting?
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Help: Which secret key cipher?
Date: Fri, 22 Jan 1999 17:45:34 GMT
On Fri, 22 Jan 1999 10:21:56 -0500, in <[EMAIL PROTECTED]>,
in sci.crypt Dorina Lanza <[EMAIL PROTECTED]> wrote:
>[...]
>The other complaint about OTP-style security is that it takes too much pad
>material. However, the density of data storage is now so high that very
>infrequent use of a secure channel can support long term (months or years)
>worth of traffic in most cases.
That sounds *extremely* dangerous. As long as that data exists, it is
a danger to information past and future.
The ideal would be to get weekly or daily pads, use what is needed,
and discard the rest. In this way any compromise of a particular pad
ends when we get a new one.
A huge pad not only risks more messages, but, since it is held for a
long time, is more likely to be compromised.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED]
Subject: Multiple key cipher bit strength?
Date: Fri, 22 Jan 1999 17:35:54 GMT
Reply-To: [EMAIL PROTECTED]
Hi, I'm looking for a general way to calculate the effective bit strength of a
multiple decryption key cipher (ie if the key space is 128 bits and has 3 keys
that can decrypt the data, what is the effective strength?)
My exact situation is this:
I'm trying to implement a secure cache that will contain cached resources
(multiple keys). In order to get access to a resource, you must know its
exact name, which will be a long random string. I guess what I'm wondering
is, if I use names that are 128 bits long, and I have 1000 entries in the
cache, how difficult would it be to find *ANY* data just by brute force.
Basically I'm looking for a general equation which I can calculate the
general bit strength.
Thanks!
-Justin Chapweske
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 22 Jan 1999 10:56:11 -0500
In article <1999Jan22.102105.1@eisner>, <[EMAIL PROTECTED]> wrote:
>Organization: DECUServe
>Lines: 39
>
>In article <[EMAIL PROTECTED]>, Darren New <[EMAIL PROTECTED]>
>writes:
>> You're kind of mixing up the mathematics of what things are with
>> possible implementations of what things are. For example, one possible
>> definition for an NDTM is one in which it always choses the state
>> transistion that is going to make it halt, if any will.
>
>No. That's an NDTM plus an oracle. In an NDTM, the set of available
>transitions is purely a function of current state and current tape
>symbol. You don't get to disallow certain transitions based on tape
>content not currently under the read/write head.
No, that's an NDTM. Check out any of the basic texts; I recommend
Hopcroft and Ullman.
The best (informal) definition I've seen for an NDTM is that it's
a lucky computer -- it has choke points where it can go in several
different guesses and it always guesses right. This is *NOT* simply
a DTM plus a random number generator unless you can guarantee that
the RNG will always "guess right"
Oracular computation is something entirely different -- an oracle
is a specific state that gives you a (deterministic) answer based
on some question that you've set up on the memory and/or tape.
Classic example of NDTM -- recognizing palindromes over [ab]*, where
you (nondeterministically) "guess" where the midpoint of the
palindrome is and then confirm it. An NDTM will always recognize
a palindrome because it always guesses right :
e.g.
S -> aSa
S -> bSb
S -> a
S -> b
S -> \epsilon
is guaranteed to wold the problem (probability 1).
-k.
------------------------------
Crossposted-To: muc.lists.www-security,ocunix.mail.freebsd.security
From: [EMAIL PROTECTED] (Jennifer Radtke)
Subject: USENIX Security Symposium Call; Papers due March 9
Date: Fri, 22 Jan 1999 17:50:09 GMT
8th USENIX Security Symposium
August 23-26, 1999
Washington, D.C., USA
Sponsored by USENIX in cooperation with The CERT Coordination Center
If you are working in any practical aspects of security or applications
of cryptography, the program committee urges you to submit a paper.
=============================================================
Dates for Refereed Paper Submissions
Paper submissions due: March 9, 1999
Author notification: April 27, 1999
Camera-ready final papers due: July 12, 1999
=============================================================
Please find the Call for Papers at
http://www.usenix.org/events/sec99/
The Symposium brings together researchers, practitioners, system
administrators, system programmers, and others interested in the latest
advances in security and applications of cryptography. Two days of
tutorials will be followed by two days of technical sessions, offering
refereed papers, invited talks, works-in-progress, panel discussions,
and a product exhibition.
Invited Talk Speakers include:
Ross Anderson, Computer Laboratory, Cambridge University
Ed Felten, Princeton University
Susan Landau, University of Massachusetts
Peter G. Neumann, SRI
Paul Van Oorschot, Entrust Technologies
Marcus Ranum, Network Flight Recorder
=============================================================
USENIX is the Advanced Computing Systems Association. Our international
membership includes engineers, system administrators, scientists, and
technicians. Our conferences are recognized for delivering pragmatic,
technically excellent information in a highly interactive,
vendor-neutral forum.
------------------------------
** 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
******************************
