Embodiments authenticate a user in response to receiving from a Kerberos key distribution center (“KDC”) a request to authenticate the user that includes a user identification (“ID”). Embodiments retrieve a user record corresponding to the user ID, the user record including a principal key. Embodiments decrypt the principal key using a tenant-specific encryption key and encrypt the decrypted principal key using a Kerberos master key to generate an encrypted principal key. Embodiments retrieve a password policy corresponding to the user ID. Based on the retrieved password policies, embodiments construct password state attributes and return to the KDC the encrypted principal key, the password policy and the password state attributes.