How old are Crypto?

这周的PCTF撸了两道Crypto, 果然我只是民科….(ノಠ益ಠ)ノ彡┻━┻

tonnerre

Describe: We were pretty sure the service at tonnerre.pwning.xxx:8561 source was totally secure. But then we came across this website and now we’re having second thoughts… We think they store the service users in the same database?

给了一个服务，和代码，然后一个使用了相同数据库的网站.

网站有SQLi, 很简单，直接用sqlmap跑就行了得到:

salt,user,verifier
D14058efb3f49bd1f1c68de447393855e004103d432fa61849f0e5262d0d9e8663c0dfcb877d40ea6de6b78efd064bdd02f6555a90d92a8a5c76b28b9a785fd861348af8a7014f4497a5de5d0d703a24ff9ec9b5c1ff8051e3825a0fc8a433296d31cf0bd5d21b09c8cd7e658f2272744b4d2fb63d4bccff8f921932a2e81813,get_flag,ebedd14b5bf7d5fd88eebb057af43803b6f88e42f7ce2a4445fdbbe69a9ad7e7a76b7df4a4e79cefd61ea0c4f426c0261acf5becb5f79cdf916d684667b6b0940b4ac2f885590648fbf2d107707acb38382a95bea9a89fb943a5c1ef6e6d064084f8225eb323f668e2c3174ab7b1dbfce831507b33e413b56a41528b1c850e59
# salt 并没发现有啥用

然后这段代码拿去sage跑出x

N = 168875487862812718103814022843977235420637243601057780595044400667893046269140421123766817420546087076238158376401194506102667350322281734359552897112157094231977097740554793824701009850244904160300597684567190792283984299743604213533036681794114720417437224509607536413793425411636411563321303444740798477587
g = 9797766621314684873895700802803279209044463565243731922466831101232640732633100491228823617617764419367505179450247842283955649007454149170085442756585554871624752266571753841250508572690789992495054848
v = 165674960298677315369642561867883496091624769292792204074150337092614964752287803122621876963359715780971900093578962850132496591192295131510624917204670192364009271723089444839548606533268832368676268405764377988005323809734321470184299186127132537376393324213965008025487569799622831466701444653263068925529
A = g ** 2 % N
(aa, bb, cc) = xgcd(v/A, N)
x = (bb * A) mod N

python版:

from gmpy2 import invert
N = 168875487862812718103814022843977235420637243601057780595044400667893046269140421123766817420546087076238158376401194506102667350322281734359552897112157094231977097740554793824701009850244904160300597684567190792283984299743604213533036681794114720417437224509607536413793425411636411563321303444740798477587
g = 9797766621314684873895700802803279209044463565243731922466831101232640732633100491228823617617764419367505179450247842283955649007454149170085442756585554871624752266571753841250508572690789992495054848
v = 165674960298677315369642561867883496091624769292792204074150337092614964752287803122621876963359715780971900093578962850132496591192295131510624917204670192364009271723089444839548606533268832368676268405764377988005323809734321470184299186127132537376393324213965008025487569799622831466701444653263068925529
A = g ** 2 % N
k = invert(A, N)
x = invert(k*v, N)

payload:

#!/usr/bin/env python
# -*- coding:utf-8 -*-

from pwn import *
from Crypto.Hash import SHA256

x = "e2a218006a120b096d7836bf397e7dbb1a8f8f6cedb87c20fe3d4a2b99fc9f6661777bbe804b82e9c17a0ad2d508b97031d146934479076a4c11c199322e0dc9724d2cdac24480c6decae4e547f020273f3a2849f9d068cb8c774e029a747fc7c726a1bad2b9f9a7c091096002c364f018f2f1157ad492d42c00305d84f37db7"
v = 165674960298677315369642561867883496091624769292792204074150337092614964752287803122621876963359715780971900093578962850132496591192295131510624917204670192364009271723089444839548606533268832368676268405764377988005323809734321470184299186127132537376393324213965008025487569799622831466701444653263068925529
N = 168875487862812718103814022843977235420637243601057780595044400667893046269140421123766817420546087076238158376401194506102667350322281734359552897112157094231977097740554793824701009850244904160300597684567190792283984299743604213533036681794114720417437224509607536413793425411636411563321303444740798477587L

# context.log_level = "debug"
def H(P):
    h = SHA256.new()
    h.update(P)
    return h.hexdigest()

def tostr(A):
    return hex(A)[2:].strip('L')

s = remote("tonnerre.pwning.xxx", 8561)
print s.recv()
s.sendline("get_flag")
s.sendline(x)

