Entropy (computing)

From HandWiki
Short description: Computing concept


In computing, entropy is the randomness collected by an operating system or application for use in cryptography or other uses that require random data. This randomness is often collected from hardware sources (variance in fan noise or HDD), either pre-existing ones such as mouse movements or specially provided randomness generators. A lack of entropy can have a negative impact on performance and security.

Linux kernel

The Linux kernel generates entropy from keyboard timings, mouse movements, and integrated drive electronics (IDE) timings and makes the random character data available to other operating system processes through the special files /dev/random and /dev/urandom. This capability was introduced in Linux version 1.3.30.[1]

There are some Linux kernel patches allowing one to use more entropy sources.[2] The audio_entropyd project,[3] which is included in some operating systems such as Fedora, allows audio data to be used as an entropy source.[4] Also available are video_entropyd,[5] which calculates random data from a video-source and entropybroker,[6] which includes these three and can be used to distribute the entropy data to systems not capable of running any of these (e.g. virtual machines). Furthermore, one can use the HAVEGE algorithm through haveged to pool entropy.[7] In some systems, network interrupts can be used as an entropy source as well.[8]

OpenBSD kernel

Main page: OpenBSD security features

OpenBSD has integrated cryptography as one of its main goals and has always worked on increasing its entropy for encryption but also for randomising many parts of the OS, including various internal operations of its kernel. Around 2011, two of the random devices were dropped and linked into a single source as it could produce hundreds of megabytes per second of high quality random data on an average system.[clarification needed] This made depletion of random data by userland programs impossible on OpenBSD once enough entropy has initially been gathered.

Hurd kernel

A driver ported from the Linux kernel has been made available for the Hurd kernel.[9]

Solaris

/dev/random and /dev/urandom have been available as Sun packages or patches for Solaris since Solaris 2.6,[10] and have been a standard feature since Solaris 9.[11] As of Solaris 10, administrators can remove existing entropy sources or define new ones via the kernel-level cryptographic framework.

A 3rd-party kernel module implementing /dev/random is also available for releases dating back to Solaris 2.4.[10]

OS/2

There is a software package for OS/2 that allows software processes to retrieve random data.[12]

Windows

Microsoft Windows releases newer than Windows 95 use CryptoAPI to gather entropy in a similar fashion to Linux kernel's /dev/random.[13]

Windows's CryptoAPI uses the binary registry key HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Cryptography\RNG\Seed to store a seeded value from all of its entropy sources.[14]

Because CryptoAPI is closed-source, some free and open source software applications running on the Windows platform use other measures to get randomness. For example, GnuPG, as of version 1.06, uses a variety of sources such as the number of free bytes in memory that combined with a random seed generates desired randomness it needs.[15]

Programmers using CAPI can get entropy by calling CAPI's CryptGenRandom(), after properly initializing it.[16]

CryptoAPI was deprecated from Windows Vista and higher. New API is called Cryptography API: Next Generation (CNG).[17] Windows's CNG uses the binary registry key HKEY_LOCAL_MACHINE\SYSTEM\RNG\Seed to store a seeded value.

Newer version of Windows are able to use a variety of entropy sources:

  • TPM if available and enabled on motherboard
  • Entropy from UEFI interface (if booted from UEFI)[18]
  • RDRAND CPU instruction if available
  • Hardware system clock (RTC)
  • OEM0 ACPI table content
  • Interrupt timings
  • Keyboard timings and Mouse movements[19]

Embedded systems

Embedded systems have difficulty gathering enough entropy as they are often very simple devices with short boot times, and key generation operations that require sufficient entropy are often one of the first things a system may do. Common entropy sources may not exist on these devices, or will not have been active long enough during boot to ensure sufficient entropy exists. Embedded devices often lack rotating disk drives, human interface devices, and even fans, and the network interface, if any, will not have been active for long enough to provide much entropy. Lacking easy access to entropy, some devices may use hard-coded keys to seed random generators, or seed random generators from easily-guessed unique identifiers such as the device's MAC address. A simple study[which?] demonstrated the widespread use of weak keys by finding many embedded systems such as routers using the same keys. It was thought that the number of weak keys found would have been far higher if simple and often attacker determinable one-time unique identifiers had not been incorporated into the entropy of some of these systems.[20]

(De)centralized systems

A true random number generator (TRNG) can be a (de)central service. One example of a centralized system where a random number can be acquired is the randomness beacon service from the National Institute of Standards and Technology. The Cardano platform uses the participants of their decentralized proof-of-stake protocol to generate random numbers.[21]

