Sunday 27 September 2020

Implementation of kleptography in Python (SETUP attack)

My task is to reproduce the plot below:

enter image description here

It comes from this journal (pg 137-145)

In this article, the authors describe a kleptographic attack called SETUP against Diffie-Hellman keys exchange. In particular, they write this algorithm:

enter image description here

Now, in 2 the authors thought "Maybe we can implement honest DHKE and malicious DHKE, and then we compare the running time of the two algorithms". Then, the plot above was created. For this purpose, they say

"We have implemented contaminated and uncontaminated versions of Diffie-Hellman protocols in ANSI C and linked with RSAREF 2.0 library using GNU C v 2.7 compiler. All tests were run on Linux system using a computer with a Pentium II processor (350 MHz) and 64 Mb memory. Computation time for a single protocol was measured in 10- 2s."

I want to do the same, i.e. implement good and evil DH and compare the running time. This is the code I produced:

import timeit #used to measure the running time of functions
import matplotlib.pyplot as plt #plot the results
import random
import numpy as np

import pyDH #library for Diffie-Hellman key exchange

X= pyDH.DiffieHellman() #Eve's private key
Y= X.gen_public_key() #Eve's public key

#The three integers a,b,W embedded by Eve
W=3
a=2
b=2

#Honest DH
def public_key():
    d1 = pyDH.DiffieHellman()
    return d1.gen_public_key()

#Malicoius Diffie_Hellman (SETUP)  #line 1-7 in the algorithm
def mal_public_key():        
    d1 = pyDH.DiffieHellman().get_private_key()
    t=random.choice([0,1])
    z1=pow(pyDH.DiffieHellman().g,d1-W*t,pyDH.DiffieHellman().p)
    z2=pow(Y,-a*d1-b,pyDH.DiffieHellman().p)
    z= z1*z2 % pyDH.DiffieHellman().p
    d2=hash(z)
    return pow(pyDH.DiffieHellman().g,d2,pyDH.DiffieHellman().p)



#function that plot the results 
def plot(ntest=100000):
    times = []
    times2=[]

    for i in range(ntest):

        #Running time HONEST Diffie-Hellman (worked two times = two key generations)
        elapse_time = timeit.timeit(public_key, number=2)
        #here I collect the times
        times += [int(round(elapse_time* pow(10, 2) ) )]


        # Running time MALICOIUS Diffie-Hellman
        elapse_time2 = timeit.timeit(mal_public_key, number= 1)
        times2 += [int(round(elapse_time2* pow(10, 2)) )]
    x_axis=[i for i in range(0,20)]

    #collect how many tests last i seconds
    y_axis = [times.count(i) for i in x_axis]
    y_axis2 = [times2.count(i) for i in x_axis]

    plt.plot(x_axis, y_axis, x_axis, y_axis2)
    plt.show()

plot()

where I used pyDH for honest Diffie-Hellman. This code gave me this figure:

enter image description here

I think the blue line (honest DH) is ok but I'm a little bit suspicious about the orange line (SETUP DH) which is linked to this function:

def mal_public_key():     #line 1-7 in the algorithm
    d1 = pyDH.DiffieHellman().get_private_key() 
    t=random.choice([0,1])
    z1=pow(pyDH.DiffieHellman().g,d1-W*t,pyDH.DiffieHellman().p)
    z2=pow(Y,-a*d1-b,pyDH.DiffieHellman().p)
    z= z1*z2 % pyDH.DiffieHellman().p
    d2 = hash(z)
    return pow(pyDH.DiffieHellman().g,d2,pyDH.DiffieHellman().p)

  1. Can the above function be considered as an "implementation" of SETUP attack against DH? Otherwise, what would you write? (any comments to the whole code will be really appreciated)
  2. In the article, one can read:

"It is interesting that the curve representing the contaminated implementation has a small peak at the same value of computation time where the correct implementation has its only peak. [...] There are two different parts which occur every second call to device. The first one is identical to original [...] protocol and exactly this part is presented on the small peak. The disproportion between two peaks of curve representing contaminated implementation is clearly visible. The reason is that for practical usage after the first part of the protocol, (i.e. lines 1-3) device repeats the second part (i.e. lines 4-7) not once but many times."

Can you explain this statement to me? In particular, why there is no small orange peak in my plot? Maybe the mal_public_key() function is bad.

I'm working with Windows10 64bit, 8Gb RAM, AMD A10-8700P radeon R6, 10 compute cores 4C+6G 1.80GHz where I use Python 3.8. I know my computer should be better than the authors' one (I think). Maybe this can affect the results. However, here a similar experiment on an elliptic curve is showed and the plot is close to the original one (but, it's an elliptic curve).

(P.S. I assumed that a=b=2 and W=3 because Young and Young don't say what these integers should be).



from Implementation of kleptography in Python (SETUP attack)

No comments:

Post a Comment