I recently ran into the same issue while developing my app. I started off in debug mode and, following the docs, I added the SHA-1 and SHA-256 keys to the Firebase project settings. Everything was working fine so far. But when I switched to the release version to see how my app behaves in that environment, I started encountering errors.

I tried a bunch of different solutions, including directly adding the key to Google Cloud GCP interface to add restrictions to API keys, but none of that worked. After some more troubleshooting, I decided to try adding the key back to Firebase's project settings. And to my surprise, that fixed the issue! Now, everything works as expected in both debug and release mode. Firebase project settings As you can see I have 4 keys now(2 for debugging and 2 for release)

So, if you're facing similar issues, make sure you've added both SHA-1 and SHA-256 keys to Firebase's project settings. That might just do the trick!