Re: having source code for your CPU chip -- NOT
At 09:02 23/09/1999 -0400, Steven M. Bellovin wrote: By example, I could verify the machine code for IDEA, but not PGP and certainly not your favorite version of UNIX. Actually, while there are bugs and security holes, it's pretty certain that V6 Unix didn't have any crypto trapdoors ... and you can now own your very own source code license for early Unix including C compiler, complete with source for a PDP-11 emulator to run it on... this might come in handy one day as a stable, recreatable base. See http://minnie.cs.adfa.edu.au/PUPS , the PDP and Unix Preservation Society. [Of course, what guarantees does one have about the provenance of the code? --Perry] regards, Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9181-4851 FAX: +61-2-9181-5470 Suite 410, Birkenhead Point, http://people.qualcomm.com/ggr/ Drummoyne NSW 2047 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Re: snake-oil voting?
Did any of you see this http://www.votehere.net/content/Products.asp#InternetVotingSystems that proposes to authenticate the voter by asking for his/her/its SSN#? It looked like the idea for this part was to prevent double voting, plus make sure that only authorized people could vote. It wasn't necessarily SSN, it could be name/address/date of birth or whatever. Similar to what is done when you go and vote in person. It's not similar at all. Here in New York, for example, where I used to be an election inspector, the voter list includes your signature, age, sex, and usually (if you gave them when you registered) your height and eye and hair color. Each voter has to sign, and if the signature isn't similar enough or the other items looked wrong, we'd ask for better ID. Each polling place has both Democrat and Republican inspectors, the inspectors for one party have an incentive to challenge dubious voters of the other party. This is a reasonable level of validation given that voters have to show up in person, making mass vote fraud a lot of work to organize. (For absentee ballots, your entry in the book is marked as absentee, so if someone got a fake ballot for you, you'd know when you tried to vote.) The combination of biometric info and personal appearance makes it fairly difficult to vote fraudulently. The SSN has become a pseudo-secret identifier. That is, the reality is that your SSN is widely available, but many organizations pretend that it's secret and will believe that anyone who presents your SSN is you. Given that the SSN is not secret, the lack of biometric data, and the reality that it's a whole lot easier to fake network transactions than to fake voting in person, this scheme screams "defraud me". Any security system needs a threat model. I can't figure out what the threat model for this system is other than "whip up something quick and easy". Regards, John Levine, [EMAIL PROTECTED], Primary Perpetrator of "The Internet for Dummies", Information Superhighwayman wanna-be, http://iecc.com/johnl, Sewer Commissioner Finger for PGP key, f'print = 3A 5B D0 3F D9 A0 6A A4 2D AC 1E 9E A6 36 A3 47
Re: having source code for your CPU chip -- NOT
Date: Thu, 23 Sep 1999 18:38:57 -0400 (EDT) From: Eli Brandt [EMAIL PROTECTED] Arnold Reinhold wrote: Perry, if you really believe that the question of whether a given lump of object code contains a Thompson Trap is formally undecidable I'd be interested in seeing a proof. Otherwise Herr Goedel has nothing to do with this. That sure smells undecidable to me. Any non-trivial predicate P on Turing machines (non-trivial meaning that both P and not-P are non-empty) is undecidable by Rice's Theorem. There are technical issues in encoding onto the tape all possible interactions with the world -- the theorem doesn't apply if some inputs are deemed illegal -- but, hey, it's all countably infinite; re-encode with the naturals. I don't think Rice's Theorem applies in this case because it's not a language property. The non-trivial predicate should be on r.e. languages, not on Turing machines. For example, determining whether a Turing machine accepts a string consisting of 3 symbols is undecidable by Rice's Theorem (since some r.e. languages contain strings of 3 symbols and others don't), but determining whether a Turing machine has 3 states is not. That's not to say that it's not undecideable! Just that Rice's Theorem is insufficient to prove it (unless you can somehow reformulate it as a language property). Instead you might try directly reducing some undecideable problem to it. (For those who don't know the terminology, r.e. = recursively enumerable = accepted by a Turing machine.)
Re: snake-oil voting?
Anonymous wrote: Ed Gerck wrote: Did any of you see this http://www.votehere.net/content/Products.asp#InternetVotingSystems that proposes to authenticate the voter by asking for his/her/its SSN#? It looked like the idea for this part was to prevent double voting, plus make sure that only authorized people could vote. It wasn't necessarily SSN, it could be name/address/date of birth or whatever. Similar to what is done when you go and vote in person. The disconnect here is that it does not make sure that only authorized *people* can vote -- but that an authorized he/she/it can vote. Thus, I find that this is not similar to when I go vote in *person*, when election officials will not allow bots or dogs to vote ;-) Here, anything can get an authorization, not just anyone. And, someone could easily have a directory of "voters" (real or made-up) and automatically proceed to obtain authorization and vote with each one of these "voters". There is nothing to prevent bulk voting commanded by one person. There was also this idea of what they earnestly called a VERN, Voter Encrypted Registration Number, which would be distributed in advance to people who were authorized to vote. You'd provide your VERN along with your authenticating info (DOB/SSN/whatever) to prove that you were authorized. Again, one is mislead by the assumption that it would be distributed to people. The VERN voting is similar to what we see in majordomo for example, when a nonce is sent to a *virtual* subscriber and must be mailed back to confirm list subscription, from the same requesting email address -- ie, similar to casting a vote in VoteHere. But, bots can also subscribe using majordomo. So, since the VERN is requested by and provided along with virtual info, there is no verification of the voter's identity even as a person (ie, not a bot) neither when the VERN is sent to the presumed voter nor when the VERN is used. Any voting system ultimately relies on real world proof like this. But, there is no real-world proof here, everything happens entirely in the virtual world. The real point of the protocol is to keep people from finding out HOW each person voted, while assuring that the vote count is correct. There has been a lot of work on crypto protocols for secure voting and this appears to be what they have implemented. I see no protocol, I see a table of names and nonces. Each one can see their name, but no one can verify if two or more names may (wrongly) correspond to one person or, if a nonce listed is the correct one for a name. So, "One Person, One Vote" as declared by VoteHere is more likely "One Name, One Vote". And, what is to prevent populating the table with names/nonces? If absentee ratio is large, there is considerable room to populate the table and still have less than a given number of voters (assuming that the total number of voters is known, which is not true for USENET or in the Internet -- we don't even know how many hosts the Internet has, let alone users, and known host statistics are only relative to in-addr.arpa registration). This looks like a good system although it would be nice to see more details. It certainly sounds better than alternatives. What alternatives do you mean? With current Usenet votes everyone gets to see how you voted. With this VoteHere system you could be assured that your vote was correct (because it would match the encryption you sent in), But, you could not be sure whether any other vote is correct. nobody else could see how you voted, This is not what the site says -- it says: "..decrypted by a simultaneous coordination of election officials and observers, to obtain and/or audit the election results.", which means that such group can decrypt the tally result but does not mean that it cannot decrypt *one* entry from the name/nonce table. Since the table is public, if voting nonces can be decrypted one by one then any vote can be identified. To avoid this, the encryption method used to create the nonces would have to be one-way with trapdoor for the tally but one-way for any nonce. Let us suppose that this is true. But, since a tally is the sum of two or more nonces, if I have *one* known vote (my own) then I can know any other vote in a sum of two nonces. And, knowing two votes I can know the sum of three votes, and so on. I can continue the process and eventually learn how everyone voted, starting only from my own vote -- even under the assumption that the encryption method used to create the nonces is one-way with trapdoor for the tally but one-way for any nonce. and yet you could be sure that the vote total was correct (by running the sum operation on the encrypted data, and verifying that the decryption of this is the claimed sum). Given the information in the site, I cannot see how you deducted this. But, even if what you say is true and I missed it elsewhere, then the argument above shows that knowing only my
Re: having source code for your CPU chip -- NOT
At 6:38 PM -0400 9/23/99, Eli Brandt wrote: Arnold Reinhold wrote: Perry, if you really believe that the question of whether a given lump of object code contains a Thompson Trap is formally undecidable I'd be interested in seeing a proof. Otherwise Herr Goedel has nothing to do with this. That sure smells undecidable to me. Any non-trivial predicate P on Turing machines (non-trivial meaning that both P and not-P are non-empty) is undecidable by Rice's Theorem. There are technical issues in encoding onto the tape all possible interactions with the world -- the theorem doesn't apply if some inputs are deemed illegal -- but, hey, it's all countably infinite; re-encode with the naturals. I am not asking about the class of all Turing machines, just one particular lump of object code OC that happens to be a compiler--say the C++ compiler on the Red Hat 6.0 distribution. And the question is whether OC, which was compiled from a particular source file SF, only contains code attributable to SF or contains some additional self-propagating code inserted by the compiler OCprev that produced OC. SF is trusted by assumption. Only OCprev is suspect. You can even modify SF to some extent, say to turn off optimization or to produce an auxiliary file that matches object code to source statements. If you can answer this question just one time then Thompson's attack can be defeated. This problem is not remotely undecidable. One way to solve it is to write a new compiler from scratch OCalt. Then see if (OCalt(SF))(SF) = OC. As others have pointed out, you can also attempt to ascribe each byte of object code to the source that generated it. The practical impact of this is not immediately apparent. All non-trivial theorem-proving about programs is futile in this same sense, but people do it, or try. They have a lot of difficulties less arcane than running into the pathological cases constructed to prove these undecidability theorems. Your argument reminds me of claims I always hear that nothing can be measured because of the Heisenberg Uncertainty principle. I do feel your pain. More like disgust, actually. Too many computer scientists engage in this sort of name dropping, citing theorems that generally apply only in some infinite limit and specifically do not apply to the case at hand. Most people in the industry, who think an uncountable cardinal has something to do with electing the Pope, take their pronouncements on faith and just give up. The fact is almost nothing in crypto is on a rigorous mathematical foundation. No one has proved that factoring or discrete logs are hard problems (at least not publicly). Yet almost all the difficulties in building trustable systems do not lie in undecidablility results but in human failings. The Open Source model, in my opinion, is the best hope of creating trusted systems we have. Designing a process that can demonstrate that a given system is totally derived from a body of published code is an important goal. The Thompson paper is a often cited as proof that this cannot be done. It deserves to be debunked. Arnold Reinhold
Re: having source code for your CPU chip -- NOT
Perry, if you really believe that the question of whether a given lump of object code contains a Thompson Trap is formally undecidable I'd be interested in seeing a proof. That sure smells undecidable to me. Any non-trivial predicate P on Turing machines (non-trivial meaning that both P and not-P are non-empty) is undecidable by Rice's Theorem. [...] There are no Turing machines. Real computers are finite, and real source codes are finite. I'm sure that if you set a limit on the length of the source code which is recognized by the supposed trap, a sufficiently large FSM can decide in a finite time whether there's a trap. __ Matt Crawford[EMAIL PROTECTED] Fermilab "A5.1.5.2.7.1. Remove all classified and CCI boards from the COMSEC equipment, thoroughly smash them with a hammer or an ax, and scatter the pieces."
Re: having source code for your CPU chip -- NOT
There are no Turing machines. Real computers are finite, and real source codes are finite. I'm sure that if you set a limit on the length of the source code which is recognized by the supposed trap, a sufficiently large FSM can decide in a finite time whether there's a trap. mere finiteness doesn't help much in practice if you're up against algorithms which take time exponential in some parameter (like the size of the 'trap' region) which is likely to get even moderately sized.. - Bill
Re: having source code for your CPU chip -- NOT
Ray Hirschfeld wrote: That sure smells undecidable to me. Any non-trivial predicate P on Turing machines (non-trivial meaning that both P and not-P are non-empty) is undecidable by Rice's Theorem. There are technical issues in encoding onto the tape all possible interactions with the world -- the theorem doesn't apply if some inputs are deemed illegal -- but, hey, it's all countably infinite; re-encode with the naturals. I don't think Rice's Theorem applies in this case because it's not a language property. The non-trivial predicate should be on r.e. languages, not on Turing machines. Yeah, I was trying to avoid bringing in the term "recursively enumerable", and I tripped myself up. The "technical issue" I mumbled about was supposed to address this, but that reduction is in the wrong direction: I need to show that if you can answer Thompson(M) you can answer Thompson'(L), not the other way around. Which, when one stops waving one's hands and thinks about it, is not going to happen, not without drawing on some information about Thompson(). -- Eli Brandt | [EMAIL PROTECTED] | http://www.cs.cmu.edu/~eli/
Re: having source code for your CPU chip -- NOT
Arnold Reinhold wrote: Arnold Reinhold wrote: Perry, if you really believe that the question of whether a given lump of object code contains a Thompson Trap is formally undecidable [...] I am not asking about the class of all Turing machines, just one particular lump of object code OC that happens to be a compiler--say the C++ compiler on the Red Hat 6.0 distribution. I must admit, even though you said "whether a given lump" I assumed the decision procedure was supposed to exist uniformly over lumps. If you swap the quantifiers, sure, for any program there exists a decision procedure -- either the decider that always says "yes" or the one that always says "no". (Okay, I see why you don't find theory relevant.) -- Eli Brandt | [EMAIL PROTECTED] | http://www.cs.cmu.edu/~eli/
Re: having source code for your CPU chip -- NOT
At 06:38 PM 9/23/99 -0400, Eli Brandt wrote: Arnold Reinhold wrote: Perry, if you really believe that the question of whether a given lump of object code contains a Thompson Trap is formally undecidable I'd be interested in seeing a proof. Otherwise Herr Goedel has nothing to do with this. That sure smells undecidable to me. Any non-trivial predicate P on Folks, its not that complex. Thompson suggested that the trojan compiler subvert only login and compiler code. The trojan would not subvert generic code; no funky Godelian self-referential stuff is necessary. Of course, this was before the 90s: the net, downloadable code, chronically lame OSes made other approaches much easier.
Re: snake-oil voting?
John R. Levine writes, quoting others: Did any of you see this http://www.votehere.net/content/Products.asp#InternetVotingSystems that proposes to authenticate the voter by asking for his/her/its SSN#? It looked like the idea for this part was to prevent double voting, plus make sure that only authorized people could vote. It wasn't necessarily SSN, it could be name/address/date of birth or whatever. Similar to what is done when you go and vote in person. It's not similar at all. Here in New York, for example, where I used to be an election inspector, the voter list includes your signature, age, sex, and usually (if you gave them when you registered) your height and eye and hair color. Each voter has to sign, and if the signature isn't similar enough or the other items looked wrong, we'd ask for better ID. Each polling place has both Democrat and Republican inspectors, the inspectors for one party have an incentive to challenge dubious voters of the other party. There is a wide variation in the amount of validation done at polling places. In the local region none of this is done; you are asked to sign, bug your signature is not checked. No ID is required, and observers from political parties are not present. The SSN has become a pseudo-secret identifier. That is, the reality is that your SSN is widely available, but many organizations pretend that it's secret and will believe that anyone who presents your SSN is you. Given that the SSN is not secret, the lack of biometric data, and the reality that it's a whole lot easier to fake network transactions than to fake voting in person, this scheme screams "defraud me". Note that the original scheme did not refer to the SSL as being especially secret. It was used in parallel with date of birth as an example of something which would not be widely known about a person. Obviously date of birth is not particularly secret, but it merely adds an extra amount of security to the protocol. Here is how they describe the authentication process: : Each registered voter is sent a VERN (Voter Encrypted Registration Number) : to serve as something the voter "is given." The VERN can be sent by : email or traditional postal mail. The VERN is often accompanied by a web : site address where the voter can log-on to the Internet to vote. Once at : the voting web site, the voter enters the VERN and additional pieces of : information known only to the voter and election officials (e.g., DOB, : SSN#) to serve as something the voter "knows." The main authentication is this VERN which is sent directly to the registered voters. The additional DOB/SSN adds extra security, it is not the basis for the whole authentication. Any security system needs a threat model. I can't figure out what the threat model for this system is other than "whip up something quick and easy". It seems clear that the system is primarily oriented towards preventing fraud by election officials and those involved in setting up the electronic voting. Historically, this is the greater danger in election fraud. Stuffing the ballot box is much easier if you are the one in charge of delivering the ballots or counting the ballots. If you actually have to get a bunch of people to try to vote under false names it is a huge undertaking and unlikely to be kept secret. Fraud by corrupting officials is much more cost effective and hence more dangerous. In this case, the point of the system is to allow everyone to verify that the counting and recording of the ballots was done honestly. This insures that the officials and operators of the election are doing their jobs correctly. It therefore addresses the primary form of election fraud.
Re: snake-oil voting? voter authentication
At 11:18 PM 9/23/99 -0700, Ed Gerck wrote: that proposes to authenticate the voter by asking for his/her/its SSN#? It looked like the idea for this part was to prevent double voting, plus make sure that only authorized people could vote. It The disconnect here is that it does not make sure that only authorized *people* can vote -- but that an authorized he/she/it can vote. Thus, I find that this is not similar to when I go vote in *person*, when election officials will not allow bots or dogs to vote ;-) Here, anything can get an authorization, not just anyone. NB: In America, *anyone* with an address who can write [1] *can* in practice vote because there is no authentication of citizenship. Note that *everyone* is not legal to vote ---you must be a citizen, for instance, and not a felon--- but there is *no* authentication done on your citizenship when you register to vote. With absentee ballots, dogs and cats can and do vote. (It is of course a crime, as is noncitizen voting...) And dead people are well known to keep voting after internment. This is a regular source of November entertainment in SoCal, where the Republicrats accuse the Demopublicans of encouraging voting by illegal aliens (who tend to vote with them). Some years, the former party posts unofficial guards and "Citizens Only" signs near voting places in the barrios, and gets abuse for it later. Look up the Dornan vs. Sanchez race. NB: There is no requirement in the US to carry identification unless you're driving a car in public. And there are no laws requiring ID to vote. My point being, authentication of voters is a *very* tricky political subject, because it has to do with political power allocation. Much like plans to mess with the US census rose very quickly all the way to the supreme court. The census is how US congresscritters are allocated. (Apologies for civics pedagogy/local anecdotes; I'm assuming there are furriners reading) [1] Probably illiterate citizens can vote too; the law lets a witnessed "X" be a signature, and these days illiterates would claim ADA applied... certainly blind (and braille-illiterate) citizens vote.
Re: having source code for your CPU chip -- NOT
For the truly paranoid: it is perfectly possible to boostrap a working Forth environment *by hand*, whether by hand assembly and flashing the resulting image, or by porting eForth (or any Forths written in C) to an embedded target. You simply can't fit any Trojan in there: a minimal Forth OS can fit into just 2 k, typical environments take 12..16 kBytes. Of course you're abandoning any GNU/Unix compatibility, but the intrinsic rewards of a Forth environment can be considerable -- I don't know of any more productive system. Is there a crypto code library out there? Greg Rose writes: At 09:02 23/09/1999 -0400, Steven M. Bellovin wrote: By example, I could verify the machine code for IDEA, but not PGP and certainly not your favorite version of UNIX. Actually, while there are bugs and security holes, it's pretty certain that V6 Unix didn't have any crypto trapdoors ... and you can now own your very own source code license for early Unix including C compiler, complete with source for a PDP-11 emulator to run it on... this might come in handy one day as a stable, recreatable base. See http://minnie.cs.adfa.edu.au/PUPS , the PDP and Unix Preservation Society. [Of course, what guarantees does one have about the provenance of the code? --Perry]
Re: snake-oil voting?
It seems clear that the system is primarily oriented towards preventing fraud by election officials and those involved in setting up the electronic voting. Historically, this is the greater danger in election fraud. Stuffing the ballot box is much easier if you are the one in charge of delivering the ballots or counting the ballots. If you actually have to get a bunch of people to try to vote under false names it is a huge undertaking and unlikely to be kept secret. Fraud by corrupting officials is much more cost effective and hence more dangerous. Indeed, but I don't see how this scheme offers any defense against ballot box stuffing. The election officials know the VERN and whatever "private" info the voters are supposed to provide for validation purposes, so it seems to me that it'd be no trouble at all to whip up a few thousand forged e-mails with exactly the right voter info, much easier than scribbling fake signatures into a book. To make a system like this forgery resistant, you need to collect some sort of token with each vote that's known to the voter but not known to the officials, so in case of doubt about authenticity you can go back to the voter and validate the token. In a world with widely deployed crypto, that would mean public key signatures, but lacking that, a question like "what color shirt are you wearing today?" might do. Having said all this, I realize that there's a tradeoff between security and usability. Anyone who owns stock in a publicly traded company has probably gotten a proxy form that refers to ADP's proxyvote.com. To vote there, you need only enter a 12 digit number found on the proxy form, or punch it into your phone if voting via their 800 number. That's pretty weak security, but it seems adequate for the purpose, since most corporate elections are uncontested or close to it. I have no idea if they use something more secure when they have an actively contested proxy battle. Regards, John Levine, [EMAIL PROTECTED], Primary Perpetrator of "The Internet for Dummies", Information Superhighwayman wanna-be, http://iecc.com/johnl, Sewer Commissioner Finger for PGP key, f'print = 3A 5B D0 3F D9 A0 6A A4 2D AC 1E 9E A6 36 A3 47
The well-travelled packet
Forwarded with permission (the permission being the short quote below, the message being the long one). I don't have a copy of the traceroute, but it definitely showed packets going from Washington DC to NYC through Paris. Dick St.Peters writes: Well, the questions were really intended to be rhetorical and/or amusing, but sure. The crypto guys will probably be as amused as anyone. Dick St.Peters writes: Remember that traceroute I sent you showing packets from me to a site near here going by way of Europe? I was telling a friend about that this morning, and he asked an interesting question. Suppose someone on my network sent someone at the site a cryptographic program - a US citizen in the US sending it to another US citizen in the US, but the packet route is via Europe. Is that illegal? If so, who is guilty? My user with no knowledge of the route? Sprint, who sent the packets abroad with no knowledge of what they contained? EUNet, who BGP-announced the route to Sprint in Europe? -- Dick St.Peters, [EMAIL PROTECTED] Gatekeeper, NetHeaven, Saratoga Springs, NY Saratoga/Albany/Amsterdam/BoltonLanding/Cobleskill/Greenwich/ GlensFalls/LakePlacid/NorthCreek/Plattsburgh/... Oldest Internet service based in the Adirondack-Albany region
