System.ArgumentException when you create SharePoint 2013 Claims Based Site

Recently We were implementing SharePoint 2013 for one of our client. The requirement was quite simple and we were using all out of the box feature. Then when we create the team site it came as a surprise for as it dint work.

Problem:
We got "Exception of type 'System.ArgumentException' was thrown. Parameter name: encodedValue" error on creation of Claims based site (Which is default when you create site from central admin UI). When we looked at the stack trace  it was pointing at the issue with "Microsoft.SharePoint.Administration.Claims.SPClaimEncodingManager.DecodeClaimSuffix(String encodedValue) +600". After debugging for some days we found out that the issue is with STSToken issuer.

Solution:
SharePoint 2013 make use of STS webservice for authentication. If you want to check if STS is able to issue the security token, please execute the PowerShell script. if you get the token back then STS is working fine.
$farm = [Microsoft.SharePoint.Administration.SPFarm]::Local
$webServiceCollection = new-object Microsoft.SharePoint.Administration.SPWebServiceCollection($farm)
foreach ($service in $webServiceCollection)
{
    foreach ($webApp in $service.WebApplications)
    {
        $firstWebApp = $webApp
        #Get the context
        $context = $firstWebApp.GetResponseUri([Microsoft.SharePoint.Administration.SPUrlZone]::Default)
        Write-Host "Web Application Context:" $context.AbsoluteUri
        #Call the token generator function
        $token = [Microsoft.SharePoint.SPSecurityContext]::SecurityTokenForContext($context)
        Write-Host "Token:" $token.InternalTokenReference
        Write-Host "**************************"

    }
}
It turns out the core issue is about policy setting in domain level, the "System cryptography: Use FIPS compliant algorithms for encryption, hashing, and signing" is blocking the authentication. To check the stats of the policy, go to Local Security Policy > Local Policy > Security Option. The FIPS policy should be in disabled mode, if it's not, ask your network team to make changes to disable the FIPS.

 Once this is done, re-provision the STS using below script:
stsadm -o provisionservice -action start -servicetype "Microsoft.SharePoint.Administration.Claims.SPSecurityTokenService, Microsoft.SharePoint, Version=14.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" -servicename SecurityTokenService

After this your STS should function properly.