Computer implemented method for generating a random seed with high entropy

Abstract

In a computer implemented method for generating a random seed with high entropy as an entropy source a machine instruction ‘compare-and-swap’ —CAS— is used to calculate a random seed.

Claims

1. A computer implemented method for generating a random seed with high entropy, wherein as an entropy source a machine instruction ‘compare-and-swap’ —CAS— is used to calculate a random seed:

2. A method according to claim 1, comprising the steps of using on each machine thread a program including the machine instruction CAS during multithreading on at least two machine threads, the program filling a last-in-first-out-queue list and removing elements in a certain pattern until the list is destroyed by the program, and using the random-affected moment of destruction of the list to calculate the random seed.

3. A method according to claim 2, comprising running at least two machine threads on different CPU cores of a computer.

4. A method according to claim 1, comprising the steps of connecting the computer to at least one Internet based sender of data packets, which are sent by packet switching within a given time pattern, detecting the moment of receipt of consecutively received data packets, determining the random-affected time differences between the moment of receipt of consecutively received data packets, and calculating a random seed from the random-affected time differences.

5. A method according to claim 4, wherein the data packets are sent under a public Internet protocol.

6. A method according to claim 5, wherein the data packets are sent under one of HTTP, TCP and UDP.

7. A method according to claim 4, wherein the computer records at least one Internet based sender which is sending one of audio data packets and video data packets.

8. A method according to claim 4, wherein by means of an operating system function implemented in the computer's operating system the current moment of receipt of a data packet is determined with a resolution in the magnitude of nanoseconds.

9. A method according to claim 4, wherein the computer is connected in parallel to several Internet based senders, combining the random-affected time differences in the moment of receipt of consecutively received data packets from the several senders to calculate the random seed.

10. A method according to claim 4, wherein the values of the random-affected time differences between the moment of receipt of consecutively received data packets are mixed with at least one further entropy source by applying an appropriate hashing function.

11. A method according to claim 10, wherein the values of the random-affected time differences between the moment of receipt of consecutively received data packets are mixed with the random generated by detecting the content of the received data packets by applying an appropriate hashing function.

12. A method according to claim 10, wherein the values of the random-affected time differences between the moment of receipt of consecutively received data packets are mixed with at least one further entropy source by applying a logical XOR function.

Description

EXAMPLE 1

[0041] As a basic source for getting random seed the special machine instruction CAS is used.

[0042] As today's computers have multiple CPU cores and are running multiple threads which all can access the same memory location, CAS is needed and is implemented in many different hardware platforms. Now, this special instruction can be used to access a LIFO (last-in first-out) queue in memory.

[0043] Now in the document “IBM System/370 Principles of Operation GA22-7000-4 Lock/Unlock with LIFO Queuing for Contentions Free-Pool-List Manipulation”, there is the following basic information how CAS works:

[0044] “Consider a chained list of the type used in the LIFO lock/unlock example. Assume that the first two elements are at locations A and B, respectively. If one program attempted to remove the first element and was interrupted between the fourth and fifth instructions of the LUNLK routine, the list could be changed so that elements A and C are the first two elements when the interrupted program resumes execution. The CS”—(Remark: IBM uses the term ‘CS’ instead of the term ‘CAS’ used in this patent application)—“instruction would then succeed in storing the value B into the header, thereby destroying the list.”

[0045] For this invention, to generate a random seed, a short software program part is used with the special instruction CAS and running this program on multiple threads. It fills a LIFO queue and removes elements in a certain pattern. As in the IBM description, the list is destroyed, and the program detects when the list is destroyed. It is not predictable at what time the list will be destroyed, so this time can be used as a source for the random seed.

[0046] For an approximate calculation of the expected entropy, which can be gained by the described procedure, the following assumptions are made: [0047] The time of detecting the destruction of the queue list through a conflict event in Intel x86 CPUs is given in time steps of around 300 nanoseconds. [0048] The following calculation uses these approximate equations: [0049] I. 300˜256=2.sup.8, [0050] II. 10.sup.3=1000˜1024=2.sup.10.

[0051] Within an observed time of one second and an accuracy of time measure in nanoseconds, the time quantum would be 10.sup.9.

[0052] Supposed that 10.sup.9˜2.sup.30 (see above equation II), divided by the above assumed destruction granularity of 2.sup.8 (see above equation I), an entropy of 22 (30−8) bits would be expected out of this calculation.

[0053] One does not get time intervals from the conflict events, only, but also from other random numbers, like the threat numbers and the queue element numbers where the conflict events happen, and other numbers. At all one may get 16 (=2.sup.4) random numbers additionally.

