Entropy (computing)

Last updated

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.

Contents

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

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:

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

Related Research Articles

The Open Sound System (OSS) is an interface for making and capturing sound in Unix and Unix-like operating systems. It is based on standard Unix devices system calls. The term also sometimes refers to the software in a Unix kernel that provides the OSS interface; it can be thought of as a device driver for sound controller hardware. The goal of OSS is to allow the writing of sound-based applications that are agnostic of the underlying sound hardware.

A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG).

Transport Layer Security (TLS) is a cryptographic protocol designed to provide communications security over a computer network. The protocol is widely used in applications such as email, instant messaging, and voice over IP, but its use in securing HTTPS remains the most publicly visible.

<span class="mw-page-title-main">OpenSSL</span> Open-source implementation of the SSL and TLS protocols

OpenSSL is a software library for applications that provide secure communications over computer networks against eavesdropping, and identify the party at the other end. It is widely used by Internet servers, including the majority of HTTPS websites.

<span class="mw-page-title-main">/dev/random</span> Pseudorandom number generator file in Unix-like operating systems

In Unix-like operating systems, /dev/random and /dev/urandom are special files that serve as cryptographically secure pseudorandom number generators (CSPRNGs). They allow access to a CSPRNG that is seeded with entropy from environmental noise, collected from device drivers and other sources. /dev/random typically blocks if there was less entropy available than requested; more recently it usually blocks at startup until sufficient entropy has been gathered, then unblocks permanently. The /dev/urandom device typically was never a blocking device, even if the pseudorandom number generator seed was not fully initialized with entropy since boot. Not all operating systems implement the same methods for /dev/random and /dev/urandom.

The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protocols often require frequent generation of random quantities. Cryptographic attacks that subvert or exploit weaknesses in this process are known as random number generator attacks.

<span class="mw-page-title-main">TLS acceleration</span> Method to accelerate Transport Layer Security

TLS acceleration is a method of offloading processor-intensive public-key encryption for Transport Layer Security (TLS) and its predecessor Secure Sockets Layer (SSL) to a hardware accelerator.

A random password generator is a software program or hardware device that takes input from a random or pseudo-random number generator and automatically generates a password. Random passwords can be generated manually, using simple sources of randomness such as dice or coins, or they can be generated using a computer.

Crypto API is a cryptography framework in the Linux kernel, for various parts of the kernel that deal with cryptography, such as IPsec and dm-crypt. It was introduced in kernel version 2.5.45 and has since expanded to include essentially all popular block ciphers and hash functions.

<span class="mw-page-title-main">Random number generation</span> Producing a sequence that cannot be predicted better than by random chance

Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular outcome sequence will contain some patterns detectable in hindsight but impossible to foresee. True random number generators can be hardware random-number generators (HRNGs), wherein each generation is a function of the current value of a physical environment's attribute that is constantly changing in a manner that is practically impossible to model. This would be in contrast to so-called "random number generations" done by pseudorandom number generators (PRNGs), which generate numbers that only look random but are in fact pre-determined—these generations can be reproduced simply by knowing the state of the PRNG.

The Microsoft Windows platform specific Cryptographic Application Programming Interface is an application programming interface included with Microsoft Windows operating systems that provides services to enable developers to secure Windows-based applications using cryptography. It is a set of dynamically linked libraries that provides an abstraction layer which isolates programmers from the code used to encrypt the data. The Crypto API was first introduced in Windows NT 4.0 and enhanced in subsequent versions.

<span class="mw-page-title-main">Network Security Services</span> Collection of cryptographic computer libraries

Network Security Services (NSS) is a collection of cryptographic computer libraries designed to support cross-platform development of security-enabled client and server applications with optional support for hardware TLS/SSL acceleration on the server side and hardware smart cards on the client side. NSS provides a complete open-source implementation of cryptographic libraries supporting Transport Layer Security (TLS) / Secure Sockets Layer (SSL) and S/MIME. NSS releases prior to version 3.14 are tri-licensed under the Mozilla Public License 1.1, the GNU General Public License, and the GNU Lesser General Public License. Since release 3.14, NSS releases are licensed under GPL-compatible Mozilla Public License 2.0.

