Trong lúc các đồng đội của mình đang thực hiện thao tác trên các hệ thống nội bộ, Võ bằng kinh nghiệm truy vết của mình tìm ra 1 dịch vụ lạ trên một máy chủ đặt tại nhà riêng của Snowden. Tuy nhiên dịch vụ được bảo vệ bởi một số đoạn mã với yêu cầu vô cùng phức tạp mà chỉ có Anonymous mới nắm giữ bí quyết khởi tạo. Công việc tưởng bất khả thi nhưng chưa đầy 1 nốt nhạc sau, Võ đã nắm trong tay kết quả…
Challenge: nc 138.91.39.179 45456

Không đội nào giải được? Ok, đây là lúc để mình tỏa sáng

Nội dung chính

Kết nối đến server, ta nhận được lời chào:

    Prove that you are one of us! This is the new algorithm we have developed for our VenaSploit tool
We give you a set of character, you need to give me back a long enough string such that every 4 consecutive bytes is unique
All characters in the charset should be included for it to be valid. A charset is given between the tag <pre>
Example: <pre>01</pre> length: 8 , Answer: 00010111

Charset: <pre>01</pre>
Give me a pattern of size at least 16 using the given charset:

Như vậy, nhiệm vụ của chúng ta là tìm một chuỗi có kích thước n, được tạo bởi một tập các ký tự cho trước, với điều kiện là 4 ký tự bất kỳ liền kề không được trùng nhau (mình gọi là tính chất UEY). Ví dụ chuỗi:

0001110001100

là không hợp lệ, do 1100 xuất hiện 2 lần. Còn một điều kiện nữa là tất cả các ký tự trong charset đều phải được dùng, tuy nhiên điều này không mấy quan trọng.

Thuật toán

Kể từ ngày tham gia một cuộc thi chính thức đầu tiên (DEFCON thì phải) và giải được 2 bài thuộc thể loại coding tương tự, mình đã hiểu rằng mình sẽ yêu nó. Ít nhất thì đến bây giờ, mình vẫn còn cảm thấy hứng thú và bình yên với cái thể loại nhí nhảnh và nhộn nhịp này

Bắt đầu từ thử thách thứ nhất, tạo chuỗi dài 16 ký tự, charset là 01. Ta thấy kích thước charset là 2, và 2^4 = 16 (4 chính là kích thước nhóm ký tự không lặp lại). Người thì bảo là trùng hợp, nhưng mình thì, cũng nghĩ thế

Lúc đầu, mình cho rằng bài này cần đến thuật toán quay lui, nhưng sau đó, mình không chứng minh, nhưng đoán rằng có thể chứng minh được, là tại mỗi bước, luôn tìm được ký tự tiếp theo để chuỗi mới vẫn là chuỗi hợp lệ (thỏa mãn tính chất UEY). Lý do thì rất đơn giản: mình đã thử, và hình như đã thành công.

Nhưng như vậy vẫn là chưa đủ, điều quan trọng nằm ở việc tối ưu code, nhất là việc kiểm tra tính hợp lệ của chuỗi mới sau mỗi bước. Ok, việc chạy một vòng lặp đi suốt chiều dài chuỗi vài nghìn ký tự tốn không đáng là bao nhiêu công sức, tuy nhiên nếu tưởng tượng rằng cái công sức đó bị nhân lên vài nghìn lần, mọi thứ sẽ khác. Thêm nữa, mỗi khi thêm mới một ký tự, tại sao chúng ta lại phải kiểm tra lại cái phần đã được kiểm tra trước đó? Máy yếu thực sự không thích điều này

Giải pháp mình đưa ra sau vài tiếng đứng chôn chân trên xe bus, đó là lên danh sách sẵn các pattern (nhóm 4 ký tự), gọi là available_patterns dựa trên charset bài cho, khởi tạo giá trị 1 cho mỗi pattern (cũng chính là mỗi phần tử của mảng: key => value), và mỗi khi thêm một ký tự, ta kiểm tra pattern mới nhất (4 ký tự cuối của chuỗi) có nằm trong available_patterns hay không (giá trị của phần tử = 1), nếu có, ta coi ký tự vừa thêm hợp lệ (chưa được dùng), ta sẽ sử dụng nó, đồng thời gán phần tử ứng với pattern đó bằng 0; ngược lại, nếu giá trị của phần tử đã bằng 0, tức pattern đó đã được sử dụng, ta bỏ qua ký tự vừa thêm và thay bằng ký tự khác. Việc truy xuất giá trị một phần tử của mảng là nhanh vô cùng, nên ta khỏi lo bị chậm

