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

1. The letters in the word can be found in the passphrase
2. There are edges between any two consecutive letter pairs

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}'

```

[link to blog](https://bronson113.github.io/2023/06/26/googlectf-2023-writeup.html#npc)

Original writeup (https://bronson113.github.io/2023/06/26/googlectf-2023-writeup.html#npc).