crypto/random

451 points

Writeup by Aryan

This is the source code we are provided with.

#include<chrono>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<string>
#include<fstream>
#include<thread>
#include<map>
using namespace std;

bool amazingcustomsortingalgorithm(string s) {
    int n = s.size();
    for (int i = 0; i < 69; i++) {
        cout << s << endl;
        bool good = true;
        for (int i = 0; i < n - 1; i++)
            good &= s[i] <= s[i + 1];
        
        if (good)
            return true;

        random_shuffle(s.begin(), s.end());

        this_thread::sleep_for(chrono::milliseconds(500));
    }

    return false;
}

int main() {
    string s;
    getline(cin, s);

    map<char, int> counts;
    for (char c : s) {
        if (counts[c]) {
            cout << "no repeating letters allowed passed this machine" << endl;
            return 1;
        }
        counts[c]++;
    }

    if (s.size() < 10) {
        cout << "this machine will only process worthy strings" << endl;
        return 1;
    }

    if (s.size() == 69) {
        cout << "a very worthy string" << endl;
        cout << "i'll give you a clue'" << endl;
        cout << "just because something says it's random mean it actually is" << endl;
        return 69;
    }

    random_shuffle(s.begin(), s.end());
    
    if (amazingcustomsortingalgorithm(s)) {
        ifstream fin("flag.txt");
        string flag;
        fin >> flag;
        cout << flag << endl;
    }
    else {
        cout << "UNWORTHY USER DETECTED" << endl;
    }
}

Obviously, there's no way a random string will pass the sorting algorithm (and if it will, then you should have probably bought a lottery ticket instead of solving the challenge).

I tried using the random_shuffle function myself, and realized it isn't actually random, and specific input indices will always go to specific output indexes. Thus, we can construct a string that will be sorted when going through random_shuffle, meaning it will pass the check on the first attempt.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(void) {
    cin.tie(0)->sync_with_stdio(0);
    string s = "abcdefghij";
    random_shuffle(s.begin(), s.end());
    cout << s << endl; // will always print edhiafcbgj
    /*
        input: abcdefghij
        output: edhiafcbgj
        index mappings:
        1 -> 5, 2 -> 8
        3 -> 7, 4 -> 2
        5 -> 1, 6 -> 6
        7 -> 9, 8 -> 3
        9 -> 4, 10 -> 10
        wanted output: abcdefghij
        input (reverse the mappings): ehgbaficdj
    */
}

Flag: n00bz{5up3r_dup3r_ultr4_54f3_p455w0rd_5ce88a62ff2b}