+3

[Cryptopals] Set 8: Abstract Algebra (Challenge 57-62)

Đây là một bài trong series Cùng giải Cryptopals!.
Các bạn nên tự làm hoặc vừa đọc vừa làm thay vì đọc lời giải trực tiếp.


Set này hiện tại không được publish trên trang chủ,
và email thì cũng đến mùa quýt mới được trả lời,
nên mình đã Google đề để làm (。・ ω<)ゞ

Cẩn thận nhé, phần này rất rất dài, và khó hơn các phần trước rất nhiều.


Challenge 57: Diffie-Hellman Revisited: Small Subgroup Confinement

Tạo hàm sinh ra MAC đã.

enclen = (p.bit_length() + 7) // 8
msg = b"crazy flamboyant for the rap enjoyment"
def get_mac(key: int, msg: bytes) -> bytes:
    return digest(key.to_bytes(enclen, 'big'), msg, 'md5')

Sử dụng factordb, chúng ta có các ước của jj (có multiplicity 1) bé hơn 2162^{16}:

factors = [2, 5, 109, 7963, 8539, 20641, 38833, 39341, 46337, 51977, 54319, 57529]

Do chỉ cần các ước số có tích vừa đủ lớn hơn qq để sử dụng định lý thặng dư Trung Hoa, chúng ta lọc bớt mấy số to to đi và tính luôn tích đó:

# keep only factors that sum up to be greater than q
prod = 1
for i, v in enumerate(factors):
    prod *= v
    if prod > q: break
assert prod > q
del factors[i + 1:]

Tạo secret key của Bob mà Eve (chúng ta) cần phải lấy được:

# bob's secret key
secret = randrange(1, q)

Với mỗi một ước số trong factors, chúng ta lấy MAC (bất hợp lệ) của Bob, rồi bruteforce ra số dư khi chia private exponent của Bob với ước số đó:

# remainder modulus `factors`
remainders = []
for factor in factors:
    # get element of order `factor`
    exponent = (p - 1) // factor
    while True:
        h = randrange(1, p)
        h = pow(h, exponent, p)
        if h != 1: break
    # get message encrypted with invalid public key
    mac = get_mac(pow(h, secret, p), msg)
    # bruteforce remainders
    for i in range(factor):
        if mac == get_mac(pow(h, i, p), msg):
            remainders.append(i)
            break
assert len(factors) == len(remainders)

Và sử dụng định lý thặng dư Trung Hoa để lấy được secret key của Bob:

# do chinese remainder theorem
recovered = 0
for factor, remainder in zip(factors, remainders):
    factor_ = prod // factor
    inverse = invmod(factor_, factor)
    recovered = (recovered + remainder * inverse * factor_) % prod

assert recovered == secret

Easter egg: Tin nhắn được MAC

crazy flamboyant for the rap enjoyment

là lyrics từ bài Protect Ya Neck của Wu-Tang Clan. Đây cũng là title của email cần gửi đến Cryptopals để lấy đề set 8 này.

Challenge 58: Pollard's Method for Catching Kangaroos

Chúng ta implement đúng như hướng dẫn đề bài:

def pollard(y, min_exp, max_exp, k=16, p=p, q=q, g=g):
    # generate params from k
    f = lambda y: 2 ** (y % k)
    '''
    avg of f is (2 ^ k - 1) / k
    multiplied by 4 -> (2 ^ (k+2) - 4) / k
    '''
    N = (2 ** (k + 2)) // k

    # get the endpoint
    xT = 0
    yT = pow(g, max_exp, p)
    for _ in range(N):
        fT = f(yT)
        xT += fT
        yT = (yT * pow(g, fT, p)) % p

    # then search if we met
    xW = 0
    yW = y
    while xW < max_exp - min_exp + xT:
        fW = f(yW)
        xW += fW
        yW = (yW * pow(g, fW, p)) % p

        if yW == yT:
            return max_exp + xT - xW

Và chạy 2 tests:

y = 7760073848032689...
res = pollard(y, 0, 2 ** 20)
assert pow(g, res, p) == y
print(res) # 705485

y = 9388897478013399...
res = pollard(y, 0, 2 ** 40, k=20)
assert pow(g, res, p) == y
print(res) # 359579674340

Chú ý để kk cao lên để kangaroo nhảy được xa hơn. Với k=16k=16, ước tính loop sau mất tầm 30' trường hợp xấu nhất; với k=20k=20, 3 phút (thực tế mất 2'), và với k=25k=25, 1' (nhưng loop đầu đã mất 2 phút). Cụ thể, do với kk lớn, bước nhảy xa hơn, và do số bước trước đặt trap NN là trung bình của độ dài các bước nhảy, loop đầu sẽ lâu hơn với kk lớn hơn. Tuy nhiên, vì bước nhảy dài hơn, nên thỏ con sẽ nhảy qua từ lower bound đến upper bound rất nhanh để mau chóng rơi vào trap chúng ta đã đặt. Vì vậy, nếu bound cho exponent lớn, hãy đặt kk cao lên, vì độ dài loop 2 sẽ bé đi rất rất rất nhiều so với lượng thời gian tăng lên để chạy loop 1; và giảm kk trong trường hợp ngược lại.

Ở phần 2, chúng ta copy i xì code của bài trước. Trong đó, các ước bé hơn 2162^{16} của jj là:

factors = [2, 12457, 14741, 18061, 31193, 33941, 63803]
prod = 2 * 12457 * 14741 * 18061 * 31193 * 33941 * 63803

Lần này chúng ta sẽ cần dùng đến public key của Bob:

# bob's key
secret = randrange(1, q)
public = pow(g, secret, p)

Dùng code của bài trước chúng ta sẽ có được số dư residue khi chia secret cho prod. Sử dụng Pollard's Method như bài trước và thế là hết:

