1. Zone transfer
Some nameservers allow for DNS zone transfers to anyone on the internet, usually unintentionally. In this question, it is explained further: DNS zone transfer attack.
Tools for zone transfers
The second answer on that question mentions how to test for it for both Windows and Linux:
Windows:
nslookup
> server <DNS you are querying>
> set type=any
> ls -d <target>
Unix (nslookup is deprecated on Unix):
dig -t axfr @<DNS you are querying> <target>
(I edited the Unix one, because -axfr does not appear to work. I needed to specify -t axfr.)
2. DNSSEC zone walk
DNSSEC signs DNS records, so you can be sure you receive the correct answer (well, given some trust roots and intermediaries). But how do you prove that something does not exist, e.g. when looking for nonexistentsub.example.com, how does the nameserver of example.com prove nonexistence of a subdomain? It doesn't have the signing key on it (signing is done upon updating the zone by administrators).
In their answer to How does DNSSec work? Are there known limitations or issues?, /u/tylerl explains:
Obviously that response needs to be signed, but generally the DNS server itself doesn't have access to your signing key and can't sign the response on-the-fly; the signatures are all created "offline" ahead of time. This keeps your key from being exposed if your DNS server gets compromised.
So instead, you alphabetize your subdomains and say "for every name between mail.example.com and pop.example.com, no other subdomains exist" and sign that assertion. Then when someone asks for nachos.example.com you can just give them that response (which has already been signed) and the client knows that because nachos.example.com falls alphabetically between mail.example.com and pop.example.com, then the "this domain doesn't exist" response is considered to be correctly signed and actually came from you.
The place where this becomes problematic is that by having a set of these negative responses which explicitly state that "no responses exist between X and Y, you can easily map out exactly which domains exist for the entire zone. You know that "X" exists, and you know that "Y" exists, and you know there is nothing else between them. Just do a little more poking at random and you'll quickly be able to compile a list of all the records that do exist.
The record that specifies "until pop.example.com there is nothing" is called NSEC (Next SECure record).
A workaround was designed for this: NSEC3. It hashes names, so mail turns into b83a88... and pop turns into b21afc.... Imagine those are the two only subdomains, then the signed response will say "no record exists between b21afc... and b83a88...". Again it works alphabetically and you can obtain them all, but this time you will need to crack each hash before you learn what the subdomains are.
In my experience, most have the NSEC3 extension enabled.
Tools for zone walking
NSEC3Walker does both the enumeration and the cracking. I cannot vouch for how efficient the cracking is, but it's definitely only CPU-based. Since NSEC3 uses SHA1 (at least originally), there are probably better cracking programs.
dnsrecon also appears to be able to do it: dnsrecon -z -d example.com. I don't know if there is an official website with information, but in Debian Stretch, Buster, and Bullseye I can apt install dnsrecon.
3. Reverse lookups in a subnet
By guessing a few, you will often find responses in a similar range. If you know www. exists and mail. exists, and they both resolve to 192.168.3.x, there might be more. Try to do a reverse lookup for all addresses in the 192.168.3.0-255 range (the /24), and you will probably find more subdomains. You may also want to try a WHOIS query on the IP address to find the range's boundaries (if they have their own block).
Tools for reverse lookups
dnsrecon can do this:
dnsrecon -t rvl -r 192.168.1.0/24
Where -t rvl means "type reverse-lookup" and -r passes an IP range in CIDR notation. I don't know if there is an official website with information, but in Debian Stretch, Buster, and Bullseye I can apt install dnsrecon.
4. DNS service records
One can set SRV (service) records for service discovery, for example _sip._tcp.example.com could point to sipserver.example.com on port 5060. Since the service names ("sip" in the example) are typically the standard ones registered with IANA, we can iterate through them.
Tools for querying srv records
dnsrecon can do this:
dnsrecon -t srv -d example.com
It will take a subset of the existing service names, selected by an unknown method, as mentioned in its man page (man dnsrecon).
5. Other methods
You already mentioned some of those. I won't go into detail, because they're quite self-explanatory, and either depend on an application running on the target (such as FTP), depend on a third party, or there is really just not much to say about them.
Certificate transparency logs may show for which subdomains certificates were obtained, e.g. see https://crt.sh.
Search results might reveal subdomains. Again, dnsrecon can do this with the -t goo option (uses Google specifically).
Checking other TLDs for the same name might reveal some other variants or IP addresses. E.g. if example.com exists, example.org might exist as well. dnsrecon can also do this with dnsrecon -t tld -d example.com.
Crawling a website or finding references elsewhere might give hints. (Help wanted: which tool to use?)
Looking at TLS certificates often yields results. Be sure to check the ports for HTTPS, SMTP(S), FTP(S), etc. and use STARTTLS.
There are third party tools which can list subdomains in a domain. Their methods are less clear, but crawling the internet and historical records (maybe a domain transfer was once possible?) are often part of it. (Help wanted: any recommendations? I only remember seeing that it exists.)
6. Guessing.
The last option is just guessing, either by a dictionary (I'd recommend that) or brute force. This is made harder by wildcards, though many tools will try to detect and solve this.
Tools for guessing/brute-forcing
Fierce was built to do this: https://github.com/mschwager/fierce
It is installed by default in Kali Linux.
As /u/rook mentioned in another answer in this thread, they wrote Subbrute for this purpose: https://github.com/TheRook/subbrute
dnsrecon can do this with dnsrecon -t brt -d example.com. Use -f to "Filter out of Brute Force Domain lookup records that resolve to the wildcard defined IP Address when saving records" (citing its man page). You can pass -D for a dictionary file.
Appendix: dictionaries
I am still looking for good dictionaries (for guessing/brute forcing), but here are some that I'm aware of. Please help me complete this list! The bigger the better, as long as they are sorted by likelihood.
