[HN Gopher] UCLA computer grad constructs "crown jewel of crypto...
___________________________________________________________________
UCLA computer grad constructs "crown jewel of cryptography"
Author : geox
Score : 308 points
Date : 2023-05-24 22:14 UTC (1 days ago)
(HTM) web link (www.acm.org)
(TXT) w3m dump (www.acm.org)
| [deleted]
| hkopp wrote:
| The precise mathematical definition of obfuscation and what is
| considered obfuscation for an average software engineer are two
| very different things.
|
| In fact, the article is only about indistinguishability
| obfuscation. What is mostly discussed in this thread is the
| notion of virtual black box obfuscation (VBB). VBB has been
| proven to be impossible in the general case (see
| https://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf). There are a
| few special programs where VBB is feasible, such as point
| functions, but in general in cannot be achieved.
|
| Indistinguishability obfuscation (iO) means that if you obfuscate
| two programs that compute the same function, then you cannot
| distinguish them. Or put in different words, if you get two
| obfuscated programs, then there is no better way than random
| guessing (except for a factor that is negligible in some security
| parameter) to find out if they stem from the same original
| program.
| codethief wrote:
| Thanks, I had no idea what to make of the OP, so your comment
| is very valuable!
|
| > Or put in different words,
|
| I don't see how the second phrasing follows from the first one.
| In fact, I don't understand what the second statement is
| supposed to mean to begin with. Could you elaborate?
| DannyBee wrote:
| If you have a bubble sort and selection sort, and run them
| through IO, for either result, you can't tell if the original
| was bubble sort or selection sort.
|
| Roughly: VBB is the ability to take any program and make it
| indistinguishable from random.
|
| IO is the ability to take two programs that compute the same
| function and make them indistinguishable from each other.
| dilippkumar wrote:
| How far does this analogy go?
|
| For example, if I plot how long both programs take at
| various scales, at some point I should be able to determine
| which one is O(n log(n)) right?
| DannyBee wrote:
| I gave the formal definition of distinguishability in the
| other comment, but it does not include running time.
| Waterluvian wrote:
| And that involves preventing the leakage of any data? Such
| as the time each take?
| DannyBee wrote:
| The original goal was to be able to make public key
| systems out of secret key systems, so hiding existing
| running time is not part of the definition of
| indistinguishable.
|
| It is about what information you can glean about either
| of the originals. Formally (from the paper):
|
| Indistinguishability: For every two ensembles {C0,l} and
| {C1,l} of polynomial-sized circuits that have the same
| size, input length, and output length, and are
| functionally equivalent, that is, [?]l, C0,l(x) = C1,l(x)
| for every input x, the following distributions are
| computationally indistinguishable:
| {iO(1l, C0,l)} {iO(1l, C1,l)}
|
| IE you can take a secret key system, hardwire the key
| into the program, and turn it into a public key system
| without fear that the secret key will be recovered -
| instead, it will not be distinguishable from other
| programs with different hardwired keys.
| Waterluvian wrote:
| Ah I think I understand better. Thanks!
| gnull wrote:
| The latter is useful to hide who wrote the program? Like some
| features of code that might reveal your personal patterns?
|
| Or what is it for?
|
| And how does it deal with timing? If two programs I gave it
| have different complexity, would it pad the running time to
| some fixed value? If so, how is that value chosen?
| DannyBee wrote:
| To try to make this concrete, if you have a program A that does
| bubble sort, and a program B that does selection sort:
|
| 1. VBB would be making it so you can't glean information about
| A or B by running VBB(A) or VBB(B) or examining them, for
| various definitions of "information".
|
| You can't tell A is a bubble sort at all, and you can't tell B
| is a selection sort at all.
|
| VBB is, as mentioned, impossible in the general case.
|
| 2. IO would be making it so if you are holding IO(A) and IO(B),
| you can't tell them apart, and can't tell if the original was A
| or B.
|
| So you can have functionally identical programs, and when you
| run them through IO, you can't tell whether the original was A
| or B.
| junon wrote:
| Thanks, this is a great explanation.
| e12e wrote:
| Ed: redundant - asked and answered in thread.
| DannyBee wrote:
| Yeah, I probably should have collected an the pieces into a
| single reply. Right now the number of comments is small
| enough that it's not hard to find though.
| [deleted]
| [deleted]
| foota wrote:
| I wonder how this compares to homomorphic encryption? If I
| understand correctly, I could give someone a computation with an
| embedded key that operates over encrypted data, and they wouldn't
| be able to decrypt the data other than for the computation I gave
| them, right?
| noam_k wrote:
| I think it compares more to a One Time Program or Functional
| Encryption.
|
| Homomorphic Encryption won't prevent you from decrypting other
| outputs (if you have a decryption key), and with Functional
| Encryption it's assumed both parties know the function being
| evaluated, so OTP is really the closest.
| marktangotango wrote:
| For those, like me, wondering what this is about;
|
| > Program obfuscation would enable a host of useful applications:
| For instance, you could use an obfuscated program to delegate
| particular tasks within your bank or email accounts to other
| individuals, without worrying that someone could use the program
| in a way it wasn't intended for or read off your account
| passwords (unless the program was designed to output them).
|
| I relate this to cracking; run a program and watch the memory,
| see where the password is checked and edit the binary at that
| location to bypass. So this level obfuscation would make that
| impossible? Seems like magic honestly.
| yalogin wrote:
| DRM implementations already use code obfuscation heavily. Can
| someone with knowledge of the math clarify why this is a big
| deal? Why would it matter that there is mathematical proof that
| someone cannot figure out what the code is doing? How does it
| apply to crypto?
| Vervious wrote:
| The code obfuscation that DRM implementations use is not
| provably secure. I don't think anyone would (or should) hide a
| bitcoin secret key inside of an obfuscated program. There's no
| formal guarantee of security.
|
| This work, on the other hand, shows a provably secure
| construction for obfuscation (assuming that some assumptions
| about the hardness of various well-studied mathematical
| problems are true). In other words, extracting a bitcoin secret
| key from an obfuscated algorithm is as hard as _insert math
| problem here_. (This is how all cryptography works; e.g.
| breaking RSA encryption is as hard as factoring large products
| of primes.) This paper is special because, for the first time,
| the hard math problem they use (to build the obfuscation) is
| "reasonable": they've been studied for decades, and no one
| knows how to break them. (Indeed, a lot of cryptography is
| built on top of the same assumptions/problems.)
|
| Thus, we would be surprised if someone extracted our bitcoin
| secret key from our obfuscated program, because it means they
| solved some "thought-to-be-unsolvable" mathematical problem.
| This is a much nicer guarantee than the alternative, e.g. with
| current obfuscation, where we say "oh, it looks pretty random,
| let's stick my key in" and then trusting that no one will break
| it. (That's a lot of trust, when you might have a 100,000
| Bitcoin at stake.)
|
| Of course, none of this is really feasible; at best, we can
| securely obfuscate tiny circuits (in the present time). So the
| main utility is probably to hide keys and the such, not to
| obfuscate entire programs. This might enable better secure MPC
| schemes, NIZKs, etc. So I guess, per your question, it's also
| targeted towards a different use case.
|
| Now, as to why theoretical cryptographers care about
| obfuscation in general: it's not so much about the direct
| application of obfuscating programs. (It's not obvious why
| obfuscation is more interesting than encryption, etc, from an
| applied point of view.) Instead, from a theoretical point of
| view, if we can build indistinguishability obfuscation, we can
| directly build public key encryption, non-interactive zero
| knowledge proofs, Multiparty computation, etc. etc. (assuming
| one-way functions). So really, this is a primitive that somehow
| connects all of the other primitives, which is why
| theoreticians think it is a big deal.
| Retr0id wrote:
| > I don't think anyone would (or should) hide a bitcoin
| secret key inside of an obfuscated program.
|
| I can't remember where I read this, or if it was just a
| hypothetical, but I think I heard of people doing this
| deliberately as a sort of canary. If the wallet gets drained,
| then you know someone cracked your obfuscation.
| anonymousDan wrote:
| How does obfuscating a key differ from encrypting it?
| Vervious wrote:
| For example, we could write a program that hard-codes a
| secret key, and then signs bitcoin transactions with that
| secret key, but only if the transaction has value less than
| 0.5 bitcoin. Then anyone who has the program can sign
| things of small value on our behalf; if the program is
| indistinguishably-obfuscated, they won't be able to get any
| additional information about the key itself, or use it in
| any other way.
|
| I guess just encrypting the key won't let you use it to
| sign things.
| kybernetikos wrote:
| Imagine you wrote a decoder program with the key embedded in
| it. From looking at the program you can't work out what the key
| is, but you can use it to decode a secret message. You can have
| a secret encoder program too. Effectively blackbox obfuscation
| among other things allows you to turn symmetric encryption into
| asymmetric encryption.
|
| Another possible use is in cloud computing. You could prepare a
| program with private information in it and still safely submit
| it to a third party to execute. This would also be very useful
| with smartcontracts. Since the smart contract code is public it
| can't contain any secrets unless it's safely obfuscated.
|
| As I understand it we are still quite a way off from any of
| these techniques being feasible, since the overhead at the
| moment is huge.
| aaroninsf wrote:
| Thanks to DannyBee for ITT de-obfuscating the finding and its
| practical implications.
| Sophistifunk wrote:
| If mankind can't stomach 10% overhead to check array bounds and
| collect unused memory, what makes anybody think they can sell
| 1,000,000% overhead to make your DRM driver (and viruses) harder
| to reverse?
| Retr0id wrote:
| We already accept something on the order of 1000% overhead for
| video DRM (software vs hardware decoding)
| doctor_eval wrote:
| Same reason. Money.
| ronsor wrote:
| Denuvo would like a word with you.
| gmerc wrote:
| But does it withstand a powerful LLM attack? Because cursory
| tests on existing commercial code obfuscation solutions so far
| look like it's clubby baby seals for them LLM
| hmmmcurious1 wrote:
| Weird how having research of this quality only lands you
| assistant professorship. The competition in academia is insane
| neom wrote:
| It's not weird, it's how academia works, it's not even about
| competition, it's about putting in the work in a sustained
| manner. It's about proving if you can get funding (who do you
| know, how often do you publish, what type of publishing do you
| do), how long have you been teaching for, etc etc. In addition
| to experience, most institutions have specific criteria and
| expectations for promotion to full professorship...
| demonstrated record of excellence in teaching, multiple
| significant contributions to the field through research and
| active engagement in service and leadership roles within the
| academic community. This guy has a very very sparse resume.
| Just because he did one impressive thing doesn't mean anything
| in academia (thankfully).
| imtemplain wrote:
| [dead]
| derrida wrote:
| 1 year old
| Animats wrote:
| That is a fascinating result. A remarkable mathematical
| achievement. And a nightmare.
|
| This thesis says that it's possible to obfuscate code in such a
| way that there is a lower bound on the level of effort needed to
| de-obfuscate it. That lower bound can apparently be comparable to
| the level of effort required to break a cryptosystem.
|
| So, coming soon, viruses and worms nobody can figure out. Code
| where no one can tell if it has a backdoor. ML classifiers where
| no one can be sure what they really do.
| elefanten wrote:
| Seems some of those cases (backdoors and classifiers) could be
| prevented by regulation and/or social convention (eg- don't use
| programs/services obfuscated in this way).
|
| The malware seems trickier. Maybe systems will need to require
| proof of unobfuscated source to run code?
| tptacek wrote:
| Isn't that where we're already at with ML classifiers?
| astrange wrote:
| Well, we know they're ML classifiers and they're not making
| syscalls. So there's obviously a limit to "we don't know what
| they do".
| tptacek wrote:
| You'd still know what syscalls a cryptographically
| obfuscated userland program was making.
| sbierwagen wrote:
| If it's a total black box, wouldn't the NOBUS thing to do
| would be to have some large key that it's watching input
| for that flips it into a malicious mode?
|
| If BB(6) took years to execute, how long would you have
| to spend feeding random input to a suspected-hostile
| 10000 symbol Turing machine (whose source code and state
| you can't examine) in a sandbox before you decided it was
| safe?
| rini17 wrote:
| Easy, have all executable segments read-only with none
| (or fixed) syscall instructions.
| astrange wrote:
| Think it'd be a bit dangerous to let them make any
| though, unless you were single stepping.
| godelski wrote:
| Wouldn't this also be a field day for encryption maximalists?
|
| I'd imagine if all code were to be perfectly obscured then to
| the public it wouldn't matter, but many would demand for more
| open source and that'd be the only way to trust.
| stuckkeys wrote:
| Yeah pretty much. It is only going to get wilder in the
| ransomware scene. Good times ahead.
| amoss wrote:
| Ah, "code is law". Good luck with that.
| macawfish wrote:
| Just wait until the legislators catch wind of this.
| NoMoreNicksLeft wrote:
| Even if the vendor is willing to provide source, you can't be
| sure that the binary matches. Nice.
|
| I think Saberhagen's Berserkers actually had this feature.
| Tangurena2 wrote:
| This was the point behind _Reflections on Trusting Trust_ -
| you can 't trust it. Unless you build the entire
| compiler/linker tool chain from source that you've already
| inspected.
|
| https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref.
| ..
| schoen wrote:
| You can be sure that it matches if the vendor (1) doesn't use
| an obfuscated binary, or (2) provides exact details of how
| the obfuscated binary was constructed (presumably including
| some kind of seed for the obfuscator).
| Animats wrote:
| > I think Saberhagen's Berserkers actually had this feature.
|
| Yes. Code decoded other code, etc. So if the code wasn't
| running normally, it couldn't be analyzed. It was handwaving
| back then, but it may become real.
| Tangurena2 wrote:
| It was standard coding practices if you were selling games
| - to prevent people from hacking the license key stuff. Or
| by cheating software to prevent detection by anti-cheat
| software. One of the hooks built into Windows is "is a
| debugger connected" helps the virus/cheat code determine if
| it is "safe" to run or not.
| eru wrote:
| Just don't trust that code, and don't run it?
|
| You should require positive proof that code does what you want.
|
| Similar to how eg Haskell's type systems doesn't have to solve
| the halting problem [0]: it just rejects some programs that
| would be ok, but don't conform to the type system.
|
| See also proof-carrying code.
| https://en.wikipedia.org/wiki/Proof-carrying_code
|
| [0] Ok, unless you use undecidable instances or something like
| that.
| Attrecomet wrote:
| > You should require positive proof that code does what you
| want.
|
| That's just saying you should only ever solve simple problems
| with your computer.
| ilyt wrote:
| > Just don't trust that code,
|
| That's even harder problem to solve
| zamalek wrote:
| Any program worth obfuscating is not worth trusting.
| twelve40 wrote:
| Among other things, tons of desktop software and most
| mobile apps and even javascript you run from most
| websites is obfuscated. How is it possible to avoid that?
| Do you run 100% open source for everything with
| javascript disabled?
| bentcorner wrote:
| Some people do take it that seriously:
| https://www.gnu.org/software/librejs/
| Technotroll wrote:
| Wouldn't this be a great case for a sort of machine or
| program that delivers Zero Knowledge Proofs for each input
| and output?
| s3p wrote:
| Yes great so let's not use any software at all on our
| machines! only things we can program ourselves or are open-
| source. what a dystopia we live in...
| DannyBee wrote:
| Well, no.
|
| What you are worried about is VBB (roughly can i take a program
| a and obfuscate it in a way that you get no information about
| the original from the obfuscated version), which has been
| proven impossible.
|
| This is about indistinguishability, which is a form of
| obfuscation, but not the kind you are thinking about.
|
| This is really something like "If you have two programs a and b
| that compute the same function, it's possible to obfuscate them
| in a way that the resulting programs are indistinguishable from
| each other"
|
| So if program a is "bubble sort" and program b is "selection
| sort" (function here is the mathematical sense, so these
| compute the same function), obfuscation can make it so you
| can't tell them from each other, and you can't tell if the
| original program of what you are holding was bubble or
| selection .
|
| Roughly: VBB is the ability to take any program and make it
| indistinguishable from random.
|
| IO is the ability to take two programs that compute the same
| function and make them indistinguishable from each other.
|
| "compute the same function" is actually what makes it feasible
| :)
|
| The original use case was really trying to turn secret key
| systems into public key systems by hardwiring the secret key
| into the program and then obfuscating it.
|
| So an example use case today would be "every DVD decoding
| program has a different key but computes the same function, can
| you make them all indinguishtable and thus hide the key" or
| something like that.
| cs702 wrote:
| > The original use case was really trying to turn secret key
| systems into public key systems by hardwiring the secret key
| into the program and then obfuscating it.
|
| Wow, that definitely qualifies as a "crown jewel." I, for
| one, would not look forward to a future in which software
| running on _my_ hardware is able to hide secrets, like one-
| off media encryption keys, _from me_!
| DannyBee wrote:
| In practice, as the thesis proves, you can use iO to
| generate a lot of things people care about in cryptography.
| I will go out on a limb and say you can use it to build
| almost everything interesting :)
|
| Now, it happens for a lot of those we don't need iO and iO
| may be impractical, but as a theoretical building block,
| it's quite nice.
|
| As for your concern, yes, this is now possible, at least in
| the sense that you do as good as is possible to do in
| making them computationally indistinguishable. This does
| not prevent you from attacking it in other ways :)
|
| Two things, good or bad depending on how you look at it:
|
| 1. You can prove iO is as least as good as the best
| possible obfuscation scheme that can ever exist. So
| whatever that enables you to do or not, it's the limit.
|
| 2. It also means you can get away with handing over less
| secrets, ensure better isolation, etc.
|
| The following things are possible with iO (trivially so),
| due to this paper:
|
| Adaptively secure succinct garbled RAM - which would let
| you hand secure databases to untrusted providers and not
| worry about it.
|
| Sender deniable encryption where you can't prove what the
| original plaintext was and various options are equally
| likely.
|
| Fully deniable interactive encryption where secrecy of
| communication is protected even if the parties are later
| coerced (or willingly bribed) to expose their entire
| internal states: plaintexts, keys and randomness.
|
| etc
|
| These are just some examples.
|
| Now, some of this, as I said, we know how to do already,
| some we don't. But this paper gives you iO as a building
| block that can do them _without having to separately prove
| that it is as sound and secure as existing crypto systems
| are_.
|
| Again, iO only provides computational indistinguishability,
| not other things, but it is a nice primitive.
| cs702 wrote:
| Thank you for taking the time to respond so thoroughly
| :-)
|
| Everything you write makes sense to me -- though I had to
| lookup and skim Canetti and Holmgren's work to understand
| the bit about succint garbled RAM.
|
| We live in interesting times!
| krageon wrote:
| > viruses and worms nobody can figure out
|
| Sandboxing and modeling interaction are still possible and
| useful, and is a large part of figuring out viruses and worms.
| That's not going away
| m463 wrote:
| Could you steal source code, obfuscate it, and sell it as your
| own?
| quickthrower2 wrote:
| Does it run at the same speed as the original?
| omgwtfbyobbq wrote:
| Across the same universe of discourse.
| dataflow wrote:
| Is it just an existence proof or is it actually constructive?
| (I haven't read the dissertation.)
| [deleted]
| vlovich123 wrote:
| Looks like constructive but my math knowledge is probably
| equivalent to a freshman's at best.
| matthewdgreen wrote:
| It is not efficient enough that you need to worry about
| exciting developments using this scheme. But it's a step
| towards more reasonable mathematical assumptions than
| previous constructions, assumptions that may actually be
| true. Give it a few more years and we might be able to use
| this stuff.
| Animats wrote:
| I'm not sure. It seems to be applied to "circuits", which in
| this context seems to mean a one-way set of logic gates (such
| as AND, OR, NOT, NAND) which map a set of boolean inputs to a
| set of boolean outputs. In theory you can construct any
| finite digital function that way. It's a useful abstraction,
| like a Turing machine.
|
| Unlike a Turing machine, a circuit is finite. All circuits
| are "solveable" (given a outputs, compute an input which
| yields them) by trying all the input patterns.. There's no
| undecidability and no halting problem. There's just
| difficulty. "Difficult" here means there's no way easier than
| trying all the patterns. This is the same property sound
| cryptosystems are supposed to have - there's no easier way
| than trying all the keys.
|
| Whether this result can be extended to programs with
| iteration I'm not sure. The paper doesn't seem to mention
| iteration or storage.
| jhanschoo wrote:
| A (polynomial-sized) circuit in this context is a sequence
| of DAGs whose nodes are binary logic gates where the nth
| DAG infers 1 output bit from n input bits, such that some
| polynomial bounds the size of the graphs of the sequence.
| See https://en.wikipedia.org/wiki/Circuit_complexity
|
| The class of circuits in question is P/poly which includes
| BPP (which includes P, the class of polynomial-time
| programs). So the result is quite general, since most
| practical programs are in P.
|
| For an introduction to complexity theory, see Arora, Barak
| (2009) (Draft available here
| https://theory.cs.princeton.edu/complexity/book.pdf ); same
| Barak that did the presentation "On the (Im)Possibility of
| Obfuscating Programs" (2001) mentioned in the abstract.
| ihm wrote:
| As mentioned on page 9 of the thesis, IO as constructed in
| the thesis implies IO for RAM machines, so yes you can do
| programs with iteration.
| dmix wrote:
| The next question is why didn't the high end shops spending
| a ton of money and recruiting effort on crypto and state
| malware like NSA .. or Russia(?) figure this out already or
| did they
| whatshisface wrote:
| Because figuring out what a worm does doesn't help if it
| has already done it, and for that matter they're supposed
| to remain undetected. Furthermore people already cannot
| tell whether code has backdoors, or what ML classifiers
| do for that matter.
|
| Unfortunately, the biggest industrial use case is making
| wi-fi routers that are absolutely impossible to install
| OpenWRT on, etc...
| whitemary wrote:
| > _people already cannot tell whether code has backdoors_
|
| I was feeling crazy after reading that.
| tivert wrote:
| > The next question is why didn't the high end shops
| spending a ton of money and recruiting effort on crypto
| and state malware like NSA .. or Russia(?) figure this
| out already or did they
|
| There's no way to know. But the NSA (at least) has a
| documented history of making crypto breakthroughs and
| keeping them secret (e.g. public key crypto:
| https://en.wikipedia.org/wiki/Public-
| key_cryptography#Classi..., differential cryptanalysis: h
| ttps://en.wikipedia.org/wiki/Differential_cryptanalysis#H
| is...).
| withinboredom wrote:
| The fun open secret about working as a researcher for the
| NSA is that even after you leave the NSA, any and all
| research must be approved by them before publishing.
| KMag wrote:
| There are more efficient ways to hide malware from
| current scanners, and on the flip-side, the scanners that
| use heuristics/ML to classify the sequence of system
| calls made by the binary wouldn't be affected by this
| sort of obfuscation.
| x-complexity wrote:
| IMO: Paranoid about the implications, slightly less worried
| about it applying in practice.
|
| As shown by the DRM schemes used in modern games, this type
| of obfuscation comes at the cost of performance: Unless you
| want to compute a sensitive function at the user's end in
| an obfuscated manner, it'd be much simpler to just run that
| function on your end and optimize it in terms of running
| costs & performance.
|
| Such a design would also runs counter to the everything-as-
| a-service model that companies are trending towards, as it
| places more power back at the user's end, even if the user
| can't decipher the obfuscated function's inner mechanisms.
| Such a design would reduce the need to phone home, and thus
| the need for EaaS.
| anonymousDan wrote:
| Would it be possible to use this to obfuscate other
| cryptographic primitives (e.g. a hash function or a
| simple program that checks whether the hash of some input
| equals a hardcoded value)?
| scarmig wrote:
| Can't finite iteration and recursion just be unrolled? And
| storage just considered another part of the input?
| jahewson wrote:
| This is how SMT solvers deal with bounded quantifiers.
| grayhatter wrote:
| In theory? Absolutely; unrolling a loop is exactly what
| it sounds like. Recursion is just a fancy loop. But
| there's a reason no one does that, and why no compilers
| emit that as code.
| User23 wrote:
| Fancy in the sense of being a loop with an implicit
| stack. Or maybe just some registers if TCO.
|
| And yet the machines we can actually build are far closer
| to LBAs than TMs.
| Tangurena2 wrote:
| We already have code that obfuscates itself. And runs
| differently based on whether it is running in a debugger or
| not. This has been the cat & mouse game played by:
|
| virus writers vs anti-virus code.
|
| game hackers vs anti-cheat software.
|
| license checking code vs cheapskates.
|
| Stuxnet.
|
| > _Code where no one can tell if it has a backdoor._
|
| Back in 1984, Ken Thompson wrote _Reflections on Trusting
| Trust_ [0]. The short answer is "no, you can never ever tell
| if it has a backdoor. Ever."
|
| > _The moral is obvious. You can 't trust code that you did not
| totally create yourself. (Especially code from companies that
| employ people like me.) No amount of source-level verification
| or scrutiny will protect you from using untrusted code. In
| demonstrating the possibility of this kind of attack, I picked
| on the C compiler. I could have picked on any program-handling
| program such as an assembler, a loader, or even hardware
| microcode._
|
| Back in the 90s, I was interested in hacking. The sort of
| hacking that starts with "this is the disassembler. Step one,
| hack the trial version of IDA Pro." It was fascinating at the
| time (and bores me now, my punishment for growing up, I guess)
| so I read & did lots of stuff like that.
|
| 0 -
| https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
| hgsgm wrote:
| Obfuscation is itself a malware signature.
| Vervious wrote:
| I mean, the same argument has been applied to other
| cryptographic tools. Why encrypt your messages, unless you're
| sending something sketchy? Why obfuscate programs, unless
| you're hiding something?
|
| Yet I think the utility of encryption is well-demonstrated,
| and not just theoretical. It can be used by good people to
| defend against adversarial intent. And it may well be that
| obfuscation (in its most direct application) has the same
| effect. (e.g. companies sharing proprietary algorithms for
| you to run at home, without revealing the secret sauce; or me
| delegating computation to AWS without revealing secrets)
|
| Note that this is not why indistinguishability obfuscation
| (iO) is a crown jewel, here. Practically, iO is nowhere close
| to obfuscating anything larger than a tiny circuit. But it
| can still be useful to do things like obfuscate secret keys
| when designing cryptographic protocols. Theoretically, iO
| allows us to derive essentially every cryptographic
| primitive, which is why this paper is interesting, and why iO
| is called a crown jewel. And now, we can build iO for the
| first time from well-studied hardness assumptions.
| ilyt wrote:
| > I mean, the same argument has been applied to other
| cryptographic tools.
|
| Intent matters.
|
| > Why encrypt your messages, unless you're sending
| something sketchy?
|
| Because I am sending something private, I can't believe
| people bring this dumbass argument still, and even here.
|
| > Why obfuscate programs, unless you're hiding something?
|
| Why indeed. This one is the red flag, not message in your
| e-mail client being encrypted. Again. Intent, and context,
| matters.
| denton-scratch wrote:
| > and why iO is called a crown jewel.
|
| Ah, thanks. That's far from clear in the article.
| moring wrote:
| > I mean, the same argument has been applied to other
| cryptographic tools. Why encrypt your messages, unless
| you're sending something sketchy? Why obfuscate programs,
| unless you're hiding something?
|
| There is a huge difference: Encryption is used to hide
| something from a third party, while obfuscation is used to
| hide something from the intended recipient.
|
| Or, if you'd like to argue that the intended recipient is
| the computer, not the user: To turn that computer into a
| deputy of the sender, while still formally belonging to the
| recipient.
| consp wrote:
| > while obfuscation is used to hide something from the
| intended recipient.
|
| No. Most obfuscation is done to increase the time needed
| to reverse the source of publicly available programs. Not
| the user (99% of the recipients) but the adversary is the
| intended target. The users are just cought in the
| crossfire.
|
| Unless you consider every user of apps as someone who has
| both the skill and the need to reverse engineer your app.
| Xelynega wrote:
| > No. Most obfuscation is done to increase the time
| needed to reverse the source of publicly available
| programs.
|
| So to stop the intended recipient from deciphering the
| program.
|
| "Adversaries" are the strawman used to hurt legitimate
| customers who are left with black boxes for device
| drivers and no functioning hardware since the
| manufacturers make it impossible to open source firmware
| updates.
| ilyt wrote:
| In case of DRM sure, but there are cases like online
| games where "adversaries" are players (intended users of
| the app) trying to use cheat programs on game binary to
| get an advantage over other players.
|
| I share the sentiment that in most cases it just serves
| DRM vendors and is disservice to users but that's not
| _all_ the cases.
| yjftsjthsd-h wrote:
| > I mean, the same argument has been applied to other
| cryptographic tools. Why encrypt your messages, unless
| you're sending something sketchy? Why obfuscate programs,
| unless you're hiding something?
|
| It's easy to argue that everyone has legitimate interest in
| hiding some things in data, but what would be a legitimate
| case for hiding things in code?
| Brotkrumen wrote:
| "This is a trade secret. We have not patented it, because
| it's so clever and valuable that it needs to be protected
| longer than a patent lasts"
| pxc wrote:
| That remains a fundamentally anti-social motivation...
| Xelynega wrote:
| Except we know(and have example from cryptocurrency) that
| the problems with ownership in real life have little to
| do with cryptography.
|
| The reason coca cola doesn't use Pepsi's recipe isnt
| because mixing the ingredients under heat creates an
| irreversible mixture that you can seperate to find the
| recipe. They don't use pepsis recipe because its illegal.
| Attrecomet wrote:
| That's true for a recipe that was developed in a past
| millennium. Trade secrets are still very much relevant
| for companies that work with more modern technologies
| than soda from before the Great War, and a useful
| protection against competition. Even if you do believe
| that companies within the US or EU wouldn't touch other's
| IP with a 10 foot pole due to strong laws, you'd have to
| be very naive to think this is valid in all parts of the
| globe.
|
| Edit: it's also trivially not true for trade secrets in
| the legal sense -- if you upload your trade secret
| willingly to AWS, it's no longer a trade secret, unless
| you have extra contracts in place. With obfuscation, you
| could skip a lot of red tape to keep it secret.
| liminvorous wrote:
| You can't copyright a recipe, the thing reason it doesn't
| make sense for Pepsi to make an exact duplicate of coke
| is that Coke is better at selling Coke that Pepsi is, and
| it's better for them to be a niche alternative some
| people prefer than to be an undifferentiated
| competititor. Reverse engineering trade secrets is
| perfectly legal if you haven't agreed otherwise.
| andrewflnr wrote:
| Since when is coca cola niche?
| joelfried wrote:
| Making it harder for bad actors to create malware would
| seem like one legitimate case.
| Hnaomyiph wrote:
| Until it's standard practice by all companies to protect up
| under the guise of consumer protection with all closed
| sourced software.
| hulahoof wrote:
| like that time sony gave everyone a rootkit: https://en.wik
| ipedia.org/wiki/Sony_BMG_copy_protection_rootk...
| RockRobotRock wrote:
| similar to starforce for those that don't know:
| https://www.youtube.com/watch?v=p-wyIalhdPU
| jrpt wrote:
| Sure but it's a very weak signal.
| [deleted]
| [deleted]
| Cyph0n wrote:
| I'm sure DRM companies like Denuvo are having a field day.
| vlovich123 wrote:
| If I'm reading Wikipedia [1] correctly, a program that does an
| AND of 32 booleans when obfuscated is 32 GiB. No indication of
| runtime overhead but something tells me it's a large constant
| overhead (if I skimmed the paper correctly, the complexity class
| must be the same).
|
| [1]
| https://en.wikipedia.org/wiki/Indistinguishability_obfuscati...
| sn_master wrote:
| But can it be compressed with something like UPX?
| arsome wrote:
| And can you tell where an operation begins and ends, for
| example, determine inputs and outputs?
| 7to2 wrote:
| Does this mean we will be able to embed private keys and API keys
| in deliverables? (i.e. to cryptographicaly sign artifacts, APIs
| tokens, and other niceties).
|
| Sucks that DRM and user rights violations is about to get much
| much worse.
| throwawayadvsec wrote:
| your API tokens could still probably get sniffed in the
| requests?
| luxcem wrote:
| No because the requests are encrypted (with a public-key
| crypto method for example).
| [deleted]
| EuropeOverlords wrote:
| [dead]
| kevinwang wrote:
| Here's the quanta article referenced by the title:
| https://www.quantamagazine.org/computer-scientists-achieve-c...
| bertman wrote:
| And its discussion from 3 years ago:
|
| https://news.ycombinator.com/item?id=25046738
| eerikkivistik wrote:
| So wait, doesn't this also indirectly imply that we will never be
| able to decipher neural networks of sufficient size for the
| general case?
| hgsgm wrote:
| Trash title.
|
| > established the feasibility of mathematically rigorous software
| obfuscation from well-studied hardness conjectures
| y7 wrote:
| This is not about software obfuscation, this is about
| cryptographic indistinguishability obfuscation (iO). It's
| targeting a different problem -- software obfuscation is more
| about hiding program behavior, whereas iO is more useful for
| white box cryptography, like hiding an AES key.
|
| Maybe you could obfuscate software eventually, but we don't
| have practical efficiency even for tiny circuits. It's a bit
| like saying how fully homomorphic encryption allows you to
| securely run "software" on someone else's computer:
| theoretically maybe yes, but in practice it's used _within
| software_ to run very specific computations.
| qotgalaxy wrote:
| [dead]
| Vervious wrote:
| Why? It's not a trash title. Explain yourself, and give us some
| substance instead of being inflammatory.
|
| Indistinguishability obfuscation (plus one-way functions)
| implies basically every cryptographic primitive there is,
| including public key encryption, NIZKs, and MPC. It gets close
| to giving us FHE (open question, I think). In some sense it is
| a "unifying primitive". Absolutely a holy grail to
| cryptographers, even if it isn't for you.
| denton-scratch wrote:
| The article doesn't explain what "indistinguishability
| obfuscation" does, nor why it is the "crown jewel of
| cryptography".
___________________________________________________________________
(page generated 2023-05-25 23:01 UTC)