Sharing "mined" private keys (.onions) with others in a trustless way?

[xanoni]

The ones who ask the seemingly stupid questions—the questions that no one else dares to ask—can sometimes make the critical difference, so let's do this ;-)

Is there any way a "mined" private key (vanity .onion) can be shared with another person (for that person to use it to host some service), WITHOUT requiring full trust in the person who originally found the key?

Without further precautions, I assume the person receiving the key has no guarantees that the person who found the key didn't keep a copy to then take over the service (or to at least surveil it in some form).

I don't see how this could be made trustless, but maybe my superficial knowledge of ed25519 is not sufficient to see the relevant nuances.

[scribblemaniac]

In my non-expert opinion: yes it is likely possible. This is possible with ECDSA for sure as there are multiple programs out there that support this functionality already. See https://bitcoin.stackexchange.com/questions/3853/can-one-safely-buy-vanity-addresses-from-a-third-party-without-risking-ones-coi for an explanation of how this works. Since EdDSA also relies upon elliptic curves, it seems like it should have the same properties and would be able to generate vanity addresses trustlessly in the same way. Here someone is asking that very question and although there is no answer, it does have some relevant links: https://crypto.stackexchange.com/questions/75981/does-eddsa-share-schnorr-signature-secure-linearity-property.

Without further precautions, I assume the person receiving the key has no guarantees that the person who found the key didn't keep a copy to then take over the service (or to at least surveil it in some form).

Yes if someone you do not trust has a copy of your private key at any point, it's worthless from a security standpoint.

[xanoni]

That's pretty cool... nice. Now we just need to put the pieces together ...

[cathugger]

huh so basically, requester sends public keys to miner.
miner performs certain amount of additions to that given public key and finds public key which matches given criteria.
then miner returns amount of additions it performed to requester.
quite nifty idea.

[cathugger]

and requester then easily adds that counter to its current secret key.
not very difficult to implement logic wise but i wonder what best protocol would be for this.

[cathugger]

additionally, with that linearity property, one wouldn't need to re-send new public keys for eventual exhaustion case. one could just send offset public key. upon successful match, workserver would send private keys back, which would be added to local offset private key. in theory. there are some actual limitations to what ed25519 secret key components have to look like. so not 100% sure if this would be okay.

[cathugger]

was thinkin abt this a bit and even if we use scalar addition to make up secret keys, we would still need sending fresh ones upon every successful find because otherwise other keys would be too easy to compromise by leaking only single key of such set.
attacker would know scalars it generated in set, and if one scalar with secret part added gets leaked, attacker could easily subtract whole key from their part and obtain secret part they could easily use to calculate rest of keys from the set by adding secret part to them.
it's non-issue if user would only use single key of set but definitely a footgun. honestly it's probably going to be much easier to just think of proper way of feeding needed data to workserver which will make this problem go away regardless whether we only send deltas or do scalar addition magic.

[adapt-L]

I think this is a great idea, and I would like to offer a 0.8 monero bounty to anyone who can implement this properly.

I've been trying to generate a 10-char onion address, and at this rate it will take me a year or two. My attempts to make a GPU-accelerated vanity generator have been abysmal, with only ~0.2% performance of amd64-64-24k on the host CPU. With this feature, I could just have my buddy mine the vanity for me on his server.

I don't really know much about elliptic curve cryptography, but the impression I get from cathugger is that networking is only needed for generating multiple vanities that are independently secure from the miner if the SK is revealed.

My use case here is just generating a single vanity, but could a generic solution to this be something like the client generates 1000 random keypairs and puts all the public keys in a file and manually sends them to miner? I think It would remove the need for networking, so the user interface is basically just:

• a command-line flag for the client to generate N keypairs (where N is a big number like 1000 by default) and export the seckeys and pubkeys to separate files

Client sends the pubkey file to miner...

• a command-line flag for the miner to generate vanities using the file full of pubkeys, iterating through the list every time it finds one.

The miner does that and uses the first command-line flag to export the seckeys and pubkeys to separate files, and sends them back to the client...

• a command-line flag for the client to combine the keypair files

The client combines the keypairs and exports it as a normal onion service directory

I guess it isn't so great if you're generating like millions of vanities and doing some sort of dictionary search or something, but the filtering should really be done on the miner's side, no?

