Are they brute forcing them, or are they relying on the fact that most users of wildcard certs also have wildcard DNS entries, so it's just that everything is actually available. Wildcard DNS pointing to a web server with a wildcard cert will pass through to the web server, and at that point the web server responds with a 404 if the host header isn't one configured for virtual hosts.
thwarted|1 year ago