Archive for the ‘Security’ Category

Some Thoughts On Secure Random Numbers

Sunday, October 30th, 2016

Many protocols and cryptographic primitives such as DSA rely on secure random numbers. For example, the Signal messenger and it’s quite intricate protocol was recently analyzed and a paper about the analyses published[1]. The authors wrote that they “do not consider faulty/malicious random number generators” in their threat model, but also state that if “[…] generated randomness is compromised or bad, Signal offers no protection”. Secure random numbers are the most common weakness. A compromised random number generator used widely even allows for bulk data collection and decryption[2].

In my mind this problem is relatively easy to avoid. For one, protocols can be modified to  not to leak raw output of the random number generator, which makes practical attacks on the rng much harder. For example, instead of sending a nonce consisting of raw rng output, which would give an eavesdropper information to determine the state of the rng, one could use the sha512 of the rng output. To ensure that this is correctly implemented the protocol participants can exchange the raw rng output later once secure communication has been established and ensure that indeed the nonce that was used was sha512(rng) and not raw rng output itself. For primitives that require random numbers for operation (e.g., signing) one can use the secure hash of the message and private-key for a unique, deterministic and secure random number (this is used by ed25519, IIRC). My point is that most of these problems seem avoidable and systems can be hardened to not completely fail even if the random number generator has been compromised.

The other point is that random numbers should be generated by the OS and incorporate as many different sources as possible. Linux, OpenBSD and other operating systems offer APIs that return secure random numbers collected from various sources of entropy in the system. The latest generation of x86 chips even has RNG instructions that generate secure random numbers (caveats: [3,4]). I think the more entropy from difference sources the better (caveat: [5]), and personally I think systems like HAVEGED can be helpful as an additional source of entropy. One counter argument that I heard was that nobody knows how good this cpu entropy really is, and that entropy extracted from hard-disk latency (and similar). However, for other sources of entropy we don’t know that either. The most sensible paper showing entropy extraction from disk drive latency[6] shows that technically only for certain drives, and I’m willing to wager that all of these results will look quite differently for modern SSD drives. As far as I know quantifying the goodness of entropy sources on computers is an open research problem. I think adding entropy from cpu sources like HAVEGED does is helpful, especially in situations like device startup and other situations where there’s not a lot of entropy available from other sources.


[1] Katriel Cohn-Gordon, Cas Cremers, Benjamin Dowling, Luke Garratt, and Douglas Stebila, “A Formal Security Analysis of the Signal Messaging Protocol”,

[2] Daniel J. Bernstein, Tanja Lange, Ruben Niederhagen. “Dual EC: a standardized back door.” Pages 256–281 in The new codebreakers: essays dedicated to David Kahn on the occasion of his 85th birthday, edited by Peter Y. A. Ryan, David Naccache, Jean-Jacques Quisquater. Lecture Notes in Computer Science 9100, Springer, 2015. ISBN 978-3-662-49300-7.


[4] Becker, CHES’13 Proceedings of the 15th international conference on Cryptographic Hardware and Embedded Systems,Pages 197-214, DOI 10.1007/978-3-642-40349-1_12,


[6] D. Davis, R. Ihaka, and P. Fenstermacher, “Cryptographic Randomness from Air Turbulience in Disk Drives,” Advances in Cryptology — CRYPTO ’94 Proceedings, Springer-Verlag, 1994, pp. 114–120.

Random Number Generation on low entropy computer systems

Monday, October 13th, 2014

Lately, I got interested in random number generation. Generating random numbers securely so they are suitable for cryptographic use is hard.

Linux introduced /dev/random, a block device to a random number generator in the kernel. The generator keeps an estimate of the number of bits of noise in the entropy pool. From this entropy pool, random numbers are created by using a secure hash function on the data in the pool . When read, the /dev/random device will only return random bytes within the estimated number of bits of noise in the entropy pool. The Operating System adds entropy from all sorts of sources, such as disk latency. However, if you are running Linux on an embedded device (or “internet of things”) or in a cloud instance, there may not be a “real” disk drive, and whatever latency is measured may not contain good enough entropy. Another important source of entropy is the clock-cycle timer (rdtsc) that is called at various instances to measure the time between interrupts and other frequently and somewhat randomly occurring events. The rdtsc instruction is often virtualized in cloud-machines which could make it harder to get good entropy.  Anyways… the problem of getting random numbers in low-entropy situations is important enough that Intel added an on-chip random number generator to their new processors (rdrand), but many cloud instances emulate older CPUs and embedded system don’t necessarily run with x86 chips that have rdrand.

