Cryptography

Tổng quan

    Cryptography (Mật mã học) là một phân nhánh cổ xưa nhất của bảo mật. Có lẽ trong số chúng ta lại biết nhiều nhất là mật mã Caesar của quân đội La Mã cổ đại, nhưng thực chất, lịch sử của mật mã học đã phát triển từ trước đó rất lâu rồi. Cụ thể, mật mã đầu tiên được ghi nhận là hệ thống các chữ tượng hình được khắc trên một lăng mộ tại Ai Cập (khoảng năm 1900 TCN), cũng vào thời kì này của Ai Cập, có một cuốn sách mang tên Greek Magical Papyri cũng được mã hoá một phần. Tại Ấn Độ (400 TCN - 200), các cặp đôi yêu nhau sử dụng kĩ thuật Mlecchita vikalpa như một phương pháp để trao đổi thông tin mà không bị phát hiện. Skip nhanh đến thời hiện đại, một nhà toán học vĩ đại, người mà nổi tiếng không chỉ trong lĩnh vực toán học, mà còn là tiền đề của ngành mật mã học và ngành học máy, Alan Turing với chiếc máy Bombe của mình, đã thành công giải mã các mật mã được tạo ra bởi cỗ máy Enigma của Đức Quốc xã (thứ mã Hitler ca ngợi là “Mật mã số một thế giới, thần thánh cũng không giải được”), từ đó, đem lại chiến thắng cho quân Đồng Minh.

­    Ngày nay, mật mã được ứng dụng rất nhiều trong tin học, cụ thể là trong việc trao đổi và lưu trữ dữ liệu một cách an toàn theo các tiêu chí:

-     Confidentiality (tính bảo mật): Dữ liệu phải được đảm bảo không bị lộ, truy cập bởi những người dung không được phép.

-     Integrity (tính toàn vẹn): Dữ liệu phải nguyên vẹn, đảm bảo không bị chỉnh sửa cho dù với bất kì nguyên nhân nào (bị tấn công, mất mát, …)

-     Availability (tính sẵn sàng): Dữ liệu phải luôn trong trạng thái sẵn sàng và có thể truy cập bất cứ lúc nào.

-     Non-repudiation (không thể chối bỏ): Cụ thể là khi dữ liệu được trao đổi giữa 2 bên A và B, cả 2 bên không thể phủ nhận việc đó, và cũng đồng thời chắc chắn rằng, không ai khác ngoài A và B biết điều này.

    Mặc dù tính sẵn sàng không được thể hiện quá nhiều trong mã hoá, nhưng trong ứng dụng thực tế, các cơ chế mã hoá điện tử lại thể hiện rất rõ 3 tính chất còn lại. Hiện nay, việc nhắc đến “Cryptography” là ám chỉ một trong các kĩ thuật sau:

-     Symmetric encryption (Mã hoá đối xứng)

-     Asymmetric encryption (Mã hoá bất đối xứng)

-     Hasing (Kĩ thuật băm)

-     Digital signatures (Chữ kí số)

Có 2 thuật ngữ mà ta cần nắm rõ:

-     Encryption: là quá trình mã hoá một thông điệp từ dạng đọc được (Plain text) thành không đọc được (Cipher text)

-     Decryption: là quá trình ngược lại của encryption (Cipher text à Plain text )

Symmetric encryption

​     Mã hoá đối xứng là kiểu mã hoá mà quá trình encryption và decryption sử dụng chung một mã (key). Các thuật toán mã hoá đối xứng thường được sử dụng như DES, AES, RC4, RC5,…

    Việc sử dụng mã hoá đối xứng sẽ hoạt động như sau:

-     Bên gửi sinh ra Plain text (M)

-     Bên gửi sinh ra một khoá kín (KS – Secret Key) một cách ngẫu nhiên và gửi cho bên nhận

-     Bên gửi sử dụng khoá KS để encrypt plain text M thành một bản mật (C - Cipher text), quá trình này được thể hiện như sau C = E(KS, M) và gửi cho bên nhận

-     Bên nhận sử dụng key KS và Cipher text đã nhận để Decrypt về plain text M = D(KS, C)

    Từ cơ chế trên, ta thấy rằng, việc để ổ khoá chung với chìa khoá như vậy sẽ sinh ra các vấn đề về bảo mật. Hãy thử tưởng tượng, ông tướng A gửi một thư mật cho ông tướng B, bức thư được mã hoá và bên dưới có ghi cách giải, ông A giao cho anh lính gửi hoả tốc, nhưng trên đường bị tướng địch bắn hạ và thu được mật thư :D Đây chính là phương pháp tấn công Man-in-the-middle (MITM).

