Tuesday 24 May 2016

From Session to JWT : A graceful migration.

Introduction

Today, We will discuss about a relatively new way of authenticating requests in a stateless manner which I recently implemented for a client. We will also discuss about some of the issues with sessions and how JWT solves those problems. Finally I hope you can read more and consider migrating to JWT.

Plain Ol' Sessions

HTTP is a stateless protocol. This is because each request is new to the server irrespective of if the same client made the same request, and it is also connection-less in that when a request is made, a response is returned and the connection is closed.
The first problem that comes to mind is how does a server distinguish between several users? If I was a server, I would like to know who was requesting for content as that might allow me to send meaningful and personalized content. This is the problem of maintaining state.

This problem was first solved with the use of cookies. Cookies were a relatively good solution to the problem of maintaining state. Basically, when a user makes a request, a server sends back certain data that the user must attach with each subsequent request. It is this combined with additional processing at the server that enables us to distinguish each user.

Note that with each new request, the server must use the simple data sent with the request to get more information about the user. This can be making database calls or accessing a session data store. This can slow down the application.

Another issue with sessions is that it goes against the fundamental nature of HTTP which is that it is a stateless protocol. Sessions store state and try to verify every request. What if there was a way to achieve stateless authentication of a request without the need for any extra calls o a data source?

JSON Web Tokens (JWT)

JWT is an open standard for securely creating and signing tokens that assert a number of claims.
The first thing to have in mind is that JWT is just JSON and the aim is to carry some claims with each request to the server. Let us look at the structure of JWT and how it fits into the whole framework of of authenticating a request.

Header

The header looks something like this: header = '{"alg":"HS256","typ":"JWT"}'
This states the type of  token and that it is signed with HMAC-SHA256.

Payload

The pathyload contains the data the server want to send to the user. It can contain information such as an email or username. It looks like this: payload = '{"username":"admin","iat":1458694982, "email" : "@gmail.com"}'


The third and last part is called the signature and it involves the base64 encoding of both the header and the payload. We will consider these functionalities in terms of functions and who's (server or client) responsibility it is to perform the function.

Generating and Signing of Token

 When a request is made and the request contains no token, the server assumes that the user is not authenticated and send a 401 not authorized. Suppose that the user is trying to login or register, then it is the function of the server to generate and sign a token which is sent back to the client.


    function generate(privateKey, header, payload) {
        unsingedToken = e(header) + . + e(payload);
        signature = HMAC-SHA256(unsignedToken, privateKey);
        token = e(header) + . + e(payload) + . + e(signature);
        return token;
    }

So there is a private key that is known only to the server and is used for signing tokens. The function e(x) used is the base64url encoding scheme. Notice that the token uses dots to demarcate the header, footer and the signature parts. This is what is sent to the client and proves that the client is now authenticated.


Verification of Tokens

It is the function of the server to verify the authenticity of a token that is sent as part of a request.  The server knows that all its tokens are secretly signed and so, if this token is able to produce the same signature segment as what would be produced by the server then it must have been signed by the server and is hence authentic. Below is a basic idea of how the pseudocode should look like


    function generate(privateKey, header, payload) {
        unsingedToken = e(header) + . + e(payload);
        signature = HMAC-SHA256(unsignedToken, privateKey);
        token = e(header) + . + e(payload) + . + e(signature);
        return token;
    }

    //decode is base64decode function
    function(privateKey, token) {
        
        payload = decode(token.split(.)[1]);
        header = decode(token.split(.)[0]);
        return token == generate(privateKey, header, payload);
    }

As you can see in the second function, we basically fetch the header and payload parts by splitting by the dot operator. Subsequently we can re-generate a token based on our private key and compare with what the client sent in the request. If they don't match we reply with a 401 unauthorized otherwise, we allow the request to be handled.

The function of the client

The main function of the client is to store the token and ensure it is sent along with every request. To store the token in a browser, we can use local storage. Though this is not implemented in all browsers, we can default to using cookie storage.
With each request, the client must send the token as a header to the server.

Conclusions

JWT solves the problem of authenticating request beautifully. In place of HMAC-SHA256, You can use RSA public/private key system. It can also be extended to authenticating API requests. 
Migrating to JWT is easy and straight forward. It comes with libraries to handle the generating and signing of requests. It is also easy to make the client send the token on each request. All in all, you get an easy, stateless and efficient way to handle authentication.

For more about JWT please check out JWT
Qusestions : Leave in comments or shoot me an email at : arthurugochukwu@gmail.com

Tuesday 17 May 2016

Binary Search


Last week, We discussed about socket programming. This week, We will discuss about a searching algorithm called binary search.
  1. Seaching Problem
  2. Motivation for Binary Search
  3. Basic Binary Search
  4. Using Loop invariants to understand it.
  5. Using Binary search to find roots of certain equations.
  6. Binary Search to the answer.
  7. Summary and Conclusions
One of the most basic problems in computer science is to find an item in a list of items. Without any additional information, we have no choice but to search through each and every element in our list. The cost of searching in such a case is linear. If the list is searched often, then we might probably solve the problem more efficiently with a HashTable , but that would require more space.

Linear Search




int search(int[] a, int key) {
  if(a == null || a.length == 0) return -1;
  for(int i=0;i<a.length;i++) {
    if( a[i] == key ) {
      return i;
    }
  }
  return -1;
 }





Motivation For Binary Search

Binary search becomes effective when the array is sorted. In that case, just searching the array one at a time is naive. We can do better.

