This is more to assist the community than to address any particular unresolved issue. After many hours of searching I could not find any discussion on this and mostly had to confirm behavior through trial and error. Since most of my research and testing was strictly around signing e-mails (not encrypting), I will stick to just discussing signing behavior in this post.

Background

Issue

When our users would try to send signed e-mails to external parties, the receiver would often get the error below in their Outlook client.

Error: The system cannot validate the certificate used to create this signature because the issuer's certificate is either unavailable or invalid. The system cannot determine whether the certificate used to create this signature is trusted or not.

In our particular case we are using Sectigo certificates issued from an enterprise account. This issue ultimately stemmed from the fact that our Outlook clients were not attaching intermediate certificates. This was confirmed by exporting e-mails as .eml files from the modern Outlook client and then running openssl commands against them to strip the attached certificates and display their subject and issuer.

Hopefully the details in this post help anyone else who runs across this.

Intermediate Certificate Authorities

I'm not certain on the protocols and standards Outlook, Outlook (Classic), Outlook for Mac, or OWA use; but it is something along the lines of S/MIME, which in turn is based off CMS, which in turn was built off PKCS#7. A .p7s or .p7m file will be attached to the e-mail which includes the message body, attachments, signature, s/mime meta data, etc. in a single attachment.

https://en.wikipedia.org/wiki/S/MIME

https://en.wikipedia.org/wiki/Cryptographic_Message_Syntax

https://www.rfc-editor.org/info/rfc5652/ 

The PKCS#7 standard clearly states that signed data should include intermediate certificates that "may be required to verify these signers."

https://signify.readthedocs.io/en/latest/pkcs7.html#signeddata

The CMS RFC5652 states "The CertificateSet type provides a set of certificates. It is intended that the set be sufficient to contain certification paths from a recognized 'root' or 'top-level certification authority' to all of the sender certificates with which the set is associated."

https://www.rfc-editor.org/info/rfc5652/#section-10.2.3

The S/MIME RFC8550 states "In many cases, the certificates included in a signed message may represent a chain of certification from the sender to a particular root."..."Sending agents SHOULD include any certificates for the user's public key(s) and associated issuer certificates. This increases the likelihood that the intended recipient can establish trust in the originator's public key(s)."

