December 2003 - cypherpunks-legacy

No Subject
by pcw＠access.digex.net 17 Dec '03

17 Dec '03

> > I wonder if Jesus can create a number so large he can't factor it? This is a trope on the old question of whether an all powerful God could make something so big that even he couldn't move it. I.e Church/Rosser before they "conceived" of that theorem. The question is whether there is any strict bounds on the complexity of making rocks and moving rocks. I would think that making and moving rocks is in the same complexity class. The effort to make a rock is undoubtably linearly related to the size of the rock. At least in the asymptotic case. Here's an algorithm that proves it's linear. Make a small rock. Repeat until the size is big enough. Gravity will pull it together once the rock is big enough. So this proves that the cost is at least asymptotically linear. The effort to move a rock is also linearly related to the mass of the rock. F=ma. So we can see that these are in the same complexity class. That means we can't really be sure whether he could make some rock that was slightly bigger than he could move. The complexity theory really isn't strong enough to solve it. On the other hand, creating composite numbers with two large, relatively equally sized prime factors is pretty easy to do in time linear to the number of bits. Factoring that number still requires time _exponentially_ proportional to the number of bits. So if the God had a finite amount of effort available, (but still beyond the ken of mere mortals) then I think it is safe to say that he COULD create numbers so big that even he couldn't factor them. Now what if God had a _countable_ amount of effort available? Then he should be able to factor any number that he created. I think that this follows from the same proof that shows that the rational numbers are countable. --Peter "I would build my Church/Rosser on this Rock" Wayner {I keep trying to stop making this pun, but it keeps pulling me back in.}

1 0

Re: T-Shirts, Neil Young, Asilomar, and Smalltalk
by Phil G. Fraering 17 Dec '03

17 Dec '03

Aren't there freely available versions of Smalltalk for Unix? GNU Smalltalk apparently lacks the classical graphic interface, but from what I've seen, so does Perl ;-) pgf

2 1

Fractal steganography
by nobody＠jarthur.cs.hmc.edu 17 Dec '03

17 Dec '03

