TQLCTF-Wordle题目出自当下火热的填字游戏
填字游戏的规则为输入五个字母，然后分别返回五个颜色
- 绿色：位置和字母均正确
- 黄色：字母正确位置不正确
- 灰色：字母和位置均不正确
我们的任务就是用最少的次数，把答案找出来
在该题目中，颜色可以通过字节流分辨出来。在这之前，我在B站大学看到过一个讲述相关技术的视频，于是我就翻了下。
利用信息论解决Wordle问题
理论存在，实践开始
于是，又写了一个10K的代码，发现自己的代码只能做到平均4.3左右。
好废物啊我
于是上Github找轮子Wordle-solver
这个开源项目能做到平均3.4，然后就有了如下10K代码
import os
import re
import pwn
import time
import string
import random
import argparse
from collections.abc import Sequence, Mapping, Iterable
from typing import Optional
from array import array
ALL_LETTERS = 'abcdefghijklmnopqrstuvwxyz'
GREEN = '\x1b[42m \x1b[0m'
YELLOW = '\x1b[43m \x1b[0m'
WHITE = '\x1b[47m \x1b[0m'
class WordleSolver:
def __init__(self, wordlen: int = 5, dictfile_solutions: str = './valid_words.txt', dictfile_guesses: Optional[str] = './allowed_guesses.txt', allow_dup_letters: bool = True, hard_mode: bool = False, const_first_guess: Optional[str] = 'crane'):
self.wordlen = wordlen
self.hard_mode = hard_mode
self.all_solution_words = self._load_words(dictfile_solutions, allow_dup_letters)
if dictfile_guesses == None:
self.all_guess_words = self.all_solution_words.copy()
else:
self.all_guess_words = self._load_words(dictfile_guesses, allow_dup_letters)
self._fast_word_result_buf = array('b', [ 0 for i in range(256) ])
self.const_first_guess = const_first_guess
self.reset()
def _load_words(self, dictfile: str, allow_dup_letters: bool) -> None:
with open(dictfile, 'r') as f:
all_words = [ line.lower().strip() for line in f if re.fullmatch(r'[a-z]+', line.strip()) ]
all_words = [ word for word in all_words if len(word) == self.wordlen ]
all_words = list(set(all_words))
def has_dup_letters(word):
letterset = set()
for l in word:
if l in letterset:
return True
letterset.add(l)
return False
if not allow_dup_letters:
all_words = [ word for word in all_words if not has_dup_letters(word) ]
return all_words
def _get_letter_counts(word: str, all_letters: bool = False) -> dict[str, int]:
r = { l : 0 for l in ALL_LETTERS } if all_letters else {}
for l in word:
r[l] = r.get(l, 0) + 1
return r
def _get_letter_count_ranges_of_words(words: Sequence[str]) -> dict[str, tuple[int, int]]:
r = {}
for word in words:
for letter, count in WordleSolver._get_letter_counts(word, True).items():
if letter in r:
c = r[letter]
if count < c[0]:
c = (count, c[1])
if count > c[1]:
c = (c[0], count)
r[letter] = c
else:
r[letter] = (count, count)
for letter in ALL_LETTERS:
if letter not in r:
r[letter] = (0, 0)
return r
def reset(self) -> None:
self.positions = []
for i in range(self.wordlen):
self.positions.append(set(ALL_LETTERS))
self.letter_counts = WordleSolver._get_letter_count_ranges_of_words(self.all_solution_words)
self.tried_words = set()
self.tried_word_list = []
self.potential_solutions = set(self.all_solution_words)
self.solved = False
self.first_word_queue = [ self.const_first_guess ] if self.const_first_guess and self.const_first_guess in self.all_guess_words else []
self.potential_guesses = set(self.all_guess_words)
def _fast_word_result(self, guess: str, target: str):
retval = 0
target_lcounts = self._fast_word_result_buf
for i in range(self.wordlen):
target_lcounts[ord(target[i])] += 1
placeval = 1
for i in range(self.wordlen):
if guess[i] == target[i]:
retval += placeval * 2
target_lcounts[ord(target[i])] -= 1
placeval *= 3
placeval = 1
for i in range(self.wordlen):
g = guess[i]
t = target[i]
ordg = ord(g)
if g != t and target_lcounts[ordg] > 0:
retval += placeval
target_lcounts[ordg] -= 1
placeval *= 3
for i in range(self.wordlen):
target_lcounts[ord(target[i])] = 0
return retval
def update(self, guessed_word: str, result: str) -> None:
assert(len(guessed_word) == self.wordlen)
assert(len(result) == self.wordlen)
assert(re.fullmatch(r'[CLX]+', result))
guess_lcounts = WordleSolver._get_letter_counts(guessed_word, True)
result_lcounts = { l : 0 for l in ALL_LETTERS }
for letter, rchar in zip(guessed_word, result):
if rchar == 'C' or rchar == 'L':
result_lcounts[letter] += 1
for letter in guess_lcounts:
gc = guess_lcounts[letter]
rc = result_lcounts[letter]
crange = self.letter_counts[letter]
assert(gc >= rc)
if gc > rc:
crange = (rc, rc)
else:
crange = (rc, crange[1])
self.letter_counts[letter] = crange
for i, (letter, rchar) in enumerate(zip(guessed_word, result)):
if rchar == 'C':
self.positions[i] = set([ letter ])
else:
self.positions[i].discard(letter)
lbound_sum = sum(( lbound for lbound, ubound in self.letter_counts.values() ))
if lbound_sum >= self.wordlen:
self.letter_counts = { letter : ( lbound, lbound ) for letter, (lbound, ubound) in self.letter_counts.items() }
for letter, (lbound, ubound) in self.letter_counts.items():
nexclusive = sum(( 1 if letter in lset and len(lset) == 1 else 0 for lset in self.positions ))
if nexclusive >= ubound:
for lset in self.positions:
if not (letter in lset and len(lset) == 1):
lset.discard(letter)
self.tried_words.add(guessed_word)
self.tried_word_list.append(guessed_word)
self._filter_words_by_known_info(self.potential_solutions)
if self.hard_mode:
self._filter_words_by_known_info(self.potential_guesses)
self.letter_counts = WordleSolver._get_letter_count_ranges_of_words(list(self.potential_solutions))
if result == 'C' * self.wordlen:
self.solved = True
self.potential_solutions = set([ guessed_word ])
def _filter_words_by_known_info(self, words: set[str]) -> None:
regex_str = ''.join([
'[' + ''.join(list(letterset)) + ']'
for letterset in self.positions
])
rx = re.compile(regex_str)
def word_within_bounds(word):
lcounts = WordleSolver._get_letter_counts(word, True)
for letter, lcount in lcounts.items():
lbound, ubound = self.letter_counts[letter]
if not (lbound <= lcount <= ubound):
return False
return True
for word in list(words):
if not (rx.fullmatch(word) and word not in self.tried_words and word_within_bounds(word)):
words.discard(word)
def get_guess(self) -> str:
if len(self.first_word_queue):
return self.first_word_queue.pop(0)
if len(self.potential_solutions) == 0:
raise Exception('Answer unknown')
elif len(self.potential_solutions) <= 2:
return list(self.potential_solutions)[0]
best_word = None
best_score = -1
for word in self.potential_guesses:
solution_group_counts: dict[str, int] = {}
for potsol in self.potential_solutions:
resstr = self._fast_word_result(word, potsol)
solution_group_counts[resstr] = solution_group_counts.get(resstr, 0) + 1
avg_expected_group_size = sum(( s * s for s in solution_group_counts.values() )) / sum(( s for s in solution_group_counts.values() ))
word_score = avg_expected_group_size
if word in self.potential_solutions:
word_score -= 0.01
if word_score < best_score or best_score == -1:
best_score = word_score
best_word = word
return best_word
def get_word_result(guess: str, target: str) -> str:
r_list = [ 'X' ] * len(target)
target_lcounts = WordleSolver._get_letter_counts(target, True)
for i, (guess_letter, target_letter) in enumerate(zip(guess, target)):
if guess_letter == target_letter:
r_list[i] = 'C'
target_lcounts[target_letter] -= 1
for i, (guess_letter, target_letter) in enumerate(zip(guess, target)):
if guess_letter != target_letter and target_lcounts[guess_letter] > 0:
r_list[i] = 'L'
target_lcounts[guess_letter] -= 1
return ''.join(r_list)
def run_auto(self, target_word: str) -> int:
self.reset()
nguesses = 0
while True:
nguesses += 1
guess = self.get_guess()
if guess == target_word: break
res = WordleSolver.get_word_result(guess, target_word)
self.update(guess, res)
return nguesses
host = '47.106.102.129'
port = 43511
while(1):
nc = pwn.remote(host, port)
nc.recv()
nc.sendline('2')
print(nc.recvline())
i=0
while(i<512):
solver = WordleSolver()
while True:
guess = solver.get_guess()
print(guess)
nc.sendline(guess)
tmp=nc.recvline()
tmp=tmp.replace(GREEN.encode(),"C".encode())
tmp=tmp.replace(YELLOW.encode(),"L".encode())
tmp=tmp.replace(WHITE.encode(),"X".encode())
tmp=tmp.replace("Correct!".encode(),"".encode())
tmp=tmp.replace("Wrong!".encode(),"".encode())
tmp=tmp.replace(" ".encode(),"".encode())
tmp=tmp.replace("\n".encode(),"".encode())
tmp=tmp.replace(">".encode(),"".encode())
print(tmp)
res = tmp.decode()
if(res=="CCCCC"):
print(nc.recvline())
break
if re.fullmatch(r'[a-z]{' + str(solver.wordlen) + '} [CXL]{' + str(solver.wordlen) + '}', res):
parts = res.split(' ')
nc.sendline(parts[0])
solver.update(parts[0], parts[1])
else:
solver.update(guess, res)
i=i+1
nc.interactive()
nc.close()这个代码能够稳定1难度和概率2（30%）难度，以及基本上没可能3难度
于是只能得到一个残缺的Flag以及出题人的嘲笑
1得到的嘲笑：UWNYZ1c5dzR3UWQ9dj9oY3Rhdy9tb2MuZWJ1dHVveS53d3cvLzpzcHR0aA==
2得到的残缺的Flag:F7_7__S324rsT3_T}L3_CUt1R~s_tn@WITO_eCbQ{rRh1lty1EDlF5
在比赛结束后，有疑似非预期解
Python-random-module-cracker
通过Round ID的随机数反推答案，也真有一手的
2022/2/22：
正解WP节选如下，代码就不展示了
从这⾥可以看出，randrange 实际上就是在调⽤ getrandbits(32)，所以这⾥就可以套⽤Python random module cracker 来预测答案！
总结⼀下：
通过两轮 Easy Mode 获得前 624 道题的答案，结合 ID 反推 getrandbits(32) 的值并丢进 random-cracker 获得预测随机数的能⼒
注意到 40902^{20} 离 2^{32} 还有⼀定的差距，结合代码可知如果 getrandbits(32) ⼤于 40602^{20}，则该数将会被丢弃导致预测随机数失败。经过计算可知，成功率为 \left(\frac{4090} {4096}\right)^{624}=0.4006237250 ，⼗分可观。
exp: https://github.com/Konano/CTF-challenges/blob/master/wordle/exp.py
顺便还埋了⼀些彩蛋：
- Easy Mode 通关后会获得「NULL」 Normal Mode 通关后会获得 「UWNYZ1c5dzR3UWQ9dj9oY3Rhdy9tb2MuZWJ1dHVveS53d3cvLzpzcHR0aA==」
- Hard Mode 通关后会获得经过 random.shuffle 后的 flag
- Insane Mode 通关后会获得完整的 flag
