February 22, 2017

Delay attacks - the forgotten attack?

The unlock scenario

Together with colleges at ASSA ABLOY, I am working with a secure channel protocol called Salt Channel. It is open source and can be found on Github. One potential application is to control a lock (lock / unlock commands) from a credential in the proximity of the lock (RFID card, mobile phone, fob).

Typical secure channel implementations, like TLS, provide confidentiality and mutual authentication. Data integrity is also provided. They generality protect against attacks such as: replay attacks, various types of man-in-the-middle attacks and more. However, I know of no secure channel protocol that protects against delay attacks.

A delay attack is an attack where the attacker simply delays a packet in the communication. This is definitely in the scope of what an attacker is allowed to do in just about any threat model. Also, in practice, it can be easy to perform. Delaying a packet may not seem like a threat at first. Surely, it did not appear to us while developing Salt Channel v1, that a packet delay could be a security issue. Well, it can!

The figure about shows the scenario. Alice wants to unlock Lock with her phone through a radio communication channel (Bluetooth, Bluetooth Low Energy, NFC) to Lock. Mallory intercepts the communication and function as a man-in-the-middle. Alice establishes a secure channel with Lock. This is successful since Mallory simply forwards all messages between Alice and Lock. Then Alice sends the unlock message to Lock. Mallory recognizes this packet by packets size, packet ordering and so on (based on studying previous communication sessions). Mallory cannot read the contents of the package, nor modify it, however she delays it. Alice detects that she cannot open the door. Something seems to not work. She walks away. Once Alice is gone, Mallory, who is hiding near the door, sends the unlock packet. The Lock unlocks and Mallory can get in through the door without being detected.

Literature

I have not found literature focused on this issue. Perhaps I am just googling wrong, I have not studied this much. Any help is appreciated. I don't even know a name for this, so I invented "delay attack" since I could not find a term for it. Surely, this must be treated in public literature already.

Note, that this is not a replay attack. The packet is not replayed and a delay attack requires completely different counter-measures.

Note, this is not a timing attack. Even though timing is involved, timing attacks is a completely different thing and should therefore not be used for this type of attacks.

Existing delay attacks

There seem to exist practical delay attacks against car key systems.

Protection

Many application layer implementations likely do not consider packet delay attacks and their implications. It can be argued that there should be protection against delay attacks in the secure channel layer.

When Alice sends the unlock command she implicitly wants the door to open now. Not in 60 seconds. We can see this as an integrity protection of her intent to unlock now. Of course, this could be handled by the application layer. But why not put it in the secure channel layer? It sure seems like a general problem to deal with in a general way.

Perhaps another blog post will deal with countermeasures of delay attacks. We need some.

March 11, 2016

TestableThread - a Simple Way to Test Multi-Threaded Code

Multi-threaded code is hard to write and hard to test. For years, I have been missing simple tools for testing multi-threaded Java applications. Anyway, for certain types of test situations the TestableThread class can be used. See below and the TestableThread class at the java-cut repo.

The idea is simple. By introducing named "breakpoints" in code run by threads, the test management code can control the execution of a thread by telling it to go to a certain breakpoint. Breakpoints are added to normal code using statements like:

assert TestableThread.breakpoint("breakA");

By using an assert, the breakpoint code will not incur any performance penalty when the software is run in production (the default way to run Java software is without -ea, that is, without enabling assertions).

Given defined breakpoints, test code can let threads execute till they reach a given named breakpoint, for example, the code:

t1.goTo("breakA");

will enable the t1 thread to run until it reaches breakpoint "breakA". When the breakpoint is reached, the t1 thread will stop executing until it gets another goTo() request.


The implementation below is only 50 LOCs or something, but still have been shown to be useful. There are, of course, lots of improvements / additions to be made including conditional breakpoints.

Code:

public class TestableThread extends Thread {
    private final Object sync = new Object();
    private volatile String breakName;
    
    public TestableThread(Runnable r) {
        super(r);
    }
    
    /**
     * Run thread until it hits the named breakpoint or exits.
     */
    public void goTo(String breakName) {
        synchronized (sync) {
            this.breakName = breakName;
            sync.notifyAll();
        }
        
        if (getState() == Thread.State.NEW) {
            start();
        }
    }
    
    /**
     * Run thread, not stopping at any break points.
     */
    public void go() {
        goTo(null);
    }
    
    public static boolean breakpoint(String breakName) {
        if (breakName == null) {
            throw new IllegalArgumentException("breakName == null not allowed");
        }
        
        Thread thread = Thread.currentThread();
        if (thread instanceof TestableThread) {
            TestableThread tt = (TestableThread) thread;
            synchronized (tt.sync) {
                while (tt.breakName != null && tt.breakName.equals(breakName)) {
                    try {
                        tt.sync.wait();
                    } catch (InterruptedException e) {
                        throw new Error("not expected: " + e);
                    }
                }
            }
        }
        
        return true;
    }
 }
 

