I’ll skip the theory of statistical analysis and practical way of executing the test script reliably, if you’re interested in that, see the debugging code article and the tlsfuzzer documentation. That being said, to understand what we’ll be doing, you need to understand that small p-values indicate departure from expected result (where expected result in our case is “no discernable difference based on input”) and what 95% confidence interval means.

With that out of the way, let’s look at a server.

Server

In this example we’ll consider a simple server that expects a password and, in case the password is correct, replies with some kind of secret data. To make execution of the tests easier, and interpretation of the graphs more clear, let’s assume that the password in question contains only lower case Latin letters, i.e. ‘a’ to ‘z’.

The server code and test client is available on gist, you can compile the server with gcc:

gcc password_server.c -o password_server

Then execute it by running:

./password_server

It will listen on port 5001 on all network interfaces.

The critical part of it is the loop that inspects the characters of the provided password (data) with the expected password (password) until either string ends (through newline character or null character):

   /* check if all the letters match */
   for (a=data, b=password; *a != '\n' && *a != '\x00' && *b != '\n' && *b != '\x00'; a++, b++) {
       if (*a != *b) {
          goto end;
       }
   }
   /* check if length matches */
   if (!((*a == '\n' || *a == '\x00') && (*b == '\n' || *b == '\x00'))) {
      goto end;
   }

Now, since it aborts as soon as a letter is different, it will provide a side-channel signal. Question is, how big, and can we attack it?

Test client

While running the server is fairly simple, getting the client script running is a bit more involved. You’ll need to have python available (new enough for scipy and numpy to work) and permissions to run the tcpdump packet capture (easiest way to do it is by running the script as root).

First of all, download the tlsfuzzer repository:

git clone https://github.com/tlsfuzzer/tlsfuzzer.git

Then create a virtual environment and install the dependencies needed to run script and the statistical analysis:

python3 -m venv tlsfuzz-venv
tlsfuzz-venv/bin/pip install -r tlsfuzzer/requirements.txt -r tlsfuzzer/requirements-timing.txt

Then as either user with permission to run tcpdump or as root, you can execute the test script against the server:

PYTHONPATH=./tlsfuzzer/ ./tlsfuzz-venv/bin/python3 ./test-passwd-guess.py -i lo -o /tmp --repeat 1000 --no-quickack

The PYTHONPATH environment variable tells python where to find the tlsfuzzer library, we specify python3 from inside the virtual environment so that it has access to the installed dependencies. The meaning of the options is as follows: -i lo specifies the interface on which the packet capture needs to be executed on (you will need to inspect output of ip addr ls to learn the interface name of external facing interface when running the test over real network), -o /tmp specifies where to keep the temporary files and the results, --repeat 1000 specifies that every letter needs to be used in 1000 connections, and finally the --no-quickack specifies that we don’t want to expect the TCP QUICKACK feature to be in use.

Internally, the script does something fairly simple: connects to the server, sends a password guess, expects error, and then connection close. The password guesses are just the 26 letters of the alphabet. In addition to that we have also the canary (or placebo) probe, that’s a second probe with letter ‘a’. By sending the probes in random order and measuring the response time from the server, we can effectively see if the server accepted the first letter of the password or not (as testing two letters for equality will take more time than testing just one).

Results

If you execute those commands on a typical system you will likely see the script report “No statistically significant difference detected”, or in more detail, summary that looks something like this:

Sign test mean p-value: 0.5348, median p-value: 0.5464, min p-value: 0.0009225
Friedman test (chisquare approximation) for all samples
p-value: 0.669298684947114
Worst pair: 5(e), 22(v)
Mean of differences: 6.99390e-06s, 95% CI: -1.42111e-06s, 2.193720e-05s (±1.168e-05s)
Median of differences: 4.00000e-08s, 95% CI: 1.00000e-08s, 7.000000e-08s (±3.000e-08s)
Trimmed mean (5%) of differences: 1.04511e-07s, 95% CI: 4.44867e-08s, 1.665733e-07s (±6.104e-08s)
Trimmed mean (25%) of differences: 7.88520e-08s, 95% CI: 2.81640e-08s, 1.227660e-07s (±4.730e-08s)
Trimmed mean (45%) of differences: 3.86200e-08s, 95% CI: 1.00900e-08s, 6.882000e-08s (±2.936e-08s)
Trimean of differences: 7.26250e-08s, 95% CI: 2.00000e-08s, 1.157937e-07s (±4.790e-08s)
For detailed report see /tmp/test-passwd-guess.py_v1_1697395170/report.csv
No statistically significant difference detected

With accompanying graph looking like this:

Does that mean that there is no side channel leakage? No. As the 95% confidence intervals of both median and trimmed means are in the range of tens of nanoseconds (30ns and 29ns respectively) we cannot exclude the possibility of a side channel. This test was executed on an AMD Ryzen 5 5600X that can boost up to 4.6GHz, which means that the smallest side channel it can have is on the order of 0.2ns. So a small side channel would be undetectable with such a small sample.

OK, let’s execute the same test again, but with --repeat 100000 option. Now, after about 10 minutes of execution time, the test reports failure (it’s a failure as correctly implemented server wouldn’t have a side-channel leak), with the overall statistics that look like this:

Sign test mean p-value: 0.42, median p-value: 0.4144, min p-value: 1.545e-31
Friedman test (chisquare approximation) for all samples
p-value: 4.028330499541504e-44
Worst pair: 13(m), 15(o)
Mean of differences: 6.71613e-08s, 95% CI: -7.92283e-07s, 9.030701e-07s (±8.477e-07s)
Median of differences: -2.00000e-08s, 95% CI: -2.00000e-08s, -1.900000e-08s (±5.000e-10s)
Trimmed mean (5%) of differences: -1.81057e-08s, 95% CI: -2.57158e-08s, -1.146633e-08s (±7.125e-09s)
Trimmed mean (25%) of differences: -1.80656e-08s, 95% CI: -2.33658e-08s, -1.299852e-08s (±5.184e-09s)
Trimmed mean (45%) of differences: -1.89289e-08s, 95% CI: -2.21798e-08s, -1.605050e-08s (±3.065e-09s)
Trimean of differences: -1.77500e-08s, 95% CI: -2.25000e-08s, -1.675000e-08s (±2.875e-09s)
For detailed report see /tmp/test-passwd-guess.py_v1_1697385326/report.csv

Both the Friedman test has a statistically significant p-value, and the smallest sign test p-value is small enough to be significant.

But the graphs of the confidence intervals of the means still are not clear:

That’s because I’ve executed the script on a machine with no special configuration, with other workloads running at the same time (I had no core isolation set up and I was watching YouTube in the meantime). If we take a look at the ECDF of the collected measurements, we’ll see that there’s a huge spread (of over 7 orders of magnitude larger than the difference we want to measure) in the calculated differences:

And looking at heatmap of the differences, the data not only has long and heavy tails, it is clearly multi-modal (in this case we see 3 clear modes):

Thankfully, there are simple ways to work with such data, we can either look at the confidence interval of the median (here it it’s limited by the resolution of the clock source the kernel decided to use):

Or at the confidence interval of the trimmed means:

In both of those graphs, clearly the class 13 is the outlier. By looking at the legend.csv or at the report, we can deduce that class 13 corresponds to ‘m’, so the first letter of the password is “m”.

With this information we can ask the script to start looking for the second letter:

PYTHONPATH=./tlsfuzzer/ ./tlsfuzz-venv/bin/python3 ./test-passwd-guess.py -i lo -o /tmp --repeat 100000 --no-quickack --base m

That will provide us with a summary like this:

Sign test mean p-value: 0.4052, median p-value: 0.4143, min p-value: 3.179e-25
Friedman test (chisquare approximation) for all samples
p-value: 2.0606607949733857e-53
Worst pair: 1(a - canary), 20(t)
Mean of differences: -4.81858e-08s, 95% CI: -6.41017e-07s, 5.886469e-07s (±6.148e-07s)
Median of differences: -1.90000e-08s, 95% CI: -2.00000e-08s, -1.000000e-08s (±5.000e-09s)
Trimmed mean (5%) of differences: -1.38332e-08s, 95% CI: -2.02997e-08s, -7.578911e-09s (±6.360e-09s)
Trimmed mean (25%) of differences: -1.68099e-08s, 95% CI: -2.17857e-08s, -1.185134e-08s (±4.967e-09s)
Trimmed mean (45%) of differences: -1.55797e-08s, 95% CI: -1.82030e-08s, -1.287140e-08s (±2.666e-09s)
Trimean of differences: -1.62500e-08s, 95% CI: -2.00000e-08s, -1.000000e-08s (±5.000e-09s)
For detailed report see /tmp/test-passwd-guess.py_v1_1697386248/report.csv

And a graph like this:

Does that mean that all letters are valid? No. Since the script uses ‘a’ as the baseline (class 0) and as the placebo/canary probe (class 1), and in the graph we’re comparing all classes to the baseline, only the canary probe will match it. Which means that the second letter of the password is ‘a’.

Exercises for the reader

We’ve cracked first two letters of the password in mere 20 minutes of machine time despite the side-channel being equivalent to around 75 CPU clock cycles. Given that, you can try few things to have a better feel for the side-channel attacks:

Try to set this setup yourself, decode remaining letters of the password. As I wrote, the only special thing you need to do, is have the permission to execute tcpdump, any other configuration will just require fewer connections.

Take the server application and execute it at a different system: either connected to the same network switch or few network hops away (use the -h option of the script to specify a remote host). How does the size of the sample necessary to detect side-channel change?

Look at the statistical results of the sign test and Wilcoxon signed-rank test in the report.csv file. How do they correlate with the graphs? Note: keep in mind Bonferroni correction.

Run the server on a specific CPU core together with some other heavy load (like sha1sum /dev/zero). Does that hide the side channel?

Try to modify the server code so that it is processing the password in side-channel free way.

Experiment with adding random delay to processing. Why that doesn’t help to hide the side-channel signal?

Theoretical background

To be able to use statistical tests reliably, the collected data needs to meet few criteria. Typically the tests require the the measurements are independent and identically distributed (IID). If that property isn’t satisfied, then the tests will be unreliable, in either direction: depending on the kind of lack of independence the test may report difference when there isn’t one in reality or the test may not detect a difference despite there being a significant one.

Given that the measurements from timing data will be autocorrelated, the tests used must be able to handle this kind of data. The autocorrelation is caused by the inherent way that modern computers work: the fluctuations in CPU frequency as it boosts depending on its temperature, the general power state of the machine and the OS, etc. Thankfully, the fix is relatively simple: instead of collecting data from one kind of input, then for another input, and finally comparing those two distributions with each other, we perform tests on pairwise differences. As the name suggest, to perform this kind of tests, we execute the inputs in random order, but in pairs (or larger tuples), calculate the difference between them, and then perform analysis on the distribution of those differences. The most basic tests that work in this way are the box test and the Wilcoxon signed-rank test. Tests that can work on longer tuples are the Friedman tests and rANOVA (though rANOVA expects normally distributed data, which typically timing data doesn’t follow).

By running the tests with data classes in random order we also ensure one more thing: the code executed right before the code we’re interested in will be random, and what’s even more important, with the same distribution for each input. Thus, we will be able to compare those results even to very small differences (single clock cycles).

That also means that the test harness needs to behave in a side-channel free manner, as otherwise the system state before test execution will be correlated with the probe and thus will show up as signal in the system under test. Consider a pathologic example: a test harness is sending three exact same messages, let’s call them A, B, and C to the server. But, just before sending the message C, it flushes the entire CPU cache. In such situation, the server code and runtime data will have to be fetched from main memory instead of the the local cache, making the execution of them appear to take longer. Such a difference will be measurable, and thus will be detected by the statistical tests.

Basic setup

When testing a whole operation (like TLS handshake, or a complete API call), we don’t have to perform anything special to make the test work: we simply measure the time the whole operation took and perform statistical tests on such data.

For majority of tests, making the test harness side-channel free is fairly simple; as long as it can read same-sized byte string from the disk and pass them to the system under test without being impacted by the particular values of the bytes being shuffled around, the whole testing process just need to be performed in two steps. In first step the test data (inputs) are prepared, written in random order to disk, together with its order. In second step, code that’s oblivious to the order of the data, reads same-sized chunks from disk and passes them to the system under test.

Debugging

Unfortunately, when the test of a whole cryptographic operation shows a side channel (e.g. decryption of a message from a PKCS#1 v1.5 ciphertext), we won’t know where the timing signal is created.

To address that, we can employ a little bit of instrumentation together with the bisection strategy. As mentioned in the theory section, code executed before will influence code execute after. Thus, the first step, even if we have a suspicion where the side channel is coming from, is to make sure that any code executed before the code we’re interested in doesn’t contribute to the timing signal.

Example: RSA PKCS#1 v1.5 in TLS

Let’s consider the example of a state of the art implementation of RSA key exchange in TLS. To perform it, the server needs to:

1. Convert the ciphertext string into an integer
2. Apply the blinding factor to the ciphertext
3. Calculate a new set of blinding factors
4. Apply the blinding factor the the private exponents in modular exponentiation
5. Calculate the modular exponentiation (ciphertext to the power of private exponent modulo public key)
6. Apply the unblinding factor to the result of exponentiation
7. Convert the result to a byte string to form the plaintext
8. Generate a random 48 byte long key, to be used in case padding checks fail
9. Verify that the padding in the plaintext is correct, that the encrypted message has correct length and that the first two bytes match the TLS version from Client Hello)
10. In case the padding check doesn’t succeed, use the previously generated 48 byte long key
11. Use either the message or the random key in the derivation of the master secret

Obviously, that’s a lot of operations that require a lot of code.

Now, since we can expect that the blinding will use unbiased random numbers, we can assume that all code up until (but excluding) the application of unblinding factor has access only to ciphertext or obfuscated plaintext, the first code that needs to be constant time with respect to the plaintext is the application of the unblinding factor. So, to verify that no code before it has timing leaks, we need to start the measurement right before parsing of the Client Key Exchange message, and stop the measurement right before application of the unblinding factor.

Timing measurement is best done using highest precision and lowest overhead time sources on a particular CPU. For x86_64 platform, that’s the TSC register. Since we want to reduce the effect of measurement as much as possible, for situations like TLS implementations, it’s best to save those start and stop values of the TSC in global variables, and then write the difference between them to a file (as those 8 bytes) after connection shutdown. Tlsfuzzer scripts execute just one connection at a time, so race conditions shouldn’t be an issue. Such collected timing data can then be converted to format expected by tlsfuzzer analysis script using the extract.py script. The --raw-times, --binary, and -l are the minimum options you will need to use. Using also the --clock-frequency option is likely to make interpretation of any results easier. More information about using the tlsfuzzer scripts is in the project’s documentation.

Once we verify that all the code up to and including modular exponentiation doesn’t leak (by collecting enough data such that the 95% confidence intervals of trimmed means are in the few clock cycles range, i.e. below or around a 1ns), we can then start applying the bisection.

Since we know that the whole operation leaks, and we verified that the code up until application of the blinder doesn’t leak, we can do either of two things. Either apply the bisection blindly and simply measure first half of the remaining code, or consider what’s the most likely next place for the side channel leak. In the latter case, we can measure just the application of the blinder and conversion of the result to a byte string.

If we find that the application of the blinder provides a signal if many (8+) most significant bytes are zero, then the code in question has exact same bug as the OpenSSL CVE-2022-4304 and thus requires similar fix: the multiplication and reduction modulo must be performed in a constant-time fashion with respect to the output.

Crucially, because execution of the earlier code will influence the latter code, there is no point in testing any code after a leaky code is found: because of the side effects of the leaky code, any code after it will appear leaky.

After fixing the bug (or, at least, applying some code fixes), you can run the same timing tests against the particular snippet, or, if you feel optimistic, against the whole operation.

In case the fixed part doesn’t show a side-channel any more, but the whole operation still shows a side-channel, you simply continue down the list of operations: check the conversion to a byte string, the depadding code, the selection between decrypted message and randomly generated message…

