Fiat-Shamir heuristic in the eyes of attackers

Overview

In this article, I’ll explain the Fiat-Sharmir heuristic from the attackers’ perspective. It means that I’ll focus on why the Fiat-Sharmir heuristic is treated as secure rather than just how it works. Specifically, this article is going to start with an interactive proof of knowledge of a discrete logarithm and discuss what role a random challenge plays (i.e., how it gets insecure if a challenge is not a random value). And then, it will switch to how the Fiat-Sharmir heuristic transforms it into a non-interactive proof. In this step, I’ll explain what happens if a hash function is comprised in an insecure way.

PS. all algorithms and attacks in this article are implemented in this code.

Interactive proof of knowledge of a discrete logarithm

First, here is an interactive proof of knowledge of a discrete logarithm. In this proof scenario, there are two actors, Peggy (prover) and Victor (verifier). And Peggy wants to prove to Victor that she knows some secret value x. (I’m going to omit finte-field-relevant stuff on purpose for the sake of simplicity)

Peggy wants to prove to Victor that she knows x in y = g^x. (sends y to Victor)
Peggy picks a random v and computes t = g^v and sends t to Victor.
Victor picks a random challenge c and sends it to Peggy.
Peggy computes r = v - cx and returns r to Victor. (the resulting proof is (t, r))
Victor checks whether t == g^r * y^c. This holds because g^r * y^c = g^v-cx * g^cx = g^v = t

The above algorithm can make sure that Victor can check whether proof (t, r) is generated by Peggy, but without revealing Peggy’s secret key. And its security relies on the fact that y = g^x → log_g(y) = x it is very difficult to solve this discrete logarithm problem (i.e., getting to know x). So, what attacking this algorithm means is computing x without having to solve the discrete logarithm. Imagine that log_g(y) = x = y + z and we already know y and z. In this case, we can know x either even without solving the discrete logarithm. This is what we will do when we refer to attacks.

– Try an attack when a random challenge `c` is constant.

What makes this algorithm secure is the presence of the random challenge c. To understand why putting a random challenge in this protocol is necessary, just assume a case where there’s no random challenge and try to compute a secret key x. (i.e., say c is always 1) And the aim of this attack is to produce a valid triple (y, t, r). This attack starts with some precomputation steps (Step 1 ~ Step 4) to get a valid triple and next does the above interactive protocol to confirm this triple is valid. (Step 5)

[attacker] pick a random v and a random r without the use of the equation r = v - x.
[attacker] compute t = g^v.
[attacker] derive y from the verification condition t = g^r * y. That is, y = t / g^r, and as we already know t and r and g, we can compute y.
[attacker] compute x = v - r. By this point, the attacker has a triple (y, t, r).
[attacker] Start the interactive protocol with the triple (y, t, r) derived from Step 1 to Step 4. If Victor confirms that this proof is valid, the attacker can assure the precomputed pair of x-y is valid.

Through the above procedure, attackers are able to compute a certain y that can be derived from v and r of their choice. Therefore, they can compute x accordingly. However, as you may notice, this attack is not a targeted attack, which means it’s not possible to compute Peggy’s secret key (who we’re targeting). Nevertheless, it’s still a valid attack as gets us a direct solution (x = v - r) to x.

– A random challenge comes to the rescue

It’s time to see how a random challenge stops the above attack. For this attack to work, the attacker is required to do some precomputations for (y, t, r). But, the attacker cannot determine t = g^r * y^c because c is a value that comes in an interactive process. That is to say, this attack can be blocked because a random challenge can stop them from doing the necessary precomputations.

Fiat-Shamir heuristic to transform it into a non-interactive one

The aforementioned interactive proof demands multiple communications between two parties in order for a proof to be verified. So, this may get ineffective in many scenarios of the real world. This is where Fiat-Shamir heuristic comes into play. It basically turns Step 3 of the interactive protocol into the use of a cryptographic hash function instead of a random challenge. It works as follows.

Peggy wants to prove to Victor that she knows x in y = g^x.
Peggy picks a random v and computes t = g^v and sends t to Victor.
Peggy computes c = H(g, t), where H is a cryptographic hash function.
Peggy computes r = v - cx. And the resulting proof is (y, t, r).
Victor or anyone checks whether t == g^r * y^c. This holds because g^r * y^c = g^v-cx * g^cx = g^v = t

The benefits of this non-interactive protocol, compared to an interactive one, are 1) there is no necessary intermediate communication, and 2) not only Victor but also anyone checks a resultant proof.

– An attack when H(g, t) is used

In this protocol, what goes into a hash function as inputs is really important to determine its security. This paper (ASIACRYPT 2012) introduced an attack against a weak fiat-shamir transformation. Specifically, the use of H(g, t) is vulnerable to this attack, and I’m going to explain how this attack works.

[attacker] pick a random v and t = g^v.
[attacker] compute c = H(g, t).
[attacker] pick a random r without the use of the equation r = v - cx.
[attacker] derive y from the verification condition t = g^r * y^c. That is, y^c = t / g^r → y = (t / g^r)^1/c, and as we already know t and r and g, we can compute y.
[attacker] compute x that matches the computed y by using x = (r - v) / c.

This attack is similar to what we did in the attack against interactive ones. The aim of it is to produce a valid triple (y, t, r) so that attackers can compute x, which is identical to what we did before. I admit that seemingly this attack doesn’t seem to cause any practical threats because anyhow we’re not able to compute a targeted public-private key pair. But, it can become a real threat in a more detailed context described in this paper. Plus, the concept of this attack (generating a valid set of values) can apply to other primitives than the discrete logarithm, and the practicality of this attack can vary on what primitive to use.

– H(g, y, t) comes to the rescue

To stop the attack, let’s consider putting y in as input to a hash function and walk through the same attack with it.

[attacker] pick a random v and t = g^v.
[attacker] compute c = H(g, y, t). → we can’t compute c because we don’t know y at this step.
[attacker] pick a random r without the use of the equation r = v - cx.
[attacker] derive y from the verification condition t = g^r * y^c. → we can’t compute y because we don’t know c.

As seen above, there is no way to compute c and y when y is unknown. Because putting y in a hash function can lead to a contradictory relationship between c and y.