Hi, sorry if this appears twice, but I sent it a few days ago and it never turned up. Recent mention of using fractals for steganography of PGP-encrypted messages reminded me that I'd never seen this announcement posted to cypherpunks... >>>BEGIN INCLUDED MESSAGE >Newsgroups: sci.crypt,alt.security.pgp >From: qwerty(a)netcom.com (-=Xenon=-) >Subject: New Steganograph Available >Date: Sun, 13 Mar 1994 04:50:27 GMT -----BEGIN PGP SIGNED MESSAGE----- Henry Hastur's latest. This thing generates fractals, hiding a PGP or Stealth PGP message in them as well. I have put it up for ftp at ftp.netcom.com in /pub/qwerty, as MandelSteg1.0.tar.Z. Also there, is a "Steganography.software.list", and other steganographic software. -=Xenon=- P.S. I will forward mail to "Henry" if you would like to contact him. -----BEGIN PGP SIGNATURE----- Version: 2.3 iQCVAgUBLYJUWgSzG6zrQn1RAQEL0AQAutxwMCxCS09qdZFGxuO9+9kqUkigm2Jk 0ng+uZkAPuh9J8TNOg+xSaqoil2+AOYyQmUB1w/5HablUL22BffvX9omfkkAWFYR gPRBIC1Dr56SP/PmZnLTQxjjUm5HfHupZHJCGs268uffizufi6Rzahp9y0iJ0YGf JH/cGCpQqEQ= =pA25 -----END PGP SIGNATURE----- MandelSteg V1.0 and GIFExtract V1.0 ----------------------------------- These two programs allow you to hide confidential data in fractal GIF images, giving an increased level of security compared to sending PGP-encrypted email over the Internet. MandelSteg will create a Mandelbrot image (though it could easily be modified to produce other fractals), storing your data in the specified bit of the image pixels, after which GIFExtract can be used by the recipient to extract that bit-plane of the image. MandelSteg is not intended to replace the standardised methods of using encryption (e.g. ASCII-armoured PGP email) ; in an ideal world we would all be able to send openly encrypted mail or files to each other with no fear of reprisals, however there are often cases when this is not possible, either because the local government does not approve of encrypted communication, or perhaps because you are working for a company that does not allow encrypted email but doesn't care about Mandelbrot GIFs. This is where steganography can come into play. You will probably find that you also need to get hold of a copy of an interactive Mandelbrot viewer in order to determine suitable coordinates to use for images. There are numerous such viewers available on the Internet and BBS systems (e.g. xmandel). MandelSteg - 'Mandelbrot Steganography' --------------------------------------- MandelSteg has numerous modes of operation, depending on the level of security you desire. With no command line options specified it will simply generate a 640x480 GIF of the default section of the set, and send it to stdout. With the -c option it will calculate how many bytes can be stored in the image and with -e will take the data fed to stdin and hide it in the image (specify a file name after the -e to write it to a file), and pad out the data with random bytes if neccesary if -r was specified. For the lowest security level, the data will simply be stored in the specified bit of each pixel, and a 128-color palette created such that the pixel looks the same regardless of whether there is data stored in it or not. This will be sufficient to survive a cursory examination, but will be obvious to anyone versed in the arts of steganography - in particular replacing the supplied palette for the image with another will show up the data bits hidden in areas of solid color. To avoid this problem, you should specify the -ns flag, which will only store data in areas of non-solid color (note that this can greatly decrease the amount of data that you can store in the image). Another indication of a steg-ed image is the duplicated 128-color palette, which can be replaced with a 256-color palette with the -fp flag. Obviously if you specify -fp and don't specify -ns, you will produce a readily apparent steg-ed image. If you don't have enough space for your data in the image, you can simply increase the size of the image by using the -sz flag, followed by the width and height in pixels. Alternatively, you can select a different area of the mandelbrot set by using -md followed by the start x, start y, width and height, specified with floating-point values. Finally, you can specify the bit to store the data in using -b followed by the bit number, otherwise the program defaults to bit seven. Bit seven gives the best performance, but bit zero should give the most security. You can also specify that a number of bytes in the image should be missed out before the encrypted data with the -bp option, followed by the number of bytes to miss out. If the -r option is specified, then random data will be placed in these bytes, and also appended to the input data to completely fill the specified bitplane. Compilation: ------------ On a BSD unix system you should be able to simply extract the source and run make to generate the executables. On a System V version of Unix you will need to edit the makefile to use one of the 'CFLAGS = ... -DSYSV ...' lines instead of the default. If you have plenty of memory, you can undefine LOW_MEM, which will improve performance slightly. On an MS-DOS machine with the Microsoft C compiler, simply execute COMP.BAT. This batch file will compile and link the source to build the executables. Sorry, but I was too lazy to create a proper DOS makefile ! Examples of use: ---------------- [ Note : Due to file system limits, on MS-DOS the executable names are mandsteg and gifextr rather than mandelsteg and gifextract. Also note that unless you have an 80x87 coprocessor or are running on a 486DX+ processor, mandsteg will run VERY slowly due to the number of floating point operations required ! ] Store file in 640x480 mandel.gif : mandelsteg -e mandel.gif < file.dat Store file in 400x400 mandel.gif, using non-standard co-ordinates : mandelsteg -sz 400 400 -md -0.5505 -0.5505 0.0001 0.0001 -e mandel.gif < file.dat Encrypt file with PGP, strip headers with stealth, and store in bit 0 of mandel.gif with non-standard coordinates, using 256-color palette and not storing in solid colors, with 23 byte random prefix : pgp -ef < secrets.dat | stealth | mandelsteg -sz 400 400 -md -1.0 -1.0 2.0 2.0 -b 0 -ns -fp -bp 23 -r -e mandel.gif Test non-standard coordinates for available space : mandelsteg -ns -sz 400 400 -md -0.5505 -0.5505 0.0001 0.0001 -c > /dev/null Generate image containing random data to annoy cryptanalysts : mandelsteg -fp -r -ns -e annoying.gif < /dev/null Error messages: --------------- The only likely error messages will indicate either invalid commands, or that the input data has been truncated (i.e. not all the data that was piped into the program could be stored in the GIF file). In the latter case, you should create a larger file to store the data. Security: --------- Well, frankly, it's not that secure, even with -ns -fp -b ? -bp ? specified on the command line. There are several main reasons : 1. In essence, mandelsteg can be regarded as a one-time pad cipher using the mandelbrot image as the pad. As a result, the 'key' to this cipher would be the coordinates and size of the area you've generated, as with that data the cryptanalyst would be able to generate the 'real' image and compare it to the steg-ed image to find the data. Two important things to realise here as a result are that a) you should *never* use the default coordinates for secret data, and b) you should never use the same coordinates twice. 2. Obviously, any cryptanalyst out there can just run 'gifextract' on the image, and your data will come out ! It may take sixteen or more attempts using the different bit values, -bp values and -ns options, but it will extract a valid copy of the data. And if the data has a PGP header or something, well, they've got you. This can be hindered by either using 'Stealth' to produce headerless data, or by generating large numbers of images containing random data to provide a cover for the real data. 3. Typically, a mandelbrot image consists of about 55 % of one bits and 45 % of zero bits. If you have replaced this with a PGP-encrypted messge, these frequencies will be more like 50% each. If you use an image much larger than neccesary, and a large -bp value, this will be somewhat disguised. 4. The standard random() function is used to generate random padding, and the distribution of bits in the output wil therefore probably be different to that expected for encrypted data. If you are attempting to get data past a serious adversary, you should replace this with a cryptographically strong random number generator such as the idea_rand() function used in PGP. In most cases, none of these should be a real problem, as MandelSteg is not intended to provide foolproof security against cryptanalysis, but primarily to prevent cryptanalysis by disguising the fact that you are sending encrypted messages at all. In addition, YOU SHOULD ALWAYS VIEW THE IMAGE BEFORE SENDING IN CASE YOUR CHOICE OF PARAMETERS HAS PRODUCED UNEXPECTED ARTIFACTS IN THE OUTPUT IMAGE !!!!!!!! Excuse the shouting, but ths is important... 8-). I haven't seen any strange results yet produced by the algorithm, but you only need to accidentally miss out a command line parameter once and your use of steganography will be obvious to anyone examining the image. GIFExtract ---------- GIFExtract is a very simple program, which simply extracts the specified bitplane from an image and sends the data to stdout. The program defaults to extracting bit 7 of each pixel, but the bit can be specified with the -b command line option, with -ns it will only extract data from non-solid areas, -bp can be used to ignore the first specified number of bytes extracted, and -a to analyse the distribution of zero and one bits in the image. Examples of use --------------- Extract bit-plane 4 from foo.gif into secrets.pgp : gifextract -b 4 foo.gif > secrets.pgp or gifextract -b 4 < foo.gif > secrets.pgp Analyse bit plane 1 of foo.gif for one bit and zero bit frequencies prior to using it for steganography : gifextract -a -b 1 foo.gif Extract the secrets.dat file that was used in the mandelsteg example above, if your PGP key id is 23ffff : gifextract -b 0 -bp 23 -ns mandel.gif | stealth -a 0x23ffff | pgp -f > secrets.dat Error messages -------------- The only likely error messages will be due to either failure to allocate the required memory for GIF decompression, or failure to open the input file. DISTRIBUTION NOTES ------------------ Either of these programs can be freely distributed, however you must take into account any prevailing cryptography import and export regulations in international transfers. This program was written outside the US, and as such copies should be available from European ftp sites as well. Henry Hastur >>>END INCLUDED MESSAGE

