[CSAW CTF 2013] crackme (Re300)

crackme – 300 Points

Solved by 174 teams.

nc 128.238.66.218 54321
crackme

File dự phòng:

Nội dung chính

Thuật toán của target không có gì phức tạp, có thể minh họa lại như sau:

Điều chúng ta cần là tìm ra một key (dài tối đa 256 ký tự) với giá trị sau khi gọi hàm calc()0xEF2E3558.

Đây là một bài mà mình nghĩ để ở bên Crypto sẽ hợp lý hơn là Reversing, và nó đồng thời cũng là bài mà mình thấy “không vui” nhất sau khi cuộc thi kết thúc. Mình quyết tâm tìm một lời giải đẹp mắt hơn, tất nhiên sẽ kèm cả may mắn nữa, nhưng không đến mức quá hên xui như writeup của một số team đã post.

Chúng ta cần nhận thức rõ những vấn đề sau:

  • Với một kết quả cho trước, có thể tìm được nhiều key thỏa mãn.
  • Không có thuật toán tìm ngược từ kết quả để ra được key, lý do là ở mỗi bước tính toán, ta đều chỉ giữ lại giá trị thuộc phạm vi 32bit, nên không thể biết được 0xEF2E3558 kia, nó có thực sự là 0xEF2E3558 không, hay lại là 0x01EF2E3558, 0x02EF2E3558,… hay thậm chí là 0x22EF2E3558? Chính bởi vì có quá nhiều trường hợp để thử, trong khi độ dài chính xác của key lại không biết, nên chúng ta chỉ có thể lê những bước nặng nhọc trên một ngả đường hoang vắng mà thôi.

Dù không biết được độ dài key, nhưng chúng ta cần có một niềm tin rằng, nó sẽ không quá dài. Thật vậy, nếu là người ra đề, chúng ta cũng không hâm hâm đến mức đập loạn xạ vô bàn phím để ra một key loằng ngoằng bất tận, rồi hả hê tự nhủ rằng “Đố thằng nào tìm được”, đó chỉ là phong thái của các bạn tự kỷ thôi tire

Nhưng giả sử rằng, ta biết key chỉ dài cùng lắm là 30 ký tự (xin lỗi, 30 là số đẹp của mình), thì có thể làm gì? Cũng vẫn rất mù mờ và khù khờ, tựa như sự bế tắc trong những phút đá bù giờ emo_popo_pudency

Ý tưởng của mình là:

  1. Bắt đầu từ key = empty.
  2. Tìm ký tự tiếp theo bằng cách:
    1. Duyệt từng printable character.
    2. Thêm nó vào key từ 1 cho đến n lần, sao cho len(key) không quá giới hạn ta quy định.
    3. Xác định min_diff (diff là chênh lệch giữa giá trị tính được từ key và giá trị mà bài yêu cầu).
    4. Chọn ký tự có min_diff nhỏ nhất.
  3. Lặp đến khi tìm được key có diff = 0.

Code thử với MAX_LENGTH = 30:

Output:

Quá tuyệt vời! surrender

Với giải thuật này, gần như mọi MAX_LENGTH đều có thể tìm được key, trong đó ngắn nhất mình có là aRaV^W, còn đẹp nhất…. là http://ctf.yeuchimse.com ^_^ ((1</+1 emo_popo_haha

Connect với server để gửi key, ta sẽ nhận được flag (nhưng mình quên rồi, còn ban tổ chức thì cũng đã xóa sạch dấu vết).

Leave a Reply

Your email address will not be published. Required fields are marked *