Tag: theory

Side-Channel Attack on LLC

Introduction

This semester I am taking a Cyber Security class and for the final assignment, I was tasked with performing a side-channel attack on a computer’s LLC(Last Level Cache).

Much like the last assignment to simulate quantum key encryption, there are two parts to the assignment. I was to create both a program and write a short report on the assignment. My report should cover both the theory behind the attack and the effectiveness of the program I created. To write the report I used LaTeX as I have found it to be a very effective tool this semester. I am writing the program for this assignment in Java though most languages should be effective.

What is a Side-Channel Attack?

First off I should explain what a side channel attack is. A side-channel attack is a method by which one can infer information about a computer or a program using indirect methods. If you want to learn more about side-channel attacks I would highly recommend reading about the Meltdown and Spectre vulnerabilities. The example for this assignment is inferring the size of the LLC of a computer’s CPU. Therefore to perform a side channel attack I must find an indirect way to infer the size of a computer’s LLC.

My Side-Channel Attack

After reading the article we were provided with when given the assignment I then decided on using differently sized arrays. I will measure the time needed to access data in the array and this should allow me to infer the cache size. I will step through the different sizes of arrays and measure a value for each. Plotting these values should allow me to see a spike in time which means we are having cache misses.

I used arrays from 1Kb in size up to 64Mb doubling at each step. For each size I will run 100 tests, each test will consist of incrementing values in the array 1 million times. Each test will be timed and the times for each size will be averaged. This should allow us to get an accurate value for each size without running into any outliers.

We will use two different methods to determine which element of an array we access. A random method, and a sequential method. This is another requirement of the assignment is that I test multiple methods for my attack.

Side-Channel Attack output
Output of Random Access Side-Channel Attack

The Report

I wrote a short report (5-page limit) on my methodology for the attack and the results I got from said attacks. I wrote this report using LaTeX as I have found it to be a very useful tool this semester. Included in the report were graphs of my results and an analysis of my results for each method. If you wish to read it in full the PDF is available below.

main.pdfDownload

Disclaimer

Though it should go without saying I will say. This is all for purely educational purposes. Do not run software of this kind on any systems you do not have permission to use. Also, ensure when testing software of this kind you are doing so in a secure environment and are in compliance with all local laws and regulations.

Regular Expression Parser and Compiler

I have been given an assignment focused on regular expressions (regexp) and parsing. This assignment is split into two parts. A parser and compiler that converts a regular expression into a set of Finite State Machines (FSM) that can then be loaded into a second piece of software that searches a piece of text for patterns that match the regular expression. I will work on the first part and my partner will work on the second.

The parser and compiler will adhere to a set of rules that have been laid out for us in the assignment document. An expression will then be run through that set of rules and the program will output a set of FSM that the second piece can then read. This will require format to be agreed with my partner but I feel this should be relatively simple. The rules for this compiler are as follows:

Rules

  • Any non-special character is a literal
  • . (period) is a wild card that can be any literal
  • adjacent regexps are concatenated to a single regexp
  • * indicates closure (zero or more) on the preceding regexp
  • ? indicates that the preceding regexp can occur zero or one times
  • | is an infix alternation operator such that if r and e are regexps r|e means r or e
  • ( and ) may enclose a regexp to raise its precedence such that (e) is a regexp that is equivilent to e
  • \ is an escape character that matches λ but indicates that the following character loses any special meaning and is a literal
  • Operator precedence is as follows:
    • Escaped characters
    • Paretheses
    • Repetition
    • Concatenation
    • Alternation
  • Optional: ! not operator

An example of this would be (r | e) a*:

State0123456
Typebrbrrebraλ
Next 1124454.
Next 213..6..
FMS Table of Regular Expression Above
Regular Expression FSM graph

I will continue to work on this over the next few weeks and provide updates as I go along with the development process.