- cypherpunks-legacy - lists.cpunks.org

Kahn Sees On-Going Battle On Cryptography 06/14/93
by gnu＠cygnus.com 15 Jun '93

15 Jun '93

From: newsbytes(a)clarinet.com Newsgroups: clari.nb.general Subject: Kahn Sees On-Going Battle On Cryptography 06/14/93 PALO ALTO, CALIFORNIA, U.S.A., 1993 JUN 14 (NB) -- David Kahn, author of "The Codebreakers", speaking at the Third CPSR Cryptography Conference, told those assembled that he sees an on- going battle between government and privacy advocates over personal and business uses of cryptography. Kahn began by saying "My thesis is that the growth of cryptography follows the growth of communication. When there was little literacy, writing itself was a form of cryptography" "A great leap forward came in World War I -- the use of radio brought the need for greater use of codes to insure the privacy of messages. In the fall out after the war, the use of cipher machines was attempted but this approach was not really practical until computers came along," he added. According to Khan, in recent times, interest in cryptography has grown dramatically. "When the RSA algorithm was mentioned in Scientific American, there were 5,000 requests for reprints of the article; the story "Ultra Secret" about the breaking of the Germans' code raised interest and threats such as computer "hackers", viruses and cellular phone fraud raised additional interest in cryptography and the protection of privacy," he said. Kahn then moved to his Antithesis: "(The) Government wants to stop the movement toward privacy. (The) Government wants to know about criminal and terrorists. It tries to accomplish this objective through such things as export controls and the Clipper & Capstone chips," he told the audience. "The Government sees its activity. not as an additional intrusion into individual privacy. but as an attempt to maintain the present state. However, the domain of individual rights has been expanding -- the Miranda warnings, abortion decisions and the more strident avocation of privacy rights are examples of this trend," he said. "The Government moves are trying to block the advance of privacy rather than intrude into present rights. Export limits inhibits business expansion," he added. Kahn concluded: "Now we have to look for the synthesis. It's a matter of "privacy is good" and "business profits are good" versus "security is good." The question that must be answered is how to balance these goods. Do we give up the first for the second?" "The World Trade Center bombing shows that terrorism is here and is a concern. Government wants to hold back technology. This can't be done forever but can be done for a while. Government will argue that the temporary holding back will save some lives and properties," he said. In the question and answer period that followed, Bill Murray, consultant to Deloite and Touche, commented: "When the government wants us to give up the right to private communications, it must show us the danger (that warrants it). If drug dealers and terrorists are the problem, it should be demonstrated that drug dealers and terrorists are abusing private communications." In response to a Newsbytes question as to whether the triumph of the expansion of privacy rights over government concerns was inevitable, Kahn said: "Privacy is to powerful a force to be stopped. It will eventually prevail." Ross Stapleton, a Central Intelligence Agency (CIA) analyst, commented: "These changes in information may cause a rethinking of the concept of national sovereignty. Governments have always have tried to control the flow of information; with the new technology and communications capabilities, they cannot. control it any longer." Murray said: "We cannot control it but we can criminalize it and that would be a mistake. By criminalizing drugs, we have destabilized society. There is so much illegal money from this policy that courts, law enforcement departments and legislatures have been corrupted." Asked by Newsbytes if he saw illegal money growing if the government tries to rein in the growth of cryptography or tries to make wiretapping more pervasive, Murray said: "No, it's not analogous in the money sense. But the criminalizing of anything without real justification causes destabilization." (Barbara E. McMullen & John F. McMullen/19930614/Press Contact: David Banisar, Computer Professionals For Social Responsibility, 202-544-9240 (voice); 202-547-5481 (fax); banisar(a)washofc.cpsr.org on the Internet) "Copyright 1993 by <UPI/Newsbytes/Whoever> (I have no idea who). Reposted with permission from the ClariNet Electronic Newspaper newsgroup clari.nb.general. For more info on ClariNet, write to info(a)clarinet.com or phone 1-800-USE-NETS."

1 0

Re: CERT: the letter from CERT to berkeley.edu admin
by bbyer＠BIX.com 15 Jun '93

15 Jun '93

In-Reply-To: <9306081620.AA07331(a)soda.berkeley.edu> > Here, in its almost full glory, is the letter that CERT sent to the > admin at berkeley. I've removed the addressee, since there's no need > to involve that person. I have not, however, removed the name of the > sender. > ... > > We have been passed information that indicates that the anonymous FTP > archive on the following host(s) may be in use by intruders for ^ > illegal trading of commercial software: > > >>>>>>> soda.berkeley.edu /pub/cypherpunks > > We have not confirmed this information, nor have we identified that > the anonymous FTP configuration on the above-listed host(s) is open > for abuse. ^ > > ... This look suspiciously like a form letter. The possible plurals ("(s)") and the fact that the site name is in a "list type" format indicate this is probably a form letter. This is even more disturbing; do they have a form letter because they use it often or do they have a daemon that searches for highly undesirable things such as ftp sites with lots of encryption related things and automatically fires off this harassing form letter? Ben Byer <bbyer(a)bix.com>