salt = s.recv().strip()
residue = s.recv().strip()
re = int(residue, 16)

session_secret = (((re - v) % N) ** 2) % N
session_key = H(tostr(session_secret))

answer = residue + session_key
s.sendline(H(answer))
print s.recv()

这题很简单，我这菜鸡都能做出来，本来不准备写分析了，不过估计我过段时间又忘光了，还是写写分析吧.

从代码中已知N, g，我们可控的public_client设为x，从数据库得到verifier设为v，从代码中可得$c = (x * v)\ mod\ N$

每次随机一个random_server设为r, public_server设为p_s的值为$p_s = g^r\ mod\ N$

服务器每次会返回给我们一个residue设为re，值为$re = (p_s + v)\ mod\ N$

接着，$session\_secret = c^r\ mod\ N$

需要我们输入一个proof要满足下面的条件才能GetFlag.
$$SHA256(re+SHA256(session\_secret)) == proof$$

推论其实很简单, session_secret中只有r未知，但是我们知道
$$re = ((g^r\ mod\ N) + v)\ mod\ N$$
可以推出
$$(re - v)\ mod\ N = g^r\ mod\ N$$

如果我们能算出一个x => $(x * v)\ mod\ N = c = g$

这样就出来了，不过代码中却有限定条件，

if c in [N-g, N-1, 0, 1, g]:
    req.sendall('Sorry, not permitted.\n')
    req.close()
    return

不过并没啥影响，我们仍然能继续构造一个x使得
$$(x * v)\ mod\ N = c = g^2$$
接着就可以推出
$$session\_secret = g^{2*r}\ mod\ N = (g^r\ mod\ N)^2\ mod\ N$$

然后现在的问题是怎么算x，就用上面构造的等式
$$(x * v)\ mod\ N = g^2$$
可以得出
$$(x * v * g^{-2})\ mod\ N = 1$$

这个就用扩展欧几里德算呗，不过这里有一个知识点

假设$A = g^2$，那么$A^{-1}$值为啥？A明显是大整数，数论是研究整数性质的学科，所以不可能有分数参与计算，所以就有了这个推论
$$(x * v * A^{-1})\ mod\ N = ((x * v)\ mod\ N) * (A^{-1}\ mod\ N)\ mod\ N$$
假设$A^{-1}\ mod\ N \equiv k$
这不就模逆元么，可得$A * k \equiv 1\ (mod\ N)$
这不就可以用扩展欧几里德算出k么，所以最后是
$$x * (v * k) \equiv 1\ (mod\ N)$$
又是通过扩展欧几里德算出x

rabit

Describe: Just give me a bit, the least significant’s enough. Just a second we’re not broken, just very, very insecure. Running at rabit.pwning.xxx:7763

已知$N = p * q$, N的值可以得到，p和q却是未知

我们还知道c的值，$c = flag^2\ mod\ N$

我们可控设为x, 当
$$x^{\frac{\phi(q)}{2}}\ mod\ q = 1$$
$$x^{\frac{\phi(p)}{2}}\ mod\ p = 1$$
同时成立时，
$$x^{\frac{\phi(N)+4}{8}}\ mod\ N = m$$
我们可得知m的奇偶性

然后我数学还是太菜，没撸出来，等看了WP后再来更新

UPDATA: 4/19

这题用的是rabin算法，使用的是 rsa lsb oracle attack

首先要求N是一个Blum integer:

$N = p * q$ => p和q是两个不相等的随机素数，且$q \equiv 3\ (mod\ 4)$和$p \equiv 3\ (mod\ 4)$同时满足

当N为Blum Integer时，会有下面推论:
$$C = X^2\ mod\ N$$
$$X = C^{\frac{\phi(N)+4}{8}}\ mod\ N$$

就可以进行rabin加解密了

根据勒让德符号的公式，可控的x，要满足

存在一个 $a_1$ , 使得
$$a_{1}^{2} \equiv x\ (mod\ q)$$

存在一个 $a_2$ , 使得
$$a_{2}^{2} \equiv x\ (mod\ p)$$

写了个本地测试脚本:

#!/usr/bin/env python
# -*- coding:utf-8 -*-

from Crypto.Util.number import GCD, bytes_to_long, long_to_bytes
import math

FLAG = "testtesttesttesttesttest"
p = 9106955210961894382213398084695411548991508552135116475739483485343599066229167723931080143408618040894126850992819734177810259561241614741757319165906087L
q = 10285773789873373607105204107746706058912747747297377854417892145690734334799058020026041693440549801695363225930871791013981165203481480366182233263169487L
N = p * q

