0
$\begingroup$

Suppose $g$ is a pairing-friendly elliptic curve with subgroup generators $G_1$ and $G_2$. Suppose also that $M$ is the message I want to sign.

Setup

  1. Compute $A = a \cdot G_1$ and $P = p \cdot G_2$, where $a$ and $p$ are some secret values.
  2. The public key is then defined as a tuple $(A, P)$.

Signature

  1. Hash message $M$ to a number using a hash function: $m=Hash(M)$.
  2. Compute $C = \frac{p}{a \cdot m} \cdot G_2$.
  3. The signature is then defined as $C$.

Verification

  1. Compute $m = Hash(M)$.
  2. Verify that $e(A, C)^m = e(G_1, P)$.

Are there any holes in this scheme?

$\endgroup$
  • 2
    $\begingroup$ This scheme falls to the same attack as your last suggestion: You can compute any $C=1/(am)\cdot P$ to forge a message. $\endgroup$ – SEJPM Dec 19 '18 at 10:09
  • $\begingroup$ But in this scheme $a$ is not public - so, the attacker shouldn't be able to calculate $am$. Or am I missing something? $\endgroup$ – irakliy Dec 19 '18 at 14:16
  • $\begingroup$ Attackers can just choose an $a$ themselves... $\endgroup$ – SEJPM Dec 19 '18 at 14:25
  • $\begingroup$ Ah! I've updated the scheme by moving $A$ into the public key. Is it still broken? $\endgroup$ – irakliy Dec 19 '18 at 15:06
  • $\begingroup$ Let $C$ be a signature for $M$. We compute a signature for $M'$ by computing $x=H(M')/H(M)$ and $C' = \frac{1}{x}\cdot C$. $\endgroup$ – Maeher Dec 19 '18 at 15:17
3
$\begingroup$

Your proposed signature scheme falls to universal forgeries under a known message attack (UF-KMA).

The adversary $\mathcal{A}$ receives the public key $(A,P)$, a single message signature pair $(M,C)$ and the challenge message $M^*$. It outputs $$C' := \frac{H(M)}{H(M^*)} \cdot C.$$

The adversary described above is succesful with probability $1$. To see this, consider that $C$ is by definition $$C = \frac{p}{a\cdot H(M)} \cdot G_2.$$ We now have \begin{align} C' &= \frac{H(M)}{H(M^*)} \cdot C\\ &= \frac{H(M)}{H(M^*)}\cdot\frac{p}{a\cdot H(M)} \cdot G_2\\ &=\frac{p\cdot H(M)}{a\cdot H(M) H(M^*)} \cdot G_2\\ &=\frac{p}{a\cdot H(M^*)} \cdot G_2, \end{align} which is exactly the signature of $M^*$ and will therefore be accepted by the verification equation.

$\endgroup$
2
$\begingroup$

No, it doesn't work; forgeries are still easy.

Suppose the attacker has a valid signature $C$ for a message $M$ with $e(A, C)^m = e(G_1, P)$

Now, the attacker has a second message $M'$ with $m' = \text{Hash}(M')$.

Then, the attacker computes $C' = (m'^{-1} \cdot m)C$

Then, we have $e(A, C')^{m'} = e(A, m' C') = e(A, mC) = e(A, C)^m$, which agrees with the constant (for a public key) $e(G_1, P)$, and so $C'$ is a valid forgery for $M'$

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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