1 0

Distributed "Family" of processors
by PMARKS＠VAX1.UMKC.EDU 17 Dec '03

17 Dec '03

I recognized the basic schema in the following from the history of the French Resistance movement. The idea is for critical information to be held in separate "cells" each of which knows only enough to inteact with the others, but not enough to compromise the entire net. ************************************************************************** Consider three sets of code in three computers that constitutes a "Family"(the whole program). "Grandpa" talks to "Pa". "Pa" then talks "Son". "Son" then talks to "Grandpa". Each "Family" member closely monitors its cup clock & if its expected message is not received on time - it suicides! Capture "Pa" & in seconds, "Grandpa" & "Son" take their own lives! That is to say, they scramble certain essential parts of themselves including cryptographic sections. ************************************************************************** In any covert activity, many conditions will lead to a mission abort. This is largely due to the paranoid nature of the activity and the low level of trust in others neccessitated by said activity. If even one aspect seems "wrong" the meeting, transmission, transfer, trade, whatever, is called off. No offense intended, and ususally none taken. When you are trying to be covert, everyone fears compromise. A computer system so paranoid that it swallows a poison-pill whenever it suspects unauthorized tampering (read: investigation) would be fairly secure, but unreliable. ***Many*** conditions would trigger the "trip-wire" mech- anisms so the system would have to have a high order of built-in redundency. What it always boils down to is, "who do you **really** trust?". Or, boy was my face red when I found out I vouched for my best friend's public key only to find out that he worked for the NSA. (Think it doesn't happen? HUMINT will tell you much more than Signal Analysis ever will.)

2 1

Remailers
by David Merriman 17 Dec '03

17 Dec '03

