- cypherpunks-legacy@lists.ogf.org

Re: Traveller's Checks...
by hkhenson＠cup.portal.com 20 Aug '93

20 Aug '93

Not that this is really relevant . . . but I remember an article on traveller's checks that a significant percentage of them are *never* cashed. Talk about float! Keith

1 0

Re: genetic algorithms for crypto analysis
by Reply to: hahn＠lds.loral.com 20 Aug '93

20 Aug '93

It has been noted in this thread that a good crypto algorithm would require an attacker to locate a single spike in a problem space, rather than having to climb a hill (which is, of course, much easier). I recall reading (I think in Sci. Am.) that a theory under investigation now as to why nature has sexual reproduction as part of its repertoire is that this gives a solution-seeking population a better opportunity to located spikey solutions. From the point of view of genetic algorithms, sexual reproduction means that each offspring must be generated from two members of the existing population, each of which contributes half the information needed to generate the offspring. In theory, this maintains a population that is spread over a wider terrain, and is thus more likely to find the spike. I don't know if such a strategy would help at all in crypto analysis, or whether any genetic algorithm programs currently in use employ this strategy. __ | (V) | "Tiger gotta hunt. Bird gotta fly. | (^ (`> | Man gotta sit and wonder why, why, why. | ((\\__/ ) | Tiger gotta sleep. Bird gotta land. | (\\< ) der Nethahn | Man gotta tell himself he understand." | \< ) | | ( / | Kurt Vonnegut Jr. | | | | ^ |

2 1

Re: genetic algorithms for crypto analysis
by peb＠PROCASE.COM 20 Aug '93

20 Aug '93

Using a GA to drive a brute force key search would certainly not help: the fitness surface has a needle in a haystack (spike). This kind of problem has been identified as "unlearnable" by theoreticians like Valiant at Harvard. However, using a GA to drive a more intelligent cryptanalysis that has partial results *would* help. It seems that cryptanalysis benefits from human assistance due our excellent abilities at recognition of partial solutions. Because of this, a GA could help automate the cryptanalysis process. (My knowledge of cryptanalysis ends at the Enigma machine breaker cbw (crypt breakers workbench in comp.sources.unix archives) which uses an interative process where partial results are visible and are used to guide new guesses. The Enigma machine does state-machine substitution, but no diffusion/mixing/scrambling; lack of the latter makes visual recognition much simpler. Since DES uses scrambling, I'm not sure whether partial results are possible.) > I recall reading (I think in Sci. Am.) that a theory under investigation > now as to why nature has sexual reproduction as part of its repertoire > is that this gives a solution-seeking population a better opportunity to > located spikey solutions. Crossover of the genome is the key part of "avoiding hill-climbing" and it the key ingredient to Holland's proof of a super-linear speedup (thus "violating" Amdahl's Law of parallelization never attaining a linear speedup) otherwise known as implicit parallelism. Holland's proof of this in the '70s opened up research in GAs because of this attractive feature. [Note that it requires certain assumptions about independence and stasis of the bits in the genome to make the proof tractable, but the hope is that this will still be useful for real problems.] Paul E. Baclace peb(a)procase.com

1 0

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