flagmaker

Solving CTF challenges often involves a lot of work, which is very unfair to lazy competitors. To even things out, we designed a self-solving challenge: Just type make flag and make yourself a coffee while the solution is computed.

Time

6 hours
Mostly for solving the turing machine rather than reversing.

Solution

TL;DR

Extract the turing machine configuration from the code.
Observe the behavior of it.
Implement a efficient version.

The task gives a Makefile which contains a lot of long function. Here's a slightly a beautified version. One of our team member (@Bookgin) tells me that we can use

$(if $(shell echo $(3) 1>&2),,)

to inspect variables.

That Makefile code is not very readable, so I reimplement each function using python. And here's a better version after cleanup. (Note: we use x to represent + and . to represent - for better visualization effect)

The code is actually simulating a turing machine, and it use the content on the tape when it halt to calculate the flag. The state graph looks like:

              .-.
              \ V
           .-> G -> (Terminate)
          /
     .-> C ---.
    /          v
-> A <=> B --> D <.
   ^     ^    / \_/
   |     |   /
   F <=> E <'

If you run the cleanup-ed script, You can see some pattern like this

          Notice this line ---.
                              V
 977 D ........xx.x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 978 D .........x.x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 979 E .......x.x.x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 980 F ......xx.x.x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 981 E ......xx.x.x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 982 F ......xxxx.x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 983 E ......xxxx.x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 984 F ......xxxxxx.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 985 E ......xxxxxx.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 986 F ......xxxxxxxx.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 987 E ......xxxxxxxx.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 988 F ......xxxxxxxxxx.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 989 E ......xxxxxxxxxx.x.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 990 F ......xxxxxxxxxxxx.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 991 E ......xxxxxxxxxxxx.x.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 992 F ......xxxxxxxxxxxxxx.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 993 E ......xxxxxxxxxxxxxx.x...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 994 F ......xxxxxxxxxxxxxxxx...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 995 E ......xxxxxxxxxxxxxxxx...x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 996 F ......xxxxxxxxxxxxxxxxx..x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 997 A ......xxxxxxxxxxxxxxxxxx.x.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 998 B ......xxxxxxxxxxxxxxxxxxxx.x.x.x.x.x.x.x.x.x.x.x.x..x.....
 999 D ......xxxxxxxxxxxxxxxxxxx..x.x.x.x.x.x.x.x.x.x.x.x..x.....
1000 E ......xxxxxxxxxxxxxxxxxxx.xx.x.x.x.x.x.x.x.x.x.x.x..x.....
1001 F ......xxxxxxxxxxxxxxxxxxxxxx.x.x.x.x.x.x.x.x.x.x.x..x.....
1002 E ......xxxxxxxxxxxxxxxxxxxxxx.x.x.x.x.x.x.x.x.x.x.x..x.....
1003 B ......xxxxxxxxxxxxxxxxxxxxxx.x.x.x.x.x.x.x.x.x.x.x..x.....
1004 D ......xxxxxxxxxxxxxxxxxxxx.x.x.x.x.x.x.x.x.x.x.x.x..x.....
1005 D ......xxxxxxxxxxxxxxxxxxxx...x.x.x.x.x.x.x.x.x.x.x..x.....
1006 E ......xxxxxxxxxxxxxxxxxxxxx..x.x.x.x.x.x.x.x.x.x.x..x.....
1007 B ......xxxxxxxxxxxxxxxxxxxxx..x.x.x.x.x.x.x.x.x.x.x..x.....
1008 D ......xxxxxxxxxxxxxxxxxx.xx..x.x.x.x.x.x.x.x.x.x.x..x.....
1009 D ......xxxxxxxxxxxxxxxxxx..x..x.x.x.x.x.x.x.x.x.x.x..x.....
1010 E ......xxxxxxxxxxxxxxxxxxx.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1011 B ......xxxxxxxxxxxxxxxxxxx.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1012 D ......xxxxxxxxxxxxxxxx.xx.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1013 D ......xxxxxxxxxxxxxxxx..x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1014 E ......xxxxxxxxxxxxxxxxx.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1015 B ......xxxxxxxxxxxxxxxxx.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1016 D ......xxxxxxxxxxxxxx.xx.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1017 D ......xxxxxxxxxxxxxx..x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1018 E ......xxxxxxxxxxxxxxx.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1019 B ......xxxxxxxxxxxxxxx.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1020 D ......xxxxxxxxxxxx.xx.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1021 D ......xxxxxxxxxxxx..x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1022 E ......xxxxxxxxxxxxx.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1023 B ......xxxxxxxxxxxxx.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1024 D ......xxxxxxxxxx.xx.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1025 D ......xxxxxxxxxx..x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1026 E ......xxxxxxxxxxx.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1027 B ......xxxxxxxxxxx.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1028 D ......xxxxxxxx.xx.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1029 D ......xxxxxxxx..x.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1030 E ......xxxxxxxxx.x.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1031 B ......xxxxxxxxx.x.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1032 D ......xxxxxx.xx.x.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1033 D ......xxxxxx..x.x.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1034 E ......xxxxxxx.x.x.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1035 B ......xxxxxxx.x.x.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1036 D ......xxxx.xx.x.x.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....
1037 D ......xxxx..x.x.x.x.x.x.x.x..x.x.x.x.x.x.x.x.x.x.x..x.....

