crackme – 300 Points

Solved by 174 teams.

nc 128.238.66.218 54321
crackme

File dự phòng:

• https://db.tt/Yw5prmr3

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:

[python]def calc(key):
v4 = 1337

for c in key:
if (ord(c) == 0x00 or ord(c) == 0x0a):
break;

v4 += 32 * v4 + ord(c)
v4 &= 0xFFFFFFFF

return v4[/python]

Đ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() là 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

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ờ

Ý 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:

[python]import sys

def calc(key):
v4 = 1337

for c in key:
if (ord(c) == 0x00 or ord(c) == 0x0a):
break;

v4 += 32 * v4 + ord(c)
v4 &= 0xFFFFFFFF

return abs(v4 – 0xEF2E3558)

MAX_LENGTH = 30
s = ”
while (True):
best_diff = 0xFFFFFFFF
best_char = None

for c in [chr(asc) for asc in range(32, 127)]:
min_diff = 0xFFFFFFFF
for mul in range(1, MAX_LENGTH – len(s)):
s2 = s + c * mul
diff = calc(s2)
if (diff < min_diff): min_diff = diff if (min_diff < best_diff): best_diff = min_diff best_char = c s += best_char print 'new char: %s, diff: %s, key: %s' % (best_char, best_diff, s) if (calc(s) == 0): print 'goodboy' sys.exit(0) if (len(s) == MAX_LENGTH): print 'not found, :sosad:' break [/python] Output: [sh]new char: Z, diff: 542971, key: Z new char: Z, diff: 542971, key: ZZ new char: 0, diff: 165701, key: ZZ0 new char: 0, diff: 165701, key: ZZ00 new char: 0, diff: 165701, key: ZZ000 new char: 0, diff: 165701, key: ZZ0000 new char: 0, diff: 165701, key: ZZ00000 new char: 0, diff: 165701, key: ZZ000000 new char: h, diff: 93085, key: ZZ000000h new char: h, diff: 93085, key: ZZ000000hh new char: h, diff: 93085, key: ZZ000000hhh new char: h, diff: 93085, key: ZZ000000hhhh new char: h, diff: 93085, key: ZZ000000hhhhh new char: h, diff: 93085, key: ZZ000000hhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhhhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhhhhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhhhhhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhhhhhhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhhhhhhhhhhh new char: h, diff: 93085, key: ZZ000000hhhhhhhhhhhhhhhhh new char: e, diff: 18095, key: ZZ000000hhhhhhhhhhhhhhhhhe new char: u, diff: 127, key: ZZ000000hhhhhhhhhhhhhhhhheu new char: y, diff: 9, key: ZZ000000hhhhhhhhhhhhhhhhheuy new char: p, diff: 0, key: ZZ000000hhhhhhhhhhhhhhhhheuyp goodboy[/sh] Quá tuyệt vời!

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

[sh]new char: a, diff: 17800903, key: a
new char: R, diff: 543812, key: aR
new char: a, diff: 12088, key: aRa
new char: V, diff: 265, key: aRaV
new char: ^, diff: 7, key: aRaV^
new char: W, diff: 0, key: aRaV^W
goodboy[/sh]

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).