Lecture 3: Digital signatures

Due to the birthday problem, there is an upper bound on how strong a hash function can be. For a hash function \(H: \{0, 1\}^* \to \{0, 1\}^n\) whose output is \(n\) bits long, the best we can hope for is that:

• Breaking one-wayness takes around \(2^n\) time.
• Breaking collision resistance takes around \(\sqrt{2^n} = 2^{n/2}\) time.

One application of hash functions is to improve integrity of file outsourcing. Suppose Alice wants to store a large, important file \(f\) on a cloud service like Dropbox or Google Drive. Then she can:

• Compute the hash \(h = \texttt{SHA256}(f)\) of the file before uploading it to the cloud.
• Re-compute the hash every time she downloads the file, and compare it to \(h\) to ensure the file contents have not been tampered.

Due to collision resistance, even if the malicious adversary Mallory is running the cloud provider, she cannot find a new file \(f'\) that is different from Alice’s original file \(f\) and yet still hashes to the same string \(h\).

Fortunately, there is another approach that still allows Alice to verify one file at a time. Before uploading the files, Alice must construct a Merkle tree as follows.

• Take the hash of each individual file.
• Then, take the hash of each pair of hashes.
• Only store the hash at the root of the tree.

(This data structure is named after cryptographer Ralph Merkle.)

The nice part about Merkle trees is that:

• Alice only has to store one 32-byte hash digest \(h_{1,8}\) that corresponds to, and binds together, the entire set of files \(f_1, f_2, \ldots, f_k\).
• Later, the cloud provider Mallory can send one file and prove to Alice that this file is contained “within” the Merkle tree.

To construct a proof that (for example) a claimed file \(f_3^*\) is in the set, the cloud provider Mallory sends the following \(\log(k)\) hash digests to Alice.

I put an asterisk on the received file \(f_3^*\) and the received hash digests \(h_4^*, h_{1,2}^*, h_{5,8}^*\) because Alice does not yet know that the cloud provider Mallory is telling the truth. That is, these might potentially be different than the variables that Alice used when she initially constructed the Merkle tree.

To test whether the received file \(f_3^*\) is correct, Alice can “fill in the blanks” of the path of the Merkle tree from the leaf up to the root.

\[\begin{align} h_{3}^* &= H(f_3^*) \\ h_{3,4}^* &= H(h_3^*,h_4^*) \\ h_{1,4}^* &= H(h_{1,2}^*,h_{3, 4}^*) \\ h_{1,8}^* &= H(h_{1,4}^*,h_{5,8}^*) \\ \end{align}\]

Remember that the real file \(f_3\) contributed toward \(\log(n)\) hash digests. For instance, if we “trace” the path of the file \(f_3\), here are all of the variables that it influenced.

\[\begin{align*} h_{3} &= H(f_3) \\ h_{3,4} &= H(h_3,h_4) \\ h_{1,4} &= H(h_{1,2},h_{3, 4}) \\ h_{1,8} &= H(h_{1,4},h_{5,8}) \\ \end{align*}\]

Because Alice has stored \(h_{1,8}\), she can test whether \(h_{1,8}^* = h_{1,8}\). If this equality holds:

• From the final equation: it must be true that \(h_{1,4}^* = h_{1,4}\) and \(h_{5,8}^* = h_{5,8}\). Otherwise, \(H(h_{1,4},h_{5,8}) = H(h_{1,4}^*,h_{5,8}^*)\) so Mallory has broken collision resistance.

• From the second-to-last equation: it must also be true that \(h_{1,2}^* = h_{1,2}\) and \(h_{3,4}^* = h_{3,4}\). Otherwise, \(H(h_{1,2},h_{3,4}) = H(h_{1,2}^*,h_{3,4}^*)\) so Mallory has broken collision resistance.

• …and so on, until eventually the first equation tells us that \(f_3 = f_3^*\), as desired!

In this way: hash functions provide a succinct yet tamper-evident way to represent large volumes of data.

Let’s rewind time and imagine that the date is currently November 30, 2007. At that time, here were some of the leading candidates for the 2008 U.S. presidential election.

John Edwards	Al Gore	John McCain	Barack Obama	Mitt Romney

[Images from Wikipedia]

Here’s the scenario:

• Alice claims to Bob that she can predict the outcome of the upcoming election. Specifically, she has an image file \(x\) on her computer containing a picture of her claimed winner.
• Alice and Bob would like to make a $1 bet that she knows the correct answer (which, as we now know, should be the picture of President Obama).
• However, Alice does not want to reveal \(x\) to Bob right now – if she did so, then Bob would know the result and could place a bet with other people.
• Instead, Alice would like to make the bet now, and then reveal her answer after the 2008 election.

There is a clear problem here: if Alice won’t reveal the image \(x\) until after November 2008, then how does Bob know that she knew the answer beforehand?

Question. Can we design a way to make this bet that:

• Convinces Alice that Bob will not learn \(x\) yet
• Convinces Bob in November 2008 that Alice knew \(x\) all along and never changed it?

In the physical world, here is one way to solve this question:

• Alice can write her prediction on a piece of paper and put it in an envelope.
• She can place the envelope in between Alice and Bob, in public view of both of them.

In the digital world, here is a potential way to solve this problem using cryptographic hash functions.

• In 2007, Alice can take a hash \(h = H(x)\) of the predicted winner’s image file \(x\) and send it to Bob
• After the 2008 election, Bob can take the hash of the actual winner’s image file \(x'\) and see if it equals \(h\).

Intuitively, this proposed construction looks appealing because:

• The hash function is deterministic, so hashing the same file twice will produce the same answer.
• The hash function is one-way, so it should not be possible for Bob in 2007 to compute a pre-image of \(h\).

Unfortunately, the above argument is not correct.

Question. Why not?

Commitments are a digital analog to putting a written message inside of an envelope and placing it on the table. Everyone knows that the message is inside of the envelope, but nobody can read the message until the envelope is opened.

Let’s precisely specify two guarantees provided by message commitment schemes — and also, by envelopes. To do so, we introduce our malicious adversary Mallory in place of either Alice or Bob.

• Binding: after the Commit step, it is infeasible for a malicious committer to be able to Open the commitment to two different messages \(m_1\) and \(m_2\) and have the receiver be convinced by both of them.

Mallory		Bob
	\(\overset{c}{\longrightarrow}\)

• Hiding: after the Commit step, it is infeasible for a malicious receiver to learn anything about the message \(m\) before the Open step. (That is: the receiver cannot learn the entire message \(m\), or not even the first half of \(m\), or not even the first bit with more than a 50/50 guess.)

Alice		Mallory
	\(\overset{c}{\longrightarrow}\)

Hash functions provide the binding property thanks to collision resistance. But on their own, they do not provide hiding.

Fortunately, there is a simple way to use cryptographic hash functions in order to build a commitment scheme that is both hiding and binding.

The hiding property stems from Bob’s unawareness of the randomness \(r\). Since he does not know \(r\), he cannot do a brute-force attack of all images to see which one hashes to the value \(c\).

Later in the semester, we will see other constructions and applications of commitment schemes.

A major concern in the subject [of cryptography] is that of authentication. How do you know some data is correct (data authentication), and how do you know an entity is who they claim to be (entity authentication).

– Nigel Smart, Cryptography Made Simple

Recall that a digital signature must satisfy two requirements:

• Everyone in the world should be able to verify signatures that Alice created using her secret key.
• Nobody else in the world should be able to forge signatures on messages that Alice herself never signed.

To understand the unforgeability guarantee better, it helps to introduce our adversary Mallory.

• Alice signs a message \(M\) and intends to send it to Bob.

Alice		Bob
	\(\longrightarrow\)

• However, there is a meddler-in-the-middle Mallory who intercepts the message en route.

Alice		Mallory		Bob
	\(\longrightarrow\)		\(\longrightarrow\)

We want to ensure that any attempt by Mallory to tamper with the messages from Alice to Bob will be detected:

• No matter how many messages Alice sends. Even if she sends 10, 100, or 1000 messages \(M_1, M_2, \ldots, M_{1000}\) (or more!), Mallory cannot forge any other message that Alice hasn’t sent.

• No matter which messages Alice sends. That is, for any choice of the 1000 messages \(M_1, M_2, \ldots, M_{1000}\) that Alice sent, Mallory cannot create a signature for message 1001.

Here is our formal definition.

Correctness means that for any secret/public keypair produced by KeyGen, it is the case that any signature made via the Sign algorithm is subsequently accepted by Verify.

Let’s try to construct a digital signature. It turns out that this is challenging to do. Remember that we need the following properties to hold:

• Given Alice’s public key, it is difficult to forge a signature \(\sigma\) corresponding to a message \(M\).
• Given Alice’s public key, it is easy to verify whether the signature \(\sigma\) corresponding to a message \(M\) is correct, if Alice has already created \(\sigma\) for you.

So: we need to find a math problem that is difficult to solve but easy to verify.

Unfortunately, we do not know for certain whether any such math problems exist! If you can find one, the Clay Math Institute will give you a prize of $1 million. (This is called the \(\textit{P}\) vs. \(\textit{NP}\) question.)

So we do the next best thing: build signature schemes from math problems that we believe to have this property of “difficult to solve but easy to check.” One such problem is factoring.

• Given a composite integer \(N\) that is the product of two primes, it is difficult to find the primes \(p\) and \(q\) such that \(N = pq\).
• If I told you the prime factors, you could easily multiply them together to verify whether \(p q \overset{?}{=} N\).

However, RSA is less commonly used today. The reason for this is performance, not security.

• RSA keys and signatures are small, but not that small. As shown in the image above, the RSA keys and signatures used by bu.edu are 2048 bits (or 256 bytes) long. This is because factoring is a hard problem, but it’s not a really hard problem, so we have to pick very large numbers for it to be infeasible by modern computers.

• As a result: RSA is fast, but not that fast. Signing and verification take around 1 millisecond on a modern laptop or phone, give or take.

These costs may not sound big, and indeed a single signature is small and quick to compute. But if you run a web server and calculate RSA for every client that visits your website, then the costs add up quickly.

Instead, the most common standard is called the digital signature algorithm, or DSA.

• It is based on a different math problem that is difficult to solve but easy to verify: something called the discrete logarithm problem.
• Often this algorithm is instantiated using a mathematical object called an “elliptic curve,” in which case we give it the name elliptic curve digital signature algorithm, or ECDSA.