Certificate revocation is known to be a difficult problem on the web, and it is even harder in constrained environments such as the maritime sector where ships can be at sea for long times, with no or very limited connectivity with lands. In this blog post, we present the reasons that lead us to study this problem, the possible revocation mechanisms that could be used and the results of a simulation we conducted in order to determine the best possible solution. The full paper, published in Springer LNCS, is available here.
VDES & The Maritime PKI
With new communication technologies being introduced on board ships, such as VHF Data Exchange System (VDES), a variety of digital services become available. This includes for instance digital ship reporting, electronic port clearance, improved search and rescue communications or the broadcast of maritime safety information. These services will require information security, and a Public Key Infrastructure (PKI) for distributing digital certificates and securing the integrity and confidentiality of the exchanges has been acknowledged by the International Maritime Organization (IMO) and is currently ongoing standardization by IALA. Figure 1 presents the envisionned PKI, where the Root CA could be operated by IMO, and Intermediate CAs could be operated by the Flag States (every merchant ship has to be registered under a jurisdiction, called the Flag State, which has the responsibility to enforce regulations over vessels registered under its flag.).
When speaking about the maritime sector’s infrastructure, it is important to highlight that it differs from similar infrastructures on land: a ship might have to communicate using a wide range of technologies, with different entities, having different connectivity levels. For instance, a ship can communicate with another ship directly, or with a shore station using either direct communication or SATcom. As a result, the way certificates are exchanged in the maritime PKI is slightly different to how they are exchanged on the web for instance. In the maritime PKI, entities should have the possibility to store certificates in a local storage, in case they cannot reach the certificates’ server.
But then, what about certificate’s revocation? This is a difficult problem already in the web, where entities are online and usually have access to a large bandwidth, and it is thus even more difficult in the maritime sector. This is the problem we have been studying.
Candidates for the revocation mechanism in the maritime PKI
The first step to identifying good candidates for the revocation mechanism was to establish the key requirements in the maritime sector given the constraints previously mentioned. We identified three main requirements:
Offline support: The revocation mechanism should be able to operate when the vessel has no internet connectivity.
Completeness: The revocation mechanism should inform about all revoked vessels in a timely manner.
Bandwidth: The bandwidth usage of the revocation mechanism should be within the capacity of the available communication link.
As possible candidates for the certificates’ revocation mechanism, we selected common mechanisms used in PKI nowadays. This includes the well-known Certificate Revocation List (defined in RFC 5280), the Online Certificate Status Protocol (defined in RFC 6960), but also more recent methods used in modern browser: CRLSets and OneCRL, from Chrome and Firefox respectively. In addition, we added a more “recent” method, CRLite, which is also developed by Firefox. Principles behind those mechanisms won’t be explained in this post, but more details can be found in our paper. Solutions that were still at the conceptual level were excluded from our research. This includes for instance blockchain-based certificate transparency and revocation mechanisms.
Once the mechanisms selected, we looked at whether or not they were meeting the requirements exposed above.
| Offline Support | Completeness | Bandwidth Usage | |
|---|---|---|---|
| CRL / DeltaCRL | Yes | Yes | ? |
| OCSP | No | Yes | |
| OCSP Stapling | Not Completely | Yes | |
| OCSP Must Staple | Not Completely | Yes | |
| CRLSet / OneCRL | Yes | No | |
| CRLite | Yes | Yes | ? |
| Short Lived Certificate | Not Completely | No |
The reason for OCSP Stapling, OCSP Must staple and short-lived certificates to only partially meet the requirement on offline support is that they are offline only for a given period of time (for instance 7 days), and will not work anymore after that, whereas CRLs will keep working, even if it might be with outdated information.
As it can be observed, only CRL and CRLite meet both the offline and the completeness requirements. It is however difficult to predict the bandwidth usage, as this will depend on parameters from the system (such as the number of certificates, the revocation ratio, etc.). The growing size of CRLs is a known problem, and CRLite was conceived with low-bandwidth usage in mind. However, it has only been applied to the web by Mozilla, and the web has very different parameters than the maritime sector.
Simulation
To evaluate which mechanism is “the best solution” between CRL and CRLite regarding bandwidth usage, we setup a simulation, reproducing the envisioned PKI. We estimated the number of end entities enrolled in the maritime PKI to 100 000, we also evaluated the yearly revocation ratio to be around 5% (this ratio is mainly due to the ships changing their state of flag, thus needing a certificate from a new Intermediate CA). In addition, the validity period of a certificate was set to 3 years, as this was the proposition made by several independent research groups.
We developed a PKI simulator to help us evaluate the payload sizes for CRL, deltaCRL, CRLite and DeltaCRLite filter. The simulator was run for a period of 20 years and simulated a growth of the PKI from 1000 entities at the start, to 100 000 after 5 years. The revocation frequency was 7 days, which is a common revocation frequency for a CRL. At each iteration of the simulation, the following steps are taken:
- Renew certificates that are about to expire.
- Revoke random certificates based on the revocation ratio parameter.
- Generate revocation data:
- Generate new CRL.
- Generate DeltaCRL.
- Generate Optimised (minimum) CRLite filter.
- Update CRLite filter.
- Generate Delta Filter (using the updated filter).
- Enroll new entities (if any, when growth enabled).
What we really care about is the “steady” state of the PKI, i.e. how the PKI behaves over time, once the number of ships enrolled has been stabilized. This is why we ran the simulation over 20 years.
Figures 2 and 3 present the results of the simulation. One can notice a pattern in the curves, this is due to expired revoked cert being removed from the CRL, thus creating this 3-year period pattern. As it was expected, the CRL size is much bigger than the size of the other mechanisms, with an average size of 356 kB. Even if this is much smaller than CRLs in the Internet world, it is still too big to be downloaded over a low-speed network. Despite the size of the DeltaCRL being quite small (8.6 kB), the DeltaFilter from CRLite is even smaller with an average of 2 kB. It is also interesting to note that the size of the Delta Filter is close to constant once the system has reached its equilibrium. Based on the simulation, it looks like CRLite is well suited for low-bandwidth usage, not only for the Internet world, but also for the maritime sector.
Conclusion
The requirements analysis has shown that CRLite is well suited for the maritime sector. Does that mean it should be chosen without any further considerations? Obviously, it is not that simple, and while CRLite seems best in class when it comes to our requirements, we saw that the CRL/DeltaCRL solution is not lagging far behind. In addition, CRLite is a recent solution, not standardized or field-tested yet and this can be an obstacle when it comes to implementation. On the other hand, CRL/DeltaCRL are well-known and already implemented in commercial PKI. The final decision will thus be a trade-off between selecting the more well-known and mature technology (CRL) or going for a potentially more efficient but less tested solution (CRLite).
The full research paper is available here.