Performance Evaluation and Modeling of Cryptographic Libraries for MPI Communications

Standard documents, such as NIST SP 800-38A [8] and 800-38D [29], specify several modes of encryption. Many of them, such as Electronic Codebook (ECB), Cipher Block Chaining (CBC), Counter (CTR), Galois/Counter Mode (GCM), and Counter with CBC-MAC (CCM), are well-known and widely used. However, these schemes are not equal in security and ease of correct use. The ECB mode, for example, is insecure [2]. CBC and CTR modes provide only privacy, meaning that the adversary cannot even distinguish ciphertexts of its chosen messages with those of uniformly random messages of the same length. They however do not provide data integrity in the sense that the adversary cannot modify ciphertexts without detection.¹¹1 Actually, the adversary can still replace a ciphertext with a prior one; this is known as replay attack. Here we do not consider such attacks. Among the standardized encryption schemes, only GCM and CCM satisfy both privacy and integrity, but GCM is the faster one [30]. Therefore, in this paper, we will focus on GCM; one does not need to know technical details of GCM to understand our paper.

Syntactically, AES-GCM is a nonce-based encryption scheme, meaning that to encrypt plaintext $P$, one needs to additionally provide a nonce $N$, i.e., a public value that must appear at most once per key. The same nonce $N$ is required for decryption, and thus the sender needs to send both the nonce $N$ and the ciphertext $C$ to the receiver. See Fig. 1 for an illustration of the encrypted communication via GCM. In AES-GCM, nonces are 12-byte long, and one often implements them via a counter, or pick them uniformly at random. In addition, each ciphertext is $16$-byte longer than the corresponding plaintext, as it includes a $16$-byte tag to determine whether the ciphertext is valid.

In our implementation, we consider the following cryptographic libraries: OpenSSL [3], BoringSSL [4], Libsodium [5], and CryptoPP [6]. They are all in the public domain, are widely used, and have received substantial scrutiny from the security community.

OpenSSL is one of the most popular cryptographic libraries, providing a widely used implementation of the Transport Layer Security (TLS) and Secure Sockets Layer (SSL) protocols. Due to its importance, there has been a long line of work in checking the security of OpenSSL, resulting in the discovery of several important vulnerabilities, such as the notorious Heartbleed bug [31]. As a popular commercial-grade toolkit, OpenSSL is used by many systems. BoringSSL is Google’s fork of OpenSSL, providing the SSL library in Chrome/Chromium and Android OS.

Libsodium is a well-known cryptographic library that aims for security and ease of correct use. It provides several benefits such as portability, cross-compilability, and API-compatibility, and supports bindings for all common programming languages. As a result, Libsodium has been used in a number of applications, such as the cryptocurrency Zcash and Facebook’s OpenR (a distributed platform for building autonomic network functions). It however only supports AES-GCM with 256-bit keys.

CryptoPP is another popular open-source cryptographic library for C++. It is widely adopted in both academic and commercial usage, including WinSSHD (an SSH server for Windows), Steam (a digital distribution platform purchasing and playing video games), and Microsoft SharePoint Workspace (a document collaboration software).

For large messages, say 2MB ones, encrypted MPI libraries have poor performance compared to the baseline: even the fastest BoringSSL yields 78.3% overhead, and CryptoPP’s overhead is much worse, nearly 400%. These performance results can be explained as follows.

• •

  The running time of an encrypted MPI library consists of (i) the encryption-decryption cost, and (ii) the underlying MPI communications, which roughly corresponds to the baseline performance.

• •

  For BoringSSL, on 2MB messages, the encryption-decryption throughput of AES-GCM-256 (1381 MB/s) is about 1.32 times that of the ping-pong throughput of the baseline (1038 MB/s). Estimatedly, BoringSSL’s ping-pong time would be roughly $\frac{1+1.32}{1.32}\approx 1.76$ times slower than that of the baseline. This is consistent with the reported 78.3% overhead above.

• •

  For CryptoPP, on 2MB messages, the encryption-decryption throughput of AES-GCM-256 (273 MB/s) much worse, just around 26% of the ping-pong performance of the baseline (1038 MB/s). One thus can estimate that CryptoPP’s ping-pong time would be about $\frac{1+0.26}{0.26}\approx 4.84$ times slower than that of the baseline. This is again consistent with the reported 400% overhead above.