Summary

While using timing data isn’t as precise as formal analysis using tools like ctgrind in locating the exact leaky code, it doesn’t depend on any assumptions in regards to executed instructions (e.g. ctgrind won’t flag division operations that include secret data as inputs, despite most CPUs having variable execution time for the division operation) and it can be performed using very crude methods that will work irrespective of the underlying architecture. By using bisection we can still achieve very similar effect, and find the leaky instructions even inside large and complex code.

The same approach will work with any kind of cryptographic implementations that need to perform operations in constant-time with regards to inputs: other PKI algorithms (ECDSA, FFDH, ECDH) or symmetric encryption (AES) are the obvious candidates.

As those bugs are fixed now, let’s see how to configure Fedora or RHEL (with dracut) and Archlinux (with mkinitcpio) to automatically assemble the MD-RAID on dm-integrity volumes so that the root file system can reside on them.

Word of caution

As we’re modifying disk partitions and completely overwriting them, modifying boot-time configuration and in general performing rather complex and advanced configuration, make sure you have good and current backups of the data you care about!

Basic configuration

First, we need to prepare partitions for the volumes that will be used by dm-integrity. There are no special requirements for them, but it’s a good idea to keep them aligned to 1MiB boundaries. That’s especially important when working with SSDs or with HDDs that have 4KiB native sectors (so called Advanced Format disks). Current versions of tools like parted do that automatically.

As most hard disks do come in 4KiB sector sizes (and future replacements are only more and more likely to be like this), we need to format the partition with a 4096B sector size.

The main feature of dm-integrity is the calculation and verification of checksums, as such we need a checksum that is fast enough. To do a quick benchmark, you may use OpenSSL:

$ openssl speed md5 sha1 sha256 sha512
...
 type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
 md5             165603.90k   373152.90k   664617.35k   816564.66k   871069.01k   882553.30k
 sha1            185971.19k   427639.36k   846229.23k  1108107.61k  1228931.51k  1233747.97k
 sha256           99550.05k   219782.83k   413438.72k   517541.21k   556638.21k   559961.43k
 sha512           64932.77k   258782.93k   459379.29k   693776.04k   799465.47k   810766.90k

(Technically, we should benchmark the kernel hash performance as that’s what we’ll use, but I didn’t find an easy way to do that. Drop me a line if you know how to do it.)

As I wrote previously, by default dm-integrity uses a crc32 checksum, it’s small and possibly used by the disks themselves to check for read errors, thus we want to use something different. I’ll use SHA-1 in the following examples. You may also have good experience with BLAKE2b-256.

Finally, as the purpose of the checksums is just to detect accidental errors, not malicious changes, we don’t need the full output of the hash function. I’ve selected 8 bytes per sector (see the previous article for reasons why).

Let’s format the partitions (in this example a 4-disk RAID 6 array; switch the sda1, sdb1, sdc1 and sdd1 to the partitions you are actually using).

integritysetup format /dev/sda1 --sector-size 4096 --tag-size 8 --integrity sha1
integritysetup format /dev/sdb1 --sector-size 4096 --tag-size 8 --integrity sha1
integritysetup format /dev/sdc1 --sector-size 4096 --tag-size 8 --integrity sha1
integritysetup format /dev/sdd1 --sector-size 4096 --tag-size 8 --integrity sha1

This process will run for few hours on a modern multi-terabyte hard-drive so I suggest running them in parallel.

Once the devices are formatted we need to open them. Note: as the integritysetup superblock doesn’t save the algorithm used to calculate the checksums, you need to specify the --integrity option every time you open the device!

integritysetup open /dev/sda1 int1 -I sha1
integritysetup open /dev/sdb1 int2 -I sha1
integritysetup open /dev/sdc1 int3 -I sha1
integritysetup open /dev/sdd1 int4 -I sha1

This will create 4 block devices in the /dev/mapper directory named int1, int2, int3 and int4 (you can use other names too, like int-sda1 or such).

Opening the devices during boot

There are no ready to use standards to mount the dm-integrity volumes on boot so we need to modify the initramfs used by kernel to mount them ourselves.

Fedora

Fedora for a long time now has been using the dracut initramfs. It’s also used in RHEL-8 and CentOS 8, so the instructions for them are the same too. I’ve tested it with Fedora 31 and CentOS 8.3

Dracut uses a system of modules which automatically detect if they need to be included in the initramfs or not. After that it uses udev to detect when new devices show up and what to do with them. As such, we need to create a system of files that will automatically detect when the dm-integrity block devices show up and what to do with them (how to name the integrity device and what hash to use).

I’ve created the necessary files in the dracut-dm-integrity project on github.

As instructions in the README.md state, you need to copy the files from scripts directory to the /usr/lib/dracut/modules.d/90integrity directory. After that, edit the integrity-mount.sh to make it mount your integrity volumes. Finally, run dracut -f to include this new module in the initramfs.

Archlinux

Archlinux uses fairly simple system for construction of its initramfs. The modules live in the /usr/lib/initcpio/ directory and are enabled using the /etc/mkinitcpio.conf file.

You can find ready to use scripts in the mkinitcpio-dm-integrity repository.

Don’t forget to run mkinitcpio -P every time you edit /etc/mkinitcpio.conf!

MD-RAID creation

After restarting the system to verify that the devices are automatically opened on startup, we can create an MD RAID array on top of them.

The one special option that is beneficial to the arrays built on top of dm-integrity is specifying the size of chunk. As when writing data to dm-integrity device both the sector with data and the sector with checksums needs to be updated, performing writes large enough to update all checksums in a sector will mean that the sector with checksums doesn’t have to be read first to modify just part of it. In our example, the checksums are 8 bytes large, which means in a 4096 B sector we fit 512 checksums. So a write needs to be a multiple of: 512 (checksums in a sector) * 4096 (sector size) = 2097152 B = 2MiB, to not cause a read-modify-write operation. This option is specified in KiB, by default it’s 512KiB.

To create the MD-RAID use the following command:

mdadm -C /dev/md0 -n 4 -l 6 --chunk 2048 --assume-clean /dev/mapper/int[1234]

Such an MD-RAID will require the usual setup of adding its settings to /etc/mdadm.conf and regenerating the initramfs again:

mdadm --detail --scan >> /etc/mdadm.conf

Usage

Such MD-RAID can be used as usual, as a backing device for a file system or to put the Physical Volume of an LVM2 system. One thing to note is because we created the md-integrity volumes with 4096B sectors, it presents a block device with 4096B native sectors. From what I’ve noticed, ext4 and btrfs don’t mind getting migrated from a 512B sector disk to a 4096B sector disk. The file system that did, is XFS, it refused to mount. If you still need to mount such an fs stored on such an array, you may want to use the dm-ebs module to emulate the 512B sectors. I haven’t tried it though.

If you want to create an XFS that uses such an array (4 disks in RAID 6, with 4KiB sectors and 8 byte checksums), you can use mkfs.xfs -d su=2M,sw=2 /dev/md0 to do so. That being said, with standard MD-RAID, it will automatically detect those settings.

Update 2020-10-03: in the above mkfs.xfs command there was an error, the sw option indicates number of data disks in a stripe. As we’re using RAID 6, we loose two disks to checksums, we’re using 4 disks total, so we’re left with two disks in a stripe

You may be familiar with the following piece of code to implement the constant time comparison function for strings:

def constant_time_compare(val1, val2):
    if len(val1) != len(val2):
        return False
    result = 0
    for x, y in zip(val1, val2):
        result |= x ^ y
    return result == 0

The idea behind this code is to compare all bytes of input using a flag value that will be flipped in any of the comparisons fail. Only when all the bytes were compared, is the ultimate result of the method returned. This is used to thwart attacks that use the time of processing queries to guess secret values.

Unfortunately, because of CPython specifics, this code doesn’t work for its intended purpose.

Sensitive code should always use hmac.compare_digest() method and you should not write code that needs to be side channel secure in Python.

With the tl;dr version out, let’s investigate why.

Timing side channel

Many attacks against cryptographic implementations don’t actually use maths to compromise the systems. The Bleichenbacher Million Messages attack, POODLE and Lucky 13 attacks use some kind of a side channel to guess the contents of encrypted messages, either the timing of responses or contents of responses (different TLS Alert description field values).

Side channel attacks don’t impact only cryptographic protocols, other places where secret values need to be compared to values that are controlled by attacker, like checking password equality, API tokens and HMAC value validation need to be performed in constant time too.

Already back in 00’s, differences in timing as low as 100ns could be distinguished over LAN environment. See research by Crosby at al. in Opportunities And Limits Of Remote Timing Attacks and Brumley and Boneh in Remote TIming Attacks are Practical. Currently we also have to worry about cross VM or cross-process attacks where ability to distinguish between single cycles may be possible.

Measuring timing differences

Let’s see what happens if we use the simple way to compare two strings in python, the == operator.

Benchmarking code:

import perf

setup = """
str_a = b'secret API key'

alt_s = b'XXXXXXXXXXXXXX'

str_b = str_a[:{0}] + alt_s[{0}:]

assert len(str_a) == len(str_b)
"""

fun = """str_a == str_b"""