CryptGenRandom is a deprecated cryptographically secure pseudorandom number generator function that is included in Microsoft CryptoAPI. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed. A 2007 paper from Hebrew University suggested security problems in the Windows 2000 implementation of CryptGenRandom. Microsoft later acknowledged that the same problems exist in Windows XP, but not in Vista. Microsoft released a fix for the bug with Windows XP Service Pack 3 in mid-2008.

There are various implementations of the Advanced Encryption Standard, also known as Rijndael.

Mbed TLS is an implementation of the TLS and SSL protocols and the respective cryptographic algorithms and support code required. It is distributed under the Apache License version 2.0. Stated on the website is that Mbed TLS aims to be "easy to understand, use, integrate and expand".

wolfSSL is a small, portable, embedded SSL/TLS library targeted for use by embedded systems developers. It is an open source implementation of TLS written in the C programming language. It includes SSL/TLS client libraries and an SSL/TLS server implementation as well as support for multiple APIs, including those defined by SSL and TLS. wolfSSL also includes an OpenSSL compatibility interface with the most commonly used OpenSSL functions.

The Transport Layer Security (TLS) protocol provides the ability to secure communications across or inside networks. This comparison of TLS implementations compares several of the most notable libraries. There are several TLS implementations which are free software and open source.

RDRAND is an instruction for returning random numbers from an Intel on-chip hardware random number generator which has been seeded by an on-chip entropy source. Intel introduced the feature around 2012, and AMD added support for the instruction in June 2015.

The OpenBSD Cryptographic Framework (OCF) is a service virtualization layer for the uniform management of cryptographic hardware by an operating system. It is part of the OpenBSD Project, having been included in the operating system since OpenBSD 2.8. Like other OpenBSD projects such as OpenSSH, it has been ported to other systems based on Berkeley Unix such as FreeBSD and NetBSD, and to Solaris and Linux. One of the Linux ports is supported by Intel for use with its proprietary cryptographic software and hardware to provide hardware-accelerated SSL encryption for the open source Apache HTTP Server.

Entropy-supplying system calls are system calls in Unix-like operating system kernels through which processes can obtain entropic or random data. The first of these was getentropy, introduced to the OpenBSD operating system in release 5.6, as a refactoring of the sysctl(3) KERN_ARND approach used since 1997. Linux offers a very similar system call, getrandom, which was based on getentropy. It was first available in Linux 3.17, released in October 2014. In July 2015, Solaris introduced slightly modified versions of getentropy and getrandom. In August 2015, FreeBSD introduced the read_random system call for obtaining random data from the kernel.

