December 2003 - cypherpunks-legacy

Re: Symantec's claim.
by Alan Olsen 17 Dec '03

17 Dec '03

At 03:45 PM 11/25/96 +0200, cracker(a)icon.co.za wrote: >Anyone come across the pkz300 trojan,if you have it send it please. Why would you want it? The PKZ 3.0 trojan is at least 5 years old. (I am amazed I can still read the disk my copy is on without the magnetic media flaking off.) It is a pretty pathetic trojan at that... And no, I am not going to send you a copy. You would use it not for good, but for evil. (And not the fun sort of evil either. That required things and devices you are far to young to know about... As well as black leather clad women with <ahem> ... Sorry...) I suggest that you put your inquisitive nature into researching something that will do you some good. (Or at least, get you out of the house.) --- | "Remember: You can't have BSDM without BSD." | |"The moral PGP Diffie taught Zimmermann unites all| Disclaimer: | | mankind free in one-key-steganography-privacy!" | Ignore the man | |`finger -l alano(a)teleport.com` for PGP 2.6.2 key | behind the keyboard.| | http://www.ctrl-alt-del.com/~alan/ |alan(a)ctrl-alt-del.com|

1 0

[GAK] Clipper chip
by nobody＠huge.cajones.com 17 Dec '03

17 Dec '03

Tim C[rook] May likes to lick the semen-shit mixture that accumulates in the crack of his mother's ass.

1 0

Re: Another Nutty Idea about SPAM
by ichudov＠algebra.com 17 Dec '03

17 Dec '03

Steven Garman wrote: > I have had yet another twisted idea. I would be interested in your thoughts. > > Once method of combatting the spammers is to use disinformation. For example > we use new addresses for their "remove" lists to check on their honesty. > > What about attacking the lists themselves with false data? Say you run a site. > You can make and delete accounts as you please. So, make a whole bunch of > new accounts, and submit them by various means to places that will probably > use them in bulk e-mail lists. Then, delete the accounts. Viola, the lists > have some worthless addresses. Another nutty idea: to create a database of people who do NOT want to receive unsolicited advertisements, and make it widely available. The obvious problem is that some very uncsrupulous spammers would want to grab this database and use it as a source of email addresses. This problem has a solution, however: instead of distributing people's email addresses, distribute MD5 checksums of their addresses. For example, an entry for ichudov(a)algebra.com would be b51175dae78f25427351d5e3ff43de30 There is no way to guess the original text from an MD5 checksum. Spammers should be advised to exclude all addresses with MD5 checksums from that database from the recipient list, and include instructions on how to get one added to the database into their spams. Database maintainers could even provide a email filter-bot that would accept recipient lists by email and send back the same lists, but WITHOUT addresses that wish not to receive spam. This way stupid low-tech spammers (who make up the majority) will be able to process their email lists quickly and easily. This database may be maintained centrally. Users may be able to sign up for inclusion into that database by email or by filling out a Web-based form. Identity verifications may be done by using cookie protocol. - Igor.

2 1

Re: Provably "Secure" Crypto
by Dana W. Albrecht 17 Dec '03

17 Dec '03

