Tags: misc bruteforce graphs
Rating:
A friend handed me this map and told me that it will lead me to the flag.
It is confusing me and I don't know how to read it, can you help me out?
solves: 102
# Copyright 2023 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""This file encrypts a given file using a generated, easy to remember password.
Additionally, it generates a hint in case you forgot the password.
"""
import dataclasses
import re
import secrets
import sys
from pyrage import passphrase
def get_word_list():
with open('USACONST.TXT', encoding='ISO8859') as f:
text = f.read()
return list(set(re.sub('[^a-z]', ' ', text.lower()).split()))
def generate_password(num_words):
word_list = get_word_list()
return ''.join(secrets.choice(word_list) for _ in range(num_words))
@dataclasses.dataclass
class Node:
letter: str
id: int
@dataclasses.dataclass
class Edge:
a: Node
b: Node
@dataclasses.dataclass
class Graph:
nodes: list[Node]
edges: list[Edge]
class IdGen:
def __init__(self):
self.ids = set()
def generate_id(self):
while True:
new_id = secrets.randbelow(1024**3)
if new_id not in self.ids:
self.ids.add(new_id)
return new_id
def generate_hint(password):
random = secrets.SystemRandom()
id_gen = IdGen()
graph = Graph([],[])
for letter in password:
graph.nodes.append(Node(letter, id_gen.generate_id()))
for a, b in zip(graph.nodes, graph.nodes[1:]):
graph.edges.append(Edge(a, b))
for _ in range(int(len(password)**1.3)):
a, b = random.sample(graph.nodes, 2)
graph.edges.append(Edge(a, b))
random.shuffle(graph.nodes)
random.shuffle(graph.edges)
for edge in graph.edges:
if random.random() % 2:
edge.a, edge.b = edge.b, edge.a
return graph
def write_hint(graph, out_file):
out_file.write('graph {\n')
for node in graph.nodes:
out_file.write(f' {node.id} [label={node.letter}];\n')
for edge in graph.edges:
out_file.write(f' {edge.a.id} -- {edge.b.id};\n')
out_file.write('}\n')
def encrypt(num_words, secret):
password = generate_password(num_words)
hint = generate_hint(password)
with open('hint.dot', 'w') as hint_file:
write_hint(hint, hint_file)
filename = 'secret.age'
with open(filename, 'wb') as f:
f.write(passphrase.encrypt(secret, password))
print(f'Your secret is now inside password-protected file {filename}.')
print(f'Use the password {password} to access it.')
print(
'In case you forgot the password, maybe hint.dot will help your memory.')
if __name__ == '__main__':
encrypt(num_words=int(sys.argv[1]), secret=sys.argv[2].encode('utf-8'))
In this challenge, the flag file is encrypted using a passphrase that generated from a wordlist. A hint.dot file is also provided. THe most import part is to identiy how the hint is generate. In the encrypt.py file we can see that each letter is assigned a node, and each consecutive letters are link with a directly edge. Afterward, random edges are added, the node orders are shuffled, and the edge order are randomly flipped. Since there are a lot of randomness in the hint, all we can extract from the hint are what letters are in the passphrase, and what letters can be connected. I parse the hint file and get the list of letters presented. I then treat all edges as bi-directional, and filter the words based on the following criteria.
This filters the word list down to 86 words, I then randomly generates passphrase from that wordlist that have the same word sets as the passphrase. I then permutes that word sets and test all permutations until the correct passphrase is found. See solve.py for more detail.
I think that the word set phase can potentially be change to a more efficient approach, as that problem is similar to a subset sum, not sure if there are any potential in a more efficient algorithm.
import re
import random
import secrets
from tqdm import tqdm
import string
from sage.all import *
from pyrage import passphrase
from itertools import permutations
def get_word_list():
with open('USACONST.TXT', encoding='ISO8859') as f:
text = f.read()
return list(set(re.sub('[^a-z]', ' ', text.lower()).split()))
word_list = get_word_list()
def get_valid_nodes():
with open("hint.dot") as f:
header = f.readline()
tmp = f.readline()
nodes = {}
inv_nodes = {}
edges = []
while "label" in tmp:
node_id, letter = tmp.split('[label=')
letter = letter[0]
node_id = int(node_id)
nodes[node_id] = letter
if letter in inv_nodes:
inv_nodes[letter].append(node_id)
else:
inv_nodes[letter] = [node_id]
tmp = f.readline()
while "--" in tmp:
fid, tid = tmp.split('--')
fid = int(fid)
tid = int(tid[:-2]) # ;\n
edges.append((fid, tid))
edges.append((tid, fid)) # since it's randomly flipped, treat as non directional
tmp = f.readline()
return nodes, inv_nodes, edges
nodes, inv_nodes, edges = get_valid_nodes()
def path_exist(inv_map, edge, f, t):
for fr in inv_map[f]:
for dst in inv_map[t]:
if (fr, dst) in edge:
return True
# print(f, t)
return False
#print(n, e)
appeared_letter = list(nodes.values())
valid_words = []
for w in word_list:
if not all(i in appeared_letter for i in w):
continue
for l in w:
if w.count(l) > appeared_letter.count(l):
break
else:
for s, e in zip(w, w[1:]):
if not path_exist(inv_nodes, edges, s, e):
break
else:
valid_words.append(w)
print(valid_words)
print(len(appeared_letter))
print(len(valid_words))
verify = "".join(sorted(appeared_letter)).strip()
print(verify)
print(type(verify))
password_len = len(verify)
def generate_password(num_words):
word_list = valid_words
return ''.join(secrets.choice(word_list) for _ in range(num_words))
def word2vec(word):
return [word.count(l) for l in string.ascii_lowercase]
#verify = "aacddeeeeegiiinnnoorrrsssstt"
secret = open("secret.age", "rb").read()
for words in Subsets(valid_words):
password = "".join(words)
if len(password) != password_len:
continue
s_password = "".join(sorted(password))
# print(s_password)
# print(type(s_password), type(verify))
if s_password in verify:
print(password)
print(words)
for ws in permutations(words):
password = "".join(ws)
print(password)
for s, e in zip(password, password[1:]):
if not path_exist(inv_nodes, edges, s, e):
break
else:
try:
print(passphrase.decrypt(secret, password))
print("FOUND!!!!")
exit(1)
except Exception as e:
pass
#standardwatersigngivenchosen
#b'CTF{S3vEn_bR1dg35_0f_K0eN1g5BeRg}'
