Digital Signature Algorithm for large files - bottle-necked by hash function?

Question

I am new to studying digital signatures like ECDSA and EdDSA, and was curious about something.

Lets say hypothetically I want to create a digital signatures of millions of files, with a total size of 10TB.

From what I understand, digital signature algorithms are hash-then-sign, and the hash functions used must be cryptographic hashes such as SHA-2 or SHA-3. However, looking up the typical benchmarks of SHA-2 and SHA-3, their speed in terms of throughput (bytes/second) seem to be well under 500MB/s per core on modern laptop CPUs, which is not bad.

But in environments without hardware acceleration, it is probably at least 4x slower. On mobile devices, SHA-3 seems to perform 20MB/s on my phone according to a javascript benchmark.

It seems like in certain environments, the hash function will be the bottleneck in both creating the signature, as well as verifying it. Especially for mobile devices -- it would take several days to sign/verify a 10TB inventory of files.

Are there any cryptographically secure digital signature algorithms that are optimized for large files in terms of throughput? Or are we always bottlenecked by the hash function?

Are there any fast, non-cryptographic hash function we could use for digital signatures while keeping the cryptographic security?

Answer 1

When you are considering authenticating a 10 TB dataset, consider what forgeries the verifier must be willing to handle: if you sign the 10 TB dataset in one swell foop, the verifier must be willing to do all the work to hash up to 10 TB of data before they have a chance to reject a forgery, even if there was only a single bit flipped anywhere in the data set. And the computation can't really be parallelized.

There are a couple ways to do this that parallelize much better:

• You can sign each record independently, with a prefix that encodes a unique index or key or path for the record so that the signed content of one record can't be plopped into another record where it wasn't intended, like replacing the files named gpg-1.4.14.tar.gz and gpg-1.4.14.tar.gz.asc by the vulnerable ones gpg-1.4.13.tar.gz and gpg-1.4.13.tar.gz.asc which are nevertheless a valid message/signature pair under the correct key.

  Since the records are all signed independently, you can easily parallelize the computation. Then as long as each record has a bounded size, say a megabyte or a gigabyte, there's a reasonable limit on the amount of data that a forger can use to deny service to a verifier before the verifier can drop the forgery on the floor.

  However, this means that an adversary in control of the Amazon S3 servers where you're storing them could roll back a single record without your notice.

• You can hash each record, and hash each directory of records as a list of hashes for the respective records, and hash each directory of directories, and so on, and when you get up to the root, sign the root hash.

  (For better security: when you start the process, pick a randomization string $r$; then use $m \mapsto H(r \mathbin\| m)$ as your hash function instead of just $H$, and sign $(r, h)$ where $h$ is the root hash. Then even if the adversary had an offline collision attack on $H$, if they can't predict $r$ up front the collision attack is of no use, as long as $H$ exhibits the much weaker property of ‘target collision resistance’.)

  This is called a Merkle tree, and it too can be parallelized because each branch of the tree is hashed independently. It also admits fast verification of each record: verify the root hash, verify the directory entry hash, verify the subdirectory entry hash, etc., and finally verify the record hash. Roughly this structure is used by, for example, Tahoe-LAFS, a cryptographic capability security distributed file system.

  An adversary could roll back the entire tree, but could not roll back records selectively. And, of course, you could hold on to the root hash itself, rather than relying on someone else to hold onto the most recent signed version of it, and thereby prevent rollbacks altogether.

Answer 2

It is potentially a bottleneck, but will it be a problem in practice? My phone doesn't have 10TB of storage, and if the files are remote the network speed will be the limiting factor. There are other strategies possible, like computing hashes as the data is transferred to the device, or hash trees for updating a hash without re-computing the whole thing (for e.g. a small edit to a file).

Answer 3

Your last sentence is strange; if a non-cryptographic hash function can be used for digital signature then it will be a cryptographic hash function and that needs to satisfy the common requirements as pre-image resistance, second pre-image resistance, and collision resistance.

If you need speed, you may look at Blake series which is faster than SHA-3, SHA-2, SHA-1, and MD5. The below comparison is taken from Blake2's website blake2.net.

\begin{array}{|c|c|} \hline \text{Hash function} & \text{Hash function speed in MiBps} \\ \hline \text{BLAKE2b} & 947\\ \hline \text{SHA-1} & 909 \\ \hline \text{BLAKE2s} & 648 \\ \hline \text{MD5} & 632 \\ \hline \text{SHA-512} & 623 \\ \hline \text{SHAKE-128} & 445 \\ \hline \text{SHA-256} & 413 \\ \hline \text{SHA3-256} & 367 \\ \hline \text{SHA3-512} & 198 \\ \hline \end{array}