December 2003 - cypherpunks-legacy

Re: Prime magnitude and keys...a ?
by Jim choate 17 Dec '03

17 Dec '03

> > If you can get the sign of the difference between RSA(your number) and > RSA(unknown key), then you can discover (unknown key) in log n time. > That implies, due to the nature of RSA, that you can factor in log n > time using whatever algorithm it is that makes the determination of > the sign of the difference. No, again it will allow you to find the secret key, it will not provide any information about the factors of that number. It might be used for that but as you have pointed out, it takes a long time. If I can take a cypher-text and look at the periodicity of the mod function when several false keys are provided I can narrow down the guess through a binary search. I am going up, not down (ie finding the factors which must be smaller than n). I am looking for n, not its *@$^%# factors. You are asking the wrong question. I am asking, since I can't factor the keys is there some periodicity in the mod function that I can attack.

2 1

a bit more information on key escrow
by smb＠research.att.com 17 Dec '03

17 Dec '03

I and a few others sent a short list of questions to Dorothy Denning and Steve Kent, with a request that they forward them to the other review panel members. Here are Denning's answers. I do not know if they represent the view of the other committee members, or if more details will be forthcoming. In particular, I do not know if anyone on the committee will ask NSA to declassify any information relative to these questions. I did ask that if the answer to anything was ``it's classified'', that a persuasive rationale for the classification status be given. Reposted with permission.... --Steve Bellovin ------- Forwarded Message Date: Fri, 17 Jun 94 16:01:43 EDT From: denning(a)chair.cosc.georgetown.edu (Dorothy Denning) Steve, Here are answers to the questions you asked. The answers generally apply to the current system. In some cases, I noted changes that will be made in the target system that is under development. Regards, Dorothy Questions on Key Escrow 1. How are the halves of the unit key generated? What is the function? The Device Unique Key (KU) is a function of two Random Seed values that are brought to the chip programming facility by Escrow Officers from each of the Escrow Agents, arbitrary input from the keyboard provided by the Escrow Officers, and the Device Unique Identifier (UID). The exact function is classified in order to avoid revealing cryptographic principles about generating good keys. 2. How are the seeds generated for the unit key generation process? These are extremely sensitive values, since their compromise could give away an entire production run. Each Escrow Agent generates a separate Random Seed using a PC and NIST-developed smart card. The smart card implements a pseudorandom number generator (PRNG) approved for cryptographic key generation in FIPS 171. Input from the keyboard as well as keystroke timing are used as input to the Secure Hash Algorithm. After hashing, the result is fed to the PRNG. Compromise of the Random Seed values could not give away an entire production run since the Unique Keys are also a function of arbitrary input from the keyboard. In addition, the algorithm for generating the KU values, being classified, is not generally available. 3. How is the serial number generated? Randomly? With only 32 bits, the probability of a collision is moderately high. The serial numbers are generated in sequence. 4. How are the seeds destroyed after generation? The Escrow Officers bring the seeds on floppy disks. These disks are to be destroyed or stored in the double-locked safe inside the programming facility (SCIF) until they can be destroyed. The seeds and all other key data is erased from the memory and hard disk of the computer used for key generation at the end of a programming session. The disk is then stored in the safe. 5. How is the session key encrypted within the LEAF? The details of the LEAF creation method, including the exact modes of encryption used, are classified in order to make it more difficult to build an interoperable rogue product that produced fake LEAFs in the event the Family Key should be compromised, and also to avoid revealing cryptographic principles. 6. How is the entire LEAF encrypted? The LEAF/IV package use in Tessera? In particular, is the family key used for session-level cryptographic protection of the IV? The IV is passed in the clear. See 5 about how the LEAF is encrypted. 7. How is the checksum in the LEAF calculated? See 5. 9. What is the nature of the key exchange and key negotiation protocol? The key exchange protocol on the Capstone chip is classified to avoid revealing cryptographic principles of key generation and exchange. However, it is not a requirement to use this algorithm. Other techniques can be used instead. The Escrowed Encryption Standard (EES) does not specify a key exchange method and the Clipper chip does not implement one. 10. How does the Tessera card generate its random keys and IVs? A true random number generator? A pseudo-random number generator? How is it seeded? From a true random source? Why not use that all the time? There is a true random number generator on the Capstone chip. This can be used to generate all random values including the IV. The target programming device may use this random number generator in the generation of Device Unique Keys, but it would not replace the entire algorithm. 11. How are escrowed keys protected during transport and storage? What about backup? Escrowed Key Components are stored in encrypted form on floppy disks inside double locked safes. It takes 2 Escrow Officers at each Escrow Agent site to open a safe, and it takes an Escrow Officer from each Escrow Agent to form the Key Enciphering Key (KCK) needed to decrypt the Encrypted Key Components. KCK is a function of two Key Numbers, KN1 and KN2, each of which is held by one of the Escrow Agents in its safe. For backup, there are two copies of key escrow data in each safe. In addition, each Escrow Agent has a backup safe, which contains an additional two copies. Encrypted Key Components are transported on floppy disks inside tamper-detecting packages. A number is written on each package. Upon arrival, the packages are checked for tampering and the numbers are checked. In the target system, key escrow data will be transmitted electronically using cryptography for protection. 12. What mechanisms will protect the key halves during transmission to authorized wiretap agents? The same methods as for 11. 13. How will an audit trail be maintained of unit key requests and usage? Audit records are written for the following events: generation of keying material, storage of and access to keying material, request for Key Components, confirmation of a key release certification, and notification that a Unique Key was deleted in the Decrypt Processor. These records are kept in the double locked safes under two person control. 14. How will wiretap keys expire? When the Escrow Officers load the Key Components into the Decrypt Processor, they also type in the expiration date. The date is stored with the Unique Key, but the person operating the Decrypt Processor must issue a command to delete the key. When that happens, the Escrow Agents are to be notified of the key deletion. In the target system, the key will be deleted automatically when the court order expires, and the notification will be sent automatically from the Decrypt Processor. ------- End of Forwarded Message

