Implementation of kleptography in Python (SETUP attack)

Question

My task is to reproduce the plot below:

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:

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:

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).

Answer 1

The problem is most easily understood using a concrete example: Alice has a device that generates Diffie-Hellman keys for her. On this device the malicious Diffie Hellman variant is implemented.

Implementation of the malicious DH variant / SETUP

The malicious DH variant is defined as follows, s. here, sec. 3.1:

MDH1: For the first generated key pair the following applies:

• The private key c₁ is a random value smaller than p-1. c₁ is stored for later use.
• The public key is calculated according to m₁ = g^c₁ mod p.
• The device provides Alice with the private key (c₁) and the public key (m₁).

MDH2: For the second generated key pair the following applies:

• A random t is chosen (0 or 1).
• z₂ is calculated according to z₂ = g^{(c₁ - Wt)} * Y^{(-ac₁ - b)} mod p.
• The private key c₂ is calculated according to H(z₂). Here H is a cryptographic hash function. c₂ is stored for later use.
• The public key is calculated according to m₂ = g^c₂ mod p.
• The device provides Alice with the private key (c₂) and the public key (m₂).

MDHi: What happens for the third and subsequent key pairs? The same algorithm is used as for the second generated key pair, i.e. for example for the third key exchange, c₂ is now used instead of c₁ and m₂ is now used instead of m₁, or in general if the i-th key pair c_i, m_i is generated:

• A random t is chosen (0 or 1).
• z_i is calculated according to z_i = g^{(c_i-1 - Wt)} * Y^{(-ac_i-1 - b)} mod p.
• The private key c_i is calculated according to H(z_i). Here H is (the same) cryptographic hash function. c_i is stored for later use.
• The public key is calculated according to m_i = g^c_i mod p.
• The device provides Alice with the private key (c_i) and the public key (m_i).

Note that there are two categories of key exchange processes, MDH1 and MDHi, which will later play an important role in the discussion of timing behavior.

Evaluation of the posted implementation of the malicious DH variant:
SETUP (Secretly Embedded Trapdoor with Universal Protection) is not implemented by the implementation of the malicious DH variant posted in the question.
SETUP establishes a relationship between two consecutive generated key pairs. This makes it possible to derive the private key of the last key generation from two such correlated public keys, which can be intercepted e.g. during the key exchange process.
But for this, the private key must be passed between successive key generations to use it in the last key generation for establishing this relationship. This does not happen in the implementation, so that the required relationship cannot be achieved.
From a more technical point of view, the implementation fails mainly because the cases MDH1 and MDHi are not implemented separately but together as a closed process. Closed in the sense that the private key is not stored between successive calls, so it cannot be passed on. Subsequent calls of the implementation therefore generate random key pairs that are not in the required relationship to each other.
Also note that from the similar time behaviour (only similar, because e.g. the secondary peak is missing, which will be discussed below) of the posted implementation and the implementation used in the papers, of course no working implementation can be concluded.

A working Python implementation of SETUP or the malicious Diffie-Hellman variant could look like this:

import timeit 
import matplotlib.pyplot as plt 
import Crypto.Random.random
import hashlib
import pyDH 

DH = pyDH.DiffieHellman()
xBytes = bytes.fromhex("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f")
X = int.from_bytes(xBytes, 'big')   #Attacker's private key
Y = pow(DH.g, X, DH.p)              #Attacker's public key
W = 3
a = 1
b = 2
...
privateKey = -1
def maliciousDH():
    
    global privateKey
    DH = pyDH.DiffieHellman()
    
    if privateKey == -1:
        privateKeyBytes =  Crypto.Random.get_random_bytes(32)
        privateKey = int.from_bytes(privateKeyBytes, 'big')
        publicKey = pow(DH.g, privateKey, DH.p)
        return publicKey
    else:
        t = Crypto.Random.random.choice([0,1])
        z1 = pow(DH.g, privateKey - W*t, DH.p)
        z2 = pow(Y, -a*privateKey - b, DH.p)
        z = z1 * z2 % DH.p
        privateKey = hashVal(z)
        publicKey = pow(DH.g, privateKey, DH.p)
        return publicKey
        
