Obfuscation
4 views
Skip to first unread message
Alan Karp
May 12, 2022, 11:58:28 AM5/12/22
to <friam@googlegroups.com>
I wonder what we're assuming the attacker knows about the semantic content of the program. Consider
mysecretkey = 42
print mysecretkey
that is obfuscated to
print 42
I would think that's not considered sufficiently obfuscated.
--------------
Alan Karp
--------------
Alan Karp
๏̯͡๏ Jasvir Nagra
May 12, 2022, 12:02:51 PM5/12/22
to fr...@googlegroups.com
I will go over this again this Friday - definitely ran out of time last week. I cover two different definitions of obfuscation and I will dwell a bit on a very precise definition because the word is intuitively overloaded. You should worry if you find yourself saying things like "sufficiently obfuscated".
--
Jasvir Nagra
--
You received this message because you are subscribed to the Google Groups "friam" group.
To unsubscribe from this group and stop receiving emails from it, send an email to friam+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/friam/CANpA1Z1%2B_hGYPvgToXUPY_o3H72pm%3DrHgW6EKqU8YWr3ab2gvw%40mail.gmail.com.
Baldur Jóhannsson
Jun 10, 2022, 12:31:15 PM6/10/22
to fr...@googlegroups.com
I was mulling over the difference between "&PI; in the sky" the
oracle version of a black box versus the desired but unrealizable
single execution locus* virtual black boxes promised by the false
intuation of obfusication that I had a glimmering of a recollection.
I had read somewhere that in cryptography there is something called
monotonic access structures.
I might be misunderstanding the concept but one example of such is an
multi recepiant OpenPGP message.
Basically, the plaintext of the message is encrypted using a symmetric
key and then that key is encrypted in multiple copies with the public
keys of the recipiants (and sometimes with a pre-aranged passphrase)
effectively making an OR kind of access structure.
Another example is doubly encrypted file where both, symmetric or
private keys are require to decrypt and get the plaintext. This makes
the AND kind of access structure.
Yet another example is a document with encrypted redactions, where
having higher and higher level of authorizaton/clearance gives one
keys to decrypt to redactions and unveil what was obscured.
(Basically a bit like Universal Hinting System file in a sense)
As the examples above alude to you can express any combinational
boolean logic of ANDs and ORs as such an access structure. However we
do not have any obvious means of making NOTs kind of access
structures.
As making this kind of access structures and how to excercise them
given the right keys can be cumbersome manually lets use
Clueless Software Agents from [1] instead.
Already we might be faring better only using the basic construction of
these CSAs as they can affect their environment of each other.
Even though that environment is quite local to the spefic
runtime-instance of a spefic collection of them meant to run together.
Lets say such a local environment is simply a key** value store.
This store contains keys and values that semantically look random and
might have at construction time of the lot been pulled from a hat.
Basically, random bitstrings that only has meaning to the constructor
of the lot. A bit like code phrases used by spies, secret societies
and such of yore.
This might give us weak/tentative way of realizing NOT functionality
lacking in monotonic access structures described above. How?
Simply, by having few basic construction CSAs in the lot to set values
of some spefic keys in the store to certain bitstrings that are, to
the constructure, the semantic inverse of other value(s) that
particular key could hold.
For the purpose of confusing a reverse engineer, those CSAs can
be modifing quite a few such key value mappings in the store and
the reverse engineer could not be sure at each juncture which
modifications are semantically salient.
Does this kind of ammalgated thing give us a virtual blackbox?
Well only a weak version of a forward only combinational boolean logic
one with possibility of side effects.
What you said, Jasvir, this friam (2022-05-13) about oracle version of
the black box of a program is that the reverse engineer only has
certain amount of asking that oracle. However one thing not mentioned
but implied is that the oracle has independent memory the requestor
and reverse engineer can not reset. (He lacks the capability ;-)
In the case of the single execution loci virtual box the reverse
engineer is unencumbered*** to reset the memory/state of the thing,
here the key value store, as many times as needed and rerun
the thing with diffrent inputs. In single player gamming this is often
refered to as save scumming.
But not to despair all is not yet lost, with a co-operation of a
minimally trusted third party or parties**** we might be able to
salvage this.
One kind of such party is the NynceService.
It is basically an key value store but each entry has
also an expiry, and a hmac root key associated with it.
Access to each entry is comtrolled and done via macaroon-esque
constructs. In addition to the usual timestamp caveats (onlyBefore and
onlyAfter) there are permission discarding caveats (allowOnly and
disallow) and operations chunks. That last contain something akin to
Bitcoins Script code. This code can manipulate the contents
of the key-value this macaroon-esque construct designates.
When such a comstruct is verified and its operations performed by a
NynceService it can at the end return results to the invoker of it.
Btw some of the caveats and operations chunks could be symmetrically
encrypted using the current hmac key at that point.
Like how parts of third party macaroon caveats are.
With help of such kind of third party or parties we can deprive the
reverse engineer of his save-scumm ability and regain the memory and
only-forward-progress of the oracle version.
This though only gives us ability to obfusicate programs that are near
straight line code (conditional execution of basic blocks) with
no looping.
Although if it is known at obfusication time the maximum amount of looping
expected the program to be obfusicated does then it pretty much
devolves to loop unrolling and we get back to near straight line code.
With smpc though we could make a reconstructor/renewer of such CSAs lot.
Such reconstructor/renewer is made with the semantic knowledge***** of
what the key-value mapping bitstrings represent statewise of the
obfusicated program.
But yeah, I think obfusication of programs without external help as
above is impossible.
Cheers!
-Baldur
* a multi execution loci virtual black boxes would posible through
Secure MultiParty Computation setups like the one described in [2]. In
such a setup afaiui, even if just one such locus/party has secrecy of
its secret shares used in the execution of the SMPC then the veil of
confidentiality is extended and covers the secrets inside that SMPC.
** key here meaning index key and not cryptographic key. Basically a
selector into a compound data structure.
*** beware, this is what lojban does to ones vocabulary, bends it to
more pendantry.
**** example of such in [1] are the time services used in the
OnlyAfter (NotBefore) and OnlyBefore (NotAfter) constructions.
***** a bit of semantic pun here, is the maker of the
reconstructor/renewer that has that semantic knowledge or is it the
reconstructor/renewer? I say either or both.
[1] https://www.schneier.com/academic/archives/1998/06/environmental_key_ge.html
[2] https://crypto.ethz.ch/publications/Maurer06.html
>> <https://groups.google.com/d/msgid/friam/CANpA1Z1%2B_hGYPvgToXUPY_o3H72pm%3DrHgW6EKqU8YWr3ab2gvw%40mail.gmail.com?utm_medium=email&utm_source=footer>
>> .
>
oracle version of a black box versus the desired but unrealizable
single execution locus* virtual black boxes promised by the false
intuation of obfusication that I had a glimmering of a recollection.
I had read somewhere that in cryptography there is something called
monotonic access structures.
I might be misunderstanding the concept but one example of such is an
multi recepiant OpenPGP message.
Basically, the plaintext of the message is encrypted using a symmetric
key and then that key is encrypted in multiple copies with the public
keys of the recipiants (and sometimes with a pre-aranged passphrase)
effectively making an OR kind of access structure.
Another example is doubly encrypted file where both, symmetric or
private keys are require to decrypt and get the plaintext. This makes
the AND kind of access structure.
Yet another example is a document with encrypted redactions, where
having higher and higher level of authorizaton/clearance gives one
keys to decrypt to redactions and unveil what was obscured.
(Basically a bit like Universal Hinting System file in a sense)
As the examples above alude to you can express any combinational
boolean logic of ANDs and ORs as such an access structure. However we
do not have any obvious means of making NOTs kind of access
structures.
As making this kind of access structures and how to excercise them
given the right keys can be cumbersome manually lets use
Clueless Software Agents from [1] instead.
Already we might be faring better only using the basic construction of
these CSAs as they can affect their environment of each other.
Even though that environment is quite local to the spefic
runtime-instance of a spefic collection of them meant to run together.
Lets say such a local environment is simply a key** value store.
This store contains keys and values that semantically look random and
might have at construction time of the lot been pulled from a hat.
Basically, random bitstrings that only has meaning to the constructor
of the lot. A bit like code phrases used by spies, secret societies
and such of yore.
This might give us weak/tentative way of realizing NOT functionality
lacking in monotonic access structures described above. How?
Simply, by having few basic construction CSAs in the lot to set values
of some spefic keys in the store to certain bitstrings that are, to
the constructure, the semantic inverse of other value(s) that
particular key could hold.
For the purpose of confusing a reverse engineer, those CSAs can
be modifing quite a few such key value mappings in the store and
the reverse engineer could not be sure at each juncture which
modifications are semantically salient.
Does this kind of ammalgated thing give us a virtual blackbox?
Well only a weak version of a forward only combinational boolean logic
one with possibility of side effects.
What you said, Jasvir, this friam (2022-05-13) about oracle version of
the black box of a program is that the reverse engineer only has
certain amount of asking that oracle. However one thing not mentioned
but implied is that the oracle has independent memory the requestor
and reverse engineer can not reset. (He lacks the capability ;-)
In the case of the single execution loci virtual box the reverse
engineer is unencumbered*** to reset the memory/state of the thing,
here the key value store, as many times as needed and rerun
the thing with diffrent inputs. In single player gamming this is often
refered to as save scumming.
But not to despair all is not yet lost, with a co-operation of a
minimally trusted third party or parties**** we might be able to
salvage this.
One kind of such party is the NynceService.
It is basically an key value store but each entry has
also an expiry, and a hmac root key associated with it.
Access to each entry is comtrolled and done via macaroon-esque
constructs. In addition to the usual timestamp caveats (onlyBefore and
onlyAfter) there are permission discarding caveats (allowOnly and
disallow) and operations chunks. That last contain something akin to
Bitcoins Script code. This code can manipulate the contents
of the key-value this macaroon-esque construct designates.
When such a comstruct is verified and its operations performed by a
NynceService it can at the end return results to the invoker of it.
Btw some of the caveats and operations chunks could be symmetrically
encrypted using the current hmac key at that point.
Like how parts of third party macaroon caveats are.
With help of such kind of third party or parties we can deprive the
reverse engineer of his save-scumm ability and regain the memory and
only-forward-progress of the oracle version.
This though only gives us ability to obfusicate programs that are near
straight line code (conditional execution of basic blocks) with
no looping.
Although if it is known at obfusication time the maximum amount of looping
expected the program to be obfusicated does then it pretty much
devolves to loop unrolling and we get back to near straight line code.
With smpc though we could make a reconstructor/renewer of such CSAs lot.
Such reconstructor/renewer is made with the semantic knowledge***** of
what the key-value mapping bitstrings represent statewise of the
obfusicated program.
But yeah, I think obfusication of programs without external help as
above is impossible.
Cheers!
-Baldur
* a multi execution loci virtual black boxes would posible through
Secure MultiParty Computation setups like the one described in [2]. In
such a setup afaiui, even if just one such locus/party has secrecy of
its secret shares used in the execution of the SMPC then the veil of
confidentiality is extended and covers the secrets inside that SMPC.
** key here meaning index key and not cryptographic key. Basically a
selector into a compound data structure.
*** beware, this is what lojban does to ones vocabulary, bends it to
more pendantry.
**** example of such in [1] are the time services used in the
OnlyAfter (NotBefore) and OnlyBefore (NotAfter) constructions.
***** a bit of semantic pun here, is the maker of the
reconstructor/renewer that has that semantic knowledge or is it the
reconstructor/renewer? I say either or both.
[1] https://www.schneier.com/academic/archives/1998/06/environmental_key_ge.html
[2] https://crypto.ethz.ch/publications/Maurer06.html
>> .
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "friam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to friam+un...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/friam/CAK1HgMh1XpLf7gxQnn6MRmDOv-73twpaAbKP44DUs3g2gWNgTg%40mail.gmail.com.
>
> --
> You received this message because you are subscribed to the Google Groups
> "friam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to friam+un...@googlegroups.com.
> To view this discussion on the web visit
>
Tony Arcieri
Jun 10, 2022, 1:08:06 PM6/10/22
to fr...@googlegroups.com
I feel like I'm missing some context here, but...
Kerckhoffs' Principle has largely held up in practice. Whitebox cryptography has attempted to obfuscate keys into code but in practice has exclusively slowed down attacks, with every whitebox being broken in practice.
No one has created a secure one, however Indistinguishability Obfuscation holds the potential to do so (although generally remains too slow to be practical):
--
You received this message because you are subscribed to the Google Groups "friam" group.
To unsubscribe from this group and stop receiving emails from it, send an email to friam+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/friam/CANpA1Z1%2B_hGYPvgToXUPY_o3H72pm%3DrHgW6EKqU8YWr3ab2gvw%40mail.gmail.com.
Tony Arcieri
Alan Karp
Jun 10, 2022, 10:07:05 PM6/10/22
to <friam@googlegroups.com>
On Fri, Jun 10, 2022 at 9:31 AM Baldur Jóhannsson <zaru...@gmail.com> wrote:
As the examples above alude to you can express any combinational
boolean logic of ANDs and ORs as such an access structure. However we
do not have any obvious means of making NOTs kind of access
structures.
One security policy that needs NOT is the Chinese Wall, often used by consulting houses. If you have permission to use resources from company A, you must be denied access to those of Company B. The trick for implementing this policy is to make a capability to use ra esource from A a negative capability for resources from B. Obviously, there are limits. For example, you can't allow Alice to first retrieve something from A and then from B. She could just use the capabilities separately. What you can do is prevent a single operation from accessing both resources. Of course, nobody implements things this way. They just use ACLs.
--------------
Alan Karp
Reply all
Reply to author
Forward
0 new messages