The Deviant <deviant(a)pooh-corner.com> writes: > On Mon, 25 Nov 1996, Dana W. Albrecht wrote: > > Rigorous proofs of the non-existence of an algorithm are not new. > > Neither are rigorous proofs that any algorithm which can solve a given > > problem requires a minimal running time. Or, in an even stronger sense, > > Hrmmm... I seem to see a problem (namely Moore's first law) in assigning > anything a "minimal running time". Perhaps "minimal instruction count" > would be more suited to your example. Because if you're talking about > time, it essentially boils down to "the longer something takes the less > time it takes". > > > that a particular known algorithm for a given problem is indeed a > > (provably) optimal algorithm for that problem. > > Never happen. It just won't. As a rule, there's _always_ a faster way. This is just simply not true. In fact, since you seem to have gracefully failed to quote the section of my prior post which demonstrates otherwise, let me re-iterate it: > > For a (non-cryptographic) example of a proof of the first sort --- that > > is, that "there exists no algorithm" --- consider the famous "Halting > > Problem" for Turing machines. (I believe someone else has also > > mentioned this.) There are many proofs such as this one, often related, > > though the Halting Problem itself is perhaps the most famous example. > > > > For an (again, non-cryptographic) example of a proof of the second sort > > --- that is, that "any algorithm that solves a given problem requires a > > minimal running time" --- consider the proof that the "minimal" number > > of key comparisons in the worst case required to sort a random list of > > elements for which only an ordering relationship is known is O(nlog(n)). > > See Knuth, Volume 3, section 5.3. For a simpler example, a standard > > "binary" search which requires O(log(n)) comparisons to find a given > > element in the worst case is provably the optimal algorithm for this > > task. Which part of this have you failed to understand? Look in section 5.3.1 of Volume 3 of "The Art of Computer Programming" by Knuth. You will find there a rigorous proof that the "information theoretic lower bound" of an algorithm which sorts by comparison of keys is O(nlg(n)). Alternatively, refer to section 6.2.1 of the same book where it is demonstrated that a binary search by comparison of keys on a sorted list where no other information is available is an "optimum" algorithm. If you wish to discuss this further, then you're going to have to directly address what's widely known and beautifully articulated in Knuth. > > Turning once again to cryptography, there is presumably an "optimal" > > algorithm for factoring a "general" number in the "worst" case. Of > > Ok, now I have to pose a question: If cryptographers actually beleive > this, why continue to search for a faster one. That's easy. That an "optimum" factorization algorithm exists does not mean it is _known_. Similarly, while one might demonstrate a mathematical lower bound on the worst-case running times of all possible (known and unknown) factorization algorithms, this does not mean that an actual algorithm which runs in this time is known, nor does it even mean that an actual algorithm which runs in this time even exists. If you want a completely useless (but easy to prove) lower bound on the number of operations a factorization algorithm must necessarily have, I submit to you a trivial one: 1. Proof of this is left to the reader. :) Proofs of more interesting lower bounds left to experienced mathematicians. > > Turning once again to cryptography, there is presumably an "optimal" > > algorithm for factoring a "general" number in the "worst" case. Of > > course, known algorithms for factorization seem to regularly improve and > > no one has even suggested that any current algorithm is (provably) the > > "optimal" algorithm. Worse case bounds on running time for currently > > known algorithms can certainly be produced, but no one currently knows > > if these are the best algorithms. > > Again I say, there's _always_ a faster way. No, there's not. While no proofs of useful lower bounds on factorization algorithms are presently known, this does NOT mean that they do not exist. That such proofs exist for other, simpler algorithms (see above) just simply refutes this statement. > > Obviously, discussion on this topic is unrelated to such security > > problems as implementation mistakes, fault analysis, outright theft of > > keys, etc. I hope that I've been careful to explain what I mean by > > "provably secure" and that it's not interpreted to include these types > > of attacks. > > Yes, I must commend you on your amazing tact in asking this incredebly > irrevelant question. You're welcome to think it's irrelevant. I, for one, am glad that people like Matt Blaze took the trouble to do some work in this area. I'm also grateful that this has been pointed out to me in response to my previous post. (Thanks to "Mark M." <markm(a)voicenet.com>) Dana W. Albrecht dwa(a)corsair.com

1 0

Re: Netscape working with the NSA.
by Greg Broiles 17 Dec '03

17 Dec '03

At 05:34 AM 11/26/96 +0000, Tim Tartaglia wrote: > >Check out the following: >http://www-tradoc.army.mil/dcsim/browser.htm > >Here's an excerpt: > >> ...Netscape has been working with NSA...Their proposed solution is based >> on the use of Fortezza card technology. In November NSA expects to >> certify Netscape Navigator 3.0 for "unclassified but sensitive" use... The NSA has two main tasks: gathering [foreign] signals intelligence ("SIGINT") and making it difficult/impossible for other parties to get signal intelligence from the US ("INFOSEC"). Given the context of the information you found, it looks like they're negotiating with Netscape and Microsoft to evaluate the strength of their browsers to that the browsers can be used for "unclassified but sensitive" tasks; that is to say, NSA is operating in their "protect domestic data" mode, not their "wiretap everything" mode. Certifying the browsers (or other domestic privacy tools) as safe if they're not (or if they've got designed-in weaknesses) would play a very dangerous game - the NSA would gain little and risk a lot. They could (and probably do, or will soon) mandate the use of GAK crypto for official "sensitive" applications; so adding hidden weaknesses (which are essentially stealth GAK) doesn't give them much they don't have already, but it does create the potential that a third party will learn of the hidden weakness (through careful study or exploiting a traitor or whatever) and then have access to information the gov't would like to keep private for an unknown period of time - followed by a sudden expensive & disruptive switch of crypto tools when the discovery of the weakness became known. So it seems unlikely that there's anything bad going on here; it doesn't make much sense for the NSA (or other TLA) to intentionally weaken a crypto app and then certify it as secure for government use. They want to keep the good stuff for themselves, and make us use the weak software. They don't seem to be especially shy about telling us when they want to spy on us. I suppose it's possible to see government contracts as a foot in the door to economic "incentivization", e.g., if Netscape and Microsoft want the govt's money/approval badly enough, they'll switch over to the dark side. But this danger is pretty much unavoidable; and the government's got enough ways to coerce folks (cf. Jim Bidzos and the guys who want to run him over in the parking lot) that this seems mild by comparison. If the government chooses to apply some pressure to incentivize a corporation, they'll find a way. So far, it appears that they played fair when they certified DES as secure - and folks on the outside have been banging away on DES for almost 20 years, without finding any trapdoors. The balance of risks suggests that they'll probably keep playing fair when certifying privacy tools; not because they're nice guys, but because it's in their best interests to do so. -- Greg Broiles | US crypto export control policy in a nutshell: gbroiles(a)netbox.com | http://www.io.com/~gbroiles | Export jobs, not crypto. |

1 0

Bounty Server, Revisited.
by Petro 17 Dec '03

17 Dec '03

I have started drafting a proposal statement for the Bounty server. This is where I am at right now. I need as many comments on this as to the way it will work as possible. I am posting this from petro(a)smoke.suba.com because that is my primary account rather than snow, which is only for cypherpunks. Sorry for any killfiles this sneaks by. Please reply to snow(a)smoke.suba.com or the list. Thanks. Bounty Server, The proposal: Version 0.1 Abstract: This proposal is an attempt to outline a system for awarding cash payments for the creation of new technologies without the overhead or ownership associated with conventional systems such as contract or work-for-hire, or employee-employer systems. The objective is to actually bring this system online. Background: There is a lot of software floating around. It basically falls into 5 catagories: Commercial, Shareware, Freeware, Gnu (and other "Copyleft" schemes) and Public Domain. <Need to fill this in, but at this point we all know what the 5 types are> It is the "Copylefted" software that interests me at this point. There is quite a bit of high quality "Gnu" software, and at least one operating system based on the GNU mentality (linux) however there is a dearth of _enduser_ tools such as mail and news readers for the more popular end user operating systems, word processors and graphics editing software, easy to use Graphic Design Software (TeX is NOT easy to use) and easy to use Cryptographic software. In order to get these kinds of tools, especially the Cryptographic tools widely deployed, there needs to be a reason for someone to invest the time and effort into polishing the user interfaces and designing them for the average internet user to operate. Figuring out new algorythms is fun. Being on the cutting edge, or flipping the bird at Governments is fun. Doing something that has already been done isn't nearly as sexy, yet to deploy the kinds of tools we want _today_ and promote the development of the kings of tools we will want tomorrow, there needs to be some sort of mechanism in place to pay programmers to make these tools. This mechanism (IMO) should be "market" driven, it should allow the community of users to decide which projects should have priority, and which shouldn't. This mechanism should be as flexible as possible. This mechanism should be as simple as possible, and as easy to use as possible. Originally I proposed this to apply to software, but I don't see why it should stop at software. Initally the server will be restricted to software, but I hope that this will work out, and be expanded further. The proposal: What I am going to attempt to do is to set up a "Bounty Server" where someone can iniate a "bounty" on a peice of technology. The initator will write up a set of specifications for the technology, and an initial award to be paid to the developer. They then post it on the server and send their initial "bid" to the organization. This is the "bounty". Other people can add to this bounty, allowing the totals to add until someone claims that bounty by providing proof of development to the initiator of the bounty. In software terms they would upload the software to the server and notify the originator of the bounty, and the server operators. Other technology will be figured out as it becomes necessary. Originally I was going to put the stipulation in that the software written must be Copylefted. I decided that that wasn't really necessary, but rather simply desired. To aid in that desire, I am going to build in an initative to releaseing the software "copylefted". To get more specific: A bounty is considered to be posted when the initial payment is cleared by the bank, and the specifications (discussed later are considered clear enough to avoid interpretation problems. The initial bounty contract gets posted to the WWW server, (possibly) to a "developers list" of interested people, and (possibly) to an appropriate UseNet Newsgroup. Once the bounty is posted, other people can "bid up" or add to the bounty, and their contribution will be added to the total bounty as well as their "name" (email address) added to a list of contributors (unless they request not to). The amount they gave will not be listed. It isn't important. At this point contributions and initial bids will be accepted by credit card, check, money order, and possibly ecash (e-cash will be taken at some point, but it really isn't important at this point since almost no one uses it.) The first developer to upload a _working_ package to the server will be awarded the total bounty, minus "brokerage" fees (discussed later) "First" will be soley determined by the time stamp of the server. As soon as the package is uploaded, the initiator and the server adminstrator will be notifed, and the bounty marked "claimed". If the package is accepted by the initiator, the bounty will be marked "closed", the package moved to an FTP site for distribution (if Copylefted) or moved offline if not (archived copies will be kept for legal reasons-- more on that later). At that point a check for the developer will be cut (or ecash mailed if that works out). The Server Adminstrator will also do an cursory check to make sure that there are no obvious copyright violations. In the event that there is a conflict between the initiator and the developer, the claim will go into adjudication. The server adminstrators decesion is final, and he will make every effort to settle the claim fairly. Adjudication will incur an additional fee (see the fees section). Writing the bounty: The bounty specifications should include the following: 1) Target Operating Enviroment (i.e. Operating System for Software, and whatever for other technology) 2) What the desired technology is intended to be used for (i.e. a Word Processor, a Hardware RNG etc, whatever) 3) Desired Characteristics of the technology--specific features of the technology. It isn't enough to say that you want a word processor, you must specify minimum features you wish this technology to contain (i.e. WYSIWYG, Postscript output, Outliner etc.) 4) Desired "quality" level: Proof of Concept, Alpha, Beta, Release etc. 5) Copyright status desired--whether the software will be owned by the initiator of the bounty (in which case it is unlikely that anyone else will contribute), owned by the programmer (well someone might be that magnanomous), or "copylefted". 6) Where the initiators money is to go if the bounty is not claimed: I will provide a short (8 or 10) list of charities that the money will go to if the bounty is not met. This is to keep the initiator honest, as well as the server. Each contributor will also get this choice. I am sure that I am missing something here, and I will need some assistance in fleshing this out, as well as a couple of people to write different specs as examples. Adding to the bounty: The bounty will be considered added to when the deposit clears and is credited by the bank. A person adding to the bounty will also be allowed to choose from the list as to where they would like their money to go if the bounty expires. Fees: The Organization will get 2% of any bounty where the software or Technology that is copylefted. 20% of any other scheme. Adjudication will incur an additional fee of 2 to 5% depending on the difficulty in judging the claim. All interest that acrues belongs to the Organization, and will be used to defray any costs, or to provide for additional bounties should there be an apprecialble excess. Status: At this point in time I am (obviously) still in the process of developing the procedures. I have registered a Domain Name (bounty.org) and I have a couple promises off assistance in certain areas. As well, I have a server to start off with. Where I need help at this point: Legal issues. Any lawyers want to talk to me about this? Comments. I will be working on this, revising it, and soon I will be putting it up on www.bounty.org. Postmodernism is the refusal to think--Ron Carrier petro(a)suba.com Deconstruction is the refusal to believe that anyone else can either. Revolution and War are not murder unless you lose. This is a basic tenet of civilization.--Jim Choate on the cpunks list.