So far, so good. For now, I don’t have an embedded system to experiment with, but a similar problem is with servers in the cloud. Can the rdtsc instruction still be used to get entropy in a virtual machine? I found this, played around a bit with the program listed and also learned about the existence of haveged (I’ll get back to that). I started a micro-instance (1 CPU, 512Mb RAM) in a popular cloud service and found that, yes indeed, the rdtsc instruction seems to be virtualized. The average tick count between millions of two consecutive rdtsc instructions is far too small to account for whatever else is going on on the machine (unless, of course, I somehow got a 512MB machine all by myself – which is unlikely). On the other hand, the output of the least significant bit of the difference of two consecutive rdtsc calls looked pretty random, but didn’t pass randomness tests. Adding von-Neumann whitening on the LSB obtained from two rdtsc calls is actually sufficiently random to pass FIPS 140-2 randomness tests (I used the implementation in rngtest) and only fails about 1 in 1000 (comparison: a test-run with entropy from /dev/random failed 1:10000). So in theory, this should be okay to use as an entropy source, but maybe it should still be combined with other sources of entropy.

Coming back to other already existing solutions. It turns out there’s an entropy gathering demon called haveged that can add entropy to the pool to remedy low-entropy conditions that can occur in servers, but possibly also on embedded devices and in cloud instance. The method exploits the modifications of the internal volatile hardware states as a source of uncertainty. Modern superscalar processors feature various hardware mechanisms which aim to improve performance: caches, branch predictors, TLBs and much more. The state of these components is also volatile and cannot be directly monitored in software. On the other hand, every invocation of the operating system modifies thousands of these binary volatile states. The general idea of extracting entropy from rdtsc still works, however the only thing that still makes me wonder a bit is that the full timer (not just the LSB) is used and that the whitening method is rather complex.

I learned a lot, but there’s still more to explore. Cloud machines probably have more going on than embedded systems, so I’m still not convinced that this will work on embedded devices. I’ll try to wrap my head around the whitening function in haveged. It’s still being developed and maybe ARM support will be added some day. Then the demon could be used on smart phones to improve the security of the random number generation.



Cross-VM Side Channels and Their Use to Extract Private Keys

Sunday, October 28th, 2012

Cool application of machine learning in the security field: extracting private keys from virtual machines running on shared hardware by training a Support-Vector-Machine model to classify data bits collected.

Risk Assessment of Rare Events in adversarial Scenarios

Tuesday, June 21st, 2011

The RAND corporation just published an interesting paper exploring the benefits of using risk prediction to reduce the screening required at airports. You might have noticed various attempts to establish some kind of fast-lane or trusted traveler program. Obvious this is a very sensitive topic and probably hard to get right. Screening certain groups of the population more than others (“profiling”) is generally frowned upon and also not a good idea in general (see “Strong profiling is not mathematically optimal for discovering rare malfeasors on rare event detection“), but what hasn’t been examined much is identifying people that can be considered more “safe” than others. The paper explores that idea and shows that even under the assumption that the bad guys will try and subvert this program that there can be benefits to implementing this solution. The paper is a bit sparse on mathematical details. Certainly an interesting idea, though.

Paper: Assessing the Security Benefits of a Trusted Traveler Program in the Presence of Attempted Attacker Exploitation and Compromise


Thursday, April 16th, 2009

My girlfriend caught a new (?) version of some malware on her machine; what a nuisance and scanners don’t seem to recognize this thing… Some think it’s Vundo others just complain that it’s packed. It doesn’t quite fit the Vundo description,though. MD5 8e06f428178cbfbf12a8372fa6b16d0d size 50688 bytes. It registers some CLSID 721ee819 – b263 – 42e0 – a594 – b82fd0f24bdf , a browser-helper object and various things for notifications by the LSA service plus AppInit_Dll. It constantly restores these keys and it seems that even stomping out all the threads that this DLL-thing spawned everywhere won’t help. I overlooked something and it just comes back as soon as the next GUI app is started. As soon as I know how to get rid of it, I’ll update this post.

Update 1:

It hooks AppInit, the run key using rundll32 to start itself and the LSA notification (something Hijackthis doesn’t check). I can kill all the threads that this thing generates in each executable with ProcessExplorer and regmon will show that the constant checking of the appinit-key stops. However, as soon as the next GUI application is started it is back. So I deleted all the events and mutex objects that things created (I found some clues in the strings in memory) in each executable, again making sure that I didn’t miss anything, and it took a few seconds this time for it to come back. There’s “something” that will load the DLL with OpenProcess to load the DLL into the process space. Since the strings in the DLL show that it opens and writes to process memory this wouldn’t be surprising; question is how I find the threads that do this. Other odd things include that svchost starts a window-less iexplore.exe presumably to upload some stuff to a server or something. It might have some sloppy rootkit (RootkitRevealer went nuts with file-system discrepancies), because I can’t find the DLL (using “dir”) referenced in the keys, yet the tab-extension finds it and overwriting the non-existant file gets an access denied. Some interesting strings from the decrypted memory image of the DLL:

