AADSTS90072 User Does not Exist in Tenant

During a recent migration project from one tenant to another, a test user was unable to sign in. The sign-in page in Office 365 redirected to AD FS on-premises for authentication. The user credentials worked in AD FS and the web browser was redirected back to Office 365. Then this error was displayed: 

Sign in

Sorry, but we’re having trouble signing you in.

AADSTS90072: User account 'Bob.Smith@domain.com' from identity
provider'urn:sso.domain.com:domain.com' does not exist in
tenant 'Byron Co' and cannot access the application '4765445b-
32c6-49b0-83e6-1d93765276ca'(OfficeHome) in that tenant. The
account needs to be added as an external user in the tenant
first. Sign out and sign in again with a different Azure
Active Directory user account.

This error indicates that the user authenticated by AD FS does not exist in Azure AD. Based on the UPN, Bob.Smith@domain.com existed both in on-premises AD and Azure AD. So, there is some other property being used to match the two objects after AD FS authentication.

To understand where this broke down, you need to understand how objects in AD are linked with objects in Azure AD. There is an ImmutableID property on Azure AD users that links Azure AD users to on-premises AD users. Early implementations of Azure AD Connect (or Dirsync) copied the object GUID from on-premises AD and used that value for the ImmutableID. This worked well until you migrated user objects to new AD domain or AD forest where they'd have a different GUID.

New implementations of Azure AD Connect use ms-ds-ConsistencyGUID in the on-premises user object instead of GUID. This value can be copied between domains to preserve synchronization during object migrations. By default ms-ds-ConsistencyGUID is populated with the same value as the object GUID the first time the object is synced.

AD FS authentication uses the object GUID or ms-ds-ConsistencyGUID during authentication. This value must match the ImmutableID in AzureAD to allow authentication to complete. The older instructions for configuring AD FS authentication manually had you configure a rule for object GUID. If you use Azure AD Connect to configure AD FS then it creates rules that use ms-ds-ConsistencyGUID if populated or object GUID. This article talks about the rule configuration: https://docs.microsoft.com/en-us/azure/active-directory/hybrid/how-to-connect-fed-management#modclaims.

If you update your deployment of Azure AD Connect to use ms-ds-ConsistencyGUID as the source anchor and forget to update AD FS to allow ms-ds-ConsistencyGUID in the authentication process, AD FS authentication will continue to work because object GUID and ms-ds-ConsistencyGIUD are the same value by default. However when you start migrating objects and retain the ms-ds-ConsistencyGUID (which will now be different from the object GUID) authentication starts to fail because the token passed back to Office 365 for authentication contains the object GUID which doesn't match the immutable ID/ms-ds-ConsistencyGUID. Thus the error message above.

In our case, the AD migration tool we were using copied the ms-ds-ConsistencyGUID from a source AD domain to target AD domain which caused our authentication issue. Because users were getting new mailboxes in this migration, we didn't need to maintain ms-ds-ConsistencyGUID. Our short term fix was to copy the object GUID value and place that in ms-ds-ConsistencyGUID and immutableID. However, the correct long term solution is to update AD FS to correctly use ms-ds-ConsistencyGUID during authentication.

This article has some examples you can use to convert object GUID to ms-ds-ConsistencyGUID and ImmutableID: http://byronwright.blogspot.com/2020/10/convert-immutableid-to-hex.html.