|

 

Coresecurity.com

Advanced Software Protection Now Diego Bendersky1,2, Ariel Futoransky1, Luciano Notarfrancesco1, Carlos Sarraute1,3, and Ariel Waissbein1,3 1 Corelabs, Core Security Technologies; 2 Departamento de Computaci´on, FCEyN, Universidad de Buenos Aires (UBA), 3 Departamento de Matem´atica, FCEyN, UBA Argentina.
Abstract. We introduce a novel software-protection method, which canbe fully implemented with today's technologies, that provides traitortracing and license-enforcement functionalities, and requires no addi-tional hardware nor inter-connectivity other than those needed to ex-ecute the respective protected software.
In [1] authors introduce the secure triggers and show that it is secure,modulo the existence of an ind-cpa secure block cipher. In this work,we present a framework for license enforcement and fingerprinting ofcomputer programs in which these capabilities are coupled with securetriggers to produce a secure software protection system.
Software piracy has troubled the computer industry, producing millions ofdollars of losses, and rising numerous scientific and technical problems ofinterest in computer security (see, e.g., [2], [3], [4]). Software is hardly sold,but it is typically licensed according to policies defined by software licenseowners. Licensed software is executed within the licensed customers' com-puters and is expected to be run according to license policy. For example,the license may establish that only users from an authorized IP addresscan use it, or that it can only run on a specific computer, or establishes anexpiration date. However, the license owner does not have any technicalwarranties to enforce his policy, unless he uses a secure software protec-tion system. The need for one such system remains after a long historyof trials (see, e.g., [5], [2]).
Software protection aims at enforcing license policy through technicalmeans, sometimes profiting from special-purpose hardware devices, andbeing supported by digital rights management legislations. Fingerprint-ing is roughly defined as the act of uniquely marking and registering a build of the program allowing the license owner to trace back a copy ofthis build to its original licensee ([6]). Today, there is no agreement onhow can license enforcement and traitor tracing be implemented. It iscommonly acknowledged that given sufficient time (within human reach)and effort an attacker will crack any protection system. As a result, soft-ware protection systems attempt to discourage crackers by making thecracking job a highly difficult (e.g., time-consuming) task.
In the past, software protection solutions have tried to make (por- tions of) the software "unavailable" for inspection by its users. Assumingavailable a procedure that provides this functionality, we could constructa software protection system by making license checks in this "unavail-able mode" (because an attacker cannot thwart license checks he cannotaccess). Among other things, software protection studies how to providethis "unavailability" through code obfuscation (see, e.g., [7], [8], [9]). Ob-fuscation, in software engineering, comprises the techniques used for pre-venting software analysis methods to produce qualitative results. On theother side, reverse engineering (e.g., program comprehension; see, e.g.,[10]), is the de facto software analysis discipline.
Regrettably, Barak et alii ([11]) give a negative result on obfusca- tion in the context of computational complexity, namely that obfuscationprocedures can be defeated. More explicitly, they show that for everyprobabilistic polynomial-time Turing machine obfuscator, which receivesas input a polynomial-time Turing machine (hereafter TM) and outputsa polynomial-time TM with the same functionality but such that only itsinput/output behavior is revealed by inspection, there exists a polynomial"deobfuscator" that learns more than just the I/O behavior.
Notice that [11] gives only an existential result, and the construc- tion of deobfuscators remains an interesting problem. Moreover, manualobfuscation is still possible, and the "international obfuscated C codecontest" ([12]) is a good example of this. It seems that the notion of au-tomated TM obfuscation is too restrictive, and that a straight-forwardcomputational complexity approach to software protection will not suf-fice to give a definitive answer (whether software protection is possibleor not). Our thesis is that an hybrid approach, which combines compu-tational complexity with software engineering, can be used to analyze asoftware protection system with the necessary detail. Evidence of this canbe found in modern reverse engineering literature (e.g., [13], [14], [15]).
This work follows a new research direction integrating hardness results tothe software engineering and reverse engineering disciplines to the designof software protection systems (cf. [4], [16], [13]).
In the past two decades (‘80,‘90) countering reverse engineering was en-deavored either by encrypting the software, or by having it run on trustedenvironments or tamper-proof hardware devices. Unfortunately, typicalhardware solutions have remained useless or too expensive (see, e.g., [17],[18], [19]); the case of typical software-only solutions has remained invari-ably insecure (see, e.g., [20], [5]). These solutions either violate Kherchoff'sprinciple (e.g., rely on security by obscurity) or at least rely on hypothe-ses on debuggers or hardware devices that cannot be verified (cf. [21]).
"Computation with encrypted data" (e.g., [9]) provides an alternativeapproach, but no solution applicable to generic software has been foundyet. So it has often been possible to circumvent anti-piracy procedures byreusable methods that could be wide-spread over the Internet4.
Some novel software protection systems, such as our own, aim to dis- courage crackers by counter-attacking reverse engineering tools, for ex-ample [4] provides an obfuscation tool-set aimed at obstructing static(flow-sensitive) code analysis; [24] proposes tamper-proofing of licenseenforcement by coupling license enforcement tools with dynamically self-checking programs; [16] presents an obfuscation method that aims at re-ducing de-obfuscation to solving the acceptance problem on linear Turingmachines (which is PSPACE-complete). However, these models for secu-rity are incomplete and there remains to answer if they are secure in arealistic sense (e.g., cannot be countered by crackers). The case of theTrusted Computing Group ([25]) is different, TCG plans to provide anew generation of personal computers that, among other things, allow forDRM of content and software. This solution requires a technology thatis now unavailable, has not been inspected by the public, and it will takeyears before this solution is effectively implemented.
This work addresses two complementary goals. First, to present a semi-automated method for software protection that addresses todays' prob-lematic, and can be implemented and used within the actual technology.
It enforces license policy, in the sense that it will not run when policy isviolated, and incorporates effectively traceable fingerprints. As a secondgoal, we propose a very realistic model of security for software protectionsystems, and analyze the security of our system.
4 Crackers and hackers web-pages as [22] or [23] contain very complete lists of cracks and serial number generators for almost every licensed software.
We will assume the reader has some knowledge of software develop- ment and cryptography. An introduction to these subjects can be foundin [26] and [27].
Architecture and implementation The protection system can be applied to the source code of a C/C++program, developed for win32 or Unix platforms5 requiring no additionalhardware nor connectivity. Additionally, we introduce a traitor-tracingsystem that detects these fingerprints (e.g., if a licensee redistributes hiscopy on the internet, he can be traced by this procedure). We describeboth procedures and give implementation directions.
The protection system requires the intervention of a programmer, which need not be the original developer of the software, that we callthe developer. The protection process consists of two phases where thesource code of a program is transformed into a protected build. On thefirst (manual) phase, the developer is required to add pragma directives(directives for short) to the source code of the program that is being pro-tected —specifying the location and name of the protection transforms(e.g., for fingerprinting or obfuscation). The manual phase is performedonly once, either during or after development, and integrates to the devel-opment cycle enabling debugging and barely augmenting the developmentwork. In the second (automated) phase, the protection system transformsthe modified source code into a customized build according to both the di-rectives added and a configuration file containing a license ID and licenseconstraints.
Model and Security The threat model is defined by a developer that uses this protectionsystem to transform the source code of the program into (protected) builds.
Each build includes an ID and license constraints, and is delivered to thelicensed customer as binary code. A valid attack against our system willconsist on a sequence of analyses and transformations to a set of buildsdone with crackers' tools.
Crackers' tools are: Disassemblers and decompilers (e.g., [28]), debug- gers (e.g., [29]), auto-decryptors and auto-decompressors, and analyzers 5 The underlying method can be deduced from this paper and then be extended for protection systems on Java, Python and other programming languages —thoughthat is not the aim of this paper.
for: API access patterns, application flow, and binary layout data. Theo-retic counterparts for these tools are mainly static analysis methods (i.e.,those analyzing the code from a frozen image of a build; see, e.g., [30],[31]), such as control- and data-flow static analysis; and dynamic analysismethods (i.e., those that infer the program's properties through runninga copy; see, e.g., [32]) such as frequency spectrum and coverage conceptanalysis. We argue that by making our system invulnerable to these "the-oretic counterparts" we are in fact defending from the real attacks.
Attackers are said to succeed at cracking our protection system if they are able, either to bypass the license constraints, or to erase thefingerprints (avoiding traitor tracing) using the aforementioned tools.
The security provided by this system depends on both the program being protected and the directives inserted during protection. This ob-servation differences our method from most protection methods. More-over, we cannot assert that programs protected by our system becomeun-crackable, but aim to prove that this system helps to make crack-ers job more difficult. Our method can profit from the syntax of sourcecode implementations (e.g., flow chart, number of variables used, func-tions implementations, etcetera) and the developer's ability. We shall giveguidelines for the manual phase so that any programmer can use it.
As for the security brought by our system, first we remark that a new interpretation of the secure triggers ([1]) technique, described in Sec-tion 3.1, can be used to obfuscate programs securely (e.g., obfuscation isas secure as a block cipher is).
Second, with our system the developer gains the ability to enforce policy by binding the program's execution code with environment pa-rameters. In particular, by binding the program's execution with licenseinformation, the program will inject failures inside its own code, inevitablycrashing, if there occur discrepancies between the expected values forthese parameters and those actually assumed by them. Failures are in-jected both stealthily and dynamically, making them more difficult todetect (e.g., by static analysis algorithms).
Third, the protection system embeds fingerprints during the protec- tion process that are spread throughout the code producing customizedbuilds. No two are alike (even locally). Further, the secure triggers tech-nique referenced above will augment fingerprinting capabilities so thatcracking triggers is necessary for cracking fingerprinting.
Finally, notice that [11] does not apply to fingerprinting because our fingerprinting method does not pretend to hide fingerprints from crack-ers (as it happens with watermarking methods), but aims at replicating fingerprints throughout the complete build so they cannot be removed.
In fact, this impossibility result does not apply to license enforcementeither, since in our case environment additional information —that is in-dependent of the obfuscation process— needs to be fed for a protectedprogram to run properly. Using a suitable strategy for the manual phase(see Section 5), both fingerprinting and license enforcement capabilitieswill change dynamically during the protected program's lifetime as thedifferent branches of the program are explored. More explicitly, the ob-fuscated portions of the program will be actually encrypted with a blockcipher (e.g., AES), and the keys needed for decryption will be computedfrom environment variables and program parameters (some related to li-cense conditions) on the fly as needed. As a result, a cracker will not beable to assert whether he has completely cracked a build until he hasdecrypted every enciphered portion of code. We will argue later that thisis a difficult job, and hence so is cracking our system.
The paper continues as follows: in Section 3 we isolate the protec- tion techniques required by this system. An implementation outline isdrafted in Section 4. Strategic considerations for the manual phase followin Section 5. Section 6 includes our conclusions and discuss results.
Tools and techniques for software protection Our system performs transforms to the program following directives in-serted in the manual phase. These transforms do not change the observ-able behavior of the program. They comprise cryptographic or softwareengineering methods that we introduce here as stand-alone algorithms.
Implementation details follow in the next sections.
Obfuscation through secure triggers Secure triggers are cryptographic primitives ideally suited for solvingmalicious-host problems of mobile computing (see [1], [33], cf. [7]). Gen-erally speaking, given a predicate (i.e., a binary valued function) p :{0, 1}∗ → {true, false} and a secret procedure f , a cryptographic trig-ger is an algorithm that executes the procedure f on receiving the input xonly if p(x) = true, else it returns nothing. Secure triggers encompass al-gorithms that compute functions t(f, p) and are secure against white-boxanalysis, say, that given complete access to the algorithm that computesthe function t(f, p), it is infeasible for an attacker to recover any semanticinformation regarding the procedure f .
Every trigger's overall behavior is similar, after setup the trigger will accept inputs and launch the secret procedure only if the trigger crite-rion is verified by the input. In [1] three trigger examples: The simpletrigger will decrypt and launch the secret functionality if the input re-ceived matches a predefined value; the multi-strings trigger decrypts andlaunches if it receives a sequence of values that contains a predeterminedsubsequence, and the subset trigger decrypts and launches only when cer-tain specific bits of the input hold a predetermined value (see Appendixfor details). Browsing the code of these programs will render no key, norwhat are the triggering bits in the latter case. The hardness result ofFutoransky et alii, ibidem, states that: If there exists an ind-cpa secureblock cipher (see [27]), then no probabilistic polynomial time attacker canrecover semantic information for f when inspecting the algorithm T (f, p)in any of the three examples described above. The appendix contains adescription of these triggers and the underlying security results.
Let us now describe how is the simple trigger used in our protection system. The use of other triggers can be derived from it. Say that withinthe program's source code we isolated a procedure f . Assume that thenatural flow of the program assigns the value k to the local variable tmp.
Let E and D denote a pair of symmetric encryption and decryption prim-itives. We then use a simple trigger (p(x) = true if, and only if, x = k)by replacing the procedure for f by the algorithm on Figure 3.1, where stored: iv, E(k, iv), E(k, f ).
input: tmp.
output: S or ⊥.
compute E(tmp, iv);If E(tmp, iv) = E(k, iv) then {output D(tmp, E(k, f ))}; Fig. 1. The simple trigger E(k, f ) denotes an encryption of a compiled f . A best usage strategy andimplementation details are included in Sections 5 and 6.
We are particularly interested in software fingerprints that are robustand collusion resistant6. Our approach to fingerprinting follows common 6 A software fingerprint is robust if the it remains even after disassembly, modification and reassembly. The fingerprinting method is said collusion-resistant, if the method practices (see, e.g., [34], [35], [36]) but profits from our architecture designand the use of secure triggers. Furthermore, the secure triggers techniqueturns this difficult-to-defeat fingerprinting system into a robust scheme.
The fingerprint module in our system is probabilistic: Every protected program is customized from a different ID (used as a seed). Static finger-prints are embedded by random modifications on the syntactic structureor layout of the source code that do not modify its functionality. Aftercompilation, this random changes remain in the build. A suspected copycan be identified with the aid of our traitor tracing tool (see Section 4.2)by different statistic correlation analyses between the suspected copy andthose copies stored by the software license owner.
The cornerstone of our fingerprinting method comes from the real- ization that programmers take arbitrary decisions during development,that this variations are present in the binaries, and that this slack canbe harnessed for embedding fingerprints. Our approach is to have thedeveloper manually identify the places in the source code open to arbi-trary decisions, and then have the fingerprinting module to automaticallyrandomize decisions on compilation. For example, developers arbitrarilydecide the order in which a function accepts its arguments; with ourmethod the developer will identify the arguments that can be arbitrarilyreordered, then on each build the protection system will randomly reorderthese arguments maintaining the code's logic.
Other "permutables" include: local and global variable definitions, function definitions, struct members, class data members, class methods,enumerated types, constant arrays, object code link order, if/then/elsestatements, independent statements. As a result, a single permutationwill introduce multiple changes on several parts of the binary code. Forexample, permuting the order of global variables definitions will produce aone byte difference in the binary code on each reference to these variables.
Random generated implementations for common-use functions (e.g., manipulation of constants, multiplication of large integers, etcetera) pro-vide yet another fingerprinting channel. Say, for example, numeric con-stants can be replaced, automatically in each build, by functions evalu-ating to those same constants —with a minor performance penalty.
Software byproducts, such as intermediate or temporary files, can also be fingerprinted by methods similar to those used above aiding forensicpractices (see [37]). Candidates for byproduct fingerprinting include in-termediate or temporary files, saved documents, configuration or state remains robust even when the attacker is given a set of different fingerprinted buildsbut cannot produce a single untraceable build.
information, network traffic, and internal data structures. Fingerprintscan be embedded, e.g., as order permutations, formatting and documentlayout, and packet encapsulation.
Robustness is then achieved with no significant effort: since the marks are embedded in no particular portion of the build but distributed through-out the code. To erase these fingerprints an attacker would first need toidentify each of this random changes, then disassemble the said portionof the code and make the necessary modifications to erase this randomchanges following the code's logic (e.g., if the protection swaps a coupleof global variables, a cracker attempting to erase this mark would need toswap every appearance of this variables on the build). A more thoroughdiscussion follows in Section 6. See also e.g., [38] and [39].
Dynamic fingerprints can also be inserted in several ways. For exam- ple, easter eggs (see, e.g., [34]) that hatch with fingerprinting informationwhen accessed with special inputs can be embedded in the program andhidden through the usage of secure triggers. Say, for example, that ifsomeone inserts an entry to the program's database of a lady born on theyear 2531, then the program decrypts and executes a function displayingthe license ID on the screen.
License Enforcement We aim to make license enforcement by binding the program's (policy-conforming) execution to the values assumed for license parameters. Moreexplicitly, we establish two levels of protection. First level license checksare used to inform the licensee when the licensed program cannot beused at that moment (e.g., because it has expired). No effort is made atthis level neither to hide the location of these checks in the program norto prevent attackers from removing them7. The second level of licenseenforcement does counter cracking. Our parameter binding method con-sists in replacing certain program constants by functions that evaluate tothe expected value for these constants only when the license parametershold values conforming with license policy. The process is quite simple:During the manual phase of the protection, the developer identifies someconstants in the source code that he wants to get bound on compilation,and he also supplies the functions that return license parameters (e.g., 7 For example, if the software has an expiration date, then the protection scheme checks for the current time with a standard system call. A cracker can hook thissystem call always returning a date falling before expiration, procedure completelybreaks the first level of license enforcement.
the present time, or the host IP number). The system will automaticallymake the binding on the second phase.
We give a simplistic example for second level checks: Suppose that license policy establishes that the software expires on 31-Dec-2009. Then,the protected program will "assume" that the second (rightmost) digitof the year is a 0, and thus several appearances of the constant 0 willbe replaced by the variable "second rightmost digit of the year." If theyear 2010 is reached, and the attacker has circumvented the explicit checks(but not the parameter-binding ones) every function that replaces 0 by thevariable "second rightmost digit of the year" will evaluate to 1, injectingfaults in the program, and forcing the program to crash while failuresspread during execution. In fact, different occurrences of the constant 0will be replaced by different implementations of the function that returnsthe current time (e.g., the time of creation of temporary files and othertimestamps within reach), making it more difficult to thwart these checks.
More generally, execution and operational parameters can be used to specify license constraints such as number of records held on a database,the time of the creation of a record, the number of simultaneous users,usage time elapsed, and any machine identification parameter.
To circumvent this license enforcement method a cracker must identify every license check and swindle the application with bogus information(e.g., hooking these checks and always returning the correct values). Sincemost of these checks will be obfuscated by secure triggers, the cracker willneed to break the obfuscation scheme to remove license constraints.
We give details for implementing a system that performs the automatedphase of the protection process for C application projects (e.g., softwareapplications) under Microsoft Visual Studio for the win32 platform.
We shall require the use of different cryptographic primitives that can to be chosen by the developer: A symmetric cipher, say AES in CBCmode, a hash function, say SHA-1, and a random pool (see, e.g., [27]).
The system consists of three procedures: the crypto pre-processor pro-cedure (CPPP), the compiler, and the post-processor. Additionaly, itrequires a library including the functions underlying triggers (e.g., de-cryption and integrity checks). The CPPP is the first module executed, it receives as input a modified source code (e.g., that includes directives)and outputs a randomized source code. At startup it initializes the ran-dom pool as seeded by the configuration file (the pool's required size isproportional to the number of directives in the source code). Then, theCPPP parses the source code individualizing the portions of code markedfor transformation.
Subsequently the transforms are applied according the random pool and the marking directives. This system enables for the use of manytransforms. In the following paragraphs we give a flavor of the transformssupported by this system introducing fingerprinting, license enforcementand obfuscation transforms. We start with an example of the permutationtransform which reorders variable assignments: fingerprint begin permute; a = 5;b = 4;tmp = "hello"; fingerprint end permute; The parser will identify the three assignments between the begin and endclauses. Reordering is done by first enumerating the permutable lines andthen applying a successive swaps to the enumerated lines. Notice thatthese modifications do not change the program's functionality.
Another fingerprinting directive is prepended to if/then/else state- ments as follows: fingerprint if;if (a < 22) printf("yes"); else printf("no"); According to the next bit in the random pool this will leave the statementas it is or replace it by the equivalent statement if (!a < 22) printf("no"); else printf("yes"); The fingerprint constant(value,size[,func=value2]) directive can be used in the declaration of constants for fingerprinting and li-cense enforcement. The CPPP will replace the declaration of the constantprepended by this directive by randomly generated arithmetic expressionof size size evaluating to value8. For example, the declaration a:=2;could be replaced by a:=4 - (3*2) + 5 - 2 + 1; which evaluates to2. The optional argument is used for license enforcement, the function 8 Compiler's optimization options can be switched not to destroy these expressions, and still optimize producing a small slowdown.
func returns an operational parameter, that is assumed to take the valuevalue2 (see Section 3.3 for details).
Triggers are handled by different encryption directives. The code to be encrypted is enclosed between directives, say between simple Trig-ger begin(key) and simple Trigger end. The CPPP will identify eachtrigger occurrence and add calls to the corresponding trigger function(e.g., that of Figure 3.1 in the case of the simple trigger) including alsointegrity checks, and will create a file in its working directory which con-tains references to the blocks associated to triggers (by specifying thestarting line and ending line of each block in source code file). Whenrunning a protected program, if a function inside an encrypted block isrequired by the control flow of the program, the protected program willautomatically compute the decryption key, (implicitly) check the validityof this key, decrypts the block, checks the block's integrity against a pre-stored hash value, and finally execute it. The CPPP also configures theproject makefile (i.e., where "details for files, dependencies and rules bywhich an executable application is built" are stored in msdev) to link thepost-processor and the additional library to the project.
Then, the randomized source code computed by CPPP is compiled into a binary build with the msdev C compiler. The output of this proce-dure is an executable binary, except no blocks are encrypted. Encryptionis handled by the post-processor module.
Finally, the post-processor modifies the binary files computed by the compiler, by encrypting specified blocks as needed and completing pa-rameters used by the triggers. Explicitly, the post-processor makes twopasses on these binary files. For each block marked for encryption, it firstcomputes and stores its length in bytes and the symmetric key, and thehash value for the cleartext; then, on the second pass, it encrypts theblock and copies on the build overwriting cleartexts and inserting auxil-iary information.
Traitor tracing module The traitor tracing module detects static fingerprints using simple statis-tics methods. Let n be a positive integer chosen by the developer. Say,n = 10. For every software build that has been delivered to a licensee,the traitor-tracing module will analyze the binaries making a dictionaryof all the n byte strings appearing within this file. This dictionary is con-structed by hash tables requiring a computation time proportional to thesize of the program and the number of copies delivered.
When a suspected build is found it is parsed into n bytes strings and each string is looked up in the dictionary. Then, for each protected build,the following statistic parameters are computed: i) the number of stringsthat can be found only in the suspected copy and this build, ii) it alsocomputes the number of strings found in the suspected copy, this build,and some other delivered build; iii) the number of strings that can befound in the suspected copy and every delivered build.
Dynamic fingerprints such as easter eggs can be detected automat- ically: A single-sing-on procedure will start the program and take thenecessary steps to insert the special entries on the databases so that thehidden license ID value is displayed. More information on dynamic fin-gerprints can be found in Sections 3.2 and 6.
The developer's strategy In this section we shall describe strategies for the manual phase that willresult in a stronger protection. We remark that the security of programsprotected by our system will depend on their characteristics and on thedeveloper's job during the manual phase.
The recommended strategy will be aimed at making the fingerprint- ing robust and making license checks hard to crack. We recommend to: i)use the fingerprinting commands whenever possible, maximizing the ran-domization within protected builds; ii) replace constants in the programwith the license enforcement primitive in error-prone places of the pro-gram, so that when license fails the failures injected are hard to reproduceand will get the program to behave erratically; iii) spread license checksthrough the length of the code and within every trigger's encrypted por-tion of software; iv) maximize the number of access channels to the licenseparameters (e.g., retrieve the actual time using different functions); v) in-sert fake triggers, i.e., that are not reached by normal executions, bothallowing fingerprinting and making infeasible to the attacker the job ofdecrypting every trigger; vi) nest occurrences of triggers; vii) make thekeys used by triggers non-obvious deriving them from variables that arepermanently updated (e.g., so that these variables take the value of thekey only when it is needed).
This section servers two purposes, on the one side it describes the strengthof this protection system, on the other it complements Sections 3 and 5 giving insight on how to counter the attackers' tools. We analyze thestrength of several attack strategies against our method.
We first discuss the effectivity of our traitor tracing module. Suppose that we have recovered a pirate copy and want to identify its origin.
Initially, the developer will try to check for explicit client IDs. In casethey were removed by crackers, the traitor tracing module is run.
Attempts at "destroying" every fingerprint through code re-optimi- zation are futile for several reasons. For example, because optimizationtools will not be able to difference between low-use and fake code —beingdead-code elimination an intractable problem ([40], cf. [41]).
Frequency spectrum analysis and other kinds of dynamic analyses will not be able to difference easter-egg dynamic fingerprints from thosepieces of code that are rarely used (e.g., code that is executed only undervery particular situations). Also, since static fingerprints were provokedby arbitrary decisions (that might look meaningful inside the code) anautomatic tool may not be able to remove them all. It turns out, thattypical software solutions for re-optimization cannot be used to deletethese fingerprints (we give more details below).
Furthermore, since certain parts of the code are encrypted by trigger procedures, the attacker will need to decrypt them to find out if theycontain fingerprints and have them deleted.
As an experiment, a 1.2 M b win32 executable was marked with finger- printing directives (and no encryption directives). Twelve different buildswere compiled (using different IDs) rising the compilation time of 45 min-utes (without protection) in a couple of minutes (and less than an hourin all if triggers are used). The resulting files were analyzed using thetraitor tracing tool doing statistics with n = 10 bytes strings in a fewseconds. The size of the resulting dictionary was of 440,000 values, forthe 1,200,000 totality of strings (recall that the file is 1.2Mb long). About182,000 of the values of the dictionary were present in every build. Foreach build, the percentage of strings appearing in it and no other buildranged from 20% to 30% of the size of the dictionary —giving an excellentidentification ratio. On the other hand, an average less than 40% of theentries in each build were present on only one other build. Cut-and-pasteattacks, collusion attacks attempting to replace pieces of a build by otherbuild's pieces in order to remove fingerprints, are not likely to succeedfacing this statistics (e.g., almost half of the builds are needed to producean unmarked copy). In fact, cut-and-paste attacks fail because the mix-ing builds produces inconsistencies in the variable's assignations, and inparticular for those used by triggers' functions.
To counter license constraints the attacker has two approaches ([3]) he can either identify every function (within the protected software) execut-ing a license check and patch it, or he can identify every attribute that ischecked and patch it so the miss-match cannot be detected. In any case,attackers would need to analyze the program's code in order to identifywhat is checked or how it is checked. Notice that static analysis tools willfail since encrypted portions of code will not be readable by these tools.
Also notice that, since the different portions of the code are disclosed gradually (e.g., the program is not decrypted at once), new checks mightappear at any time (unannounced). An attacker cannot ensure he hasremoved every check unless every single portion of the code has beenanalyzed (even fake triggers).
So far we have argued that cracking is impossible, unless every trig- ger occurrence is inspected and license checks are thwarted. A method tosystematically do this would inevitably take the following steps: i) Findthe decryption algorithm entry points (e.g., searching for decryption al-gorithm's magic constants). ii) Then modify the decryption function toinclude a key-logger by adding a procedure that saves the keys used when-ever a portion of code is decrypted. iii) Trigger every block, by intensivelyusing the application exploring every possible execution path. This proce-dure will get every encrypted portion of code decrypted. Except step iii),all the others can be automated and efficiently implemented. However,following every path of a computer program is an intractable problem(e.g., as difficult as the halting problem) that grows exponentially withthe number of branches in the program.
As we noted, none of the above attacks, attempting to reveal every trigger block, is feasible. Further, a cracker will not be able to assert ifa trigger is fake unless he understands all the related code. But, that isprecisely our goal: making it necessary for a successful attack to take thetime and effort to understand the complete code of the program and thenerase the protection's fingerprints and thwart license constraints.
1. Futoransky, A., Kargieman, E., Sarraute, C., Waissbein, A.: applications for secure triggers. Submitted. (2003) 2. Devanbu, P.T., Stubblebine, S.G.: Software engineering for security: a roadmap.
In: ICSE - Future of SE Track. (2000) 227–239 3. Hachez, G., Hollander, L.D., Jalali, M., Quisquater, J.J., Vasserot, C.: Towards a practical secure framework for mobile code commerce. In: Proceedings of the ThirdInternational Information Security Workshop (ISW 2000), Wollongong, Australia.
Volume 1975 of LNCS. (2000) 164–178 4. Wang, C., Davidson, J., Hill, J., Knight, J.: Protection of software-based surviv- ability mechanisms. In: The International Conference on Dependable Systems andNetworks (DSN'01), Goteborg, Sweden (July, 2001), IEEE Press (2001) 193–205 5. van Oorschot, P.C.: Revisiting software protection (invited talk). In Boyd, C., Mao, W., eds.: Information Security, 6th International Conference, ISC 2003, Bristol,UK, October 1-3, 2003, Proceedings. Volume 2851 of LNCS. (2003) 1–13 6. Chor, B., Fiat, A., Naor, M.: Tracing traitors. In Desmedt, Y., ed.: Advances in Cryptology — CRYPTO '94, Proceedings,. Volume 839 of LNCS., Santa Barbara,CA, USA, Springer-Verlag (1994) 257–270 7. Hohl, F.: Time limited blackbox security: Protecting mobile agents from malicious hosts. In Vigna, G., ed.: Mobile Agents and Security. Volume 1419 of LNCS. (1998)92–113 8. Sarmenta, L.F.G.: Protecting programs from hostile environments: Encrypted computation, obfuscation, and other techniques. Area Exam Paper, Dept. of Elec-trical Engineering and Computer Science, MIT, July 1999. (Edited and publishedas an appendix in [42]) (1999) 9. Sander, T., Tschudin, C.: Towards mobile cryptography. In: Proceedings of the IEEE Symposium on Security and Privacy, Oakland, CA, USA, IEEE ComputerSociety Press (1998) 10. Chikofsky, E., Cross, J.: Reverse engineering and design recovery: A taxonomy.
IEEE Software 7 (1990) 13–17 11. Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Crypto '01. Volume 2139of LNCS., Springer (2001) 1–18 12. International Obfuscated C Code Contest (IOCC): At http://www.iocc.org. web- 13. Carter, L., Ferrante, J., Thomborson, C.: Folklore confirmed: Reducible flow graphs are exponentially larger. In: Principles of Programming Languages 2003, POPL'03,New Orleans, Luisiana (2003) 14. Pande, H.D., Ryder, B.G.: Static type determination for c++. Technical Report TD-93-1, Tata Research Development and Design Center, Pune, India (1993) 15. Muth, R., Debray, S.: On the complexity of flow-sensitive data-flow analyses. In: 27th ACM Symposium on Principles of Programming Languages 2000, POPL'00,Boston, MA, USA (2000) 16. Chow, S., Gu, Y., Johnson, H., Zakharov, V.A.: An approach to the obfuscation of control flow of sequential computer programs. In: Information Security, 4thInternational Conference, ISC 2001, Malaga Spain, Proceedings. Volume 2200 ofLNCS. (2001) 155–155 17. Anderson, R., Kuhn, M.: Low cost attacks on tamper resistant devices. In Chris- tianson, B., Crispo, B., Lomas, T.M.A., Roe, M., eds.: Security Protocols, 5thInternational Workshop, Paris, France, April 7-9, 1997, Proceedings. Number 1361in LNCS, Springer (1998) 125–136 19. Appel, A., Govindavajhala, S.: Using memory errors to attack a virtual machine.
In: IEEE Symposium on Security and Privacy, 2003 ( "Oakland Security Confer-ence"). (2003) 20. Gosler, J.R.: Software protection: Myth or reality? In Williams, H.C., ed.: Ad- vances in Cryptology - CRYPTO '85, Santa Barbara, California, USA, August18-22, 1985, Proceedings. Volume 218 of LNCS., Springer (1986) 140–157 21. Micali, S., Reyzin, L.: Physically observable cryptography. In the IACR's ePrint archive at eprint.iacr.org (2003) 22. Fravia: Mirrored at http://tsehp.cjb.net/. web page (2002)23. Anti-crack — Deutschland: http://www.reverse-engeneering.de/. Internet por- tal for scientific software-protection, reverse-engeneering and IT security. Web page(2002) 24. Horne, B., Matheson, L., Sheehan, C., Tarjan, R.E.: Dynamic self-checking tech- niques for improved tamper resistance. In Sander, T., ed.: Security and Privacyin Digital Rights Management, ACM CCS-8 Workshop DRM 2001, Philadelphia,PA, USA, November 5, 2001. Volume 2320 of LNCS., Springer (2002) 25. TCG: The trusted computing group webpage. http://www.tcp.org (2004)26. Lippman, S.B., Lajoie, J.: C++ Primer (3rd Edition). Addison Wesley (1998)27. Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of applied cryptog- raphy. CRC Press (1996) 28. IDA Pro: http://www.datarescue.com. Software program (2002)29. Yuschuk, 30. Hetcht, M.: Flow analysis of computer programs. Elsevier North-Holland (1977)31. Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction of approximation points.
Record of the 4th Annual ACM Symposium on Principles of Programming Lan-guages (POPL' 77). (1977) 238–252 32. Ball, T.: The concept of dynamic analysis. In Nierstrasz, O., Lemoine, M., eds.: Software Engineering - ESEC/FSE'99, 7th European Software Engineering Con-ference, Toulouse, France, September 1999, Proceedings. Volume 1687 of LNCS.,Springer (1999) 216–234 33. Waissbein, A.: Secure triggers for preserving privacy in executable code. Technical report. Corelabs, Core Security Technologies. (2004) 34. Collberg, C.S., Thomborson, C.: Watermarking, tamper-proofing, and obfuscation - tools for software protection. University of Arizona Technical Report 2000-03 #170, University of Arizona (2000) 35. Arboit, G.: A method for watermarking java programs via opaque predicates. In: The Fifth International Conference on Electronic Commerce Research (ICECR-5).
(2002) 36. Wroblewski, G.: General Method of Program Code Obfuscation.
Wroclaw University of Technology, Institute of Engineering Cybernetics (2002) 37. Prosise, C., Mandia, K.: Incident Response: Computer Forensics (second edition).
McGraw-Hill Osborne Media (2003) 38. Bull, R.I., Trevors, A., Malton, A.J., Godfrey, M.W.: Semantic grep: Regular ex- pressions + relational abstraction. In: Working Conference on Reverse Engineering(WCRE 02), Richmond, VA, October 2002, Proceedings. (2002) 39. Marchionini, G.: Information seeking in electronic environments. Cambridge Uni- versity Press (1995) 40. Gaissarian, S.: Prelininary report on optimizing compilers and code transforma- tions. Technical report, Department of Compiler Technology, Institute for systemprogramming, Russian Academy of Sciences (2000) 41. Bodik, R., Gupta, R.: Partial dead code elimination using slicing transformations.
In: SIGPLAN Conference on Programming Language Design and Implementation.
(1997) 159–170 42. Sarmenta, L.F.G.: Volunteer Computing. PhD thesis, Dept. of Electrical Engi- neering and Computer Science, MIT (2001) 43. Canetti, R.: Universally composable security: A new paradigm for cryptographic In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Proceedings,, Las Vegas, Nevada, USA, 14th-17th October 2001, IEEEComputer Society (2001) 136–145 44. Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J.
ACM 33 (1986) 792–807 We follow [1]. Futoransky et alii, ibidem describes different secure triggersin the "universally composable security (UCS) framework" of R. Canetti([43]). We give a concise description of the underlying algorithms andsecurity results (for a complete description see [1] and [43]).
Let (Gen, Enc, Dec) be a ind-cpa secure symmetric cipher.
The simple trigger protocol Let S ∈ {0, 1}∗ be a secret procedure described as a string of bits. Fixk ∈ Z a security parameter. On set up we run the key generation algorithmGen to produce a key k of size k and arbitrarily choose a string iv ∈{0, 1}k. Then we compute Enck(iv), Enck(S) and initialize the algorithmin Figure 3.1 with these three values.
Security follows from the indistinguishability property of the symmet- ric cipher (see [1, Th. 3.1]). Or, in the language of [44], for any attackerA against this scheme there exists an attacker A0 against the ind-cpa se-curity of the block cipher (with a single known plaintext), such that theadvantage A has is smaller than the advantage of A0.
Subsequence trigger For the subsequence trigger procedure, the trigger criterion is satisfiedwhen a pre-defined subset of an input message (considered as a sequenceof bits) matches a particular value. Formally, let s, k be positive integerswith s > k. This trigger family is defined by the predicates pK : {0, 1}s → {true, false}; K ⊂ {1, 2, . . , s} × {0, 1}, #K = k, and if (i, b), (i, b0) ∈ K then b = b0o A predicate pK evaluates to true on input x = (x1, . . , xs) ∈ {0, 1}s, ifand only if, for every pair (i, b) in K, it holds true that xi = b.
To implement this trigger we construct an auxiliary family of (poly- nomially-computable, uninvertible) functions from {0, 1}s to {0, 1}k, suchthat a member τ verifies: i) given x in {0, 1}s, there exist indices j1, . . , jk ∈ {1, 2, . . , s} ⊂ Z – if y ∈ {0, 1}s is such that yj = x for 1 ≤ ≤ k, then both values have the same output τ (x) = τ (y).
ii) τ is onto, and for every y ∈ {0, 1}k the cardinality of the preimage τ −1(y) is 2s−k.
Assume τ has this properties, and fix values x ∈ {0, 1}s and b := (b1, . . , bk) :=τ (x). Let p be the predicate defined by p(y) = true if and only ifτ (x) = b. By hypotheses, there exist indices 1 ≤ i1, . . , ik ≤ s such thatb = τ (x) = (xi , . . , x ) and for every y ∈ {0, 1}s that, for 1 ≤ j ≤ k, satisfies yi = x , the equality τ (x) = τ (y) holds. Hence, if p(x) is true, then p(y) is also true.
With out further ado let Hash : {0, 1}∗ → {0, 1}m denote a one-way hash function and let the function family σ(t1,.,ts) : {1, 2, . . , s} × {0, 1}s → {0, 1}k; ti ∈ {0, 1}m, for 1 ≤ i ≤ s be defined by the assignment σ(t1,.,ts)(i, x) := y := (y1, . . , yk) and theprocedure in Figure A.2. Given any function σ from this family, notice Stored: (t1, . . , ts).
Input: i, (x1, . . , xs).
Output: (y1, . . , yk).
set i1 := i; y1 := xi; I := {i1};for n := 2 to k do: { compute i := Hash(y 1k . . kyn−1) ⊕ ti compute i := i + #{j : j ∈ I ∧ j ≤ i}; I := I ∪ {i};set in := i; yn := xi;} output (y1, . . , yk); Fig. 2. The auxiliary function that for every i, 1 ≤ i ≤ s, τ := σ(i, ) : {0, 1}s → {0, 1}k trivially verifiesproperties i) and ii).
The algorithm for this trigger can now be explained. Let S ∈ {0, 1}∗ be the secret procedure. Let (Gen, Enc, Dec) be a ind-cpa secure symmet-ric cipher. On the initialization, we run the key generation algorithmand get a key b = (b1, . . , bk) of size k, we randomly chooses bit-stringst1, . . , ts ∈ {0, 1}m of size m, and arbitrarily chooses a bit-string iv (ofsize k), finally we compute Encb(iv), Encb(S) and store these values.
Let σ := σ(t1,.,ts) be the function induced by the stored values t1, . . , ts. Let x denote the input of the trigger algorithm, then this algorithmfor every i, 1 ≤ i ≤ s computes τ (i, x) and checks if Decσ(i,x)(Encb(iv))for any i, 1 ≤ i ≤ s. If this happens, it must be that σ(i, x) = b and thealgorithm (computes and) outputs the secret S.
Security follows from [1, Th. 3.2].
Multiple-strings trigger Let k, s ∈ Z be integers with s ≥ 2, where k is the security parameterand s is the number of keys that are used to trigger. The trigger familyis then defined by the predicates : {0, 1}∗ → {true, false}; k where the predicate pk (x) = true on input x if, writing x = (x xt) there exist indices i1, . . , is such that (xi , . . , x i1+k−1) = k1, . . , (xis . . , xis+k−1) = ks.
We describe the algorithm for this trigger. Fix s ∈ N. On initializa- tion we use the key generation algorithm Gen to generate keys k1, . . , ksof size k, compute a random bit-string iv of size k, and finally computesEnck (iv), . . , Enc (iv) and Enc (S). These values are stored for the algorithm to access. For every input x ∈ {0, 1}∗, the triggerer proce-dure checks for the existence of integers 1 ≤ i1, . . , ik ≤ m such thatEnc(x (iv) holds for all j. If it does, it then com- ij +k−1)(iv) = Enckj putes ⊕j(xi , . . , x ij +k−1) and S = Dec⊕j (xi ,.,x ij +k−1)(Enc⊕iki Security follows from [1, Th. 3.3].

Source: https://www.coresecurity.com/system/files/publications/2016/05/BenderskyEtal_2003.pdf