Upgrade From SQL 2012 to SQL 2016 - Problem with Certificates

Summary

You may need to drop and recreate your certificates after migrating from SQL 2012 to SQL 2016+.

Background

We're working to move from 2012 to 2016, and I think we have most of this figured out pretty well. Crypto-wise, we are importing the old service master key (SMK), and restoring our old DBs and their old database master keys (DMKs). We have a few cross-DB stored procedures that rely on certificate signing and presence of identical certs in multiple DBs. All that works with no effort. We can test these procedures and be certain that the cross-DB certificate signing is working on the SQL 2016 instance.

Problem

But when we try to sign a new stored procedure with one of the existing certs, it fails:

Msg 33176, Level 16, State 2, Line 32
Signing operation failed. Key uses deprecated algorithm 'rsa_1024' which is no longer supported at this db compatibility  level. If you still need to use this key switch to a lower db compatibility level.

We'd updated our DBs to 130 compatibility on the new server. So one easy way out might be changing back to a lower compatibility level. But we didn't want to do that if we didn't need to.

We looked at all our keys (sys.asymmetric_keys, sys.symmetric_keys) and did not see any evidence of any RSA 1024 keys. The SMK and DMKs are all AES-256. But the SQL 2016 sys.certificates table has an undocumented column "key_length" which did show 1024 for all of the certificates that we'd brought over with the DB restores--the same certs that we use for signing.

Solution

So we tried dropping and recreating our certificates. Problem solved. The new certs have "key_length" = 2048 and can successfully be used to sign our stored procedures. This was a little work. To drop and re-create, for each cert we needed to:

find and drop all associated signatures from related stored procedures
drop the users that we'd created from the cert
drop and then recreate the cert
re-create users from the cert
re-grant rights to those users
re-sign all the stored procedures that need signing

I was not able to find any discusion of this online, but hard to believe we're the first to run across this issue. So maybe I'm wrong? If you think so, please let me know.