Key-Slot Checker Tool

Hi all.

I just wrote a very simple key-slot checker. It divides all active keyslots into 512 byte sectors and calculates entropy for each. For valid encrypted data, entropy will be close to 0.95 on average (would be 1, but this is sample entropy, calculated on a limited data set).

No fancy output, no library usage (but verifies LUKS version), support for non-default key-sizes and setting your own entropy threshold. I put in 0.85 as default threshold, which should work well.

Now I am not sure where to put it. Should I put it in misc/ in the sources? That seems to be sort of a contrib/ directory. Or should we add a section in the Wiki for tools?

Anyways, if anybody want to test it, it is attached. Compile instructions at the head of the file.

Arno

Arno Wagner,    Dr. sc. techn., Dipl. Inform.,   Email: [email protected] 
GnuPG:  ID: 1E25338F  FP: 0C30 5782 9D93 F785 E79C  0296 797F 6B50 1E25 338F
----
One of the painful things about our time is that those who feel certainty 
are stupid, and those with any imagination and understanding are filled 
with doubt and indecision. -- Bertrand Russell 

/*
* Simple LUKS keyslot entropy tester. Works only for header version 1.
* This is a quick hack, do not expect too much.
* In particular, this could be scripted for greater flexibility. *
* Version history:
* v0.1: 9.9.2012 Initial release
*
* Copyright (C) 2012, Arno Wagner <[email protected]>
*
*
* This file is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version. *
* This file is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this file; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301 USA.
*/

/*
* this should compile with a simple
* gcc -lm chk_luks_keyslots.c -o chk_luks_keyslots
*/

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <math.h>
#include <fcntl.h>
#include <inttypes.h>

char * help =
"Help:\n"
"\n"
"This tool checks all keyslots of a LUKS device for \n" "low entropy sections. If any are found, they are reported. \n" "This allows to find areas damaged by things like filesystem \n" "creation or RAID superblocks. \n"
"\n"
"Default parameters: \n"
" Section size: 512 bytes \n"
" Entropy threshold: 0.85 \n"
//" Print details at end: no \n"
" \n"
" \n"
"Commandline parameters: \n"
" \n"
" chk_luks_keyslots [options] luks-device \n"
" \n"
"Options: \n"
" -t <num> Entropy threshold. Possible values 0.0 ... 1.0 \n"
//" -v Print found suspicuous sectors verbosely at end \n"
"\n";

/* Config defaults */

int sector_size = 512;
double threshold = 0.85;

struct bad_sector {
int num;
int keyslot;
int ks_start;
int offset;
int entropy;
struct bad_sector * next; /* for linked list */
};

struct bad_sector * first_bad;

struct keyslot {
int num;
uint32_t active;
uint32_t key_material_offset;
uint32_t stripes;
int start;
int len;
};

struct keyslot ks[8];

/* tools */

double ent_samp(unsigned char * buf, int len) {
/* Calculates and returns sample entropy on byte level for
* The argument.
*/

  int freq[256];   // stores symbol frequencies
  int i;
  double e, f;
  // 0. Plausibility checks
  if (len <= 0) return(0.0);
  
  // 1. count all frequencies       
  for (i = 0; i < 256; i++) {
    freq[i] = 0.0;  
  }
  for (i = 0; i < len; i ++) 
    freq[buf[i]]++;

// 2. calculate sample entropy
e = 0.0;

  for (i = 0; i < 256; i++) {
    f = freq[i];
    if (f > 0) {
      f =  f / (double)len;
      e += f * log2(f);
    }  

}
if (e != 0.0) e = -1.0 * e;
e = e / 8.0;
return(e);
}