# y = g^x = g^(n + mr) = g^n + (g^r)^m
for k in range(25, 0, -1):
    m = pollard(
        (public * pow(g, q - residue, p)) % p,
        0,
        q // prod + 1,
        k = k,
        g = pow(g, prod, p)
    )
    if m is not None: break
recovered = prod * m + residue
assert recovered == secret

Nên nhớ rằng, Pollard's Method là probabilistic, nó không chắc chắn sẽ đưa ra đáp án. Trong trường hợp đó, hãy đổi kk xem có giải ra được không nhé.

Challenge 59: Elliptic Curve Diffie-Hellman and Invalid-Curve Attacks

Việc đầu tiên cần làm là implement thuật toán Elliptic Curve, bắt đầu từ WeierstrassCurve:

class WeierstrassCurve:
    def __init__(self, a, b, p, g, q, order):
        '''
        @a, b   params of the curve equation
                    y^2 = x^3 + ax + b
        @p      the GF(p) to work on
        @g      the coordinates of the generator
        @q      the order of the generator
        @order  the number of elements in the finite field
                    generated by the curve on GF(p)
        '''
        self.a = a
        self.b = b
        self.p = p
        self.q = q
        self.order = order
        self.g = self.point(*g)
        self.id = self.point(0, 1)

        assert self.g * q == self.id
    
    def point(self, x, y):
        return WeierstrassPoint(self, x, y)

    def __eq__(self, obj):
        # same config different object is different field
        # this is to prevent recursive comparison
        return id(self) == id(obj)

    def get_eqn(self):
        ret = 'x^3'
        if self.a > 0:
            ret += f' + {self.a}x'
        elif self.a < 0:
            ret += f' - {-self.a}x'
        if self.b > 0:
            ret += f' + {self.b}'
        elif self.b < 0:
            ret += f' - {-self.b}'
        return ret

    def generate_keypair(self):
        private = randrange(0, self.q)
        public = self.g * private
        return private, public

Và class cho một điểm bất kỳ trên curve đó. Chú ý, disable cái assertion về điểm nằm trong curve, và dòng tối ưu nhân điểm, để attack này hoạt động.

class WeierstrassPoint:
    def __init__(self, field, x, y):
        self.field = field
        self.x = x
        self.y = y

        # make sure the point is valid -- disable this for the attack
        # if x != 0 or y != 1:
        #     assert (pow(x, 3, curve.p) + curve.a * x + curve.b) % curve.p == pow(y, 2, curve.p), "Point not on the curve!"


    def __str__(self):
        return f'{(self.x, self.y) if self != self.field.id else "Identity"}' + \
               f' of {self.field.get_eqn()}'
    
    __repr__ = __str__

    def copy(self):
        # shallow copy
        return WeierstrassPoint(self.field, self.x, self.y)

    def __neg__(self):
        return WeierstrassPoint(self.field, self.x, self.field.p - self.y)

    def __eq__(self, obj):
        return self.field == obj.field and self.x == obj.x and self.y == obj.y

    def __add__(self, obj):
        assert isinstance(self, WeierstrassPoint) and isinstance(obj, WeierstrassPoint), \
                'Can only add Point with another Point.'
        assert self.field == obj.field, 'Points must be of the same field.'
        
        field = self.field
        if self == field.id:
            return obj
        if obj == field.id:
            return self
        if self == -obj:
            return field.id

        if self == obj:
            m = ((3 * self.x * self.x + field.a) * invmod(2 * self.y, field.p)) % field.p
        else:
            m = ((obj.y - self.y) * invmod(obj.x - self.x, field.p)) % field.p
        
        new_x = (m * m - self.x - obj.x) % field.p
        new_y = (m * (self.x - new_x) - self.y) % field.p
        
        return WeierstrassPoint(field, new_x, new_y)

    def __mul__(self, scalar):
        assert isinstance(self, WeierstrassPoint) and isinstance(scalar, int), \
                'Can only multiply Point with a scalar.'
        # disable this for the attack
        # scalar %= self.field.q
        pow2 = self
        acc = self.field.id
        while True:
            if scalar & 1:
                acc += pow2
            scalar >>= 1
            if scalar == 0: return acc
            pow2 += pow2
    
    def __rmul__(self, scalar):
       return self * scalar

Implement hàm lấy Jacobi symbol vì sau này sẽ cần dùng:

def jacobi_symbol(n: int, p: int):
    assert n > 0 and p > 0, 'Parameters to Jacobi symbol must be positive!'
    assert p % 2, 'p must be odd.'
    sign = 1
    while True:
        if p == 1: return sign
        n %= p
        if n == 0: return 0
        even_invert = (p % 8) in (3, 5)
        while n & 1 == 0:
            if even_invert:
                sign = -sign
            n >>= 1
        if n == 1: return sign
        if n % 4 == 3 and p % 4 == 3:
            sign = -sign
        n, p = p, n

Implement luôn hàm căn bậc 2 theo modulo (thuật toán Tonelli-Shanks):

def sqrtmod(n: int, p: int) -> int:
    ''' Tonelli-Shanks algorithm '''
    # find q, s such that q2^s = p-1
    q = p-1
    s = 0
    while q & 1 == 0:
        s += 1
        q >>= 1
    # get a quadratic non-residue
    for z in range(1, p):
        if jacobi_symbol(z, p) == -1:
            break
    # let
    m = s
    c = pow(z, q, p)
    t = pow(n, q, p)
    r = pow(n, (q + 1) >> 1, p)
    # loop
    while True:
        if t == 0: return 0
        if t == 1: return r
        t2i = t
        for i in range(1, m):
            t2i = pow(t2i, 2, p)
            if t2i == 1: break
        else:
            return None
        b = pow(c, 1 << (m - i - 1), p)
        m = i
        c = pow(b, 2, p)
        t = (t * c) % p
        r = (r * b) % p

Test handshake giữa Alice và Bob:

curve = WeierstrassCurve(
    a = -95051,
    b = 11279326,
    p = 233970423115425145524320034830162017933,
    g = (182, 85518893674295321206118380980485522083),
    q = 29246302889428143187362802287225875743,
    order = (29246302889428143187362802287225875743 << 3)
)
# test handshake
priv_a, pub_a = field.generate_keypair()
priv_b, pub_b = field.generate_keypair()
assert pub_a * priv_b == pub_b * priv_a

Tạo hàm ký với key chung lấy được từ Diffie-Hellman:

# according to ECIES, x coord is enough (uh, no?)
# since y can be computed from x *without* the sign, we add that too
msg = b"crazy flamboyant for the rap enjoyment"
def get_mac(pubkey: Point) -> bytes:
    return digest(int_to_bytes(pubkey.x, curve.p.bit_length()) + \
        (b'+' if pubkey.y * 2 < curve.p else b'-'), msg, 'md5')

Trong tiêu chuẩn ECIES, họ chỉ dùng toạ độ xx trong public key để ký. Tuy nhiên, với mỗi một giá trị xx tồn tại 2 giá trị yy, nên trong KDF của chúng ta dùng cả 2: xx và dấu của yy.

Tạo hàm generate một điểm có order rr trên curve tương tự với RSA:

