6

I have seen proprietary testing results of pummelling a CA for a long time and measuring its throughput (certs issued / second). It was found that CAs become slower to issue new certificates as the size of their database / revocation list grows (proprietary work, no results to link to sadly). For example, some corporate infrastructure CAs (ex.: S/MIME) bog down with around 100,000 certs in the database. EJBCA bogs down around 1 million certs, etc.

My question is: databases can easily handle fast lookups / inserts on millions of lines, so what is different about certificate issuance? Presumably there is some sort of crypto going on whose runtime depends on the size of the database.

Note that this is a follow-on question from comments to this question.

Community
  • 1
Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • 3
    I would be interested in seeing the Schema and Indexes EJBCA uses. The backend might need maintenance plans, that a suitable DBA can answer. – makerofthings7 Dec 08 '15 at 21:47
  • Also, I would like to see a EJBCA SQL trace. It could be the ORM (if it uses one) or the driver (Java drivers are terrible) – makerofthings7 Dec 08 '15 at 21:48
  • 1
    It is unknown what really was measured but it might be that they check if the certificate was issued already or that they want to make sure that the serial number is unique. There is no cryptographic operation during signing which needs knowledge of any previous certificates or even their number. – Steffen Ullrich Dec 08 '15 at 22:14
  • I know with databases in general, that the more indexes you have in the database, the longer insertions will take to complete (as the indexes need to be rebuilt against new or changed rows). This would be done if it is a higher priority to quickly query the database than it is to quickly insert. – Jonathan Gray Dec 09 '15 at 01:18
  • @JonathanGray No index with only 100,000 entries should take a noticeable amount of time to insert into. Even if the database had to re-write the whole index for some reason, that should still be a matter of milliseconds. – user253751 Dec 09 '15 at 05:11
  • @immibis No single index, no. But it's not just a single insert that's causing the delay either, and if that what you're assuming that I've implied, you would be incorrect. Obviously the operation would consist of multiple reads from and writes to different locations from maybe even more than one database. So it's actually sort of like a balancing act in the end. Too much or too little indexing can affect performance. – Jonathan Gray Dec 09 '15 at 05:58
  • As a rule of thumb, when you get to a million records, you do need to take some care with database indexing, house keeping, schema design - if you want decent performance. I expect the CAs you've investigated were never really designed or tested for that scale. There's no fundamental limit here though, I'm sure this could be fixed. Even the dupe checking you mention can be done efficiently. – paj28 Dec 09 '15 at 23:24

1 Answers1

2

Self-answer.

The comments suggest that these results can be explained by the fact that we are doing near-constant inserts into an unmanaged, one-size-fits-all database, and that they could likely be fixed by putting some effort into the database.

In mentioning this to a colleague, it was pointed out that some CAs will - as a courtesy - check that your public key is unique to prevent one server from impersonating another. That would require an O(log n) search, or background hashtable maintenance, or something else that would use non-trivial amounts of CPU as the database gets large.

Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207