int main(int argc, char **argv) {

  /* for option processing */		
  int tflag = 0;	
  double tvalue = 0.8;  
  int vflag = 0;
  int opt_index;
  int c;
  char * device;

unsigned char * buffer;

/* Other vars */
int f_luks; // device file for the luks device
uint32_t stripe_size;

/* temprary helper vars */
int i;
uint32_t u32;
uint16_t u16;

  /* get commandline parameters */
  while ((c = getopt (argc, argv, "t:v")) != -1) {
    switch (c) {
      case 't': {
        char * s, * end;         
        tflag = 1;
        s = optarg;
        tvalue = strtod(s, &end);
        if (s == end) {
          fprintf(stderr, "\nError: Parsing of argument to -t failed.\n");
          abort();
        }
        if (tvalue < 0.0 || tvalue > 1.0) {
          fprintf(stderr,"\nError: Argument > 1.0 or < 0.0 to -t\n");
          abort();
        }    
        threshold = tvalue;
        break;	
      }
      case 'v':
        vflag = 1;
        break;    
      case '?':
        if (optopt == 't')
          fprintf (stderr,"\nError: Option -%c requires an argument.\n", 
                   optopt);
        else if (isprint (optopt)) {
          fprintf(stderr,"\nError: Unknown option `-%c'.\n", optopt);
          fprintf(stderr,"\n\n%s", help);                        
        } else {
          fprintf (stderr,
                   "\nError: Unknown option character `\\x%x'.\n",
                   optopt);
          fprintf(stderr,"\n\n%s", help);         
        }
        return(1);

      default: 
        abort();
    }  

}

  /* parse non-option stuff. Should be exactly one, the device. */
  if (optind+1 != argc) {
    fprintf(stderr,"\nError: exactly one non-option argument expected!\n");
    fprintf(stderr,"\n\n%s", help);
    abort();
  }
  device = argv[optind];
   
  /* test whether we can open and read device */
  f_luks = open(device, O_RDONLY);
  if (f_luks == -1) {
    fprintf(stderr,"\nError: Opening of device %s failed:\n", device);
    perror(NULL);
    abort();
  }       

  /* some init */
  buffer = (unsigned char *) calloc(sector_size, 1);

/* plausibility checks: look for magic string and
version field.
*/

  lseek(f_luks, 0, SEEK_SET);
  read(f_luks, buffer, 6);
  if (buffer[0] != 'L' || buffer[1] != 'U' || buffer[2] != 'K' ||
      buffer[3] != 'S' || buffer[4] != 0xBA || buffer[5] != 0xBE) {
    fprintf(stderr,"\nError: LUKS magic string not found!\n");
    abort();
  }  

lseek(f_luks, 6, SEEK_SET);
read(f_luks, buffer, 2);
/* LUKS headers are stored big-endian, i.e. network byte order */ u16 = ntohs(*(uint16_t *)buffer);
if (u16 != 1) {
fprintf(stderr,"\nError: LUKS header version is not 1!\n"); abort();
}

/* Find stripe size. It is the same as the key-bytes. */ lseek(f_luks, 108, SEEK_SET);
read(f_luks, &u32, 4);
stripe_size = ntohl(u32);

// printf("stripe size: %d\n", stripe_size);

/* enumerate keyslots */
for (i = 0; i < 8; i ++) {
lseek(f_luks, 208 + i * 48, SEEK_SET);
read(f_luks, &u32, 4);
u32 = ntohl(u32);
if (u32 == 0x00ac71f3)

     ks[i].active = 1;
   else if (u32 == 0x0000dead) 
     ks[i].active = 0;
   else {
     fprintf(stderr,
            "\nError: found unknown value in keyslot %d active field: %8x\n",
            i, u32);
     abort();

}

   lseek(f_luks, 208 + i * 48 + 40, SEEK_SET);
   read(f_luks, &u32, 4);
   ks[i].key_material_offset = ntohl(u32);

   lseek(f_luks, 208 + i * 48 + 44, SEEK_SET);
   read(f_luks, &u32, 4);
   ks[i].stripes = ntohl(u32);

   ks[i].num = i;
   ks[i].start = ks[i].key_material_offset * 512;
   ks[i].len = ks[i].stripes * stripe_size; 

// printf("num: %d active: %d start:%8x end:%8x\n",
// ks[i].num, ks[i].active, ks[i].start, ks[i].start + ks[i].len);
}

printf("\nSectors with entropy below threshold (%f):\n", threshold);

  for (i = 0; i < 8; i ++) {
    int j;
    int s, l;
    int ofs;
    int num_sect;
    double ent;
    s = ks[i].start;
    l = ks[i].len;
    num_sect = l / sector_size;

    printf("\nKeyslot %d: start: %#8x \n", i, s);
    if (!ks[i].active) {
      printf("  keyslot not in use\n");
      continue;
    }  
    for (j = 0; j < num_sect; j++) {
      ofs = s + j * sector_size;
      lseek(f_luks, ofs, SEEK_SET);
      read(f_luks, buffer, sector_size);
      ent = ent_samp(buffer, sector_size);
//      printf("slot: %d  offset: %8x  ent: %f\n", i, ofs, ent);  
      if (ent < threshold) 
        printf("  position: %#8x   entropy: %f\n", ofs, ent);
      

    }  

}

return(0);
}

