[Plaidctf 2015] Crypto180 - Lazy

[ping]

Plaidctf 2015 do nhóm PPP tổ chức diễn ra vào giữa tháng 4 vừa rồi với nhiều challenge khá thú vị. Dưới đây tôi sẽ trình bày write-up challenge lazy – crypto180, một trong những challenge mà tôi giải được.

Đầu bài cung cấp cho chúng ta 1 file nén trong đó có:

• knapsack.py: thực hiện công việc sinh mã và giải mã
• utils.py: chứa các hàm phụ trợ cho knapsack.py
• pubkey.txt: khóa công khai
• ciphertext.txt: văn bản đã bị mã hóa

Mục tiêu của chúng ta trong challenge này là phá hệ mã công khai knapsack. Như hầu hết các hệ mã khóa công khai khác, nguyên lý của chúng đều dựa trên các bài toán khó giải trong thời gian thực (NP khó). Hệ mã knapsack được xây dựng dựa bài toán tổng các tập con - subset sum problem (đây là trường hợp đặc biệt của bài toán cái túi – knapsack problem), được phát biểu như sau:

Cho trước một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng 0?

Sử dụng hệ mã knapsack như sau:

1. Tạo khóa:
   • Chọn một chuỗi số siêu tăng A = {a1, a2...an}, là chuỗi mà giá trị của số ở vị trí i+1 lớn hơn tổng giá trị của các số đứng trước nó
   • W = a1+a2+...+an
   • Chọn một số N > W
   • Chọn một số r trong khoảng [1, N) và nguyên tố cùng nhau với N
   • Khóa bí mật bao gồm (N, W, r)
   • Khóa công khai là chuỗi P = {p1, p2 ...pn}, với pi = (ai*r) mod N
2. Sinh mã
   • Với văn bản thuần đầu vào, chuyển nó về dạng chuỗi nhị phân M = {m1, m2..mn}, chuỗi này có độ dài bằng số phần tử của chuỗi khóa công khai
   • Tính C = m1*p1+ m2*p2 +...+mn*pn
3. Giải mã
   • Tính C’ = C*r-1 mod N với r-1 là nghịch đảo modul N
   • Do C’ = A.M nên có thể tính được M

Trở lại với challenge lazy, hàm sinh mã và giải mã trong file knapsack.py đúng như quy trình trên. Chúng ta có thể chuyển việc giải challenge này về giải bài toán tìm chuỗi nhị phân M thỏa mãn:

Trong đó:
• m1, m2, ...mn là các phần tử của M, mi = {0, 1}
• p1, p2, ...pn là các phần tử của khóa công khai
• C là chuỗi số ciphertext

Để giải bài toán trên, tôi sử dụng thuật toán LLL (Lenstra–Lenstra–Lovász), về cơ bản đây là thuật toán tối ưu lưới. Trong trường hợp này, sử dụng LLL sẽ giúp chúng ta tìm short vector, chính là tập các giá trị m. Tôi sẽ chỉ trình bày phương pháp sử dụng LLL ở đây, các bạn có tìm hiểu thêm ứng dụng LLL trong việc phá mã knapsack ở những nguồn khác.
Đầu tiên, tôi chuyển các dữ liệu đầu vào về dạng ma trận

Tôi dùng sagemath để áp dụng LLL cho ma trận này và lấy flag
Source code: https://github.com/everping/ctfs/blob/master/2015/4/plaidctf/crypto/lazy/solve.py

__author__ = 'Ping'


def load_data():
    """
    Load input data from file
    :return: ciphertext and public key
    """
    f1 = open('pubkey.txt', 'r')
    f2 = open('ciphertext.txt', 'r')
    pub_keys = f1.read().strip()[1:-1].split(', ')
    ciphertext = int(long(f2.read().strip()))
    f1.close()
    f2.close()
    return pub_keys, ciphertext


def create_matrix_from_knapsack(ciphertext, pub_keys):
    """
    Create the matrix from input data of the form [URL]http://goo.gl/aOQE7J[/URL]
    """
    last_col = []
    for p in pub_keys:
        last_col.append(int(long(p)))

    last_col.append(ciphertext)
    last_row = [1 for i in pub_keys]

    # I use sagemath to do this
    my_matrix = MatrixSpace(ZZ, len(pub_keys))(2)
    m_last_row = matrix(ZZ, 1, len(last_row), last_row)
    m_last_col = matrix(ZZ, len(last_col), 1, last_col)

    my_matrix = my_matrix.stack(m_last_row)
    my_matrix = my_matrix.augment(m_last_col)

    return my_matrix


def is_short_vector(vector):
    """
    Is short vector?
    :return: True/False
    """
    for v in vector:
        if v != 1 and v != -1 and v != 0:
            return False
    return True


def find_short_vector(matrix):
    """
    Find short vector from matrix was applied LLL algorithms
    """
    for row in matrix:
        if is_short_vector(row):
            return row


def main():
    pub_keys, cipher = load_data()
    my_matrix = create_matrix_from_knapsack(cipher, pub_keys)

    # Apply LLL algorithm to matrix
    new_matrix = my_matrix.LLL()

    # Get short vector
    short_vector = find_short_vector(new_matrix)

    # Change 1 to 0 and -1 to 1 to get solution vector
    solution_vector = []
    for v in short_vector:
        if v == 1:
            solution_vector.append(0)
        elif v == -1:
            solution_vector.append(1)

    # and we get flag
    flag = hex(int(''.join([str(i) for i in solution_vector])[::-1], 2))[2:-1].decode('hex')

    print flag


main()

 

Re: [Plaidctf 2015] Crypto180 - Lazy

Hóa ra thím là con sâu đó à -_-