Does the nonce really have to be hashed as part of the challenge in a Schnorr signature?

Question

From this article: https://tlu.tarilabs.com/cryptography/digital_signatures/introduction_schnorr_signatures.html#why-do-we-need-the-nonce

The article states that the challenge e = H(P || m) is insecure, and that e = H(R || P || m) should be used instead. The signature is s = k * e, where k is the private key.

My question is: what if we used the insecure challenge e = H(P || m) and made the nonce part of the signature like so: s = r + (k * e)? Would that still be secure, or is there a way to extract the private key with this approach?

I've tried to adapt the Rust code example to see if the secret key could still be extracted from the public information with this adapted signature scheme, but it looks like it's still not possible:

extern crate libsecp256k1_rs as secp256k1;

use secp256k1::{SecretKey, PublicKey, thread_rng, Message};
use secp256k1::schnorr::{ Challenge};

// This one tests that adding r/R makes key extraction impossible
#[allow(non_snake_case)]
fn main() {
    // Create a random private key
    let mut rng = thread_rng();
    let r = SecretKey::random(&mut rng);
    println!("My private random value is: {}", r);

    let R = PublicKey::from_secret_key(&r);

    let k = SecretKey::random(&mut rng);
    println!("My private key: {}", k);

    let P = PublicKey::from_secret_key(&k);

    // Challenge, e = H(P || m)
    let m = Message::hash(b"Meet me at 12").unwrap();
    let e = Challenge::new(&[&P, &m]).as_scalar().unwrap();

    // Signature (with nonce)
    let s = r + (e * k);

    // Verify the signature
    assert_eq!(PublicKey::from_secret_key(&s), R + (e*P));
    println!("Signature is valid!");

    let hacked = s * e.inv();
    assert_eq!(k, hacked);  // fails
    println!("Hacked key:     {}", k)
}

Answer 1

A signature under a public key $P$ is a pair $(R,s)$ such that $[s]G = R + [e]P$, where $G$ is the standard base point, and $e$ is the challenge.

If $e = H(P, m)$ doesn't involve $R$, then I can just pick $s$ arbitrarily and compute $R = [s]G - [e]P$ to forge any signature I want.

---

The motivation for the Schnorr signature scheme is the Schnorr identification protocol, whereby a prover named Peggy aims to convince a verifier named Victor that she knows the secret $k$ such that $P = [k]G$—that is, $\log_G P$, the discrete log of $P$. The dialogue goes something like this:

VICTOR (given $P$): Hey Peggy, do you know $\log_G P$?

PEGGY (chooses $r$ uniformly at random, computes $R = [r]G$): Yes, but I can't tell you directly. Instead, here's another point I know the discrete log of: $R$.

VICTOR (chooses $e$ uniformly at random): OK. Can you tell me what $\log_G R + e \log_G P$ is?

PEGGY (computes $s := r + e k$): Why, yes, in fact—it's $s$.

VICTOR (confirms $[s]G \stackrel?= R + [e]P$): whoa…OK, I guess maybe you do know $\log_G P$.

This protocol is guaranteed not to leak $k$ as long as Peggy chooses $r$ and Victor chooses $e$ independently and uniformly at random each time—in other words, it's an honest-verifier zero-knowledge protocol.

This protocol is convincing to Victor because, if you think of Peggy as a machine (typical of a man like Victor to do in a patriarchal society!), and you suspend the computation in the middle and run it forward with two different challenges $e$ and $e'$, then the resulting values $s$ and $s'$ lead to recovery of $k$ by $(s - s')/(e - e')$, so unless Peggy just got astonishingly lucky for one run (we work with a space of possibilities for $e$ so large that this is not plausible), she must know $k$.

On the other hand, if Peggy doesn't choose $R$ until she already knows what the challenge is, she could just choose $s$ arbitrarily and then derive $R := [s]G - [e]P$. That's why it's crucial that she commit to $R$ by sharing it with Victor first.

We turn this protocol into a signature scheme by the Fiat–Shamir heuristic: We simulate the challenge that Victor would have chosen, by a random oracle; then instead of an interaction, we get a noninteractive receipt that Peggy can compute on her own, and that anyone in the world can verify later on requiring no further interaction with Peggy. For the Fiat–Shamir heuristic to work, though, we have to pass in everything Peggy would have committed to Victor so far in the protocol. That means, in this case, that we have to pass in $R$ and whatever message $m$ Peggy wants to attest to.

---

You're not the first person to wonder about this! This trick—forgetting to hash in $R$ along with everything else—was used recently by the Swiss election authority to fail to convince cryptographers that their newfangled electronic voting system is verifiable—along with some other tricks—despite reams of paper on cryptidigitation to prove their software correct. Also the New South Wales election authority, with the same software, despite being alerted to the problem at the same time.