1 0

Re: DH for email (re: email protection and privacy)
by wcs＠anchor.ho.att.com 14 Jun '93

14 Jun '93

peb(a)PROCASE.COM writes: > > >Case 4: "I forgot." > > > > This one seems to work for U.S. presidents. Yes, but in Reagan's case it was quite believable that he had forgotten; you, on the other hand, are presumed to be competent :-) Bill

1 0

funky wierdmail
by Stanton McCandlish 14 Jun '93

14 Jun '93

Anyone got any idea why I keep getting mail like this? It appears to be a bounce of some sort. Dunno which list (if any) it is coming from, but many mailwizzes seem to be reading, so I am hoping no one will mind the bandwidth use... This is the WHOLE message, it's just header and no body. I get several of them per day, starting about 5 days ago. Quoth uucp(a)attmail.com, verily I saith unto thee: > From uucp(a)attmail.com Sun Jun 13 18:38:55 1993 > id <AA02312>; Sun, 13 Jun 1993 18:38:53 -0600 > Message-Id: <9306140038.AA02312(a)hydra.unm.edu> > From: uucp(a)attmail.com > Date: 14 Jun 93 00:30:46 GMT > To: anton(a)hydra.unm.edu > Report-Version: 2 > Confirming-Mts-Message-Id: </C=US/AD=ATTMAIL;internet1650027060> > Confirming-Ua-Content-Id: <ternet1650027060> > Original-Date: Mon Jun 14 00:30:46 GMT 1993 > Not-Delivered-To: mhs!wu/O=duncan_frissell/DD.ELN=62896145 due to 05 Unavailable User Agent > Content-Type: text > > -- When marriage is outlawed only outlaws will be inlaws! Stanton McCandlish, SysOp: Noise in the Void DataCenter Library BBS Internet anton(a)hydra.unm.edu IndraNet: 369:1/1 FidoNet: 1:301/2 Snail: 1811-B Coal Pl. SE, Albuquerque, New Mexico 87108 USA Data phone: +1-505-246-8515 (24hr, 1200-14400 v32bis, N-8-1) Vox phone: +1-505-247-3402 (bps rate varies, depends on if you woke me up...:)

1 0

NitV open again
by Stanton McCandlish 14 Jun '93

14 Jun '93

Your PGP *utilities* source for the BBS side of things in back online again, though there still remain some hardware probs of nasty proportions. I have upped the online time for the ANONYMOUS, password GUEST, account so you can get the larger stuff. See .sig for info. Note that FREQing may not work after the next Fido nodelist comes out, but that will only be temporary. I have the latest PGPShell (2.1), plus some innovative Fido-tech networking crypto goodies. I'd likely UL them to soda, but I was told that if it doesn't come with source code don't bother. Slightly frustrating, but oh well that's not my site. Anyway, got lots of other such goodies too, for Unix, and about 6 other platforms, including various shell and Perl scripts, NeXT diffs, etc. Disclaimer: Due to legal threats from RSADSI/PKP, I am not able to provide PGP itself. Anyone know if it would be legal to provide it in "kit form" (source code)? -- When marriage is outlawed only outlaws will be inlaws! Stanton McCandlish, SysOp: Noise in the Void DataCenter Library BBS Internet anton(a)hydra.unm.edu IndraNet: 369:1/1 FidoNet: 1:301/2 Snail: 1811-B Coal Pl. SE, Albuquerque, New Mexico 87108 USA Data phone: +1-505-246-8515 (24hr, 1200-14400 v32bis, N-8-1) Vox phone: +1-505-247-3402 (bps rate varies, depends on if you woke me up...:)

1 0

FORWARD: Burt Kaliski: Anderson's RSA Trapdoor Can Be Broken
by Henry Strickland 14 Jun '93

14 Jun '93

