FLOW TRACKER – A Flow Analysis to Discover Side Channels



FlowTracker Usage

A simple example

In cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a crypto system by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and the time can differ based on the input; with precise measurements of the time for each operation, an attacker can work backwards to the input.

Information about the key or other sensitive information can leak from a system through measurement of the time it takes to respond to certain queries. How much such information can help an attacker depends on many variables: crypto system design, the CPU running the system, the algorithms used, assorted implementation details, timing attack countermeasures, the accuracy of the timing measurements, etc.

Below we can see a simple example of String Matching implementation. In this example we have a main function which reads a string from terminal and calls compVar function in order to know if the received input is equal to string pw (“secret”). compVar function do not execute in constant time, because for instance if the first character of those string does not match, compVar returns immediately. But if the strings are identical the loop for execute all 7 iterations. So, the time for return to main will be increased. This is the vulnerability named timing attack.

Lets go to example code. You can copy and paste this code in a .c file in order to submit it to our online tool.

  /*If pw == in returns 1, else returns 0 */
  int compVar (char *pw, char *in) {
    int i;
    for (i=0; i<7; i++) {
      if (pw[i]!=in[i]) {
        return 0;
      }
    }
    return 1;
  }

  int main(void) {
    int comp=1;
    char pw[]="secret";
    char in[7];
    int result;
    scanf ("%s", in);
    result = compVar(pw, in);
    printf ("%d", result);
  }


Please, see that you must inform in a xml file the functions and respective parameters which you consider sensitive or secret. Below you can see an example of such an xml file. In this case, FlowTracker will locate the function named compVar and it will consider the first parameters (pw variable) as sensitive information. If the user specific parameter 0, FlowTracker will consider the function's return value as secret.

  <functions>
    <sources>
    <function>
      <name>compVar</name>
      <parameter>1</parameter>
    </function>
    </sources>
  </functions>


Finally, you can check standard output and table of content checkboxes in order to respectively get a summary of vulnerability reached and each vulnerable path.

Standard Output

For example above we got the following std output: 

********* Flow Tracking Summary ************ 
Secrets 1 
Branch instructions 2 
Vulnerable Subgraphs: 2

- Secrets informs how many secrets were found according the information provide in .xml file.
- Branch instructions is the total number of branch instructions in the .c file.
- Vulnerable Subgraphs is the total number of vulnerabilities reached in the .c file. For each vulnerability, FlowTracker will produce 3 other files at Table of Content output.

Table of Content Output

Table of content will produce the following information: A fullGraph.dot file and three files for each vulnerable path reached. You can download these files and/or download a .jpg version for any .dot files showed.

1 – FullGraph.dot file: FlowTracker works with the concept of dependence graph. A dependence graph is a graph where vertex are opcodes and operands from LLVM Intermediate Language and edges represents data dependence and control dependence (dashed edges).

2 – SubgraphLines.dot file: A subgraph of FullGraph file which has one or more paths connecting a secret to a branch instruction. This is a problem because the branch normally influences the execution time of the program. So, if an adversary can measure this time for a given input which he controls, it may discover some information about the secret that we want to protect. In this graph the shortest patch is in red color and each vertex has the line number which it has extracted from uploaded .c file.

3 – SubgraphLLVM.dot file: A subgraph of FullGraph file which has a one or more paths connecting a secret to a branch instruction. Different of the SubgraphLines.dot, in this file each vertex has a opcode or an operand. This file is useful only for who knows the LLVM intermediate language.

4 – SubgraphASCII.txt file: This is a useful output for who wants a concise information about the vulnerabilities reached by FlowTracker. Each .txt file has, in ASCII format, the shortest path detached in red collor at SubgraphLLVM and SubgraphLines dot files. For instance, if your output has SubgraphLines0.dot and SubgraphLLVM0.dot, you also has a SubgraphASCII0.txt which has only the shortest vulnerable path from those files.

For common users, the most important file is the SubgraphASCIII.txt because it shows the line of your code where the vulnerability starts and the line one where it ends. Of course, the intermediate lines are shown.

Example's Gallery

In this page we show some examples of programs, and the results that out flow tracker analysis produces for them. For all examples, our secret is the variable pw. We use the following keys in the table:



C-SRC

FULL DEP GRAPH

TAINTED SUB GRAPH

TXT-Files

XML

COMMENTS

ex1.c: this is an example of naive string matching algorithm. the function compvar does not execute at constant time because the return instruction inside the loop could ends the function before the last iteration for some inputs

ex2.c: again, an example of naive string matching algorithm. the function compvar does not execute at constant time because the attribution of variable isequal could not be done for some input

ex3.c: this is a good example of a function for string comparisson which runs in constant time and can be used in cryptosystem's implementation. of course, our tool did not found any vulnerable tainted subgraph in this example

ex4.c: again, this example runs in constant time. of course we have a branch instruction, but it is not problematic because the loop runs for constant iterations and the cost of each iteration is the same. therefore our tool did not found any tainted subgraph in this example

ex5.c: another example which the code runs in constant time. in this case the branch instruction for the while loop is influenced by information stored in the secret variable. however, again this loop runs all iteration and therefore the code is not dangerous. of course, our too did not found any problem with this code

ex6.c: at this example, the number of instructions in both side of branch instruction (true and false) is the same. however the execution time could be non constant because architectural aspects like cache miss, speculative execution and the respective pipeline flush for instance. so, flow tracker informs a vulnerability at this code

ex7.c: this example uses a ternary operator in order to make a test. llvm compiler translate this c code in such way that no branch instruction is generated. so, this example is safe because the translation is good

ex8.c: here we have an example where a secret information is used to memory indexing. so, this code is vulnerable to a attack named cache-timing attack. the rule for avoiding cache-timing attacks is "avoid table look-ups indexed by secret data". that's the rule stated in http://cryptocoding.net. flow tracker can find this kind of vulnerability

ex9.c: It is a tiny example showing that Flow Tracker is a inter-procedural analysis and It can get vulnerabilities inter-process.

armandoExample1.c: Thanks to Armando from IC-Unicamp by this example. Flow Tracker can get its vulnerability as well.

smult.c: is a implementation in constant time of eliptic curves diffie-hellman (curve25519). of course, the implementation is safe and flow tracker not found any vulnerability.