August 1993 - cypherpunks-legacy

cypher breaking and genetic algorithms
by bill＠twwells.com 20 Aug '93

20 Aug '93

Well, since I'm here, I thought I'd satisfy a curiosity of mine. Has anyone done any research, formal or informal, on the use of genetic algorithms to break cyphers? If not, would anyone care to discuss how it might be done?

2 1

building a sound sampler for cryptophone application...
by gtoal＠an-teallach.com 20 Aug '93

20 Aug '93

In article <9308201757.AA04239(a)soda.berkeley.edu> hughes(a)soda.berkeley.edu writes: > That said, I think that designing custom hardware for sound sampling > is a waste of time, given the abundance of multimedia cards that > already work. Yes, but have you ever tried to drive them from a C program? From the scanty docs I got with my Soundblaster, I wouldn't know where to start. And I get the impression that there's a major cpu overhead with these cards, like you can't actually do anything useful apart from grab the data. I want the data input to be free so there's CPU left over for compression and encryption and network or modem driving, without having to use a 66MHz 486 to do it... Oh, and multimedia cards are pretty expensive. This will cost maybe $25 at most. It's the sort of thing that once designed, hardware-inclined cypherpunks could hack up dozens of at home and pass them on at conventions like HoHoCon or the one we just had in the Netherlands... > While I applaud your enthusiasm, your effort toward getting usable > secure phones would be much betting spent writing device drivers for > various soundblaster-type cards. *My* effort already is being better expended elsewhere. As I said, my old uncle has time on his hands and wanted suggestions; I thought it was better not to squander such an opportune resource on junk like chiming doorbells when he could be doing something for us just as easily. Now, if anyone actually has an answer to the question, which was about how to drive a PC parallel port for input, do let me know please. regards Graham === Personal mail to gtoal(a)gtoal.com (I read it in the evenings) Business mail to gtoal(a)an-teallach.com (Be careful with the spelling!) Faxes to An Teallach Limited: +44 31 662 4678 Voice: +44 31 668 1550 x212

2 1

Thurn, Thurn, Thurn (und Taxis, too!)
by tcmay＠netcom.com 20 Aug '93

20 Aug '93

J. Eric Townsend writes: >Eric Hughes writes: > > alt.w.a.s.t.e > >please make it alt.waste, or alt.w-a-s-t-e if you must have seps >between letters. The additional '.' characters will cause a >hierarchy: > >alt.w >alt.w.a >alt.w.a.s >alt.w.a.s.t >alt.w.a.s.t.e For the first 3/4 of "The Crying of Lot 49," Oedipa Maas thinks she is seeing "WASTE" written on boxes and mail drops. It is only later, as she is travelling through Berkeley by AC-DC ("standing for Alameda County Death Cult"), that she notices the periods, writ very small (.). So calling our cyberspace mail drop "alt.waste" would have resonances with this Oedipal error, allowing the correcting of newbies. Don't Ever Antagonize the Horn. (I hear you crying "No maas!," so I'll stop with the puns.) -Tim -- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay(a)netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^756839 | Public Key: by arrangement Note: I put time and money into writing this posting. I hope you enjoy it.

2 3

Re: cypher breaking and genetic algorithms
by collins＠newton.apple.com 20 Aug '93

20 Aug '93

Hello, -- T. William Wells writes: -- Well, since I'm here, I thought I'd satisfy a curiosity of mine. Has anyone done any research, formal or informal, on the use of genetic algorithms to break cyphers? If not, would anyone care to discuss how it might be done? GA's (which I love, but you won't be able to tell from the following) are a 'robust' search mechanism better at finding _good_ answers than _the_ answer. Because genetic search is driven by partial reward from a partially correct solution, GA's are not adept at searching a space that is very flat except for the single 'spike' of the correct answer. Good encryption systems are like this. You are either right or wrong, no in between. Being one bit off in the key should give a totally fruitless result. GA's don't help much with such ciphers. However, in simple substitution ciphers, frequencies and patterns in partial decryptions can provide the reward GA's need to climb the hills. In fact, Spillman, Janssen, Nelson and Kepner wrote an article in the January 1993 Cryptologia titled "Use of a Genetic Algorithm in the Cryptanalysis of Simple Substitution Ciphers" in which they found that, for the particular class of problems they were solving, within (a short) 100 generations, the GAs could bring the cipher text to the point where a human could 'just read it', whatever that means. Scott Collins | "Few people realize what tremendous power there | is in one of these things." -- Willy Wonka ......................|................................................ BUSINESS. voice:408.862.0540 fax:974.6094 collins(a)newton.apple.com Apple Computer, Inc. 1 Infinite Loop, MS 301-2C Cupertino, CA 95014 ....................................................................... PERSONAL. voice/fax:408.257.1746 1024/669687 catalyst(a)netcom.com