Other systems

There are some software packages that allow one to use a userspace process to gather random characters, exactly what /dev/random does, such as EGD, the Entropy Gathering Daemon.[22]

Hardware-originated entropy

Modern CPUs and hardware often feature integrated generators that can provide high-quality and high-speed entropy to operating systems. On systems based on the Linux kernel, one can read the entropy generated from such a device through /dev/hw_random.[23] However, sometimes /dev/hw_random may be slow;[24][25]

There are some companies manufacturing entropy generation devices, and some of them are shipped with drivers for Linux.[26][27]

On Linux system, one can install the rng-tools package[28] that supports the true random number generators (TRNGs) found in CPUs supporting the RDRAND instruction, Trusted Platform Modules and in some Intel, AMD, or VIA chipsets,[29] effectively increasing the entropy collected into /dev/random and potentially improving the cryptographic potential. This is especially useful on headless systems that have no other sources of entropy.

Practical implications

System administrators, especially those supervising Internet servers, have to ensure that the server processes will not halt because of entropy depletion. Entropy on servers utilising the Linux kernel, or any other kernel or userspace process that generates entropy from the console and the storage subsystem, is often less than ideal because of the lack of a mouse and keyboard, thus servers have to generate their entropy from a limited set of resources such as IDE timings.

The entropy pool size in Linux is viewable through the file /proc/sys/kernel/random/entropy_avail and should generally be at least 2000 bits (out of a maximum of 4096).[30][31] Entropy changes frequently.

Administrators responsible for systems that have low or zero entropy should not attempt to use /dev/urandom as a substitute for /dev/random as this may cause SSL/TLS connections to have lower-grade encryption.[32]

Some software systems change their Diffie-Hellman keys often, and this may in some cases help a server to continue functioning normally even with an entropy bottleneck.[33]

On servers with low entropy, a process can appear hung when it is waiting for random characters to appear in /dev/random (on Linux-based systems). For example, there was a known problem in Debian that caused exim4 to hang in some cases because of this.[34]

Security

Entropy sources can be used for keyboard timing attacks.[35]

Entropy can affect the cryptography (TLS/SSL) of a server: If a server fails to use a proper source of randomness, the keys generated by the server will be insecure. In some cases a cracker (malicious attacker) can guess some bits of entropy from the output of a pseudorandom number generator (PRNG), and this happens when not enough entropy is introduced into the PRNG.[36]

Potential sources

Commonly used entropy sources include the mouse, keyboard, and IDE timings, but there are other potential sources. For example, one could collect entropy from the computer's microphone, or by building a sensor to measure the air turbulence inside a disk drive.[37]

For Unix/BSD derivatives there exists a USB based solution that utilizes an ARM Cortex CPU for filtering / securing the bit stream generated by two entropy generator sources in the system.[38]

Cloudflare use an image feed from a rack of 80 lava lamps as an additional source of entropy.[39]

See also

