Re: Maths holy grail could bring disaster for internet
hello, The security of elliptic curve cryptosystems depend on the difficulty in solving the elliptic curve discrete log problem(ECDLP). If any body gets to prove that P=NP, then all the public key cryptosystemts which rely on 'hard' problems will be useless for crypto. Sarath. --- Sunder [EMAIL PROTECTED] wrote: Forgive my ignorance, but would other PK schemes that don't rely on prime numbers such as Elliptic Curve be affected? --Kaos-Keraunos-Kybernetos--- + ^ + :Our enemies are innovative and resourceful, and so are we. /|\ \|/ :They never stop thinking about new ways to harm our country /\|/\ --*--:and our people, and neither do we. -G. W. Bush, 2004.08.05 \/|\/ /|\ : \|/ + v + :War is Peace, freedom is slavery, Bush is President. - On Tue, 7 Sep 2004, Matt Crawford wrote: On Sep 6, 2004, at 21:52, R. A. Hettinga wrote: This would be a good thing. Because to rebuild the infrastructure based on symmetric crypto would bring the trusted third party (currently the CA) out of the shadows and into the light. __ Do you Yahoo!? New and Improved Yahoo! Mail - Send 10MB messages! http://promotions.yahoo.com/new_mail
Re: Spam Spotlight on Reputation
At 03:15 PM 9/6/2004, Hadmut Danisch wrote: On Mon, Sep 06, 2004 at 11:52:03AM -0600, R. A. Hettinga wrote: E-mail security company MX Logic Inc. will report this week that 10 percent of all spam includes such SPF records, I have mentioned this problem more than a year ago in context of my RMX draft (SPF, CallerID and SenderID are based on RMX). Interestingly, nobody really cared about this major security problem. All RMX-derivatives block forged messages (more or less). But what happens if the attacker doesn't forge? That's a hard problem. And a problem known from the very beginning of the sender verification discussion. It's not a hard problem, just a different problem. Whitelisting your friends and aggressively filtering strangers is an obvious technique for reducing false positives without increasing false negatives, but it fails if spammers can forge identities of your friends. RMX-derivatives help this problem, and they help the joe-job problem. If a spammer wants to claim that they're the genuine spammers-are-us.biz, well, let them. I find it more annoying that there are spammers putting PGP headers in their messages, knowing that most people who use PGP assume PGP-signed mail is from somebody genuine and whitelist it. Bill Stewart [EMAIL PROTECTED]
Re: Gilmore case...Who can make laws?
At 11:19 AM 9/8/04 -0400, Tyler Durden wrote: Hum. I wonder. Do you think these secret regulations are communicated via secure channels? What would happen if someone decided to send their own regulations out to all of the local airline security offices rescinding any private regs, particularly if one used official-looking letterhead? It would be better to inject *more heinous* secret rules than to attempt to remove them. Why is left as an exercise to the reader. Fax would probably suffice. At 01:52 PM 9/7/04 -0500, J.A. Terranson wrote: I am however intrigued that they may be preparing to posit that secret rules (which act under color of law) can be enforced without being described publicly. This, if accepted, would effectively end all constitutional protections. The phrase constitutional protections doesn't pass the giggle test these days. However the courts --when trials get that far-- will still toss out cases in which the state's evidence is not revealed. I expect that behavior will stop when domestic-US secret trials become common. To protect means, methods, and the chldren, of course. At least the Europeans don't take the US seriously, esp after the use of torture was made clear, see eg the German trials. But the US is trying to control them via the oil connection. Rome did not fall in a day.
Re: Gilmore case...Who can make laws?
Well, still ruminating... The kind of regulations that regulatory bodies have made in the past are in their nature different from these secret rules I still believe. This is of course aside from their secret nature. Previously, if a regulatory body such as the FCC enacted some kind of policy, they could fine companies that did not comply. From my naive perspective, I didn't view these regs as really having a direct impact on private citizen units/individuals, apart from their organization, but then again I could probably think of exceptions. Hum. I wonder. Do you think these secret regulations are communicated via secure channels? What would happen if someone decided to send their own regulations out to all of the local airline security offices rescinding any private regs, particularly if one used official-looking letterhead? -TD From: J.A. Terranson [EMAIL PROTECTED] To: Eric Cordian [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Gilmore case...Who can make laws? Date: Tue, 7 Sep 2004 13:52:40 -0500 (CDT) On Tue, 7 Sep 2004, Eric Cordian wrote: An argument that the TSA cannot make rules, even secret rules, regulating air travel, because it is not Congress, will not pass the giggle test in court, unless you can show that the TSA exceeded its regulatory powers. Absolutely correct. I am however intrigued that they may be preparing to posit that secret rules (which act under color of law) can be enforced without being described publicly. This, if accepted, would effectively end all constitutional protections. -- Yours, J.A. Terranson [EMAIL PROTECTED] 0xBD4A95BF ...justice is a duty towards those whom you love and those whom you do not. And people's rights will not be harmed if the opponent speaks out about them. Osama Bin Laden - - - There aught to be limits to freedom!George Bush - - - Which one scares you more? _ Get ready for school! Find articles, homework help and more in the Back to School Guide! http://special.msn.com/network/04backtoschool.armx
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: Seth Schoen's Hard to Verify Signatures
At 11:48 AM 9/8/04 -0700, Hal Finney wrote: 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 could be called a salt-free algorithm :-) Basically its like the problem that a salted-password cracker has to solve when the salt has to be guessed. As far as a modexp() solution, I suggest this, which is as far as I can tell different from what you reference: In an RSA cryptosystem the public exponent is typically low, often 3 or 65537 (for efficiency reasons only a few bits are set; the other constraint is that your message, raised to that power, wraps in your modulus, which makes 65537 a little better). The private exponent is big. Therefore, traditional encryption is fast, and decryption is slow; the reverse is that signing is slow, verifying a signature is fast. This can be used to achieve Seth's required fast to make, slow to verify. To achieve the required user-controllable, the user gets to set the number of bits in the modulus. One might have to use extraordinarily long moduli (making 4Kbits look puny), depending on the time-scale of slow and fast, but so what, primes are free :-) and might even be re-used. If this passes group-muster pass it on..
Re: Seth Schoen's Hard to Verify Signatures
Hi
I proposed a related algorithm based on time-lock puzzles as a step
towards non-parallelizable, fixed-minting-cost stamps in section 6.1
of [1], also Dingledine et al observe the same in [2].
The non-parallelizable minting function is in fact the reverse: sender
encrypts (expensively) and the verifier encrypts again (but more
cheaply) and compares, but I think the relationship is quite analogous
to the symmetry between RSA encryption and RSA signatures.
I think maybe you have observed an additional simplification. In my
case I use sender chooses x randomly (actually hash output of random
value and resource string), and computes y = x^{x^w} mod n as the work
function (expensive operation); and z = x^w mod phi(n), y =? x^z mod
n as the cheap operation (verification).
I think your approach could be applied on the encryption side too
resulting in simpler, faster verification. Instead it would be:
x is random, compute y = x^{2^t+1} mod n; verify x =? y^d mod n
I'll add a note about that when I get around to updating it next.
Adam
[1] Hashcash - Amortizable Publicly Auditable Cost-Functions
http://www.hashcash.org/papers/amortizable.pdf
[2] Andy Oram, editor. Peer-to-Peer: Harnessing the Power of
Disruptive Technologies. O'Reilly and Associates, 2001. Chapter 16
also available as
http://freehaven.net/doc/oreilly/accountability-ch16.html.
On Wed, Sep 08, 2004 at 11:48:02AM -0700, Hal Finney wrote:
Seth Schoen of the EFF proposed an interesting cryptographic primitive
called a hard to verify signature in his blog at
An alternative is based on the paper, Time-lock puzzles and
timed release Crypto, by Rivest, Shamir and Wagner, from 1996,
[...]
Choose the number of modular squarings, t, that you want the
verifier to have to perform. [...] you will sign your value using
an RSA key whose exponent e = 2^t + 1. 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.
Re: Seth Schoen's Hard to Verify Signatures
From: \Hal Finney\ [EMAIL PROTECTED] Sent: Sep 8, 2004 2:48 PM To: [EMAIL PROTECTED] Subject: Seth Schoen's Hard to Verify Signatures 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. I've seen this described in a paper by Abadi, Lomas Needham as an alternative to a high iteration count for password hashing. Hal Finney --John Kelsey
Re: Seth Schoen's Hard to Verify Signatures
On Wed, Sep 08, 2004 at 12:44:39PM -0700, Major Variola (ret) wrote: [...] In an RSA cryptosystem the public exponent is typically low, often 3 or 65537 (for efficiency reasons only a few bits are set; the other constraint is that your message, raised to that power, wraps in your modulus, which makes 65537 a little better). The private exponent is big. Therefore, traditional encryption is fast, and decryption is slow; the reverse is that signing is slow, verifying a signature is fast. This can be used to achieve Seth's required fast to make, slow to verify. To achieve the required user-controllable, the user gets to set the number of bits in the modulus. One might have to use extraordinarily long moduli (making 4Kbits look puny), depending on the time-scale of slow and fast, but so what, primes are free :-) and might even be re-used. If this passes group-muster pass it on.. Can't be too short, less than about a third the size of the modulus you start running into problems [*], which, with the sizes you're suggesting (you would need, what, a 100K+ bit key to do this?) would make signature generation pretty slow too. Easier to do standard RSA and then encrypt the whole thing with a 64 or 80 bit symmetric key. [*] http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf -Jack