References

  1. ↑ random(4) - Linux man page Archived 2007-10-11 at the Wayback Machine (die.net)
  2. ↑ "Robotic Tendencies » Missing entropy". Archived from the original on 2022-12-06. Retrieved 2023-05-23.
  3. ↑ "audio entropy daemon". March 23, 2021. Archived from the original on 2021-03-23.
  4. ↑ "Fedora Package Database – audio-entropyd".[ permanent dead link ]
  5. ↑ "video_entropyd". March 23, 2021. Archived from the original on 2021-03-23.
  6. ↑ "Entropy Broker". May 29, 2020. Archived from the original on 2020-05-29.
  7. ↑ "haveged – A simple entropy daemon". Archived from the original on 27 October 2012. Retrieved 3 April 2011.
  8. ↑ "Entropy and Random Devices | LinuxLink by TimeSys – Your Embedded Linux Resource". Archived from the original on 2016-04-02. Retrieved 2007-10-15.
  9. ↑ /dev/{,u}random driver for GNU/Hurd Archived 2007-09-18 at the Wayback Machine (ibofobi.dk)
  10. 1 2 "Solaris /dev/random through emulation". Archived from the original on 2007-11-04. Retrieved 2007-10-15.
  11. ↑ "Solaris /dev/random". Archived from the original on 2008-05-11. Retrieved 2007-10-17.
  12. ↑ "Rexx Entropy Gathering Daemon for OS/2". r6.ca. Archived from the original on 2007-10-31. Retrieved 2007-10-15.
  13. ↑ Malayter, Ryan (November 9, 2001). "GPL command-line shred alternative for Windows". Archived from the original on October 27, 2021. Retrieved May 23, 2023.
  14. ↑ "Source for entropy on Windows platforms with CryptoAPI installed". www.mail-archive.com. Archived from the original on 2018-10-02. Retrieved 2023-05-23.
  15. ↑ Malayter, Ryan (February 15, 2002). "How does Windows GnuPG generate random numbers on keygen?". Archived from the original on December 1, 2021. Retrieved May 23, 2023.
  16. ↑ "[or-cvs] Get entropy in windows". archives.seul.org. Archived from the original on 2013-05-07. Retrieved 2023-05-23.
  17. ↑ "About CNG - Win32 apps". Archived from the original on 2018-05-17. Retrieved 2018-05-17.
  18. ↑ "UEFI entropy gathering protocol - Windows drivers". Archived from the original on 2018-05-17. Retrieved 2018-05-17.
  19. ↑ "CryptGenRandom function (Wincrypt.h) - Win32 apps". Archived from the original on 2020-08-12. Retrieved 2020-08-31.
  20. ↑ Constantin, Lucian. "Millions of embedded devices use the same hard-coded SSH and TLS private keys". Network World. Archived from the original on 2018-11-05. Retrieved 2018-11-05.
  21. ↑ "A solution for scalable randomness". iohk.io. June 6, 2017. Archived from the original on April 17, 2021. Retrieved September 14, 2020.
  22. ↑ "Random Numbers". dwheeler.com. Archived from the original on 2022-12-30. Retrieved 2023-05-23.
  23. ↑ "'Re: SSL/TLS entropy problem,' - MARC". marc.info. Archived from the original on 2018-11-15. Retrieved 2023-05-23.
  24. ↑ "Re: /dev/hw_random". Archived from the original on 2007-10-31. Retrieved 2007-10-15.
  25. ↑ "Re: /dev/hw_random". Archived from the original on 2007-11-12. Retrieved 2007-10-15.
  26. ↑ "Random Noise Sources". Archived from the original on 2007-11-21. Retrieved 2007-10-15.
  27. ↑ http://random.com.hr/products/random/hg324.html Archived 2008-05-13 at the Wayback Machine
  28. ↑ "rng-tools". Archived from the original on 2007-10-21. Retrieved 2007-10-16.
  29. ↑ "Linux support for random number generator in i8xx chipsets — The Linux Kernel documentation". www.kernel.org. 2000. Archived from the original on 31 July 2013.
  30. ↑ "Re: [exim] no reply to STARTTLS". lists.exim.org. Archived from the original on 2012-07-22. Retrieved 2023-05-23.
  31. ↑ random(4) Linux man page Archived 2007-10-11 at the Wayback Machine , die.net
  32. ↑ "'SSL/TLS entropy problem, aka pops timeouts (was: sasl ldap problem)' - MARC". marc.info. Archived from the original on 2018-11-15. Retrieved 2023-05-23.
  33. ↑ Josefsson, Simon; [TLS] Re: Short Ephermal Diffie-Hellman keys Archived 2007-11-11 at the Wayback Machine (ietf.org mailing list)
  34. ↑ "[gnutls-dev] gnutls_rsa_params_init hangs. Is regenerating rsa-params once a day too frequent?". lists.gnupg.org. 14 December 2004. Archived from the original on 2007-01-17.
  35. ↑ Zalewski, Michal; Unix entropy source can be used for keystroke timing attacks Archived 2011-07-19 at the Wayback Machine , 2003
  36. ↑ Re: entropy depletion (was: SSL/TLS passive sniffing) Archived 2011-05-17 at the Wayback Machine , 2005
  37. ↑ "Build your own cryptographically safe server/client protocol - 4.8.3. Collecting entropy". Archived from the original on 2012-07-23. Retrieved 2020-01-08.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  38. ↑ "Simtec Electronics Entropy Key: USB True Random Number Generator". www.entropykey.co.uk. Archived from the original on July 22, 2010.
  39. ↑ "Randomness 101: LavaRand in Production". The Cloudflare Blog. November 6, 2017. Archived from the original on May 1, 2023. Retrieved May 23, 2023.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.