2 1

ADMIN: Blacknet mailings on the cypherpunks list
by Eric Hughes 20 Aug '93

20 Aug '93

There was a recent PGP message encrypted for Blacknet that sailed by on the list. This message did not discuss any topic relevant to cypherpunks from what I could read, since, _a fortiori_ it didn't say anything I could read. Encrypted traffic such as this is inappropriate for this list. Take it elsewhere. Tim and I have already invented the proper forum for this. It's a usenet newgroup called alt.w.a.s.t.e (Read Pynchon to get the joke) The charter for this group is that it takes only encrypted messages. No plaintext allowed. Discussions about alt.w.a.s.t.e must therefore occur in a separate discussion group, named according to Usenet convention alt.w.a.s.t.e.d If someone would kindly create these two groups, the BlackNet folks can revise their announcement appropriately. I was waiting for some reason to create the newsgroup, because I didn't know what traffic would go across it. Now there is some, and it deserves its own home. Eric

3 2

Re: cypher breaking and genetic algorithms
by collins＠newton.apple.com 20 Aug '93

20 Aug '93

Oops, forgot to CC:cypherpunks. Sorry. -- Peter Baumbach writes: -- What if the GA "knew" the plain-text, the cyphertext, and the encryption algorithm, and was searching for a decryption algorithm without the encryption key? Would that be for fruitful? The attack I was describing assumed that the genetic strings _were_ keys and the population was about finding the right key. Peters response suggests that rather than a population comprising keys, a population of 'programs' -- probably built from (constantly reordered) modules that performed the same atomic operations used by the encryption algorithm (and then some). This is a very strong generalization, and one that is getting more attention in the field. 'Genetic Programming'. In practice this can lead to more fluid populations. In this instance, though, you can think of a key as a program to be executed by an encryption or decryption machine and see that a population of programs is similar in expressive power to a population of keys. In the case of cryptanalysis of a _good_ cipher, it is the terrain (of the problem space) itself that gives us the clues about the expected performance of GA's. For a population to improve, it has to be able to measure the performance of an individual (how high has it climbed?) so that it can give increased resources to the more successful (whose children are likely to climb higher on a continuous surface). In cryptanalysis, the goal (the mountain peak) is the correct plaintext. An individual, however it may be constructed, yields a trial decryption. Its performance must be measured against the only standard available in this case, the known plaintext (or the expected statistics of plaintext if known plaintext is not available). If there were an accurate measure of how 'good' a trial decryption was then your GA could climb. However that would imply a continuous 'goodness' function, whose surly bonds strong ciphers surely seek to slip. It is this reliance on continuousness that make GAs great at climbing hills, but rarely better than undirected random search at finding a needle in a haystack. Scott Collins | "Few people realize what tremendous power there | is in one of these things." -- Willy Wonka ......................|................................................ BUSINESS. voice:408.862.0540 fax:974.6094 collins(a)newton.apple.com Apple Computer, Inc. 1 Infinite Loop, MS 301-2C Cupertino, CA 95014 ....................................................................... PERSONAL. voice/fax:408.257.1746 1024/669687 catalyst(a)netcom.com

1 0

No Subject
by Anonymous 20 Aug '93

20 Aug '93

