Cryptography-Digest Digest #40, Volume #9 Fri, 5 Feb 99 15:13:03 EST
Contents:
Untrusted function evaluation (Mark 'Mad Dog' Spinelli)
Re: *** Where Does The Randomness Come From ?!? *** ("PAC")
Re: Metaphysics Of Randomness ("John Feth")
Re: XOR encryption... (Jim Gillogly)
Re: *** Where Does The Randomness Come From ?!? *** (Seisei Yamaguchi)
cryptology in physics (David Leuenberger)
Re: Threat Models: When You Can't Use a One-Time Pad (Jim Gillogly)
Re: I hate to bring up PRNGs again... (R. Knauer)
Rational points on a curve (Jayant Shukla)
Re: _____FAQ list for this newsgroup_____ 978 (Jim
Gillogly)
Re: Metaphysics Of Randomness (R. Knauer)
Re: *** Where Does The Randomness Come From ?!? *** ([EMAIL PROTECTED])
Re: Metaphysics Of Randomness (R. Knauer)
----------------------------------------------------------------------------
From: Mark 'Mad Dog' Spinelli <[EMAIL PROTECTED]>
Subject: Untrusted function evaluation
Date: Fri, 05 Feb 1999 11:41:17 -0500
Reply-To: [EMAIL PROTECTED]
Hello all,
I'd like to solve the following problem, but I don't know where to
start.
Alice and Bob, who don't trust each other, and don't trust a third
party, would like to perform the following.
Alice is in possesion of a secret boolean function, f(p,q,r,etc). Bob
knows very little about this function. But Bob wishes to evaluate an
instance of the function without telling Alice what his arguments are,
and Alice wants to help Bob evaluate the function without telling Bob
what her function is.
For example, Alice and Bob are playing a game of Battleship. Bob wants
to attack one of Alice's square without revealing what square he is
attacking. All Alice can learn is weather Bob's attack was a hit or a
miss.
Is there an easy solution to this?
Thanks!
-Mark ([EMAIL PROTECTED])
------------------------------
From: "PAC" <[EMAIL PROTECTED]>
Crossposted-To: sci.philosophy.meta,sci.physics,sci.skeptic
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: Fri, 5 Feb 1999 09:08:42 -0800
PAC wrote in message <79e2ev$1su$[EMAIL PROTECTED]>...
>
>R. Knauer wrote in message <[EMAIL PROTECTED]>...
>
>>"The reason a number is simple is that there is a simplifying
>>algorithm that can reproduce it." That simple algorithm is the "cause"
>>of the number being simple. The fascinating thing is that this cause
>>is contained almost completely contained in the number itself.
>
>>Typically numbers of size N can be reduced by an algorithm of size
>>log2(N) + c, where c is that constant of order unity. That quantity is
>>smaller by orders of magnitude than N itself - IOW it is exponentially
>>smaller. The fact that there are very few numbers that can be
>>algorithmically reduced points to the fact that order is a rare
>>occurance in reality.
>
> Though this seems different than physical reality where through
disorder
>a more ordered state is actually occurring - when things breakdown they
>eventually breakdown to more fundamental units, normally perceived, and
>therefore more order is occurring through disorder instead of the opposite
>commonly assumed.
> But I would think that the cause of the simplicity of a number itself
>would be similar to the representation of maybe primary fundamental
>Plank-type units. How these breakdown occurs seems to be a direct result
>that mutability might occur only when relations are the simplest and at the
>most exchange oriented, i.e 1+/- 1 being the lowest form of mutability in a
>equation and the beginnings of added structure that are always brought up
or
>down through the manipulation of the fundamental (1) units that remain as a
>constant in any equation.
> The constant here being the number "1" that occurs in all calculations
>as its most fundamental part and when all equations are reduced to it
>creating the greatest simplicity of like parts. 2 x 2 must be reduced to
>1+1+1+1 to see the interactions and the algorithm of the greater complete
of
>2 x 2. The number "1" must be in every occurrence (fractions also being a
>direct representation of its necessity) at every instance for any equation
>to occur, hence both the constant and its most fundamental unit.
> Here ordered simplicity of like parts are at the foundation of
>mathematics as well as maybe the universe itself as it relates to a closed
>"1" thing. "1" thing is the only thing contained to itself and not able to
>be dissolved except to its own terminology ALA fractions, therefore most
>fundamental and where everything proceeds to a most indissoluble/ordered
>unity.
> So in this case the cause of a number being simple would be its direct
>representation to its fundamental unit/constant "1" as maybe it relates to
>the entire grand reality and maybe its reflection in fundamental units.
>
I'm surprised that I don't get blasted for this one, but this is just
based on the idea that objects are comparative not by being dissimilar, but
of basic similarity that is due to innate philosophical purity of LCD-type
factors based on wholeness, ultimate mutability, fundamental particles and
the corresponding closed nature of the universe itself.
Most mathematicians living out of the middle ages I guess might assume
more that similarity both in nature and in math is based more not on
similarity due to objects being the same, therefore having to get more into
innate stuff, but to those objects being different, being not what they are.
In this case basing arithmetic on the number �0" radiating out as all
numbers being different from it, and then though the number �1" can�t be
denied in mathematics for its unique relations; in physics and such dealing
with order/disorder can be most easily resolved by what things aren�t. Then
algorithms deciding to the least factor of why something appears out of
place would be brought more into play, not as finding similarities based on
ultimate mutability, but more in finding the algorithm that most satisfies
the object has it is recursively pared down to size to find out what it most
resembles by being what it isn�t; basing itself on �0" from the number
scale.
Or something like that,
Phil C.
------------------------------
From: "John Feth" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: 5 Feb 1999 17:12:19 GMT
R. Knauer <[EMAIL PROTECTED]> wrote in article
<[EMAIL PROTECTED]>...
> On 3 Feb 1999 09:23:12 -0500, [EMAIL PROTECTED] (Patrick Juola)
> wrote:
>
> >>I'm going to remind you just one more time
> >>that dividing random strings into True Random Numbers and Pseudo Random
> >>Numbers creates a distinction without a difference since no test exists
to
> >>distinguish them.
>
> >It's not a distinction without a difference. You're just doing the
> >wrong test. There's a test to distinguish Chryslers from Fords.
> >But it's not a test you're going to perform by measuring the gas
mileage.
Snip
> All we hear in this regard is that there are these wonderful
> statistical tests out there that anyone can use easily that perform
> all this wonderful mathematical magic, but when challenged to produce
> these magical tests and defend them as being so wonderful, we never
> see any presented.
>
> That smacks of Snake Oil.
>
> Bob Knauer
Holy Smokes Bob! Put that Snake Oil away and learn about the Allan
Deviation from:
D. W. Allan "The Measurement of Frequency and Frequency Stability of
Precision Oscillators" NBS (now NIST) Tech Note 669 (1975) Available from
NIST, Time and Frequency Division Boulder, Colorado 80303
D. A. Howe, D. W. Allan, J. A. Barnes "Properties of Oscillator Signals and
Measurement Methods" Available as above
Barnes et al "Characterization of Frequency Stability" NBS Tech Note 394
(1970) Available as above
D. A. Howe "Frequency Domain Stability Measurements: A Tutorial
Introduction" NBS Tech Note 679 Available as above
D. B. Sullivan et al "Characterization of Clocks and Oscillators" NIST Tech
Note1337 (1990) Available as above
If you want this want the mechanics of the analysis to be easy, try the
software program Stable 32, Available from Hamilton Technical Services, 195
Woodbury Street, S. Hamilton, MA 01982 Phone 978-468-3703
By the way Bob, given your zeal for "crypto-grade" random numbers, I'm
surprised you didn't leap at the well known encryption algorithm below. I
believe it's well established that if you dispose of p, q, p-1, q-1, and m
after use, (keeping p*q and e, of course) c becomes one of your "provably
secure crypto grade" random strings.
Find two large primes, p and q such that the product is
1500 digits long. Find a number, e, that does not divide the product
(p-1)*(q-1) evenly. Now we're in business. Generate your first random
string, c, as
c=mod(m^e, p*q)
by choosing m to be a non-zero number 1490 digits long. Change a single
digit in m and you have an entirely different string c. You can continue
in this manner and concatenate the subsequent strings to create an even
larger random string.
Regards,
John Feth
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: XOR encryption...
Date: Fri, 05 Feb 1999 09:17:24 -0800
Reply-To: [EMAIL PROTECTED]
Binder Edgar wrote:
> I know that XOR-ing the password trough a file is verry weak
> encryption. I even wrote a program the breaks XOR encryption on files
> with low entropy, and I really don't know much about cryptanalisis.
> My question : How safe is XOR encryption on files with verry high
> entropy ? I plan to use a XOR encryptor with a Burrows-Wheeler transform
> based compressor, because XOR-ing is pretty fast, and BWT does really a
> good job at randomizing because it doesn't start with low entropy like
> LZ-based algorithm do. Thanks for your answer...
As I understand the BWT, it doesn't have compression built in, but
is a front-end sorting algorithm that produces text to which
some other [set of?] compressor[s?] is applied, and that it works
on individual blocks of input text. I suspect the answer will lie
in the details of what compressors you're applying to the output
and the block size you choose for the BWT. If the latter is too
small you'll run into known plaintext attacks, where (e.g.) the
attacker guesses that your plaintext starts with the same three
library functions that the previous version of the product used.
Are you planning to simply use the output of bzip2 as the first
stage? If so, you'd better know all about its block assumptions
and what it's using to compress the BWT output.
In any case, since you say "password", it could be subject to a
dictionary attack. For any data that's worth anything, the
cryptanalyst will have a way to test whether the resulting
plaintext is meaningful, so trying lots of possible passwords
and decompressing the result should result in something testable.
For some compression algorithms, trying to decompress garbage
will result in errors or overflows -- e.g. the next character is
marked as 47121 bits long, when the maximum for this implementation
is 14 bits per character; or for a system with a maximum of 16 bits
per character you get a long run of 15- and 16-bit characters. This
can help eliminate faulty keys rapidly without having to test the
plaintext.
ARJ used your proposed strategy for encryption, and I found it pretty
challenging to do a single file in an archive, since the compression
was quite good and there wasn't much statistical leverage for an
analytical attack. I think Paul Kocher solved one or more of these
individual ARJ files. Still, something messier than a straight XOR
with your password will give you better security.
In general, a no-hints compression procedure is a good first step
before encryption, if only to minimize transmission bandwidth...
but you may as well use a good encryption system at that point.
RC4 won't take much longer to run than your XOR, and since you're
taking the time to compress it, you're not all that worried about
nibbling every microsecond off the processing time.
--
Jim Gillogly
Trewesday, 15 Solmath S.R. 1999, 16:40
12.19.5.16.10, 4 Oc 3 Pax, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Seisei Yamaguchi)
Crossposted-To: sci.skeptic,sci.philosophy.meta
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: 5 Feb 1999 17:18:53 GMT
Hi, this is Seisei.
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 2 Feb 1999 18:51:28 GMT, [EMAIL PROTECTED] (Seisei Yamaguchi) wrote:
>
>>Randomness and unforeseeableness are not identical.
>Why not?
Randomness:
No way to processing.
And, cannot create the way, forever.
Unforeseeableness:
From not enough knowledge ---and/or speed--- to processing it.
AD0019th_century's and AD0020th_century's are not same.
--
Seisei Yamaguchi (name( first( $B@D@1(B ), last( $B;38}(B ) ))
http://hp.vector.co.jp/authors/VA010205/
Text imparts all
$B:#F|$O;D$j$N?M@8$N:G=i$NF|(B ---from BH90210
I want your indication ($B7/$N0U8+$r$-$3$&(B. $B%,%D%s$H8@$C$F$/$l(B)
I want to hug with you each other
This message is copylefted (see GPL)
68 lovers capable
------------------------------
Date: Fri, 05 Feb 1999 18:19:24 -0800
From: David Leuenberger <[EMAIL PROTECTED]>
Subject: cryptology in physics
Hi!
Cryptology is a discipline taking place in an abstract number place
(it's a mathematical discipline)
I wonder if there are analogous mechanism to the Alice-Bob-Eve-pattern,
to one-way-functions and to zero-knowledge-protocols in general physics,
biological systems (DNA?), ...
Thanks for any reply
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Threat Models: When You Can't Use a One-Time Pad
Date: Fri, 05 Feb 1999 09:31:56 -0800
Reply-To: [EMAIL PROTECTED]
While in general I agree with the analysis, I'll suggest one quibble...
don't want to be left out of the feeding frenzy.
John Savard wrote:
> If I keep the one-time pad on a floppy in a safe: my security is the
> same as if I kept my file, unencrypted, on a floppy in that safe. And
> the convenience of my access to that file is exactly the same too.
You might want to do this for plausible deniability. The Mounties
break down your door and find your encrypted file and the OTP program
that will decrypt it. They look around for a suitable CD and see only
your execrable taste in heavy metal (totally unsuitable for a OTP key,
as we've observed time and again). They demand the key. You produce
the CD from your safe, and sure enough it decrypts the offending file,
which is revealed to be a clip from the beginning of the pirated work
print of The Adventures of Buckaroo Banzai Across the Eighth Dimension
revealing Jamie Lee Curtis as the eponymous hero's mother. After they
leave in embarrassed disarray, you pull down your copy of "Scrambled
Debutante: Cuisenart Madness", decrypt, and resume your planning for
world domination.
--
Jim Gillogly
Trewesday, 15 Solmath S.R. 1999, 17:23
12.19.5.16.10, 4 Oc 3 Pax, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: I hate to bring up PRNGs again...
Date: Fri, 05 Feb 1999 17:22:27 GMT
Reply-To: [EMAIL PROTECTED]
On 5 Feb 99 03:50:09 GMT, [EMAIL PROTECTED] () wrote:
>Oh, very definitely you can, since all strong ciphers are built out of
>small steps that are not strong in themselves.
I challenge that statement on the grounds that crypto-grade security
must have at least one intinsically random source in those steps. IOW,
confusion does not imply crypto-grade randomness. It takes
indeterminancy to create crypto-grade randomness.
You might respond that there can be work-effort security in
confusion-based ciphers, and I would agree with you in principle. The
problem I have with that, however, is that there is always the
possibility that a cryptanalyst can discover a method of decryption
that circumvents the confusion - and you can never prove that he
cannot.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (Jayant Shukla)
Subject: Rational points on a curve
Date: 5 Feb 1999 18:34:23 GMT
Hi,
Is there an easy way to find integer points on
the curve y^2 = a x^2 + b x + c? i.e. both x and y
are integers. The constants a, b, and c are integers
as well.
regards,
Jayant
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Crossposted-To: news.admin.net-abuse.usenet
Subject: Re: _____FAQ list for this newsgroup_____ 978
Date: Fri, 05 Feb 1999 11:25:24 -0800
Reply-To: [EMAIL PROTECTED]
John Savard wrote:
> >http://news-faqlist.696.net
> >hgmmqirqdfnzospylcwpkxmrxjlzju
> zbjbxodxczjwlngydurcwsuhpmtskz
> ujpijidrsihithkdxjivohmgjlpxcz
> vwtpmwuovmmllwwuglrwngrcmtciud
> jqmiijzwfcvqlgxtfwqenkxdoxrybt
> kfebdylp
Hmm. A frequency count shows there's not an 'a' in the
lot. Otherwise it's pretty flat, with maybe 'x' getting
a few more than you'd expect. No repeats worth noticing.
Not simple sub or a short periodic or a digraphic. I'm
guessing garbage.
--
Jim Gillogly
Trewesday, 15 Solmath S.R. 1999, 19:22
12.19.5.16.10, 4 Oc 3 Pax, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Fri, 05 Feb 1999 20:04:17 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 05 Feb 1999 08:12:26 -0700, "Tony T. Warnock"
<[EMAIL PROTECTED]> wrote:
>My example of Champernowne's number shows that a
>computation that provable generates all k-bit sequences with the proper
>frequency (1/2^k) cannot be random because some million bit subsequences
>cannot be generated in the first million bits.
Champernowne's number is not normal in base 2, only in base 10.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.skeptic,sci.philosophy.meta
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: Fri, 05 Feb 1999 18:19:56 GMT
In article <79acfa$351$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Patrick Juola) wrote:
> In article <79ab94$34b$[EMAIL PROTECTED]>, PAC <[EMAIL PROTECTED]> wrote:
> > Though viewer perspective is part of the problem with randomness,
> >specially dealing with more radical theories I guess, still more implicit
> >that randomness\determinism is more of a causal question than that of
> >perspective: something random/determined would have the same status
> >regardless of viewer perspective, something ordered/disorder not so.
>
> That's the basic problem relative to cryptography -- a message that
> *appears* disordered to me may simply be because I haven't analyzed
> it deeply (or intelligently) enough.
>
> But proof by lack-of-imagination doesn't fly philosophically, and
> is not particularly valued in the Real World, either.
>
> -kitten
>
If you are handed a message without having *any* idea of the underlying
language or cryptograhic system, the number of possible kinds of hidden order
are as near to infinite as makes no odds. So it's not just lack of
imagination. The process of trying to decipher a message by going through
every possible variant of interpretation is not guaranteed to stop -- so
hidden order cannot necessarily be disinguished from no order.
Regards,
Peter D Jones
Brighton, UK
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Fri, 05 Feb 1999 20:07:49 GMT
Reply-To: [EMAIL PROTECTED]
On 5 Feb 1999 17:12:19 GMT, "John Feth" <[EMAIL PROTECTED]>
wrote:
>Holy Smokes Bob! Put that Snake Oil away and learn about the Allan
>Deviation from:
Why don't you explain it?
>By the way Bob, given your zeal for "crypto-grade" random numbers, I'm
>surprised you didn't leap at the well known encryption algorithm below. I
>believe it's well established that if you dispose of p, q, p-1, q-1, and m
>after use, (keeping p*q and e, of course) c becomes one of your "provably
>secure crypto grade" random strings.
Proveably secure, eh? A crypto-grade random number being generated by
an algorithmic process, eh?
Von Neumann must be spinning in his grave right now.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
** 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
******************************
