Microsoft Authenticator Fails To Login Or Restore Backup On New iPhone (iOS 17)

Question

Microsoft Authenticator appears to be completely broken on iOS 17 as I've had this behavior on two phones.

First issue: restoring from iCloud backup completely fails and I suspect it has to do with the authentication to Office 365/Microsoft timing out. I know the backup is there as I can see it in the app but when I go to sign in it gives me the spinning wheel of death and then the error "Something Went Wrong". Based on older posts from 2022 this was due to an issue with some backend thing at Microsoft.

Before anybody asks:

1. I reached out to support, they said they were desktop support and referred me here
2. I know the backup exists, I can see it. I have tried removing the backup on the old phone and re-running it with no success.
3. The auth flow is kind of working, I can get login prompts on my old phone but the response time is extremely slow

The second (and possibly related) issue: I cannot sign into my Microsoft account in Authenticator on the new phone. Since I basically gave up on the backup I decided to re-add my account and just migrate codes manually. However the same thing happens: I sign in, verify it's me and then spinning wheel of death and a "Something Went Wrong" error.

I have a hunch this is a Microsoft issue since it happened on both phones. I accidentally tried to sign into my O365 account on the old phone and it timed out too!

This is incredibly frustrating as it means I have to keep my old phone around to use my Microsoft Account because I literally can't even turn off Two Factor Authentication in the Web UI which appears to be an entirely separate issue.

Here are the Incident IDs for my in app "feedback"
DSQDZP6Z - Backup enabled
D9GFFE7B - Backup disabled