[openssl-dev] [openssl.org #3828] OpenSSL random number generator initialization causes a deadlock on Windows

Thu Apr 30 18:03:05 UTC 2015

Hi,

we discoverd a bug in the PRND initialization of OpenSSL (version 1.0.1j, but the code in the current version is identical) when executed on Windows 7 SP1. We're assuming that the problem is very likely to occur on all Windows Versions.
The function RAND_poll that is used to seed the PRND walks through heap entries (rand_win.c lines 430 - 478). A deadlock can occur when another thread is implicitly creating a low fragmentation heap at the same time the OpenSSL thread traverses the heap. Details why this can happen are explained below.

Here is our WinDbg session output. In this output the deadlock situation is clearly visible:

Critical Sections

0:000> !locks
...
CritSec +630138 at 00630138
WaiterWoken        No
LockCount          8
RecursionCount     1
OwningThread       600
EntryCount         0
ContentionCount    6e
*** Locked

CritSec +38c0138 at 038c0138
WaiterWoken        No
LockCount          1
RecursionCount     1
OwningThread       52c
EntryCount         0
ContentionCount    2
*** Locked
...

Thread Callstacks

Callstack of Thread 600
# ChildEBP RetAddr  Args to Child
00 03bcec98 77339e2e 00000540 00000000 00000000 ntdll!NtWaitForSingleObject+0x15
01 03bcecfc 77339d12 00000000 00000000 03bceeac ntdll!RtlpWaitOnCriticalSection+0x13e
02 03bced24 7733782a 038c0138 00000000 00000000 ntdll!RtlEnterCriticalSection+0x150
03 03bced58 773bf9d6 038c0000 74fc9206 03bceeec ntdll!RtlLockHeap+0x3d
04 03bcee40 7738de9e 03bceeac 773a3dc5 00000000 ntdll!RtlpQueryExtendedHeapInformation+0xbd
05 03bcee80 773a445d 00000000 00000002 03bceeac ntdll!RtlQueryHeapInformation+0x4a
06 03bcef24 77383320 04830000 75030000 03bcefec ntdll!RtlQueryProcessHeapInformation+0x288
07 03bcefa0 750c5f33 000004ec 00000014 04830000 ntdll!RtlQueryProcessDebugInformation+0x28a
08 03bcefd0 100526b6 04830000 d7b8ddca 00000014 kernel32!Heap32Next+0x4d
09 03bcf4e4 1004e3c4 00000000 00004000 03826c00 lib!RAND_poll+0x586
0a 03bcf538 1004e7a3 03826d08 00000010 00000001 lib!ssleay_rand_bytes+0xd4
0b 03bcf54c 1005a4f5 03826d08 00000010 006e5001 lib!ssleay_rand_pseudo_bytes+0x13
0c 03bcf568 1012445f 101b2ba8 d7b8d822 006e50a8 lib!SSL_CTX_new+0x2a5
...

Callstack of Thread 52c
# ChildEBP RetAddr  Args to Child
00 0338f3f8 77339e2e 00000454 00000000 00000000 ntdll!NtWaitForSingleObject+0x15
01 0338f45c 77339d12 00000000 00000000 00630000 ntdll!RtlpWaitOnCriticalSection+0x13e
02 0338f484 77339f93 00630138 74788926 00078000 ntdll!RtlEnterCriticalSection+0x150
03 0338f560 77333074 000003f8 00000400 00000000 ntdll!RtlpAllocateHeap+0x159
04 0338f5e4 77338593 00630000 00800000 000003f8 ntdll!RtlAllocateHeap+0x23a
05 0338f630 77337a87 00000028 74788a86 04190048 ntdll!RtlpAllocateUserBlock+0xae
06 0338f6c0 7732e0f2 04190048 04190048 00000000 ntdll!RtlpLowFragHeapAllocFromContext+0x802
07 0338f734 77337489 00630000 00000000 00000020 ntdll!RtlAllocateHeap+0x206
08 0338f744 77333fb3 038c0000 04190048 00000000 ntdll!RtlpAllocateDebugInfo+0x28
09 0338f780 773342f4 04190048 00000000 00000000 ntdll!RtlInitializeCriticalSectionEx+0x93
0a 0338f794 7733ee0d 04190048 04190048 038c0000 ntdll!RtlInitializeCriticalSection+0x12
0b 0338f7a8 7733eddb 00000000 00000800 038c0000 ntdll!RtlpInitializeLowFragHeap+0x28
0c 0338f7b8 7733eb85 74788bb6 038c00cc 038c0000 ntdll!RtlpCreateLowFragHeap+0x28
0d 0338f7f0 7733ec2d 038c0000 038c021c 0338f8dc ntdll!RtlpActivateLowFragmentationHeap+0xc9
0e 0338f800 7733ebf9 038c0000 7478849a 72c8d09c ntdll!RtlpPerformHeapMaintenance+0x2a
0f 0338f8dc 77333074 0000008c 00000098 038c021c ntdll!RtlpAllocateHeap+0x172
10 0338f960 72c85b50 038c0000 00000008 0000008c ntdll!RtlAllocateHeap+0x23a
11 0338f99c 754459b1 024b4a54 0338faa8 00000000 nlaapi!WSM_NSPLookupServiceBegin_v2+0x5e
12 0338f9b8 7544598d 024b4a18 0338faa8 00000000 ws2_32!NSPROVIDER::NSPLookupServiceBegin+0x1b
13 0338f9d4 7544591c 024b4dd8 0338faa8 00000000 ws2_32!NSPROVIDERSTATE::LookupServiceBegin+0x1d
14 0338fa38 754457cc 024d63b8 0338faa8 00000210 ws2_32!NSQUERY::LookupServiceBegin+0x18d
15 0338fa88 7566ea34 0338faa8 00000210 0069c3a8 ws2_32!WSALookupServiceBeginW+0x7f
16 0338fafc 7566e987 00000000 0338fb24 75663577 wininet!NLA_NET_CHANGE::Initialize+0xa3
17 0338fb08 75663577 00000001 00000000 00000000 wininet!CheckForNetworkChange+0x26
18 0338fb24 756590bf 037accb8 037b86e8 00000000 wininet!CFsm_HttpSendRequest::RunSM+0x98
19 0338fb64 75659779 037b86e8 00000000 00000000 wininet!CFsm::Run+0x7a
1a 0338fb7c 75686366 037be640 75665e5d 0339528c wininet!DoFsm+0x25
1b 0338fbcc 756838ca 00cc000c 00000000 00000000 wininet!HttpWrapSendRequest+0x1ce
1c 0338fbf0 756d1b16 00cc000c 00000000 00000000 wininet!InternalHttpSendRequestA+0x1d
1d 0338fc48 101076ec 00cc000c 00000000 00000000 wininet!HttpSendRequestA+0x36
...

Conclusions

Notes:

-      The first parameter of RtlEnterCriticalSection is the pointer to the critical section the caller wants to lock.

-      The first parameter of RtlAllocateHeap is the heap handle

-      The first parameter of RtlLockHeap is the heap handle

The threads are in a deadlock situation because:

-      Thread 600

o    Locks critical section 00630138

o    Waits for critical section 038c0138

-      Thread 52c

o    Locks critical section 038c0138

o    Waits for critical section 00630138

?  Deadlock

Why does the deadlock occur?

-      Thread 600 locks the critical section 00630138. This critical section belongs to the heap 00630000. I don't know why thread 600 keeps this critical section locked.

-      Thread 52c allocates memory on heap 038c0000. The heap is locked (critical section 038c0138).

-      Thread 600 wants to query extended heap information for the heap 038c0000 and waits because the heap is locked (critical section 038c0138).

-      Thread 52c: Windows decides to activate the low fragmentation feature on the heap 038c0000.

-      Thread 52c: Windows creates a new critical section and wants to store the critical section in the heap 00630000.

-      Thread 52c: Because the heap 00630000 is locked (critical section 00630138) thread 52c wait.

-      Now thread 52c and 600 are in a deadlock situation and the heap 038c0000 and 00630000 are locked forever which blocks other threads too.

What does this mean:

-      It isn't a good idea to traverse heaps on Windows operating systems.

How to fix the problem:

Note: We've analyzed three different deadlock situations on two different machines. The callstacks for all deadlocks are nearly identical.

The same problem was reported by different users too:
http://openssl.6102.n7.nabble.com/Deadlock-in-RAND-poll-s-Heap32First-call-td2614.html
http://rt.openssl.org/Ticket/Display.html?id=2485&user=guest&pass=guest

We're changed our code in a way that we're avoiding the deadlock situation by reading some random bytes from the random number generator in a static initializer. This initializes the PRND at process start. But this workaround just lowers the probability that the deadlock occurs. Generally on Windows, heap data should not be used as a source for the random number generator initialization. Therefore we're recommending to remove the heap traversing code in RAND_poll.

Mit freundlichen Gr??en

Stefan Titze
Entwicklung

[cid:baramundi_LOGO_Mailsignatur.jpg]<http://www.baramundi.de>

baramundi software AG
Beim Glaspalast 1
86153 Augsburg

stefan.titze at baramundi.de<mailto:stefan.titze at baramundi.de>
www.baramundi.de<http://www.baramundi.de/>

Fon: +49 (821) 5 67 08 - 575
Fax: +49 (821) 5 67 08 - 19

Vorstand: Dipl.-Ing. (FH) Uwe Beikirch | Marcus Eiglsperger
Aufsichtsratsvorsitzender: Rainer Liebich
Sitz und Registergericht: Augsburg, HRB-Nr. 2064 | USt-IdNr. DE 210294111

[cid:14-Fujitsu_DeskView.jpg]<https://www.baramundi.de/produkte/management-suite/connect/hardware-management/fujitsu-deskview/>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: baramundi_LOGO_Mailsignatur.jpg
Type: image/jpeg
Size: 10149 bytes
Desc: not available
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20150430/a07c8847/attachment-0002.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 14-Fujitsu_DeskView.jpg
Type: image/jpeg
Size: 31763 bytes
Desc: not available
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20150430/a07c8847/attachment-0003.jpg>