Python中的kleptography的实现（SETUP攻击）

Question

我的任务是重现下面的情节：

它来自这个期刊（第 137-145 页）

在本文中，作者描述了一种针对 Diffie-Hellman 密钥交换的名为 SETUP 的窃取攻击。特别是，他们编写了这个算法：

现在，在2中作者认为“也许我们可以实现诚实的 DHKE 和恶意的 DHKE，然后我们比较两种算法的运行时间”。然后，创建了上面的情节。为此，他们说

“我们在 ANSI C 中实施了受污染和未受污染的 Diffie-Hellman 协议版本，并使用 GNU C v 2.7 编译器与 RSAREF 2.0 库链接。所有测试均在 Linux 系统上运行，使用一台配备 Pentium II 处理器（350 MHz）和 64 Mb 内存。单个协议的计算时间测量为 10-2 秒。”

我想做同样的事情，即实现善恶DH并比较运行时间。这是我生成的代码：

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

我在那里使用pyDH作为诚实的 Diffie-Hellman。这段代码给了我这个数字：

我认为蓝线（诚实的 DH）没问题，但我对与此功能相关联的橙色线（SETUP DH）有点怀疑：

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. 上述功能是否可以认为是SETUP攻击DH的“实现”？不然怎么写？（对整个代码的任何评论将不胜感激）
2. 在文章中，您可以阅读：

“有趣的是，代表受污染实现的曲线在计算时间的相同值处有一个小峰值，而正确的实现只有它的峰值。[...] 每隔一次调用设备就会发生两个不同的部分。第一个与原始 [...] 协议相同，这部分恰好显示在小峰上。代表受污染实施的曲线的两个峰之间的不比例清晰可见。原因是在第一部分之后的实际使用中协议，（即第 1-3 行）设备重复第二部分（即第 4-7 行）不是一次而是多次。”

你能向我解释一下这个说法吗？特别是，为什么我的情节中没有小橙色峰？可能是mal_public_key()功能不好。

我正在使用 Windows10 64 位、8Gb RAM、AMD A10-8700P radeon R6、10 个计算内核 4C+6G 1.80GHz，其中我使用 Python 3.8。我知道我的电脑应该比作者的好（我认为）。也许这会影响结果。然而，这里显示了一个关于椭圆曲线的类似实验，并且该图与原始图很接近（但是，它是一条椭圆曲线）。

（PS我以为，a=b=2和W=3因为年轻而年轻不说这些整数应该是什么）。

Answer 1

使用一个具体的例子最容易理解这个问题：Alice 有一个为她生成 Diffie-Hellman 密钥的设备。在此设备上实施了恶意的 Diffie Hellman 变体。

恶意DH变种/SETUP的实现

恶意DH变体定义如下，s。在这里，秒。3.1：

MDH1：对于第一个生成的密钥对，以下适用：

• 私钥c ₁是小于p-1的随机值。c ₁被存储以备后用。
• 公钥根据 m ₁ = g ^{c ₁} mod p 计算。
• 设备向 Alice 提供私钥 (c ₁ ) 和公钥 (m ₁ )。

MDH2：对于第二个生成的密钥对，以下适用：

• 选择随机 t（0 或 1）。
• z ₂根据z ₂ = g ^{(c ₁ - Wt)} * Y ^{(-ac ₁ - b)} mod p 计算。
• 根据H(z ₂ )计算私钥c ₂。这里 H 是一个密码哈希函数。c ₂被存储以备后用。
• 公钥根据m ₂ = g ^{c ₂} mod p 计算。
• 设备向 Alice 提供私钥 (c ₂ ) 和公钥 (m ₂ )。

MDHi：第三个和后续的密钥对会发生什么？使用与第二个生成的密钥对相同的算法，即例如对于第三个密钥交换，现在使用c ₂代替 c ₁并且现在使用m ₂代替 m ₁，或者通常如果第 i 个生成密钥对 c _i , m _i：

• 选择随机 t（0 或 1）。
• ž_我是按照z计算值_我=克^{（C _I-1 -重量）} * Y ^{（-ac _I-1 - B）}模p。
• 根据H(z _i )计算私钥c _i。这里 H 是（相同的）加密哈希函数。c _i被存储以备后用。
• 公钥根据 m _i = g ^{c _i} mod p 计算。
• 设备向 Alice 提供私钥 ( _ci ) 和公钥 (m _i )。

注意，有两类密钥交换过程，MDH1 和 MDHi，它们将在后面的时序行为讨论中发挥重要作用。

对已发布的恶意 DH 变体实现的评估：问题中发布的恶意 DH 变体的实现并未实现
SETUP（具有通用保护的秘密嵌入式陷阱门）。 SETUP 在两个连续生成的密钥对之间建立关系。这使得可以从两个这样的相关公钥导出最后一代密钥的私钥，例如可以在密钥交换过程中截取该公钥。 但是为此，必须在连续的密钥生成之间传递私钥，以便在最后生成的密钥中使用它来建立这种关系。这在实现中不会发生，从而无法实现所需的关系。


