Cryptography-Digest Digest #461, Volume #12 Wed, 16 Aug 00 16:13:01 EDT
Contents:
Re: Not really random numbers ([EMAIL PROTECTED])
Re: OTP using BBS generator? (Mok-Kong Shen)
My first serious (kinda) paper. (Ichinin)
Re: 215 Hz five-qubit quantum processor (Mike Haertel)
Re: Proposal of drafting rules of conduct of posting (Mok-Kong Shen)
Re: 215 Hz five-qubit quantum processor (Steve Newman)
Re: Proposal of drafting rules of conduct of posting (David A Molnar)
Re: My first serious (kinda) paper. ([EMAIL PROTECTED])
Re: Looking for a DES or RSA chip with write-only key. (Paul Rubin)
Re: 215 Hz five-qubit quantum processor (SCOTT19U.ZIP_GUY)
Re: 215 Hz five-qubit quantum processor (SCOTT19U.ZIP_GUY)
Re: Impossible Differentials of TC5 ([EMAIL PROTECTED])
Re: Proposal of drafting rules of conduct of posting ("Paul Pires")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Not really random numbers
Date: Wed, 16 Aug 2000 17:16:49 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mark Wooding) wrote:
> Simon Johnson <[EMAIL PROTECTED]> wrote:
> > How about this:
> >
> > Pick a large prime,p. Pick another large prime, Q. Find two
> > primitives, one in GF(p) and one in GF(q), call these numbers a
> > & b repectivly . Then iterate the following:
> >
> > c=(c*a) mod p
> > d =(d*b) mod q
> >
> > output stream-byte = (c+d) mod 256
>
> This gives me the heebiejeebies. It's basically two linear
congruential
> generators (only they're simpler because there are no additive
> constants), and then you combine them in a simple way.
Plus if 'a' and 'b' are not chosen properly their outputs can be very
nonrandom. See Knuth Vol2 P23 section 3.2.1.3 "Potency".
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Wed, 16 Aug 2000 19:41:31 +0200
David Hopwood wrote:
>
> Mok-Kong Shen wrote:
> > Sorry, I am really confused. 'Parity bits' or 'LSB'? Thanks.
>
> Either (they are equally secure).
Intuitively I would think that the parity bit (in the
common term, i.e. count of 1's) is at least as secure as
LSB but I don't see any way of proving that.
I have finally been able to obtain a copy of the BBS
paper. The result of interest here says that modulo the
quadratic residuacity assumption, the x^2 mon N is
polynomial-time unpredictable to the left. Is there
any concrete relation between the quadratic residuacity
assumption and the assumption of hardness of factoring N?
Thanks.
M. K. Shen
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: My first serious (kinda) paper.
Date: Wed, 16 Aug 2000 08:47:44 +0200
Hi.
My suggestions on how to build a secure key
schedule using variable key rotations, avalance
and "one wayness". (Key modification is still DIY)
http://www.geocities.com/ichinin/KeySchedule.htm
So - "Let the pie fight begin".
Regards,
Glenn
______________________________________________
Disclaimer: According to consultation with ISP
(=BXA) on 2000/August/16, there is no difference
in exporting crypto knowledge in an electronical
or book form out from the Europeean union or
Sweden. (Hey! The algorithm even support export
restriction)
------------------------------
From: [EMAIL PROTECTED] (Mike Haertel)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: 16 Aug 2000 12:51:18 -0500
In article <[EMAIL PROTECTED]>,
Steve Newman wrote:
>Oh, well. Then my brilliant idea for the ultimate compression
>algorithm is probably no good either. (Generate all possible
>bitstrings, select the ones that when executed on a virtuam machine
>interpreter generate the uncompressed file as output, and keep the
>shortest such bitstring.)
That's not the "ultimate compression algorithm" either, because the
maximum amount of compression you could get for any given input
would vary with the details of the virtual machine interpreter's
instruction set.
Of course, this suggests the obvious improved strategy: generate all
possible bit strings, all possible virtual machine interpreters... :-)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Proposal of drafting rules of conduct of posting
Date: Wed, 16 Aug 2000 20:11:50 +0200
Mark Wooding wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > The practical problem consists in: (1) FAQ appears only every 21 days;
> > there is no HTML version that can be accessed at any time.
>
> Is http://www.cpsr.org/cpsr/privacy/crypto/tools/docs/sci.crypt-faq.txt
> a mirage? (Yes, I know it's not HTML, but HTML is overrated anyway.)
>
> I think the best thing to be done with the FAQ is to *update* the damned
> thing. I heard rumours that someone was doing it; otherwise I might
> even be tempted to try maintaining it myself.
I didn't know that. The official FAQ posted here every 21
days doesn't contain any URL of a web page, if I don't err.
You seem to imply that the above is a copy and is not
surely up-to-date. Is that right?
> > (1) A status problem. You don't see gentlemen and ladies in fine
> > costumes in company of the saleswomen of the fish or vegetable
> > markets, do you?
>
> I don't see why this shouldn't be the case. Well, perhaps without the
> `fine costumes' -- that would look too much like showing off. But I'd
> certainly consider that not wishing to be associated with someone
> *merely* on account of their station is snobbery of a rather unpleasant
> kind.
It may not be a problem for you, because you have an
exceptionally fine character etc., but it surely is for
many who are e.g. rich. You can accuse them of snobbery
or what not, but that doesn't change the fact that
there exists snoberry, etc.
>
> > (3) No necessity from moral point of view.
>
> Depends. I *do* feel a slight `moral necessity', because sci.crypt is
> where I really started learning about crypto. Besides, I do think that
> there's enough intelligent discussion here to make it worthwhile anyway,
> despite the Szopas and Scotts and Po-Han Lins of the world.
The same argument of mine above also applies here. Don't
assume too much similarity between you and others. A
proverb says: One should not dispute over tastes and colours.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Steve Newman)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: Wed, 16 Aug 2000 18:04:06 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Mike Haertel) wrote:
> In article <[EMAIL PROTECTED]>,
> Steve Newman wrote:
> >Oh, well. Then my brilliant idea for the ultimate compression
> >algorithm is probably no good either. (Generate all possible
> >bitstrings, select the ones that when executed on a virtuam machine
> >interpreter generate the uncompressed file as output, and keep the
> >shortest such bitstring.)
>
> That's not the "ultimate compression algorithm" either, because the
> maximum amount of compression you could get for any given input
> would vary with the details of the virtual machine interpreter's
> instruction set.
>
> Of course, this suggests the obvious improved strategy: generate all
> possible bit strings, all possible virtual machine interpreters... :-)
Well, for large files, this becomes almost irrelevant -- if a certain
virtual machine is better suited to decompressing a particular file,
then the compressed version of that file would just include the
necessary VM (implemented in the basic instruction set). This would
be discovered automatically by the search algorithm. Hence there's
just the overhead for the extra VM interpreter (which is why I said
"almost" irrelevant and "for large files") -- and remember that the
system will automatically discover the smallest possible encoding
the VM interpreter in the basic instruction set.
Of course, finding the best instruction set for typical files is
easy -- just iterate over all possible bitstrings of a certain
length, treat each one as a VM, and see what compression length
it supports for a suite of benchmark files. Pick the best one
and use it as your standard. *Damn* I wish this worked. :)
-- Steve Newman
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Proposal of drafting rules of conduct of posting
Date: 16 Aug 2000 18:04:19 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
> I think the best thing to be done with the FAQ is to *update* the damned
> thing. I heard rumours that someone was doing it; otherwise I might
> even be tempted to try maintaining it myself.
I made brief plans towards the aim of updating the FAQ about this time
last year. They were pre-empted by the announcement in the current part 1
of the FAQ which claims that a project to update it is underway
right now, subject to the resolution of some copyright issues.
(That's not my doing) Also the beginning of school somehow got in the way.
Last time I asked about "is anyone updating the FAQ?" (september 99),
I received a bunch of "don't know" responses and one "yes." The "yes"
did not comment further.
On the one hand, if some of the same people as last time are involved
in updating the FAQ, then it will be worth the wait. On the other hand,
it's been several years since the last update. On the gripping hand,
whoever maintains it will be in for a rather large commitment...
-David
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: My first serious (kinda) paper.
Date: Wed, 16 Aug 2000 18:55:02 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi.
>
> My suggestions on how to build a secure key
> schedule using variable key rotations, avalance
> and "one wayness". (Key modification is still DIY)
>
> http://www.geocities.com/ichinin/KeySchedule.htm
>
> So - "Let the pie fight begin".
Hehehe, It's an interesting albeit brief paper. You have a few
spelling and grammatical mistakes but other then that it's to the point.
Some picky stuff however.
Am I correct in assuming 'stuff' is a simple 32-bit quantity? Seems
kinda like a small chaining variable. Note collisions in the 'stuff'
variable can make the keys less random then you think.
Second multiplication modulo 2^32 is not bijective and is hardly a good
way to create random keys. In fact you lose bits of entropy with each
multiplication. Unless you ensure the quantity is odd it's a bad
idea. Also multiplication has diffusion but it is very directed
towards the upper bits. The lower bits will not be affected at all by
the upper bits and the overal output will not be sufficiently random.
Also note that something like ((x<<<5)>>>3) is the same as (x<<<2) you
have double rotations in various places in your code and they just make
it look more complicated.
Also note that constant rotations are hardly non-linear since the
mapping of bits is known it's in fact perfectly linear.
Finally you seem to mix the user key into the thing by multiplication,
that's a terribly bad idea for the reasons given above.
Good luck :)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Looking for a DES or RSA chip with write-only key.
Date: 16 Aug 2000 19:07:28 GMT
Sniggerfardimungus <ronb.cc@usu@edu> wrote:
>I actually do have a reason to burn in a key. I don't want it to
>change and I would rather that a battery failure not lose it... This
>is not a typical communication application, so most of the
>assumptions about key distribution and security do not apply. My
>application is about as far from communication as you can get....
If you just want a small quantity of something reasonably cheap, try
http://www.brouhaha.com/~eric/crypto
which has DES and Skipjack implementations for the PIC microprocessor.
The 16c84 series starts around $4. The code is stored in flash memory
and there are 64(?) bytes of data EEPROM where you can store keys.
For lower cost, and probably somewhat better security against hardware
attacks, try a smart card chip. Gemplus, Schlumberger, Motorola, and
Siemens all make these. But these are generally mask programmed so
you'll have to buy in fairly large quantity.
For much more serious security at higher cost, try a Dallas iButton
(www.ibutton.com). I think the ones with cryptography start around
$10 (low quantity) and then there's a connector that you need.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: 16 Aug 2000 19:12:48 GMT
[EMAIL PROTECTED] (Steve Newman) wrote in <snewman-
[EMAIL PROTECTED]>:
>In article <8ndcr7$4f1$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Paul
>Rubin) wrote:
>
>> In article <[EMAIL PROTECTED]>,
>> Steve Newman <[EMAIL PROTECTED]> wrote:
>>
>> >It occurred to me some years back that with the appropriate "magic
>> >box", you could trivially implement a theorem prover for arbitrary
>> >theorems. Simply generate all possible strings up to a certain
>> >length, and run each string through a theorem checker to see if it
>> >constitutes a proof for the theorem. This requires a theorem
>> >checker, but that's not hard to write.
>>
>> This doesn't tell you whether a theorem is true, of course. Input the
>> extended Riemann hyponthesis and start the prover, stopping it when
>> the strings reach a billion characters. Say it stops without finding
>> a proof. You still don't know whether there is a proof of ERH that
>> happens to be a billion and one characters long. Some awfully long
>> proofs have in fact been published. The theorem classifying the
>> finite simple groups fills something like 10,000 journal pages.
>
>Yes, of course, it wouldn't be a universal theorem decider. But it
>might manage to prove some things that have been stumping us for a
>fair while.
>
>
>> >Could this algorithm be implemented in a (sufficiently advanced)
>> >quantum computer?
>>
>> Probably no better than on a classical computer. The problem you're
>> describing ("is there a proof of X, that's < N characters long?") is
>> clearly NP-hard.
>
>Oh, well. Then my brilliant idea for the ultimate compression
>algorithm is probably no good either. (Generate all possible
>bitstrings, select the ones that when executed on a virtuam machine
>interpreter generate the uncompressed file as output, and keep the
>shortest such bitstring.) This one is actually even worse than the
>theorem-proving algorithm because it requires interpreting (executing)
>each bitstring, not just running it through a proof checker.
>
Any method of full finite file transforms that leave no gaps
are already perfect compressors. In the sense that they make
maximum use of the file space. MY huffman coders and Matt Arithmetic
coder are examples of perfect compression. One test of perfect
compression is that for any file A = uncompress ( compress ( A ))
and A = compress ( uncompress ( A))
>It would be interesting to see what problems that are traditionally
>"too hard to bother even thinking about" do become tractable on a
>reasonably large quantum computer. But I'm wandering pretty far
>from comp.arch...
>
>-- Steve Newman
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
"The road to tyranny, we must never forget, begins with the destruction
of the truth."
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: 16 Aug 2000 19:23:02 GMT
[EMAIL PROTECTED] (David T. Wang) wrote in
<8nd8hl$9vd$[EMAIL PROTECTED]>:
>In comp.arch [EMAIL PROTECTED] wrote:
>
>: Wow .. this technology is moving fast! In 2Q98 there were still
>: many physicists doubting that anyone could ever make a model that
>: could remain coherent for more than one or two operations at a time,
>: and now here's IBM in 3Q00 demo'ing a 215 Hz system!
>
>: It sounds like practical quantum computing might intersect the
>: domain of digital computing sooner than anyone expected 8-|
>
>: IBM's system is a one-function device, but what a function!
>: Finding the period of a function as a one-step calculation! It
>: makes me wonder how long it will be before our computers are
>: hybrid systems, with fast digital processors remaining at the
>: heart of the system, but with single-function co-processors
>: standing by to perform "hard" operations as needed.
>
>: It reminds me of the P/NP problems the professor would give us
>: in college, where he'd say "here, assume you have a conventional
>: computer that runs pascal, and a magic function that solves this
>: NP problem in P time. Write a function to solve this other NP
>: problem in P time by using this magic function."
>
>: Seems to me that if a quantum computer like IBM's can solve the
>: period of an arbitrary function in P time (indeed, in O(1) time),
>: then it might also be able to solve the halting problem in P time
>: for at least some subset of algorithms (or at least be used by a
>: conventional computer to solve the halting problem, a la AVG's
>: classroom exercises). The mind boggles at what we could do with
>: that.
>
>: Question -- is keeping an N+1 qubit computer coherent a *lot*
>: harder than keeping an N qubit computer coherent? IE, does it
>: get more difficult as an exponential, polymetric, linear, or some
>: other function of qubits, roughly speaking? Or is everyone still
>: scratching their heads and unable to say?
>
>The problem of using technologies such as these would be to interface
>them with the existing infrastructure, and the communcation latencies
>involved. That is, unless these special purpose gizmos can somehow
>take over all of the computational load, then they have to talk to some
>other form of intelligence, and eventually I/O. A quantum computer
>can indeed be very exciting if it can decrypt 1024 key encrpytion
>in a single "cycle". (Sneakers?) However, then the next logical
>question is, how long does it take to get the quantum computer, or
>for that matter, any special form of computing element to be setup
>to the point when it can compute what we want it to compute, and then
>get the information out to a point and place where we can understand
>the result.
>
>
Even if it took years to set it up for a special case then the
NSA would still do it so they could solve PGP types of encryptions.
It would be worth their time. It also may be the death of many ciphers
where if the NSA know it was encrypted text that only a few blocks of
the encrypted text need to be looked at. What makes most small block
and key ciphers weak to this kind of attack is that there usually is
only one solution. If one encrypts in such a way that many false
keys give the wrong anwser then there is no solution for the quantum
computer to settle on. That is why it may be best to use encryption
methods that treat the whole file like a single block such as
SCOTT19U.ZIP
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
"The road to tyranny, we must never forget, begins with the destruction
of the truth."
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Impossible Differentials of TC5
Date: Wed, 16 Aug 2000 19:17:42 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> David Eppstein <[EMAIL PROTECTED]> wrote:
> >In article <[EMAIL PROTECTED]>,
> tomstd
> ><[EMAIL PROTECTED]> wrote:
> >
> >> Ok still at some point you must attack the 64/32/16 bit
> >> feistels. I want to know how you do that please.
> >
> >As I understand it, you don't. You just attack the 128-bit
> ones,
> >treating everything else as a black-box F-function.
>
> Technically the F function has a 128 byte (1024 bit) round key
> associated with it. It's not as simple as the round key being
> xor'd in though... I still don't see how the attack works, if
> it does even at all.
>
> Tom
Tom,
A simple key recovery attack exists. If the F function operates on the
left half, the four round impossible differential is
0 d probabilty of 1
d 0 e != 0 since the F function is bijective, p = 1
e d f != d since f = (F(e) ^ d) and F(e) != 0, p = 1
f e
g f ciphertext, g = F(f) ^ e
All the above are diffentials of course.
What we know
e != 0
f = f1 ^ f2, where f1 and f2 are known
g = F(f1^k) ^ F(f2^k) ^ e, where k is the secret key.
F() is a bijective 64-bit function
Now if we assume e = 0, we can calculate possible values for the key, k.
In a brute force manner, we loop through all possible values of k' and
check
(1) F(f1^k') ^ F(f2^k') = g.
Any value of k' that satifies (1) cannot be the actual key, k. If k =
k' then e = 0. Since e != 0, we have created a contradiction.
For TC5, the last round key can be discovered this way and the cipher is
reduced to three rounds.
The attack will need less than 2^66 plain/cipher text pairs. About 2^33
actual plaintext/ciphertext should be enough to create the proper
number of differential pairs.
Each pair will require 2^64 rounds of TC5 to calculate impossible keys.
The result should be one candidate key. The three round version can be
broken easily.
If I have the above attack correct, the cipher is broken with 2^33 known
plaintext/ciphertext and about 2^104 rounds of TC5 work. A better way
to elimate keys may exist.
It appears that the 64/32/16 do -not- have to be attack. Perhaps, the
attack can be improved by understanding the coherence within the F
function though.
It looks like bumping the outsize loop to 6 rounds should fix the
problem.
--Matt
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Proposal of drafting rules of conduct of posting
Date: Wed, 16 Aug 2000 12:28:56 -0700
David A Molnar <[EMAIL PROTECTED]> wrote in message
news:8nel33$obq$[EMAIL PROTECTED]...
> Mark Wooding <[EMAIL PROTECTED]> wrote:
>
>
> > I think the best thing to be done with the FAQ is to *update* the damned
> > thing. I heard rumours that someone was doing it; otherwise I might
> > even be tempted to try maintaining it myself.
>
> I made brief plans towards the aim of updating the FAQ about this time
> last year. They were pre-empted by the announcement in the current part 1
> of the FAQ which claims that a project to update it is underway
> right now, subject to the resolution of some copyright issues.
> (That's not my doing) Also the beginning of school somehow got in the way.
>
> Last time I asked about "is anyone updating the FAQ?" (september 99),
> I received a bunch of "don't know" responses and one "yes." The "yes"
> did not comment further.
>
> On the one hand, if some of the same people as last time are involved
> in updating the FAQ, then it will be worth the wait. On the other hand,
> it's been several years since the last update. On the gripping hand,
> whoever maintains it will be in for a rather large commitment...
Moderators? Gripping hand? Hehe. Perhaps the only beings up to the task.
Question, after the FAQ is updated, is it going to be posted for review?
BBS, OTP and TRUE randomness will be beign discussions next to that!
Try asking C. Mathew Curtin. I believe he wrote the Snake Oil FAQ sheet and
suspect that he was involved with the Sci.crypt 10 commandments in some way.
Ok, I have commented on everyone elses suggestions but haven't posted any of
my own. I have none but I do have observations.
(The background lights dim...)
1, Rules of civilized conduct will only be followed by the civilized. Deja
Vu all over again.
2, Good behavior is not rewarded here and bad behavior is rewarded with
attention, analysis and fame (infamy?). The tool is working. Don't complain
if it does not do as you wish. It responds to your actions, not your wishes
or intent.
3, Trolls and polite residents both misuse the forum. Drowning in sewage or
apple pie and motherhood are both drowning. This could be a forum where
people openly discuss issues of merit, Where they can even risk a little and
be survivably wrong. The MOST well known principles and common knowledge
require constant scrutiny and challenge regardless of whether it is likely
to be a fruitfull (or sane)exercise.
You folks are missing the Point! If the percieved quality of this form is
dropping like Monika in a knee pad factory it is because of a lack of worth
and NOT an upsurge in badness.
I just don't think an Emily Post wich hunt is the solution. No one here is
good at coloring inside the lines. Everbody is behaving in a way that they
feel is justified or essentially right and new rules defining rightness will
not change that.
"Just my opinion, I could be wrong."
Paul
>
> -David
>
------------------------------
** 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
******************************
