Skip to content

Latest commit

 

History

History
148 lines (113 loc) · 7.39 KB

Cryptography.md

File metadata and controls

148 lines (113 loc) · 7.39 KB

Keys and cryptographic primitives

Key generation

General cryptographic remarks

We have several recommendations about minimum key length around:

The high-level summary is that for any key that should be useful for many years,

  • choose a cryptographic algorithm
    • that has been under scrutiny from cryptograpic experts, and
    • is not yet weak or broken (and neither is this foreseeable); and
  • use the longest practical key size of a particular algorithm.

Algorithm diversity

Generally, diversity can be good or bad when it comes to security:

  • More options give more options to potenial attackers, who just have to find a single weakness
  • More options allow for more interoperability

In the case of a timestamping network, we have the property that if just one of the nodes is trustworthy, the entire network is almost as trustworthy, because the timestamp of that trustworthy entity will limit the backdating ability of all others.

Algorithm selection

GnuPG currently (2019) supports the following algorithm and has supported all of them for a few years now:

  • RSA up to 4096 bits (long signatures)
  • DSA up to 3072 bits (short signatures)
  • ECC keys (short signatures, fast operation; bit length in name unless specified otherwise):

Please do chose from the multitude of algorithms, a wide variety helps here. A signature-only algorithm is perfect for our needs.

Key length selection

For key length, this implies that the longest key length should be used which is supported by the server and its expected clients. One criteria for public timestamping servers could be to support a cipher length which has been supported by GnuPG for a few years already.

Cryptographic primitives

The signing key is only part of the equation. Two other parts are worthwhile mentioning:

Key creation

To create a timestamping key out of the full list of algorithms, use

gpg --expert --full-key-gen

and follow the options.

SHA-1 in git

SHA-1 is considered broken by the SHAttered attack. SHAttered is able to create a hash collision between a pair of carefully chosen plaintexts. We do not believe this is of a practical concern for the timestamping application:

  • SHAttered requires a careful preparation of a block to be susceptible to the attack. I.e., a collision needs to be carefully prepared and cannot be randomly inserted later.
  • git since v2.13.0 uses the "Hardened SHA-1" function, which is supposed to make it impossible to sneak contents into a repository which can later be replaced using the SHAttered attack. ("Hardened SHA-1" detects attempts to navigate the internal SHA-1 state into the required state to perform the SHAttered attack and will create a different SHA-1 hash for these. This hash is presumed to be immune against SHAttered.)

So, as a result, it seems that preparing for a collision is thwarted by git today. Even if it were possible to work around this, modifying a previous block (a necessary operation for successful backdating of a timestamp) would require large amounts of careful preparation and could probably only be done for a carefully-chosen replacement. I.e., "let me just thrown these few million dollars of computation time into creating a timestamp now which says it was created last year" is not something we have to worry about.

Nevertheless, we will follow the upcoming transition of git to SHA-256 carefully and take appropriate means in a timely fashion.

PGP Timestamper's PGP 2 key

The PGP Timestamper uses a PGP key created in 1995, which is compatible to the MIT PGP 2.x version, using MD5 hashes and IDEA symmetric encryption algorithm.

This is no longer state of the art, but backdating without careful preparation, a lot of money and even more luck is extremely hard, to say the least. Even given that MD5 is considered broken, hash collisions are extremely hard to create for an existing old hash.

Therefore, the PGP Timestamper is still a source of assurance, but should not be used as the only means of cross-assurance. Instead, publication and/or zeitgitter cross-timestamping should be used as an additional means of assurance.

Some signing speeds

Here are some signing speeds showing the average run time over 10 sequential runs of gpg --sign of a 40-byte input file. For each test, the longest keys offered by gpg --expert --full-gen-key were used. Shorter keys will be faster, zeitgitterd will also take advantage of multiple cores.

Processor (single run) dsa3072 rsa4096 ed25519 nistp521 bpP512r1 secp256k1
AMD EPYC 7351P (2.4 GHz) 23 ms 59 ms 38 ms 49 ms 30 ms 13 ms
AMD Ryzen 2700 X (3 GHz) 10 ms 28 ms 21 ms 27 ms 22 ms 9 ms
Intel Core i7-6600U (2.6 GHz) 19 ms 30 ms 21 ms 27 ms 19 ms 9 ms
BCM2835 (ARM, Raspberry Pi Zero) 398 ms 1192 ms 575 ms 901 ms 785 ms 219 ms
BCM2838 (ARM, Raspberry Pi 3 B+) 144 ms 602 ms 217 ms 357 ms 318 ms 82 ms
Odroid XU3 (ARM) 72 ms 305 ms 159 ms 230 ms 215 ms 61 ms

Thus, a meekly Rasbperry Pi Zero can create about 2…5 timestamps per second, while a single core (!) of an AMD Ryzen or Intel Core i7 above each achieve over 30…100 timestamps per second.

One would expect that the AMD processor with its 16 cores could run 16 gpg processes in parallel and the Intel processor (with 2 real and 4 virtual cores) could run 2…4 gpg processes in parallel. However, GnuPG 2.x uses a single, single-threaded gpg-agent for all secret key operations. Therefore, running multiple GnuPG processes does not result in higher parallelism; i.e., running 10 processes "in parallel" will still require roughly 10x as long as running a single gpg process.

However, I noticed one exception: Running 10 parallel dsa3072 operations on the AMD only requires around 80 ms, so it gains about a factor of 3. I do not have an explanation for this yet.