How to use cryptography to assure data integrity?

I only understand assurance of integrity using a hash function. How to use cryptograpy to assure data integrity?

• If you use a cryptographically secure hash like SHA-256, you technically use cryptography. From that perspective, your “hash vs cryptography” doesn't really make sense. Maybe you could edit your question to clarify it a bit more? For example, by defining what kind of hashes you're talking about and/or by describing a detailed scenario/problem you're trying to handle cryptographically? That would be great... thanks in advance for your related efforts. – e-sushi Jul 15 '18 at 12:23

If I want to ask a potentially compromised server to remember a file that I don't have room to store myself, I can pick and remember a 256-bit secret uniformly at random, and compute a short—say, 128-bit—authenticator (or MAC, message authentication code) for the file under the secret key. I keep the key on my person; I affix the authenticator to the file.

• Standard MAC algorithms include Poly1305, which is very fast but can handle only one file per secret key, and HMAC-SHA256, which is much slower but can handle many files per secret key.

If, when I ask the server to retrieve my file, the server tries to fool me into accepting a file that is different from the one I stored, I can recompute the authenticator using the secret key, and compare it to the one that was stored alongside the file. If they match, then it is almost certainly the file I stored. If they don't match, then the file was modified.

• The technical property that a MAC has is existential unforgeability under chosen-message attack: we conjecture, or prove in the case of one-time authenticators like Poly1305, that an adversary who can learn the authenticator for one or many messages of their choice has only negligible probability of finding the true authenticator themselves for any other message. That is, we consider a game where the adversary can query you, the bearer of the secret key, for the authenticator for one or many messages of their choice; then the adversary wins if they can find, without asking you, the correct authenticator on any other message.

What if I want someone else to be able to verify integrity, without their being able to forge the messages? For example, I want to make a promise in a contract, and publish the contract so that anyone can read it, but I don't want to let anyone else alter the contract. I first share a public key with everyone, and then use the corresponding private key to digitally sign the contract. Anyone can use the public key to verify the signature. Only I, with secret knowledge of the private key, can make a signature that will pass verification. So anyone can verify, but only I can sign.

• Standard signature algorithms include RSASSA-PSS, which is based on the mathematical magic of the RSA trapdoor permutation $$m \mapsto m^3 \bmod n$$ for $$n = pq$$ a product of large randomly chosen primes, and Ed25519, which is based on arithmetic in the scalar ring of the twisted Edwards elliptic curve $$-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$$ over the finite field $$\mathbb Z/(2^{255} - 19)\mathbb Z$$.

The technical property that a digital signature scheme has is also called existential unforgeability under chosen-message attack, but in the public-key setting where the adversary also has access to the public key in addition to being able to query you for the signature on any message of their choice.

• Using hash or cryptograpy, if the data was corrupted, It is necessary retransmission or it is recoverable? – Ed S Jul 14 '18 at 15:02
• @EdS An authenticator or signature only detects errors. It cannot correct them. Whether your protocol can recover from a failure like this, or can retransmit, depends on your protocol. – Squeamish Ossifrage Jul 14 '18 at 15:11
• @SAIPeregrinus Signing or authenticating $H(m)$ instead of $m$ itself makes you vulnerable to collisions in $H$. This mistake can be put into the design of the signature scheme itself too, like the standard and widely used RSASSA-PSS, which, despite having a randomization $r$, figures the message $m$ into the signature via $H(r \mathbin\| H(m))$ rather than $H(r \mathbin\| m)$. This mistake was actually exploited in an international incident of industrial espionage by the governments of the United States and Israel against Iran. – Squeamish Ossifrage Jul 14 '18 at 20:23
• @MartinBonner It depends on the application. Maybe each file has a unique number, in which case you can derive the one-time Poly1305 key for each file as a PRF of its file number under a long-term secret. My point in mentioning both Poly1305 and HMAC-SHA256 is that there are multiple different ways to use cryptography for data integrity with qualitatively different specific security goals and performance characteristics: one-time authenticators, many-time authenticators, digital signatures. You need to be clear on the goals in order to use them. – Squeamish Ossifrage Jul 15 '18 at 0:10
• @MartinBonner The reason I am reluctant to comment on storing a known-good SHA-256 hash is that it is tempting to take that advice and translate it into, e.g., placing a SHA-256 hash next to a download link for a file, which a priori does nothing to thwart forgery, unless the host of the web page with the download link and the SHA-256 hash is meaningfully separated from the download server. This story is more complicated and more delicate to convey. – Squeamish Ossifrage Jul 15 '18 at 0:19