How to improve long-term duration of standard checksum for authenticity purposes?

Question

Official CMS's of Government gazettes (in the third world), need to publish the checksum of each article and each cited external documentin (eg. full-text contracts) in a permanent support medium like paper, CD, DVD, etc. And, this is valid as legal proof for decades...

But the checksum is not valid for decades, and the CPU-cost to compute a checksum in this context is not the first problem... So, the question is

  how to improve standard checksums, with minimal impact on the existing workflow?

---

Examples:
(so alternative question is "what is the best?" or "why not?")

• use the truncated form of "the best of the best" (ex. truncated SHA256 instead SHA1).

• use two checksums instead of only "the best of the best" (ex. SHA1+MD5).

• use two checksums, the second after some "file conversion", such as gzip, imagemagick (eg. png2jpg), some pandoc (eg. pdf2text), that preserves main content.

---

CONTEXT AND EXPLANATIONS

The SHA1 is a cryptographic hash that has been used as checksum with aims of integrity and authenticity... So, the context of the question is this tradition of use cryptographic checksums for authenticity comprovations, there are no alternatives for a tradition, please not insist :-)

Let's give the name "authenticity-checksum" to this tradition and the methodologies it uses.

The theme gained more appeal last week with the first practical attack, with the discovery of an algorithm that can build a PDF document with the same SHA1 of other distinct PDF... You can check by yourself in a Linux terminal:

  wget -c https://shattered.io/static/shattered-1.pdf
  wget -c https://shattered.io/static/shattered-2.pdf
  # open each file with your PDF-viewer, see how much distinct they are.

  sha1sum shattered-1.pdf shattered-2.pdf
     # 38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf 
     # ...
  # look at your terminal! the same SHA1 for both files! 

The SHA1 was published as a standard by NIST in 1995, gaining popularity and intensive in the 2000s. The first real and published attack was last week, 2017 (when standard was 22 years old). The first published "attack in theory" demonstration was in 2005, so 10 years after launch.

MD5, its precedent, published as RFC in 1992, with theoretical demonstration in 2008 and real attack in 2012.. It has had a similar timeline in its life-cycle.

We can use the standard's timilines as good time-scale reference, decades, and the historic facts (and Moore's law) as clue that SHA256 will survive less than a decade.

---

... So, about the use of authenticity-checksum in important digital repositories and digital preservation with horizon of decades context.

Imagine a CD-ROM with a big list of file-names and its checksums, a CD recorded in the year 2004, when we still believed in the durability of SHA1. For this "Use Case in the past",
what the best practices, what can we suggest to improve?

(is impossible to test hypothesis with the new standards, as SHA256, but we can in an imaginary use cases, testing the old standards, truncated hashes, and extrapolating results)

Answer 1

In this case, a simple change will improve robustness: include hashes produced by multiple functions. (This can be counterproductive if the hashed data is not fully public, because one hash being inverted would reveal the data even if the other hashes had resisted. But here the data is public so there's no loss of security in adding extra hashes.)

So for example, today, you should include (at least) both a SHA-256 (SHA-2) and a SHA3-256 (SHA-3) hash. (Or other sizes if you prefer, but today there's no strong reason.) One of the reasons why SHA-3 was chosen to be what it was is that it uses rather different techniques (a sponge construction, whereas MD5, SHA-1 and SHA-2 all used a Merkle-Damgård construction), so it's very unlikely that both will be broken at the same time.

You can find recommended hash lengths for a given duration of protection according to various authorities on keylength.com. Most are satisfied with a 256-bit hash for as long as they're willing to give recommendations for. My personal inclination would be to make an effective 512-bit hash by concatenation SHA-256 and SHA3-256.

The primary threat against your system is second-preimage resistance (not being able to tamper with a legal document after it was archived), but collision resistance is also a concern: someone could submit a document (e.g. a contract) with a prepared “trap” that allows them to craft a collision after the contract has been signed (e.g. “you owe us \$1 if you have a blue contract or \$1,000,000 if you have a red contract” — uh-oh). Hash functions seem to be more vulnerable to collision attacks, i.e. finding $M$ and $M'$ such that $H(M) = H(M')$, than to second-preimage attacks, i.e. finding $M'$ such that $H(M) = H(M')$. For example, collisions are known for MD5 and SHA-1, but nobody knows how to find a collision for a given message as opposed to a specially-crafted message (at least nobody who's said so publicly). Here are two things you can do to mitigate collision attacks:

• The known techniques to generate collisions require taking the hash function through “near-collision” states which are extremely unlikely to occur naturally. So you can detect a probable collision attack when hashing a single message! This idea is due to Marc Stevens and an implementation for SHA-1 is available.
• Crafting collisions for MD5 or SHA-1 requires a bit of “garbage” in the middle; that garbage can be hidden in some insignificant part of a complex format such as PDF, or in comments in a computer program, but current techniques don't allow crafting a collision between plain text English documents even with MD5. If you hash plain text¹ rather than (or in addition to) complex formats such as PDF, collision attacks will be easy to detect after the fact, unless our knowledge of how to craft collision makes significant leaps. If your input is not plain text, this does require a deterministic process to generate the plain text.

In the longer term, the only viable solution is algorithm agility: periodically re-hash the documents with newer hash functions. This can be combined with the need to verify and update physical supports. Paper can last centuries or more with proper care, but a magnetic tape or CD is unlikely to last so long; data needs to be transferred to new media every so often. That point in time is a good time to verify originals and re-hash them using up-to-date algorithm. Note that this requires access to the originals, which isn't the case for a plain medium-to-medium transfer; you might not want to do it on every physical transfer, but you should have a procedure for it.

Note that a hash only guarantees integrity, not authenticity. There's only one message with a given hash (as long as the hash function isn't broken), but anyone can produce this hash. Authenticity requires a signature: having a valid signature shows that somone holding the corresponding private key saw the document and was willing to endorse it (subject to the conditions under which the signer is willing to sign documents).

¹ _{Here, “plain text” means a pure text format (e.g. stragiht ASCII or Unicode), what MIME would classify as text/plain, not cryptographic plaintext as opposed to ciphertext.}