def hashVal(value):
    valBytes = value.to_bytes((value.bit_length() + 7) // 8, 'big')
    hashBytes = hashlib.sha256(valBytes).digest()
    hashInt = int.from_bytes(hashBytes, 'big')
    return hashInt
    

Please note the following:

• The case privateKey == -1 corresponds to the generation of the first key pair (MDH1), the other case to the generation of the following key pairs (MDHi). The private key is stored in the global variable privateKey.
• W, a, b are constants that are known to the attacker. X, Y are the key pair of the attacker. Only the attacker as owner of the private key X can perform the attack. W, a, b are freely choosable constants, which should introduce randomness. W is odd by definition.
• Cryptographic functions are used to generate random data (from Crypto.Random, e.g. the private keys) and the hashs (SHA256 digest).
• pyDH is only used to generate p and g.

The following function now generates 5 consecutive key pairs for Alice:

def maliciousDHRepeated(nRepeats):
    for repeat in range(nRepeats):  
        publicKey = maliciousDH()
        print('Key Exchange: {0}\nPublic Key:  {1}\nPrivate Key: {2}\n'.format(repeat, publicKey, privateKey))
maliciousDHRepeated(5)     

The output looks e.g. as follows:

Key Exchange: 0
Public Key:  18226633224055651343513608182055895594759078768444742995197429721573909831828316605245608159842524932769748407369962509403625808125978764850049011735149830412617126856825222066673989542531319225049606268752217216534778109596553167314895529287398326587713050976475410688145977311375672549266099133534202232996468144930213166214281451969286299514333332818247602266349875280576154902929160410595469062077684241858299388027340353827453534708956747631487004964946083413862389303833607835673755108949997895120758537057516467051311896742665758073078276178999259778767868295638521495976727377437778558494902010641893884127920
Private Key: 4392204374130125010330067842931188140034970327696589536054104764110713347126

Key Exchange: 1
Public Key:  30139618311151172765747180096035363693813051643690049553112194419098573739435580694888705607377666692401242533649667511485491747154556435118981839182970647673078490062996731957675595514634816595774261281319221404554602729724229286827390637649730469857732523498876684012366691655212568572203566445090111040033177144082954609583224066018767573710168898588215102016371545497586869795312982374868713234724720605552587419481534907792549991537554874489150528107800132171517459832877225822636558667670295657035332169649489708322429766192381544866291328725439248413336010141524449750548289234620983542492600882034426335715286
Private Key: 3611479293587046962518596774086804037937636733424448476968655857365061813747

Key Exchange: 2
Public Key:  15021809215915928817738182897850696714304022153200417823361919535871968087042467291587809018574692005905960913634048699743462124350711726491325639829348819265101140044881197573825573242439657057004277508875703449827687125018726500056235788271729552163855744357971593116349805054557752316498471702822698997323082247192241750099101807453692393170567790930805933977981635528696056267034337822347299945659257479795868510784724622533533407893475292593560877530083021377556080457647318869173210614687548861303039851452268391725700391477968193268054391569885481465079263633084038436082726915496351243387434434747413479966869
Private Key: 60238983934252145167590500466393092258324199134626435320227945202690746633424

Key Exchange: 3
Public Key:  10734077925995936749728900841226052313744498030619019606720177499132029904239020745125405126713523340876577377685679745194099270648038862447581601078565944941187694038253454951671644736332158734087472188874069332741118722988900754423479460535064533867667442756344440676583179886192206646721969399316522205542274029421077750159152806910322245234676026617311998560439487358561468993386759527957631649439920242228063598908755800970876077082845023854156477810356816239577567741067576206713910926615601025551542922545468685517450134977861564984442071615928397542549964474043544099258656296307792809119600776707470658907443
Private Key: 62940568050867023135180138841026300273520492550529251098760141281800354913131

Key Exchange: 4
Public Key:  2425486506974365273326155229800001628001265676036580545490312140179127686868492011994151785383963618955049941820322807563286674799447812191829716334313989776868220232473407985110168712017130778639844427996734182094558266926956379518534350404029678111523307272488057571760438620025027821267299005190378538083215345831756055838193240337363440449096741629258341463744397835411230218521658062737568519574165810330776930112569624066663275971997360960116063343238010922620695431389619027278076763449139206478745130163740678443228451977971659504896731844067323138748945493668050217811755122279988027033740720863980805941221
Private Key: 3330795034653139675928270510449092467425071094588264172648356254062467669676

---

Verification

To verify the implementation, two tests are performed:

Test 1: Are the generated key pairs Diffie-Hellman pairs? This can be verified by comparing the generated secrets, e.g. as follows (for Alice the key pair from exchange process 4 is taken):

def determineSecrets():
    
    # Bob's key pair
    DH = pyDH.DiffieHellman()
    privateKeyBob = DH.get_private_key()
    publicKeyBob = DH.gen_public_key() 
    
    #Alice's key pair (from Key Exchange 4)
    privateKeyAlice = 3330795034653139675928270510449092467425071094588264172648356254062467669676
    publicKeyAlice = 2425486506974365273326155229800001628001265676036580545490312140179127686868492011994151785383963618955049941820322807563286674799447812191829716334313989776868220232473407985110168712017130778639844427996734182094558266926956379518534350404029678111523307272488057571760438620025027821267299005190378538083215345831756055838193240337363440449096741629258341463744397835411230218521658062737568519574165810330776930112569624066663275971997360960116063343238010922620695431389619027278076763449139206478745130163740678443228451977971659504896731844067323138748945493668050217811755122279988027033740720863980805941221
    
    #Secrets
    secretBob = pow(publicKeyAlice, privateKeyBob, DH.p)
    secretAlice  = pow(publicKeyBob, privateKeyAlice, DH.p)
    
    print("Bob's secret:    {0}\nAlices's secret: {1}\n".format(secretBob, secretAlice))
    
determineSecrets()

The calculated secrets are identical:

Bob's secret:    7003831476740338689134311867440050698619657722218522238000557307099433806548522159881608160975874841852430612290661550184838734726150744064473827597359598057583882560698588377500873394072081781357504452653998970161870108172814907873339750240946592215609078441859786431410312119968080615568505910664062291703601148542762668346870718638131670350107907779759989388216242619752036996919178837249552098220438246127095430336587506739324288803914290366560286806624611103226334708363046293511682782019638354540305524062643841864120561080971292493441027391819191342193393031588366711412191000779126089156632829354631140805980
Alices's secret: 7003831476740338689134311867440050698619657722218522238000557307099433806548522159881608160975874841852430612290661550184838734726150744064473827597359598057583882560698588377500873394072081781357504452653998970161870108172814907873339750240946592215609078441859786431410312119968080615568505910664062291703601148542762668346870718638131670350107907779759989388216242619752036996919178837249552098220438246127095430336587506739324288803914290366560286806624611103226334708363046293511682782019638354540305524062643841864120561080971292493441027391819191342193393031588366711412191000779126089156632829354631140805980

Test 2: Can the attacker determine Alice's private keys?

The algorithm for deriving the keys is, s. here, sec. 3.1:

• Determination of r according to r = m_i-1^a * g^b mod p
• Determination of u according to u = m_i-1/r^X mod p. If m_i = g^H(u) mod p, then the private key is c_i = H(u) and end
• Determination of v according to v = u/g^W mod p. If m_i = g^H(v) mod p, then the private key is c_i = H(v)

Apart from the constants W, a, b and the private key X, which the attacker knows all, only the public keys m_i and m_i-1 are needed to determine the private key c_i.

A possible implementation of this algorithm is:

def stealPrivateKey(currentPublicKey, previousPublicKey):
    r = pow(previousPublicKey, a, DH.p) * pow(DH.g, b, DH.p) % DH.p
    u = previousPublicKey * pow(r, -X, DH.p) % DH.p
    if currentPublicKey == pow(DH.g, hashVal(u), DH.p):
        return hashVal(u)
    v = u * pow(DH.g, -W, DH.p) % DH.p
    if currentPublicKey == pow(DH.g, hashVal(v), DH.p):
        return hashVal(v)
    return -1

For verification the public keys from the key exchange processes 3 and 4 are used:

previousPublicKey = 10734077925995936749728900841226052313744498030619019606720177499132029904239020745125405126713523340876577377685679745194099270648038862447581601078565944941187694038253454951671644736332158734087472188874069332741118722988900754423479460535064533867667442756344440676583179886192206646721969399316522205542274029421077750159152806910322245234676026617311998560439487358561468993386759527957631649439920242228063598908755800970876077082845023854156477810356816239577567741067576206713910926615601025551542922545468685517450134977861564984442071615928397542549964474043544099258656296307792809119600776707470658907443
currentPublicKey = 2425486506974365273326155229800001628001265676036580545490312140179127686868492011994151785383963618955049941820322807563286674799447812191829716334313989776868220232473407985110168712017130778639844427996734182094558266926956379518534350404029678111523307272488057571760438620025027821267299005190378538083215345831756055838193240337363440449096741629258341463744397835411230218521658062737568519574165810330776930112569624066663275971997360960116063343238010922620695431389619027278076763449139206478745130163740678443228451977971659504896731844067323138748945493668050217811755122279988027033740720863980805941221
currentPrivateKey = stealPrivateKey(currentPublicKey, previousPublicKey)
print(currentPrivateKey)

The result is

3330795034653139675928270510449092467425071094588264172648356254062467669676

and thus corresponds to the private key from key exchange 4.

---

Analysis of time behaviour

To compare the timing behavior of the malicious and standard DH variant, an implementation of the standard DH variant is required:

SDHi: For all generated key pairs the following applies:

• The private key c_i is a random value smaller than p-1.
• The public key is calculated according to m_i = g^c_i mod p.
• The device provides Alice with the private key (c_i) and the public key (m_i).

with e.g. the following implementation:

def standardDH():
    
    DH = pyDH.DiffieHellman()
    privateKeyBytes = Crypto.Random.get_random_bytes(32)
    privateKey = int.from_bytes(privateKeyBytes, 'big')
    publicKey = pow(DH.g, privateKey, DH.p)
    return publicKey

The comparison between malicious and standard DH variant is performed with the following implementation:

def plot(nTests = 1000, nKeyExPerTest = 10):
    
    global privateKey
    
    timesStandardDH = []
    timesMaliciousDH = []

    for test in range(nTests): 
               
        for keyExPerTest in range(nKeyExPerTest):
            elapseTimeStandardDH = timeit.timeit(standardDH, number = 1)
            timesStandardDH += [int(round(elapseTimeStandardDH * pow(10, 3) ) )]
        privateKey = -1
        for keyExPerTest in range(nKeyExPerTest):
            elapseTimeMaliciousDH = timeit.timeit(maliciousDH, number = 1)
            timesMaliciousDH += [int(round(elapseTimeMaliciousDH * pow(10, 3)) )]
                    
    x_axis=[i for i in range(0, 50)]       
    y_axisStandardDH = [timesStandardDH.count(i) for i in x_axis]
    y_axisMaliciousDH = [timesMaliciousDH.count(i) for i in x_axis]

    plt.plot(x_axis, y_axisStandardDH, x_axis, y_axisMaliciousDH)
    plt.show()

plot()

The following applies here:

• nTests = 1000 tests are performed.
• For each test nKeyExPerTest = 10 key exchange processes are performed. privateKey = -1 ensures that each test starts again with MDH1.
• For each key exchange process the duration is measured and a frequency distribution of the duration is created.
• All measurements were performed with an Intel Core i7-6700 processor (3.40 GHz), Cores/Threads: 4/8, 16 GB RAM, NVIDIA Geforce GTX 960/4GB under Win10/64 bit and Python 3.8.

The following two figures show this frequency distribution of the duration of the key exchange process:

Left: x-axis: x 1000^-1 sec, right: x-axis: x 10000^-1 sec

The figures correspond qualitatively to the figures posted from the papers:

• As expected, the main peak of the malicious Diffie-Hellman variant is at higher time values than the main peak of the standard DH variant. The ratio is similar at about 3.
• The malicious Diffie-Hellman variant has a secondary peak at the main peak of the standard DH variant.
• The secondary peak of the malicious DH variant is significantly smaller than the main peak of the malicious DH variant.
• Deviations in the waveform are probably due to different implementations, different hardware etc.

Explanation of the secondary peak of the malicious DH variant:
In the case of the malicious DH variant, there are two different cases, MDH1 and MDHi. MDH1 corresponds practically to the case of the standard DH variant SDHi. This is the reason why the secondary peak of the malicious and the main peak of the standard DH variant coincide.
However, MDH1 and MDHi occur at different frequencies. E.g. for the tests, 10 key exchange processes per test were defined, i.e. the ratio of MDH1 to MDHi exchanges is 1:9, which explains the significantly smaller secondary peak relative to the main peak.
The code could easily be changed to randomly determine the number of key exchange processes per test, which would be more realistic. But with a fixed number of key exchange processes the relations are easier to illustrate.
Why does the secondary peak not appear in the implementation of the malicious DH variant posted in the question? This is because this implementation combines the cases MDH1 and MDHi and implements them as one case, so that only a single value is measured.

Finally, here is a link to a helpful work of Eindhoven University of Technology on this topic.