Hello and welcome to my talk about I'm at our more curtain My name is Rene Frank Ruhr and I'm going to tell you in the next minutes a little bit about Exploitation and especially about how to bypass different mitigation techniques of emet. So let's have a look at the plan for the day First of all, I will introduce give you a very short introduction about my person and my company And after that we come to the basics chapter where I'll talk about different mitigation techniques like data execution prevention Or address based realization from current operating systems and how we can bypass these mitigation techniques I will also introduce the firefox array reduce write vulnerability Which I will use during this presentation to show you all my bypass techniques after that we come to the first emet related chapter So for everyone who doesn't know emet is the enhanced mitigation experience toolkit from Microsoft Which is an application which can be used to further harden your operating system So if you install it you can add additional protections through a running application to protect against memory corruption vulnerabilities The first step for my bypass techniques is always to find emet delaying memory So the first chapter is about how we can do this then I will come to a chapter about advanced code reuse and After that we talk about the different mitigation techniques So emet consists out of many many different protections and today We just have time to talk about some of them So I focus on the return on the programming protections and how we can bypass them and on the expert address table access filtering protection At the end I give you some final thoughts and talk a little bit about the other protections And I will also give you a comparison between the different emet versions So basically I have developed all my bypass techniques for emet 4.1 because it was the current version Now we have emet 5.0 5.1 and 5.2 And I will show you how much effort it was to migrate my exploits and my bypasses Yeah, as already mentioned my name is Renny Frank Rubber. I'm working a second site since about three years as Security consultant and penetration tester. I wrote my bachelor thesis about exploitation and later found out that this is so a huge topic so I just Used emet as the new topic and broke my bachelor thesis now about emet So if you want if you're interested you can just drop me a mail and I can forward you my bachelor thesis It has more details than I can present you today Also contributing at Capture the Flex. So for example is the VONU team Maybe you know us from the ICTF or DEFCOM CDFs and of course because I'm a penetration tester My interests are web application security, reversing and stuff like that It's just one quick slide about our company second site We have a team of over 50 security experts. So really persons who are doing active penetration testing and Have projects all around the world and I think the most important part for you is that we are currently hiring So if you're interested just drop me a mail In my opinion Exploitation 15 years ago was quite easy. For example, if you have a stack-based buffer flow You just had to pad until you reach the return address Overwrite the return address with some address pointing again to the stack for example hard-coded address and Place your own shellcode there on the stack in front of a nob slat and everything would be executed and everything would work So I think developing such an exploit was possible to meet in five or ten minutes Nowadays everything becomes harder. So first of all vulnerabilities are harder to find so there are no low-hanging fruits And then you have many many different protections there So in the picture you see here on the left side some of them And the two biggest ones are here data execution prevention depth and address base your organization ESLR because in my opinion these two protections together are the hardest part to buy bus nowadays So each protection on its own is quite simple to buy bus, but if both there, it's quite hard The idea of data execution prevention is that data should just be marked as data So it should be just read and write table, but not execute table So if you store something on the stack or on the heap you cannot execute it So it cannot execute the tag as applied code and The idea of a dress-based organization is that everything every addition started a randomized address So even if you can store your own code on the stack or on the heap you do not know where it is Exactly, so you don't know Which address you use when you override the return address because you don't know where your data is and Here you see why it's so hard to buy bus both protections together So the typical way to buy bus data execution prevention is to use a technique which is called a return on a data programming so instead of Jumping or returning to your own data to your own code You are returning to already existing code and you're chaining the already existing code together to build a new logic For example logic to disable data execution prevention And here's the problem if address-based realization is also there You do not know where the already existing code is stored because it's always loaded at a random address And that's the reason why it's so hard to buy bus both protections together So the typical way is that you first buy bus address-based realization For example if you build an information leakage vulnerability then leak the base address of some loaded module and after you know the base address You can build a rob chain on top of this module and abuse the already existing code You will see this a little bit more in detail in the next slides when I talk about Firefox vulnerability. I Have chosen this vulnerability because of several reasons. So first of all the array reduce write vulnerability is from 2011 So it's a little bit older which means I can show you the exploitation code here And the other reason was it's I think it's a very very interesting vulnerability It works the exploit works reliable against all kinds of operating systems You can bypass address-based realization and data execution prevention. You're not using any kind of hip spraying So one idea to bypass address-based realization is that you can just spray your own data to complete memory So if your own data is at the complete memory You can just use any address because you know your data will be there So this is one idea to buy this address-based address-based realization But the problem with this approach is that you would freeze the browser because you're spraying to the heap and this would freeze the browser for five or ten seconds and In this case if the victim goes to my website, he really sees nothing So there's no spraying no freezing the browser would not crash. Everything looks like a normal web page Unfortunately, I don't have enough time to talk about talk about all details today I think you can have a look at this great talk by Fiumbe Howard Davis You can just Search for this on YouTube to find that or you can just read my bachelor thesis where I give more details Today I can just give you a quick overview about this vulnerability To understand this vulnerability we first have to discuss the reduce function So for everyone who doesn't know the array reduce function can be used to invoke a callback Function on all elements of an array. So let's say the callback function is a print function You would just go to the first element So element with index zero and called a callback function, which is print the print the first element Then go to the next element make the same print the next element and so on until you print the last element and Array reduce right from that Just goes from the right to the left. So it starts with the last element So this element length minus one because we start counting with zero and then prints length minus one The element at length minus one then prints length minus two and so on until it reaches the element with index zero and You see here the problem because in JavaScript you can set the length field to any value Which you like so for example, I can set the length field here to a very huge value Like C zero zero zero zero and so on and the problem is That index is declared as a signed integer That means index can wrap around to negative number and this is exactly what happens So I can set index to a negative number and this allows me to bypass the check if I'm inside the array Inside the scope of the ray. You see this a little bit better on the next slide So the green block here would be my array This has a capacity of six elements and if I try to access the element with index zero It would just say zero is smaller than six. This is allowed Same applies for the last element so five is smaller than six This is allowed if I try to access something outside the scope like element with index 10 This is not inside my array. So this would be not allowed and The problem is with this vulnerability inside the array reduce write function I can wrap the index to negative number and this negative number would always bypass the check if I'm inside the array So I can access memory Or space in front of my array which is under my control So you see here Some internals of the array. So if I'm allocating an array inside JavaScript in Firefox I would end up with this data structure here So I have some fields describing the array Then if I store something at index zero, it would come up here inside this green array here Every data entry consists out of four bytes for the data and four bytes for the data type So let's say I'm storing an integer value inside the array at index zero It would just say here it's an integer and here would store the integer value If I would store and string it would just say here It's a string data type string and here I would Store a pointer to the string data structure and so on same applies for Objects or something like that If you store something at index one it would come here But you see here this green array has a fixed size for example I can just store here ten elements, but in JavaScript I can store an arbitrary number of Elements inside an array that means if I'm trying to store more elements than there is space for it It would just reallocate this green array So it would just make here a new allocation, which is bigger for more space and For that we have the slots array pointer So typically this pointer points to the start of this green array here But if it's going to be relocated It would just be updated to point to this new location and every stuff from this green array would be copied to this New location and here I have more space to fulfill my request and Exactly this I can abuse during my attack. So what I'm doing is I just have relocated here The slots array I have forced a relocation so that the space here is exactly five hundred twelve bytes big And just before making this relocation I make many many allocations of the same size which allows me to control the memory in front of it So I'm just making many allocations to fill the holes in the hip memory and after that to make the relocation Which means I have full control over the memory in front of this green slots array So if I'm now Executing the array reduce write function and with a length value of C 0 C 0 and so on it would just Use the index minus one so it would just use the memory in front of it Which is under my control and here you can just say Can just set here the values to Something which I like in this case. I have just set the data type to an To to a string so in this case f f f f 0 0 0 5 so the 0 5 says it's a string That means the first the word is interpreted as a string pointer I can then just say the string pointer just points again to my own data and Specified their the string for example, I can say the start address of the string is now the start address of the memory Which I want to read so now have the ability to provide an address and read from that address So you can now read anything from the memory space of the running application You see here the implementation of it. I think I just go very quickly over it So for example, you see here setting a data type and here is the stuff for the for a string object You see here how I set the length field and With this line, I'm executing the reduce write function providing here the callback function So this is the function which will be invoked for all elements. This is exactly this one here I'm just checking here if the current element is really of type string If not, I know there is something wrong and if it's really string I just set the variable here so an exception because I do not want to iterate over all elements I'm just want to exit the reduce write function. I'm catching here at the right side This exception and then just return the string and I now can read from the string So now I have the ability to read any memory in the memory space The next step is that we want to get code execution You can easily do this by changing the data type from a string to an object So we know at the start of every object. We have here a pointer to the virtual table and inside this virtual table We have pointers to virtual functions and For example, here's the type of function pointer. So if you go back to the last slide If the variable current would be of type object I would invoke here is this line the type of function of this current element So what it would do? It would just go to the start of the current element Follow the virtual table pointer then add the relative offset here inside to reach the type of function and then execute this function And since I have full control over the pointer to the object I have full control over the pointer to the virtual table I can just let it the virtual table point to my own data That means I can control all the function pointers inside this virtual table and let them point to my own shell code In my attack, I'm not using the type of function I'm using the set element function here instead because it has some benefits because later I will modify the stack pointer Which means after execution of the shell code the stack point is wrong If I then just return the firefox will crash because it could not find the stack anymore and the set set element Pointer function pointer here has the benefit that if I'm using this one It it stores the old content of the stack point and some register That means I can restore the stack pointer after execution of the shell code Which means I can prevent firefox from crashing. So this is the reason why I've chosen here another Function pointer you see here how the attack works So it's the same again. I just changed here the data type or to 0 7 which is now object That means the first deal is integrated as an object pointer here. I'm following the virtual table pointer This stuff here is the offset inside the virtual table and here the set element pointers just pointing again to my own data And then I just execute my knob sled and my shell code and after that I have here The opcode C3 which is just a return some just returning from the set element function and firefox just continues to execute after my shell code is executed This attack here has one problem It would just work against very old operating systems like windows 6b sir respect zero systems In your systems, we have data execution prevention and that means we first have to bypass data execution prevention So typically the blue mark memory here is stored on the heap and a data on the heap is not marked as executed But so I cannot execute the shell code because it would just segmentation fold So the next step is that I develop a rob chain a return of the programming chain to disable data execution prevention first and Here we have another problem Because if I'm now let the function point the point to any code already existing code Then the instructions would be executed and then I come to a return and the return takes the return address from the stack and jumps to this address or Returns to this address and the problem in these cases I do not have control over this return address because it takes this value from the stack pointer And the stack point is pointing as the name implies to the stack. I only have control over stuff from the heap here It's on the red part. So my task is that I find a rob gadget which just shifts the stack pointer To this attacker controlled memory location. This is the first instruction with the first gadget So to find such a gadget I have to look at the Firefox module you see here. I Can find their jump instruction So if you jump and then put to pop instructions and then a return and this jump instruction consists out of two bytes So the first byte is the opcode for the jump and the second byte is the relative offset and This return did a programming. I can just jump into the middle of this instruction So the dislocation here and reinterpreted as a new instruction so I can bring new instructions inside the module but just Jumping into the middle of one instruction. So if I now re-interpret this one here you see C9 is now integrated as a leaf instruction and leaf is exactly doing what I need to do So it just takes the base pointer value and moves it into the stack pointer and the base pointer is just pointing to my Own attacker controlled memory and that means it's exactly doing what I want to do I see I'm very late in time. So I'm go very quickly over this stuff here This is a quick digression. The problem is I have the task to find a gadget Which has the behavior to take the base pointer value and move it into the stack pointer and you see here I've many many different possibilities many many different instructions which can do this and I just Generated a catalog of all the existing code which I can use and then search inside this catalog if one of these instructions is there And this stuff is very time-consuming because if I don't find such an instruction I have to think about another instruction which has the same behavior and as you can think of this is very Very time-consuming and very very error-prone So what I was doing is instead I was using PI Emo So just make a catalog of all existing gadgets which I can use and then I will emulated the gadgets again and again for different starting register values and Then I stored the behavior of this gadget in a database which allowed me to make behavior-based searchers So I can now make searches where I say give me a gadget with this the behavior take the base pointer and move it Into the stack pointer, but don't modify the eax for cases or something like that, and this really Helped me a lot. So this seat just here a very quick output of the program, but I think I skip this one here And I'll come to the first emmett related chapter. It's about finding a material in memory So if you start emmett the enhanced mitigation experience toolkit You will end up with a user interface like this and the lower part you see the running applications and which are Protected by emmett so in this case the firefox application is protected you see here The global operating system wide protectors like data execution prevention and address base levelization and if you click the apps button You see the pair process mitigation techniques So in this example have enabled all mitigation techniques for firefox and if I now start my firefox exploit you would see that it just crashed and At the right bottom you see emmett has detected an attack is ongoing So in this case it was emmett 5.0 the current version is 5.2 I will talk a little bit later about emmett 5.2 But just remember for the next slides that the stack pivot mitigation technique detected that an attack is ongoing Before discussing different bypass techniques. We have to do some general considerations So what we really want to do is we want to protect against real world attackers And for me that means we have to think like a real world attacker and what are the goals of real world attackers? So first of all, I want a reliable bypass technique. So if 100 persons visit my website I want that 100 persons are infected So that means my bypass techniques should work against all versions of emmett So like emmett 3.5 4.1 5.0 and so on or if emmett is not installed And it should work against all operating systems like windows xp windows 7 and so on but that means I do not want to hard-code any system codes or stuff like that because system code numbers change between different versions of Windows and The nice to have thing is that the bypasses should be easy to reuse So for example if I spend two weeks to implement my bypasses for the Firefox vulnerability and one month later I found a Vulnerability in Internet Explorer. I just want to make copy and paste and everything works again and This last thing brings us to the idea that we built everything on top of emmett So emmett works by injecting its own library into all Protected applications and then it can hook critical functions and execute some checks before executing the critical function And you see here emmett is a very good target to build all bypasses on top of it because If the application is protected by emmett, we know emmett is there and that means we can easily reuse the code So it's always there regardless if you attack Internet Explorer flash or Adobe reader or something like that Other researchers for example researchers from offensive security also implemented some emmett bypasses and for their approach they also required that they find emmett delay first in memory I can really recommend that you have a look at these three very good blog posts for offensive security I will later come to their technique what they are doing But in their attack they just assumed that one of the attack modules is importing the function getModuleHandle So what they were doing is they just executed the getModuleHandle function with the argument emmett and the function would just Return the image space of emmett But for my vulnerability for the Firefox vulnerability This was not possible because the getModuleHandle function was not imported by one of the modules So I had to develop my own approach here and I called this approach the hook approach and To understand this we have to understand how emmett works with the hooking of critical functions So as already mentioned emmett works by hook and critical functions like virtual analog or virtual product because they can be used to disable data execution prevention or winexact because it can be used to Execute additional to execute applications or load library because you can use load library to load additional modules from UNC paths or from window shares This can also be used to bypass data execution prevention and address business organization And for example what emmett can do is it can add a check if the stack point is correct This is exactly the stack pointer mitigation technique which you saw on the picture before which mitigated my attack So in my Firefox exploit I just shifted the stack pointer from the stack to the heap because I only have control over stuff on The heap and emmett is exactly checking this because it checks if the stack point is pointing to the stack But in my case it's pointing to the heap and that means emmett can Detect it and attack is ongoing because the stack point is just wrong You see here how the hooking works. So this is the implementation of virtual product This is just a forwarding execution to another module But this is the unprotected version and if I protect now this function with emmett It would just replace the first bytes Here with a jump so with the hooking code to its own code and if you follow this code You would end up with this code which is allocated by emmett And it would just go here downwards And make here a final code to emmett delay so You see here something other important the third push value this one here is pointing to this location down here Which is exactly the last Start the original starting bytes instructions of the function which was hooked by emmett So because emmett has replaced the instructions with its own hooking code You have to store the old instructions somewhere in memory and this is exactly a dislocation and What I'm doing now is to find emmett delay memory is I just go to one of the critical functions Following the hooking code to come to dislocation here Then I'm just going downward here for example is a relative offset and Here I have a call inside emmett delay so I can just extract this value here I know this one is pointing inside emmett delay And then I can just go downward until I find the bee or dos header and then I know the image space of it so you see here a big summary about this attack and Here is the code implementation for this but you see here This is not so good because I have here hard-coded values For example, this is the relative offset from the start of the hooking code to the final call For different emmett versions because they change But this is not good because at the current stage I do not know which emmett version is there So my exploit would just work against one specific emmett version, which is very bad To overcome this problem, you can use that once code reuse technique which I will introduce in the next chapter So with the return of data programming We are reusing already or abusing over existing code and in the case of a browser or PDF reader We can do better because we know that there must be code related to JavaScript for example handle strings So what what we can do is you can just write a very very short Rob chain and this Rob chain just manipulates the data structure Then we are returning to JavaScript code and then inside JavaScript is just working with the manipulator data structure Which allows us to implement everything in JavaScript, which is much easier than implemented in a Rob chain I later found out that this approach was already found found by young you who Described it last year at Kansas Quest. So I can really recommend that you have a look at this great talk Here are some examples what we can do So one example is that we can just manipulate the starting address of a string and let the string point to the hooking code So the start of the hooking code. So that means I can now Implement the parsing of the hooking code inside JavaScript, which is very easy Another example is that I can just modify the start address of an array and let the Start address the base address of the array be on the stack So that means inside JavaScript I can now copy everything to the stack which is very good because it can be used to bypass the stack view of mitigation technique and a third Example which is very useful is that I can just say the start address of a string is exactly the start address of the Code section of one of the load up modules for example, I'm a delay and the length of this string is exactly the length of this code section so now have Code section and my string is exactly a word and then I can use search functions from this string to Dynamically find me Rob gadgets So you can just say inside the string find me the offset for the opcode for pop eggs instruction and a return this means My my attack would just work against all versions of Emmett without the requirement that I change anything So if Emmett updates to 5.3 or something like that my exploit still works because it dynamically finds everything which it needs Which is a very cool technique So you see here just the JavaScript implementation of it So I'm just saying here inside JavaScript leave me the starting bytes at virtual a lock Which is a critical function and then I just verify inside JavaScript is the first byte 8b Which is a move instruction then I know it's a standard prologue which means Emmett is not there So it was not hooked so I can run the exploit without Emmett bypass us If the first byte is E9, which is a opcode for jump I know the function was hooked that means Emmett is there and that means I have to find the call Instructional to get the point that I'm a delay that means I'm just looping here until I find E8 Which is the opcode for the call Instructional If it's not E8, I'm just always adding the size of the instruction So I say if it's this opcode it has the size of this if it's this opcode It has the size of 5 and so on until I find the call and as soon as I have the call I can extract the image space of it and read from the PE header At this stage I just read and check some field and the timestamp field and based on these values I can then identify the exact version of Emmett In this case 4.1 or 5.0 and based on the Emmett version I can then apply different Bypass techniques So at the current stage I know if Emmett is there or not and I know the exact image space of Emmett And I know the exact version of Emmett and now come to the different protections So to bypass the return of data programming protections I have three different possibilities So first of all I can bypass each protection on its own so there are five different protections So I can just look at every protection and see how it works and then think about a bypass How can bypass it? So this is described in the paper Bypassing Emmett 4.1 by Chatti Mott But another good idea is was developed by Offensive Security So they found out that there is a global flag inside Emmett DLL and if this flag is set to false All protections are just disabled So what they were doing is they just wrote a rob chain which found this global flag Disabled it and then all protections are just disabled With the release of Emmett 5.0 Emmett tried to protect against this attack by encoding the pointer to this global flag But of course this didn't work because it's quite easy to decode the pointer and with the release of Emmett 5.1 They implemented the approach which I suggested They now moved this global flag to a read-only location because if it's read-only cannot override the flag Which means you cannot apply this technique anymore because you have to first make the location right table But that means you have to first bypass all protections And there's also another approach which works by using the system codes so the problem is that Emmett is completely in user space and If I'm making direct system codes to the kernel Emmett has no possibility to be in between of this and add checks So if I make direct system codes, they cannot do anything about it But the problem with this is that hard coding system code numbers is bad because they change between different Windows versions But we have a good way to come around this to make it very reliable But I come to this later and I'll talk about the five different rob protections And how they can be bypassed so the first protection is very simple. It's load library protection It just says every time if load library is cold It just checks if the first argument is a UNC path so a path to attacker supply chair and If it's the case it just forbids execution But in my case I didn't head to bypass this protection because I'm not loading any additional modules from attacker supply chairs But if you want to see Bipers you can have a look at this paper by biasing all of the things by a room Portnoy But I think his approach just work against Emmett 3.5 But I think it's not too hard to find a bypass for current versions of Emmett Another interesting rob protection is mem protect. It just says that it's forbidden to use functions like virtual Protect or virtual a look to make the stack executable because the stack should just contain Data and that means the data should neither ever be executable and to bypass this one It's quite simple. We can just make another location executable. So for example, I'm making the heap executable instead But this means we have to modify our rob chain. So typically we as exploit up developer are Quite lazy. So we're just using a tool such as Mona, which is a plug-in for immunity bugger Which generates us the rob chain. So in this case this is a rob chain, which was automatically generated by the mona plug-in and I don't want to go into all details here But it's using the push ed instruction to call the virtual a lock function And this instruction would push all the arguments to the stack Which means it would just make the stack pointer executable That means it would just make the stack executable. But in my case, I want to make a Location executable, which I can choose That means I have to write my own rob chain. So what I'm doing instead is I'm using here a push instruction stat Which means I can supply here an address, which I like. I Will talk about this rob chain later a little bit more detail The next protection we already heard about this one. It's a stack pivot mitigation technique So this one just checks if the stack pointers pointing to the stack and not to the heap So in the case of my Firefox exploit I shifted the stack pointer to the heap Which means it just detected this attack and to bypass this one We can just copy everything from the heap to the stack and then execute everything on the stack. So you see here This is the rob chain which implements this attack. So I think I will go very quickly over the rob chain here So typically the stack pointer is pointing to this location here That means as soon as they come to a return it would take take this address here as new return address At this address we have stored this instructional So it would execute pop ex so the stack pointer is now pointing to this location here so it would just take this value here and Move it into the eggs then we come to the return Now the stack pointer points of this location here. So we would now start executing this instruction The instructions started this address which is this one here. So this instruction would just resolve the stuff and so on it would just Go downward here and so on so the first Instructions here just ensure that the eggs register is pointing to the stack and after that I go into a loop and Inside this loop. I'm just executing here a pop ex so popping here to next value Which I want to write to the stack with this instruction I just take the this value which I popped move it here to the eggs which is pointing to the stack So I'm copying it to the stack then I come to the next iteration in the next iteration. I'm just subtracting here It is which is for from eggs or I'm just going four bytes down in the stack and then I'm copy here the next bytes So just I just copied a complete rob chain to the stack and this is last line here I just Jump to the stack and start executing their option there another interesting Protection is the caller mitigation. So we have typically three Different possibilities to call a function or to invoke a function. So first of all, we can just We can just call the function, which is the valid one But we can also jump to the start of the function or we can push the address and then make directly a return So it would now Interpreate this address here as the functional return address and would return to the start of the function And during the return of the programming. We are really applying this sort approach here So we're applying this technique and what Emmett is doing is as soon as the function is called It just verifies the return address and checks goes to the return address and checks if directly in front of the return address Call to the function is stored. You maybe see it here a little bit better on the next slide So the following gadget is used by this paper, but chatty mod This is the way how he bypassed the stuff. So if you have a look here instead of directly returning to the start of a virtual Alloc, I'm now returning to an instruction which makes a call to a virtual Alloc So if this instruction makes you the call It would just push this value here. It would Just push This return address here So Emmett would go to this address go one instruction before it and check if this call goes to virtual Alloc Which is valid in this case now, which means I can bypass in this case the caller protection but this gadget here, I see some problems because After executing virtual Alloc, I have to reach this return here to execute my next code But in between of this call and the return I have many many different memory references Which means all these memory references could result in a segmentation fold and if the segmentation fold I could not execute my shellcode and the Firefox would just crash So in my case I was using a gadget inside MADLL So I know this gadget is always there regardless of the operating system and In this case, I'm calling virtual product I have here just one memory reference, but I can ensure that this is not crashing then I feel a jump Which goes directly to the return But the problem is what if is if there is no Shots such a call to a critical function near a return and in this case You can just use any call to a register. So this is the Rob chain, which I'm using in my attack I Will go in a second or at this one here, but what I'm doing is I'm calling Or returning to this location here. I'm executing here code to ED So I just have to ensure that the ED register is pointing to the virtual Alloc or virtual product function after this I take this jump to this location here Just go down and have here the return so there's no no memory reference at all I just have to ensure that ED is pointing to this location and you see here how I'm doing it So I'm just making here pop e-x. That means I'm popping the address of the address of virtual Alloc Inside e-x this this line. I'm resolving it. That means e-x is not pointing to a virtual Alloc Then I'm exchanging it. So I'm just moving e-x E-x into ED so now ED is pointing to virtual Alloc, which is exactly what I want And then I'm popping the address where I want to jump. This is this one and this this line I'm just jumping to this address. So it would just Jump to this address here. ED is pointing exactly to virtual Alloc and it would just work and The last raw protection is simexec flow. This is the same Protection as the color mitigation, but just applied for all return addresses on the code stack So it would just apply it for every return address But if you bypass the color protection, this protection is also bypassed by default So we don't have to do anything here. Of course, we have to enter offensive security approach to Disable all protections, but this is not working anymore for the current versions for for m8 5.2 It's not working anymore. A third approach is that we can use direct system codes But hard coding system code numbers is very bad because they change between different versions of m8 between different Microsoft versions so Windows versions But we have something better And in this case, this is the unprotected virtual product and the real implementation. So you see here This is the system code number for virtual project It's moved into eaX and these two lines just invoke the system code So it would just go here make the sys enter the code to the kernel And if you now protect this this function with emet It would just do the same it just replaces the first bytes here is the hooking code Pointing to this location here and you see here blue marked This is the old start of the function and this stuff is exactly doing what I wanted to do. It moves the correct system code number into eaX and makes the code to the kernel and It's quite simple to obtain the base address here And then I can just calculate the address of this system code here and I can directly jump to this location So I'm just jumping over all protections of emet and making the direct system call and after that I'm just returning to my next code so I can just jump over all protections of emet And I think this is the best approach to do because It's very simple to use this approach to bypass the techniques And this is all also working for the current version of emet. So I think they introduced this vulnerability with emet 5.0 And now we have emet 5.2 and it's still not a fixed You see here the ROP chain for this it's a little bit longer because this ROP chain is self-patching So it's patching itself, but yeah, it's not too hard to write such a stuff and now come to another protection, which is the Expert address table access filtering So typically shellcode has to pass different fields for example the address of functions field inside the beheader of current 32 Because it has to find the functions load library and get process address And what emet now do is it places hardware breakpoints on top of this field That means every time someone tries to read this field Hardware breakpoint that is triggered and emet code kicks in and can add additional checks. So For example emet can check if the triggering instruction belongs to a loaded module or if the triggering instruction is stored on the heap So in the case of my shellcode the triggering instructions on the heap which means it's invalid and emet can detect that an attack is ongoing and To bypass this protection that we have again many many different possibilities So first of all we can just use a ROP Gadget to read the field because then the triggering instruction would belong to a loaded module or You can use that once code reuse technique, which is quite the same Or we can just assume that one of the attack modules Imports the functions load library and get process address and then we can read the base address of these functions in the input address table But this is not a very raw case. So don't think that this would work every time And I think the best solution is that you can just remove or break breakpoints before executing the shellcode and There's again many many different possibilities to remove the breakpoints before executing the shellcode I think because I'm not good in time. I will just skip this one here But basically we have two API codes which can be used to remove harder breakpoints So the first one is sets red context and the second one is anti-continue And of course we can use the associated system codes to make the direct system code to the kernel But all of these approaches has some benefit disadvantages And I think the best approach is That we make that jump over the hook technique from the last chapter So we so there is a for example the function for anti-continue and if this function is protected by emet The code for making the dark system core is moved into a material And I can just jump to this code and jump over all protections that can make the direct system core To disable to remove all part of breakpoints and I'll come to the final thoughts so Emmet consists of many many more protections So I just gave you a overview about in my opinion the most interesting ones like the return of date programming and EF Protections, but it has many more for example a tech surface reduction They can say it's not possible anymore that you load Java in the internet zone You can just load Java in from the Internet or something like that and you see here some other protections For example the heap spraying protections, but bypassing these protections is not too hard from the technical perspective So I just skip this once here in my talk today But you can just have a look at the slides here or a perpetual thesis where I give more details about this stuff Here's a quick recap. So what I have done first of all I have identified if emet is there or not then I've extracted the image space and the version of it and Then I later I built everything on top of emet DLL. So in the slides here I just have implemented everything based on what's just DLL which means you cannot copy paste my code from the slides Because I don't want that you can abuse my code here to attack emet If the emet version is unknown we can use that once code viewers technique, of course, we have here something better which can also be used and You see here a quick demonstration of it So you see here everything is green Firefox is protected.  I go to the advanced options.  If I now restart emet Firefox You see it's still protected and if I'm not using my bypasses, you see it's just working. So I'm just executing calculator You see nothing is freezing or crashing. I can execute it again and again and typically the attack the victim Who doesn't know that attack is ongoing here. Yeah, some words for the EIF plus mitigation This is a new mitigation thing from emet 5.1 or something like that This protection should protect my current exploit, but it doesn't I don't know why I just talked to Microsoft and they also don't know why it's not protecting but But even if it would protect it would not be too hard to bypass this mitigation as well Here's a quick summary about the workload So writing the initial exploit without the emet bypasses took me about three to five days But I didn't try to write it very fast because I was doing this stuff in my free time for my bachelor thesis So was watching TV and stuff like that while doing this Writing then the first bypass took me a really high effort. So the exploit has about 5,000 lines of code This is a really huge amount. This is because I have developed many many different bypasses for all of the different techniques Protections and not only one for each protection But this was good because later when I had to migrate from emet 5.4.1 to 5.0 It just took me five minutes. So I just had to add additional passing instructions so In the hook-in code I'm going down to find the code instruction and I'm always saying if this opcode is this the length is this So there are just two new assembly instructions, which I just had not implemented yet So just had to specify the length of these instructions This emet 5.0 is the release of emet 5.1 It took me for about 40 minutes because they tried to destroy my scan down hook-in approach So as soon as I have a pointer to emet-delay, I'm just going downward to find the bee header And what emet is not doing is it introduced a hole in between of the code section and the bee header So you now have the code section You have the bee header and there's a hole of unmet memory in between So if I now go just downward, I would try to access memory inside this hole and if this memory is not mapped It would just segmentation fold and close firefox So what I'm now doing is I'm just search for the start of the code section As soon as I've identified the start of the code section can subtract the offset of the hole and go to the bee header and Of course this emet 5.1 It took me about five minutes because I just had to change the signature of the code section start because The starting bytes just changed So you see here How this worked? So this here is the address where the bee header is stored It has a size of 1,000 and if you add a base address with the length You just come to the start of the code section Here to take a section same applies for emet 5.0 Base address size of 1,000 if you add both together you come to the text section and here with emet 5.1 You see it's not the case because we have here a hole So this is the base address 1,000 if you add both together you don't come here to 1,000 you have here a hole in between So what I'm doing is it just search for this address here and as soon as I have this address I can just subtract to 0 0 0 0 and reach the bee header You see here the picture. This is emet 5.1 and This is a new one. This is the current version which is emet 5.2 So you see all protections are enabled and you also see here in the debug output that it detected that it's emet 5.2 and of course calculator popped up here are some contact information and Yeah, thank you very much for your attention if you have any questions you can just ask now or come to me later