Asymmetric encryption

    Mã hoá bất đối xứng là kiểu mã hoá mà quá trình encryption và decryption sử dụng mã key khác nhau, các thuật toán mã hoá tiêu biểu: RSA, DSA, PKCS,…

    Quá trình mã hoá bất đối xứng như sau:

-     Bên nhận tạo ra một khoá công khai (KP – public key) và gửi cho bên gửi, đồng thời tạo khoá kín (KS), được bên nhận giữ kín

-     Bên gửi sau khi tạo ra plain text (M), tiến hành mã hoá M bằng KP của bên nhận đã gửi trước đó:

C = E(M, KP) và gửi C cho bên nhận

-     Bên nhận sử dụng khoá KS để giải mã thông điệp đã nhận được: C = D(M, KS)

    Trong mã hoá bất đối xứng, KS và KP sẽ được tạo sao cho trong trường hợp người dung bị MITM lấy mất KP, hackers cũng không thể suy ra được KS nhưng vẫn tồn tại một mối quan hệ toán học giữa 2 key, cơ chế KS – KP này giúp người dung có thể yên tâm, ngay cả khi thông điệp giữa bên A và B bị lộ, thì những quá trình trao đổi thông tin giữa A và C, D, … vẫn được đảm bảo bí mật.

    Có thể thấy rằng, mã hoá bất đối xứng đã giải quyết được những hạn chế của mã hoá đối xứng, khi mà chỉ có người sở hữu KS mới có thể đọc được nội dung đã được mã hoá bằng KP. Nhưng, làm thế nào để ta biết được cái KP là chính xác của bên gửi? Hãy tìm hiểu thêm về Public Key Infrastructure (PKI). Trên thực tế, chúng ta sẽ nhờ các nhà cung cấp chứng thực số (Certificate Authority - CA) đóng vai trò làm trung gian trong quá trình trao đổi thông tin.

    Hashing functions

    Ngược lại với cơ chế mã hoá/giải mã như trên, hashing functions là những hàm chỉ có 1 chiều, tức là, bạn đưa input vào hash functions và nhận được một đoạn hash, nhưng bạn không thể convert ngược đoạn hash đó về input được :D

    Một hàm hashing lý tưởng phải thoả mãn 2 điều kiện:

-     Mã hash được tạo ra của input phải là độc nhất, 2 input khác nhau không được phép có mã hash giống nhau.

-     Với input giống nhau phải cho ra mã hash giống nhau.

    Nếu đã từng thao tác với mã hash thì sẽ thấy chúng giống như được tạo ra ngẫu nhiên, nhưng không phải vậy, với mỗi loại mã hash (SHA256, MD5, …) thì chúng sẽ có một độ dài cố định.

    Từ những đặc điểm trên, hashing functions không thể được sử dụng trong việc lưu trữ dữ liệu (mã hoá xong phát coi như mất :D) nhưng lại có thể được sử dụng để xác định tính toàn vẹn của dữ liệu, vì chỉ cần thay đổi dù chỉ là một dấu cách trong input, sẽ tạo ra một mã hash khác hoàn toàn. Bên cạnh đó, khi mà việc lưu trữ trực tiếp password trong database đã quá nguy hiểm, việc lưu trữ chúng dưới dạng Hashing cũng là một lựa chọn, lưu password được tạo dưới dạng mã hash, mỗi lần người dùng đăng nhập thì hashing lại input của người dùng và đối chiếu với mã hash đã lưu, vừa đảm bảo có gì đó để so sánh, vừa đảm bảo không để lộ thông tin nhạy cảm khi sự cố xảy ra.

    Digital signatures

    Đây là sự kết hợp giữa mã hoá bất đối xứng và hashing functions:

-     Phía signer sẽ tiến hành hash input và mã hoá tiếp với KS

-     Signer gửi thông điệp đính kèm với chữ kí số vừa được tạo

