Various folks have been asking lately if their DKIM key might be "insecure." At least one ISP out there is failing working keys with "verification failed; insecure key" as the error. A number of small, second or third tier ISPs note that the DKIM validation passed, but with a warning: "1024-bit key; insecure key."
After talking to folks and doing a bit of investigation, I think that ISP should not be failing the the DKIM signature in question. The key passes perfectly fine elsewhere, and my suspicion is that the ISP in question is running an out of date version of OpenDKIM. I myself have had issues with "insecure" warnings from OpenDKIM -- when that happens, what it's actually complaining is that the sending entity hasn't implemented DNSSEC. As I mentioned in my prior post, yeah, DNSSEC is a good thing and something to look at, but I would posit that it's really not appropriate to level an error (or a big scary warning) in email header over this, because a great number of perfectly fine entities have yet to implement it.
Indeed, the specification governing DKIM signatures (RFC 6376) mentions DNSSEC in passing but does not list it as a requirement.
TL;DR? "Insecure key" just means a sender is not running DNSSEC; it's not common or appropriate to fail a DKIM signature for this reason.
Update: A friend asks, what if the "verification failed" and "insecure key" messages are unrelated? This quite possibly could be the case. Data's a bit thin, but if so, it would still suggest to me that the ISP in question is potentially using a broken or out of date install of OpenDKIM. I am noting that it is likely OpenDKIM due to the "insecure" message and I am suggesting "broken or out of date" due to failing a DKIM key that is working when tested elsewhere. I'll provide an update if/when I learn more about this issue.