1. A method comprising: tracking credential usage of an end-user on one or more end-user devices by a cloud-based authentication service executing by a server computing system; receiving, at the cloud-based authentication service over a first connection between the server computing system and a relying party website, a credential request for credentials associated with the end-user for the relying party website, wherein the end-user no long has authentication credentials for access to the relying party website; issuing, by the cloud-based authentication service over a second connection between the server computing system and a first end-user device of the one or more end-user devices, a dynamic knowledge-based (KB) challenge to the end-user on the first end-user device, wherein the dynamic KB challenge is based on the tracked credential usage of the end user, wherein at least a portion of the dynamic KB challenge comprises information from the credential usage that is not site-centric to the relying party website; receiving, at the cloud-based authentication service over the second connection, a response to the dynamic KB challenge from the end-user; and sending temporary credentials over the first connection to the relying party website for the end-user when the response is validated.