def generate_point(curve, a, b, q, r):
    # generate new point of order r without randomness
    point = curve.id.copy()
    for x in range(curve.p):
        y = sqrtmod((pow(x, 3, curve.p) + a * x + b) % curve.p, curve.p)
        if y is None: continue
        # craft the point to override the error check
        point.x, point.y = x, y
        point *= (q // r)
        assert point * r == curve.id
        if point != curve.id: return point

Lần lượt tạo các điểm trên 3 curve fake kia để lấy các số dư như challenge 57. Trong đó, các ước nguyên tố đã được lọc sao cho chỉ giữ các số nguyên tố khác nhau và nhỏ nhất sao cho tích của chúng vẫn lớn hơn order của generator.

# y^2 = x^3 - 95051*x + 210     233970423115425145550826547352470124412
a, b1, q1 = -95051, 210, 233970423115425145550826547352470124412
factors1 = [3, 11, 23, 31, 89, 4999, 28411]
remainders1 = []
for factor in factors1:
    point = generate_point(curve, a, b1, q1, factor)
    mac = get_mac(point * priv_a)
    for r in range(factor):
        if mac == get_mac(point * r):
            remainders1.append(r)
            break

# y^2 = x^3 - 95051*x + 504     233970423115425145544350131142039591210
b2, q2 = 504, 233970423115425145544350131142039591210
factors2 = [5, 7, 61, 12157]
remainders2 = []
for factor in factors2:
    point = generate_point(curve, a, b2, q2, factor)
    mac = get_mac(point * priv_a)
    for r in range(factor):
        if mac == get_mac(point * r):
            remainders2.append(r)
            break

# y^2 = x^3 - 95051*x + 727     233970423115425145545378039958152057148
b3, q3 = 727, 233970423115425145545378039958152057148
factors3 = [37, 67, 607, 1979, 13327, 13799]
remainders3 = []
for factor in factors3:
    point = generate_point(curve, a, b3, q3, factor)
    mac = get_mac(point * priv_a)
    for r in range(factor):
        if mac == get_mac(point * r):
            remainders3.append(r)
            break

Và lấy lại private key thôi:

recovered, modulus = chinese_remainder(
    factors1 + factors2 + factors3,
    remainders1 + remainders2 + remainders3
)

assert modulus >= curve.q
assert recovered == priv_a

Challenge 60: Single-Coordinate Ladders and Insecure Twists

Viết code (hay chính xác là sửa pseudocode trong đề) tính scale theo ladder:

def ladder(u: int, k: int, a: int, p: int) -> int:
    # calculate u * k, with u being the first coordinate and k a scalar
    u2, w2 = 1, 0
    u3, w3 = u, 1
    for i in reversed(range(p.bit_length())):
        b = 1 & (k >> i)
        if b: u2, u3, w2, w3 = u3, u2, w3, w2

        # don't compute this twice in the second line below
        u2u2, u2w2, w2w2 = u2 * u2, u2 * w2, w2 * w2
        u3, w3 = pow(u2 * u3 - w2 * w3, 2, p), (u * (u2 * w3 - w2 * u3) ** 2) % p
        u2, w2 = pow(u2u2 - w2w2, 2, p), (4 * u2w2 * (u2u2 + a * u2w2 + w2w2)) % p

        if b: u2, u3, w2, w3 = u3, u2, w3, w2
        
    return (u2 * invmod_prime(w2, p)) % p

Có lẽ việc sử dụng single-coordinate ladder chính là lý do tại sao trong ECIES chỉ sử dụng toạ độ xx thay vì cả 2.

Công thức của ladder thực ra nhìn thế thôi nhưng đa phần là hù doạ: trong 2 phép tính lại toạ độ thì phép tính đầu tiên là cộng 2 điểm (u2,w2)+(u3,w3)(u_2, w_2) + (u_3, w_3), và phép thứ 2 là nhân đôi một điểm (u2,w2)+(u2,w2)=(u2,w2)2(u_2, w_2) + (u_2, w_2) = (u_2, w_2) * 2. Hai công thức của 2 phép tính trên thì lằng nhằng thật và bạn không cần hiểu mà chỉ cần lấy từ EFD, còn phần lõi của Montgomery ladder thì đơn giản hơn rất nhiều: ở iteration thứ ii, bạn sẽ có (u2,w2)(u_2, w_2) là giá trị sau khi đã nhân đến kk % (2^i), và (u3,w3)(u_3, w_3) là giá trị đó nhân với kk % (2^i) + 1. Chứng minh bằng quy nạp sẽ cho ta thấy sau khi qua đủ số-bit-của-k iteration thì chúng ta sẽ có được kết quả đúng.

Đề bài muốn chúng ta map u2=u3+534u2+uu^2 = u^3 + 534u^2 + u với u=x178u = x-178. Thay thế vào công thức chính, ta có:

y2=(x178)3+534(x178)2+(x178)=x3534x2+95052x5639752+534x2190104x+16919256+x178=x395051x+11279326\begin{aligned} y^2 &= (x-178)^3 + 534(x-178)^2 + (x-178) \\ &= x^3 - 534x^2 + 95052x - 5639752 + 534x^2 - 190104x + 16919256 + x - 178 \\ &= x^3 - 95051x + 11279326 \end{aligned}

Đây chính là Weierstrass Curve từ challenge trước.

Check kèo implementation của ladder:

p = 233970423115425145524320034830162017933
q = 29246302889428143187362802287225875743
a = 534 # b = 1
assert ladder(4, q, a, p) == 0

Và thử như đề bài sẽ có:

u = 76600469441198017145391791613091732004
v = (u * u * u + a * u * u + u) % p
print(ladder(u, 11, a, p)) # 0
print(jacobi_symbol(v, p)) # -1

Giá trị Jacobi symbol 1-1 có nghĩa là không tồn tại căn bậc 2 modulo pp của vv.

Tương tự như challenge trước, chúng ta viết hàm tạo điểm trên curve:

def generate_point(a, p, q, r):
    # generate new point of order r
    for u in range(1, p):
        v2 = (u * u * u + a * u * u + u) % p
        # make sure it's on the twist
        y = jacobi_symbol(v2, p)
        assert y != 0
        if y == 1:
            continue
        # craft the point to override the error check
        point = ladder(u, q // r, a, p)
        if point == 0: continue
        assert ladder(point, r, a, p) == 0
        return point

Và lần này thì hàm ký không cần giá trị toạ độ kia nữa:

def get_mac(pubkey: int) -> bytes:
    return digest(
        int_to_bytes(pubkey),
        b"crazy flamboyant for the rap enjoyment",
        'md5'
    )

Tạo ECC keys cho Bob:

secret = randrange(1, curve.q)
public = _ladder(4, secret, curve.a, curve.p)

Tương tự như challenge trên, chúng ta viết code sinh ra một điểm sao cho có một order qq cụ thể: nhớ rằng, nếu Jacobi symbol là 1-1, điều đó nghĩa là giá trị đó không phải là một số chính phương, và điểm đó không tồn tại trên curve mà nằm trên twist.

def generate_point(a, p, q, r):
    # generate new point of order r with custom group order q
    for u in range(1, p):
        v2 = (u * u * u + a * u * u + u) % p
        # make sure it's on the twist
        y = jacobi_symbol(v2, p)
        assert y != 0
        if y == 1:
            continue
        # craft the point to override the error check
        point = _ladder(u, q // r, a, p)
        if point == 0: continue
        assert _ladder(point, r, a, p) == 0
        return point

Tìm ra order của twist và tìm các ước của chúng:

q_ = 2 * curve.p + 2 - curve.order
factors = [11, 107, 197, 1621, 105143, 405373, 2323367]#, 1571528514013]

Chúng ta bỏ nghiệm cuối do nó quá lớn và sẽ mất 110 ngày (!) chỉ để tìm số dư khi chia cho nó. Giờ là code để tìm các số dư đó, có hỗ trợ thanh progress bar và xử lý đa luồng (vì code này mà để đơn luồng lâu kinh khủng):

retval = Value('i', -1)
def find_remainders(u, ranger, mac):
    global retval
    for remainder in ranger:
        with retval.get_lock():
            if retval.value != -1:
                break
        mac_ = get_mac(_ladder(u, remainder, curve.a, curve.p))
        if mac == mac_:
            with retval.get_lock():
                retval.value = remainder
            break

def load_divider(u, f, mac):
    count = cpu_count()
    pool = Pool(count)
    retval.value = -1
    params = []
    step = f // count + int((f % count) > 0)
    bottom = 0
    for _ in range(count):
        params.append(range(bottom, min(bottom + step, f)))
        bottom += step

    pool.starmap(find_remainders, zip(repeat(u), params, repeat(mac)))
    return sorted([retval.value, f - retval.value])

Và tìm lấy số dư cuối cùng:

print('Getting individual factors...')
for f in tqdm(factors):
    u = generate_point(curve.a, curve.p, q_, f)
    mac = get_mac(_ladder(u, secret, curve.a, curve.p))
    remainders.append(load_divider(u, f, mac))
    
print('Getting union factors...')
while len(factors) > 1:
    new_factors = []
    new_remainders = []
    len_factors = len(factors)
    midpoint = len_factors // 2 + len_factors % 2
    for idx1 in range(midpoint):
        idx2 = len_factors - idx1 - 1
        if idx1 == idx2:
            new_factors.append(factors[idx1])
            new_remainders.append(remainders[idx2])
            continue
        f1 = factors[idx1]
        f2 = factors[idx2]
        f3 = f1 * f2
        u3 = generate_point(curve.a, curve.p, q_, f3)
        mac = get_mac(_ladder(u3, secret, curve.a, curve.p))
        r3s = []
        for r1 in remainders[idx1]:
            for r2 in remainders[idx2]:
                r3, _ = chinese_remainder([f1, f2], [r1, r2])
                mac_ = get_mac(_ladder(u3, r3, curve.a, curve.p))
                if mac == mac_:
                    r3s.append(r3)
        new_factors.append(f3)
        new_remainders.append(r3s)
    
    factors = []
    remainders = []
    for f, r in sorted(zip(new_factors, new_remainders)):
        factors.append(f)
        remainders.append(r)

factor = factors[0]
remainders = remainders[0]

Trong đề bài có nhắc tới việc sẽ có 2 giá trị dư có thể xảy ra cho mỗi modulus, và lượng số dư có thể cho factor cuối sẽ là 27=1282^7=128. Con số này rất lớn, vì (spoiler alert) code chạy phần đằng sau mất tầm 6 tiếng cho mỗi khả năng trên. Vì vậy, chúng ta có thể sinh ra tất cả các khả năng trước, rồi sinh ra MAC như với mỗi ước riêng kia, để check xem số dư đó có thoả mãn không. Kết quả cuối cùng là bạn sẽ rút ra chỉ có 2 số dư tiềm năng thôi.

Do Pollard's Kangaroo yêu cầu phải có cả phép cộng và nhân, sử dụng mỗi Montgomery ladder không thôi sẽ không thành. Vì thế, có 2 việc chúng ta phải làm: 1 là tạo ra các candidate cho public key để xử lý:

y = sqrtmod((public ** 3 + curve.a * public ** 2 + public) % curve.p, curve.p)
public = curve.point(public, y)

Khả năng thứ 2 của public key chính là -public, với giá trị toạ độ yy bị đổi dấu. Việc thứ 2 phải làm là implement thêm hàm cộng/nhân bình thường:

def _add(self, obj):
    curve, x1, y1, x2, y2 = self.curve, self.x, self.y, obj.x, obj.y
    a, b, p = curve.a, curve.b, curve.p
    x3 = b * pow(y2 - y1, 2, p) * pow(x2 - x1, p - 1 - 2, p) - a - x1 - x2
    y3 = (2 * x1 + x2 + a) * (y2 - y1) * invmod_prime(x2 - x1, p) - b * pow(y2 - y1, 3, p) * pow(x2 - x1, p - 1 - 3, p) - y1
    return MontgomeryPoint(curve, x3 % p, y3 % p)

def _double(self):
    curve, x, y = self.curve, self.x, self.y
    a, b, p = curve.a, curve.b, curve.p
    x3 = b * pow(3 * x * x + 2 * a * x + 1, 2, p) * pow(2 * b * y, p - 1 - 2, p) - a - x - x
    y3 = (2 * x + x + a) * (3 * x * x + 2 * a * x + 1) * invmod_prime(2 * b * y, p) - b * pow(3 * x * x + 2 * a * x + 1, 3, p) * pow(2 * b * y, p - 1 - 3, p) - y
    return MontgomeryPoint(curve, x3 % p, y3 % p)

Cấu trúc của class MontgomeryPoint tương tự với lớp WeierstrassPoint ở bài trước; nếu có thắc mắc gì bạn có thể đọc code cụ thể tại repo mình.

Sửa hàm Pollard's Kangaroo cho Elliptic Curve:

def pollard(y, min_exp, max_exp, g, k=24, progress=True):
    # generate params from k
    f = lambda y: 2 ** (y.x % k)
    '''
    avg of f is (2 ^ k - 1) / k
    multiplied by 4 -> (2 ^ (k+2) - 4) / k
    '''
    N = (2 ** (k + 2)) // k

    assert y.curve == g.curve

    # get the endpoint
    xT = 0
    yT = g * max_exp
    if progress:
        ranger = trange(N)
    else:
        ranger = range(N)
    for _ in ranger:
        fT = f(yT)
        xT += fT
        yT += g * fT

    # then search if we met
    xW = 0
    yW = y
    if progress:
        pbar = tqdm(total=max_exp - min_exp + xT)
    while xW < max_exp - min_exp + xT:
        fW = f(yW)
        xW += fW
        yW += g * fW

        if progress:
            pbar.update(fW)

        if yW == yT:
            return max_exp + xT - xW

Và vì code này chạy rõ lâu, mà có nhiều khả năng phải thử (4=24 = 2 số dư ×2\times 2 public keys), nên chúng ta lại chạy song song:

# y = g^x = g^(r + qf) = g^r + (g^f)^q
def pollard_helper(public, r, progress=True):
    y = public - curve.g * r
    max_ = curve.q // factor
    q = pollard(y, 0, max_, y.curve.g * factor, 23, progress)
    if q is None: return
    ret = (q * factor + r) % curve.q
    return ret

# parallel compute all 4 instances
pool = Pool(cpu_count())
results = pool.starmap(pollard_helper,
    ((public, remainders[0], True),
    (-public, remainders[0], False),
    (public, remainders[1], False),
    (-public, remainders[1], False))

Và sau 6 tiếng chạy code chúng ta sẽ có kết quả:

assert secret in results
for result in results:
    assert result is None or result == secret

Ngoài lề: Có một điều khá thú vị mà mình phát hiện ra: sau khi scale quá order của group thì các lý thuyết bay qua cửa sổ: khi scale với bội số của origin sẽ không về được origin nữa. Chắc là tại khi gặp origin 1 lần thì nó toang, vì origin là một điểm nằm ở vô cực, và x/wx/w chỉ là một ước lượng. Ngoài ra cũng tại điểm 0 và điểm origin đều cùng giá trị 0. Vấn đề này là một phần nhỏ của việc chỉ sử dụng toạ độ xx, là mỗi giá trị của xx tương ứng với 2 điểm trên curve. Điều này cũng làm cho việc hàm fast multiplication (nhân đôi rồi cộng gộp) sẽ bị toang, do không biết được chính xác hiệu của 2 điểm đó; và chúng ta cần hiệu vì curve này không có công thức closed form cho cộng điểm, mà phải sử dụng differential addition.

Challenge 61: Duplicate-Signature Key Selection in ECDSA (and RSA)

Phần 1: ECDSA

Đầu tiên chúng ta implement lại hàm ký và verify cho ECDSA:

def sign(message, private_key, curve, hash_fn=sha256):
    q = curve.q

    # get the leftmost bits equal to the group order
    hashed = int.from_bytes(hash_fn(message).digest(), 'big')
    hashed >>= max(hashed.bit_length() - q.bit_length(), 0)

    # generate nonce key
    while True:
        private, public = curve.generate_keypair()
        k, r = private, public.x
        if r % q == 0: continue
        s = ((hashed + private_key * r) * invmod_prime(k, q)) % q
        if s != 0: break
        
    return r, s

def verify(message, signature, public_key, hash_fn=sha256):
    r, s = signature
    q = public_key.curve.q

    # get the leftmost bits equal to the group order
    hashed = int.from_bytes(hash_fn(message).digest(), 'big')
    hashed >>= max(hashed.bit_length() - q.bit_length(), 0)
    
    s_inv = invmod_prime(s, q)
    u1 = (hashed * s_inv) % q
    u2 = (r * s_inv) % q
    R = u1 * public_key.curve.g + u2 * public_key
    return r == R.x

Tạo chữ ký cho một random key:

curve = WeierstrassCurve(
    a = -95051,
    b = 11279326,
    p = 233970423115425145524320034830162017933,
    g = (182, 85518893674295321206118380980485522083),
    q = 29246302889428143187362802287225875743,
    order = (29246302889428143187362802287225875743 << 3)
)
private, public = curve.generate_keypair()

message = b"leavin' is the hardest thing to do"
signature = sign(message, private, curve)
assert verify(message, signature, public)

Và tạo ra một đôi key mới có thể mạo danh chữ ký trên:

# from the verify code
r, s = signature
q = curve.q
hashed = int.from_bytes(sha256(message).digest(), 'big')
hashed >>= max(hashed.bit_length() - q.bit_length(), 0)
s_inv = invmod_prime(s, q)
u1 = (hashed * s_inv) % q
u2 = (r * s_inv) % q
# craft public key
d_ = randrange(1, q)
t = (u1 + u2 * d_) % q
R = u1 * curve.g + u2 * public
g_ = invmod(t, q) * R
Q_ = d_ * g_
Q_.curve = WeierstrassCurve(
    a = -95051,
    b = 11279326,
    p = 233970423115425145524320034830162017933,
    g = (g_.x, g_.y),
    q = 29246302889428143187362802287225875743,
    order = (29246302889428143187362802287225875743 << 3)
)
assert verify(message, signature, Q_)

Thực ra tán công này khá đơn giản nếu bạn để ý một chút: chúng ta chọn generator và public key mới sao cho RR cũ và mới giống nhau:

R=(u1+u2d)G=(u1+u2d)(u1+u2d)1R=R.R' = (u_1 + u_2d') * G' = (u_1 + u_2d') * (u_1 + u_2d')^{-1} * R = R.

Điều quan trọng cần nhớ ở đây là với các thông tin có được từ chủ nhân chính thống, chúng ta có được key trộn cần mạo danh, và tìm một đôi (d,G)(d',G') để cho giá trị đó không đổi không quá khó. Đặc biệt là với order của generator là nguyên tố, tất cả các giá trị mà generator đó sinh ra đều sẽ có cùng order (trừ identity).

Phần 2: RSA (DSA + forged plaintext)

Việc đầu tiên cần làm là tạo ra các smooth order ZP\mathbb{Z}_P; ở đây mình giới hạn số nguyên tố chỉ 128 bit thôi cho dễ crack.

def try_prime(cap=2**32):
    p = getPrime(128)
    factors = factorize_factordb(p-1)
    if factors is not None and max(factors.keys()) < cap:
        print(p)
        print(factors)
        
threads = []
for _ in trange(100000):
    t = Thread(target=try_prime)
    t.start()
    threads.append(t)
for t in tqdm(threads):
    t.join()

Trong đó, hàm factorize_factordb lấy các ước từ trang factordb.com. Trong đó, các ước dài quá không hiện lên sẽ được skip, vì đằng nào nó cũng dài quá; nhưng sau này nếu cần bạn nên query link đó để lấy số cụ thể.

def factorize_factordb(p: int) -> dict:
    result = requests.get(f'http://factordb.com/index.php?query={p}').text
    # only get fully factored
    status = re.search(r'\WFF\W', result)
    # if not found
    if status is None: return None
    ret = {}
    pattern = r'<a href="index.php\?id=\d+"><font color="#\d\d0000">(\d(?:[\d.]+)?)(?:\^(\d+))?<\/font><\/a>'
    for match in re.finditer(pattern, result):
        xp, mult = match.groups()
        if '.' in xp: return None
        ret[int(xp)] = int(mult or 1)
    return ret

Đây là vài giá trị mình có được:

p1 = 238727251533741716722400942888398144591
f1 = {2: 1, 3: 5, 5: 1, 3659: 1, 5119: 1, 6709: 1, 1495633: 1, 252293677: 1, 2071853237: 1}
p2 = 333608929053242853170317622636449152139
f2 = {2: 1, 3: 1, 11: 1, 1373167: 1, 1640207: 1, 7028431: 1, 112211117: 1, 2845623511: 1}
p3 = 243252225961672840334482281305736742759
f3 = {2: 1, 3: 3, 23: 1, 29: 1, 97093697: 1, 103165889: 1, 569538457: 1, 1183823651: 1}

p = 268334761709516764273654696771078405403
p_ = {2: 1, 1109: 1, 102750629: 1, 342655031: 1, 1577600767: 1, 2178094333: 1}

Giờ chúng ta sinh ra tin nhắn và RSA MAC để crack:

# reverse RSA-based DSA
message = b"ButBeingLeftIsHarderYesItsTru"
msg = int.from_bytes(pkcs15_pad(message, 256 // 8), 'big')
n, _, d = generate_key(prime_bitlength=128)
enc = RSA_encrypt(msg, n, d)

Như đề bài đã nói, plaintext (msg) và signature (enc) nên là primitive root của cả pp lẫn qq. Ngoài ra, pq>npq>n để message/signature của chúng ta không bị wrap lại trong trường hợp xấu nhất. Chúng ta thử để chọn ra qq, và nếu không tồn tại thì throw RuntimeError vì sẽ không giải được với các lựa chọn số nguyên tố này:

if not is_primitive_root(enc, p, p_) or not is_primitive_root(msg, p, p_):
    # exit("Message/Signature is not a primitive root, please try again.")
    raise RuntimeError

if p * p1 > n and is_primitive_root(enc, p1, f1) and is_primitive_root(msg, p1, f1):
    q, q_ = p1, f1
elif p * p2 > n and is_primitive_root(enc, p2, f2) and is_primitive_root(msg, p2, f2):
    q, q_ = p2, f2
elif p * p3 > n and is_primitive_root(enc, p3, f3) and is_primitive_root(msg, p3, f3):
    q, q_ = p3, f3
else:
    # the primes are not good enough, try again
    # exit("Message/Signature is not a primitive root, please try again.")
    raise RuntimeError

Trong đó hàm is_primitive_root làm giống như trong hướng dẫn: check xem với tất cả các ước số có thể (ngoài 1 và chính nó) thì generator candidate đó có bị loop về 1 không:

def get_all_factors(prime_factors: dict) -> list:
    factors = []
    primes = list(prime_factors.keys())
    iterators = [range(prime_factors[k] + 1) for k in primes]
    for exponents in product(*iterators):
        factor = 1
        for p, e in zip(primes, exponents):
            factor *= p ** e
        factors.append(factor)
    factors.sort()
    return factors

def is_primitive_root(g: int, p: int, order: dict) -> bool:
    # ignore 1 and itself
    for factor in get_all_factors(order)[1:-1]:
        if pow(g, factor, p) == 1:
            return False
    return True

Ngoài ra, chúng ta cần thuật toán Pohlig-Hellman để tính discrete log với smooth-order groups: code này có hỗ trợ tính song song để tăng tốc độ.

def pohlig_hellman(y: int, g: int, p: int, order: dict, parallel=False):
    if len(order) == 1:
        x = 0
        for p_, e in order.items(): pass
        order = p_ ** e
        gamma = pow(g, p_ ** (e - 1), p)
        for k in range(e):
            h = pow(y * pow(g, order - x, p), pow(p_, e - 1 - k), p)
            d = bsgs(h, gamma, p_, p)
            x = (x + d * pow(p_, k)) % order
        return x
    else:
        params = []
        order_ = 1
        for p_, e in order.items():
            order_ *= p_ ** e
        factors = []
        for p_, e in order.items():
            factor = p_ ** e
            power = order_ // factor
            factors.append(factor)
            gi = pow(g, power, p)
            yi = pow(y, power, p)
            params.append([yi, gi, p, {p_: e}])
        if parallel:
            from multiprocessing import Pool, cpu_count
            remainders = Pool(cpu_count()).starmap(pohlig_hellman, params)
        else:
            from itertools import starmap
            remainders = starmap(pohlig_hellman, params)
        remainders = list(remainders)
        return chinese_remainder(factors, remainders)[0]

Và hàm đó cần sử dụng một hàm tính discrete log cơ bản chung chung. Ở đây mình sử dụng Shank's algo, hay còn gọi là baby-step giant-step:

def bsgs(y, g, n, p):
    '''
    Baby step - Giant step aka Shank's algorithm to find discrete log
    Params:
        @y  point to find the discrete log
        @g  generator of the Abelian group
        @n  order of the group/generator
        @p  the GF(p) we're working with
    '''
    m = ceil_root(n, 2)
    hashtable = dict()
    for j in range(m):
        hashtable[pow(g, j, p)] = j
    
    invm = pow(g, (-m) % (p - 1), p)
    gamma = y
    for i in range(m):
        if gamma in hashtable:
            return i * m + hashtable[gamma]
        gamma = (gamma * invm) % p

Viết nốt code sinh ra bộ (e,p,q)(e', p, q):

ep = pohlig_hellman(msg, enc, p, p_, True)
eq = pohlig_hellman(msg, enc, q, q_, True)

e = chinese_remainder([(p - 1) // 2, q - 1], [ep % ((p - 1) // 2), eq])[0]
new_msg = RSA_encrypt(enc, p * q, e)
assert msg == new_msg

Và phần còn lại là chạy: trong trường hợp (p,q)(p,q) không phù hợp, chúng ta chạy lại bài này để được secret private key khác 😄

Câu cuối về việc decrypt RSA ra một plaintext bất kỳ chỉ đơn giản là chúng ta chọn ss là plaintext cần decrypt ra, thay public exponent ee bằng private key dd, và giải sd=mmodNs^d=m \mod N tương tự.

Challenge 62: Key-Recovery Attacks on ECDSA with Biased Nonces

Do chúng ta sẽ phải làm việc với vector của các phân số, chúng ta sẽ code qua các hàm tính toán trên vector phân số:

Vector = List[Fraction]

def add(v1: Vector, v2: Vector) -> Vector:
    assert len(v1) == len(v2), "Cannot add vectors of different dimensions!"
    return [x1 + x2 for (x1, x2) in zip(v1, v2)]

def sub(v1: Vector, v2: Vector) -> Vector:
    assert len(v1) == len(v2), "Cannot subtract vectors of different dimensions!"
    return [x1 - x2 for (x1, x2) in zip(v1, v2)]

def dot(v1: Vector, v2: Vector) -> Fraction:
    assert len(v1) == len(v2), "Cannot dot product vectors of different dimensions!"
    return sum([x1 * x2 for (x1, x2) in zip(v1, v2)])

def l2_sqr(v: Vector) -> Fraction:
    return dot(v, v)

def scale(v: Vector, s: Fraction) -> Vector:
    return [x * s for x in v]

def project(v1: Vector, v2: Vector) -> Vector:
    '''
    Project v1 upon v2.
    '''
    assert len(v1) == len(v2), "Cannot project vectors of different dimensions!"
    l22v2 = l2_sqr(v2)
    if l22v2 == 0: return [Fraction(0)] * len(v1)
    return scale(v2, dot(v1, v2) / l22v2)

def gram_schmidt(basis: List[Vector]) -> List[Vector]:
    new_basis = []
    for i, vec in enumerate(basis):
        for k in range(i):
            vec = sub(vec, project(vec, new_basis[k]))
        new_basis.append(vec)
    return new_basis

Đọc pseudocode của LLL trên Wikipedia, chúng ta implement hàm LLL:

def LLL(basis, delta=0.99):
    '''
    Lenstra-Lenstra-Lovasz to reduce a basis
    '''
    basis = basis[:]
    ortho = gram_schmidt(basis)

    def mu(i, j):
        v = basis[i]
        u = ortho[j]
        return dot(u, v) / dot(u, u)

    n = len(basis)
    k = 1

    while k < n:
        for j in reversed(range(k)):
            mu_ij = mu(k, j)
            if abs(mu_ij) > 1 / 2:
                basis[k] = sub(basis[k], scale(basis[j], round(mu_ij)))
                # ortho = gram_schmidt(basis)

        if l2_sqr(ortho[k]) >= (delta - mu(k, k - 1) ** 2) * l2_sqr(ortho[k-1]):
            k = k + 1
        else:
            basis[k], basis[k - 1] = basis[k - 1], basis[k]
            # since only two vectors swapped
            old_k1 = ortho[k - 1]
            ortho[k - 1] = add(ortho[k], project(basis[k - 1], old_k1))
            ortho[k] = sub(old_k1, project(old_k1, ortho[k - 1]))
            # ortho = gram_schmidt(basis) # <-- old code
            k = max(k - 1, 1)

    return basis

Trong đó, chúng ta phải optimize sao cho không phải chạy Gram-Schmidt mỗi iteration (vì thuật toán đó chạy rất lâu, 2n32n^3 ops. Trong đó, có 2 chỗ đã sửa:

  • Chỗ đầu tiên chúng ta xóa luôn code gọi Gram-Schmidt, vì đang trừ thành phần của vjv_j khỏi vkv_k, với vjv_j đã xuất hiện trước. Từ đó, basis thứ kk có thể chắc chắn đã không còn component nào của vjv_j, nên basis không đổi.
  • Chỗ thứ chúng ta swap vk1v_{k-1}vkv_k: vậy chúng ta chỉ cần sửa basis ở 2 vector đó thôi.
    • vkv_k được chuyển lên trên, đồng nghĩa với việc chúng ta cần recover lại component của vk1v_{k-1} đã lọc từ lần Gram-Schmidt trước: project và cộng. Để ý là index của basis cần project phải là k1k-1 chứ không phải kk, do chúng ta đã swap từ trước.
    • vk1v_{k-1} bị chuyển xuống dưới, nên chúng ta chỉ phải trừ đi component mới mà chúng ta vừa làm ở gạch đầu dòng trên: project rồi trừ.

Sửa mấy cái đó cần biết về đại số tuyến tính, nên đừng tưởng bài này dễ nhai không cần kiến thức như họ đã quảng cáo. Nhưng mà tin vui là xong hết mấy phần khó rồi, giờ là thủ tục thôi: đầu tiên là định nghĩa curve:

curve = WeierstrassCurve(
        a = -95051,
        b = 11279326,
        p = 233970423115425145524320034830162017933,
        g = (182, 85518893674295321206118380980485522083),
        q = 29246302889428143187362802287225875743,
        order = (29246302889428143187362802287225875743 << 3)
    )

Và hàm ký sao cho 8 bit cuối của secret key bị zero out:

def broken_sign(message, private_key, curve, hash_fn=sha256):
    q = curve.q

    # get the leftmost bits equal to the group order
    hashed = int.from_bytes(hash_fn(message).digest(), 'big')
    hashed >>= max(hashed.bit_length() - q.bit_length(), 0)

    # generate nonce key
    while True:
        private = randrange(1, curve.q)
        # zero out the last byte
        private ^= (private & 0xFF)
        public = curve.g * private
        k, r = private, public.x
        if r % q == 0: continue
        s = ((hashed + private_key * r) * invmod_prime(k, q)) % q
        if s != 0: break
        
    return hashed, r, s

Tạo key,

# generate keys
secret, public = curve.generate_keypair()

Và ký vài (33) dòng lyrics:

# sign like 33 messages for keepsake
text = "<chorus, bridge, và verse 2 của No Church In The Wild>"
text = text.replace('\n\n', '\n').split('\n')
print(len(text)) # 33
bases = []
for i in range(len(text)):
    bases.append([Fraction()] * i + [Fraction(curve.q)] + [Fraction()] * (len(text) - i + 1))
us = []
ts = []
for msg in text:
    msg = msg.encode()
    # H(m), r, s
    h, r, s = broken_sign(msg, secret, curve)
    # since we know q is prime
    s_inv = invmod_prime(s << 8, curve.q)
    t = (r * s_inv) % curve.q
    u = (-h * s_inv) % curve.q
    us.append(Fraction(u))
    ts.append(Fraction(t))
ts.append(Fraction(1, 256))
ts.append(Fraction())
us.append(Fraction())
us.append(Fraction(curve.q, 256))
bases.append(ts)
bases.append(us)

Chạy hàm LLL, mình mất 8 phút. Nếu không optimize thì mỗi iteration bị chậm đi phải tầm nghìn lần, nên đừng thử.

bases = LLL(bases)

Và lấy lại secret key:

recovered = []
for vector in bases:
    if vector[-1] == Fraction(curve.q, 256):
        recovered.append(int(vector[-2] * -256) % curve.q)
assert secret in recovered

Cố lên, còn 4 challenge nữa thôi..



All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.