Abstract:
In the computer data security field, a cryptographic hash function process embodied in a computer system and which is typically keyless, but is highly secure. The process is based on the type of randomness exhibited by the well known gambling game of roulette played on a roulette wheel involving dropping a ball onto a partitioned spinning wheel. The ball loses momentum and drops into one of the partitions (pockets) of the wheel. Computation of the hash value (digest) is the result of executing in a model (such as computer code or logic circuitry) such a game algorithm using the message as an input to the game algorithm, then executing the game algorithm. A state of the game (the final ball location) after a ball (or several balls) are played gives the hash digest value of the message.

Description:
FIELD OF THE INVENTION 
       [0001]    This invention relates to computers, computer data security, and hash functions (hashing). 
       BACKGROUND 
       [0002]    Hash functions are well known in the field of data security. The principle is to take data (a digital message, digital signature, etc.) and use it as an entry to a hash function resulting in an output called a “digest” of predetermined length which is intended to uniquely identify (“fingerprint”) the message. A secure (cryptographic) hash is such that any alteration in the message results in a different digest, even though the digest is much shorter than the message. Such hash functions are “collision-resistant” and “one-way.” 
         [0003]    Cryptography and data security deal with digital signatures, encryption, document authentication, and hashing. In all of these fields, there is a set of basic tools/functions which are widely used, for instance hash functions. Several properties are required for the use of hash functions in cryptographic applications: preimage resistance, second preimage resistance and collision resistance. 
         [0004]    In the recent years, much energy has been expended finding new hash functions, since collisions (weaknesses or successful attacks) have been found in the widely used SHA-1 standard hash. 
       SUMMARY 
       [0005]    Disclosed here is a new type of cryptographic (secure) hash function or process. The goal is a highly modular hash function that is also computationally efficient (fast). The present hash function can conventionally be used for document integrity for exchanges and signatures. It can be also used as a derivation function or as a HMAC (hash message access code) by adding a key conventionally (as in for instance the well known HMAC-SHA1) and the term “hash” as used herein is intended to encompass all these uses, both keyed and non-keyed. 
         [0006]    A hash function is a deterministic procedure that accepts an arbitrary input value, and returns a hash value. The input value is called the message, and the resulting output hash value is called the digest. The message is authenticated by comparing the computed digest to an expected digest associated with the message. 
         [0007]    The present hash process is based on the concept and rules and physics of physical roulette games. Roulette is a casino gambling game named after the French word for small for wheel. Players place bets on a number on the wheel, a range of numbers, the color red or black, or whether the number is odd or even. To determine the winning number and color, a croupier spins the wheel in one direction, then spins a ball in the opposite direction around a tilted circular track running around the circumference of the wheel. The ball eventually loses momentum and falls onto the wheel and into one of 37 (in European roulette) or 38 (in American roulette) colored and numbered pockets on the wheel. In some forms of early American roulette wheels there were numbers 1 through 28, plus a single zero, a double zero, and an American Eagle. 
         [0008]    No actual (physical) roulette game is played or even displayed in accordance with the invention and there is no betting involved and no croupier or players. Instead a “notional” roulette game (in terms only of movement of the roulette ball on the wheel) is modeled mathematically, without players or betting. In accordance with the present hash function, there is no introduction of randomness from a user since the way the game ball (which is notional) moves is uniquely determined by the input (the message to be hashed) in one embodiment. This means the hash function disclosed here is completely deterministic. The notional roulette game is any one of the above described games or variants thereof; it need not conform to any such actual game in terms of rules (such as wheel layout) or the physics of the ball movement. 
         [0009]    The present approach is based on the observation that actual roulette exhibits a high degree of chaos in the way the ball moves on the roulette wheel. The present goal is to use the principles of roulette to compute a hash function since such a chaotic (randomness) characteristic provides a secure hash function. In this sense secure means strongly one way, meaning that given a message it is easy to compute the digest, but it is very difficult to find a message that returns a given digest. 
         [0010]    Since roulette is well known and exists in several variants, programming details of the present ball movement and wheel interaction modeling algorithm (which models such games as a process in accordance with the invention) are not given here as being well known. There is a literature on the physics of roulette, complete with mathematical models based on Newtonian mechanics. This literature provides the mathematical models used in accordance with the invention to model ball movement and wheel interaction. Writing such computer code (or designing equivalent logic circuitry) is routine to one skilled in the art given the mathematical models. Variations of roulette are known in terms of wheel layout and their principles may be used in accordance with the invention, given however that here no person is playing a physical roulette game but there is execution of the core algorithm (physics and rules) of such a game to generate the hash digest. Moreover the present hash function is computed very rapidly in computer software (or hardware—dedicated logic circuitry). For instance, a hash “checksum” as used when transferring data requires fast determination of the digest. This hash function is especially useful when transferring large amounts of data. 
         [0011]    Note that terms such as “ball,” “speed,” “roulette wheel,” “energy,” “friction,” “position,” “cell,” and “game” used here in connection with the present invention do not refer to any physical object or game or any actual depiction of same even on a computer or game display, but instead to values, identifiers, or variables used in computer code or logic to compute a hash function or equivalent, and are used only for convenience of understanding herein as referring conceptually to analogous aspects of the above described roulette game. Moreover, the betting aspect of roulette is not present here; all that is of concern is the ball-wheel interaction and where the notional ball lands on the notional wheel. 
     
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
         [0012]      FIG. 1  shows a set of variables and parameters. 
           [0013]      FIG. 2  shows relevant portions of a computing device for carrying out the present method. 
           [0014]      FIG. 3  shows additional detail of the  FIG. 2  computing device. 
       
    
    
     DETAILED DESCRIPTION 
       [0015]    The present hash function is based on the well-known game of roulette. This actual game is as follows: the roulette wheel spins at a given speed and the ball is dropped in the roulette wheel with an initial speed, in the inverse direction of the roulette wheel spin. Because of friction between the ball and the roulette wheel, the speed of the ball (more precisely, the difference between the speeds of the roulette wheel and the ball) reduces to zero or some other minimum value (i.e., at the end of the play, the ball is stationary on the roulette wheel, which is still spinning). The position of the ball at the end of the play determines amongst the players the winners and their gains. 
         [0016]    The first point is to consider the roulette wheel as the physics frame of reference for the ball. Then the ball is dropped onto the roulette wheel with an initial speed (where speeds are measured in the roulette wheel frame of reference). Physically, there are several sources of movement changes for the ball: friction, and the impact of the ball with the various pockets and cells of the wheel. For the present hash function, the ball behavior is to be as unstable (random or high entropy) as possible. This means that modifying by a small amount the initial state must have a large impact on the behavior, so one can consider all of these behavioral aspects of the ball as sources of entropy. 
         [0017]    Friction is in physics modeled as a force proportionally inverse to the speed (velocity) of the ball. Additionally, impacts between the ball and the wheel pockets and cells are more complicated to model mathematically, and so here one may use a simplified model (e.g., not fully in accordance with the physics of the actual game). 
         [0018]    The algorithm of the present hash function is as follows. The hash function uses a large state (array or table or data structure referred here to generally as a table) h, of k data words, and hashes blocks of message m of 1 words (where for good security, k is much greater than one). Conventionally one pads the message such that any message is partitionable into an integer number of blocks. Initially, table h is initialized for the first block with an initial value (constant) IV. There is also defined a security parameter (integer) SEC_PARAMETER, which preferentially is much larger than k and determines the number of repetitions of the process. 
         [0019]    The hashing of each block (in cryptography, this is called the compression function) is expressed in pseudo code where this pseudo-code is conventionally structurally similar to actual code but somewhat less detailed and is not executable and is as follows: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 Function: Perform for One Block 
               
               
                   
                 Input: message m[0], ... m[l−1] (set of l bytes), h[0], ... h[k−1] 
               
               
                   
                 (set of k bytes) 
               
               
                   
                 Output: hash h[0] ... h[k−1] (set of k bytes) 
               
               
                   
                 for(i = 0; i &lt; k; i++) 
               
               
                   
                   h[i] {circumflex over ( )}= m[i % l] 
               
               
                   
                 for(l = 0; l &lt; SEC_PARAMETER; i++) { 
               
               
                   
                   stop = 0; 
               
               
                   
                   v0 = InitialSpeedDetermine(h); 
               
               
                   
                   Ball = definingBall(h); 
               
               
                   
                   Destination = definingStartingDestination(h); 
               
               
                   
                   while (v0 &gt; 0) 
               
               
                   
                   { 
               
               
                   
                     /* Update with friction */ 
               
               
                   
                     v0 = speedReducedByFrictions(v0); 
               
               
                   
                     /* Goes to destination, and hit */ 
               
               
                   
                     (v0, Destination) = hitWheeling(h, v0, Destination, Ball); 
               
               
                   
                   } 
               
               
                   
                   /* Place ball at final destination */ 
               
               
                   
                   h[Destination] {circumflex over ( )}= Ball; 
               
               
                   
                 } 
               
               
                   
                 return 0; 
               
               
                   
                   
               
             
          
         
       
     
         [0020]    For any number of blocks of the message, the hashing process is as follows: (1) initiate h with an initial value (the IV referred to above) h 0 ; (2) for each block of the message (which is conventionally padded to be an integer number of blocks as explained above) apply the process defined by the above pseudo code. 
         [0021]    In this algorithm (process) InitialSpeedDetermine is a function that takes the initial hash state h, and outputs an initial notional speed v 0  for the notional ball. The notional mass of the ball is set by the function definingBall which also uses as an input the initial hash state. In the same way, the notional destination (the position on the notional roulette wheel the ball ends up) is defined by the function definingStartingDestination. Then, speedReducedByFrictions is a function which uses a conventional Newtonian physics model expressed in equations to calculate the reduction of speed of the notional ball. Lastly, function hitWheeling expresses (again using a physics model) the impact(s) between the notional ball and the notional wheel, which results in a new speed (smaller than the original speed) and in a new direction of the notional ball. 
         [0022]    The present method in another embodiment is generalized to a notional roulette wheel with more than one notional ball in play, which is even more random (chaotic), since in addition to friction and impacts between the balls and cells and pockets of the wheel, there are impacts between the notional balls. 
         [0023]    A somewhat simplified model in Newtonian physics of actual (physical) roulette (with only one ball) expresses the ball position in the X, Y, Z axes relative to frame of reference of the roulette wheel. It uses as variables the ball&#39;s initial linear velocity, the ball track radius of the wheel (where the pockets and cells are on the wheel), and the ball&#39;s centripetal acceleration. It computes the Z axis (height) position of the ball in terms of friction force and air drag of the ball. Air drag is conventionally a function of the ball&#39;s mass, its centripetal acceleration, air density and drag coefficient. The ball at some point loses contact with the vertical side of the ball track on the wheel, called the drop off condition. The reduction of the speed due to friction is not necessarily constant according to the speed and can depend on the ball&#39;s the position. Other values needed for the physics model are the inner slope of the ball track, and radius of the ball. Of course this is a somewhat simplified model of the physical game, but sufficient for the present purpose. 
         [0024]    The present hash process is applied a predetermined number of times denoted kSEC_PARAMETER as set forth above defining the level of security of the process. Considering an actual roulette game, this is exactly as if the notional croupier was playing the ball several times in succession determined by the value of kSEC_PARAMETER using a roulette ball on the roulette wheel and only the position of the ball after the several plays was used as the hash state. The state after one play defines the initial configuration of the next play and so on. Other parameters can be used in the definition. 
         [0025]    Operators used in this pseudo code are conventional for the C computer language. “++” denotes increment by one. Comments are surrounded by “/*” and “*/”. The operator “̂” denotes the Boolean exclusive OR (XOR) operation and “̂=” denotes the XOR association (results in); “%” denotes modulus. 
         [0026]      FIG. 2  shows in a block diagram relevant portions of a computing device (system)  30  in accordance with the invention. This is, e.g., a server platform, computer, mobile telephone, Smart Phone, personal digital assistant or similar device, or part of such a device and includes conventional hardware components executing in one embodiment software (computer code) as represented by the above pseudo-code example. This code may be, e.g., in the C or C++ computer language or its functionality may be expressed in the form of firmware or hardware logic; writing such code or designing such logic would be routine in light of the above pseudo code. Of course, the above pseudo code example is not limiting. 
         [0027]    The computer code is conventionally stored in code memory (computer readable storage medium)  40  (as object code or source code) associated with conventional processor  38  for execution by processor  38 . The incoming message (in digital form) is received at port  32  and stored in computer readable storage medium (memory)  36  where it is coupled to processor  38 . Processor  38  conventionally partitions the message into suitable sized blocks at partitioning module  42 . Other software (code) modules in processor  38  make up the roulette game algorithm module  46  which carries out the pseudo code functionality set forth above. 
         [0028]    Also coupled to processor  38  is a third storage  57  for the resulting extracted hash digest. The hash digest is conventionally extracted from the table, for instance as n consecutive entries so as to provide a hash digest of sufficient fixed length. One can perform this extraction in various ways, so as to extract the needed number of bytes for the digest from the final state of the table. Storage locations  36 ,  40 ,  57  may be in one or several conventional physical memory devices (such as semiconductor RAM or its variants or a hard disk drive). 
         [0029]    Electric signals conventionally are carried between the various elements of  FIG. 2 . Not shown in  FIG. 2  is the subsequent conventional use of the resulting hash digest stored in storage  57 , which is compared by processor  38  to a second expected hash digest value associated with the incoming message. Only if the two hash digest values match is the incoming message (a digital document, digital signature or similar information) authenticated. 
         [0030]      FIG. 3  shows further detail of the  FIG. 2  computing device in one embodiment.  FIG. 3  illustrates a typical and conventional computing system  60  that may be employed to implement processing functionality in embodiments of the invention and shows additional detail of the  FIG. 2  system. Computing systems of this type may be used in a computer server or user (client) computer or other computing device, for example. Those skilled in the relevant art will also recognize how to implement embodiments of the invention using other computer systems or architectures. Computing system  60  may represent, for example, a desktop, laptop or notebook computer, hand-held computing device (personal digital assistant (PDA), cell phone, palmtop, etc.), mainframe, server, client, or any other type of special or general purpose computing device as may be desirable or appropriate for a given application or environment. Computing system  50  can include one or more processors, such as a processor  64  (equivalent to processor  38  in  FIG. 2 ). Processor  64  can be implemented using a general or special purpose processing engine such as, for example, a microprocessor, microcontroller or other control logic. In this example, processor  64  is connected to a bus  62  or other communications medium. Note that in some embodiments the present process is carried out in whole or in part by “hardware” (dedicated circuitry) which is equivalent to the above described software embodiments. 
         [0031]    Computing system  60  can also include a main memory  58  (equivalent to memories  32 ,  40 ,  57  in  FIG. 2 ), such as random access memory (RAM) or other dynamic memory, for storing information and instructions to be executed by processor  64 . Main memory  68  also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor  64 . Computing system  60  may likewise include a read only memory (ROM) or other static storage device coupled to bus  62  for storing static information and instructions for processor  64 . 
         [0032]    Computing system  60  may also include information storage system  70 , which may include, for example, a media drive  62  and a removable storage interface  80 . The media drive  72  may include a drive or other mechanism to support fixed or removable storage media, such as flash memory, a hard disk drive, a floppy disk drive, a magnetic tape drive, an optical disk drive, a compact disk (CD) or digital versatile disk (DVD) drive (R or RW), or other removable or fixed media drive. Storage media  78  may include, for example, a hard disk, floppy disk, magnetic tape, optical disk, CD or DVD, or other fixed or removable medium that is read by and written to by media drive  72 . As these examples illustrate, the storage media  78  may include a computer-readable storage medium having stored therein particular computer software or data. 
         [0033]    In alternative embodiments, information storage system  70  may include other similar components for allowing computer programs or other instructions or data to be loaded into computing system  60 . Such components may include, for example, a removable storage unit  82  and an interface  80 , such as a program cartridge and cartridge interface, a removable memory (for example, a flash memory or other removable memory module) and memory slot, and other removable storage units  82  and interfaces  80  that allow software and data to be transferred from the removable storage unit  78  to computing system  60 . 
         [0034]    Computing system  60  can also include a communications interface  84  (equivalent to port  32  in  FIG. 2 ). Communications interface  84  can be used to allow software and data to be transferred between computing system  60  and external devices. Examples of communications interface  84  can include a modem, a network interface (such as an Ethernet or other network interface card (NIC)), a communications port (such as for example, a USB port), a PCMCIA slot and card, etc. Software and data transferred via communications interface  84  are in the form of signals which can be electronic, electromagnetic, optical or other signals capable of being received by communications interface  84 . These signals are provided to communications interface  84  via a channel  88 . This channel  88  may carry signals and may be implemented using a wireless medium, wire or cable, fiber optics, or other communications medium. Some examples of a channel include a phone line, a cellular phone link, an RF link, a network interface, a local or wide area network, and other communications channels. 
         [0035]    In this disclosure, the terms “computer program product,” “computer-readable medium” and the like may be used generally to refer to media such as, for example, memory  68 , storage device  78 , or storage unit  82 . These and other forms of computer-readable media may store one or more instructions for use by processor  64 , to cause the processor to perform specified operations. Such instructions, generally referred to as “computer program code” (which may be grouped in the form of computer programs or other groupings), when executed, enable the computing system  60  to perform functions of embodiments of the invention. Note that the code may directly cause the processor to perform specified operations, be compiled to do so, and/or be combined with other software, hardware, and/or firmware elements (e.g., libraries for performing standard functions) to do so. 
         [0036]    In an embodiment where the elements are implemented using software, the software may be stored in a computer-readable medium and loaded into computing system  60  using, for example, removable storage drive  74 , drive  72  or communications interface  84 . The control logic (in this example, software instructions or computer program code), when executed by the processor  64 , causes the processor  64  to perform the functions of embodiments of the invention as described herein. 
         [0037]    This disclosure is illustrative and not limiting. Further modifications will be apparent to these skilled in the art in light of this disclosure and are intended to fall within the scope of the appended claims.