Two Web Application Proxy Servers and two AD FS 2.0 servers. Users are Office 365 users with a federated domain suffix so they must authenticate via AD FS.
Initially, only a few users were having issues logging into Office 365. As the day wore on, more and more users were having issues until there was a full on outage. Both internal clients and external clients were affected. The clients were getting this error when trying to log into Office 365
Sign In Sorry, but we're having trouble signing you in. We received a bad request. Additional technical information: Correlation ID: <ID> Timestamp: <timestamp> AADSTS50008: SAML token is invalid
On the AD FS servers there were no errors being logged in the AD FS/Admin event logs. We were able to browse to the self test site:
https://<ADFS Server public FQDN>/adfs/ls/IdpInitiatedSignon.aspx
Using the test site, a user account using a machine located within the corporate network, was able to authenticate successfully against AD FS. But logging into O365 failed for the same users.
As we were switching remote desktop sessions, the administrator, from the corner of his eye, noticed a time skew between the AD FS server time and the WAP server time. Upon further investigation, we found that the domain machines all had a time skew of about 20 minutes in the future of the actual time.
Since the WAPs are not joined to the domain, they are not using the DCs as the time source.
This time skew made perfect sense in relation to the error the clients were receiving. The authentication token that AD FS was granting was not yet valid when it was received by O365 servers.
We set the time right on the DCs and rebooted the AD FS servers. After the AD FS servers were available again, with the correct time, users were able to log into Office 365 successfully.