[nando] ------- Forwarded Message Date: Mon, 14 Jun 93 11:21:38 PDT From: burt(a)RSA.COM (Burt Kaliski) Message-Id: <9306141821.AA06771(a)RSA.COM> To: rsaref-users(a)RSA.COM, pem-dev(a)TIS.COM Subject: Anderson's RSA Trapdoor Can Be Broken Sender: pem-dev-relay(a)TIS.COM In a recent issue of Electronics Letters, Ross Anderson proposes a trapdoor in RSA whereby a hardware device generates special RSA keys that the device's manufacturer can break easily. The following note, just submitted to EL, shows that the special keys can be broken by anyone, not just the manufacturer. The trapdoor is ineffective. - -- Burt Kaliski RSA Laboratories - ---------------------------------------------------------------------- \documentstyle[12pt]{article} \newcommand{\mat}[2] {\left( \begin{array}{#1}#2 \end{array} \right)} \begin{document} \title{Anderson's RSA Trapdoor Can Be Broken} \author{Burton S. Kaliski Jr.\thanks{RSA Laboratories, 100 Marine Parkway, Redwood City, CA 94065. Email address: {\tt burt(a)rsa.com}.}} \date{June 11, 1993} \maketitle \begin{abstract} The RSA trapdoor proposed in Ross Anderson's recent letter can be broken. \end{abstract} \section{Introduction} A recent letter by Ross Anderson \cite{anderson-trapdoor} proposes a ``trapdoor'' in the RSA public-key cryptosystem \cite{rsa} whereby a hardware device generates RSA primes $p$ and $p'$ in such a way that the hardware manufacturer can easily factor the RSA modulus $n = pp'$. Factoring the modulus hopefully remains difficult for all other parties. The proposed trapdoor is based on a secret value $A$ known only to the manufacturer. For 256-bit RSA primes, the secret value $A$ is 200 bits long. The device generates primes $p$ of the form \begin{equation} \label{prime-form} p = rA + q = r(q,A)A + q, \end{equation} where $q$ is at most about 100 bits long, and $r$ is 56 bits long and a function of $A$ and $q$. To factor the RSA modulus $n = pp'$, the manufacturer reduces the modulus modulo $A$ to recover the product $qq'$, following the relationship \begin{equation} \label{modulus-form} n = pp' = rr'A^2 + (rq'+r'q)A + qq'. \end{equation} The 200-bit product $qq'$ is easily factored, and the manufacturer recovers the primes $p$ and $p'$ according to Equation \ref{prime-form}. \section{Breaking the trapdoor} While the trapdoor is indeed practical, it can be broken: Factoring such ``trapped'' moduli is easy. Let $n_0, \ldots, n_k$ be a set of such moduli, and let $r_0,r_0', \ldots, r_k,r_k'$ be the corresponding parameters from Equation \ref{modulus-form}. It is easy to show the following inequalities for the given parameter lengths: \begin{equation} \left\| r_0r_0' \frac{n_i}{n_0} - r_ir_i' \right\| \le 2^{-41}, \quad 1 \le i \le k. \end{equation} Such inequalities are called ``simultaneous Diophantine approximations,'' and they are classified as ``unusually good'' if the error term is less than $n_0^{-1/k}$ \cite{lagarias-approx}. For the given parameter lengths, this is so when $k$ is 13 or more. Given a set of moduli known to have such approximations, finding the approximations is straightforward. Following techniques for breaking knapsack cryptosystems (see \cite{brickell-survey}, \cite{lagarias-approx}, \cite{lll}), one finds a set of short vectors in the lattice generated by the basis \begin{equation} \mat{ccccc} {\lambda n_0 & 0 & 0 & \cdots & 0 \\ 0 & \lambda n_0 & 0 & \cdots & \vdots \\ \vdots & 0 & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & \lambda n_0 & 0 \\ - -\lambda n_1 & -\lambda n_2 & \cdots & -\lambda n_k & 1}, \end{equation} where $\lambda$ is an integer near $n_0^{-1/k}$. In most cases, the short vector \begin{equation} \mat{ccccc}{\lambda(r_1r_1'n_0-r_0r_0'n_1) & \cdots & \lambda(r_kr_k'n_0-r_0r_0'n_k) & r_0r_0'} \end{equation} is a member of the set. The secret value $A$ follows from $r_0r_0'$, since, by Equation \ref{modulus-form}, the integer nearest to $n_0/(r_0r_0')$ is $A^2$. One way to overcome this attack is to assign a different secret value to each device, a precaution Anderson has suggested for another purpose. Then a user can only factor his or her own moduli. The user does not need 14 moduli to find $A$, however. Two prime factors $p$ and $p'$ suffice, since the fraction $r'/r$ is such a good approximation to the fraction $p'/p$ that it is guaranteed to be a convergent in the continued fraction expansion of $p'/p$. The user can therefore detect a trapdoor even if the device generates each modulus with a different secret value. \section{Conclusion} The manufacturer's only recourse, at least as far as the proposed trapdoor is concerned, is for the device to generate each modulus with a different secret value and to keep the prime factors secret. In such a situation, the manufacturer may as well preload the device with the primes and escrow copies---a practical ``trapdoor'' to which all cryptosystems, not just RSA, are vulnerable. \section{Acknowledgements} Matt Robshaw offered helpful comments and suggestions. I also thank God (Col. 3:17). \bibliographystyle{plain} \begin{thebibliography}{1} \bibitem{anderson-trapdoor} Ross Anderson. \newblock A practical {RSA} trapdoor. \newblock {\it Electronics Letters}, 29(11):995, 27 May 1993. \bibitem{brickell-survey} E.F. Brickell and A.M. Odlyzko. \newblock Cryptanalysis: {A} survey of recent results. \newblock {\it Proceedings of the IEEE}, 76:578--593, 1988. \bibitem{lagarias-approx} J.C. Lagarias. \newblock Knapsack public key cryptosystems and diophantine approximation. \newblock In D. Chaum, editor, {\it Advances in Cryptology: Proceedings of CRYPTO '83}, pages~3--23, Plenum Press, New York, 1984. \bibitem{lll} A.K. Lenstra, H.W. {Lenstra Jr.}, and L. Lovasz. \newblock Factoring polynomials with rational coefficients. \newblock {\it Math. Annalen}, 261:513--534, 1982. \bibitem{rsa} R.L. Rivest, A. Shamir, and L. Adleman. \newblock A method for obtaining digital signatures and public-key cryptosystems. \newblock {\it Communications of the ACM}, 21(2):120--126, February 1978. \end{thebibliography} \end{document} ------- End of Forwarded Message

1 0

Re: DH for email (re: email protection and privacy)
by peb＠PROCASE.COM 14 Jun '93

14 Jun '93

>Case 4: "I forgot." This one seems to work for U.S. presidents. Paul E. Baclace peb(a)procase.com

2 1

DH for email (re: email protection and privacy)
by m5＠vail.tivoli.com 14 Jun '93

14 Jun '93

In light of a conversation (not a private conversation; it was at an EFF-Austin gathering) with Mike Godwin in which he stated that the court has ample precedent to cite you for contempt upon refusal to produce encryption keys, I think it's clear that no decypherable encryption scheme is really adequate to protect private materials during a legal investigation. Similarly, I suspect that a scheme to protect information by automatic destruction or obfuscation (as a friend described it, "digital flash paper") would be considered illegal obstruction of justice. Therefore, were I to be in possession of information that for political or business reasons I strongly required absolute privacy, I would resort to physical security as the closest thing to a sure-fire solution. Back things up onto high-density tape, and keep the tapes (*and* the tape drive, lest its presence be taken as prima facie evidence of the existance of off-line "evidence") in some secure place. - -- Mike McNally

4 6

Re: Rude CryptoStacker Suggestion
by peb＠PROCASE.COM 14 Jun '93

14 Jun '93

>have you made sure such code doesn't exist already? In case no one has mentioned this yet: There is a Norton Utility (not free, but fairly priced) that makes a crypto disk. I saw this last summer, but disregarded it since it use the amateur "secrecy through obscurity" method. Thus, the meme is out to some degree, but not strong enough. Paul E. Baclace peb(a)procase.com

1 0

digital cash
by Timothy Newsham 14 Jun '93

14 Jun '93

Several people on this list seem interested in the idea of setting up a digital cash system. A while back someone was dumping legal info on the legitimacy of running your own bank. I have an idea that would allow for "fun" use of digital cash systems while allowing a platform to test out ideas and put the system into a somewhat "real" environment. All that is needed for a digital cash environment is a way to earn money and a way to spend money. The ideas proposed so far seemed to be "send me real money and we'll give you credits." How about putting the digital money in a game/bbs environment? Example: mud's could allow people to transfer their funds between different games, to give away some of their game money electronically to others, etc. BBS's might let you spend your digital cash earned from a MUD for more time or other services. Maybe they'll let you earn money from them in special ways. A bank could be set up, and fixed sized donations could be sent out to each service (BBS, MUD, etc) participating. Each service could then award its participants with earnings as they play. How could something like this actually come about? Banking routines for transfer of funds would have to be written in portable code, with an easy interface for software authors to use in their packages. Most people running BBS's, MUD's and other services on the net have the technical knowledge to patch something this simple into their programs. I am not a big fan of MUD's, and hardly BBS around, but I think this might be a good way to get a system up and running. This will enable flaws in the system to surface, and even under very bad circumstances, no one loses real money. Tim

2 1