June 1993 - cypherpunks-legacy

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

Re: PKP
by Doug Porter 14 Jun '93

14 Jun '93

> establishing and securing a monopoly is the whole point of patent law. Sure is; but patents are intended to convey a sharply limited monopoly. I seem to remember Judge Green expressing intense dissatisfaction with interlocking patents used to control an entire industry. We need info from someone who knows. Mike, are you listening, and are you familiar with antitrust law? Doug

2 1

REMAIL/ANON/PGP: System becoming available
by nowhere＠bsu-cs.bsu.edu 14 Jun '93

14 Jun '93

Cypherpunks, I realize that I have been completely quiet on the list for a few months... Sorry about that, but I have been away from the University. Right now I am working in Indianapolis and telnetting from IUPUI up to BSU. Anyway, to the heart of the matter... I have gotten permission from one of the "good guys" at BSU to put my 486dx/33 with 386BSD in his office (secure) and get it on the Ethernet. I will probably run my anonymous remailer on there (the current one will stay in business) where it is safer. In addition, I want to run a pseudonymous service like anon.penet.fi. I have written some software in C that does it, but does not quite support PGP yet (it's not as easy as I would like to have believed before starting the project). It will give you an ID and will restrict mail from and to certain addresses/sites. It also puts a standard header into the message and has features to add header lines and footers to the messages automatically. The system will sit idle (aside from mail) most of the time, so I have no problem using PGP and being an encryption drop-point. I am about to start a rewrite of my remailer pretty soon because it needs some help. Anyway, I will send you all the IP address and host name of my computer when it's online. This could get exciting... I have a guest account on there where you can request an account, but I can't afford to give out too many accounts. Of course, I would much rather cypherpunks have accounts than a bunch of sniveling netbrats. Anyway, gotta run. Incidentally, I have about 3 MB of backed up mail here. It's only since the second week of May! Chael Hall -- Chael Hall nowhere(a)bsu-cs.bsu.edu, 00CCHALL(a)BSUVC.BSU.EDU, chall(a)bsu.edu chall(a)phantom.bsu.edu, nowhere(a)chaos.bsu.edu [not online yet] (317) 776-4000 from 8 am - 5 pm CST

1 0

Rude CryptoStacker Suggestion
by mlshew＠dixie.com 14 Jun '93

14 Jun '93

I have one possible suggestion that might speed up your goals of getting an ecrypting filesystem on PC Clones, although I'm not exactly sure how to put it politely: Seeing as you're looking for encrypting filesystems to work on PC clones, have you made sure such code doesn't exist already? Why not just scrounge through ftp sites (or archie) until you find an already written DOS program that does what you like, and use it instead? With DOS's huge installed user base, I have an extremely difficult time believing that this stuff doesn't already exist for it. Ryan, I don't intend to demean your efforts to bring privacy to the hard drives of the great unwashed masses, (especially if they really are without options at this point)--on the contrary, it's quite a noble goal, and would be a good programming project in its own right even if other solutions do exist, but I'd hate to see you waste your efforts if the same thing really exists elsewhere. -Mark Shewmaker

1 0

Re: Mail logging
by Peter shipley 14 Jun '93

14 Jun '93

-----BEGIN PGP SIGNED MESSAGE----- >>>The single most basic problem with mail development that we have is >>>that we don't have enough mail volume through the remailers we have > >As I said before, any experimentation that people want to do with list >distribution can be done by hacking the current remailer code. You >don't have to have any sysadmin privileges to do this. You don't even >have to have my permission to do this. > My home system has lots of spare CPU then I am willing to setup a cypherpunks crypto remailer. In enough people want to recive cypherpunks in PGP'ed crypt text I will set it up. -----BEGIN PGP SIGNATURE----- Version: 2.2 iQBFAgUBLBwE4Mhmn7GUWLLFAQGjzAF8DwqasQMdJATSkMD2HBEzQdDqVC8nSszn BewSSI0NW8YrrXo0ZWV2g6pos5dJOIN0 =UyFN -----END PGP SIGNATURE-----

1 0