Cryptography-Digest Digest #491, Volume #12 Sun, 20 Aug 00 16:13:00 EDT
Contents:
Re: 215 Hz five-qubit quantum processor ([EMAIL PROTECTED])
Re: Stream Cipher/PRBG idea. ("Scott Fluhrer")
Re: 215 Hz five-qubit quantum processor (Vernon Schryver)
Re: Question on Decorelation Theory ([EMAIL PROTECTED])
Re: Breaking Simple XOR Encryption ("Douglas A. Gwyn")
Re: News re annotated version of "Fire Upon the Deep" (phil hunt)
Re: OTP using BBS generator? ("Douglas A. Gwyn")
Re: 215 Hz five-qubit quantum processor ("Douglas A. Gwyn")
Re: How Many? (John Savard)
Re: How Many? ("Paul Pires")
Re: OTP using BBS generator? (Mok-Kong Shen)
Re: How Many? ("John A. Malley")
----------------------------------------------------------------------------
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
From: [EMAIL PROTECTED]
Date: Sun, 20 Aug 2000 14:23:28 GMT
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>Maynard Handley wrote:
>> I would contend that what's interesting about Godel is more that certain
>> things ARE true, but can't be PROVED true. The standard example is always,
>> of course, Goldbach's conjecture ...
>
>Actually I don't think that is a good example, because our intuition
>is that its proof should be feasible (if it's indeed true). The
>kind of "unprovable truths" we are sure are Godelian are ones that
>are carefully engineered to be self-referential in a suitable coding,
>but they aren't very interesting compared to statements like
>Goldbach's conjecture. Using Godel incompleteness as a possible
>reason why we haven't yet proved some possible theorem seems to be
>a cop-out (a lame excuse).
Closely related to Goedel's work is the notion of undecidabilty
(within a system). This is a not-uncommon status for a theorem to
wind up in. Such theorems are neither true nor false, but either the
truth or falsehood of the theorem may be assumed as an axiom.
I think Goedel may have been the first to discover and prove
the undecidability of a theorem -- didn't he do the cardinality of the
continuum?
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Stream Cipher/PRBG idea.
Date: Sat, 19 Aug 2000 23:11:05 -0700
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I've a new idea for a stream cipher (Psuedo Random Bit Generator).
>
> L : 4 integers, { 211, 223, 227, 229 }
> N : 4 bitstrings, which can be considered constants, or long term keys.
> N[i] : a string of L[i] bits
> N[i][j] : the jth bit of N[i]
> K : the [short term] key.
> K[i] : a number in the range 0..(L[i]-1)
>
> X : the keystream / psuedo-random-bit-stream
> X[j] = sum( i=0..3, N[i][ (j+K[i]) mod L[i] ] ) mod 2
>
> I realize that the [short term] key space is too small to avoid being
> brute forced, but I can't see any other real flaws in the system --
> especially since N is much too large to avoid being brute forced.
David Wagner has already pointed out that it can be broken with
211+223+227+229 bits of keystream. Still, I will go through your specific
questions:
>
> Assume the attacker knows L for all the following questions.
>
> If the attacker knows N and some part of X for some message, what
> methods other than brute force allow him to find K, and how much X is
> needed?
Well, if you define:
Z[i][j] = N[i][j mod L[i]]
Then, the attacker can form the equation:
X[j] ^ N[j+K[0]] ^ N[j+K[1]] = N[j+K[2]] ^ N[j+K[3]]
The attacker can list the possible left side values for all possible values
of K[0] and K[1], and the possible right side values for all possible values
of K[2] and K[3], and then look for duplicate values within the two lists.
This gives a way to find the short term key with O(2**17) operations and
perhaps 32 keystream outputs.
>
> If the attacker knows K and some part of X for some messages, how can he
> find N? How long does X from those messages have to be?
Gaussian elimination -- the equations are linear. It takes 211+223+227+229
bits, plus possibly a few more if the equations are not independant (which
they will be if the keystream is from a contiguous section of the same K,
but might not be otherwise)
>
> If the attacker has X for multiple messages, but not N or K, what can he
> do? How much X is needed to perform any attack?
Again, he can rederive an equivilant (that is, produces the same keystream
output) N and K with 211+223+227+229 keystream outputs in O(2**24) time,
assuming they are all from a single K (again, invoking Gaussian
elimination).
>
> Assuming that N has (sum(i=0..3,L[i])) bits of entropy, how much X is
> needed to distinguish from random?
There exists a polytime algorithm that, given 211+223+227+229+M bits, says
TRUE with probability 1 if the bits were generated by the PRBG, and says
TRUE with probability 2**-M if the bits were generated by a true random
generator.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: 20 Aug 2000 09:53:21 -0600
In article <ARRn5.6761$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
> ...
> I think Goedel may have been the first to discover and prove
>the undecidability of a theorem -- didn't he do the cardinality of the
>continuum?
If you mean the independence of the axiom of choice and the continuum
hypothesis, Goedel did prove that the continuum hypothesis is consistent
with the axiom of choice. However, it was not until 1963 that Paul J.
Cohen invented "forcing" and proved the other direction.
--
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Question on Decorelation Theory
Date: Sun, 20 Aug 2000 16:24:20 GMT
In article <8nokij$d71$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> When a function is 1-wise decorrelated such as F(x) = x + k, you need
> only one input to begin a simple attack on it.
>
> When something is pair-wise decorrelated such as F(x) = ax + b, that
> means you have to look at pairs of inputs/outputs?
Does that mean without two inputs there is no way to tell it from
random basically?
How many pairs would be needed? Is it the 1/p bound since the
differences are random?
> Then wise is F(x) = (ax + b)/c 3-wise decorrelated?
Sorry this was F(x) = (a + b)/(x + c)
Which doesn't look right anyways...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Breaking Simple XOR Encryption
Date: Sun, 20 Aug 2000 12:41:08 -0400
Simon Johnson wrote:
> Altough you are perfectly correct, You knew exactly what he meant by
> the 'XOR' system of encryption, ...
No, as a matter of fact I did not. "Simple XOR encryption" could
have involved a one-time-pad, a periodic key, or any of a number of
other variations. It is important to use proper terminology,
especially when the details matter.
------------------------------
From: [EMAIL PROTECTED] (phil hunt)
Crossposted-To: rec.arts.sf.written
Subject: Re: News re annotated version of "Fire Upon the Deep"
Date: Sun, 20 Aug 2000 16:05:36 +0100
On Sat, 19 Aug 2000 13:25:03 +0100, Stephen Kitt <[EMAIL PROTECTED]> wrote:
>On Fri, 18 Aug 2000 20:51:35 GMT, Matthew Austern <[EMAIL PROTECTED]> wrote:
>>Patrick uses a Palm Pilot. If this is released in any proprietary
>>format, I'd guess that AportisDoc would be a likely candidate.
>
>Unlikely - the format is documented, and source code that reads doc-format
>files is available. A likelier candidate for Palm release is
>peanutpress.com's format which is encrypted and better suited to books in
>the first place (and there's peanutpress.com's infrastructure and
>pre-existing publishing links, especially in the SF world); the encryption
>uses the purchaser's name and credit card number, so I can't really imagine
>people giving others copies with the necessary info to use them :-). I've
>got no idea how hard it is to crack though - probably not since plaintext is
>available and cyphertexts can be obtained in multiple versions where the
>changes are known (different name and credit card number).
I suspect it is not too hard to crack. Not being an experienced cryptanalyst,
I'm crossposting this to sci.crypt.
--
*****[ Phil Hunt ]*****
** The RIAA want to ban Napster -- so boycott the music industry! **
** Don't buy CDs during August; see http://boycott-riaa.com/ **
** Spread the word: Put this message in your sig. **
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Sun, 20 Aug 2000 12:56:21 -0400
Mok-Kong Shen wrote:
> Once again I like to stress the need of practical tests,
> which should not be simply 'exempted' by the 'fame' of
> some mathematical 'proofs' (in particular those that do
> not in fact claim perfect security on a par with the
> ideal OTP) in connection with the sources being used.
? That sounds like you're suggesting empirical tests to
check *theoretical* properties, not correct functioning
of the implementation. That could also be done
theoretically, which would give a more reliable measure
than a finite amount of testing. Of course, for many
people it might be *easier* to implement the algorithm
and run some standard tests (e.g. Diehard), but that
doesn't make it the best way to gain confidence in the
patternlessness of the output from the algorithm.
Suppose I have an ideal PRNG that passes all standard
statistical tests, and I embed it into an algorithm as
follows:
toggle = 0
forever:
pick uniform random integer P in (100,150)
generate P outputs from PRNG
output toggle
toggle = 1 - toggle
That introduces a bias that is very hard to detect unless
you suspect that an algorithm like that is being used and
devise a test specifically for that kind of bias. In fact
this sort of thing has been important in cracking some
systems in the past. (Sorry, no details.)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: Sun, 20 Aug 2000 12:58:52 -0400
Vernon Schryver wrote:
> If you mean the independence of the axiom of choice and the continuum
> hypothesis, Goedel did prove that the continuum hypothesis is consistent
> with the axiom of choice. However, it was not until 1963 that Paul J.
> Cohen invented "forcing" and proved the other direction.
And note that nobody seriously thinks that Goldbach's conjecture
could be added as an independent axiom in number theory.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: How Many?
Date: Sun, 20 Aug 2000 18:10:47 GMT
On Sun, 20 Aug 2000 15:06:42 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>I think that, when considering diffusion/confusion
>(permutation/substitution), there is the issue of
>granularity (bits, bytes, words, etc.). The two
>mechanisms need not always work at the same granularity
>and in one single algorithm different parts/levels can
>operate at different granularities.
Yes, I not only agree with that, but I think that this principle needs
to be considered explicitly. Thus, one of my three additional goals is
called 'convolution' to make this explicit. (As Terry Ritter noted,
this may not be a good name, but I could not think of a better.)
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: How Many?
Date: Sun, 20 Aug 2000 11:39:31 -0700
Warning! Just an opinion. The author has no credentials or standing to imply
that it is in any way profound.
A step sideways? A twisted mind sees procedural elements cooperating to
achieve certain effects, composed of computational elements. Talking about
XOR, S-Boxes, transposition and rotation is like carpenters describing a job
in terms of nails screws and lumber.
I see stream ciphers as a bank account. You start off with so much
principal, you acquire "interest" each iteration in the form of adding
unpredictability to the pot and you spend from the account each iteration by
using some of the hoard as a basis for encrypting. At this point the analogy
breaks down since you have to speculate what the interest rate really is and
you might not know if your vault has a hole in it, leaking out your
principal. Your guess is only confirmed if you go bankrupt. "A break".
Block ciphers are a different strategy more akin to shuffling cards to deal
a hand. It is not a good analogy since the cards are not just interleaved,
their values select other values and the split deck isn't just interleaved
but the values themselves are combined by XOR to form new cards.
It seems that qualifying the primitives used is pretty meaningless if the
operations selected for a process do not cooperate and interact in a
desirable way. It also seems that these primitives can't be seen as trivial
or potent when viewed alone. A trivial element applied at the right place in
the right process could ruin an adversary's whole day.
Warning! self-serving troll behavior.
I don't think the element list is complete. I put forward what I thought was
a new primitive that does "Ranking" (Just a weird way of doing dynamic
substitution) in my contest submission. Just because these elements might be
basic and simple, does not mean that they are easy to figure out or
recognize if stumbled upon. At least not for me.
Paul
Future Beacon <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> I don't know whether to call them principles or elements. How many
> are essential to encryption? I see transposition as a special case
> of substitution. Both binary operations and transformations could
> be viewed as look-up tables. I seem to view every element of
> encryption as look-up table formation, look-up table use or random
> number sources.
>
> Does anybody view any other principle or element as essential to
> encryption?
>
> If they are few in number, it might be instructive to study them
> rather than studying a compendium of techniques that each contain
> more than one of them.
>
>
> Jim Trek
> Future Beacon Technology
> http://eznet.net/~progress
> [EMAIL PROTECTED]
>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Sun, 20 Aug 2000 21:21:34 +0200
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > Once again I like to stress the need of practical tests,
> > which should not be simply 'exempted' by the 'fame' of
> > some mathematical 'proofs' (in particular those that do
> > not in fact claim perfect security on a par with the
> > ideal OTP) in connection with the sources being used.
>
> ? That sounds like you're suggesting empirical tests to
> check *theoretical* properties, not correct functioning
> of the implementation. That could also be done
> theoretically, which would give a more reliable measure
> than a finite amount of testing. Of course, for many
> people it might be *easier* to implement the algorithm
> and run some standard tests (e.g. Diehard), but that
> doesn't make it the best way to gain confidence in the
> patternlessness of the output from the algorithm.
>
> Suppose I have an ideal PRNG that passes all standard
> statistical tests, and I embed it into an algorithm as
> follows:
> toggle = 0
> forever:
> pick uniform random integer P in (100,150)
> generate P outputs from PRNG
> output toggle
> toggle = 1 - toggle
> That introduces a bias that is very hard to detect unless
> you suspect that an algorithm like that is being used and
> devise a test specifically for that kind of bias. In fact
> this sort of thing has been important in cracking some
> systems in the past. (Sorry, no details.)
Checking the validity of theory in practice has always
been the routine in all applied sciences, from medicine
to aerospace engineering. This is because a theory almost
without exception is based on assumptions which are
simplifications/approximations of the real world and
hence one needs to verify that the error thereby involved
is indeed negligible or tolerable. That tests are
imperfect and themselves involve the reliability/accuracy
issue is well-known but is not relevant in the present
context. Statistical tests are BTW by nature never
'perfect' (in the sense of giving absolute answers),
otherwise the term 'confidence interval' would not exist.
Some of them have better 'power' in that they are more
sensitive than the others in certain issues. It can well
be that in certain circumstances what the theory can
easily tell about the existence of some defects is not
(yet) discernable by any currently existing tests. But
this does not distract from my theme that one should
always COMPLEMENT theoretical assertions with checks
of practical nature (in our case statistical tests).
It is noteworthy that in papers in numerical mathematics,
where e.g. certain new solution methods are developed
with solid sophisticated theoretical foundations,
examples of computational results are almost invariable
given, providing confidence that the theory indeed
fulfills what has been expected of it. On the other
hand, an essential shift in the kind/nature of tests
can be observed in many fields of science and
engineering. In automobile industry, for example, a large
proportion of field tests have nowadays been replaced
by numerical simulations, though real old-style field
tests continue to be carried out. What I actually like
to warn is against a potential 'vanity' of believing
that having a (presumably) perfect theory with an
impeacable proof is 'everything', thus being blind of
the fact that the truth of many theorems are contigent
on the fulfillment of their respective assumptions,
leading consequently under circumstances to regretful
disasters.
M. K. Shen
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: How Many?
Date: Sun, 20 Aug 2000 12:22:50 -0700
"Trevor L. Jackson, III" wrote:
>
> "John A. Malley" wrote:
>
> >
> > Well, algorithmically transposition and substitution seem to cover
> > cryptography. Even public key ciphers. For example, take RSA. (Out on a
> > limb here, asbestos suit ON. Check.)
>
> Neither of them cover masking with noise (steganography).
Actually, transposition and substitution do cover steganography.
Chapter 1 of "Decrypted Secrets, Methods and Maxims of Cryptology", F.L.
Bauer, discusses the relationship of steganography to cryptography -
"masking leads to substitution and veiling leads to transposition," pg.
23 of the first edition.
Consider open code linguistic steganography:
Backslang (saying the words backwards) is a form of transposition. It's
intended to hide the true spoken message. And there's Verlan in French
which permutes syllables to encode a message. Bauer lists other
examples.
Jargon-code messages substitute phrases or sounds to stand for the
actual message. Examples - "underground" slang, such as "mole" for girl,
"narc" for informer, "snow" or "blow" for cocaine, and so on.
What about semagrams - visible concealment of a message in an image (or
in the bits of a file) ?
Modulations of some element of the original image or text encode the
message in a non-obvious way - but that encoding is a substitution of
the original message. For example, using spaces between the letters
within a word to encode a message, or placing dots above newsprint text
in a newspaper to "spell out" a hidden message. The spaces and the dots
above the letters substitute for the original message plaintext
(encode). And encoding the message as variations of the LSB of a JPEG
image file? That's a substitution.
Transposition and substitution are at the heart of steganography.
John A. Malley
[EMAIL PROTECTED]
------------------------------
** 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
******************************