Suppose you are to search for a key=3 in a list from 1 to 100. Would it make sense to keep on searching If I told you to start from the item 10 ? Of course not because, after 10, all numbers after it are greater and there is no way to find the key 3. In such cases, binary search works well.

The idea is to search in the middle, check if you have gone to far and adjust the bounds. This technique is called divide and conquer. Let us look at a simple code to show it.
.
int search(int[] a, int key) {
  if(a[0] == key)  return key;
  int lo=0, hi=n-1;
  while(lo < hi) {
    int mid = lo + (hi-lo+1)/2;
      if(a[mid] > key) {
        hi = mid-1;
      }
      else {
        lo=mid;
      }

  }

  if(a[lo] < key)  return -1;
  return lo; // :)
}


How do I know If I am correct ? Well, I am using something called a loop invariant . A loop invariant is a property of a program that remains true before, during and after a program executes.
The loop invariants I maintained that enabled me to be check program correctness are


[0, lo]  Within this range, I am sure that always, a[i] <= key
[lo+1, hi]  Unexplored region, I know nothing about this range.
[hi+1,  n-1]  Within this range I am sure that  a[i] > key

So within each iteration, I compute the value of  mid if I my  mid falls within the first range, I push lo=mid , otherwise, I push  hi=mid-1. That way, i respect my invariants.

Using Binary Search to find solutions to certain monotonic functions
Write code to find the sqrt(int x). You are not allowed to use any language library functions.

To the untrained eye, It is not immediately obvious that this is solvable with binary search. Consider the function 

f(x) = sqrt(x);

if f(x) = d, then d*d = x.

Notice that if for a certain g, g*g > x, then for all t > g,

It is clear that t*t > x and so we need to adjust the range

by setting hi = mid.

Similarly, if for a certain g, g*g <= x, then for all t <= g,

t*t <= x and we set lo=mid . The function is clearly monotonic. :)

public int sqrt(int a) {
  double a1 = 1.0*a;
  double lo = 0.0;
  double hi = 1.0*a;
     
  for(int i=0;i<=1000;i++){
    double mid = (lo+hi)/2.0;
    if(mid*mid > a1)  {
      hi = mid;
    }
    else  {
      lo = mid;
    }
     
    return (int)lo;
  }

}

Notice that we ran the code for 1000 iterations, It is common to run the algorithm for a certain number of iterations for the solution to converge to the right answer. Such is common in codeforces Thanks to Mike Mirzayanov.

The last part is "Binary Search to the answer". This is kind of like a generalization to the binary search approach.
Suppose we have a range [L, R] and a predicate function f(x) that is monotonic over this range(L, R), then we can solve certain optimizations problems in R-L+1 * O(f) time if O(f) = O(n) then it is O(nlgn).


The basic binary search can be casted in terms of this where the predicate function is O(1).

Let us look at a recent problem on codeforces and how I solved it with binary search to the answer.

Problem Statement

Waking up in the morning, Apollinaria decided to bake cookies. To bake one cookie, she needs n ingredients, and for each ingredient she knows the value ai — how many grams of this ingredient one needs to bake a cookie. To prepare one cookie Apollinaria needs to use all n ingredients.
Apollinaria has bi gram of the i-th ingredient. Also she has k grams of a magic powder. Each gram of magic powder can be turned to exactly 1 gram of any of the n ingredients and can be used for baking cookies.
Analysis
Your task is to determine the maximum number of cookies, which Apollinaria is able to bake using the ingredients that she has and the magic powder. 
She can always bake 0 amounts of cake (base case).

If she can use x, then she can also use x-1. Though we don’t know if she can use x+1 and above.

How can we know if she can use x to back cake? Just do a simple linear simulation

This two statements are sufficient to solve the problem. This is the link to my solution during the contest.

In summary, you can use binary search to solve the basic searching problem provided that the list is sorted by some key. You can also extend this to find the roots of certain monotonically increasing/decreasing functions.


Finally, If you can show that a certain process or function has the monotonic property, then we can use binary search to the answer to solve certain optimization problems related to it.

Phew!!!. See you next week.




Tuesday 10 May 2016

Socket Programming

What are Sockets ?

Sockets are communication endpoints that allow transfer of data between different programs.
These programs can live on different servers and still communicate using sockets.
Both communicating programs must expose a socket to allow data to be shared between both programs.

A socket is characterized by a pair; its IP address and port number.  Several programs on the same machine usually share the same address and so we need the port to distinguish between programs on a single machine.

A connection can be established over TCP or UDP depending on the nature of the programs that are in communication.  TCP means transmission control protocol and is used to create reliable, sequence, flow-controlled two-way communication based on byte streams.
UDP means User Datagram protocol and is unreliable as there is no guarantee that the packets will arrive or will be in order.

A connection therefore can best be described as the tuple (Protocol, IP, Port, RemoteIP, RemotePort) and it must be unique for any two communicating processes.

What are some use cases of sockets?

Sockets are used when there is a need for communication to take place between two programs such as
1. Database access, 
2. Spreading tasks across different hosts
3. Chat/messaging applications.

In this post, we are going to be implementing a simple example of a service that is able to return the Capital city of any country. The client sends a request for the capital of a country and the server responds with the right answer.

Possible extensions include improving the service to instead send a small wiki about any country or
send me my personal data/files with the click of a button.

Implementation

All implementation details are found here github. Hope you enjoy testing the example.