Problem:
All of a sudden o365 login is not working anymore.
Solution:
One of the simplest solutions, because we are dealing with time based assertions:
The time of the ucs system was ahead of its time. So the assertion was not valid yet.
You can simply adjust the servers time with
rdate -n <timeserver IP>