Cryptography-Digest Digest #205, Volume #12 Tue, 11 Jul 00 16:13:01 EDT
Contents:
Re: One plaintext, multiple keys ("Paul Pires")
Re: Missing nuclear secrets found behind Los Alamos copy machine (Joaquim Southby)
Re: NTRU PKC (Vin McLellan)
Re: Proposal of some processor instructions for cryptographical (Dennis Yelle)
Re: NTRU PKC (Vin McLellan)
Re: Suggestions for crypto for constrained-memory/CPU computers? (Mark Wooding)
Re: Steganographic encryption system (Paul Martin)
Re: Turning off scripting (dbt)
Re: Random Numbers (Bill Unruh)
Re: Quantum Computing (Was: Newbie question about factoring) ("Tony T. Warnock")
Re: Random Numbers (Bill Unruh)
Re: One plaintext, multiple keys (Doug Kuhlman)
Re: Random Numbers ("David Hyde")
Re: Using CRC's to pre-process keys (David Hopwood)
Re: Base Encryption FAQ (immune from plain-text attacks)) (Doug Kuhlman)
Re: Proposal of some processor instructions for cryptographical applications
(Maynard Handley)
----------------------------------------------------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: One plaintext, multiple keys
Date: Tue, 11 Jul 2000 11:14:03 -0700
Guy Macon <[EMAIL PROTECTED]> wrote in message
news:8kfb7p$[EMAIL PROTECTED]...
> Paul Pires wrote:
> >
> >What do you mean "Other algorithms can leak if you repeatedly send the
same
> >plaintext enciphered with different keys." ? All others or just some
others?
> >Any in the class of DES, AES finalist? Can you give an example of one and
> >show the type of information leaked?
> >
>
> You are confusing "can" with "do". "Can leak" is the opposite of
> "Can't leak" (leakage is impossible), which is a property of OTP
> and not, say, DES. In fact, many commonly used ciphers are, in
> theory, "easily" breakable by an exhaustive key search by a
> sufficiently powerful computer. In many cases, the speed of light
> is too slow for the speed required and the total number of atoms in
> the universe is too small for the memory required, but the crack is
> still conceptually simple. You can't crack OTP with a brute force
> "try every key" approach even if your computer is infinitely fast
> and infinitely powerful.
Thanks but "can" isn't my choice of words either. I was just wondering if
S.T.L. Had any special knoledge or insight I might hijack.
Personally, I wouldn't equate an exhastive key search with leaking. Just
because one can unload a barrel of wine, one glass at a time, doesn't mean
it leaks even if this is what one does tell ones wife :-)
(The exhastive barrel search attack)
Paul
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Crossposted-To: alt.war.nuclear
Subject: Re: Missing nuclear secrets found behind Los Alamos copy machine
Date: 11 Jul 2000 18:16:09 GMT
In article <[EMAIL PROTECTED]> Doug Stell,
[EMAIL PROTECTED] writes:
>Blowfish isn't approved for protecting anything of interest to the
>Government. It is a commercial or Type 3 algorithm. As such, it is
>ignored by the Government.
>
>SKIPJACK is a Type 2 algorithm and can protect only Unclassified But
>Sensitive (SBU) data. There is very little data that falls into this
>category. It can be used to provide a second layer of protection for
>data that is normally protected by a stronger mechanism. It has been
>temporarily approved for use in protecting classified data, but I
>believe that that approval has expired.
>
>Only Type 1 algorithms are approved to protect classified (SECRET and
>TOP SECRET) data. These high-grade algorithms are all classified and
>provided by the NSA.
>
I've worked on projects with NSA as the approving authority of our
design. They OK'ed Blowfish to protect data classified TS/SAR. They
also suggested that Triple DES would be sufficient for their approval.
------------------------------
From: Vin McLellan <[EMAIL PROTECTED]>
Subject: Re: NTRU PKC
Date: Tue, 11 Jul 2000 14:35:55 -0400
Vin McLellan wrote:
> > In a sci.crypt post about SecurID crypto, I twitted Joseph Ashwood
<snip>
> > Mr. Ashwood, in reply, denied making those statements ...
Roger Schlafly noted:
> You said that Ashwood trashed NTRU as a public key system, and
> you said he said it was "shit", using quotes. The way I read
> Ashwood, he was only attacking the application of NTRU to the
> copy protection of music.
>
> There's a big difference. NTRU may be a wonderful public key
> cryptosystem, but no better than anything else for music copy
> protection. Also, you shouldn't use quotes unless you are actually
> quoting him.
Someone whom I presumed to be Mr. Ashwood, wrote on C'punks:
"And they were granted a patent on this useless shite?"
I repeat, I don't think this was a serious comment. I don't believe
that Mr. A bothered to looked up the patent he was referring to before
he (it seemed to me) condemned it with a sneer.
He, and a lot of other people, seemed to be just reacting to the newsy
context in which Chartrand, the NYT's patent columnist, chose to report
the issuance of the NTRU patent.
The point of my original post to C'punks -- and I could have grabbed
comments, similar to those attributed to Mr. A, from any of several
dozen posts as my foil -- was that serious technocrats should check out
the patent being discussed, before they allowed themselves to be swept
away by one journalist's interpretation of its claims and potential
applications.
(Thought-provoking example of the power of the press, though, wasn't
it?)
When, to my surprise, I found myself addressing (apparently) the same
gentleman in a discussion of SecurID crypto here, I only brought up his
seemingly thoughtless dismisal of the <quote> patent <unquote> as a
parenthetical tease.
> > (Elsewhere, Mr. Ashwood recently described the NTRU PKC [as} a piece of
> > "shit" which doesn't deserve the patent it just received -- a crisp
> > cryptographic evaluation which I suspect his professional and personal
> > friends may find opportunity to recall often in the years to come;-)
I acknowledge that I was treading a fine line. I had no intention of
claiming that Mr. A's earlier comment on Cypherpunks was a hanging
offense or a serious comment on the NTRU patent.
I don't think it was. I thought, and think, that he was shooting from
the hip, tossing off a flip comment without really knowing which
"patent" he was talking about. (Apparently, a week later, he _still_
didn't know which patent he had been talking about on C'punks;-)
When I was challenged to cite his earlier comment, I offered the whole
exchange to the newsgroup just to allow everyone to put his initial
comment, and my jocular reference to it, in a proper and realistic
perspective.
Much ado about very little, I conceed.
_Vin
------------------------------
From: Dennis Yelle <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Tue, 11 Jul 2000 11:41:02 -0700
Runu Knips wrote:
>
> Mok-Kong Shen wrote:
> >
> > Runu Knips wrote:
> >
> > > When I have worked on Paranoia, my little cipher in the
> > > contest, I had to spend much time thinking about exactly
> > > that theme. I have described a network in the cipher paper
> > > which requires 109 bits to specify all (32!) possible
> > > bit permutations of a 32 bit word. One could implement
> > > that with using the following 4 instructions:
> > >
> > > BRT1 src, dest, mask
> > >
> > > - For each pair of bits at the position 2*n and 2*n+1,
> > > n in 0..15, of bits in src, if the bit n is set in mask,
> > > the values of the bit pair is swapped before getting
> > > assigned to dest. Therefore the mask has 16 bits.
> >
> > [snip]
> >
> > I am interested to see a formal proof that your scheme works for any
> > arbitrary permuation. Or could you illustrate on a reduced example
> > of an 8 bit permutation? Thanks.
>
> In fact, I thought it worked perfect, but trying to proove this
> formally leaded into *big* problems :-( because of a detail I've
> overlooked. It might or might not be true, I've to check this
> at home :-(
>
> 8 bits are 8! possibilies, too much to get computed by hand. Hmm
> here is my version for 4 bits:
>
> Lets make a table. According to our scheme, we have to show that
>
> BRT1 reg1, reg1, mask1
> BRTL2 reg1, reg1, mask2
> BRT1 reg1, reg1, mask3
>
> can create all possible bit permutations on 4 bits. Mask1
> and mask3 are pairs of single bits, mask2 is two bits, i.e.
> in [0..3].
>
> Permutation Mask1 Mask2 Mask3
> 1234 [identity] 0,0 0 0,0
> (or: 0,1 0 0,1 [...])
> 1243 0,1 0 0,0
> (or: 0,0 0 0,1)
> 1324 0,1 3 1,0
> 1342 0,1 3 1,1
> 1423 0,0 3 1,0
> 1432 0,0 3 1,1
> 2134 1,0 0 0,0
> (or: 0,0 0 1,0 [...])
> 2143 1,1 0 0,0
> (or: 1,0 0 0,1 [...])
> 2314 0,0 1 0,1
> 2341 0,0 1 0,0
> 2413 0,1 1 0,1
> 2431 0,1 1 0,0
> 3124 0,1 3 0,0
> 3142 0,1 3 0,1
> 3214 1,1 3 0,0
> 3241 1,1 3 0,1
> 3412 0,0 2 0,0
> 3421 0,0 2 0,1
> 4123 0,0 3 0,0
> 4132 0,0 3 0,1
> 4213 1,0 3 0,0
> 4231 1,0 3 0,1
> 4312 0,1 2 0,0
> 4321 1,1 2 0,0
In the 8 bit case,
my brute force search indicates that only
38272 of the permutations are reachable,
but 8! is 40320.
In particular, starting with abcdefgh,
this was extracted from the sorted list
of possible results:
aedhbcfg
aedhbcgf
aedhbfcg
aedhbfgc
aedhcbfg
aedhcbgf
aedhcgbf
aedhcgfb
Notice that the entries starting with
aedhbg
are missing.
The weakness seems to be that there is only one operation
that moves bits from the left half to the right half, or
vice versa.
Of course, it is possible that there is a bug in my program.
Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here: http://table.jps.net/~vert
------------------------------
From: Vin McLellan <[EMAIL PROTECTED]>
Subject: Re: NTRU PKC
Date: Tue, 11 Jul 2000 14:52:00 -0400
Joseph Ashwood wrote:
> Given that I accept that this was a genuine misunderstanding. I was not
> referring to NTRU itself as worthless and wasteful, as a matter of fact I
> have not yet studied NTRU to make such a determination. However, I was
> making a similar statement regarding using cryptography to prevent the
> piracy of MP3s, even given perfect cryptography, the benefits can be gotten
> around, and an unrestricted MP3 made, making the protection only an
> annoyance for legitimate users.
> Joe
I acknowledge, too, that I should not have used such a complex
reference in such a jocular and teasing manner, particularly in this
forum.
I also presume that there were several layers of misunderstanding
here.
I regret any confusion my use of a perhaps slightly out-of-context
quote may have caused -- but I still think you should have looked up the
damn patent before you 'dissed and dismissed it on the Net;-)
_Vin
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Suggestions for crypto for constrained-memory/CPU computers?
Date: 11 Jul 2000 18:46:31 GMT
Paul Rubin <[EMAIL PROTECTED]> wrote:
> More to the point it doesn't give the kind of speedup being asked for.
> Normally you find x^s mod p with a square-and-multiply algorithm,
> where for n bits you do n squarings and (on average) n/2
> multiplications. The low hamming weight gets rid of most of the
> multiplications but you're left with the squarings. Squaring can be a
> little more efficient than multiplication, but still, you've only
> gotten a factor of 2 or so at best out of the total.
OK. Let's make the residues *small*, but different. Now I know there
are attacks against small decryption exponents, but
(a) the decryption exponent itself is very likely to be large anyway,
since the residues are distinct; and
(b) according to my copy of HAC, they don't work if e is large, which
it will be because we didn't choose it to be small.
So: is this a really bad idea, or does it just give people (myself
included) bad vibes?
(Thanks to DAW for giving me some offline prompting to get my thoughts
in order properly.)
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Paul Martin)
Crossposted-To: comp.os.linux.development.apps,uk.comp.os.linux
Subject: Re: Steganographic encryption system
Date: 11 Jul 2000 19:06:36 GMT
In article <[EMAIL PROTECTED]>,
Jim Howes wrote:
>John Winters wrote:
>>
>> Explaining quite why a 1k plaintext encrypts to a 30k cyphertext
>> might keep you busy.
>>
>> John
>No, it's explained easily. The user has written a 1k message
>using Microsoft Word
There's a thought. I wonder how much of the bloat space in a .DOC file
is actually interpreted by MS Word.
--
Paul Martin <[EMAIL PROTECTED]>
at home, swap dash to dot to email.
------------------------------
From: [EMAIL PROTECTED] (dbt)
Subject: Re: Turning off scripting
Date: Tue, 11 Jul 2000 19:17:46 GMT
Greg Keogh <[EMAIL PROTECTED]> says:
>Hi Scott,
>
>It's a real pain in the you-know-what to have to turn off scripting just to
>visit your web site.
>
>Are you sure this is necessary? I'm not aware of any virus risks from
>JavaScript, and I only accept ActiveX controls from signed sources.
>Demanding that visitors turn off scripting and other advanced browser
>features seems to be somewhat dictatorial. I'm not sure what the point is.
>Are you protecting people from your own site, or are you suggesting that
>they keep browser security at the highest safety levels at all times, even
>after they leave your site?
"This is really offtopic, but ..."
ActiveX signing gives you, at best, someone to blame in the event a
control goes awry. It does NOTHING to protect your machine in terms
of sandboxing or locking down the operating system. It runs with
full native privilege of the user.
Example: http://www.wired.com/news/business/0,1367,34544,00.html
Complaints about the Microsoft CryptoAPI which can result in malicious
users stealing keys and signing malicious controls with otherwise
trusted keys are more ontopic, but I don't have up-to-date information
on whether they've fixed problems previously reported here.
--
David Terrell | "Instead of plodding through the equivalent of
Prime Minister, NebCorp | literary Xanax, the pregeeks go for sci-fi and
[EMAIL PROTECTED] | fantasy: LSD in book form." - Benjy Feen,
http://wwn.nebcorp.com | http://www.monkeybagel.com/ "Origins of Sysadmins"
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Random Numbers
Date: 11 Jul 2000 19:18:21 GMT
In <[EMAIL PROTECTED]> Nicol So <[EMAIL PROTECTED]> writes:
]Herman Rubin wrote:
]>
]> Independence is MUCH harder to approximate than lack of
]> bias. It is also much harder to detect.
]Both statements above relate to the existence of secure encryption
]algorithms. Since I tend to believe in their existence, I tend to agree
]with the latter statement (but I also believe that independence cannot
]be *too* hard to approximate).
]Strictly speaking, what I'm going to say depends on how the notion of
]security is formalized, but to keep the discussion informal, I'll
]handwave. So bear with me.
]If secure encryption is indeed possible, one can construct a secure
This is of course a big "if". Noone knows if secure encryption is indeed
possible (ie an encryption scheme which creates out of a short key, an
encryption which cannot ever be broken.)
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: Tue, 11 Jul 2000 13:18:53 -0600
Reply-To: [EMAIL PROTECTED]
Bob Silverman wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Jeff Erickson wrote:
> >
> > > ca314159 <[EMAIL PROTECTED]> writes:
> > > | D. Mermin poses a useful problem for only one qubit:
> > > | to determin the millionth bit of the binary expansion
> > > | of sqrt(2+x). That would be big news.
> > >
> > > Hardly. Given the recent computation of the trillionth(!) bit of pi
> > > using classical computers, why should anyone think computing bits of
> > > sqrt(2+x) is hard?
> >
> > I'm going to guess that it's much harder to compute the bits of an
> algebraic
> > number than the bits of Pi or or some other transcendentals.
>
> No. It is because an algorithm by Simon Plouffe allows computation
> of the k'th bit of Pi **without** having to compute the 1...k-1
> bits.
That's true. I was basing my comment on the article by van der Poorten and
Loxton in Crelle's Journal vol 392, p57, that (purported, there may be an
error) that the bits of an algebraic number can not be generated by a finite
state machine. Bit strings generated by finite state machines must be either
rational or transcendental.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Random Numbers
Date: 11 Jul 2000 19:24:32 GMT
In <8kfbpm$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Guy Macon) writes:
]>>Sorry I left out some detail about the random bit stream. The bit stream
]>>has been generated from a white noise source I built from a zener diode, a
]>>couple of op-amp stages and a comparator. Although the bits produced are
]>>independent of each other, there is a bias that can't be removed by
]>>adjusting the dc mean level of the noise. Therefore I was asking if there
]>>is a way of processing the bit stream to produce 16-bit random numbers with
]>>a uniform distribution?
Unfortunately you do not know that the bits are independent. Physical
processes often have long range correlations (eg stray capacitances etc
can produce oscillations in the circuit which introduce correlations in
the output of the zenner.) You really need a good physical model for
the system, and then look for correlations produced by that model.
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: One plaintext, multiple keys
Date: Tue, 11 Jul 2000 13:59:37 -0500
Believe it or not, I'd actually gotten the RSA example already. It
seemed reasonably obvious. And Mok-Keng is right. I was asking for an
example of a block cipher with/without this property.
Is it even being studied? Are the AES candidates examined if the same
plaintext is encrypted with multiple keys? Would a little salt at the
beginning/end solve my problem?
OK, I'm excessively stupid (or maybe just lazy). I couldn't even come
up with examples like that. I thought if I could (or could convince
someone else to), it might lead me to seeing how to avoid that problem
in general.
David A Molnar wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > [snip]
>
> > He was however asking for an example of block cipher, I suppose.
>
> I know. I just wanted to give a somewhat natural example other than OTP.
> I don't know of any natural examples for block ciphers, although it seems
> you could come up with some explicitly stupid examples without too much
> work.
>
> -David
------------------------------
From: "David Hyde" <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Date: Tue, 11 Jul 2000 20:38:27 +0100
"Guy Macon" <[EMAIL PROTECTED]> wrote in message
news:8kfc20$[EMAIL PROTECTED]...
> David Hyde wrote:
> >
> >
> >
> >"David Hyde" <[EMAIL PROTECTED]> wrote in message
> >news:8kac12$nk2$[EMAIL PROTECTED]...
> >> Does anyone know how to convert a random bit stream into random 16-bit
> >> numbers with uniform distribution?
> >>
> >>
> >
> >Sorry I left out some detail about the random bit stream. The bit stream
> >has been generated from a white noise source I built from a zener diode,
a
> >couple of op-amp stages and a comparator. Although the bits produced are
> >independent of each other, there is a bias that can't be removed by
> >adjusting the dc mean level of the noise. Therefore I was asking if
there
> >is a way of processing the bit stream to produce 16-bit random numbers
with
> >a uniform distribution?
> >
> >
>
> Consider the case if you sample at. say 10 Gigasamples/second.
> Would the bits produced be independent of each other?
>
Depends on the bandwidth of the white noise source. I'm sampling at a very
much lower rate then the highest frequency produced by the bandlimited white
noise.
------------------------------
Date: Tue, 11 Jul 2000 17:22:06 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Using CRC's to pre-process keys
=====BEGIN PGP SIGNED MESSAGE=====
"David A. Wagner" wrote:
> In article <[EMAIL PROTECTED]>,
> Scott Nelson <[EMAIL PROTECTED]> wrote:
> > If we assume that the hash is completely unbiased
> > within the 128 bit space, hashing all possible 128 bit
> > keys would result in approximately 1/e values being
> > missed, and 1/e single hits, with the rest being
> > hit multiple times. Effectively reducing the key
> > space by less than 3 bits, which I agree is pretty
> > irrelevant in most cases. It's not 0 though, so this
> > is an advantage that CRC has over SHA1.
>
> Yup, looks irrelevant to me. Brute-forcing a 125-bit keyspace is utterly
> infeasible, so this 'advantage' of CRC over SHA1 appears negligible to me.
Not to mention that, unless SHA-1 has some serious weaknesses, there's no
way to characterise the set of possible keys in a way that would
allow you to reduce the expected work factor to less than 2^127. I.e.
you don't know where the collisions are without hashing as many values
as would be needed for simple brute-force.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOWo2GjkCAxeYt5gVAQFP2Qf9GhyNRdsCzdCvO6s3/yXCfnFzvairzmK3
pqDOFkDmhoUCSCvWSMDALuBbdD7v6JeoDqDNHQ1cdmqucDISBXhDnfnJn2Mqk/Km
s6O1pahjlaJ8MxbuGAGmMfOLH2B9r6AIZXQO/o5FSzuX+iRbjSlna+U4MVxrDes+
dAQ/+pzOviwUiJTb94KolnDT7ZcVQwsN3e7xefSxQUjJXf2Z4u1GyDw6K9P+kgez
xNPK/yLafUQDoWzHw/bW8wpckLjeLMy9RVINX92/qxkEeuIOML6cPrZouXkdJRys
fr0xp+AqVaiZPdyzWlbqa+y4s154MMAaXrGu4LVzQvhijDdH7zqs7Q==
=Ravy
=====END PGP SIGNATURE=====
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: Base Encryption FAQ (immune from plain-text attacks))
Date: Tue, 11 Jul 2000 14:19:26 -0500
Couldn't resist....
[EMAIL PROTECTED] wrote:
>
=> Why is Base Encryption strong?
>
> Answer:
> Base Encryption utilized many unique properties that are
> unbreakable. It provides dynamic base (symbol set), dynamic
> algorithms (operators and operations), and one-time-pad security
> without the inconveniences. It is a full-fledged cypher that easily
> fits into the internet's web-centric model.
>
How about more inconvenience than one-time-pad with less security?
Your "key" has to be the entire program used to shuffle your plaintext.
If you change that mid-message, the key has to change, too. This "key"
then gets quite long and cumbersome.... Plus, the receiver has to
decide how to invert each operation, which makes it far from
easy-to-use.
This key has to be sent to the user somehow.... You never address how a
receiver decrypts information (probably because you don't know, huh?)
Somehow, this information has to be passed -- and that means public-key
cryptography. And a VERY LARGE key compared to other symmetric ciphers
(except, maybe, OTP...and you could easily have a key much longer than
THAT!).
Oh, yeah. And you have to change your key for every message. Using the
same key twice basically breaks the whole system. If you open your mind
a bit, you might see why this is a problem.
While I'm writing this, I might as well comment on the speed of the
algorithm. Imagine a reasonable document (50K bytes). You propose to
make this one big number that you can manipulate...using some random
base. OK, this can be done, but not effeciently. Try using your toy
to multiply a number on the order of 2^{400000} by 7 in base 13 and see
how long it takes to calculate. Then invert that.... Let me know how
it works.
Oh, one final thing. To send your key over to the recipient, you have
to codify your algorithm somehow. Bingo-bango, a nice easy keyspace to
search through.
Doug
P.S. Please do the crypto world a favor and don't try to sell this.
Somebody might be ignorant enough to listen....
------------------------------
From: [EMAIL PROTECTED] (Maynard Handley)
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Tue, 11 Jul 2000 12:43:11 -0700
In article <[EMAIL PROTECTED]>, Paul Koning
<[EMAIL PROTECTED]> wrote:
>"Douglas A. Gwyn" wrote:
>>
>> Konrad Schwarz wrote:
>> > From an abstract point of view, possibly. From a practical
>> > point of view, I beleive not: the investment in byte addressable
>> > hardware is just too large and the payoff of bit-addressing too small.
>>
>> Spoken like somebody who does not program communication protocols,
>> error-correcting codes, etc.
>
>I do all that and I agree with Konrad...
>
>> There is no fundamental obstacle. The main issue is that bit
>> addresses require 3 more bits than octet addresses. Whoopdeedo.
>
>No, the bigger issue is that bit addressing requires 8 times as
>many write enable lines on the bus.
>
>The reason byte access works efficiently is that system buses have
>byte lane enables so you can selective byte writes *without* the
>absurd overhead of a read/modify/write sequence. To do that on a
>bit basis requires bit write enables. And you'd need memory that
>has per-bit write enables, which is fine if you have Nx1 memory
>chips but not if you have Nx4 or Nx8 as happens often enough.
I don't buy this. The case we care about (or at least I care about) is
cached data. The CPU already sees the cache as essentially a 256 bit wide
structure and misaligned loads are not expensive because there isn't
really a "byte" concept---the appropriate bits are simply pulled in. The
extension being proposed simply hooks off that mechanism. Obviously, just
like on current PPC and x86 for misaligned loads, there will be edge cases
that are more expensive---eg crossing a cache line boundary may take an
extra cycle, and crossing a page boundary may trap to the OS for help.
However those cases are rare and we live with them in the case of
misaligned data. (And don't give me guff about how misaligned data is "bad
programming". If one is talking about LARGE arrays of structs that are
naturally, say, 1+2 bytes wide, and if one's CPU handled misaligned reads
and writes, packing the array works just fine and gives you a whole lot
better performance than not doing so.)
CPUs already define a bunch of attributes for pages or segments. There is
no reason why the "bit addressed" attribute is not tied to the "cached,
write back" attribute meaning the bus never needs to care about this.
Maynard
------------------------------
** 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
******************************