For small messages, encrypted MPI libraries often perform reasonably well, since the encryption-decryption throughput of AES-GCM-256 is quite higher than the ping-pong throughput of the baseline. For example, for 256-byte messages, the encryption-decryption throughput of Libsodium is 409.67 MB/s, much higher than the 7.01 MB/s baseline ping-pong throughput. Consequently, Libsodium has just 5.89% overhead for 256-byte messages.

For medium and large messages, as the number of pairs increases, the relative performance of the encrypted MPI libraries becomes much better, because (i) the network bandwidth remains the same, yet the computational power doubles, and (ii) encryption/decryption can overlap with MPI communications. When there is just a single pair, even BoringSSL cannot encrypt fast enough to keep up with the network speed. However, when there are 8 pairs, even CryptoPP can reach the baseline performance, for 16KB messages. These results suggest that (1) the overhead for a single communication flow may be significant, but (2) in modern multi-core machines, when multiple flows happen concurrently, the performance of encrypted MPI libraries may be on par with the baseline.

For small messages, the situation is different, because the network bandwidth is not fully used. As shown in Fig. 4, for 1B-data, the baseline throughput keeps increasing as the number of pairs increases. In contrast, for medium and large messages, the baseline throughput is saturated when there are just two pairs of senders and receivers. Consequently, even when there are 8 pairs, BoringSSL still incurs 61.67% overhead, and CryptoPP is far worse, resulting in 506.25% overhead.

To understand the performance of Encrypted_Bcast, recall that each encrypted broadcast consists of an ordinary MPI_Bcast and an encryption and a decryption per node. Hence the encryption overhead of the three encrypted MPI libraries, illustrated in Fig. 5, loosely mirrors their encryption-decryption throughput of Fig. 2.

• •

  For example, for large messages (say 2MB), the encryption-decryption throughput of BoringSSL (1381 MB/s) is around 2.37 times that of Libsodium (583 MB/s). On the other hand, the encryption overhead in Encrypted_Bcast of BoringSSL (44.8%) is 2.03 times smaller than that of Libsodium (90.96%), approximating the ratio 2.37 above.

• •

  As another example, for BoringSSL, the encryption-decryption throughput for 2MB messages is about the same as that for 16KB messages. Thus one would expect the encryption cost for 4MB messages in Encrypted_Bcast would be about $\frac{4\text{MB}}{16\text{KB}}=256$ times that for 16KB messages. Indeed, for 4MB messages, BoringSSL spends about 4,298 $\mu$s on encryption/decryption, which is about 298 times its encryption/decryption time for 16KB messages (14.42 $\mu$s).

The trend of Encrypted_Alltoall, illustrated in Fig. 5, is similar.

• •

  For example, for 16KB messages, the encryption-decryption throughput of BoringSSL (1332 MB/s) is about $2.35$ times that of CryptoPP (568 MB/s). The encryption overhead of BoringSSL in Encrypted_Alltoall (17.19%) is 2.57 times smaller than that of CryptoPP (44.19%).

• •

  As another example, for CryptoPP, the encryption-decryption throughput for 2MB messages (273 MB/s) is about a half of that for 16 KB messages (568 MB/s). Thus one would expect the encryption cost for 4MB messages in Encrypted_Alltoall would be about $\frac{4\text{MB}}{16\text{KB}}\cdot 2=512$ times that for 16KB messages. Indeed, for 4MB messages, CryptoPP spends about 1,331,103 $\mu$s on encryption/decryption, which is about 459 times its encryption/decryption time for 16KB messages (2900 $\mu$s).

Again, for large messages, the performance of the encrypted MPI libraries is much lower than that of the baseline, but the situation is much worse than the Ethernet setting. For example, for 2MB messages, even BoringSSL results in a 215.2% overhead. With InfiniBand, the baseline ping-pong throughput is significantly higher than that with Ethernet while the encryption-decryption throughput remains the same: the encryption-decryption throughput of AES-GCM-256 is much lower than the ping-pong throughput of the baseline. For example, for 2MB messages, the encryption-decryption throughput of AES-GCM-256 in BoringSSL (1384 MB/s) is just around 46% of the baseline ping-pong throughput (3023 MB/s), and thus estimatedly, BoringSSL’s ping-pong time would be about $\frac{1+0.46}{0.46}\approx 3.17$ times slower than that of the baseline. This is consistent with the reported 215.2% overhead above.

For small messages, the situation is somewhat better, but even BoringSSL would yield poor performance. For example, for 256-byte messages, BoringSSL has a 80.93% overhead.

