A couple of other thoughts on this:

• Instead of passing hostID + signature, I think we should just pass publicKey + signature, essentially like the SSH handshake works, and Almanac devices should add their public keys to PhabricatorUserSSHKey (at some point, we'll rename that to PhabricatorKnownPublicSSHKey or something, and change userPHID to objectPHID). This allows users to use the signing mechanism, too, and makes public key lookup consistent. This can give us a place to solve the caching problem too, maybe (allow the table to store keys in multiple formats).
• I think we probably should hand the private key to ConduitClient and put the signing logic there, and have request signature computation live in libphutil.

Sooooo it looks like ssh-keygen -e -f ... -m ... is broken on Mavericks.

What about Yosemite?

I can work around it regardless, but you can check with this if you have Yosemite:

ssh-keygen -y -f ~/.ssh/id_rsa > rsa.pub # generate your ssh-formatted public key if you don't have a copy already
ssh-keygen -e -f rsa.pub -m pem # this fails on Mavericks

Chads-MacBook-Pro:~ chad$ ssh-keygen -y -f ~/.ssh/id_rsa > rsa.pub
Chads-MacBook-Pro:~ chad$ ssh-keygen -e -f rsa.pub -m pem
PEM_write_RSAPublicKey failed

Yep, same failure mode I'm getting. There are reasonable workarounds, it's just a minor setback.

I need to reduce/alter the authentication strength of this a bit. D1040 originally required CLI access to associate a key with a device, so it was OK to give requests using a key to authenticate omnipotent access because association guaranteed direct database access.

Since you can use the web UI to manage keys, giving device keys omnipotent access unconditionally would violate the security model: anyone with Almanac access could add a key to a device, then sign requests with it and act as the omnipotent user.

We do need omnipotent keys (or at least highly-privileged keys) so the daemons can make unrestricted requests when processing repositories. These need to be elevated via CLI, though.

For non-CLI keys, I'm going to let administrators optionally bind them to bot accounts. If they're unbound, they won't be usable for Conduit authentication. A new CLI workflow (bin/almanac empower-device-key or similar) will rebind them as omnipotent. This is better for the SAAS case too, because web instances can have a device key with very limited access (essentially, read-only access to Almanac). Unbound keys will still be accessible via the API (eventually) and usable for third-party key stuff.

I'm going to skip all the account binding junk and just sign the SAAS requests as a user instead of as a device. It's simpler and not much different in the end.

This is effectively working now. Some followup work in T5955 and T6706.