Password Sync uses MD5 hash algorithms for compatibility reasons.
The MD5 algorithms are used to decrypt the password hash derived from Active Directory.
Windows Azure Active Directory Sync then re-hashes the password hash with a stronger SHA256 hash per RFC 2898 before sending it to the cloud.
The SHA256 hash is computed using the crypto API documented at http://msdn.microsoft.com/en-us/library/windows/desktop/dd433795(v=vs.85).

Federal Information Processing Standard (FIPS)-compliant systems bar use of MD5 hash algorithms.
Password Sync will fail with the following exception (logged in the event log) in a FIPS enabled environment:

Microsoft.Online.PasswordSynchronization.SynchronizationManagerException: Recovery task failed. ---> System.InvalidOperationException: This implementation is not part of the Windows Platform FIPS validated cryptographic algorithms. at System.Security.Cryptography.MD5CryptoServiceProvider..ctor() at Microsoft.Online.PasswordSynchronization.PasswordUtility.ComputeMd5(Byte[] sessionKey, Byte[] salt) at Microsoft.Online.PasswordSynchronization.PasswordUtility.Decrypt(Byte[] rid, Byte[] sessionKey, Byte[] salt, Byte[] encryptedData) at Microsoft.Online.PasswordSynchronization.ClearPasswordHashGenerator.CreatePasswordHash(ChangeObject changeObject) at Microsoft.Online.PasswordSynchronization.PasswordHashGenerator.CreatePasswordHash(ChangeObject changeObject) at Microsoft.Online.PasswordSynchronization.PasswordSynchronizationTask.CreatePasswordData(ChangeObject changeObject) at Microsoft.Online.PasswordSynchronization.PasswordSynchronizationTask.BuildPasswordBatch(IList`1 passwordChanges, IEnumerable`1 changeObjects) at Microsoft.Online.PasswordSynchronization.RecoveryTask.SynchronizeCredentialsToCloud()

To fix the exception, Password Sync can be enabled in a FIPS compliant system by locally disabling FIPS for the Directory Sync process.
This can be done by adding the following to the miiserver.exe.config file:
<enforceFIPSPolicy enabled="false" />
The miiserver.exe.config can be found at:
%ProgramFiles%\Windows Azure Active Directory Sync\SYNCBUS\Synchronization Service\Bin\miiserver.exe.config.