The subject disclosure is directed towards securely synchronizing passwords that are changed at a source location (e.g., an on-premises directory service) to a target location (e.g., a cloud directory service), so that the same credentials may be used to log into the source or target location, yet without necessarily having each domain controller handle the synchronization. The plaintext password is not revealed, instead using hash values computed therefrom to represent the password-related data. The target may receive a secondary hash of a primary hash, and thereby only receive and store a password blob. Authentication is accomplished by using the same hashing algorithms at the target service to compute a blob and compare against the synchronized blob. Also described are crypto agility and/or changing hashing algorithms without requiring a user password change.