It keeps pushing waves from left to right. EF loop will change alternating sequence .x into all xx, and state E will detect consecutive .., and push it to the right. BDDE loop will change xx prefix back to .x sequence.

When it reach the left boundary, it will add a new symbol, like this:

 601 B .....xxxxxxxxxxxxxxxxx.x.x.x.x...x..x........
 602 D .....xxxxxxxxxxxxxx.xx.x.x.x.x...x..x........
 603 D .....xxxxxxxxxxxxxx..x.x.x.x.x...x..x........
 604 E .....xxxxxxxxxxxxxxx.x.x.x.x.x...x..x........
 605 B .....xxxxxxxxxxxxxxx.x.x.x.x.x...x..x........
 606 D .....xxxxxxxxxxxx.xx.x.x.x.x.x...x..x........
 607 D .....xxxxxxxxxxxx..x.x.x.x.x.x...x..x........
 608 E .....xxxxxxxxxxxxx.x.x.x.x.x.x...x..x........
 609 B .....xxxxxxxxxxxxx.x.x.x.x.x.x...x..x........
 610 D .....xxxxxxxxxx.xx.x.x.x.x.x.x...x..x........
 611 D .....xxxxxxxxxx..x.x.x.x.x.x.x...x..x........
 612 E .....xxxxxxxxxxx.x.x.x.x.x.x.x...x..x........
 613 B .....xxxxxxxxxxx.x.x.x.x.x.x.x...x..x........
 614 D .....xxxxxxxx.xx.x.x.x.x.x.x.x...x..x........
 615 D .....xxxxxxxx..x.x.x.x.x.x.x.x...x..x........
 616 E .....xxxxxxxxx.x.x.x.x.x.x.x.x...x..x........
 617 B .....xxxxxxxxx.x.x.x.x.x.x.x.x...x..x........
 618 D .....xxxxxx.xx.x.x.x.x.x.x.x.x...x..x........
 619 D .....xxxxxx..x.x.x.x.x.x.x.x.x...x..x........
 620 E .....xxxxxxx.x.x.x.x.x.x.x.x.x...x..x........
 621 B .....xxxxxxx.x.x.x.x.x.x.x.x.x...x..x........
 622 D .....xxxx.xx.x.x.x.x.x.x.x.x.x...x..x........
 623 D .....xxxx..x.x.x.x.x.x.x.x.x.x...x..x........
 624 E .....xxxxx.x.x.x.x.x.x.x.x.x.x...x..x........
 625 B .....xxxxx.x.x.x.x.x.x.x.x.x.x...x..x........
 626 D .....xx.xx.x.x.x.x.x.x.x.x.x.x...x..x........
 627 D .....xx..x.x.x.x.x.x.x.x.x.x.x...x..x........
 628 E .....xxx.x.x.x.x.x.x.x.x.x.x.x...x..x........
 629 B .....xxx.x.x.x.x.x.x.x.x.x.x.x...x..x........
 630 D ......xx.x.x.x.x.x.x.x.x.x.x.x...x..x........
 631 D .......x.x.x.x.x.x.x.x.x.x.x.x...x..x........
 632 E .....x.x.x.x.x.x.x.x.x.x.x.x.x...x..x........
 633 F ....xx.x.x.x.x.x.x.x.x.x.x.x.x...x..x........
 634 E ....xx.x.x.x.x.x.x.x.x.x.x.x.x...x..x........
 635 F ....xxxx.x.x.x.x.x.x.x.x.x.x.x...x..x........
 636 E ....xxxx.x.x.x.x.x.x.x.x.x.x.x...x..x........
 637 F ....xxxxxx.x.x.x.x.x.x.x.x.x.x...x..x........
 638 E ....xxxxxx.x.x.x.x.x.x.x.x.x.x...x..x........
 639 F ....xxxxxxxx.x.x.x.x.x.x.x.x.x...x..x........
 640 E ....xxxxxxxx.x.x.x.x.x.x.x.x.x...x..x........
 641 F ....xxxxxxxxxx.x.x.x.x.x.x.x.x...x..x........
 642 E ....xxxxxxxxxx.x.x.x.x.x.x.x.x...x..x........
 643 F ....xxxxxxxxxxxx.x.x.x.x.x.x.x...x..x........
 644 E ....xxxxxxxxxxxx.x.x.x.x.x.x.x...x..x........
 645 F ....xxxxxxxxxxxxxx.x.x.x.x.x.x...x..x........
 646 E ....xxxxxxxxxxxxxx.x.x.x.x.x.x...x..x........

When those two lines collapsed, the behavior depends on the pattern at the end.

