Let's Encrypt and DNS over TLS Hell on Android

I run a DNS over TLS server with Adguard Home to enable DNS-level ad-blocking on the go on my Android device via the Private DNS setting. I've had a peaceful 3 years of running the DNS server with zero issues, browsing the internet without fear of being spammed by disruptive ads. This is especially important for me as I have ADHD, and ads are a major source of distraction.

Goodbye halcyon days

However, that changed recently when it just stopped working and all it showed me was Couldn't connect in my Android device when I entered my DNS server's hostname in the Private DNS provider hostname field. This coincided with the time I decided to wipe my cluster clean and start over, so I figured that it was probably a misconfiguration on my part.

Fast forward to yesterday, 30 days later, I still haven't managed to find out why my DNS over TLS is not working. All this time, I've had many sleepless nights pondering why it didn't work as I'm the kind of person that cannot rest without getting to the root cause of a problem.

Today, I decided to it give it another go to deep dive into the problem and it was then that I finally found the issue; the expired Root Certificate.

Some backstory

Before we dive into the depths of DNS-over-TLS hell, to help us understand the problem better, let us run through a little background on TLS Certificates, trust chains and what happened so far in the past 6 years since the advent of Let's Encrypt.

Note: I do not claim to be an expert in TLS, and am only sharing the limited knowledge I have on the topic so if you're truly interested, do read up on your own accord.

What is TLS?

Transport Layer Security (abbreviated as TLS) is a protocol designed to provide cryptographic security for communications over a computer network, be it between machines in your local home network, or between your computer and a server on the internet.

Without delving into the specifics of how TLS works and at the risk of oversimplification, TLS can be summed up as a protocol that ensures confidentiality and integrity of data transmitted between 2 machines, the server, and the client, through the use of asymmetric ciphers (Public and Private keys) and other cryptographic algorithms (symmetric ciphers and message digests).

In plain english:

TLS ensures that data transmitted between the server and the client reaches the destination without unauthorized modification (integrity) and that no one other than the intended recipient can read it (confidentiality)

TLS also provides identification of the server (more accurately, the public key of the server) through the use of TLS Certificates which are issued to servers by trusted providers that hold Certificate Authority (abbreviated as CA) Certificates. The possession and subsequent presentation of the TLS Certificate on initial communication uniquely identifies the server as the intended party (and not some other malicious server) when a domain name is accessed.

Just as domain names come and go, TLS Certificates have a limited validity period, after which they must be renewed. This is to ensure that the certificates conform to latest security standards and that the domain is still controlled by the owner of the server.

TLS Certificate Trust Chain

A TLS Certificate is trusted on the basis that it is issued by a trusted provider. During issuance, a new TLS Certificate is created and signed by the trusted provider's CA Certificate. A CA Certificate is in turn trusted because it is signed by a Root Certificate. This establishes the chain of trust of a TLS Certificate.

There are only a handful of Root Certificates in the world (around 200), and companies holding Root Certificates undergo a lot of scrutiny to ensure that they are trustworthy and remain so over time. This is because Root Certificates are very powerful, so much that the entire foundation of the security offered by TLS Certificate relies on their proper use.

Because Root Certificates are so powerful, they are permanently stored offline in a secure physical location, disconnected from the Internet. Throughout the lifetime of a Root Certificate, it is only used a handful of times, mostly (if not always) to sign CA Certificates (intermediate certificates). These intermediate certificates are subsequently used to sign TLS Certificates for issuance.

Establishing trust