So all that to say, it is not only desired, but expected that e-mail clients sending signed e-mails will include intermediate certificates up to an expected trusted root (that the receiver would have), such that the receiver can resolve the chain of certificates and trust the sender. How each e-mail client explicitly handles (and documents) this is where things start to break down and get more complicated. Another complicating factor to all of this occurs from a newer feature used in X.509 certificates called Authority Information (AIA). The purpose of AIA is to provide clients with a URL to download the issuing certificate of the one being inspected. So for instance, if AIA is functioning and all the receiving client has is the leaf cert it would: read the leaf cert, download the issuing cert (intermediate CA #1), confirm the leaf certificate is properly signed by the intermediate cert, download the issuing cert (intermediate CA #2) of intermediate CA #1, confirm intermediate CA #2 is properly signed by intermediate CA #1. It would continue this until getting to the root CA, and then check if the root CA is trusted by the client/receiver. Since AIA provides the client the ability to download the cert (if not disabled), the receiver does not have to have the intermediate certificates in the signed e-mail being received or in their local certificate store. However, not all e-mail clients support AIA.

It is also important to know that on Windows, if AIA is working you will see certificates populate in the Certificates - Current User\Intermediate Certification Authorities section/store in the certificate manager on Windows. AIA also kicks off when you simply view a certificate in the Windows certificate properties viewer (i.e. double clicking on a .crt file). So for instance, say you received a signed e-mail with no intermediate certificates attached. If you [open this e-mail in Outlook (Classic) -> Click the warning symbol -> Click Details -> Click View Details -> Click View Certificate], this will open the certificate in the Windows certificate properties viewer, automatically run the AIA process, and download and install the intermediate certificates, adding them to the local Current User\Intermediate Certification Authorities store. The simple act of viewing the certificate's properties in Windows causes this process to run - whether you click OK or just close the certificate properties has no impact. Since the local store now has the intermediate certificate, backing out will cause Outlook (Classic) to now show the signature as valid, even though the intermediate certificate is missing from the signed e-mail.

https://learn.microsoft.com/en-us/windows-server/security/authority-information-access-retrieval?tabs=gp 

There are two issues at play here. One is how Outlook clients handle building and attaching certificates to signed e-mails being sent. The other is how Outlook clients handle resolving whether a received signed e-mail is trusted or not.

Findings

Determine Certificates Attached to a Signed E-mail

To confirm the certificates being sent by a user when they sign emails, the following can be done.

• Have the user send you a signed e-mail
• In the modern Outlook client, right click the e-mail and select Save as --> Save as EML
• Get the saved .eml file to a system with openssl (this can be Ubuntu or a Windows compiled version of OpenSSL)
• Run the following command (exact command may vary for Windows)

openssl smime -pk7out -in myemail.eml | openssl pkcs7 -print_certs -noout

Outlook Behavior for Attaching Certificates

This is the behavior I tested in various Outlook clients for building the certificate chain for a signed e-mail and attaching necessary certificates to signed e-mails being sent.

• Outlook Web App (OWA)
  • The chain is resolved using certificates uploaded to the SMIMECertificateIssuingCA SMIME setting on Exchange Online.
  • Either the OWAIncludeCertificateChainWithoutRootCertificate or OWAIncludeCertificateChainAndRootCertificate S/MIME setting on Exchange Online must also be set to True.
  • See section below on "How to Update S/MIME Settings on Exchange Online".
• Windows
  • Outlook (Modern)
    • Works the same as OWA. S/MIME settings with the intermediate certificates (and roots if you want them attached, but is not necessary) must be set on Exchange Online.
  • Outlook (Classic)
    • Uses the local Microsoft certificate store to build the chain. As long as the certificates exist somewhere on the local Microsoft cert stores that the user can access, Outlook will resolve the chain and include both the root and intermediate certificates in a signed e-mail.
• Mac
  • Outlook for Mac
    • The user must open their "login" Keychain and use File->Import to import a single .p12 file that includes their private key, public key, intermediate certificates, and root certificates. If they import the certificate in this way, Outlook will build/resolve the chain and include both the root and intermediate certificates in a signed e-mail.

Outlook Behavior for Resolving Certificates

• Outlook Web App (OWA)
  • I am not sure on this one, but it appears to use the local certificate store to resolve the chain, and will use AIA to download missing intermediates.
• Windows
  • Outlook (Modern)
    • Uses the local Windows certificate store and AIA to resolve the chain.
  • Outlook (Classic)
    • Uses the local Windows certificate store to resolve the chain.
    • This does NOT use AIA.
• Mac
  • Outlook for Mac
    • Uses the local Mac keychain certificate store.
    • I do not know if this uses AIA or not.

Properly Setting up Exchange Online to Attach Intermediate Certificates

If you are using Exchange Online (Microsoft cloud-hosted e-mail), OWA and modern Windows Outlook clients use properties and certificate stores setup on the backend. This is possibly true for other self-hosted versions of Exchange as well, but my environment was Exchange Online.

Updating S/MIME settings for Exchange Online is done through PowerShell commands. Once the attributes are updated it can take thirty minutes to an hour for the changes to take effect. It seems like the expectation is that organizations are responsible for maintaining and updating these S/MIME settings. I don't know why Microsoft doesn't just maintain a collection of certificates for trusted Root CAs like they do for their operating systems, and use AIA to download/cache necessary intermediate certificates, or at least give administrators more options to control this - have Microsoft managed certs as an option, and make that the default.

There are two settings that must be updated here for Outlook to properly attach certificates to signed-emails.

1. SMIMECertificateIssuingCA

   1. This is a certificate store kept on the back end. It should include all intermediate certificates that would need to be attached to e-mails being signed by users using your Exchange Online service. It will not allow you to upload more than 70 KB of data or any expired certificates.
   2. WARNING: this is an all or nothing change. When you update this value it will destroy whatever the previous value of this setting was. In other words, you will lose any set of certificates Exchange Online was previously configured to use for S/MIME. I never found any clear documentation on everything this certificate store is used for, but it seems like it may just be for building chains and attaching certificates to signed or encrypted e-mails you are sending.

2. OWAIncludeCertificateChainWithoutRootCertificate

   1. This must be set to True for Exchange Online to attach certificates to signed e-mails you are sending.

https://learn.microsoft.com/en-us/powershell/module/exchangepowershell/set-smimeconfig?view=exchange-ps#-smimecertificateissuingca

https://learn.microsoft.com/en-us/exchange/security-and-compliance/smime-exo/configure-smime-exo#step-2-set-up-a-virtual-certificate-collection-in-exchange-online 

https://learn.microsoft.com/en-us/exchange/policy-and-compliance/smime/smime?source=recommendations 

# Connect to Exchange Online

Connect-ExchangeOnline -UserPrincipalName email address removed for privacy reasons

# Get S/MIME Configuration on Exchange Online account

Get-SmimeConfig

# Store the S/MIME Configuration in a local variable to work with

$smime = Get-SmimeConfig

# The SMIMECertificateIssuingCA attribute on this object is an array of bytes that make up a .sst file

# A .sst file is a collection of certificates.

# Save current SMIMECertificateIssuingCA value as a local .sst file

$smime = Get-SmimeConfig

[System.IO.File]::WriteAllBytes("C:\temp\current.sst", [byte[]]$smime.SMIMECertificateIssuingCA)

# Alternative method to save current SMIMECertificateIssuingCA value as a local .sst file

$bytes = [byte[]]($cfg.SMIMECertificateIssuingCA | ForEach-Object {[byte]$_})

[System.IO.File]::WriteAllBytes("C:\temp\current.sst", $bytes)

# Load local .sst file into a PowerShell object to review contents of file

$col = New-Object System.Security.Cryptography.X509Certificates.X509Certificate2Collection

$col.Import("C:\temp\current.sst")

# Get count of certificates in .sst

$col.Count

# Display all certificates in .sst

$col | Select-Object Subject, Issuer, NotAfter, Thumbprint | Format-Table -AutoSize

# Display all expired certificates in .sst

$col | Where-Object {$_.NotAfter -lt (Get-Date)} | Select-Object Subject, NotAfter

# Display certificates that partially match a string in the Subject in .sst

$col | Where-Object {$_.Subject -like "*Sectigo*"} | Select-Object Subject

# Add certificates from multiple sources to a new collection and save to a new .sst file

$new = New-Object System.Security.Cryptography.X509Certificates.X509Certificate2Collection

$new.AddRange($col)

$new.Import("C:\temp\R36.crt")

$new.Import("C:\temp\R46.crt")

[System.IO.File]::WriteAllBytes("C:\temp\merged.sst", $new.Export([System.Security.Cryptography.X509Certificates.X509ContentType]::SerializedStore))

# You can also export a .sst file from the mmc.exe Certificates snapin.

# Browse to the Trusted Root Certificate Authorities\Certificates folder, select desired certificates, right click, All Tasks, Export.

# Click Next, and select "Microsoft Serialized Certificate Store (.SST).

# Set SMIMECertificateIssuingCA value to a new .sst file

Set-SmimeConfig -SMIMECertificateIssuingCA ([System.IO.File]::ReadAllBytes('C:\temp\exchange_online_issue_CAs.sst'))

# Set OWAIncludeCertificateChainWithoutRootCertificate to True

Set-SmimeConfig -OWAIncludeCertificateChainWithoutRootCertificate $true