December 2003 - cypherpunks-legacy

CYPHERPUNKS TO THE RESCUE
by jim＠bilbo.suite.com 17 Dec '03

17 Dec '03

You don't even need encryption. 1) Initialize the garage unit and hand unit with a secret initialization vector for a crypto-hash function. 2) Push hand unit button to send "open" signal in clear. 3) Garage unit send a large random number in the clear. While waiting for reply, garage unit calculates hash of the random number it just sent. 4) Hand unit hashes random number and sends result to garage unit. 5) Garage unit opens door if the received hash matches the local hash. 6) And best of all...YOU CAN EXPORT IT! Jim_Miller(a)suite.com

1 0

Re: CYPHERPUNKS TO THE RESCUE
by Pierre Uszynski 17 Dec '03

17 Dec '03

Let's not go overboard!!! I hear things like "public/private key", "battery backup", "the door unit transmits", "a keypad on both sides" Hey! This is a garage door opener! You think you can add $20 of stuff and still have a profit margin? How about no keypad, no battery backup on the remote, just a (random) secret key, no door unit transmitter, normal batteries in the remote and door unit: 1 - Plug the remote into the door unit. The door unit writes a roughly random number (electronic noise), into the remote, and remembers the same. Units synchronize time, while they are at it. 2 - Take the remote for a drive. When you come back press the "open" button. 3 - The remote send the current time (as per its 1 min (im)precise real time clock), encrypted with the secret key. See later real message because of replay attacks. 4 - The door unit decrypts and checks against time, time +1, or time - 1. If valid, it opens the door, and synchronizes its time to the time stamp. POWER LOSS. This is a garage door opener. What do you do when your garage door remote fails, you try again, then you use your key and replace the **** battery (start again at step 1). In my area, power outages are so rare that I wouldn't even need a battery on the door unit (your milage may vary). REPLAY ATTACK. To foil an attacker who would record the time stamp and replay it within a minute: After a time stamp opens the door, a bare time stamp will only work again after something like 2 minutes. Instead, when you push the remote "open" several times within the same protected period, you issue "timestamp, tag1", then "timestamp, tag2", etc... say you are allowed 6 "opens" in the same protection period. The door unit has to check against time - 1, time, time +1, and the corresponding 6 tags. When a tagged stamp worked, all the previous ones are disabled for the protection period, whether the door unit received them or not (to avoid the reuse of messages that failed to open the door.) If you push the remote "open" and it fails to open the door, and you simply give up on the idea of opening the door, you are susceptible to replay attack for something like 2 minutes... that's life. "CLOSE" ACTION. Just close the door, no crypto. Any problem with this SIMPLE solution? Considering there is no point in spending zillions on the garage door opener if your windows do not have alarms. The reason some current units may not be secure is probably the usual: the manufacturers are not interested in what the customers don't want and the customers don't want what the manufacturers have never told them could (or should) be done. And politicians are more interested in legislative action than in suggesting their constituents do not buy junk. Pierre. pierre(a)shell.portal.com ObQuotesFromPreviousMessages: Sandy Sandfort <sandfort(a)crl.com> said something like: > On Tue, 26 Jul 1994, Arsen Ray Arachelian wrote: > > > You'd need a clock on the garage controller....The garage opener > > would receive a signal from the remote, issue a challenge code based on a > > hash of the time/date + some random numbers. The remote would encrypt this > > hash with the owner's IDEA key and send back the response. > > Am I missing something here? Why would you need a clock? What I had in > mind was something like: > > 1--The owner presses the "open" button on the remote. > 2--The remote sends an "ask me" signal to the door unit. > 3--The door unit transmits a random number in the clear. > 4--The remote encrypts and signs the random number using > its unique private key. > 5--The door unit decrypts and compares the numbers, using > the remotes public key. > 6--If the numbers match, the door opens. QED. > > Adjusting my flame retardant underwear, > > > S a n d y > > P.S. For most car and garage doors, relatively short (32 bit?) keys > should be more than sufficient, I would think. > > > > > >

1 0

Re: LITTLE BROTHER INSIDE
by Justin Lister 17 Dec '03

17 Dec '03