To establish trust, a device must at least have a copy of all CA certificates currently active in the internet, stored in the device itself. This entails that all devices across the world (including the one you're using to read this) already has a copy of all CA certificates, the only difference between each device is how outdated the list is.

Just as all TLS certificates expire, CA Certificates also have a validity period albeit longer than typical certificates. This list must then be updated regularly on all devices through OS updates alike to ensure that new CA Certificates are added. Expiry dates are stored in the certificate itself so old CA Certificates need not be removed as they are considered invalid past expiry.

Unreachability of TLS Certificates

TLS Certificates, as good as they sound, have traditionally been out of reach by the masses due to its exorbitant cost. A basic (Domain Validated) TLS Certificate typically costs around US$100 per year in the past. Though that has come down to around US$50 per year in recent times, it is still pretty pricey for use cases such as self-hosted blogs like mine.

Other tiers of TLS Certificates (Organization Validated and Extended Validation) cost more (upwards of US$200 per year) but are unnecessary for typical use and are more applicable for large organizations.

The situation changed when Let's Encrypt entered the game.

What is Let's Encrypt?

Let's Encrypt is a non-profit CA run by the Internet Security Research Group (ISRG) with the aim of securing all websites across the world by offering TLS Certificates free-of-charge. They currently are the largest Certificate Authority in the world with over 2 billion certificates issued and used by over 265 million websites.

ISRG Root X1 and IdenTrust DST Root CA X3

In 2015, Let's Encrypt began operations and started issuing TLS Certificates for free. I was among the early adopters of Let's Encrypt and witnessed its meteoric rise to prominence.

To enable issuance of TLS Certificates, Let's Encrypt created a Root Certificate, ISRG Root X1. Subsequently, they created 4 intermediate CA Certificates Let's Encrypt Authorities X1 thru X4, signed by their Root Certificate.

Because ISRG Root X1 is a Root Certificate that was only created on Jun 4, 2015, all new TLS Certificates, if issued as is at that point in time, will not be recognized by devices that received their final updates to their CA Certificates before Jun 4, 2015. To mitigate this, Let's Encrypt partnered with IdenTrust to cross-sign their 4 intermediate CA Certificates with their Root Certificate, DST Root CA X3.

As the DST Root CA X3 is created on Sep 30, 2000, Let's Encrypt-issued TLS Certificates can be verified by devices last updated in year 2000, enabling these devices to access servers and websites using the newly-issued Let's Encrypt TLS Certificates.

DST Root CA X3 Expiration

The DST Root CA X3 Root Certificate expired on Sep 30 14:01:15 2021 GMT according to certificate transparency logs provided by crt.sh linked above. This means that all certificates cross-signed by DST Root CA X3 will be invalidated, regardless of whether their expiration date has lapsed.

Unfortunately, the expiration of the Root Certificate also means that devices with outdated versions of the CA Certificates will no longer be able to access websites that use Let's Encrypt TLS Certificates without special configuration that allows trust beyond certificate expiry.

The solution for older Android devices

Let's Encrypt devised a trust chain that allows old Android devices to validate Let's Encrypt TLS Certificates past the expiration of the DST Root CA X3 Root Certificate, with the use of a special cross-sign by IdenTrust's DST Root CA X3. This special cross-sign lasts 3 years, allowing the aforementioned Android devices to continue accessing sites secured by Let's Encrypt TLS Certificates up till 2024.

Putting the plan into action, certificates issued by Let's Encrypt after May 4, 2021 utilized the special cross-sign (in green). Alternatively, with some additional configuration, certificate requestors may request for the alternate chain which uses the ISRG Root X1 as the final certificate (in blue).

Back to the problem at hand

TLS Certificates for my personal domain are issued by Let's Encrypt and I have been relying on the default configuration since time immemorial, after all, as the saying goes:

Don't fix what's not broken

On the evening of Sep 30, 2021, after ensuring that backups are in place, I deleted my entire Kubernetes cluster to start afresh due to performance issues of late.

Notice that the date I decided to refresh my cluster coincides with the expiry date of DST Root CA X3 Root Certificate. The expiry event probably happened a few hours after the cluster was refreshed.

After installing Adguard Home, I realized that all my Android devices can no longer connect to my Private DNS server, as I've already explained.

Debugging DNS over TLS

Debugging DNS over TLS can be a huge pain. After 30 minutes of searching, I found a staggering grand total of 1 tool that can make a proper DNS over TLS query. That tool is kdig by knot.

On MacOS, kdig can be installed with:

$ brew install knot-resolver

On Linux, kdig can be installed with:

$ apt install knot-dnsutils

With kdig, I made a DNS query to my DNS over TLS server, the output shown below has been redacted with my DNS server's domain replaced with mydnsserver.tld.

$ kdig -d @mydnsserver.tld +tls-ca google.com
;; DEBUG: Querying for owner(google.com.), class(1), type(1), server(mydnsserver.tld), port(853), protocol(TCP)
;; DEBUG: TLS, imported 193 system certificates
;; DEBUG: TLS, received certificate hierarchy:
;; DEBUG:  #1, CN=mydnsserver.tld
;; DEBUG:      SHA-256 PIN: <REDACTED>
;; DEBUG:  #2, C=US,O=Let's Encrypt,CN=R3
;; DEBUG:      SHA-256 PIN: jQJTbIh0grw0/1TkHSumWb+Fs0Ggogr621gT3PvPKG0=
;; DEBUG: TLS, skipping certificate PIN check
;; DEBUG: TLS, The certificate is trusted.
;; TLS session (TLS1.3)-(ECDHE-X25519)-(RSA-PSS-RSAE-SHA256)-(AES-256-GCM)
;; ->>HEADER<<- opcode: QUERY; status: NOERROR; id: 37943
;; Flags: qr rd ra; QUERY: 1; ANSWER: 6; AUTHORITY: 0; ADDITIONAL: 1

;; EDNS PSEUDOSECTION:
;; Version: 0; flags: ; UDP size: 4096 B; ext-rcode: NOERROR

;; QUESTION SECTION:
;; google.com.         		IN	A

;; ANSWER SECTION:
google.com.         	298	IN	A	142.251.12.102
google.com.         	298	IN	A	142.251.12.113
google.com.         	298	IN	A	142.251.12.138
google.com.         	298	IN	A	142.251.12.100
google.com.         	298	IN	A	142.251.12.101
google.com.         	298	IN	A	142.251.12.139

;; Received 135 B
;; Time 2021-10-31 03:01:20 +08
;; From my.dns.ip.address@853(TCP) in 17.9 ms

To ensure that the query was indeed made with DNS over TLS, I verified that the port used was indeed 853.

The output showed a successful DNS query for google.com and I was even more confused as to why my Android device errored out with a very informative Couldn't connect message when I tried setting it as my Private DNS server.

Checking the TLS Certificates

The next logical step was to check the TLS Certificates. This can be done with a widely available tool known as openssl.

On MacOS, openssl can be installed with:

$ brew install openssl

On Linux, openssl can be installed with:

$ apt install openssl

To retrieve TLS Certificate information, I ran the following command:

$ openssl s_client -showcerts -servername mydnsserver.tld -connect mydnsserver.tld:853
CONNECTED(00000005)
depth=2 C = US, O = Internet Security Research Group, CN = ISRG Root X1
verify return:1
depth=1 C = US, O = Let's Encrypt, CN = R3
verify return:1
depth=0 CN = mydnsserver.tld
verify return:1
---
Certificate chain
 0 s:CN = mydnsserver.tld
   i:C = US, O = Let's Encrypt, CN = R3
-----BEGIN CERTIFICATE-----
<REDACTED>
-----END CERTIFICATE-----
 1 s:C = US, O = Let's Encrypt, CN = R3
   i:C = US, O = Internet Security Research Group, CN = ISRG Root X1
-----BEGIN CERTIFICATE-----
MIIFFjCCAv6gAwIBAgIRAJErCErPDBinU/bWLiWnX1owDQYJKoZIhvcNAQELBQAw
TzELMAkGA1UEBhMCVVMxKTAnBgNVBAoTIEludGVybmV0IFNlY3VyaXR5IFJlc2Vh
cmNoIEdyb3VwMRUwEwYDVQQDEwxJU1JHIFJvb3QgWDEwHhcNMjAwOTA0MDAwMDAw
WhcNMjUwOTE1MTYwMDAwWjAyMQswCQYDVQQGEwJVUzEWMBQGA1UEChMNTGV0J3Mg
RW5jcnlwdDELMAkGA1UEAxMCUjMwggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAwggEK
AoIBAQC7AhUozPaglNMPEuyNVZLD+ILxmaZ6QoinXSaqtSu5xUyxr45r+XXIo9cP
R5QUVTVXjJ6oojkZ9YI8QqlObvU7wy7bjcCwXPNZOOftz2nwWgsbvsCUJCWH+jdx
sxPnHKzhm+/b5DtFUkWWqcFTzjTIUu61ru2P3mBw4qVUq7ZtDpelQDRrK9O8Zutm
NHz6a4uPVymZ+DAXXbpyb/uBxa3Shlg9F8fnCbvxK/eG3MHacV3URuPMrSXBiLxg
Z3Vms/EY96Jc5lP/Ooi2R6X/ExjqmAl3P51T+c8B5fWmcBcUr2Ok/5mzk53cU6cG
/kiFHaFpriV1uxPMUgP17VGhi9sVAgMBAAGjggEIMIIBBDAOBgNVHQ8BAf8EBAMC
AYYwHQYDVR0lBBYwFAYIKwYBBQUHAwIGCCsGAQUFBwMBMBIGA1UdEwEB/wQIMAYB
Af8CAQAwHQYDVR0OBBYEFBQusxe3WFbLrlAJQOYfr52LFMLGMB8GA1UdIwQYMBaA
FHm0WeZ7tuXkAXOACIjIGlj26ZtuMDIGCCsGAQUFBwEBBCYwJDAiBggrBgEFBQcw
AoYWaHR0cDovL3gxLmkubGVuY3Iub3JnLzAnBgNVHR8EIDAeMBygGqAYhhZodHRw
Oi8veDEuYy5sZW5jci5vcmcvMCIGA1UdIAQbMBkwCAYGZ4EMAQIBMA0GCysGAQQB
gt8TAQEBMA0GCSqGSIb3DQEBCwUAA4ICAQCFyk5HPqP3hUSFvNVneLKYY611TR6W
PTNlclQtgaDqw+34IL9fzLdwALduO/ZelN7kIJ+m74uyA+eitRY8kc607TkC53wl
ikfmZW4/RvTZ8M6UK+5UzhK8jCdLuMGYL6KvzXGRSgi3yLgjewQtCPkIVz6D2QQz
CkcheAmCJ8MqyJu5zlzyZMjAvnnAT45tRAxekrsu94sQ4egdRCnbWSDtY7kh+BIm
lJNXoB1lBMEKIq4QDUOXoRgffuDghje1WrG9ML+Hbisq/yFOGwXD9RiX8F6sw6W4
avAuvDszue5L3sz85K+EC4Y/wFVDNvZo4TYXao6Z0f+lQKc0t8DQYzk1OXVu8rp2
yJMC6alLbBfODALZvYH7n7do1AZls4I9d1P4jnkDrQoxB3UqQ9hVl3LEKQ73xF1O
yK5GhDDX8oVfGKF5u+decIsH4YaTw7mP3GFxJSqv3+0lUFJoi5Lc5da149p90Ids
hCExroL1+7mryIkXPeFM5TgO9r0rvZaBFOvV2z0gp35Z0+L4WPlbuEjN/lxPFin+
HlUjr8gRsI3qfJOQFy/9rKIJR0Y/8Omwt/8oTWgy1mdeHmmjk7j1nYsvC9JSQ6Zv
MldlTTKB3zhThV1+XWYp6rjd5JW1zbVWEkLNxE7GJThEUG3szgBVGP7pSWTUTsqX
nLRbwHOoq7hHwg==
-----END CERTIFICATE-----
 2 s:C = US, O = Internet Security Research Group, CN = ISRG Root X1
   i:O = Digital Signature Trust Co., CN = DST Root CA X3
-----BEGIN CERTIFICATE-----
MIIFYDCCBEigAwIBAgIQQAF3ITfU6UK47naqPGQKtzANBgkqhkiG9w0BAQsFADA/
MSQwIgYDVQQKExtEaWdpdGFsIFNpZ25hdHVyZSBUcnVzdCBDby4xFzAVBgNVBAMT
DkRTVCBSb290IENBIFgzMB4XDTIxMDEyMDE5MTQwM1oXDTI0MDkzMDE4MTQwM1ow
TzELMAkGA1UEBhMCVVMxKTAnBgNVBAoTIEludGVybmV0IFNlY3VyaXR5IFJlc2Vh
cmNoIEdyb3VwMRUwEwYDVQQDEwxJU1JHIFJvb3QgWDEwggIiMA0GCSqGSIb3DQEB
AQUAA4ICDwAwggIKAoICAQCt6CRz9BQ385ueK1coHIe+3LffOJCMbjzmV6B493XC
ov71am72AE8o295ohmxEk7axY/0UEmu/H9LqMZshftEzPLpI9d1537O4/xLxIZpL
wYqGcWlKZmZsj348cL+tKSIG8+TA5oCu4kuPt5l+lAOf00eXfJlII1PoOK5PCm+D
LtFJV4yAdLbaL9A4jXsDcCEbdfIwPPqPrt3aY6vrFk/CjhFLfs8L6P+1dy70sntK
4EwSJQxwjQMpoOFTJOwT2e4ZvxCzSow/iaNhUd6shweU9GNx7C7ib1uYgeGJXDR5
bHbvO5BieebbpJovJsXQEOEO3tkQjhb7t/eo98flAgeYjzYIlefiN5YNNnWe+w5y
sR2bvAP5SQXYgd0FtCrWQemsAXaVCg/Y39W9Eh81LygXbNKYwagJZHduRze6zqxZ
Xmidf3LWicUGQSk+WT7dJvUkyRGnWqNMQB9GoZm1pzpRboY7nn1ypxIFeFntPlF4
FQsDj43QLwWyPntKHEtzBRL8xurgUBN8Q5N0s8p0544fAQjQMNRbcTa0B7rBMDBc
SLeCO5imfWCKoqMpgsy6vYMEG6KDA0Gh1gXxG8K28Kh8hjtGqEgqiNx2mna/H2ql
PRmP6zjzZN7IKw0KKP/32+IVQtQi0Cdd4Xn+GOdwiK1O5tmLOsbdJ1Fu/7xk9TND
TwIDAQABo4IBRjCCAUIwDwYDVR0TAQH/BAUwAwEB/zAOBgNVHQ8BAf8EBAMCAQYw
SwYIKwYBBQUHAQEEPzA9MDsGCCsGAQUFBzAChi9odHRwOi8vYXBwcy5pZGVudHJ1
c3QuY29tL3Jvb3RzL2RzdHJvb3RjYXgzLnA3YzAfBgNVHSMEGDAWgBTEp7Gkeyxx
+tvhS5B1/8QVYIWJEDBUBgNVHSAETTBLMAgGBmeBDAECATA/BgsrBgEEAYLfEwEB
ATAwMC4GCCsGAQUFBwIBFiJodHRwOi8vY3BzLnJvb3QteDEubGV0c2VuY3J5cHQu
b3JnMDwGA1UdHwQ1MDMwMaAvoC2GK2h0dHA6Ly9jcmwuaWRlbnRydXN0LmNvbS9E
U1RST09UQ0FYM0NSTC5jcmwwHQYDVR0OBBYEFHm0WeZ7tuXkAXOACIjIGlj26Ztu
MA0GCSqGSIb3DQEBCwUAA4IBAQAKcwBslm7/DlLQrt2M51oGrS+o44+/yQoDFVDC
5WxCu2+b9LRPwkSICHXM6webFGJueN7sJ7o5XPWioW5WlHAQU7G75K/QosMrAdSW
9MUgNTP52GE24HGNtLi1qoJFlcDyqSMo59ahy2cI2qBDLKobkx/J3vWraV0T9VuG
WCLKTVXkcGdtwlfFRjlBz4pYg1htmf5X6DYO8A4jqv2Il9DjXA6USbW1FzXSLr9O
he8Y4IWS6wY7bCkjCWDcRQJMEhg76fsO3txE+FiYruq9RUWhiF1myv4Q6W+CyBFC
Dfvp7OOGAN6dEOM4+qR9sdjoSYKEBpsr6GtPAQw4dy753ec5
-----END CERTIFICATE-----
---
Server certificate
subject=CN = mydnsserver.tld

issuer=C = US, O = Let's Encrypt, CN = R3

---
No client certificate CA names sent
Peer signing digest: SHA256
Peer signature type: RSA-PSS
Server Temp Key: X25519, 253 bits
---
SSL handshake has read 4574 bytes and written 380 bytes
Verification: OK
---
New, TLSv1.3, Cipher is TLS_AES_128_GCM_SHA256
Server public key is 2048 bit
Secure Renegotiation IS NOT supported
Compression: NONE
Expansion: NONE
No ALPN negotiated
Early data was not sent
Verify return code: 0 (ok)
---
---
Post-Handshake New Session Ticket arrived:
SSL-Session:
    Protocol  : TLSv1.3
    Cipher    : TLS_AES_128_GCM_SHA256
    Session-ID: 7D146CAA42D5DEDA4C4D4CC79255BE2EC19E560099D967B07A0789E963B86D0B
    Session-ID-ctx:
    Resumption PSK: 80E897CF4262502E2D3CF8C714547E18B87C1BEE3E6B4A96CE4F10ED243402F8
    PSK identity: None
    PSK identity hint: None
    SRP username: None
    TLS session ticket lifetime hint: 604800 (seconds)
    TLS session ticket:
    0000 - 01 49 70 89 17 f7 98 21-ac 8b 2b 96 56 b2 03 f7   .Ip....!..+.V...
    0010 - ef de 90 e9 09 6d 1b c1-e1 b6 09 4e 1e 00 de 67   .....m.....N...g
    0020 - 3b bc 25 61 d9 18 e8 bf-c1 8a b9 cf 71 e5 2b a2   ;.%a........q.+.
    0030 - c0 39 b0 c0 f6 bc 82 f8-17 49 62 99 14 4e 2e f7   .9.......Ib..N..
    0040 - 61 93 20 84 01 72 87 24-41 14 b1 a3 92 2d c1 f9   a. ..r.$A....-..
    0050 - 03 14 5b 6b f0 b4 2f 54-33 d8 e7 21 19 82 62 52   ..[k../T3..!..bR
    0060 - 5b e0 2e 63 21 2d 96 20-1f dd 4c ec 66 a1 5a f8   [..c!-. ..L.f.Z.
    0070 - 51                                                Q

    Start Time: 1635621153
    Timeout   : 7200 (sec)
    Verify return code: 0 (ok)
    Extended master secret: no
    Max Early Data: 0
---
read R BLOCK

What caught my attention was this line:

   i:O = Digital Signature Trust Co., CN = DST Root CA X3

It seems that DST Root CA X3 is still in the trust chain but it is not shown in the DNS over TLS query for some reason. Since I'm aware that this certificate has already expired, I had a feeling that this might have been the issue

The solution

Turns out, after a quick search, that this issue is prevalent among users of Adguard Home running DNS over TLS, with Let's Encrypt certificates requested using the default settings.

The solution was to request certificates that use the "ISRG Root X1" trust chain (shown in blue above) that does not contain the expired DST Root CA X3 certificate.

If you use certbot to renew your Let's Encrypt TLS Certificates, adding the parameter --preferred-chain="ISRG Root X1" should fix the issue.

In my case, I use cert-manager (if you're keen on using it as well, check out my other post) so I created a new ClusterIssuer resource for this alternate trust chain (with secret fields removed):

apiVersion: cert-manager.io/v1
kind: ClusterIssuer
metadata:
  name: letsencrypt-x1
spec:
  acme:
    server: https://acme-v02.api.letsencrypt.org/directory
    preferredChain: ISRG Root X1

I then switched my Certificate issuer field to this newly-created issuer (again, with secret fields removed):

apiVersion: cert-manager.io/v1
kind: Certificate
metadata:
  name: mydnsserver-tld
  namespace: network
spec:
  secretName: tls-cert-mydnsserver-tld
  dnsNames:
  - mydnsserver.tld
  issuerRef:
    name: letsencrypt-x1
    kind: ClusterIssuer
    group: cert-manager.io

After deploying the changes waiting for a couple of minutes, the new certificate was issued.

Verifying the trust chain

I verified that DST Root CA X3 is no longer in the trust chain by running the openssl command again.

$ openssl s_client -showcerts -servername mydnsserver.tld -connect mydnsserver.tld:853
CONNECTED(00000005)
depth=2 C = US, O = Internet Security Research Group, CN = ISRG Root X1
verify return:1
depth=1 C = US, O = Let's Encrypt, CN = R3
verify return:1
depth=0 CN = mydnsserver.tld
verify return:1
---
Certificate chain
 0 s:CN = mydnsserver.tld
   i:C = US, O = Let's Encrypt, CN = R3
-----BEGIN CERTIFICATE-----
<REDACTED>
-----END CERTIFICATE-----
 1 s:C = US, O = Let's Encrypt, CN = R3
   i:C = US, O = Internet Security Research Group, CN = ISRG Root X1
-----BEGIN CERTIFICATE-----
MIIFFjCCAv6gAwIBAgIRAJErCErPDBinU/bWLiWnX1owDQYJKoZIhvcNAQELBQAw
TzELMAkGA1UEBhMCVVMxKTAnBgNVBAoTIEludGVybmV0IFNlY3VyaXR5IFJlc2Vh
cmNoIEdyb3VwMRUwEwYDVQQDEwxJU1JHIFJvb3QgWDEwHhcNMjAwOTA0MDAwMDAw
WhcNMjUwOTE1MTYwMDAwWjAyMQswCQYDVQQGEwJVUzEWMBQGA1UEChMNTGV0J3Mg
RW5jcnlwdDELMAkGA1UEAxMCUjMwggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAwggEK
AoIBAQC7AhUozPaglNMPEuyNVZLD+ILxmaZ6QoinXSaqtSu5xUyxr45r+XXIo9cP
R5QUVTVXjJ6oojkZ9YI8QqlObvU7wy7bjcCwXPNZOOftz2nwWgsbvsCUJCWH+jdx
sxPnHKzhm+/b5DtFUkWWqcFTzjTIUu61ru2P3mBw4qVUq7ZtDpelQDRrK9O8Zutm
NHz6a4uPVymZ+DAXXbpyb/uBxa3Shlg9F8fnCbvxK/eG3MHacV3URuPMrSXBiLxg
Z3Vms/EY96Jc5lP/Ooi2R6X/ExjqmAl3P51T+c8B5fWmcBcUr2Ok/5mzk53cU6cG
/kiFHaFpriV1uxPMUgP17VGhi9sVAgMBAAGjggEIMIIBBDAOBgNVHQ8BAf8EBAMC
AYYwHQYDVR0lBBYwFAYIKwYBBQUHAwIGCCsGAQUFBwMBMBIGA1UdEwEB/wQIMAYB
Af8CAQAwHQYDVR0OBBYEFBQusxe3WFbLrlAJQOYfr52LFMLGMB8GA1UdIwQYMBaA
FHm0WeZ7tuXkAXOACIjIGlj26ZtuMDIGCCsGAQUFBwEBBCYwJDAiBggrBgEFBQcw
AoYWaHR0cDovL3gxLmkubGVuY3Iub3JnLzAnBgNVHR8EIDAeMBygGqAYhhZodHRw
Oi8veDEuYy5sZW5jci5vcmcvMCIGA1UdIAQbMBkwCAYGZ4EMAQIBMA0GCysGAQQB
gt8TAQEBMA0GCSqGSIb3DQEBCwUAA4ICAQCFyk5HPqP3hUSFvNVneLKYY611TR6W
PTNlclQtgaDqw+34IL9fzLdwALduO/ZelN7kIJ+m74uyA+eitRY8kc607TkC53wl
ikfmZW4/RvTZ8M6UK+5UzhK8jCdLuMGYL6KvzXGRSgi3yLgjewQtCPkIVz6D2QQz
CkcheAmCJ8MqyJu5zlzyZMjAvnnAT45tRAxekrsu94sQ4egdRCnbWSDtY7kh+BIm
lJNXoB1lBMEKIq4QDUOXoRgffuDghje1WrG9ML+Hbisq/yFOGwXD9RiX8F6sw6W4
avAuvDszue5L3sz85K+EC4Y/wFVDNvZo4TYXao6Z0f+lQKc0t8DQYzk1OXVu8rp2
yJMC6alLbBfODALZvYH7n7do1AZls4I9d1P4jnkDrQoxB3UqQ9hVl3LEKQ73xF1O
yK5GhDDX8oVfGKF5u+decIsH4YaTw7mP3GFxJSqv3+0lUFJoi5Lc5da149p90Ids
hCExroL1+7mryIkXPeFM5TgO9r0rvZaBFOvV2z0gp35Z0+L4WPlbuEjN/lxPFin+
HlUjr8gRsI3qfJOQFy/9rKIJR0Y/8Omwt/8oTWgy1mdeHmmjk7j1nYsvC9JSQ6Zv
MldlTTKB3zhThV1+XWYp6rjd5JW1zbVWEkLNxE7GJThEUG3szgBVGP7pSWTUTsqX
nLRbwHOoq7hHwg==
-----END CERTIFICATE-----
---
Server certificate
subject=CN = mydnsserver.tld

issuer=C = US, O = Let's Encrypt, CN = R3

---
No client certificate CA names sent
Peer signing digest: SHA256
Peer signature type: RSA-PSS
Server Temp Key: X25519, 253 bits
---
SSL handshake has read 3235 bytes and written 400 bytes
Verification: OK
---
New, TLSv1.3, Cipher is TLS_AES_256_GCM_SHA384
Server public key is 2048 bit
Secure Renegotiation IS NOT supported
Compression: NONE
Expansion: NONE
No ALPN negotiated
Early data was not sent
Verify return code: 0 (ok)
---
---
Post-Handshake New Session Ticket arrived:
SSL-Session:
    Protocol  : TLSv1.3
    Cipher    : TLS_AES_256_GCM_SHA384
    Session-ID: 37E86E98EE2D92D39A138FA635567C95C44857CCA8EA515E41C33B6B848432C7
    Session-ID-ctx:
    Resumption PSK: 4D778AA121A10AE3E62DDA0AA638637E1BAFFEEC73F4AFBFE0DFC67ED77A055B2BB582BA3C3CF16F95F113E72FFE66D3
    PSK identity: None
    PSK identity hint: None
    SRP username: None
    TLS session ticket lifetime hint: 604800 (seconds)
    TLS session ticket:
    0000 - 76 0f 9d 35 20 1c 21 8d-b1 76 d3 50 cd 5d 44 f9   v..5 .!..v.P.]D.
    0010 - c8 8c c5 8d 94 e5 10 d9-b4 17 8b 57 00 5a 47 70   ...........W.ZGp
    0020 - 97 bf cb e4 5d d9 76 88-1c 4e 57 4f f6 7c 89 d9   ....].v..NWO.|..
    0030 - 1a b2 5b 65 06 8c 06 74-cf 09 a5 f5 20 90 22 84   ..[e...t.... .".
    0040 - f0 4d 58 6b b2 64 e0 07-6a 44 8f 2d da 88 e5 dd   .MXk.d..jD.-....
    0050 - 97 75 17 1b 66 5f 85 7a-34 3d 49 a9 20 2e 0e 4a   .u..f_.z4=I. ..J
    0060 - 2e 62 c2 85 74 26 bc 71-76 b9 94 f1 59 07 7d f3   .b..t&.qv...Y.}.
    0070 - 63 ef 19 c6 0c 15 3c 21-e7 28 9e ba e8 f8 a7 47   c.....<!.(.....G
    0080 - 00                                                .

    Start Time: 1635623367
    Timeout   : 7200 (sec)
    Verify return code: 0 (ok)
    Extended master secret: no
    Max Early Data: 0
---
read R BLOCK

Indeed DST Root CA X3 is nowhere to be found in the output of the command, confirming that the new TLS Certificate is now using the newly configured trust chain.

Upon setting the Private DNS setting to my personal DNS Server, my phones were finally able to connect successfully without a hitch.

What I think the problem is

Strangely, at the time of writing, information across the Internet touching on this problem provide only the solution but not the root cause.

In the process of debugging this issue, my findings are as follows:

1. Websites seem to work fine with the default trust chain
2. DNS over TLS clients such as kdig seem to work fine with the default trust chain
3. DNS over TLS on Android breaks with the default trust chain
4. DNS over TLS on Android only works with the trust chain that consists of only valid certificates
5. Let's Encrypt was confident enough to set the trust chain with DST Root CA X3 as default

Based on those findings, I'm guessing that the issue lies not with Let's Encrypt's default trust chain (since some 265 million websites are at stake) but with Android's DNS over TLS implementation where it somehow validates all the certificates up the trust chain.

D=0 DNS server certificate 
D=1 Let's Encrypt R3 
D=2 ISRG Root X1 
D=3 DST Root CA X3 <-- Expired

Typically, the trust chain validation should stop on encountering the first valid Root Certificate, but in this case the expired DST Root CA X3 Root Certificate which is one step deeper than the ISRG Root X1 Root Certificate in the chain, likely raised a fatal error when establishing a connection with a DNS over TLS server. As a result, the phone fails to connect to the DNS over TLS server.

Closing thoughts

Self-hosting is a mixed bag of fun and pain and this is a prime example of the pains that a self-hoster deals with.

Nonetheless, the joy is worth the pain, at least for me, and the solving of this problem is yet another victory in my self-hosting journey, against the never-ending torrent of challenges from running servers at home.

To my self-hosting friends out there, keep up the good fight!