ࡱ> &Y(   4 vern.c vern.c,$BibliographyVC(Which side are you? chess.txtDZ0Other Obfuscation Models,uBibliographypv"www.cloakware.com2http://www.cloakware.com/,~Bibliography/ 00DArialngs,(0(z[ 0 DBook Antiqua,(0(z[ 0  DSymboltiqua,(0(z[ 0 0DWingdingsua,(0(z[ 0 @ .  @n?" dd@  @@`` ,$v6     1     $%u * -.02 356 7:3&ABCDEFGH IJ KLM NOQ%$TVWYZ[\]^)`bc 0AA0 f@fV F ʚ;>a9ʚ;g4KdKd@z[ 0p2 p@ <4ddddl 0p, <4KdKdl< 00___PPT10 ``v___PPT9X$CZu~L!$085?  %I.On the (Im)possibility of Obfuscating ProgramscBoaz Barak, Oded Goldreich, Russel Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan and Ke Yangdd   *Theory/Practice  Gap In practice Hackers successfully obfuscate viruses Researchers successfully obfuscate programs [2,4] Companies sell obfuscation products [3]$x ~U 0beuU 0 AIn theory [1] There is no good algorithm for obfuscating programs4x4x4$U 0 Why Do I Give This Talk?(Understand Theory/Practice Gap An example of a good paper An example of an interesting research: shows how to model a practical problem in terms of complexity theory Illustrates techniques used by theoreticians I did not understand the paper. I thought that explaining the paper to others, will help me understand it To hear your opinion (free consulting) To learn how to pronounce  obfuscation BaxsxxasT7 DisclaimerThis paper is mostly about complexity theory I m not a complexity theory expert I present and discuss only the main result of the paper The paper describes extensions to the main result which I did not fully explore Hence, some of my interpretations/conclusions/suggestions may be wrong/incomplete You are welcome to catch me,Fxo Talk StructureObfuscation ConceptA good obfuscator: a virtual black box  Anything an adversary can compute from an obfuscated program O(P), it can compute given just an oracle access to P The weakest notion of compute: a predicate, or a property of P. ~(PP(?0@ Turing Machine Obfuscator :[Functionality property] O(M) computes the same function as M. [Efficiency property] O(M) running time1 is the same as M. [Black box property] For any efficient algorithm2 A (Analysis) that computes a predicate p(M) from O(P), there is an efficient (oRacle access) algorithm2 RM that for all M computes p(M): 8" Z" ZZ  2 #B   >%0Talk Structure  Proof OutlineBuilding E (1)( @Combination Machine. For any M,N: COMBM,N(1,x) M(x) and COMBM,N(0,x) N(x). Hence, COMBM,N can be used to compute N(M).    ,42Building E (2)& NLet a,b{0,1}K Let Note: Da,b can distinguish between Ca,b and Ca ,b when (a,b)(a ,b ) Ea,b=COMBDa,b,Ca,b Remember: Ea,b can be used to compute Da,b(Ca,b) JZZ    C9+ Proof OutlineThe Analysis AlgorithmInput: A combination machine COMBM,N(b,x). Algorithm: Decompose COMBM,N into M and N. COMBM,N(1,x) M(x) COMPM,N(0,x) N(x)). Return M(N). Note: A(O(Ea,b)) is a predicate that is always (i.e., with probability 1) true: A(O(Ea,b)) = A(O(COMBDa,b,Ca,b)) Da,b(Ca,b) = 1 You must provide oracle access algorithm: RM s.t. Pr[REa,b(1|Ea,b|)=1] 1.V:P!" P," P " PP   BB      Y   /    P B:, Proof Outline The Z machine& Let Zk be a machine that always return 0k. Z is similar to Ea,b (COMBDa,b,Ca,b): replace Ca,b with Zk. Z=COMBDa,b,Zk Note A(O(Z)): is a predicate that is always (i.e., with probability 1) false: A(O(Z)) = A(O(COMBDa,b,Zk)) Da,b(Zk) = 0 Pr[RZ(1|Z|]=0) 1 ?. If we show that Pr[RZ(1|Z|]=0) << 1, we are done. p;4 ! CB CCN   b_ hVWhy Pr[RZ(1|Z|]=0)<<1 ?$$$$$$$NLet us look at the execution of REa,b: z(B   ;- Proof Outline"Talk Structure&Modeling Obfuscation>A good obfuscator: a virtual black box  Anything that an adversary can compute from an obfuscation O(P), it can also compute given just an oracle access to P J(xx( Obfuscation Model Space)!TM Obfuscator O(M) computes the same function as M. O(M) running time1 is the same as M. For any efficient algorithm2 A (Analysis) that computes a predicate p(M), there is an efficient (oRacle) algorithm2 RM that for all M computes p(M): " Z" ZZ   #   >)*#Obfuscation Model Space,$TM Obfuscator O(M) computes the same function as M. O(M) running time1 is the same as M. For any efficient algorithm2 A (Analysis) that computes a predicate p(M), there is an efficient (oRacle) algorithm2 RM that for all M computes p(M): " Z" ZZ   #   >)K4Talk Structure/'Other Obfuscation ModelsH30Barak s Model LimitationFVirtual Black Box: Not surprising in some sense (but, still excellent work) Does not corresponds to what attackers/researchers are doing:  the virtual black box paradigm for obfuscation is inherently flawed Too general: obfuscator must work for all programs for any property (Barak addresses this in the extensions) Too restrictive: does not allow to fit the oracle algorithm per Turing machine (does it matter?). tZZZ`ZdZ`dF0Alternative Models Property Hiding Model : for a given property q: (i) q can be computed from P, (ii) q cannot be (is more difficult to?) computed from O(P). Given an algorithm A, and a Turing machine M such that A(M)=q(M), obfuscate M such that [property hiding] for every algorithm A, A(O(M)) q(M) [functionality] M and O(M) computes the same functiont" .1    &BCBB,P;U8Alternative Models (2)Backdoor Model: hide functionality for a single input, change functionality for most other inputs Given a Turing machine M and an input x [obfuscated back door] there exists y such that M(x)=O(M)(y) [non functionality] for every zy Pr[M(z)O(M)(z)] is high6P|" P{$BC B BP" J2SummaryWhat to take home: The gap is possible because: Virtual black box paradigm is different than real world obfuscation. The Obfuscation Model Space . Nice research: Concept Formalism Properties A lot remain to be donereHe0ZU 0zL5 BibliographyB. Barak, O. Goldreich R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan and K. Yang, "On the (Im)possibility of Obfuscating Programs", CRYPTO, Aug. 2001, Santa Barbara, CA. Cullen Linn and Saumya Debray. "Obfuscation of Executable Code to Improve Resistance to Static Disassembly", CCS Oct. 2003, Washington DC. www.cloakware.com. Christian S. Collberg, Clark D. Thomborson, Douglas Low: Manufacturing Cheap, Resilient, and Stealthy Opaque Constructs. POPL 1998.F" S0HL 7  Ro   @ vU 08IU 0K`U 0wU 0/h +3456 7 8 = > ?@ABCDMNOPSP=  ` 33` Sf3f` 33g` f` www3PP` ZXdbmo` \ғ3y`Ӣ` 3f3ff` 3f3FKf` hk]wwwfܹ` ff>>\`Y{ff` R>&- {p_/̴>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>>K0 WO(    6  " `}  T Click to edit Master title style! !$  0 " `  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0P "^ `  X*  0 " "   MSecurity Seminar, Fall 2003  0 "^ `  Z*B  s *޽h ? 3f3FKf80___PPT10.]* Default Design 0 zrD (  D D 0t P    P*   D 0\     R*  d D c $ ?   D 0L  0  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S D 6 _P   P*   D 6 _   R*  H D 0޽h ? 3380___PPT10. ?!4PK0 3+ (  r  S \xq x r  S h` 2  x   < x   +Presented by Shai RubinH  0޽h ? 33___PPT10i.``n*+D=' = @B + K0 tl@(  x  c $Wx `}  x    0sx"`bR  x   S 4_ Ok  x   0x * RB  U 0 Which side are you? $x C U 0B  s *޽h ? 33___PPT10u.. D+D=' = @B + K0 0 $(   r  S $x `}  x r  S Ȕx ` x H  0޽h ? 33___PPT10i.XA8+D=' = @B + bK0  0(  x  c $x `}  x x  c $Lx ` x H  0޽h ? 3f3FKf___PPT10i.i@[+D=' = @B +: K0 P(  r  S x `}  x 2  0;"`rd,$@ 0  <x%1,$ 0 Z Motivation (Theory/Practice Gap)! 2  0;"` n` ,$@ 0  <xuW ,$  0 AObfuscation Model2   0;"` N @  ,$@  0   <Txt ,$  0 DImpossibility Proof    s *|mA ,$D  0"   6HZI>|-qa,$@ 0  <(xr&[ ,$ 0 CTheoretician Track2  0;"` v ,$@  02  0;"`  ,$@ 0  <\xb a ,$ 0 KOther Obfuscation Models   s *|H H ,$D 0  <x} r ,$ 0 CPractitioner Track2  0;"`,$@ 0  <x  ,$ 0 8Summary   "  <GHHņI|M ,$@ 0"  6H@4I|H ,$@ 0 @ BZGFHuIF|$ w H ,$@ 0  <xf =  ,$ 0 LObfuscation Model Analysis H  0޽h ?o       33s)@ TIMING$|8.7|7.8|14.3|24.1#)___PPT10).+[D'' = @B D&' = @BA?%,( < +O%,( < +D' =%(%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*D' =1:B solid*a3>Bfill.type<*D' =1:B true*]3>Bfill.on<*D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D ' =%(D ' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D ' =%(D ' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+x ++0+x ++0+ x ++0+x ++0+x ++0+x ++0+x ++0+x +)  3K0   ` (  r  S P `}      6 "`t2 <$ 0  *n&^n  B8c"`  ,$@ 0 PProg.c  Bh8c"`R bV ,$D 0 S O(Prog.c)    B8c"` <`z ,$@ 0 PProg.c  0q"`<  ,$@ 0  <0 k J ,$  0 7 p(Prog.c)  c $  ,$@  0 @ c $ S,$@  0 @ c $ ,$@  0  6!"`8 ol ,$D 0 4$  6$"`- }3,$@ 0 DInput/Output queries  6("`,  4,$@  0 Z(Code + Analysis + Input/Output queries))H  0޽h ??` 33@ TIMING$|38.9|30.|14.8|4.4___PPT10.p|+G7D' = @B DR' = @BA?%,( < +O%,( < +D' =%(%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*(%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*)%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D~' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D[' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(Du' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D3' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ +  K0 rjL(  Lx L c $z `}    L  <p"`t   *PkK L <ԣ0 i-2Probabalistic polynomial-time Turing machine . -  L <k4 ]!1Polynomial slowdown is permitted " ! K L 0l G  UA Turing machine O is a Turing Machine (TM) Obfuscator if for any Turing machine M: \U@kK L <l 7c  .XPr[A(O(M)) = p(M)] Pr[RM(1|M|) = p(M)]|- 6 L 0k"` l\ ,$ 0 9In words: For every M, there is no predicate that can be (efficiently) computed from the obfuscated version of M, and cannot be computed by merely observing the input-output behavior of M. ^ZJH L 0޽h ? 33 & TIMING |109.___PPT10. !NR+WS;DO' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(+8+0+Ll +  AK0   v (  x  c $P `}   f2  0;"`rdf2  0;"` n`   <huW  AObfuscation Modelf2  0;"` N @    <迷t  DImpossibility Proof R  s *|mA ^"  6HZI>|-qaf2  0;"` v f2  0;"`    <(ŷb a  KOther Obfuscation Models R  s *|H H f2  0;"`  <xʷ   8Summary   d"  <GHHņI|M ^"  6H@4I|H j @ BZGFHuIF|$ w H   <hϷ%1 Z Motivation (Theory/Practice Gap)!   <(շr&[  CTheoretician Track  <ٷ} r  CPractitioner Track  <۷f =   LObfuscation Model Analysis H  0޽h ?o     33___PPT10i.+D=' = @B + K0   P (  x  c $ `}      0uJ e,$ 0 v2. Really? Please provide O."i   0 Jh ,$ 0 x4. I show you a predicate p, and an (analysis) algorithm s.t.: A(O(E))=p(E). You must provide RM: Pr[RE(1|E|)= p(E)] Pr[A(O(E))=p(E)]. i#     b9 &  0 Ju3,$ 0 q5. I choose another machine Z and obfuscate it using O. I show you that Pr[RZ(1|Z|)= p(Z)] << Pr[A(O(Z))=p(Z)]. ri   >V  0"`mJ x1. You say:  I have an obfuscator: for any Machine M, for any (analysis) algorithm A that computes a predicate p(M), there is an oracle access algorithm RM that for all M computes p(M). 3'  ,oD 8XZ  0`@J0 ,$ 0 <3. Given O and a my chosen Turing machine E, I compute O(E).R=i @A @AD  0$J,$ 0 V6. Conclusion: please try another obfuscator (i.e., you do not have a good obfuscator)"WiVH  0޽h ? 331J TIMING.|45.9|3.7|8.5|34.8|27.7 ___PPT10 . !NR+oDs ' = @B D. ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+ ++0+ ++0+  ++0+ ++0+ +  `WK0 T)(  Tr T S 0Z `}   r T S [ :   T <t\p   COMBM,N(b,x)=V   Xr T 02 G T <<^i Q XM(x) b=1  T <h^ NX XN(x) b=0 H T 0޽h ? Sf3f___PPT10i.-+D=' = @B +   аK0 R(  x  c $ `}      <L"`   8   I s   < Ca,b(x)=J ,@ i  I  i  I`r  0i# 8  <|Ź #  B b x=a  <r O I B 0 otherwise l8  0    <   vDa,b(C)=J 2@  0   0`r   0 P   <8? H1 C(a)=b    <P60 B 0 otherwise H  0޽h ? Sf3f___PPT10i.-+D=' = @B + K0   hK (  hx h c $  `}    h 0 uJ e <2. Really? Please provide O. >i h 0 > Jh  N>4. I show you a predicate p, and an (analysis) algorithm s.t.: A(O(Ea,b))=p(Ea,b). You must provide RM: Pr[REa,b(1|Ea,b|)= p(Ea,b)] Pr[A(O(Ea,b))=p(Ea,b)]. ni#     b9/ h 0(& Ju3 q5. I choose another machine Z and obfuscate it using O. I show you that Pr[RZ(1|Z|)= p(Z)] >> Pr[A(O(Z))=p(Z)]. ri   >V  h 0*"`mJ |1. You say:  I have an obfuscator: for any Machine M, for any (analysis) algorithm A that computes a predicate p(M), there is an oracle access algorithm RM that for all M computes p(M). 3'  ,oD 8X h 0Lz@J0  J3. Given O and a my chosen Turing machine E, I compute O(Ea,b). Bi @A @AAA h 0psJ V6. Conclusion: please try another obfuscator (i.e., you do not have a good obfuscator)"WiVH h 0޽h ? 33___PPT10i. !NR+D=' = @B +  yK0 n(  r  S  `}     S t `<$ 0  *eEH  0޽h ? 3f3FKf0 TIMING|30.3|51.8M___PPT10-.l0+&D' = @B D' = @BA?%,( < +O%,( < +D^ ' =%(%(D ' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*-%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*.:%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*:[%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*[p%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(Ds' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*3%(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*4^%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*^%(+8+0+ +$  5K0 #   p (  px p c $l `}  l  p 0kuJ e <2. Really? Please provide O. >i p 0P,k Ju3 q5. I choose another machine Z and obfuscate it using O. I show you that Pr[RZ(1|Z|)= p(Z)] << Pr[A(O(Z))=p(Z)]. ri   >V  p 0"`mJ |1. You say:  I have an obfuscator: for any Machine M, for any (analysis) algorithm A that computes a predicate p(M), there is an oracle access algorithm RM that for all M computes p(M). 3'  ,oD 8X p 0Lk@J0  $|3. Given O and a my chosen Turing machine E, I compute O(E). p?i @A @AA p 0J V6. Conclusion: please try another obfuscator (i.e., you do not have a good obfuscator)"WiV<  p 0 Jhh  .4. I show you a predicate p, and an (analysis) algorithm s.t.: A(O(Ea,b))=1. You must provide RM: Pr[REa,b(1|Ea,b|)= 1] Pr[A(O(Ea,b))=1] = 1. Bi#      ,9AH p 0޽h ? 33___PPT10i. !NR+D=' = @B + `WK0 @P(  r  S Z `}     S p[ `<$ 0  H  0޽h ? 3f3FKf 0 TIMING|41.8|48.2P ___PPT100 .o e++D ' = @B D ' = @BA?%,( < +O%,( < +D' =%(%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*,%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*-x%(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*y%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*N%(+8+0+ +Fc 7K0 ''P5t /'(  r  S w `}   r  S xD!  B  6D8cjj,$@ 0  <z_e,$ 0 5Start  <VMe,$ 0 3Endl D N !j,$D 02  N"`D  XDa,b4rB  BDjJNz D N * ! j,$D 02 + H܀"`D  XDa,b4lB , <DjJNz D N - !1j,$D  02 . H"`D  XDa,b4lB / <DjJNz  NR  0 j ,$D  02 1 H "` R  XCa,b4lB 2 <DjJN 4 6"`v,$D  0 31B 5 6D8c= = ,$@  0 6 <d w8 ,$ 0 5Start 7 <d e8 ,$ 0 3End G 6"` F ,$D 0 :Out n H 0 O ,$  0 When we replace the oracle to Ca,b with oracle to Zk, we get RZ. What will change in the execution?eBCBCK BCKC$B21 I 0|  sL RPr(out =0) = Pr(a query to Ca,b returns non-zero) = Pr(query=a) = 2-kXH$6 #   z SNh  Y <  ,$D 02 Z HH"`Sh  ZkHlB [ <DjJNz D N \  < ,$D 02 ] H"`D  XDa,b4lB ^ <DjJNz D N _  < ,$D 02 ` H<"`D  XDa,b4lB a <DjJNz D N b  *< ,$D 02 c H"`D  XDa,b4lB d <DjJN z iNR  e < ,$D 02 f H"`iR  ZkHlB g <DjJN42 i N"`t ,$@ 0 tZk<  2 k H"` ,$@ 0 PCa,b,  l <,$ 0 j REa,b:B  n < H ,$ 0 ]RZ:> l  NR   j,$D 02  H"` R  XCa,b4lB   <DjJNf o 0"` zf p 0"` HLf q 0"` f r 0"`  s <HZ,$ 0 T3 Inaccurate, see paper.    t <> L ,$ 0 13H  0޽h ? 3f3FKf';` TIMINGD|9.1|23.6|11.5|20.4|10.6|32.8|14.5:___PPT10:.p+W2D7' = @B DN7' = @BA?%,( < +O%,( < +D' =%(%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D ' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<**%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =%( D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*-%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*4%(D' =%(D@' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*H%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*5%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*6%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*n%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*7%(D ' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*Y%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*\%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*_%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*e%(D' =%( D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*b%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*G%(D2' =%(D' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*o%(D' =%(D>' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*p%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*i%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*k%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*s%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*t%(D2' =%(D' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*q%(D2' =%(D' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*r%(++0+ ++0+ ++0+4 ++0+6 ++0+7 ++0+G ++0+H ++0+i ++0+k ++0+l ++0+n ++0+s ++0+t +1 \K0 0 ( | (  |x | c $/ `}    | 01uJ e <2. Really? Please provide O. >i | 04 Jh  Z4. I show you a predicate p, and an (analysis) algorithm s.t.: A(O(E))=1. You must provide RM: Pr[RE(1|E|)= 1] Pr[A(O(E))=1] = 1. i#    ,98v | 0A Ju3 5. I choose another machine Z and obfuscate it using O. I show you that Pr[RZ(1|Z|)= 0]=2-k << Pr[A(O(Z))=0] = 1. xi   b  | 0<|"`mJ |1. You say:  I have an obfuscator: for any Machine M, for any (analysis) algorithm A that computes a predicate p(M), there is an oracle access algorithm RM that for all M computes p(M). 3'  ,oD 8X | 0G@J0  $|3. Given O and a my chosen Turing machine E, I compute O(E). p?i @A @AA | 0LJ V6. Conclusion: please try another obfuscator (i.e., you do not have a good obfuscator)"WiVH | 0޽h ? 33___PPT10i. !NR+D=' = @B +  @rK0   v (  x  c $ha `}   f2  0;"`rdf2  0;"` n`   <PuW  AObfuscation Modelf2  0;"` N @    <t  DImpossibility Proof R  s *|mA ^"  6HZI>|-qaf2  0;"` v   <f =   LObfuscation Model Analysis f2  0;"`    <|b a  KOther Obfuscation Models R  s *|H H f2  0;"`  <   8Summary   d"  <GHHņI|M ^"  6H@4I|H j @ BZGFHuIF|$ w H   <|r&[  CTheoretician Track  <л} r  CPractitioner Track  <ؿ%1 Z Motivation (Theory/Practice Gap)! H  0޽h ?o     33___PPT10i.+D=' = @B + K0    (  x  c $ `}     c $z   *n&^n  B l8c"`|  s PProg.c  Bl8c"`AbV S O(Prog.c)    BT8c"`r<`i PProg.cf  03"`+  < W   KnowledgeL   c $ L  @ c $ S    0 "` z,$ 0 VBarak shows: there are properties that cannot be efficiently learned from I/O queries, but can be learned from the code However, we informally knew it: for example, whether a program is written in C or Pascal, or which data structure a program uses nL  c ${   6L"`'ol  4$   6@ "` }"  DInput/Output queries   6"` #  Z(Code + Analysis + Input/Output queries))H  0޽h ??`   33f: TIMING|21.8|16.6|36.3___PPT10.p|+lWD' = @B DS' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* y%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* z%(+8+0+  + 0 K0    (  r  S * `}   ^B  6D8cFcL^B  6D8ccdG  0,y  ,$ 0 d*Difficulty to gain information from O(P).+%  <t0/rt,$ 0 9 Efficient    <4/ 5,$ 0 ; inefficient    <h:,$ 0 5!Information hidden by obfuscator.   <$> ',$ 0 CSpecific predicate   <BYA,$ 0 @All predicates B  0DjJ @,$@  0B  0DjJd{ ,$@ 02   s *"`2 l $,$@  0  <I ,$  0 HBarak s ModelH  0޽h ? 3f3FKf8 TIMING|5.1|21.8|19.9___PPT10.3@+nD' = @B D' = @BA?%,( < +O%,( < +Ds' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(Ds' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+ ++0+ ++0+  ++0+  ++0+  ++0+  ++0+ +F  vK0    (     s *"`Gj,$D 0x  c $l `}  l    <l"`t  l *PkK  <l0 i-2Probabalistic polynomial-time Turing machine . -   <0lk4 ]!1Polynomial slowdown is permitted " ! :  0k G  DA Turing machine O is a TM obfuscator if for any Turing machine M: \D/kK  <+l a  0ZPr[A(O(M)) = p(M)] Pr[RM(1|M|) = p(M)] |. 6H  0޽h ? 33$ TIMING|13.___PPT10n. !NR+P!wDB' = @B D' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(+', K0 C;P(    s *"`y0 ,$D 0r @ 6G 3f"`k02,$@ 0r  s *"` r8I,$@ 0x  c $eO `   ^B  6D8c 0 ^B  6D8c00   <g   9 Efficient   <pl   ; Inefficient XB   0DjJw B @ 6Do 0,$@ 0  <st,$ 0 Programs  BBu ,$ 0 < All Programs B  0DjJu{ { I,$@  0B @ 0DjJk{ q,$D  0B  6DjJ{ ,$@  0B  0DjJk0{ ,$D 0  0{9 IO  d*Difficulty to gain information from O(P).+%`2   s *"`_9  < HBarak s Model  <L  _Information gained from O(P).&  <l *  CSpecific predicate  <Z- @All predicates   BBPF f ,$ 0 ASpecific ProgramH  0޽h ? 3f3FKft* TIMING|7.9|9.:___PPT10.3@+TD' = @B D' = @BA?%,( < +O%,( < +DT' =%(%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D ' =%(D ' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D ' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(DM' =%(D)' =4@BB8BB%()?)?D}' =.E7 BBBBBWM 1.11111E-6 2.22222E-6 L -0.10295 0.1875 *3>*B ppt_xB ppt_y=@0BBAApBB33SB=<* D:' =A@BB8BB0B%()?)?D' =.I7 BBBBB[M 3.61111E-6 -3.33333E-6 L -0.12136 0.19445 *3>*B ppt_xB ppt_y=@0BBAApBBxBr=<*D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<* %(D' =%( D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+ ++0+ ++0+ ++0+ +> K0 ` @(      s *"`L ,$D 0   s *"`Gj,$D 0x   c $ `}       < "`t   *PkK   <h0 i-2Probabalistic polynomial-time Turing machine . -    <kk4 ]!1Polynomial slowdown is permitted " ! :   0k G  DA Turing machine O is a TM obfuscator if for any Turing machine M: \D/kK   <Hk} ?  0ZPr[A(O(M)) = p(M)] Pr[RM(1|M|) = p(M)] |. 6H   0޽h ? 33$ TIMING|5.9___PPT10. !NR+ÐD' = @B DY' = @BA?%,( < +O%,( < +DT' =%(%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(+s  gK0 r j : (  x  c $$ `}   f2  0;"`rd  <8*3^b  Motivationf2  0;"` n`   <-uW  AObfuscation Modelf2  0;"` N @    <0t  DImpossibility Proof R   s *|mA ^"   6HZI>|-qaf2   0;"` v f2   0;"`     <6b a  KOther Obfuscation Models R  s *|H H f2  0;"`  <`;   8Summary   d"  <GHHņI|M ^"  6H@4I|H j @ BZGFHuIF|$ w H   <P@r&[  CTheoretician Track  <D} r  CPractitioner Track  <Hf =   LObfuscation Model Analysis H  0޽h ?o       33___PPT10i.+D=' = @B +? K0 80'20(  0 10 6TS "` w,$D 0 \Signature obfuscation:8X` 0 s *"` 0 lr 0@ 6G 3f"`0`r 0 s *"` r8x 0 c $lRh `8   ^B 0 6D8c 0 ^B 0 6D8cn00   0 <8\w 7  9 Efficient   0 <dav 6  ; Inefficient  0 < ` x HBarak s Model^B 0@ 6Do 0n 0 <i>t% ProgramsXB 0@ 0DjJ{ ^B 0 6DjJ{ XB 0 0DjJ0{ B 0 0DjJ  ,$@ 0B 0 0DjJ   ,$@ 0B 0@ 0DjJ2   ,$@ 0B 0 0DjJJ  ,$@ 02 0 s *"` ,$@ 0B 0@ 0DjJ2  ,$@  0B  0 0DjJ2 2 ,$@  0 "0 BHpG H "` |$D  0H@___PPT9" @Signature obfuscation: Not all properties Not virtual black box?***8X #0 0t IOa  d*Difficulty to gain information from O(P).+% $0 BB B P < All Programs  %0 <hr  _Information gained from O(P).& '0 <4Z- @All predicates B *0@ 0DjJ H ,$@ 0B +0 0DjJ H ,$@ 0B ,0@ 0DjJ  ,$@ 0B -0 0DjJ HH,$@ 0B .0 0DjJ  ,$@ 0B /0 0DjJ ,$@ 02 )0 s *"`Z L,$@ 0`2 0 s *"` ~ 20 6h p,$D  0 ]Static Disassembly [2]:8X &0 <# Bi  CSpecific predicate 00 BlGXHR p|$@ 0H@___PPT9" OStatic Disassembly [2]: Not all properties Not difficult Not virtual black box?*888XH 0 0޽h ?/ "000 3f3FKf5&@ TIMING$|4.8|31.4|91.|24.8%___PPT10%.3@+-)D$' = @B D<$' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*10%(D-' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* 0%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*"0%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*20%(D' =%(DT' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<**0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*)0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*+0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*,0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*.0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*/0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*-0%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*00%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*&0%(++0+10 ++0+"0 ++0+20 ++0+&0 ++0+00 + `cK0 p0(  x  c $ `}   x  c $ `  H  0޽h ? 3f3FKf___PPT10i.T+D=' = @B +  0 K0 @%(  r  S  `}      6 "`]l   *eE  0l"`G @ ,$ 0 qVirus Signature Obfuscation A(M) = q(M) = substring of instructions inside M O(M) does not contain this substringXxVx &!#Ln  02"`< p ,$ 0 TStatic Disassembly A(M)=(particular) Dissembler q(M) = A(M) 90% of the instruction in A(M) are different than the instructions in A(O(M)) ~xxx ( 0XnH  0޽h ? 3f3FKf0 TIMING|48.4|61.4T___PPT104.@96+o-?D' = @B DS' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(+p+0+ ++0+ + 0 K0 0n(  x  c $> `}      6R"` `^  *eEH  0޽h ? 3f3FKf0 TIMING|48.4|61.4___PPT10i.@96+D=' = @B + K0 `0(  x  c $X `}   x  c $Y `  H  0޽h ? 3f3FKf___PPT10i.Y+D=' = @B + K0 F(  x  c $\_ `}     c $b ` l "p`PpH  0޽h ? 3f3FKf___PPT10i.ʵp(+D=' = @B + 0 \TH(  HX H C D   T H S D 0l  TL___PPT9.&  Purpose of the slide: To illustrate the gap between theory and practice. To illustrate the modeling question What you talk about? Try to decide whether there is or not We need to understand: obfuscation, and good, and program. Transition: So the main purpose of the talk is to try and to understand this  gap between practice and theory, however there are other reasons for which I give this talk. @b" bH H 0޽h ? 3380___PPT10. ?! 0  p(  pX p C D     p S D 0   Why this is a good definition: Because it means that there is no analysis algorithm that can find something that I cannot find by just running M. H p 0޽h ? 3380___PPT10.p]W! 0 `X0(  ^  S D   R  c $ D 0   Why this is a good definition: Because it means that there is no analysis algorithm that can find something that I cannot find by just running M. Transition: How can we prove that TM obfuscator does not exist H  0޽h ? 3380___PPT10.p]W$ 0 p$*(  $^ $ S D    $ c $)D 0    But there is another weird thing that I do not fully understand 1. Why cant you adjust the oracle access algorithm to a specific M? H $ 0޽h ? 3380___PPT10.p]W3 0 LC(  LX L C D    L S  $D 0   E1Transition: OK, so what are we going to do today?H L 0޽h ? 3380___PPT10. 0  P(  PX P C D    P S 3D 0   Transition: So let us start with one of the reason for this talk: how to you take a practical concept of obfuscation and expresses it in theoretical terms. H P 0޽h ? 3380___PPT10. x2c 0 0T(  TX T C D    T S ND 0l  TL___PPT9.&  You talk about: First step: define the concept of obfuscation. What is obfuscation? Here is the model barak came with. We need to understand what he means by (I) compute (ii) oracle access Compute Oracle access In words What is important to take from here? Transition: (i) repeat the concept of a good obfuscator. So, we have the model of a virtual black box, the next step is to formalize it or express it in terms of complexity theory so we will be able to say something about it. " " "   ag~H T 0޽h ? 3380___PPT10. P!w 0 @X(  XX X C D    X S RD 0   7Transition: What we did till now? (i) define the concept of obfuscation, (ii) formalize the concept. So now we have a well defined goal to show that such obfuscator does not exit. How we are going to show that? We are going to take the definition and show that there is no obfuscator with all those properties 681 H X 0޽h ? 3380___PPT10.#PL  0 -%P\(  \X \ C D   % \ S bD 0   Enter: what it means that you have a good obfuscator? Transition: So you say you have a good obfuscator, and you give it to me. Now let see what TM I choose to obfuscate.H \ 0޽h ? 3380___PPT10.#kh 0 ``x(  `X ` C D    ` S jD 0   zEnter: The E machine that  i choose is very simple, but it takes some symbols to explain, so if you get confused by symbols just think about what the machine is suppose to do without the formalism behind. Transition: so we have a machine that is a combination of two machines and can be used to simulate either one of them. Now let us see the particular machines M and N that I use inside E. HlH ` 0޽h ? 3380___PPT10.Hj$o 0 pd(  dX d C D    d S zD 0   m Transition my E machine is a combination of D and C. What to take out is that D can distinguish between Cs. H d 0޽h ? 3380___PPT10.I`~+ 0 91l(  l^ l S D   + l c $DmD 0   Enter: what it means that you have a good obfuscator? Transition: So you say you have a good obfuscator, and you give it to me. Now let see what TM I choose to obfuscate.H l 0޽h ? 3380___PPT10.#kJ, 0 tZ(  t^ t S D    t c $HD 0   PEnter: So let us see again where do we stand in the proof. Transition: So now I need to show you another machine Z such my analysis algorithm compute one value and yours oracle access algorithm computes another one. I will call this machine the Zero machine denoted Z. $H t 0޽h ? 3380___PPT10.#k 0 x(  xX x C D    x S еD 0l  TL___PPT9.& EYou talk: Simple, replace Let us see what is the value of the predicate our analysis algorithm computes Now we need to understand what the oracle algorithm answer is Transition: We are going to show that the probability that the PR[] is false is very low. How we are going to do so? We are going to compare the execution of Rz and Re and to show that they must be very similar, and if they are similar the output should be similar.@ "   FjH x 0޽h ? 3380___PPT10.KPJ >- 0 me(  ^  S D   _  c $D 0   Enter: what it means that you have a good obfuscator? Transition: So you say you have a good obfuscator, and you give it to me. Now let see what TM I choose to obfuscate. This conclude the theoretician track of the talk. H  0޽h ? 3380___PPT10.#k 0 NF(  X  C D   F  S D 0   Transition: Barak s obfuscation concept seems somewhat unfair. In particular in the light that there are many other possibilities for defining obfuscation. Let us try to visualize the possibilities for obfuscation H  0޽h ? 3380___PPT10.M0৏  0 NF(  X  C D   F  S 4D 0   Transition: so, we have the first view of barack model in our obfuscation space. Barak s model set very high restrictions on the concept, or definition, of obfuscation. But, what is more interesting is that its formalism put even more restrictions on the concept of a good obfuscator. Let me remind you what a good obfuscator is.,*!H  0޽h ? 3380___PPT10.NJc 0 s(  X  C D     S D 0   u?Transition. So we have defined teh algorithm and the predicate.H  0޽h ? 3380___PPT10.f] 0 %(  X  C D     S XD 0   'Transition What we have showed? We have showed that the execution of the algorithm with must be very similar to the execution of the oracle with E. This means that the output shoe be the same, this means the the output will be 1 and not zeroH  0޽h ? 3380___PPT10.i` 0 c[(  X  C D   [  S D 0`  H@___PPT9" In summary: We saw a concept. We saw a formal definition. We saw the impossibility of an obfuscator according to this definition. Transition: What are we going to see now? We are going to examine whether the concept of the obfuscation barak defined is what people are using. < v" " %H  0޽h ? 3380___PPT10.jPs4 0 .&(  X  C D   &  S D 0   Enter: so we have a picture where Barak s model sits inside the obfuscation space. Transition: What we want to see now is where real-life obfuscator position themselves with respect to this model. "H  0޽h ? 3380___PPT10.k<J' 0 Z(  X  C D   |  S |D 0n  |VN___PPT90( dYou talk: Signature obfuscation: Assume that you wand to check the quality of your obfuscator according to the virtual black box model: then here is the position. But I believe that the more interesting case is whether you want to measure the quality of an obfuscator using the virtual black box model. Barak proof is centered around properties that (I) cannot be computed from I/O, and (I) can be computed from the program. The signature obfuscator is centered around a different question: (i) I know that I cannot compute the property from I/O, (ii) I only care whether you can compute the property from O(M).F " C" C00H  0޽h ? 3380___PPT10.bXr$`.Yui:qlv0#sc% (  2/0Ue"&(P1!M/oi3' G=Lmb8FHTJp[fyS07 s5? UOh+'0 hp   Slide 1 shai rubinhai shai rubin37iMicrosoft PowerPointP@D@`( @| Gg  0  3-- @ !--'@Arial-. 02 }Security Seminar, Fall 2003      ."System-@Arial-. 2 On the (/""".-@Arial-. 2 Im)possibility3""".-@Arial-.  2 of ".-@Arial-. %2 Obfuscating Programs/""""")"""3.-@Arial-. 2 4Boaz e .-@Arial-. 2 48Barake .-@Arial-.  2 4, .-@Arial-.  2 4Oded.-@Arial-. 2 4 Goldreichi .-@Arial-.  2 4, .-@Arial-. 2 4Russel.-@Arial-. 2 \ Impagliazzoi .-@Arial-. 2 \T , Steven z   .-@Arial-. 2 \Rudich.-@Arial-.  2 \@, .-@Arial-.  2 \RAmit .-@Arial-. 2 \Sahaih.-@Arial-.  2 \, .-@Arial-. 2 \Salilh.-@Arial-. 2 VVadhan.-@Arial-.  2 and  .-@Arial-.  2 Ke.-@Arial-.  2 EYang.-@Arial-. *2 jPresented by Shai Rubin    .-՜.+,D՜.+,p    On-screen ShowUWsA #Arial Book AntiquaSymbol WingdingsDefault Design/On the (Im)possibility of Obfuscating ProgramsTheory/Practice GapWhy Do I Give This Talk? DisclaimerTalk StructureObfuscation ConceptTuring Machine Obfuscator Talk StructureProof OutlineBuilding E (1)Building E (2)Proof OutlineThe Analysis AlgorithmProof OutlineThe Z machineWhy Pr[RZ(1|Z|]=0)<<1 ?Proof OutlineTalk StructureModeling ObfuscationObfuscation Model SpaceTM Obfuscator Obfuscation Model SpaceTM Obfuscator Talk StructureOther Obfuscation ModelsBaraks Model LimitationAlternative ModelsAlternative Models (2)Summary Bibliography  Fonts UsedDesign Template Slide Titles 8@ _PID_HLINKSA*vern.c279,16,Bibliography chess.txt 310,29,Other Obfuscation Models309,29,Bibliographyhttp://www.cloakware.com/309,29,Bibliography"_ shai rubinshai rubin  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)Current UserSummaryInformation(PowerPoint Document(DocumentSummaryInformation8