Like the Ethernet setting, for medium and large messages, although the encryption overhead is substantial when there is only one pair of communication, when the number of pairs increases, the throughput of encrypted MPI libraries is much closer to the baseline throughput. However, for medium message size (say 16KB), even when there are eight communication flows, BoringSSL only achieves 2561 MB/s, which is just 81.8% of the baseline throughput of 3128 MB/s. This gap is due to the speed difference between Ethernet and Infiniband.

For small messages, the trend is at first similar to that of the Ethernet setting, but when the number of pairs increases from 4 pairs to 8 pairs, the baseline throughput is throttled, probably due to network contention. This decrease also happens for medium and large messages, but not as conspicuously as the case of small messages. Due to the plummeting of the baseline throughput, for 8 pairs and one-byte messages, BoringSSL’s overhead is just 29.91%, whereas for 4 pairs, its overhead is 308.33%.

To obtain the parameters of the Hockney model, we use linear least squares on latency measurements from the Ping-Pong benchmarks in Section 5 to find the best fitting $(\alpha_{\mathrm{comm}},\beta_{\mathrm{comm}})$.³³3 If the linear regression results in a meaningless negative $\alpha_{\mathrm{comm}}$ then we will instead let $\alpha_{\mathrm{comm}}$ be the average latency of Ping-Pong benchmarks for one-byte data, and then find the best fitting $\beta_{\mathrm{comm}}$ via linear least squares. The values of those parameters are given in Table IX.

If we let $\alpha_{\mathrm{ecom}}=\alpha_{\mathrm{comm}}+\alpha_{\mathrm{enc}}$ and $\beta_{\mathrm{ecom}}=\beta_{\mathrm{comm}}+\beta_{\mathrm{enc}}$ then we obtain

Intuitively, encrypted communication can be viewed as conventional MPI communication over a private and authenticated channel, thus Eq. (1) is the Hockney model for communication over this network. Since this Hockney model takes both communication and encryption into account, we will call it the enhanced Hockney model.

An advantage of the enhanced Hockney model above is that the parameters $\alpha_{\mathrm{ecom}}$ and $\beta_{\mathrm{ecom}}$ can be obtained without implementing encrypted MPI. In fact, one can use available benchmarks of conventional MPI implementations and cryptographic libraries to obtain $\alpha_{\mathrm{comm}},\beta_{\mathrm{comm}},\alpha_{\mathrm{enc}},\beta_{\mathrm{enc}}$, and compute $\alpha_{\mathrm{ecom}}\leftarrow\alpha_{\mathrm{comm}}+\alpha_{\mathrm{enc}}$ and $\beta_{\mathrm{ecom}}\leftarrow\beta_{\mathrm{comm}}+\beta_{\mathrm{enc}}$. In other words, the independent benchmarking results summarized in Table IX (for MPI libraries) and Table X (for cryptographic libraries), can directly derive the model parameters for the enhanced Hockney model. Consider, for example, small messages (Eager protocol) with BoringSSL on InfiniBand. From Table IX, we have $\alpha_{\mathrm{comm}}=3.40$ and $\beta_{\mathrm{comm}}=3.83\times 10^{-4}$; from Table X, we have $\alpha_{\mathrm{enc}}=0.53$ and $\beta_{\mathrm{comm}}=6.90\times 10^{-4}$. Hence, for the encrypted single-flow MPI point-to-point communication, the enhanced Hockney model has the parameters $\alpha_{\mathrm{ecom}}=\alpha_{\mathrm{comm}}+\alpha_{\mathrm{enc}}=3.40+0.53=3.93$ and $\beta_{\mathrm{ecom}}=\beta_{\mathrm{comm}}+\beta_{\mathrm{enc}}=3.83+6.90=10.73$ for small messages. The model parameters for other combinations of libraries and systems can be derived similarly.

Using parameters derived from independent benchmarking of MPI and encryption libraries, we validate the enhanced Hockney models for single-pair encrypted MPI communications by comparing the model’s predicted performance to the measured performance of our encrypted MPI libraries with the Ping-Pong benchmark on different systems. Three encryption libraries, BoringSSL, Libsodium, and CryptoPP, and two networks, InfiniBand and Ethernet are studied. Results for OpenSSL are similar to those for BoringSSL and are not reported. As shown in Fig. 10, for all configurations, our enhanced Hockney models capture the trend of encrypted communication with reasonable accuracy.

