Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Solution draft for the DownUnderCTF 2021 challenge "Flying Spaghetti Monster". See https://jfhr.me/down-under-ctf-2021
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Net.Sockets;
using System.Numerics;
using System.Text;
namespace ConsoleApp1
{
record FsmItem(int From, int To, char Char, BigInteger Mult, BigInteger Add);
record FsmQuery(int State, BigInteger Mult, BigInteger Add);
public class Program
{
static List<FsmItem> _fsm = new();
static void Main()
{
ParseFsm();
var buffer = new byte[1024 * 256];
var socket = new Socket(SocketType.Stream, ProtocolType.Tcp);
socket.Connect("pwn-2021.duc.tf", 31915);
while (true)
{
var bytesRead = socket.Receive(buffer, SocketFlags.None);
if (bytesRead == 0)
{
break;
}
var question = Encoding.UTF8.GetString(buffer[..bytesRead]);
question = question.Trim();
Console.Error.WriteLine(">>> " + question);
string answer = question.Contains("proof-of-work") ? GetAnswerManually(question) : GetAnswer(question);
if (answer == null)
{
continue;
}
answer = EnsureNewline(answer);
Console.Error.WriteLine("<<< " + answer);
var bytesWritten = Encoding.UTF8.GetBytes(answer, buffer);
socket.Send(buffer[..bytesWritten], SocketFlags.None);
}
}
private static string EnsureNewline(string message)
{
if (!message.EndsWith("\n"))
{
return message + "\n";
}
return message;
}
public static string GetAnswer(string question)
{
var parts = SplitQuestion(question);
if (parts == null)
{
return null;
}
var query = new FsmQuery(
int.Parse(parts[2]),
BigInteger.Parse(parts[0]),
BigInteger.Parse(parts[1])
);
var sb = new StringBuilder();
Search(query, sb);
return ToReverseString(sb);
}
private static string ToReverseString(StringBuilder sb)
{
var charArray = new char[sb.Length];
for (int i = 0; i < sb.Length; i++)
{
charArray[i] = sb[sb.Length - 1 - i];
}
return new string(charArray);
}
private static string[] SplitQuestion(string question)
{
foreach (var line in question.Split('\n'))
{
var parts = line.Split(new[] { "*x + ", " -> " }, StringSplitOptions.TrimEntries);
if (parts.Length == 3)
{
return parts;
}
}
return null;
}
// For the initial pow question
private static string GetAnswerManually(string question)
{
Console.WriteLine(question);
Console.Write("$ ");
string input = Console.ReadLine();
return input?.Trim();
}
public static void ParseFsm()
{
var fsmRaw = File.ReadAllLines("fsm.txt");
foreach (var line in fsmRaw)
{
var parts = line.Split(new[] { "->", "\t", "*x + ", "*x" }, StringSplitOptions.TrimEntries);
_fsm.Add(new FsmItem(
int.Parse(parts[0]),
int.Parse(parts[1]),
(char)int.Parse(parts[2]),
BigInteger.Parse(parts[3]),
parts[4] == "" ? 0 : BigInteger.Parse(parts[4])
));
}
Debug.Assert(_fsm.Count == 10000);
}
static bool Search(FsmQuery query, StringBuilder result)
{
foreach (var fsmItem in _fsm)
{
if (fsmItem.To == query.State && (query.Mult % fsmItem.Mult).IsZero &&
((query.Add - fsmItem.Add) % fsmItem.Mult).IsZero)
{
result!.Append(fsmItem.Char);
if (query.Mult == fsmItem.Mult && query.Add == fsmItem.Add)
{
// We found a solution!
return true;
}
var newQuery = new FsmQuery(
fsmItem.From,
query.Mult / fsmItem.Mult,
(query.Add - fsmItem.Add) / fsmItem.Mult
);
if (Search(newQuery, result))
{
return true;
}
}
}
return false;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment