Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #948 > unrolled thread

invitation to discussion: code and protocol obfuscation techniques

Back to article view | Back to comp.compilers

Contents

  invitation to discussion: code and protocol obfuscation techniques "Gyll ." <isiisorisiaint@gmail.com> - 2013-08-01 14:49 +0300
    RE: invitation to discussion: code and protocol obfuscation techniques "Costello, Roger L." <costello@mitre.org> - 2013-08-03 20:58 +0000
    Re: invitation to discussion: code and protocol obfuscation techniques glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-08-04 03:41 +0000
    Re: invitation to discussion: code and protocol obfuscation techniques "Gyll ." <isiisorisiaint@gmail.com> - 2013-08-05 13:42 +0300
    Re: invitation to discussion: code and protocol obfuscation techniques "Gyll ." <isiisorisiaint@gmail.com> - 2013-08-05 15:44 +0300
      Re: invitation to discussion: code and protocol obfuscation techniques glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-08-06 19:09 +0000
        Re: invitation to discussion: code and protocol obfuscation techniques isiisorisiaint@gmail.com - 2013-08-08 03:24 -0700
          Re: invitation to discussion: code and protocol obfuscation techniques glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-08-08 14:41 +0000
            Re: invitation to discussion: code and protocol obfuscation techniques isiisorisiaint@gmail.com - 2013-08-14 08:20 -0700
            Re: invitation to discussion: code and protocol obfuscation techniques Gene Wirchenko <genew@telus.net> - 2013-08-20 19:05 -0700

#948 — invitation to discussion: code and protocol obfuscation techniques

I'd like to get some info on the subject of code obfuscation,
particularly source code-level obfuscation methods that will not get
rendered [totally] useless by code optimizers, program flow graph
extractors, and other program analysis tools.

More specifically, i need to build an obfuscator source code
preprocessor for a P2P client such that the obfuscator automatically
introduces additional protocol states to the base protocol in the
client code (a "protocol state" is state in the client algorithm state
machine where a [set of] messages are exchanged between two P2P
clients). The obfuscator-introduced protocol validation messages
should be as well obfuscated as possible, in order to make it
difficult for an attacker which has the original source code of the
client to determine which new protocol states have been introduced
(and where inside the code) by the obfuscator.

[toc] | [next] | [standalone]

#949

UCLA computer science professor Amit Sahai and a team of researchers have
designed a system to encrypt software so that it only allows someone to use a
program as intended while preventing any deciphering of the code behind it.
This is known in computer science as "software obfuscation," and it is the
first time it has been accomplished.

http://newsroom.ucla.edu/portal/ucla/ucla-computer-scientists-develop-247527.aspx

[I looked at the paper, but it's not obvious to what extent they've actually
made it work on real code. -John]

-----Original Message-----
From: compilers-owner@lists.iecc.com [mailto:compilers-owner@lists.iecc.com]
On Behalf Of Gyll .
Sent: Thursday, August 01, 2013 7:49 AM
Subject: invitation to discussion: code and protocol obfuscation
techniques

I'd like to get some info on the subject of code obfuscation,
particularly source code-level obfuscation methods that will not get
rendered [totally] useless by code optimizers, program flow graph
extractors, and other program analysis tools. ...

[toc] | [prev] | [next] | [standalone]

#950

Gyll . <isiisorisiaint@gmail.com> wrote:
> I'd like to get some info on the subject of code obfuscation,
> particularly source code-level obfuscation methods that will not get
> rendered [totally] useless by code optimizers, program flow graph
> extractors, and other program analysis tools.

As far as I know, the usual obfuscator generates a program with the
exact same function, flow, etc, (as seen by a compiler) but harder to
read by humans.

> More specifically, i need to build an obfuscator source code
> preprocessor for a P2P client such that the obfuscator automatically
> introduces additional protocol states to the base protocol in the
> client code (a "protocol state" is state in the client algorithm
> state machine where a [set of] messages are exchanged between
> two P2P clients).

Seems to me that this would require the obfuscator to know much more
about the algorithm than is usual. First of all, it has to recognize
that it is a state machine. It is not so unusual for verilog reading
tools to recognize and optimize state machines, but, as far as I know,
unusual for other languages. Even so, they expect a fairly specific
way of writing the state machine.

> The obfuscator-introduced protocol validation messages
> should be as well obfuscated as possible, in order to make it
> difficult for an attacker which has the original source code
> of the client to determine which new protocol states have
> been introduced (and where inside the code) by the obfuscator.

As usual, how well that can be done depends on how determined the
attacker is. What the value (in actual money) would be to an attacker,
and what tools would be available.