> C'punks, > On Tue, 26 Jul 1994, Jim choate wrote: > > . . . > > This would of course assume that the police were silly enough to > > use the disk and such from your machine in your machine. From my > > experience w/ Mentor and Erik Blookaxe during Operation Sun Devil this > > is not very realistic....Also it would only work > > once. Thereafter they would either examine the equipment in a Farady Cage > > or else start doing pager rental scans prior to seizure. Why not just use an encrypted partition. I guess then it is a problem of not being persuaded to reveal the key. What laws/rights does the user have as to revealing the key ? And if the user says "I forget" what would be likely response ? How many users would hold tight, from cases I have heard they usually give in when the stakes are raised. > I'm not so sure. Operation Sun Devil was a more sophisticated operation > than the average cops run. Cops, for the most part, are incredibly lazy > and stupid. I think you could count on lots of them not doing it right. A while back a local BBS system was investigated, it was amazing to find that the police had little knowledge of the software (MSDOS and OS/2 - Remote Acess RA and Front Door) and hardware being used. Apparently the sysop had the system setup so that he could quickly delete the drives FAT and do random zeroing of the drives. Although it wasn't performed as they weren't even familar with hidden (attrib) directories or using non-printable dir names. Essentially they relied on information from the sysop to carry out the investigation. -- +---------------------+--------------------------------------------------+ | ____ ___ | Justin Lister ruf(a)cs.uow.edu.au | | | \\ /\ __\ | Center for Computer Security Research | | | |) / \_/ / |_ | Dept. Computer Science voice: 61-42-835-114 | | | _ \\ /| _/ | University of Wollongong fax: 61-42-214-329 | | |_/ \/ \_/ |_| (tm) | Computer Security a utopian dream... | | | LiNuX - the only justification for using iNTeL | +---------------------+--------------------------------------------------+

5 8

Re: CYPHERPUNKS TO THE RESCUE
by Pierre Uszynski 17 Dec '03

17 Dec '03

Sorry for following up on my own post, but when I said: > The reason some current units may not be secure is probably the > usual: the manufacturers are not interested in what the customers > don't want and the customers don't want what the manufacturers have > never told them could (or should) be done. And politicians are more > interested in legislative action than in suggesting their constituents > do not buy junk. On the other hand, our leaders may be interested in promoting technology and the American Way. To this end, NIST (in close collaboration with NSA and the FBI) could be mandated to assign a committee to prepare a report detailing the need for further study on the Information Highway Garage Door Opener Voluntary Standard (IHGDOVS, sorry). Clearly National Security would mandate the use of an escrow system, and of secret algorithms, but as phone coverage of the country (and soon cellular coverage) if pretty good, key escrow would not impose that much of a burden on the taxpayer. The door unit would be a tamper proof, reverse engineering proof unit back-end programmed in Fort Meade to hold the escrow serial number. Its full alphanumeric keyboard (anything less would be un-american) could not be used to enter a new pass-phrase unless a phone connection exists back to headquarters. Because of the escrow system, there would then be no objection to the use of a really secure system (with full length 500 bit keys). And because "compute cycles are cheap" voice recognition could be added on the remote to foil crude attacks in the line of stealing the silly thing. All this resulting in a definite strategic and economic advantage for the US and US companies. Pierre. pierre(a)shell.portal.com

1 0

Re: CYPHERPUNKS TO THE RESCUE
by Matt Blaze 17 Dec '03

17 Dec '03

