December 2003 - cypherpunks-legacy

Re: Emergency Broadcast System
by cme＠ellisun.sw.stratus.com 17 Dec '03

17 Dec '03

>Subject: Emergency Broadcast System >Date: Fri, 22 Oct 1993 13:36:33 -0600 (MDT) >From: "Philippe_D_Nave" <pdn(a)dwroll.dw.att.com> > 1) Mailing list data should be distributed to "N" sites where "N" is a > magic number that minimizes the chance of losing all the copies. > (Mathematicians, sharpen your pencils!) I've done the math, if anyone is interested. (part of the job here at a producer of fault tolerant machines.) BTW, we also have solutions for tolerating death of servers which I should write up and post one of these days.... It's such second nature here at Stratus that I don't pay much attention to the fact that not everyone has seen the various solutions. - Carl - <<Disclaimer: All opinions expressed are my own, of course.>> - Carl Ellison cme(a)sw.stratus.com - Stratus Computer Inc. M3-2-BKW TEL: (508)460-2783 - 55 Fairbanks Boulevard ; Marlborough MA 01752-1298 FAX: (508)624-7488

1 0

Warning about exposing anon id
by an41418＠anon.penet.fi 17 Dec '03

17 Dec '03

I am a strong believer in the importance of being able to have an anonymous identity with a reputation. As such, let me post a warning about the most common way people are revealing their identities to me. If you see a post to cypherpunks from an anonymous user of the Finish remailer. That is, an####(a)anon.penet.fi, and you reply to cypherpunks and to that person, then the article that appears on cypherpunks will have your real name and e-mail address, but the message received by the original poster will be from your anonymous id. It's easy to put the two together and establish a list of who is who. Personally, I am ignoring it when this happens, but if I wanted to, I could have a list of about 15 of you by now. It's important to understand how an anonymous service works if you want to rely on it. Also realize, that even if you don't think you are using the service, it is allocating an id for you when you reply to an anonymous poster. You will receive a message about this auomatically from the remailer. Wonderer ------------------------------------------------------------------------- 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

Sharing a secret
by hfinney＠shell.portal.com 17 Dec '03

17 Dec '03

I will give a simple example of Shamir secret sharing. Suppose you have some data D which you want to split up into n pieces such that any 2 of them are sufficient to reconstruct D. Shamir solves the problem for any k of them being sufficient, but the case k=2 is especially simple. Pick a random number m which will be the slope of a line. Take the equation y = mx + D, and substitute x = 1, x = 2, ... x = n. Pass out the y's for each value of x as the secret shares. For example, if D=12, pick random m = 4, and pass out (1,16), (2,20), (3,24), (4,28), and so on. Now, suppose an enemy gets hold of one of these - say (2,20). What does this tell him about the value of D? Nothing! D could be anything, depending on the value of m. But suppose we have two of these values - say (1,16) and (2,20). From these it is easy to calculate m=4, and from that it is easy to see that D=12. Two points determine a line. In the actual Shamir scheme, integers mod a prime p are used, where p>D. The math is basically the same. For k=3, a parabola is used instead of a line, so that 3 points are needed; for k=4, a third-degree polynomial is used, and for general k, a (k-1)-degree polynomial is used. In each case, knowing k-1 points tells you nothing, because there will be a (k-1)-degree polynomial that would pass through any possible value of D. Hal

2 1

Re: Warning about exposing anon id
by freeman＠MasPar.COM 17 Dec '03

17 Dec '03

A very interesting warning, and an interesting conceptual loophole, if I understand it correctly. What I think I understand is, that if I reply to an anonymous message, the remailer will create and maintain an anonymous ID for me, of the form "an12345", which it will use for all subsequent messages that I send through it. If so, then the gotcha is this: Suppose I am not interested in anonymity. I read a message that looks interesting, and reply to it -- both to the originator and to the newsgroup. The remailer gives me an "anonymous" ID which is promptly compromised because the same text went out both with my name on it and with the anonymous ID attached. But who cares -- as I stipulated, at the time I was not interested in anonymity, and may not even have realized that the message I was replying to was posted via an anonymous remailer. BUT suppose that six months from now I suddenly turn paranoid (or realist -- which term you choose depends on your world view), and decide I would like to use the anonymous mailer. Now I send messages to and through it, but the mailer already has an "anonymous" ID for me -- the one long since compromised -- so it keeps using it. Sounds to me like an interesting way for a user to compromise anonymity without it really being anybody's fault. I hope this problem is explained in the remailer documentation (which I haven't sent for -- at the moment I am not interested in anonymity), and that there is an easy way for a user to request a new anonymous ID. A fair fraction of the readers of this list will probably be saying "caveat emptor" or words to that effect, but I suggest that it would be a desirable property of a service offering any kind of anonymity, to lead users -- especially novices -- away from trivial beginner's mistakes. -- Jay Freeman