-     Phía người nhận sẽ sử dụng KP để decrypt chữ kí số về mã hash, sau đó tiến hành hash thông điệp đính kèm để đối chiếu với mã hash của chữ kí số

    Đây là cách để đảm bảo tính toàn vẹn, tính bảo mật và tính không thể chối từ của thông điệp được gửi đi. Nhờ đảm bảo được những điều trên, chữ ký số được sử dụng trong giao dịch điện tử, e-mail, chuyển tiền, thanh toán trực tiếp, … Ngoài ra, chữ ký số cũng được áp dụng trong các công vụ của Chính phủ như thuế, hải quan, …

Kết luận

    Mật mã học (Cryptography) là một mảng đã có quãng thời gian phát triển lâu đời nhất trong bảo mật thông tin, với lịch sử phát triển lâu đời như vậy, thật không dễ để chúng ta có thể nắm được, vì vậy tôi xin được đề cập một số cuốn sách để tham khảo và rèn luyện về mảng “Old but Gold” này:

-     Cryptography made simple – Nigel P. Smart

-     Applied cryptography – Bruce Schneier

-     Cryptography: Theory and Practice – Doug Stinson

-     Understanding cryptography: A textbook for students – Christof Paar

-     Giáo trình mật mã học và an toàn thông tin – Ts. Thái Thanh Tùng

Continue Reading...

FPT Uni SecAthon 4 | Cryptography Writeup | CRY301-CRY302-CRY303

 

CRYPTO

1. CRY301 (1000 pts)

Một bài crypto giải bằng kiến thức toán học và tư duy về code. Full source code đề bài xem tại đây

Bài này yêu cầu mình tìm được số xban đầu từ kết quả của 2 hàm easyone(x) và alittlebitharderone(x).

a. Phân tích hàm easyone(x)

Nhìn sơ qua hàm easyone(x), có 3 phép biến đổi chính được lặp đi lặp lại 3 lần

1. Phép xor với left shift bit của chính nó
2. Phép nhân
3. Phép & với 0xffffffffffffffffffffffffffffffff.

def easyone(x):
    assert(x < 2 ** 128)
    x ^= x >> (64 + 19)
    x *= 0xd3856e824d9c8a26aef65c0fe1cc96db #281159923981539500379670095774511568603
    x &= 0xffffffffffffffffffffffffffffffff
    x ^= x >> (64 + 3)
    x *= 0xe44035c8f8387dc11dd3dd67097007cb #303397380928069120521467215513016862667
    x &= 0xffffffffffffffffffffffffffffffff
    x ^= x >> (64 + 20)
    x *= 0xc9f54782b4f17cb68ecf11d7b378e445 #268448390289851351177030176676964262981
    x &= 0xffffffffffffffffffffffffffffffff
    x ^= x >> (64 + 2)
    return x

Như vậy, có 2 bài toán đặt ra cần giải quyết:

1. Tìm x biết ax = b \pmod na∗x=b(modn) với aa, bb, nn* đã biết.
2. Khôi phục lại kết quả phép xor. Tìm x có a \oplus x = ba⊕x=b với aa, bb đã biết. Khá đơn giản với x=a \oplus bx=a⊕b.

Cùng đi sâu hơn chút vào từng bài toán 1 nhé

Bài toán 1: Tìm x biết ax = b \pmod na∗x=b(modn) với aa, bb, nn* đã biết.

Đây là bài toán cơ bản cơ bản về inverse mod (modular inverse) trong finite field (trường hữu hạn). Đơn giản, mình có thể tìm xx bằng cách x = a^{-1} b \pmod nx=a−1∗b(modn), trong đó a^{-1} \pmod na−1(modn) là giá trị inverse modulo của a trong finite field \bmod (n)mod(n*).

Chi tiết cách tìm inverse mod bằng toán học với extended euclidean algorithm có thể xem tại đây. Lúc code giải thì mình dùng luôn hàm invert(a, n) trong thư viện gmpy2 của python để tìm a^{-1} \pmod na−1(modn)

Mình chuyển 1 đoạn code sang dạng bài toán gốc để dễ hình dung. Cụ thể, đoạn code dưới đây biểu diễn dưới dạng toán học sẽ là x 281159923981539500379670095774511568603 = b \pmod nx∗281159923981539500379670095774511568603=b(modn) với bb* có thể thu được từ việc dịch lại phép xor (sẽ nói ở bài toán 2).

Lưu ý: x &= 0xfffffffffffffffffffffffffffffffftương đương với x %= 0xffffffffffffffffffffffffffffffff, hay x %= 2**128