We consider the performance of multiple concurrent pairs of encrypted MPI point-to-point communications like the OSU multiple-pair benchmark.

We use linear least-squares on latency measurements from the (unencrypted) Multiple-Pair benchmarks in Section 5 to obtain the best fitting $(\alpha_{\mathrm{comm}},\beta_{\mathrm{comm}})$. The values of those parameters are given in Table XI. ⁴⁴4Since OSU Multiple-Pair benchmark uses non-blocking sends and Ping Pong uses blocking sends, the parameter $\beta_{\mathrm{comm}}$ of the former is smaller than that of the latter. Moreover, as OSU Multiple-Pairs benchmark sends 64 messages back-to-back, its latency $\alpha_{\mathrm{comm}}$ is an order of magnitude smaller than that of the Ping Pong benchmark.

To obtain the training data for deriving the parameters, we run the encryption-decryption benchmark in Section 5 for BoringSSL for $k\in\{1,2,4,8\}$ threads. To account for the pipelining effect of AES-NI and whether a message fits the L1 cache (32 KB), we divide the message size into three corresponding levels—small (up to 256B), moderate (larger than 256B but smaller than 32KB), and large (32KB or more)—and use different parameters $(\alpha_{\mathrm{enc}},A,B)$ for each level. To obtain the parameters $(\alpha_{\mathrm{enc}},A,B)$, we use Matlab’s non-linear least square on the latency measurements from the experiment above to find the best fitting choice.⁵⁵5Specifically, we use Matlab’s command lsqnonlin. The values of $(\alpha_{\mathrm{enc}},A,B)$ are given in Table XII.

In the OSU multiple-pair benchmark, the performance is measured for iterations of 64-round loops. For each iteration, each sender encrypts a message of $m$ bytes and then sends the ciphertext to its receiver via a non-blocking send; with our encrypted library implementation, each receiver waits for all 64 ciphertexts to arrive and decrypt them. In modeling this multiple-pair communication, we make the following assumptions:

• •

  The encryption time and decryption time for a message are the same.⁶⁶6In modern machines that support AES-NI and CLMUL instruction set, AES-GCM encryption is often slightly faster than decryption, but the speed difference is small.

• •

  The transmission of the $i$-th message (via non-blocking send) and the encryption of the $(i+1)$-th message can happen concurrently. Likewise, the receiver can simultaneously decrypt a ciphertext of the $i$-th message while receiving the ciphertext of the $(i+1)$-th message.

In this communication, each sender will first encrypt the $m$ bytes data, which takes $\frac{T_{\mathrm{enc}}(k,m)}{2}$ time (half of the encryption and description time), after that, there are 63 overlapped encryptions and communications, which takes $63\cdot\max\Bigl{\{}\frac{T_{\mathrm{enc}}(k,m)}{2},T_{\mathrm{comm}}(k,m)\Bigr{\}}$ time, and one last communication, that takes $T_{\mathrm{comm}}(k,m)$ time. Hence, the encryption and sending time can be modeled as

Since the receiver waits for all 64 ciphertexts to arrive and decrypt them, the total time for a 64-round loop in the encrypted Multiple-Pair experiment can be modeled as

and thus the average time $T_{\mathrm{ecom}}(k,m)$ for a single round is

Notice that the model for multiple-pair encrypted MPI point-to-point communication, $T_{\mathrm{ecom}}(k,m)$ is derived from $T_{\mathrm{comm}}(k,m)$ and $T_{\mathrm{enc}}(k,m)$. Hence the model parameters for multiple-pair communication can also be derived from independent benchmarking results for the MPI library and encryption libraries.

We validate the model by comparing the predicted performance from the model to the measured performance using the OSU Multiple-Pair benchmark [9] with the three encryption libraries and two networks (Ethernet and InfiniBand). Fig. 11 shows the results for Ethernet and Fig. 12 shows the results for InfiniBand.

An advantage of our models for both single-pair and multiple-pair communications is that the parameters can be obtained from the available benchmarks of conventional MPI and encryption, meaning that using these models, one does not need to implement encrypted MPI in order to understand encrypted MPI communication performance. As shown earlier, these models capture the performance trend and predict the performance with reasonable accuracy for different libraries and networks. Hence, the models allow us to reason about the performance of encrypted MPI communications.

