11.20 Gathering Entropy from the Keyboard

11.20.1 Problem

You need entropy in a low-entropy environment and can prompt the user to type in order to collect it.

11.20.2 Solution

On Unix, read directly from the controlling terminal (/dev/tty). On Windows, process all keyboard events. Mix into an entropy pool the key pressed, along with the timestamp at which each one was processed. Estimate entropy based upon your operating environment; see the considerations in Recipe 11.19.

11.20.3 Discussion

There can be a reasonable amount of entropy in key presses. The entropy comes not simply from which key is pressed, but from when each key is pressed. In fact, measuring which key is pressed can have very little entropy in it, particularly in an embedded environment where there are only a few keys. Most of the entropy will come from the exact timing of the key press.

The basic methodology is to mix the character pressed, along with a timestamp, into the entropy pool. We will provide an example implementation in this section, where that operation is merely hashing the data into a running SHA1 context. If you can easily get information on both key presses and key releases (as in an event-driven system like Windows), we strongly recommend that you mix such information in as well.

The big issue is in estimating the amount of entropy in each key press. The first worry is what happens if the user holds down a key. The keyboard repeat may be so predictable that all entropy is lost. That is easy to thwart, though. You simply do not measure any entropy at all, unless the user pressed a different key from the previous time.

Ultimately, the amount of entropy you estimate getting from each key press should be related to the resolution of the clock you use to measure key presses. In addition, you must consider whether other processes on the system may be recording similar information (such as on a system that has a /dev/random infrastructure already). See Recipe 11.19 for a detailed discussion of entropy estimation.

The next two subsections contain code that reads data from the keyboard, hashes it into a SHA1 context, and repeats until it is believed that the requested number of bits of entropy has been collected. A progress bar is also displayed that shows how much more entropy needs to be collected.

11.20.3.1 Collecting entropy from the keyboard on Unix

First, you need to get a file descriptor for the controlling terminal, which can always be done by opening /dev/tty. Note that it is a bad idea to read from standard input, because it could be redirected from an input source other than /dev/tty. For example, you might end up reading data from a static file with no entropy. You really do need to make sure you are reading data interactively from a keyboard.

Another issue is that there must be a secure path from the keyboard to the program that is measuring entropy. If, for example, the user is connected through an insecure telnet session, there is essentially no entropy in the data. However, it is generally okay to read data coming in over a secure ssh connection. Unfortunately, from an application, it is difficult to tell whether an interactive terminal is properly secured, so it's much better to issue a warning about it, pushing the burden off to the user.

You will want to put the terminal into a mode where character echo is off and as many keystrokes as possible can be read. The easiest way to do that is to put the terminal to which a user is attached in "raw" mode. In the following code, we implement a function that, given the file descriptor for the tty, sets the terminal mode to raw mode and also saves the old options so that they can be restored after entropy has been gathered. We do all the necessary flag-setting manually, but many environments can do it all with a single call to cfmakeraw( ), which is part of the POSIX standard.

In this code, timestamps are collected using the current_stamp( ) macro from Recipe 4.14. Remember that this macro interfaces specifically to the x86 RDTSC instruction. For a more portable solution, you can use gettimeofday( ). (Refer back to Recipe 4.14 for timestamping solutions.)

One other thing that needs to be done to use this code is to define the macro ENTROPY_PER_SAMPLE, which indicates the amount of entropy that should be estimated for each key press, between the timing information and the actual value of the key.

We recommend that you be highly conservative, following the guidelines from Recipe 11.19. We strongly recommend a value no greater than 2.5 bits per key press on a Pentium 4, which takes into account that key presses might come over an ssh connection (although it is reasonable to keep an unencrypted channel out of the threat model). This helps ensure quality entropy and still takes up only a few seconds of the user's time (people will bang on their keyboards as quickly as they can to finish).

For a universally applicable estimate, 0.5 bits per character is nice and conservative and not too onerous for the user.

Note that we also assume a standard SHA1 API, as discussed in Recipe 6.5. This code will work as is with OpenSSL if you include openssl/sha.h and link in libcrypto.