You might, for example, have an obfuscator that makes the code hard
for a human, but a program could determine that the added states
didn't make logical sense, and remove them.

-- glen

[toc] | [prev] | [next] | [standalone]

#951

@Roger: thank you for the pointer. i tried to walk through the article
PDF http://eprint.iacr.org/2013/451.pdf trying to figure out what
exactly the practical results are, and from what i've managed to
understand there's not very much of those yet, but i'll definitely
keep an eye on the subject.

Now, let me explain *my specific problem* a bit more in detail:

What I want to have is a two-halves program which are linked together
via a communication protocol, where one half of the program resides on
a trusted server and the other half is a client that is distributed in
the wild (to make things more clear, in my specific case the trusted
half will be a login server - but which can also do other stuff than
validating logins should it be needed, and the untrusted half that
needs to be protected is a messaging client)

What I am actually interested in is "code obfuscation-based moving
target defense", I.E. the client code (that needs to be protected) *is
allowed to be [periodically] re-obfuscated* by the server and
re-distributed (in the newly-obfuscated form) in order to achieve [a
very high level of] protection.

So the protection scheme looks something like this:

periodically_repeat: {
   new_obfuscation_method=pick_
at_random(set_of_obfuscation_methods);
   new_server_code:=obfuscate(new_obfuscation_method, original_server_code);
   new_client_code:=obfuscate(new_obfuscation_method, original_client_code);
   distribute(new_client_code);
}

and this brings me to following [code obfuscation-based moving target
defense] mechanism that i would like to have a discussion about:

1) each new version of the program introduces *new states* in the
communication protocol between the server-side and the client-side
halves of the program: this will make any not-updated version of a
client unfunctional (it will neither be able to log in on the server,
nor will it be able to comminicate with other clients (because the
clinet-to-client protocol also changes))
1.a) the protocol changes will consist *only* of adding protocol
validation messages, e.g. a new stage in the communication protocol
might have the server ask "tell me what is 1+1" and the client must
both understand the [newly-introduced] question, and (correctly) reply
to the question
2) each new version of the program is [heavily] obfuscated in a
different way, such that when comparing any two obfuscated program
versions it must be very hard to identify which code blocks in one
program version corresponds to which block in the other program
version
2.a) for an attacker who already knows exactly what code blocks *of
the original non-obfuscated program* he wants to change (i.e. in order
to implement a given malicious behavior into the *original* program),
it must be very hard for him to find (and then modify) the
corresponding code blocks *in the obfuscated program*: in this way the
attacker is delayed in introducing into the obfuscated program the
changes he wants to make, although he knows exactly how, and where, to
implement those changes in the original program code
2.b) alternatively, an attacker (who we assume has already crafted a
[malicious] patch to the source code *for the original program and
protocol*) must also have a hard time in understanding *exactly what
protocol changes have been made* in [each] new version of the client:
in this way, the attacker will be delayed in implementing any new
protocol changes into his already-maliciously-modified version *of the
original program* (until he first understands exactly what those
changes are)

So the input I'd be very much interested in is comments/ideas related
to this generic question: how can we leverage protocol obfuscation in
a split program where one part is trusted and the other is not, using
the moving target defense class of solutions based on code *and
protocol* obfuscation

I've been looking on the net for something along the lines described
in my previous post but came up empty handed, so, apart from any
original input on the topic, I'd also very much appreciate if anyone
can provide any pointers to some [published] work related to [a
similar method to] what I described

[toc] | [prev] | [next] | [standalone]

#952

Allow me to [try to] kickstart the discussion with an idea (dependent
on, and thus characteristic to) the the split-program structure that i
described (i.e. half trusted, half not, and communicating with
each-other via a communication protocol):

an obfuscated version of the protocol can allow, apart from
introducing new protocol stages and modifying the message format (in
order to render older versions of a program inoperable), also to
introduce *new dependencies in the program*, thus apparently (to me)
having the potential to completely change the program's abstract
syntax tree (AST) beyond recognition; namely:
a) new variables can be introduced, where said variables are
initialized from values coming in messages from the trusted half of
the program (the server in my case); then these variables can be
pollute the program by embedding them in opaque expressions
b) various [known only to the trusted half] relationships between the
newly-introduce variables can exist, thus enabling the creation of
opaque predicates, which in turn can be used to cloak both the program
flow, and to cloak the statistics of a code block (thus making harder
the identification of a code block that performs a given function)
* of course, the above techniques must be assisted by variable codecs
(e.g. variable merging and the likes) in order to hide the
dependencies of an expression on a given (set of) variable(s)