norm(a)netcom.com (Norman Hardy) writes: >At 09:51 1994/07/26 -0400, Russell Nelson wrote: >>Why not generate a random number, checksum it, and sign it using a >>public key? Or is that overkill? >... >Seems good. But to thwart replay of the signed message the garage unit must >never accept the same signed number twice. How about the car unit signing >successive numbers. The garage unit would remember the last number that it >accepted and only accept signed numbers larger than that. Garbled >transmissions would then cause no problems. They would be fixed by yet new >transmissions, just as with current units. > As Eric Hughes points out (a couple of messages after these), you don't need public-key signatures for this; any secret key cipher or hash function will do, since the base and remote trust each other unconditionally (at least for garage doors; nuclear weapons may be a different story). Both base and remote need to store a shared key and a counter; the remote needs a transmitter and the base needs a receiver. To authenticate itself, the remote sends {counter, hash(key,counter)} and then increments its counter. The base calculates the hash for the received counter value, verifies that it matches the received hash value, verifies that the counter increases the stored counter value, stores the new value, and opens the door. A practical system system also probably include some mechanism for rekeying and for zeroizing the counters. There is no need for public key cryptography, two way communication (except for key setup), synchronized clocks, or extensive storage at either side. This protocol as described is very simple, almost trivial; given the right constraints it follows almost directly from the problem. I mention it because very small variations and poorly chosen parameters render it vulnerable to several classic protocol failures. First, observe that this system has a work factor to break of no more than the SMALLER of the secret hash key and the size of the hash output. Clearly, a single {counter, hash(key,counter)} message contains enough information to permit an conventional exhaustive search for key. If the hash space is too small (say, 16 bits or so), the adversary can select an unused counter value and probe the receiver with random hash values until the door opens. Worse, if the bad guy selects a counter value that is much larger than the remote's counter value, it has the added bonus of denial-of-service to the real user. Also, note that the order of operation on the receiver's part is critical. If the received counter value is stored BEFORE the hash is received, we are also vulnerable to denial-of-service (but at least not false authentication). Finally, there is the "man in the middle" attack, in which the bad guy intercepts a message intended for but never received by the base, records it, and plays it back later (but before the real owner returns to increment the counter again). A likely scenario involves pushing the button twice on return home, but where only the first message is received by the base. One way to deal with this is to encourage frequent resyncs between the base and remote; for example, the remote, when in the garage, could send periodic "null" commands that increment the counters without actually opening the door. (Of course, you'd need to make sure that these messages themselves cannot be used to construct spoofed open-door messages.) Basing the counter in part on a real-time clock would also help here, but again, this complicates the protocol greatly and increases the opportunities for both denial-of-service (if the clocks get too far out of sync) and false authentication (if the clocks get reset - say at daylight savings time...) My point is not that this is a particularly hard problem, only that even simple cryptographic protocols can have serious bugs. -matt

2 1

New Threat on the Horizon: Software Key Escrow
by tcmay＠netcom.com 17 Dec '03

17 Dec '03