February 21, 2016

The Unsolvable Rubik's Cube?

Introduction

A very puzzling thought has been on my mind for a while now: is it possible to create a mechanical puzzle, something like the Rubik's Cube, that is unsolvable in general, but still demonstrably solvable if one knows the scrambling moves.

Such a puzzle would be truly mind-boggling and incredible frustrating for puzzle-solvers. Imaging a puzzle that starts from the solved state, just like a Rubik’s cube with all sides completed. Then, a long enough sequence of random moves (a scrambling sequence) would make it impossible to go back to the solved state if the scrambling sequence is not known. If the scrambling sequence is known, it is however trivial to reach the solved state by simply applying the inverse of each move in the scrambling sequence in reverse order.

The definition of unsolvable

By impossible to solve or unsolvable, we mean that it is infeasible for a human to reach the solved state given a scrambled puzzle. To be concrete: there should be no general algorithm that solves the puzzle in less than 100 million moves. This roughly corresponds to one move every second for three years. Of course, one could always be lucky and find the solution faster, but on average, there should be no way to solve the puzzle in less than 100 million moves. And this is by my definition "infeasible" for a human to do.

Notation and puzzle properties

Let's go ahead and define this problem more rigorously.

Consider a mechanical puzzle with a finite distinct number of states. From a particular puzzle state, S, another state can be reached by making a move. A move, m, is a mathematical function from one puzzle state to the next.

    Si = mi(S_i-1)

OK, that looks ugly. MathML looks much better:

  S i = m i ( S i - 1 ) 

but it is slow to edit and does not work on all browsers (mobile phone browsers in particular). Let's go on using the ugly style.

Every move, m, has a corresponding inverse move, m'. So, for every move, m, and every state, S, there is an inverse move, m', such that:

  S = m'(m(S))

When dealing with long move sequences, the function notation with all the resulting parenthesis is too annoying, instead we will use the following notation:

  S3 = S0 | m1 m2 m3

to mean that when moves m1, m2, and m3 are applied to state S0, the resulting state is S3. So, with the new notation, we have:

  Si = Si-1 | mi

and

  S = S | m m'

Each puzzle state has a corresponding finite set of possible next moves. In the case of the Rubik's Cube, each state has 12 possible next moves (only 90 degree moves are considered, "quarter-turn metrics"). Often they are denoted: F, Fi, B, Bi, U, Ui, D, Di, L, Li, R, Ri.

The puzzle has one particular state called the solved state. Solving the puzzle is equivalent to finding a move sequence that transforms the current state to the solved state.

A scrambling of the puzzle is a random sequence of moves starting from the solved state. At each state, the next move is chosen randomly. Each possible next-move has the same probability of being chosen. A random scrambling of size n, is a random scrambling with n moves.

Now we are ready to summarize the properties of our puzzle. Lets call it an F-puzzle to distinguish it from other puzzles. An F-puzzle is a puzzle with the following properties:
  • The puzzle has a finite number of states.
  • One puzzle state is called the solved state.
  • Each puzzle state has a set of next possible moves. The set is finite and has a size of at least two.
  • For any state, S, and any move, m, there is an inverse move, m', such that:
    S = S | m m'.
  • A scrambling is a random sequence of moves starting from the solved state. The state after a scramble of size N is:
    S_scrambled = S_solved | m1 m2 m3 ... mN.
  • A scrambling is trivial to unscramble given that the scramble sequence is known:
    S_solved = S_solved | m1 m2 m3 ... mN mN' m(N-1)' ... m3' m2' m1'
Hopefully, that is precise enough. Tell me if the F-puzzle definition is not clear.

The Rubik’s Cube is one example of an F-puzzle. However, it is solvable. In particular, any scrambling of the Rubik’s Cube can be solved in 20 moves in half-turn metrics and 26 moves in quarter-turn metrics. See www.cube20.org.

The problem

So, now we can state the problem.

1. Can we create a mathematical unsolvable F-puzzle?

2. Can we create a mechanical unsolvable F-puzzle?

3. Can we create a practical mechanical unsolvable F-puzzle that can be mass-produced with a unit cost below 100 Euro?

To be concrete, we would like a mechanical puzzle that cannot be solved in 100 million moves after a scrambling of size 100 or less (20 or less would be nice). By "practical", we mean a puzzle that can be scrambled or unscrambled within one minute by most humans without training or tools. We also want a solution that is not a "mechanical computer"; it should be more of a Rubik's cube than a mechanical computer where symbols are used. For example, we don't want something like a code lock where digits are used to set a code.

That's the problem. Let's discuss potential solutions some other time.

