Rego Prototype Review was a challenge at NorthSec 2022 which was unlike the rest, involving just figuring out a new programming language. This programming language resembles a cocktail of Go and Prolog. It's a bit unique in that it uses logical programming, as well as Go-like assignments and Javascript object syntax. But this isn't Robert's Programming Language review, we have Fireship for that.
Challenge 1
This is a warm up challenge, designed to get you used to the language. You're told to input a JSON object akin to:
{
"flag": "<FLAG ATTEMPT>"
}
Then, Rego will run the code to eval the flag and tell you whether or not it's correct. Kinda like reverse engineering without the BS.
We have a couple things in the source of the first challenge.
package challenge1
default correct_flag = false
mycorize(s) := replace(replace(s, "o", "0"), "i", "y")
correct_flag {
words := ["champ", "mycoverse", "exo", "meta", "cyber", "block", "chain", "life"]
parts := split(input.flag, "-")
parts[1] == mycorize(words[x])
indexof(input.flag, "4") == 15
parts[3] == mycorize(words[y])
[parts[0], x, y] == ["FLAG", 1, 7]
}
Off the bat, you might be drawn to the massive cluster at the bottom. It's labeled "correct_flag" and has a couple of conditions. Rego is a logical programming language, meaning that it tries to find a way to make each condition true to the best of its ability. Therefore, some assignments can look a little strange. Either way, that entire cluster has to evaluate to true.
Within this cluster, we have an array of words called words, and we know the flag is split into parts separated by hyphens (the split() function should look familiar to anyone who's used Python for a while). We also know that parts[1] has to be the result of the mycorize() function applied to words[x]. Wait, x hasn't been specified, what?
This is where the magic of logical programming comes in. Remember how the language tries to make each condition true to the best of its ability? We see x again in that last condition:
[parts[0], x, y] == ["FLAG", 1, 7]
So parts[0], x, and y have to be "FLAG", 1, and 7 respectively. And because of the way Rego works, that's effectively an assignment, since x and y have yet to be defined. Cool!
Once you know that, the rest follows basic programming (though there is a first class function with myconize, so definitely read up on it if that looks foreign), and you get the flag.
FLAG-myc0verse-4-lyfe
Challenge 2
package challenge2
default correct_flag = false
parts = split(input.flag, "-")
flag = split(parts[1], "")
correct_flag {
parts[0] == "FLAG"
regex.match("[0-9a-f]{18}", parts[1])
check_flag
}
check_daeb6676fb {
checks = ["{2,5,f,e}", "{f,e,0}", "{7,a}", "{0,3}", "{8,3,4}", "{9,3}", "{b,6}", "{3,1}", "{7,0}", "{5,6,7,f}", "{4,d,3,b}", "{0,6}", "{5,7,d,0}", "{b,0,f}", "{0,2}", "{e,6}", "{5,4,a,3}", "{9,a,8}"]
glob.match(checks[i], [], flag[i])
}
check_6fab77bfa0 {
checks = ["{1,0}", "{0,3,5,1}", "{a,8,1,d}", "{f,b,a}", "{8,4}", "{f,2}", "{e,0,9,8}", "{8,d}", "{b,9}", "{e,6}", "{4,8}", "{c,e,a}", "{2,b,0}", "{4,3}", "{2,c,9,b}", "{e,0,6,1}", "{8,7,b,e}", "{a,2}"]
glob.match(checks[i], [], flag[i])
}
# A bunch of check functions later...
check_flag {
not check_daeb6676fb
not check_6fab77bfa0
not check_1303f08f3b
not check_1e7696120e
not check_7dfd706380
not check_428af9a07f
not check_31c7b0af16
not check_549bdbab83
not check_544db8ad08
not check_8d627e437c
not check_a1ab717ea8
not check_2a472fcb62
not check_32ad655751
not check_dd21d3c001
not check_5ef3d7283b
not check_122e25ab7a
not check_a592a1319d
not check_c657345566
not check_7c7db63c8b
not check_13feb5fbad
not check_818e5b66b1
not check_a40912a851
not check_06e9b90392
not check_6a9b5a6923
not check_88634b49bd
not check_0d9a709c04
not check_c52d9dc000
not check_4ef6d355b8
not check_564539041c
not check_736ca3e0fa
not check_a896cae94d
not check_f50c810345
}
Gah, that's long. However, looking at it, it's basically a bunch of checks that look like regex matches. So you have an array that checks for each character in the flag. Catch is, all the checks are negated. So what this is really telling you is which characters aren't in the flag. So a flag all in hex that's 18 characters without the "FLAG-" bit, checking to make sure there are no illegal characters.
Now, you could do this by manually going through and figuring out which characters are remaining, but I like my Python too much and had too little time to do that. So I used good old sets and loops!
checks0 = ["{2,5,f,e}", "{f,e,0}", "{7,a}", "{0,3}", "{8,3,4}", "{9,3}", "{b,6}", "{3,1}", "{7,0}", "{5,6,7,f}", "{4,d,3,b}", "{0,6}", "{5,7,d,0}", "{b,0,f}", "{0,2}", "{e,6}", "{5,4,a,3}", "{9,a,8}"]
checks1 = ["{1,0}", "{0,3,5,1}", "{a,8,1,d}", "{f,b,a}", "{8,4}", "{f,2}", "{e,0,9,8}", "{8,d}", "{b,9}", "{e,6}", "{4,8}", "{c,e,a}", "{2,b,0}", "{4,3}", "{2,c,9,b}", "{e,0,6,1}", "{8,7,b,e}", "{a,2}"]
checks2 = ["{8,c,5}", "{b,1,7,f}", "{9,7,c}", "{0,e}", "{3,1}", "{0,e,7,6}", "{6,5,e}", "{9,c,4,3}", "{5,f,d}", "{8,f,7}", "{1,a,f}", "{4,0}", "{8,3,9}", "{1,4}", "{a,2}", "{6,3}", "{4,f,6}", "{4,e,f}"]
checks3 = ["{0,5}", "{2,a,3}", "{8,7,e,f}", "{3,8,7,9}", "{2,6,9,7}", "{1,7}", "{d,b,a,5}", "{a,c,b}", "{a,7,1}", "{3,9,2,5}", "{8,2,7}", "{d,a,1,5}", "{8,3}", "{8,3,d}", "{0,b,9}", "{0,1}", "{b,c,1}", "{4,2}"]
...SNIP...
checks = [
checks0,
checks1,
checks2,
...SNIP...
checks30,
checks31
]
possible_chars = set([s for s in "0123456789abcdef"])
flag = "FLAG-"
for i in range(18):
illegal_chars = set()
for check_set in checks:
cleaned_check_set = check_set[i].replace("{", "").replace("}","").split(",")
for illegal_char in cleaned_check_set:
illegal_chars.add(illegal_char)
flag += possible_chars.difference(illegal_chars).pop()
print(flag)
FLAG-690c052231c2caff9b
Challenge 3
package challenge3
default correct_flag = false
parts = split(input.flag, "FLAG-")
flag = split(parts[1], "")
f(s) = sp {
c := flag[s.i]
g[s.s][0] == c
j := count({ x | array.slice(flag, 0, s.i)[x] == c })
sp := { "i": s.i + 1, "s": g[s.s][2][j] }
}
g = [["y",1,[11]],["n",1,[13]],["-",3,[12,10,9]],["h",1,[2]],["u",1,[9]],["l",1,[8]],["b",1,[13]],["t",1,[3]],["i",2,[7,4]],["m",3,[13,0,null]],["w",1,[8]],["c",2,[12,13]],["o",2,[9,1]],["e",4,[11,2,2,5]]]
hash := crypto.sha256(parts[1])
correct_flag {
g[s][0] == flag[0]
f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f({ "i": 0, "s": s })))))))))))))))))))))))).i == count(flag)
}
This one was tricky. I could have probably solved it with a Python script, but that would have been a bit too error prone for my liking.
What that mild clusterfuck of a script boils down to is that g is like a convoluted recursive linked list, with pointers to the next item in the list based on how many of each entry's letters are in the flag. If that sounded confusing, it was.
What led me to this realization was that exactly one element in the "pointer list" of an entry of g was null. What else has a null final pointer? A linked list. (Yes, there are circular linked list, but technicalities are for the other challenges.)
So here's the structure of this "linked" list:
- The list is comprised of entries. In each entry:
- A letter, which we can call the "data."
- A number, which represents the number of times the data appears in the flag
- A list, which is the list of pointers to other entries. If the data has appeared 0 times so far, use pointer at index 0. 1 time, index 1, and so on.
So we can work backwards from the final letter and figure out what would point to it, by taking the most recent pointer that points to its index, and marking down the letter associated with that pointer. It's messy, but it works.
FLAG-become-one-with-mycelium
Conclusion
Rego Prototype Review was a slightly unrealistic but fun challenge using a new programming language. I think if I hadn't learned logical programming in school before this CTF I would have been stuck for way longer, but it is an excellent introduction without the weirdness of Prolog.
Top comments (0)