I 'know' that a decent remailer will time-delay forwarding messages so as to throw sand in the gears of traffic analysis. I wonder if it wouldn't help more if the remailer(s) were set up so that people could send 'dummy' messages to them. That is, say I wanted to ensure that traffic analysis on myself were made as difficult as possible. I could Email something to a remailer with an embedded 'flag' or code (ex: blackhole, disposal, trash, etc) telling it to forward the message to the Bitbucket. Alternatively, I could include some other code or flag (ex: rubber, bounce, ricochet, etc) telling it to take the included (dummy) data, scramble it some, and return it some random time later. Alternatively, the remailer could take a so-tagged message, generate some random data of similar size, and send it (along with my address) to another remailer that it knew about, which would generate *different* random data, and sent that back to me. Wouldn't something like this further complicate traffic analysis, or would it just constipate the net? Dave Merriman - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Politics: fr. Latin 'poly' meaning 'many'; 'ticks' small blood-sucking parasites.

1 0

Re: Remailers
by Hal 17 Dec '03

17 Dec '03

From: David Merriman <merriman(a)metronet.com> > That is, say I wanted to ensure that traffic analysis on myself were made > as difficult as possible. I could Email something to a remailer with an > embedded 'flag' or code (ex: blackhole, disposal, trash, etc) telling it > to forward the message to the Bitbucket. Try chaining the message through multiple remailers, then to a bitbucket address. One such address is "nobody(a)soda.berkeley.edu". Presumably there are many of this type. > Alternatively, I could include > some other code or flag (ex: rubber, bounce, ricochet, etc) telling it to > take the included (dummy) data, scramble it some, and return it some > random time later. Send yourself an encrypted message, chaining through a bunch of remailers. See the cypherpunks ftp archive on soda.berkeley.edu for scripts which will let you do these things. Hal

2 1

current remailer list?
by jdblair＠nextsrv.cas.muohio.EDU 17 Dec '03

17 Dec '03

Would someone please forward me, or tell me know where I can find, a current list of remailers? I am no longer on the general cypherpunks list-- please e-mail me directly. thanks in advance, -john. -------------------------------------------------------------------------- John Blair: <jdblair(a)nextsrv.cas.muohio.edu> voice: (513) 529-4877 http://phoenix.aps.muohio.edu/users/jdblair/home.html KILL YOUR PGP public key available upon request. TELEVISION

1 0

Re: Byzantine Agreement Problem
by collins＠newton.apple.com 17 Dec '03

17 Dec '03

The "Byzantine Agreement Problem" is _not_ solved in theory. The last time I surveyed the literature, it was still widely conjectured to be theoretically intractable. It has direct implications on networks and networked systems; however, often some of the constraints of the original problem can, with effort, be violated---which makes practical systems more feasible. These violations usually take the form of a second, more reliable, band of communication. Scott Collins | "That's not fair!" -- Sarah | "You say that so often. I wonder what your basis 408.862.0540 | for comparison is." -- Goblin King ................|.................................................... BUSINESS. fax:974.6094 R254(IL5-2N) collins(a)newton.apple.com Apple Computer, Inc. 5 Infinite Loop, MS 305-2D Cupertino, CA 95014 ..................................................................... PERSONAL. 408.257.1746 1024:669687 catalyst(a)netcom.com

1 0

Re: current remailer list?
by jdblair＠nextsrv.cas.muohio.EDU 17 Dec '03

17 Dec '03

Before my mailbox is filled with answers, thanks to Karl Lui Barrus for answering my request for a remailer list. -john. -------------------------------------------------------------------------- John Blair: <jdblair(a)nextsrv.cas.muohio.edu> voice: (513) 529-4877 http://phoenix.aps.muohio.edu/users/jdblair/home.html KILL YOUR PGP public key available upon request. TELEVISION

1 0

Clipper LEAF Holes?
by Mike Ingle 17 Dec '03

17 Dec '03

As I understand the Clipper/Capstone LEAF, it works like this: Take 80-bit session key. Encrypt with device-unique key. Add 32-bit serial number and 16-bit checksum. Encrypt resulting 128-bit packet with family key. One of the EES chips, the type designed for cellular and other phones, operates in "1-bit CFB mode". This would seem to indicate that it is a straight-thru device - that the data input and output rates are the same. So the LEAF is only sent once; it is not repeated throughout the output. The user is forced to send a valid LEAF because the receiving chip will not set up without receiving a LEAF. But how does the receiving chip check to see if the LEAF is valid? The obvious way is to decrypt it with the family key, and then verify the checksum. But EES chips for different countries will have different family keys. So if an American EES chip sends a LEAF to a foreign one, how does the foreign one verify the LEAF? Even if the receiver can decrypt the first level of the LEAF and examine the checksum, it doesn't have your device-unique key, so it cannot check to see if the session key in the LEAF is the same session key that you sent to it. So it would seem that any valid LEAF would work, even if it is not the one for the current session key. Am I missing something in the Clipper design which prevents this? --- Mike

1 0