#include <termios.h> #include <unistd.h> #include <fcntl.h> #include <stdio.h> #include <stdlib.h> #include <errno.h> #ifndef TIOCGWINSZ #include <sys/ioctl.h> #endif #include <openssl/sha.h>     #define HASH_OUT_SZ     20 #define OVERHEAD_CHARS  7 #define DEFAULT_BARSIZE (78 - OVERHEAD_CHARS)  #define MAX_BARSIZE     200     void spc_raw(int fd, struct termios *saved_opts) {   struct termios new_opts;       if (tcgetattr(fd, saved_opts) < 0) abort(  );   /* Make a copy of saved_opts, not an alias. */   new_opts = *saved_opts;   new_opts.c_lflag    &= ~(ECHO | ICANON | IEXTEN | ISIG);   new_opts.c_iflag    &= ~(BRKINT | ICRNL | INPCK | ISTRIP | IXON);   new_opts.c_cflag    &= ~(CSIZE | PARENB);   new_opts.c_cflag    |= CS8;   new_opts.c_oflag    &= ~OPOST;   new_opts.c_cc[VMIN]  = 1;   new_opts.c_cc[VTIME] = 0;   if (tcsetattr(fd, TCSAFLUSH, &new_opts) < 0) abort(  ); }     /* Query the terminal file descriptor with the TIOCGWINSZ ioctl in order to find  * out the width of the terminal.  If we get an error, go ahead and assume a 78  * character display.  The worst that may happen is bad wrapping.  */ static int spc_get_barsize(int ttyfd) {   struct winsize sz;       if (ioctl(ttyfd, TIOCGWINSZ, (char *)&sz) < 0) return DEFAULT_BARSIZE;   if (sz.ws_col < OVERHEAD_CHARS) return 0;   if (sz.ws_col - OVERHEAD_CHARS > MAX_BARSIZE) return MAX_BARSIZE;   return sz.ws_col - OVERHEAD_CHARS; }                                   static void spc_show_progress_bar(double entropy, int target, int ttyfd) {   int  bsz, c;   char bf[MAX_BARSIZE + OVERHEAD_CHARS];       bsz = spc_get_barsize(ttyfd);   c   = (int)((entropy * bsz) / target);   bf[sizeof(bf) - 1] = 0;   if (bsz) {     snprintf(bf, sizeof(bf), "\r[%-*s] %d%%", bsz, "",              (int)(entropy * 100.0 / target));     memset(bf + 2, '=', c);     bf[c + 2] = '>';   } else     snprintf(bf, sizeof(bf), "\r%d%%", (int)(entropy * 100.0 / target));   while (write(ttyfd, bf, strlen(bf)) =  = -1)     if (errno != EAGAIN) abort(  ); }     static void spc_end_progress_bar(int target, int ttyfd) {   int bsz, i;       if (!(bsz = spc_get_barsize(ttyfd))) {     printf("100%%\r\n");     return;   }   printf("\r[");   for (i = 0;  i < bsz;  i++) putchar('=');   printf("] 100%%\r\n"); }     void spc_gather_keyboard_entropy(int l, char *output) {   int            fd, n;   char           lastc = 0;   double         entropy = 0.0;   SHA_CTX        pool;   volatile char  dgst[HASH_OUT_SZ];   struct termios opts;   struct {     char         c;     long long    timestamp;   }              data;       if (l > HASH_OUT_SZ) abort(  );   if ((fd = open("/dev/tty", O_RDWR)) =  = -1) abort(  );   spc_raw(fd, &opts);   SHA1_Init(&pool);   do {     spc_show_progress_bar(entropy, l * 8, fd);     if ((n = read(fd, &(data.c), 1)) < 1) {       if (errno =  = EAGAIN) continue;       abort(  );     }     current_stamp(&(data.timestamp));     SHA1_Update(&pool, &data, sizeof(data));     if (lastc != data.c) entropy += ENTROPY_PER_SAMPLE;     lastc = data.c;   } while (entropy < (l * 8));   spc_end_progress_bar(l * 8, fd);   /* Try to reset the terminal. */   tcsetattr(fd, TCSAFLUSH, &opts);   close(fd);   SHA1_Final((unsigned char *)dgst, &pool);   spc_memcpy(output, (char *)dgst, l);   spc_memset(dgst, 0, sizeof(dgst)); }
11.20.3.2 Collecting entropy from the keyboard on Windows

To collect entropy from the keyboard on Windows, we will start by building a dialog that displays a brief message advising the user to type random characters on the keyboard until enough entropy has been collected. The dialog will also contain a progress bar and an OK button that is initially disabled. As entropy is collected, the progress bar will be updated to report the progress of the collection. When enough entropy has been collected, the OK button will be enabled. Clicking the OK button will dismiss the dialog.

Here is the resource definition for the dialog:

#include <windows.h>     #define SPC_KEYBOARD_DLGID      101 #define SPC_PROGRESS_BARID      1000 #define SPC_KEYBOARD_STATIC     1001     SPC_KEYBOARD_DLGID DIALOG DISCARDABLE  0, 0, 186, 95 STYLE DS_MODALFRAME | DS_NOIDLEMSG | DS_CENTER | WS_POPUP | WS_VISIBLE |      WS_CAPTION FONT 8, "MS Sans Serif" BEGIN     CONTROL         "Progress1",SPC_PROGRESS_BARID,"msctls_progress32",                     PBS_SMOOTH | WS_BORDER,5,40,175,14     LTEXT           "Please type random characters on your keyboard until the \                     progress bar reports 100% and the OK button becomes active.",                     SPC_KEYBOARD_STATIC,5,5,175,25     PUSHBUTTON      "OK",IDOK,130,70,50,14,WS_DISABLED END

Call the function SpcGatherKeyboardEntropy( ) to begin the process of collecting entropy. It requires two additional arguments to its Unix counterpart, spc_gather_keyboard_entropy( ):

hInstance

Application instance handle normally obtained from the first argument to WinMain( ), the program's entry point.

hWndParent

Handle to the dialog's parent window. It may be specified as NULL, in which case the dialog will have no parent.

pbOutput

Buffer into which the collected entropy will be placed.

cbOutput

Number of bytes of entropy to place into the output buffer. The output buffer must be sufficiently large to hold the requested amount of entropy. The number of bytes of entropy requested should not exceed the size of the hash function used, which is SHA1 in the code provided. SHA1 produces a 160-bit or 20-byte hash. If the requested entropy is smaller than the hash function's output, the hash function's output will be truncated.

SpcGatherKeyboardEntropy( ) uses the CryptoAPI to hash the data collected from the keyboard. It first acquires a context object, then creates a hash object. After the arguments are validated, the dialog resource is loaded by calling CreateDialog( ), which creates a modeless dialog. The dialog is created modeless so that keyboard messages can be captured. If a modal dialog is created using DialogBox( ) or one of its siblings, message handling for the dialog prevents us from capturing the keyboard messages.

Once the dialog is successfully created, the message-handling loop performs normal message dispatching, calling IsDialogMessage( ) to do dialog message processing. Keyboard messages are captured in the loop prior to calling IsDialogMessage( ), however. That's because IsDialogMessage( ) causes the messages to be translated and dispatched, so handling them in the dialog's message procedure isn't possible.

When a key is pressed, a WM_KEYDOWN message will be received, which contains information about which key was pressed. When a key is released, a WM_KEYUP message will be received, which contains the same information about which key was released as WM_KEYDOWN contains about a key press. The keyboard scan code is extracted from the message, combined with a timestamp, and fed into the hash object. If the current scan code is the same as the previous scan code, it is not counted as entropy but is added into the hash anyway. As other keystrokes are collected, the progress bar is updated, and when the requested amount of entropy has been obtained, the OK button is enabled.

When the OK button is clicked, the dialog is destroyed, terminating the message loop. The output from the hash function is copied into the output buffer from the caller, and internal data is cleaned up before returning to the caller.