[0054] Data, which is used for calculating the random seed, is taken from: [0055] the execution time until the next fault event occurs, [0056] the threat number where the fault event was detected, [0057] the number of the element in the queue where the fault event was detected, [0058] the number of loops that have been running in that threat where the fault event was detected.

[0059] in summary 22+4=26 bits of entropy per second are to be expected.

[0060] When this process is run for a longer time, for example about ½ minute, and assumed that the events in every observed second are independent, one can add the bits of entropy of every second. This results in 26*30=780 bits entropy within 30 seconds.

[0061] Tests when running a preferred implementation show that the results depend strongly on the hardware of the computer machine, especially on the number of available CPU cores. On some machines truly tens of thousands of bits of entropy can be generated in one second.

[0062] Following program examples can be given to realize the CAS based random seed generator:

[0063] In Pseudocode the routine to access LIFO queues—with the described object—can be given as:

TABLE-US-00002 Initialize (ff = pointer to LIFO queue, dummy: pointer to dummy memory cell) I1: ff->head = null # initialize the head cell - dequeue (ff = pointer to LIFO queue): pointer to memory cell D1: head = ff->head # read the head cell D2: loop # try until dequeue is done D3:  if head == NULL # is queue empty ? D4:  return NULL D5:  endif D6:  next = head->next # read the next memory cell D7:  CAS (&ff->head, head, next) D8:  if successful break D9: endloop D10: return head - enqueue (ff = pointer to LIFO queue, cl = pointer to memory cell) E1: head = ff->head # read the head memory cell E2: loop # try until enqueue is done E3:  cl->next = head # set the cell next pointer to NULL E4:  CAS (&ff->head, head, cl) E5:  if successful break E6: endloop E7: return

[0064] Following explanations are to be given:

[0065] E4: CAS compares the second operand with the content of the first operand. [0066] When these are equal, the third operand is copied to the content of the first operand and the condition code is set to SUCCESSFUL. [0067] In case they are not equal, the content of the first operand is copied into the second operand and the condition code is set to FAILED.

[0068] The routine which detects the object, and where the data are used for the random, looks like this:

[0069] R1: get entry from store

[0070] R2: mark with pattern

[0071] R3: sleep or do something else

[0072] R4: check if still same pattern

[0073] R5: put entry back to store

[0074] R6: sleep or do something else

[0075] R7: next iteration [0076] when check fails: error occurred before [0077] or

[0078] R1: get n entries from store, mark each entry with unique pattern

[0079] R2: sleep or do something else

[0080] R3: check each (n) entry and put entry back to store

[0081] R4: sleep or do something else

[0082] R5: next iteration [0083] when check fails: error occurred before

[0084] The basic idea behind these CAS routines is, that multiple threads or cores of a CPU work concurrently under conditions that allow these errors to occur. The randomness is taken from the unpredictable proceeding in which these errors occur, regarding the time difference between two consecutive events and some other event related data serving as processible output. When only one core is used, the routine still works in a preemptive operation system, but the faults occur only very seldom.

EXAMPLE 2

[0085] To enhance the entropy achieved by using the CAS instruction as explained under example 1 further entropy sources can be admixed according to the following explanation, referring to FIG. 1 which shows a flow diagram of a preferred embodiment of the method according to the invention using three Internet radio stations.

[0086] Beginning with step 10 “Start” in the next step 20 three Internet radio stations are connected to a computer on which the random seed is to be calculated. The connections are configured to receive audio data packets continuously in a loop for some time under the HTTP protocol.

[0087] The loop box 30 illustrates the method routine running for each of the three connections. Basically the computer in step 40 waits for data to receive from the Internet radio stations via all three connections. In step 50 for each received data buffer N the moment of receipt in nanoseconds is retrieved from the system. In the query 60 it is checked whether data N is different from the previous data (N−1). If “no”—branch 70—the connection is disconnected and a new connection is made—step 80. The process is redirected to step 40 “Wait for data to receive”.

[0088] If in query 60 the answer is “yes”—branch 90—the process proceeds to step 100 in which the random affected time difference between the moment of receipt of buffer N and the moment of receipt of buffer (N−1) is calculated.

[0089] In step 110 the random seed is calculated incorporating for example the entropy of the buffer N data by a bitwise exclusive OR (XOR) operation. The resulting random seed is added to the seed pool of the employed or random generator of the computer in this step.

[0090] The final STOP-query 120 is made. When the processes is to be continued by choosing “No”—branch 130—the process is redirected to step 40. If the process is to be terminated by choosing “Yes”—branch 140—it proceeds to step 150—“End”.