x *= 0xd3856e824d9c8a26aef65c0fe1cc96db #281159923981539500379670095774511568603
x &= 0xffffffffffffffffffffffffffffffff

Như vậy, ta có thể dễ dàng tìm xx với x = b281159923981539500379670095774511568603^{-1} \pmod {2^{128}}x=b*∗281159923981539500379670095774511568603−1(mod2128).

x *= gmpy2.invert(268448390289851351177030176676964262981, 2**128)
x &= 0xffffffffffffffffffffffffffffffff

Vấn đề là để hoàn thiện quá trình giải thì mình cần tìm bb, nghĩa là cần phải giải quyết bài toán số 2. Ngay sau đây 

Bài toán 2: Khôi phục lại kết quả phép xor

Để giải quyết phần xor này, chúng ta cần phải lưu tâm x sau khi bitshift thì còn những bit nào còn giữ nguyên, bit nào dịch chuyển để thực hiện xor.

x ^= x >> (64 + 2)

Để dễ hình dung, bạn có thể nhìn hình mô phỏng trước và sau khi leftshift dưới đây. Bit màu xanh là những bit còn giữ nguyên sau khi leftshift. Bit màu vàng là bit màu xanh được chuyển ra sau khi leftshift. Bit màu đỏ là những bit có thể bị thay đổi sau bitshift (và cũng là bit thực sự tham gia xor)

Dễ dàng nhận thấy, phần bit dùng để xor với giá trị x ban đầu vẫn giữ nguyên sau khi xor \longrightarrow⟶ Như vậy mình có thể dễ dàng khôi phục phần bit dùng để xor bằng cách leftshift lại giá trị sau khi xor bằng đúng một khoảng dùng để xor trước đó (tức leftshift (64+2) đơn vị trong trường hợp trên).

x ^= x >> (64 + 2)

Kết luận trên đúng với tất cả trường mà x được leftshift ít nhất 64 đơn vị.

Vậy là mình đã giải quyết xong cả 2 bài toán trên! Cuối cùng mình có đoạn code để lấy giá trị x từ hàm easyone(x) như sau:

def solveeasyone(x):
    x ^= x >> (64 + 2)
    x *= gmpy2.invert(268448390289851351177030176676964262981, 2**128)
    x &= 0xffffffffffffffffffffffffffffffff
    x ^= x >> (64 + 20)
    x *= gmpy2.invert(303397380928069120521467215513016862667, 2**128)
    x &= 0xffffffffffffffffffffffffffffffff
    x ^= x >> (64 + 3)
    x *= gmpy2.invert(281159923981539500379670095774511568603, 2**128)
    x &= 0xffffffffffffffffffffffffffffffff
    x ^= x >> (64 + 19)
    return int(x)

Tada, first round~~

b. Phân tích hàm alittlebitharderone(x)

Giải quyết hàm này cũng cần giải quyết 2 bài toán như hàm easyone(x). Bài toán 1 về tìm inverse mod hoàn toàn giống hệt. Cái khó hơn nằm ở Bài toán 2, do mình không thể ngay lập tức khôi phụ được bit dùng trong phép xor trước đó từ kết quả thu được.

Tuy nhiên, điều đáng mừng là nguyên lý cách làm vẫn thế. Chúng ta cũng sẽ dùng những bit còn nguyên, để khôi phục lại những bit gốc, rồi lân la dần dần để khôi phục toàn bộ bit gốc đó. Mình mô phỏng với 1 bài toán nhỏ với 1 chuỗi 6 bit với độ leftshift bằng 2 như sau:

Với trường hợp như trên, mình khôi phục lại giá trị ban đầu của x bằng cách đi qua từng bước như sau đây (Mô tả bằng hình ảnh cho dễ hiểu nhé)

1. Xor 2 bit đầu (2 bit còn giữ nguyên sau khi xor) với 2 bit liền kều sau nó. Những bit còn lại giữ nguyên. Như vậy, mình đã khôi phục lại được bit số 3 và bit số 2

   

   

2. Xor tiếp 2 bit vừa thu được (bit số 3 và 2) với 2 bit liền kề sau nó để khôi phục tiếp 2 bit còn lại (bit 5 và 6)

   

   