1 in 8 American women will be diagnosed with breast cancer in their lifetimes. There are a number of compounds in plant foods that may protect against breast cancer by a variety of mechanisms. I've talked about the benefits of broccoli, and flax seeds, and soy foods, but this recent study out of Germany reported something new. Evidence for reduced breast cancer risk associated with consumption of sunflower and pumpkin seeds. Sunflower and pumpkin seeds were associated with reduced breast cancer risk, which they initially chalked up to the lignans in the seeds, something else I've talked about, but their lignan lead did not pan out. Maybe it's the phytosterols, then, that are found concentrated in seeds? There's evidence phytosterols may be anti-cancer nutrients that may play a role in reducing breast cancer risks. I thought the phytosterols just lowered cholesterol. What does cancer have to do with cholesterol? Well, increasing evidence demonstrates the role that cholesterol may play in the development and progression of breast cancer. Cancer feeds on cholesterol, transformed cells take up LDL, so-called bad cholesterol, and it's capable of stimulating the growth of human breast cancer cells in a petri dish. See all these little red dots?  The ability to accumulate fat and cholesterol may enable cancer cells to take advantage of people eating high-fat diets and high-cholesterol diets. Increased dietary cholesterol intake may result in increased breast cancer risk, and may at least partially explain the benefit of a low-fat diet on lowering human breast cancer recurrence. Though data has been mixed, the largest study today found a 17% increased risk in women who had cholesterol over 240 compared to women whose cholesterol was under 160, though they cannot rule out that there may be something else in cholesterol-raising foods that's raising breast cancer risk.  Since cancer feeds on cholesterol, maybe we can stuff some chemo into it, as like a Trojan horse poison pill. That's probably why people's cholesterol levels drop so low after they get cancer, the tumor is eating it up. In fact, patient survival may be lowest when cholesterol uptake is highest. High LDL receptor content in human breast cancer tissue seems to indicate a poor prognosis, suggesting that breast tumors rich in LDL receptors may grow rapidly in the body. We've known about this for decades. You can tell this is an old study. Back in the 80s, only one in 11 American women got it.


