In other words, you should and most likely have to start from scratch again due to the way 2FA works (although you can use the same email).
You should, because you compromise your security when you lose your device (because 2FA functions on a device, even without internet).
You have to in most cases, because without backup codes for every account there is no way to recover your 2FA.
TIP: It isn’t enough to just have one backup code, for example the backup codes you get when you set up Google 2FA. To fully recover your 2FA you need to have the backup codes of each account you set-up 2FA on. This code is a security token that is a string of number and letters and/or a QR code. It is the code you use to actually set up your 2FA when you turn it on for a given account.
Given the above, it can be smart to always install 2FA on more than one device or to save the backup codes you get when you set up your 2FA. As both of these tactics will help speed up the process if a device is lost, broken, or stolen.
Basically there are two types of 2FA accounts. Those that you can’t recover if you lose your device, and those encrypted on a cloud that you can.
If you can recover your 2FA, then you can go through the recovery steps.
With most types of 2FA however, like with Google 2FA, the security comes from the 2FA app being device specific.
The only way to add the same 2FA with the same codes to another device is to have your backup codes.
When you first generate your 2FA you get a security token / QR code you can use to create your 2FA and you get backup codes. You’ll want to save both of these for account recovery (and yes, that means taking a screenshot of the QR code to use later).
Further, every time you set-up 2FA on another account you get a security token / QR code and often backup codes which you can save for account recovery later.
If you have saved all of these you can use the tokens and back-up codes to re-create your 2FA.
With that said, if you lost your phone you compromised your security… and that means you should set up a new 2FA anyway.
Still, having the backup codes / keys can make that process easier, as you won’t have to contact support for every platform with 2FA to have it reset, you can reset it yourself.
Even better, if you have 2FA on more than one device, you can quickly switch everything to a new 2FA after losing your device without having to deal with backup codes.
TIP: Especially with device specific 2FA, where your info isn’t recoverable via a cloud-based service, the most important part of account recovery isn’t your main 2FA account, it is the security tokens / QR codes / backup codes you get when you set-up 2FA on a given account. You can actually use those codes to access your accounts with 2FA on them even if you can’t recover your main account. So for example if you have Google 2FA, and then use it to put 2FA on Facebook, it is the Facebook security token that is the most important code to store for account recovery. Still, if you want to get everything back just the way it was, it makes sense to save your all tokens and codes for your main 2FA account too.
TIP: Always store important information offline in a secure format. For example, an encrypted USB drive is a good tool for storing important information like security tokens offline. You can even disconnect from the internet when you connect it to your computer for extra security.
- Common issues with 2-Step Verification. Support.Google.com.