wscntfy.exe wscntfy_mtx mrt.exe explorer.exe iexplore.exe opera.exe firefox.exe Global\ mrt.exe explorer.exe iexplore.exe opera.exe firefox.exe dll .tmp exe rdl InprocServer32 \Internet Explorer\PhishingFilter Enabled Rundll32.exe ” ThreadingModel Both \Internet Explorer\ieuser.exe -Embedding tmp MS Juan cpm las SHELL32.dll ole32.dll OLEAUT32.dll vector<T> too long unknown ntoskrnl.exe ntkrnlmp.exe ntkrnlpa.exe ntkrpamp.exe Mozilla/4.0 (compatible; MSIE 6.0) WinNT 5.1 LoadLibraryW Kernel32 SeDebugPrivilege /frame.html url suid dnsapi.dll DnsQuery_A DnsRecordListFree Global\ wuauserv SYSTEM CURRENT_USER Advapi32.dll ConvertStringSidToSidA IsWow64Process kernel32 shell32.dll SHGetKnownFolderPath wininet.dll InternetOpenUrlA HttpOpenRequestA InternetCloseHandle InternetConnectA InternetOpenA InternetSetOptionA InternetQueryOptionA HttpQueryInfoA HttpSendRequestA InternetReadFile HttpAddRequestHeadersA HTTP/1.1 POST Content-Length ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ InprocServer32 setupapi.dll IsUserAdmin BITS b’kJ SHGetFolderPathW CoCreateInstance CoTaskMemFree CoInitialize CoUninitialize CoCreateGuid __dllonexit _onexit _XcptFilter _initterm _amsg_exit _adjust_fdiv WriteFile FlushFileBuffers LocalFree CreateFileW GetFileSize VirtualAlloc ReadFile VirtualFree GetModuleFileNameW lstrcpyW CreateMutexW GetLastError WaitForMultipleObjects GetExitCodeThread lstrlenW OpenMutexW WaitForSingleObject GetProcAddress GetModuleHandleA OpenProcess VirtualAllocEx WriteProcessMemory CreateRemoteThread VirtualFreeEx CreateToolhelp32Snapshot Process32FirstW lstrcmpiW Process32NextW GetCurrentProcess OpenEventW SetEvent Sleep ResetEvent lstrcatW MoveFileW MoveFileExW SetFilePointer SetEndOfFile ReleaseMutex GetModuleFileNameA DisableThreadLibraryCalls ExitProcess LoadLibraryW InitializeCriticalSection DeleteCriticalSection EnterCriticalSection LeaveCriticalSection GetSystemTimeAsFileTime FreeLibrary LoadLibraryA GetLogicalDriveStringsW GetDriveTypeW DeleteFileW GetTickCount GetCurrentThreadId CreateDirectoryW GetSystemTime SystemTimeToFileTime SetFileTime GetWindowsDirectoryA GetVolumeInformationA CreateProcessW OpenMutexA OpenEventA GetCurrentThread GetCurrentProcessId TerminateProcess TerminateThread CreateEventW WideCharToMultiByte HeapAlloc GetProcessHeap HeapFree SetFileAttributesW InterlockedIncrement InterlockedDecrement GetVersion lstrcmpiA lstrcpynW InterlockedExchange InterlockedCompareExchange RtlUnwind QueryPerformanceCounter UnhandledExceptionFilter SetUnhandledExceptionFilter KERNEL32.dll CallNextHookEx SetWindowsHookExA PostMessageA UnhookWindowsHookEx GetSystemMetrics USER32.dll OpenProcessToken LookupPrivilegeValueA AdjustTokenPrivileges RegCreateKeyExW RegDeleteValueW RegFlushKey RegCloseKey RegDeleteKeyW RegQueryValueExW RegSetValueExW RegOpenKeyExW SetSecurityInfo RegEnumValueW GetTokenInformation IsValidSid ConvertSidToStringSidW OpenSCManagerA OpenServiceA ControlService ChangeServiceConfigA AllocateAndInitializeSid CheckTokenMembership FreeSid InitializeSecurityDescriptor SetSecurityDescriptorDacl ConvertStringSidToSidA SetEntriesInAclA DuplicateTokenEx SetTokenInformation GetLengthSid SetThreadToken RegQueryInfoKeyA RegEnumKeyExA RegOpenKeyExA RegQueryValueExA CloseServiceHandle QueryServiceConfigA QueryServiceStatusEx StartServiceA ADVAPI32.dll LocalAlloc RaiseException _except_handler3 222.dll DllCanUnloadNow DllGetClassObject Software\Microsoft\Windows\CurrentVersion\Run Software\Microsoft\Windows\CurrentVersion\Explorer\Browser Helper Objects CLSID SYSTEM\CurrentControlSet\Control\Lsa Notification Packages Software\Microsoft\Windows NT\CurrentVersion\Windows AppInit_DLLs LoadAppInit_DLLs Software\Microsoft\Internet Explorer\Main Check_Associations Software\Microsoft\Windows\CurrentVersion\Ext\Settings Software\Microsoft SYSTEM\CurrentControlSet\Control\Session Manager PendingFileRenameOperations PendingFileRenameOperations2 Software\Microsoft\Windows\CurrentVersion\Explorer\ShellExecuteHooks Software\Microsoft\Security Center UpdatesDisableNotify Software\Microsoft\Security Center\Svc EnableNotifications EnableNotifications\Ref Software\Microsoft\Windows NT\CurrentVersion DigitalProductId RegisteredOrganization RegisteredOwner C:\WINDOWS\system32\renobuda C:\WINDOWS\system32\calc.exe C:\WINDOWS\system32\defariha.dll C:\WINDOWS\system32\defariha.dll C:\WINDOWS\system32\dadeyisi.dll C:\WINDOWS\system32\vofehafi.dll {721ee819-b263-42e0-a594-b82fd0f24bdf} Global\vimegolatiturew Global\nifuseguji C:\WINDOWS\system32\mrt.exe own1 hdn_dsk .?AVCDownloader@@ .?AVCUrlStorage@@ .?AUIObjectWithSite@@ .?AVCConBHO@@ .?AUIUnknown@@ .?AUIClassFactory@@ .?AVCFactory@@

