Identify and verify users based on how they type

Document options Document options requiring JavaScript are not displayed Sample code Rate this page Help us improve this content

Level: Introductory

Nathan Harrington (harrington.nathan@gmail.com), Programmer, IBM　

18 Mar 2008

Modify the GNOME Display Manager (GDM) to support user verification through keystroke-dynamics processing. Create and store a one-way encrypted hash of your keystroke patterns when entering your user name. Add code to GDM to read current keystroke patterns and permit a user to log in when the characteristics are a match.

Many commercial products today provide two-factor authentication on Linux® systems. These technologies generally require the purchase of additional hardware and create a closed implementation unsuitable for many environments. The code and processes presented here allow you to implement a low-cost authentication-input system based on the characteristics of how a user types his password into the GDM. Moving beyond examples and into implementation, the modifications to GDM presented here allow you to enhance the security of your computer.

What is GDM? GNOME, which is part of the GNU project, defines the GNOME Display Manager (GDM) as software that implements all significant features required for managing attached and remote displays. This includes authenticating users, starting the user session, and terminating the user session. As we learn here, GDM is readily extensible for supporting keystroke dynamics

Requirements

Hardware

Almost any computer manufactured in the past 10 years with any old processor and puny amount of RAM should provide plenty of power for building and using the code described here. This article was developed on IBM® T30 and T42 ThinkPads with Intel® Pentium® 4 processors, but slower hardware will be sufficient.

Software

Start with a standard Linux distribution, such as Ubuntu V7.10. You need the various libraries required to compile GDM from the source. Note that many libraries are required to build GDM, including everything from GTK to Xinerama, so plan to use your favorite package manager to pull down the prerequisites (see Resources).

Check Resources for the GDM source code and note that this article was built using the gdm-2.20.0 release. Keep in mind that this release will not compile straight from the archive on the Ubuntu V7.10 distribution. Small changes to the Makefile are described below to allow the make process to complete.

Back to top

General approach to simple keystroke dynamics in GDM

As a biometric, keystroke dynamics are relatively imprecise. Unlike Iris scans or fingerprints, even the most highly repetitive individuals make subtle variations in their typing patterns. The challenge in using keystroke dynamics in an authentication or verification context is to discern acceptable variations from incorrect credentials.

Consider Figure 1 below, which shows the intra-key release times of the author's typing of "nathan." (The trailing "n" is not measured because it is the final character in the string.)

As you can see, the delay between key releases are relatively regular for this particular user and this particular text. Note how the spike at position 19 indicates an extended pause between keys, but the rest of the entries are grouped in relatively close proximity. Therefore, an algorithm that permits a "close-enough" match is required to compensate for the average user's inability to precisely match a given set of intra-key timings.

All the design decisions and testing in this article took place in a non-networked context for GDM logins. Exercise caution before implementing remote logins with keystroke dynamics, as network latency and a host of other variables need to be considered for reliable verification.

Instead of replacing the standard Linux authentication process, the approach used here will introduce another layer of verification based on the user name. This allows for easy integration with existing security configurations, as the user name and password will remain unchanged. This approach also allows for a transparent addition to the security policy, as account lockouts and password change processes will remain unaffected.

Back to top

Modifying xevKeyDyn.pl for dynamics creation and practice

Before beginning modifications to the GDM source, establishing a test program to create and practice keystroke dynamics is highly recommended. The test program used is a derivative of the xevKeyDyn.pl program first described in the developerWorks article "Expand your text entry options with keystroke dynamics" (see Resources). You'll need to consult that article for instructions to install and configure xev and xevKeyDyn.pl properly. Once you have completed the steps shown in "Expand your text entry options with keystroke dynamics," return here to continue building the test program. Alternatively, you may skip to the Download area and grab the new practice_xevKeyDyn.pl program.

Review of the xevKeyDyn.pl program

Recall that the xevKeyDyn.pl program is designed to measure various keystroke related events and their timings. The modifications below focus on measuring just the key-release timings, as well as providing a useful interface for practicing keystrokes.

Modifications to detect release timings only