def legendreSymbol(a, p):
    return pow(a, (p-1)/2, p)

def decrypt(c, p, q):
    if GCD(c, p*q) != 1:
        print "bad1"
        return None
    if legendreSymbol(c, p) != 1:
        print "bad2"
        return None
    if legendreSymbol(c, q) != 1:
        print "bad3"
        return None
    return pow(c, ((p-1)*(q-1) + 4) / 8, p*q)

def encrypt(m, N):
    return pow(m, 2, N)

def pad(s):
    assert(len(s) < N.bit_length() / 8)
    padded = bytes_to_long(s.ljust(N.bit_length()/8, "0"))
    while decrypt(padded, p, q) == None:
        padded += 1
    return padded

msg = """Welcome to the LSB oracle! N = {}\n""".format(N)
print msg
padded = pad(FLAG)
print padded
enc_flag = encrypt(padded, N)
assert long_to_bytes(padded)[:len(FLAG)] == FLAG
assert decrypt(enc_flag, p, q) == padded
assert decrypt(2, p, q) != None

print "Encrypted Flag: {}\n".format(enc_flag)

m = decrypt(enc_flag, p, q)

# while True:
#   x = raw_input("Give a ciphertext: ")
#   x = long(x)
#   m = decrypt(x, p, q)
#   # print m
#   if m is None:
#       m = 0
#   print "lsb is {}\n".format(m % 2)

flag_lower_bound = 0
flag_upper_bound = N
mult = 0
c = enc_flag
iter_count = math.log(N, 2)
for i in xrange(0, long(math.ceil(long(iter_count)))):
    c = ((encrypt(2, N) * c) % N)
    mult += 1
    print("upper = %d" % flag_upper_bound)
    print("upper flag = %s" % long_to_bytes(flag_upper_bound))
    print("lower = %d" % flag_lower_bound)
    print("lower flag = %s" % long_to_bytes(flag_lower_bound))
    print("multiplier = %d" % mult)
    mm = decrypt(c, p, q)
    if mm is None:
        mm = 0
    if mm % 2 == 0:
        flag_upper_bound = (flag_upper_bound + flag_lower_bound) / 2
    else:
        flag_lower_bound = (flag_upper_bound + flag_lower_bound) / 2

LSB oracle attack

因为N是Blum Integer, 所以 $p\ mod\ 4 = 3\ \&\&\ q\ mod\ 4 = 3$

可以得出: $N\ mod\ 4 = 1$，或者$N\ mod\ 2 = 1$，所以N是odd
设ev为even, 我们可得出结论:
$$
\begin{cases}
if\ ev < N\ then\ ev\ mod\ N = \{even\}\\
if\ 2N > ev > N\ then\ ev\ mod\ N = \{odd\}\\
if\ 3N > ev > 2N\ then\ ev\ mod\ N = \{even\}\\
\ldots
\end{cases}
$$
简单的来说，对于一个RSA加密：
$m^e\ mod\ N = c$ 乘以 $2^e\ mod\ N = c_2$
得到
$$(2*m)^e\ mod\ N = c * c_2\ mod\ N = CC$$
然后把CC拿去解密
$$CC^d\ mod\ N = (2 * m)^{e*d}\ mod\ N = 2*m\ mod\ N = MM$$

从上面的结论我们可以得出:
$$
\begin{cases}
if\ MM\ is\ \{odd\}\ then\ 2*m > N\\
if\ MM\ is\ \{even\}\ then\ 2*m < N
\end{cases}
$$

本题就是利用这样的方法来确定出flag的范围，然后逐渐缩小范围，到最后确定值，我再多推一步，这一步理解了就可以全部理解了
下一步用$m^e\ mod\ N = c$ 乘以 $4^e\ mod\ N = c_2$
得到
$$(4*m)^e\ mod\ N = c * c_2\ mod\ N = CC_2$$

然后把$CC_2$拿去解密
$$CC_{2}^{d}\ mod\ N = (4 * m)^{e*d}\ mod\ N = 4*m\ mod\ N = MM_2$$

if MM is odd:
    if $MM_2$ is odd:
        3N < 4 * m < 4N
    else:
        2N < 4 * m < 3N
else:
    if $MM_2$ is odd:
        N < 4 * m < 2N
    else:
        0 < 4 * m < N

这题从头到尾我都想错了方法，而且我只是自己一个人蒙头苦算，注意收集和脚本中的信息，去google搜索，也许这题就能撸出来了.