Update 2: Ok, I got rid of it. Turns out there’s no root-kit; the DLL was simply marked as hidden (I feel stupid…). Killing all the threads off, preventing it from re-loading and then re-installing the Service-Pack seems to have gotten rid of it for good.

Photo-based CAPTCHAs

Wednesday, October 15th, 2008

I found an interesting article about solving photo-based CAPTCHAs (tell cats from dogs etc.). Turns out machine learning is quite capable of solving the Asirra CAPTCHA (apart from simply following the adopt-me link and deducing from the text whether it’s a cat or a dog).

CAPTCHAs – Not dead

Thursday, August 14th, 2008

I recently attended a talk where the authors claimed that the CAPTCHA technology (the squiggly letters they make you type in whenever you sign up for anything) is dead and defeated. I disagree. In the talk, they demonstrated how to break a couple of “home-brew” captcha-implementations they found on the internet. Most of them were – not surprisingly – not very good. I think this is almost comparable to people inventing there own encryption algorithms.

All the implementations they broke were either insecure implementations (accepting solutions several times, hiding the answer in an invisible form field etc.) or were simply writing numbers in images with little or no distortion. The audio captcha they broke was simply reading numbers with a little bit of clicking noise in the background. Those are all very simple. What is supposed to make “real” captchas hard is that they are hard to segment – compare the phpBB captcha with the one from Yahoo. In the later you will have problems separating the letters for your OCR. A good audio captcha overlays music, chatter or other noise that is hard to separate from the code being read.

Just like home brew cryptography, it is probably a good idea to use an established technology (think reCAPTCHA) that was made by people with a background in OCR. Edit: A nice recap of how well the reCAPTCHA project is coming along is in ArsTechnica.

ISC on the Future of Anti-Virus Protection

Friday, August 1st, 2008

An article on the Internet Storm Center discusses wether Anti-Virus software in the current state is a dead end. In my opinion it has been dead for quite a while now. Apart from the absolutely un-usable state that anti-virus software is in, I think it’s protecting the wrong things. Most attacks (trojans, spyware) nowadays come through web-browser exploits and maybe instant-messenger (see reports on ISC). So instead of scanning incoming emails, how about a behavior blocker for the web-browser and the instant messenger? There are a couple of freeware programs (e.g. IEController [German]) out there that successfully put Internet Explorer, etc. into a sandbox; whatever Javascript exploit – known or unknown – the browser won’t be able to execute arbitrary files or write outside its cache-directory. Why is there nothing like that in the commercial AV packages?