Vậy làm mình đã thu lại được đoạn bit gốc, tức giá trị của x cần tìm. Với chuỗi bit dài hơn, mình chỉ cần chạy quá trình trên lặp đi lặp lại là được.

Dễ rồi phải không? Mặc dù mình nghĩ ra được ý tưởng mình việc code tốn của mình tận 30 phút... và cuối cùng lại chỉ thành 1 đoạn code ngắn ngủi sau:

def xor(a, b):
    return ''.join(str(int(_a) ^ int(_b)) for _a, _b in zip(a, b))

def shiftsolong(x, bitshift):
    x = '{0:b}'.format(x)
    for i in range(0, len(x) - bitshift):
        x = x[:bitshift*(i+1)] + xor(x[bitshift*i:bitshift*(i+1)], x[bitshift*(i+1):bitshift*(i+2)]) + x[bitshift*(i+2):]
    return int(x, 2)

Ta nói đời về căn bản là buồn mà  Thôi tổng hợp lại, thì mình có đoạn code lấy lại giá trị x từ hàm alittlebitharderone(x)

def solvehardone(x):
    x = shiftsolong(x, 2)
    x *= gmpy2.invert(268448390289851351177030176676964262981, 2**128)
    x &= 0xffffffffffffffffffffffffffffffff
    x = shiftsolong(x, 20)
    x *= gmpy2.invert(303397380928069120521467215513016862667, 2**128)
    x &= 0xffffffffffffffffffffffffffffffff
    x = shiftsolong(x, 3)
    x *= gmpy2.invert(281159923981539500379670095774511568603, 2**128)
    x &= 0xffffffffffffffffffffffffffffffff
    x = shiftsolong(x, 19)
    return int(x)

Qua vòng 2 và nhận được flag. Chỉ là không kịp submit nữa...

Nếu có ước muốn trong cuộc đời này, mình sẽ ước có một không gian riêng mà thời gian chảy chậm để ngồi debug trước khi hết giờ FUSEC 

2. CRY302 (1000 pts)

1 bài liên quan tới hash, cách thực hiện khá dễ. Full source code bạn có thể xem tại đây

a. Bổ đề

Tóm tắt lại thì mình sẽ được đưa cho 1 số tiền ngẫu nhiên từ 1 tới 2000 và bị bắt phải mua 1 cái FLAG có giá tận 99,999. Kiểu gì cũng không đủ cho được.

Khi mình order 1 vật phẩm bất kỳ, order của mình sẽ có cấu trúc dạng kiểu product=FLAG&price=99999&time=1633845957.70&sign=67df43a8c83ea4ee53ac7bb61cc9a51661f5b55b54153afb942246c11a3ab9a93cb7a1cecb235195eab957fceb3e3daaf3e97f484d29718aea8b0f63e1a3704a (đã được decode từ chuỗi base64 encoded)

Khi nhập lại cái order ở trên để xác nhận mua sản phẩm, order này được kiểm tra các cấu trúc và tính toàn vẹn, cụ thể gồm:

1. Tồn tại cặp parameter-value sign={sign_value}
2. Có signature hợp lệsha512(signkey+payment).hexdigest() == signature

Sau khi qua các bài check trên, payment sẽ được truyền vào hàm parse_sql(self, query) để tiến hành extract các parameter tương ứng.

def parse_qsl(self, query):    m = {}    parts = query.split(b'&')    for part in parts:        key, val = part.split(b'=')        m[key] = val    return m

Với cách hàm parse hoạt động như này, giả sử query có 2 cặp giá trị của price (ví dụ như price=99999&price=0) thì giá trị price cuối cùng sẽ được quyết định bởi cái đằng sau. Điều đó đồng nghĩa với việc nếu mình có thể kéo dài cái payment của mình bằng cách append thêm 1 đoạn &price=0, mình có thể mua bất cứ thứ gì trong cửa hàng!

Ý tưởng kéo dài 1 đoạn payment được hash đã đưa mình đến hash length extension attack

b. Hash length extension attack

Hash length extension attack là gì?

Hash length extension attack cho phép mình kéo dài chuỗi văn bản được hash, đồng thời tính toán giá trị hash mới hợp lệ cho chuỗi văn bản được kéo dài ra từ hash của chuỗi văn bản ban đầu.

Nguồn đọc hiểu hash length extension attack