1 0

Tell me this,referring to Symantec's claim.
by cracker＠icon.co.za 17 Dec '03

17 Dec '03

Okay granted,i am virtually sure Deeyenda does not exhist,but i asked a simple question. Altavista is a cute idea though ;) Who posted this shit then,someone care to get back to him???? >The internet community has again been plagued by another virus.This message is being spread >throughout the internet,including USENET posting,EMAIL and other inherent activities...The >reason for all the attention is because of the nature of this virus and the potential security risks >it makes.Instead of a destructive trojan virus (most viruses!),this virus,referred to as Deeyenda >Maddick,performs a comprehensive search on your computer,looking for valuable information >such as email and login,passwords,credit cards,personal info,etc. The Deeyenda virus also has >the capability to stay memory resident whil running a host of applications and operating systems, >such as Windows 3.11 and Windows 95.What this means to internet users is that when a login and >PASSWORD are sent to the server,this virus can COPY this information and SEND IT OUT TO AN >UNKNOWN ADDRESS (varies). >The reson for this warning is because the Deeyenda virus is virtually undetectable.Once attacked >your computer will be unsecure.Although it can attack any O/S,this virus is most likely to attack >those users viewing Java enhanced Web Pages (Netscape 2.0 + Microsoft Internet Explorer 3.0 + >which are running on Windows 95) . Researchers at Princeton University have found this on a >number of world wide web pages and fear its spread. > Please pass this on,for we must alert the general public at the security risks >Steven K. Johnson >Computer Center >Carnegie Mellon University >(412) 455-3756 >e-mail : SJohnson14(a)cmu.edu Sounds like a pretty amazing virus to me??? More a crock of shit than anything else,but... Hey maybe it'll run for president as well.... Sorry to inconvenience anybody,ridicule should have a purpose ;) J a m e s "Lead.Follow. Or get out of the way" -------------------------------------------------------------------------------------------- Type Bits/KeyID Date User ID pub 1024/9E318AA5 1996/09/24 Cracker <cracker(a)icon.co.za> -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.6.3ia mQCNAzJHdKwAAAEEALl3A6auLG0JLdtgEzl6KfPNqbTTSDX4L4To2b7PLqGDVV5r BezC9dD/ITrCK9M64juiQ2p/DNjIihnXlEsJCy2btypStypQgU1fvAei3AnZ1cQ8 NiAnHNS+ImUAJgZjSHEQSevGE53IUovmWQ7YHUz9VpTTCtoJoUKxYuqeMYqlAAUR tBxDcmFja2VyIDxjcmFja2VyQGljb24uY28uemE+iQCVAwUQMkd0rkKxYuqeMYql AQEjagP/cYgGLAkWZJLeRcM4URwBX3J/0R54DadVnsvvoxDkzilv7U02IXZGZGnA CvXsu2sThS7qDBiHFop/OZs3WmlQbQ4BAZ/hiCs5tSU2e7fkk0EKxsGAD1pTbw/J rRU4WePLc++vv+6CBKw5NCSR5kMh8H3X4qtZZ9dYX9zsuzWKdpk= =YGH8 -----END PGP PUBLIC KEY BLOCK-----

