Symptoms

Establishing a domain trust between Samba on Fedora 33 and an Active Directory on Windows Server 2016 failed with the following log output in /var/log/samba/log.winbindd:

[2021/05/02 17:14:40.562837,  2, pid=3415] ../../auth/kerberos/kerberos_pac.c:101(check_pac_checksum)
 check_pac_checksum: PAC Verification failed: Decrypt integrity check failed (-1765328353)
[2021/05/02 17:14:40.562892,  2, pid=3415] ../../auth/kerberos/kerberos_pac.c:101(check_pac_checksum)
 check_pac_checksum: PAC Verification failed: Decrypt integrity check failed (-1765328353)
[2021/05/02 17:14:40.562961,  2, pid=3415] ../../auth/kerberos/kerberos_pac.c:101(check_pac_checksum)
 check_pac_checksum: PAC Verification failed: Decrypt integrity check failed (-1765328353)
[2021/05/02 17:14:40.563008,  2, pid=3415] ../../auth/kerberos/kerberos_pac.c:101(check_pac_checksum)
 check_pac_checksum: PAC Verification failed: Decrypt integrity check failed (-1765328353)
[2021/05/02 17:14:40.563063,  3, pid=3415] ../../auth/kerberos/kerberos_pac.c:413(kerberos_decode_pac)

Checking other possible sources

Windows side

In Windows' System Event Log the following entry could be found:

Log Name: System  
Source: Microsoft-Windows-Kerberos-Key-Distribution-Center  
Event ID: 14  
Task Category: None  
Level: Error  

While processing an AS request for target service krbtgt, the account user did not have a suitable key for generating a Kerberos ticket (the missing key has an ID of 1). The requested etypes : 18 20 26 19 17 25. The accounts available etypes : 23 -133 -128. Changing or resetting the password of user  will generate a proper key.

Wireshark

In Wireshark we were able to confirm that the Kerberos AS request did acutally provided the given set of encryption types stated in Windows' System Event Log:

Reducing possible influences

After digging into this issue, executing kinit inside the Fedora environment already failed with

KDC has no support for encryption type while getting credentials for user@DOMAIN.TLD

That showed us that this problem has not been a misconfiguration of Samba or winbindd but of the Kerberos installation of Fedora.

Root issue

Microsoft has described the issue in "Unsupported etype" error when accessing a resource in a trusted domain document. As the trust between Samba and Windows could not be established in the first place, we were not able to use ksetup /setenctypeattr $domain to change the supported encryption types for the (non-existing) trust.

For the domain controller of the Active Directory domain, we tried to changed the MsDS-SupportedEncryptionTypes with ADSIEdit to an encryption type Samba supports. This had no effect, even after restarting the KDC distribution center service. We assume that the whole DC had to be restarted which was not possible at that moment.

Adjusting Kerberos encryption types on the Fedora side

Squid's documentation contains a working configuration for Kerberos and Windows 2008 and later, which we applied to /etc/krb5.conf:

[libdefaults]
; only relevant for the issue above
default_tgs_enctypes = aes256-cts-hmac-sha1-96 rc4-hmac des-cbc-crc des-cbc-md5
default_tkt_enctypes = aes256-cts-hmac-sha1-96 rc4-hmac des-cbc-crc des-cbc-md5
; not relevant for this exact issue but also required
permitted_enctypes = aes256-cts-hmac-sha1-96 rc4-hmac des-cbc-crc des-cbc-md5

Relevant for this very issue is the default_tgs_enctypes but the other parameters have to be also set. In addition to that, rc4-hmac is required because of the reasons Microsoft is describing in their document. Afterwards we were able to establish the domain trust.