Is it possible to recover Google authenticator database I am using 2 factor authentication through google authenticator and forgot to keep backup for one of the websites (cex.io). When I changed to new phone, I uninstalled Google authenticator from the old one. And now I am locked out of my account. I still have access to the phone and I have reinstalled google authenticator. 

Now in this situation, is there any possible way to recover the keys for two factor that were saved on my phone? Customer support for cex.io is very slow and I am not sure when they are going to disable two factor so that I can setup for my new phone. If it is relevant, I was using Redmi 1s from Xiomi.
Google Authenticator uses "seed" values which are symmetric keys used to generate OTPs (One Time Passwords). This means there is more than one copy of these keys, one with Google and other with the registered applications. In a sense they are in pair, hence symmetric. When you try to register your new device with authenticator, there are more than two copies of these keys and this causes an authentication problem. If these keys were easy to be backed up and restored, the security might have been at risk. So, all you can do is re-register your new instance of Google Authenticator. For this you need to follow these steps-


Log in to your Google account (Since the Authenticator's key we have wouldn't be useful here, you can choose either Call or Message to get a code on your registered mobile number.)
After logging in, go to My Account > Sign-in &amp; Security. In the password and sign-in method click on 2-step verification (you will be asked to enter your password again).
On the next screen, you will see an option for Authenticator app, click Change phone and select Android or iPhone(accordingly). 
On your new phone install Google Authenticator app and open it, go to Set up an account and choose Scan barcode. Delete the previous entry if you have pre-installed the app and have an account registered.
On the next screen, enter the 6-digit key which you get on your app.
Let me know if there's an issue.