The M/o/Vfuscator

Video in TIB AV-Portal: The M/o/Vfuscator

Formal Metadata

The M/o/Vfuscator
Turning 'mov' into a soul-crushing RE nightmare
Title of Series
Part Number
Number of Parts
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Release Date

Content Metadata

Subject Area
Based on a paper that proves that the "mov" instruction is Turing complete, the M/o/Vfuscator takes source code and compiles it into a program that uses *only* mov instructions - no comparisons, no jumps, no math (and definitely no SMC cheating) - turning the program into one of the most painfully difficult reverse engineering targets you will ever encounter.
State observer Group action Functional (mathematics) State of matter Multiplication sign Range (statistics) Online help Parameter (computer programming) Student's t-test Turing-Maschine Computer icon Data transmission 2 (number) Product (business) Mathematics Goodness of fit Finite set Energy level Series (mathematics) Office suite Set theory Exception handling Computer architecture Pairwise comparison Mapping Information Constructor (object-oriented programming) Projective plane Bit Machine code Symbol table Uniform resource locator Word Loop (music) Software Order (biology) Quicksort Table (information) Tuple Reverse engineering
State diagram Arithmetic mean Process (computing) Computer animation State of matter Turing-Maschine Abstraction
State observer Computer animation File format Execution unit Iteration Codierung <Programmierung> Compiler Computer architecture
State of matter Multiplication sign Equaliser (mathematics) 1 (number) Primitive (album) Mereology Turing-Maschine Neuroinformatik Mathematics Semiconductor memory Single-precision floating-point format Damping Physical system Block (periodic table) Structural load Sound effect Bit Variable (mathematics) Parsing Quicksort Freeware Arithmetic progression Speicheradresse Resultant Point (geometry) Slide rule Computer programming Real number Adaptive behavior Virtual machine Branch (computer science) Programmschleife Operator (mathematics) Energy level Address space Pairwise comparison Dependent and independent variables Forcing (mathematics) Machine code Incidence algebra Cartesian coordinate system Symbol table Compiler Loop (music) Pointer (computer programming) Logic Network topology Statement (computer science) Abstraction
Point (geometry) Slide rule Computer programming Functional (mathematics) Hoax State of matter Real number Equaliser (mathematics) Multiplication sign Branch (computer science) Element (mathematics) Programmschleife Bit rate Semiconductor memory Operator (mathematics) Selectivity (electronic) Damping Extension (kinesiology) Macro (computer science) Address space Physical system Block (periodic table) Data storage device Bound state Sound effect Bit Variable (mathematics) Subject indexing Uniform resource locator Word Pointer (computer programming) Elementary arithmetic Order (biology) Chain Statement (computer science) Self-organization Speech synthesis Right angle Quicksort Table (information) Speicheradresse
Ocean current Point (geometry) Computer programming Building Group action Hoax Multiplication sign Equaliser (mathematics) Execution unit Letterpress printing Control flow Similarity (geometry) Branch (computer science) Inequality (mathematics) Element (mathematics) Formal language Programmschleife Bit rate Semiconductor memory Internetworking Macro (computer science) Logic gate Set theory Condition number Physical system Programming language Programming paradigm Shift operator Fibonacci number Block (periodic table) Cellular automaton Bit Machine code Cartesian coordinate system Compiler Arithmetic mean Pointer (computer programming) Spring (hydrology) Loop (music) Elementary arithmetic Personal digital assistant Logic Order (biology) Figurate number Table (information) Speicheradresse Finite element method
Ocean current Point (geometry) Computer programming Building Hoax Link (knot theory) State of matter Multiplication sign Real number Equaliser (mathematics) Workstation <Musikinstrument> Source code Branch (computer science) Online help Function (mathematics) Wave packet Operator (mathematics) Operating system Damping Macro (computer science) Error message Set theory Compilation album Physical system Condition number Key (cryptography) Block (periodic table) Structural load Cellular automaton Constructor (object-oriented programming) Data storage device Bit Compiler Pointer (computer programming) Spring (hydrology) Computer animation output Right angle Musical ensemble Quicksort Table (information)
Turing test Computer programming Functional (mathematics) Group action State of matter Multiplication sign Real number Range (statistics) Branch (computer science) Coma Berenices Streaming media Neuroinformatik Revision control Semiconductor memory Core dump Flag Series (mathematics) Exception handling Computer architecture Mapping Demo (music) Structural load Projective plane Bit Machine code Complete metric space Compiler Pointer (computer programming) Process (computing) Loop (music) Computer animation Integrated development environment Order (biology) Buffer overflow Spacetime
Point (geometry) Computer programming Computer file Multiplication sign Gradient Letterpress printing Function (mathematics) Machine code Compiler Message passing Loop (music) Computer animation String (computer science) Order (biology) PRINCE2 Analytic continuation Set theory
Computer programming Pairwise comparison Presentation of a group Functional (mathematics) Letterpress printing Branch (computer science) Machine code Mereology Symbol table 2 (number) Loop (music) Computer animation Right angle Exception handling
Computer programming Complete metric space Data transmission Numerical analysis Mathematics Word Computer animation Encryption Game theory Office suite Quicksort Factorization Reverse engineering
Point (geometry) Computer programming Complex (psychology) Group action Functional (mathematics) Bit Line (geometry) Fraktalgeometrie Computer animation Tower Operator (mathematics) Order (biology) Interpreter (computing) Pattern language Game theory Contrast (vision) Control flow graph Set theory Reverse engineering
Computer programming Complex (psychology) Computer animation Block (periodic table) Multiplication sign Office suite Quicksort Machine code Reverse engineering
Computer programming Trail Group action Multiplication sign Execution unit Sheaf (mathematics) Software bug 2 (number) Differenz <Mathematik> Mathematics Different (Kate Ryan album) Semiconductor memory Operator (mathematics) Office suite Extension (kinesiology) Macro (computer science) Set theory Addition Shift operator Inheritance (object-oriented programming) Block (periodic table) Bit Machine code Price index Limit (category theory) Compiler Arithmetic mean Arithmetic logic unit Logic Order (biology) Moving average Figurate number Quicksort Table (information)
Module (mathematics) Computer programming Shift operator Multiplication Implementation Multiplication sign Cellular automaton Real number Bit Branch (computer science) Division (mathematics) Limit (category theory) Neuroinformatik Semiconductor memory Order (biology) Right angle Series (mathematics) Macro (computer science) Monster group Hydraulic jump Modulo (jargon) Set theory
Computer programming Functional (mathematics) 1 (number) Branch (computer science) Mass Mereology Revision control Intermediate language Mathematics Semiconductor memory Term (mathematics) Videoconferencing Damping Compilation album Computer architecture Pairwise comparison Standard deviation Assembly language Information Bit Machine code Complete metric space System call Compiler Computer animation Order (biology) Right angle Spacetime Library (computing)
Computer programming Presentation of a group Interior (topology) Multiplication sign Branch (computer science) Mass Formal language Neuroinformatik Twitter Revision control Causality Velocity Single-precision floating-point format Set theory Exception handling Pairwise comparison Standard deviation Scaling (geometry) Arm Demo (music) Constructor (object-oriented programming) Projective plane Feedback Binary code Bit Line (geometry) Machine code Incidence algebra System call Compiler Data mining Computer animation Right angle Table (information) Reverse engineering Library (computing)
Computer animation
the who it could be that the the who do you think you could and the over the over the I I I I a a very long range
from right that's going to get started so a good afternoon everyone thanks for being here my name's christopher Domus I want to talk to you a little bit about a project I've been working on recently that I call them office here but before we get into any technical detail the 1 to give you a little bit of background the information on this project so this whole thing started when I was bored 1 weekend I was browsing us icon already math so he invented this get help place on it's absolutely fascinating just tons and tons of Austin articles I love reading things here so check that out as soon as you can if you haven't seen it already so as browsing through something that are a matter looking for something interesting I found something that cop my i an article by a guy named Steven Dolan so both article started out with this humorous observation about the x 86 architecture and says it is well known that he x 86 instruction set is baroque over complicated and redundantly redundant we show just how much fluff has by demonstrating that remains Turing-complete when reduced to just 1 constructions of that really caught my attention right away I thought I'd been using x 86 fur for a decade and I did know 1 of these instructions in this architecture was Turing-complete by itself would 1 instruction is this stolen what magical powerful instruction is so awesome that it is Turing complete on its own it turns out it's the move instruction the simplest instruction in the entire architecture moving data from 1 place to another is apparently Turing complete so what is it mean if if movies Turing-complete sort of at a high level it means that any code that we write I could be written as a set of moves instead and absolutely nothing else just a bunch of moves in that boggled my mind at 1st about really I mean we think of all the incredibly complicated things we do with our code like arithmetic in comparisons and Johnson function called an exception handling didn't tell me that move can do all of these things on its own on that seems impossible but if movies turning complete and that's the way it is so the more I thought about that the cooler it seems to Americana realized that'd be pretty hard to reverse engineer wouldn't it because we go from something like this where we got all these nice instructions that tell us exactly what this code is doing it as a matter of seconds I can look at this and see that were initializing of variable to 0 then we're pushing a stream out of the stack and printing out removing argument from the stack were incrementing a local variable by 1 and comparing it to a hundred and if it's not a hundred yeah repeating 100 times this whole thing in a loop so just by looking at them and mnemonics in this in a couple of seconds I can reverse engineer and understand exactly what this code is doing but movies turn complete if we rewrote this whole thing is a series of moves we go from from this word got all these nice clues into into this just a whole bunch of incomprehensible data transfers from 1 location to another lose all the clues that we use for reverse engineering software in passing like you'd be devastating for reverse-engineering efforts so that there's really cool now want to pursue a more but in order to use this idea we understand a little bit more about what a Turing machine is so if you're not familiar with this this concept a Turing machines are not at a high academic level is really just 5 tuple where you've got this finite set of states Q distinguish starting state in Q a finite set of symbols sigma in 1 of those is a blind signal and you get this transition table delta that maps on the cross product of students sigma much the cross product of Q mind they're left to right what they really gives you is a
state transition diagram a way of moving from 1 state to another and that's exactly how Dolan approached this problem in his article he designed his own little Turing machine Joe how you can move from 1 state to another using only the move instruction and through his abstract Turing machine by showing that it could work with just moved to prove that movies Turing-complete so that's really really cool
but that's really purely academic because as soon as you try to apply this concept what you're gonna
find is that this idea of this abstract state transition diagram this does a really map well to the processes that we use every day meaning that the ideas from this article although they're really fascinating I'm just aren't that useful
In practice and Dolan acknowledges this he sort of on concludes his article with tongue-in-cheek observation he says removing all but the move instructions from future iterations of the x 86 architecture we have many advantages instruction format will be greatly simplified the expensive decode unit would become much cheaper in silicon currently used for complex functional units could be repurposed and even more cash as long as someone else implements the compiler so I was actually fascinated by his article and really amused with his approach so I read the last piece and I thought you know I'll take you want 1 I can I can implement a compiler for you channel
was accepted so I set out to
implement stolons move only compiler but it was a little bit daunting to start on this thing because like I said his ideas are so far removed from any practical application of their little bit hard to use but there were a few key ideas from the article that we can pretty quickly adapt his 1st key idea was then move can check for equality really me comparison instruction because moved into a for us and it's just this simple for example if we have 2 variables X and Y and we wanna see if these variables are equal to each other all we have to do is move 0 into the memory pointed to by X move wine into the memory pointed to by Y and then read back from the memory pointed to by X so imagine x and y are both 3 both of these are equal to each other in this is move 0 into memory address 3 move wine into memory address 3 overriding the 0 and then read that for memory address 3 lesson we wrote a memory address tree was a 1 are becomes 1 indicating that these 2 things are equal to each other now suppose anodic suppose X was to and why was 3 this is moves 0 into memory address to move 1 into memory address 3 and read back from memory address to little lesson we wrote to was 0 sorry becomes 0 indicating that these things are not equal to each other so just remove instructions we can actually check values on free quality another key idea from the ones paper that is really only 1 code pacify got is a bunch of moves in no branches everything executes all the time but don't observed that if he designs incorrectly a block of move instructions can actually you're have an effect on the system state or have no effect on the system state all depending on the initial state of the system so will show little bit more of how we can use that later on those western machine apart a single jump instruction to loop back to the beginning of his program that sounds kind of like it's cheating if a kind of prove that movies turned completely can start tossing in jump instructions but we show later that this kind of incident so we can actually get away from this jump instruction but a useful starting point for a design and what they look like it would have a whole bunch of move instructions followed by at the very end jump back to the beginning so somehow this whole thing's connects to over and over and over again in a loop it's gonna magically do computation for us if we can make this work on 1 of the key idea from his paper his Turing machine on required an invalid memory address for halting if you Madam discuss these moves executing inner loop forever we need some way to stop the progress of Boland said assume I'm Turing machine has an invalid address tried access that address the program stops us another useful idea we can adapt so that these these basic ideas values move for some useful stuff up with a little bit challenging to get started with this but I thought maybe if we can build on these primitive Turing machine operations at the wind came up with the commit adapters for some higher-level logic regressor changes during Machine hissing just works and abstract symbols of Wenatchee applied as we need something that will work on real data so will adapt for real data will start adding new operations we can gradually build up I'm operations for if else arithmetic logic jumps loops everything else are program needs to do we can add these piece by piece using move instructions and maybe if we do all those things we can actually get this a little closer to something we could use in practice so as to how it actually build up some of these operations so that 1 of the most critical ones for programming if how we build an if statement using only move instructions to want design something like this is X and Y equal to each other then assign 100 to the value x so pretty simple at this level but we gotta be catch if you wanna just use move instructions namely we have no branches going back a slide for not having great I don't have any way to skip this x equals 100 effects in wire not equal all the parser can execute all the time no matter what so the solution I came up with for this is that we can sort of force of path to operate on dummy data if we don't want to results in real
data if we do want results the l look something like this or that have a real copy of our data this is a real system state sitting in this copy of the data and we have a scratch copyrighted acephate system state just gets discarded you never really used for anything important then I have a selective basically a pointer the letters select between a real system state in the state system state In will do is will evaluate the 1st part of this is the you will see if x and y are equal to each other if they are selector with a pointer to the real data the I'm so that when we execute x equals 100 that 120 gets stored into the real copy of the system state on the other hand if X and Y are not equal to each other when a load up our selector with a pointer to the fate of the scratch system state x equals 100 is still 1 execute that 120 sport scratch state instead of the real state effectively discarding the results that some again sort implement
statements on using just move instructions and see that that look a little bit something like this uh we've got an array of 2 pointers 1 pointer points to a dummy data 1 point 0 points to the real data out there we use or a quality check to select either between the real point where the fate pointer we dereference that point on we assign 100 to whatever points to so without any actual branches we just effectively implemented this if statements are using this pointer selection method so it's something that would look something a little bit more like this would have a real copy of both over variables in a fake copy of both of our variables now had the selection arrays so let us choose between a real copy I'm in the fake copy and move instructions themselves to implement that statement wanna look like this at 1st were just going to do the quality check that we already talked about to determine if X and Y are equal to each other is so here it set 1 thing if not it could set to something else than we use dx is an index into a pointer selection table to select a pointer heater to the real data or to the fake data can be dereferenced up wherein store 102 whatever points to effectively storing 102 X if X and Y were equal strong data if they want so I'm really we can implement any if statement then just by adding the selector functions which are really just gonna raise to all of our variables to switch back and forth between real and fake data after being closed its you might notice that there's a little bit of a problem with the equality I showed were sort of reading these variable X and trying to assign 0 into whatever on memory address that is you can't really write any arbitrary memory addresses been a good way to say fault so we get around this if we limit ourselves to bite-size data industry a scratch to 56 element array for this equality check so this get the details of that for brevity but you really curious as to how we get around the state for issue with these a quality checks you can check out the slides later so
that we've got a way do it statement will get the on with a few simple extensions is not too hard to imagine how do if-else statements the if else if all statements or any quality checks overall pretty easy extensions to our basic if statement thing if we to write all this in just moves this can get really really tedious in a hurry so we build up some simple assembly macros on using Nazim syntax macros are so that we can have some high-level functionality that's going to expand to move so this is a macro for checking to values for quality using only move instructions for checking 2 values for any quality on this the macro for setting up the selector race to check the select between real and fake data of bounds organ further but but what we really want beyond this it's is awaiting loops and branches but we can extend that a false idea in order to make this work so here's how we can do arbitrary branches with only move instructions on essentially every time we have a conditional jump that we wanna performed were gonna check should that bridge the taken if a children's store the address that we're trying to branch to we knew there was a move instruction Minturn execution off unless it turn execution off I mean simply switch all your pointers over 2 dummy data so that anything that speech will not have an effect on a real system states on the other hand if the rate is not taken simply leave execution on in work on real data then on each basic operation not every move instruction but each primitive operation you're trying to perform in a chat is institution on effects chains on just from the operation on real data if executions off need to check should I turn execution on in other words is the current address the store branch target if it is true execution on and run the operation really that's not turn institution often and on the dummy data so it's really really complicated what's taken at 1st but it's pretty simple with an illustration so this is where a program looks like a whole bunch of moves followed by a jump back to the beginning is just the next you know let's say I want a branch from this location my program to this location my program using only move instructions such she matter that on at this location the program were going to store the target that we're trying to branch to I'm trying to branch to address 1 0 0 c so a story that somewhere at this location the program non-return execution Austin by turning it off I mean wilderness which all are pointers over 2 dummy data so that any memory right that occur don't affect the real system states I turn execution off by switching others pointers over now allow execution continues all these moves happen but there are going to be affecting dummy instead of real data each of these are basic blocks is going to check if the branch target or not they're not the branch target they just operate on the dummy data having no real effect so it's continue executions of each block checking that's the branch target of finally we hit 1 0 0 C 1 0 0 c that's the branch target so it's which is execution on in other words it's which is all the pointers over to real data is fake so that now in the subsequent moves will actually have an effect on the system state so this effectively implements branching just by switching execution on and off whenever you wanna take a branch so that a little bit further but we still have a long ways to go what do anything useful with the idea that too computationally together do arithmetic with it it actually turns out to be surprisingly easy with move instructions especially given that we've already constrained ourselves to 1 byte values so we can she do basic arithmetic was simple lookup tables on which allows you to move instructions for this so that looks something like this
that said we want to implement the increments function with move instructions only what we to make a look up table for that so this will allow us to do is if we wanna figure out what it's 3 incremented by 1 i go element 3 my look up table so this is 0 1 2 3 sigh Finite element 3 year 3 incremented by 1 is simply a value for some something like this to build up our table and something like this as our actual increment instructions really really simple 1 move instruction performs incremented simply are goes to the table looks up an element in the table reads it out in order to increment that value so I'm increment couldn't be easier with move instructions same with decrement we can build other decrement table so from a figure out what is to minus 1 good element to my table is 0 1 2 I find to decremented is 1 the
same basic thing we can build up a decrement table with assembly macros and that's our decrement instruction as as a move instead of deck so again a little bit closer on we've got some really really basic arithmetic now we still need logic gates we've never say things like and or not on stuff like that we can do that with lookup tables to so this is a little bit easier to visualize and see if let's say we want to arm figure out what is the logical and of wine in 0 without using and instruction just using lookup tables what we can do that with this with this table I go to a rate 1 in Table element 0 so that the ontological and of 1 and 0 is 0 without the logical or 0 or 1 I go to erase 0 you might want look at table element 1 to figure out logical or of those 2 values is 1 to really got these tables e to the logical or tables as assembly macros logical intervals assembly macros logical not from all expanding this simple move instructions we need a way to stop our program on a for this executing these loops er excuse moves in a continuous loop that are similar to stop this whole thing right now program loops forever unfortunately goal in figure this out for us he said assume we've got some invalid memory address among the axis it's the program stops such should sound kind of familiar it's basically just not only nor programs stops and it's a false not the cleanest way to stop it stops so what known as a convenient way to just stop our program execution so we really going to do is try to access from the null pointer in order to halt execution obviously we don't have access and all the halter program every single time you want really the issue we do that to do that was look up tables as well as a way to unconditionally look up you're real prior to real data were the No . 2 2 0 in the reference set conditions hold the system for really getting there we've got all these building blocks now as as assembly macros that extend to move instruction so I should have some high-level logic going on here we've got macros for equality inequality not in or we have ways to get real and fake data with increment decrement turn execution on and off but all the macros for some high-level logic I'm at this point if you go to another these macros on programming this way action becomes almost doable assembly but if we not the really useful I'd like to give a go beyond programming with assembly macros so C compilers a lofty goal here and so on and start with something similar so I promise the compiler for this talk of Internet she say what we be compiling so in a talk of her start off with a really really simple programming language in which some people call something else and called the spring yucky for the purpose of this talk the brain is a minimalistic esoterica programming language it's really simple it's got 8 basic instructions and only 2 registers an instruction pointer and a data point and so these are the a pretty hefty instructions were interested in bringing you can incremented decrement your data pointer you can increment or decrement the bite pointed to by the data pointer you can read a bite and you can print a bite out you can branch forward and you can range backwards so 8 really simple instructions I'm adding 1 more to allow a programs the holds so this little bit of an introduction of brain yet if you haven't seen it before this work printing out 1 2 3 4 would look like and brain you keep all your memory starts and with the zeros in bringing up the martha out 1 2 3 4 as T 1 is text 31 so we need to get 1 of our zeros up to the value 31 in order to print this out so I increments are current data cells the cell pointer by . 31 times in order to get it up to ask you 1 unit printout that 1 I am committed against heated up to 30 to print out the 2 etc. etc. print out 1 2 3 4 the common paradigm in brain you use the sole archon here is so we set the the cells to 0 in brain that's what this says is checked the current data cell if it's 0 and then branch over here if it's not 0 and decremented check again if it's 0 now continue if it's not 0 branch back so all this does is it sits in a loop decrement the data so 1 by 1 until it reaches 0 so that's how we set a value to 0 in bringing the code so can I should go up some real programs in the spring of these Turing-complete meaning we can write anything and bring up the I wouldn't any other language so this is hello world in brain activity some complicated loops to get their data cells right up around the ASCII values of corner need Mr. printing things out of this prints out the capital I shifts over a data cell decrements it down to a lower case e prints out the and then it starts becoming the I F G H I J K L prints out to ALS increments it in all them and held him and old prints out the you know but they're etc. to print out the whole Hello World program we get more complicated this a Fibonacci number generator in brain the this is
99 bottles of beer on the wall in bringing out you can really program anything in this on the thing is this is even worse than the
moves ever were so wonderful we try to this to our tour design if it's this ridiculous on well with the building blocks that we've already built up the things we've already talked about it turns out that she really really easy to implement these brain yucky operations with just a move instruction which means that if I can get the cold that I want you to bring up the then I can easily converted into only move operations and going into this actually knew that there existed a pretty decent basic to bring up the compiler already so by chaining together these compilers Igarashi go from bringing error from basic into only move instructions so it's about how the brain the key to move compiler would actually work to start out by on simply using some moves to read in the current brain lucky instruction there and figure out what the instruction is using or equality macro again this equality macro expanding to a bunch of times where C is the instruction output is it employed on music increment or decrement the data pointer cetera cetera so figure out what that bring construction is this what the increment bring a construction would look like as a set of moves 1st when check if execution is on a not if execution is on in we're dealing with the increment instruction then select the real data pointer if neither of those were either of those in the falls over the scratch data for execution read in the value from the data cell into a l and entail and then use increment table to figure out what they incremented by 1 then store back into the the real data the conditions were true or the safety of these conditions were false that's sort of what or instructions are gonna look like check it this is the right instruction load up your selector with your real or fake data pointer and carry out the instruction decrements pretty much the same increment decrement the data points are are really pretty basic on halting the system's pretty easy we are source or how to do that by dereferencing the null data pointer input now put it a little bit more complicated and brain you so we start out from the same way we always did you check if this is the right instruction set of the system state accordingly on which you understand your that something that's not a move instruction at the end of the day need to ask the operating system to do this I O for me on to to actually run help with something the Council reader value and from the Council so that kind of fella cheating but it's an easy way to get started or to show how we can fix that later on but for now we're using the in instruction to do this comedies reading data in an easily move instructions for reading data in branching gets a little bit more complicated but it's still not all that bad so we're doing is taking are we on the branch instruction and is execution on and do we want a branch of all those things are true then return execution off we switch over to the state data pointers in continue execution branching backwards pretty much the same thing so we've got all these on brain yet instructions and now about ways to translate those into only move instructions and collectively at recalled the martha skater away to translate brain that you to only move instruction sort of get a really basic 1 example of using master station so that this spring at the program this a rock 13 cypher written in Common training you with a must here let's steel so let us take that code in on compiled into only move instructions so I just give the compiler them data are up 13 the safer and I had helped put a set of assembly of 4 that's safer so many years and hasn't to link this saying want you grow into a similar thing we use all dealing link this sense of funny I've got of rot 13 program and written only move instructions for mostly move instructions let's see what this looks like thank you the so there are instructions for operating cyphered itself if you got a little bigger than a than might have been harmed by other techniques I so small single instructions we've got the jump at the end I talked about that we've
got those in the eighties at all that I talked about so
fix those in a little bit with the now it from connected you computation for us which is kind a core it's just a whole lot of new instructions executed in a continuous loop doing computation I think that's that's actually kind often that this actually works but there's something that really really bothered me about this you know that in the instruction in that jump instruction at the end only violate the Turing completeness of this and I don't think it violates the spirit of the of the projects on it really bothered me that I had to non move instructions in this blue arise in this i in this program so i record bring for a while trying to come up with with how to fix the problem so that we can really only have move instructions on this I came up with a way to do it wasn't too hard era that NTT instructions so before a program starts to execute on in our environment set up we can actually get reducing the with in meiosis administered function before real program begins with up the environment to call and mapped to map standard and standard out into the process's memory space allowing us to access from the I O streams through move instruction so we can get rid of entity that way that was pretty easy that jump at the end that was a little bit more problematic we need to somehow performer John using only move instructions and then all a lot of architectures you can load instruction pointed directly with the move instruction you can't do that in 86 synthetic better get a little bit more creative so they came up with on for this was to set my series of moves to be their own exception handler then at the very end of the series of moves when a trigger very specific exception so our using the state fault exception to hold the program and find a different exceptions I decided to use the illegal and instruction exception handler to us to do this so in our stock function before program really begins executing wall calls the see action on function in order to set up our program has its own exception handler set this no differ flag allowing the exception in order to com recursively trigger exceptions so we call that is well set that up and finally the key piece all this is replacing that jump instruction with an illegal move unless a legal move I don't mean on just a move that's kind of fault only something like accessing the null pointer at you memory access violation rather than in a legal move instruction as far as I could I could think I'm of 1 legal move instruction in all of x 86 which is trying to load the code segment register with the move instruction they want load the consignor registers other ways I could try to do this this instruction does code but it's the only invalid and move instructions so replacing the jump with this invalid move instruction will cause this exception to trigger causing a program to jump back in the was my to the beginning to handle its own exception findings says when it becomes exception handler recursively we need to not overflow the stack so we know the stack pointer on every time this this loop executes so that bring which gets us to our our new version of the maps skater or we can use only move instructions but we've got a big problem if we have to write all of our code in range of the because that's way worse than just dealing with is similar to that here on this other compiler comes into play this basic to bring up the compiler allows us to write our code in basic in the feed that into the martyrs skater to come up with move only our code so to get a demo of our have that kind of thing my my work so
when I got here so I can find it Ch so I wrote this little I know basic program here 99 bottles of beer on the wall and not a whole lot to it a string and basically initialize a variable to 99 we start a loop we call our 1st set of lyrics call a 2nd set of lyrics called the 1st set again printout take 1 down pass around decremental bottles of beer repeat the lyrics and continue until we reach no more as you know a whole lot to that yeah it's 1 checked how many bottles of beer we have left to prints 1 thing if we have not a print something else if we have some near 2 same thing Prince 1 thing at the about as your left print something else at the odds and funny this is all done some at the end which you might if there's if there's time today
um but what we can do is we can use this yes basic compiler to take our basic coding translated into bring up the code so now when I open up however newly created gradient file BCR compiler just created this 15 thousand instruction bring up the program to implement 99 bottles of beer on the wall so we can do at this point is the exact and 2 are Lhasa scary in order to good build a move only version of of this of this program so mosquito just took the brain the code output assembly reuse Nazim to a
symbol that no the to link the whole thing come together now if we look at this who's gonna move only code and it really is only move instructions for the entire program we get rid of those pesky in the eighties we get rid of that jump at the end I think this will finish dumping sometime before the end of my presentation but it's the sizable aluminum of instructions we see if I would give a few more seconds the right so you can see so you can see not you there we get rid of that jump instruction it's just a legal move instruction that's been a trigger an exception part in this whole thing to re-execute forever an inner loop so we can go ahead and run this thing yes he and when we
do that nothing will happen at 1st because it's really really really slow and but it does work on it just takes a little while but so give it a 2nd we can find out how many bottles of beer last after we take 1 down 98 so but it seems impractical so this seems totally unusable in a probably a fairly unusable but I think it's really really cool and because it's not just such as the giant print stuff right it's such as printing or the lyrics that once it's actually doing on arithmetic in comparison and branches in function calls all with only the move instruction that's that's really really need that move can do everything on for us and I want to really our highlight on the fact that we can do really efficient things with only the
move instruction so here's a factorisation program on using only the move instructional fact izations none easy thing it's factoring large numbers using only data transfers of course it's
Segfault at the end to stop the program on we can find try numbers
using only move instructions so again really complicated math in arithmetic on just by moving data from from 1 place to another fact years of
complete on CSS
decryption Pfeiffer written with only move instructions on why you want that but but she could get that what else so here's a complete role playing game that I compiled and only move instructions I even pay them off the my my office data so have got a program written only move instructions I will compile other programs and so only move instructions now it's never going to finish dumping so words kill that as well so so this from the scanning we can really do anything with it move instructions and then they had sort of gonna concept prove out prevent out new that I could the this I I want to redress my original question of of this is a real in the reverse engineering technique Howard experience reverse-engineer approach this I thought was an experience
reverse-engineer what would I do if I sat down and drop something inside of and just saw thousands and thousands of move instructions and nothing else so the truthfully I thought if if I saw this I do I go find something else to do
as I reverse-engineer collecting it's but this but this doesn't look like fun to me but more realistically I think I think thinking about how would reverse engineer such a thing brings
up some interesting points so if we had written at 99 bottles of beer on the wall program in on and compiled it would look something like this for our our main routine which just calls familiar the 1st set of lyrics look like this the 2nd set of lyrics look like this if you can use any functions your 99 bottles of beer on the wall program would look like this and C so really clear concise and easy to understand and interpret control flow graph here on so ran this through uh different opposition toward you my went up with something like this a lot of obfuscation tools work by trying to add complexity making things very very complicated in order to make them difficult to reverse engineer we can have experience even this isn't really all that bad you can look at it not and figure out which nodes matter which shows don't matter which groups of nodes are performing more basic operations and you can sort of reduces the something a little bit easier to understand this problem still kind of approachable like this but in contrast this is what the stated a 99 bottles of beer on the wall program looks like it's it's line in fact this is the rot 13 safer that we saw earlier this is the Towers of Hanoi this is a Mandelbrot fractal and this is the last role playing game you may notice a pattern here and pretty much everything looks the same not only do all the instructions look the same the control flow graphs are all identical so
on also we tried actually look at this and i'd either really really doesn't like hundred thousand of instructions in a single block it crashes every single time you try to look at
anything that my office stated so it is really can
this works completely opposite of other opposition tools instead of adding complexity it sort of removes all the complexity and somehow removing complexity makes things really really hard to reverse-engineer because every single program is that will be exactly the same on top of that there's really no way to reduce this is always simplify the problem because there's no dead code here is only code that sometimes works on fake data and sometimes works on real data
but there is 1 thing you could do to try to approach this a good reverses near would eventually see that you've got the same repeated blocks of move instructions and they'll give a figure out what each block of move instruction is doing it eventually reverse-engineer the program back into the original brain at the code and I work at the brain the code instead of the hundred thousand move instructions that she pretty easy for that approach so I have enacted on this yet but it's not too hard to imagine almost the move instructions inside basic blocks are independent of 1 another it's not hard to shuffle those things around in order to make no 2 blocks look at look alike it's also easy agile instructions these blocks to add diversity the blocks are independent of each other meaning you can interleave these different move blocks you can even rearrange the different blocks effectively are making if you wanted to you could get this thing reproduce the entire program every single time you compile understand especially effective in a move world where everything looks the same already the compiler once you look like this compile again it would look like this again would like look like this on such that the lactose sift through another really going to make it awfully hard to reconstruct the original bring at the code on from these programs but
even without this of their on 1 a while when I was I was making this thing I make a mistake have a bug in my code and action at the diver the GB and start trying to decipher what was going on you know I I myself I just written is move instructions 15 seconds ago I could not understand what was going on when I tried to watch the program run because every single instruction looks exactly the same you just cannot keep track of what's going on when all you see is his move instructions so it was actually a pretty effective on my found not too hard to match some extensions to this idea it's pretty easy to imagine a substituting other instructions for moves so for example pair of X Axhausen Hadsell parenting and or pair push pop pair all those can do basically the same thing as a move us so you get an X. office data and some obfuscator if you so desire from a sort of honor roll here as having a lot of fun with this I wonder where else I could take it in early on i said that we were limiting ourselves to 1 by data was a pretty big limitation so I wondered how hard would be to actually From go beyond 1 vital how could I do 32 bit operations on with my office the code so I built a 32 bit arithmetic logic unit for doing 32 bit matter here the challenge doing 32 bit math with move instructions indicators use lookup tables like we did with 8 bit MAC unit of memory for it which you can do is cascade a whole bunch of 8 bit operations of a ripple carry fashion in order to implement 32 bit logic so these are the macros for 32 bit addition expands out to a set of moves that section not to that a whole lot of moves for 32 bit editions 32 bit subtraction is similar on the shifts get along
the more complicated for left shift as macros less shift as moves the right
should shift as macros this that expanded to
move multiplication is where things start to get pretty hairy so this is a 32 bit multiplication as a series of NASA macros which expands
to this fairly monster set of move instructions the division in module that's where it's that this is 32 bit Division modulo as NASA macros this is that expanded to the instructions of 7 thousand move instructions to implement division module but it can be done because movies trying complete so and so limitations with this approach for the arts and what we can do we can do anything I think it's pretty obvious limitations is speed the thing just runs way too slow to be useful and really if you think about how it works the reason for a horrible speed is essentially that are the way we have to implement jumps with only moves jumping switches between dummy data In real data you can imagine jumping for just a little bit if I want to jump from here down to here I switched data offer which execution off here I switch over to fake data so all these moves execute but they operate on fake data such as the bond wasted computation that's not a whole lot of wasted computation of would just a short jump forward it's a short jump backwards that cause the bigger problem from a jump from here to here at the turn execution off my entire program has to re-execute on dummy data before it can reach my short jump backward branch the problem with that is in bringing the short jumps back short jumps backward happen an awful lot so this is how again we said data to 0 in brain yucky is simply looking over the same memory cell over and over decrementing it by 1 each time so if you imagine if you had a cell set to 200 if you just want set that soda 0 your entire program has to react to 200 times in order to make that happen so that's gonna make things a really really slow and totally unusable this the highlight the fact if we check on how our and 99 bottles of
your program is doing it's still it's still churning away and my lot that's not too happy about it that the 60 bottles of beer on will get there but this is pretty time-consuming for something that should taken well under a 2nd term to run so not the fastest thing in the world not especially usable in its current state but but I sort of in this tell you have gone this far I might as well keep going so I relax you weeks ago recall Moskita at 2 . 0 which is actually a complete C compiler that will are compiled C code into only move instructions I did this by retargeting the L C C compiler that's a little C-compiler unwittingly any experience with retarded compilers they know what I was doing GCC and LV and look really really complicated else L LCC looks almost ovals that's why I think LCC for this is an interesting little experiment we needed a lot of registers just in order to do that the memory transfers the shuffle things around that reserve most of the registers for myself on unless LCC with only the assigned EDI work with effectively turning at 56 into a to register architecture had make my own calling conventionally existing ones work very well from obfuscated code built an emulated stack for only move instructions integrate my 32 bit ALU on change the way we do dummy selectors instead of having duplicate copies of all or variables and that that 1 big scratch space the program to operate on when institutions often implemented all 102 intermediate language instructions LCC needed with only move instructions in overall this actually would way more smoothly than I ever could have imagined I'm especially given that I had no idea what I was doing in fact the only bad part about this this whole thing was LCC uses GCC for a couple of pieces namely policy relies on GCC's assembler and like things in 18 syntax which I just find abhorrent so I had a right to an awful lot of assembly on looking something like that which which just felt Rosen may be measurable by the end of the day but other than dealing with 18 the syntax of this this wasn't too bad so to consequently demo via the new version of the mass skater which works on the C code the so I really just this working on pretty much last nite so and
medicinal enables program and that's a really ugly short simple version of the nobles gain in CA users and curses for for the video there for the for the graphics now we can use LCC to compile this thing so I'm asking LCC compiler using my new move at 6 back and so it'll build that of a bunch of debug information I now we can check our our program that created yeah we'll see our move only version of of nibbles others a couple of thinking happened have really really good eyes you might notice that there's 1 not move instruction in there every once in a while still as external function calls are through a jump equals instruction comparison instructions on the way to fix that I don't have been implemented yet beneath an all under the standard c libraries it started its values those 2 instructions but beyond that it's really nothing but moves on doing all of our work we
run this thing with that of version enables now running with the only move instructions unless it's actually of fairly fast this a new version of the code runs blazingly fast I'm just really surprised about but but it's it's actually the delay in here to make it come a little bit more playable but us so the new version of mosquitoes C compiler is actually produces fairly usable skated code so as far as I know I think this is the 1st single instruction C compiler and I think it's the 1st single instruction compiler for any language that actually is a real instruction not synthetic construction which is kind of cool online social minimize set of I go with this also been try to think of ideas from US data 3 . 0 a friend of mine pointed me to this presentation showing that the x 86 and then you turn complete but that lets you do let's do computation without any instructions not was 1 instruction with no instructions that's actually things to US Ambassador here right now I'm enjoying a surrogate so my goal for 2016 will be having no instructions C compiler building off of what we've already got here but we'll see how far that goes the so wrapping everything up but I really don't religion interior solution and I have spend a lot time actually trying to reverse engineer the stuff I really only made is because I thought I would fine but it turned out to be a really really fun project is really interesting to see that move can do anything we could possibly imagine something to work on all around so if you're at all interested in this and I've got a version 1 of the off data that's the brain that you to move compilers and get help now you can check that out to see how it works on it on the C compiler out as soon as I can I wanted to coat cleaned up it's really ugly embarrassing right now as does again of permission from I'm sorry to oppose that there's well like it that this is possible some will die from compass bursty the other datasets are going to do this you really need to make a crappy for you can give a presentation on in the reverse engineering technique not give people you and actually reverse-engineer so the other nite I made the simplest possible crack me I can imagine the 15 lines see program it's basically just a string compare other compiled it with the master status of just about move instructions out of the velocity try their hand at that on that's on that hub as well I think 1 has ideas of feedback on this approach I would absolutely love to discuss it honey down the conference are just signed up for Twitter by the other day I that I can actually talk to people here so it's x or EAX EAX EDX if you wanna on talk about from any of this so I've got a tiny bit of time left if there are any questions and while we're doing that we can see our how our our
bottles of beer or you're doing it so it's getting their tensile little bit faster as it gets further along telephone quite make it out to the end before before the the presentation so are there any any questions people have yeah the the 1st question is what is the typical size of our of binaries on a large scale is the answer so there's about a megabyte of lookup tables for anything no matter how simple the program and in these 2 megabytes for your your lookup tables I mean it's probably a hundred to a thousand times increase the actual program size beyond that so on larger size a concern this is not the opposition call for you yeah the yeah it that's really depressing that did not finish the bottles of beer and lower what the she was there but the question is how do we ask above recall with the move of the mass skater so for external cause there's really no way you would get well that's not true I a way to get 2 extra calls like in the standard C library will be used to call instruction from so that's basically what we have in this C compiler right now and you can do that through exception handling on the same way that I call it caused it to a jump back to the beginning of the incident the next edition to the C compiler it is a move instructions only for phone calls of this yeah so and so all at end the the that in 0 I did think about targeting arms that seemed easier so I did 1 as you that and I thought I would say if you got any more questions feel free to have down sometime about thought little bit more about this and really so that the demo didn't quite get down to 0 bottles of beer on the wall but I guess the 98 is good enough for today so thanks everyone and
uh to see