December 2003 - cypherpunks-legacy

Re: Other forms of strong cryptography
by smb＠research.att.com 17 Dec '03

17 Dec '03

Why is it that the idea of taking a difficult problem, such as a knapsack problem, and using it to encode ciphers, was abandoned? Too many trapdoors? These NP-complete type problems seem ideal since they can be verified in polynomial time, but are practically impossible to solve for any significant input. Verification of a solution could be decryption, where the solution is the key, and the problem could be used to encode the text somehow. I understand that Shamir broke the knapsack problem. So, is that enough reason to completely abandon this approach? Nobody seems to talk about it anymore. The approach hasn't been abandoned; it's just a lot harder than it looks, for a number of reasons. First is that complexity theory says nothing about the average difficulty of solving a problem, as opposed to the worst case. A cryptosystem that only hides 1% of the messages isn't very useful. Second, finding a suitable problem -- one that has a keyed back door isn't that easy. Third -- and this is what sunk the knapsack problem -- you need a cryptosystem that exploits the full NP-complete problem, as opposed to just a simple case. (The knapsack problem was solvable by someone who knew the key because it wasn't a general knapsack, but a super- increasing sequence -- each number in it was greater than the sum of all of its predecessors. (This was the simplest version; there were, I believe, some others.))

1 0

MIT Guide to Lockpicking
by an43512＠anon.penet.fi 17 Dec '03

17 Dec '03

I want to share with you an interesting story about information sharing, copyrights, artistic control and lockpicking. Long ago I wrote the MIT Guide To Lockpicking, and wanted to limit its distribution (for reasons that are no longer apparent). I decided to delete the electronic forms, and just allow the distribution of hardcopy. That worked for many, many years. Over the summer, I started taking steps to publish the Guide electronically, but I was beaten to the punch-line by some cyberpunks who scanned it in, and posted it. On the whole I don't mind, since I was planning to publish it anyways, but it does feel wrong that as the author of this work I do not have any say over its distribution anymore. The copyright notice in the Guide says that it can be feely distributed, but at the time, that meant hardcopy form, because scanners were too expensive for anyone to be likely to scan in the guide, and the printers had not reached any standard for expressing pictures. Thus, the original copyright notice did what I wanted. As technology changed, the term "feely" came to mean "very feely in any form". Oh well. Is there any crypto technology that would allow an author to control derivative works based on something that has been published on the network as a postscript file, or a latex source file? I know that a worked could be signed to indicate that it is "authorized", but can any more be achieved? For your information, I have attached the posting announcement I sent to the alt.locksmithing. Hopefully someone will place the Guide in an FTP site soon (any volunteers from soda?), as I do not want to be sending out email copies. By the way, having a pseudonym to carry out correspondence as "Ted The Tool" was an enabling technology for me to post the Guide, and to request cooperation on producing the next revision. Thank you for creating this technology. Sincerely, Ted The Tool ------------------------------------------------------------------------- To find out more about the anon service, send mail to help(a)anon.penet.fi. Due to the double-blind, any mail replies to this message will be anonymized, and an anonymous id will be allocated automatically. You have been warned. Please report any problems, inappropriate use etc. to admin(a)anon.penet.fi.

1 0

"ignore them"
by George A. Gleason 17 Dec '03

17 Dec '03

The simple solution to pesky posts is, as soon as you see it's something you're not interested in, press ctrl C and go on to the next posting. If someone's being a real online pest, ignore them and maybe they'll go away. -gg

1 0

on line books & credit card scams
by remail＠tamsun.tamu.edu 17 Dec '03

17 Dec '03

Forwarded message:

1 0

Knapsack Cryptosystems
by Brian A. LaMacchia 17 Dec '03

17 Dec '03

From: smb(a)research.att.com To: an41418(a)anon.penet.fi Cc: cypherpunks(a)toad.com Date: Tue, 19 Oct 93 04:34:58 EDT For a good survey paper of knapsack cryptosystems, see [1]. Third -- and this is what sunk the knapsack problem -- you need a cryptosystem that exploits the full NP-complete problem, as opposed to just a simple case. (The knapsack problem was solvable by someone who knew the key because it wasn't a general knapsack, but a super- increasing sequence -- each number in it was greater than the sum of all of its predecessors. (This was the simplest version; there were, I believe, some others.)) Even knapsack cryptosystems that exploit the full NP-complete problem may still be susceptible to general attacks, depending on their density (a property of the weights of the knapsack problem). If the weights $a_i$ are too large, you get a "low-density knapsack" (i.e. you're sending lots of bits of cyphertext to hide few bits of plaintext). Brickell [2] and Lagarias and Odlyzko [3] showed that there are general attacks against subset-sum problems with density < 0.6463... In [4] we showed that this bound can be improved to about 0.9408... Joux and Stern came up with essentially the same result at about the same time [5]. (Note that if your density is > 1, then you have the possibility of two different plaintexts encrypting to the same ciphertext. Without more information, the encryption can be ambiguous.) We combined our two techniques in a joint paper -- you can get it via anon. FTP from martigny.ai.mit.edu in pub/bal/sumcc.ps, if you're interested. --bal References: [1] A. M. Odlyzko, The rise and fall of knapsack cryptosystems, {\it Cryptology and Computational Number Theory}, C. Pomerance, ed., Am. Math. Soc., Proc. Symp. Appl. Math. {\bf 42} (1990), 75-88. [2] E. F. Brickell, Solving low density knapsacks, {\it Advances in Cryptology, Proceedings of Crypto '83}, Plenum Press, New York (1984), 25-37. [3] J. C. Lagarias and A. M. Odlyzko, Solving low-density subset sum problems, {\it J. Assoc. Comp. Mach.\/} {\bf 32(1)} (January 1985), 229-246. [4] M. J. Coster, B. A. LaMacchia, A. M. Odlyzko and C. P. Schnorr, An improved low-density subset sum algorithm, {\it Advances in Cryptology: Proceedings of Eurocrypt '91}, D. Davies, ed., to appear. [5] A. Joux and J. Stern, Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems, to be published.

1 0

No Subject
by Anonymous 17 Dec '03

17 Dec '03

S. Boxx wrote: >THE CYPHERPUNKS HAVE BEEN POISONED WITH LIES AND HIGH TREACHERY. THOSE >WHO DO NOT CONFESS WILL BE EXPOSED. THE FRAUDS AND THE POSEURS WILL BE >RUTHLESSLY PUNISHED. IF NECESSARY, ON TALK.POLITICS.CRYPTO OR IN THE >MAINSTREAM MEDIA. > >YOU HAVE BEEN WARNED. Jeez... switch to decaf.

1 0

Re: jrk@sys.uea.ac.uk (Richard Kennaway)
by nobody＠cicada.berkeley.edu 17 Dec '03

17 Dec '03

> From: peb(a)procase.com (Paul Baclace) > > >Go to you local copier store. Pay cash. No one will care. > > I'm talking about buying the color *copier* itself. In all the > copier businesses I've seen, none of them allowed one to make > color copies unattended. Is this because they are complicated > or expensive per copy or because of some kind of technology > restriction (e.g., high quality color copies cannot simultaneously > be anonymous and private). I've got friends who've had unlimited, unsupervised access to color copiers at their schools or offices (art students, designers). It's not such a big deal. I have even color-xeroxed currency several times (mainly for a zine I used to edit, wherein we encouraged people to deface money). The reactions of the employees of the copy shops ranged from complete indifference to "you know, this is illegal," but I never had anyone refuse. -Mr. Funn

1 0

ISS
by Anonymous 17 Dec '03

17 Dec '03

Can someone point me in the direction of this ISS program? BTW, Is this a DOS or UNIX binary? Is it in source or already compiled? Thanks in advance...

1 0

META: Re: jrk@sys.uea.ac.uk (Richard Kennaway)
by jrk＠sys.uea.ac.uk 17 Dec '03

17 Dec '03

It's all very flattering to see my name in lights, but could everyone responding to this thread on color copiers please change to a more informative title? -- ____ Richard Kennaway __\_ / School of Information Systems Internet: jrk(a)sys.uea.ac.uk \ X/ University of East Anglia uucp: ...mcsun!ukc!uea-sys!jrk \/ Norwich NR4 7TJ, U.K.

1 0

Color Copiers/Re: jrk@sys.uea.ac.uk (Richard Kennaway)
by peb＠PROCASE.COM 17 Dec '03

17 Dec '03

Well, I'm glad to hear that use of color copiers isn't highly restricted, although there seems to be a good amount of misinformation (probably intentional from the SS). This is an example of a technology that cannot be controlled so the government uses warnings and threats. Similarly, (non-escrow) crypto could end up like this: penalties could be applied if it is used for illegal activity. If such a law were proposed, it would be difficult to oppose it on the basis of freedom of expression. Paul E. Baclace peb(a)procase.com

3 2