{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# WIFI (id: wifi) -- 200 Points\n\n### Scenario\n\nYou really need to check your email, unfortunately you don't know the password.  Fortunately, someone wrote it down.  Unfortunately, it's written down on a low-dimensional manifold embedded in a very high-dimensional space.  Check out the `wifi/Embedded characters.npz` file -- a list of tokens is given in the `tokens` key with their corresponding embeddings in the same order under the `embeddings` key -- and recover the password.\n\n### Objective\n\nThe password is your flag, like all others, it has the format `FLAG{something}`","metadata":{}},{"cell_type":"code","source":"# We're just importing some stuff to make sure the challenges and helper code works.\n# Feel free to import anything else you need (or solve in a different language), but if you overwrite these, provided code may not work.\n\nimport pandas as pd\nimport numpy as np\nimport os\nimport requests\nfrom IPython.display import Image as Ima\nfrom IPython.display import clear_output, display\nfrom PIL import Image as Im\nfrom torch.utils.data import Dataset, DataLoader\nimport torch\nimport joblib\nimport matplotlib.pyplot as plt\nimport json\nimport base64\nimport shutil\nimport warnings\nwarnings.filterwarnings(\"ignore\")\n\n\ndir_name = \"/kaggle/input/ai-village-ctf\"\n\n# Input data files are available in the read-only \"../input/\" directory\n# You can write up to 20GB to the current directory (/kaggle/working/) that gets preserved as output when you create a version using \"Save & Run All\" \n# You can also write temporary files to /kaggle/temp/, but they won't be saved outside of the current session","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","execution":{"iopub.status.busy":"2022-09-14T06:16:26.425386Z","iopub.execute_input":"2022-09-14T06:16:26.425966Z","iopub.status.idle":"2022-09-14T06:16:27.038097Z","shell.execute_reply.started":"2022-09-14T06:16:26.425887Z","shell.execute_reply":"2022-09-14T06:16:27.036809Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# A helper function for tracking flags. You could do it yourself, but why?\n\ndef add_flag(challenge_id: str, flag: str) -> str:\n    try:\n        submission_path = \"/kaggle/working/submission.csv\"\n        template_path = f\"{dir_name}/submission.csv\"\n        if not os.path.isfile(submission_path) :\n            shutil.copyfile(template_path, submission_path)\n        flags = pd.read_csv(submission_path, index_col=\"challenge_id\")\n        valid = flags.index.to_list()\n        if challenge_id in valid:\n            flags.at[challenge_id] = flag\n            flags.to_csv(submission_path)\n            print(\"Flag saved. If you want to update the scoreboard, click 'submit' on the right. Remember that you can only update your score on the scoreboard 50 times per day\")\n        else:\n            print(\"Invalid challenge_id\")\n    except:\n        print(\"We had trouble saving that flag. Keep a copy of it and contact the CTF organizers.\")","metadata":{"execution":{"iopub.status.busy":"2022-09-14T06:16:27.039859Z","iopub.execute_input":"2022-09-14T06:16:27.040858Z","iopub.status.idle":"2022-09-14T06:16:27.048089Z","shell.execute_reply.started":"2022-09-14T06:16:27.040819Z","shell.execute_reply":"2022-09-14T06:16:27.046689Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"wifi = np.load(\"../input/ai-village-ctf/wifi/Embedded_characters.npz\")\nfor file in wifi.files:\n    print(file)\n    print(wifi[file].shape)\n    \nprint(type(wifi['tokens']))","metadata":{"execution":{"iopub.status.busy":"2022-09-14T06:16:27.049668Z","iopub.execute_input":"2022-09-14T06:16:27.050124Z","iopub.status.idle":"2022-09-14T06:16:27.071676Z","shell.execute_reply.started":"2022-09-14T06:16:27.050081Z","shell.execute_reply":"2022-09-14T06:16:27.070427Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(wifi['tokens'])","metadata":{"execution":{"iopub.status.busy":"2022-09-14T06:16:27.075878Z","iopub.execute_input":"2022-09-14T06:16:27.076875Z","iopub.status.idle":"2022-09-14T06:16:27.084411Z","shell.execute_reply.started":"2022-09-14T06:16:27.076824Z","shell.execute_reply":"2022-09-14T06:16:27.083121Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"What we know from the problem statement and by simple inspection of the input data\n* Embeddings are embedded in a high dimensional space\n* There are 188 embeddings and 188 chars in the token. 1-1 mapping between the characters and the embeddings\n\nSame characters in the token maps to different embeddings in the embedding vector. In hindsight, what is means is that the exact values of the embeddings don't matter much to arrive at the solution.\n\nWithout knowing much on how to solve this, the only thing I could do is just explore reducing the dimensions. For that I need to know how many dimensions to convert the input data. So, I used PCA with different n_components. It was apparrent that the data could be converted to two dimensions. \n\nTo visualize how all the embeddings are related, I simply did a scatter plot.","metadata":{}},{"cell_type":"code","source":"from sklearn.decomposition import PCA\nfrom sklearn.manifold import TSNE\nfrom sklearn.manifold import Isomap\nfrom sklearn.manifold import MDS\n\n\nvariances = []\nN = range(1,9)\nfor n in N:\n    pca = PCA(n_components=n)\n    pca.fit(wifi['embeddings'])\n\n    variances.append(np.sum(pca.explained_variance_ratio_))\n\nplt.plot(N, variances, 'bx-')\nplt.xlabel('n')\nplt.ylabel('variance')\nplt.title(f'Optimal n')\nplt.show()\n\npca = PCA(n_components=2)\nemb_reduced = pca.fit_transform(wifi['embeddings'])\nplt.scatter(emb_reduced[:,0], emb_reduced[:,1])","metadata":{"execution":{"iopub.status.busy":"2022-09-14T06:16:27.085998Z","iopub.execute_input":"2022-09-14T06:16:27.086359Z","iopub.status.idle":"2022-09-14T06:16:28.318538Z","shell.execute_reply.started":"2022-09-14T06:16:27.086329Z","shell.execute_reply":"2022-09-14T06:16:28.317353Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"This where I was stuck for quite some time, not knowing what to do afterwards. I kept staring at this spiral over multiple days and realized that all these points are in some order, moving away from the center(i.e the distance of all these points is increasing from the center). So, I just logged the characters corresponding to each of these embeddings sorted by the distance from the center and that's it.\n(If I had plotted this scatter plot with labels, perhaps the solution would have been apparrent easily)","metadata":{}},{"cell_type":"code","source":"list_tokens = wifi['tokens'].tolist()\ndist = np.linalg.norm(emb_reduced,axis=-1)\nflag_string = \"\"\nfor idx in np.argsort(dist):\n    flag_string += list_tokens[idx]\n    \nprint(flag_string)","metadata":{"execution":{"iopub.status.busy":"2022-09-14T06:16:28.320137Z","iopub.execute_input":"2022-09-14T06:16:28.320471Z","iopub.status.idle":"2022-09-14T06:16:28.328800Z","shell.execute_reply.started":"2022-09-14T06:16:28.320441Z","shell.execute_reply":"2022-09-14T06:16:28.327318Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Submission Helper\n\ntry:\n    r = requests.post(\"http://flags.fly.dev:5000/score\", json=json.dumps({\"challenge_id\": \"wifi\", \"submission\": \"FLAG{TURNED}\"}))\n    print(r.text)\nexcept requests.exceptions.ConnectionError:\n    print(\"Connection problems. Contact the CTF organizers.\")","metadata":{"execution":{"iopub.status.busy":"2022-09-14T06:16:45.477456Z","iopub.execute_input":"2022-09-14T06:16:45.477890Z","iopub.status.idle":"2022-09-14T06:16:45.719550Z","shell.execute_reply.started":"2022-09-14T06:16:45.477857Z","shell.execute_reply":"2022-09-14T06:16:45.718539Z"},"trusted":true},"execution_count":null,"outputs":[]}]}