December 2003 - cypherpunks-legacy

For Pr0duct Cypher: faster mp_inv
by nobody＠shell.portal.com 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- Pr0duct Cypher wrote: > How big should the blinding factor be? I am not sure. Right now, it is set > to the modulus minus one byte. This is certainly secure, but it takes a > long time to unblind because mp_inv is a slow operation. If you know how > long it needs to be, feel free to change it. PGP's mp_inv is needlessly slow. It works OK for the little numbers they normally use ("e" exponents) but bogs down for big numbers. Fortunately I wrote a fast version of mp_inv some time ago just for this application (blinding). You might say it is "blindingly" fast! Here it is, from my private copy of pgp source. With this you can choose anything for your blinding. You will probably want to change it to use your safemalloc. #ifdef OLD_MPINV /* Replaced by a faster routine, below */ void mp_inv(unitptr x,unitptr a,unitptr n) /* Euclid's algorithm extended to compute multiplicative inverse. Computes x such that a*x mod n = 1, where 0<a<n */ { /* The variable u is unnecessary for the algorithm, but is included in comments for mathematical clarity. */ short i; unit y[MAX_UNIT_PRECISION], temp[MAX_UNIT_PRECISION]; unit gcopies[3][MAX_UNIT_PRECISION], vcopies[3][MAX_UNIT_PRECISION]; #define g(i) ( &(gcopies[i][0]) ) #define v(i) ( &(vcopies[i][0]) ) /* unit ucopies[3][MAX_UNIT_PRECISION]; */ /* #define u(i) ( &(ucopies[i][0]) ) */ mp_move(g(0),n); mp_move(g(1),a); /* mp_init(u(0),1); mp_init(u(1),0); */ mp_init(v(0),0); mp_init(v(1),1); i=1; while (testne(g(i),0)) { /* we know that at this point, g(i) = u(i)*n + v(i)*a */ mp_udiv( g(iplus1), y, g(iminus1), g(i) ); mp_mult(temp,y,v(i)); mp_move(v(iplus1),v(iminus1)); mp_sub(v(iplus1),temp); /* mp_mult(temp,y,u(i)); mp_move(u(iplus1),u(iminus1)); mp_sub(u(iplus1),temp); */ i = iplus1; } mp_move(x,v(iminus1)); if (mp_tstminus(x)) mp_add(x,n); mp_burn(g(iminus1)); /* burn the evidence on the stack...*/ mp_burn(g(iplus1)); mp_burn(v(0)); mp_burn(v(1)); mp_burn(v(2)); mp_burn(y); mp_burn(temp); #undef g #undef v } /* mp_inv */ #else /* OLD_MPINV */ /* Faster mp_inv, based on "Fast Multiplicative Inverse in Modular * Arithmetic", J. Gordon, in Cryptography and Coding, edited by * Henry J. Beker and F.C. Piper, 1989. * The mapping from the variables in that paper to our variables is, * roughly, M->n, X->a, HCF->u(iminus1), U->u(i), temp->u(iplus1), * INV->v(iminus1), V->v(i), temp->v(iplus1). We rotate the assignment to temp * and INV in their 2nd block of code. */ void mp_inv(unitptr x,unitptr a,unitptr n) /* Euclid's algorithm extended to compute multiplicative inverse. Computes x such that a*x mod n = 1, where 0<a<n */ { /* The variable u is unnecessary for the algorithm, but is included in comments for mathematical clarity. */ int shifts; int i = 1; int enterloop; unit vcopies[3][MAX_UNIT_PRECISION], ucopies[3][MAX_UNIT_PRECISION]; #define u(i) ( &(ucopies[i][0]) ) #define v(i) ( &(vcopies[i][0]) ) /* Modify this to do one division at the beginning. That makes it faster. mp_move(u(0),n); mp_move(u(1),a); mp_init(v(0),0); mp_init(v(1),1); mp_init(v(2),1); */ mp_move(u(0),a); mp_init(v(0),1); /* Init U to n%a, V to -n/a. */ mp_udiv(u(1), v(1), n, a); mp_neg(v(1)); mp_move(v(2),v(1)); do { enterloop = 0; shifts = -1; if (mp_compare(u(i),u(iminus1)) > 0) /* if U > HCF then */ mp_init(u(iplus1),0); else { enterloop = 1; mp_move(u(iplus1),u(i)); /* temp := U */ while (mp_compare(u(iplus1),u(iminus1)) <= 0) { /* temp<=HCF */ ++shifts; mp_shift_left(u(iplus1)); /* leftshift(temp,1) */ } mp_shift_right_bits(u(iplus1),1); /* rightshift(temp,1) */ } mp_sub(u(iminus1),u(iplus1)); /* temp := HCF - temp */ mp_move(u(iplus1),u(iminus1)); i = iplus1; /* V := tempV, tempV := INV, INV := V, */ /* U := tempU, tempU := HCF, HCF := U; */ /* (All simultaneous) */ if (enterloop) { while (shifts--) mp_shift_left(v(i)); /* leftshift(V,shifts) */ mp_sub(v(iplus1),v(i)); /* temp = temp - V */ } mp_move(v(i),v(iplus1)); /* V := temp */ } while (testne(u(i),0) && mp_compare(u(i),u(iminus1))!=0); mp_move(x,v(iminus1)); if (mp_tstminus(x)) mp_add(x,n); mp_burn(u(0)); /* burn the evidence on the stack...*/ mp_burn(u(1)); mp_burn(u(2)); mp_burn(v(0)); mp_burn(v(1)); mp_burn(v(2)); #undef u #undef v } /* mp_inv */ #endif /* OLD_MPINV */ -----BEGIN PGP SIGNATURE----- Version: 2.1e iQCVAgUBLVLeoArkCJ6S8691AQH9/QP+LRZ4oXiwNTUkpK7/4uJWhvJCLHPsCNsR YXruZCgY1448DRpbNV4PCtFg/GhDqvJpsWtWOy3lFZIO9zxrDb/tsIfruIJJZr0w lpWhhY+xUJNQYuqgu69EOY2IhJPiyZ+AyMuE4uYscuxEKmAEdLm/BAypX1zNplue NdURpM+pPw4= =f7BH -----END PGP SIGNATURE-----

1 0

UNSUB
by MCALVINK＠ccmail.sunysb.edu 17 Dec '03

17 Dec '03

UNSUBSCRIBE m calvinkoons

2 1

clipper_q-and-a.txt
by nobody＠soda.berkeley.edu 17 Dec '03

17 Dec '03

Q. Who will hold the escrowed keys? A. The government.

1 0

wh_press_secy.statement
by nobody＠shell.portal.com 17 Dec '03

17 Dec '03

The following is a self contradictory statement, if considered to apply for the time period of the next 20 years as the govenment's policy, and it down right PISSES ME OFF. Fuck you, government. >The Administration believes that the steps being announced today >will help provide Americans with the telecommunications security >they need without compromising the capability of law enforcement >agencies and national intelligence agencies. Today, any American can >purchase and use any type of encryption product. The >Administration does not intend to change that policy. Nor do we have >any intention of restrictiog domestic encryption or mandating the use >of a particular technology.

1 0

Food for thought
by Perry E. Metzger 17 Dec '03

17 Dec '03

In conjunction with the latest Big Brother Chip announcements, I've dug up an article I wrote for the net a while back. Some of it seems a bit weak now, but so much of it still feels current that I decided to repost it here. ---------------------------------------------------------------------- Newsgroups: sci.crypt Subject: The Escrow Database. Summary: Expires: References: <1993Apr18.034352.19470(a)news.clarkson.edu> <strnlghtC5puor.704(a)netcom.com> <bontchev.735230663@fbihh> Sender: Followup-To: Distribution: Organization: Partnership for an America Free Drug Keywords: Here is a disturbing thought. Now, we no longer live in the days of big filing cabinets. We live in the electronic age. I asked myself, how big could the escrow database get? How hard might it be to steal the whole thing, particularly were I an NSA official operating with the tacit permission of the escrow houses? (We can pretend that such will not happen, but thats naive.) Well, lets see. Ten bytes of each escrow half. Lets asume ten bytes of serial number -- in fact, I believe the serial number is smaller, but this is an order of magnitude calculation. We assume 250*10^6 as the population, and that each person has a key. I get five gigabytes for each of the two escrow databases. Fits conveniently on a single very valuable Exabyte tape. This can only get easier with time, but who cares -- I can already hold all the clipper keys in the country in my pocket on two 8mm tapes. Admittely, they will think of safeguards. They won't put the whole database on one disk, prehaps. Maybe they will throw stumbling blocks in the way. This changes nothing -- they keys will be needed every day by hundreds if not thousands of law enforcement types, so convenience will dictate that the system permit quick electronic retrieval. At some point, with or without collusion by the agencies, those exabyte tapes are going to get cut. Dorothy Denning and David Sternlight will doubtless claim this can't happen -- but we know that "can't" is a prayer, not a word that in this instance connotes realism. With two exabyte tapes in your pocket, you would hold the keys for every person's conversations in the country in your hands. Yeah, you need the "master key" two -- but thats just ten bytes of information that have to be stored an awful lot of places. Come to think of it, even if the NSA getting a copy of the database isn't a threat to you because unlike me you have no contraversial political views, consider foreign intelligence services. You know, the ones that David Sternlight wants to protect us from because of the evil industrial espionage that they do. The French apparently do have a big spying operation in friendly countries to get industrial secrets, so he isn't being completely irrational here (although why our companies couldn't use cryptosystems without back doors is left unexplained by those that point out this threat.) Presumably, foreign intelligence services can get moles into the NSA and other agencies. We have proof by example of this: its happened many times. Presumably, someday they will get their hands on some fraction of the keys. You can't avoid that sort of thing. Don't pretend that no one unauthorized will ever get their hands on the escrow databases. We crypto types are all taught something very important at the beginning of intro to cryptography -- security must depend on the easily changed key that you pick to run your system, and not on a secret. The escrow databases aren't the sorts of secrets that our teachers told us about, but they are the sort of big secrets they would lump into this category. Imagine trying to replace 100 million Clipper chips. I cannot believe that the NSA or whomever it is thats doing this doesn't realize all this already. They are too smart. There are too many of them who have made their bones in the real world. I suspect that they know precisely what they are doing -- and that what they are doing is giving us the appearance of safety so that they can continue to surveil in spite of the growth of strong cryptography. I suspect that they realize that they can't put things off forever, but they can try to delay things as long as possible. Who knows. Maybe even some of the higher ups, the inevitable bureaucratic types that rise in any organization, really do believe that this scheme might give people some security, even as their subordinates in Fort Meade wring their hands over the foolishness of it all.

1 0

Re: Running regularly
by Matthew Bernardini 17 Dec '03

17 Dec '03

> Matthew Bernardini <matthew(a)gandalf.rutgers.edu> wrote: > > > Why not make two shell scripts, one that sleeps for so long (say 20 minutes) > > using the unix sleep command, and then calls the remailer scripts in an > > infinite while loop. This would work if you set it up as a background > > process,and you don't need to be root for it to work. Only downsides are > > that when the machine crashes you have to log back in and restart script, > > your sleep command will always be in the top window if your sys-admin > > is watching, and you have to be careful not to spawn to many processes and > > bring the system down. > > I tried this on the system here, but it killed off the process when I > logged off. > > As for starting too many processes, just don't start them... leave it > as one single process that just repeats itself indefinently with sleeps > in between. > Did the processes get killed BECAUSE you logged off ? Or did they get killed because you left a single process runnning in the background for an extended period of time and an automated script killed the job. Why not ask the sysadmin how to setup a long computational job for a couple of days ? I don't think any sysadmin would have a problem with that. Then you could find out if the jobs are killed automatically somehow. If it turns out that it was just the process that was automatically killed on a time interval, then you could easily write a script that would spawn a new process and then kill the parent. Matt

2 1

Unsubscribe
by jcook＠pro-storm.metronet.com 17 Dec '03

17 Dec '03

Unsubscribe me please

1 0

Re: CERT advisory
by smb＠research.att.com 17 Dec '03

17 Dec '03

>The big issue, in my mind, is how the ftpd is going to get the key >to unlock the *system's* private key... Do you compile it into the >code? Should ftpd ask for it when it comes up? Since active interception is not nearly so easy as passive listening, it would be appropriate to use a Diffie-Hellman key exchange in this situation. This protocol has no persistent private keys, so the issue of keeping a private key around securely is not an issue. But you still have to type a password to a command that itself could have been compromised. (Not that D-H wouldn't be a tremendous help, of course.) All of the hand-held authenticators I'm familiar with require that the host -- or a dedicated, trusted, security server -- keep a secret key per user. That's not a great idea. Bellcore's S/Key doesn't, but I don't know of any hardware devices that implement it. Another possibility would be hand-held digital signature boxes that could sign a random challenge from the host.