At the June Cypherpunks meeting, Whit Diffie (co-inventor of public-key crypto, as you should all know) filled us in on a workshop on "key escrow" held in Karlsruhe, Germany. All the usual suspects were there, and I gather that part of the purpose was to bring the Europeans "into the tent" on key escrow, to deal with their objections to Clipper, and so on. Diffie described in some detail a software-based scheme developed by NIST (and Dorothy Denning, if I recall correctly) that, as I recall the details, avoids public key methods. Perhaps this was also described here on the list. I know Bill Stewart has recently discussed it in sci.crypt or talk.politics.crypto. What has me worried about it now is evidence from more than one source that this program is actually much further along than being merely a "trial balloon" being floated. In fact, it now looks as though the hardware-based key escrow systems will be deemphasized, as Al Gore's letter seems to say, in favor of software-based schemes. While I've been skeptical that software-based schemes are secure (the bits are hardly secure against tampering), the addition of negotiation with another site (a lot like online clearing of digital cash, it seems) can make it nearly impossible for tampering to occur. That is, I'm now more persuaded that the NIST/NSA(?) proposal would allow software-based key escrow. Here's the rub: * Suppose the various software vendors are "incentivized" to include this in upcoming releases. For example, in 30 million copies of Microsoft's "Chicago" (Windows 4.0) that will hit the streets early in '95 (betas are being used today by many). * This solves the "infrastructure" or "fax effect" problem--key escrow gets widely deployed, in a way that Clipper was apparently never going to be (did any of you know _anybody_ planning to buy a "Surety" phone?). (Granted, this is key escrow for computers, not for voice communication. More on this later.) * Once widely deployed, with not talk of the government holding the keys, then eventual "mandatory key escrow" can be proposed, passed into law by Executive Order (Emergency Order, Presidential Directive, whatever your paranoia supports), an act of Congress, etc. I don't claim this scenario is a sure thing, or that it can't be stopped. But if in fact a "software key escrow" system is in the works, and is more than just a "trial balloon," then we as Cypherpunks should begin to "do our thing," the thing we've actually done pretty well in the past. To wit: examine the implications, talk to the lobbyist groups about what it means, plan sabotage efforts (sabotage of public opinion, not planting bugs in the Chicago code!), and develop ways to make sure that a voluntary key escrow system could never be made mandatory. (Why would _anyone_ ever use a voluntary key escrow system? Lots of reasons, which is why I don't condemn key escrow automatically. Partners in a business may want access under the right circumstances to files. Corporations may want corporate encryption accessible under emergencyy circumstances (e.g., Accounting and Legal are escrow agencies). And individuals who forget their keys--which happens all the time--may want the emergency option of asking their friends who agreed to hold the key escrow stuff to help them. Lots of other reasons. And lots of chances for abuse, independent of mandatory key escrow.) But there are extreme dangers in having the infrastructure of a software key escrow system widely deployed. I can't see how a widely-deployed (e.g., all copies of Chicago, etc.) "voluntary key escrow" system would remain voluntary for long. It looks to me that the strategy is to get the infrastructure widely deployed with no mention of a government role, and then to bring the government in as a key holder. (The shift of focus away from telephone communications to data is an important one. I can see several reasons. First, this allows wide deployment by integration into next-gen operating systems. A few vendors can be "incentivized." Second, voice systems are increasingly turning into data systems, with all the stuff surrounding ISDN, cable/telco alliances, "set-top" boxes, voice encryption on home computers, etc. Third, an infrastructure for software key escrow would make the backward extension to voice key escrow more palatable. And finally, there is a likely awareness that the "terrorist rings" and "pedophile circles" they claim to want to infiltrate are more than likely already using computers and encryption, not simple voice lines. This will be even more so in the future. So, the shift of focus to data is understandable. That it's a much easier system in which to get 40-60 million installed systems _almost overnight_ is also not lost on NIST and NSA, I'm sure.) In other words, a different approach than with Clipper, where essentially nobody was planning to buy the "Surety" phones (except maybe a few thousand) but the government role was very prominent--and attackable, as we all saw. Here, the scenario might be to get 40-60 million units out there (Chicago, next iteration of Macintosh OS, maybe Sun, etc.) and then, after some series of events (bombings, pedophile rings, etc.) roll in the mandatory aspects. Enforcement is always an issue, and I agree that many bypasses exist. But as Diffie notes, the "War on Drugs" enlistment of corporations was done with various threats that corporations would lose assets/contracts unless they cooperated. I could see the same thing for a software-based key escrow. A potentially dangerous situation. I was the one who posted the Dorothy Denning "trial balloon" stuff to sci.crypt, in October of 1992, six months before it all became real with the announcement of Clipper. This generated more than a thousand postings, not all of them useful (:-}), and helped prepare us for the shock of the Clipper proposal the following April. I see this software-based key escrow the same way. Time to start thinking about how to stop it now, before it's gone much further. Putting Microsoft's feet to the fire, getting them to commit to *not* including any form of software-based key escrow in any future releases of Windows (Chicago or Daytona) could be a concrete step in the right direction. Ditto for Apple. I'm sure we can think of other steps to help derail widespread deployment of this infrastructure. --Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay(a)netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway." -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay(a)netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."

5 5

No, each tape position cannot... (was Re: GUT and P=NP)
by collins＠newton.apple.com 17 Dec '03

17 Dec '03

>Could I not let each position on the tape represent a real value in >[0...1]? You could try! But you would always omit values. You can demonstrate this with the `diagonal rule' or similar proofs. Here's a simple one: Take any two adjacent `positions' on the tape; Write out the decimal (or binary) notation for the real values they represent (note, the representations may be infinite). Given two such strings that are not identical, you can always find a string numerically `between' them (even if both are infinite) as long as they are not identical. E.g., "0.12345" --->"0.123455"<---- "0.12346" Such a string is a real value you omitted. Your tape, even if it is infinite, is not the right order of infinity to model the Real numbers. Scott Collins | "Invention, my dear friends, is 93% perspiration, | 6% electricity, 4% evaporation, and 2% butter- collins(a)acm.org | scotch ripple." -- Willy Wonka ..................|.................................................. Apple Computer, Inc. 5 Infinite Loop, MS 305-2D Cupertino, CA 95014 408.862.0540 fax:974.6094 R254(IL5-2N) collins(a)newton.apple.com ..................................................................... 408.257.1746 1024:669687 catalyst(a)netcom.com