References

  1. ↑ random(4) - Linux man page (die.net)
  2. ↑ "Robotic Tendencies » Missing entropy". https://ramcq.net/2005/09/25/missing-entropy/. 
  3. ↑ "audio entropy daemon". March 23, 2021. https://www.vanheusden.com/aed/. 
  4. ↑ "Fedora Package Database – audio-entropyd". https://admin.fedoraproject.org/pkgdb/packages/name/audio-entropyd. [yes|permanent dead link|dead link}}]
  5. ↑ "video_entropyd". March 23, 2021. https://www.vanheusden.com/ved/. 
  6. ↑ "Entropy Broker". May 29, 2020. https://www.vanheusden.com/entropybroker/. 
  7. ↑ "haveged – A simple entropy daemon". http://www.issihosts.com/haveged/. Retrieved 3 April 2011. 
  8. ↑ "Entropy and Random Devices | LinuxLink by TimeSys – Your Embedded Linux Resource". https://linuxlink.timesys.com/docs/about_entropy. 
  9. ↑ /dev/{,u}random driver for GNU/Hurd (ibofobi.dk)
  10. ↑ 10.0 10.1 "Solaris /dev/random through emulation". http://www.cosy.sbg.ac.at/%7Eandi/SUNrand/. 
  11. ↑ "Solaris /dev/random". http://docs.sun.com/app/docs/doc/816-5177/random-7d?a=view. 
  12. ↑ "Rexx Entropy Gathering Daemon for OS/2". http://r6.ca/RexxEGD/. 
  13. ↑ Malayter, Ryan (November 9, 2001). "GPL command-line shred alternative for Windows". https://lists.gnupg.org/pipermail/gnupg-users/2001-November/010831.html. 
  14. ↑ "Source for entropy on Windows platforms with CryptoAPI installed". https://www.mail-archive.com/openssl-dev@openssl.org/msg21829.html. 
  15. ↑ Malayter, Ryan (February 15, 2002). "How does Windows GnuPG generate random numbers on keygen?". https://lists.gnupg.org/pipermail/gnupg-users/2002-February/011909.html. 
  16. ↑ "[or-cvs Get entropy in windows."]. https://archives.seul.org/or/cvs/Mar-2004/msg00078.html. 
  17. ↑ "About CNG - Win32 apps". https://msdn.microsoft.com/en-us/library/windows/desktop/aa375276(v=vs.85).aspx. 
  18. ↑ "UEFI entropy gathering protocol - Windows drivers". https://docs.microsoft.com/en-us/windows-hardware/drivers/bringup/uefi-entropy-gathering-protocol. 
  19. ↑ "CryptGenRandom function (Wincrypt.h) - Win32 apps". https://docs.microsoft.com/en-us/windows/win32/api/wincrypt/nf-wincrypt-cryptgenrandom. 
  20. ↑ Constantin, Lucian. "Millions of embedded devices use the same hard-coded SSH and TLS private keys" (in en). Network World. https://www.networkworld.com/article/3009139/millions-of-embedded-devices-use-the-same-hard-coded-ssh-and-tls-private-keys.html. 
  21. ↑ "A solution for scalable randomness". June 6, 2017. https://iohk.io/en/blog/posts/2017/06/06/a-solution-for-scalable-randomness/. Retrieved September 14, 2020. """" 
  22. ↑ "Random Numbers". https://dwheeler.com/secure-programs/Secure-Programs-HOWTO/random-numbers.html. 
  23. ↑ "'Re: SSL/TLS entropy problem,' - MARC". https://marc.info/?l=kroupware&m=116377029100152&w=2. 
  24. ↑ "Re: /dev/hw_random". http://www.redhat.com/archives/rhl-devel-list/2004-August/msg00770.html. 
  25. ↑ "Re: /dev/hw_random". http://www.redhat.com/archives/rhl-devel-list/2004-August/msg00786.html. 
  26. ↑ "Random Noise Sources". http://www.std.com/~reinhold/truenoise.html. 
  27. ↑ http://random.com.hr/products/random/hg324.html
  28. ↑ "rng-tools". http://packages.debian.org/unstable/utils/rng-tools. 
  29. ↑ "Linux support for random number generator in i8xx chipsets — The Linux Kernel documentation". 2000. https://www.kernel.org/doc/Documentation/hw_random.txt. 
  30. ↑ "Re: [exim no reply to STARTTLS"]. https://lists.exim.org/lurker/message/20060217.000128.2064ef9b.en.html. 
  31. ↑ random(4) Linux man page , die.net
  32. ↑ "'SSL/TLS entropy problem, aka pops timeouts (was: sasl ldap problem)' - MARC". https://marc.info/?l=kroupware&m=116375188915536&w=2. 
  33. ↑ Josefsson, Simon; [TLS Re: Short Ephermal Diffie-Hellman keys] (ietf.org mailing list)
  34. ↑ "[gnutls-dev gnutls_rsa_params_init hangs. Is regenerating rsa-params once a day too frequent?"]. 14 December 2004. http://lists.gnupg.org/pipermail/gnutls-dev/2004-December/000800.html. 
  35. ↑ Zalewski, Michal; Unix entropy source can be used for keystroke timing attacks , 2003
  36. ↑ Re: entropy depletion (was: SSL/TLS passive sniffing) , 2005
  37. ↑ "Build your own cryptographically safe server/client protocol - 4.8.3. Collecting entropy". http://www.codeproject.com/internet/YourOwnSecureProtocol.asp?df=100&forumid=316484&exp=0&select=1846294. 
  38. ↑ "Simtec Electronics Entropy Key: USB True Random Number Generator". Archived from the original on July 22, 2010. https://web.archive.org/web/20100722164508/http://www.entropykey.co.uk/. 
  39. ↑ "Randomness 101: LavaRand in Production". November 6, 2017. http://blog.cloudflare.com/randomness-101-lavarand-in-production/. 

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Entropy_(computing)&oldid=3372482"