550 Message does not pass DomainKeys requirements for domain

I got this error from my mail server log when attempting to send a mail to one of our clients:

/var/log/syslog.4.gz:Dec 14 18:13:01 XXXXXX postfix/smtp[26150]: 01BA812B22C: to=<xxxxx@yyyyy.com>, 
relay=smtp.xxxxxx.com[1.2.3.4]:25, delay=0.11, delays=0.03/0.01/0.02/0.05, dsn=5.0.0,
status=bounced (host smtp.xxxxxx.com[1.2.3.4] said: 550 Message does not pass DomainKeys requirements
 for domain zzzz.com (in reply to end of DATA command))

I’ve not implemented DomainKeys in my mail servers (but they was in the past), but I noticed that my DNS servers was wrong configured to support this protocol. DomainKeys needs two TXT records, one for the policy and one for the selector.

The policy is set with a TXT record for _domainkey.yourdomain.com, “o=~;” means that some mails can be signed and “o=-;” means all mails must be signed for domain yourdomain.com. I my case I had to change “o=-;” to “o=~;” because now, I was not using Domainkeys in my MTAs.

_domainkey                TXT    "o=~;"

The selector is implemented with other TXT record, in which you set your public key. According to RFC:

Selectors are arbitrary names below the “_domainkey.” namespace. A selector value
and length MUST be legal in the DNS namespace and in email headers
with the additional provision that they cannot contain a semicolon.

brisbane._domainkey IN TXT "g=; k=rsa; p=MHww ... IDAQAB"

The flags you can set are explained below:

g = granularity of the key. If present with a non-zero length
value, this value MUST exactly match the local part of the
sending address. This tag is optional.

The intent of this tag is to constrain which sending address
can legitimately use this selector. An email with a sending
address that does not match the value of this tag constitutes
a failed verification.

k = key type (rsa is the default). Signers and verifiers MUST
support the ‘rsa’ key type. This tag is optional.

n = Notes that may be of interest to a human. No interpretation
is made by any program. This tag is optional.

p = public key data, encoded as a Base64 string. An empty value
means that this public key has been revoked. This tag MUST be
present.

t = a set of flags that define boolean attributes. Valid
attributes are as follows:

y = testing mode. This domain is testing DomainKeys and
unverified email MUST NOT be treated differently from
verified email. Recipient systems MAY wish to track
testing mode results to assist the sender.

This tag is optional.

For example, valid entries for selectors can be:

“coolumbeach._domainkey.example.net”
“sebastopol._domainkey.example.net”
“reykjavik._domainkey.example.net”
“default._domainkey.example.net”

Here, you can use these links to test if your DNS records are well formed. the first one is to check your policy and the last one to check the selector:

http://domainkeys.sourceforge.net/policycheck.html
http://domainkeys.sourceforge.net/selectorcheck.html