2 1

Cantwell bill outcome
by Dave Otto 17 Dec '03

17 Dec '03

The following post to 'eff.talk presents what, IMO, is one of the most plausible explanations for the ITAR crypto restrictions. I guess I'm not nearly devious enough to work for a TLA. I believe NO request for export of the App. Crypto disk will be approved as long as this type of (semi-hidden) agenda is driving the descisions. However, with the (continuing) spread of PGP, even this argument is bogus:-) ---------- begin forwarded message ----------- Newsgroups: comp.org.eff.talk From: Liudvikas Bukys <bukys(a)cs.rochester.edu> Subject: My conversation with Greg Frasier (House Intelligence Committee) Sender: bukys(a)cs.rochester.edu (Liudvikas Bukys) Organization: University of Rochester Computer Science Dept Date: Fri, 17 Jun 1994 14:53:38 -0400 I decided to call around Washington a bit about the unanimous House Intelligence Committee vote against relaxation of export controls on encryption. I ended up speaking to Greg Frasier, an aide at the House Intelligence Committee. He basically reiterated the case re national security and legitimate needs of law enforcement. FYI, reportedly, the report is due (from the President) 150 days after the enactment of the bill. A couple of interesting statements from Mr. Frasier (paraphrased -- I didn't record the conversation!): That the arguments they are hearing about American companies are unproven, and that no single case of a problem has been documented (in his view). In particular, US companies are allowed some export to the non-US subsidiaries and to financial institutions, so what's the problem? ! While they are aware that software for secure encryption is ! available from non-US, they are making a best effort to prevent ! a standard from emerging, while hoping that some escrowed ! encryption scheme will gain acceptance. I was surprised by the unanimous vote, but he was not. He says that there has been a lot of discussion on this on the committee, but the security/enforce ++ment concerns generally prevail. My impression is that the range of possible outcomes went from outright rejection of export reform (at worst), to a request for a report from the President (at best). I would guess that as long as there is any hope of promulgating government key escrow, they will do their best to discourage the adoption of non-escrowed strong cryptography. Liudvikas Bukys <bukys(a)cs.rochester.edu> Dave Otto -- dave(a)marvin.jta.edd.ca.gov -- daveotto(a)acm.org "Pay no attention to the man behind the curtain!" [the Great Oz] {I *DO* have a life, it's just that my kids are using it right now!}

1 0

Computational Complexity
by mpd＠netcom.com 17 Dec '03

17 Dec '03

Perry E. Metzger writes: > Ahem. He was proposing a mechanism that will work in log(n) > time. All current known methods are subexponential. As you > SHOULD know, a log function will eventually be smaller than > a subexponential one if you only let N grow large enough. > This is baby complexity theory. I find it astonishing that I > should even have to mention it. As I read it, he simply asked (and quite nicely at that) if such a algorithm might exist, and asked if there were any references to it in the literature. Now clearly he was hoping that such a mechanism might offer the opportunity to binary search the key space efficiently and perhaps those hopes were misplaced, but I don't think the idea was so off the wall as to be deserving of the ridicule you heaped upon it. Far weirder things have been proposed on this list. > Thats not what he was proposing. Obviously one can build > such an algorithm given a factoring algorithm, and we know > of exponential factoring algorithms. That wasn't the idea. > His notion was that there might be a CHEAP algorithm to do > this. I think the key word here is "might." Hope springs eternal, even in cryptology. :) -- Mike Duvos $ PGP 2.6 Public Key available $ mpd(a)netcom.com $ via Finger. $

1 0

Some observations on xMODn...
by Jim choate 17 Dec '03

17 Dec '03

I propose to clarify with a little mathematics as best I can what I was, and am, asking... To those this material appears obvious too please feel free to delete. As I understand it MOD is a function which returns the remainder of a number (x) when divided by another number (n). As an example: 5mod3=2 ie 3 will go into 5 a single time and there will be a left over of 2. 11mod3=2 ie 3 will go into 11 a total of 3 times and there will be 2 left over. I propose there is a periodicity in the mod function: n 0 1 2 3 4 5 6 7 8 9 10 11 12 nmod5 0 1 2 3 4 0 1 2 3 4 0 1 2 this can be simplified into a generic formula for a sequence: rem = (kn)+i |big # |big # | | |i=0 |k=0 What this formual does is give you the sequence of any given remainder for xmodn. In a generic algorithm it appears as such: n = some number for k = 0 to "some really big number" for i = 0 to "some really big number" rem=(k*n)+i next i next k >From p.282 on Schneier the RSA encryption algorithm is given as: e c = m (mod n) i i In my notation this reduces to: rem = (kn)+i | | | | | n=0 |i=0 What I am asking is that since the numbers we are looking at are very large there should (to the way I am thinking at the moment) some means of detecting a sequence of patterns of periodicity related to the difference between the actual key and the key we just select randomly. Specificaly what I am asking for is some reference to some work in this area. I don't know what it is called, it doesn't appear in any books that I have looked at. Thanks for any help you may be able to provide...

1 0

Re: Perry vs. the Math Teacher
by Jeff Gostin 17 Dec '03

17 Dec '03

perry(a)imsi.com (Perry E. Metzger) writes: > the result applicable to factoring, I feel rather sad. Its depressing > commentary on what cypherpunks has become. Go figger. It's become a haven of learning, where the more learned teach those willing to learn, instead of the self-congratulatory elitist squad I was told it once was. That's why *I'm* here, to learn from those who know more than I do. I am VERY willing to learn what others have to teach. They know more than I do, and there's some very knowledgeable people here. I've recieved some very nice replies to my earlier question about what O(f(x)) meant, including one from you, Mike McNally, Bill O'Hanlon, and Douglas Sinclair (thanx guys!! If anyone else sent anything, I haven't recieved it yet, but you do have my thanx, in advance!). This only proves that there are people who are only too willing to teach if someone shows they are willing to listen, and learn. The moral of the story is this: Someone had to teach you at one time, didn't they Perry? One is well-advised to remember, and be humbled by, the fact that they weren't born knowing everything. Flames in e-mail, please. Constructive replies always welcome. --Jeff -- +------------------------------------+---------------------------------------+ | Jeff Gostin jgostin(a)eternal.pha.pa.us | +------------------------------------+---------------------------------------+ | "The risk... is that our vision is too small, our dreams not large enough" | | -Jim Seymour | +------------------------------------+---------------------------------------+

5 4

Re: Crypto export legislation defeated in House Intelligence Cmte.
by Bill Frezza 17 Dec '03

17 Dec '03

On 6/17 John said: <If you have any ideas on just how to do this, I'd sure be interested. We've been talking to all the involved people, from NSA "special assistant to the director" to the White House to the Justice Dept to the Intelligence Committee staff to the senators and representatives who are fighting this battle. If they have something that they won't tell us, claiming the info is classified, what do you recommend that we do to change their minds?> I recommend that we give up the battle and go fight the real war. We are totally outgunned if we stick to this approach and are wasting our time. What the entire net community should do is focus it's energies on chopping NSA's budget, period. That's what these guys really care about after all. Let's go on the offense rather than play a losing defense. Make them squirm in appropriation committee hearings, embarrass them for their intelligence failures, and put them on notice that we are going to hit back where it hurts. And don't even bother raising the "freedom of encryption" or free trade issues. Forget it. It's going to happen anyway and they can't stop it. Focus on defecit reduction and downsizing the intelligence community in the wake of the collapse of the Soviet Union. Keep the attack very broad and avoid specific "national security" issues. Get the investigative journalists to write exposes on the huge spending black hole these guys have created. Whine about all the other worthy things taxpayer money can be spent on <gag> if we stop giving it to spooks and weirdos. Of course, this strategy may be tough for the EFF if you are simultaneously urging increased government involvement in the "Information Superhighway". Regards, Bill Frezza DigitaLiberty

1 0

Bumper Sticker
by nobody＠shell.portal.com 17 Dec '03

17 Dec '03

I saw a bumper sticker: I love my country but fear my government. Rat

1 0

Re: Crypto export legislation defeated in House Intelligence Cmte.
by gtoal＠an-teallach.com 17 Dec '03

17 Dec '03

: I recommend that we give up the battle and go fight the real war. We are : totally outgunned if we stick to this approach and are wasting our time. : What the entire net community should do is focus it's energies on chopping : NSA's budget, period. That's what these guys really care about after all. There was quite an interesting quotation in one of the British papers recently from Ames, the CIA spy who was caught - he said that the intelligence infrastructure in the US was a self-serving bureaucracy. I forget the exact wording, but it was the sort of thing you'd imagine the head of any big organisation like that would want to say but was never in a position to be able to - of course, now Ames can say what he likes :-) I wonder if he's available for interviews by the Cypherpunk Press ;-) G

2 1

Notes on xmodn...
by Jim choate 17 Dec '03

17 Dec '03

n 0 1 2 3 4 5 6 7 8 9 10 nmod5 0 1 2 3 4 0 1 2 3 4 0 mult5 0 0 0 0 0 1 1 1 1 1 2 mod3 0 1 2 0 1 2 0 1 2 0 1 mult3 0 0 0 1 1 1 2 2 2 3 3 mod3mod5 0 1 2 0 1 2 0 1 2 0 1 mult 3/5 0 0 0 0 0 0 0 0 0 0 0 mod5mod3 0 1 2 0 1 0 1 2 0 1 0 mult 5/3 0 0 0 1 1 0 0 0 0 1 0 I am interested in the behaviour of the modamodb and mult a/b. I have been unable to find any kind of work along this line...

1 0