1 0

Tell me this,referring to Symantec's claim.
by cracker＠icon.co.za 17 Dec '03

17 Dec '03

Okay granted,i am virtually sure Deeyenda does not exhist,but i asked a simple question. Altavista is a cute idea though ;) Who posted this shit then,someone care to get back to him???? >The internet community has again been plagued by another virus.This message is being spread >throughout the internet,including USENET posting,EMAIL and other inherent activities...The >reason for all the attention is because of the nature of this virus and the potential security risks >it makes.Instead of a destructive trojan virus (most viruses!),this virus,referred to as Deeyenda >Maddick,performs a comprehensive search on your computer,looking for valuable information >such as email and login,passwords,credit cards,personal info,etc. The Deeyenda virus also has >the capability to stay memory resident whil running a host of applications and operating systems, >such as Windows 3.11 and Windows 95.What this means to internet users is that when a login and >PASSWORD are sent to the server,this virus can COPY this information and SEND IT OUT TO AN >UNKNOWN ADDRESS (varies). >The reson for this warning is because the Deeyenda virus is virtually undetectable.Once attacked >your computer will be unsecure.Although it can attack any O/S,this virus is most likely to attack >those users viewing Java enhanced Web Pages (Netscape 2.0 + Microsoft Internet Explorer 3.0 + >which are running on Windows 95) . Researchers at Princeton University have found this on a >number of world wide web pages and fear its spread. > Please pass this on,for we must alert the general public at the security risks >Steven K. Johnson >Computer Center >Carnegie Mellon University >(412) 455-3756 >e-mail : SJohnson14(a)cmu.edu Sounds like a pretty amazing virus to me??? More a crock of shit than anything else,but... Hey maybe it'll run for president as well.... Sorry to inconvenience anybody,ridicule should have a purpose ;) J a m e s "Lead.Follow. Or get out of the way" -------------------------------------------------------------------------------------------- Type Bits/KeyID Date User ID pub 1024/9E318AA5 1996/09/24 Cracker <cracker(a)icon.co.za> -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.6.3ia mQCNAzJHdKwAAAEEALl3A6auLG0JLdtgEzl6KfPNqbTTSDX4L4To2b7PLqGDVV5r BezC9dD/ITrCK9M64juiQ2p/DNjIihnXlEsJCy2btypStypQgU1fvAei3AnZ1cQ8 NiAnHNS+ImUAJgZjSHEQSevGE53IUovmWQ7YHUz9VpTTCtoJoUKxYuqeMYqlAAUR tBxDcmFja2VyIDxjcmFja2VyQGljb24uY28uemE+iQCVAwUQMkd0rkKxYuqeMYql AQEjagP/cYgGLAkWZJLeRcM4URwBX3J/0R54DadVnsvvoxDkzilv7U02IXZGZGnA CvXsu2sThS7qDBiHFop/OZs3WmlQbQ4BAZ/hiCs5tSU2e7fkk0EKxsGAD1pTbw/J rRU4WePLc++vv+6CBKw5NCSR5kMh8H3X4qtZZ9dYX9zsuzWKdpk= =YGH8 -----END PGP PUBLIC KEY BLOCK-----

