Opened 3 years ago
Last modified 4 weeks ago
#8106 assigned defect
Make .onion addresses harder to harvest by directory servers
Reported by: | asn | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | Tor: 0.2.??? |
Component: | Tor | Version: | |
Keywords: | SponsorZ, tor-hs, 026-triaged-1, 027-triaged-1-out | Cc: | isis@…, teor |
Actual Points: | Parent ID: | #12424 | |
Points: |
Description
Currently, an HSDir can relax on the hash ring, receive descriptor lookups and harvest .onions for days. Furthermore, it doesn't even have to change identity keys, since its position on the hash ring changes every day (because of the timestamp), so it gets new .onions all the time.
This ticket is for research on how we can make .onion addresses harder to harvest.
Proposal 143 has some ideas that will reduce the exposure of .onions, but it doesn't solve the problem itself.
On actual solutions, Robert posted:
https://lists.torproject.org/pipermail/tor-dev/2012-September/004026.html
some months ago. I don't have the cryptographic skills to robustly analyze his idea, but if this is the only thing we have, we should point some cryptographers at it so that it gets some comments.
I also seem to recall that there was a paper suggesting hidden services to create ephemeral .onion addresses or something, but after asking Karsten and crawling anonbib I'm not sure that such a paper exists.
Are there any other proposed solutions out there? If not, this might be a fun research problem.
Child Tickets
Attachments (1)
Change History (43)
comment:1 in reply to: ↑ description ; follow-up: ↓ 11 Changed 3 years ago by rransom
comment:2 Changed 3 years ago by nickm
- Milestone set to Tor: 0.2.5.x-final
- Priority changed from normal to major
comment:3 Changed 3 years ago by asn
(Finally, found the paper I mentioned in my first post. It's Lasse and Paul's Valet services: Improving hidden servers with a personal touch and the idea is detailed in subsection Distributing tickets of section 3.2. Unfortunately, IIRC their idea depends on the Valet services idea which is not-implemented and controversial (proposal 142 is related). When I get some time I should reread the Valet services paper.)
comment:4 follow-up: ↓ 5 Changed 2 years ago by asn
Valet Services paper: http://freehaven.net/anonbib/cache/valet:pet2006.pdf
Here is the Valet Services scheme (as presented in subsectionDistributing Tickets of section 3.2) adapted to the current HS protocol:
a) HS finds the HSDirs responsible for it exactly like in the current HS protocol. b) HS uploads its descriptor symmetrically encrypted with key = H(onion+'1') HS also uploads an index for the descriptor, where index = H(onion+'2')
When a client wants to visit the HS:
a) The client derives the key and the index from the .onion. b) The client fetches the descriptor from the HSDir and decrypts it with the key.
A problem pointed out by Nick is that this turns HSDir into cloud storage servers, since anyone can upload anything to it.
comment:5 in reply to: ↑ 4 Changed 2 years ago by asn
Replying to asn:
A problem pointed out by Nick is that this turns HSDir into cloud storage servers, since anyone can upload anything to it.
I guess we can make this a bit less painful, by partially encrypting the descriptor. Basically, by encrypting all the fields of the descriptor, but leaving the headers intact. And of course by enforcing a size limit.
The current v2 descriptor has encrypted fields that can be used to store arbitrary information anyway (like the introduction-points encrypted-string field).
comment:6 Changed 2 years ago by nickm
Reposting with permission an old message of Robert Ransom's about Valet Services, their drawbacks, and better living through cryptography:
The system described in section 3.2 of that paper does not allow a directory server to verify that a hidden service descriptor is being published to a descriptor index by a party which "owns" the index. I see no way that the reverse-hash-chain technique described there could prevent an attacker from publishing a bogus descriptor with a targeted hidserv's descriptor index. At best, if the hidserv "wins the race", the hash-chain would allow it to hold on to its descriptor index; at worst, the attacker could win the race and lock out the real hidserv. The only system I have come up with to hide a hidserv's identity key from the directory servers requires that the hidserv use a discrete-log cryptosystem for its identity key, and that the HS address contain enough of the identity key that a client can compute a scalar multiple of the identity key. (For example, the identity key can be a point on an elliptic curve in Weierstrass form, and the HS address can be the point's x coordinate.) The system designer chooses a group, an element P of prime order p in that group, and a publicly computable one-way function h mapping bitstrings to integers in the interval [1, p-1]. The HS chooses a secret key n and computes its public key nP; its descriptor index in time period t can be computed by any party which knows its public key as h(t | nP)*nP, but only the HS will know the discrete logarithm h(t | nP)*n of the descriptor index with base P. The HS can therefore compute an ECDSA signature, for example, which the directory server can verify using the descriptor index as a public key. > Also "Privacy-enhancing Technologies for Private Services", Karsten's > PhD dissertation, also available from the anonbib. > Also see Tor proposal > 121-hidden-service-authentication.txt I am aware of the current authentication mechanism for hidden services (which those documents describe), but it cannot hide the hidden service's identity key or name from the directory servers.
comment:7 follow-up: ↓ 8 Changed 2 years ago by asn
Robert, in the scheme of comment:1, where you use Ed25519 for the
discrete-log-based long-term keypair, the HS address (".onion") is
supposed to be the Ed25519 public key base32'ed, right?
If yes, Ed25519 public keys are 256-bits long, whereas old HS
addresses were only 80 base32'ed bits. This means that new HS
addresses will be much longer than the old ones, right?
If the difference is so big, why not just append a symmetric key to
the end of the 80-bits that currently get base32'ed?
What am I missing here?
comment:8 in reply to: ↑ 7 Changed 2 years ago by rransom
Replying to asn:
Robert, in the scheme of comment:1, where you use Ed25519 for the
discrete-log-based long-term keypair, the HS address (".onion") is
supposed to be the Ed25519 public key base32'ed, right?
I would use the Montgomery-form x coordinate of the public-key group element, not the Ed25519 public key format (which consists of the Edwards-form y coordinate plus an additional bit specifying the other Edwards coordinate's LSB). (Point-reduced Montgomery form is more convenient for single-scalar variable-base multiplication, which is what a client would need to do with that group element in order to blind the public key.)
For an elliptic curve without a secure ‘twist’, the Edwards-form y coordinate is probably better. (The extra bit identifying the other coordinate is still unnecessary.)
If yes, Ed25519 public keys are 256-bits long, whereas old HS
addresses were only 80 base32'ed bits. This means that new HS
addresses will be much longer than the old ones, right?
HS addresses for my protocol over the Curve25519/Ed25519 elliptic curve would be 255 bits long (so 51 base32 characters, not 52). They would be longer than the current protocol's addresses, but 80-bit addresses are too vulnerable to brute-force attacks to be used in any new protocol (about 2^{80-n} ‘operations’ to break the first of 2^{n} targets).
Note that if you want to continue to sacrifice security for usability with the new HS protocol, you can use an elliptic curve over a smaller coordinate field. For example, page 16 of http://cr.yp.to/newelliptic/twisted-20080313.pdf specifies a suitable curve over 2^{160} - 47 (32 base32 characters); impersonating any HS over that curve would require a discrete-logarithm computation (around 2^{80} ‘operations’ to impersonate the first HS of any number of targets; significantly harder than brute-forcing an 80-bit space). (There should be a good elliptic curve over a convenient 200-bit coordinate field too, if you want something in between that and Curve25519.)
If the difference is so big, why not just append a symmetric key to
the end of the 80-bits that currently get base32'ed?
What am I missing here?
80-bit addresses are no longer long enough to prevent impersonation by brute force.
My protocol is the only one that can be used to prevent HSDir servers from linking an HS's descriptors across days (or whatever time periods you choose for the new protocol). (If you want this feature, you'll also have to either encrypt HS descriptors or abandon introduction points at ‘day’ boundaries. Encrypting the bodies of HS descriptors (everything but the expiration time, day number, and serial number) is a good idea anyway.)
Apart from those reasons, I see several possible protocols that fit your description (or are plausible extensions of it) except for the length of the public-key hash. All of them are trickier to implement securely than my protocol, and require similar HS address lengths to my protocol for similar security levels.
comment:9 Changed 2 years ago by rransom
2^{200} - 75, 2^{199} - 49, 2^{199} + 101, 2^{198} - 17, 2^{198} + 15, 2^{195} + 35, 2^{194} - 33, and 2^{194} + 27 are prime.
comment:10 Changed 2 years ago by rransom
2^{190} - 11 is also prime.
comment:11 in reply to: ↑ 1 Changed 2 years ago by asn
Replying to rransom:
Replying to asn:
On actual solutions, Robert posted:
https://lists.torproject.org/pipermail/tor-dev/2012-September/004026.html
some months ago. I don't have the cryptographic skills to robustly analyze his idea, but if this is the only thing we have, we should point some cryptographers at it so that it gets some comments.
For an Ed25519-based signature scheme with both the public-key group element and the base point blinded, the verification equation is equivalent to S*B = (HB(nonce, B, A)^(-1))*R + H(R, HB(nonce, B, A)*B, HB(nonce, B, A)*A, M)*A, where R is carefully chosen to be a uniform random group element and HB(nonce, B, A) is (computationally) independent of R. This equation does not leak any more information about the log of A than the verification equation for unmodified Ed25519 does, so this cryptosystem is obviously as safe as Ed25519.
Thanks for your last message (wrt onion address sizes using your scheme).
Another question: how did you end up with S*B = (HB(nonce, B, A)^(-1))*R + H(R, HB(nonce, B, A)*B, HB(nonce, B, A)*A, M)*A as the verification equation of ed25519? How did the extra HB(nonce, B, A)*B get into H()?
comment:12 follow-up: ↓ 13 Changed 2 years ago by asn
I called it extra because the hash in the vanilla verification equation is H(R,A,M) while yours has 4 parameters: H(R, HB(nonce, B, A)*B, HB(nonce, B, A)*A, M)
comment:13 in reply to: ↑ 12 ; follow-up: ↓ 14 Changed 2 years ago by rransom
Replying to asn:
I called it extra because the hash in the vanilla verification equation is H(R,A,M) while yours has 4 parameters: H(R, HB(nonce, B, A)*B, HB(nonce, B, A)*A, M)
In Ed25519, the public key is A. In my blinded-public-key variant of Ed25519, the blinded public key is (HB(nonce, B, A)*B, HB(nonce, B, A)*A). Since Ed25519 uses H(R, (public key), M) as its message hash, the obvious message hash to use for a blinded-public-key version was H(R, (blinded public key), M).
comment:14 in reply to: ↑ 13 Changed 2 years ago by hyperelliptic
Hi, this is Tanja Lange
Replying to rransom:
Replying to asn:
I called it extra because the hash in the vanilla verification equation is H(R,A,M) while yours has 4 parameters: H(R, HB(nonce, B, A)*B, HB(nonce, B, A)*A, M)
In Ed25519, the public key is A. In my blinded-public-key variant of Ed25519, the blinded public key is (HB(nonce, B, A)*B, HB(nonce, B, A)*A). Since Ed25519 uses H(R, (public key), M) as its message hash, the obvious message hash to use for a blinded-public-key version was H(R, (blinded public key), M).
I'm a bit puzzled by the basepoint updating etc. Could you state what your definition of S is (other than: it's the S that makes this work). In general you want to avoid inversions modulo the group order.
I also doubt that basepoint blinding is a good idea: I understood the idea of this scheme to be that the server can "verify" signatures under the updated public keys and ensure that no party can override another parties data (unless by chance they hit the same daily public key or one party breaks the DLP). However, if I let an attacker choose the basepoint then he can sabotage the system by choosing the public key the same as mine (i.e. overriding my data) and computing a basepoint and matching secret key to have the signature verify on the server side. Of course this would be caught by the clients, because the signature is not valid under what should be today's basepoint so it "only" affects availability but that's not good. You cannot give the functionality to compute today's basepoint to the server (if you want to hide A), so I don't know how to bootstrap from this. I don't have a similar concern with the original scheme posted in the email.
If you want proofs then of course it's necessary to come up with a simple cryptographic assumption that this can boil down to -- but it makes sense to define the scheme first (and rule out simple attacks).
Some commments on the earlier post:
I don't see what the trouble with the factor 8 on all sides would be - other than 3 extra doublings.
comment:15 Changed 2 years ago by rransom
Here is ‘pseudocode’ (actually, ready-to-compile code written in a not-yet-implemented programming language) specifying exactly how to implement my signature scheme.
PrivKey = struct { a: Exponent; messageKeySecret: byte[32]; }; PubKey = struct { A: GroupElement; }; BlindingNonce = byte[32]; BlindedPubKey = struct { Bprime: GroupElement; Aprime: GroupElement; }; Message = byte[]; Signature = struct { R: GroupElement; s: Exponent; }; B: GroupElement; keygen = procedure(): (PubKey, PrivKey) { priv := PrivKey{ a = hashToExponent(generateRandomBytes(64)), messageKeySecret = generateRandomBytes(32) }; pub := PubKey{ A = scalarmult(priv.a, B) }; return (pub, priv); }; blindPub = procedure(pub: PubKey; nonce: BlindingNonce): BlindedPubKey { blindingExponent := HB(nonce, B, pub.A); return BlindedPubKey{ Bprime = scalarmult(blindingExponent, B), Aprime = scalarmult(blindingExponent, pub.A) }; }; sign = procedure(priv: PrivKey; pub: PubKey; nonce: BlindingNonce; msg: Message): Signature { blindedPub := blindPub(pub, nonce); r := hashToExponent(H(priv.messageKeySecret, nonce, msg)); R := scalarmult(r, blindedPub.Bprime); messageHash := H(groupElementToBytes(R), groupElementToBytes(blindedPub.Bprime), groupElementToBytes(blindedPub.Aprime), msg); s := r + (hashToExponent(messageHash) * priv.a); return Signature{R = R, s = s}; }; verify = procedure(blindedPub: BlindedPubKey, msg: Message, sig: Signature): Bool { messageHash := H(groupElementToBytes(sig.R), groupElementToBytes(blindedPub.Bprime), groupElementToBytes(blindedPub.Aprime), msg); verificationEqLHS := scalarmult(sig.s, blindedPub.Bprime); verificationEqRHS := sig.R + scalarmult(hashToExponent(messageHash), blindedPub.Aprime); return (verificationEqLHS == verificationEqRHS); };
sig.s is computed in almost exactly the same way as Ed25519's S; the only change is in what is hashed along with the message. (I've used a lowercase s here instead of Ed25519's uppercase S so that it won't be mistaken for a group element.)
There is no need to skip Ed25519's multiplication of both sides of the verification equation by 8; I omitted it here (and in my post above) for the sake of clarity.
To prove that the verification equation for this signature scheme leaks no more information about the secret key than Ed25519's verification equation, divide both sides of it by blindingExponent and divide the definition of sig.R by blindingExponent. (The verification equation is equivalent to the equation I posted above.)
Also note that the blinded public key contains the blinded base point; the attacker does not get to choose the base point separately from the blinded public-key group element.
comment:16 follow-up: ↓ 17 Changed 2 years ago by rransom
Also, the blinded base point is a function of the non-blinded public key.
comment:17 in reply to: ↑ 16 Changed 2 years ago by hyperelliptic
Replying to rransom:
Also, the blinded base point is a function of the non-blinded public key.
I understand, that's why I said that the clients will notice the attacker, but the server cannot check this (without knowing A -- and the whole point of this scheme is that the server should not know A). There is also no way that the server can verify that B and the other point have been multiplied by the same scalar -- again, that's a feature, otherwise you'd be back to enumeration attacks, so don't try using pairing-friendly curves on this.
My understanding is that the nonce will be time dependent, so clients know the nonce and know the public key of the hidden service and everybody knows B. So, they can compute HB(nonce, B, pub.A) and the updated key parameters. I assume that they then ask the server for the information on Aprime = scalarmult(blindingExponent, pub.A), right? If the server stores the encrypted routing information under Aprime then I can override this -- with a differnt Bprime, but there is no way to say which one is right; you cannot take the first one either, otherwise at least insiders knowing A can compute the next Aprime just a tad faster and submit that along with a wrong Bprime.
Note that you need 2 different verification equations: one for the server (which does not know A and the nonce) and one for clients who first recompute Aprime and then check that the world matches, i.e. the verification needs 2 steps.
I realize that you can bootstrap from this by including Bprime in the storage location so that the real data and the attack data get written to different places, but then you suddendly have twice the length.
Could you describe what worried you about the version in which the basepoint does not vary?
comment:18 follow-up: ↓ 19 Changed 2 years ago by asn
Hey Robert,
I talked with hyperelliptic today and she explained me her concerns of comment:17. I'm just bumping this thread -- in case you missed the last comment or forgot about it -- because now I'm also wondering about the leak in the version where only the public key is blinded.
comment:19 in reply to: ↑ 18 ; follow-up: ↓ 20 Changed 2 years ago by rransom
Replying to asn:
Hey Robert,
I talked with hyperelliptic today and she explained me her concerns of comment:17.
None of those concerns are legitimate.
I'm just bumping this thread -- in case you missed the last comment or forgot about it -- because now I'm also wondering about the leak in the version where only the public key is blinded.
I have told you three times now -- twice on this ticket, and another time in a semi-private discussion -- why my cryptosystem is as secure as Ed25519. This is the last time that I will explain it to you.
As you know, in all ElGamal-like discrete-logarithm-based signature schemes, each signature discloses a linear equation relating the long-term signing secret key to the per-message secret key. Because of this information leak, a signature scheme which is secure when used with independent, identically distributed long-term signing secret keys may not be secure when a signer uses multiple long-term secret keys which are related by publicly known equations. (Forgery remains as hard as recovering one of the secret keys, even when they are related.)
My original idea was to use an existing signature scheme with multiple related secret keys. Since you and Nick claim to be too afraid of ‘new’ cryptographic primitives to consider using one in Tor, this would have required an easy-to-understand security argument, and I didn't expect it to have one.
In my revised cryptosystem, each signature discloses the same linear equation involving the hidden service's long-term signing secret key that an Ed25519 signature using a slightly different hash function would. Thus, this cryptosystem is provably as secure as Ed25519, and the proof is so simple that anyone who had read the Ed25519 paper would understand it.
Because my goal was to find a cryptosystem which would provide the security properties which a new hidden service protocol would require, I quit looking for a security argument for my original idea once I had found an alternative with such a simple proof of security. I don't know why you have put so much effort into finding a broken scheme to use instead.
comment:20 in reply to: ↑ 19 ; follow-ups: ↓ 21 ↓ 22 Changed 2 years ago by hyperelliptic
Replying to rransom:
Replying to asn:
Hey Robert,
I talked with hyperelliptic today and she explained me her concerns of comment:17.
None of those concerns are legitimate.
Huh? Let me try this again.
There are two security requirements:
- Nobody can produce a signature that passes verification by a user knowing A's long-term key.
AND
- Nobody can produce a signature that passes verification for the short-term public key.
The second proposal of rransom flunks the second requirement.
Here is why this requirement matters:
The HS address is the x-cooordinate of the short-term public key. This can be computed by anybody knowing the long-term public key. An attacker could overwrite the correct information on the directory service with bogus information if he could produce a signature under the short-term public key.
What makes the attack work on the second scheme is that the basepoint is provided as part of the signature and is therefore under the control of the attacker.
To avoid this problem, use a fixed basepoint or use x(short-term key),x(basepoint) as HS address.
comment:21 in reply to: ↑ 20 Changed 2 years ago by hyperelliptic
To be fully explicit, here is the attack using your notation; l is the group order.
Aprime = scalarmult(blindingExponent, pub.A);
this is computed the proper way so that it will store to the desired HS address.
fakea = hashToExponent(generateRandomBytes(64));
inva = 1/fakea mod l;
Bprime = scalarmult(inva, Aprime);
r = hashToExponent(generateRandomBytes(64));
R = scalarmult(r, Bprime);
messageHash := H(groupElementToBytes(R),
groupElementToBytes(blindedPub.Bprime),
groupElementToBytes(blindedPub.Aprime),
msg);
s := r + (hashToExponent(messageHash) * fakea);
return Signature{R = R, s = s};
verification will work because
sBprime = rBprime+(hashToExponent(messageHash) * fakea)Bprime
R + (hashToExponent(messageHash) * fakea*1/fakea)Aprime
R + hashToExponent(messageHash) Aprime
This is all the directory service can check, so it will accept the information provided with the signature as authoritative.
comment:22 in reply to: ↑ 20 ; follow-up: ↓ 23 Changed 2 years ago by rransom
Replying to hyperelliptic:
Replying to rransom:
Replying to asn:
Hey Robert,
I talked with hyperelliptic today and she explained me her concerns of comment:17.
None of those concerns are legitimate.
Huh? Let me try this again.
There are two security requirements:
- Nobody can produce a signature that passes verification by a user knowing A's long-term key.
AND
- Nobody can produce a signature that passes verification for the short-term public key.
The second proposal of rransom flunks the second requirement.
Here is why this requirement matters:
The HS address is the x-cooordinate of the short-term public key. This can be computed by anybody knowing the long-term public key. An attacker could overwrite the correct information on the directory service with bogus information if he could produce a signature under the short-term public key.
What makes the attack work on the second scheme is that the basepoint is provided as part of the signature and is therefore under the control of the attacker.
To avoid this problem, use a fixed basepoint or use x(short-term key),x(basepoint) as HS address.
I said explicitly in comment:13, before your first comment here, that the blinded base point is part of the blinded public key:
In Ed25519, the public key is A. In my blinded-public-key variant of Ed25519, the blinded public key is (HB(nonce, B, A)*B, HB(nonce, B, A)*A).
I said in comment:15, in the explicit description of my signature scheme which you specifically asked for (and thus can be expected to have read), that the blinded base point is part of the blinded public key:
BlindedPubKey = struct { Bprime: GroupElement; Aprime: GroupElement; };
Since you had previously missed that fact in comment:13, I repeated it for emphasis in comment:15, as explicitly as it can be said:
Also note that the blinded public key contains the blinded base point; the attacker does not get to choose the base point separately from the blinded public-key group element.
You have not only misrepresented my idea, you are now attempting to claim credit for it.
I'm done putting up with your crap.
comment:23 in reply to: ↑ 22 ; follow-up: ↓ 24 Changed 2 years ago by hyperelliptic
I said explicitly in comment:13, before your first comment here, that the blinded base point is part of the blinded public key:
In Ed25519, the public key is A. In my blinded-public-key variant of Ed25519, the blinded public key is (HB(nonce, B, A)*B, HB(nonce, B, A)*A).
If you meant this to say that the .onion address is the concatenation of the 2 x-coordinates than the easy reply to "I realize that you can bootstrap from this by including Bprime in the storage location so that the real data and the attack data get written to different places, but then you suddendly have twice the length." in
https://trac.torproject.org/projects/tor/ticket/8106?replyto=22#comment:16
would be to say that you in fact accept the double length.
In any case, double-length .onion addreses or a broken scheme are pretty "legitimate reasons for concern".
comment:24 in reply to: ↑ 23 Changed 2 years ago by rransom
Replying to hyperelliptic:
I said explicitly in comment:13, before your first comment here, that the blinded base point is part of the blinded public key:
In Ed25519, the public key is A. In my blinded-public-key variant of Ed25519, the blinded public key is (HB(nonce, B, A)*B, HB(nonce, B, A)*A).
If you meant this to say that the .onion address is the concatenation of the 2 x-coordinates than the easy reply to "I realize that you can bootstrap from this by including Bprime in the storage location so that the real data and the attack data get written to different places, but then you suddendly have twice the length." in
https://trac.torproject.org/projects/tor/ticket/8106?replyto=22#comment:16
would be to say that you in fact accept the double length.
In any case, double-length .onion addreses or a broken scheme are pretty "legitimate reasons for concern".
The ‘.onion address’ (I prefer the term “hidden service address” or “HS address”) represents a public key (PubKey), not a blinded public key (BlindedPubKey). A hidden service address can still contain only one group element (or a compact representation of one).
The blinded public key would only be used in two ways in the directory-service protocol, where users do not need to see it:
- Each hidden service periodically uploads a ‘hidden service descriptor’ (a message accompanied by a signature and a blinded public key) to each of several directory servers. Currently, each hidden service descriptor contains an ASN.1-encoded RSA public key with 1024-bit modulus, variable-length exponent, and some wrapping bytes, and an ASN.1-encoded RSA signature under that public key. Using the Curve25519 curve without point compression, my blinded public key is smaller than the current public-key blob, and my signature is smaller than the current signature blob; with point compression, both my blinded public key and my signature are smaller than the current public-key modulus alone.
- Each hidden service client uploads a collision-resistant hash of a blinded public key to a directory server in order to obtain a hidden service's most recent descriptor. My blinded public keys are small enough at 512 bits that the hash could be omitted.
comment:25 Changed 2 years ago by rransom
If you don't like the fact that my BlindedPubKey contains two group elements, find a good security argument for a cryptosystem satisfying the properties that I specified above in which BlindedPubKey contains only one group element. Ed25519 with only A blinded may indeed be secure; I stopped trying to prove it secure because I didn't need to in order to solve this problem.
(Also, it would be nice to find a concise, meaningful term for such a cryptosystem.)
comment:26 Changed 2 years ago by asn
FWIW, we decided that the way forward with this task is to devise a robust proof of the suggested protocol. Dan and Tanja suggested to prove the protocol under the generic-hash generic-group model.
We also decided that if we manage to prove the variant where the base point is not blinded, we should proceed with that. OTOH if we don't manage to prove that scheme, we should try to prove the variant where the base point is blinded (like Robert has been suggesting).
comment:27 Changed 2 years ago by nickm
Incidentally, Christian Grothoff told me that GNUnet does something similar here, but they haven't done a proof either.
comment:28 Changed 2 years ago by isis
- Cc isis@… added
Changed 23 months ago by asn
comment:29 follow-up: ↓ 30 Changed 23 months ago by asn
I started writing the crypto part of the proposal (https://lists.torproject.org/pipermail/tor-dev/2013-October/005534.html) and I think I understood why Robert prefers the variation where the base point is blinded.
If the base point is blinded, the ed25519 verification equation remains the same. If we don't blind the base point, the original unblinded public key appears in the equation and HSDirs are not supposed to know it.
There might be a smart multiplication somewhere there that would make the unblinded public key disappear from the equation, but I don't see it currently.
I attached my notes in attachment:hs_notes.jpg which are hopefully cleaner than math equations in Trac.
comment:30 in reply to: ↑ 29 Changed 23 months ago by hyperelliptic
Hi everybody.
Replying to asn:
There might be a smart multiplication somewhere there that would make the unblinded public key disappear from the equation, but I don't see it currently.
Yes, the equation changes. The initial version had some divisions, which will not be so good performance wise. So, here is how it works without blinding the base point:
General system set up: base point B on elliptic curve, B has prime order l.
Signer knows: a (secret key), h=blinding factor of the day =hash(date,A,B), where date is given in some agreed upon precision.
Long-term public key (known to the user): A=aB
Public key of the day: A'=hA=(ha)B
This means, that the secret key of the day is (ha).
Signature which is valid under A':
Pick random r (or better, compute it in some deterministic manner, see EdDSA paper),
compute R=rB, compute S=r+hash(R,A',M)ah mod l, send signature (R,S) and public key A'
Verify at DS: check whether SB=R+hash(R,A',M)A'.
This works for a valid signature since
SB=(r+hash(R,A',M)ah)B=rB+(hash(R,A',M)ah)B=R+hash(R,A',M)A'
Verify by user: User knows A and date, so can compute A' to query DS. Can verify signature
the same way as DS does.
All the best
Tanja
comment:31 Changed 22 months ago by asn
Some notes from the CCS meeting:
The scheme requires two proofs.
The first one proves that the public keys of this scheme are unlinkable to each other (unlikability). Apparently this is easy to prove using the random-oracle model + the standard DDH assumption.
The second proof guarantees that an adversary should not be able to forge signatures (unforgeability), even if she has access to an arbitrary amount of previous signatures, or ephemeral public-keys or the long-term public key.
This seems like a harder proof. The idea is to try to prove this using the forking lemma (which apparently might be the easiest way to do this) and hope that it gives us a tight security bound (it usually doesn't, apparently). Then we can start working on a tighter security proof.
comment:32 follow-up: ↓ 34 Changed 22 months ago by asn
During the CCS meeting, someone said that Bitcoin is using a similar construct for their "Pay to Contract" scheme. I can't find a textual description of the protocol, but here is a video https://www.youtube.com/watch?v=qwyALGlG33Q
comment:33 Changed 18 months ago by nickm
- Milestone changed from Tor: 0.2.5.x-final to Tor: 0.2.6.x-final
comment:34 in reply to: ↑ 32 Changed 17 months ago by wfn
Replying to asn:
During the CCS meeting, someone said that Bitcoin is using a similar construct for their "Pay to Contract" scheme. I can't find a textual description of the protocol, but here is a video https://www.youtube.com/watch?v=qwyALGlG33Q
Maybe something like this:
comment:35 Changed 16 months ago by asn
Stupid of me to not update this page with the proof that Nick posted in tor-dev:
https://lists.torproject.org/pipermail/tor-dev/2013-December/005943.html
You can find the proof here:
https://www-users.cs.umn.edu/~hopper/basic-proof.pdf
comment:36 Changed 14 months ago by nickm
- Keywords 026-triaged-1 added
comment:37 Changed 12 months ago by nickm
My 'ed25519_ref10' branch now has an implementation of the key blinding approach, as I understand it. It is pretty simple, based on ed25519_ref10, and is done in a file named "blinding.c". It will need review. I should finish that branch first.
comment:38 Changed 10 months ago by nickm
- Milestone changed from Tor: 0.2.6.x-final to Tor: 0.2.7.x-final
- Parent ID set to #12424
comment:39 Changed 5 months ago by nickm
- Status changed from new to assigned
comment:40 Changed 5 months ago by nickm
- Keywords 027-triaged-1-out added
Marking triaged-out items from first round of 0.2.7 triage.
comment:41 Changed 5 months ago by nickm
- Milestone changed from Tor: 0.2.7.x-final to Tor: 0.2.???
Make all non-needs_review, non-needs_revision, 027-triaged-1-out items belong to 0.2.???
comment:42 Changed 4 weeks ago by teor
- Cc teor added
Replying to asn:
For an Ed25519-based signature scheme with both the public-key group element and the base point blinded, the verification equation is equivalent to S*B = (HB(nonce, B, A)^(-1))*R + H(R, HB(nonce, B, A)*B, HB(nonce, B, A)*A, M)*A, where R is carefully chosen to be a uniform random group element and HB(nonce, B, A) is (computationally) independent of R. This equation does not leak any more information about the log of A than the verification equation for unmodified Ed25519 does, so this cryptosystem is obviously as safe as Ed25519.
(My original proposal (only blind the public-key group element (A in Ed25519)) would have had a different, potentially leakier, verification equation.)
Tor's hidden service protocol requires a cryptosystem with the following properties:
(This is equivalent to a pair of signature schemes A and B, with a pair of blinding functions (A.PubKey, BlindingNonce) -> B.PubKey and (RNG, A.PrivKey, BlindingNonce) -> B.PrivKey, but specifying the properties that this pair of blinding functions needs would be more annoying.)
The obvious ways to blind RSA-like and McEliece-like public keys allow an attacker to link different blinded versions of the same original public key. It might be possible to blind public keys for multivariate-quadratic or Alekhnovich-type cryptosystems, but there's enough structure in MQ keys that I would expect to see linkability issues, and if there are suitable signature schemes based on the LPN-like problems, they won't be as well-understood as discrete-log-based signatures. So, for now, any cryptosystem that solves this problem will look a lot like my (revised) proposal (unless someone comes up with a screwy pairing-based version that provides lower security and lower performance).