Solution draft for the DownUnderCTF 2021 challenge "Flying Spaghetti Monster". See https://jfhr.me/down-under-ctf-2021

ductf-2021-spaghetti.cs

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