@iPhan 2018-08-03T07:30:29.000000Z 字数 8625 阅读 916

LCTF2017 Crypto write up from 1phan

LCTF2017 xdsec writeup

LCTF2017 Crypto write up from 1phan

双线性对

两道题目中没有用到双线性对其他复杂的性质与困难问题，只用到了最基本的一条性质：

e(g^a, h^b) == e(g, h)^(a*b)

Charm

看到许多人卡在安装charm上，略有些惊讶……

pip install charm-crypto

如果没有安装依赖，是无法直接用pip安装charm的。 charm的文档中描述了charm的依赖包，以及如何手动编译安装。

官方文档

Crypto1

0X00. 题目原文

#!/usr/bin/env python3
from charm.toolbox.pairinggroup  import *
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from urllib import parse, request
logo = """
_|          _|_|_|  _|_|_|_|_|  _|_|_|_|  
_|        _|            _|      _|        
_|        _|            _|      _|_|_|    
_|        _|            _|      _|        
_|_|_|_|    _|_|_|      _|      _|        
  _|_|      _|      _|  _|_|_|_|_|  
_|    _|  _|  _|  _|_|          _|
    _|    _|  _|    _|        _|
  _|      _|  _|    _|      _|
_|_|_|_|    _|      _|    _|
"""
def sign(message, G, k, g, h, S):
    d = ***************************************
    message = bytes(message, 'UTF-8')
    message = bytes_to_long(message)
    if message == 0:
        message = G.random(ZR)
    mid = S**k
    mid = G.serialize(mid)
    mid = bytes_to_long(mid)
    P = G.pair_prod(g**mid, h**(message + d*k))
    return G.serialize(P)
def check_token(token, name):
    url = 'http://lctf.pwnhub.cn/api/ucenter/teams/'+token+'/verify/'
    req = request.Request(url=url)
    try:
        res = request.urlopen(req)
        if res.code == 200:
            return True
    except :
        pass
    return False    
def main():
    print(logo)
    S = ************************************************
    R0 = ***********************************************
    R1 = ************************************************
    R2 = ***********************************************
    S1 = S + R0
    S2 = S + R0*2
    G = PairingGroup('SS512')
    g = b'1:HniHI3b/eK111pzcIdKZKJCK9S7QiL5xItmJ9iTvEaGGEVuM4hGc2cMRqhNwsV29BN/QpqhopD+2XgUaTdQMqQA='
    h = b'2:OGpVSq03JR4dWKsDZ+6DBJ6Qwy2E4jaNA6HsWJZNP1vhHe2wYjLUvw990iouBG8XQVEbKr+uLNc3k9n4JDAJOgA='
    g = G.deserialize(g)
    h = G.deserialize(h)
    token_str = input("token:>>")
    name = input("team name:>>")
    if not check_token(token_str, name):
        return 0
    else:
        try:
            token = bytes(token_str,'UTF-8')
            token = bytes_to_long(token)
        except :
            return 0
    if token%2 ==1:
        point = G.pair_prod(g**token, h**R1) * G.pair_prod(g**S1, h)
    else:
        point = G.pair_prod(g**token, h**R2) * G.pair_prod(g**S2, h)
    print(G.serialize(point))
    S = G.pair_prod(g,h)**S
    k = G.serialize(S)
    k = bytes_to_long(k)
    message = input('message to sign:>>')
    if "show me flag" in message:
        return 0
    else:
        signed = sign(message, G, k, g, h, S)
        print(signed)
    signed_from_challenger = input('sign of "show me flag":>>')
    if str(sign('show me flag', G, k, g, h, S)) == signed_from_challenger:
        with open('./flag') as target:
            print(target.read())
if __name__ == '__main__':
    main()

0X01. 思路

从下往上找可以看到，想要获得flag就需要提供sign('show me flag', ...)。
再往上看，这个服务能提供所有不包含'show me flag'子串的字符串M对应的sign(M)。显然这里是一个选择明文攻击（CPA）。
检查函数sign，发现sign中未引入随机量，据此判断sign没有CPA安全性。
分析sign，在选择明文攻击中攻破sign。

0x02. 攻破sign

def sign(message, G, k, g, h, S):
    d = ************************************************
    message = bytes(message, 'UTF-8')
    message = bytes_to_long(message)
    if message == 0:
        message = G.random(ZR)
    mid = S**k
    mid = G.serialize(mid)
    mid = bytes_to_long(mid)
    P = G.pair_prod(g**mid, h**(message + d*k))
    return G.serialize(P)

读读sign，发现这是对ECDSA的拙劣模仿。

sign(M, ...)返回的结果是这样的：

e(g^(S^k), h^(M + d*k))

其中，S, k, d 三个值现在都不知道；g, h 已知；M可以自由控制但是不能为空，也不能包含子串'show me flag'。

化简一下sign(M, ...)返回的结果：

e(g, h) ^ (S^k * M + S^k * d * k)

一个直观的思路：

选择M1, M2，保证 bytes_to_long(M1) - bytes_to_long(M2) = t，t为任意常数
请求 s1 = sign(M1, ...) ; s2 = sign(M2, ...)
选择 M'，保证 bytes_to_long(M') + k = bytes_to_long('show me flag')
请求 s' = sign(M', ...)
计算:

s = s' * (s1 / s2) 
  = (e(g, h) ^ (S^k * M' + S^k * d * k)) * ((e(g, h) ^ (S^k * M1 + S^k * d * k)) / (e(g, h) ^ (S^k * M2 + S^k * d * k)))
  = e(g, h) ^ (S^k * (M' + M1 - M2) + S^k * d * k)
  = e(g, h) ^ (S^k * (M' + k) + S^k * d * k)
  = e(g, h) ^ (S^k * M + S^k * d * k)
   = sign('show me flag', ...)

至此crypto1的解计算完成。提交时看看题目给出代码中的判断部分注意提交格式。

Crypto2

0X00. 题目原文

#!/usr/bin/env python3
from charm.toolbox.pairinggroup  import *
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from urllib import parse, request
logo = """
_|          _|_|_|  _|_|_|_|_|  _|_|_|_|  
_|        _|            _|      _|        
_|        _|            _|      _|_|_|    
_|        _|            _|      _|        
_|_|_|_|    _|_|_|      _|      _|        
  _|_|      _|      _|  _|_|_|_|_|  
_|    _|  _|  _|  _|_|          _|
    _|    _|  _|    _|        _|
  _|      _|  _|    _|      _|
_|_|_|_|    _|      _|    _|
"""
def sign(message, G, k, g, h, S):
    d = ********************************************
    message = bytes(message, 'UTF-8')
    message = bytes_to_long(message)
    if message == 0:
        message = G.random(ZR)
    mid = S**k
    mid = G.serialize(mid)
    mid = bytes_to_long(mid)
    P = G.pair_prod(g**mid, h**(message + d*k))
    return G.serialize(P)
def check_token(token, name):
    url = 'http://lctf.pwnhub.cn/api/ucenter/teams/'+token+'/verify/'
    req = request.Request(url=url)
    try:
        res = request.urlopen(req)
        if res.code == 200:
            return True
    except :
        pass
    return False    
def main():
    print(logo)
    S = ***********************************************
    R0 = ************************************************
    R1 = ************************************************
    R2 = ************************************************
    S1 = S + R0
    S2 = S + R0*2
    G = PairingGroup('SS512')
    g = b'1:HniHI3b/eK111pzcIdKZKJCK9S7QiL5xItmJ9iTvEaGGEVuM4hGc2cMRqhNwsV29BN/QpqhopD+2XgUaTdQMqQA='
    h = b'2:OGpVSq03JR4dWKsDZ+6DBJ6Qwy2E4jaNA6HsWJZNP1vhHe2wYjLUvw990iouBG8XQVEbKr+uLNc3k9n4JDAJOgA='
    g = G.deserialize(g)
    h = G.deserialize(h)
    token_str = input("token:>>")
    name = input("team name:>>")
    if not check_token(token_str, name):
        return 0
    else:
        try:
            token = bytes(token_str,'UTF-8')
            token = bytes_to_long(token)
        except :
            return 0
    if token%2 ==1:
        point = G.pair_prod(g**token, h**R1) * G.pair_prod(g**S1, h)
    else:
        point = G.pair_prod(g**token, h**R2) * G.pair_prod(g**S2, h)
    print(G.serialize(point))
    S = G.pair_prod(g,h)**S
    k = G.serialize(S)
    k = bytes_to_long(k)
    message = 'abcd'
    signed = sign(message, G, k, g, h, S)
    print('signed of "abcd":>>', signed)
    signed_from_challenger = input('sign of "show me flag":>>')
    if str(sign('show me flag', G, k, g, h, S)) == signed_from_challenger:
        with open('./flag2') as target:
            print(target.read())
if __name__ == '__main__':
    main()

0X01. 思路

比赛结束前三小时crypto2放出了hint：“这不止是一道crypto题目，它还是一道……”

两道题目只有几行代码不同，crypto2中不允许用户提交自己的字符串。只会返回sign('abcd', ...)。无法选择明文了，允许输入的地方只有三个：token，队名，和最后的变量 signed_from_challenger。其中‘队名’这个变量是打酱油的，丝毫用处都没有。（此处偷偷谴责一下写token校验api的兄台 :-P）

读完代码后应该可以意识到crypto2里sign函数也几乎是打酱油的，全程只有可能执行sign('abcd')与sign('show me flag')。

那么问题肯定出在前面那一坨代码上了。

读一下前面的代码，意识到前面的代码其实是在双线性对映射出的那个群中一点e(g, h)的指数上实现了一个两层递归的 shamir门限方案。这个shamir树型结构也是CP-ABE（Cipher Policy - Attributes Based Encryption）的基础结构。

图示：

shamir递归树

题目中如下代码实现了这颗树。

if token%2 ==1:
    point = G.pair_prod(g**token, h**R1) * G.pair_prod(g**S1, h)
else:
    point = G.pair_prod(g**token, h**R2) * G.pair_prod(g**S2, h)
print(G.serialize(point))

在实际代码中，奇数选手将得到 e(g, h)^(token*R1 + S1)；偶数选手将得到 e(g, h)^(token*R2 + S2)。从更靠前的代码可以看到S1，S2的来源：已知S1，S2时，它们组成了一个简单的二元一次方程组。如果想要恢复出sign函数输入中的S和k，就需要先拿到S，或者拿到S的一些特征，比如说e(g, h)^S。

S1 = S + R0
S2 = S + R0*2

对于S，如果只知道S1，或者只知道S2，是无法解出S的。毕竟“K元一次方程需要至少K个一组才可能有解，否则一定有无穷多解”。

对于选手能直接得到的 e(g, h)^(token*R1 + S1) ，有两个未知量R1，S1，在只有一个token时也是有无穷多解的。因此需要两个奇数token，两个偶数token才有可能恢复出S（这里对应给出的hint：它不只是一道crypto题目，它还是一道社工题）。在实际操作中，我们只能恢复到e(g, h)^S，不过这已经足够我们求出'show me flag'的sign啦。

因为我们只能得到'abcd'的sign，即 e(g^(S^k), h^('abcd' + d*k))
（注：此处代码前，S被赋值成了e(g, h)^S，详情见题目原文）
在我们能得到S = e(g, h)^S，且可以根据S求得k时，我们就可以给任意消息做签名了。

0X02. writeUp.py

from charm.toolbox.pairinggroup import *
from Crypto.Util.number import bytes_to_long, inverse
def main():
    G = PairingGroup('SS512')
    g = b'1:HniHI3b/eK111pzcIdKZKJCK9S7QiL5xItmJ9iTvEaGGEVuM4hGc2cMRqhNwsV29BN/QpqhopD+2XgUaTdQMqQA='
    h = b'2:OGpVSq03JR4dWKsDZ+6DBJ6Qwy2E4jaNA6HsWJZNP1vhHe2wYjLUvw990iouBG8XQVEbKr+uLNc3k9n4JDAJOgA='
    # 4 different token. 2 even 2 odd
    t1 = bytes_to_long(b'4795968fe0bf73a1e39e6fec844dee01')
    S1 = b'3:cOlYveeItjU4ZHh8B58RjWUYJwdtFi/FXzqtd2GnnqEMJ9AFKzNjV90eUoPDLkinkWsdmbYTJxFTq5bvucwVHE98Uvw2laNvrsCFY9Mw766YdEPAtj7smBt/tIDl+u1mORufxZX8Q31F3dJjnzEoYhlxRZ9e9JFVtK7nW2Di6Iw='
    t2 = bytes_to_long(b'f11ca9db1f547b71a1b9592659553814')
    S2 = b'3:NjqqiCxaQtlFS1FEsSD+jmuO9Z0srysMi4K1nVCg2yAxJRjX62PPMSbY5JAa+Y4Ap25p9+u1EZ05f1RSwOXyZiIAZoDoS0crKDHRLJtE40aswcnPaf1JklMGBOGLdBUOZ3+nknLRDLACyBFnTW8y6FnHzLICGruBHisLhschvHM='
    t3 = bytes_to_long(b'97fddec1d9e630075803fc67d4220b05')
    S3 = b'3:GYcIbust8E1tcYZghIgC4x6YhrAyJUvy0lHHUxfvIOD7S/ann03RFrhO4qKb0jQ4vcU7pHJPv9Q+WDDPV/mAcH224dIfSyGcv91adl0tuhS6z0Fr4tBz03YUFUcGvAvi7bHvjnywwAjkTe1ZmMybyUnc9bMTPUxIZ3kli2b3PRs='
    t4 = bytes_to_long(b'adafcd958bbe176dd9cc96ef3aaa6438')
    S4 = b'3:R7Zhznj9aRtEv9ifZfLf9aqt4PSZzrMCSXuxkwZDdLEC2pqRPC1dWtP41BLR0UbbZVbTyOuojif9HYVuDu7oFSMTtj3zUxwXUW2x5sCYnkY3MOhSKM9JJxzAktSF0H2rIVvw4iBhQoh6Ecy3qRYfjZSha4Bc729DXHbYx0sMxd4='
    # SS512's order. get from G.order()
    order = 730750818665451621361119245571504901405976559617
    #init
    g = G.deserialize(g)
    h = G.deserialize(h)
    S1 = G.deserialize(S1)
    S2 = G.deserialize(S2)
    S3 = G.deserialize(S3)
    S4 = G.deserialize(S4)
    #compute x**S1
    t_S1 = ((S1**t3)/(S3**t1))**inverse((t3-t1), G.order())
    print(t_S1)
    #compute x**S2
    t_S2 = ((S2**t4)/(S4**t2))**inverse((t4-t2), G.order())
    print(t_S2)
    #compute x**S
    t = (t_S1*t_S1)/t_S2
    print(t)
    #compute k
    k = G.serialize(t)
    k = bytes_to_long(k)
    #compute mid
    mid = t**k
    mid = G.serialize(mid)
    mid = bytes_to_long(mid)
    #compute sign
    signed = b'3:loZKMHi9WWkS46zTQyidX5546U2Sg/JLnNi18X2KRklZdJSth4Kyj5FPg0J8sVpc9hyClgIo2P8xOGsRK6Zxc2AW6euFkyaOUWI9ZmYp2AhE0kcOypR4vASF9vWYtNqj0qlsExtMThSUtS53HYHCczbxcxA2Vcr/tkFagicyU30='
    signed = G.deserialize(signed)
    message = bytes_to_long(b'abcd')
    signed = signed/(G.pair_prod(g, h)**(mid*message))
    message = bytes_to_long(b'show me flag')
    signed = signed*(G.pair_prod(g, h)**(mid*message))
    print(str(G.serialize(signed)))
if __name__ == '__main__':
    main()

LCTF2017 Crypto write up from 1phan

双线性对

Charm

Crypto1

0X00. 题目原文

0X01. 思路

0x02. 攻破sign

Crypto2

0X00. 题目原文

0X01. 思路

0X02. writeUp.py

内容目录