If I asked you how the ECB's monetary policy decisions reach the economy, you might well say through banks. And you'd mostly be right. Banks are indeed one of the main channels through which our monetary policy is passed on to the economy. Plus, it's where many people like you and me feel the changes to monetary policy through the rates for loans and savings. Welcome to the ECB Podcast Summer School, helping you understand what's going on in the economy and central banking. My name is Katie Ranger. Banks aren't doing all the work when it comes to what we call monetary policy transmission. Financial markets are key players and some funds and insurers are also becoming more important as providers of loans and financial services. But here in the Euro area, banks play a particularly important role. That's because our capital markets are less developed than in, say, the US, meaning that those looking for funding are much more likely to turn to banks to find it. Explaining today's topic for us is ECB Chief Economist and Professor Philip R. Lane. Good to see you again, Philip, for the last episode of our Summer School mini-series. It's my pleasure to be here. Now we want to zoom in on exactly how banks pass on our monetary policy decisions to you, to me, and to the rest of the economy, and the important role that they play in helping us to get inflation back down to our target of 2%. So Philip, how exactly does it work? How do banks pass on the changes to our key interest rates? So that's a many layered question. So let me tackle it in a couple of ways. Number one, I think everyone listening understands that they do not have a direct relationship with the ECB. If you as an individual knock on our door, we're not going to open up a deposit account and we're not going to offer you a loan. So as you say, most firms and households in Europe primarily rely on their bank if they want to save or to borrow. You raise deep questions about the role of the wider financial system, whether it's insurance companies, pension funds, mutual funds, other type of market activity, which has grown in Europe, but remains relatively limited compared to the US. So let's take the case where a firm or an individual really has mostly the option if they want to save or to borrow to go to their bank. So then the big question is, how do banks determine what is the interest rate they're going to charge and a loan? And then equally, what is the interest rate they're going to offer on a deposit? And then let me trace that back to us at the ECB. So at ECB, when we raise interest rates, we are basically raising the rates at which banks can deposit money with us or lend money from us. So the ECB is a central bank, and it's called a central bank because our customers are banks, our kind of parties are banks. So if we take the deposit rate, the rate at which they can receive income on a deposit with us, when we raise the deposit rate, it means that it puts a floor on the rates more generally in the economy because a bank, if you like, always has a choice. Well, if I cannot earn more on a loan to a firm, I can always put money on deposit at ECB. So it puts a floor on the rate at which it will lend to a firm or a household, and that floor is very important. Now, you might say, why can't they just charge me the exact same rate that they receive from the ECB? I've always wondered that. And the basic answer is twofold. One is a cost to run a bank. They need to add a kind of margin for running costs. So whether that's the technology to fund the apps we all use these days, whether it's the cost of running a branch network, the cost of regulation because we do that to fight terrorism and money laundering, banks also have to spend a lot of money on what's called know your customer. So all of the regulatory elements from that. So there's a lot of administration there. So one element is there's going to be basically an administration cost extra amount added on top. And then there's also going to be a risk factor because it's not the case everyone pays back their bank loan. Firms sometimes fail. Sometimes individuals get into a problematic situation and don't pay back their mortgage. So banks have to add a risk margin as well. So the rate facing you when you walk into a bank or you phone up or you do an online chat, it's going to be a mix of the costs coming from us in terms of like the wholesale cost of finance and then all of these margins. Let me emphasize also it is in terms of the the overall cost to a bank of making a loan to you. Partly they can borrow from us and they also heavily rely on deposits from customers and then also they have kind of various market type funding that they may issue a bond in the bond marketer. And so the overall cost of finance depends on the rates they have to offer depositors. It depends on the bond market rate and these other sources of funding. So this is why it's not straightforward to see the connection between the ECB rate and the rate offered on bank loans. But this has been a long running topic. Okay so many of us have indeed seen banks pass on higher interest rates quickly when it came to making loans more expensive but not so quickly for the interest we receive on our savings. So what have we seen? Have banks passed on our key interest rate changes this last year? So we know quite a bit about history and what we see now is basically in line with historical evidence. What's happened? They've raised their lending rates quite a bit you know quite sharply and in terms of the rates they offer in deposits let me make a very sharp distinction between two types of deposits. One is if you like the what we call the overnight rate. So everyone who has a bank account will have a current account this is the rate at which the account at which you debit money on your debit card or you add money from your paycheck whatever. On those overnight accounts very little interest is offered but that's always true because essentially people have these accounts not necessarily to save money but just to run their life all the transactions. Now when interest rates were super low maybe people did use these overnight accounts just also to save because what else were they going to do? So what's happened now is essentially banks have raised the deposit rate quite a bit on what's called a time deposits. If you agree to commit your money for a year for six months for two years for five years then the interest rate on those deposits it didn't happen immediately but over time these have gone up and they're not too far away on average to the ECB rate. So this is where you park your money essentially for a certain amount of time and you get a higher rate than if you're just leaving it in your savings account and have access to it all the time essentially. Exactly so this is if you like a return to some normal pattern if you go back to the 1990s when I was a student you know I do recall at that point people would make the effort because they say why would I leave money in my current account when I can get some interest in my saving account and people have essentially over the last year have relearned this at least those who have enough money where it makes a difference. So this is where I think it is happening it's not happening to the same degree across all of the European countries because clearly banks will raise the deposit rates more quickly if they face competitive pressure and also if they're in an economy where there's a big demand for loans so that they want to raise funding in order to provide credit. So in those European economies where there's less demand for loans or where there's less competition it's happened less but the basic economics is it takes time but eventually banks will raise their lending rate which happened quite quickly and will raise their deposit rates but let me emphasize mostly only on those time deposits where the customer does not have if you like instant access you do have to accept that you can't have it both ways if you want instant access you're not going to earn much if any interest if you are no you have the kind of flexibility to put some of your money away for a year two years whatever then you are starting to see visible interest rates again. Let's zoom out to look at how banks affect the economy in particular what we call the real economy so this is the part that produces goods and services so big manufacturers but also the bakery around the corner or my hairdresser the real economy is crucial to the euro areas economic activity and growth so how has the behavior of banks during our interest rate hikes affected the real economy what have we seen there? So again we're one year into this hiking cycle what we've seen is essentially the level of lending has really come down quite quickly and that's a mix of two factors one with high interest rates firms and houses are less interested in taking a loan so one way operates is that loan demand is lower and the other way it operates is that loan supply and it goes back to what we talked about earlier on it is banks become more cautious if they see that essentially risk has gone up because we're high interest rates and with a slowing economy the probability of a firm or household running into trouble it doesn't you know dramatically shoot up but not just up so they are going to be more careful saying well I don't want to make too many loans because some of these loans may turn bad so we see all of that okay where does this matter I think one issue where we would be tracking quite carefully is investment so firms may be tempted to say well you know this year I'm not going to invest for the future because it's too expensive and then over time if there's a lack of investment it reduces the growth capability of the economy so in the near term it means less demand for investment goods so many firms in Europe are there to support investment they're making capital goods that they're advising architects you know project managers there's many people whose job it is to support investment so less investment uh you're going to see it I think we're seeing it also in basic consumption is is is flat consumption is not growing even though incomes are growing so these are things like people buying fridges or yeah so I mean I think in there's a hierarchy it's less activity in the housing market and then it has the knock on effects if this fewer houses being sold then fewer people who are visiting furniture shops you know washing machines all of that so we do think that that's quite visible right now let me emphasize whoever and this is so important to appreciate it is we do think that there's a very fundamental reason why this process is working but in a relatively stable manner because another byproduct of the pandemic was that people did have a period when they were consuming very little so they did save more than normal and these pandemic savings allowed them to reduce their debt allowed them to maybe build up a nest for example a mutual fund or something like that so it does mean if a house gets into trouble they maybe have more buffers and they don't necessarily get get into a bad loan situation so quickly also for firms I mean for firms it differs quite a bit across sectors but many firms were were supported by their governments during the pandemic and then more recently many firms as we talked about in another episode have been making money have been making good profits so there's also if you like the kind of what we think is this will help reduce the amount help cool inflation but will not produce the kind of deep recession we had in Europe 15 years ago and so this is this is a I think very important distinction because people are very nervous when they hear kind of phrases about tightening kind of depressing demand dampening demand and what we're trying to do is do enough that we do make sure inflation comes back to target but we don't see the conditions right now because you usually need this kind of toxic mix where firms are already weak customers are already weak but but you know I think many people are in okay shape so they will respond to high interest rates by reducing demand but we don't think it'll lead into this kind of vortex that leads to a deep recession if we look specifically at economic activity you just mentioned that we're not looking to to have a recession here in Europe the economy is however weak right now and it is expected to recover but only kind of over time do you see that as an issue what does it mean if activity stagnates I mean not a recession but it stagnates well that's not overly focused on on the issue the technical issue of recession because I think we've always said for months now that that you know whether the economy is a little bit above zero a little bit below zero it's not the fundamental issue what I thought about is what's very damaging is a deep and sustained recession so we don't see that and what we do see is compared to where we were last year there's a lot of reasons to believe the European economy will grow over the next couple of years one basically is it remains the case there's still a recovery from the pandemic there's a bounce back we're well below the level of the economy we might have expected if the pandemic had not happened and if you like that that kind of trend line we would expect to reemerge over time we would expect energy price has been a lot lower now that's not fully been arrived in people's utility bills yet but over time lower energy bills will help and now we are seeing wages go up so as wages go up the kind of very difficult situation at the end of last year where inflation was sky high and yet wages were had not gone up over time households should be in a better financial position so there are a number of reasons to believe that the European economy will grow over the next couple of years and the trick for us is basically to make sure demand does not add on supply so it's not a question of having a driving a demand deeply negative it just has to grow more slowly than supply okay well as you know Philip we we always ask our guests to share a tip maybe a book a film a story with our listeners on the topic that we've been talking about today so banks what would you have to share with our listeners today so let me advertise work by some of our colleagues at the Bank of England so I think there's a very nice book which is I think should be of interest to to to many people and the title of the book is called can't we just print more money economics intense simple questions by Rupal Patel and Jack Meening and this book I think is a fantastic explainer of many of the concepts we've been talking about I can only agree it's a fantastic book and I really recommend that everyone reads it as you do well that brings us to the end of this episode I want to thank ECB chief economist Philip Arlene for taking us through the role banks have in passing on our monetary policy and for being our guest on these three summer school episodes if you found them useful please subscribe and leave us a review and be sure to check out the show notes for more on this topic you've been listening to the ECB podcast summer school with Katie Ranger this is my last episode before I hand over the mic for a little while so today I'm signing off with an especially big thanks for listening