1 0

Re: Another Nutty Idea about SPAM
by Omegaman 17 Dec '03

17 Dec '03

> Steven Garman wrote: > > Once method of combatting the spammers is to use disinformation. For example > > we use new addresses for their "remove" lists to check on their honesty. > > > > What about attacking the lists themselves with false data? Say you run a site. (snip) Igor Chudov wrote: > Another nutty idea: to create a database of people who do NOT want to > receive unsolicited advertisements, and make it widely available. Of course. But this does not address the issue of "unscrupulous spammers" which is what Steven was commenting upon. > The obvious problem is that some very uncsrupulous spammers would want > to grab this database and use it as a source of email addresses. > > This problem has a solution, however: instead of distributing people's > email addresses, distribute MD5 checksums of their addresses. For > example, an entry for ichudov(a)algebra.com would be > > b51175dae78f25427351d5e3ff43de30 > > There is no way to guess the original text from an MD5 checksum. > > Spammers should be advised to exclude all addresses with MD5 checksums from > that database from the recipient list, and include instructions on how > to get one added to the database into their spams. Okay fine. The spammer is "advised" but if he is unscrupulous in the first place, he'll simply ignore the advice and continue bulk-mailing to every address he can grab. > Database maintainers could even provide a email filter-bot that would > accept recipient lists by email and send back the same lists, but > WITHOUT addresses that wish not to receive spam. This way stupid > low-tech spammers (who make up the majority) will be able to process > their email lists quickly and easily. Indeed, stupid low-tech spammers would benefit from such a service if they wish to honor "do not send" requests. > This database may be maintained centrally. Users may be able to sign up > for inclusion into that database by email or by filling out a Web-based > form. Identity verifications may be done by using cookie protocol. I like the idea and if I had the resources, I would do it personally. Optimistically, many bulk e-mailers would sign on to the plan. (Ironically, one would probably have to solicit bulk e-mailers to sign up). However, many, being unscrupulous, ignorant, etc. will not be involved. The only way I see to get bulk e-mailers to utilize this service is to offer a positive and/or negative incentive for usage of the service. ie. "What do I gain by elminating people from my bulk mail-outs? What can be done if I don't follow this protocol?" Ideas? Comments? me -------------------------------------------------------------- Omegaman <mailto:omega@bigeasy.com> PGP Key fingerprint = 6D 31 C3 00 77 8C D1 C2 59 0A 01 E3 AF 81 94 63 Send a message with the text "get key" in the "Subject:" field to get a copy of my public key. --------------------------------------------------------------

