blinded scalarmult on untrusted workers

[warner]

@tarcieri pointed out that we could spread the work over untrusted worker nodes by blinding a base private key on the local (trusted) controller first. If I understand it correctly, we'd do something like:

• generate private scalars a and b locally, use scalarmult to compute A = aG and B = bG
• send elements A and B to worker (keeping scalars a and b secret)
• worker counts with scalar k starting from some random value (so each worker searches a different part of the space)
• worker computes C = A + kB for each k, serializes C into base64, checks for substring match, sends k to controller when a match is found
• controller computes private key a+kb, and public key (a+kb)G which should match C

The one wrinkle is that Curve25519 private keys are generally clamped (zeroing out the low-order 3 bits) to prevent an information leakage ("small subgroup attack") for implementations that don't check the public key for group membership. I don't think that clamping would be compatible with this scheme: the a+kb value will have non-zero low-order bits, and the public key associated with clamped(a+kb) will be completely different (and won't have the substring match). On the other hand, I don't know if Wireguard cares about clamping or not.

[tarcieri]

I think it should be possible to design a scheme where a+kb is always equal to clamped(a+kb) by relying on certain properties of how a, b, and k are chosen, although clamping is moderately more involved than just clearing the lowest three bits (to clear the cofactor), it also clears the highest bit (to ensure the integer is modulo p), and sets the second highest bit, which I understand is important for certain implementations of the Montgomery ladder, including, I believe, "ref10".

I think you might be able to reuse some of the procedures/formulas from BIP32-Ed25519 for this purpose.

[warner]

The work in #12 is encouraging: once that lands, the main question will be how to manage the remote workers.

As for UI, I'm thinking of letting you add one or more --remote arguments to say "in addition to the local machine, also run a worker on this other machine":

wireguard-vanity-address --remote [USER@]HOSTNAME [..--remote..] PREFIX

The leader would spawn ssh user@hostname wireguard-vanity-address --worker and then talk to it over stdio. The leader would send a line line search PREFIX BASE_PUBKEY, and would expect back lines line progress NUMKEYS ELAPSEDTIME and then a single found COUNT BASE_PUBKEY. After found, the worker will do nothing until it gets a new search command (since we only use one keypair per starting point).

The progress messages should be used to compute an aggregate search rate. I'd love some sort of curses-style status display, like how rustc shows compile progress: the bottom-most line shows the number of worker machines, keys checked per second, elapsed time, total keys checked, total keys found. The rest of the lines show the keys themselves. The keys are printed to stdout so you can go back and cut-and-paste your favorite (and so they can scroll off the top and still be retrievable), but the status goes to stderr. And if you're piping the whole thing into a pty, it only prints keys, and skips all the status stuff.

It might be useful to allow some amount of pipelining: send a second (or third, etc) search command while the first ones are still running. If the worker finds suitable keypairs quickly, this would avoid wasteful idleness during the round-trip time.

Another useful option would be --remotes FILENAME, where the file would contain one remote specifier per line.

I can imagine someone wanting the tool to be able to spin up AWS nodes and shut them down again afterwards, but I think I'd prefer that go into a separate program. Maybe the --remotes argument would be enough to support such a program: it spins up the nodes and gets ssh configured, writes all the contact details into the file, runs wireguard-vanity-address --remotes FILENAME PREFIX, waits for the user to interrupt it (needs to catch SIGINT), kills the child process, then shuts down all the AWS nodes before terminating.