1 0

Re: Subliminal Channels
by cme＠ellisun.sw.stratus.com 17 Dec '03

17 Dec '03

>Message-Id: <9310222041.AA00922(a)anon.penet.fi> >From: an41418(a)anon.penet.fi (wonderer) >Date: Fri, 22 Oct 1993 20:41:37 UTC >Subject: Re: Subliminal Channels >Big brother comes and tells you that you are not allowed >to encrypt anything, and you say that you used a random >number generator for this new form of art that appears >to be total oblivion, but really represents a new way of >looking at the meaning of life. Have you seen random dot stereo pictures? (cross-eye stereo) There are 5 or 6 repetitions of a seemingly random dot field -- but the first repetition really is random (I believe). A friend of a friend has S/W for generating these. I remember looking at it once and it's not hard at all. However, that was years ago. - Carl

1 0

ANON: revealing penet id
by Karl Lui Barrus 17 Dec '03

17 Dec '03

Hm... this topic seems to come up every few months - just today I was reading the newest Risks digest and an32153 (or something like that) was announcing the "risk" of using penet. I mailed off a submission describing how to avoid this. I think people don't know about this because it isn't published anywhere. Or is it? Maybe somebody could help Julf out and offer to write a new help file that specifically mentions the an/na trick. Last time I looked at the penet help file, this wasn't mentioned. It only takes a bit of work to avoid blowing your id - you just can't hit 'r' and reply to the addressee; instead you must type in the address manually (and be sure to type na#### instead of an####). Last week I responded to some email from a penet user. I was careful to respond to na####, or penet would have allocated me an id for klbarrus(a)owlnet.rice.edu (since I don't have one for this account) and thus someone would have been able to correlate my penet id and this account. As a matter of fact, I think that I revealed the penet id for an old account of mine (elee9sf(a)menudo.uh.edu) this exact way, although this was before the an/na functionality. -- Karl L. Barrus: klbarrus(a)owlnet.rice.edu keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5 3D F3 93 7E 81 B5 CC 32 "One man's mnemonic is another man's cryptography" - my compilers prof discussing file naming in public directories

1 0

Re: Subliminal Channels (jsteg)
by plaz＠netcom.com 17 Dec '03

17 Dec '03

replying to: Karl Lui Barrus <klbarrus(a)owlnet.rice.edu> >Someone did write a program which embeds information in a JPEG, but I >don't have any other info (like where to get it, who wrote it, etc. >:-) I saw jsteg on soda.berkeley.edu from the cypherpunks area (/pub/cypherpunks/applications/jsteg). I haven't actually tried it, mind you, but that's where I saw it. It's actually in the form of jpeg source and a diff file to turn it into jsteg. Forward, upward, outward, onward, and every which way but loose! _______________________________________________________________________ Geoff Dale -- insert standard disclaimers here -- plaz(a)netcom.com "We are the shock troops of reality." - Voice of the Friends (Wild Palms)

1 0

Re: crypto technique
by hughes＠ah.com 17 Dec '03

17 Dec '03

I've looked at Matthew Ghio's encryption technique and have some comments. First let me summarize the system. private key: a sequence of polynomial functions f_1, f_2 ... f_n of the form a_i x (x+1)/2 + b_i, where a_i is odd. public key: the composition of these functions f(x) = f_1 ( f_2 ( ... f_n(x))) and a modulus P = 2^k plaintext: a value 't' ciphertext: the value u = f(t) decryption: finding t such that f(t)=u, by using of the f_i Matthew has repeatedly claimed that it can't be broken. Now one of the first rules of cipher design is don't claim that unless you have some good reason to believe that it can't be broken. Merely saying "I can't figure out how" is NOT sufficient. No flame intended, Matthew, this is probably the single most common failing of people interested in crypto. In particular, Matthew has made the claim that one must find the coefficients of the f_i in order to decrypt and claims that finding such coefficients is difficult. He calls this operation factoring; properly speaking this is a 'decomposition', since the operation used to make f(x) is not multiplication by composition (called iteration when all the functions are the same). As I suspected and Karl has demonstrated, these decompositions are not unique. Since the plaintext, ciphertext pair does not depend on the representation of the function, only upon the coefficients of the polynomial function which is the public key, any such decomposition will suffice for decryption. In other words, you don't have to find how the function was created in order to decode. All you need is some way of inverting the polynomial function f(x). Note that I am using the phrase polynomial function here, and not just the word polynomial. There is a big difference. Polynomial functions are real functions with a domain and range. Polynomials are elements of a ring created by adjoining an indeterminate 'x' to some ring. Polynomials can be 'evaluated' as polynomial functions under some circumstances, but not always. A side note. The function Matthew picks, 1/2 x(x+1) is not, properly speaking, a function with coefficients in Z/2^k (integers mod 2^k). It is, however, a coefficient in Z/2^{k+1} There's one significant difference for the purposes of this proposed cipher: polynomials have arbitrarily large degree, but every polynomial function over a finite ring (such as integers mod N) is equal to some polynomial function of finite degree. One can see this easily be recalling Fermat's little theorem a^N == a (mod N). Thus x^N == x (mod N) for polynomial functions, which limits the degree. Matthew has proposed that arbitrarily many compositions will give a function which can't be inverted. This is certainly not the case if N = 2^k as he proposes. The following relation holds for all integers n > 0 and for all integers t: 2^{2^n - 1} | \Product_{i=0}^{2^n - 1} ( t + i ) What this means is that as the 2^k grows larger, the maximum degree of the polynomial functions grows as 'k', not as 2^k. In other words, the degree grows as the logarithm of the modulus, or linearly in the number of bits in the modulus, if you prefer. This is certainly not a good sign. Recommendation: don't use N=2^k. It's a general rule of cryptosystems that if you use 2^k moduli to speed your encryption, you will also speed the attack, and not just from increased speed, but from algebraic properties of these moduli. There have been some spectacular failures in this regard, notably a chip which was built to do modular exponention for a particular 2^k which was later found to be totally insecure. Another property which decreases the security of the scheme is that polynomials over Z/2^k don't have unique factorization. Therefore the polynomial functions don't have unique representations. For example (x+1)(x+3) = (x+5)(x+7) (mod 8) (x+2)(x+4) = x (x+6) (mod 8) x (x+1)(x+2)(x+3) = 0 (mod 8) (from the expression above) This makes it all the easier to invert the polynomial. The reason that you don't have unique factorization is that Z/2^k has zero divisors: 2 x 4 = 0 (mod 8), so two divides zero. The presence of zero divisors means that you don't get unique factorization. There is, however, a twist. If you don't even see the zero-divisors, you can pretend they aren't there. This is exactly what RSA does, since if you find a multiple of one of the factors of the modulus, you've broken the system. But if you use a modulus of the form pq, you're basically using RSA! RSA picks a particularly easy polynomial function to invert, namely f(x) = x^e. Other polynomials would work as well, and, in fact, appear in the patent application, albeit without examples. Now if you pick a prime modulus, you don't have a public key system anymore. This is the Hellman-Pohlig patent, which uses x^e (mod p) as its encryption. In this scheme 'p' is kept secret, since otherwise the exponentiation could be reversed. In short, I don't think Matthew's scheme can be made to work. There is an open question about how the base field increases with each composition because of the presence of the 1/2, but I don't think currently that this makes it work. For a specific reference, see the collection _Cryptology and Computational Number Theory_ which contains an essay by Kevin McCurley "Odds and Ends from Computational Number Theory." Section 3 of this essay discusses the breaking of some similar schemes by some non-obvious means. I quote: "Moreover, it holds a valuable lesson for those who tend to believe that a computational problem is difficult just because the only apparent solution is difficult." Eric

1 0

random dot stereo
by cme＠ellisun.sw.stratus.com 17 Dec '03

17 Dec '03

My friend's code is still around. I don't have permission to post it but if there's interest I'll ask. Each picture generated requires up to 2^17 random bits to seed the process. - Carl

1 0

Conon redux
by XXCLARK＠indst.indstate.edu 17 Dec '03

17 Dec '03

<trebor(a)fortune.co.jp> wrote: >Most likely by modulating the Least Significant Bit of the color Thank you. Never would have thunk it. Attempted an off-list reply, but can't find the damn gateway. ec

1 0