Cơ mà một vấn đề mới lại phát sinh sau khi mình cài đặt thử, đó là đối với charset quá rộng, thì kích thước các pattern hợp lệ là rất lớn, chiếc máy nhỏ xinh của mình bị báo MemoryError ngay sau vài nốt nhạc. Hướng giải quyết là gì?

Là thôi không lập chỉ mục sẵn nữa, nhưng vẫn phải tìm cách để biết được pattern nào đã dùng rồi, pattern nào chưa. Điều này tưởng như đơn giản, nhưng hóa ra lại… đơn giản thật. Đó là với đối tượng dictionary (python), khi ta truy xuất một phần tử không có trong từ điển, exception sẽ nhảy ra (mà chắc ngôn ngữ nào cũng vậy thôi). Như thế, ta sử dụng một dictionary để lưu những pattern đã được dùng, thì khi kiểm tra, nếu có exception, tức là pattern đó chưa có trong từ điển (nghĩa là nó hợp lệ), và ngược lại. Chỉ có vậy thôi

[python]import socket
import sys

sys.setrecursionlimit(30000)
found = False
flag = ”

def gen_next_string(current_string, length, charset, used_patterns):
global found, flag
if found:
return flag

# progress
sys.stdout.write(“current length: %d / %dr” % (len(current_string), length) )
sys.stdout.flush()

for char in charset:
new_string = current_string + char
new_pattern = new_string[-4:]
try:
used_patterns[new_pattern]
except: # if new_pattern has not been used
used_patterns[new_pattern] = 1
if len(new_string) < length: next_string = gen_next_string(new_string, length, charset,used_patterns) if (next_string != None): return next_string else: found = True flag = new_string del used_patterns[new_pattern] return None def create_string(length, charset): global found, flag found = False flag = '' start_string = charset[0] * 4 used_patterns = {} used_patterns[start_string] = 1 gen_next_string(start_string, length, charset, used_patterns) print "n" HOST = '138.91.39.179' PORT = 45456 s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect((HOST, PORT)) while True: found = False flag = '' message = s.recv(1024) message += s.recv(1024) # print message try: charset = str(message.split('Charset:

‘)[1].split(‘

‘)[0])
length = int(message.split(‘Give me a pattern of size at least ‘)[1].split(‘ using the given charset: ‘)[0])
print ‘len(charset):’, len(charset), ‘, length:’, length

create_string(length,charset)
# print ‘flag:’, flag
s.send(flag + “n”)
except: # flag
print message
sys.exit(0)[/python]

Sau một thời gian chạy khá nhanh (có lâu thì cũng là do đề bài cho charset quá phức tạp và length quá dài thôi, chứ thuật toán thì generate ra flag nhanh lắm ), ta có cờ:
[sh]len(charset): 2 , length: 16
current length: 15 / 16

len(charset): 3 , length: 81
current length: 80 / 81

len(charset): 6 , length: 1296
current length: 1295 / 1296

len(charset): 8 , length: 2506
current length: 2505 / 2506

len(charset): 26 , length: 2677
current length: 2676 / 2677

len(charset): 52 , length: 3283
current length: 3282 / 3283

len(charset): 98 , length: 4239
current length: 4238 / 4239

len(charset): 103 , length: 4315
current length: 4314 / 4315

len(charset): 179 , length: 6031
current length: 6030 / 6031

len(charset): 117 , length: 5049
current length: 5048 / 5049

len(charset): 107 , length: 4867
current length: 4866 / 4867

len(charset): 157 , length: 5173
current length: 5172 / 5173

len(charset): 164 , length: 6109
current length: 6108 / 6109

len(charset): 106 , length: 4882
current length: 4881 / 4882

len(charset): 174 , length: 5765
current length: 5764 / 5765

len(charset): 102 , length: 4488
current length: 4487 / 4488

len(charset): 156 , length: 5671
current length: 5670 / 5671

len(charset): 119 , length: 4767
current length: 4766 / 4767

len(charset): 111 , length: 4736
current length: 4735 / 4736

Your Flag: SVATTT_US3_PEDA_D0NT_Y0U?[/sh]

Your Flag: SVATTT_US3_PEDA_D0NT_Y0U?