Cryptography-Digest Digest #9, Volume #9 Sun, 31 Jan 99 00:13:04 EST
Contents:
Re: Metaphysics Of Randomness (R. Knauer)
Re: Random numbers generator and Pentium III ("Kazak, Boris")
Re: Who will win in AES contest ?? ([EMAIL PROTECTED])
Re: Encoding for telephone over Internet
PRNG Theorem ([EMAIL PROTECTED])
Re: *** Where Does The Randomness Come From ?!? *** (Marty Fouts)
Re: Fialka Punch Card Speculation
Re: Blowfish: Affecting strength of algorithm? (Logi Ragnarsson)
Re: Metaphysics Of Randomness ("Trevor Jackson, III")
Re: Some more technical info on Pentium III serial number (TTK Ciar)
Re: Spread Spectrum ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Sun, 31 Jan 1999 00:27:18 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 30 Jan 1999 14:18:50 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>But it's a counter example because the sequences are perfectly predictable.
The reason that your LFSR is predictable is because it cannot produce
all possible sequences equiprobably. Once it has produces a particular
sequence, the next one it produces is not equiprobable.
Just because your LFSR can produce all possible sequences does not
make it a TRNG. A counter can do that, and it is not a TRNG. The
output must also be equiprobable, which means that any one of 2^N
possible sequences must be possible each time a new sequence is
produced. Each new sequence must be from a sample space that is 2^N in
size.
>Not hardly. Equal probabilities does not imply indeterminacy. Nor does
>indeterminacy imply equal probabilities. Neither is sufficient. Both are
>necessary for provably perfect security.
Equiprobability does too imply indeterminancy. If a sequence can be
one of 2^N possibilities equiprobably, then the output is
indeterminant, because you cannot determine which one of the 2^N
possible equiprobable sequences it will be.
I knew you had some weasel word trick up your sleeve. You must have
studied sophistry once.
>That is why it is characterized as a defensive consideration. It is silly to
>protect a $100 secret with $10,000 worth of security transaction cost. The same
>is true of $1B secrets. They aren't worth more than $1B to protect.
What if there is more at stake than money - like human life?
>So? Sorry, I missed it. Please point to the threat model you noticed.
Any of the attacks against stream ciphers.
Bob Knauer
"I place economy among the first and most important virtues and
public debt as the greatest dangers to be feared. We must not
let our rulers load us with perpetual debt."
--Thomas Jefferson
------------------------------
From: "Kazak, Boris" <[EMAIL PROTECTED]>
Subject: Re: Random numbers generator and Pentium III
Date: Sat, 30 Jan 1999 19:42:12 -0500
Reply-To: [EMAIL PROTECTED]
R. Knauer wrote:
>
> My problem with statistical properties goes deeper than that.
>
> Statistical properties are inadequate for determining proveable
> security, and therefore have no value whatsoever. What possible good
> are statistical tests that can pass a non-secure PRNG?
>
> The fact is that their use leads to a false sense of confidence, which
> is the surest way to have problems with crypto.
>
> Bob Knauer
========================
Again agreed without objection. IMHO, it will be useful to regard
both properties as components of a system. Otherwise the discussion
can quickly go along the lines - what is more important in a table,
the deck or the legs. The answer is, none of those alone can make a
useable table, both are needed.
The useable random sequence MUST be produced by the way unguessable
to the opponent and MUST pass the statistical test. Failure to comply
with any one of these requirements is (again IMHO) sufficient ground
for rejection.
Respectfully BNK
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Who will win in AES contest ??
Date: Sun, 31 Jan 1999 00:49:01 GMT
put on your dark glasses and always remember
Hogans Heroes was the finest WWII movie ever made and of course the greatest
actor of all times has got to be thumbs down!
Sergeant Shultz.
"I know nothink!"
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Encoding for telephone over Internet
Date: 30 Jan 1999 22:18:35 GMT
why do you you think that a real time communication doesnt need
as much security ?
On 28 Jan 1999 11:02:42 -0500, Patrick Juola <[EMAIL PROTECTED]> wrote:
[snip]
>
>OTP level? No? "Pretty good"? Yup. PGPfone is out and available
>and uses pretty hefty encryption. The advantage of telephone, &c.
>is that as the communication is real-time, you usually don't need
>as much security -- the communications don't need to stay secret
>as long.
>
------------------------------
From: [EMAIL PROTECTED]
Subject: PRNG Theorem
Date: Sun, 31 Jan 1999 01:22:57 GMT
I cooked up this theorem for some work I am doing:
=======================
Hash PRNG Cycle Theorem
=======================
A class of pseudo-random number generators (PRNG's) works as follows. An
initial state (seed) x_0 is chosen arbitrarily, and contains K bits.
Subsequent states are obtained by applying a good hash function to the
state, i.e. x_i = H( x_(i-1) ). The bits of x_1, x_2, ... (or some
subset of them) are taken as the PRNG output.
It is known that this type of feedback PRNG will contain at least one
cycle, and that the largest possible cycle length is 2^K. We wish to
quantify the probability that a cycle is encountered within a certain
number of hash rounds.
Assume that all 2^K possible hash outputs are equally probable for an
arbitrary input. If this is not true then we do not have a good hash
function and should consider another choice.
Let p(i) be the probability that the PRNG enters a cycle (encounters a
previous state) after i hash rounds, starting from an arbitrary initial
state, and given that a cycle was not entered in a previous round.
Obviously,
i
p(i) = --- (1)
2^K
Let q(i) bet the probability that a cycle is encountered within i hash
rounds. It is observed that a cycle is not encountered if the PRNG does
not enter a cycle in each round, so
i
---
1 - q(i) = | | [ 1 - p(j) ] (2)
j=1
i
--- j
q(i) = 1 - | | [ 1 - --- ] (3)
j=1 2^K
A simple closed-form expression for (3) (not containing Gamma or
Pochhammer functions) has not been found. However, one can derive the
inequality
i (i+1)
q(i) <= ------- (4)
2^(K+1)
with equality holding only for i=1.
As an example, it is extremely unlikely that a K=128 hash PRNG
encounters a cycle within a billion rounds, since
q(10^9) < 1.5x10^-21 (5)
========================================================================
Is it correct?
Is it new?
Can it be extended for the state equation x_i = H( x_(i-1) ; i mod m )
where m is some constant, maybe a power of 2?
Can (3) be simplified?
Can (3) be accurately calculated for K=128 and large i?
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Crossposted-To: sci.skeptic,sci.philosophy.meta
Subject: Re: *** Where Does The Randomness Come From ?!? ***
From: Marty Fouts <[EMAIL PROTECTED]>
Date: 30 Jan 1999 17:42:10 -0800
>>>>> Tom Norback pounded silicon into:
> Marty Fouts wrote in message ...
>> My personal definition is 'effect without cause'. Using the
>> formulation we were discussing before, If a system has a
>> configuration C_n followed by a configuration C_(n+1) and there
>> exists no F such that C_(n+1) = F(C_n) (other than an F which
>> trivially enumerates states as successors) then C_(n+1) 'had no
>> cause', and is a truely random state.
>>
> QM does deny the possibility of a function such as F. This is not
> the same, however, as saying that C_(n+1) has no causal relation
> to C_(n) or that C_(n+1) is a random state. What QM suggests is
> that the future is underdetermined (not "undetermined") by the
> past. Every configuration C_(n+1) does indeed have its efficient
> cause in C_(n). But C_(n) does not necessitate one particular
> C_(n+1).
F in this case is multivalued, in the formalism I'm proposing, that is
F() no longer established _the_ successor to C_(n) but rather the set
of possible successors to C_(n).
> It may be that likening reality to a system with discrete
> configurational states introduces difficulties into our analysis.
possibly. However, if one assumes that time is quantized then it
should follow.
--
that is all
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Fialka Punch Card Speculation
Date: 31 Jan 99 02:24:17 GMT
Frode Weierud ([EMAIL PROTECTED]) wrote:
: Ah, I see what you mean. However, the Fialka did not use normal Hollerith
: punched cards. The cards were of a special design which to my knowledge was
: used for only this very special purpose.
I was worried that might be a possibility, since it makes sense from a
security standpoint, making my speculations pointless.
: You will find that Russian
: equipment often are using quite different solutions than what we are used
: to. I have seen that in their electronic equipment. There is often used
: quite ingenious mechanical solutions instead of relying entirely on
: electrical or pure electronic solutions. The Agat cipher machine is an
: almost purely mechanical machine which is in stark contrast to other
: one-time-tape machines of the same epoch.
Interesting. I shall be looking up your Cryptologia article on the various
forms of the Enigma, and keeping an eye out for anything you publish about
Russian cipher machines as well.
John Savard
------------------------------
From: [EMAIL PROTECTED] (Logi Ragnarsson)
Subject: Re: Blowfish: Affecting strength of algorithm?
Date: 31 Jan 1999 02:08:26 GMT
"Uta Loeckx" <[EMAIL PROTECTED]> writes:
>A Random object is created using the computer clock. Then every time
>data is encrypted, the Random object produces a 64bit value which should
>be equally distributed (see Java1.2APIdocumentation).
>This value gets XORed with the 18 PBoxes of Blowfish's expanded key,
>always putting two of these boxes together to produce 64bits. I actually
>thought, that this might improve security because no one knows the PBox
>values if he/she doesn't know the key, but one might guess the system
>time. This is my main question: is this random enough for encryption???
I'm not sure this is a good idea. An attacker can guess the time of an
encryption, and use it to get the value returned by the Random object. If
he xors this with the IV, he'll have information about the key. Horror of
horrors!
I think you would be better off using a good random number generator to
begin with. java.security.SecureRandom should be good enough in most
cases, methinks (although it isn't "secure" in the sense of
http://www.counterpane.com/pseudorandom_number.html. I *think* my own
PRNG is, but I should spend some more time on it)
There is also a serious bug in SecureRandom in java versions before 1.2,
which cause the initial seeding to hang indefinately (or at least over
the weekend, which amounts to the same thing)
Logi Ragnarsson - [EMAIL PROTECTED]
--
Logi Ragnarsson - [EMAIL PROTECTED] - Math and CS student at Univ. of Iceland
Some day we all shall be out of scope. (Beware the garbage collector.)
------------------------------
Date: Sat, 30 Jan 1999 22:11:25 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
R. Knauer wrote:
> On Sat, 30 Jan 1999 14:18:50 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >But it's a counter example because the sequences are perfectly predictable.
>
> The reason that your LFSR is predictable is because it cannot produce
> all possible sequences equiprobably. Once it has produces a particular
> sequence, the next one it produces is not equiprobable.
>
> Just because your LFSR can produce all possible sequences does not
> make it a TRNG. A counter can do that, and it is not a TRNG. The
> output must also be equiprobable, which means that any one of 2^N
> possible sequences must be possible each time a new sequence is
> produced. Each new sequence must be from a sample space that is 2^N in
> size.
>
> >Not hardly. Equal probabilities does not imply indeterminacy. Nor does
> >indeterminacy imply equal probabilities. Neither is sufficient. Both are
> >necessary for provably perfect security.
>
> Equiprobability does too imply indeterminancy. If a sequence can be
> one of 2^N possibilities equiprobably, then the output is
> indeterminant, because you cannot determine which one of the 2^N
> possible equiprobable sequences it will be.
>
> I knew you had some weasel word trick up your sleeve. You must have
> studied sophistry once.
Look, equiprobable means equal probabilities. I.e., a flat distribution. It has
nothing to do with indeterminacy. The technical term you want is independence. The
individual samples have to be independent. This process gives you the indeterminacy
that you are looking for.
The equiprobable criteria is trivial to meet. The
indeterminact/independence/unpredicability criteria is the hard part. So concentrate
on it.
>
>
> >That is why it is characterized as a defensive consideration. It is silly to
> >protect a $100 secret with $10,000 worth of security transaction cost. The same
> >is true of $1B secrets. They aren't worth more than $1B to protect.
>
> What if there is more at stake than money - like human life?
Yeah, what if? The trade off still exists. For example, construction projects
always have to provide for a non-zero accident rate. On really big projects the
lethal accident rate becomes non-trivial. Life is full of risk. People accept risks
based on the rewards. Often monetary rewards.
The value of defensive security measures is limited by the value being protected.
The units do not matter.
>
>
> >So? Sorry, I missed it. Please point to the threat model you noticed.
>
> Any of the attacks against stream ciphers.
An attack is not a threat model.
------------------------------
From: [EMAIL PROTECTED] (TTK Ciar)
Crossposted-To: talk.politics.crypto,comp.sys.intel
Subject: Re: Some more technical info on Pentium III serial number
Date: 30 Jan 1999 19:32:41 -0800
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED]
(John Savard) writes:
>
>2) It is nice that Intel has devised a scheme whereby a web server,
>desiring to see people's Pentium III ID numbers, will get an ID signed
>by Intel which will then be used to request only a keyed hash of the
>ID number from your chip.
Does the PIII have built-in firmware which (1) searches for and
identifies a network device on bootup, and (2) causes it to emit an
identification packet on the network, or does it rely on the OS or
browser software to do this for it? If the latter (which seems
much, much more likely than the former) then what reasons do Micro-
soft, Be, and Netscape have to co-operate?
>Will people be able to see the ID numbers of their own chips, to
>ensure they aren't buying stolen property?
Isn't this, again, a software issue rather than hardware? If the
CPUID instruction is available in the user protection ring, then any
teenage programmer could write a three-line C program that displays
it. I'm sure that in a matter of weeks, someone will slap a GUI on
top of that three-line program, put it in a glitzy box, and sell it
for $40. (During the christmas holidays I noticed someone selling a
utility which overwrites files before deleting them for about $40.
>From now on, *nothing* will surprise me.)
>What guarantee is there that browser makers will abide by this scheme,
>and not also give out unfiltered Pentium III IDs - or, for that
>matter, any other information, such as the ID numbers of plug-and-play
>PCI cards, someone having claimed they have serial numbers (yes, there
>are ID numbers that identify the make and model, but I fail to see the
>relevance of a _serial_ number to plug-and-play...)?
If the CPUID instruction just puts a value in a register, then
there's nothing at all stopping someone with access to browser source
code (eg Netscape, lynx, etc) from writing a CPU ID network spoofer.
It would be trivial.
The only way I see to guarantee this will not happen is if Intel
builds RSA encryption firmware into the PIII, makes the public keys
for all CPU's available to web server owners, and makes the CPUID
instruction put an encrypted timestamp into the register instead of
a never-changing ID number. Then the best a spoofer could do would
be to use logic probes to determine the private key of a PIII and
use that in their spoofing software (on any computer).
>3) If the instruction to return ID number is publicly known, then a
>browser maker can choose, or not choose, to use the Intel scheme for
>providing only a hash of the ID number.
There is no way to hide this information. The instruction will
be known within weeks, at most, of the PIII's hitting the shelves.
>At first, this makes the relevance of "tamper-resistant software" seem
>limited. If there is a hash scheme involved, then the original ID
>number is not recoverable, from any correct implementation of the hash
>scheme. Normally, web sites can't rewrite the browser on my computer.
>
>But then I see what is going on.
>
>The software is tamper resistant to prevent ID number spoofing.
>
>The ID number on the chip is just a serial number, with no signature
>by Intel, just as Bruce said.
>
>But a web site _can_ get a guarantee that the ID number is not spoofed
>- _if_ they accept getting only a personal hash of the ID number, to
>protect user privacy.
>
>Because the software is protected against tampering _by the user_. So
>it will only take your real Pentium III ID number, hash it with the
>Intel-signed web site identifier of the web site you're visiting, and
>give them a personal identifier that can't be tracked but can't be
>forged.
A spoofer can still spoof a known PIII's ID number on any computer.
-- TTK
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Spread Spectrum
Date: Sun, 31 Jan 1999 04:14:18 GMT
[EMAIL PROTECTED] wrote:
> >> >> Title is The Bug Book and publisher is
> >> >> Paladin Press in Boulder Colorado.
If you don't mention PGPfone (or Nautilus, another freeware
secure phone) you will be negligent.
PGPfone will work modem-to-modem (ie, dial up then go secure
on the same line) as well as IP to IP.
Say hi to Uncle Fester.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