We will use examples to show that the models give simple and intuitive explanation of the performance results across different cryptographic libraries and different networks in Section 5. Consider for example the single-pair communication. For large messages, $T_{\mathrm{comm}}(m)$ and $T_{\mathrm{ecom}}(m)$ are dominated by $\beta_{\mathrm{comm}}\cdot m$ and $\beta_{\mathrm{ecom}}\cdot m$ respectively, and thus the encryption overhead (for throughput) is

For example, the overhead of BoringSSL for large messages is predicted to be

for Ethernet, which is consistent with the Ping-pong benchmark results in Figure 3 in Section 5—the measured results have an overhead of 78.3% for 2MB messages. For InfiniBand, the overhead of BoringSSL for large messages is predicted to be

where as the measured results of the Ping-pong benchmark in Figure 7 in Section 5 have an overhead of 215% for 2MB messages.

Consider now the multiple-pair communication:

There are two situations depending on the relative speed of communication and encryption. For a slow network such that $T_{\mathrm{comm}}(k,m)\geq\frac{T_{\mathrm{enc}}(k,m)}{2}$, we have $T_{\mathrm{ecom}}(k,m)=T_{\mathrm{comm}}(k,m)+\frac{T_{\mathrm{enc}}(k,m)}{2}$, and the encryption overhead (for throughput) is

meaning that the overhead is inversely proportional to $2k$: the larger the value of $k$ (pairs of communications), the smaller the overhead. Both 10Gbps Ethernet and 40Gbps InfiniBand has $T_{\mathrm{comm}}(k,m)\geq\frac{T_{\mathrm{enc}}(k,m)}{2}$ when $k=8$. This overhead trend is observed in Figure 4 and Figure 8. Plugging in the values of $A$ and $B$ from Table XII and $\beta_{\mathrm{comm}}$ from Table XI will give a reasonable estimation of the overheads for OSU multiple pair benchmarking results.

For a faster network such that $T_{\mathrm{comm}}(k,m)<\frac{T_{\mathrm{enc}}(k,m)}{2}$, $T_{\mathrm{ecom}}(k,m)\approx T_{\mathrm{enc}}(k,m)$, meaning that the communication cost can be completely hidden. However, the performance will be bounded by the encryption speed, which can be much slower than the network speed.

Clearly, there is a gap between what single-core encryption can provide and what a high-speed network can consume. The gap is likely to increase since (1) we reach the limit of Moore’s law and single-core computing performance will not drastically improve, and (2) communication technology is still improving as the network bandwidth continues to increase. As such, efficient encrypted MPI communication will be even more challenging in the future.

The models can give guidance on the techniques to achieve higher encrypted MPI communication performance as well as the potential benefits of such techniques. Consider for example to improve the single-pair encrypted performance. One potential technique is to overlap encryption with communication. For large messages, this can be achieved by chopping the message into small segments, then encrypting (and decrypting) each segment, and using non-blocking communication to overlap communication with encryption and decryption as in streaming encryption [34]. Using this technique, $T_{\mathrm{ecom}}(m)\approx\max\{T_{\mathrm{comm}}(m),T_{\mathrm{enc}}(m)\}$. For systems with a slow network such as an 10Gbps Ethernet where $T_{\mathrm{comm}}(m)\geq T_{\mathrm{enc}}(m)$, we have $T_{\mathrm{ecom}}(m)\approx T_{\mathrm{comm}}(m)$: the encryption overhead can virtually be completely removed. However, for a faster network such as 40Gbps InfiniBand where $T_{\mathrm{enc}}(m)\geq T_{\mathrm{comm}}(m)$, $T_{\mathrm{ecom}}(m)\approx T_{\mathrm{enc}}(m)$. Consider for example, encrypted communication for large message with BoringSSL on InfiniBand, we have $\beta_{\mathrm{comm}}=3.12\times 10^{-4}$ (Table IX) and $\beta_{\mathrm{enc}}=6.90\times 10^{-4}$ (Table X), hence $T_{\mathrm{enc}}(m)\approx 2.2T_{\mathrm{comm}}(m)$. Thus, even with the encryption and communication overlapping technique, the encryption overhead will roughly be $\frac{T_{\mathrm{ecom}}(m)}{T_{\mathrm{comm}}(m)}-1\approx 120\%$. This overhead is further be improved by using multiple threads to perform concurrent encryption and decryption. This technique with multiple threads will be more attractive for future systems since they will likely to have more (idle) cores in each node.