From patchwork Mon Apr 30 16:27:29 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Zack Weinberg X-Patchwork-Id: 27058 Received: (qmail 24198 invoked by alias); 30 Apr 2018 16:27:45 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 24076 invoked by uid 89); 30 Apr 2018 16:27:44 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.0 required=5.0 tests=GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, SPF_PASS, TIME_LIMIT_EXCEEDED autolearn=unavailable version=3.3.2 spammy=Republic, India, modern, zealand X-HELO: mailbackend.panix.com From: Zack Weinberg To: libc-alpha@sourceware.org Cc: carlos@redhat.com, fweimer@redhat.com, nmav@redhat.com Subject: [PATCH 1/3] Reshuffle manual sections on cryptography and random numbers. Date: Mon, 30 Apr 2018 12:27:29 -0400 Message-Id: <20180430162731.2971-2-zackw@panix.com> In-Reply-To: <20180430162731.2971-1-zackw@panix.com> References: <20180430162731.2971-1-zackw@panix.com> MIME-Version: 1.0 The "unpredictable bytes" section of crypt.texi and the "pseudo-random numbers" section of math.texi are moved to a new chapter, random.texi; the obsolete DES encryption functions are also moved to a new chapter, des.texi. This leaves crypt.texi devoted entirely to password handling. I completely dropped the "Legal Problems" section, because it is more than a little out-of-date and we don't have the manpower or the expertise to keep it up to date. Better not to say anything at all than to say something misleading. All discussion of FIPS compliance has also been dropped. I also revised the description of the 'crypt' function a little, and wrote new introductory text for crypt.texi, des.texi, and random.texi. More could be done. * manual/des.texi, manual/random.texi: New manual chapters. * manual/crypt.texi: "DES encryption" section moved to des.texi; "unpredictable bytes" section moved to random.texi; "legal problems" section removed. New introductory text. Improve explanation of salt formats. Mention support for SHA-2-based hashes. * manual/math.texi: "Pseudo-Random Numbers" section moved to random.texi. * manual/arith.texi, manual/conf.texi, manual/time.texi: Adjust next/prev links. * manual/string.texi (memfrob, strfry): Drop cross-references to DES encryption. --- manual/Makefile | 4 +- manual/arith.texi | 2 +- manual/conf.texi | 2 +- manual/crypt.texi | 508 +++++------------------------- manual/des.texi | 195 ++++++++++++ manual/math.texi | 586 +---------------------------------- manual/random.texi | 753 +++++++++++++++++++++++++++++++++++++++++++++ manual/string.texi | 6 +- manual/time.texi | 2 +- 9 files changed, 1035 insertions(+), 1023 deletions(-) create mode 100644 manual/des.texi create mode 100644 manual/random.texi diff --git a/manual/Makefile b/manual/Makefile index c2756640a7..4d71219d69 100644 --- a/manual/Makefile +++ b/manual/Makefile @@ -36,9 +36,9 @@ endif chapters = $(addsuffix .texi, \ intro errno memory ctype string charset locale \ message search pattern io stdio llio filesys \ - pipe socket terminal syslog math arith time \ + pipe socket terminal syslog math arith random time \ resource setjmp signal startup process ipc job \ - nss users sysinfo conf crypt debug threads \ + nss users sysinfo conf crypt des debug threads \ probes tunables) appendices = lang.texi header.texi install.texi maint.texi platform.texi \ contrib.texi diff --git a/manual/arith.texi b/manual/arith.texi index 116788ba9a..fe4bf9bd0d 100644 --- a/manual/arith.texi +++ b/manual/arith.texi @@ -1,4 +1,4 @@ -@node Arithmetic, Date and Time, Mathematics, Top +@node Arithmetic, Random Number Generation, Mathematics, Top @c %MENU% Low level arithmetic functions @chapter Arithmetic Functions diff --git a/manual/conf.texi b/manual/conf.texi index f1dce4aa44..bc1faea671 100644 --- a/manual/conf.texi +++ b/manual/conf.texi @@ -1,4 +1,4 @@ -@node System Configuration, Cryptographic Functions, System Management, Top +@node System Configuration, Password Handling, System Management, Top @c %MENU% Parameters describing operating system limits @chapter System Configuration Parameters diff --git a/manual/crypt.texi b/manual/crypt.texi index 99d2d8e092..d967ca32c2 100644 --- a/manual/crypt.texi +++ b/manual/crypt.texi @@ -1,95 +1,25 @@ -@c This node must have no pointers. -@node Cryptographic Functions -@c @node Cryptographic Functions, Debugging Support, System Configuration, Top -@chapter DES Encryption and Password Handling -@c %MENU% DES encryption and password handling +@node Password Handling, Obsolete Encryption, System Configuration, Top +@chapter Password Handling +@c %MENU% Password Handling -On many systems, it is unnecessary to have any kind of user -authentication; for instance, a workstation which is not connected to a -network probably does not need any user authentication, because to use -the machine an intruder must have physical access. - -Sometimes, however, it is necessary to be sure that a user is authorized -to use some service a machine provides---for instance, to log in as a +Sometimes it is necessary to be sure that a user is authorized to use +some service a machine provides---for instance, to log in as a particular user id (@pxref{Users and Groups}). One traditional way of -doing this is for each user to choose a secret @dfn{password}; then, the -system can ask someone claiming to be a user what the user's password -is, and if the person gives the correct password then the system can -grant the appropriate privileges. - -If all the passwords are just stored in a file somewhere, then this file -has to be very carefully protected. To avoid this, passwords are run -through a @dfn{one-way function}, a function which makes it difficult to -work out what its input was by looking at its output, before storing in -the file. +doing this is for each user to choose a secret @dfn{password}; then, +the system can ask someone claiming to be a user what the user's +password is, and if the person gives the correct password then the +system can grant the appropriate privileges. -@Theglibc{} provides a one-way function that is compatible with -the behavior of the @code{crypt} function introduced in FreeBSD 2.0. -It supports two one-way algorithms: one based on the MD5 -message-digest algorithm that is compatible with modern BSD systems, -and the other based on the Data Encryption Standard (DES) that is -compatible with Unix systems. - -@vindex AUTH_DES -@cindex FIPS 140-2 -It also provides support for Secure RPC, and some library functions that -can be used to perform normal DES encryption. The @code{AUTH_DES} -authentication flavor in Secure RPC, as provided by @theglibc{}, -uses DES and does not comply with FIPS 140-2 nor does any other use of DES -within @theglibc{}. It is recommended that Secure RPC should not be used -for systems that need to comply with FIPS 140-2 since all flavors of -encrypted authentication use normal DES. +Programs that handle passwords must take special care not to reveal +them to anyone, no matter what. @Theglibc{} provides functions to +assist with two aspects of password handling: prompting for passwords +on a terminal, and one-way hashing of passwords for storage. @menu -* Legal Problems:: This software can get you locked up, or worse. * getpass:: Prompting the user for a password. * crypt:: A one-way function for passwords. -* DES Encryption:: Routines for DES encryption. -* Unpredictable Bytes:: Randomness for cryptography purposes. @end menu -@node Legal Problems -@section Legal Problems - -Because of the continuously changing state of the law, it's not possible -to provide a definitive survey of the laws affecting cryptography. -Instead, this section warns you of some of the known trouble spots; this -may help you when you try to find out what the laws of your country are. - -Some countries require that you have a license to use, possess, or import -cryptography. These countries are believed to include Byelorussia, -Burma, India, Indonesia, Israel, Kazakhstan, Pakistan, Russia, and Saudi -Arabia. - -Some countries restrict the transmission of encrypted messages by radio; -some telecommunications carriers restrict the transmission of encrypted -messages over their network. - -Many countries have some form of export control for encryption software. -The Wassenaar Arrangement is a multilateral agreement between 33 -countries (Argentina, Australia, Austria, Belgium, Bulgaria, Canada, the -Czech Republic, Denmark, Finland, France, Germany, Greece, Hungary, -Ireland, Italy, Japan, Luxembourg, the Netherlands, New Zealand, Norway, -Poland, Portugal, the Republic of Korea, Romania, the Russian -Federation, the Slovak Republic, Spain, Sweden, Switzerland, Turkey, -Ukraine, the United Kingdom and the United States) which restricts some -kinds of encryption exports. Different countries apply the arrangement -in different ways; some do not allow the exception for certain kinds of -``public domain'' software (which would include this library), some -only restrict the export of software in tangible form, and others impose -significant additional restrictions. - -The United States has additional rules. This software would generally -be exportable under 15 CFR 740.13(e), which permits exports of -``encryption source code'' which is ``publicly available'' and which is -``not subject to an express agreement for the payment of a licensing fee or -royalty for commercial production or sale of any product developed with -the source code'' to most countries. - -The rules in this area are continuously changing. If you know of any -information in this manual that is out-of-date, please report it to -the bug database. @xref{Reporting Bugs}. - @node getpass @section Reading Passwords @@ -136,7 +66,24 @@ The substitute takes the same parameters as @code{getline} (@pxref{Line Input}); the user must print any prompt desired. @node crypt -@section Encrypting Passwords +@section One-way Hashing for Passwords + +Passwords are stored in a file that is only accessible with special +privileges, but this is not enough protection by itself; the file +might be ``leaked'' via a bug or a misconfiguration, and system +administrators shouldn't learn everyone's password even if they have +to edit that file for some reason. To avoid this, passwords are also +run through a @dfn{one-way hash function}, a function which makes it +difficult to work out what its input was by looking at its output, +before they are stored in the file. + +@Theglibc{} currently supports four different one-way functions, based +on the SHA-2-512, SHA-2-256, MD5, and DES cryptographic primitives. +New passwords should be hashed with either of the SHA-based functions. +The other two are only still supported for backward compatibility; it +is too easy for an intruder to decode them by making many guesses. +The DES-based hash is especially weak, because it ignores all but the +first eight characters of its input. @deftypefun {char *} crypt (const char *@var{key}, const char *@var{salt}) @standards{BSD, crypt.h} @@ -145,7 +92,7 @@ The substitute takes the same parameters as @code{getline} @c Besides the obvious problem of returning a pointer into static @c storage, the DES initializer takes an internal lock with the usual @c set of problems for AS- and AC-Safety. The FIPS mode checker and the -@c NSS implementations of may leak file descriptors if canceled. The +@c NSS implementations may leak file descriptors if cancelled. @c The MD5, SHA256 and SHA512 implementations will malloc on long keys, @c and NSS relies on dlopening, which brings about another can of worms. @@ -156,38 +103,59 @@ that, given the output of the function, the best way to find a @var{key} that will produce that output is to guess values of @var{key} until the original value of @var{key} is found. -The @var{salt} parameter does two things. Firstly, it selects which -algorithm is used, the MD5-based one or the DES-based one. Secondly, it -makes life harder for someone trying to guess passwords against a file -containing many passwords; without a @var{salt}, an intruder can make a -guess, run @code{crypt} on it once, and compare the result with all the -passwords. With a @var{salt}, the intruder must run @code{crypt} once -for each different salt. - -For the MD5-based algorithm, the @var{salt} should consist of the string -@code{$1$}, followed by up to 8 characters, terminated by either -another @code{$} or the end of the string. The result of @code{crypt} -will be the @var{salt}, followed by a @code{$} if the salt didn't end -with one, followed by 22 characters from the alphabet -@code{./0-9A-Za-z}, up to 34 characters total. Every character in the -@var{key} is significant. +The @var{salt} parameter controls which one-way function is used, and +it also ensures that the output of the one-way function is different +for every user, even if they have the same password. This makes life +harder for someone trying to guess passwords against a file containing +many passwords. Without a @var{salt}, the intruder could make a +guess, run @code{crypt} on it once, and compare the result with all +the passwords. With a @var{salt}, the intruder must run @code{crypt} +once for each different salt. + +To verify a password, pass the previously hashed password as the @var{salt}. + +To hash a new password for storage, set @var{salt} to a string +consisting of a prefix plus a sequence of randomly chosen characters, +according to this table: + +@multitable @columnfractions .3 .3 .4 +@headitem Algorithm @tab Prefix @tab Random sequence +@item SHA-2-512 +@tab @samp{$6$} +@tab 16 characters +@item SHA-2-256 +@tab @samp{$5$} +@tab 16 characters +@item MD5 +@tab @samp{$1$} +@tab 8 characters +@item DES +@tab @samp{} +@tab 2 characters +@end multitable + +In all cases, the random characters should be chosen from the alphabet +@code{./0-9A-Za-z}. +@end deftypefun -For the DES-based algorithm, the @var{salt} should consist of two -characters from the alphabet @code{./0-9A-Za-z}, and the result of -@code{crypt} will be those two characters followed by 11 more from the -same alphabet, 13 in total. Only the first 8 characters in the -@var{key} are significant. +@deftypefun {char *} crypt_r (const char *@var{key}, const char *@var{salt}, {struct crypt_data *} @var{data}) +@standards{GNU, crypt.h} +@safety{@prelim{}@mtsafe{}@asunsafe{@asucorrupt{} @asulock{} @ascuheap{} @ascudlopen{}}@acunsafe{@aculock{} @acsmem{}}} +@c Compared with crypt, this function fixes the @mtasurace:crypt +@c problem, but nothing else. -The MD5-based algorithm has no limit on the useful length of the -password used, and is slightly more secure. It is therefore preferred -over the DES-based algorithm. +The @code{crypt_r} function does the same thing as @code{crypt}, but +takes an extra parameter which includes space for its result (among +other things), so it can be reentrant. @code{data@w{->}initialized} must be +cleared to zero before the first time @code{crypt_r} is called. -When the user enters their password for the first time, the @var{salt} -should be set to a new string which is reasonably random. To verify a -password against the result of a previous call to @code{crypt}, pass -the result of the previous call as the @var{salt}. +The @code{crypt_r} function is a GNU extension. @end deftypefun +The @code{crypt} and @code{crypt_r} functions are declared in the +header @file{crypt.h}. @code{crypt} is also declared in +@file{unistd.h}. + The following short program is an example of how to use @code{crypt} the first time a password is entered. Note that the @var{salt} generation is just barely acceptable; in particular, it is not unique between @@ -205,319 +173,3 @@ for a password and prints ``Access granted.'' if the user types @smallexample @include testpass.c.texi @end smallexample - -@deftypefun {char *} crypt_r (const char *@var{key}, const char *@var{salt}, {struct crypt_data *} @var{data}) -@standards{GNU, crypt.h} -@safety{@prelim{}@mtsafe{}@asunsafe{@asucorrupt{} @asulock{} @ascuheap{} @ascudlopen{}}@acunsafe{@aculock{} @acsmem{}}} -@c Compared with crypt, this function fixes the @mtasurace:crypt -@c problem, but nothing else. - -The @code{crypt_r} function does the same thing as @code{crypt}, but -takes an extra parameter which includes space for its result (among -other things), so it can be reentrant. @code{data@w{->}initialized} must be -cleared to zero before the first time @code{crypt_r} is called. - -The @code{crypt_r} function is a GNU extension. -@end deftypefun - -The @code{crypt} and @code{crypt_r} functions are prototyped in the -header @file{crypt.h}. - -@node DES Encryption -@section DES Encryption - -@cindex FIPS 46-3 -The Data Encryption Standard is described in the US Government Federal -Information Processing Standards (FIPS) 46-3 published by the National -Institute of Standards and Technology. The DES has been very thoroughly -analyzed since it was developed in the late 1970s, and no new -significant flaws have been found. - -However, the DES uses only a 56-bit key (plus 8 parity bits), and a -machine has been built in 1998 which can search through all possible -keys in about 6 days, which cost about US$200000; faster searches would -be possible with more money. This makes simple DES insecure for most -purposes, and NIST no longer permits new US government systems -to use simple DES. - -For serious encryption functionality, it is recommended that one of the -many free encryption libraries be used instead of these routines. - -The DES is a reversible operation which takes a 64-bit block and a -64-bit key, and produces another 64-bit block. Usually the bits are -numbered so that the most-significant bit, the first bit, of each block -is numbered 1. - -Under that numbering, every 8th bit of the key (the 8th, 16th, and so -on) is not used by the encryption algorithm itself. But the key must -have odd parity; that is, out of bits 1 through 8, and 9 through 16, and -so on, there must be an odd number of `1' bits, and this completely -specifies the unused bits. - -@deftypefun void setkey (const char *@var{key}) -@standards{BSD, crypt.h} -@standards{SVID, crypt.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:crypt}}@asunsafe{@asucorrupt{} @asulock{}}@acunsafe{@aculock{}}} -@c The static buffer stores the key, making it fundamentally -@c thread-unsafe. The locking issues are only in the initialization -@c path; cancelling the initialization will leave the lock held, it -@c would otherwise repeat the initialization on the next call. - -The @code{setkey} function sets an internal data structure to be an -expanded form of @var{key}. @var{key} is specified as an array of 64 -bits each stored in a @code{char}, the first bit is @code{key[0]} and -the 64th bit is @code{key[63]}. The @var{key} should have the correct -parity. -@end deftypefun - -@deftypefun void encrypt (char *@var{block}, int @var{edflag}) -@standards{BSD, crypt.h} -@standards{SVID, crypt.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:crypt}}@asunsafe{@asucorrupt{} @asulock{}}@acunsafe{@aculock{}}} -@c Same issues as setkey. - -The @code{encrypt} function encrypts @var{block} if -@var{edflag} is 0, otherwise it decrypts @var{block}, using a key -previously set by @code{setkey}. The result is -placed in @var{block}. - -Like @code{setkey}, @var{block} is specified as an array of 64 bits each -stored in a @code{char}, but there are no parity bits in @var{block}. -@end deftypefun - -@deftypefun void setkey_r (const char *@var{key}, {struct crypt_data *} @var{data}) -@deftypefunx void encrypt_r (char *@var{block}, int @var{edflag}, {struct crypt_data *} @var{data}) -@standards{GNU, crypt.h} -@c setkey_r: @safety{@prelim{}@mtsafe{}@asunsafe{@asucorrupt{} @asulock{}}@acunsafe{@aculock{}}} -@safety{@prelim{}@mtsafe{}@asunsafe{@asucorrupt{} @asulock{}}@acunsafe{@aculock{}}} - -These are reentrant versions of @code{setkey} and @code{encrypt}. The -only difference is the extra parameter, which stores the expanded -version of @var{key}. Before calling @code{setkey_r} the first time, -@code{data->initialized} must be cleared to zero. -@end deftypefun - -The @code{setkey_r} and @code{encrypt_r} functions are GNU extensions. -@code{setkey}, @code{encrypt}, @code{setkey_r}, and @code{encrypt_r} are -defined in @file{crypt.h}. - -@deftypefun int ecb_crypt (char *@var{key}, char *@var{blocks}, unsigned int @var{len}, unsigned int @var{mode}) -@standards{SUNRPC, rpc/des_crypt.h} -@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} - -The function @code{ecb_crypt} encrypts or decrypts one or more blocks -using DES. Each block is encrypted independently. - -The @var{blocks} and the @var{key} are stored packed in 8-bit bytes, so -that the first bit of the key is the most-significant bit of -@code{key[0]} and the 63rd bit of the key is stored as the -least-significant bit of @code{key[7]}. The @var{key} should have the -correct parity. - -@var{len} is the number of bytes in @var{blocks}. It should be a -multiple of 8 (so that there are a whole number of blocks to encrypt). -@var{len} is limited to a maximum of @code{DES_MAXDATA} bytes. - -The result of the encryption replaces the input in @var{blocks}. - -The @var{mode} parameter is the bitwise OR of two of the following: - -@vtable @code -@item DES_ENCRYPT -@standards{SUNRPC, rpc/des_crypt.h} -This constant, used in the @var{mode} parameter, specifies that -@var{blocks} is to be encrypted. - -@item DES_DECRYPT -@standards{SUNRPC, rpc/des_crypt.h} -This constant, used in the @var{mode} parameter, specifies that -@var{blocks} is to be decrypted. - -@item DES_HW -@standards{SUNRPC, rpc/des_crypt.h} -This constant, used in the @var{mode} parameter, asks to use a hardware -device. If no hardware device is available, encryption happens anyway, -but in software. - -@item DES_SW -@standards{SUNRPC, rpc/des_crypt.h} -This constant, used in the @var{mode} parameter, specifies that no -hardware device is to be used. -@end vtable - -The result of the function will be one of these values: - -@vtable @code -@item DESERR_NONE -@standards{SUNRPC, rpc/des_crypt.h} -The encryption succeeded. - -@item DESERR_NOHWDEVICE -@standards{SUNRPC, rpc/des_crypt.h} -The encryption succeeded, but there was no hardware device available. - -@item DESERR_HWERROR -@standards{SUNRPC, rpc/des_crypt.h} -The encryption failed because of a hardware problem. - -@item DESERR_BADPARAM -@standards{SUNRPC, rpc/des_crypt.h} -The encryption failed because of a bad parameter, for instance @var{len} -is not a multiple of 8 or @var{len} is larger than @code{DES_MAXDATA}. -@end vtable -@end deftypefun - -@deftypefun int DES_FAILED (int @var{err}) -@standards{SUNRPC, rpc/des_crypt.h} -@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} -This macro returns 1 if @var{err} is a `success' result code from -@code{ecb_crypt} or @code{cbc_crypt}, and 0 otherwise. -@end deftypefun - -@deftypefun int cbc_crypt (char *@var{key}, char *@var{blocks}, unsigned int @var{len}, unsigned int @var{mode}, char *@var{ivec}) -@standards{SUNRPC, rpc/des_crypt.h} -@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} - -The function @code{cbc_crypt} encrypts or decrypts one or more blocks -using DES in Cipher Block Chaining mode. - -For encryption in CBC mode, each block is exclusive-ored with @var{ivec} -before being encrypted, then @var{ivec} is replaced with the result of -the encryption, then the next block is processed. Decryption is the -reverse of this process. - -This has the advantage that blocks which are the same before being -encrypted are very unlikely to be the same after being encrypted, making -it much harder to detect patterns in the data. - -Usually, @var{ivec} is set to 8 random bytes before encryption starts. -Then the 8 random bytes are transmitted along with the encrypted data -(without themselves being encrypted), and passed back in as @var{ivec} -for decryption. Another possibility is to set @var{ivec} to 8 zeroes -initially, and have the first block encrypted consist of 8 random -bytes. - -Otherwise, all the parameters are similar to those for @code{ecb_crypt}. -@end deftypefun - -@deftypefun void des_setparity (char *@var{key}) -@standards{SUNRPC, rpc/des_crypt.h} -@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} - -The function @code{des_setparity} changes the 64-bit @var{key}, stored -packed in 8-bit bytes, to have odd parity by altering the low bits of -each byte. -@end deftypefun - -The @code{ecb_crypt}, @code{cbc_crypt}, and @code{des_setparity} -functions and their accompanying macros are all defined in the header -@file{rpc/des_crypt.h}. - -@node Unpredictable Bytes -@section Generating Unpredictable Bytes - -Some cryptographic applications (such as session key generation) need -unpredictable bytes. - -In general, application code should use a deterministic random bit -generator, which could call the @code{getentropy} function described -below internally to obtain randomness to seed the generator. The -@code{getrandom} function is intended for low-level applications which -need additional control over the blocking behavior. - -@deftypefun int getentropy (void *@var{buffer}, size_t @var{length}) -@standards{GNU, sys/random.h} -@safety{@mtsafe{}@assafe{}@acsafe{}} - -This function writes @var{length} bytes of random data to the array -starting at @var{buffer}, which must be at most 256 bytes long. The -function returns zero on success. On failure, it returns @code{-1} and -@code{errno} is updated accordingly. - -The @code{getentropy} function is declared in the header file -@file{sys/random.h}. It is derived from OpenBSD. - -The @code{getentropy} function is not a cancellation point. A call to -@code{getentropy} can block if the system has just booted and the kernel -entropy pool has not yet been initialized. In this case, the function -will keep blocking even if a signal arrives, and return only after the -entropy pool has been initialized. - -The @code{getentropy} function can fail with several errors, some of -which are listed below. - -@table @code -@item ENOSYS -The kernel does not implement the required system call. - -@item EFAULT -The combination of @var{buffer} and @var{length} arguments specifies -an invalid memory range. - -@item EIO -More than 256 bytes of randomness have been requested, or the buffer -could not be overwritten with random data for an unspecified reason. - -@end table - -@end deftypefun - -@deftypefun ssize_t getrandom (void *@var{buffer}, size_t @var{length}, unsigned int @var{flags}) -@standards{GNU, sys/random.h} -@safety{@mtsafe{}@assafe{}@acsafe{}} - -This function writes @var{length} bytes of random data to the array -starting at @var{buffer}. On success, this function returns the number -of bytes which have been written to the buffer (which can be less than -@var{length}). On error, @code{-1} is returned, and @code{errno} is -updated accordingly. - -The @code{getrandom} function is declared in the header file -@file{sys/random.h}. It is a GNU extension. - -The following flags are defined for the @var{flags} argument: - -@table @code -@item GRND_RANDOM -Use the @file{/dev/random} (blocking) pool instead of the -@file{/dev/urandom} (non-blocking) pool to obtain randomness. If the -@code{GRND_RANDOM} flag is specified, the @code{getrandom} function can -block even after the randomness source has been initialized. - -@item GRND_NONBLOCK -Instead of blocking, return to the caller immediately if no data is -available. -@end table - -The @code{getrandom} function is a cancellation point. - -Obtaining randomness from the @file{/dev/urandom} pool (i.e., a call -without the @code{GRND_RANDOM} flag) can block if the system has just -booted and the pool has not yet been initialized. - -The @code{getrandom} function can fail with several errors, some of -which are listed below. In addition, the function may not fill the -buffer completely and return a value less than @var{length}. - -@table @code -@item ENOSYS -The kernel does not implement the @code{getrandom} system call. - -@item EAGAIN -No random data was available and @code{GRND_NONBLOCK} was specified in -@var{flags}. - -@item EFAULT -The combination of @var{buffer} and @var{length} arguments specifies -an invalid memory range. - -@item EINTR -The system call was interrupted. During the system boot process, before -the kernel randomness pool is initialized, this can happen even if -@var{flags} is zero. - -@item EINVAL -The @var{flags} argument contains an invalid combination of flags. -@end table - -@end deftypefun diff --git a/manual/des.texi b/manual/des.texi new file mode 100644 index 0000000000..51db650e0e --- /dev/null +++ b/manual/des.texi @@ -0,0 +1,195 @@ +@node Obsolete Encryption, Debugging Support, Password Handling, Top +@chapter Obsolete Encryption +@c %MENU% Obsolete Encryption +@cindex DES +@cindex Data Encryption Standard + +For historical reasons, @theglibc{} includes several functions which +perform encryption using the obsolete Data Encryption Standard (DES). +None of these functions should be used in new programs. Instead, use +one of the many free encryption libraries that use modern ciphers. + +DES is a block cipher standardized by the US government in 1977. +It is no longer considered to be secure, and has been withdrawn as a +standard, because it only has @math{2@sup{56}} possible keys, so +testing all of them is practical. +@c +@c In 1998, it cost US$250,000 to build a massively parallel computer +@c that could test all the keys in three days. +@c +@c It would be nice to say how much a similar machine would cost now +@c (2018), and how fast it would be. + +@deftypefun void setkey (const char *@var{key}) +@standards{SVID, stdlib.h} +@standards{GNU, crypt.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:crypt}}@asunsafe{@asucorrupt{} @asulock{}}@acunsafe{@aculock{}}} +@c The static buffer stores the key, making it fundamentally +@c thread-unsafe. The locking issues are only in the initialization +@c path; cancelling the initialization will leave the lock held, it +@c would otherwise repeat the initialization on the next call. + +The @code{setkey} function prepares to perform DES encryption or +decryption using the key @var{key}. @var{key} should point to an +array of 64 @code{char}s, each of which must be set to either @samp{0} +or @samp{1}; that is, each byte stores one bit of the key. Every +eighth byte (array indices 7, 15, 23, @dots{}) must be set to give it +plus the preceding group of seven bytes odd parity. For instance, if +there are three bytes set to @samp{1} among bytes 0 through 6, then +byte 7 must be set to @samp{0}, and similarly if there are four bytes +set to @samp{1} among bytes 8 through 14, then byte 15 must be set to +@samp{0}, and so on. Thus, of the 64 bytes, only 56 can be used to +supply key data. + +The @code{setkey} function is declared in @file{stdlib.h}. +@end deftypefun + +@deftypefun void encrypt (char *@var{block}, int @var{edflag}) +@standards{SVID, unistd.h} +@standards{GNU, crypt.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:crypt}}@asunsafe{@asucorrupt{} @asulock{}}@acunsafe{@aculock{}}} +@c Same issues as setkey. + +The @code{encrypt} function encrypts @var{block} if @var{edflag} is 0, +otherwise it decrypts @var{block}, using a key previously set by +@code{setkey}. The result overwrites the previous value of +@var{block}. + +Like @code{setkey}, @var{block} is as an array of 64 @code{char}s, +each of which stores one bit of the block to be encrypted. Unlike +@code{setkey}, there are no parity bits. All 64 of the bits are +treated as data. + +The @code{encrypt} function is declared in @file{unistd.h}. +@end deftypefun + + +@deftypefun void setkey_r (const char *@var{key}, {struct crypt_data *} @var{data}) +@deftypefunx void encrypt_r (char *@var{block}, int @var{edflag}, {struct crypt_data *} @var{data}) +@standards{GNU, crypt.h} +@c setkey_r: @safety{@prelim{}@mtsafe{}@asunsafe{@asucorrupt{} @asulock{}}@acunsafe{@aculock{}}} +@safety{@prelim{}@mtsafe{}@asunsafe{@asucorrupt{} @asulock{}}@acunsafe{@aculock{}}} + +These are reentrant versions of @code{setkey} and @code{encrypt}. The +only difference is the extra parameter, which stores the expanded +version of @var{key}. Before calling @code{setkey_r} the first time, +@code{data->initialized} must be cleared to zero. + +Both of these functions are declared in @file{crypt.h}. +@end deftypefun + +@deftypefun int ecb_crypt (char *@var{key}, char *@var{blocks}, unsigned int @var{len}, unsigned int @var{mode}) +@standards{SUNRPC, rpc/des_crypt.h} +@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} + +The function @code{ecb_crypt} encrypts or decrypts one or more blocks +using DES. Each block is encrypted independently, which means that if +any two input blocks are the same, then their encryptions will also be +the same. This is an additional weakness in the encryption, on top of +the weakness of DES itself. + +The @var{blocks} and the @var{key} are stored packed in 8-bit bytes, so +that the first bit of the key is the most-significant bit of +@code{key[0]} and the 63rd bit of the key is stored as the +least-significant bit of @code{key[7]}. The least-significant bit of +each byte must be chosen to give each byte odd parity, as with +@code{setkey}. + +@var{len} is the number of bytes in @var{blocks}. It should be a +multiple of 8 (so that there are a whole number of blocks to encrypt). +@var{len} is limited to a maximum of @code{DES_MAXDATA} bytes. + +The result of the encryption replaces the input in @var{blocks}. + +The @var{mode} parameter is the bitwise OR of two of the following: + +@vtable @code +@item DES_ENCRYPT +@standards{SUNRPC, rpc/des_crypt.h} +This constant, used in the @var{mode} parameter, specifies that +@var{blocks} is to be encrypted. + +@item DES_DECRYPT +@standards{SUNRPC, rpc/des_crypt.h} +This constant, used in the @var{mode} parameter, specifies that +@var{blocks} is to be decrypted. + +@item DES_HW +@standards{SUNRPC, rpc/des_crypt.h} +This constant, used in the @var{mode} parameter, asks to use a hardware +device. If no hardware device is available, encryption happens anyway, +but in software. + +@item DES_SW +@standards{SUNRPC, rpc/des_crypt.h} +This constant, used in the @var{mode} parameter, specifies that no +hardware device is to be used. +@end vtable + +The result of the function will be one of these values: + +@vtable @code +@item DESERR_NONE +@standards{SUNRPC, rpc/des_crypt.h} +The encryption succeeded. + +@item DESERR_NOHWDEVICE +@standards{SUNRPC, rpc/des_crypt.h} +The encryption succeeded, but there was no hardware device available. + +@item DESERR_HWERROR +@standards{SUNRPC, rpc/des_crypt.h} +The encryption failed because of a hardware problem. + +@item DESERR_BADPARAM +@standards{SUNRPC, rpc/des_crypt.h} +The encryption failed because of a bad parameter, for instance @var{len} +is not a multiple of 8 or @var{len} is larger than @code{DES_MAXDATA}. +@end vtable +@end deftypefun + +@deftypefun int cbc_crypt (char *@var{key}, char *@var{blocks}, unsigned int @var{len}, unsigned int @var{mode}, char *@var{ivec}) +@standards{SUNRPC, rpc/des_crypt.h} +@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} + +The function @code{cbc_crypt} encrypts or decrypts one or more blocks +using DES in Cipher Block Chaining mode. + +For encryption in CBC mode, each block is exclusive-ored with @var{ivec} +before being encrypted, then @var{ivec} is replaced with the result of +the encryption, then the next block is processed. Decryption is the +reverse of this process. + +This has the advantage that blocks which are the same before being +encrypted are very unlikely to be the same after being encrypted, making +it much harder to detect patterns in the data. + +Usually, @var{ivec} is set to 8 random bytes before encryption starts. +Then the 8 random bytes are transmitted along with the encrypted data +(without themselves being encrypted), and passed back in as @var{ivec} +for decryption. Another possibility is to set @var{ivec} to 8 zeroes +initially, and have the first block encrypted consist of 8 random +bytes. + +Otherwise, all the parameters are similar to those for @code{ecb_crypt}. +@end deftypefun + +@deftypefn Macro int DES_FAILED (int @var{err}) +@standards{SUNRPC, rpc/des_crypt.h} +@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} +This macro returns 1 if @var{err} is a `success' result code from +@code{ecb_crypt} or @code{cbc_crypt}, and 0 otherwise. +@end deftypefn + +@deftypefun void des_setparity (char *@var{key}) +@standards{SUNRPC, rpc/des_crypt.h} +@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} + +The function @code{des_setparity} changes the 64-bit @var{key}, stored +packed in 8-bit bytes, to have odd parity by altering the low bits of +each byte. +@end deftypefun + +The @code{ecb_crypt}, @code{cbc_crypt}, and @code{des_setparity} +functions and their accompanying macros are all defined in the header +@file{rpc/des_crypt.h}. diff --git a/manual/math.texi b/manual/math.texi index d19a14b47d..776db62d1e 100644 --- a/manual/math.texi +++ b/manual/math.texi @@ -28,7 +28,7 @@ @end ifclear @node Mathematics, Arithmetic, Syslog, Top -@c %MENU% Math functions, useful constants, random numbers +@c %MENU% Math functions, useful constants @chapter Mathematics This chapter contains information about functions for performing @@ -81,8 +81,6 @@ aarch64, alpha, mips64, riscv, s390 and sparc. * Hyperbolic Functions:: sinh, cosh, tanh, etc. * Special Functions:: Bessel, gamma, erf. * Errors in Math Functions:: Known Maximum Errors in Math Functions. -* Pseudo-Random Numbers:: Functions for generating pseudo-random - numbers. * FP Function Optimizations:: Fast code or small code. @end menu @@ -1401,588 +1399,6 @@ Functions not listed do not have known errors. @c This multitable does not fit on a single page @include libm-err.texi -@node Pseudo-Random Numbers -@section Pseudo-Random Numbers -@cindex random numbers -@cindex pseudo-random numbers -@cindex seed (for random numbers) - -This section describes the GNU facilities for generating a series of -pseudo-random numbers. The numbers generated are not truly random; -typically, they form a sequence that repeats periodically, with a period -so large that you can ignore it for ordinary purposes. The random -number generator works by remembering a @dfn{seed} value which it uses -to compute the next random number and also to compute a new seed. - -Although the generated numbers look unpredictable within one run of a -program, the sequence of numbers is @emph{exactly the same} from one run -to the next. This is because the initial seed is always the same. This -is convenient when you are debugging a program, but it is unhelpful if -you want the program to behave unpredictably. If you want a different -pseudo-random series each time your program runs, you must specify a -different seed each time. For ordinary purposes, basing the seed on the -current time works well. For random numbers in cryptography, -@pxref{Unpredictable Bytes}. - -You can obtain repeatable sequences of numbers on a particular machine type -by specifying the same initial seed value for the random number -generator. There is no standard meaning for a particular seed value; -the same seed, used in different C libraries or on different CPU types, -will give you different random numbers. - -@Theglibc{} supports the standard @w{ISO C} random number functions -plus two other sets derived from BSD and SVID. The BSD and @w{ISO C} -functions provide identical, somewhat limited functionality. If only a -small number of random bits are required, we recommend you use the -@w{ISO C} interface, @code{rand} and @code{srand}. The SVID functions -provide a more flexible interface, which allows better random number -generator algorithms, provides more random bits (up to 48) per call, and -can provide random floating-point numbers. These functions are required -by the XPG standard and therefore will be present in all modern Unix -systems. - -@menu -* ISO Random:: @code{rand} and friends. -* BSD Random:: @code{random} and friends. -* SVID Random:: @code{drand48} and friends. -@end menu - -@node ISO Random -@subsection ISO C Random Number Functions - -This section describes the random number functions that are part of -the @w{ISO C} standard. - -To use these facilities, you should include the header file -@file{stdlib.h} in your program. -@pindex stdlib.h - -@deftypevr Macro int RAND_MAX -@standards{ISO, stdlib.h} -The value of this macro is an integer constant representing the largest -value the @code{rand} function can return. In @theglibc{}, it is -@code{2147483647}, which is the largest signed integer representable in -32 bits. In other libraries, it may be as low as @code{32767}. -@end deftypevr - -@deftypefun int rand (void) -@standards{ISO, stdlib.h} -@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} -@c Just calls random. -The @code{rand} function returns the next pseudo-random number in the -series. The value ranges from @code{0} to @code{RAND_MAX}. -@end deftypefun - -@deftypefun void srand (unsigned int @var{seed}) -@standards{ISO, stdlib.h} -@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} -@c Alias to srandom. -This function establishes @var{seed} as the seed for a new series of -pseudo-random numbers. If you call @code{rand} before a seed has been -established with @code{srand}, it uses the value @code{1} as a default -seed. - -To produce a different pseudo-random series each time your program is -run, do @code{srand (time (0))}. -@end deftypefun - -POSIX.1 extended the C standard functions to support reproducible random -numbers in multi-threaded programs. However, the extension is badly -designed and unsuitable for serious work. - -@deftypefun int rand_r (unsigned int *@var{seed}) -@standards{POSIX.1, stdlib.h} -@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} -This function returns a random number in the range 0 to @code{RAND_MAX} -just as @code{rand} does. However, all its state is stored in the -@var{seed} argument. This means the RNG's state can only have as many -bits as the type @code{unsigned int} has. This is far too few to -provide a good RNG. - -If your program requires a reentrant RNG, we recommend you use the -reentrant GNU extensions to the SVID random number generator. The -POSIX.1 interface should only be used when the GNU extensions are not -available. -@end deftypefun - - -@node BSD Random -@subsection BSD Random Number Functions - -This section describes a set of random number generation functions that -are derived from BSD. There is no advantage to using these functions -with @theglibc{}; we support them for BSD compatibility only. - -The prototypes for these functions are in @file{stdlib.h}. -@pindex stdlib.h - -@deftypefun {long int} random (void) -@standards{BSD, stdlib.h} -@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} -@c Takes a lock and calls random_r with an automatic variable and the -@c global state, while holding a lock. -This function returns the next pseudo-random number in the sequence. -The value returned ranges from @code{0} to @code{2147483647}. - -@strong{NB:} Temporarily this function was defined to return a -@code{int32_t} value to indicate that the return value always contains -32 bits even if @code{long int} is wider. The standard demands it -differently. Users must always be aware of the 32-bit limitation, -though. -@end deftypefun - -@deftypefun void srandom (unsigned int @var{seed}) -@standards{BSD, stdlib.h} -@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} -@c Takes a lock and calls srandom_r with an automatic variable and a -@c static buffer. There's no MT-safety issue because the static buffer -@c is internally protected by a lock, although other threads may modify -@c the set state before it is used. -The @code{srandom} function sets the state of the random number -generator based on the integer @var{seed}. If you supply a @var{seed} value -of @code{1}, this will cause @code{random} to reproduce the default set -of random numbers. - -To produce a different set of pseudo-random numbers each time your -program runs, do @code{srandom (time (0))}. -@end deftypefun - -@deftypefun {char *} initstate (unsigned int @var{seed}, char *@var{state}, size_t @var{size}) -@standards{BSD, stdlib.h} -@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} -The @code{initstate} function is used to initialize the random number -generator state. The argument @var{state} is an array of @var{size} -bytes, used to hold the state information. It is initialized based on -@var{seed}. The size must be between 8 and 256 bytes, and should be a -power of two. The bigger the @var{state} array, the better. - -The return value is the previous value of the state information array. -You can use this value later as an argument to @code{setstate} to -restore that state. -@end deftypefun - -@deftypefun {char *} setstate (char *@var{state}) -@standards{BSD, stdlib.h} -@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} -The @code{setstate} function restores the random number state -information @var{state}. The argument must have been the result of -a previous call to @var{initstate} or @var{setstate}. - -The return value is the previous value of the state information array. -You can use this value later as an argument to @code{setstate} to -restore that state. - -If the function fails the return value is @code{NULL}. -@end deftypefun - -The four functions described so far in this section all work on a state -which is shared by all threads. The state is not directly accessible to -the user and can only be modified by these functions. This makes it -hard to deal with situations where each thread should have its own -pseudo-random number generator. - -@Theglibc{} contains four additional functions which contain the -state as an explicit parameter and therefore make it possible to handle -thread-local PRNGs. Besides this there is no difference. In fact, the -four functions already discussed are implemented internally using the -following interfaces. - -The @file{stdlib.h} header contains a definition of the following type: - -@deftp {Data Type} {struct random_data} -@standards{GNU, stdlib.h} - -Objects of type @code{struct random_data} contain the information -necessary to represent the state of the PRNG. Although a complete -definition of the type is present the type should be treated as opaque. -@end deftp - -The functions modifying the state follow exactly the already described -functions. - -@deftypefun int random_r (struct random_data *restrict @var{buf}, int32_t *restrict @var{result}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buf}}@assafe{}@acunsafe{@acucorrupt{}}} -The @code{random_r} function behaves exactly like the @code{random} -function except that it uses and modifies the state in the object -pointed to by the first parameter instead of the global state. -@end deftypefun - -@deftypefun int srandom_r (unsigned int @var{seed}, struct random_data *@var{buf}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buf}}@assafe{}@acunsafe{@acucorrupt{}}} -The @code{srandom_r} function behaves exactly like the @code{srandom} -function except that it uses and modifies the state in the object -pointed to by the second parameter instead of the global state. -@end deftypefun - -@deftypefun int initstate_r (unsigned int @var{seed}, char *restrict @var{statebuf}, size_t @var{statelen}, struct random_data *restrict @var{buf}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buf}}@assafe{}@acunsafe{@acucorrupt{}}} -The @code{initstate_r} function behaves exactly like the @code{initstate} -function except that it uses and modifies the state in the object -pointed to by the fourth parameter instead of the global state. -@end deftypefun - -@deftypefun int setstate_r (char *restrict @var{statebuf}, struct random_data *restrict @var{buf}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buf}}@assafe{}@acunsafe{@acucorrupt{}}} -The @code{setstate_r} function behaves exactly like the @code{setstate} -function except that it uses and modifies the state in the object -pointed to by the first parameter instead of the global state. -@end deftypefun - -@node SVID Random -@subsection SVID Random Number Function - -The C library on SVID systems contains yet another kind of random number -generator functions. They use a state of 48 bits of data. The user can -choose among a collection of functions which return the random bits -in different forms. - -Generally there are two kinds of function. The first uses a state of -the random number generator which is shared among several functions and -by all threads of the process. The second requires the user to handle -the state. - -All functions have in common that they use the same congruential -formula with the same constants. The formula is - -@smallexample -Y = (a * X + c) mod m -@end smallexample - -@noindent -where @var{X} is the state of the generator at the beginning and -@var{Y} the state at the end. @code{a} and @code{c} are constants -determining the way the generator works. By default they are - -@smallexample -a = 0x5DEECE66D = 25214903917 -c = 0xb = 11 -@end smallexample - -@noindent -but they can also be changed by the user. @code{m} is of course 2^48 -since the state consists of a 48-bit array. - -The prototypes for these functions are in @file{stdlib.h}. -@pindex stdlib.h - - -@deftypefun double drand48 (void) -@standards{SVID, stdlib.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} -@c Uses of the static state buffer are not guarded by a lock (thus -@c @mtasurace:drand48), so they may be found or left at a -@c partially-updated state in case of calls from within signal handlers -@c or cancellation. None of this will break safety rules or invoke -@c undefined behavior, but it may affect randomness. -This function returns a @code{double} value in the range of @code{0.0} -to @code{1.0} (exclusive). The random bits are determined by the global -state of the random number generator in the C library. - -Since the @code{double} type according to @w{IEEE 754} has a 52-bit -mantissa this means 4 bits are not initialized by the random number -generator. These are (of course) chosen to be the least significant -bits and they are initialized to @code{0}. -@end deftypefun - -@deftypefun double erand48 (unsigned short int @var{xsubi}[3]) -@standards{SVID, stdlib.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} -@c The static buffer is just initialized with default parameters, which -@c are later read to advance the state held in xsubi. -This function returns a @code{double} value in the range of @code{0.0} -to @code{1.0} (exclusive), similarly to @code{drand48}. The argument is -an array describing the state of the random number generator. - -This function can be called subsequently since it updates the array to -guarantee random numbers. The array should have been initialized before -initial use to obtain reproducible results. -@end deftypefun - -@deftypefun {long int} lrand48 (void) -@standards{SVID, stdlib.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} -The @code{lrand48} function returns an integer value in the range of -@code{0} to @code{2^31} (exclusive). Even if the size of the @code{long -int} type can take more than 32 bits, no higher numbers are returned. -The random bits are determined by the global state of the random number -generator in the C library. -@end deftypefun - -@deftypefun {long int} nrand48 (unsigned short int @var{xsubi}[3]) -@standards{SVID, stdlib.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} -This function is similar to the @code{lrand48} function in that it -returns a number in the range of @code{0} to @code{2^31} (exclusive) but -the state of the random number generator used to produce the random bits -is determined by the array provided as the parameter to the function. - -The numbers in the array are updated afterwards so that subsequent calls -to this function yield different results (as is expected of a random -number generator). The array should have been initialized before the -first call to obtain reproducible results. -@end deftypefun - -@deftypefun {long int} mrand48 (void) -@standards{SVID, stdlib.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} -The @code{mrand48} function is similar to @code{lrand48}. The only -difference is that the numbers returned are in the range @code{-2^31} to -@code{2^31} (exclusive). -@end deftypefun - -@deftypefun {long int} jrand48 (unsigned short int @var{xsubi}[3]) -@standards{SVID, stdlib.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} -The @code{jrand48} function is similar to @code{nrand48}. The only -difference is that the numbers returned are in the range @code{-2^31} to -@code{2^31} (exclusive). For the @code{xsubi} parameter the same -requirements are necessary. -@end deftypefun - -The internal state of the random number generator can be initialized in -several ways. The methods differ in the completeness of the -information provided. - -@deftypefun void srand48 (long int @var{seedval}) -@standards{SVID, stdlib.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} -The @code{srand48} function sets the most significant 32 bits of the -internal state of the random number generator to the least -significant 32 bits of the @var{seedval} parameter. The lower 16 bits -are initialized to the value @code{0x330E}. Even if the @code{long -int} type contains more than 32 bits only the lower 32 bits are used. - -Owing to this limitation, initialization of the state of this -function is not very useful. But it makes it easy to use a construct -like @code{srand48 (time (0))}. - -A side-effect of this function is that the values @code{a} and @code{c} -from the internal state, which are used in the congruential formula, -are reset to the default values given above. This is of importance once -the user has called the @code{lcong48} function (see below). -@end deftypefun - -@deftypefun {unsigned short int *} seed48 (unsigned short int @var{seed16v}[3]) -@standards{SVID, stdlib.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} -The @code{seed48} function initializes all 48 bits of the state of the -internal random number generator from the contents of the parameter -@var{seed16v}. Here the lower 16 bits of the first element of -@var{seed16v} initialize the least significant 16 bits of the internal -state, the lower 16 bits of @code{@var{seed16v}[1]} initialize the mid-order -16 bits of the state and the 16 lower bits of @code{@var{seed16v}[2]} -initialize the most significant 16 bits of the state. - -Unlike @code{srand48} this function lets the user initialize all 48 bits -of the state. - -The value returned by @code{seed48} is a pointer to an array containing -the values of the internal state before the change. This might be -useful to restart the random number generator at a certain state. -Otherwise the value can simply be ignored. - -As for @code{srand48}, the values @code{a} and @code{c} from the -congruential formula are reset to the default values. -@end deftypefun - -There is one more function to initialize the random number generator -which enables you to specify even more information by allowing you to -change the parameters in the congruential formula. - -@deftypefun void lcong48 (unsigned short int @var{param}[7]) -@standards{SVID, stdlib.h} -@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} -The @code{lcong48} function allows the user to change the complete state -of the random number generator. Unlike @code{srand48} and -@code{seed48}, this function also changes the constants in the -congruential formula. - -From the seven elements in the array @var{param} the least significant -16 bits of the entries @code{@var{param}[0]} to @code{@var{param}[2]} -determine the initial state, the least significant 16 bits of -@code{@var{param}[3]} to @code{@var{param}[5]} determine the 48 bit -constant @code{a} and @code{@var{param}[6]} determines the 16-bit value -@code{c}. -@end deftypefun - -All the above functions have in common that they use the global -parameters for the congruential formula. In multi-threaded programs it -might sometimes be useful to have different parameters in different -threads. For this reason all the above functions have a counterpart -which works on a description of the random number generator in the -user-supplied buffer instead of the global state. - -Please note that it is no problem if several threads use the global -state if all threads use the functions which take a pointer to an array -containing the state. The random numbers are computed following the -same loop but if the state in the array is different all threads will -obtain an individual random number generator. - -The user-supplied buffer must be of type @code{struct drand48_data}. -This type should be regarded as opaque and not manipulated directly. - -@deftypefun int drand48_r (struct drand48_data *@var{buffer}, double *@var{result}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} -This function is equivalent to the @code{drand48} function with the -difference that it does not modify the global random number generator -parameters but instead the parameters in the buffer supplied through the -pointer @var{buffer}. The random number is returned in the variable -pointed to by @var{result}. - -The return value of the function indicates whether the call succeeded. -If the value is less than @code{0} an error occurred and @var{errno} is -set to indicate the problem. - -This function is a GNU extension and should not be used in portable -programs. -@end deftypefun - -@deftypefun int erand48_r (unsigned short int @var{xsubi}[3], struct drand48_data *@var{buffer}, double *@var{result}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} -The @code{erand48_r} function works like @code{erand48}, but in addition -it takes an argument @var{buffer} which describes the random number -generator. The state of the random number generator is taken from the -@code{xsubi} array, the parameters for the congruential formula from the -global random number generator data. The random number is returned in -the variable pointed to by @var{result}. - -The return value is non-negative if the call succeeded. - -This function is a GNU extension and should not be used in portable -programs. -@end deftypefun - -@deftypefun int lrand48_r (struct drand48_data *@var{buffer}, long int *@var{result}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} -This function is similar to @code{lrand48}, but in addition it takes a -pointer to a buffer describing the state of the random number generator -just like @code{drand48}. - -If the return value of the function is non-negative the variable pointed -to by @var{result} contains the result. Otherwise an error occurred. - -This function is a GNU extension and should not be used in portable -programs. -@end deftypefun - -@deftypefun int nrand48_r (unsigned short int @var{xsubi}[3], struct drand48_data *@var{buffer}, long int *@var{result}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} -The @code{nrand48_r} function works like @code{nrand48} in that it -produces a random number in the range @code{0} to @code{2^31}. But instead -of using the global parameters for the congruential formula it uses the -information from the buffer pointed to by @var{buffer}. The state is -described by the values in @var{xsubi}. - -If the return value is non-negative the variable pointed to by -@var{result} contains the result. - -This function is a GNU extension and should not be used in portable -programs. -@end deftypefun - -@deftypefun int mrand48_r (struct drand48_data *@var{buffer}, long int *@var{result}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} -This function is similar to @code{mrand48} but like the other reentrant -functions it uses the random number generator described by the value in -the buffer pointed to by @var{buffer}. - -If the return value is non-negative the variable pointed to by -@var{result} contains the result. - -This function is a GNU extension and should not be used in portable -programs. -@end deftypefun - -@deftypefun int jrand48_r (unsigned short int @var{xsubi}[3], struct drand48_data *@var{buffer}, long int *@var{result}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} -The @code{jrand48_r} function is similar to @code{jrand48}. Like the -other reentrant functions of this function family it uses the -congruential formula parameters from the buffer pointed to by -@var{buffer}. - -If the return value is non-negative the variable pointed to by -@var{result} contains the result. - -This function is a GNU extension and should not be used in portable -programs. -@end deftypefun - -Before any of the above functions are used the buffer of type -@code{struct drand48_data} should be initialized. The easiest way to do -this is to fill the whole buffer with null bytes, e.g. by - -@smallexample -memset (buffer, '\0', sizeof (struct drand48_data)); -@end smallexample - -@noindent -Using any of the reentrant functions of this family now will -automatically initialize the random number generator to the default -values for the state and the parameters of the congruential formula. - -The other possibility is to use any of the functions which explicitly -initialize the buffer. Though it might be obvious how to initialize the -buffer from looking at the parameter to the function, it is highly -recommended to use these functions since the result might not always be -what you expect. - -@deftypefun int srand48_r (long int @var{seedval}, struct drand48_data *@var{buffer}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} -The description of the random number generator represented by the -information in @var{buffer} is initialized similarly to what the function -@code{srand48} does. The state is initialized from the parameter -@var{seedval} and the parameters for the congruential formula are -initialized to their default values. - -If the return value is non-negative the function call succeeded. - -This function is a GNU extension and should not be used in portable -programs. -@end deftypefun - -@deftypefun int seed48_r (unsigned short int @var{seed16v}[3], struct drand48_data *@var{buffer}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} -This function is similar to @code{srand48_r} but like @code{seed48} it -initializes all 48 bits of the state from the parameter @var{seed16v}. - -If the return value is non-negative the function call succeeded. It -does not return a pointer to the previous state of the random number -generator like the @code{seed48} function does. If the user wants to -preserve the state for a later re-run s/he can copy the whole buffer -pointed to by @var{buffer}. - -This function is a GNU extension and should not be used in portable -programs. -@end deftypefun - -@deftypefun int lcong48_r (unsigned short int @var{param}[7], struct drand48_data *@var{buffer}) -@standards{GNU, stdlib.h} -@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} -This function initializes all aspects of the random number generator -described in @var{buffer} with the data in @var{param}. Here it is -especially true that the function does more than just copying the -contents of @var{param} and @var{buffer}. More work is required and -therefore it is important to use this function rather than initializing -the random number generator directly. - -If the return value is non-negative the function call succeeded. - -This function is a GNU extension and should not be used in portable -programs. -@end deftypefun - @node FP Function Optimizations @section Is Fast Code or Small Code preferred? @cindex Optimization diff --git a/manual/random.texi b/manual/random.texi new file mode 100644 index 0000000000..f14b9e6e82 --- /dev/null +++ b/manual/random.texi @@ -0,0 +1,753 @@ +@node Random Number Generation, Date and Time, Arithmetic, Top +@chapter Random Number Generation +@c %MENU% Various ways to generate random values. + +Many algorithms require a source of @dfn{random numbers}, or to be +more precise, sequences of numbers chosen uniformly at random from +some subset of the integers or reals. There are several different +ways to generate random numbers, depending on how stringent your +requirements are. + +A @dfn{pseudo-random generator} (PRNG) produces a sequence of numbers +that @emph{appears} to be random, and has statistical properties +matching what we expect of numbers chosen uniformly at random. +However, an ordinary PRNG doesn't guarantee that its output is +unguessable. Also, the output of a PRNG depends on a relatively small +@dfn{seed} value, and so there are only a small number of sequences +that it can produce; astronomically small, relative to the total +number of random sequences. If the seed is reused, the output will +be exactly the same, which is sometimes exactly what you want, and +sometimes disastrous. + +A @dfn{cryptographically strong pseudo-random generator} (CSPRNG) is a +PRNG that @emph{does} guarantee its output is unguessable. Formally, +there is no deterministic, polynomial-time algorithm@footnote{Assuming +@iftex +@c Don't typeset NP as if multiplying N by P. Use text italic for both. +@math{\hbox{\it P} \neq \hbox{\it NP}}@c +@end iftex +@ifnottex +@math{P ≠ NP}@c +@end ifnottex +.} that can tell the difference between the output of +a CSPRNG and a sequence of numbers that really were chosen uniformly +at random. A CSPRNG still uses a seed and can only produce an +astronomically small number of random sequences. + +Finally, a @dfn{true random generator} (TRNG) produces random numbers +not from a seed, but from some unpredictable physical process. In +principle, a TRNG's output is unguessable, and is not limited to an +astronomically small number of sequences. However, TRNGs are very +slow, and because there is no seed, there is no way to make one repeat +its output. Usually, it is best to use a TRNG only to choose the seed +for a PRNG or CSPRNG. + +At present, @theglibc{} offers a variety of ordinary PRNGs, and on +some operating systems it also offers access to an OS-provided TRNG. +We may add a CSPRNG in the future. + +@menu +* Pseudo-Random Numbers:: Sequences of numbers with apparently + random distribution, but not difficult + to predict. +* Unpredictable Bytes:: Asking the operating system for truly + unpredictable bytes. +@end menu + +@node Pseudo-Random Numbers +@section Pseudo-Random Numbers +@cindex random numbers +@cindex pseudo-random numbers +@cindex seed (for random numbers) + +This section describes the GNU facilities for generating a series of +pseudo-random numbers. The numbers generated are not truly random; +typically, they form a sequence that repeats periodically, with a period +so large that you can ignore it for ordinary purposes. The random +number generator works by remembering a @dfn{seed} value which it uses +to compute the next random number and also to compute a new seed. + +Although the generated numbers look unpredictable within one run of a +program, the sequence of numbers is @emph{exactly the same} from one run +to the next. This is because the initial seed is always the same. This +is convenient when you are debugging a program, but it is unhelpful if +you want the program to behave unpredictably. If you want a different +pseudo-random series each time your program runs, you must specify a +different seed each time. For ordinary purposes, basing the seed on the +current time works well. + +You can obtain repeatable sequences of numbers on a particular machine type +by specifying the same initial seed value for the random number +generator. There is no standard meaning for a particular seed value; +the same seed, used in different C libraries or on different CPU types, +will give you different random numbers. + +@Theglibc{} supports the standard @w{ISO C} random number functions +plus two other sets derived from BSD and SVID. The BSD and @w{ISO C} +functions provide identical, somewhat limited functionality. If only a +small number of random bits are required, we recommend you use the +@w{ISO C} interface, @code{rand} and @code{srand}. The SVID functions +provide a more flexible interface, which allows better random number +generator algorithms, provides more random bits (up to 48) per call, and +can provide random floating-point numbers. These functions are required +by the XPG standard and therefore will be present in all modern Unix +systems. + +@menu +* ISO Random:: @code{rand} and friends. +* BSD Random:: @code{random} and friends. +* SVID Random:: @code{drand48} and friends. +@end menu + +@node ISO Random +@subsection ISO C Random Number Functions + +This section describes the random number functions that are part of +the @w{ISO C} standard. + +To use these facilities, you should include the header file +@file{stdlib.h} in your program. +@pindex stdlib.h + +@deftypevr Macro int RAND_MAX +@standards{ISO, stdlib.h} +The value of this macro is an integer constant representing the largest +value the @code{rand} function can return. In @theglibc{}, it is +@code{2147483647}, which is the largest signed integer representable in +32 bits. In other libraries, it may be as low as @code{32767}. +@end deftypevr + +@deftypefun int rand (void) +@standards{ISO, stdlib.h} +@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} +@c Just calls random. +The @code{rand} function returns the next pseudo-random number in the +series. The value ranges from @code{0} to @code{RAND_MAX}. +@end deftypefun + +@deftypefun void srand (unsigned int @var{seed}) +@standards{ISO, stdlib.h} +@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} +@c Alias to srandom. +This function establishes @var{seed} as the seed for a new series of +pseudo-random numbers. If you call @code{rand} before a seed has been +established with @code{srand}, it uses the value @code{1} as a default +seed. + +To produce a different pseudo-random series each time your program is +run, do @code{srand (time (0))}. +@end deftypefun + +POSIX.1 extended the C standard functions to support reproducible random +numbers in multi-threaded programs. However, the extension is badly +designed and unsuitable for serious work. + +@deftypefun int rand_r (unsigned int *@var{seed}) +@standards{POSIX.1, stdlib.h} +@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} +This function returns a random number in the range 0 to @code{RAND_MAX} +just as @code{rand} does. However, all its state is stored in the +@var{seed} argument. This means the RNG's state can only have as many +bits as the type @code{unsigned int} has. This is far too few to +provide a good RNG. + +If your program requires a reentrant RNG, we recommend you use the +reentrant GNU extensions to the SVID random number generator. The +POSIX.1 interface should only be used when the GNU extensions are not +available. +@end deftypefun + + +@node BSD Random +@subsection BSD Random Number Functions + +This section describes a set of random number generation functions that +are derived from BSD. There is no advantage to using these functions +with @theglibc{}; we support them for BSD compatibility only. + +The prototypes for these functions are in @file{stdlib.h}. +@pindex stdlib.h + +@deftypefun {long int} random (void) +@standards{BSD, stdlib.h} +@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} +@c Takes a lock and calls random_r with an automatic variable and the +@c global state, while holding a lock. +This function returns the next pseudo-random number in the sequence. +The value returned ranges from @code{0} to @code{2147483647}. + +@strong{NB:} Temporarily this function was defined to return a +@code{int32_t} value to indicate that the return value always contains +32 bits even if @code{long int} is wider. The standard demands it +differently. Users must always be aware of the 32-bit limitation, +though. +@end deftypefun + +@deftypefun void srandom (unsigned int @var{seed}) +@standards{BSD, stdlib.h} +@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} +@c Takes a lock and calls srandom_r with an automatic variable and a +@c static buffer. There's no MT-safety issue because the static buffer +@c is internally protected by a lock, although other threads may modify +@c the set state before it is used. +The @code{srandom} function sets the state of the random number +generator based on the integer @var{seed}. If you supply a @var{seed} value +of @code{1}, this will cause @code{random} to reproduce the default set +of random numbers. + +To produce a different set of pseudo-random numbers each time your +program runs, do @code{srandom (time (0))}. +@end deftypefun + +@deftypefun {char *} initstate (unsigned int @var{seed}, char *@var{state}, size_t @var{size}) +@standards{BSD, stdlib.h} +@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} +The @code{initstate} function is used to initialize the random number +generator state. The argument @var{state} is an array of @var{size} +bytes, used to hold the state information. It is initialized based on +@var{seed}. The size must be between 8 and 256 bytes, and should be a +power of two. The bigger the @var{state} array, the better. + +The return value is the previous value of the state information array. +You can use this value later as an argument to @code{setstate} to +restore that state. +@end deftypefun + +@deftypefun {char *} setstate (char *@var{state}) +@standards{BSD, stdlib.h} +@safety{@prelim{}@mtsafe{}@asunsafe{@asulock{}}@acunsafe{@aculock{}}} +The @code{setstate} function restores the random number state +information @var{state}. The argument must have been the result of +a previous call to @var{initstate} or @var{setstate}. + +The return value is the previous value of the state information array. +You can use this value later as an argument to @code{setstate} to +restore that state. + +If the function fails the return value is @code{NULL}. +@end deftypefun + +The four functions described so far in this section all work on a state +which is shared by all threads. The state is not directly accessible to +the user and can only be modified by these functions. This makes it +hard to deal with situations where each thread should have its own +pseudo-random number generator. + +@Theglibc{} contains four additional functions which contain the +state as an explicit parameter and therefore make it possible to handle +thread-local PRNGs. Besides this there is no difference. In fact, the +four functions already discussed are implemented internally using the +following interfaces. + +The @file{stdlib.h} header contains a definition of the following type: + +@deftp {Data Type} {struct random_data} +@standards{GNU, stdlib.h} + +Objects of type @code{struct random_data} contain the information +necessary to represent the state of the PRNG. Although a complete +definition of the type is present the type should be treated as opaque. +@end deftp + +The functions modifying the state follow exactly the already described +functions. + +@deftypefun int random_r (struct random_data *restrict @var{buf}, int32_t *restrict @var{result}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buf}}@assafe{}@acunsafe{@acucorrupt{}}} +The @code{random_r} function behaves exactly like the @code{random} +function except that it uses and modifies the state in the object +pointed to by the first parameter instead of the global state. +@end deftypefun + +@deftypefun int srandom_r (unsigned int @var{seed}, struct random_data *@var{buf}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buf}}@assafe{}@acunsafe{@acucorrupt{}}} +The @code{srandom_r} function behaves exactly like the @code{srandom} +function except that it uses and modifies the state in the object +pointed to by the second parameter instead of the global state. +@end deftypefun + +@deftypefun int initstate_r (unsigned int @var{seed}, char *restrict @var{statebuf}, size_t @var{statelen}, struct random_data *restrict @var{buf}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buf}}@assafe{}@acunsafe{@acucorrupt{}}} +The @code{initstate_r} function behaves exactly like the @code{initstate} +function except that it uses and modifies the state in the object +pointed to by the fourth parameter instead of the global state. +@end deftypefun + +@deftypefun int setstate_r (char *restrict @var{statebuf}, struct random_data *restrict @var{buf}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buf}}@assafe{}@acunsafe{@acucorrupt{}}} +The @code{setstate_r} function behaves exactly like the @code{setstate} +function except that it uses and modifies the state in the object +pointed to by the first parameter instead of the global state. +@end deftypefun + +@node SVID Random +@subsection SVID Random Number Function + +The C library on SVID systems contains yet another kind of random number +generator functions. They use a state of 48 bits of data. The user can +choose among a collection of functions which return the random bits +in different forms. + +Generally there are two kinds of function. The first uses a state of +the random number generator which is shared among several functions and +by all threads of the process. The second requires the user to handle +the state. + +All functions have in common that they use the same congruential +formula with the same constants. The formula is + +@smallexample +Y = (a * X + c) mod m +@end smallexample + +@noindent +where @var{X} is the state of the generator at the beginning and +@var{Y} the state at the end. @code{a} and @code{c} are constants +determining the way the generator works. By default they are + +@smallexample +a = 0x5DEECE66D = 25214903917 +c = 0xb = 11 +@end smallexample + +@noindent +but they can also be changed by the user. @code{m} is of course 2^48 +since the state consists of a 48-bit array. + +The prototypes for these functions are in @file{stdlib.h}. +@pindex stdlib.h + + +@deftypefun double drand48 (void) +@standards{SVID, stdlib.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} +@c Uses of the static state buffer are not guarded by a lock (thus +@c @mtasurace:drand48), so they may be found or left at a +@c partially-updated state in case of calls from within signal handlers +@c or cancellation. None of this will break safety rules or invoke +@c undefined behavior, but it may affect randomness. +This function returns a @code{double} value in the range of @code{0.0} +to @code{1.0} (exclusive). The random bits are determined by the global +state of the random number generator in the C library. + +Since the @code{double} type according to @w{IEEE 754} has a 52-bit +mantissa this means 4 bits are not initialized by the random number +generator. These are (of course) chosen to be the least significant +bits and they are initialized to @code{0}. +@end deftypefun + +@deftypefun double erand48 (unsigned short int @var{xsubi}[3]) +@standards{SVID, stdlib.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} +@c The static buffer is just initialized with default parameters, which +@c are later read to advance the state held in xsubi. +This function returns a @code{double} value in the range of @code{0.0} +to @code{1.0} (exclusive), similarly to @code{drand48}. The argument is +an array describing the state of the random number generator. + +This function can be called subsequently since it updates the array to +guarantee random numbers. The array should have been initialized before +initial use to obtain reproducible results. +@end deftypefun + +@deftypefun {long int} lrand48 (void) +@standards{SVID, stdlib.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} +The @code{lrand48} function returns an integer value in the range of +@code{0} to @code{2^31} (exclusive). Even if the size of the @code{long +int} type can take more than 32 bits, no higher numbers are returned. +The random bits are determined by the global state of the random number +generator in the C library. +@end deftypefun + +@deftypefun {long int} nrand48 (unsigned short int @var{xsubi}[3]) +@standards{SVID, stdlib.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} +This function is similar to the @code{lrand48} function in that it +returns a number in the range of @code{0} to @code{2^31} (exclusive) but +the state of the random number generator used to produce the random bits +is determined by the array provided as the parameter to the function. + +The numbers in the array are updated afterwards so that subsequent calls +to this function yield different results (as is expected of a random +number generator). The array should have been initialized before the +first call to obtain reproducible results. +@end deftypefun + +@deftypefun {long int} mrand48 (void) +@standards{SVID, stdlib.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} +The @code{mrand48} function is similar to @code{lrand48}. The only +difference is that the numbers returned are in the range @code{-2^31} to +@code{2^31} (exclusive). +@end deftypefun + +@deftypefun {long int} jrand48 (unsigned short int @var{xsubi}[3]) +@standards{SVID, stdlib.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} +The @code{jrand48} function is similar to @code{nrand48}. The only +difference is that the numbers returned are in the range @code{-2^31} to +@code{2^31} (exclusive). For the @code{xsubi} parameter the same +requirements are necessary. +@end deftypefun + +The internal state of the random number generator can be initialized in +several ways. The methods differ in the completeness of the +information provided. + +@deftypefun void srand48 (long int @var{seedval}) +@standards{SVID, stdlib.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} +The @code{srand48} function sets the most significant 32 bits of the +internal state of the random number generator to the least +significant 32 bits of the @var{seedval} parameter. The lower 16 bits +are initialized to the value @code{0x330E}. Even if the @code{long +int} type contains more than 32 bits only the lower 32 bits are used. + +Owing to this limitation, initialization of the state of this +function is not very useful. But it makes it easy to use a construct +like @code{srand48 (time (0))}. + +A side-effect of this function is that the values @code{a} and @code{c} +from the internal state, which are used in the congruential formula, +are reset to the default values given above. This is of importance once +the user has called the @code{lcong48} function (see below). +@end deftypefun + +@deftypefun {unsigned short int *} seed48 (unsigned short int @var{seed16v}[3]) +@standards{SVID, stdlib.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} +The @code{seed48} function initializes all 48 bits of the state of the +internal random number generator from the contents of the parameter +@var{seed16v}. Here the lower 16 bits of the first element of +@var{seed16v} initialize the least significant 16 bits of the internal +state, the lower 16 bits of @code{@var{seed16v}[1]} initialize the mid-order +16 bits of the state and the 16 lower bits of @code{@var{seed16v}[2]} +initialize the most significant 16 bits of the state. + +Unlike @code{srand48} this function lets the user initialize all 48 bits +of the state. + +The value returned by @code{seed48} is a pointer to an array containing +the values of the internal state before the change. This might be +useful to restart the random number generator at a certain state. +Otherwise the value can simply be ignored. + +As for @code{srand48}, the values @code{a} and @code{c} from the +congruential formula are reset to the default values. +@end deftypefun + +There is one more function to initialize the random number generator +which enables you to specify even more information by allowing you to +change the parameters in the congruential formula. + +@deftypefun void lcong48 (unsigned short int @var{param}[7]) +@standards{SVID, stdlib.h} +@safety{@prelim{}@mtunsafe{@mtasurace{:drand48}}@asunsafe{}@acunsafe{@acucorrupt{}}} +The @code{lcong48} function allows the user to change the complete state +of the random number generator. Unlike @code{srand48} and +@code{seed48}, this function also changes the constants in the +congruential formula. + +From the seven elements in the array @var{param} the least significant +16 bits of the entries @code{@var{param}[0]} to @code{@var{param}[2]} +determine the initial state, the least significant 16 bits of +@code{@var{param}[3]} to @code{@var{param}[5]} determine the 48 bit +constant @code{a} and @code{@var{param}[6]} determines the 16-bit value +@code{c}. +@end deftypefun + +All the above functions have in common that they use the global +parameters for the congruential formula. In multi-threaded programs it +might sometimes be useful to have different parameters in different +threads. For this reason all the above functions have a counterpart +which works on a description of the random number generator in the +user-supplied buffer instead of the global state. + +Please note that it is no problem if several threads use the global +state if all threads use the functions which take a pointer to an array +containing the state. The random numbers are computed following the +same loop but if the state in the array is different all threads will +obtain an individual random number generator. + +The user-supplied buffer must be of type @code{struct drand48_data}. +This type should be regarded as opaque and not manipulated directly. + +@deftypefun int drand48_r (struct drand48_data *@var{buffer}, double *@var{result}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} +This function is equivalent to the @code{drand48} function with the +difference that it does not modify the global random number generator +parameters but instead the parameters in the buffer supplied through the +pointer @var{buffer}. The random number is returned in the variable +pointed to by @var{result}. + +The return value of the function indicates whether the call succeeded. +If the value is less than @code{0} an error occurred and @var{errno} is +set to indicate the problem. + +This function is a GNU extension and should not be used in portable +programs. +@end deftypefun + +@deftypefun int erand48_r (unsigned short int @var{xsubi}[3], struct drand48_data *@var{buffer}, double *@var{result}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} +The @code{erand48_r} function works like @code{erand48}, but in addition +it takes an argument @var{buffer} which describes the random number +generator. The state of the random number generator is taken from the +@code{xsubi} array, the parameters for the congruential formula from the +global random number generator data. The random number is returned in +the variable pointed to by @var{result}. + +The return value is non-negative if the call succeeded. + +This function is a GNU extension and should not be used in portable +programs. +@end deftypefun + +@deftypefun int lrand48_r (struct drand48_data *@var{buffer}, long int *@var{result}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} +This function is similar to @code{lrand48}, but in addition it takes a +pointer to a buffer describing the state of the random number generator +just like @code{drand48}. + +If the return value of the function is non-negative the variable pointed +to by @var{result} contains the result. Otherwise an error occurred. + +This function is a GNU extension and should not be used in portable +programs. +@end deftypefun + +@deftypefun int nrand48_r (unsigned short int @var{xsubi}[3], struct drand48_data *@var{buffer}, long int *@var{result}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} +The @code{nrand48_r} function works like @code{nrand48} in that it +produces a random number in the range @code{0} to @code{2^31}. But instead +of using the global parameters for the congruential formula it uses the +information from the buffer pointed to by @var{buffer}. The state is +described by the values in @var{xsubi}. + +If the return value is non-negative the variable pointed to by +@var{result} contains the result. + +This function is a GNU extension and should not be used in portable +programs. +@end deftypefun + +@deftypefun int mrand48_r (struct drand48_data *@var{buffer}, long int *@var{result}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} +This function is similar to @code{mrand48} but like the other reentrant +functions it uses the random number generator described by the value in +the buffer pointed to by @var{buffer}. + +If the return value is non-negative the variable pointed to by +@var{result} contains the result. + +This function is a GNU extension and should not be used in portable +programs. +@end deftypefun + +@deftypefun int jrand48_r (unsigned short int @var{xsubi}[3], struct drand48_data *@var{buffer}, long int *@var{result}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} +The @code{jrand48_r} function is similar to @code{jrand48}. Like the +other reentrant functions of this function family it uses the +congruential formula parameters from the buffer pointed to by +@var{buffer}. + +If the return value is non-negative the variable pointed to by +@var{result} contains the result. + +This function is a GNU extension and should not be used in portable +programs. +@end deftypefun + +Before any of the above functions are used the buffer of type +@code{struct drand48_data} should be initialized. The easiest way to do +this is to fill the whole buffer with null bytes, e.g. by + +@smallexample +memset (buffer, '\0', sizeof (struct drand48_data)); +@end smallexample + +@noindent +Using any of the reentrant functions of this family now will +automatically initialize the random number generator to the default +values for the state and the parameters of the congruential formula. + +The other possibility is to use any of the functions which explicitly +initialize the buffer. Though it might be obvious how to initialize the +buffer from looking at the parameter to the function, it is highly +recommended to use these functions since the result might not always be +what you expect. + +@deftypefun int srand48_r (long int @var{seedval}, struct drand48_data *@var{buffer}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} +The description of the random number generator represented by the +information in @var{buffer} is initialized similarly to what the function +@code{srand48} does. The state is initialized from the parameter +@var{seedval} and the parameters for the congruential formula are +initialized to their default values. + +If the return value is non-negative the function call succeeded. + +This function is a GNU extension and should not be used in portable +programs. +@end deftypefun + +@deftypefun int seed48_r (unsigned short int @var{seed16v}[3], struct drand48_data *@var{buffer}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} +This function is similar to @code{srand48_r} but like @code{seed48} it +initializes all 48 bits of the state from the parameter @var{seed16v}. + +If the return value is non-negative the function call succeeded. It +does not return a pointer to the previous state of the random number +generator like the @code{seed48} function does. If the user wants to +preserve the state for a later re-run s/he can copy the whole buffer +pointed to by @var{buffer}. + +This function is a GNU extension and should not be used in portable +programs. +@end deftypefun + +@deftypefun int lcong48_r (unsigned short int @var{param}[7], struct drand48_data *@var{buffer}) +@standards{GNU, stdlib.h} +@safety{@prelim{}@mtsafe{@mtsrace{:buffer}}@assafe{}@acunsafe{@acucorrupt{}}} +This function initializes all aspects of the random number generator +described in @var{buffer} with the data in @var{param}. Here it is +especially true that the function does more than just copying the +contents of @var{param} and @var{buffer}. More work is required and +therefore it is important to use this function rather than initializing +the random number generator directly. + +If the return value is non-negative the function call succeeded. + +This function is a GNU extension and should not be used in portable +programs. +@end deftypefun + + +@node Unpredictable Bytes +@section Generating Unpredictable Bytes + +Some cryptographic applications need truly unpredictable bytes. +@Theglibc{} provides two functions for this purpose, both of which +access a true random generator implemented by the operating system. +Not all operating systems support these functions; programs that use +them must be prepared for them to fail. They are slow, and can only +produce short sequences of unpredictable bytes. Most programs should +use these functions only to seed a cryptographically strong +pseudo-random generator. + +Most programs should use @code{getentropy}. The @code{getrandom} +function is intended for low-level applications which need additional +control over the blocking behavior. + +@deftypefun int getentropy (void *@var{buffer}, size_t @var{length}) +@standards{GNU, sys/random.h} +@safety{@mtsafe{}@assafe{}@acsafe{}} + +This function writes @var{length} bytes of random data to the array +starting at @var{buffer}, which must be at most 256 bytes long. The +function returns zero on success. On failure, it returns @code{-1} and +@code{errno} is updated accordingly. + +The @code{getentropy} function is declared in the header file +@file{sys/random.h}. It is derived from OpenBSD. + +The @code{getentropy} function is not a cancellation point. A call to +@code{getentropy} can block if the system has just booted and the kernel +entropy pool has not yet been initialized. In this case, the function +will keep blocking even if a signal arrives, and return only after the +entropy pool has been initialized. + +The @code{getentropy} function can fail with several errors, some of +which are listed below. Applications must check for failure. +However, when it succeeds, it will always produce exactly @var{length} +bytes of random data. + +@table @code +@item ENOSYS +The kernel does not implement the required system call. + +@item EFAULT +The combination of @var{buffer} and @var{length} arguments specifies +an invalid memory range. + +@item EIO +More than 256 bytes of randomness have been requested, or the buffer +could not be overwritten with random data for an unspecified reason. + +@end table + +@end deftypefun + +@deftypefun ssize_t getrandom (void *@var{buffer}, size_t @var{length}, unsigned int @var{flags}) +@standards{GNU, sys/random.h} +@safety{@mtsafe{}@assafe{}@acsafe{}} + +This function writes up to @var{length} bytes of random data to the +array starting at @var{buffer}. On success, this function returns the +number of bytes which have been written to the buffer, which can be +less than @var{length}. On error, @code{-1} is returned, and +@code{errno} is updated accordingly. + +The @code{getrandom} function is declared in the header file +@file{sys/random.h}. It is a GNU extension. + +The following flags are defined for the @var{flags} argument: + +@table @code +@item GRND_RANDOM +Use the @file{/dev/random} (blocking) pool instead of the +@file{/dev/urandom} (non-blocking) pool to obtain randomness. If the +@code{GRND_RANDOM} flag is specified, the @code{getrandom} function can +block even after the randomness source has been initialized. + +@item GRND_NONBLOCK +Instead of blocking, return to the caller immediately if no data is +available. +@end table + +The @code{getrandom} function is a cancellation point. + +Obtaining randomness from the @file{/dev/urandom} pool (i.e., a call +without the @code{GRND_RANDOM} flag) can block if the system has just +booted and the pool has not yet been initialized. + +The @code{getrandom} function can fail with several errors, some of +which are listed below. In addition, the function may not fill the +buffer completely. Applications must check for failure and for short +writes. + +@table @code +@item ENOSYS +The kernel does not implement the @code{getrandom} system call. + +@item EAGAIN +No random data was available and @code{GRND_NONBLOCK} was specified in +@var{flags}. + +@item EFAULT +The combination of @var{buffer} and @var{length} arguments specifies +an invalid memory range. + +@item EINTR +The system call was interrupted. During the system boot process, before +the kernel randomness pool is initialized, this can happen even if +@var{flags} is zero. + +@item EINVAL +The @var{flags} argument contains an invalid combination of flags. +@end table + +@end deftypefun diff --git a/manual/string.texi b/manual/string.texi index b07cfb4550..f113777f2d 100644 --- a/manual/string.texi +++ b/manual/string.texi @@ -2469,8 +2469,6 @@ Unlike Rot13, @code{memfrob} works on arbitrary binary data, not just text. @cindex Rot13 -For true encryption, @xref{Cryptographic Functions}. - This function is declared in @file{string.h}. @pindex string.h @@ -2487,9 +2485,7 @@ Note that @code{memfrob} a second time on the same data structure returns it to its original state. This is a good function for hiding information from someone who doesn't -want to see it or doesn't want to see it very much. To really prevent -people from retrieving the information, use stronger encryption such as -that described in @xref{Cryptographic Functions}. +want to see it or doesn't want to see it very much. @strong{Portability Note:} This function is unique to @theglibc{}. diff --git a/manual/time.texi b/manual/time.texi index 4d154452eb..d0821703c0 100644 --- a/manual/time.texi +++ b/manual/time.texi @@ -1,4 +1,4 @@ -@node Date and Time, Resource Usage And Limitation, Arithmetic, Top +@node Date and Time, Resource Usage And Limitation, Random Number Generation, Top @c %MENU% Functions for getting the date and time and formatting them nicely @chapter Date and Time