Trước hết, cần phải hiểu được sha512 hoạt động như thế nào đã. Bạn có thể xem tổng quan về hàm sha512 tại đây và xem chi tiết cách sha512 vận hành từng bước 1 tại đây. Thanks for Indian guys 

Tiếp đó, mình đọc mô tả cách hash length extension attack hoạt động, và có bản demo tại đây. Thực ra trước có 1 bài blog bằng tiếng Việt cho họ hash SHA luôn, mà giờ trang đấy sập rồi  Nên mình sẽ mô tả lại trong bài này để các bạn hiểu dưới góc độ python code, phòng trường hợp các bạn đọc demo trên mạng đều code bằng C và không hiểu gì =)))

Điều kiện để thực hiện hash length extension attack

Để thực hiện được hash length extension attack mà văn bản xác thực có dạng secret_value + public_value, mình cần có đủ 3 dữ kiện:

1. Độ dài của secret_value, ở trong bài này chính là độ dài của signkey. Bài không cho cụ thể nhưng chỉ cho 24 giá trị khả năng, hoàn toàn có thể bruteforce. Mình không cần giá trị của secret_value!
2. Giá trị của public_value, ở trong bài này chính là payment
3. Giá trị hash của secret_value + public_value, ở trong bài này chính là sign

Vậy là bài này hội tụ đủ cả 3 yếu tố để tiến hành rồi.

Tiến hành tấn công thôi!

Mục tiêu của mình bao gồm:

1. Append thêm 1 đoạn &price=0 vào cuối payment
2. Tạo ra 1 giá trị sign mới sao cho sha512(signkey+payment) = sign với payment mới

Sơ sơ cơ chế hoạt động của hash length extension attack sẽ như sau.

1. Cơ chế hoạt động của hàm hash: Hàm hash sha512 sẽ chia input đầu vào thành các khối 1024 bits, mỗi khối lại chia thành từng phần nhỏ h[i]gồm 128 bits. Một tuple (h[0], h[1], h[2], h[3], h[4], h[5], h[6], h[7]) được gọi là current_state của hàm hash hiện tại. current_state sẽ được dùng để tính state cho khối 1024 bits tiếp theo. Hàm xử lý quá trình này gọi là round_function hoặc compress (tùy theo tài liệu). Kết quả cho khối 1024 bits cuối cùng chính là giá trị hash mình thu được.
2. Cơ chế hoạt động của hash length extension attack: Từ cơ chế hoạt động trên của hàm hash, mình có thể thấy rằng chỉ cần biết được current_state và khối 1024 bits cuối cùng, mình hoàn toàn có thể tính toán state cho khối 1024 bits tiếp theo, trong đó, khối 1024 bits sẽ có giá trị tùy ý mình thích. Đó cũng chính là giá trị hash mới với chuỗi văn bản được kéo dài.

Khá là đơn giản phải không. Giờ mình sẽ đi vào cụ thể nhé:

1. Order FLAG, nhận giá trị order trả về product=FLAG&price=99999&time=1633849486.36&sign=275e626950c677c05a669e4e9d73f015858ca2b477335b2e99f419f9f0bc860736e95bd87de1226764c70f8c59029edc10e6b2a514342bb85f0c29fe24b9d3e2. Tách payment và sign riêng.
2. Padding cho payment để payment có dạng k1024k*∗1024, và lấy block cuối cùng, thu được product=FLAG&price=99999&time=1633849486.36\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02P. Vốn chuỗi ban đầu không dài hơn 1024 bits nên cũng chỉ có block duy nhất. Trong phần ví dụ này, mình giả sử độ dài của signkey bằng 31. Cơ chế padding mình đính kèm nguồn ở trên.
3. Append chuỗi &price=0 vào chuỗi đã được padding ở trên. Lại tạo 1 khối 1024 bits có chứa &price=0 bằng cách padding, thu được &price=0\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x018
4. Extract state từ giá trị sign, sau đó đưa state cùng khối 1024 bits có chứa &price=0 ở trên vào hàm compress của sha512, thu được giá trị sign mới bằng ad38b9ceecbdf41de6bb33970a473ecc1c500935e2cfd90007be639fa6754b6272c45340fca0f173090748722cc1e25e3440cc9975c3b712a8cabe7809cf6d7f
5. Nối chuỗi payment mới và sign mới vào với nhau, chuyển lên server và lấy flag. order mới sẽ là product=FLAG&price=99999&time=1633849486.36\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02P&price=0

