7
$\begingroup$

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)

$\endgroup$
4
  • $\begingroup$ Shouldn't this be fine even when collisions are happening if you quit your current hash as soon as collisions are a threat, after all you have a fixed input-hash pair which means an attack would need a 2nd preimage which isn't possible w/o brute force for most hashes. $\endgroup$
    – SEJPM
    Feb 28, 2017 at 21:44
  • $\begingroup$ Thanks @SEJPM. Can I interpret your comment as a kind of assertion about the explained context? That is: a hash-function which is only second pre-image resistant, is considered good for this context (?) $\endgroup$ Feb 28, 2017 at 22:31
  • $\begingroup$ @PeterKrauss, I tried to fix the English, excellent question by the way. Could you have a look and also please fix the term authenticity comprovations! Compromises? Comparisons? $\endgroup$
    – kodlu
    Mar 1, 2017 at 6:29
  • $\begingroup$ Thanks @kodlu, English is not my first language... In fact the term is problematic when the context is public document in a transparency aim... My idea in "authenticity purposes" is to reinforce that must conforming to an original, as it in the first public diffusion (gazette first publishing). The "diffuse public" (many citizens) endorsed the first publishing, not one especific (signed) person, not even the writer. $\endgroup$ Mar 1, 2017 at 10:40

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks @Gilles, your answer is perfect! ... Can I use your teaching a little more? It is about truncation. Supposing that all standardized and popular hashes are reasonable, the only good approach to avoid collisions, against far-future attacks, is to use a big hash... as big as the far-future CPU power... Suppose that there are a consensual "secure length L for the next 10 years". As an financial investor that not put all money in only one asset, a good investment is to use two trucated-hashes of L/2 instead one with L, e.g. truncated-SHA2 and truncated-SHA3... Is it? make sense? $\endgroup$ Mar 1, 2017 at 11:48
  • $\begingroup$ About your assertion "Authenticity requires a signature"... But the context is public document, transparency and "endorsement by the public". The public (all citizens that reads the gazette) have no signature, is a diffuse entity. It is not in conflict with the authentication concept at Wikipedia's articles of Message authentication and Authentication: is a question of choice of the concept-specialization by the context. $\endgroup$ Mar 1, 2017 at 11:59
  • $\begingroup$ @PeterKrauss See keylength.com for length recommendations — but for hashes they're pretty uniformly “256 bits is fine”. Truncating hashes is fine according to current knowledge (all the bits of a hash should have equal “strength”). But I would not like to see SHA-256/128 + SHA3-256/128 as a long-term hash, it feels weak to me (allows a 64-bit collision attack on each hash if their collision resistance is broken). My recommendation would be SHA-256 + SHA3-256. $\endgroup$ Mar 1, 2017 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.