Proving a Forged Signature — The Fail-stop Signature Method

Proving a Forged Signature — The Fail-stop Signature Method

I did a pre-interview with the mighty Torben P Pedersen (famous for the Pedersen Commitment) [here], and will be following up with a full interview, soon. Torben has contributed so much to cryptography of the decades, so let’s take a look at his work on fail-stop signatures:

At the time, Torben was at Aarhus University in Denmark, and Engene at CWI in Amsterdam [here]. With the fail-stop signature, a forgery can be detected, and then the signing mechanism no longer used. We have various properties for this:

• If Alice has signed a message, Bob should be able to accept it.
• Eve cannot forge the signature, without going costly work.
• If Eve manages to create a forgery, Alice can prove with a proof-of-sorgery.
• Alice cannot produce a signature which at a future time will be marked as a forgery.

So, how do you detect a forger? Well, get them to do something that is valid, but to become valid, there’s a few different options that the forger could use to make the fake. If there are lots of options to select from, the forger is unlikely to pick the right one, and we’ll be able to detect a forger a work.

With the van Heijst-Pedersen meethod [1], the generation of the keys is split between the TTP (trusted third partner) and Alice. The TTP generates two prime numbers q and p, and where q divides into p−1. Next the TTP selects a generator value (g) and computes α) such that:

Next select a random value of a from 0 to q−1 and computes:

The TTP sends (p,q,α,β) to Alice. Alice now selects four random values (x1,x2,y1,y2) . She then computes:

Alice creates a signature for message (M) with:

The signatures is then (sig1,sig2). Bob verifiers with:

If v1 is equal to v2 is signature is correct. The signature proof is:

This method is a one time signing scheme.

Detecting the forgery

Now for the elements of the public key (β1,β2), we can have other possible values for x′1,x′2,y′1,y′2. A forger will try to generate the values of β1 and β2 with x′1,x′2,y′1,y′2 . In the following the forger can discover the alternative values:

try:
  for x1 in range(1,q-1):
    for x2 in range(1,q-1):
      for y1 in range(1,q-1):
        for y2 in range(1,q-1):
          beta1fake = (pow(alpha,x1,p)*pow(beta,x2,p)) % p
          beta2fake = (pow(alpha,y1,p)*pow(beta,y2,p)) % p
          if (beta1==beta1fake and beta2==beta2fake): raise StopIteration
except StopIteration: pass
        
sig1fake = (x1+ m*y1) % q
sig2fake = (x2+m*y2)  % q

print (f"\nx1={x1}, x2={x2}")
print (f"y1={y1}, y2={y2}")
print (f"\nSig1={sig1fake}, Sig2={sig2fake}")

The forger can then publish x′1,x′2,y′1,y′2 and signfake1(s′1) and signfake2(s′2) and it will appear valid. The fake is detected by computing:

The coding is here:

import random
import libnum
import sympy

from Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes

import sys

primebits=8

if (len(sys.argv)>1):
  primebits=int(sys.argv[1])

if primebits>128: primebits=128

isprime=False

# For q, search for a prime q that is a factor of p-1

while (isprime==False):
  p = getPrime(primebits, randfunc=get_random_bytes)
  q = p//2
  if (sympy.isprime(q) and sympy.gcd(q,p-1)>1): isprime=True

alpha=1
while (alpha==1):
  g=3
  alpha = pow(g,(p-1)//q,p)

a=random.randint(1,q-1)
beta=pow(alpha,a,p)

m=10

x1 = random.randint(1,q-1)
x2 = random.randint(1,q-1)
y1 = random.randint(1,q-1)
y2 = random.randint(1,q-1)

print("\nAlice's private key:")
print (f"x1={x1}, x2={x2}, y1={y1}, y2={x2} ")

beta1 = (pow(alpha,x1,p)*pow(beta,x2,p)) % p
beta2 = (pow(alpha,y1,p)*pow(beta,y2,p)) % p

print("\nAlice's public key:")
print (f"p={p}, q={q}, alpha={alpha}, beta={beta}, beta1={beta1}, beta2={beta2}")

sig1 = (x1+ m*y1) % q
sig2 = (x2+m*y2)  % q

print (f"\nx1={x1}, x2={x2}")
print (f"y1={y1}, y2={y2}")
print (f"\nSig1={sig1}, Sig2={sig2}")

v1=(beta1*pow(beta2,m,p)) % p
v2=(pow(alpha,sig1,p)*pow(beta,sig2,p)) % p

print (f"v1={v1}, v2={v2}")
if (v1==v2): print("Signature checks okay")
else: print("Bad signature")

# ===== Fake
if (primebits>8): sys.exit()
print ("\n\nNow let's generate a fake...")

try:
  for x1 in range(1,q-1):
    for x2 in range(1,q-1):
      for y1 in range(1,q-1):
        for y2 in range(1,q-1):
          beta1fake = (pow(alpha,x1,p)*pow(beta,x2,p)) % p
          beta2fake = (pow(alpha,y1,p)*pow(beta,y2,p)) % p
          if (beta1==beta1fake and beta2==beta2fake): raise StopIteration
except StopIteration: pass
        
sig1fake = (x1+ m*y1) % q
sig2fake = (x2+m*y2)  % q

print (f"\nx1={x1}, x2={x2}")
print (f"y1={y1}, y2={y2}")
print (f"\nSig1={sig1fake}, Sig2={sig2fake}")

s1diff= (sig1-sig1fake)%q
s2diff= libnum.invmod(sig2-sig2fake,q)

aval=(s1diff * s2diff) % q

print (f"aval={aval}, a={a}")

A sample run is:

Alice's public key:
172416440120879 86208220060439 9 3

Alice's private key:
a:  32435590251523
Sigs  57589080246324 79290697369458
v1= 74539090295259 v2= 74539090295259

If we use 8-bit primes, the program searches for a fake value of the private key. Here is a run:

Alice's private key:
x1=47, x2=74, y1=69, y2=74 

Alice's public key:
p=179, q=89, alpha=9, beta=147, beta1=173, beta2=146

x1=47, x2=74
y1=69, y2=52

Sig1=25, Sig2=60
v1=16, v2=16
Signature checks okay

Now let's generate a fake...

x1=1, x2=32
y1=1, y2=17

Sig1=11, Sig2=24
aval=35, a=54

Here is a demo:

and the code:

References

[1] van Heijst, E., Pedersen, T. P., & Pfitzmann, B. (1992, August). New constructions of fail-stop signatures and lower bounds. In Annual International Cryptology Conference (pp. 15–30). Springer, Berlin, Heidelberg [here].