Starting at line 25, make the changes shown in Listing 1.

                
## remove lines:
  printPassword( \@keysOne );

  readPassword( \@keysTwo, "Confirm the");
  printPassword( \@keysTwo );

  my $catch = <STDIN>  #initial password catch
     $catch = <STDIN>  #confirmation password catch

  next unless( charactersMatch() );
  next unless( totalTimeOK() );
  next unless( hasNonPrintable() );
  next unless( individualKeyTimingsOK() );

  $passwordOK = 1;

## insert line:
  printCharacteristics();

Fill out the printCharacteristics subroutine called in the main loop by inserting the code in Listing 2 starting at line 31.

                
sub printCharacteristics
{
  my $count = 0;
  my $sig1 = "";

  while( $count < ($#keysOne) )
  {
    my( $time1, undef, undef) = split " ", $keysOne[$count];
    my( $time2, undef, undef) = split " ", $keysOne[$count+1];
    my $timeDiff_0 = $time2 - $time1;

    $sig1 .= substr( $timeDiff_0, 0, length($timeDiff_0)-1) . " ";
    $count++;
  }

  $sig1 = substr($sig1,0,length($sig1)-1);

  map { print "", (split " ", $_)[1]; } @keysOne;

  my $val =`echo "$sig1" | mkpasswd -H md5 --stdin`;
  print " ", substr($val,0,11) , " ";
  print substr($val,11);
  print "\n";
  print "$sig1\n";

}#printCharacteristics

Shown here in printCharacteristics (as well as below in the GDM modifications), is the removal of the least significant portion of the intra-key release timings. When measuring intra-key release times, most often in the hundreds of milliseconds, it is highly unlikely to match the precise millisecond of the key release. To compensate for this, the least-significant digit is removed from the end of a time difference resulting in a useful, but less specific data point. For example, if the time between "n" and "a" character is 235 milliseconds, the recorded value will be "23." Later processing will make use of this relative imprecision to make more accurate matches.

Ensure that only key releases are recorded by making the changes shown in Listing 3.

                
#change line:
if( $inLine =~ /KeyPress event/ || $inLine =~ /KeyRelease event/ )
#to:
if(  $inLine =~ /KeyRelease event/ )

Finally, make a small change that seems required based on certain keyboard configurations, as shown below.

                
#change lines:
      # get the time entry
      my $currTime = <XEV>

#to:
      # get the time entry
      my $currTime = <XEV>
      # certain configurations require this additional read
      $currTime = <XEV>  if( $currTime !~ /time / );

Save your changes to practice_xevKeyDyn.pl and read on for usage instructions on how to build and practice your keystroke-dynamics "signature."

Printing measurements to practice timings

As described in "Expand your text entry options with keystroke dynamics" (see Resources), use xwininfo to get the window ID of your local terminal and run perl practice_xevKeyDyn.pl <windowId> Enter the user name you want to create a keystroke-dynamics signature for and press Enter twice to display the built cryptographic hash and key-release intervals. Listing 5 shows an example output of the practice_xevKeyDyn.pl program.

                
Enter a password:
nathan

nathan $1$Ag51/gt5 $WBcCKPxP5xnbDu2S5BbNt.

24 26 13 23 11
Enter a password:
nathan

nathan $1$gva6aFYD $oZhayCi3AdVXsuyQ0uBFg0

26 26 11 22 11
Enter a password:

For testing purposes, try to create an even, easily repeatable timing pattern, such as two-tenths of a second between each key release. Note how there are always (total characters -1) numbers printed as the release between the final key and Enter are not recorded.

Creating a /etc/shadow.dynamics file

Once you have developed a key-release interval setup that you have practiced repeatedly, it's time to create a repository for the GDM modification to read. Copy the cryptographic hash representing your preferred timings, such as nathan $1$gva6aFYD $oZhayCi3AdVXsuyQ0uBFg0 and insert it as a new line into the /etc/shadow.dynamics file. Change the permissions on the /etc/shadow.dynamics file with the command chmod o-r /etc/shadow.dynamics and modify the owner so the GDM program can read it with the command chown gdm /etc/shadow.dynamics. Repeat the insertion process for every user you want to enable keystroke-dynamics verification for, but remember that this process is not a well-tested and robust solution. It's possible there are many security vulnerabilities in the code and storage mechanisms presented here, so take care when deploying this outside your personal machine.

Back to top

Modifying GDM to support keystroke dynamics

Setup read and processing of keystroke dynamics and current release timings

With an established keystroke-dynamics signature in place, it's time to start modifying the GDM source to permit logins only when the keystroke-dynamics criteria have been met. Unpack the gdm-2.20.0 source and add the following library definition and variable declarations in gui/gdmlogin.c at line 66.

                
#include <crypt.h>
int g_in_username_mode = 1;  // check only username dynamics
int g_dynamics_loaded = 0;   // loaded /etc/shadow.dynamics file ok
int g_name_index = -1;       // current username index in /etc/shadow.dynamics
int g_matched_dynamics = 0;  // username dyanmics match the stored dynamics

guint32 g_release_time[500]; // maximum five hundred key release events
int g_release_count = 0;     // total number of key release events
int g_sig[500];              // maximum five hundred intra key timings
int g_range = 2;             // search range for dynamics match
int g_user_count = 0;        // current number of users in /etc/shadow.dynamics

struct g_user
{
  char username[50];
  char salt[50];
  char password[50];
  char salty_password[50];
};

struct g_user g_user_dynamics[500];  // maximum five hundred users

As the GDM code says, "It's hard to be event controlled while maintaining state," so we add our own state-monitoring variables and data structures to process the keystroke-dynamics functions. Next, add these function definitions at line 209.

                
void load_shadow_dynamics(void);
char * check_dynamics( char *, int);

After the data structures, state variables, and function definitions are in place, add the load_shadow_dynamics function at line 3163.

                
void load_shadow_dynamics(void)
{
  FILE *fp;
  struct stat f_status;
  int retcode;
  char *shadow_file;
  shadow_file = "/etc/shadow.dynamics";

  fp = NULL;
  VE_IGNORE_EINTR (retcode = g_lstat (shadow_file, &f_status));

  // make sure it's a 'normal' file     
  if (retcode == 0) 
  {
    if (S_ISREG (f_status.st_mode)) 
    {
      g_dynamics_loaded = 1;
      VE_IGNORE_EINTR (fp = fopen (shadow_file, "r"));
    }           
  }

  if( fp != NULL )
  {
    char * line = NULL;
    size_t len = 0;
    ssize_t  read;
    while((read = getline(&line, &len, fp)) != -1 )
    {
      char username[50] = "";
      char salt[50] = "";
      char password[50] = "";

      if( sscanf( line, "%s %s %s", username, salt, password) == 3 )
      {
        sprintf(g_user_dynamics[g_user_count].username, "%s", username);
        sprintf(g_user_dynamics[g_user_count].salt, "%s", salt);
        sprintf(g_user_dynamics[g_user_count].password, "%s", password);
        sprintf(g_user_dynamics[g_user_count].salty_password,
          "%s%s", salt, password);
        g_user_count++;
      }else
      {
        g_dynamics_loaded = 0;
      }//if incorrect dynamics file
    }//while line in
  }//if file pointer is not null

  VE_IGNORE_EINTR (fclose (fp));

}//load_shadow_dynamics

The first part of load_shadow_dynamics sets up the file read variables and does sanity checks on the file's readability. Recall that the format of the /etc/shadow.dynamics file is "username salt password," which the while loop reads each line of the file into the g_user_dynamics data structure.

Now enable some user feedback based on the loading of the shadow dynamics file at line 1379.

                
// change:
        gtk_label_set_text_with_mnemonic (GTK_LABEL (label), _("_Username:"));
// to:
        if( g_dynamics_loaded == 0 )
          gtk_label_set_text_with_mnemonic (GTK_LABEL (label), 
            _("_Username: (dynamics misconfigured)"));
        else
          gtk_label_set_text_with_mnemonic (GTK_LABEL (label), _("_Username:"));

        g_release_count = 0;
        g_in_username_mode = 1;

Do a similar feedback addition at line 1414.

                
// change:
            gtk_label_set_text_with_mnemonic (GTK_LABEL (label), _("_Password:"));
// to:
         if( g_dynamics_loaded == 0 )
           gtk_label_set_text_with_mnemonic (GTK_LABEL (label), 
             _("_Password: (dynamics misconfigured)"));
         else
           gtk_label_set_text_with_mnemonic (GTK_LABEL (label), _("_Password:"));

         g_in_username_mode = 0;

Call the load of the dynamics file by inserting the following at line 3239.

                
load_shadow_dynamics();

Finally, set up the recording of each key-release event by adding the following lines at line 2135.

                
        if( g_in_username_mode == 1 )
        {
          g_release_time[g_release_count] =  event->time;
          g_release_count++;
        }

Processing and matching keystroke dynamics in GDM

So far, the program has read the keystroke "signatures" from /etc/shadow.dynamics and placed every key-release time in the appropriate data structure. The next two code listings will process the current key-release times and look for a match with the existing signatures. To begin, add the code in Listing 13 at line 889.

                
        g_matched_dynamics = 0;
        if( g_in_username_mode == 1 )
        {
          int i =0;
          g_name_index = -1;
          for( i=0; i< g_user_count; i++ )
          {
            if( strcmp( g_user_dynamics[i].username,
                          gtk_entry_get_text(GTK_ENTRY(entry)) ) == 0  )
            {
              g_name_index = i;
              i = g_user_count; // to exit the loop
            }
          }//for each username read from file

          // require at least two key presses to measure
          if( g_name_index != -1 && g_release_count >= 2 )
          {
            i=0;
            for( i=0; i< g_release_count-1; i++ )
            {
              char sig_num[50] = "";
              sprintf( sig_num, "%u", abs(g_release_time[i] - g_release_time[i+1]) );

              char clip_str[50] = "";
              strncat( clip_str, sig_num, strlen(sig_num)-1 );
              g_sig[i] = atoi( clip_str );
            }//for each i

            check_dynamics("", 0);
          }

          if( g_matched_dynamics != 1 )
          {
            // name not found, set username to garbage value to ensure no-login
            // this way you can't defeat keystroke dynamics checks by removing an
            // entry from the /etc/shadow.dynamics file
            //  -comment this line out if you want to enable non-dynamics protected
            //  logins
            gtk_entry_set_text (GTK_ENTRY (entry), " ");
          }

        }// if in username mode

When the user clicks OK or presses Enter to move from user name to password entry, the logic block shown above is executed. The first for loop looks for the current user name in the list of loaded user names from /etc/shadow.dynamics. If a matching user name was found, the next for loop discards the least-significant portion of the timing interval between keystrokes and builds a new array g_sig with the timing values. Once the current timing signature has been created, the check_dynamics function is called to walk through all the possible combinations of the signature that are within the g_range distance from the current signature. At line 875, insert the code shown in Listing 14 to build the check_dynamics function.

                
char * check_dynamics( char * in_string, int level )
{       
  int start = g_sig[level] - g_range;
  int stop  = g_sig[level] + g_range;
  int curr  = start;
         
  // eliminate the g_matched_dynamics != 1 check to enforce consistent 
  // processing time regardless of when the match is found.  In theory, this 
  // will reduce the ability to perceive a dynamics match due to processing 
  // time - which becomes much more effective for longer usernames or greater
  // g_range values

  while( curr <= stop && g_matched_dynamics != 1 )
  {
    if( level == (g_release_count-2) )
    {
      // if deepest level, perform match check
      char current_timing[500];
      char current_salt[50];

      sprintf( current_timing, "%s %d", in_string, curr);
      sprintf( current_salt, "%s", g_user_dynamics[g_name_index].salt);
      char * crypt_pass = crypt( current_timing, current_salt);

      if( strcmp(crypt_pass, g_user_dynamics[g_name_index].salty_password) == 0)
        g_matched_dynamics = 1;

    }else
    {
      // append to the current 'signature', go to next level
      char test_pass[500] = "";
      if( strlen(in_string) != 0 )
        sprintf(test_pass,"%s %d", in_string, curr);
      else
        sprintf(test_pass,"%d", curr);

      check_dynamics( test_pass, level+1);
    }//if at maximum level
    
    curr++;

  }//while current < stop

  return("");

}//check_dynamics

The check_dynamics function recursively calls itself while building signatures encompassing the full range of possibilities defined by the g_range parameter. Each in_string variable is built level by level from a single intra-key release time all the way up to a key-release time for each recorded letter in the user name. For example, if you enter keys that have corresponding release times of "20 20 20 20 20," the check_dynamics function will work through the necessary permutations to check "18 18 18 18 18," "22 22 22 22 22," and everything in between.

After reading the large comment block, note that loose matching (with a high g_range value) or long user names will drastically increase the amount of time required to check all possibilities. An attacker can potentially exploit this extended processing attribute by looking for relatively short processing times. If the overall time is measurably shorter than most other measured times, the attacker can be reasonably assured they have entered the release times correctly. Removing the g_matched_dynamics != 1 check will disable this capability at the expense of continued processing, even when a match has been found.

Back to top

Building and using the code

As mentioned, the gdm-2.20.0 code will not compile directly from the archive. Run ./configure followed by make and you should see an error message like that shown below.

                
    make  all-recursive
    make[1]: Entering directory `/home/nathan/gdm-2.20.3'
    Making all in po
    make[2]: Entering directory `/home/nathan/gdm-2.20.3/po'
    file=`echo af | sed 's,.*/,,'`.gmo \
              && rm -f $file  &&  -o $file af.po
    /bin/sh: -o: not found
    make[2]: *** [af.gmo] Error 127
    make[2]: Leaving directory `/home/nathan/gdm-2.20.3/po'
    make[1]: *** [all-recursive] Error 1
    make[1]: Leaving directory `/home/nathan/gdm-2.20.3'
    make: *** [all] Error 2

To eliminate this problem, you'll need to make the changes described in Listing 16 at line 331 in gdm-2.20.0/Makefile.

                
# change:
SUBDIRS = \
  po      \
  config      \
# to:
SUBDIRS = \
  config      \

This change removes support for GDM in multiple languages, but English is still supported. If you've made it this far, chances are good you'll be able to understand the GDM greeter without support in your natural language, so make the final build process change and insert $(EXTRA_DAEMON_LIBS) \ at line 555 to enable crypt.h support when building gdmlogin.c.

Run another make followed by make install, and you will have a newly built version of GDM installed in /usr/local/sbin/. To test your installation on Ubuntu V7.10, enter runlevel 1 and start GDM as root, preferably with the -nodaemon option. Keep in mind that as you enter your user name according to your (hopefully well-practiced) timings, it make take a few tries to enter your user name with enough precision to match the expected values.

Back to top

Conclusion and further examples

GDM has now been modified to support intra-key timings for release-events only. Go ahead and tell your password to a friend. They still won't be able to log in using GDM without knowing the precise method of typing required when entering your user name. Use the architecture described here and in the "Expand your text entry options with keystroke dynamics" article to add total user-name entry checks, nonprintable character requirements, or other keystroke-related features to further enhance GDM keystroke-dynamics support.

Share this... Digg this story Post to del.icio.us Slashdot it!

Back to top

Download

	Information about download methods

Resources

• Learn about the GNOME Display Manager at Gnome.org.
  
  
• This article builds on the developerWorks article "Expand your text entry options with keystroke dynamics."
  
  
• To listen to interesting interviews and discussions for software developers, check out developerWorks podcasts.
  
  
• Stay current with developerWorks' Technical events and webcasts.
  
  
• Check out upcoming conferences, trade shows, webcasts, and other Events around the world that are of interest to IBM open source developers.
  
  
• Visit the developerWorks Open source zone for extensive how-to information, tools, and project updates to help you develop with open source technologies and use them with IBM's products.
  
  
• Watch and learn about IBM and open source technologies and product functions with the no-cost developerWorks On demand demos.
  
  

• Download GDM V2.20.0's source code from Gnome.org, Debian.org, or Georgia Tech.
  
  
• A major distribution like Ubuntu provides excellent package management for developing a build environment and installing prerequisites necessary to compile GDM. Download Ubuntu to get started with this Linux distribution.
  
  
• For easy testing, download xev, an X Window System package.
  
  
• Innovate your next open source development project with IBM trial software, available for download or on DVD.
  
  
• Download IBM product evaluation versions, and get your hands on application development tools and middleware products from DB2®, Lotus®, Rational®, Tivoli®, and WebSphere®.

• Participate in developerWorks blogs and get involved in the developerWorks community.
  
  

About the author

		Nathan Harrington is a programmer at IBM currently working with Linux and resource-locating technologies.

Rate this page

Please take a moment to complete this form to help us better serve you. Did the information help you to achieve your goal? Yes No Don't know   Please provide us with comments to help improve this page:   How useful is the information? 1 2 3 4 5 Not useful Extremely useful