I can confirm that the problem affects 32-bit Windows-7 as well.
James
-----Original Message-----
From: The default queue via RT [mailto:[email protected]]
Sent: Friday, November 13, 2009 12:14 AM
To: James Baker
Subject: [openssl.org #2100] AutoReply: RAND_poll can be incredibly slow on
Windows7 due to Heap32Next
Greetings,
This message has been automatically generated in response to the
creation of a trouble ticket regarding:
"RAND_poll can be incredibly slow on Windows7 due to Heap32Next",
a summary of which appears below.
There is no need to reply to this message right now. Your ticket has been
assigned an ID of [openssl.org #2100].
Please include the string:
[openssl.org #2100]
in the subject line of all future correspondence about this issue. To do so,
you may reply to this message.
Thank you,
[email protected]
-------------------------------------------------------------------------
bug report (first time, please forgive any faux-paus)
64-bit Windows 7 Ultimate
affects openssl/crypto/rand/rand_win.c from at least 2005 (v1.4.5) to current
0.9.8 and 1.0.0
Even when doing the absolute minimum heap traversal, RAND_poll walks the first
80 entries of the first heap list to generate entropy without checking how much
time it’s taking. This can easily take more than a minute to execute with a
moderate-to-large heap size.
Expected behavior: RAND_poll needs to be limited to taking only a few seconds
while still gathering enough entropy. Suggested remedies: A) find an alternate
method of heap list traversal or B) find an alternate source of entropy
The cause is the usage of Heap32Next: my testing shows that performance of
Heap32Next is linear w/r/t the number of heap entries in the first heap list.
Each invocation of Heap32Next (on Win7, contrasted with XP and Vista) can
easily take more than 1 second - graphs of the performance of Heap32Next are
here:
http://thenewjamesbaker.blogspot.com/2009/11/performance-of-heap32next-on-64-bit.html
This report springs from this openssl-users thread:
http://groups.google.com/group/mailing.openssl.users/browse_thread/thread/b38d72135da93951/d3cf46fe6311ddbb
Attached is rand_win.cpp, a test harness I used in MSVC2005 to instrument a
stripped-down version of RAND_poll.
// randwin.cpp
#include <stdio.h>
#include <tchar.h>
#define OPENSSL_SYS_WINDOWS 1
// Don't need these to run the relevant parts of RAND_poll
//#include "cryptlib.h"
//#include <openssl/rand.h>
//#include "rand_lcl.h"
#if defined(OPENSSL_SYS_WINDOWS) || defined(OPENSSL_SYS_WIN32)
#include <windows.h>
#ifndef _WIN32_WINNT
# define _WIN32_WINNT 0x0400
#endif
#include <wincrypt.h>
#include <tlhelp32.h>
/* Limit the time spent walking through the heap, processes, threads and
modules to
a maximum of 1000 miliseconds each, unless CryptoGenRandom failed */
#define MAXDELAY 1000
/* Intel hardware RNG CSP -- available from
* http://developer.intel.com/design/security/rng/redist_license.htm
*/
#define PROV_INTEL_SEC 22
#define INTEL_DEF_PROV L"Intel Hardware Cryptographic Service Provider"
/* It appears like CURSORINFO, PCURSORINFO and LPCURSORINFO are only defined
when WINVER is 0x0500 and up, which currently only happens on Win2000.
Unfortunately, those are typedefs, so they're a little bit difficult to
detect properly. On the other hand, the macro CURSOR_SHOWING is defined
within the same conditional, so it can be use to detect the absence of said
typedefs. */
#ifndef CURSOR_SHOWING
/*
* Information about the global cursor.
*/
typedef struct tagCURSORINFO
{
DWORD cbSize;
DWORD flags;
HCURSOR hCursor;
POINT ptScreenPos;
} CURSORINFO, *PCURSORINFO, *LPCURSORINFO;
#define CURSOR_SHOWING 0x00000001
#endif /* CURSOR_SHOWING */
#if !defined(OPENSSL_SYS_WINCE)
typedef BOOL (WINAPI *CRYPTACQUIRECONTEXTW)(HCRYPTPROV *, LPCWSTR, LPCWSTR,
DWORD, DWORD);
typedef BOOL (WINAPI *CRYPTGENRANDOM)(HCRYPTPROV, DWORD, BYTE *);
typedef BOOL (WINAPI *CRYPTRELEASECONTEXT)(HCRYPTPROV, DWORD);
typedef HWND (WINAPI *GETFOREGROUNDWINDOW)(VOID);
typedef BOOL (WINAPI *GETCURSORINFO)(PCURSORINFO);
typedef DWORD (WINAPI *GETQUEUESTATUS)(UINT);
typedef HANDLE (WINAPI *CREATETOOLHELP32SNAPSHOT)(DWORD, DWORD);
typedef BOOL (WINAPI *CLOSETOOLHELP32SNAPSHOT)(HANDLE);
typedef BOOL (WINAPI *HEAP32FIRST)(LPHEAPENTRY32, DWORD, size_t);
typedef BOOL (WINAPI *HEAP32NEXT)(LPHEAPENTRY32);
typedef BOOL (WINAPI *HEAP32LIST)(HANDLE, LPHEAPLIST32);
typedef BOOL (WINAPI *PROCESS32)(HANDLE, LPPROCESSENTRY32);
typedef BOOL (WINAPI *THREAD32)(HANDLE, LPTHREADENTRY32);
typedef BOOL (WINAPI *MODULE32)(HANDLE, LPMODULEENTRY32);
#include <lmcons.h>
#include <lmstats.h>
#if 1 /* The NET API is Unicode only. It requires the use of the UNICODE
* macro. When UNICODE is defined LPTSTR becomes LPWSTR. LMSTR was
* was added to the Platform SDK to allow the NET API to be used in
* non-Unicode applications provided that Unicode strings were still
* used for input. LMSTR is defined as LPWSTR.
*/
typedef NET_API_STATUS (NET_API_FUNCTION * NETSTATGET)
(LPWSTR, LPWSTR, DWORD, DWORD, LPBYTE*);
typedef NET_API_STATUS (NET_API_FUNCTION * NETFREE)(LPBYTE);
#endif /* 1 */
#endif /* !OPENSSL_SYS_WINCE */
//////////////////////////// My stubs
void RAND_add(void* buf, SIZE_T buffer_size, int entropy_size) {
//printf("Add%d ", entropy_size);
}
int RAND_poll(void)
{
HCRYPTPROV hProvider = 0;
int good = 0;
printf("Starting RAND_poll.\n");
{
/* load functions dynamically - not available on all systems */
HMODULE advapi = LoadLibrary(TEXT("ADVAPI32.DLL"));
HMODULE kernel = LoadLibrary(TEXT("KERNEL32.DLL"));
HMODULE user = NULL;
HMODULE netapi = LoadLibrary(TEXT("NETAPI32.DLL"));
CRYPTACQUIRECONTEXTW acquire = NULL;
CRYPTGENRANDOM gen = NULL;
CRYPTRELEASECONTEXT release = NULL;
NETSTATGET netstatget = NULL;
NETFREE netfree = NULL;
BYTE buf[64];
if (advapi)
{
printf("ADVAPI32.DLL loaded.\n");
/*
* If it's available, then it's available in both ANSI
* and UNICODE flavors even in Win9x, documentation says.
* We favor Unicode...
*/
acquire = (CRYPTACQUIRECONTEXTW) GetProcAddress(advapi,
"CryptAcquireContextW");
gen = (CRYPTGENRANDOM) GetProcAddress(advapi,
"CryptGenRandom");
release = (CRYPTRELEASECONTEXT) GetProcAddress(advapi,
"CryptReleaseContext");
}
if (acquire && gen && release)
{
printf("Got ProcAddresses for CryptoAPI functions\n");
/* poll the CryptoAPI PRNG */
/* The CryptoAPI returns sizeof(buf) bytes of randomness */
if (acquire(&hProvider, NULL, NULL, PROV_RSA_FULL,
CRYPT_VERIFYCONTEXT))
{
printf("Acquired RSA_FULL context.\n");
if (gen(hProvider, sizeof(buf), buf) != 0)
{
RAND_add(buf, sizeof(buf), 0);
good = 1;
printf("randomness from PROV_RSA_FULL\n");
}
release(hProvider, 0);
}
/* poll the Pentium PRG with CryptoAPI */
if (acquire(&hProvider, 0, INTEL_DEF_PROV, PROV_INTEL_SEC, 0))
{
printf("Acquired Pentium PRG context\n");
if (gen(hProvider, sizeof(buf), buf) != 0)
{
RAND_add(buf, sizeof(buf), sizeof(buf));
good = 1;
printf("randomness from PROV_INTEL_SEC\n");
}
release(hProvider, 0);
}
}
if (advapi)
FreeLibrary(advapi);
printf("good: %d\n", good);
if (kernel)
{
printf("KERNEL32.DLL loaded.\n");
CREATETOOLHELP32SNAPSHOT snap;
CLOSETOOLHELP32SNAPSHOT close_snap;
HANDLE handle;
HEAP32FIRST heap_first;
HEAP32NEXT heap_next;
HEAP32LIST heaplist_first, heaplist_next;
PROCESS32 process_first, process_next;
THREAD32 thread_first, thread_next;
MODULE32 module_first, module_next;
HEAPLIST32 hlist;
HEAPENTRY32 hentry;
DWORD stoptime = 0;
snap = (CREATETOOLHELP32SNAPSHOT)
GetProcAddress(kernel, "CreateToolhelp32Snapshot");
close_snap = (CLOSETOOLHELP32SNAPSHOT)
GetProcAddress(kernel, "CloseToolhelp32Snapshot");
heap_first = (HEAP32FIRST) GetProcAddress(kernel, "Heap32First");
heap_next = (HEAP32NEXT) GetProcAddress(kernel, "Heap32Next");
heaplist_first = (HEAP32LIST) GetProcAddress(kernel, "Heap32ListFirst");
heaplist_next = (HEAP32LIST) GetProcAddress(kernel, "Heap32ListNext");
process_first = (PROCESS32) GetProcAddress(kernel, "Process32First");
process_next = (PROCESS32) GetProcAddress(kernel, "Process32Next");
thread_first = (THREAD32) GetProcAddress(kernel, "Thread32First");
thread_next = (THREAD32) GetProcAddress(kernel, "Thread32Next");
module_first = (MODULE32) GetProcAddress(kernel, "Module32First");
module_next = (MODULE32) GetProcAddress(kernel, "Module32Next");
if (snap && heap_first && heap_next && heaplist_first &&
heaplist_next && process_first && process_next &&
thread_first && thread_next && module_first &&
module_next && (handle = snap(TH32CS_SNAPALL,0))
!= INVALID_HANDLE_VALUE)
{
printf("Got ProcAddresses for
Heap/Process/Thread/Module functions.\n");
/* heap list and heap walking */
/* HEAPLIST32 contains 3 fields that will change with
* each entry. Consider each field a source of 1 byte
* of entropy.
* HEAPENTRY32 contains 5 fields that will change with
* each entry. Consider each field a source of 1 byte
* of entropy.
*/
hlist.dwSize = sizeof(HEAPLIST32);
DWORD starttime = GetTickCount();
if (good) stoptime = starttime + MAXDELAY;
printf("starttime: %d\n", starttime);
printf("stoptime: %d\n", stoptime);
if (heaplist_first(handle, &hlist)) {
printf("Got heaplist_first.\n");
do
{
RAND_add(&hlist, hlist.dwSize, 3);
hentry.dwSize = sizeof(HEAPENTRY32);
if (heap_first(&hentry,
hlist.th32ProcessID,
hlist.th32HeapID))
{
printf("heap1st ");
int entrycnt = 80;
do {
RAND_add(&hentry, hentry.dwSize, 5);
printf(".");
} while (heap_next(&hentry)
&& --entrycnt > 0);
}
} while (heaplist_next(handle,
&hlist) && GetTickCount() < stoptime);
DWORD realstoptime = GetTickCount();
printf("\nreal stop time: %d\n",
realstoptime);
printf("elapsed time: %d\n",
realstoptime - starttime);
}
}
FreeLibrary(kernel);
}
}
printf("Exiting RAND_poll\n");
return(1);
}
#endif
// Heap Allocations, Milliseconds
// 100000, 1531
// 200000, 3125
// 300000, 8828
// 400000, 10469
// 500000, 12297
// 600000, 22922
// 700000, 24359
// 800000, 26406
// 900000, 27844
// 1000000, 29453
// 1100000, 49250
// 1200000, 52078
// 1300000, 52953
// 1400000, 54562
// 2000000, 64781
// 2100000, 101172
#define NUM_ALLOCS 2100000
int _tmain(int argc, _TCHAR* argv[])
{
char** dummymem = new char*[NUM_ALLOCS];
for (int i = 0; i<NUM_ALLOCS; i++) {
dummymem[i] = new char[2];
}
RAND_poll();
printf("\nFinished. Hit Enter to terminate.\n");
getchar();
delete [] dummymem;
return 0;
}
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [email protected]
Automated List Manager [email protected]