3 3

Re: Provably "Secure" Crypto
by peter.allan＠aeat.co.uk 17 Dec '03

17 Dec '03

Dana W. Albrecht originally wrote: > Rigorous proofs of the non-existence of an algorithm are not new. > Neither are rigorous proofs that any algorithm which can solve a given > problem requires a minimal running time. Or, in an even stronger sense, > For a (non-cryptographic) example of a proof of the first sort --- that > is, that "there exists no algorithm" --- consider the famous "Halting > Problem" for Turing machines. (I believe someone else has also > mentioned this.) There are many proofs such as this one, often related, > though the Halting Problem itself is perhaps the most famous example. > > For an (again, non-cryptographic) example of a proof of the second sort > --- that is, that "any algorithm that solves a given problem requires a > minimal running time" --- consider the proof that the "minimal" number > of key comparisons in the worst case required to sort a random list of > elements for which only an ordering relationship is known is O(nlog(n)). > See Knuth, Volume 3, section 5.3. For a simpler example, a standard > "binary" search which requires O(log(n)) comparisons to find a given > element in the worst case is provably the optimal algorithm for this > task. Dana W. Albrecht (dwa(a)corsair.com) replies to The Deviant <deviant(a)pooh-corner.com> like this: > Which part of this have you failed to understand? Look in section 5.3.1 > of Volume 3 of "The Art of Computer Programming" by Knuth. You will find > there a rigorous proof that the "information theoretic lower bound" of > an algorithm which sorts by comparison of keys is O(nlg(n)). That is a bound on a _reliable_ algorithm. A faster one is to shuffle the elements and present it as sorted. Lightning fast, but only with low probability of correctness. That is what we are up against in a key search attack. The other guy just might guess my 100 bit key first time, millionth time or whatever - early enough anyway. So to get a lower bound you have to show that a lucky guess cannot be distinguished from an unlucky one - and if you do that without a one time pad I take my hat off. -- Peter Allan peter.allan(a)aeat.co.uk

1 0