February 11, 2016

The flaws of shared-secret authentication

Consider the scenario where Alice wants to authenticate to Bob; that is, prove her identity to Bob. Also, let us limit the discussion to digital communication.

Shared-secret authentication is common. In particular, password-based authentication is still the most common way to authenticate a user to website. Gmail, Twitter, Facebook -- all major Internet services still use some type of password-based login.

Shared-secret authentication is an authentication approach based on sharing secret information between Alice and Bob prior to the start of the authentication. For example a password (or pin code, Mifare UUID, credit card number etc) is shared between Alice and Bob.

The inherent flaws of shared-secret authentication are:
  • Impersonation. Since Bob knows the password of Alice, Bob can impersonate Alice if Alice reuses the same shared secret when authenticating with other parties.
  • Proliferation of secrets. To avoid the problem with impersonation, Alice may choose to use one password for each party she would like to authenticate with. The obviously leads to a problem of remembering the passwords and having password-recovery mechanisms for all of them.
  • No real identity. Shared-secret authentication can only be used among the parties who know the secret. Alice cannot use the same credential to prove her identity to others if she wants to avoid the threat of impersonation. Therefore, she cannot build a single identity between, for example, Internet services. The identity really only exists between Alice and Bob. Alice is not able to prove her identity to some one else using the same credential she is using to authenticate with Bob.
All these problems can be fixed! And, of course, the solution is to use public-key cryptography.

Let's call this public-key authentication. Alice and Bob generates key pairs and exchange their public keys with each other. Bob cannot impersonate Alice, Alice can safely reuse her credential for authenticating with multiple parties, and she can (if she chooses to) maintain a single identity between multiple parties.

The principle is: secret credentials should never be shared! The key pair should be generated by Alice and the private key should not leave the place where it was generated (except for backup purposes).

One could also call this type of authentication: zero-knowledge authentication. This is because Alice proves possession of her private key without revealing any information about the private key itself. She needs to reveal zero information about her secret credential to Bob or any one else.

Conclusion:

If Alice wants real, secure authentication, she should use public-key authentication. This requires a credential that can do public key crypto computations and handle a digital dialogue with Bob. To generate the key pair, a source of random data is also required.

October 25, 2015

Three fundamental types of identifiers: Local ID, Global ID, and Provable ID

Identifiers are crucial in information technology and in our society in general. There seems to be three fundamentally distinct types of identifiers. Surprisingly, I could not find any prior text on these identifier types, so I will describe them in this blog post.
  1. Local ID. Local IDs are unique, but only within a specific context. They require an ID issuer to attain unique IDs within the context. For example, an integer can be used as an ID of a row in a database table (primary key). This ID can be used to pick one row in the specific table. The database manager is the ID issuer that ensures that each row of the table has a unique ID. Uniqness of the ID is not guaranteed outside the ID context (the database table in the example).

    Local IDs are common. Examples include: domain names, passport numbers, email addresses, variable names and US social security numbers.
  2. Global ID. Global ID schemes require no central ID issuer. An ID can be 16 random bytes for example. Version 4 UUIDs, and GUIDs are other examples of global IDs. A checksum of byte content can be used as a global ID of the content as long as the content is static.

    Global IDs are (in practice) globally unique, but they can be forged. Anyone can create a specific global ID and claim that it identifies something.
  3. Provable ID. A provable ID is an identifier that in itself can be used to prove what it identifies. The identification (id -> entity) is provable. A provable ID cannot be forged like a global ID or a local ID. No one can create a different ID and claim that it identifies the same thing. Also, no one can use a particular provable ID and claim that it identifies something else.

    A provable ID is a cryptographic construction -- a public key or a secure hash or similar. A secure hash can be used to as a provable ID of static content (content-addressable storage [3]). The GIT version control system uses a secure hash (Merkle tree) to identify commits. This is one example of a provable ID.

    To identify entities that are "live" (can compute) their public key can be used as a provable ID. An entity identified with its public key can prove possession of the corresponding private key.
Some IDs have other information included in them beyond the data needed to identify an element. Such identifiers are not considered in this blog post.

That is my take on identifiers.

[1] UUID, https://en.wikipedia.org/wiki/Universally_unique_identifier
[2] GUID, https://en.wikipedia.org/wiki/Globally_unique_identifier
[3] Content-addressable storage, https://en.wikipedia.org/wiki/Content-addressable_storage

Blog name change

Today, I am changing the name of my blog from "From Theory To Disk" to "My Take on IT" to reflect a broader blog scope. Will possibly cover just about anything in information technology.

You can reach the blog at: http://blog.franslundberg.com/ as before.

January 8, 2015

BergDB 2015.1

Released a new version of BergDB today -- BergDB 2015.1. Download it from bergdb.com.