1 0

Re: CYPHERPUNKS TO THE RESCUE
by fnerd＠smds.com 17 Dec '03

17 Dec '03

I think Norm gets the prize for the best garage door opener: > ...How about the car unit signing successive numbers.... But this raises an idle question: how much easier is it to break a DES key given a sequence of (n, DES(n)) where the n's are successive numbers, than it is if the n's are random (but still known)? I doubt this is a practical threat for garage doors. - -Steve - - - - - - - - - - - - - - - nutritional information per serving: less than one (1) bit -----BEGIN PGP SIGNATURE----- Version: 2.3a aKxB8nktcBAeQHabQP/d7yhWgpGZBIoIqII8cY9nG55HYHgvt3niQCVAgUBLMs3K ui6XaCZmKH68fOWYYySKAzPkXyfYKnOlzsIjp2tPEot1Q5A3/n54PBKrUDN9tHVz 3Ch466q9EKUuDulTU6OLsilzmRvQJn0EJhzd4pht6hSnC1R3seYNhUYhoJViCcCG sRjLQs4iVVM= =9wqs -----END PGP SIGNATURE-----

2 1

Re: CYPHERPUNKS TO THE RESCUE
by sidney＠taurus.apple.com 17 Dec '03

17 Dec '03

Sandy Sandfort <sandfort(a)crl.com> wrote: >Am I missing something here? Why would you need a clock? I recently used a smart card system for secure remote access to a network. It looked like both the card and the remote system had clocks that were in synch and both ran the same PRNG to produce a new number every minute. Part of the login procedure was to enter the number currently being displayed on the card. A garage door opener built on this principle would not need the ability for the base to transmit any codes, for the remote to receive any, nor to encrypt or decrypt anything. Just a continuously running, clocked PRNG, the ability for the base to receive signals sent by the remote and compare the numbers, and some provision for synching up the clock and state of the PRNG with that of the remote, probably using a physical connection. The remote would transmit a code to the opener. The code would be available to someone listening in, but it would only be valid for the current clock period. The length of the clock period would be a trade off: Too long, and someone could listen in and enter the garage after you have left but before the current code has expired. Too short, and you will have to synch up the remote and the receiver too often to be convenient. (I.e., if the clocks drift by four seconds per year, you can go quite a while with one number per minute, but less than a month at one number per second, before the system becomes unuseable without resynching.) There also has to be some provision for a retry if you happen to signal close to the transition time, within the period where they are out of synch. -- sidney <sidney(a)apple.com>

2 1

Re: New Threat on the Horizon: Software Key Escrow
by Matt Blaze 17 Dec '03

17 Dec '03

Tim May writes: >Diffie described in some detail a software-based scheme developed by >NIST (and Dorothy Denning, if I recall correctly) that, as I recall >the details, avoids public key methods. Perhaps this was also If it's the same scheme that I'm thinking of (that Dorothy Denning presented at the Karlshrue workshop), it was developed by Stephen Walker and David Balenson of Trusted Information Systems, in cooperation with NIST. It's a cute scheme - it doesn't involve secret hardware or algorithms, but does involve public key cryptography, roughly in place of the clipper unit and family keys. You can thwart the system with cooperation at both ends, but you can't interoperate with legal users; in this sense it's more robust against abuse than the Clipper hardware-based system The basic idea is that each user gets a unique public key from the government, which is used to encrypt the session key. You encrypt the session key with this key and send both it and the certified public key to the reciever, who verifies the signature to confirm that it really was issued by the government. Now the receiver also encrypts the session key and compares the result with what you sent, refusing to operate if they don't match. Of course, two parties can cheat by patching their verification routines. But it's very hard to interoperate with non-rogues. -matt

1 0