Yes, this is something very useful.

But 512 slots is quite small chunk of random data, there will be some false warnings I guess.
(Adding add test for the whole keyslot combined
with separate sectors? Not sure if it helps something though...)

(Well, and it cannot obviously detect corruption with overwriting random data :)

Parsing header on its own is something which should not be even in misc section (in the worst case it should include luks.h directly).

But anyway, this could be integrated into luks
format checker directly (and run in "check" cryptsetup command). (And the same random test perhaps should be in tests for large enough blocks - see tests/differ.c, there is nice fixme :-)

I am just not sure introducing floating point in libcryptsetup is good idea. But perhaps this can be compile time option, if some ancient/embedded CPU/distro has problems here, so it can be compiled-out.

Milan

Thanks!

Very, very few. Remember that the data looks like high-quality randomness if correct. I might do a measurement how rarely, but with my test-header I had to go up to 0.93 (default is 0.85) to get a single false detection. And the entropy-threshold is tunable.

I don't think that is needed, but a sector-size option (with 0 = whole slot) is a possibility.

That would be quite a trick ;-)

I can do that. Just wanted to see whether it works first.

That would probably be a good idea. Is that a new command? If you can point out were that is in the code, I can add these tests.

Will have a look.

While this can be done without, it is really hard. Basically you eiher need to simulate the logarithm in fixed-point integer or build up huffman tree as direct entropy estimator. Easiest way would probably be fixed-point and a 1000-entry table for the log().

I like that idea much better.

So, next step, make it use luks.h and put it in misc/ ?

Arno

Arno Wagner,    Dr. sc. techn., Dipl. Inform.,   Email: [email protected] 
GnuPG:  ID: 1E25338F  FP: 0C30 5782 9D93 F785 E79C  0296 797F 6B50 1E25 338F
----
One of the painful things about our time is that those who feel certainty 
are stupid, and those with any imagination and understanding are filled 
with doubt and indecision. -- Bertrand Russell 

[...]

Question for that, is the "R" option one random thing replaced with another random thing? If so, I can fix that test by XORing both and calculating entropy on the result.

Will still require -lm for the log() though.

And an update on the 0.85 threshold: I have checked 10 Million random 512B blocks and the sample entroy never went below 0.92. For larger blocks the probability will be even lower. I think 0.85 is quite adequate as threshold.

However, the test in differ.c will probably need to go back to a count of differing bits for blocks significantly smaller than 512B or use a lower threshold. Is it used for small blocks, e.g. keys?

Arno

Arno Wagner,    Dr. sc. techn., Dipl. Inform.,   Email: [email protected] 
GnuPG:  ID: 1E25338F  FP: 0C30 5782 9D93 F785 E79C  0296 797F 6B50 1E25 338F
----
One of the painful things about our time is that those who feel certainty 
are stupid, and those with any imagination and understanding are filled 
with doubt and indecision. -- Bertrand Russell