slower than the first eight. So it's Matsej Jinovsky who still leads qualifying then and as things stand we'll have first pick of what position in the one to sixteen to go for for tomorrow night and therefore that choice will be influenced by the gate positions that Magic has. Kel's already studied the various gate position stats from down the years here in Malilla and here's Leon Madsen, joint leader of the championship, but suffered a crash in a Polish league meeting last Friday and with Drew from the SEC the European Championship, a point to last weekend. I'm bearing in mind he is the European champion that was a massive decision for Leon Tomei. He's had an injection he tried without earlier on but couldn't hang on to it and then subsequently it has. It's all down his right side, his right ankle, his right shoulder are giving him a lot of discomfort. He's roaring away there and he's already into 14 flat. That's a fabulous time. The wounded animal Leon Madsen producing a stunning time there to push himself right back into second place. That's a fabulous effort from him on his opening lap. Leon Madsen has been a revelation this year and even though he's injured and he's hobbling around the pits I've got to say two 14 flats puts himself into second place. Very good effort. 14.053 was his lap time, the best lap time there and amazingly with all his injury problems riding through the pain but the injection must have worked. It has, it's just numbed him up completely. He can't feel the right side at all so that's certainly allowing him to produce a decent time and he'll be pleased with that because there's no doubt that he was concerned about tomorrow but if he can stay in that sort of form then he'll certainly go away with a hat full of points.