if __name__ == "__main__":
    total_runs = 128
    runs_per_process = 4
    runner = perf.Runner(values=runs_per_process,
                         warmups=16,
                         processes=total_runs//runs_per_process)
    vals = list(range(14))  # length of str_a
    for delta in vals:
        runner.timeit("eq_cmp delta={0:#04x}".format(delta),
                      fun,
                      setup=setup.format(delta))

Running it will simulate what timings does the attacker see when the difference from the expected value is at different positions in the attacker provided string.

PYTHONHASHSEED=1 python3 timing-eq_cmp-perf.py \
-o timing-eq_cmp-perf-1.py --fast

.................
eq_cmp delta=0x00: Mean +- std dev: 18.4 ns +- 0.0 ns
.................
eq_cmp delta=0x01: Mean +- std dev: 20.8 ns +- 0.0 ns
.................
eq_cmp delta=0x02: Mean +- std dev: 20.8 ns +- 0.0 ns
.................
eq_cmp delta=0x03: Mean +- std dev: 20.8 ns +- 0.0 ns
.................
eq_cmp delta=0x04: Mean +- std dev: 20.8 ns +- 0.0 ns
.................
eq_cmp delta=0x05: Mean +- std dev: 20.8 ns +- 0.0 ns
.................
eq_cmp delta=0x06: Mean +- std dev: 20.8 ns +- 0.0 ns
.................
eq_cmp delta=0x07: Mean +- std dev: 20.8 ns +- 0.0 ns
.................
eq_cmp delta=0x08: Mean +- std dev: 21.3 ns +- 0.0 ns
.................
eq_cmp delta=0x09: Mean +- std dev: 21.3 ns +- 0.0 ns
.................
eq_cmp delta=0x0a: Mean +- std dev: 21.3 ns +- 0.0 ns
.................
eq_cmp delta=0x0b: Mean +- std dev: 21.3 ns +- 0.0 ns
.................
eq_cmp delta=0x0c: Mean +- std dev: 21.3 ns +- 0.0 ns
.................
eq_cmp delta=0x0d: Mean +- std dev: 21.3 ns +- 0.0 ns

Already we can see that the difference in timing when the first different byte is at fist position or the second position is quite huge, looking at a box plot of the specific values makes it quite obvious:

a = read.csv(file="timing-eq_cmp-perf-1.csv", header=FALSE)
data = as.matrix(a)
boxplot(t(data))

Let’s see how does it compare to the "constant_time"_compare. First the code:

import perf

setup = """
def constant_time_compare(val1, val2):
    if len(val1) != len(val2):
        return False
    result = 0
    for x, y in zip(val1, val2):
        result |= x ^ y
    return result == 0

str_a = b'secret API key'

alt_s = b'XXXXXXXXXXXXXX'

str_b = str_a[:{0}] + alt_s[{0}:]

assert len(str_a) == len(str_b)
"""

fun = """constant_time_compare(str_a, str_b)"""

if __name__ == "__main__":
    total_runs = 128
    runs_per_process = 4
    runner = perf.Runner(values=runs_per_process,
                         warmups=16,
                         processes=total_runs//runs_per_process)
    vals = list(range(14))  # length of str_a
    for delta in vals:
        runner.timeit("ct_eq_cmp delta={0:#04x}".format(delta),
                      fun,
                      setup=setup.format(delta))

The test run:

PYTHONHASHSEED=1 python3 timing-ct_eq_cmp-perf.py \
-o timing-ct_eq_cmp-perf-1.json --fast

.................
ct_eq_cmp delta=0x00: Mean +- std dev: 1.36 us +- 0.02 us
.................
ct_eq_cmp delta=0x01: Mean +- std dev: 1.37 us +- 0.01 us
.................
ct_eq_cmp delta=0x02: Mean +- std dev: 1.37 us +- 0.01 us
.................
ct_eq_cmp delta=0x03: Mean +- std dev: 1.37 us +- 0.01 us
.................
ct_eq_cmp delta=0x04: Mean +- std dev: 1.37 us +- 0.01 us
.................
ct_eq_cmp delta=0x05: Mean +- std dev: 1.37 us +- 0.00 us
.................
ct_eq_cmp delta=0x06: Mean +- std dev: 1.36 us +- 0.01 us
.................
ct_eq_cmp delta=0x07: Mean +- std dev: 1.35 us +- 0.01 us
.................
ct_eq_cmp delta=0x08: Mean +- std dev: 1.35 us +- 0.01 us
.................
ct_eq_cmp delta=0x09: Mean +- std dev: 1.34 us +- 0.00 us
.................
ct_eq_cmp delta=0x0a: Mean +- std dev: 1.35 us +- 0.00 us
.................
ct_eq_cmp delta=0x0b: Mean +- std dev: 1.33 us +- 0.01 us
.................
ct_eq_cmp delta=0x0c: Mean +- std dev: 1.33 us +- 0.01 us
.................
ct_eq_cmp delta=0x0d: Mean +- std dev: 1.32 us +- 0.01 us

The results don’t look too bad, but there’s definitely a difference between the first and last one, even accounting for one standard deviation between them. Let’s see the box plot:

a = read.csv(file="timing-ct_eq_cmp-perf-1.csv", header=FALSE)
data = as.matrix(a)
boxplot(t(data))

That doesn’t look good. Indeed, if we compare the distributions for the different delta values using the Kolmogorov–Smirnov test, we’ll see that results for all deltas are statistically different:

a = read.csv(file="timing-ct_eq_cmp-perf-1.csv", header=FALSE)
data = as.matrix(a)
r = c()
for (i in c(1:length(data[,1]))){
  r[i] = ks.test(data[1,], data[i,])$p.value}
which(unlist(r) < 0.05/(length(data1[,1])-1))

 [1]  2  3  4  5  6  7  9 10 11 12 13 14

Which means that the distributions are statistically distinguishable. (The 0.05 p-value is divided by the amount of performed tests because we’re applying the Bonferroni correction)

To make sure, we re-run the test 4 more times and check for correlation between medians (as the distributions are unimodal, median is robust statistic).

require(corrplot)

a = read.csv(file="timing-ct_eq_cmp-perf-1.csv", header=FALSE)
data = as.matrix(a)
vals = cbind(apply(data, 1, median))

for (i in 2:5) {
  name = paste("timing-ct_eq_cmp-perf-", i, ".csv", sep="")
  a = read.csv(file=name, header=FALSE)
  data = as.matrix(a)
  vals = cbind(vals, apply(data, 1, median))
}
corrplot(cor(vals, method="spearman"), method="ellipse")

There is a very strong correlation between all the different runs, so indeed, it does look like the function is leaking timing information.
Note, we’re using the "spearman" correlation statistic as the values are not normally distributed.

Let’s compare it to the hmac.compare_digest() method:

import perf

setup = """
from hmac import compare_digest

str_a = b'secret API key'

str_b = b''.join((str_a[:{0}], b'X' * (14 - {0})))

assert len(str_a) == len(str_b)
assert len(str_a) == 14
"""

fun = """compare_digest(str_a, str_b)"""

if __name__ == "__main__":
    total_runs = 128
    runs_per_process = 4
    runner = perf.Runner(values=runs_per_process,
                         warmups=64,
                         processes=total_runs//runs_per_process)
    vals = list(range(14))  # length of str_a
    for delta in vals:
        runner.timeit("compare_digest delta={0:#04x}".format(delta),
                      fun,
                      setup=setup.format(delta))

PYTHONHASHSEED=1 python3 timing-compare_digest-perf.py \
-o timing-compare_digest-perf-1.json --rigorous

a = read.csv(file="timing-compare_digest-perf-1.csv", header=FALSE)
data = as.matrix(a)
boxplot(t(data))

While there is some difference that depends on where the first differing byte is, there is no difference between first and second byte, and the “step” around 8th byte is only around it (when comparing longer strings, I still see just one step at the beginning and one at the end). I have no good explanation for it. That being said, the difference between medians of the 2nd byte and 11th byte is 0.240 ns, for comparison, one cycle of the CPU (4Ghz) on which the test is running takes 0.250 ns. So I’m assuming that it is not detectable over the network, but may be detectable in cross-VM attacks.

To confirm the results I’ve run the test with simple == for 255 byte long strings and with using the hmac.compare_digest().

Results for ==:

a = read.csv(file="timing-eq_cmp-2-perf-1.csv", header=FALSE)
data = as.matrix(a)
boxplot(t(data))

As expected, obvious steps that are directly dependant on the amount of matching data between the two parameters to the operator.

Results for compare_digest():

a = read.csv(file="timing-compare_digest-8-perf-1.csv", header=FALSE)
data = as.matrix(a)
boxplot(t(data), ylim=c(min(data), quantile(data, 0.99)))

They are quite noisy, but what the grouping around 2.239e-7 hints at (the thick horizontal line comprised of circles), is that the distribution is not unimodal (otherwise the outliers would look like the ones below the boxes). Let’s see what are the counts for different time bins, as in a histogram, in detail:

require("lattice")
a = read.csv(file="timing-compare_digest-8-perf-1.csv", header=FALSE)
data = as.matrix(a)
h <- hist(data, breaks=200,plot=FALSE)
breaks = c(h$breaks)
mids = c(h$mids)
hm <- rbind(hist(data[1,], breaks=breaks, plot=FALSE)$counts)
for (i in c(2:length(data[,1]))) {
  hm <- rbind(hm, hist(data[i,], breaks=breaks, plot=FALSE)$counts)}

d = data.frame(x=rep(seq(1, nrow(hm), length=nrow(hm)), ncol(hm)),
               y=rep(mids, each=nrow(hm)),
               z=c(hm))
levelplot(z~x*y, data=d, xlab="delta", ylab="time (s)",
  ylim=c(min(data), quantile(data, 0.99)))

We can see now, that even though the measurements with delta between 0 and 8 and 249 and 255 look very different on the box plot, it’s more because a third mode was added to them rather than one of the other two was removed. Statistical test confirms this:

a = read.csv(file="timing-compare_digest-8-perf-1.csv", header=FALSE)
data = as.matrix(a)
r = c()
for (i in c(1:length(data[,1]))){
  r[i] = ks.test(data[19,], data[i,])$p.value}
which(unlist(r) < 0.05/nrow(data))

 [1]   1   2   3   4   5   6   7   8  36  37  38  39  41  45  46  49  50  51  52
[20]  53  54 249 250 251 252 253 254 255

(the deltas between 36 and 54 are a fluke that subsequent quick runs didn’t show).

Note about benchmarking

You may have noticed that the data we have collected, has very low amounts of noise. While it is partially the result of use of the perf module instead of the timeit library module, it mostly is the result of careful system configuration.

On the benchamrking system, the following tasks were performed:

• 3rd and 4th core were isolated
• kernel RCU was disabled on the isolated cores
• HyperThreading was disabled in BIOS
• Intel TurboBoost was disabled
• Intel power management was disabled (no C-states or P-states other than C0 were allowed)
• CPU frequency was locked in place to 4Ghz (the nominal for the i7 4970K of the workstation used)
• Decreasing maximum perf probe query rate to 1 per second
• Disabling irqbalance and setting default IRQ affinity to un-isolated cores
• ASRL disabled
• Python hash table seed fixed

Those operations can be performed by:

1. Adding isolcpus=2,3 rcu_nocbs=2,3 processor.max_cstate=1 idle=poll to the kernel command line
2. Disabling HyperThreading in BIOS
3. Running python3 -m perf system tune
4. Disabling ASLR by running echo 0 > /proc/sys/kernel/randomize_va_space
5. exporting the PYTHONSEED environment variable

Documentation of the perf module provides most of the explanations of the particular options, but we diverge in two places: ASLR and Python hash seed. The purpose of the perf module is to test the overall performance of a piece of Python code (and compare it to either compilation or different implementation). Because Python is a language than answers the question “what if everything was a hash table” ;), that means the names of variables, memory positions of variables or code, number of variables, and particular hash table key have significant impact on performance. But, because we are interested if an attacker is able to tell behaviour of code between two different inputs, and those two inputs will likely be processed by the same process, both the ASLR seed and the Python hash table seeds will be constant from the point of view of the attacker. To speed up finding the expected value for particular inputs I thus opted out of those randomisation mechanisms.

Expectations of behaviour

You may wonder, why is the Python code so unstable, so data dependant, if the implementation of hmac.compare_digest() is doing exactly the same thing (xor-ing the values together and then or-ing result with a guard variable)? The problem stems from the fact that the Python int and C unsigned char are vastly different data types – one is used for arbitrary precision arithmetic while the other can store just 256 unique values. Thus, even such simple operations like xor or or with two small integers are data dependant in Python.

Let’s see how much time does the Python VM need for those two small integers. (Unfortunately, it looks like perf uses the slow json module, and because it exports results after every loop iteration, after few hundred results, the export takes more time than benchmarking. To make it fast enough, and not waste few days on exporting the same data over and over again, we will use timeit module.)

Script:

import timeit
import sys
import math

setup = """
val_a = {0}

val_b = {1}
"""

fun = """val_a ^ val_b"""

def std_dev(vals):
    avg = sum(vals)/len(vals)
    sum_sq = sum((i - avg)**2 for i in vals)
    return math.sqrt(sum_sq / (len(vals) - 1))

if __name__ == "__main__":
    total_runs = 20
    runs_per_process = 3
    warmups = 16

    runner = timeit.Timer(fun, setup=setup.format(0, 0))
    number, delay = runner.autorange()
    number //= 2
    delay /= 2

    print(("will do {0} iterations per process, "
           "expecting {1:7.2} s per process")
          .format(number, delay), file=sys.stderr)
    print("warmups:", file=sys.stderr, end='')
    sys.stderr.flush()
    for _ in range(warmups):
        timeit.repeat(fun, setup=setup.format(0, 0), repeat=1,
                      number=number)
        print(".", file=sys.stderr, end='')
        sys.stderr.flush()
    print(file=sys.stderr)

    for a in range(256):
        for b in range(256):
            res = []
            for _ in range(total_runs // runs_per_process):
                # drop the first result as a local warmup
                res.extend(i / number for i in
                           timeit.repeat(fun,
                                         setup=setup.format(a, b),
                                         repeat=runs_per_process + 1,
                                         number=number)[1:])
                print(".", file=sys.stderr, end='')
                sys.stderr.flush()
                if std_dev(res)  timing-xor-2-timeit-1.csv

require("lattice")
a = read.csv(file="timing-xor-2-timeit-1.csv",
             header=FALSE, col.names=seq(1, 20),
             fill=TRUE)
data = as.matrix(a)
med = apply(data, 1, median, na.rm=TRUE)
# full lines
len = length(med)
columns = ceiling(length(med) / 256)
d = data.frame(x=rep(seq(0, 255), length.out=len, 256),
               y=rep(seq(0, 255), length.out=len, each=256),
               z=med)
my.at = seq(min(med), max(med), length=40)
levelplot(z~x*y, data=d, xlab="b", ylab="a",
          at=my.at, aspects="iso",
          colorkey=list(at=my.at, labels=list(at=my.at)))

While there few repeating patterns, there are 4 things that are of particular importance – behaviour when the two numbers are equal (the lighter diagonal), when both are zero, or when one of the operands is zero. The difference between the background and the diagonal is small, just 0.555 ns, but that translates to about 2 cycles at 4GHz. The difference between the 0, 0 and the backgrounds is even smaller, just 0.114 ns, so half a cycle. The difference between the background and the situations when the second variable is non-zero is about 2.24 ns which translates to about 9 cycles. When the first variable is non-zero and the second is, the difference is about 1.39 ns which is about 6 cycles. Here’s the zoomed in part of the graph for the small numbers:

The binary or operator is similarly dependant on values of parameters:

Both of those things put together mean that using the supposedly constant time compare doesn’t actually protect against timing attacks, but rather makes them easier. The strength of the signal for different inputs is about 100 time stronger, likely allowing them even over Internet, not only over LAN (as is the case for == operator).

Anything else?

Because I started looking into those microbenchmarks to verify the “constant” time CBC MAC and pad check from tlslite-ng, needed to protect against Lucky 13 (see the very extensive article by Adam Langley on the topic), I’ve also checked if it is possible to speed up the process of hashing data. Because on the Python level we don’t have the luxury of access to lower level hash APIs, as the developers of OpenSSL have, to implement the CBC check, I wrote code that in fact calculates 256 different hmacs for every record that contains at least 256 bytes of data + padding. That means that for every record processed, the client and server actually process 64 KiB of additional data. In theory (that is, if the hmac itself is constant time), we could speed the process of checking the mac and de-padding in TLS dramatically, if we could hash the data just once, as OpenSSL is doing in its TLS implementation. You may say, “but hashes are implemented in C, surely they are constant time!”. To which I’ll answer, “what did we say about trusting assumptions?”.

Let’s see how our assumptions hold. First code that hashes all of provided data, but returns also a hash from the “middle” of data (in a TLS implementation that would be the real HMAC that we need to compare to the one from record):

import perf

setup = """
import hmac
from hashlib import sha1

def fun(digest, data, split):
    digest.update(data[:split])
    ret = digest.copy().digest()
    digest.update(data[split:])
    return ret, digest.digest()

str_a = memoryview(b'X'*256)
key = b'a' * 32

val_b = {0}

mac = hmac.new(key, digestmod=sha1)
"""

fun = """fun(mac.copy(), str_a, val_b)"""

if __name__ == "__main__":
    total_runs = 128
    runs_per_process = 4
    runner = perf.Runner(values=runs_per_process,
                         warmups=16,
                         processes=total_runs//runs_per_process)
    vals = list(range(256))  # length of str_a
    for delta in vals:
        runner.timeit("hmac split delta={0:#04x}".format(delta),
                      fun,
                      setup=setup.format(delta))

Command to gather the statistics:

PYTHONHASHSEED=1 python3 timing-hmac-split-perf.py \
-o timing-hmac-split-perf-1.json

And a way to visualise them:

require("lattice")
a = read.csv(file="timing-hmac-split-perf-1.csv", header=FALSE)
data = as.matrix(a)
h <- hist(data, breaks=200,plot=FALSE)
breaks = c(h$breaks)
mids = c(h$mids)
hm <- rbind(hist(data[1,], breaks=breaks, plot=FALSE)$counts)
for (i in c(2:length(data[,1]))) {
  hm <- rbind(hm, hist(data[i,], breaks=breaks, plot=FALSE)$counts)}

d = data.frame(x=rep(seq(1, nrow(hm), length=nrow(hm)), ncol(hm)),
               y=rep(mids, each=nrow(hm)),
               z=c(hm))
levelplot(z~x*y, data=d, xlab="delta", ylab="time (s)",
  ylim=c(min(data), quantile(data, 0.99)))

Besides the obvious peaks since 56th to 64th byte every 64 bytes (caused by an additional hash block that had to be padded to calculate the intermediate HMAC), there is also a dip for the first byte of the 64 byte block and a second dip for bytes between 20 and 55 of every block. Finally, when the split is about even (in that the intermediate hash is calculated over the first 120 bytes), the whole operation takes measurably longer. In short, if the position of the intermediate hash comes from the last byte of encrypted data (as it does in TLS), calculating HMAC like this has a definite sidechannel leak.

To confirm, let’s perform Kolomogorov-Smirnov test:

a = read.csv(file="timing-hmac-split-perf-1.csv", header=FALSE)
data = as.matrix(a)
r=c()
for (i in c(1:nrow(data))){
   r[i] = ks.test(data[2,], data[i,])$p.value}
which(unlist(r) < 0.05/(nrow(normalised)-1))

(we’re testing against second row as the first row (for delta of 0) is obviously different from the others so all tests failing wouldn’t be unexpected)

  [1]   1  21  23  26  44  57  58  59  60  61  62  63  64  69  71  75  77  78
 [19]  80  81  82  83  92  93  94  95  96  98  99 100 103 104 109 114 118 121
 [37] 122 123 124 125 126 127 128 130 131 132 133 134 135 136 137 138 139 140
 [55] 141 142 143 144 145 146 147 160 161 163 165 169 170 171 172 173 174 175
 [73] 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 215
 [91] 217 218 249 250 251 252 253 254 255 256

Quite obviously different, even with just 128 samples per delta value.

Summary

Moral of the story is, don’t use something without testing if it behaves as it claims to. If it does have tests, verify that they check your expectations, not only the programmers that wrote it in the first place.

State your assumptions and test them. If values look similar, measure them multiple times, and use statistical methods to compare them.

Test setup

Tests were performed, as previously mentioned, on an Intel i7 4790K CPU. The system was running Linux 4.17.5-1-ARCH with Python 3.6.6-1 and perf 1.5.1 from Archlinux.

Conversion from json files to csv files was performed using json-to-csv.py script available at the testing repo, together with raw results, at github.

Post scriptum

Other operations on integers, including equality are also not constant time:

import timeit
import sys
import math

setup = """
val_a = {0}

val_b = {1}
"""

fun = """val_a == val_b"""

def std_dev(vals):
    avg = sum(vals)/len(vals)
    sum_sq = sum((i - avg)**2 for i in vals)
    return math.sqrt(sum_sq / (len(vals) - 1))

if __name__ == "__main__":
    total_runs = 3
    runs_per_process = 3
    warmups = 16

    runner = timeit.Timer(fun, setup=setup.format(0, 0))
    number, delay = runner.autorange()
    number //= 100
    delay /= 100

    print("will do {0} iterations per process, "
          "expecting {1:7.2} s per process"
          .format(number, delay), file=sys.stderr)
    print("warmups:", file=sys.stderr, end='')
    sys.stderr.flush()
    for _ in range(warmups):
        timeit.repeat(fun, setup=setup.format(0, 0), repeat=1,
                      number=number)
        print(".", file=sys.stderr, end='')
        sys.stderr.flush()
    print(file=sys.stderr)

    for a in range(256):
        for b in range(256):
            res = []
            for _ in range(total_runs // runs_per_process):
                # drop the first result as a local warmup
                res.extend(i / number for i in
                           timeit.repeat(fun,
                                         setup=setup.format(a, b),
                                         repeat=runs_per_process+1,
                                         number=number)[1:])
                print(".", file=sys.stderr, end='')
                sys.stderr.flush()
                if std_dev(res)  timing-eq-timeit-1.csv

Execution:

PYTHONHASHSEED=1 taskset -c 2 python3 \
-u timing-eq-timeit.py > timing-eq-timeit-1.csv

Code to create the graph:

require("lattice")
a = read.csv(file="timing-eq-timeit-1.csv", header=FALSE,
             col.names=seq(1, 20), fill=TRUE)
data = as.matrix(a)
med = apply(data, 1, median, na.rm=TRUE)
# full lines
len = length(med)
columns = ceiling(length(med) / 256)
d = data.frame(x=rep(seq(0, 255), length.out=len, 256),
               y=rep(seq(0, 255), length.out=len, each=256),
               z=med)
my.at = seq(min(med), max(med), length=40)
levelplot(z~x*y, data=d, xlab="b", ylab="a",
          at=my.at, colorkey=list(at=my.at, labels=list(at=my.at)))

So it looks to me like the xor operation is actually one of the more constant time primitives…

RAID, or as it is less well known, Redundant Array of Independent Disks is a way to make the stored data more resilient against disk failure. Unfortunately it does not work against silent data corruption, which in studies from CERN were present in the 10^-7 range, other studies have also shown non-negligible rates of data corruption.

You may say, OK, I understand fixing it doesn’t work for RAID 1 with just two copies, or with RAID 5, as you don’t know which data is correct – as any one of them can be – surely the system is more clever if it has RAID 6 or 3 drives in RAID! Again, unfortunately it isn’t so. Careful reading of the md(4) man page will reveal this fragment:

If check was used, then no action is taken to handle the mismatch, it is simply recorded. If repair was used, then a mismatch will be repaired in the same way that resync repairs arrays. For RAID5/RAID6 new parity blocks are written. For RAID1/RAID10, all but one block are overwritten with the content of that one block.

In other words, the RAID depends on the disks telling the truth: if it can’t read data, it needs to return I/O error, not return garbage. But as we’ve established, this isn’t the way disks behave.

Now you may say, but I use disk encryption! Surely encryption will detect this data modification and prevent use of damaged/changed data! Again, this is not the property of either AES in XTS mode or in CBC mode – the standard modes of encryption for disk drives – those are so-called malleable encryption modes. There is no way to detect ciphertext modification for them in general case.

This was one of the main reasons behind Btrfs and ZFS; checksumming all data and metadata so that detection of such incorrect blocks could be possible (so that at the very least this corruption is detected and doesn’t reach the application) and with addition of the in-build RAID levels, also corrected.

What if you don’t want to (or likely can’t, in case of ZFS) use either of them? Until recently, there was not much you could do. Introduction of the dm-integrity target has changed that though.

Using dm-integrity in LUKS

dm-integrity target is best integrated with LUKS disk encryption.

To enable it, the device needs to be formatted as a LUKS2 device, and integrity mechanism needs to be specified:

cryptsetup luksFormat --type luks2 --integrity hmac-sha256 \
--sector-size 4096 /dev/example/ciphertext

(Other options include --integrity hmac-sha512 and --cipher chacha20-random --integrity poly1305. Smaller tags will be discussed below)

which then can be opened as a regular LUKS device:

cryptsetup open --type luks /dev/example/ciphertext plaintext

This will create a /dev/mapper/plaintext device that is encrypted and integrity protected.
And the /dev/mapper/plaintext_dif that provides storage for authentication tags.

Note that the integrity device will report (none) as the integrity mechanism:

integritysetup status plaintext_dif

/dev/mapper/plaintext_dif is active and is in use.
type:    INTEGRITY
tag size: 32
integrity: (none)
device:  /dev/mapper/example-ciphertext
sector size:  4096 bytes
interleave sectors: 32768
size:    2056456 sectors
mode:    read/write
journal size: 8380416 bytes
journal watermark: 50%
journal commit time: 10000 ms

This is expected, as LUKS passes the encryption tags from a higher level and dm-integrity is only used to store them. This can be verified with cryptsetup:

cryptsetup status /dev/mapper/plaintext

/dev/mapper/plaintext is active.
type:    LUKS2
cipher:  aes-xts-plain64
keysize: 512 bits
key location: keyring
integrity: hmac(sha256)
integrity keysize: 256 bits
device:  /dev/mapper/example-ciphertext
sector size:  4096
offset:  0 sectors
size:    2056456 sectors
mode:    read/write

The device can be removed (while preserving data, but making it inaccessible without providing password again) using cryptsetup:

cryptsetup close /dev/mapper/plaintext

Testing

To test if the verification works correctly, first let’s verify that the whole device is readable:

dd if=/dev/mapper/plaintext of=/dev/null bs=$((4096*256)) \
status=progress

988807168 bytes (989 MB, 943 MiB) copied, 6 s, 165 MB/s
1004+1 records in
1004+1 records out
1052905472 bytes (1.1 GB, 1004 MiB) copied, 6.28939 s, 167 MB/s

Now, let’s close the device and check if the block looks random, and overwrite it:

cryptsetup close /dev/mapper/plaintext
dd if=/dev/example/ciphertext bs=4096 skip=$((512*1024*1024/4096)) \
count=1 status=none | hexdump -C | head

00000000  70 a1 1d f7 da ae 04 d2  d5 f1 ed 6e ba 96 81 7a  |p..........n...z|
00000010  90 c9 7c e7 01 95 2b 12  ed fc 46 fb 0c d7 24 dd  |..|...+...F...$.|
00000020  48 a2 17 7a 17 9f 26 d8  ef ca 97 74 6e 56 2b 55  |H..z..&....tnV+U|
00000030  59 60 6c 72 e1 5d 14 b3  00 f9 70 e8 f3 31 5e 6f  |Y`lr.]....p..1^o|
00000040  c7 98 c8 e0 e0 f6 52 d3  36 07 34 93 59 42 98 12  |......R.6.4.YB..|
00000050  a8 44 f4 fa 13 94 d6 30  5d 88 ee 79 4c 99 7a a8  |.D.....0]..yL.z.|
00000060  cd 35 87 52 07 66 74 68  9e 61 2e 26 c3 74 67 91  |.5.R.fth.a.&.tg.|
00000070  33 57 21 61 44 b4 2e 31  a6 61 90 3f 04 d9 5e f3  |3W!aD..1.a.?..^.|
00000080  46 dc 2c c5 cb 50 1a b4  3a b5 4d 4d ee d3 0f fd  |F.,..P..:.MM....|
00000090  be 6c 5f 3a b6 f9 b3 f3  21 ac 6b cf dd f0 2e 3b  |.l_:....!.k....;|

Yep, looks random (and will look different for every newly formatted LUKS volume).

dd if=/dev/zero of=/dev/example/ciphertext bs=4096 \
seek=$((512*1024*1024/4096)) count=1
dd if=/dev/example/ciphertext bs=4096 skip=$((512*1024*1024/4096)) \
count=1 status=none | hexdump -C | head

00000000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00001000

Not any more.

What happens when we try to read it now?

cryptsetup open --type luks /dev/example/ciphertext plaintext
dd if=/dev/mapper/plaintext of=/dev/null bs=$((4096*256)) \
status=progress

464519168 bytes (465 MB, 443 MiB) copied, 2 s, 232 MB/s
dd: error reading '/dev/mapper/example': Input/output error
496+1 records in
496+1 records out
520097792 bytes (520 MB, 496 MiB) copied, 2.43931 s, 213 MB/s

Exactly as expected, after reading about 0.5GiB of data, we get an I/O error.
(Re-writing the sector will cause checksum recalculation and will clear the error.)

Repeating the experiment without --integrity is left as an exercise for the reader

Standalone dm-integrity setup

By default, integritysetup will use crc32 which is quite fast and small (requiring just 4 bytes per block). This gives probability of random corruption not being detected of about (as the value of the CRC and the data will be independently selected). Please remember that this is on top of the silent corruption of the hard drive; i.e. if the HDD has a probability of returning malformed data of then probability of malformed data reaching upper layer is . There is a hidden assumption in this though – that the malformed data returned by the disk has uniform distribution, I don’t know if that is typical and was unable to find more information on this topic. If it is not uniformly distributed, the failure rate for crc32 may be higher. More research is necessary in this area.

In case that probability is unsatisfactory, it’s possible to use any of the hashes supported by the kernel and listed in the /proc/crypto system file, sha1, sha256, hmac-sha1 and hmac-sha256 being the more interesting ones.

Example configuration would look like this:

integritysetup format --progress-frequency 5 --integrity sha1 \
--tag-size 20 --sector-size 4096 /dev/example/raw-1

Formatted with tag size 20, internal integrity sha1.
Wiping device to initialize integrity checksum.
You can interrupt this by pressing CTRL+c (rest of not wiped device will contain invalid checksum).
Progress:   7.5%, ETA 01:04,   76 MiB written, speed  14.5 MiB/s
Progress:  17.2%, ETA 00:49,  173 MiB written, speed  16.8 MiB/s
Progress:  25.5%, ETA 00:45,  257 MiB written, speed  16.6 MiB/s
Progress:  32.5%, ETA 00:42,  328 MiB written, speed  16.0 MiB/s
Progress:  42.1%, ETA 00:35,  424 MiB written, speed  16.5 MiB/s
Progress:  51.2%, ETA 00:29,  516 MiB written, speed  16.8 MiB/s
Progress:  58.5%, ETA 00:25,  590 MiB written, speed  16.4 MiB/s
Progress:  68.6%, ETA 00:18,  692 MiB written, speed  16.9 MiB/s
Progress:  77.3%, ETA 00:13,  779 MiB written, speed  17.0 MiB/s
Progress:  84.3%, ETA 00:09,  850 MiB written, speed  16.6 MiB/s
Progress:  93.9%, ETA 00:03,  947 MiB written, speed  16.9 MiB/s
Finished, time 00:59.485, 1008 MiB written, speed  16.9 MiB/s

A new device is created with the open subcommand:

integritysetup open --integrity-no-journal --integrity sha1 \
/dev/example/raw-1 integr-1
integritysetup status integr-1

/dev/mapper/integr-1 is active.
type:    INTEGRITY
tag size: 20
integrity: sha1
device:  /dev/mapper/example-raw--1
sector size:  4096 bytes
interleave sectors: 32768
size:    2064688 sectors
mode:    read/write
journal: not active

(note that in line 4 we now have sha1 instead of (none))

If we want to cryptographically verify the integrity of the data, we will need to use an HMAC though.
Setting it up is fairly similar, but will require a key file (note: this key needs to remain secret for the algorithm to be cryptographically secure).

dd if=/dev/urandom of=hmac-key bs=1 count=20 status=none
integritysetup format --progress-frequency 5 --integrity hmac-sha1 \
--tag-size 20 --integrity-key-size 20 --integrity-key-file hmac-key \
--no-wipe --sector-size 4096 /dev/example/raw-1
integritysetup open --integrity-no-journal --integrity hmac-sha1 \
--integrity-key-size 20 --integrity-key-file hmac-key \
/dev/example/raw-1 integr-1
dd if=/dev/zero of=/dev/mapper/integr-1 bs=$((4096*32768))
integritysetup status integr-1

Formatted with tag size 20, internal integrity hmac-sha1.
dd: error writing '/dev/mapper/integr-1': No space left on device
8+0 records in
7+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 9.45404 s, 112 MB/s
/dev/mapper/integr-1 is active.
type:    INTEGRITY
tag size: 20
integrity: hmac(sha1)
device:  /dev/mapper/example-raw--1
sector size:  4096 bytes
interleave sectors: 32768
size:    2064688 sectors
mode:    read/write
journal: not active

(this time I’ve used --no-wipe as dd from /dev/zero is much faster)

Combined mdadm and dm-integrity

Now that we know how to set up dm-integrity devices and that they work as advertised, let’s see if that indeed will prevent silent data corruption and provide automatic recovery with Linux RAID infrastructure.

For this setup I’ll be using files to make it easier to reproduce the results (integritysetup configures loop devices automatically).

RAID 5

Setup

First let’s initialise the dm-integrity targets:

SIZE=$((1024*1024*1024))
COUNT=6
for i in $(seq $COUNT); do
truncate -s $SIZE "raw-$i"
integritysetup format --integrity sha1 --tag-size 16 \
--sector-size 4096 --no-wipe "./raw-$i"
integritysetup open --integrity-no-journal --integrity \
sha1 "./raw-$i" "integr-$i"
dd if=/dev/zero "of=/dev/mapper/integr-$i" bs=$((4096*512)) || :
done

Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-1': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 5.119 s, 207 MB/s
Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-2': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 6.37586 s, 166 MB/s
Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-3': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 6.18465 s, 171 MB/s
Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-4': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 6.32175 s, 167 MB/s
Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-5': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 5.94098 s, 178 MB/s
Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-6': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 6.73871 s, 157 MB/s

Then set up the RAID-5 device and wait for initialisation.

mdadm --create /dev/md/robust -n$COUNT --level=5 \
$(seq --format "/dev/mapper/integr-%.0f" $COUNT)
mdadm --wait /dev/md/robust && echo ready

mdadm: Defaulting to version 1.2 metadata
mdadm: array /dev/md/robust started.
ready

Single failure

To make sure that we do not work from cache, stop the array, clear cache, and then overwrite half of one of the drives:

mdadm --stop /dev/md/robust
integritysetup close integr-1
tr '\000' '\377' < /dev/zero | dd of=raw-1 bs=4096 \
seek=$((SIZE/4096/2)) count=$((SIZE/4096/2-256)) \
conv=notrunc status=progress

mdadm: stopped /dev/md/robust
415428608 bytes (415 MB, 396 MiB) copied, 1 s, 413 MB/s
131008+0 records in
131008+0 records out
536608768 bytes (537 MB, 512 MiB) copied, 1.49256 s, 360 MB/s

(As we’re not encrypting data, the 00’s actually are on the disk, so we need to write something else, 0xff in this case. Also, we’re skipping last 1MiB of data as that’s where RAID superblock lives and recovery of it is a completely different kettle of fish.)

Restart the array:

integritysetup open --integrity-no-journal --integrity \
sha1 "./raw-1" "integr-1"
mdadm --assemble /dev/md/robust $(seq --format \
"/dev/mapper/integr-%.0f" $COUNT)

mdadm: /dev/md/robust has been started with 6 drives.

Verify that all data is readable and that it has expected values (all zero):

hexdump -C /dev/md/robust

00000000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
13ab00000

Additionally you can verify that the errors were reported to the MD layer.
First, run ls -l /dev/md/robust to get to know the number of the md, then use it in the following command instead of 127:

grep . /sys/block/md127/md/dev-*/errors

/sys/block/md127/md/dev-dm-14/errors:867024
/sys/block/md127/md/dev-dm-15/errors:0
/sys/block/md127/md/dev-dm-16/errors:0
/sys/block/md127/md/dev-dm-17/errors:0
/sys/block/md127/md/dev-dm-18/errors:0
/sys/block/md127/md/dev-dm-19/errors:0

Scrub the volume to fix all bad blocks:

mdadm --action=repair /dev/md/robust
mdadm --wait /dev/md/robust && echo ready

ready

And verify that all the incorrect blocks were rewritten/corrected:

dd if=/dev/mapper/integr-1 bs=4096 of=/dev/null status=progress

864800768 bytes (865 MB, 825 MiB) copied, 4 s, 216 MB/s
258086+0 records in
258086+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 4.68922 s, 225 MB/s

Double failure

Let’s see what happens if two drives return I/O error for the same area. Let’s introduce the errors:

mdadm --stop /dev/md/robust
integritysetup close integr-1
integritysetup close integr-2
tr '\000' '\377' < /dev/zero | dd of=raw-1 bs=4096 \
seek=$((SIZE/4096/2)) count=$((100*1025*1024/4096)) \
conv=notrunc status=none
tr '\000' '\377' < /dev/zero | dd of=raw-2 bs=4096 \
seek=$((SIZE/4096/2)) count=$((100*1025*1024/4096)) \
conv=notrunc status=none

mdadm: stopped /dev/md/robust

Then restart the array

integritysetup open --integrity-no-journal --integrity \
sha1 "./raw-1" "integr-1"
integritysetup open --integrity-no-journal --integrity \
sha1 "./raw-2" "integr-2"
mdadm --assemble /dev/md/robust $(seq --format \
"/dev/mapper/integr-%.0f" $COUNT)

mdadm: /dev/md/robust has been started with 6 drives.

Let’s verify:

hexdump -C /dev/md/robust

00000000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
hexdump: /dev/md/robust: Input/output error
9c026000

As expected, we’ve received an I/O error. Additionally if we look at the status of the array, we’ll see that it has become degraded:

Personalities : [raid10] [raid6] [raid5] [raid4]
md127 : active raid5 dm-14[0](F) dm-19[6] dm-18[4] dm-17[3] dm-16[2] dm-15[1]
5155840 blocks super 1.2 level 5, 512k chunk, algorithm 2 [6/5] [_UUUUU]

This is most likely because the kernel will re-try to read the sectors, but if it receives a set number of read errors it cannot correct (see max_read_errors in md directory), it will kick the disk out of the array. Probably suboptimal given this setup – knowing the error came from software not hardware would mean that kicking the disk from the RAID won’t change anything.

Clean-up

mdadm --stop /dev/md/robust
for i in $(seq $COUNT); do
integritysetup close "integr-$i"
done

RAID 6

Let’s now try with RAID 6, that is, with double redundancy.

set-up:

for i in $(seq $COUNT); do
truncate -s $SIZE "raw-$i"
integritysetup format --integrity sha1 --tag-size 16 \
--sector-size 4096 --no-wipe "./raw-$i"
integritysetup open --integrity-no-journal --integrity \
sha1 "./raw-$i" "integr-$i"
dd if=/dev/zero "of=/dev/mapper/integr-$i" bs=$((4096*512)) || :
done

Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-1': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 4.8998 s, 216 MB/s
Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-2': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 7.21848 s, 146 MB/s
Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-3': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 7.85458 s, 135 MB/s
Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-4': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 7.48937 s, 141 MB/s
Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-5': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 7.30369 s, 145 MB/s
Formatted with tag size 16, internal integrity sha1.
dd: error writing '/dev/mapper/integr-6': No space left on device
505+0 records in
504+0 records out
1057120256 bytes (1.1 GB, 1008 MiB) copied, 7.05441 s, 150 MB/s

RAID initialization:

mdadm --create /dev/md/robust -n$COUNT --level=6 \
$(seq --format "/dev/mapper/integr-%.0f" $COUNT)
mdadm --wait /dev/md/robust && echo ready

ready

Single failure

mdadm --stop /dev/md/robust
integritysetup close integr-1
tr '\000' '\377' < /dev/zero | dd of=raw-1 bs=4096 \
seek=$((SIZE/4096/2)) count=$((SIZE/4096/2-256)) \
conv=notrunc status=progress

mdadm: stopped /dev/md/robust
415428608 bytes (415 MB, 396 MiB) copied, 1 s, 413 MB/s
131008+0 records in
131008+0 records out
536608768 bytes (537 MB, 512 MiB) copied, 1.49256 s, 360 MB/s

Restart the array:

integritysetup open --integrity-no-journal --integrity \
sha1 "./raw-1" "integr-1"
mdadm --assemble /dev/md/robust $(seq --format \
"/dev/mapper/integr-%.0f" $COUNT)

mdadm: /dev/md/robust has been started with 6 drives.

Verify that all data is readable and that it has expected values (all zero):

hexdump -C /dev/md/robust

00000000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
fbc00000

Good. And let’s check the status of the array:

Personalities : [raid10] [raid6] [raid5] [raid4]
md127 : active raid6 dm-19[5] dm-18[4] dm-17[3] dm-16[2] dm-15[1] dm-14[0](F)
4124672 blocks super 1.2 level 6, 512k chunk, algorithm 2 [6/5] [_UUUUU]

Not good, looks like the raid6 target has a different way of handling I/O errors than the raid5 one and even if the failures are correctible, the array is degraded.

Double failure

Faults introduction:

mdadm --stop /dev/md/robust
integritysetup close integr-1
integritysetup close integr-2
tr '\000' '\377' < /dev/zero | dd of=raw-1 bs=4096 \
seek=$((SIZE/4096/2)) count=$((100*1025*1024/4096)) \
conv=notrunc status=none
tr '\000' '\377' < /dev/zero | dd of=raw-2 bs=4096 \
seek=$((SIZE/4096/2)) count=$((100*1025*1024/4096)) \
conv=notrunc status=none

mdadm: stopped /dev/md/robust

Restart:

integritysetup open --integrity-no-journal --integrity \
sha1 "./raw-1" "integr-1"
integritysetup open --integrity-no-journal --integrity \
sha1 "./raw-2" "integr-2"
mdadm --assemble /dev/md/robust $(seq --format \
"/dev/mapper/integr-%.0f" $COUNT)

mdadm: /dev/md/robust has been started with 6 drives.

Verify:

hexdump -C /dev/md/robust

00000000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
fbc00000

so far so good

Personalities : [raid10] [raid6] [raid5] [raid4]
md127 : active raid6 dm-14[0](F) dm-19[5] dm-18[4] dm-17[3] dm-16[2] dm-15[1](F)
4124672 blocks super 1.2 level 6, 512k chunk, algorithm 2 [6/4] [__UUUU]

not so good, both disks were marked as faulty in the array…

Clean-up

mdadm --stop /dev/md/robust
for i in $(seq $COUNT); do
integritysetup close "integr-$i"
rm "raw-$i"
done

Summary

While the functionality necessary to provide detection and correction of silent data corruption is available in the Linux kernel, the implementation likely will need few tweaks to not excerbate situations where the hardware is physically failing, not just returning garbage. Passing additional metadata about the I/O errors from the dm-integrity layer to the md layer could be a potential solution.

Update: This bug has been fixed in the upstream code in September 2019.

Also, this mechanism comes into play only when the hard drive technically already is failing, so at least you will know about the failure, and really, the failing disk is getting kicked out

Learn more

Data integrity protection with cryptsetup tools presentation by Milan Brož at FOSDEM.

Note: Above tests were performed using 4.16.6-1-ARCH Linux kernel, mdadm 4.0-1 and cryptsetup 2.0.2-1 from ArchLinux.

Diffie-Hellman key agreement

The “classical” Diffie-Hellman key exchange also known as Finite Field Diffie-Hellman uses one type of operation — modular exponentiation — and two secrets for two communication peers to arrive at a single shared secret.

The protocol requires a prime number and a number that is a so-called “generator” number to be known to both peers. This is usually achieved by either the server sending those values to the client (e.g. in TLS before v1.3 or in some SSH key exchange types) or by distributing them ahead of time to the peers (e.g. in IPSec and TLS 1.3).

When both peers know which parameters to use, they generate a random number, perform modular exponentiation with this random number, group generator and prime and send the result to the other party as a “key share”. That other party takes this key share and uses it as the generator to perform modular exponentiation again. The result of that second operation is the agreed key share.

If we define as the generator, as the prime, as the server selected random, as the server key share, as the client selected random and as the client key share, and being the agreed upon secret, the server performs following operations:

Client performs following operation:

Because both parties agree on the same .

Unfortunately both peers need to operate on a value provided by the other party (not necessarily trusted or authenticated) and their secret value at the same time. This calls for the the prime number used to have some special properties.

Modular exponentiation

The basic operation we’ll be dealing with is modular exponentiation. The simple way to explain it is that we take a number, raise it to some power. Then we take that result and divide it by a third number. The remainder of that division is our result.

For 2^10 mod 12, the calculation will go as follows, first exponentiation:

2^10 = 1024

Then division:

1024 = 85*12 + 4

So the result is 4.

One of the interesting properties of modular exponentiation, is that it is cyclic. If we take a base number and start raising it to higher and higher powers, we will be getting the same numbers in the same order:

$ python powmod.py -g 3 -m 14 -e 28
3^0  mod 14 = 1
3^1  mod 14 = 3
3^2  mod 14 = 9
3^3  mod 14 = 13
3^4  mod 14 = 11
3^5  mod 14 = 5
3^6  mod 14 = 1
3^7  mod 14 = 3
3^8  mod 14 = 9
3^9  mod 14 = 13
3^10 mod 14 = 11
3^11 mod 14 = 5
3^12 mod 14 = 1
3^13 mod 14 = 3
3^14 mod 14 = 9
3^15 mod 14 = 13
3^16 mod 14 = 11
3^17 mod 14 = 5
3^18 mod 14 = 1
3^19 mod 14 = 3
3^20 mod 14 = 9
3^21 mod 14 = 13
3^22 mod 14 = 11
3^23 mod 14 = 5
3^24 mod 14 = 1
3^25 mod 14 = 3
3^26 mod 14 = 9
3^27 mod 14 = 13

This comes from the fact that in modulo arithmetic, for addition, subtraction, multiplication and exponentiation, the order in which the modulo operations are made does not matter; a + b mod c is equal to (a mod c + b mod c) mod c. Thus if we try to calculate the example for 3^17 mod 14 we can write it down as ((3^6 mod 14) * (3^6 mod 14) * (3^5 mod 14)) mod 14. Then the calculation is reduced to 1 * 1 * 3^5 mod 14.

The inverse of modular exponentiation is discrete logarithm, in which for a given base and modulus, we look for exponent that will result in given number:

g^x mod m = n

Where g, m and n are given, we’re looking for x.

Because there are no fast algorithms for calculating discrete logarithm, is one of the reasons we can use modulo exponentiation as the base of Diffie-Hellman algorithm.

Cyclic groups

Let’s see what happens if we start calculating results of modular exponentiation for 14 with different bases:

$ python groups.py -m 14
Groups modulo 14
g:  0, [1, 0]
g:  1, [1]
g:  2, [1, 2, 4, 8]
g:  3, [1, 3, 9, 13, 11, 5]
g:  4, [1, 4, 2, 8]
g:  5, [1, 5, 11, 13, 9, 3]
g:  6, [1, 6, 8]
g:  7, [1, 7]
g:  8, [1, 8]
g:  9, [1, 9, 11]
g: 10, [1, 10, 2, 6, 4, 12, 8]
g: 11, [1, 11, 9]
g: 12, [1, 12, 4, 6, 2, 10, 8]
g: 13, [1, 13]

Neither of the numbers can generate all of the numbers that are smaller than the integer we calculate the modulo operation with. In other words, there is no generator (in number theoretic sense) that generates the whole group.

To find such numbers, we need to start looking at prime numbers.

Cyclic groups modulo prime

Let’s see what happens for 13:

$ python groups.py -m 13
Groups modulo 13
g:  0, [1, 0]
g:  1, [1]
g:  2, [1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7]
g:  3, [1, 3, 9]
g:  4, [1, 4, 3, 12, 9, 10]
g:  5, [1, 5, 12, 8]
g:  6, [1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11]
g:  7, [1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2]
g:  8, [1, 8, 12, 5]
g:  9, [1, 9, 3]
g: 10, [1, 10, 9, 12, 3, 4]
g: 11, [1, 11, 4, 5, 3, 7, 12, 2, 9, 8, 10, 6]
g: 12, [1, 12]

The obvious result is that we now have 4 generators — 2, 6, 7 and 11 generate the whole group.

But there is other result hiding. Let’s see the results for 19, but with sizes of those groups shown:

$ python groups-ann.py -m 19
Groups modulo 19
g:   0, len:   2, [1, 0]
g:   1, len:   1, [1]
g:   2, len:  18, [1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10]
g:   3, len:  18, [1, 3, 9, 8, 5, 15, 7, 2, 6, 18, 16, 10, 11, 14, 4, 12, 17, 13]
g:   4, len:   9, [1, 4, 16, 7, 9, 17, 11, 6, 5]
g:   5, len:   9, [1, 5, 6, 11, 17, 9, 7, 16, 4]
g:   6, len:   9, [1, 6, 17, 7, 4, 5, 11, 9, 16]
g:   7, len:   3, [1, 7, 11]
g:   8, len:   6, [1, 8, 7, 18, 11, 12]
g:   9, len:   9, [1, 9, 5, 7, 6, 16, 11, 4, 17]
g:  10, len:  18, [1, 10, 5, 12, 6, 3, 11, 15, 17, 18, 9, 14, 7, 13, 16, 8, 4, 2]
g:  11, len:   3, [1, 11, 7]
g:  12, len:   6, [1, 12, 11, 18, 7, 8]
g:  13, len:  18, [1, 13, 17, 12, 4, 14, 11, 10, 16, 18, 6, 2, 7, 15, 5, 8, 9, 3]
g:  14, len:  18, [1, 14, 6, 8, 17, 10, 7, 3, 4, 18, 5, 13, 11, 2, 9, 12, 16, 15]
g:  15, len:  18, [1, 15, 16, 12, 9, 2, 11, 13, 5, 18, 4, 3, 7, 10, 17, 8, 6, 14]
g:  16, len:   9, [1, 16, 9, 11, 5, 4, 7, 17, 6]
g:  17, len:   9, [1, 17, 4, 11, 16, 6, 7, 5, 9]
g:  18, len:   2, [1, 18]

Note that all the sizes of those groups are factors of 18 – that is p-1.

The third observation we can draw from those results is that, for any number the size of the group of the generated elements will be at most as large as the size of the base number.

With 19, if we take generator 8, the size of its subgroup is 6. But size of subgroups of 7, 18, 11 and 12 is respectively 3, 2, 3 and 6.

Thus, not only is the subgroup much smaller than the full group, it is also impossible to “escape” from it.

Safe primes

We saw that for primes, some bases are better than others (look into finite fields to learn more).

As we noticed, sizes of all groups are factors of the prime less one (see Fermat’s little theorem for proof of this). Of course, with the exception of 2, all primes are odd numbers, so p-1 will always be divisible by two – it will be a composite number. But q = (p-1)/2 doesn’t have to be composite. Indeed, we call primes for which q is also prime safe primes.

Let’s see what happens if we calculate groups of such a prime:

$ python groups-ann.py -m 23
Group sizes modulo 23
g:   0, len:   2, [1, 0]
g:   1, len:   1, [1]
g:   2, len:  11, [1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12]
g:   3, len:  11, [1, 3, 9, 4, 12, 13, 16, 2, 6, 18, 8]
g:   4, len:  11, [1, 4, 16, 18, 3, 12, 2, 8, 9, 13, 6]
g:   5, len:  22, [1, 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14]
g:   6, len:  11, [1, 6, 13, 9, 8, 2, 12, 3, 18, 16, 4]
g:   7, len:  22, [1, 7, 3, 21, 9, 17, 4, 5, 12, 15, 13, 22, 16, 20, 2, 14, 6, 19, 18, 11, 8, 10]
g:   8, len:  11, [1, 8, 18, 6, 2, 16, 13, 12, 4, 9, 3]
g:   9, len:  11, [1, 9, 12, 16, 6, 8, 3, 4, 13, 2, 18]
g:  10, len:  22, [1, 10, 8, 11, 18, 19, 6, 14, 2, 20, 16, 22, 13, 15, 12, 5, 4, 17, 9, 21, 3, 7]
g:  11, len:  22, [1, 11, 6, 20, 13, 5, 9, 7, 8, 19, 2, 22, 12, 17, 3, 10, 18, 14, 16, 15, 4, 21]
g:  12, len:  11, [1, 12, 6, 3, 13, 18, 9, 16, 8, 4, 2]
g:  13, len:  11, [1, 13, 8, 12, 18, 4, 6, 9, 2, 3, 16]
g:  14, len:  22, [1, 14, 12, 7, 6, 15, 3, 19, 13, 21, 18, 22, 9, 11, 16, 17, 8, 20, 4, 10, 2, 5]
g:  15, len:  22, [1, 15, 18, 17, 2, 7, 13, 11, 4, 14, 3, 22, 8, 5, 6, 21, 16, 10, 12, 19, 9, 20]
g:  16, len:  11, [1, 16, 3, 2, 9, 6, 4, 18, 12, 8, 13]
g:  17, len:  22, [1, 17, 13, 14, 8, 21, 12, 20, 18, 7, 4, 22, 6, 10, 9, 15, 2, 11, 3, 5, 16, 19]
g:  18, len:  11, [1, 18, 2, 13, 4, 3, 8, 6, 16, 12, 9]
g:  19, len:  22, [1, 19, 16, 5, 3, 11, 2, 15, 9, 10, 6, 22, 4, 7, 18, 20, 12, 21, 8, 14, 13, 17]
g:  20, len:  22, [1, 20, 9, 19, 12, 10, 16, 21, 6, 5, 8, 22, 3, 14, 4, 11, 13, 7, 2, 17, 18, 15]
g:  21, len:  22, [1, 21, 4, 15, 16, 14, 18, 10, 3, 17, 12, 22, 2, 19, 8, 7, 9, 5, 13, 20, 6, 11]
g:  22, len:   2, [1, 22]

The groups look very different to the ones we saw previously, with the exception of bases 0, 1 and p-1, all groups are relatively large – 11 or 22 elements.

One interesting observation we can make about bases that have group order of 2q, is that even exponents will remain in a group of size 2q while odd will move to a group with order of q. Thus we can say that use of generator that is part of group order of 2q will leak the least significant bit of the exponent.

That’s why protecting against small subgroup attacks with safe primes is so easy, it requires comparing the peer’s key share against just 3 numbers. It’s also the reason why it’s impossible to “backdoor” the parameters (prime and generator), as every generator is a good generator.

Scan performed between 11th of January and 4th of March 2017.

Scan performed between 6th of December 2016 and 3rd of January 2017.

Scan performed between 24th of October and 28th of November 2016.

SSL/TLS survey of 617341 websites from Alexa's top 1 million
Stats only from connections that did provide valid certificates
(or anonymous DH from servers that do also have valid certificate installed)


Supported Ciphers         Count     Percent
-------------------------+---------+-------
3DES                      530948    86.0056
3DES Only                 458       0.0742
3DES Preferred            1424      0.2307
3DES forced in TLS1.1+    874       0.1416
AES                       613965    99.4531
AES Only                  53257     8.6268
AES-CBC                   613426    99.3658
AES-CBC Only              4167      0.675
AES-GCM                   534925    86.6498
AES-GCM Only              502       0.0813
CAMELLIA                  267704    43.364
CAMELLIA Only             1         0.0002
CHACHA20                  92079     14.9154
CHACHA20 Only             1         0.0002
Insecure                  47164     7.6399
RC4                       141007    22.841
RC4 Only                  89        0.0144
RC4 Preferred             10850     1.7575
RC4 forced in TLS1.1+     5931      0.9607
x:FF 29 3DES Only         499       0.0808
x:FF 29 3DES Preferred    1718      0.2783
x:FF 29 RC4 Only          131       0.0212
x:FF 29 RC4 Preferred     12343     1.9994
x:FF 29 incompatible      493       0.0799
x:FF 35 3DES Only         505       0.0818
x:FF 35 3DES Preferred    1608      0.2605
x:FF 35 RC4 Only          147       0.0238
x:FF 35 RC4 Preferred     12357     2.0016
x:FF 35 incompatible      495       0.0802
x:FF 44 3DES Only         3262      0.5284
x:FF 44 3DES Preferred    6200      1.0043
x:FF 44 incompatible      642       0.104
y:DHE-RSA-SEED-SHA        77072     12.4845
y:IDEA-CBC-SHA            76282     12.3565
y:SEED-SHA                91038     14.7468
z:ADH-AES128-GCM-SHA256   420       0.068
z:ADH-AES128-SHA          636       0.103
z:ADH-AES128-SHA256       275       0.0445
z:ADH-AES256-GCM-SHA384   432       0.07
z:ADH-AES256-SHA          675       0.1093
z:ADH-AES256-SHA256       276       0.0447
z:ADH-CAMELLIA128-SHA     327       0.053
z:ADH-CAMELLIA256-SHA     345       0.0559
z:ADH-DES-CBC-SHA         218       0.0353
z:ADH-DES-CBC3-SHA        642       0.104
z:ADH-RC4-MD5             442       0.0716
z:ADH-SEED-SHA            262       0.0424
z:AECDH-AES128-SHA        7916      1.2823
z:AECDH-AES256-SHA        7961      1.2896
z:AECDH-DES-CBC3-SHA      7860      1.2732
z:AECDH-NULL-SHA          51        0.0083
z:AECDH-RC4-SHA           7371      1.194
z:DES-CBC-MD5             5046      0.8174
z:DES-CBC-SHA             29895     4.8425
z:DES-CBC3-MD5            13554     2.1955
z:ECDHE-RSA-NULL-SHA      57        0.0092
z:EDH-RSA-DES-CBC-SHA     25634     4.1523
z:EXP-ADH-DES-CBC-SHA     131       0.0212
z:EXP-ADH-RC4-MD5         130       0.0211
z:EXP-DES-CBC-SHA         8638      1.3992
z:EXP-EDH-RSA-DES-CBC-SHA 6804      1.1021
z:EXP-RC2-CBC-MD5         10304     1.6691
z:EXP-RC4-MD5             10764     1.7436
z:EXP1024-DES-CBC-SHA     2644      0.4283
z:EXP1024-RC4-SHA         2694      0.4364
z:IDEA-CBC-MD5            1036      0.1678
z:NULL-MD5                174       0.0282
z:NULL-SHA                173       0.028
z:NULL-SHA256             55        0.0089
z:RC2-CBC-MD5             5209      0.8438
z:RC4-64-MD5              550       0.0891

Cipher ordering           Count     Percent
-------------------------+---------+-------
Client side               144584    23.4204
Server side               472757    76.5796

Supported Handshakes      Count     Percent
-------------------------+---------+-------
ADH                       834       0.1351
AECDH                     7967      1.2905
DHE                       341995    55.3981
ECDH                      1         0.0002
ECDHE                     556450    90.1366
ECDHE and DHE             305194    49.4369
RSA                       523699    84.8314

Supported NPN protocols   Count    Percent 
-------------------------+---------+--------
None                      366921    59.4357  
None Only                 366921    59.4357  
h2                        145644    23.5921  
h2 Only                   59        0.0096   
h2-12                     5         0.0008   
h2-14                     2315      0.375    
h2-14 Only                2         0.0003   
h2-16                     65        0.0105   
h2-17                     1150      0.1863   
h2-fb                     42        0.0068   
h2c                       1153      0.1868   
http                      1         0.0002   
http/1                    1         0.0002   
http/1.0                  17848     2.8911   
http/1.1                  250648    40.6012  
http/1.1 Only             79415     12.864   
http1.0                   17        0.0028   
http1.1                   17        0.0028   
https                     1         0.0002   
https Only                1         0.0002   
spdy                      1         0.0002   
spdy/2                    15091     2.4445   
spdy/2 Only               1         0.0002   
spdy/3                    15278     2.4748   
spdy/3.0                  1         0.0002   
spdy/3.1                  110468    17.8942  
spdy/3.1 Only             1         0.0002   
x-mod-spdy/0.9.4.1-0      1         0.0002   
x-mod-spdy/0.9.4.1-146826 71        0.0115   
x-mod-spdy/0.9.4.1-1e75259 2         0.0003   
x-mod-spdy/0.9.4.1-4e5ad45 2         0.0003   
x-mod-spdy/0.9.4.1-51b34c6 1         0.0002   
x-mod-spdy/0.9.4.1-6bd08c0 2         0.0003   
x-mod-spdy/0.9.4.1-ab03b62 1         0.0002   
x-mod-spdy/0.9.4.1-df466c5 1         0.0002   
x-mod-spdy/0.9.4.1-f7ff75d 1         0.0002   
x-mod-spdy/0.9.4.2-146826 84        0.0136   
x-mod-spdy/0.9.4.2-3a57358 3         0.0005   
x-mod-spdy/0.9.4.2-413    8         0.0013   
x-mod-spdy/0.9.4.2-414    1         0.0002   
x-mod-spdy/0.9.4.3-146826 854       0.1383   
x-mod-spdy/0.9.4.3-420    202       0.0327   

Supported PFS             Count     Percent  PFS Percent
-------------------------+---------+--------+-----------
DH,1024bits               108434    17.5647  31.7063
DH,1338bits               1         0.0002   0.0003
DH,2046bits               1         0.0002   0.0003
DH,2048bits               213049    34.5107  62.2959
DH,2049bits               1         0.0002   0.0003
DH,2236bits               91        0.0147   0.0266
DH,2432bits               2         0.0003   0.0006
DH,3072bits               156       0.0253   0.0456
DH,3092bits               1         0.0002   0.0003
DH,4094bits               1         0.0002   0.0003
DH,4096bits               19952     3.2319   5.834
DH,512bits                89        0.0144   0.026
DH,6144bits               1         0.0002   0.0003
DH,768bits                310       0.0502   0.0906
DH,8192bits               5         0.0008   0.0015
ECDH,B-571,570bits        5789      0.9377   1.0403
ECDH,P-192,192bits        82        0.0133   0.0147
ECDH,P-224,224bits        81        0.0131   0.0146
ECDH,P-256,256bits        521108    84.4117  93.6487
ECDH,P-384,384bits        14019     2.2709   2.5194
ECDH,P-521,521bits        17236     2.792    3.0975
Prefer DH,1024bits        37181     6.0228   10.8718
Prefer DH,2048bits        4883      0.791    1.4278
Prefer DH,3072bits        8         0.0013   0.0023
Prefer DH,4096bits        379       0.0614   0.1108
Prefer DH,768bits         33        0.0053   0.0096
Prefer ECDH,B-571,570bits 5568      0.9019   1.0006
Prefer ECDH,P-192,192bits 3         0.0005   0.0005
Prefer ECDH,P-224,224bits 79        0.0128   0.0142
Prefer ECDH,P-256,256bits 489198    79.2428  87.9141
Prefer ECDH,P-384,384bits 11465     1.8572   2.0604
Prefer ECDH,P-521,521bits 16733     2.7105   3.0071
Prefer PFS                565530    91.6074  0
Support PFS               593251    96.0978  0

Supported ECC curves      Count     Percent 
-------------------------+---------+--------
None                      1         0.0002   
None Only                 1         0.0002   
brainpoolP256r1           37819     6.1261   
brainpoolP384r1           37835     6.1287   
brainpoolP512r1           37847     6.1306   
prime192v1                1655      0.2681   
prime256v1                533959    86.4934  
prime256v1 Only           443013    71.7615  
secp160k1                 1531      0.248    
secp160r1                 1545      0.2503   
secp160r2                 1529      0.2477   
secp192k1                 1543      0.2499   
secp224k1                 1614      0.2614   
secp224r1                 5247      0.8499   
secp224r1 Only            2         0.0003   
secp256k1                 40064     6.4898   
secp384r1                 99404     16.102   
secp384r1 Only            7234      1.1718   
secp521r1                 69486     11.2557  
secp521r1 Only            145       0.0235   
sect163k1                 1531      0.248    
sect163k1 Only            3         0.0005   
sect163r1                 1530      0.2478   
sect163r2                 1530      0.2478   
sect193r1                 1530      0.2478   
sect193r2                 1530      0.2478   
sect233k1                 1606      0.2601   
sect233r1                 1606      0.2601   
sect239k1                 1606      0.2601   
sect283k1                 39167     6.3445   
sect283k1 Only            1         0.0002   
sect283r1                 39164     6.344    
sect409k1                 39168     6.3446   
sect409r1                 39167     6.3445   
sect571k1                 39169     6.3448   
sect571r1                 39174     6.3456   
sect571r1 Only            2         0.0003   
server                    38749     6.2768   
server Only               38749     6.2768   

Unsupported curve fallback     Count     Percent 
------------------------------+---------+--------
False                          556236    90.1019  
unknown                        61105     9.8981   

ECC curve ordering        Count     Percent 
-------------------------+---------+--------
                          37735     6.1125   
client                    18709     3.0306   
server                    500010    80.9941  
unknown                   60887     9.8628   

TLSv1.2 PFS supported sigalgs  Count     Percent 
------------------------------+---------+--------
ECDSA-SHA1                     60396     9.7832   
ECDSA-SHA1 Only                4         0.0006   
ECDSA-SHA224                   60341     9.7743   
ECDSA-SHA256                   79253     12.8378  
ECDSA-SHA384                   79228     12.8337  
ECDSA-SHA512                   79233     12.8346  
ECDSA-SHA512 Only              22        0.0036   
RSA-MD5                        19577     3.1712   
RSA-SHA1                       481896    78.0599  
RSA-SHA1 Only                  26070     4.2229   
RSA-SHA224                     411504    66.6575  
RSA-SHA256                     464624    75.2621  
RSA-SHA256 Only                7718      1.2502   
RSA-SHA384                     427149    69.1917  
RSA-SHA384 Only                4         0.0006   
RSA-SHA512                     427025    69.1717  
RSA-SHA512 Only                100       0.0162   

TLSv1.2 PFS ordering           Count     Percent 
------------------------------+---------+--------
client                         291070    47.149   
indeterminate                  44        0.0071   
intolerant                     6217      1.0071   
order-fallback                 6         0.001    
server                         252346    40.8763  
unsupported                    12582     2.0381   

TLSv1.2 PFS sigalg fallback    Count     Percent 
------------------------------+---------+--------
ECDSA SHA1                     60314     9.77     
ECDSA intolerant               218       0.0353   
ECDSA pfs-rsa-SHA512           18785     3.0429   
ECDSA soft-nopfs               9         0.0015   
RSA False                      19392     3.1412   
RSA SHA1                       419870    68.0127  
RSA intolerant                 51966     8.4177   
RSA pfs-ecdsa-SHA512           21        0.0034   
RSA soft-nopfs                 369       0.0598   

Renegotiation             Count     Percent 
-------------------------+---------+--------
False                     3666      0.5938   
insecure                  14566     2.3595   
secure                    599109    97.0467  

Compression               Count     Percent 
-------------------------+---------+--------
1 (zlib compression)      5637      0.9131   
False                     3666      0.5938   
NONE                      608038    98.4931  

TLS session ticket hint   Count     Percent 
-------------------------+---------+--------
1                         3         0.0005   
1 only                    3         0.0005   
2                         1         0.0002   
2 only                    1         0.0002   
5                         6         0.001    
5 only                    6         0.001    
10                        9         0.0015   
10 only                   9         0.0015   
12                        1         0.0002   
12 only                   1         0.0002   
15                        7         0.0011   
15 only                   7         0.0011   
30                        24        0.0039   
30 only                   24        0.0039   
60                        151       0.0245   
60 only                   143       0.0232   
65                        1         0.0002   
65 only                   1         0.0002   
70                        10        0.0016   
70 only                   8         0.0013   
90                        1         0.0002   
90 only                   1         0.0002   
100                       17        0.0028   
100 only                  17        0.0028   
120                       32        0.0052   
120 only                  32        0.0052   
128                       5         0.0008   
128 only                  5         0.0008   
150                       8         0.0013   
150 only                  6         0.001    
180                       99        0.016    
180 only                  98        0.0159   
240                       17        0.0028   
240 only                  17        0.0028   
300                       304473    49.3201  
300 only                  301855    48.896   
302                       1         0.0002   
302 only                  1         0.0002   
360                       2         0.0003   
360 only                  1         0.0002   
400                       6         0.001    
400 only                  6         0.001    
420                       114       0.0185   
420 only                  100       0.0162   
450                       1         0.0002   
450 only                  1         0.0002   
480                       14        0.0023   
480 only                  14        0.0023   
500                       5         0.0008   
500 only                  5         0.0008   
540                       4         0.0006   
540 only                  4         0.0006   
600                       36341     5.8867   
600 only                  36218     5.8668   
660                       1         0.0002   
660 only                  1         0.0002   
700                       1         0.0002   
700 only                  1         0.0002   
720                       2         0.0003   
720 only                  2         0.0003   
840                       2         0.0003   
840 only                  2         0.0003   
900                       1855      0.3005   
900 only                  1836      0.2974   
960                       3         0.0005   
960 only                  3         0.0005   
1200                      3924      0.6356   
1200 only                 3920      0.635    
1320                      1         0.0002   
1320 only                 1         0.0002   
1380                      1         0.0002   
1380 only                 1         0.0002   
1440                      1         0.0002   
1440 only                 1         0.0002   
1500                      10        0.0016   
1500 only                 9         0.0015   
1800                      895       0.145    
1800 only                 886       0.1435   
1920                      1         0.0002   
1920 only                 1         0.0002   
1980                      2         0.0003   
1980 only                 2         0.0003   
2100                      2         0.0003   
2100 only                 1         0.0002   
2400                      6         0.001    
2400 only                 6         0.001    
2700                      10        0.0016   
2700 only                 10        0.0016   
3000                      46        0.0075   
3000 only                 46        0.0075   
3600                      1309      0.212    
3600 only                 1298      0.2103   
3840                      5         0.0008   
3840 only                 5         0.0008   
3900                      1         0.0002   
3900 only                 1         0.0002   
4100                      1         0.0002   
4100 only                 1         0.0002   
4200                      1         0.0002   
4500                      2         0.0003   
4500 only                 2         0.0003   
5160                      1         0.0002   
5160 only                 1         0.0002   
5400                      17        0.0028   
5400 only                 17        0.0028   
6000                      385       0.0624   
6000 only                 385       0.0624   
7200                      15426     2.4988   
7200 only                 15407     2.4957   
7500                      2         0.0003   
7500 only                 2         0.0003   
9000                      2         0.0003   
9000 only                 2         0.0003   
10800                     5668      0.9181   
10800 only                5641      0.9138   
14400                     234       0.0379   
14400 only                234       0.0379   
18000                     8         0.0013   
18000 only                8         0.0013   
21600                     4933      0.7991   
21600 only                4932      0.7989   
25200                     1         0.0002   
25200 only                1         0.0002   
28800                     1747      0.283    
28800 only                1746      0.2828   
30000                     2         0.0003   
30000 only                1         0.0002   
30322                     1         0.0002   
30342                     1         0.0002   
30359                     1         0.0002   
30375                     1         0.0002   
30389                     1         0.0002   
30407                     1         0.0002   
30426                     1         0.0002   
30447                     1         0.0002   
30463                     1         0.0002   
30481                     1         0.0002   
30496                     1         0.0002   
30513                     1         0.0002   
30533                     1         0.0002   
30555                     1         0.0002   
30574                     1         0.0002   
36000                     1425      0.2308   
36000 only                1422      0.2303   
43200                     70        0.0113   
43200 only                70        0.0113   
54000                     1         0.0002   
54000 only                1         0.0002   
60000                     1         0.0002   
60000 only                1         0.0002   
64800                     80026     12.963   
64800 only                80024     12.9627  
72000                     16        0.0026   
72000 only                16        0.0026   
79200                     1         0.0002   
79200 only                1         0.0002   
86400                     3726      0.6036   
86400 only                3720      0.6026   
90000                     1         0.0002   
90000 only                1         0.0002   
100000                    1         0.0002   
100000 only               1         0.0002   
100800                    10409     1.6861   
100800 only               10396     1.684    
108000                    1         0.0002   
108000 only               1         0.0002   
115200                    1         0.0002   
115200 only               1         0.0002   
129600                    7         0.0011   
129600 only               7         0.0011   
172800                    55        0.0089   
172800 only               55        0.0089   
216000                    3         0.0005   
216000 only               3         0.0005   
259200                    1         0.0002   
259200 only               1         0.0002   
432000                    1         0.0002   
432000 only               1         0.0002   
604800                    1         0.0002   
864000                    3         0.0005   
864000 only               3         0.0005   
7776000                   1         0.0002   
7776000 only              1         0.0002   
None                      146605    23.7478  
None only                 143741    23.2839  

Certificate sig alg     Count     Percent 
-------------------------+---------+--------
None                      8517      1.3796   
ecdsa-with-SHA256         77357     12.5307  
sha1WithRSAEncryption     8710      1.4109   
sha256WithRSAEncryption   550018    89.0947  
sha384WithRSAEncryption   12        0.0019   
sha512WithRSAEncryption   94        0.0152   

Certificate key size    Count     Percent 
-------------------------+---------+--------
ECDSA 256                 79263     12.8394  
ECDSA 384                 64        0.0104   
ECDSA 521                 1         0.0002   
RSA 1024                  8         0.0013   
RSA 2048                  522923    84.7057  
RSA 2049                  4         0.0006   
RSA 2056                  1         0.0002   
RSA 2058                  1         0.0002   
RSA 2059                  1         0.0002   
RSA 2060                  1         0.0002   
RSA 2080                  7         0.0011   
RSA 2084                  1         0.0002   
RSA 2086                  1         0.0002   
RSA 2096                  2         0.0003   
RSA 2432                  4         0.0006   
RSA 2560                  1         0.0002   
RSA 2948                  1         0.0002   
RSA 3048                  1         0.0002   
RSA 3050                  1         0.0002   
RSA 3072                  171       0.0277   
RSA 3096                  2         0.0003   
RSA 3248                  3         0.0005   
RSA 4048                  1         0.0002   
RSA 4056                  11        0.0018   
RSA 4068                  2         0.0003   
RSA 4069                  1         0.0002   
RSA 4086                  3         0.0005   
RSA 4092                  2         0.0003   
RSA 4094                  1         0.0002   
RSA 4096                  35502     5.7508   
RSA 4098                  1         0.0002   
RSA 4196                  1         0.0002   
RSA 8192                  12        0.0019   
RSA 8392                  1         0.0002   
RSA/ECDSA Dual Stack      20648     3.3447

OCSP stapling             Count     Percent 
-------------------------+---------+--------
Supported                 147812    23.9433  
Unsupported               469529    76.0567  

Supported Protocols       Count     Percent
-------------------------+---------+-------
SSL2                      13670     2.2143
SSL2 Only                 7         0.0011
SSL3                      79648     12.9018
SSL3 Only                 291       0.0471
SSL3 or TLS1 Only         40940     6.6317
SSL3 or lower Only        298       0.0483
TLS1                      602893    97.6596
TLS1 Only                 24668     3.9958
TLS1 or lower Only        53665     8.6929
TLS1.1                    554533    89.826
TLS1.1 Only               43        0.007
TLS1.1 or up Only         13986     2.2655
TLS1.2                    562252    91.0764
TLS1.2 Only               4393      0.7116
TLS1.2, 1.0 but not 1.1   4370      0.7079

Client Hello intolerance                 Count     Percent
----------------------------------------+---------+-------
ext:ALPN                                 5         0.0008
ext:EMS                                  396       0.0641
ext:EtM                                  63        0.0102
ext:ext #38                              23        0.0037
ext:key share                            423       0.0685
ext:NPN                                  5         0.0008
ext:OCSP staple                          13        0.0021
ext:padding                              402       0.0651
ext:SNI                                  109       0.0177
last ext empty                           18        0.0029
more groups                              415       0.0672
more sigalgs                             485       0.0786
secure renego ext                        567       0.0918
secure renego scsv                       526       0.0852
size c#/12                               77        0.0125
size c#/20                               40        0.0065
size c#/22                               363       0.0588
size c#/129                              1334      0.2161
size c#/201                              75        0.0121
size c#/257                              419       0.0679
size c#/304                              17        0.0028
size c#/475                              21        0.0034
size c#/501                              180       0.0292
size c#/606                              5         0.0008
size c#/612                              236       0.0382
size c#/614                              10        0.0016
size c#/651                              6         0.001
size c#/653                              161       0.0261
size c#/703                              6         0.001
size c#/734                              6         0.001
size c#/943                              5         0.0008
size c#/945                              6         0.001
size c#/998                              29        0.0047
size c#/1000                             159       0.0258
size c#/1001                             10        0.0016
size c#/1972                             36        0.0058
size c#/1979                             8         0.0013
size c#/1980                             16        0.0026
size c#/1981                             22        0.0036
size c#/1982                             44        0.0071
size c#/1983                             49        0.0079
size c#/1984                             73        0.0118
size c#/1985                             109       0.0177
size c#/1986                             137       0.0222
size c#/1987                             135       0.0219
size c#/1988                             117       0.019
size c#/1989                             62        0.01
size c#/1990                             35        0.0057
size c#/1991                             5         0.0008
size c#/2013                             5         0.0008
size c#/2021                             713       0.1155
size c#/2027                             8         0.0013
size c#/3223                             8         0.0013
size c#/4017                             5         0.0008
size c#/4018                             7         0.0011
size c#/4019                             15        0.0024
size c#/4020                             14        0.0023
size c#/4021                             17        0.0028
size c#/4022                             20        0.0032
size c#/4023                             11        0.0018
size c#/4024                             8         0.0013
size c#/4035                             69        0.0112
size c#/4088                             8         0.0013
size c#/4317                             34        0.0055
size c#/5023                             13        0.0021
size c#/5056                             9         0.0015
size c#/5075                             120       0.0194
size c#/5098                             4811      0.7793
size c#/5103                             6         0.001
size c#/5261                             7         0.0011
size c#/5510                             9         0.0015
size c#/5747                             5         0.0008
size c#/5748                             6         0.001
size c#/5751                             264       0.0428
size c#/5757                             6         0.001
size c#/6119                             55        0.0089
size c#/6207                             5         0.0008
size c#/6773                             7         0.0011
size c#/7086                             18        0.0029
size c#/7087                             46        0.0075
size c#/7088                             76        0.0123
size c#/7089                             138       0.0224
size c#/7090                             224       0.0363
size c#/7091                             355       0.0575
size c#/7092                             486       0.0787
size c#/7093                             563       0.0912
size c#/7094                             579       0.0938
size c#/7095                             491       0.0795
size c#/7096                             249       0.0403
size c#/7097                             98        0.0159
size c#/7103                             27        0.0044
size c#/7104                             31        0.005
size c#/7105                             2162      0.3502
size c#/7106                             79        0.0128
size c#/7107                             78025     12.6389
size c#/7146                             7         0.0011
size c#/7235                             12        0.0019
size c#/7656                             5         0.0008
size c#/8038                             5         0.0008
size c#/8091                             11        0.0018
size c#/8102                             6         0.001
size c#/8107                             10        0.0016
size c#/8108                             9         0.0015
size c#/8109                             24        0.0039
size c#/8110                             86        0.0139
size c#/8111                             29        0.0047
size c#/8112                             42        0.0068
size c#/8113                             44        0.0071
size c#/8114                             40        0.0065
size c#/8115                             38        0.0062
size c#/8116                             27        0.0044
size c#/8117                             20        0.0032
size c#/8118                             20        0.0032
size c#/8119                             11        0.0018
size c#/8120                             22        0.0036
size c#/8121                             21        0.0034
size c#/8122                             10        0.0016
size c#/8123                             13        0.0021
size c#/8124                             20        0.0032
size c#/8125                             34        0.0055
size c#/8126                             9054      1.4666
size c#/8127                             115       0.0186
size c#/8128                             463       0.075
size c#/8129                             496       0.0803
size c#/8130                             1058      0.1714
size c#/8131                             1875      0.3037
size c#/8132                             3274      0.5303
size c#/8133                             5263      0.8525
size c#/8134                             7846      1.2709
size c#/8135                             11111     1.7998
size c#/8136                             12963     2.0998
size c#/8137                             12113     1.9621
size c#/8138                             16315     2.6428
size c#/8139                             2233      0.3617
size c#/8140                             394       0.0638
size c#/8141                             23        0.0037
size c#/8142                             19        0.0031
size c#/8143                             22        0.0036
size c#/8144                             25        0.004
size c#/8145                             6063      0.9821
size c#/8146                             98        0.0159
size c#/8147                             21529     3.4874
size c#/8150                             9         0.0015
size c#/8152                             68        0.011
size c#/8164                             6         0.001
size c#/8165                             52        0.0084
size c#/8166                             1019      0.1651
size c#/8167                             162       0.0262
size c#/8168                             10471     1.6961
size c#/8169                             234       0.0379
size c#/8170                             393215    63.6949
size c#/8171                             69        0.0112
size c#/8172                             104       0.0168
size c#/8173                             81        0.0131
size c#/8259                             17        0.0028
size c#/8298                             124       0.0201
size c#/15299                            8         0.0013
size c#/16362                            113       0.0183
size c#/24552                            35        0.0057
size c/74                                60        0.0097
size c/78                                6         0.001
size c/161                               6         0.001
size c/162                               10        0.0016
size c/163                               9         0.0015
size c/164                               12        0.0019
size c/165                               15        0.0024
size c/166                               8         0.0013
size c/167                               6         0.001
size c/168                               10        0.0016
size c/169                               9         0.0015
size c/170                               8         0.0013
size c/171                               10        0.0016
size c/172                               20        0.0032
size c/173                               15        0.0024
size c/174                               15        0.0024
size c/175                               18        0.0029
size c/176                               20        0.0032
size c/177                               36        0.0058
size c/178                               20        0.0032
size c/179                               20        0.0032
size c/180                               18        0.0029
size c/181                               11        0.0018
size c/182                               9         0.0015
size c/183                               14        0.0023
size c/184                               10        0.0016
size c/185                               9         0.0015
size c/186                               7         0.0011
size c/187                               8         0.0013
size c/188                               5         0.0008
size c/194                               5         0.0008
size c/308                               1203      0.1949
size c/312                               124       0.0201
size c/391                               5         0.0008
size c/452                               74        0.012
size c/564                               333       0.0539
size c/568                               16        0.0026
size c/667                               5         0.0008
size c/670                               5         0.0008
size c/673                               8         0.0013
size c/674                               5         0.0008
size c/1000                              22        0.0036
size c/1052                              116       0.0188
size c/1097                              11        0.0018
size c/1135                              49        0.0079
size c/1344                              10        0.0016
size c/1356                              415       0.0672
size c/1456                              8         0.0013
size c/1521                              6         0.001
size c/1977                              5         0.0008
size c/2049                              189       0.0306
size c/2052                              10        0.0016
size c/2496                              5         0.0008
size c/2784                              10        0.0016
size c/4076                              39        0.0063
size c/4092                              1545      0.2503
size c/4103                              8         0.0013
size c/6496                              8         0.0013
size c/8192                              11        0.0018
size c/8226                              8         0.0013
size c/8766                              34        0.0055
size c/10095                             13        0.0021
size c/10245                             5104      0.8268
size c/10338                             6         0.001
size c/10654                             7         0.0011
size c/11074                             10        0.0016
size c/11628                             6         0.001
size c/11634                             263       0.0426
size c/12288                             60        0.0097
size c/12464                             5         0.0008
size c/12825                             5         0.0008
size c/13596                             7         0.0011
size c/14342                             6         0.001
size c/15360                             5         0.0008
size c/15362                             6         0.001
size c/16254                             6         0.001
size c/16289                             8         0.0013
size c/16350                             6         0.001
size c/16353                             136       0.022
size c/16378                             5         0.0008
size c/16380                             32        0.0052
size c/16382                             166       0.0269
size c/16383                             130       0.0211
size c/16384                             218       0.0353
size c/16385                             29768     4.822
size c/16386                             1462      0.2368
size c/16387                             199       0.0322
size c/16388                             334       0.0541
size c/16389                             560436    90.7822
size c/16392                             35        0.0057
size c/16396                             6         0.001
size c/16397                             8         0.0013
size c/16400                             75        0.0121
size c/16401                             65        0.0105
size c/16404                             10        0.0016
size c/16406                             7         0.0011
size c/16408                             8898      1.4413
size c/16645                             153       0.0248
size c/18502                             8         0.0013
size c/32773                             123       0.0199
size c/49153                             36        0.0058
size c/65536                             6         0.001
SSL 3.254                                12324     1.9963
SSL 4.0                                  15533     2.5161
SSL 4.3                                  14995     2.429
SSL 255.255                              15052     2.4382
TLS 1.0                                  13383     2.1678
TLS 1.1                                  3950      0.6398
TLS 1.2                                  27        0.0044
TLS 1.3                                  6836      1.1073
TLS 1.4                                  7445      1.206

Implementation families                               Count       Percent
-----------------------------------------------------+-----------+-------
c/177 c#/22                                        11        0.0018
c/308 c#/129 TLS_1.3+                              1199      0.1942
c/312 c#/129 TLS_1.3+                              59        0.0096
c/391 c#/129                                       5         0.0008
c/452 c#/201 SSL_4.0+                              74        0.012
c/564 c#/257                                       273       0.0442
c/564 c#/257 SSL_4.0+                              16        0.0026
c/564 c#/257 SSL_4.0+ SSL_3.254                    6         0.001
c/564 c#/257 TLS_1.3+                              34        0.0055
c/568 c#/257 TLS_1.3+                              16        0.0026
c/667 c#/257                                       5         0.0008
c/670 c#/257                                       5         0.0008
c/673 c#/257                                       8         0.0013
c/674 c#/257                                       5         0.0008
c/1000 c#/475 TLS_1.3+                             21        0.0034
c/1052 c#/501                                      91        0.0147
c/1052 c#/501 SSL_4.0+                             14        0.0023
c/1052 c#/501 TLS_1.3+                             9         0.0015
c/1097 c#/501                                      11        0.0018
c/1135 c#/501                                      48        0.0078
c/1344 c#/606                                      5         0.0008
c/1356 c#/612                                      236       0.0382
c/1356 c#/614 SSL_4.0+                             6         0.001
c/1356 c#/653 SSL_4.0+                             132       0.0214
c/1356 c#/653 TLS_1.3+                             24        0.0039
c/1456 c#/703 SSL_4.0+                             6         0.001
c/1521 c#/734 TLS_1.4 TLS_1.3 TLS_1.2 SSL_3.254    6         0.001
c/2049 c#/998 TLS_1.3+                             29        0.0047
c/2049 c#/1000 TLS_1.3+                            159       0.0258
c/2052 c#/1001                                     10        0.0016
c/4076 c#/1972                                     36        0.0058
c/4092 c#/943                                      5         0.0008
c/4092 c#/945                                      6         0.001
c/4092 c#/1979                                     8         0.0013
c/4092 c#/1980                                     16        0.0026
c/4092 c#/1981                                     21        0.0034
c/4092 c#/1982                                     43        0.007
c/4092 c#/1983                                     49        0.0079
c/4092 c#/1984                                     71        0.0115
c/4092 c#/1985                                     108       0.0175
c/4092 c#/1986                                     137       0.0222
c/4092 c#/1987                                     135       0.0219
c/4092 c#/1988                                     115       0.0186
c/4092 c#/1989                                     61        0.0099
c/4092 c#/1990                                     34        0.0055
c/4092 c#/2021                                     712       0.1153
c/4103 c#/2027                                     8         0.0013
c/6496 c#/3223                                     8         0.0013
c/8226 c#/4088                                     5         0.0008
c/8766 c#/4317                                     34        0.0055
c/10095                                            13        0.0021
c/10245                                            708       0.1147
c/10245 c#/4017 SSL_3.254                          5         0.0008
c/10245 c#/4018 SSL_3.254                          6         0.001
c/10245 c#/4019 SSL_3.254                          12        0.0019
c/10245 c#/4020 SSL_3.254                          13        0.0021
c/10245 c#/4021 SSL_3.254                          16        0.0026
c/10245 c#/4022 SSL_3.254                          18        0.0029
c/10245 c#/4023 SSL_3.254                          10        0.0016
c/10245 c#/4024 SSL_3.254                          7         0.0011
c/10245 c#/4035                                    69        0.0112
c/10245 SSL_3.254                                  4225      0.6844
c/10338                                            6         0.001
c/10654                                            7         0.0011
c/11074                                            10        0.0016
c/11628                                            6         0.001
c/11634                                            263       0.0426
c/12464                                            5         0.0008
c/12825                                            5         0.0008
c/13596                                            5         0.0008
c/14342                                            6         0.001
c/16254                                            5         0.0008
c/16289 SSL_4.0+                                   8         0.0013
c/16353                                            123       0.0199
c/16353 TLS_1.3+                                   12        0.0019
c/16380                                            31        0.005
c/16382                                            126       0.0204
c/16382 SSL_4.0+                                   11        0.0018
c/16383                                            89        0.0144
c/16383 SSL_4.0+                                   6         0.001
c/16383 TLS_1.3+                                   5         0.0008
c/16384                                            150       0.0243
c/16384 SSL_4.0+                                   22        0.0036
c/16384 TLS_1.3+                                   13        0.0021
c/16385                                            22319     3.6153
c/16385 SSL_4.0                                    12        0.0019
c/16385 SSL_4.0+                                   2410      0.3904
c/16385 TLS_1.3+                                   4773      0.7732
c/16385 TLS_1.3+ TLS_1.2                           6         0.001
c/16385 TLS_1.4 SSL_4.0+ SSL_3.254                 182       0.0295
c/16386                                            1352      0.219
c/16386 SSL_4.0+                                   39        0.0063
c/16386 TLS_1.3+                                   34        0.0055
c/16387                                            121       0.0196
c/16387 SSL_4.0+                                   55        0.0089
c/16388                                            282       0.0457
c/16388 SSL_4.0+                                   5         0.0008
c/16388 TLS_1.3+                                   5         0.0008
c/16389                                            555008    89.903
c/16389 SSL_4.0+                                   4661      0.755
c/16389 TLS_1.3+                                   198       0.0321
c/16392                                            34        0.0055
c/16396                                            6         0.001
c/16397                                            8         0.0013
c/16400                                            75        0.0121
c/16401                                            65        0.0105
c/16404                                            9         0.0015
c/16406                                            7         0.0011
c/16408                                            8897      1.4412
c/16645                                            131       0.0212
c/16645 SSL_4.0+                                   21        0.0034
c/18502 SSL_4.0                                    6         0.001
c/32773                                            59        0.0096
c/32773 SSL_4.0                                    64        0.0104
c/49153                                            36        0.0058
c/65536                                            5         0.0008
ext:OCSP_staple c/16389                            8         0.0013
ext:padding ext:key_share ext:EMS c/161 c#/22 TLS_1.4 SSL_3.254 5         0.0008
ext:padding ext:key_share ext:EMS c/162 c#/22 TLS_1.4 SSL_3.254 10        0.0016
ext:padding ext:key_share ext:EMS c/163 c#/22 TLS_1.4 SSL_3.254 7         0.0011
ext:padding ext:key_share ext:EMS c/164 c#/22 TLS_1.4 SSL_3.254 11        0.0018
ext:padding ext:key_share ext:EMS c/165 c#/22 TLS_1.4 SSL_3.254 14        0.0023
ext:padding ext:key_share ext:EMS c/166 c#/22 TLS_1.4 SSL_3.254 6         0.001
ext:padding ext:key_share ext:EMS c/167 c#/22 TLS_1.4 SSL_3.254 6         0.001
ext:padding ext:key_share ext:EMS c/168 c#/22 TLS_1.4 SSL_3.254 10        0.0016
ext:padding ext:key_share ext:EMS c/169 c#/22 TLS_1.4 SSL_3.254 9         0.0015
ext:padding ext:key_share ext:EMS c/170 c#/22 TLS_1.4 SSL_3.254 7         0.0011
ext:padding ext:key_share ext:EMS c/171 c#/22 TLS_1.4 SSL_3.254 10        0.0016
ext:padding ext:key_share ext:EMS c/172 c#/22 TLS_1.4 SSL_3.254 18        0.0029
ext:padding ext:key_share ext:EMS c/173 c#/22 TLS_1.4 SSL_3.254 15        0.0024
ext:padding ext:key_share ext:EMS c/174 c#/22 TLS_1.4 SSL_3.254 14        0.0023
ext:padding ext:key_share ext:EMS c/175 c#/22 TLS_1.4 SSL_3.254 18        0.0029
ext:padding ext:key_share ext:EMS c/176 c#/22 TLS_1.4 SSL_3.254 20        0.0032
ext:padding ext:key_share ext:EMS c/177 c#/22 TLS_1.4 SSL_3.254 24        0.0039
ext:padding ext:key_share ext:EMS c/178 c#/22 TLS_1.4 SSL_3.254 19        0.0031
ext:padding ext:key_share ext:EMS c/179 c#/22 TLS_1.4 SSL_3.254 20        0.0032
ext:padding ext:key_share ext:EMS c/180 c#/22 TLS_1.4 SSL_3.254 16        0.0026
ext:padding ext:key_share ext:EMS c/181 c#/22 TLS_1.4 SSL_3.254 11        0.0018
ext:padding ext:key_share ext:EMS c/182 c#/22 TLS_1.4 SSL_3.254 9         0.0015
ext:padding ext:key_share ext:EMS c/183 c#/22 TLS_1.4 SSL_3.254 11        0.0018
ext:padding ext:key_share ext:EMS c/184 c#/22 TLS_1.4 SSL_3.254 9         0.0015
ext:padding ext:key_share ext:EMS c/185 c#/22 TLS_1.4 SSL_3.254 8         0.0013
ext:padding ext:key_share ext:EMS c/188 c#/22 TLS_1.4 SSL_3.254 5         0.0008
ext:SNI c/16385 TLS_1.3+                           14        0.0023
ext:SNI c/16389                                    85        0.0138
last_ext_empty                                     7         0.0011
more_groups c/16382                                5         0.0008
more_groups c/16384                                5         0.0008
more_groups c/16385                                6         0.001
more_groups c/16388                                6         0.001
more_groups c/16389                                77        0.0125
more_sigalgs                                       33        0.0053
more_sigalgs c/16385                               10        0.0016
more_sigalgs c/16386                               8         0.0013
more_sigalgs c/16389                               99        0.016
more_sigalgs more_groups c/16389                   11        0.0018
secure_renego_ext c/312 c#/129 TLS_1.3+            65        0.0105
secure_renego_ext c/12288                          58        0.0094
secure_renego_ext c/16384                          5         0.0008
secure_renego_ext c/16385                          6         0.001
secure_renego_ext c/16388                          10        0.0016
secure_renego_ext c/16389                          98        0.0159
secure_renego_ext more_groups c/16389              6         0.001
secure_renego_ext more_sigalgs c/16389             10        0.0016
secure_renego_scsv c/16382                         5         0.0008
secure_renego_scsv c/16385                         14        0.0023
secure_renego_scsv c/16386                         7         0.0011
secure_renego_scsv c/16387                         9         0.0015
secure_renego_scsv c/16389                         84        0.0136
secure_renego_scsv c/16389 SSL_4.0+                23        0.0037
secure_renego_scsv more_sigalgs c/16389            16        0.0026
secure_renego_scsv more_sigalgs more_groups c/16389 5         0.0008
secure_renego_scsv secure_renego_ext c/16389       8         0.0013
secure_renego_scsv secure_renego_ext more_groups c/16389 6         0.001
secure_renego_scsv secure_renego_ext more_sigalgs more_groups ext:key_share c/74 c#/12 TLS_1.4 SSL_3.254 51        0.0083
secure_renego_scsv SSL_4.0+                        14        0.0023
secure_renego_scsv SSL_4.0+ SSL_3.254              27        0.0044
SSL_3.254 SSL_255.255                              20        0.0032
SSL_4.0                                            395       0.064
SSL_4.0 SSL_3.254 SSL_255.255                      30        0.0049
SSL_4.0+                                           11        0.0018
SSL_4.0+ SSL_3.254                                 360       0.0583
TLS_1.3+                                           37        0.006
TLS_1.3+ TLS_1.2                                   5         0.0008



Statistics from 380577 chains provided by 741802 hosts

Server provided chains    Count     Percent
-------------------------+---------+-------
complete                  355021    47.8593
incomplete                14438     1.9463
untrusted                 372343    50.1944

Trusted chain statistics
========================

Chain length              Count     Percent
-------------------------+---------+-------
2                         1         0.0003
3                         375989    98.7945
4                         4576      1.2024
5                         11        0.0029

CA key size in chains     Count
-------------------------+---------
ECDSA 256                 10554     
ECDSA 384                 10500     
RSA 1024                  1         
RSA 2045                  2         
RSA 2048                  599063    
RSA 4096                  145631    

Chains with CA key        Count     Percent
-------------------------+---------+-------
ECDSA 256                 10554     2.7732
ECDSA 384                 10500     2.759
RSA 1024                  1         0.0003
RSA 2045                  2         0.0005
RSA 2048                  369728    97.1493
RSA 4096                  145057    38.115

Signature algorithm (ex. root) Count
------------------------------+---------
ecdsa-with-SHA384              10480     
sha1WithRSAEncryption          4001      
sha256WithRSAEncryption        240251    
sha384WithRSAEncryption        130369    
sha512WithRSAEncryption        73        

Eff. host cert chain LoS  Count     Percent
-------------------------+---------+-------
80                        3967      1.0424
112                       366102    96.1966
128                       10508     2.7611

Most common root CAs                          Count     Percent
---------------------------------------------+---------+-------
(d6325660) COMODO RSA Certification Authority 114912    30.1942
(2c543cd1) GeoTrust Global CA                 59675     15.6801
(cbf06781) Go Daddy Root Certificate Authorit 34287     9.0092
(5ad8a5d6) GlobalSign Root CA                 25336     6.6573
(244b5494) DigiCert High Assurance EV Root CA 17608     4.6267
(b204d74a) VeriSign Class 3 Public Primary Ce 16082     4.2257
(fc5a8f99) USERTrust RSA Certification Author 15380     4.0412
(4bfab552) Starfield Root Certificate Authori 11040     2.9009
(2e4eed3c) thawte Primary Root CA             10561     2.775
(eed8c118) COMODO ECC Certification Authority 10478     2.7532
(653b494a) Baltimore CyberTrust Root          8661      2.2758
(3513523f) DigiCert Global Root CA            8436      2.2166
(ae8153b9) StartCom Certification Authority   6077      1.5968
(e2799e36) GeoTrust Primary Certification Aut 5377      1.4129
(480720ec) GeoTrust Primary Certification Aut 4278      1.1241

Most common intermediate CA                   Count     Percent
---------------------------------------------+---------+-------
(8d28ae65) COMODO RSA Domain Validation Secur 80544     21.1637
(27eb7704) Go Daddy Secure Certificate Author 34287     9.0092
(53f3e569) RapidSSL SHA256 CA - G3            23547     6.1872
(1400f578) cPanel, Inc. Certification Authori 20473     5.3795
(80ecc636) RapidSSL SHA256 CA                 17373     4.5649
(38ae8eda) DigiCert SHA2 High Assurance Serve 14767     3.8802
(cd7781e5) Starfield Secure Certificate Autho 11040     2.9009
(7d9c641e) Symantec Class 3 Secure Server CA  10812     2.8409
(16744f0c) AlphaSSL CA - SHA256 - G2          10734     2.8205
(10310d4b) GeoTrust SSL CA - G3               10577     2.7792
(6cfa716c) COMODO ECC Domain Validation Secur 10433     2.7414
(c43a77d9) COMODO RSA Organization Validation 8974      2.358
(85cf5865) DigiCert SHA2 Secure Server CA     8419      2.2122
(d7d634d4) GlobalSign Domain Validation CA -  7954      2.09
(fd917e82) SecureCore RSA DV CA               7248      1.9045
(3d97f5e2) Verizon Akamai SureServer CA G14-S 6322      1.6612
(9ad474ec) thawte SSL CA - G2                 5746      1.5098
(b85455c4) GlobalSign Organization Validation 4922      1.2933
(a0f7ac3e) Symantec Class 3 EV SSL CA - G3    4831      1.2694
(b71a5f76) GeoTrust EV SSL CA - G4            4278      1.1241
(98d7cad7) GeoTrust DV SSL CA - G3            4266      1.1209

Scan performed between 1st and 21st of October 2016.