How to get DKIM to authenticate?

I've got sednamil, dkim-milter both running on RHEL4.

DNS and config files look like:

TXT record: mail._domainkey.MYDOMAIN.com IN TXT "v=DKIM1; g=*; k=rsa; t=y; p=....snip...TRM3w7CuYnQIDAQAB"

TXT record:

_adsp._domainkey.MYDOMAIN.com. IN TXT "dkim=unknown"

/etc/dkim.conf

Canonicalization simple
Domain MYDOMAIN.com,MY2ndDOMAIN.com
KeyFile /var/db/dkim/mail.key.pem
MTA MSA
Selector mail
Socket inet:8891@localhost
SignatureAlgorithm rsa-sha256
Syslog Yes
Userid dkim
X-Header Yes
Mode sv
InternalHosts /etc/dkim-internal-hosts

/etc/dkim-internal-hosts

MYDOMAIN.com
MY2ndDOMAIN.com
127.0.0.1

Now, when I send an email as a test, I don't see anything in the headers about DKIM being authenticated, although the key does appear:

X-DKIM: Sendmail DKIM Filter v2.8.3 MYDOMAIN.com o7FLH1Wa032083
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=MYDOMAIN.com; s=mail;
t=/XKdLCPjaYaY=;
h=Message-ID:Date:Subject:From:To:MIME-Version:Content-Type:
 Content-Transfer-Encoding;
b=qetPkilXBdjnuqiKIyvAwsvTvJfAnq5urdgp/i7p/uLJ8DB+svy9A8C6CPmcfELsJ
 hDid5k2AN5JD+wM2INmUIgjeAa/IwpGTbuMloj0Wioh4njqIfbATJqOhuqxTjic

If I type in:

# host -t txt mail._domainkey.MYDOMAIN.com

I get:

Host mail._domainkey.MYDOMAIN.com not found: 3(NXDOMAIN)

What could I be missing?

It looks like your DNS is setup incorrectly. You need to put in your public key that you generated when initially setting up DKIM. A sample DKIM record is as follows:

$ dig +short TXT dkim._domainkey.twitter.com
"v=DKIM1\;" "g=*\;" "k=rsa\;" "p=MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCrZ6zwKHLkoNpHNyPGwGd8wZoNZOk5buOf8wJwfkSZsNllZs4jTNFQLy" "6v4Ok9qd46NdeRZWnTAY+lmAAV1nfH6ulBjiRHsdymijqKy/VMZ9Njjdy/+FPnJSm3+tG9Id7zgLxacA1Yis/18V3TCfvJrHAR/a77Dxd65c96UvqP3QIDAQAB"

Everything after the p= is the public key. Just paste it all on one line. The value that comes before the _domainkey is called your selector. In the twitter example above, their selector is dkim. From your /etc/dkim.conf file, it looks like your selector is called simply mail. So your DNS record should be:

mail._domainkey.MYDOMAIN.com. IN TXT "v=DKIM1; k=rsa; t=s; p=<yourpublickey>"

Once that's setup and after the record has propagated, you should get the full record when you run the following:

$ dig +short TXT mail._domainkey.MYDOMAIN.com

Hope this helps.