Hi everyone, I'm Gili and I'm going to talk about batch verification in generic group accumulators. This is joint work with Gili Segev. Let's start by quickly reviewing the notion of a cryptographic accumulator. An accumulator is a fundamental cryptographic primitive that produces a short commitment to a set of elements. The set may be static in the sense that all elements are known ahead of time or dynamic in the sense that elements may be added to the accumulator or removed from the accumulator at any point in time. In addition, the property that distinguishes accumulators from standard short commitments is their support for publicly verifiable proofs of membership with respect to the accumulated set and sometimes even proofs of non-membership. Over the years, accumulators have been found very useful for authenticating remotely stored large datasets enabling to retrieve individual elements with significant savings in terms of both communication and computation. Non-constructions of accumulators can be roughly classified into two categories, hash-based constructions and group-based constructions. Hash-based constructions generate a short commitment via a miracle tree. The length of the resulting commitment is independent of the number of accumulated elements and the length of membership proofs and the verification time are both logarithmic in the number of accumulated elements. Group-based constructions exploiting the structure provided by their underlying groups lead to accumulators in which the length of the commitment, the length of membership proofs and the verification time are all independent of the number of accumulated elements. Most notably, such accumulators have been constructed in RSA groups and in bilinear groups and in both cases the constructions do not exploit any particular property of the representation of the underlying groups and so they are generic group constructions. Motivated by recent applications of accumulators to stateless blockchains and interactive oracle proofs, Bonnet observed that a useful feature of accumulators is the ability to aggregate proofs for several elements and then to batch verify them. Hash-based accumulators seem somewhat less suitable for offering such features with practical efficiency guarantees and therefore Bonnet relied on the structure provided by RSA groups and more generally by unknown order groups such as the class group of an imaginary quadratic number field. Specifically, they show that membership proofs and non-membership proofs for any subset of T elements can be aggregated into a single proof whose length is independent of T. Then, their aggregated proofs are verified via an interactive protocol where the number of group operations performed by the verifier is again independent of T. Specifically, the verifier in their protocol performs T modular multiplications and only lambda over log lambda group operations where lambda is the security parameter instead of T times lambda over log lambda group operations as in the verification of T individual proofs. Then, by applying the Fiat-Chamir transform with a hash function that produces random primes, Bonnet showed that their interactive verification protocol yields a non-interactive publicly verifiable verification procedure. Analogous results were subsequently obtained in bilinear groups with essentially the same parameters. Other than applying the Fiat-Chamir transform for obtaining a non-interactive verification procedure, these constructions are generic group constructions. Given the key importance of non-interactive verification in most applications that involve accumulators, this leads us in this work to the fundamental question of whether non-trivial batch verification in generic group accumulators indeed requires interaction. We prove a tight lower bound on the number of group operations performed during batch verification by any generic group accumulator, stating our result somewhat informally. We prove that any generic group accumulator that stores a less than trivial amount of information must perform T times lambda over log lambda group operations for the non-interactive batch verification of any subset of T elements. In particular, this rules out non-trivial non-interactive batch verification. Our result holds both for known order and even multilinear groups and for unknown order groups where it matches the asymptotic performance of the known bilinear and RSA accumulators. It should be noted that whereas the generic group model captures generic computations in known order groups quite accurately, it's a variant that considers unknown order groups since somewhat limited in capturing generic computations in such groups and please share paper for more details. In order to state our theorem a bit more formally, we need some additional notation. We denote by NACC and L the number of group elements and additional explicit bits that are generated when accumulating K elements and we denote by Q the number of group operation queries that are issued when verifying a batch membership proof for a subset of T elements out of the K accumulated elements. In order to easily understand our lower bound, we first need to focus on a few terms. The first is log of the size of X lambda choose K that is now highlighted in yellow. This is the expected number of bits required for an exact representation of K elements that are taken from the domain X lambda. The second is NACC times log of NACC plus 1 plus L that is now highlighted in green. This turns out to be the amount of information that is actually stored from the verification algorithm's point of view. Finally, the difference between the yellow term and the green term divided by K is the average information loss per accumulated element. Now our third states that the number Q of queries that are issued when batch verifying a proof for a subset of size T is at least T times the average information loss per accumulated element times 1 over log lambda. In particular, let's consider the case where the size of the domain is exponential in the security parameter which is indeed the case for the known accumulators in RSA and by linear groups. Then either the amount of information stored by an accumulator is almost trivial or the number of queries that are issued when batch verifying T elements is at least T times lambda over log lambda. In other words, if the amount of information stored by an accumulator is bounded away from the information theoretic bound, then non-trivial batch verification is impossible. Finally, I would also like to note that our result extends somewhat beyond the generic group model. Specifically, it holds in an augmented model that enables to capture a bounded amount of non-generic information and please see our paper for more details. The rest of this talk will follow this outline. We will start by defining the generic group model within which we prove our result. Next, we'll define in more detail accumulators within this model. Then we will present a simplified version of our proof and finally, we will conclude with some closing remarks and open problems. So let's begin by discussing the generic group model. A generic group algorithm is an algorithm that does not exploit the representation of the underlying group in any way. This is captured via an oracle which manages the access of all algorithms to the group. In this work, we use the generic group model suggested by Maurer. In this model, group elements do not have an explicit representation and instead algorithms specify their queries by pointing to previously seen group elements. For example, an algorithm may ask the oracle to apply the group operation to the fourth element and the seventh element that have appeared in the computation so far. This model is a bit different from the generic group model suggested by Schup. In Schup's model, each group element has an explicit random representation. These two models have been shown to be polynomially equivalent for certain problems such as the discrete logarithm problem. But generally, the two models are incomparable. Looking ahead, a natural open problem that I would like to already point out is whether our result can be proved within Schup's model. One should note that our result can be circumvented by applying the Fiat-Chameer transform and that the random injective mapping used in Schup's model for explicitly representing group elements might potentially be exploited towards this goal. Let's define the model more formally. Any cyclic group of order p is isomorphic to the additive group Zp and therefore group elements in this model are identified with the elements of Zp. A generic computation is associated with the table B of Zp elements managed by the oracle. This table is initialized with the Zp elements corresponding to the input elements that are provided to an algorithm and the table B is always initialized with the generator 1 at its first entry. A generic algorithm can then produce two types of queries to the oracle, group operation queries and equality queries. To issue a query, an algorithm specifies the indices in the table of the two elements that it wishes to compare or to which it wants to apply the group operation and also the type of operation, plus or minus. In response to a group operation query, the oracle adds or subtracts the two corresponding elements in the table and places the result in the next vacant entry. In response to an equality query, the oracle compares the two Zp elements from the table and answers accordingly. When a generic algorithm wants to output a group element, it outputs the index of the corresponding entry in the table B. In addition to group elements, algorithms may receive as input or include in their output also explicit bit strings. This model also naturally captures interactive computations, allowing one generic algorithm to pass group elements to another generic algorithm by pointing to elements in the table B. We consider two flavors of generic groups, groups of known orders and groups of unknown orders. In the case of known order groups, which is the more standard one in the context of the generic group model, all algorithms receive the order of the underlying group as an explicit input. In the case of unknown order groups, which is somewhat less common in the context of the generic group model, the order of the underlying group is not included as an explicit input to all algorithms. Still, however, the corresponding order generation algorithm is always publicly known. In the stock for simplicity, we will consider the case where the order P is known to all algorithms. After discussing the generic group model, we can now discuss accumulators in this model. A generic group accumulator is a triplet of generic algorithms defined as follows. The algorithm setup receives its input as ZX and outputs an accumulator denoted ACC and a state. The algorithm proof receives its input an accumulator ACC, a state and a set S and outputs a proof pi. Finally, the algorithm verify receives its input an accumulator ACC, a set S and a proof pi and outputs accept or reject. The correctness requirement for this most basic form of accumulators is quite natural. For any ZX of accumulated elements, if we generate a membership proof via the algorithm proof for any subset S of X, then the algorithm verify should output accept. The notion of security is also quite natural and considers generic adversaries that can issue a polynomial number of queries but are unbounded in terms of their internal computation. The notion of security asks that any adversary wins the following experiment with only a negligible probability. First, the adversary specifies a set of elements X and receives an accumulator ACC that is honestly generated for X. Then the adversary can ask for honestly generated membership proofs for subset S of X. The goal of the adversary is to output a pair S star and pi star that is accepted by the verification algorithm with respect to the accumulator ACC, although S star is not a subset of X. Given this notion of security, we can observe that we prove our lower bound for the most basic form of accumulators that is static membership only accumulators. Therefore, our result holds in particular for accumulators with more advanced features such as a dynamic accumulators that support both membership and non-membership queries. We can now move on to present an overview of the main ideas underlying our proof. Let me just note that for the purpose of this talk, we actually present a highly simplified variant of the proof with several simplifying assumptions. We show that if an accumulator's verification algorithm issues an insufficient number of group operation queries while batch verifying a subset of T elements, then there exists an attacker A that breaks its security. Our attacker issues a polynomial number of group operation queries while being computationally unbounded in terms of internal computation. This suffices for ruling out generic group constructions since in the generic group model, problems such as discrete log are hard even for computationally unbounded algorithms as long as they are bounded in their number of group operation queries. Our attack can be divided into two steps. In the first step, the attacker chooses a random set, partitions the set into disjoint subsets, and records the view of the verification algorithm when batch verifying proofs for these disjoint subsets. In the second step, the attacker exploits this information for generating a false batch membership proof. Let's describe each step in more detail. In the first step, the attacker samples a random set X of size K and asks to accumulate this set. The attacker then partitions X into K over T, which we denote by V subsets, each of size T. The attacker asks for batch membership proofs for each subset. Then the attacker executes the verification algorithm for each subset by forwarding the algorithm's queries to the Oracle O. Now let's look into the view of the verification algorithm in these executions, which the attacker needs to record. The attacker records the equality pattern among the group elements of ACC, and for this, we need NACC times log NACC plus 1 bits. A simplifying assumption for this talk is that ACC and also the membership proofs include only group elements and not explicit streams. Then for each subset Si, the attacker records the verifier's view in the corresponding execution of the verification algorithm. The attacker records the equality pattern among the group elements of the proof Pi I and whether they are equal to any of the group elements of ACC. If each proof consists of N Pi group elements, this requires additional N Pi times log NACC plus N Pi plus 1 bits. The attacker also records the Q queries issued by the verification algorithm, where each query essentially consists of the two indices, two entries of the table B, and the type of group operation plus or minus. This requires about two Q times log NACC plus N Pi plus Q plus 1 bits. Finally, the attacker records the equality pattern induced by the responses to these queries. This requires additional Q times log NACC plus N Pi plus Q plus 1 bits. Another simplifying assumption for this talk is that N Pi is linear in Q, and therefore the total number of bits for recording the entire view is NACC times log NACC plus 1 plus Q times K over T times log lambda bits. After the attacker records the entire view of the verification algorithm, we move to the second step of the attack to generate a false batch membership proof that is consistent with this view. The attacker internally emulates the three algorithms set up, proven, verified by simulating a fresh oracle O prime instead of the actual oracle O. The attacker tries to find a set X prime and accumulator ACC prime and proves Pi prime 1 to Pi prime V that satisfy the following requirements. First, the set X prime must be different from the set X that was chosen as part of the experiment. Second, when partitioning X prime into disjoint subsets S prime 1 to S prime V, the following two requirements must be satisfied. The verification algorithm with access to the oracle O prime accepts Pi prime I as a batch membership proof for the subset S prime I with respect to the accumulator ACC prime. The exact same execution of the verification produces the same view as the execution of the verification algorithm with access to the actual oracle O on input the accumulator ACC, the subset SI and the proof Pi I all of which A obtained within the experiment. If the attacker finds such values, then it outputs one of the subsets S prime I star, which is not a subset of X, together with the proof Pi I star that belongs to the subset SI star of X. Okay, so that's our attacker. And let's just note that in the first step of the attack, the attacker issues a polynomial number of group operation queries and runs in polynomial time in terms of internal computation. This should be compared to step two of the attack where the attacker does not issue any group operation queries but may run in exponential time in terms of internal computation. The analysis of the attacker's success probability consists of two claims. The first claim states that if the attacker indeed finds such a set X prime then the verification algorithm accepts and thus the attacker wins. The intuition for the proof of this claim is as follows. Based on the definition of the attacker, we know that the yellow computation accepts but note that this computation is not executed with respect to the actual oracle O. However, we also know that the yellow and green computations produce the exact same view and the green computation is executed with respect to the actual oracle O. The main technical effort is now in showing that the yellow computation produces the same view as the green-yellow-green hybrid which therefore also accepts. The second claim states that if the number of bits required to represent a set of size K is larger than the number of bits required in step one then the required set X prime exists with probability at least one-half over the choice of X. This is a simple argument that considers the view of the verification algorithm as a function defined over all sets of size K. As long as this function loses at least one bit of information, there must be many collisions. Okay, so that was our result and I would like to conclude with two quick directions for future research. The first, which I have already mentioned, is examining whether our results can be extended to Schup's incomparable generic group model. The second, which I have mentioned somewhat implicitly, is obtaining a better understanding of batch verification in unknown order groups such as RSA groups. A natural starting point is looking into our approach in the context of the generic ring model which captures such groups more realistically. So that's all and thank you for listening.


How do you feel now? I feel I am the luckiest person in the earth. And also the blessings of my ancestors and family members. And also blessings of Brahm Lalla. It is really sometimes I feel like I am in a dream world. So this is the biggest take up.