#include <windows.h> #include <wincrypt.h> #include <commctrl.h>     #define SPC_ENTROPY_PER_SAMPLE  0.5 #define SPC_KEYBOARD_DLGID      101 #define SPC_PROGRESS_BARID      1000 #define SPC_KEYBOARD_STATIC     -1     typedef struct {   BYTE  bScanCode;   DWORD dwTickCount; } SPC_KEYPRESS;     static BOOL CALLBACK KeyboardEntropyProc(HWND hwndDlg, UINT uMsg, WPARAM wParam,                                          LPARAM lParam) {   HWND *pHwnd;       if (uMsg != WM_COMMAND || LOWORD(wParam) != IDOK ||       HIWORD(wParam) != BN_CLICKED) return FALSE;       pHwnd = (HWND *)GetWindowLong(hwndDlg, DWL_USER);   DestroyWindow(hwndDlg);   *pHwnd = 0;   return TRUE; }     BOOL SpcGatherKeyboardEntropy(HINSTANCE hInstance, HWND hWndParent,                                BYTE *pbOutput, DWORD cbOutput) {   MSG            msg;   BOOL           bResult = FALSE;   BYTE           bLastScanCode = 0, *pbHashData = 0;   HWND           hwndDlg;   DWORD          cbHashData, dwByteCount = sizeof(DWORD), dwLastTime = 0;   double         dEntropy = 0.0;   HCRYPTHASH     hHash = 0;   HCRYPTPROV     hProvider = 0;   SPC_KEYPRESS   KeyPress;       if (!CryptAcquireContext(&hProvider, 0, MS_DEF_PROV, PROV_RSA_FULL,                           CRYPT_VERIFYCONTEXT)) goto done;   if (!CryptCreateHash(hProvider, CALG_SHA1, 0, 0, &hHash)) goto done;   if (!CryptGetHashParam(hHash, HP_HASHSIZE, (BYTE *)&cbHashData, &dwByteCount,                          0)) goto done;   if (cbOutput > cbHashData) goto done;   if (!(pbHashData = (BYTE *)LocalAlloc(LMEM_FIXED, cbHashData))) goto done;       hwndDlg = CreateDialog(hInstance, MAKEINTRESOURCE(SPC_KEYBOARD_DLGID),                          hWndParent, KeyboardEntropyProc);   if (hwndDlg) {     if (hWndParent) EnableWindow(hWndParent, FALSE);     SetWindowLong(hwndDlg, DWL_USER, (LONG)&hwndDlg);     SendDlgItemMessage(hwndDlg, SPC_PROGRESS_BARID, PBM_SETRANGE32, 0,                        cbOutput * 8);     while (hwndDlg && GetMessage(&msg, 0, 0, 0) > 0) {       if ((msg.message =  = WM_KEYDOWN || msg.message =  = WM_KEYUP) &&           dEntropy < cbOutput * 8) {         KeyPress.bScanCode   = ((msg.lParam >> 16) & 0x0000000F);         KeyPress.dwTickCount = GetTickCount(  );         CryptHashData(hHash, (BYTE *)&KeyPress, sizeof(KeyPress), 0);         if (msg.message =  = WM_KEYUP || (bLastScanCode != KeyPress.bScanCode &&             KeyPress.dwTickCount - dwLastTime > 100)) {           bLastScanCode = KeyPress.bScanCode;           dwLastTime = KeyPress.dwTickCount;           dEntropy += SPC_ENTROPY_PER_SAMPLE;           SendDlgItemMessage(hwndDlg, SPC_PROGRESS_BARID, PBM_SETPOS,                              (WPARAM)dEntropy, 0);           if (dEntropy >= cbOutput * 8) {             EnableWindow(GetDlgItem(hwndDlg, IDOK), TRUE);             SetFocus(GetDlgItem(hwndDlg, IDOK));             MessageBeep(0xFFFFFFFF);           }         }          continue;       }       if (!IsDialogMessage(hwndDlg, &msg)) {         TranslateMessage(&msg);         DispatchMessage(&msg);       }     }     if (hWndParent) EnableWindow(hWndParent, TRUE);   }       if (dEntropy >= cbOutput * 8) {     if (CryptGetHashParam(hHash, HP_HASHVAL, pbHashData, &cbHashData, 0)) {       bResult = TRUE;       CopyMemory(pbOutput, pbHashData, cbOutput);     }   }     done:   if (pbHashData) LocalFree(pbHashData);   if (hHash) CryptDestroyHash(hHash);   if (hProvider) CryptReleaseContext(hProvider, 0);   return bResult; }

There are other ways to achieve the same result on Windows. For example, you could install a temporary hook to intercept all messages and use the modal dialog functions instead of the modeless ones that we have used here. Another possibility is to be collecting entropy throughout your entire program by installing a more permanent hook or by moving the entropy collection code out of SpcGatherKeyboardEntropy( ) and placing it into your program's main message-processing loop. SpcGatherKeyboardEntropy( ) could then be modified to operate in global state, presenting a dialog only if there is not a sufficient amount of entropy collected already.

Note that the dialog uses a progress bar control. While this control is a standard control on Windows, it is part of the common controls, so you must initialize common controls before instantiating the dialog; otherwise, CreateDialog( ) will fail inexplicably (GetLastError( ) will return 0, which obviously is not very informative). The following code demonstrates initializing common controls and calling SpcGatherKeyboardEntropy( ):

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine,                    int nShowCmd) {   BYTE                 pbEntropy[20];   INITCOMMONCONTROLSEX CommonControls;       CommonControls.dwSize = sizeof(CommonControls);   CommonControls.dwICC  = ICC_PROGRESS_CLASS;   InitCommonControlsEx(&CommonControls);   SpcGatherKeyboardEntropy(hInstance, 0, pbEntropy, sizeof(pbEntropy));   return 0; }

11.20.4 See Also

Recipe 4.14, Recipe 6.5, Recipe 11.19



Secure Programming Cookbook for C and C++
Secure Programming Cookbook for C and C++: Recipes for Cryptography, Authentication, Input Validation & More
ISBN: 0596003943
EAN: 2147483647
Year: 2005
Pages: 266

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net