Vậy là xong!

c. Full code exploit

Vì bài không cho giá trị cụ thể của độ dài signkey, nên mình phải viết 1 đoạn code chạy tự động trong khoảng giá trị [8, 32][8,32]. Full code exploit có thể xem ở đây. Trong code này, mình có sử dụng lại thư viện hlextend của stephenbradshaw trên github, với một chút chỉnh sửa để output ra có dạng byte thay vì string.

def solve():
    [REDACTED]

    #order
    output = recvuntil(clientSock, b'Your choice:')
    clientSock.sendall(b'2\n')
    output = recvuntil(clientSock, b'ID:')
    clientSock.sendall(b'6\n')
    output = recvuntil(clientSock, b'Your choice:')
    order = output.split(b'\n')[0][len('Your order:'):].strip()
    order = b64decode(order).decode('latin-1')

    sp = order.rfind('&sign=')
    sign = order[sp+6:]
    payment = order[:sp]
    append_msg = '&price=0'


    for i in range(8, 33):
        sha = hlextend.new('sha512')
        new_payment = sha.extend(append_msg, payment, i, sign)
        new_sign = sha.hexdigest()
        new_order = new_payment + b'&sign=' + new_sign.encode()
        new_order = b64encode(new_order)

        #confirm order
        clientSock.sendall(b'3\n')
        output = recvuntil(clientSock, b'Your order:')
        clientSock.sendall(new_order + b'\n')
        output = recvuntil(clientSock, b'Your choice:')
        if b'FUSec{' in output:
            flag = output.decode()[output.index(b'FUSec{'):output.index(b'}')+1]
            print(flag)
            break

Flag FUSec{th1s_1s_4n_0ld_vul_bUt...}

3. CRY303 (991 pts)

Một bài siêu khó về Knapsack cipher sử dụng LLL (Lenstra–Lenstra–Lovász), hay còn gọi là Latice Reducation Technique, để giải.

Nói thật thì bài này mình cũng không tự làm được lúc tham gia giải CTF, nhưng search google được 1 bài giống tới 90%, nên chỉ đọc hiểu code rồi giải lại. Bởi vì bài cũng không có gì khác biệt mấy, nên mình để nguồn bài gốc ở đây để các bạn đọc vậy.

• Link github exploit code + writeup: https://github.com/pcw109550/write-up/tree/master/2020/KAPO/Baby_Bubmi
• Bài viết cụ thể giải thích cơ chế hoạt động: http://www.secmem.org/blog/2020/09/20/poka-science-war-hacking/

Đề bài này và code giải (đã sửa theo bài) mình để ở github của mình.

Thế là hết crypto rồi. Nếu mà kịp giải hết thì mình cũng mạnh dạn insert bomman meme gáy... nhưng không được nên gà không gáy nữa...

                written by thangpd3160

Continue Reading...

FPT Uni Secathon 3 | Cryptography Writeup | CRY301 - CRY302

This is an annual competition for FPT University students to practice their skills with jeopardy CTF challenges. I was with my team, M1sh13f, and we’re at the #5 place. Congrats me and my amazing teammates!!!!

No more beating around the bush, here are my write-ups for the first two cryptography challenges.

 

Challenge: CRY301 – 1000 pts

When netcat to the server, I can easily see that this cryptography challenge is about RSA encryption and decryption with the presence of public key n, e and also the private key d.

But clearly, the server doesn’t tell anything about the ciphertext to decrypt or the message to encrypt. So, I take a look at the given zip file, containing two files: quotes.py and server.py.

The quotes.py file contains a list of possible messages that the server will send you if you don’t come up with the right flag. So, I don’t spend any minute on the quotes.py but the other file server.py.

MAGIK_STRING = b"Aww, c'mon, what's the worst that could happen?"

def handle(self):

        self.request.sendall(banner())

        n, d, e = gen_key_pair()

        self.request.sendall(b'    n = %d' % (n) + b'\n')

        self.request.sendall(b'    e = %d' % (e) + b'\n')

        self.request.sendall(b'    d = %d' % (d) + b'\n')

        self.request.sendall(

            b'\n    Now if you say the magik number correctly, I\'ll give you a magik string as a reward\n')

        self.request.sendall(b'    Enter your number here: ')

        try:

            magik_number = int(self.rfile.readline().decode())

        except ValueError:

            self.request.sendall(b'\n    ' + random_quotes() + b'\n')

            return

        if magik_number == pow(bytes_to_long(MAGIK_STRING), e, n):

            self.request.sendall(b'\n    ' + random_quotes() + b'\n')

            return

        if not pow(magik_number, d, n) == bytes_to_long(MAGIK_STRING):

            self.request.sendall(b'\n    ' + random_quotes() + b'\n')

            return

        self.request.sendall(b'\n    ' + rewards() + b'\n')