从更技术的角度来看，实现失败主要是因为案例MDH1和MDHi不是单独实现的，而是作为一个封闭的过程一起实现的。封闭的意思是私钥不存储在连续调用之间，因此无法传递。因此，实现的后续调用会生成彼此之间不具有所需关系的随机密钥对。 还要注意，从发布的实现和论文中使用的实现的相似时间行为（只是相似，因为例如缺少第二个峰值，这将在下面讨论），当然不能得出任何有效的实现。

SETUP 或恶意 Diffie-Hellman 变体的有效 Python 实现可能如下所示：

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
    

请注意以下事项：

• 这种情况privateKey == -1对应于第一个密钥对 (MDH1) 的生成，另一种情况对应于后续密钥对 (MDHi) 的生成。私钥存储在全局变量中privateKey。
• W, a,b是攻击者已知的常数。X,Y是攻击者的密钥对。只有作为私钥所有者的攻击者X才能进行攻击。W, a,b是可自由选择的常数，应该引入随机性。W根据定义是奇怪的。
• 加密函数用于生成随机数据（来自Crypto.Random，例如私钥）和散列（SHA256 摘要）。
• pyDH仅用于生成 p 和 g。

下面的函数现在为 Alice 生成 5 个连续的密钥对：

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)     

输出如下所示：

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
    

确认

为了验证实现，执行了两个测试：

测试 1：生成的密钥对是 Diffie-Hellman 对吗？这可以通过比较生成的秘密来验证，例如如下（对于 Alice，交换过程 4 中的密钥对被采用）：

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

计算出的秘密是相同的：

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)     

测试 2：攻击者能否确定 Alice 的私钥？

用于导出密钥的算法是 s。在这里，秒。3.1：

• 根据 r = m _i-1 ^a * g ^b mod p确定 r
• 根据 u = m _i-1 /r ^X mod p确定 u 。如果 m _i = g ^H(u) mod p，则私钥为 c _i = H(u) 并结束
• 根据 v = u/g ^W mod p确定 v 。如果 m _i = g ^H(v) mod p，则私钥为 c _i = H(v)

除了常数W，a，b和私钥X，该攻击者知道所有，只有公共密钥中号_我和m_的i-1是需要确定C中的私钥_我。

该算法的一种可能实现是：

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

为了验证，使用来自密钥交换过程 3 和 4 的公钥：

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

结果是

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

因此对应于来自密钥交换 4 的私钥。

时间行为分析

为了比较恶意和标准 DH 变体的计时行为，需要标准 DH 变体的实现：

SDHi：对于所有生成的密钥对，以下适用：

• 私钥 c _i是一个小于 p-1 的随机值。
• 公钥根据 m _i = g ^{c _i} mod p 计算。
• 设备向 Alice 提供私钥 ( _ci ) 和公钥 (m _i )。

使用例如以下实现：

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

恶意和标准 DH 变体之间的比较是通过以下实现进行的：

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

以下内容适用于此处：

• nTests = 进行了 1000 次测试。
• 对于每个测试nKeyExPerTest= 执行 10 个密钥交换过程。privateKey= -1 确保每次测试都以 MDH1 重新开始。
• 对于每个密钥交换过程，测量持续时间并创建持续时间的频率分布。
• 所有测量均使用 Intel Core i7-6700 处理器 (3.40 GHz)、Cores/Threads: 4/8、16 GB RAM、NVIDIA Geforce GTX 960/4GB 在 Win10/64 位和 Python 3.8 下进行。

下面两张图展示了这个密钥交换过程持续时间的频率分布：

左：x 轴：x 1000 ^-1秒，右：x 轴：x 10000 ^-1秒

这些数字与论文中发布的数字定性对应：

• 正如预期的那样，恶意 Diffie-Hellman 变体的主峰比标准 DH 变体的主峰处于更高的时间值。该比率相似，约为 3。
• 恶意Diffie-Hellman变种在标准DH变种的主峰处有一个次峰。
• 恶意DH变种的次峰明显小于恶意DH变种的主峰。
• 波形的偏差可能是由于不同的实现方式、不同的硬件等造成的。

恶意DH变种次峰说明：
在恶意DH变种的情况下，有两种不同的情况，MDH1和MDHi。MDH1 实际上对应于标准 DH 变体 SDHi 的情况。这就是为什么恶意的副峰和标准DH变体的主峰重合的原因。
然而，MDH1 和 MDHi 出现在不同的频率。例如，对于测试，每个测试定义了 10 个关键交换过程，即 MDH1 与 MDHi 交换的比率为 1:9，这解释了相对于主峰明显较小的次要峰。
可以很容易地更改代码以随机确定每次测试的密钥交换过程的数量，这将更加现实。但是通过固定数量的密钥交换过程，关系更容易说明。
为什么在问题中发布的恶意DH变种的实现中没有出现二次峰值？这是因为该实现将案例 MDH1 和 MDHi 结合起来并将它们作为一个案例实现，因此只测量单个值。

最后，这里是埃因霍温科技大学关于此主题的有用工作的链接。