However, a few possibilities suggested in the article might be worth exploring. For example, they suggest Bayesian heuristics to identify threats. Using machine learning techniques might be a direction worth exploring. IBM AntiVirus (maybe not the current version anymore) has been using Neural Networks with 4Byte sequences (n-grams) for bootsector virus detection.

A couple things to keep in mind, though:

  • Quality of the classifier (detection rate) should be measured with Area-under-ROC-Curve (AUC), not error-rate like most people tend to do in Spam-Filter comparisons. The base-rate of the “non-virus” class is pretty high; I have over 10.000 executables/libraries on my windows machine. All (most?) of them non-malicious.
  • The tricky part with that is the feature extraction. While sequences of bytes or strings extracted from a binary might be a good start, advanced features like call-graphs or imported API-calls should be used as well. This is pretty tricky and time-consuming, especially when it has to be done for different types of executables (Windows scripts, x86-EXE files, .Net files etc.). De-obfuscation techniques, just like in the signature based scanners, will probably be necessary before the features can be extracted.
  • Behavior blocking and sandboxes are probably easier, a better short-term fix, and more pro-active. This has been my experience with email-based attacks as well back in the Mydoom days when a special mime-type auto-executed an attachment in Outlook. Interestingly there are only two programs out there that sanitize emails (check mime-types, headers, rename executable attachments etc.) at the gateway-level – a much better pro-active approach than simply detecting known threats. The first is Mimedefang, a sendmail plugin. The other is impsec, based on procmail. CU Boulder was using impsec to help keep student’s machines clean (there were scalability issues with the procmail solution, though).

Firewire and DRM

Thursday, March 6th, 2008

An old security vulnerability in the Windows Firewire implementation has resurfaced. I wonder how long it takes until Microsoft figures out that if one can read/write arbitrary memory (including kernel-memory), then one can probably find encryption keys to “secured media content” …

License Key Copy Protection

Saturday, February 2nd, 2008

I had written long before I had a blog about doing copy protection the right way (read: so it requires some effort to remove it). With the more recent programing frameworks a couple of things changed. For one, all the new programing frameworks (.NET, Java) have cryptography support, which means it is far simpler to incorporate a license key scheme based on digital signatures. Personally I like using 512bit-DSA (Digital Signature Algorithm) for these purposes, because the key is long enough to stop amateurs from computing the secret key and short enough that a signature encoded as BASE32 could be typed in by someone. In the software you obviously only include your public key for verifying the signature of your license.

One issue with byte-code languages is that they are fairly trivial to disassemble (and produce very human readable code). Microsoft even included an MSIL Disassembler with .NET. Therefore the code needs to be obfuscated. One thing to try (not all obfuscater-programs support this) is to make the names as human-unfriendly as possible. Renaming classes to “A” and “B” is nice, but renaming them to “XfGkoAlPPqzz” and “XfGkoBlPPqzz” makes it even harder to read.

With a signature-based license key the hackers have only a few options left since they can’t write a key-generator. For one, they could patch a different key into the software for which they know the private key and generate signatures for this new key. It’s therefore important to use a hash of the real private key in some other ways in the program. For example, one could hash the private-key string with SHA/MD5 and use the result as a key for decrypting some data with a symmetric cypher such as AES. Another idea is to put the hash (or a checksum using the hash of some data and the public key) in some saved user data in order to prevent data-exchange between the cracked and legitimate versions of the software.

The second option is to find where the accept/reject decision is made in the program and to patch this comparison. Note that API-calls to the framework are fairly easy to find, even in obfuscated code. You should therefore have the API-call (for the crypto-functions as well as displaying any kind of error-message like “invalid license key”) far away from the comparison-operation so the hackers have to dig through more code. Also, I found that using a command-pattern makes for fairly unintelligible byte-code. Consider creating a class that encapsulates commands and has some Execute() method that can also return which command to execute next. Now, if you have a couple of commands in a List that are executed in a loop by invoking all the respective Execute() methods, then that is a bit harder to follow. Consider writing commands that can change entries in some global hash-table of strings, an If-Command, a Goto-Command, a MessageBox-Comand, a Verify-Signature-Command etc. With all those implemented, you can encode a little program by putting all those commands in a list. The important thing now is to encode the accept/reject decision (and one or two important parts of your software unrelated to the license-key) using the Command-Pattern, i.e. to write little programs in your “command-pattern-programing-language”. The If-Statement being used for the accept/reject will then be the same spot every other condition is tested in your code and can therefore not be patched without destroying other parts of the program. This forces the hackers to understand your command-pattern and to figure out what bytes they have to change to make this an unconditional jump. I found this fairly easy, clean and straight-forward to program (and debug) in a high-level language, yet fairly hard to understand in obfuscated byte-code.