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 well known table “cue sports” games such as billiards, snooker, and pool played on a billiards table involving the players striking one of a plurality of balls with a cue, the struck ball then hitting other balls, the raised sides of the table, and in some cases one or more balls going into pockets in the corners and/or sides of the table. Computation of the hash value (digest) is the result of providing a model (such as expressed in computer code) of such a game algorithm and using the message as an input to the game algorithm, then executing the game algorithm. A state of the game after a “shot” gives the hash digest value.

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 principal 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 cue sports games. Cue sports are a set of games of skill generally played with a cue stick which is used by the player to strike billiard balls, moving them around a cloth-covered billiards table bounded by cushions. Historically, the term is billiards. While that name is still employed by some for all such games, the word&#39;s usage has splintered into more exclusive competing meanings among certain groups and geographic regions. In the United Kingdom, “billiards” refers exclusively to English billiards, while in the United States it is sometimes used to refer to a particular game or class of games, or to all cue games in general, depending upon dialect and context. 
         [0008]    There are three major subdivisions of games within cue sports: Carom billiards, referring to games played on tables without pockets, including among others balkline and straight rail, cushion caroms, three-cushion billiards and artistic billiards. Pocket billiards (or “pool”) is generally played on a table with six pockets, including among others eight-ball (the world&#39;s most widely played cue sport), nine-ball, straight pool, one-pocket and bank pool. Snooker, while technically a pocket billiards game, is generally classified separately based on its historic divergence from other games, as well as a separate culture and terminology that characterize its play. 
         [0009]    No actual (physical) game is played or even displayed in accordance with the invention. Instead a “notional” cue sports game (in terms of movement of the billiard balls) is modeled mathematically, without players. In the present hash function, there is no introduction of randomness from the user since the way the billiard balls (which are notional) move is uniquely determined by the input in one embodiment. This means the hash function disclosed here is completely deterministic. The notional cue sports game is any one of the above described games or variants thereof (whether known or with modifications unique to the present system), and it need not conform to any such actual game in terms of rules or the physics of the ball movements. 
         [0010]    The present approach is based on the observation that actual cue sports games exhibit a high degree of randomness in the way the balls move on the billiards table. The present goal is to use the principle of such games 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. 
         [0011]    Since such games are well known and exist in many variants, programming details of the ball movement and interaction modeling algorithm (which models such games as a process) are not given here as being well known. There is a substantial literature on the physics of cue sports, complete with mathematical models of the relevant physics. See an early example “Théorie mathématique des effets du jeu de billiard”, Journal de l&#39;Ecole Polytechnique, by G. Coriolis, 1835. This literature provides the mathematical models used in accordance with the invention to model ball movement and interaction. Writing the portions of the code that embody the physics of the ball movement is relatively simple given these models. Many variations of such games are known and their principles may be used in accordance with the invention, given however that here no person is playing a physical 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 circuitry). For instance, a “checksum” is used when transferring data requires fast determination of the digest. This hash function is especially useful when transferring large amounts of data. 
         [0012]    Note that terms such as “ball,” “strike,” “billiard table,” “energy,” “target,” “position,” 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 cue sports games. 
     
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
         [0013]      FIG. 1  shows a set of variables and parameters. 
           [0014]      FIG. 2  shows relevant portions of a computing device for carrying out the present method. 
           [0015]      FIG. 3  shows additional detail of the  FIG. 2  computing device. 
       
    
    
     DETAILED DESCRIPTION 
       [0016]    The present method and apparatus use certain principles of cue sports games as referred to above. In one embodiment, data expressing aspects of such a game are stored in a large buffer (a data structure stored in a conventional computer readable memory) denoted TABLE (a word array) containing TABLE_SIZE words. TABLE_SIZE is a predetermined integer value. This TABLE can be viewed as expressing the state of a notional cue sports game (e.g. billiards) table in terms of the ball movements and locations. Each entry of this buffer is equivalent to a notional game ball and is e.g. one data word in length and of course expressed in binary form. The initial values of the entries of TABLE are the input message to be hashed which is conventionally first partitioned into blocks of some predetermined length, each block filling TABLE. If needed the message is conventionally padded to fill TABLE. The game algorithm starts by choosing a fixed position (entry) in the buffer denoted CurrentPosition. In this position, there is a certain data word corresponding (equivalent) to a notional ball denoted CurrentBall. The notional player notionally shoots this CurrentBall. A given ball target denoted CurrentTarget is also selected. In the notional game, this is where the notional player wants to shoot the notional ball CurrentBall. Finally, to fully determine the system, the energy of the shot is selected, denoted AccumulatedEnergy. This shot energy is also a function of the TABLE entries. [?True?—how?] 
         [0017]    At this step, the initial conditions of the system are fully determined. Now consider the update part of the system, equivalent to execution of the notional game shot or shots, expressed logically as follows: 
         [0018]    To move the ball (CurrentBall) from its current position in TABLE which is CurrentPosition to the new position in TABLE is expressed as (CurrentPosition+CurrentTarget) % TABLE_SIZE, where “%” conventionally denotes the modulus mathematical operator. 
         [0019]    When a notional ball is moving, it strikes other notional balls on the notional billiards table. Thus, the energy of the notional shot (AccumulatedEnergy) is reduced by these impacts. The struck notional balls are modified (moved) by this impact energy. At the end of the notional shot, the remaining AccumulatedEnergy is assigned to the final location; the notional ball at the final destination is moved in TABLE by 1 step (entry) or more, and is replaced by the ball (CurrentBall) the notional player has shot. [is this accurate?] 
         [0020]    New values for CurrentPosition and consequently CurrentBall, CurrentTarget and AccumulatedEnergy are defined, based on the TABLE and on the message (the initial values in TABLE). [but how do these depend on the message beyond what is explained above?] 
         [0021]    The process is applied a predetermined integer number of times denoted kSEC_PARAMETER defining the level of security of the process. Considering the notional billiards table, this is exactly as if the notional player was shooting several times determined by the value of kSEC_PARAMETER using balls on the billiard table. 
         [0022]    The following is a pseudo-code representation of computation of the present hash function using this approach. It does not include the way the input message is initially stored in TABLE, preliminarily to execution of the game algorithm, since that is typically conventional and the game algorithm is independent of that. The resulting hash digest is conventionally extracted from the word array TABLE for instance by choosing certain entries to be the hash digest. The pseudo-code is conventionally structurally similar to actual code but somewhat less detailed and is not executable and is as follows: 
         [0000]    
       
         
               
             
           
               
                   
               
             
             
               
                  for (j = 0; j &lt; kSEC_PARAMETER; j++) 
               
               
                  { 
               
               
                    /* CurrentBall moves to CurrentTarget, and modifies struck balls */ 
               
               
                    for (k = 0; k &lt; CurrentTarget; k++) 
               
               
                    { 
               
               
                        // Energy is decreased when striking balls 
               
               
                        AccumulatedEnergy = (AccumulatedEnergy − 
               
               
                        function1(Table[(CurrentPosition 
               
               
                            + k) % TABLE_SIZE])) % MAX_ENERGY; 
               
               
                        // Struck balls are modified 
               
               
                        Table[(CurrentPosition + k) % TABLE_SIZE] {circumflex over ( )}= 
               
               
                        function2(AccumulatedEnergy); 
               
               
                    } 
               
               
                    /* CurrentBall impacts on the final ball at the end */ 
               
               
                    CurrentPosition = (CurrentPosition + 
               
               
                    CurrentTarget) % TABLE_SIZE; 
               
               
                    // Use accumulated energy to modify the target balls 
               
               
                    Table[CurrentPosition] {circumflex over ( )}= AccumulatedEnergy; 
               
               
                    // Moves the target ball from one place 
               
               
                    Table[(CurrentPosition+1) % TABLE_SIZE] += 
               
               
                    Table[CurrentPosition]; 
               
               
                    // Moved ball takes the place of the target ball 
               
               
                    Table[CurrentPosition] = CurrentBall; 
               
               
                    // New values for next shot 
               
               
                    CurrentBall = Table[CurrentPosition]; 
               
               
                    (CurrentTarget, AccumulatedEnergy) = function3(Table, inputs) 
               
               
                 } 
               
               
                   
               
             
          
         
       
     
         [0023]    Operators used in this pseudo code are conventional for the C computer language. “++” denotes increment by one. Comments are denoted by “/*”. The operator “̂=” denotes the Boolean exclusive OR operation. [?OK?]. 
         [0024]    Function function 1 , function 2 , function 3  are functions that each may have various implementations. These functions depend on the system (type and detail of the notional cue sports game) being modeled. Function 1  defines how much the energy AccumulatedEnergy is decreasing. Function 2  defines the impact of the shot ball on the system. Finally, function 3  defines the next operation (ball impact) that occurs. In other words these functions model physically (using well known physics equations easily expressed in computer code or equivalent as described above) the interactions of the notional balls and billiard table. The degree of modeling (based on the physics of the notional game) varies in different embodiments depending on the level of complexity desired as explained above. 
         [0025]    An example of function 1  is based on conventional Newtonian mechanics. Given that the frictional force of a billiards table surface on a moving billiard ball is inversely proportional to the speed (velocity) of the ball, then 
         [0000]      frictional force= k/ velocity 
         [0026]    where k is a constant. 
         [0027]    Then since the ball&#39;s kinetic energy is ½*mass*velocity 2 , where the mass is that of the ball, the kinetic energy dissipated by the shot ball rolling on the table is equal to: 
         [0000]    
       
         
           
             
               1 
               / 
               2 
             
             ⋆ 
             mass 
             ⋆ 
             
               · 
               
                 
                   ( 
                   
                     k 
                     
                       frictional 
                        
                       
                           
                       
                        
                       force 
                     
                   
                   ) 
                 
                 2 
               
             
           
         
       
     
         [0000]    which expresses in one embodiment function 1 . [?OK?] 
         [0028]    Function 2  expresses the result of one notional ball striking another in terms of lost energy (and change in velocity). This function depends on the notional elasticity of the balls as well as the angle (vector) at which one ball strikes another, and is based on conventional Newtonian conservation of momentum equations involving ball mass and velocity. 
         [0029]    Function 3  determines, after one notional ball strikes another, what event (ball collision) occurs next. Typically this is somewhat simpler than a full blown Newtonian physics based analysis to make it easier to model. [explain this function more?] 
         [0030]    Also function 1 , function 2  and function 3  may assume that the notional balls (as represented by the TABLE entries) are not perfectly spherical for further complexity. Further the qualities of each notional ball (the TABLE entries) may differ in terms of departure from sphericity, elasticity, and other (notional) physical factors. (All of these factors have well understood effects on the notional ball movements and are readily modeled by embodiments of the functions.) 
         [0031]      FIG. 1  shows variables and parameters for the above pseudo code (first column) with their type (second column) and explanatory comments (third column). 
         [0032]      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. 
         [0033]    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  are the cue sports algorithm module  46  which carries out the pseudo code functionality set forth above including function 1 , function 2 , and function 3 . 
         [0034]    Also coupled to processor  38  are the TABLE computer readable storage medium (memory)  48  (which also stores the energy values), as well as a third storage  43  for the resulting extracted hash digest. The hash digest is conventionally extracted from TABLE, for instance as n consecutive TABLE entries. Storage locations  36 ,  43 ,  48  may be in one or several conventional physical memory devices (such as semiconductor RAM or its variants or a hard disk drive). 
         [0035]    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  43 , which is compared by processor  38  to a second expected hash digest value associated with the incoming message and stored in memory  36 . Only if the two hash digest values match is the message (a digital document, digital signature or similar information) authenticated. 
         [0036]      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. 
         [0037]    Computing system  60  can also include a main memory  58  (equivalent to memories  36 ,  43 ,  48 ), 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 . 
         [0038]    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. 
         [0039]    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 . 
         [0040]    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. 
         [0041]    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. 
         [0042]    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. 
         [0043]    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.