Proposal : An Integrated Zero Knowledge Authentication and Public key verification protocol using Gap Diffie Hellman Groups to counter MITM attack

Introduction : The basic idea behind the proposal is to integrate authentication and key distribution protocol. Immense work has been done to design a secure key distribution protocol starting with Needham Schroeder and evolving to OAKELEY, SKEME, IKE and ultimately to Diffie Hellman Protocol and PKI. Though much work has been done in the field of Data Integrity, Non Repudiation and Secrecy, password based authentication is still the Achilles heel of cryptography.  In the presence of Byzantine Adversaries like Man In The Middle(MITM) even a combination of multi factor authentication and PKI fails.

The Gap-DH problem
Okamoto and Pointcheval formalized the gap between inverting and decisional
problem . In particular, they applied it to the Diffie-Hellman problems:
– The Inverting Diffie-Hellman Problem (C-DH) (a.k.a. the Computational
Diffie-Hellman Problem): given a triple of G elements (g, g^a, g^b), find the
element C = g^ab.
The Decision Diffie-Hellman Problem (D-DH): given a quadruple of G elements
(g, g^a, g^b, g^c), decide whether c = ab mod q or not.
The Gap Diffie-Hellman Problem (G-DH): given a triple (g, g^a, g^b), find the
element C = g^ab with the help of a Decision Diffie-Hellman Oracle (which
answers whether a given quadruple is a Diffie-Hellman quadruple or not).

Bilinear maps and pairings 

The bilinear maps used in cryptography are the Weil and Tate pairings on some
elliptic curves.

Let G and G1 be two groups of order some large prime q, denoted
multiplicatively. An admissible bilinear map is a map e : G × G ->G1 that is:
– bilinear: e(ga, hb) = e(g, h)ab for all g, h 2 G and all a, b  belongs to Z,
– non-degenerate: for g and h two generators of G, we have e(g, h) =/= 1,
– computable: there exists an efficient algorithm to compute e(g, h) for any
g, h belongs to G.
In the case of the Weil and Tate pairings, G is a subgroup of the additive group
of points of an elliptic curve E/Fp, and G1 is the multiplicative group of the
extension field Fp2 . However, in order to remain close to the identification scheme
of Schnorr, we choose to keep the multiplicative notation both for G and G1.

Proposed Protocol 

From now on, G is a group in which the Gap Diffie-Hellman problem is intractable.
We assume the existence of an admissible linear map e : G×G -> G1
and G and G1 are of order q and we denote by g a generator of G.
The prover holds public parameters

g, g^a, g^n, e(g, g), v = e(g, g)^a

and a secret S = g^a. Here public key is g^n, where n is the corresponding private key. The value v is given in the public parameters in order to withdraw its computation by the verifier. The scheme we propose is a zero-knowledge proof of knowledge of the
value g^a obtained by iterating l times the algorithm. Along with the proof of knowledge the public key of the Prover is embedded into the proof so that while verifying the secret’s knowledge, the verifier will also enter the public key of prover as a parameter and verify the authenticity of the secret as well as of the key. So from now onwards, Man In The Middle cannot just forward the prover’s proof and forward his public key to establish a secure channel. MITM will be unable to separate the key part from the proof of secret provided and thus will be incapable of carrying out attacks like active phishing where he first forwards his public key to server and then user’s credentials. By using the proposed protocol server will detect that the credentials forwarded does not belong to the particular public key supplied earlier to establish the secure channel.

Step 1: Here Prover choose a random number in the prescribed range and computer W ( a mapping on G1).  Then we introduce the public key in the picture and computer mapping of public key using the random number r. ‘r’ is only known to the prover and is created for obfuscation. The result V is sent to the verifier.

Step 2: The Verifier computes another random number c and sends it to Prover.

Step 3: The Prover uses c to computer a product Y on G, which comprises of secret, unknown r and public key computed r-1 times.

Step 4. The Verifier multiplies the resultant Y with the known public key of prover and computes its mapping. If the mapping is equivalent to the product of mapping received in step 1 and mapping of secret c times then the proof is accepted.

To prove the security of the scheme under the G-DH problem, we follow the
outline of general zero-knowledge proofs. Namely, we prove the completeness and the soundness of the scheme. Finally we prove the protocol is zero-knowledge.
During the proof, the prover and the verifier are modeled by Probabilistic
Polynomial time Turing Machines (PPTM).


If the legitimate prover and the verifier both follow the scheme, then it always
succeeds. Indeed, at each iteration, the probability of success is equal to 1 since:

e(g, Z ) = e(g, g^r × g^ac × g^nr) = e(g, g)r+ac+nr = e(g, g)^r × e(g, g)^ac ×  e(g, g) ^nr=

{e(g, g) ^nr ×  e(g, g)^r} × e(g, g)^ac = V ×

Zero Knowledge

The present identification scheme satisfies the zero-knowledge property. To simulate
in polynomial time (in |I|) the communications between a real prover and
a (not necessarily honest) verifier, we use the following algorithm M :
For the simulation of one round, M randomly picks c in [[0, 2k[[, randomly
picks Y in G and computes W = e(g, Y ) × v−1. M then sends W to the verifier
which answers ˜c. If c = ˜c then the triple (W, c, Y ) is kept, otherwise M computes method.
In average, the equality c = ˜c holds after 2^k tests. To obtain, l triples, M
constructs l×2^k triples. If l×2^k is polynomial in |I|, then we obtain a polynomial
time algorithm.


(under work )

About Siddharth Sharma

Interested in machine learning, big data analytics, Online Advertisements analytics, Probabilistic graphical models, predictive analytics, Game AI, Automated Learning, cryptography, authentication systems, ECC, pairing based cryptography, zero knowledge proofs, key generation and distribution, homomorphic encryption, blind signatures, anonymous credential systems, Pseudo Random Number Generators,randomized algorithms, stochastic optimization
This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.

1 Response to Proposal : An Integrated Zero Knowledge Authentication and Public key verification protocol using Gap Diffie Hellman Groups to counter MITM attack

  1. Pingback: Network Security: Wrote a brief proposal on solving Man in the middle ( active phishing ) via combining Zero knowledge authentication with public key verification. Any views? - Quora

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s