Here's an example.

 642 E ....xxxxxxxxxx.x.x.x.x.x.x.x.x...x..x........
 643 F ....xxxxxxxxxxxx.x.x.x.x.x.x.x...x..x........
 644 E ....xxxxxxxxxxxx.x.x.x.x.x.x.x...x..x........
 645 F ....xxxxxxxxxxxxxx.x.x.x.x.x.x...x..x........
 646 E ....xxxxxxxxxxxxxx.x.x.x.x.x.x...x..x........
 647 F ....xxxxxxxxxxxxxxxx.x.x.x.x.x...x..x........
 648 E ....xxxxxxxxxxxxxxxx.x.x.x.x.x...x..x........
 649 F ....xxxxxxxxxxxxxxxxxx.x.x.x.x...x..x........
 650 E ....xxxxxxxxxxxxxxxxxx.x.x.x.x...x..x........
 651 F ....xxxxxxxxxxxxxxxxxxxx.x.x.x...x..x........
 652 E ....xxxxxxxxxxxxxxxxxxxx.x.x.x...x..x........
 653 F ....xxxxxxxxxxxxxxxxxxxxxx.x.x...x..x........
 654 E ....xxxxxxxxxxxxxxxxxxxxxx.x.x...x..x........
 655 F ....xxxxxxxxxxxxxxxxxxxxxxxx.x...x..x........
 656 E ....xxxxxxxxxxxxxxxxxxxxxxxx.x...x..x........
 657 F ....xxxxxxxxxxxxxxxxxxxxxxxxxx...x..x........
 658 E ....xxxxxxxxxxxxxxxxxxxxxxxxxx...x..x........
 659 F ....xxxxxxxxxxxxxxxxxxxxxxxxxxx..x..x........
 660 A ....xxxxxxxxxxxxxxxxxxxxxxxxxxxx.x..x........
 661 B ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx..x........
 662 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxx...x........
 663 E ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x.x........
 664 F ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x........
 665 E ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x........
 666 F ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx........
 667 E ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx........
 668 F ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.......
 669 A ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx......
 670 B ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.....
 671 A ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.....
 672 C ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx......
 673 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x....
 674 E ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xx...
 675 B ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xx...
 676 A ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xx...
 677 C ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx..xx...
 678 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxx...
 679 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x.x...
 680 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...x...
 681 E ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx..x...
 682 B ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx..x...
 683 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xx..x...
 684 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx..x..x...
 685 E ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x..x...
 686 B ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x..x...
 687 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xx.x..x...
 688 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx..x.x..x...
 689 E ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x.x..x...
 690 B ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x.x..x...
 691 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxx.xx.x.x..x...
 692 D ....xxxxxxxxxxxxxxxxxxxxxxxxxxxx..x.x.x..x...
 693 E ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x.x.x..x...
 694 B ....xxxxxxxxxxxxxxxxxxxxxxxxxxxxx.x.x.x..x...
 695 D ....xxxxxxxxxxxxxxxxxxxxxxxxxx.xx.x.x.x..x...
 696 D ....xxxxxxxxxxxxxxxxxxxxxxxxxx..x.x.x.x..x...
 697 E ....xxxxxxxxxxxxxxxxxxxxxxxxxxx.x.x.x.x..x...
 698 B ....xxxxxxxxxxxxxxxxxxxxxxxxxxx.x.x.x.x..x...
 699 D ....xxxxxxxxxxxxxxxxxxxxxxxx.xx.x.x.x.x..x...
 700 D ....xxxxxxxxxxxxxxxxxxxxxxxx..x.x.x.x.x..x...
 701 E ....xxxxxxxxxxxxxxxxxxxxxxxxx.x.x.x.x.x..x...
 702 B ....xxxxxxxxxxxxxxxxxxxxxxxxx.x.x.x.x.x..x...
 703 D ....xxxxxxxxxxxxxxxxxxxxxx.xx.x.x.x.x.x..x...
 704 D ....xxxxxxxxxxxxxxxxxxxxxx..x.x.x.x.x.x..x...
 705 E ....xxxxxxxxxxxxxxxxxxxxxxx.x.x.x.x.x.x..x...
 706 B ....xxxxxxxxxxxxxxxxxxxxxxx.x.x.x.x.x.x..x...
 707 D ....xxxxxxxxxxxxxxxxxxxx.xx.x.x.x.x.x.x..x...
 708 D ....xxxxxxxxxxxxxxxxxxxx..x.x.x.x.x.x.x..x...

Each push has complexity O(n^2), where n is current size of tape. The size grows exponentially with complexity O((5/4)^t). It will take too much time and space to simulate it. What we need is to store current length, then we can calculate the length and position when the wave arrive left boundary using:

pos = -(length % 4)
length += length // 4

The behavior when two lines collapse doesn't depends on the length but the pattern. So we can simulate the behavior with only 12 x in the middle, get the difference of length, and add the difference back to current length.

Here's the solver, the turing machine ends with length 2537699363594175843066 and has 2537699363594175843064 x symbols on the tape.

Additional Notes

Admin says that the turing machine is Busy Beaver on this page.

And here's the un-obfuscated code from admin.