December 2003 - cypherpunks-legacy

A secure cryptosystem with a 40-bit key?
by Scott Brickner 17 Dec '03

17 Dec '03

I've been reading a bit recently on constructed languages like Esperanto. I came across one that developed out of something called "LOGLAN" that was published in Scientific American in the early sixties. The current active project is called "Lojban". It has one really curious property that gave me an idea for an interesting symmetric-key cryptosystem. All "native" Lojban words are of entirely predictable forms. "Root" words are all five characters containing three consonants and two vowels in one of two patters (CCVCV and CVCCV). "Structure" words have four forms (VV, CV, CVV, and CV'V). "Combining forms" have two forms (CVC and CV'C). All other words are not "native" words (being either proper names or borrowed words). The upshot of this is that there is a fixed limit on the size of the Lojban dictionary of 249500 words (given 17 consonants and five vowels). The grammar of the language is *so* regularized that they are able to give a YACC description for it. A message written entirely using native Lojban words can be encrypted in a codebook fashion where the particular codebook to be used is a permutation of the dictionary represented by an 40-bit number (18 bits to permut the "root word" list, 10 bits for the "structure word" list, and 12 bits for the "combining form" list). This system has the interesting property that *any* plaintext with the same grammatical structure is a potential encryption of a given cyphertext. This is similar to some more usual cryptosystems which operate at the lexical level but which are designed to create this effect, but has the curious side effect that it is *very* easy to determine a false-key which makes the transmitted message say nearly anything you want, thus making mandatory key escrow systems irrelevant. When you want to send the message "attack at dawn", you devise a grammatically identical message, "party 'til you puke" (which is grammatically identical in Lojban), generate a random key, as well as the key representing a similar permutation, but with "attack" and "party" exchanged, "puke" and "morning" exchanged, and so forth. Transmit the message with the false key in the LEAF field (or report it to your government-approved escrow agency) and government eavesdroppers get the wrong message. Other eavesdroppers get a grammatically correct, but apparrently nonsensical message ("drink by brick"). There's still the problem of borrowed words and proper names, which remain problems in any codebook approach, but represents a small portion of the language, and the words which represent individual letters are part of the "structure words" category, and could be sent spelled-out. This works well in Lojban because it never changes word forms based on grammatical usage. Most natural language declensions and conjugations would make the encrypted message ungrammatical, and make it *much* more difficult to determine a false key for the LEAF field. The irregularity of word forms makes the dictionary much more complicated, too. Comments?

3 4

No Subject
by mixmaster＠obscura.com 17 Dec '03

17 Dec '03

To All, A theme I have been thinking about lately is a virtual data haven using a m from n secret splitting scheme via a DC Net for access and hosting the entire process via HTML and W3. The salient feature would be database objects split in such a way that participating sites would possess no more than 1 encrypted slice of any particular encrypted object. Some redundancy of storage is built into the design and participating site give up local storage to store other slices of the datahaven. At no time is the site hosting able to make correlations of slices to plaintext traffic because the split is done on the users workstation and the placement of the slice on the individual slice on the member datahaven site is accomplished with encrypted remailer tech(probably Mixmaster 2) and CGI or java scripts. The idea here is to be able to store ANY information on the net not just what the local bluenoses approve of. anon

1 0

MD5 concerns, was Re: Netscape Logic Bomb detailed by IETF
by patrick＠Verity.COM 17 Dec '03

17 Dec '03

> channel. I think that Netscape uses an MD5 checksum which the members > of this list seem to place unlimited trust in (incorrectly in my view, This is the second time you've implied that an MD5 checksum might not be as secure as we think. Could you share your thinking on this? I had believed from reading the algorithm that it's not possible to predict how a change in the input will affect the checksum. Given a modified version of netscape for example, how would you change some non-critical portion of the code to get the same checksum that the original should have. I suppose that give n bits of non-critical space in the code, (non-critical meaning that changing them will have no effect on the execution of the code, and assuming that you don't want to change the length of the code), that you could try all possible combinations of those bits, or 2^n trials and see if you get the correct MD5 checksum. If you do, then on average you'd actually only have to try 2^(n-1) trials. What if you don't? What would you do then? MD5 produces a 128 bit output, and it would seem likely that this would be hard. As far as I know there are no known attacks for any MDx algorithms in spite of Ron's worries about MD4. It's a subject of on-going research though, and it is only "conjectured that it is computationally infeasible to produce two messages having the same message digest, or to produce any messages having a given prespecified target message digest." (RFC 1321) So, if you have newer information, or pointers to any papers, (other than the ben Boer and Bosselaers papers), could you let me know? Thanks, Patrick _______________________________________________________________________ / These opinions are mine, and not Verity's (except by coincidence;). \ | (\ | | Patrick J. Horgan Verity Inc. \\ Have | | patrick(a)verity.com 1550 Plymouth Street \\ _ Sword | | Phone : (415)960-7600 Mountain View \\/ Will | | FAX : (415)960-7750 California 94303 _/\\ Travel | \___________________________________________________________\)__________/

1 0

USA Today Against ITAR & GAK
by futplex＠pseudonym.com 17 Dec '03

17 Dec '03

I'm pleased to report that USA Today editorializes today (Tuesday, Oct. 24, 1995) against both ITAR and GAK. They get the chronology of the SSL brute-forcing and PRNG seed prediction attacks on Netscape Navigator backwards, but they get many other things right in a fairly short editorial. I am certainly encouraged by this development. Someone at USA Today definitely got the message that the ITAR are a large obstacle to net security in the U.S. Some particularly apropos quotations (from pg. 12A): On ITAR: "[After the Netscape hacks] the perception of the Internet as insecure was indelible. That needn't be. Encryption software available right now is exponentially more powerful and could make code breaking virtually impossible. Its use is blocked by government export regulations that make the programs difficult if not impossible to market, even for domestic purposes." On GAK: "[...] key escrow [...] may sound reasonable, but apply that reasoning to more mundane areas of life. What the government is saying is yes, you can put bars on your windows, locks on your doors and put your jewelry in a safe, but you have to give us the keys and the combination because you might be a crook." That phrasing sounds rather familiar.... "The [GAK] system -- which the FBI and the Commerce Department declined to defend in an opposing view to this editorial [...]" Now I find that surprising. Since when does the FBI not even try to justify Clipper and its descendants in the newspapers ? For foreign readers, I'll note that USA Today has easily the largest national circulation of any daily newspaper in the U.S. [Letters to the editor can be emailed to usatoday(a)clark.net; they want you to give your snail-mail address and home and work phone numbers so they can check your identity.] -Futplex <futplex(a)pseudonym.com>

1 0

Elementrix's so-called "Power One Time Pad"
by Flame Remailer 17 Dec '03

17 Dec '03

Essentially what these guys are selling is a secret key algorithm in which the key for any given message is a function of some initial seed value, and of hashes of all previous messages transmitted between the two parties. So in theory, to break the code, one would need to know not only their initial key, but also all of the messages trasmitted between them so far. A similar result can be achieved by encrypting with PCBC, or other feedback mode involving plaintext, and carrying the IV from the end of one session to the beginning of the next. This is not, of course, a one-time pad, and hardly "groundbreaking" or "revolutionary". While such a system could be designed securely in theory, the folks at Elementrix appear to have little experience at designing secure cryptographic systems. Cryptographic systems designed by such novices frequently have bugs in the implementation which weaken the security offered, or have statistical weaknesses which allow cryptanalytic attack. Elementrix has offered no assurances that they have tested their system for either. Beware of snake oil.

1 0

80 bit security from 40 bit exportable products
by baldwin 17 Dec '03

17 Dec '03

Long ago vendors should have put encryption into network layer products, but for a variety of reasons that effort was delayed or discouraged. One effect of this lack is that almost every layer of the network stack is adding its own encryption. For example, the HTTP session layer added S-HTTP and the TCP transport layer added SSL. Soon we will have network layer encryption with IPsec. The vendors for each layer can export a product that uses ciphers with 40 bit keys. A user can then combine multiple products to get more than 40 bits worth of security. For example, a web client might fetch an S-HTTP page over an SSL protected link via a firewall that supports IPsec tunnels. That's three 40 bit keys protecting the data over the internet link (of course, this may not be equivalent to a 120 bit cipher, that depends on the details of the cipher systems and independence of the key setups). Interesting possibilities. --Bob Baldwin

3 2

CRYPTO '96 CFP
by Matt Blaze 17 Dec '03

17 Dec '03

CRYPTO '96 August 18-22, 1996, Santa Barbara, California, USA CALL FOR PAPERS General Information: Crypto '96, the Sixteenth Annual Crypto Conference, is organized by the International Association for Cryptologic Research (IACR), in cooperation with the IEEE Computer Society Technical Committee on Security and Privacy, and the Computer Science Department of the University of California, Santa Barbara. Original papers are solicited on all technical aspects of cryptology. Instructions for Authors: Please send a cover letter, one title page and 16 copies of an extended abstract. They must be received by the Program Chair at the address given below no later than February 14, 1996 (or postmarked by February 4, 1996 and sent via airmail). The cover letter must state: "This paper does not substantially duplicate work that any of the authors have published elsewhere or have submitted in parallel to any other conference or workshop that has proceedings." The title page should contain the title, the names of the authors, their postal and e-mail addresses and the short abstract; it should be made clear who is the author to whom correspondence should be sent. The first page of the extended abstract should be an informal one-page statement (that will not be published in the Proceedings) describing the content of the oral presentation that will be given at Crypto '96 in the event the paper is accepted (this statement is expected to be different from the short abstract of the paper). This page and the extended abstract must be ANONYMOUS, i.e., they must contain no indication whatsoever of the identity of the author(s). The main body of the extended abstract should start with the title, short abstract, and list of keywords. This should be followed by a succinct statement appropriate for a non-specialist reader specifying the subject addressed, its background, the main achievements, and their significance to cryptology. Technical details directed to the specialist should then follow. Submissions are limited to 10 single-spaced pages of 11pt type, not counting the bibliography and clearly marked appendices. Since referees are not required to read the appendices, the paper should be intelligible without them. The paper including bibliography and appendices must run to no more than 15 pages. These limits will be strictly enforced. Unfortunately, because of the burdens on the Program Committee and the need to keep strictly to the time schedule, we will have to summarily reject any submission not in keeping with the above instructions. Authors are encouraged to make 2-sided copies if possible. Please send submissions by post; unfortunately, we cannot accept submissions by e-mail or fax. Notification of acceptance or rejection will be sent to authors on April 22, 1996. Conference Proceedings: Proceedings will be available at the meeting. They will be published in the Springer-Verlag Lecture Notes in Computer Science. Clear instructions about the final copy will be sent to authors of accepted papers. The final copies of the accepted papers will be due on June 1, 1996. Final papers arriving too late will be removed from the main program. Authors of accepted papers must guarantee that their paper will be presented at the conference. Stipends: A limited number of stipends are available to those unable to obtain funding to attend the conference. Students whose papers are accepted and who will present the paper themselves are encouraged to apply if such assistance is needed. Requests for stipends should be addressed to the general chair. Send submissions to: Neal Koblitz, Program Chair, Crypto '96 Dept. of Mathematics, Box 354350 University of Washington Seattle, WA 98195 U.S.A. Internet: koblitz(a)math.washington.edu Phone: 1-206-543-4386 For other information contact: Richard Graveman, General Chair, Crypto '96 Bellcore 444 Hoes Lane RM 1K-221 Piscataway, NJ 08854 U.S.A. Internet: rfg(a)ctt.bellcore.com Phone: 1-908-699-4611 Program Committee: Neal Koblitz, Chair (Mathematics, University of Washington, USA) Mihir Bellare (Computer Science, University of California at San Diego, USA) Josh Benaloh (Microsoft, USA) Matt Blaze (AT&T Bell Laboratories, USA) Johannes Buchmann (Computer Science, Universitaet des Saarlandes, Germany) Don Coppersmith (IBM Research, USA) Joan Feigenbaum (AT&T Bell Laboratories, USA) Andrew Klapper (Computer Science, University of Kentucky, USA) Lars Knudsen (Computer Science, Ecole Normale Superieure, France) Peter Landrock (Mathematics, Aarhus University, Denmark) Tsutomu Matsumoto (Electrical & Computer Engineering, Yokohama National University, Japan) Chris Mitchell (Computer Science, University of London, UK) Paul Van Oorschot (Bell-Northern Research, Canada) Bart Preneel (Catholic University at Leuven, Belgium) Rainer Rueppel (R3 Security Engineering, Switzerland) Jacques Stern (Computer Science, Ecole Normale Superieure, France)

1 0

Pointer to article on ex parte search & sezure
by Rich Graves 17 Dec '03

17 Dec '03

That's where somebody, e.g. Microsoft or the Church of Scientology, gets US Federal Marshals to seize your computer. Article <46j4t6$6od(a)newsbf02.news.aol.com> in alt.religion.scientology is a good article by Adam S. Bauman of the Los Angeles Times. You might find it interesting, but not quite relevant enough to post the whole thing here. -rich

1 0

80 bits from 40 bits -- NOT
by baldwin 17 Dec '03

17 Dec '03

Well, let me eat my words. Unless all layers turn on encryption at the same time, and there is not predictable text that passes from one layer to the next, adding encryption at each layer cannot substantially improve the size of the key space. Consider two layers each of which has a verifiable header and a body of encrypted text. By "verifyable", I mean that it contains enough redundancy to recognize a correct decryption of the cipher added by the lower layer. For example, a header that included a content type field and a length field could be examined to see if it looked reasonable, and thus confirm a guess at the lower level's cipher. Plaintext-Body-1 | Layer-1-cipher | Header-1, Encrypted-Body-1 | Layer-2-cipher | Header-2, Encrypted-Body-2 To crack this system, an attacker does brute force search of the keyspace for the layer-2-cipher, for each key check the decrypted Header-1 value to see if it looks OK, if not, continue, otherwise start searching the keyspace for the Layer-1-cipher given the candidate for the Encrypted-Body-1 produced by the guess at the Layer-2-cipher key. Clearly, if you have several layer 2 blocks and they all have good looking values for the Header-1, then the Layer-2-cipher key is correct. The summary is that two layers of 40 bit ciphers with the first layer adding some verifiable information, has the effect of adding at most one bit to the effective keysize (doubling the amount of work). It DOES NOT increase the keysize to 80 bits. --Bob Baldwin ______________________________ Reply Separator _________________________________ Subject: 80 bit security from 40 bit exportable products Author: "baldwin" <baldwin(a)RSA.COM (Robert W. Baldwin)> at INTERNET Date: 10/24/95 10:52 AM Long ago vendors should have put encryption into network layer products, but for a variety of reasons that effort was delayed or discouraged. One effect of this lack is that almost every layer of the network stack is adding its own encryption. For example, the HTTP session layer added S-HTTP and the TCP transport layer added SSL. Soon we will have network layer encryption with IPsec. The vendors for each layer can export a product that uses ciphers with 40 bit keys. A user can then combine multiple products to get more than 40 bits worth of security. For example, a web client might fetch an S-HTTP page over an SSL protected link via a firewall that supports IPsec tunnels. That's three 40 bit keys protecting the data over the internet link (of course, this may not be equivalent to a 120 bit cipher, that depends on the details of the cipher systems and independence of the key setups). Interesting possibilities. --Bob Baldwin

1 0

Re: Netscape Logic Bomb detailed by IETF
by anonymous-remailer＠shell.portal.com 17 Dec '03

17 Dec '03

Perry E. Metzger writes: >anonymous-remailer(a)shell.portal.com writes: >> Clearly, someone has a vested interest which they are expending a >> great deal of effort to protect. My email to Netscape detailing their >> logic bomb has gone unanswered, and unacknowledged for ten days now. > >Maybe because you're an idiot and they don't feel that its necessary >to answer. What more need be said? I see that Perry is as charming as ever? Perry, I just don't think that it is wise to stick your head in the sand and ignore a severe flaw in your algorithm, while actively misrepresenting matters to those people who are not intimately familiar with the IETF. >Those of us who care run our postscript interpreters with all the >dangerous commands stripped out, Perry, I'll call you on that one, cause you simply can't do it. Postscript isn't like any other language around. Operator names have no special significance to the interpreter. You can't just "strip out" dangerous commands. They aren't "reserved" in the sense that operator names are in other languages, like COBOL or BASIC. In Postscript, operator names are simply keys into a LIFO dictionary. This makes Postscript different from other languages because you could redefine these names if you wanted to. Stripping something from a dictionary doesn't matter because, the search sequence is top down. If I rewrite an operator name, and put it at the top of the stack, there's not anything you can do. Gee's Perry, even if you haven't stripped something out, I can rewrite it. And the interpreter will find the rewritten version before the version that's in your machine. And before someone attacks me for an inelegant "style" these potentially confusing antics are routinely used under extraordinary circumstances. There's no malice involved at all, simply real-world operation. And this is why the Request-For-Comments from the IETF warns: "Postscript is an extensible language, and many, if not most, implementations of it provide their own extensions. This document does not deal with such extensions explicitly since they constitute an unknown factor ..." Is that clearer?? If you thought that you had "safety" cause you stripped your interpreter, then you're in trouble, cause that doesn't work. > but given that Netscape doesn't supply postscript interpreters, its not > really their fault or problem. Well, that line might work on those who don't know any better, but that's also why the Internet Engineering Task Force (IETF) tries to protect the public by suggesting that implementors like Netscape not pass the ball: "The execution of general-purpose PostScript interpreters entails serious security risks, and implementors are discouraged from simply sending PostScript email bodies to "off-the-shelf" interpreters." Netscape ignores this suggestion. I guess that Netscape simply knows more (or cares less??) than the entire collected wisdom of the International contributors who make up the IETF. Gee, there's lotsa wisdom over there at Netscape. Alice de 'nonymous ... ...just another one of those... P.S. This post is in the public domain. C. S. U. M. O. C. L. U. N. E.

3 2