An open message to "lurker(a)cyberspace.nil" As your list administrator, Erik Hughes, has requested, we will no longer accept messages posted on this List. (For bandwidth reasons.) Brief open answer to lurker(a)cyberspace.nil: No, Yes, Thanks, and "unreliable stock tips" probably have no market value. We understand that ventures like ours have a long way to go. But cyberspace is infinitely extensible, and we will eventually colonize it. In the meantime, this initial experiment proves the concept is basically sound. Lots of work needed, though. More places to post, better anonymous remailers, out-of-the-U.S. mail-to-UseNet services, etc. Onward and Inward! BlackNet<nowhere(a)cyberspace.nil> -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.3 mQCPAixusCEAAAEEAJ4/hpAPevOuFDXWJ0joh/y6zAwklEPige7N9WQMYSaWrmbi XJ0/MQXCABNXOj9sR3GOlSF8JLOPInKWbo4iHunNnUczU7pQUKnmuVpkY014M5Cl DPnzkKPk2mlSDOqRanJZCkyBe2jjHXQMhasUngReGxNDMjW1IBzuUFqioZRpABEB AAG0IEJsYWNrTmV0PG5vd2hlcmVAY3liZXJzcGFjZS5uaWw+ =Vmmy -----END PGP PUBLIC KEY BLOCK-----

1 0

(fwd) anonymus@charcoal.com is going away
by tcmay＠netcom.com 20 Aug '93

20 Aug '93

