DKIM Unauthenticated Mail is Prohibited

Question

We just started getting this bounce back message when sending to military email addresses. 
 Bounced: #5.7.5 DKIM unauthenticated mail is prohibited; Verify DKIM key length is >= 1024B 
 We have made no changes to our SEA. 
 Can anyone example what possibly changed? 
 I am guessing the military changed something on their end.

Red_Warrior · Accepted Answer

I would run your domain and the target through mxtoolbox and verify the dkim signature is fine. 
 the next thing to do is to try disabling dkim and make sure you can relay mail (as in its not an authentication issue) 
 the error its self may also indicate the actual key is generated with a cipher that is less than 1024 bytes. 
 
 see the rfc for the best information on dkim 
 https://tools.ietf.org/html/rfc4871 Appendix A . Example of Use (INFORMATIVE) 
 ensure that the signatures are been stamped correctly and such. 
 
 NOTES: 
 keep in mind this could also be a case where email is been signed either upstream or before outbound policy is complete.. Without the entire message and transmission details to/from/domains etc.. You'r best bet is to call in to support and open a case. 
 
 In the mean time you could also export the mail and message log to a syslog server and have a look at the mta logs for failures and authentication requests..