So, the message to encrypt here is the given MAGIK_STRING. And you need to find the ciphertext. It’s easy enough as the server already gave out the key. But you can see that the server won’t accept the value of c = pow(message, e, n).

The solution here is to find the number c’ that c and c’ are congruent modulo n. Simply enough, you just need to add c with n.

c’ = c + n

Send c’ to the server and here is the flag:

FUSEC{Rul3s_4r3_m4d3_t0_b3_br0k3n_lik3_buildingz_0r_p30pl3_1602068882}

Challenge: CRY302 — 1000 pts

This challenge is an upgraded version of the CRY301 problem you have seen above. netcat to the server will ask us to input the magik number.

Check out the given source code, it tells us something about the prefix of the magik number.

MAGIK_STRING = b"I cannot be good. I must be perfection."

SUFFIX = b"You lack imagination."

def handle(self):

    self.request.sendall(banner())

    n, d, e = gen_key_pair()

    self.request.sendall(b'    n = %d' % (n) + b'\n')

    self.request.sendall(b'    e = %d' % (e) + b'\n')

    self.request.sendall(b'    d = %d' % (d) + b'\n')

    self.request.sendall(

        b'\n    Now if you say the magik number correctly, I\'ll give you a magik string as a reward\n')

    self.request.sendall(b'    Enter your number here: ')

    try:

        magik_number = int(self.rfile.readline().decode())

    except ValueError:

        print('Not a number')

        self.request.sendall(b'\n    ' + random_quotes() + b'\n')

        return

    if magik_number == pow(bytes_to_long(MAGIK_STRING), e, n):

        print('Sent c')

        self.request.sendall(b'\n    ' + random_quotes() + b'\n')

        return

    if not long_to_bytes(magik_number).endswith(SUFFIX):

        print('Not end with suffix')

        self.request.sendall(b'\n    ' + random_quotes() + b'\n')

        return

    if not pow(magik_number, d, n) == bytes_to_long(MAGIK_STRING):

        print('Decrypt does not return magik')

        self.request.sendall(b'\n    ' + random_quotes() + b'\n')

        return

    self.request.sendall(b'\n    ' + rewards() + b'\n')

This challenge gives us more condition for the valid magik number. Similar to the first problem, we will need to find the number c’ that c and c’ are congruent modulo n. Also, c’ must end with the given SUFFIX.

The first hint gave me the idea of crafting an equation. As c’ and c are congruent modulo n, c’ = c + x * n. So, I have one side of an equation with an unknown x.

The other side of the equation will present the condition of ending with SUFFIX. The second hint is about how the bytes_to_long() and long_to_bytes() function work.The ultimate last hint is about how the endswith() method can be presented into the equation

So, here is the other side of the equation c’ = k * 16 ** len(hexlify(SUFFIX)) + bytes_to_long(SUFFIX) with the unknown k. You can calculate the length of SUFFIX and the value of bytes_to_long(SUFFIX). And the complete equation with c = pow(magik_String, e, n):

c + x * n = k * 16 ** 42 + 130709955709673130759780524244946733922755218992686

The next step is to solve this equation and find one value of x and k. The Sage Cell Server, an online version of Sagemath, can help.

Sagemath command to solve the equation from Sagemath doc

Replace the c and n value, and here is the output.

The unknowns x and k are described through the new t_0 variable.

Now I only need the x value, so I will choose a random value for t_0 to find x. The simplest case is t_0 = 0, and I have the value of x. Then calculate c’ = c + x * n.

Submit c’ to the server and here is our flag.

FUSEC{In_c4rn4g3_I_bl00m_lik3_4_fl0w3r_in_th3_d4wn_1602085220}

I will update the write-up for the final challenge of this competition as soon as possible. Thank you for reading.

Keeping on CTF :))) !!!!

— Jessie —

Continue Reading...