Cryptography-Digest Digest #114, Volume #9 Sat, 20 Feb 99 19:13:04 EST
Contents:
Re: New high-security 56-bit DES: Less-DES ([EMAIL PROTECTED])
Re: Looking for proof on whitening (Michael Sierchio)
Re: Randomness of coin flips ("Douglas A. Gwyn")
Re: True Randomness ("Douglas A. Gwyn")
Re: Block ciphers vs Stream Ciphers ("Douglas A. Gwyn")
QDPGP 2.60 ([EMAIL PROTECTED])
16 bit TwoFish ([EMAIL PROTECTED])
Re: Randomness of coin flips ("Douglas A. Gwyn")
Re: True Randomness ("Douglas A. Gwyn")
Re: Randomness of coin flips ("Douglas A. Gwyn")
Re: Decoding messages from ETI. ("Douglas A. Gwyn")
Scramdisk File (Gregg Berkholtz)
Re: Randomness of coin flips ("Douglas A. Gwyn")
Re: Naval Enigma - Extra rotor stepping an advantage? ("Douglas A. Gwyn")
Re: Randomness of coin flips ("Douglas A. Gwyn")
Re: Where to publish hashes? ("lyal collins")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New high-security 56-bit DES: Less-DES
Date: Sat, 20 Feb 1999 21:09:56 GMT
In article <[EMAIL PROTECTED]>,
Bryan Olson <[EMAIL PROTECTED]> wrote:
>
> [EMAIL PROTECTED] wrote:
> >
...
> > For example, in one of your last msgs you again claimed the impossible:
> >
> > |The unicity distance of English without any key is zero.
> >
> > and then you proceeded to "prove" it -- which of course would imply that any
> > English message is unambiguously known before being even written! As I
> > pointed out yesterday.
...
> You say that a zero unicity distance would mean a message is known
> before it's written. Does that mean a unicity distance of 8 means
> any message is known after the first 8 letters are written?
Yes, but pls exchange "intercepted" for "written" when the unicity > 0, and
do NOT use the word "distance" since it is NOT a "distance" as I have
commented before and in the paper. My comment that a zero unicity for English
"would imply that any English message is unambiguously known before being
even written" is however correct because zero unicity precludes transmission
or even writing it out as I counter-exemplified -- in other words, if I would
need to know zero letters from you in order to decipher your message then I
would not need you to even write anything down, much less send to me.
To be clear, the situation is different for n>0 -- I need to intercept those
letters. So, I agree that:
"A unicity of 8 means that any message is known after the first 8 letters are
intercepted."
And ... that is why it is useful -- you know what is the *least* amount of
letters (8 in this case) that you need to intercept and lug around in your
attack calculations in order to break the cipher and determine its
secret-key. Conversely, as a designer, you know what you can always slip
under a brute-force decryption attack that can try out all keys -- in this
case, 7 letters at most.
Note however two important points which are often confusing and confused in
Shannon's approach:
1. the amount of ambiguity or even obscurity within Shannon's unicity is left
unspecified. You only know that the attacker cannot decide *what* is the
correct message -- when the message has a number of letters less than the
unicity. But, the attacker may have an ambiguity of only 2 messages, with
zero obscurity (ie, the two possibilities are perfectly discernible and
intelligible). To deal with this issue, more formalism is needed -- see
htpp://www.mcg.org.br/unicity.htm#6 -- and one can for example write
mathematical expressions for the "maximum amount L of intercepted plaintext
that gives at least M expected false decipherments", which can be very useful
as an *added* design criterium for security.
2. the amount of work "to know" is also left unspecified in Shannon's
formalism, which concerns itself with an attacker of unlimited resources --
and so qualifies the "is known" above as a theoretical assertion irrespective
of any practical limit with a specific attack procedure (such as the amount
of matter in the Universe). This is useful also because it tells me what I
may expect in a worse-case limit if a better attack procedure is used (or,
found in the future), which requires less resources -- enough to be
practically used. To reduce the amount of work "to know" the attacker can of
course intercept more letters than the unicity limit, can plant
known-plaintext in order to reduce unicity (since it reduces message
entropy), can use differential cryptanalysis over a large number of messages,
etc. -- but all these techniques will fail to produce a unique solution if
the unicity (even when reduced by known-plaintext) is not reached.
Cheers,
Ed Gerck
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: Looking for proof on whitening
Date: Sat, 20 Feb 1999 13:36:12 -0800
Reply-To: [EMAIL PROTECTED]
Sandy Harris wrote:
> A proof that this makes brute force search harder by
> 2**(2N) is trivial. If the attack is to try all possible keys
> (which brute force is, by definition)
Not quite -- a brute force search stops when a key is found.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Randomness of coin flips
Date: Sat, 20 Feb 1999 21:51:58 GMT
[EMAIL PROTECTED] wrote:
> I remember reading an interesting paper years ago on coin flips. IIRC if a
> series of coin flips become biased one way or the other (ie: more heads
> than tails) the more skewed the series became the less likely it was to
> return to a 50-50 series and was more likely to become more biased.
Idealized coin-flipping is a "one-dimensional random walk".
In 1921 Pólya showed for random walks (on orthogonal lattices) in
1 and 2 dimensions that the probability of returning to the origin
is exactly 1, but in higher dimensions it is less than 1.
Later it was shown that the probability is just over 0.34 for
3 dimensions and about 0.20 for 4 dimensions.
(Probability 1 doesn't mean that a nonreturning random walk
can't happen, just that the set of nonreturning walks is a set of
measure zero with respect to the set of all possible walks.)
Now, if there is *any* inherent bias in the elementary flip
event (i.e., P(head)!=0.5), then the probability of return to
the origin is less than 1 in all dimensions from 1 on up.
The "bias" would be on the elementary event, not on the series.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness
Date: Sat, 20 Feb 1999 22:15:56 GMT
"R. Knauer" wrote:
> >For example, one can compare the likelihood of the observed
> >sequence for the true-random model versus the MLE HMM model.
> Please, spare us the obscure acronyms.
They aren't obscure to people who work in the field.
MLE = maximum-likelihood estimation
HMM = hidden Markov model
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Block ciphers vs Stream Ciphers
Date: Sat, 20 Feb 1999 22:30:21 GMT
[EMAIL PROTECTED] wrote:
> <[EMAIL PROTECTED]> wrote:
> > But how could I implement CBC mode in a stream cipher?
> Why do you want to? The purpose of CBC is to cover up patterns in the
> plaintext [foiling code-book collection and/or traffic analysis] -- patterns
> which will be covered up just fine with a stream cipher worthy of the name.
Indeed.
In response to several questions like this:
One can simulate the most fundamental, "codebook" mode of a block
cipher using a stream cipher very simply, by generating each byte
of the output block as the "next" byte in a stream whose input is
the corresponding byte of the input block. Then CBC mode can be
implemented around the basic codebook function as usual.
Before anybody says that that is not as secure as a block cipher
of the same size, consider: the "diffusion" of input bits occurs
in a stream cipher also, since it has lots of internal state
(if it is any good). It's just done in a different manner.
------------------------------
From: [EMAIL PROTECTED]
Subject: QDPGP 2.60
Date: Sat, 20 Feb 1999 22:18:47 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
FYI
QDPGP version 2.60
(a PGP plugin for Pegasus Mail [Win32])
http://community.wow.net/grt/qdpgp.html
Freeware (411 KB)
Added in this version:
- - Use of the anti-TEMPEST Secure Viewer
- - Resource files for the Portugese language
- - Optional use of native UI dialogs (all of which use the secure
memory locking drivers) to bypass automatic key selection
- - Various bug fixes
Please let me know of any bugs or problems
Gerard R Thomas
Port of Spain, Trinidad and Tobago
mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED]
PGP Key IDs: RSA:0x9DBCDE7D DH/DSS:0xFF7155A2
=====BEGIN PGP SIGNATURE=====
Version: PGP Personal Privacy 6.0.2
Comment: ...
iQA/AwUBNs80K1s8IWX/cVWiEQIQRwCghtCmavWMfUctX/rXiQAqm0z7NdwAnA9F
t3Zv4cPGjJYB/RA6CCEnO6bF
=LxPD
=====END PGP SIGNATURE=====
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: 16 bit TwoFish
Date: Sat, 20 Feb 1999 22:28:11 GMT
Has anyone here compiled the TwoFish (optimised) code
for 16 bit Windows ?
If so, were there any problems ? What compiler did you use ?
TIA
Gerard R Thomas
Port of Spain, Trinidad and Tobago
mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED]
PGP Key IDs: RSA:0x9DBCDE7D DH/DSS:0xFF7155A2
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Randomness of coin flips
Date: Sat, 20 Feb 1999 21:55:41 GMT
"R. Knauer" wrote:
> There are many comments about random sequences in Li & Vitanyi's book
> "But we cannot assert a *certainty* about a particular number n of
> throws, such as 'the proportion of heads will be p +/- eps for large
> enough n (with eps depending on n)'. We can at best say 'the
> proportion will lie between p +/- eps with at least such and such
> probability (depending on eps and n0) whenever n > n0'. But now we
> have defined probability in an obviously circular fashion."
Which is why any decent treatise on probability does not treat the
"limiting frequency" definition of probability as fundamental.
The "law of large numbers" can be proved without assuming it,
using, e.g., a Bayesian approach to probability.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness
Date: Sat, 20 Feb 1999 22:48:47 GMT
"R. Knauer" wrote:
> ... It is Quantum Mechanics that proves that certain process are
> totally random, ...
Quantum theory doesn't "prove" the randomness; rather, in most
formulations of the theory, the fundamental random nature of
certain elementary phenomena is *assumed*. The undeniable
success of the theory doesn't prove its axioms, as it is
conceivable that some alternate set of axioms (not including
any fundamental randomness assumption) might yield equally good
results.
It is sometimes said that Bell, Aspect, et al. have ruled out
the possibility of any "deterministic" alternative to classical
quantum theory, but that's highly debatable (not in *this*
newsgroup, please!).
One thing anyone resorting to "quantum equals random" needs
to be aware of: The fundamental "randomness" in quantum theory
is *of a different nature* than the probabilistic sense.
This can be seen in the superposition principle, which applies
probabilistic-like computations to "amplitudes" having complex
values, the *norm* of which are interpreted as probabilities.
If you combine the *norms* with probabilistic-like computations,
you get the wrong answer for quantum phenonema.
So if you want to talk about conventional probabilities,
it is best to leave quantum theory out of the discussion.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Randomness of coin flips
Date: Sat, 20 Feb 1999 22:53:15 GMT
Patrick Juola wrote:
> So I can make a statement such as "there is only one chance in 1,000
> that a uniform Bernoulli process would have produced such a skewed
> distribution" and therefore reject the hypothesis that it was
> produced by a u.B.p.
... with more than 99.9% confidence? To do this right, you should
also consider what your a priori estimate was for the process to be
uniform Bernoulli. (For example, if you *know with certainty* that
it really *is* a u.B.p., your a posteriori estimate will still be
certainty that it *is* a u.B.p.)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Decoding messages from ETI.
Date: Sat, 20 Feb 1999 22:35:04 GMT
fungus wrote:
> WhiteHat wrote:
> > I am searching for various methods of decoding/understanding a message
> > received from an extra terrestrial intelligence (if/when we receive
> > such a message). It is presumed that the ETI wants us to read the
> > message. Thus, the task of understanding the message is the task of
> > learning the "language" used to compose it (i.e. break the code of the
> > language).
> This is a bit impossible to answer, like asking what alien food would
> taste like.
No, because (as WhiteHat stipulates), the message has to be designed
to be understandable by alien (meaning Earth) intelligence.
> A few years back, NASA sent a message for extraterrestrials to decipher.
> IIRC, the message was a sequence of pulses. If you arranged the pulses
> into a grid, you got a two colour image. The width and height of the
> image were prime numbers so, based on the total number of pulses, there
> was only one way to create the grid. I can't remember what the image
> was but it was pretty simple, just enough to let them know we were
> intelligent.
There is an example of this sort of thing in both of the two references
I posted a short while ago.
------------------------------
From: Gregg Berkholtz <[EMAIL PROTECTED]>
Subject: Scramdisk File
Date: Sat, 20 Feb 1999 15:14:07 -0800
I am having difficulty mounting my scramdisk file.
It worked fine yesterday (multiple mount/dismounts) I have the password
written down (kept in wallet until I remember it, then it will be eaten)
and have tried entering it multiple times with no success. I have also
tried variations of the password.
I can mount my other files on this disk but this one does not mount.
The disk is a single FAT32 Partition on a Seagate 10.6 Gb running Win95.
The file I am trying to mount was created with 1024Kb specfied as the
size.
Life just plain sucks sometimes. I just got my tape backup today and I
have a customer waiting on a final copy of a database program. :-(
Any help is GREATLY appreciated!
Gregg Berkholtz
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Randomness of coin flips
Date: Sat, 20 Feb 1999 23:20:52 GMT
"R. Knauer" wrote:
> It's the "nearly certain" that bothers me.
> I understand the law of large numbers but I do not agree with the
> interpretation that tries to extrapolate probability into certainty,
> even "near certainty".
It's the difference between "almost everywhere" and "everywhere",
which is an essential concept in integration theory etc. The basic
idea is that the exceptions are outnumbered by the non-exceptions,
with an *infinite* number of non-exceptions for every exception.
(To make this more precise we have to turn to something like measure
theory.) One way of looking at the law of large numbers is that
vastly many more cases are near to the "expected" value than are
far from the expected value, and the vastness becomes utterly
overwhelming as the iterated experiment continues. A striking
exception is always *possible*, but exceedingly unlikely in the
long run. (Properties of asymptotic limits are central to analysis,
a.k.a. calculus.)
> The ensemble approach doesn't even work in Physics - there are no
> examples of a Maxwell Boltzmann gas, for example. And just because
> there was only one unicorn spotted in a herd of thousands of horses
> does not mean that unicorns do not exist.
Maxwell-Boltzmann statistics typify a particular *model*. While
it is true that there are no *perfectly* ideal gasses, many gasses
are practically ideal over a vast fraction of phase space attainable
in laboratories, so the model has great predictive and engineering
value.
As to unicorns, if one unicorn was definitely spotted then unicorns
do exist. I think you meant, if *no* unicorn was spotted in a large
herd, that doesn't mean that unicorns don't exist. While that is
true, if the herd was a good random sample then we can estimate the
likelihoods and quantities of unobserved breeds, including unicorns.
We can also compute the weight of evidence against the hypothesis
(that unicorns exist) provided by the experiment.
> Probability is a theoretical concept, and Kolmogorov among others
> questioned its applicability to the real world.
I think you have mischaracterized Kolmogorov's position.
There are certainly issues of how to properly apply probability
theory, just as there are issues of how to properly apply any theory
or model. However, many of us successfully apply probability theory
in our daily work. For example, some of us use it to crack ciphers.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Naval Enigma - Extra rotor stepping an advantage?
Date: Sat, 20 Feb 1999 23:26:10 GMT
John Halliwell wrote:
> My question, did this difference in the stepping ultimately make it
> easier or harder to break?
The real problem with the German Naval Enigma was that it took more
time on more Bombes, due to a larger number of possible wheel orders.
There are other, non-Bombe-oriented methods of attack that work
about as well for the Naval Enigma as for other variations.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Randomness of coin flips
Date: Sat, 20 Feb 1999 23:32:13 GMT
"R. Knauer" wrote:
> In fact a Perfect Circle cannot even exist mathematically, since
> there are infinitely many points on the locus that are uncomputable.
Wrong again. Circles don't intrinsically have anything to do
with representations of their points in a coordinate system.
Anyway, mathematics != "recursively enumerable function theory".
------------------------------
From: "lyal collins" <[EMAIL PROTECTED]>
Subject: Re: Where to publish hashes?
Date: Sun, 21 Feb 1999 10:20:21 +1100
How about a safety deposit box, with 2 person signatures for access, that
contains either electronic media, printed hashes, or both.
Lyal
>dan schwartz wrote:
>>
>> fungus ([EMAIL PROTECTED]) wrote:
>>
>> : The message you just posted will be stored indefinitely, for free,
>> : at http://www.dejanews.com/
>>
>> Thanks for the response. I'm looking for a solution that could
>> ultimately be used as convincing legal evidence. For that purpose,
>> I would consider dejanews marginal in terms of both permanence and
>> resistance to manipulation.
>>
>
>If it needs to stand up in a court of law then you need to use notarys
>and lawyers, I don't see any way around this. You could combine this
>with some public method, but ultimately you need legal people.
>
>After all, if what you're trying to achieve was easy, the notarys would
>be out of business....right?
>
>
>
>--
><\___/>
>/ O O \
>\_____/ FTB.
------------------------------
** 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
******************************