Note that both of the above techniques only work against static
analysis, but i'd be very interested in ideas of how to use my
specific setting (two-half program with half trusted and half not) to
harden dynamic analysis
A suggestion for a starting point: identify various computing
resources that your typical computer has (e.g. multi-threading,
multi-stasking, local loop, etc), and try to figure out how to make
best use of them for obfuscation purposes

[toc] | [prev] | [next] | [standalone]

#954

Gyll . <isiisorisiaint@gmail.com> wrote:
> Allow me to [try to] kickstart the discussion with an idea (dependent
> on, and thus characteristic to) the the split-program structure that i
> described (i.e. half trusted, half not, and communicating with
> each-other via a communication protocol):

One important thing to know is the approximate value of someone
breaking the system. That affects how much human effort one might put
into the attack.

> an obfuscated version of the protocol can allow, apart from
> introducing new protocol stages and modifying the message format (in
> order to render older versions of a program inoperable), also to
> introduce *new dependencies in the program*, thus apparently (to me)
> having the potential to completely change the program's abstract
> syntax tree (AST) beyond recognition; namely:

Some things you might read about are Diffie-Hellman key exchange and
differential cryptanalysis. I am not so sure that Diffie-Hellman will
help, but it is often used in client-server systems.  It is, for
example, how secure network connections are made.

> a) new variables can be introduced, where said variables are
> initialized from values coming in messages from the trusted half of
> the program (the server in my case); then these variables can be
> pollute the program by embedding them in opaque expressions

This is the case where differential cryptanalysis can come in.  By
comparing the differences, probably using a computer, one can
determine statistically what matters and what doesn't.

> b) various [known only to the trusted half] relationships between the
> newly-introduce variables can exist, thus enabling the creation of
> opaque predicates, which in turn can be used to cloak both the program
> flow, and to cloak the statistics of a code block (thus making harder
> the identification of a code block that performs a given function)
> * of course, the above techniques must be assisted by variable codecs
> (e.g. variable merging and the likes) in order to hide the
> dependencies of an expression on a given (set of) variable(s)

Consider that the attacker can use a program other than the one you
supply to send in requests and process the replies.  That allows one
to determine more than you might hope about what the secret side is
doing.

-- glen

[toc] | [prev] | [next] | [standalone]

#956

@glen
>As far as I know, the usual obfuscator generates a program with the
>exact same function, flow, etc, (as seen by a compiler) but harder to
>read by humans.

Yes, this is pretty much the standard definition, but what i want to have is a
*protocol* obfuscator (no "standard definition" for this one as far as i know)
which, just like code obfuscation tries to hide code, protocol obfuscation
tries to hide protocol (modifications) by polluting a "source protocol" with
extra messages/stages (and also by scrambling the format of the source
protocol messages); in this context, code obfuscation is only meant to
obfuscate the code which implements the obfuscated protocol, such that finding
correspondences between the code that implements the original protocol and the
code that implements the obfuscated protocol are made hare to identify (and
then change).

>Seems to me that this would require the obfuscator to know much more
>about the algorithm than is usual. First of all, it has to recognize
>that it is a state machine.

