See also the Step-by-Step guide from Microsoft, referenced below.
Install Windows, and create a new controller (Active Directory Server) for the domain.
By default the trust will be non-transitive. This means that only users directly from the trusted domain may authenticate. This can be changed to transitive by using the netdom.exe tool. netdom.exe can also be used to add the trust between two realms.
You need to tell Windows on what hosts to find the KDCs for the non-Windows realm with ksetup, see See Configuring Windows to use a Heimdal KDC.
This needs to be done on all computers that want enable cross-realm
Then you need to add the inter-realm keys on the Windows KDC. Start the Domain Tree Management tool (found in Programs, Administrative tools, Active Directory Domains and Trusts).
Right click on Properties of your domain, select the Trust tab. Press Add on the appropriate trust windows and enter domain name and password. When prompted if this is a non-Windows Kerberos realm, press OK.
Do not forget to add trusts in both directions (if that's what you want).
If you want to use netdom.exe instead of the Domain Tree Management tool, you do it like this:
netdom trust NT.REALM.EXAMPLE.COM /Domain:EXAMPLE.COM /add /realm /passwordt:TrustPassword
You also need to add the inter-realm keys to the Heimdal KDC. But take care to the encryption types and salting used for those keys. There should be no encryption type stronger than the one configured on Windows side for this relationship, itself limited to the ones supported by this specific version of Windows, nor any Kerberos 4 salted hashes, as Windows does not seem to understand them. Otherwise, the trust will not works.
Here are the version-specific needed information:
For Windows 2003RC2, to change the trust encryption type, you have to use the ktpass, from the Windows 2003 Resource kit *service pack2*, available from Microsoft web site.
C:> ktpass /MITRealmName UNIX.EXAMPLE.COM /TrustEncryp RC4
For Windows 2008, the same operation can be done with the ksetup, installed by default.
C:> ksetup /SetEncTypeAttre EXAMPLE.COM AES256-SHA1
Once the relationship is correctly configured, you can add the required inter-realm keys, using heimdal default encryption types:
kadmin add krbtgt/NT.REALM.EXAMPLE.COM@EXAMPLE.COM kadmin add krbtgt/REALM.EXAMPLE.COM@NT.EXAMPLE.COM
Use the same passwords for both keys.
And if needed, to remove unsupported encryptions, such as the following ones for a Windows 2003RC2 server.
kadmin del_enctype krbtgt/REALM.EXAMPLE.COM@NT.EXAMPLE.COM aes256-cts-hmac-sha1-96 kadmin del_enctype krbtgt/REALM.EXAMPLE.COM@NT.EXAMPLE.COM des3-cbc-sha1 kadmin del_enctype krbtgt/NT.EXAMPLE.COM@EXAMPLE.COM aes256-cts-hmac-sha1-96 kadmin del_enctype krbtgt/NT.EXAMPLE.COM@EXAMPLE.COM des3-cbc-sha1
Do not forget to reboot before trying the new realm-trust (after running ksetup). It looks like it might work, but packets are never sent to the non-Windows KDC.