Re: [FoRK] X.509 certificate collision via MD5 collisions (fwd from jeff@k2.com)
Eugen forwards from FoRK: > >Colliding X.509 Certificates version 1.0 > >1st March 2005 > >Arjen Lenstra, Xiaoyun Wang, and Benne de Weger > > > >http://eprint.iacr.org/2005/067 > > > >We announce a method for the construction of pairs of valid X.509 > >certificates in which the ?to be signed? parts form a collision for > >the MD5 hash function. As a result the issuer signatures in the > >certificates will be the same when the issuer uses MD5 as its hash > >function. The real news of the paper was the announcement that Wang's techniques will be revealed this May at Eurocrypt. I'm looking forward to finding out what the secret is! Presumably everyone will receive MD5 collision finding software at around that time. The cert collision is not a surprise, people anticipated this possibility shortly after the MD5 collisions were announced. And notice that Xiaoyun Wang was an author of this paper; she was of course the lead author on the original MD5 collision paper and presumably the originator of the technique for finding MD5 collisions. Using her technology it is straightforward to do this kind of thing. But no one else could have written this paper at this time. The only nontrivial part (given the remarkable ability to generate MD5 collisions) was arranging that both keys were valid RSA moduli with known factors. The did this by generating random bignums and trying to factor them. And keep in mind that her methods find random-ish collisions. They don't find matches to existing hashes, and (as far as we know) they don't find structured collisions as would be necessary to get two certs with different and plausible-sounding names in them. >From what I've read (mostly http://eprint.iacr.org/2004/264), the way these collisions are found is to start with analysis of the structure of the hash, and decide on an XOR difference between the two inputs. This implicitly makes certain assumptions about where and when carries and other nonlinearities will occur in the hash calculation. Then you do a search for inputs which match that pattern of carries and for which the pre-determined XOR difference yields an actual collision. This doesn't give you much ability to control the content of the two inputs that you create. Hal
Re: I'll show you mine if you show me, er, mine
junk) (g^k1, y^k1)(g^k2, y^k2) (F/g^k3, junk) ... When the server did its multiplications as above you'd still get the correct encryptions of c_i, but the other pair would be junk and you wouldn't learn the r_i values: E(c_1) junk junk E(c_4) junk... junk E(c_2) E(c_3) junk E(c_5) ... Now you can still decrypt it and verify your password. But for someone who is impersonating you and doesn't know your password, they're going to get a mix of c_i and r_i values that won't add up to zero, and that won't give them any clue about what the real password is, other than that they guessed wrong. I'm not 100% sure this will work, that the attacker can't create a bogus pair (F/g^k, junk) which will allow him to determine what value the server multiplied by. At a minimum I see that if junk = F/g^k then it will be obvious what the constant was, so the server would have to check for that. This is why it's good to have provable security! This way of doing things would also be quite inefficient; there are two ElGamal encryptions going back and forth (typically 2048 bits each) for every bit of your password. I'll bet the actual paper has a much more clever scheme which improves the efficiency and has a nice proof of security. I'm looking forward to seeing it. Hal Finney
Cypherpunk help with Hal Finney demo
Here's a semi-urgent request. I introduced the RPOW project last year on this list, rpow.net. It provides a sort of play-money form of digital cash, an implementation of Nick Szabo's concept of "bit gold". I am giving a talk at CodeCon, www.codecon.org, on this system, in about an hour(!) and I could use some help from you. One of the things I have done to demo a possible use is to make a patched version of BitTorrent, the widely used file sharing program, that exchanges RPOW data objects in order to reward people for uploading and seeding files. In exchange, people with RPOWs can get priority on future downloads, so by seeding today you can get a better download tomorrow. That's the concept, although at this point it is just an experiment. What I need is to have a dozen or so people doing regular BitTorrent downloads of a file I will offer during the demo, which will be at about 5:15 PM Pacific Standard Time, 8:15 PM EST, 1:15 AM GMT. That's 1 hour from now. You don't need to use any special RPOW software, just the regular BitTorrent client. If you have a BitTorrent client and know how to use it, could you start up and leave running a download of the following .torrent file: http://www.finney.org/~hal/ArkyMovie.mpg.torrent This is fully legal, it's just a home movie of my dog Arky playing on the beach with his brother. Nothing will happen with the download until I start the demo after 5. But if you could start up your BitTorrent client before then and just leave it running, it would be a big help for me. If you are able to do this, please send me an email when you start up your BT client, at [EMAIL PROTECTED] If you've never used BT, don't bother to try downloading and figuring it out. I only really need a minimum of 4 or 5 people doing it, but as I said a dozen or more would be great. Sorry about the last minute notice; I know that most people won't see this until too late, but if anyone sees it now and you know how to use BT I'd appreciate your help. Thanks! Hal Finney
Re: Off-the-Record Messaging (IM plugin)
> Nikita Borisov and Ian Goldberg have released > Off-the-Record Messaging (http://www.xelerance.com/mirror/otr/), It looks like Ian Goldberg's site might be a more authoritative source, http://www.cypherpunks.ca/otr/ . One interesting feature is authentication + deniability. You know who you are talking to, but afterwards anyone who captured a transcript can't prove who said it. Usually we do authentication with digital signatures, but the problem is that binds you to what you say and it can be used against you afterwards. OTR does it by signing the key exchange which creates a MAC key for each direction. (A MAC is a keyed hash which is then applied to each message.) Each message gets MAC'd and this way you know that the messages are authentic and untampered. This already protects you against your conversant; both of you know the MAC keys in each direction (one knows them in order to MAC new messages; the other knows them in order to verify the MAC), so each guy can forge messages created by the other guy and create a bogus transcript. That means that neither person can publish a transcript and credibly claim that it authentically represents what was said. Then, there's another trick: when you are through with them you publish your MAC keys, in the clear. This does not compromise secrecy; all of the data is encrypted with a different key. But it means that now, anyone could in retrospect forge a transcript showing you saying anything at all. And that of course means that no such transcript has any credibility in terms of providing cryptographic evidence of what you said. Hal
Re: Your source code, for sale
Ben Laurie writes: > How do you make the payment already "gone" without using a third party? Of course there has to be a third party in the form of the currency issuer. If it is someone like e-gold, they could do as I suggested and add a feature where the buyer could transfer funds irrevocably into an escrow account which would be jointly controlled by the buyer and the seller. This way the payment is already "gone" from the POV of the buyer and if the seller completes the transaction, the buyer has less incentive to cheat him. In the case of an ecash mint, a simple method would be for the seller to give the buyer a proto-coin, that is, the value to be signed at the mint, but in blinded form. The buyer could take this to the mint and pay to get it signed. The resulting value is no good to the buyer because he doesn't know the blinding factors, so from his POV the money (he paid to get it signed) is already "gone". He can prove to the seller that he did it by using the Guillou-Quisquater protocol to prove in ZK that he knows the mint's signature on the value the seller gave him. The seller thereby knows that the buyer's costs are sunk, and so the seller is motivated to complete the transaction. The buyer has nothing to lose and might as well pay the seller by giving him the signed value from the mint, which the seller can unblind and (provably, verifiably) be able to deposit. Hal
RE: Your source code, for sale
Michael_Heyman writes: > Finney, Hal (CR): > > The problem is that if the source code you are purchasing is > > bogus, or if the other side doesn't come through, you're > > screwed because you've lost the value of the torn cash. The > > other side doesn't gain anything by this fraud, but they harm > > you, and if they are malicious that might be enough. > > > Quick fix for seller incentive: the seller rips some amount of their own > cash in such a way that they cannot recover it unless the buyer provides > the remainder of the buyer's ripped cash. Yes, I'm looking at ideas like this for ecash gambling, but you have a who-goes-first problem. One side or the other has to "rip" their own cash first, and then the other side can just go away and leave the first side screwed. The act of ripping cash is relatively atomic and involves a transaction with the ecash mint, so they can't both do it at the same time. I guess the best fix is for each side to rip a little bit of cash at a time, so that the guy who goes first only loses a trivial amount if the other side aborts. Then after a few rounds both sides are sunk pretty deep and both have a strong incentive to complete the transaction. Hal
Re: Your source code, for sale
Enzo Michelangeli writes: > In the world of international trade, where mutual distrust between buyer > and seller is often the rule and there is no central authority to enforce > the law, this is traditionally achieved by interposing not less than three > trusted third parties: the shipping line, the opening bank and the > negotiating bank. Interesting. In the e-gold case, both parties have the same bank, e-gold ltd. The corresponding protocol would be for the buyer to instruct e-gold to set aside some money which would go to the seller once the seller supplied a certain receipt. That receipt would be an email return receipt showing that the seller had sent the buyer the content with hash so-and-so, using a cryptographic email return-receipt protocol. > > You could imagine a trusted third party who would inspect the code and > > certify it, saying "the source code with hash XXX appears to be > > legitimate Cisco source code". Then they could send you the code bit > > by bit and incrementally show that it matches the specified hash, > > using a crypto protocol for gradual release of secrets. You could > > simultaneously do a gradual release of some payment information in the > > other direction. > > But it's hard to assess the value of partially-released code. If the > gradual transfer bits-against-cents is aborted, what is left to the buyer > is likely to be unusable, whereas the partial payment still represents > good value. Actually you can arrange it so that neither the partially-released code nor the partially-transferred ecash is of any value until the whole transfer finishes. For example, send the whole thing first in encrypted form, then release the encryption keys bit-by-bit. If someone aborts the protocol early, the best each side can do is a brute force search over the untransferred bits to try to find the key to unlock the data they received. > A more general issue is that source code is not a commodity, and > intellectual property is not "real" property: so the traditional "cash on > delivery" paradigm just doesn't work, and looking for protocols > implementing it kind of moot. If the code is treated as trade secret, > rather than licensed, an anonymous buyer may make copies and resell them > on the black market more than recovering his initial cost, at the same > time undercutting your legitimate sales (see e.g. the cases of RC4 and > RC2). This can cause losses order of magnitude larger than refusing to pay > for his copy. That's a good point. Maybe you could use some kind of DRM or trusted computing concept to try to force the buyer to lock up his received data. For source code that would be pretty difficult though, it needs to be handled in flexible ways. Hal
RE: Your source code, for sale
"Tyler Durden" writes:
> So my newbie-style question is, is there an eGold that can be verified, but
> not accessed, until a 'release' code is sent?
>
> In other words, say I'm buying some hacker-ed code and pay in egold. I don't
> want them to be able to 'cash' the gold until I have the code. Meanwhile,
> they will want to see that the gold is at least "there", even if they can't
> cash it yet.
>
> Is there a way to send a 'release' to an eGold (or other) payment? Better
> yet, a double simultaneous release feature makes thing even more
> interesting.
I've been thinking about how to do this kind of thing with ecash.
One project I'm hoping to work on next year is a P2P gambling game (like
poker or something) using my rpow.net which is a sort of play-money ecash.
You'd like to be able to do bets and have some kind of reasonable
assurance that the other guy would pay up if he loses.
In the case of your problem there is the issue of whether the source
code you are buying is legitimate. Only once you have inspected it and
satisfied yourself that it will suit your needs would you be willing
to pay. But attaining that assurance will require examing the code in
such detail that maybe you will decide that you don't need to pay.
You could imagine a trusted third party who would inspect the code and
certify it, saying "the source code with hash XXX appears to be legitimate
Cisco source code". Then they could send you the code bit by bit and
incrementally show that it matches the specified hash, using a crypto
protocol for gradual release of secrets. You could simultaneously do
a gradual release of some payment information in the other direction.
If you don't have a TTP, one idea for using ecash is Markus Jakobsson's
"Ripping Coins for a Fair Exchange". Basically you withdraw ecash from
your account and in effect "rip it in half" and give half to the seller.
Now he gives you the product and you give him the other half of the coin.
The idea is that once you have given him the "ripped" ecash ("torn"
would be a better word because ripping means something else today),
you are out the value of the cash. You have no more incentive to cheat,
as giving him the other half won't cost you anything additional.
(Even without ecash, a service like egold could mimic this functionality.
You'd create an escrow account with two passwords, one known to each
party. Only with both passwords could data be withdrawn from the account.
Then the buyer would transfer funds into this account. After receiving
the goods, the buyer would send his password to the seller.)
The problem is that if the source code you are purchasing is bogus,
or if the other side doesn't come through, you're screwed because you've
lost the value of the torn cash. The other side doesn't gain anything
by this fraud, but they harm you, and if they are malicious that might
be enough. And likewise you might be malicious and harm them by refusing
to give them your half of the coin even after you have received the goods.
Again, this doesn't benefit you, you're still out the money, but maybe
you like causing trouble.
Another idea along these lines is gradual payment for gradual release
of the goods. You pay 10% of the amount and they give you 10% of the
source code. You pay another 10% and you get the next 10% of the source,
and so on. (Or it could be nonlinear; maybe they give out half the code
for free, but the final 10% requires a large payment.) The idea is that
you can sample and make sure they do appear to have the real thing with
a fairly small investment.
If there is some mechanism for the seller to have a reputation (like
Advogato's perhaps, with some spoofing immunity) then the problem is
easier; the seller won't want to screw buyers because it hurts his rep.
In that case it may be reasonable to ask the buyer to pay in advance,
perhaps using the partial payment system just discussed.
These various ideas all have tradeoffs, and in general this kind of
problem is hard to solve because of the complexity of what constitutes a
successful transaction. A reputation system helps a great deal to resolve
the issues, but opens up problems of its own. The betting problem I
want to work on is relatively easy because there is no ambiguity about
who wins, but even then it is hard to make sure that neither party can
maliciously harm the other.
Hal F.
Re: Federal program to monitor everyone on the road
There was a brief mention of this technology at the Crypto conference. I provided some pointers in a comment to an Ed Felten blog entry at http://www.freedom-to-tinker.com/archives/000677.html#comments (scroll down to the 3rd comment). Dan Boneh et al presented a proposal for a group signature scheme so that the data collected would not be personally identifiable. The problem is that the data needs to be authenticated, otherwise rogue transmitters could send false data and perhaps cause traffic flow problems or even serious accidents. So they want to use some cryptographic method. Putting a common key in the whole system would make it too easy for rogues to get access to, would be unrevocable, and we are back to the rogue transmitter problem. Using individual certified keys is the default solution but has privacy problems: everyone would be constantly transmitting a cryptographically verifiable record of their driving patterns, speed, lane changing and who knows what else. With the group signature, everybody has a unique key but their transmissions are not bound to that key. And if a key gets scraped out and goes rogue, it can be revoked. This is supposed to provide flexibility, authentication, and privacy. In practice I am skeptical that society will choose to protect privacy at the expense of security. One optional feature of group signatures is a trusted party who can penetrate the anonymity and learn the identity of the author of a particular message. I suspect that any vehicle based embedded communications system will retain that capability, a sort of "license plate" in the virtual realm. The ability to track the paths of bank robbers and terrorists would be too inviting for society to give up, especially if the data is only available to government agents. Hal
Seth Schoen's Hard to Verify Signatures
Seth Schoen of the EFF proposed an interesting cryptographic primitive called a "hard to verify signature" in his blog at http://vitanuova.loyalty.org/weblog/nb.cgi/view/vitanuova/2004/09/02 . The idea is to have a signature which is fast to make but slow to verify, with the verification speed under the signer's control. He proposes that this could be useful with trusted computing to discourage certain objectionable applications. The method Seth describes is to include a random value in the signature but not to include it in the message. He shows a sample signature with 3 decimal digits hidden. The only way to verify it is to try all possibilities for the random values. By controlling how much data is hidden in this way, the signer can control how long it will take to verify the signature. This idea is nice and simple, but one disadvantage is that it is probabilistic. It works on average, but occasionally someone might choose an n digit value which happens to be low (assuming the values are chosen at random). Then they don't get as much protection. They could fix this by eliminating too-low values, but then verifiers might exploit that by doing low values last in their testing. Another problem is that this method is inherently parallelizable, so that someone with N computers could solve it N times faster, by having each computer test a subset of the values. An alternative is based on the paper, "Time-lock puzzles and timed release Crypto", by Rivest, Shamir and Wagner, from 1996, http://theory.lcs.mit.edu/~rivest/RivestShamirWagner-timelock.pdf or .ps. They are looking more at the problem of encrypting data such that it can be decrypted only after a chosen amount of computing time, but many of their techniques are applicable to signatures. The first solution they consider is essentially the same as Seth's, doing an encryption where n bits of the encryption key are unknown, and letting people search for the decryption key. They identify the problems I noted above (which I stole from their paper). They also point out BTW that this concept was used by Ralph Merkle in his paper which basically foreshadowed the invention of public key cryptography. Merkle had to fight for years to get his paper published, otherwise he would be known as the father of the field rather than just a pioneer or co-inventor. The next method they describe can be put into signature terms as follows. Choose the number of modular squarings, t, that you want the verifier to have to perform. Suppose you choose t = 1 billion. Now you will sign your value using an RSA key whose exponent e = 2^t + 1. (You also need to make sure that this value is relatively prime to p-1 and q-1, but that is easily arranged, for example by letting p and q be strong primes.) The way you sign, even using such a large e, is to compute phi = (p-1)*(q-1) and to compute e' = e mod phi, which can be done using about 30 squarings of 2 mod phi. You then compute the secret exponent d as the multiplicative inverse mod phi of e', in the standard way that is done for RSA keys. Using this method you can sign about as quickly as for regular RSA keys. However, the verifier has a much harder problem. He does not know phi, hence cannot reduce e. To verify, he has to raise the signature to the e power as in any RSA signature, which for the exponent I described will require t = 1 billion modular squaring operations. This will be a slow process, and the signer can control it by changing the size of t, without changing his own work factor materially. The authors also point out that modular squaring is an intrinsically sequential process which cannot benefit from applying multiple computers. So the only speed variations relevant will be those between individual computers. Another idea I had for a use of hard to verify signatures would be if you published something anonymously but did not want to be known as the author of it until far in the future, perhaps after your death. Then you could create a HTV signature on it, perhaps not identifying the key, just the signature value. Only in the future when computing power is cheap would it be possible to try verifying the signature under different keys and see which one worked. Hal Finney
Re: Remailers an unsolveable paradox?
Spam is the least of the problems for remailers when it comes to abuse. You should be more concerned about possible liability for illegal messages. In a way, spam has actually made the remailer operator's life easier as people today are used to receiving annoying and obscene email. Ten years ago, when I ran a remailer, people were genuinely shocked to receive unsolicited pornography. Yes, it's hard to believe today, but in those quaint times, when the Internet was in black and white, most users got only a few email messages a day and they were all from their friends, family and co-workers. As far as spam, next-generation remailers should incorporate hashcash, www.hashcash.org, to make sending an anonymous message relatively costly. Let it take a minute or more to generate the "stamp" necessary for a message to enter the remailer system and spam will not be a problem, while legitimate users will have no barrier. Hal
RPOW - Reusable Proofs of Work
I'd like to invite members of this list to try out my new hashcash-based server, rpow.net. This system receives hashcash as a Proof of Work (POW) token, and in exchange creates RSA-signed tokens which I call Reusable Proof of Work (RPOW) tokens. RPOWs can then be transferred from person to person and exchanged for new RPOWs at each step. Each RPOW or POW token can only be used once but since it gives birth to a new one, it is as though the same token can be handed from person to person. Because RPOWs are only created from equal-value POWs or RPOWs, they are as rare and "valuable" as the hashcash that was used to create them. But they are reusable, unlike hashcash. The new concept in the server is the security model. The RPOW server is running on a high-security processor card, the IBM 4758 Secure Cryptographic Coprocessor, validated to FIPS-140 level 4. This card has the capability to deliver a signed attestation of the software configuration on the board, which any (sufficiently motivated) user can verify against the published source code of the system. This lets everyone see that the system has no back doors and will only create RPOW tokens when supplied with POW/RPOW tokens of equal value. This is what creates trust in RPOWs as actually embodying their claimed values, the knowledge that they were in fact created based on an equal value POW (hashcash) token. I have a lot more information about the system at rpow.net, along with downloadable source code. There is also a crude web interface which lets you exchange POWs for RPOWs without downloading the client. This system is in early beta right now so I'd appreciate any feedback if anyone has a chance to try it out. Please keep in mind that if there are problems I may need to reload the server code, which will invalidate any RPOW tokens which people have previously created. So don't go too crazy hoarding up RPOWs quite yet. Thanks very much - Hal Finney
Re: On what the NSA does with its tech
MV writes:
> Yes. They can't break a 128 bit key. That's obvious. ("if all the
> atoms in the
> universe were computers..." goes the argument).
Not necessarily, if nanotechnology works. 128 bits is big but not
that big.
Eric Drexler, in Nanosystems, section 12.9, predicts that a nanotech
based CPU fitting in a 400 nm cube could run at 1000 MIPS and consume
60 nanowatts, performing 10^16 instructions per second per watt.
Let's design a system to break a 128 bit cipher. Let's suppose it has
to do 2^10 instructions per test, so this is 2^138 instructions total,
or about 10^41. Let's let it run for four months, which is 10^7 seconds,
so our necessary processing rate is 10^34 instructions per second.
This means we need 10^34 IPS / 1000 MIPS or 10^25 of Drexler's gigahertz
cubes, call it 10^25 cubic microns or 10^7 cubic meters, a cube about
220 meters on a side.
The system will consume 10^25 * 60 nanowatts or about 6 * 10^17 watts.
Now, that's a lot. It's four times what the earth receives from the sun.
So we have to build a disk four times the area (not volume) of the earth,
collect that power and funnel it to our computers. Probably we would
scatter the computers throughout the disk, which would be mostly composed
of solar collectors. (Keeping the disk gravitationally stable is left
as an exercise for the student, as is the tradeoff involved in making
it smaller but moving it closer to the sun.)
Fortunately, exhaustive key search is perfectly parallelizable so there
is no need for complex communications or synchronizations between the
processors.
As you can see, breaking 128 bit keys is certainly not a task which is
so impossible that it would fail even if every atom were a computer.
If we really needed to do it, it's not outside the realm of possibility
that it could be accomplished within 50 years, using nanotech and robotics
to move and reassemble asteroids into the necessary disk.
Now, 256 bit keys really are impossible, unless the whole contraption
above can be made to operate as an enormous, unified quantum computer,
in which case it could theoretically break even 256 bit keys.
512 bit keys... now those really are impossible.
Hal
Re: Email tapping by ISPs, forwarder addresses, and crypto proxies
), and the recipient's computer. The way between the forwarder > and the recipient's ISP, including the recipient's mailbox, is secured. > > What do you think about this scheme? I think it's a great idea. Of course as you say there is still the problem that the forwarding server could read your email, so you have only moved the threat from the ISP to another operator. The difference I suppose is that the forwarder would be selling privacy services, hence different ones would compete to get a good reputation. Any cheating might be detected by insider whistle blowers or perhaps some kind of audit. Hal Finney
