opendkim fail | bad RSA signature | verification failed unprotected key

Question

I have fully manageable VPS running Ubuntu 14.04 which hosts websites for several domains. Recently I have tried to add DKIM signatures to avoid spam filters. I've followed ubuntu-postfix-dkim tutorial, using KeyTable and SigningTable as explained in well written post askubuntu.com. Each domain has its own public and private key and txt DNS zone record.

After testing via [email protected], [email protected] or even via http://dkimvalidator.com/ the response is quite the same:
DKIM: fail (signature doesn't verify)

Mail is signed and signature looks OK but it fails verification test. The only thing that comes to my mind is that message is somehow modified after calculating the signature hash. My question is:

Is it possible to debug the sending process? It would be great to check what and when is calculated for DKIM signature. I have tried OmitHeaders To,to,TO in configuration file but strangly To: value still appears in h= param.

I have googled a lot but still no luck. Thanks in advance.
Output from dkimvalidator.com:

DKIM Signature

Message contains this DKIM Signature:
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=inhillz.com; s=mail;
    t=1429184641; bh=g3zLYH4xKxcPrHOD18z9YfpQcnk/GaJedfustWU5uGs=;
    h=Date:From:To:Subject;
    b=fccxI1j/+InWdupEY1/hAYCUeSAlTHo3tr/594sOqETs6kEzRlyXWZDLib1b1WqV0
    xN/wr0Io+OGTJOTChp+cJ/H/KrODt1mzGgDA/O/AKWUPEGKODgk9iO03/o6DpLB4bM
    t5GVSKdBQna7sYkQJM2mGtCNgswydgsgytb0J9QA=

Signature Information:
v= Version:         1
a= Algorithm:       rsa-sha256
c= Method:          relaxed/relaxed
d= Domain:          inhillz.com
s= Selector:        mail
q= Protocol:        
bh=                 g3zLYH4xKxcPrHOD18z9YfpQcnk/GaJedfustWU5uGs=
h= Signed Headers:  Date:From:To:Subject
b= Data:            fccxI1j/+InWdupEY1/hAYCUeSAlTHo3tr/594sOqETs6kEzRlyXWZDLib1b1WqV0
    xN/wr0Io+OGTJOTChp+cJ/H/KrODt1mzGgDA/O/AKWUPEGKODgk9iO03/o6DpLB4bM
    t5GVSKdBQna7sYkQJM2mGtCNgswydgsgytb0J9QA=
Public Key DNS Lookup

Building DNS Query for mail._domainkey.inhillz.com
Retrieved this publickey from DNS: v=DKIM1; k=rsa; p=MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCpLxuEApOG3ubulSygyEMAVsGHnBUDdYfCHJpGzMguNOCPSpQSdHxUFS+AGKwwyYTLs0X9kP7KUKLhY5TcxJgFPpSl6DOkkjs7Yd/njdg5o/DZe4Ey1hv+XqquEwGh7mqH3049ph2DUA7w3sm6gEgcydYTcyR5ykZ8nQMSIoeRKQIDAQAB
Validating Signature

result = fail
Details: bad RSA signature  

EDIT
I have tried to generate new keys, also changed the DNS records and tested them with

opendkim-testkey -d inhillz.com -s mail -k mail.private -vvv

The output is:

opendkim-testkey: using default configfile /etc/opendkim.conf
opendkim-testkey: key loaded from mail.private
opendkim-testkey: checking key 'mail._domainkey.inhillz.com'
opendkim-testkey: key not secure
opendkim-testkey: key OK

After verifing via [email protected] still the same error.

Solution

When changing your DNS settings, make sure to update the serial number of the SOA record, ie; 2016092601 ; serial number, where yyyymmddhhvv = year month day hour version. If the serial number doesn't change, some DNS won't update their cache.

Also, make ABSOLUTELY SURE the dkim matches the txt record in your DNS record:

dkim._domainKey TXT ( "p=very-long-text-string")

Comments

[masegaloeh]

Can you check private key and published DNS key with opendkim-testkey and share the output?

[Matúš Makač Mačák]

Thanks for your reply. I have added the output to my question. It looks ok. Any ideas?

[maxisme]

I have this exact problem! Any ideas?

[Matúš Makač Mačák]

I haven't find any solution for this. I didn't have time to fix it but I will work on this soon. If you have any ideas, please let me now. Thx

[Marc Stürmer]

Are you using a key > 1024 bits? Many DNS servers out there are unable to process those, so better be sure your primary DNS can if!

[Mostafiz Rahman]

Having similar problem, did anyone manage to fix this?

[Federico Ponzi]

Same exactly problem in 2018 c':