Programming Task: 20 points Congratulations! You’ve just been hired as a Python programmer at an education start-up company. Your first task is to develop a prototype of a program that kindergarten students will use to check their homework assignments which involve addition, multiplication, and division problems. Program Specification The program begins with a series of prompts, then prints a few lines to the screen in response. In total there are 6 lines that are printed each time the program is run: 1 1. Prompt the user for their name 2. Greet the user and ask them to supply the first integer 3. Prompt the user for a second integer 4. Output the sum of the two numbers 5. Output the product of the two numbers 6. Rephrase the division question, and output the whole number and remainder. All numerical outputs on the 6th line of output must be integers (whole numbers, without decimals). A sample invocation of the program is shown in Figure 1: Figure 1: Sample Output Although this is a simple set of steps, there are many, many different Python programs that can achieve it. The text of your prompts does not need to match the example exactly. However, your solution must follow the the instructions above exactly as specified. For example: • Both the greeting and the prompt for the first number must be printed on the second line of output. • The last (6th) line of output must rephrase the division question and output the whole number and remainder portions of the calculation on a single line. Valid Input and Error Checking You should assume that the user provides all requested inputs (via the keyboard) as instructed, and assume that all integers are positive numbers. Your program is not required to check the input or behave in any specific way if the above conditions are not met. Testing Your Program Testing is a major component in the process of writing software. Often, testing (detecting errors) and debugging (locating and fixing errors) takes way more effort than writing the code did in the first place. We’ll talk more about testing as the quarter progresses; in the meantime, the following table provides some helpful test cases that you can use to see if your program is working correctly. Try your code out with the given pairs of integers and see if your output matches the sum, product, and division result. 2 First Integer Second Integer Sum Product Division 7 5 12 35 1 remainder 2 5 7 12 35 0 remainder 5 3 3 6 9 1 remainder 0 1 678 679 678 0 remainder 1 8364724 9738 8374462 81455682312 858 remainder 9520 Submission Double check that your program works according to the specification. Take a look through the rubric below and make sure you won’t lose points for reasons that could easily be foreseen and fixed. When you’re finished, submit your program to Canvas as a single .py file named arithmetic.py. Finally, fill out the A1 Hours quiz with an estimate of the number of hours you spent on A1 (include both the written and programming portions in your estimate). Rubric Canvas questions 16 points Author, date, and program description given in comments at the top of the file 1 point Program prompts for user’s name on the first line 4 points Greeting on second line includes user’s name 4 points First integer prompt also appears on second line 2 points Correct sum output on fourth line 2 points Correct product output on fifth line 2 points Division question is rephrased, quotient and remainder are printed on sixth line 3 points Code is commented adequately and variables are appropriately named 2 points Total 36 points 3 3 Optional Challenge Problem Some assignments will come with an optional challenge problem. In general, these problems will be worth very small amounts of extra credit: this one is worth one point. Though the grade payoff is small, you may find them interesting to work on and test your skills in Python and algorithm development. The skills and knowledge needed to solve these problems are not intended to go beyond those needed for the base assignment, but less guidance is provided and more decisions are left up to you. The A1 challenge problem is as follows: Many online real estate websites have mortgage calculator features1 . These calculators ask for some information, such as the price of a home, the down payment (amount of the home price you’d pay up front), and the interest rate, then calculate the amount you’d have to pay monthly on a loan for the home. According to NerdWallet2 , the formula used to calculate the monthly payment based on these inputs is as follows: M = (P − D) r(1 + r) N (1 + r)N − 1 Where: M = The monthly payment P = The price of the home D = The down payment amount N = The number of months over which the loan will be paid off r = R/12, the monthly interest rate, which is the yearly rate divided by 12 Write a program that asks the user to enter P, D, N, and R, then outputs the monthly payment amount M. Notice that you will prompt the user for R, the annual interest rate, but the formula uses r, the monthly interest rate. 3.1 Submission Upload your submission to Canvas in a file called challenge.py. 1See https://www.zillow.com/mortgage-calculator/ for an example 2Go to https://www.nerdwallet.com/mortgages/mortgage-calculator/calculate-mortgage-payment and click “How to calculate your mortgage payment” for the source of the formula
For this part, we will use the monks’ dataset that we have used in HW1, and use Neural Network to do Classification. Specifically, the training and test file is named monks-1.train and monks1.test. There are six attributes/features (columns 2–7), and binary class labels (column 1). See monks.names for more details. Requirements: 1. Implement a 3-layer neural network, with the number of nodes and activation function of each layer shown as follows: Layer 1 Layer 2 Layer 3 Number of nodes 8 6 1 Activation function Hyperbolic tangent ReLU Sigmoid You can either use the Sequential and Dense layer from Keras OR scikit-learn MLPClassifier OR implement you own neural network function. Next page includes a simple example of using Keras to construct a 2-layer neural network. 2. Use the cross-entropy function as the loss function as we discussed in the class for the logistic regression. 3. Set the learning rate as 0.01 or change to other values if you find 0.01 is not suitable for this problem. 4. For the two optimizers: stochastic gradient descent and Adam, record the testing accuracy for the following epochs 5, 10, 15, 20, 25, 30, 35, 40, 45, 50. Plot the testing accuracy of these two optimizers with respect to the epochs number. 2-layer NN using Keras with 12 nodes in the hidden layer. from keras.models import Sequential from keras.layers import Dense model = Sequential() model.add(Dense(12, input_dim=8, activation=’relu’)) model.add(Dense(1, activation=’sigmoid’)) model.compile(loss=’binary_crossentropy’, optimizer=’sgd’) model.fit(X, y)
Naive Bayes – Cancer Tumor Classification For this part, you will focus on a cancer dataset that comprises of 569 rows and 32 columns and perform Naive Bayes Classification. What do you need to do? 1. Load the dataset from ‘cancer.csv’ into a pandas DataFrame and print it along with its shape. ‘diagnosis’ is the target variable. 2. Print the column names and the data type of each column. 3. Plot the ‘Radius Mean’ VS ‘Texture Mean’ along with the classes represented as colors or shapes. Is the data linearly separable? 4. Perform encoding on the target variable (here label encoding will suffice). 5. Divide the data into X and Y, where X is the set of features and Y is the target variable. 6. Split the data into train and test data. Choose a split size of 70 – 30. 7. Given the nature of the data and its features, choose which Naive Bayes is the most suitable. Mention this in your report along with why you make your choice. You may use the Naive Bayes from sklearn. 8. Once you have trained your model, evaluate the model performance by printing the performance matrix. 9. Write a report with screenshots of your results and the final results for step 8. 10.Submit your code as an .ipynb file and a pdf file reporting your findings.
Problem: Implement a fixed-depth decision tree algorithm, that is, the input to the ID3 algorithmwill include the training data and maximum depth of the tree to be learned. The code skeleton as well as data sets for this assignment can be found on Camino. Data Sets: The MONK’s Problems were the basis of a first international comparison of learning algorithms. The training and test files for the three problems are named monks-X.train and monks-X.test. There are six attributes/features (columns 2–7), and binary class labels (column 1). See monks.names for more details. Visualization: The code skeleton provided contains a function render_dot_file(), which can be used to generate .png images of the trees learned by both scikit-learn and your code. See the documentation for render_dot_file() for additional details on usage. a. (Learning Curves, 15 points) For depth = 1, …, 10, learn decision trees and compute the average training and test errors on each of the three MONK’s problems. Make three plots, one for each of the MONK’s problem sets, plotting training and testing error curves together for each problem, with tree depth on the x-axis and error on the y-axis. Note: You need to write your own function to learn the tree and cannot use scikit-learn’s DecisionTreeClassifier for this question. b. (Weak Learners, 15 points) For monks-1, report the visualized learned decision tree and the confusion matrix on the test set for depth = 1, 3, 5. You may use scikit-learns’s confusion matrix() function [1]. Note: You need to write your own function to learn the tree and cannot use scikit-learn’s DecisionTreeClassifier for this question. c. (scikit-learn, 10 points) For monks-1, use scikit-learn’s DecisionTreeClassifier [2] to learn a decision tree using criterion=’entropy’ for depth = 1, 3, 5. report the visualized learned decision tree and the confusion matrix on the test set for depth = 1, 3, 5. You may use scikitlearn’s confusion matrix() function [1]. [1] https://scikit-learn.org/stable/modules/generated/sklearn.metrics.confusion_matrix.html [2] https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html
Programming Question : Heart Attack Prediction What do you need to do? 1. Create and compile as many plots as you can using the matplotlib library for the given dataset. 2. Use the created plots to try to find some numerical features that can be used for good classification models (similar to the example in class find features that help in linearly separating data) 3. Split the dataset into 70% train and 30% test. 4. Implement the Logistic Regression classification algorithm 5. Use the evaluation metrics discussed in the class to see how well your models have performed for the given dataset. 6. Submit your code as an ipynb file and a document reporting your findings. Observation Table: For Logistic Regression Features Precision Recall Accuracy F1-Score : : Roadmap 1. Use as many visualization tools on the dataset. It is not necessary that you will get information from all of them, but if you are working on a dataset then any useful information you can have will be helpful in deciding which attributes are good/bad with respect to classification. Start with 1 attribute and try combinations with others to see if they are relevant attributes or not. Use this step to eliminate attributes instead of selecting [For example you might want to eliminate DoB from the attributes since it would not help for the classification task, but it would have age as an attribute then you might wanna use it for your classification task]. 2. Once you have an idea about the attributes you want to use to build your model, use the sklearn library to build your model and then use the evaluation metrics to evaluate the performance of your model. 3. Our goal is to experiment with the dataset, not to get the most accurate model. (But try to get the best accuracy if possible :)) Dataset Description This database contains 76 attributes, but all published experiments refer to using a subset of 13 (attributes) + 1 (target) of them. The “target” field refers to the presence of heart disease in the patient. It is integer-valued 0 = no/less chance of heart attack and 1 = more chance of heart attack Attribute Information 1) age 2) sex 3) chest pain type (4 values) 4) resting blood pressure 5) serum cholestoral in mg/dl 6)fasting blood sugar > 120 mg/dl 7) resting electrocardiographic results (values 0,1,2) 8) maximum heart rate achieved 9) exercise induced angina 10) oldpeak = ST depression induced by exercise relative to rest 11)the slope of the peak exercise ST segment 12) number of major vessels (0-3) colored by flourosopy 13) thal: 0 = normal; 1 = fixed defect; 2 = reversable defect 14) target: 0= less chance of heart attack 1= more chance of heart attack
Regression for House Price Prediction What do you need to do? 1. Load the dataset into a pandas dataframe and find the data types for each column in the dataset. 2. Find the names of the columns of this dataframe. 3. Find how many numerical features exist in the dataset. 4. Find the correlation matrix for this dataset. Report which features tend to have a high correlation with the target variable. (You can use the corr() function). Refer to supplementary slide ‘Correlation’. 5. Create and compile as many graphs (feature vs target variable) as you can using the matplotlib library [https://matplotlib.org/gallery/index.html] for the given dataset. Select only numerical features. 6. Based on the graphs in step 5, identify features that have a linear relationship with the target variable. 7. Selecting different features from step 6, implement a linear regression algorithm and find the slope, the intercept and the error of the regression model. 8. Display the line of best fit from step 7. 9. Some options you can consider: a. linregress() from scipy.stats b. LinearRegression() from sklearn c. Manually code the gradient descent algorithm 10.Create a table similar to one given below for all the features selected in step 7. 11. Also attach images of the graphs to your report. Observation Table: Feature Slope Intercept : : Submit your code as an .ipynb file and a document reporting your findings. You could also show them as output of your code.
Your class project is an opportunity for you to explore an interesting data science problem of your choice in the context of a real-world data set. Below, you will find some project ideas, but the best idea would be to combine Data Science with problems in your own research area of interest. In this project you will want to apply what you have learned in class and report your findings. Select a topic you would like to work on and look for interesting project ideas related to that. Feel free to design this project based on your group’s interests and do not restrict yourself just to the topics discussed in class. 🙂 For example, Linear Regression Project Ideas could be a starting point for your project! SAMPLE PROJECT: Sensor network data Using this 54-node sensor network deployment, we collected temperature, humidity, and light data, along with the voltage level of the batteries at each node. The data was collected every 30 seconds, starting around 1 am on February 28th, 2004. http://www-2.cs.cmu.edu/~guestrin/Research/Data/ This is a “real” dataset, with lots of missing data, noise, and failed sensors giving outlier values, especially when battery levels are low. Project ideas: 1. Compare regression algorithms [A survey paper] 2. Detect failed sensors Similarly you could explore other Machine Learning algorithms for other projects. In a nutshell ● Proposal (Due 2/14/24). 10% of your project grade. ● Project report and Code (Due 3/17/24). 90% of your project grade. Sample Project Reports:- http://cs229.stanford.edu/projects2011.html Project proposal format: Proposals should be three pages maximum. Include the following information: ● Project title ● Data set ● Project idea. This should be approximately two paragraphs. ● The software you will need. ● Papers to read. Include 1-3 relevant papers. You will probably want to read at least one of them before submitting your proposal. ● Teammate: will you have a teammate? If so, whom? The maximum team size is three students. Please sign up here: Group Sign-Up Your project will be worth 10% of your final class grade, and will have two final deliverables: 1. A report of at least 5 pages, explaining the problem, approaches, results and conclusion.(NO LATE SUBMISSION ACCEPTED since I need to get your grades in) Make sure it is not double spaced and you should not just fill up your report with images. 2. Source code of your project. Final Report Grading Scheme The grades for the final project report will be loosely based on the following criteria: Background: 1. Does the final report describe the setting and reference to related research? 2. Does the final report describe the data that you are working with and how it was derived? Design: 1. Does the final report have a concrete well defined experimental design describing the learning task? 2. Does the final report describe which features and models are used and why they were chosen? Implementation: 1. Did you implement the required appropriate techniques? 2. Does the final report describe what was implemented and what tools were used? Results: 1. Does the final report have quantitative results from learning or experimenting with your data? 2. Does the final report have data analysis using visualization tools? Does the report have findings for the same? 3. Does the final report have results evaluating the learning of your model? (i.e., learning curves, precision-recall, training/testing errors, …) 4. Does the final report make effective use of graphs that are appropriately labeled and properly described in the document? Interpretation: 1. Does the final report attempt to interpret the results? 2. Does the interpretation correctly use concepts to justify the results? Overall Presentation: Is the overall presentation coherent and well organized?
Consider the SimpleCoin2 approach discussed in the lecture. Suppose you want to implement the logic used by entity G to process transactions and produce the ledger. The entity G receives a PayCoin transaction and needs to check if this transaction is valid before adding it to the ledger. You will need to write functions for this scenario. 1) (10 points) Create a PayCoin transaction data structure or class with all the fields it requires. 2) (10 points) Create the blockchain (ledger), (assume the data part of each block contains only one transaction of type PayCoin). You do not need to compute the hashes, 3) (32 points) Write a function that checks whether a given new transaction is valid or not. If valid then add it to the blockchain. The definition of “valid” transaction is in the lecture notes. Make sure to add enough comments to explain what you are doing. Assumptions: Assume you have access to everyone’s correct public key. Public keys are also included in the recipient field of the transaction. Also assume there is a function already implemented that verifies signatures and returns True or False: boolean verifySignature(pubKey, message, signature)
1. (15 points) As mentioned in the lecture, in a hash function the word diffusion refers to how the change of a single bit in input can affect many different bits in the output. Consider a single application of θ step. (a) If we change the bit in ain[1][4][63] which bits exactly are affected in aout? Remember that affected does not necessarily mean the bit changed, it means that there is the potential for change. (b) How many unique bits will be affected if you apply the θ step for a second round? (Note that we are assuming that we are only applying θ and not any of the other functions.) Show which bits are affected. 2. (10 points) Find RC[3] in the iota step. Write RC[3] in hex similar to RC[0] and RC[1] that is provided in the lecture. Show your work by checking the constant term of x t similar to the approach in the lecture. 3. (10 points) [Programming assignment] Implement the function ρ from a 3-dimensional array ain[0 . . . 4][0 . . . 4][0 . . . 63] to a 3-dimensional array aout[0 . . . 4][0 . . . 4][0 . . . 63]. Note that the rho matrix is: rhomatrix=[0,36,3,41,18;1,44,10,45,2;62,6,43,15,61;28,55,25,21,56;27,20,39,8,14] To check your work, apply your function to the input file provided to you, the output aout[4][3][9 . . . 18] should be 0110011001. Apply ρ to the input file provided. In your homework writeup, list the ten bits aout[3][1][15 . . . 24]. 4. (10 points) [Programming assignment] Implement the function π from a 3-dimensional array ain[0 . . . 4][0 . . . 4][0 . . . 63] to a 3-dimensional array aout[0 . . . 4][0 . . . 4][0 . . . 63]. To check your work, apply your function to the input file provided and the output aout[4][3][9 . . . 18] should be 0110110001. Apply π to the input file provided. In your homework writeup, list the ten bits aout[3][1][15 . . . 24]. 5. (10 points) [Programming assignment] Implement the function χ from a 3-dimensional array ain[0 . . . 4][0 . . . 4][0 . . . 63] to a 3-dimensional array aout[0 . . . 4][0 . . . 4][0 . . . 63]. To check your work, apply your function to the input file provided (sha3in.txt) and the output aout[4][3][9 . . . 18] should be 0110100001. Apply χ to the input file provided. In your homework writeup, write down the ten bits aout[3][1][15 . . . 24].
1. (10 points) Suppose we have a hash function h that takes inputs of 1088 bit strings and outputs hash strings of 256 bits. (a) As discussed this function will have collisions, and on average, h is an n-to-1 map. Find n. (b) For an output y, we expect to have n input strings that map to it. So there will be n different 1088 bit strings x such that h(x) = y. If we want to solve the one-way problem for an output string y, we need to find one of the n x’s among all 1088 bit strings. This seems easy to do as we only need to find ANY 1088 bit string x such that h(x) = y and we have n of such x’s. However, the probability that we will solve the one-way problem by applying h to random 1088 bit strings is n/(number of 1088 bit strings). Find this probability for this hash function. 2. (10 points) Let f : X → Y be a hash function and assume |X|/|Y | is very large (note |X| and |Y | are the sizes of the sets X and Y , respectively). Write an informal proof that if f has the weakly collision resistant property then f has the one-way property. You can do this by writing a contrapositive proof. So assume that f does NOT have the one-way property, and then give an informal proof that f will NOT have the the weakly collision resistant property. Recall: One-way property: Given y ∈ Y it is infeasible to find x ∈ X such that f(x) = y. Weakly collision resistant property: Given x ∈ X it is infeasible to find x 0 ∈ X with x 0 6= x such that f(x 0 ) = f(x). For the next questions: Implement the following functions all in one program file. A file called sha3in.txt is provided to you which is a file of 1600 bits. This is the input to your program. Read in this file into your program and answer the questions based on this input file. 3. (5 points) Implement a function called inputSHA3() that turns a 1-dimensional array of length 1600, v[0 . . . 1599], to a 3-dimensional array a[0 . . . 4][0 . . . 4][0 . . . 63] such that a[i][j][k] = v[64(5j + i) + k]. 4. (5 points) Implement a function called outputSHA3() that turns a 3-dimensional array a[0 . . . 4][0 . . . 4][0 . . . 63] into a 1-dimensional array of length 1600, v[0 . . . 1599], such that v[64(5j + i) + k] = a[i][j][k]. 5. (10 points) Implement the function θ from a 3-dimensional array ain[0 . . . 4][0 . . . 4][0 . . . 63] to a 3-dimensional array aout[0 . . . 4][0 . . . 4][0 . . . 63]. To check your work, apply your function to the input file provided and the output aout[4][3][9 . . . 18] should be 0011011000. Apply θ to the input file provided. In your homework writeup, list the ten bits 1 aout[3][1][15 . . . 24]. Homework 4 ends here. If you want to get a head start on next week’s assignment you can start implementing the next functions. But please do not submit them at this time. You will see these questions again as part of the next homework. NextQuestion. Implement the function ρ from a 3-dimensional array ain[0 . . . 4][0 . . . 4][0 . . . 63] to a 3-dimensional array aout[0 . . . 4][0 . . . 4][0 . . . 63]. Note that the rho matrix is: rhomatrix=[0,36,3,41,18;1,44,10,45,2;62,6,43,15,61;28,55,25,21,56;27,20,39,8,14] To check your work, apply your function to the input file provided to you, the output aout[4][3][9 . . . 18] should be 0110011001. Apply ρ to the input file provided. In your homework writeup, list the ten bits aout[3][1][15 . . . 24]. NextQuestion. Implement the function π from a 3-dimensional array ain[0 . . . 4][0 . . . 4][0 . . . 63] to a 3-dimensional array aout[0 . . . 4][0 . . . 4][0 . . . 63]. To check your work, apply your function to the input file provided and the output aout[4][3][9 . . . 18] should be 0110110001. Apply π to the input file provided. In your homework writeup, list the ten bits aout[3][1][15 . . . 24].
1. (30 points) Write a program that generates the RC4 keystream. The program has three inputs: the integer n (as described in Rc4), the integer l which is the length of plaintext or ciphertext (the number of characters) and the array of bits which is the secret key. The output of the program should be an array of bits which is the keystream (it should have length n ∗ l). Your program must include two functions. 1) A function called DecimalToBinary(int number, int n), with two integer inputs number and n. Its output is an array of length n giving the binary representation of number. So DecimalToBinary(100, 8) should output [0,1,1,0,0,1,0,0]. 2) A function called ConvertBitArraytoInt(Array k, int n) should take an array of bits and n, and output an array of integers with every n bits converted to its decimal representation. So ConvertBitArraytoInt([1,0,0,0,0,0,1,1,1,0,0,1], 3) should output [4, 0, 7, 1]. This will be used to convert the secret key input to RC4 to its decimal equivalent to be used in the RC4 algorithm. Make sure to include lots of comments so that it is easy to follow your work. Each function should have a description of what it does. (a) Submit your code separately. (b) Suppose you want to encrypt the message M = BACDDAH, with key K= [1 2 3 6] when n =3. Run your program for the these values to generate the keystream. Write the keystream from your code in your writeup. Then use the keystream to encrypt M and write down the result in your writeup. (you can leave the ciphertext as a bit string). (c) Have your program find the keystream for the inputs: n = 8, l = 24, key=[1, 0, 1, 1, 1, 0, 0, 1 , 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1]. Write the keystream in your writeup. (d) Then use this keystream to find the corresponding ASCII plaintext from the ciphertext. Write the plaintext in ASCII letters in your writeup. Both the key and the ciphertext are available in file hw3.txt so you can easily read or copy from. [1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0] 2. (a) (5 points) Consider the CFB mode of operation. Alice has a message to send and she breaks it into 10 blocks (M1,…,M10) and encrypts them using AES in CFB mode and sends Bob C1, . . . , C10. Suppose during transmission of ciphertext, 1 there are two bit errors in the transmission of C2 and Bob knows that. Explain which Mi ’s will Bob correctly decrypt? and which ones are completely wrong? Briefly explain. (b) (5 points) We said that If the value of IV used in CBC mode is not reused then the encryption is CPA-secure (resistant against Chosen plaintext attack). Explain why CBC mode with a repeating IV is not CPA-secure. In order to show that an ecnryption scheme is not CPA-secure, suppose Eve knows M and M’ and has observed C and C’ (the corresponding ciphertexts), but does not know which ciphertext corresponds to which message and she would like to learn this information. Eve can ask Bob to encrypt any message she chooses for her under the chosen plaintext threat model. Show that Eve can choose a specific message and ask Bob to encrypt it such that from the ciphertext Eve can determine whether C was the encryption of M or M’.
1. (10 pts) (a) We use a multiplication algorithm that takes time O(log2 (N)) to multiply N1 ·N2 if N1 ≈ N2 ≈ N. If it takes 3 nanoseconds to multiply two 1000 bit numbers then how long would it take to multiply two 5000 bit numbers? (b) Let N be a large positive integer. The time it takes to factor N using trial division is O( √ N). Assume that N′ is a large positive integer and that the binary representation of N′ has ten more bits than that of N. Assume that it takes 11 nanoseconds to factor N using trial division. Approximately how long would it take to factor N′ using trial division? 2. (10 pts) Let’s say we switch from 1024-bit RSA to 4096-bit RSA. How much longer does decryption take? 3. (10 pts) (a) Suppose a programmer wants to compute the sum of integers from 1 to N. The programmer writes a program by adding 1 and 2 first and then getting the result and adding it by 3, and so on: (((1 + 2) + 3) + . . . + N). Find the running time this will take in terms of N. (b) The sum of integers from 1 to N is N(N + 1)/2. Find the running time in terms of N that it would take you to compute the sum using the formula N(N + 1)/2 instead. 4. (10 pts) Find the running time required to compute 6N in terms of N. The computer program would compute ((((6 · 6) · 6)· · ·) · 6). 5. (10 pts) Let Fn denote the nth Fibonacci number. We have F1 = F2 = 1 and for i ≥ 3, Fi = Fi−1 + Fi−2 (so F3 = 2, F4 = 3, F5 = 5, F6 = 8, . . .). Recall Fn ≈ α n , where α = (1 + √ 5)/2. Find the running time of an algorithm that exactly finds the integer Qn i=1 Fi using (((F1 ·F2)·F3). . .·Fn). Your answer should be O() of a function of n and not have an F in it. Explain your answer. For simplicity, assume that you already have F1, . . . , Fn in storage, so you don’t have to worry about the time to compute them.
1. (10 pts) The following ciphertext is encrypted using a monoalphabetic substitution cipher. Use the frequency analysis technique described in the lecture to decrypt this. Show the frequency of letters in the ciphertext and show your work. You can use different tools (with citing the source) to find the frequency of letters, or write your own code. But you are not allowed to brute force the ciphertext for finding the plaintext. It is important to show your work. If you only submit the final plaintext no points will be given. Explain your thought process as you try to decrypt this. This ciphertext is included in file hw1q1cipher.txt. ZIW VQKD LAFLIOFW YOSZWKWR ZIKGAUI ZIW SWQCWL GY ZIW ZKWWL EQLZOFU RQHHSWR LIQRGVL GF ZIW UKGAFR TWSGV TOKRL EIOKHWR QFR LQFU OF ZIW TKQFEIWL QRROFU ZG ZIW HWQEWYAS QDTOQFEW GY ZIW YGKWLZ Q SOUIZ TKWWMW KALZSWR ZIW SWQCWL EKWQZOFU Q UWFZSW VIOLHWKOFU LGAFR ZIQZ YOSSWR ZIW QOK 2. (10 pts) Write a program in C/C++ or Python3 that does encryption and decryption for Vigenere cipher. This should include two functions, one for encryption and one for decryption. The inputs to the encryption function is the plaintext and the keyword. The input to the decryption function is the ciphertext and the keyword. Submit your code. Test it to make sure it works properly. The input ciphertext and plaintext should not have space characters in them. A ciphertext file is included (vigenere-cipher.txt) to show you the format of the ciphertext. This is the example in the lecture notes. 3. (30 pts) The ciphertext provided in the file hw1q3-cipher.txt was encrypted using the Vigenere cipher. Determine the length of the keyword. First use the Kasiski method to make a conjecture about the key length by finding several trigraphs and factoring the distances between them. You can use this website to find the common trigraphs in the ciphertext and then find the distances. Assuming k is the length of the keyword, now write a program that finds the frequency of letters A… Z for every letters in positions 0, k, 2k, etc. in the ciphertext. This is exactly what we did in the lecture during the cryptanalysis. The output looks like this for example: [10, 0, 0, 1, 1, 3, 7, 0, 0, 5, 7, 3, 2, 2, 0, 0, 1, 0, 4, 1, 2, 3, 10, 0, 1, 6], which means that letter A appeared 10 times, letter B appeared 0 times and … . These numbers are different from the numbers you will get. You should have k output vectors of length 26. The second shows frequency of [A,…,Z] of the letters appearing in positions 1, k + 1, 2k + 1, etc. The third shows the frequency of the letters appearing in positions 2, k + 2, etc. Now write down those histograms in your answer sheet and underline every number that is 4 or more. Use the fact that the distances between A, E, T and A in the alphabet are 4, 15, and 7 to decide how much each shift was. Write down all possible shifts for each histogram. Determine the keyword. You can test your work by finding the keyword and using it to decrypt the ciphertext using the code in question 2. It is really important to show all your work. Show the vectors you have found, show all possible shifts, show what is the key, and finally the plaintext. Your program needs to do exactly what is asked in the question.
2. Tasks Part A: [36 points + 10 extra] p1.pcap Open the p1.pcap file in Wireshark and answer the following questions by analyzing the packets. 1. [ 2 point] What is the IP address of the DHCP server assigning IP addresses? 2. [ 6 points] What are the assigned IP addresses for devices with these MACs? (a) 08:00:27:8F:4C:61 (b) 08:00:27:76:1F:7C (c) 08:00:27:0C:66:53 3. [ 2 point] Did all of the above devices receive their IP address from the DHCP protocol? If not, which devices were not assigned their IP address by this protocol (identify by IP address)? 4. [ 8 points] A series of SYN packets are sent to a destination between frames 120 and 2121, and again between frames 2241 and 4250. (a) What is the purpose of these SYN packets? (b) What new information about the destination was obtained by the SYN packets between frames 120 and 2121? (c) What new information about the destination was obtained by the SYN packets between frames 2241 and 4250? 1 CSCI 180 – Computer Security (d) What type of packet was returned to the source from the destination to indicate these new information? Explain. 5. [ 4 points] Between frames 4365 and 4368 a device utilizes the ARP protocol (Request/Reply) (a) What is the purpose of the ARP protocol? (b) Which device is collecting this information (IP and MAC)? 6. [ 8 points] Between frames 4371 and 4382 a device floods the LAN with ARP replies (a) Is this valid without an ARP request? Why? (b) What is suspicious about these ARP replies? (c) Which client (IP and MAC) are these ARP replies affecting and what is the purpose behind these ARP replies? (d) Who is the attacker in this scenario? (Identify with IP and MAC)? 7. [ 6 points] One of the clients downloaded a document from the server using HTTP (a) Was the attacker able to successfully intercept the entire document? Explain what is happening in this case. (b) What is the document media type? (c) Does the victim have any indication this file was intercepted? 8. [ 10 extra points] Try retrieving the actual file being downloaded by the client, and explain the steps you took in details. Answer the following questions in regard to the document downloaded. The answers to this question will not be graded if you do not describe your approach for retrieving the file in details. We have not learned how to do this in class, this is an extra credit activity for you to try to figure out on your own. (a) What is the month and year the document was published (shown in first page)? (b) What is the title of the page on page 25? Part B: [20 points] p2.pcap Answer the following questions using p2.pcap. This is a packet capture (from the attacker’s machine) of a targeted, man in the middle attack using sslstrip to steal a username and password. This means that the attacker and the victim are both on the same network. The first three numbers of the IP address identifies the network, so in this case, both Victim and attacker’s IP addresses start with the same numbers. The victim is trying to send packets to an address outside of this network through the gateway. The gateway’s IP address also starts with the same numbers as the victim and attacker (since they are all in the same network). 1. [ 8 points] The arp spoof activity begins at packet #3: (a) Who is the attacker (What is his MAC address?) (b) Who is the attacker trying to impersonate (What IP address)? (c) Who is the victim IP? Hint: See the target IP address in the spoofed arp packets. (d) What is the attacker’s ACTUAL IP? This can be found given the MAC address. Do not confuse it for the IP that the attacker is trying to impersonate! 2. [ 4 points] The victim begins browsing the web at packet 11. Packets 11 through 168 represent the traffic generated by google’s instant search mechanism (i.e. results updated per keystroke). Packet 162 was his final query in this search, as he had finished typing the query string. What was his search string that he submitted to Google? Provide the search string, and explain which frame number you looked at. (Hint: it comes after q=) 3. [ 8 points] After Google.com, the victim next visits a website that enforces Strict Transport Security (TLS). 2 CSCI 180 – Computer Security (a) There is a lot of advertising traffic in the packet capture. What is the second website the victim visits (domain name will suffice)? Hint: it’s easiest to first search for SSL traffic handshake messages and then look around these frames for the http get request. Use the following filter: (ssl.handshake.type == 2) (b) A HTTPS session is established in packets 1303 – 1322. Is this SSL handshake between the victim and the website; or between the attacker and the website? (c) Packet 3284 is a plaintext HTTP POST request generated by the victim pressing the login button on the website form. What is the victim’s username and password?
2. Tasks Task 1: Setting up the environment by disabling countermeasures As previously discussed in class, Operating systems and compilers have implemented several security mechanisms to make the buffer overflow attack more difficult. In this section, in order to make the attack easier, we will first disable these countermeasures. • Address Space Randomization. In order to disable address randomization temporarily use the following command: $ sudo sysctl -w kernel.randomize_va_space=0 Remember that the changes we make are temporary, so if you reboot your system you will need to run this command again. To view the current settings for ASLR on your system you can use this command: $ sysctl -a –pattern randomize If the value is 2, it means full randomization is on, and if it is 0 it means that randomization is disabled. • StackGuard protection scheme is a method used by GCC compiler to prevent buffer overflow. We will disable this feature by using the -fno-stack-protector option while compiling the program. • Nonexecutable stack. The most recent version of gcc automatically marks the binary version of program to indicate that this program does not require executable stack. In order to disable this countermeasure we use the option -z execstack when compiling the program to make the stack executable. • Configuring /bin/sh As discussed in Lab1, the shell in Ubuntu20.04 VM has a countermeasure that prevents itself from being executed in a Set-UID process. In this lab, our victim program is a Set-UID program, and our attack is trying to run /bin/sh, therefore this countermeasure makes our attack more difficult. We will make our attack easier by linking /bin/sh to another shell that does not have such a countermeasure. Later we will see that 1 CSCI 180 – Computer Security it is not very hard for the attacker to defeat this countermeasure as part of the attack. You’ve already done this part in Lab1. In order to see if your shell is /bin/zsh type in: $ ls -la /bin/sh If it shows /bin/zsh you are good to go, otherwise run the following two commands: $ sudo rm /bin/sh $ sudo ln -s /bin/zsh /bin/sh Task 2: The shellcode Before doing the attack, let’s get familiar with the shellcode. A shellcode is a code that launches a shell. This is usually the malicious code injected by the attacker to the stack. A program called shellcodetest.c is given to you. Take a look at this file. code[] contains the program to execute a shell in bytecode. The C version of this code is provided below. It is as if you write a program to execute a shell in C and then compile and extract the bytecode from it. #include int main() { char *name[2]; name[0] = “/bin/sh”; name[1] = NULL; execve(name[0], name, NULL); } shellcodetest.c program is written to test this bytecode to make sure it will launch a shell. Compile this program using the following gcc command. $ gcc -m32 -z execstack -o shellcodetest shellcodetest.c Q1: Run the program and describe your observations. Add a screenshot of what you observed. Task 3: The vulnerable program You are provided with a program called unsafe.c. We are assuming as the attacker you have access to the executable file for this program which is also a root-owned Set-UID program. This program has a buffer overflow vulnerability and your goal in this lab is to exploit this vulnerability to spawn a shell with root privilege. Compile this vulnerable program by including the -fno-stack-protector and -z execstack options to turn off the StackGuard and the non-executable stack protections as shown below. $ gcc -m32 -z execstack -fno-stack-protector -o unsafe unsafe.c After the compilation, you need to make the program root-owned Set-UID. Remember the commands to do this from Lab1? This program has a buffer overflow vulnerability as indicated in the code. It first reads an input from a file called inputfile, and then passes this input to another buffer in the function copyfunc(). The original input can have a maximum length of 527 bytes, but the buffer in copyfunc() is only BUFFSIZE bytes long. Because strcpy() does not check boundaries, buffer overflow will occur. Since this program is a root-owned Set-UID program, if a normal user can exploit this buffer overflow vulnerability, the normal user might be able to get a shell with root privileges. Remember that this program receives its input from a file and this file is under user’s control. Your goal is to create the contents for inputfile, such that when the vulnerable program copies the contents into its buffer, a root shell can be 2 CSCI 180 – Computer Security spawned. Q2: Take a look at the unsafe.c program, assuming we are at the first line inside of copyfun() draw the stack frame in your report. This means your diagram will include the stack frames for foofunc() and copyfunc(). Also remember any function calls that have been completed is no longer on the stack. Task 4: Exploiting the vulnerability, the real attack To exploit the buffer-overflow vulnerability in the unsafe.c program, we need to prepare a payload (malicious code that is designed to execute a specific action on a target system), and save it inside inputfile. You are given a partially completed exploit code called exploit.py. The goal of this code is to construct contents that will be written in inputfile, and will later get copied into the buffer when the unsafe program is running and the buffer overflow vulnerability results in invoking a shell. You need to fill out parts of the code with ‘#Need to change’ comment. Your task is to (1) find out the values needed to complete exploit.py by debugging the unsafe code as described below. (2) finish exploit.py program and run it by typing python3 exploit.py. This will generate the inputfile. troubleshoot: If you receive a permission denied error when running exploit.py, you may need to give it execute permission. Try to change the permission to rwx–x–x, for example. After you created the inputfile by running the exploit.py, (3) run the vulnerable program unsafe. If your exploit is implemented correctly, you should be able to get a root shell with # sign. Once you spawn the shell you can check your effective uid and real uid by typing id on the screen. In order to be able to complete this task you need to refer to the explanation I have provided in class in regard to this assignment. To exploit the buffer-overflow vulnerability, the most important thing to know is the distance between the buffer’s starting position and the place where the return-address is stored. We will use a debugging method to find it out. The next section ”Help with gdb” is useful in finding the addresses. 3 CSCI 180 – Computer Security Help with gdb You can use gdb to get more information about the vulnerable program. Compile the code to debug the program: $ gcc unsafe.c -m32 -o unsafe_gdb -g -z execstack -fno-stack-protector Create an empty inputfile $ touch inputfile Run the debugger $ gdb unsafe_gdb Inside the debugger, create a breakpoint at the copyfunc() gdb-peda$ b copyfunc Then run the code inside the debugger: gdb-peda$ run At this point gdb stops before the ebp register is set to point to the current stack frame, so if we print out the value of ebp here, we will get the caller’s ebp value. We need to use next to execute a few instructions and stop after the ebp register is modified to point to the stack frame of the copyfunc() function. gdb-peda$ next You can print the address of the buffer using the command: gdb-peda$ p &buffer You can print the ebp address using the command: gdb-peda$ p $ebp Use Control+D or type quit to exit from GDB at any time. Now that you have the $ebp and &buffer values, look at the diagram you drawn for the stack frame and find the distance from the buffer’s starting position to the beginning of return-address (find this distance in decimal, not hex). This is the value of offset in exploit.py code. Find the other values that need to be changed in the Python code. 4 CSCI 180 – Computer Security Q3: Deliverables: (1) Show a screenshot of your exploit.py code. (2) Write the values of &buffer and $ebp and explain how you came up with the offset value and content[offset+0 to 3]. It is very important to clearly explain your approach in finding these values. (3) Show a screenshot of the result when you run the unsafe program, and the result of id from the shell you invoked. Task 5: Defeating shell’s countermeasure As explained before, the shell in Ubuntu 20.04 drops privileges when it detects that the effective UID does not equal to the real UID. This is what we saw in Lab1, and in order to make our attack work, we changed the shell we are using in Ubuntu to a version that does not have this countermeasure. In this task, we want to see that even if we don’t disable this countermeasure, the attacker is able to defeat this. In order to be able to test this, you first need to change the shell back to a version with the countermeasure by using the following commands: $ sudo rm /bin/sh $ sudo ln -s /bin/dash /bin/sh One approach for the attacker to defeat this countermeasure is to change the real user ID of the victim process to zero before invoking the shell program. This way, when the shell compares the effective uid and the real uid they both will be equal to zero. This is because the effective uid is 0 as a result of the program being a root-owned Set-UID program. We can achieve this by calling setuid(0) before invoking /bin/sh in the shellcode. The bytecode for calling setuid(0) is as follows. All you need to do is to add the following code to the beginning of the shellcode in exploit.py: Q4: Try the attack from Task 4 again and see if you can get a root shell. Check the uid by typing id and report it. Show screenshots. Please describe your results. Task 6: Defeating Address Randomization As mentioned in class, on 32-bit Linux machines, stacks randomization space is not very high and can be brute forced. In this task we will try to defeat the address randomization countermeasure by brute forcing. First we need to turn on the Ubuntu’s address randomization using the following command. $ sudo /sbin/sysctl -w kernel.randomize_va_space=2 Q5: Run the same attack as in Task 4 and report your observation. Show screenshots. We now try to attack the vulnerable program repeatedly, hoping that the address we put in the inputfile can eventually be correct. You can use the following shell script to run the vulnerable program in an infinite loop. If the attack succeeds, the script will stop, and you will get a shell. This may take a while, try it as long as it is possible depending on your system. You might want to let it run overnight if needed. #!/bin/bash SECONDS=0 value=0 while [ 1 ] do value=$(( $value + 1 )) 5 CSCI 180 – Computer Security duration=$SECONDS min=$(($duration / 60)) sec=$(($duration % 60)) echo “It has been $min:$sec (mins:secs)” echo “The program has been running $value times so far.” ./unsafe echo “” done Q6: Run this code and describe your observations. Show a screenshot of how long you have run the script. If you did not get to successfully run the attack after a reasonable time, first take a screenshot of your screen, then stop the program and report your result. In order to stop the program you can use Ctrl-C, and if it doesn’t work, just close the terminal. Show a screenshot of how long you ran the script. For this question, make sure you write down in your report whether you are using Amazon AWS or the virtual box. Note for those who are not familiar with writing shell scripts: Write the provided code in a file, suppose you name it myattack. Then run this file: ./myattack. If you get a permission denied error, give the file execute permission and run it again.
2. Tasks Task 1: Installing John the Ripper John the Ripper is one of the most commonly used password crackers that is freely available. Do the following steps inside your VM. A: Installing on VM 1. Go to this page: Click Here 2. Go to the second section titled: Download the latest John the Ripper jumbo release 3. Choose the first one: 1.9.0-jumbo-1 sources in tar.xz, 33 MB (file name is: john-1.9.0-jumbo-1.tar.xz) 4. Click on Save file and the file will be downloaded in the Download folder. 5. Go to the Download folder and right click on the file, select Extract Here to unzip it. You will see a folder named john-1.9.0-jumbo-1. You can move this folder to any other location if you want in order to access it easier. 6. Open a terminal, change directory to where this folder is. If you have not moved it this will be the command: cd Downloads/john-1.9.0-jumbo-1/ 7. Change directory to the ‘src’ folder: cd src 8. Type: ./configure && make. This step might take about 5 to 7 minutes. B: Installing on Amazon AWS If you are using Amazon AWS use the following commands on the terminal after connecting to Amazon AWS to download and install the file: 1. sudo apt-get install libssl-dev 2. wget https://openwall.com/john/k/john-1.9.0-jumbo-1.tar.xz 3. After the file is downloaded type this command to unzip the file: tar -xf john-1.9.0-jumbo-1.tar.xz 1 CSCI 180 – Computer Security 4. Change directory to john-1.9.0-jumbo-1 folder using cd command. 5. Change directory to the ‘src’ folder: cd src 6. Type ./configure && make After the installation is done, change directory to ‘run’ folder by typing: cd ../run/ Then execute the program by typing: ./john You should be able to see the following screen. This shows that you have successfully installed the program. The list shows various options available to use while running the program. Take a look at the following documentation files: • More information about the options can be found in john-1.9.0-jumbo-1 > doc > OPTIONS. • The definition of modes such as wordlist, and incremental are described in john-1.9.0-jumbo-1 > doc > MODE. • Examples on how to use the system are shown in john-1.9.0-jumbo-1 > doc > EXAMPLES. • The john-1.9.0-jumbo-1 > doc > CONFIG file describes the configurations that you can modify. If you want to modify any of the configurations you need to change john-1.9.0-jumbo-1 > run > john.conf file. For example, if you want to emit a status line whenever a password is cracked find the following line in john.conf and change the ‘N’ to ‘Y’: CrackStatus = N. StatusShowCandidates is also useful in showing the number of password guesses tried. The result of your password cracking will be shown on the screen and will be stored in a file called john.pot. When you use multiple modes of cracking, the new results will be appended to this file. Q1: First change the CrackStatus and StatusShowCandidates configurations in john.conf file, and show a screenshot of this section of the file in your report. 2 CSCI 180 – Computer Security Task 2: Cracking a set of passwords You should have downloaded two files for this exercise. The target.txt file is a list of username and password hashes (md5) you are trying to crack. The dictionary.txt is a list of common words that you can use as a dictionary while running the password cracking attacks. Your goal in this task is to crack as many of the password hashes as possible from the target.txt file provided. You should try multiple modes with different variations. For example, you can try wordlist mode by using the command: ./john -wordlist=/dictionary.txt -format=raw-MD5 /target.txt For this exercise always use -format=raw-MD5 to identify the hash function. The wordlist is the simplest mode and will just try words from the dictionary. You can then try adding some mangling rules to each word in the dictionary by adding the option -rules to the command. -rules applies a default set of rules called Wordlist to the dictionary words. Take a look at the john-1.9.0-jumbo-1 > run > john.conf file and try to find other rule set names. Remember that the incremental mode will continue generating guesses for a very long time and may never finish, so you would want to try this option at the end, and manually stop this at some point (by pressing Ctrl-C). Q2: Start cracking the hashes in target.txt file. You should try at least 4 different modes/techniques for cracking. Out of these modes you should try at least one rule set by using -rule=. Submit the list of passwords you were able to crack with each mode, and briefly explain what this mode does and how it generates guesses. Either show the plaintext passwords with their hashes, or with the username. Show a screenshot of the command lines you used when cracking the passwords. Task 3: Find the password with the provided information Q3: Suppose you have forgotten the password you have used for a password-protected file, but you remember using the word “jackinthebox” where some of the letters were uppercase. You have also possibly replaced a with @, i with 1, e with 3 or o with 0. You have added 5 digits either to the end of it, or at the beginning. Look into John the ripper documentation and see if you can find a mode that helps you try guesses with the information given to you. Note that the mode you select must use the information provided. Just simply brute-forcing or using modes that do not take this into account is not accepted. The goal of this assignment is for you to read documentation of a software to be able to learn how the software works, as well as learning how easy it can be to do password cracking when targeting an individual with some known information on how they create their password. The MD5 hash of the password is given to you in password.txt. Try to find the password and explain the command you tried. Show screenshots.
2. Tasks Task 1: Using System() function In this task we study how the system() function works. This function is used to execute a command from a C program, but unlike execve(), which directly executes a command, system() actually executes “execl(“/bin/sh”, “sh”, “-c”, command, (char *) NULL);”, meaning it executes a shell /bin/sh first and asks the shell to execute the command. execl() function searches for an executable file if the specified filename does not contain a slash (/) character. The file is sought in the colon-separated list of directory pathnames specified in the PATH environment variable. If the specified filename includes a slash character, then PATH is ignored, and the file at the specified pathname is executed. Write a program called systemtest.c: Compile it: gcc systemtest.c -o systemtest Run the program to see how it works. Now we are going to write our own “ls” program to see how the environmental variable PATH works. Write a program called ls.c: Compile and run it. Q1 part A: If you run the systemtest program, what do you see as the result? Describe and explain your observations. Don’t forget a screenshot. 1 CSCI 180 – Computer Security Note that now there are two ls programs: 1) the one existed to list the files which is located at /bin/ls, and 2) the program you just wrote and compiled. How can we ensure that when we run systemtest it runs our ls program instead of /bin/ls? You can change the PATH environment variable in the following way: PATH=.:$PATH The “.” represents your current directory. So this new directory has been added to the beginning of the PATH variable, so the first location the system looks for is your current directory. You can view the PATH variable by typing: echo $PATH After changing the PATH variable run systemtest again to see what has changed. Q1 part B: Explain what has happened. Add a screenshot of your observation. Task 2: Set-UID programs Now we want to make our systemtest program a Set-UID program. Change its ownership to root, and make it a Set-UID program: $ sudo chown root systemtest $ sudo chmod 4755 systemtest Now any other user (e.g. you) who runs this program, will run it with root privileges. So the “ls” program that is running by the system() function is running with root privileges. How can you check this? Try changing our “ls” program so that it can print out the real user id and effective user id. You can use the functions getuid() and geteuid() respectively for this. Q2 part A: What do you expect the values of real user id and effective user id to be? What is the result you get? If the value you see does not meet your expectation read the Note section below and follow the steps. Note: The system(cmd) function executes the /bin/sh program first and then asks this shell program to run the cmd command. In Ubuntu, /bin/sh is actually a symbolic link pointing to another shell. Depending on which shell it is linked to, the shell might have a countermeasure that prevents itself from being executed in a Set-UID process. If it detects that it is executed in a Set-UID process, it immediately changes the effective user ID to the process’s real user ID, essentially dropping the privilege. Since our systemtest program is a Set-UID program, the countermeasure can prevent our attack. To see how our attack works without such a countermeasure, we will link /bin/sh to another shell that does not have such a countermeasure. We use the following commands to link /bin/sh to zsh. Make sure to type in these two commands exactly as it is. $ sudo rm /bin/sh $ sudo ln -s /bin/zsh /bin/sh Q2 part B: Now re-run the program again. What are the real and effective user ids of our ls program? Describe and explain your observations. Show a screenshot. Task 3: Real attack So far we wrote a ls program to run instead of the /bin/ls program that was the intent of the victim to run. Our ls program is not doing anything harmful except printing a few lines. As an attacker, what should your ls program be? If your ls program is a shell itself and you (as an attacker) manage to execute it instead of /bin/ls with root privilege, you can run any other program or command from this shell. Try to copy a shell and name it ls. Then try to run this shell from the systemtest program with root privileges. If you are successful you should get a new shell and if you have root privilege your shell will have a “#” sign in the beginning. 2 CSCI 180 – Computer Security Q3: Describe the steps you took to run a shell from systemtest with root privileges. Explain your observations. Include a screenshot. Task 4: Capability Leaking To comply with the principle of “Least Privilege”, Set-UID programs often permanently relinquish their root privileges if such privileges are not needed anymore. Also in cases when the program needs to hand over its control to the user, root privileges must be revoked. The setuid() system call can be used to revoke the privileges. According to the manual, “setuid() sets the effective user ID of the calling process. If the calling process is privileged, the real UID and saved set-user-ID are also set”. Therefore, if a Set-UID program with effective UID 0 calls setuid(n), the process will become a normal process, with all its UIDs being set to n. When revoking the privilege, one of the common mistakes is capability leaking. The process may have gained some privileged capabilities when it was still privileged; when the privilege is downgraded, if the program does not clean up those capabilities, they may still be accessible by the non-privileged process.Our goal in this section is to observe how this happens in this example. Compile the following program, change its owner to root, and make it a Set-UID program. Run the program as a normal user. Before running the program, you need to create the /etc/readonlyfile file as root (root-owned file). Then change the permissions of the file to 644 (Read-only by others). Q4: Answer the following questions: What happens in the code when setuid(getuid()) is called? After running the code, is /etc/readonlyfile modified? Show a screenshot. Explain what the expected behavior was and what actually happened. Did you expect the file to be modified based on the permissions? Why or why not? Read the explanation at the beginning of this task again and speculate why this has happened. You don’t need to have the correct answer to this question! #include #include #include void main() { int fd; /* Assume that /etc/readonlyfile is an important system file, and it is owned by root with permission 0644. Before running this program, you should create the file /etc/readonlyfile first. */ fd = open(“/etc/readonlyfile”, O_RDWR | O_APPEND); if (fd == -1) { printf(“Cannot open /etc/readonlyfile ”); exit(0); } /* Simulate the tasks conducted by the program */ sleep(1); /* After the task, the root privileges are no longer needed, it’s time to relinquish the root privileges permanently. */ setuid(getuid()); // getuid() returns the real uid 3 CSCI 180 – Computer Security if (fork()) { // In the parent process close (fd); exit(0); } else { // in the child process /* Now, assume that the child process is compromised, malicious attackers have injected the following statements into this process */ write (fd, “Malicious Data ”, 15); close (fd); } } 4
2. Tasks Task 0: Disable countermeasures In this section, in order to make the attack easier, we will first disable the address space randomization. In order to disable address randomization temporarily use the following command: $ sudo sysctl -w kernel.randomize_va_space=0 Remember that the changes we make are temporary, so if you reboot your system you will need to run this command again. To view the current settings for ASLR on your system you can use this command: $ sysctl -a –pattern randomize If the value is 2, it means full randomization is on, and if it is 0 it means that randomization is disabled. Task 1: Understand the code and Crash the program Compile the vulnerable code given to you using the -m32 option: $ gcc -m32 vul.c -o vul Note that as always we assume that the program is only readable/executable by you, and there is no way you can modify the code. However, in order to simplify our attack we assume we have access to the source code to be able to design the attack. Take a look at vul.c code, understand what it is doing, run the code to see what it does. Q1-A: Find the line of code that has the format string vulnerability and mention it in your report. Draw a draft of the stack frame. Your stack frame should include the stack frames of myprint() and printf(), but only the 1 CSCI 180 – Computer Security printf() that has the vulnerability. Do not report your stack frame it at this point, but you need to complete it and submit it for the next step. Drawing the stack frame is really important to understand what you have to do in your next steps. Q1-B: Find out what you should enter as the input string in order to crash the program (get Segmentation fault or Illegal Instruction or a similar error). Show a screenshot of your input and the result. Task 2: View Memory Values and Complete the Stack Frame Your first goal here is to enter a string as the input to the program such that you can see what is inside the memory locations of the stack frame. This will help you complete your drawing of the stack frame. As you take advantage of the format string vulnerability in this code to view the content of the memory, you will notice that there are some other values pushed into the stack in between the stack frames of printf() and myprint() functions. The target=0x11111111 variable will guide you to figure out how many values are pushed in between the two stack frames. This is very important for your next step. The target variable holds a hex value and so you will see the exact value of 11111111 printed out. Q2: Show the screenshot of your result. You need to show what you have entered, the result that is printed out to the screen, and submit the drawing of your completed stack frame. Task 3: Write an Integer to Memory In this task, your goal is to write something to the memory. The idea is as the attacker, we can write an integer into ANY memory address using %n. Your goal is to modify the value of the variable target. Since we need to know its address, we are “cheating” by printing out the address of this variable in the vulnerable code. Of course, in real attacks, the attackers have to find this address by other means. You need to create a string as the input to the program and include the address of target as part of your input, such that, you modify the value of target variable. As you can see the code prints out the value of target before and after the line of code that has the vulnerability and this is how you can check if you were able to successfully modify this variable. The exact stack frame that you drew in the previous task, can help you in carefully crafting your input string. In order to be able to do this, you need to provide the address of target as part of your input string. Here are the explanations on how to create an input string that contains an address. HOW TO: As we discussed in class and in the previous lab, most of our computers are little-endian machines, which means that the least significant byte of an address is stored in the lower address. So in order to store the address 0xAABBCCDD in memory, we need to save it in this order: 0xDD, 0xCC, 0xBB, 0xAA. If we enter 0x05 as part of the input string, the program will take the ASCII values of ’0x05’, rather than the hex value 0x05. The challenge is that there is no keyboard character that can be typed that is equivalent to 0x05, so we are not able to type it in as the input. One way to solve this problem is to write our input string in a file, and then use the file as the input to the program. The printf() function can actually write the address for us. Here is how it works. Suppose you want to enter the following string as your input: 0xffbfcd05.%x.Hello.This.is.me You can type the following command on your terminal that creates this string and puts it into the file called inputfile. $ echo $(printf “x05xcdxbfxff”).%x.Hello.This.is.me > inputfile In order to run the vulnerable program and use the content of the inputfile as the input string use the following command on the terminal: 2 CSCI 180 – Computer Security $ ./vul < inputfile Q3: If you manage to create your string correctly the value of the target variable will be changed and you will see that as the value of target after change as a hex value. Show a screenshot of this result. Show how you created your string. Then think about how %n works and what it writes into the memory and explain what this new value represents and where it is coming from.
