We are building a system where we will have to black-list OpenVPN keys quite a lot. Hence the question: is OpenVPN algorithm for blacklisting keys computation effective? How much keys can I safely revoke before OpenVPN requires too much resources on accepting new connection/re-verification of existing one?
As I recall, when you use a Certificate Revocation List (CRL), it is checked for each connecting client at connect time, and it is checked each time the TLS/SSL connection is renegotiated (which I believe is hourly). Based on that, I would guess that you'd have to have a pretty significant number of certs blacklisted before this would likely become a problem.
Consider, if you have two thousand clients connected, with a connect/disconnect rate of 50 client connects per minute (these numbers are purely made up for an example, but intentionally higher than most people would see), then you'd be checking against the CRL about 5000 times per hour. On a modern server, I imagine OpenVPN could do 5000 checks in about than 5 seconds, even with a decent number of certs blacklisted.
I've not seen or heard of anyone benchmarking this, so actual testing is probably the only way you'll know for sure. And I would absolutely suggest setting up a test environment, programatically generating a few thousand (or more) certs, and then revoking most of those certs. Then connect some test clients and see how the server handles it. I would expect OpenVPN won't even blink at it, but it'd probably be worth verifying.