Submitted for your consideration.... Message-ID: <Aug201408031993(a)charcoal.com> Date: 20 Aug 1993 18:08:05 GMT From: Karl_Kleinpaste(a)charcoal.com Organization: Charcoal Communicators, Pittsburgh, PA, USA Newsgroups: alt.privacy.anon-server,alt.personals,alt.sex.movies,alt.sex.fetish.feet,alt.personals.ads,alt.sex.bondage,alt.personals.bondage,soc.bi Followup-To: alt.privacy.anon-server Subject: anonymus(a)charcoal.com is going away Reply-To: anonymus+admin(a)charcoal.com I got off the phone a while ago with someone who is responsible for mail at a large southern university. He called me because he is being pressed for action regarding anonymous mail sent through charcoal.com. It seems that there is a dweeb at this university who is sending anonymous "secret admirer" mail. Two of the five recipients of this sort of mail have raised the issue through university channels as harassment, and at least one of those is in the process of dealing with the police because it correlates uncomfortably closely with harassing phone calls and other incidents going down. This mail admin, having looked through his system's mail logs for sources of the trouble, observed that one individual has repeatedly sent mail to anonymus+clear(a)charcoal.com, and sometime shortly thereafter mail comes back for these recipients, on the same machine. (Yes, really. This person is sending questionable anonymous mail to people on the same system as himself. No joke, though I wish it was. It's a Big Bluish Beastie.) So while I was unwilling to identify the originator of the mail myself, the admin identified him for me by login name, and he was (no surprise) correct. The individual in question is going to get at least a stern talking-to by Those Who Matter. It is hoped that the police can be kept at bay, and that more of that university's channels will not be exercised in this process. This comes on the heels of my having had to chase down incidents in the last week or two... ...someone sending half-Mbyte uuencoded core files via anonymus+clear ...having had to extinguish a couple of individuals due to, e.g., repetitious reposting, and personals posted outside alt.personals* ...another report of anonymous harassment whose details I do not feel I am at liberty to disclose at all. anonymus(a)charcoal.com is going away. My heart is no longer in it, because I am unwilling to ride herd on this ridiculous minority of totally cluefree individuals who seem to believe that they are somehow superior to the rest of the universe and can do things that are clearly against the requirements I stipulate in the info sheet. The potential for repercussions against myself as admin is far too high when I am informed that police are already involved -- I was much too close to such a situation 10 months ago. This server will cease operation on 31 Aug. It is my belief that other anon servers operate in all of the groups currently supported here. Users have 10 days to make other arrangements. More and more, I am convinced that life as a hermit is preferable to life on the network. It is amazing how far one's attitude will fall following one phone call. Please respect Followup-To:. Feel free (feel encouraged) to disseminate this notice wherever appropriate. This note is being posted to alt.privacy.anon-server and those groups which have received 50+ postings in the life of the current news transfer log, less alt.sexual.abuse.recovery (which happens to be far and away in the #1 slot of such a list). --

1 0

Blinded RSA signatures
by nobody＠shell.portal.com 20 Aug '93

20 Aug '93

An excellent description of blinding and digital cash, forwarded from sci.crypt: In article <24924cINNg4c(a)network.ucsd.edu>, loki(a)sdphu3.ucsd.edu (Lance M Cottrell) writes: -----BEGIN PGP SIGNED MESSAGE----- Some time ago I read an article in Scientific American about using RSA and smart cards to achieve untraceable and unforgable electronic cash. The system hinged on being able to "blind" a message which would be signed by the bank, and then the blinding would be removed without disturbing the signature. The signed message would then decrypt to the original message, but the signer would not know what she had signed. The article made no mention of how to do this "blinding". This morning I came up with a method which I would like comments upon. First the notation ^ : exponentiation n : the bank's modulus (p*q in usual notation) e : the exponent used to encrypt the message sent to the bank d : the exponent used to decrypt the bank's encryption. t : the text that you want signed. x : some random number with a multiplicative inverse mod n. y : the inverse of x mod n. c : the cipher text corresponding to t a : the blinded plain text b : the encrypted blinded text. Now the procedure. blind the plain text by a = ((x^d) * t) mod n the bank encrypts a by b = (a^e) mod n = ((((x^d)^e)mod n) * ((t^e)mod n)) mod n the blind is removed by multiplying through by y since ((x^d)^e)mod n = (x^(d*e))mod n = x c = y * b = (y * x * ((t^e) mod n))mod n = (t^e) mod n The question is, can one find x and y such that (x*y) mod n = 1, and can the bank recover t when only given a. Also, please tell me if there is some fundamental error in my handeling of math mod n. Many thanks for any comments. If anyone knows the method the original authors used, please post that as well. Fine description of Chaum's blind signature protocol. Your math looks good. It is easy to find y, given x and n, such that (x*y) mod n = 1, (provided gcd(x,n)=1, as it is for most x ). See Knuth Vol II section 4.5.2, or look up the extended Euclid's algorithm in some good algorithms text. The bank can not tell which t was signed via some a, since for any t and a with t in the multiplicative group mod n, there is some x such that a=x^d * t (mod n). Thus (1)the procedure is tractable, (2)blind forgeries are only possible if RSA is weak, and (3)the "blind" is unconditionally secure. Bryan Olson olson(a)umbc.edu

2 1

building a sound sampler for cryptophone application...
by Graham Toal 20 Aug '93

20 Aug '93

My old uncle - a retired electrical engineer - has gone back to night classes to learn electronics. His class has to do little projects that they pick themselves; nothing too advanced yet - his last one was a musical door-chime... Anyway, he was asking me for ideas for projects to build, and believe me I've got dozens :-) The one that I think is of most value to most people, if he designs a simple circuit for it that I can publish, is a cheap sound sampling interface .... which we can happen to steal for our various cryptophone projects... Here's how I see the design: it feeds data into a (probably IBM PC) parallel port (has to be the bidirectional kind, a plain printer port clearly won't work), and *it* supplies the timing, ie the PC reads from the port when the flags say data is ready, and no more data will be presented to that port until n uSecs later - I foresee it supplying data at either 8000 bytes/sec or 4000 bytes/sec if the former is too fast for a PC to handle. Putting the timing in the sampler frees the PC from a horrendous overhead in sampling at accurate times, and would make it trivial to feed the 4000Hz samples into code like 'shorten' which would then be shoved down a v32bis modem quite comfortably. At a cost *much* less than any commercial sampler: this thing is built from: a battery; a box; a DAC; a 7$ microphone; a parallel port driver; a crystal, and a counter. And that's it. Dead cheap and easy to build, I hope. What I'm writing here to ask is where can I get info on what chip to use to feed data into a PC down the bidirectional parallel port, and how do you drive the chip and what are the pinouts etc. I don't expect anyone to mail me detailed schematics or anything like that, just a pointer to where to look for them. (Though if someone *did* have data sheets, I wouldn't say no to a quick fax :-) ) (fwiw, I used to do electronics as a hobby *years* ago - I once built a dual-processor micro with dynamic ram, so don't be shy of mailing me anything grossly technical; I've forgotten most of what I knew in detail, but I remember enough to steer my uncle in the right direction, though I won't be doing the actual circuit design myself) Thanks for your time. I hope this isn't considered too off-topic... (I mean, I *could* have posted an incredibly interesting piece about the Challenger disater instead, eh Eric? ;-)) G PS Pointers to suitable usenet groups equally appreciated...

2 1