Yes, but I FORGOT TO MENTION SOMETHING IMPORTANT IN THE ORIGINAL POST: i am
allowed to include obfuscator directives in the original source code, e.g.
[...]
//OBFUSCATOR_DIRECTIVE:insert_protocol_validation_message
else if (state==STATE1) {
[...]
(also, apart from generic obfuscation methods which the obfuscator can pick at
random and insert anywhere it pleases in the code, i can use directives to
force it to introduce obfuscation in specific places where i want obfuscation
to always be introduced)

>As usual, how well that can be done depends on how determined the
>attacker is. What the value (in actual money) would be to an attacker,
>and what tools would be available

My biggest problem is to have an algorithm that requires *human intervention*,
and it would of course be nice to require as much human intervention as
possible, but as i said in a later post i don't need one particular version of
obfuscated code to be unbreakable since the obfuscated code will be constantly
updated. What i *do* need is to have an automated algorithm which can produce
such a high variety of obfuscated code that each new code version will require
human intervention.

>Some things you might read about are Diffie-Hellman key exchange and
>differential cryptanalysis.

I am familiar with these notions (actually i'm using public key crypto in my
program), but only at the protocol level, i.e. i am not a mathematician eating
groups for breakfast, so there's no way i can make an informed decision all by
myself as to if and how all kinds of crypto analysis methods can be used
against code obfuscation techniques. I did read quite a lot of articles on
code obfuscation, and, fwiw, i didn't find anything related to crypto
analysis-based de-obfuscation

[toc] | [prev] | [next] | [standalone]

#957

isiisorisiaint@gmail.com wrote:
> @glen
>>As far as I know, the usual obfuscator generates a program with the
>>exact same function, flow, etc, (as seen by a compiler) but harder to
>>read by humans.

> Yes, this is pretty much the standard definition, but what i
> want to have is a *protocol* obfuscator (no "standard
> definition" for this one as far as i know) which, just like
> code obfuscation tries to hide code, protocol obfuscation tries
> to hide protocol (modifications) by polluting a "source
> protocol" with extra messages/stages (and also by scrambling
> the format of the source protocol messages); in this context,

(snip)

>>Seems to me that this would require the obfuscator to know much more
>>about the algorithm than is usual. First of all, it has to recognize
>>that it is a state machine.

> Yes, but I FORGOT TO MENTION SOMETHING IMPORTANT IN THE ORIGINAL
> POST: i am allowed to include obfuscator directives in the
> original source code, e.g.

> //OBFUSCATOR_DIRECTIVE:insert_protocol_validation_message
> else if (state==STATE1) {
> [...]
> (also, apart from generic obfuscation methods which the
> obfuscator can pick at random and insert anywhere it pleases
> in the code, i can use directives to force it to introduce
> obfuscation in specific places where i want obfuscation to
> always be introduced)

Seems like something similar might be useful in ordinary source
obfuscation. Giving hints to the obfuscator...

>>As usual, how well that can be done depends on how determined the
>>attacker is. What the value (in actual money) would be to an attacker,
>>and what tools would be available

> My biggest problem is to have an algorithm that requires *human
> intervention*, and it would of course be nice to require as
> much human intervention as possible, but as i said in a
> later post i don't need one particular version of obfuscated
> code to be unbreakable since the obfuscated code will be
> constantly updated. What i *do* need is to have an automated
> algorithm which can produce such a high variety of obfuscated
> code that each new code version will require human intervention.

Yes, that is why I mentioned differential cryptanalysis.

After that post, I read the wikipedia page, which I had forgotten
about. It seems that the beginning of the pubic discussion on it
included noting that DES was unusually resistant to differential
analysis, that is, much more than would have been expected.

It seems that IBM knew about it at the time, designed for it,
but didn't talk about it.

In your case, I am considering the possibility that the humans
trying to break it start using computers to help. If you don't
design for it, it might be too easy.

Well, consider one example. Say you distribute programs with
magic constants in them. It would normally be difficult for
someone to find such constants. But say someone gets two different
copies, with two different constants. In that case, a byte comparison
will easily flag them. It is much less obvious in the case of
states of a state machine, but again, it might be possible
for a program to extract them, compare them, and figure out
the obfuscation.

Reminds me that one time I had a web page where I could select
the value of some parameters from a menu, but I wanted a value
that wasn't one of the choices. I downloaded the page
(saved the html source) edited the source, loaded it into a
browser, and selected the new value. The server didn't verify
that only specific values were used.

Also, note that this problem seems not so different from the
license validation keys used by many software protection systems.

>> Some things you might read about are Diffie-Hellman key
>> exchange and differential cryptanalysis.

-- glen

[toc] | [prev] | [next] | [standalone]

#959

Found something that bears some resemblance with my half-trusted execution environment, so i'll list it here maybe others will find it useful: http://www.google.com/search?q=%22Exploiting+Code+Mobility+for+Dynamic+Binary+Obfuscation%22+pdf

A couple of links on generic code obfuscation techniques:
* http://www.google.com/search?q=%22A+taxonomy+of+obfuscating+transformations%22+pdf
* https://www.google.com/search?q=%22Code+Obfuscation+against+Static+and+Dynamic+Reverse+Engineering%22+pdf

A link on proactive obfuscation as a moving target defense:
* http://www.google.com/search?q="Proactive+Obfuscation"+microsoft+pdf

Finally, a link on protocol de-obfuscation:
* http://www.google.com/search?q="Polyglot%3A+Automatic+Extraction+of+Protocol"+carnegie+pdf

[toc] | [prev] | [next] | [standalone]

#961

On Thu, 8 Aug 2013 14:41:00 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

[snip]

>Reminds me that one time I had a web page where I could select
>the value of some parameters from a menu, but I wanted a value
>that wasn't one of the choices. I downloaded the page
>(saved the html source) edited the source, loaded it into a
>browser, and selected the new value. The server didn't verify
>that only specific values were used.

     I have used that, too.

     One ISP that I had was using had a usage page.  With it, one
could get statistics on one's account for a three-month window.  The
page had to be updated by them each month.  Sometimes, they did not
get around to it right away.  I tried modifying the page locally and
using that, and with that, I was able to check usage in the new month.

[snip]

Sincerely,

Gene Wirchenko

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web