So what's the answer? Here's two very legitimate scenarios:
1) You sign up, enable two-factor auth, then lock yourself out (lost password and your second-factor). How do you prove to the service provider that you are you?
2) You sign up, enable two-factor auth, then Mallory claims that they locked themselves out. How does the service provider prove that Mallory is not you?
Text message or phone verification of details only you should know about the account history, payment methods, etc. As others mentioned, a waiting period during which they try to contact using any means s previously authorised for a response. Compare IP addresses and deny logins from strange countries or origins without further verification, etc. Of course, every measure and countermeasure needs to be justified, since there's an implementation and upkeep cost, but... It's possible to be "more certain," that something is legit or not.
Yep, so text messages and phone verification could really be considered a "third factor". I guess anything information you have already provided to your service provider is considered an X-factor.
You should review the work NearlyFreeSpeech.NET recently did on customizable account recovery options. It's easy the best I've every seen. It works like this:
1) You decide how valuable the account is, the probability that you will lose access to the account, and the probability that the account will be attacked.
2) You selected the required number of recovery actions, from one recovery action to completely unrecoverable. Possible recovery actions include (copied from NFSN):
* You provide a scanned copy of a government-issued photo ID.
* You provide a scanned copy of a statement showing both the most recent deposit and a name and address matching one of your accounts.
* You complete SMS verification. (SMS must be previously configured.)
* You complete 2-factor verification. (2-factor auth must be previously configured.)
* You correctly answer your security question. (Security question and answer must be previously configured, below.)
* You use an ssh key to create a file with a specific name on one of your sites hosted here. (Must be previously configured, won’t work if account is empty.)
* We try and fail to contact you via your currently configured email address. (This one may take a long time.)
In this case, looping in the original email address on the SendGrid account before changing to a new one would have kept this from happening. SendGrid's support personnel should almost certainly not be able to change an email address without the change being signed off on through the old address first.
You need some kind of "okay, you can get your password back, but it's going to take some time. You cannot get back up instantly."
Maybe they FedEx the password to your physical address on file. Maybe they contact all phone numbers and emails they have for you and say "someone has requested an emergency override, if you object call us back in the next 4 hours." Maybe they do a Skype session and compare your photo to the one they have on file.
All this costs money, of course. That's the price of doing business.
Yes, this is part of what I'm trying to get answers to.
Do you tell the user on signup to print an in-case-of-emergency-break-glass password which is only ever to be used to get into a locked account and other special circumstances?
It may seem over the top but seeing as it's unique across service providers, I think it's a hell of a lot better than the overly abused "what is your mother's maiden name" type questions. I consider these questions to be in the same boat as sharing passwords between websites (since they are)!
Presuming you're paying for this service (and thus have a credit card registered to it), how about the "we've made two $0.00 - $0.99 charges on your card; tell us what the cents digits are and we'll refund them and give you a reset link" model? I've only ever seen it used to initially verify a card--but, provided a card has been verified, continued access to it can be used to re-verify a compromised account.
(And if someone has managed to break into both your personal email account and your business's online-banking account, getting your web-host to recognize you will be the least of your problems.)
The solution is to do what everyone who actually needs authentication from a company does; require a posted signed letter from a director, possibly along with an outbound (from SendGrid to the director) phone call to confirm. There's plenty of low-tech ways to confirm that a company really wants to do something.
Consider a determined attacker. A posted signed letter has zero cost and is easily forged and a phone call is free via Skype. There's plenty of low-tech ways to circumvent security.
How exactly does Skype let me take over a business's phone number? I am saying that SendGrid should call the company to verify, not the other way round.
I think these services could use timed release. If you have locked yourself out, the timer starts running. If after 30 days no one has denied the request, access is granted. I'm pretty sure this approach would foil most if not all social engineering.
1) You sign up, enable two-factor auth, then lock yourself out (lost password and your second-factor). How do you prove to the service provider that you are you?
2) You sign up, enable two-factor auth, then Mallory claims that they locked themselves out. How does the service provider prove that Mallory is not you?