In any case, I think transferring the client's public keys manually in bulk through file transfer would be simpler for the client who may be behind all sorts of firewalls, NAT and other crap. For example, the miner could just be some automated (paid?) service that exposes a web server, and the client can upload their pubkey file through a web form.

[dzwdz]

I've implemented a basic PoC at https://github.com/dzwdz/mkp224o/tree/trustless. It seems to work, but I'm not sure if the math checks out. The code definitely could use some work too.

The host generates a set of base keys and sends the public part to the miner.
I haven't implemented any sort of networking or native support for multiple keys, as I don't think it's necessary.
If you wanted each generated vanity address to use a separate base key, you could just do something like this:

for base in keys/*
do
    mkp224o -n 1 --basekey $base -d out/$base/ neko
done

[preland]

Hey, I’ve been looking at this project for a few days, and it seems to be pretty promising.

I have a question regarding this issue in specific, or rather the solution currently being shown.

Would it be possible to use this “trust-less” solution to pre-generate keys for a ton of filters, building a “catalog” of sorts?
IE: if someone goes to the catalog with a specific request that has already been generated in the catalog, it can retrieve the information required for the request to be fulfilled.

If this is the case, then there is an incredibly large amount of potential here.

[dzwdz]

Would it be possible to use this “trust-less” solution to pre-generate keys for a ton of filters, building a “catalog” of sorts? IE: if someone goes to the catalog with a specific request that has already been generated in the catalog, it can retrieve the information required for the request to be fulfilled.

No. The mined .onion is tied to your keypair - if you change the base key, the address changes too.

If I'm understanding you correctly - you're asking about creating a catalog where one could redeem a premined .onion such that they would be the only person with access to the private keys. What would stop someone else (e.g. the catalog's owner) from also "redeeming" it? This solution only works because you already know the base keypair in advance.

[adapt-L]

Here is a funny idea for @preland: you might be able to create a service that crawls Tor for onion addresses and mines vanities for them ahead of time, filtering for random dictionary words, or words that occur within the onion services' webpage, for example within the webpage's <title>.

I suspect it won't be very profitable though.

[preland]

Funnily enough, I actually have already set up mkp on my own system to mine for dict. words and send the data to a yaml file (my OS rly didn’t like dumping tons of data to filesystem). I have found some interesting words using this method, but unfortunately there isn’t much use for them since they can’t be transferred to anyone without breaching their security, and I don’t really feel like personally hosting websites with random dictionary words.

I think the concept of someone sending a secure “url request” to a compute farm has some potential, but the two issues I see with it are:

1. Since you can’t “mine” for something you aren’t looking for, if someone wanted a long URL (and was somehow willing/able to pay for the effort) they would still have to wait a very very long time.
2. Say you did mine for this hypothetically long URL, let’s say it is 10 characters long. You somehow finish the cracking and send the result to the client. Statistically speaking, you probably just mined over 1 QUADRILLION URLs (32^10), all of which will be thrown away save one.

If that is what is required for trust-less, then that is what is required, but it still feels like a waste, especially when those 1 quadrillion urls most likely contain every combination of 11-character and below URLs.

[adapt-L]

Well, firstly I think the storage, bandwidth and CPU overhead of dictionary filtering could be non-trivial in some situations. But, @preland here is an interesting idea that could dramatically increase the "efficiency" of vanity mining for multiple peers:

Imagine Alice is a vanity mining service for Bob and Carl, who want vanities that begin with "bobsdomain" and "carldomain" respectively. Could you extend this shared vanity mining such that Alice combines her new pubkeys with BOTH Bob's pubkey and Carl's pubkey before filtering? That way, let's say if Alice filters the keypairs made through this process and finds a domain like "bobsdomain", then Alice and Carl can both reveal their secret key so only Bob can use it (and vice-versa if "carldomain" is found first).

It does require some level of co-operation between Bob and Carl, so it is not exactly sybil-proof (a solution may be to have the clients pay Alice upfront, and then Alice rewards/punishes them for co-cooperatively revealing/not-revealing keys in this fashion). Also there is the additional (filtering, etc.) overhead which could be nontrivial as mentioned earlier, but I expect a massive performance improvement for the reasons you mention (you don't have to generate >1 quadrillion keypairs for each new client).

This method wouldn't work with the onion scraping idea I mentioned earlier, because it requires Bob and Carl to make a temporary keypair that they may reveal if needed. The problem is that this method increases in efficiency as the number of clients peer together, but it is not sybil proof (it only takes a single person to stall the process by not revealing their keypair). It would not be able to "pre-generate keys for a ton of filters" like you asked for @preland, because it requires active user participation.

Again, I am not a cryptographer, so I may be wrong about this.

[adapt-L]

Basically what I am saying is if two people Bob and Carl want to share a trustless mining service (Alice) together, the Bob would --genbase bob.sec bob.pub, then give his bob.pub to Carl who makes a single keypair with -n 1 --basekey bob.pub --genbase bobcarl.sec bobcarl.pub, then Carl would give the resulting bobcarl.pub to Alice who mines with --basekey bobcarl.pub.

If Alice produces a pubkey that Bob wants, then Carl reveals his seckey so Bob can --combine and vice-vesa.

[dzwdz]

@adapt-L That's a brillant idea! I've implemented it on my local copy. I'll work on it a bit more and push it to the fork.
My interface's a bit simpler, the miner can just specify multiple --basekeys.

You could probably implement a mining pool based on this idea too. Instead of just searching for the .onion you want, you'd search for all the .onions that the other miners want, in exchange for them searching for your .onion too.

From the user's perspective - you'd run a modified fork of mkp224o with the same arguments as if for solo mining. It'd fetch the filter list and basekey from the network and start searching, periodically sending partial results back to show that it really is working.
After doing enough work for the network, your filters and basekeys would join the work pool too, so other miners would start working on them too.
This would yield results (much?) faster than solo mining at no extra effort/cost from the user.

Also, because this would be automated, there isn't as much of a reason to worry about an user deciding that sending their keys back isn't worth the effort. The program would automatically generate the base keys and submit them to the network every time a key is found with no user intervention.

I don't know if there's enough demand for vanity onions to make this worthwhile, though. Maybe this would create it?

(also - I'm not a cryptographer either, I have very little experience. Just because my implementation seems to work doesn't mean that it's correct.)

[GiverofMemory]

Ya, key arithmetic always sounds cool until you realize it increases vulnerabilities and decreases transparency, like schnorr.

My thought for a good direction for this would be autoencrypting private key somehow with a secret from the commisioner (reciever) and using signatures to verify nothing has been tampered with. No clue whether that is a viable strategy though. This direction, even if imperfect, will never compromise key strength, but worst case would be somehow the miner was able to bypass the security and knows your key, in which case the only variable remains the trustworthiness of the miner you chose, which is the same as it is now.

Even if all other known vulnerabilities are addressed that @cathugger mentioned, certainly the keys generated using scalar addition magic would have less than 256 bits of entropy (and could have an unpredictable amount of entropy) and thus would be a gold mine for crackers.

Allowing passphrase based keys is the only vulnerability mkp224o keys may possess (if they use a passphrase to generate, which is not standard), but it is a necessary option for mobility (passing through checkpoints where you can't carry files with you) and it is good that option is not widely publicised.

[adapt-L]

My thought for a good direction for this would be autoencrypting private key somehow with a secret from the commissioner (receiver) and using signatures to verify nothing has been tampered with.

I don't understand what you're describing here, but this sounds like security-by-obscurity.

Even if all other known vulnerabilities are addressed that @cathugger mentioned, certainly the keys generated using scalar addition magic would have less than 256 bits of entropy (and could have an unpredictable amount of entropy) and thus would be a gold mine for crackers.

Would they? I am not that familiar with elliptic curve cryptography. Can you prove that a keypair produced through this method may have less entropy than a normal keypair if one of the seckeys used in this method is known?

[dzwdz]

I have renewed interest in the project since it seems relevant to onionmine. When thinking through the security implications of generating private keys in this manner, I've discovered a bug in my current implementation. I wrote a detailed explanation, but in short: the Ed25519 paper specifies some restrictions on private keys my fork didn't respect. I don't think this has any major security implications, but it still needs fixing. Each way of fixing it has tradeoffs.

I believe the best approach here would be limiting the range of base keys. I was thinking of capping the maximum amount of base keys used at n = 2^16 = 65536, which would require base keys to be <= 2^237, which would give them a security level of around 118 bits.

I could also drop support for mining against multiple base keys, which would increase the base key range to 2^253, giving a security level of 126 bits.