1 0

Re: Magic Money Digicash System
by fb＠cyberg.win.net 17 Dec '03

17 Dec '03

> Magic Money is a digital cash system designed for use over > electronic mail. The system is online and untraceable. Online > means that each transaction involves an exchange with a server, > to prevent double-spending. Untraceable means that it is > impossible for anyone to trace transactions, or to match a > withdrawal with a deposit, or to match two coins in any way. This is the neatest thing I have read in a long time. Where can I get one? > The client module then generates proto-coins, which are > blinded but unsigned. It produces an output file containing > Alice's coins, and the new proto-coins. > Bob mails this to the server. The server counts up Alice's > coins, checks their signatures, and checks for > double-spending. It puts the coins on the cancelled list, > signs the proto-coins, and mails them back to Bob. Bob runs > his client module on the reply message. It unblinds the > signed coins and adds them to his coin file. This completes > the transfer. A few questions. Since the client which generates the proto-coins is under the control of the consumer, the bank has no way of making sure that he is not running his own code, or that the RNG he is using is cryptographically strong, or even that he is not distributing modified client programs to other users. How does the bank deal with collisions in the 16 byte values of coins? What if the user picks the numeric values for the server to sign in a way which leaks information about the banks private key? RSA is much more secure when signing random-esque data, like a message digest, than it is when signing numbers provided to it by some outside party. Similarly, how can the consumer trust the bank's representation that money has already been spent? Surely the bank should be required to publish a list of cancelled coins and timestamps with a running MD5 hash periodically for inspection by the unwashed masses. What do you do about lost messages from the server to the client. Once coins have been recorded as spent, they cannot be redeemed again. Yet the mail message containing the new coins may have been lost in transit. --------------------------------------------------------------- Francis Barrett, F.R.C. | Thou canst not travel on the path | The Cybernetics Guild | before thou hast become the Path | fb(a)cyberg.win.net | itself. | ---------------------------------------------------------------

1 0

No Subject
by smb＠research.att.com 17 Dec '03

17 Dec '03

Subject: clipper_q-and-a.txt >Q. Who will hold the escrowed keys? >. The government. All this bullshit doesnot state that a court order is required, rather 'legal authorization', which means the NSA for foreign intellingence purposes without a court order. Perhaps what is needed is statuatory protection to prevent the NSA from eavesdropping on U.S. Citizens, communicating domestically, without a court order. The law already says that. The government's right to spy on non-Americans is spelled out in the Foreign Intelligence Surveillance Act, 50 USC 1801. Enforcing it is another matter, of course. I saw an AP wire story today that's illuminating. It seems that for years, members of the Tennessee Highway Patrol have been subpoenaing phone company records without proper authority. They've been using a rubber stamp with the commissioner's signature, apparently without his knowledge or consent -- which he probably wouldn't have given, since under Tennessee law the Highway Patrol can deal with crimes committed on a highway, car theft, odometer tampering, or (of course) drug dealing. The only state police agency that has such subpoena authority is the Tennessee Bureau of Investigation -- and even they're limited; the D.A. is supposed to do such things after authorization by the grand jury. And the phone company -- they complied, of course; they had no idea (they said) that the subpoenas were illegal.

1 0