Hybrid Configuration Wizard Error: Browser based authentication failed

In a recent project we were preparing the Exchange servers for running the Hybrid Configuration Wizard (HCW). When trying to authenticate to Office 365, we encountered an error preventing us from proceeding. When clicking the “Sign-In” button within the HCW, a browser windows opened shortly and closed directly. The HCW showed two different error messages:

Looking at the HCW logs (%appdata%\Microsoft\Exchange Hybrid Configuration) there was no further information that could help finding the issue …

2022.07.16 11:40:25.555 WARNING 10396 [Client=UX, Page=Credentials, Thread=1] Authentication Failure: [Unknown] The browser based authentication dialog failed to complete. Reason: The server or proxy was not found.
2022.07.16 11:40:44.116 WARNING 10396 [Client=UX, Page=Credentials, Thread=1] Authentication Failure: [Unknown] The browser based authentication dialog failed to complete. Reason: The download has failed (the connection was interrupted).

Checking the firewall showed, that when reproducing the error, no packets were sent to the firewall, so it had to be a local problem on the machine running HCW. Even though we were using Microsoft Edge for HCW startup and Windows had Edge as default browser, it still would use Internet Explorer settings that caused the issue.

In our environment, Internet Explorer settings were mostly unconfigured and so it turned out, that TLS 1.2 was disabled in the internet settings. So the easy solution to a hard to find error was enabling TLS 1.2 in the advanced internet properties of Windows.

I hope this helps when you encounter the same issue. If yes, leave a comment or describe your solution to help others.