Image for post
Image for post
Photo by Cytonn Photography on Unsplash

Proving a Forged Signature — The Fail-stop Signature Method

Prof Bill Buchanan OBE
Oct 17 · 5 min read

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:

Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

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

Image for post
Image for post

Alice creates a signature for message (M) with:

Image for post
Image for post

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

Image for post
Image for post

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

Image for post
Image for post

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:

Image for post
Image for post

The coding is here:

import random
import libnum
import sympy
from Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes
import sysprimebits=8if (len(sys.argv)>1):
primebits=int(sys.argv[1])
if primebits>128: primebits=128isprime=False# For q, search for a prime q that is a factor of p-1while (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=10x1 = 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) % qprint (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].

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store