US20160149706A1

US20160149706A1 - Cryptographic hash generation system

Info

Publication number: US20160149706A1
Application number: US15/008,023
Authority: US
Inventors: Iris Anshel; Dorian Goldfeld
Original assignee: SecureRF Corp
Current assignee: Veridify Security Inc
Priority date: 2012-07-13
Filing date: 2016-01-27
Publication date: 2016-05-26
Also published as: US20170257218A1; US20180241566A1; US20170033929A1; US8972715B2; US20180069705A1; US20150131795A1; US20190288848A1; US20160294547A1; US20140019747A1

Abstract

A first module divides a string into a number of blocks. A second module associates the blocks with monoid elements in a list of first monoid elements to produce second monoid elements. A third module applies a first function to an initial monoid element and a first of the second monoid elements producing a first calculated monoid element and evaluates an action of the initial monoid element on the first function producing a second function. A fourth module applies the second function to the first calculated monoid element and to a second of the second monoid elements producing a second calculated monoid element and evaluates the action of the first calculated monoid element on the first function producing a third function. Further modules iteratively, corresponding to the number of blocks, apply the produced function to calculated monoid elements and the second monoid elements to produce a hash of the string

Description

BACKGROUND OF THE INVENTION

A cryptographic hash function may be used to transform a large block of a string of data into a smaller block of hash data. In some examples, the hash data may then be used as an identifier for the string or for a processor in communication with the string. The transformation may be such that recreating the string may be impractical, difficult, or infeasible. In some situations, it may also be difficult or infeasible to find two strings that may be transformed to the same hash.

SUMMARY OF THE INVENTION

One embodiment of the invention is a device effective to generate a hash of a string. The device may comprise a memory. The memory may be effective to include a first function, a first list of first monoid elements, and an initial monoid element. The device may further include a first module effective to receive the string and divide the string into a sequence of blocks. The device may further include a second module in communication with the first module and the memory, the second module effective to associate blocks in the sequence of blocks with respective monoid elements in the first list of first monoid elements to produce a second list of second monoid elements. The device may further include a third module in communication with the second module and with the memory. The third module may be effective to receive a first one of the second monoid elements, receive the initial monoid element, receive the first function, apply the first function to the initial monoid element and the first one of the second monoid elements to produce a first calculated monoid element, and evaluate an action of the initial monoid element on the first function to produce a second function. The device may further include a fourth module in communication with the second module and the third module. The fourth module may be effective to receive a second one of the second monoid elements, receive the first calculated monoid element, receive the second function, and apply the second function to the first calculated monoid element and to the second one of the second monoid elements to produce a second calculated monoid element.
Another embodiment of the invention includes a method for generating a hash of a string. The method may include receiving the string by first module. The method may include dividing the string by the first module into a sequence of blocks and receiving, by a second module, the sequence of blocks. The method may include associating, by the second module, blocks in the sequence of blocks with respective monoid elements in a first list of monoid elements to produce a second list of second monoid elements. The method may include receiving, by a third module a first one of the second monoid elements. The method may include receiving, by the third module, an initial monoid element; receiving, by the third module, a first function; applying, by the third module, the first function to the initial monoid element and the first one of the second monoid elements to produce a first calculated monoid element; and evaluating, by the third module, an action of the initial monoid element on the first function to produce a second function. The method may include receiving, by a fourth module, a second one of the second monoid elements; receiving, by the fourth module, the first calculated monoid element; receiving, by the fourth module, the second function; and applying, by the fourth module, the second function to the first calculated monoid element and to the second one of the second monoid elements to produce a second calculated monoid element.
Another embodiment of the invention is a system effective to communicate a hash of a string. The system may include a first device and a second device in communication with the first device over a network. The first device may include a first memory. The first memory may include a first function, a first list of first monoid elements, and an initial monoid element. The first device may further include a first module effective to receive the string and divide the string into a sequence of blocks. The first device may further include a second module in communication with the first module and the first memory, the second module effective to associate blocks in the sequence of blocks with respective monoid elements in the first list of monoid elements to produce a second list of second monoid elements. The first device may further include a third module in communication with the second module and with the first memory, the third module effective to receive a first one of the second monoid elements, receive the initial monoid element, receive the first function, apply the first function to the initial monoid element and the first one of the second monoid elements to produce a first calculated monoid element, and evaluate an action of the initial monoid element on the first function to produce a second function. The first device may further include a fourth module in communication with the second module and the third module, the fourth module effective to receive a second one of the second monoid elements, receive the first calculated monoid element, receive the second function, and apply the second function to the first calculated monoid element and to the second one of the second monoid elements to produce a second calculated monoid element. The fourth module may further be effective to receive the first function, and evaluate the action of the first calculated monoid element on the first function to produce a third function. The first device may further include a fifth module in communication with the second module and the fourth module. The fifth module effective to receive the third function, receive a third one of the second monoid elements, receive the second calculated monoid element, and apply the third function to the second calculated monoid element and the third one of the second monoid elements to produce the hash of the string. The second device effective to receive the hash; and compare the hash with data stored in a second memory in communication with the second device to produce an identification of the first device.

BRIEF DESCRIPTION OF THE FIGURES

The foregoing and other features of this disclosure will become more fully apparent from the following description and appended claims taken in conjunction with the accompanying drawings. Understanding that these drawings depict only some embodiments in accordance with the disclosure and are therefore not to be considered limiting of its scope, the disclosure will be described with additional specificity and detail by reference to the accompanying drawings in which:

FIG. 1 is a system drawing of a cryptographic hash generation system in accordance with an embodiment of the invention.

FIG. 2 is a flow diagram illustrating a process which could be performed in accordance with an embodiment of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT(S)

In the following detailed description, reference is made to the accompanying drawings which form a part thereof. In the drawings, similar symbols typically identify similar components unless context indicates otherwise. The illustrative embodiments described in the detailed description, drawings and claims are not meant to be limiting. Other embodiments may be utilized and other changes may be made without departing from the spirit or scope of the subject matter presented herein. It will be readily understood that the aspects of the present disclosure as generally described herein and as illustrated in the accompanying figures can be arranged, substituted, combined, separated and/or designed in a wide variety of different configurations all of which are explicitly contemplated herein.
Referring to FIG. 1, there is shown a cryptographic hash generation system 100 which may be used in accordance with an embodiment of the invention. In system 100, a user 102 may input a string 104 into a hash function generator device 106. For example, user 102 may use a processor 118 to input string 104. As discussed in more detail below, hash function generator 106 may be effective to transform string 104 into a hash of string H(S) 108. In some examples, hash function generator device 106 and/or processor 118 may further send hash 108 and hash function 132 over a network 110. Network 110 may include, for example, a wireless network, a wired network, the Internet, a cellular network, a near field communication (NFC) network, a radio frequency identification (RF-ID) network, a cloud computing environment, etc.
A processor 112, in communication with network 110, may receive hash 108 and hash function 132. Processor 112 may compare hash 108 using hash function 132 with data stored in a memory 116. Based on the comparison by processor 112, processor 112 may generate an identifier 114 for user 102 and/or processor 118. For example, processor 112 may be a reader and processor 118 may be a tag in an RF-ID environment. Hash 108 could be a transformation of a public key used in public key encryption communication between tag/processor 118 and reader/processor 112. Reader/processor 112 may compare hash 108 with data in memory 116 to determine which public key/identifier 114 will be used by tag 118.
Hash function generator device 106 may include a string to block decomposition module 120, a block sequence to monoid list module 124, and two or more function evaluation/generation modules 126. At least some of these modules may be in communication with a memory 144 and/or a processor 146. Processor 146 could have a relatively small processing power such as with a 5 MHz clock cycle. Memory 144 could have a relatively small size and have, for example, 1 kb of memory. Modules could be implemented as software such as with a processor and/or in hardware or firmware.
String 104 may be a sequence of bits with a number of bits that is a multiple of a variable λ. Hash function generator device 106 may send string 104 as an input to a string to block module 120. String to block module 120 may be effective to divide string 104 into a sequence of blocks 122 (B₁, B₂, . . .
), each with a length of λ bits. In the example, string 104 is divided into
blocks, where each block is of a length of λ bits. In situations where string 104 includes a number of bits that is not equally divisible by λ, string to block module 120 may add padding bits to produce a modified string with a number of bits that is equally divisible by λ.
String to block module 120 may send sequence of blocks 122 to a block sequence to monoid list module 124. Block sequence to monoid list module 124 may also receive a first list of monoid elements 130. List of monoid elements 130 may be stored in a memory 144. Monoid elements may be, for example, matrices with entries in a finite field.
Each block B in sequence of blocks 122 includes bits in a binary format that may represent a number with a value
between 0 and 2^λ−1. The value may be denoted by
(B_i). Block sequence to monoid list module 124 may transform sequence of blocks 122 into a corresponding sequence of numbers
(B₁), . . .
(
). Block sequence to monoid list module 124 may then associate each value
(B_i), and hence each block B_i, with a monoid element
_(B ₁ ₎in list of monoid elements 130 to produce a second list of monoid elements 128
_(B ₁ ₎. . . ,
_(B ₂ ₎, . . . ,
₍
₎. Monoid elements 128 may be sent to respective function evaluation/generation modules 126. For example,
_(B ₁ ₎may be sent to function evaluation/generation module 126 ₁,
₍
₎may be sent to function evaluation/generation module 126 _i, etc.
Each function evaluation/generation module 126 ₁receives a respective monoid element
_(B ₁ ₎from second list of monoid elements 128, a function
_i-1, and a monoid element
_i-1. Each function evaluation/generation module 126 acts on these inputs to produce an output. For example, function evaluation/generation module 126 ₁receives monoid element
_(B ₁ ₎, initial function
_o 134 and initial monoid element
_o 136. Initial function
_omay be a one-way function as discussed below and may be stored in memory 144. Monoid element
_ocould be, example, a matrix with mod p entries, and may be stored in memory 144. Function evaluation/generation module 126 ₁may apply function
_oto
_oand to
_(B ₁ ₎to produce monoid element
₁.
₁=
_o(
_o,
_(B ₁ ₎)
Function evaluation/generation module 126 ₁may also evaluate the action of
_oon initial function
_oto produce a new function
₁.
₁=
₀·
_o
Function evaluation/generation module 126 ₁may send
₁, initial function
_o, and new function
₁to function evaluation/generation module 126 ₂.
Function evaluation/ generation module 126 ₂receives monoid element
_(B ₂ ₎, initial function
_o, function
₁and monoid element
₁. Function evaluation/generation module 126 ₂may apply function
₁to
₁and to
_(B ₂ ₎to produce monoid element
₂.
₂=
₁(
₁,
_(B ₁ ₎)
Function evaluation/generation module 126 ₂may evaluate the action of
₁on initial function
_oto produce a new way function
₂.
₂=
₁·
_o
Function evaluation/generation module 126 ₂may forward
₂, initial function
_o, and new function
₂to function evaluation/generation module 126 ₃.
This iterative process of generating monoid elements
_iand new functions
_icontinues for each block in sequence of blocks 128. For example, function evaluation/generation module 126 ₃receives monoid element
_(B ₃ ₎, initial function
₀, function
₂and monoid element
₂. Function evaluation/generation module 126 ₃may apply function
₂to
₂and to
_(B ₃ ₎to produce monoid element
₃.
₃=
₂(
₂,
_(B ₃ ₎)
Function evaluation/generation module 126 ₃may evaluate the action of
₂on initial function
₀to produce a new function
₃.
₃=
₂·
_o
The last monoid element
₍
₎in list of monoid elements 128 produced by block sequence to monoid list module 124 is sent to function evaluation/generation module 126
_-1.
Function evaluation/ generation module 126
_-1receives monoid element
₍
₎), function

_-1and monoid element

_-1Function evaluation/generation module 126
_-1may produce Hash (S) 108.
Hash (S)=

_-1(

_-1,
₍
₎)
Hash(S) 108 may be sent from processor 118 to processor 112 over network 110. Processor 118 may also send hash function 132 which may include initial function
₀, list of monoid elements 130, and initial monoid element
_o. Processor 118 may receive hash 108 and compare hash 108 with a list of hash values in memory 116. In another example, processor 118 may receive hash function 132, apply hash function 132 to values in memory 116 (using hash function generator device 106) and determine which resultant hash matches hash 108. For example, passwords may be maintained in memory 116. Processor 112 may apply hash function 132 to each password and identify which password corresponds to hash 108.
Function
may be a one-way function that is computable but difficult, perhaps infeasible, to reverse. In an example, an instance of a one-way function based symmetric encryption protocol utilizes an Algebraic Eraser. An Algebraic Eraser may include a specified 6-tuple (M∝S, N, Π, E, A, B) where
M and N are monoids,
S is a group that acts on M (on the left),
M∝S denotes the semi-direct product,
A and B denote submonoids of M∝S, and
Π denotes a monoid homomorphism from M to N. The E-function, also called E-multiplication, is defined by
E: (N'S)×(M∝S)→(N×S)
E((n, s), (m ₁ , s ₁))=(nπ(^s m ₁), s s ₁).
It is observed that the E-function satisfies the following identity:
E(n, s), ((m ₁ , s ₁)·(m ₂ , s ₂))=E(E(n, s), (m ₁ , s ₁)), (m ₂ , s ₂)).
Function
may be an Algebraic Eraser (M∝S, N, π, E, A, B). Letting M=M∝S, N=N∝S, function
is defined as follows: given (n₀, s₀)εN∝S and (m, s₁)εM∝S let
: N×M→N denote the function:
(n ₁ , s ₁), (m, s ₂)=E(n ₁ , s ₁), (m, s ₁₂)=((n ₁Π(^s ¹ m), s ₁ s ₂).
The structure of the one-way function F enables the following definition of a new one-way function via a left action. Given an arbitrary element (
₀,s₀)εN , and
as specified above, the one-way {(
₀,s₀)·
} is defined by
{(n ₀ , s ₀)·
}((n ₁ , s ₁), (m ₂ , s ₂))=((n₁Π(^s ⁰ ^s ¹ m ₂), s ₁ s ₂)
where (n₁, s₁)εN∝S and (m₂, s₂)εM∝S. A feature of these specified actions is that the property
{(n ₀ ,s ₀)·
(n ₁ , s ₁), (m ₂ , s ₂)·(m ₃ , s ₃))=(n ₀ , s ₀)·F}({(n ₀ , s ₀)·F}((n ₁ , s ₁), (m ₂ , s ₂)), (m ₃ , s ₃)),
for all (n₁, s₁)εN∝S and (m₂, s₂), (m₃, s₃)εM∝S. An application of this feature is that the one-way function (n₀, s₀)·
can be evaluated incrementally, and thus efficiently.
Given a one-way function
₀, the collection of one-way functions
{(n₀, s₀)·F|(n₀, s₀)εN∝S}
satisfies the requirements for the class of one-way functions described above for initial function
₀. The sequence of one-way functions that appear in FIG. 1 may take the form:
₀, {(n₀, s₀)·
₀}, {(n₁, s₁)·
₀}, {(n₂, s₂)·
₀}, . . .
Another instance of a function that may be used is a function where monoids M and N are chosen to be a group G. Defining relators of G may allow for an effective rewriting or cloaking of group elements, and a conjugacy equation in G may be relatively difficult to solve. This insures that the function
: G×G→G defined by the equation,
(x, g)=g ⁻ x g
where x, gεG, is a one-way function. Given a group element, x₀εG, define the left action of x₀on the one-way function
by
{x ₀·
}(x, g)=g ⁻ x ₀ ⁻¹ x x ₀ g.
As with the previous example,
{x ₀·
}(x, g ₁ g ₂)={x ₀·
}({x ₀·
}(x, g ₁)), g ₂).
The collection of one-way functions,
{{x ₀ ·
}|x ₀ εG},
satisfies the requirements for the class of one-way functions described above for initial function
₀.
Among other benefits, a system in accordance with this disclosure may enable a processor to relatively quickly compute the hash of each block of a message, and, thereby, quickly compute the hash of the entire message itself. Long messages may be transformed into a shortened message due to, at least in part, the ability to break the message into smaller pieces. A hash of the message may then be generated, by first hashing the first block using, the output of which is then used to hash the second block, and then proceeding iteratively until the hash of the final block is obtained using. A signature may then be applied to the hash of the message. Functions used in producing the hash may be derived from previously used functions based on actions of monoid elements. As each iterative step may use a relatively quick to process function, the entire hash generation process may be relatively fast. As each function is mutated in subsequent steps, it would be very difficult, perhaps infeasible, to guess all of the functions used in generating the hash. Changing values of monoid elements and/or the initial monoid element may produce new hash functions.
Referring to FIG. 2, there is shown a process which could be performed in accordance with an embodiment of the invention. The process could be performed using, for example, system 100 discussed above and may be used to generate a hash of a string.
As shown, at step S2, a first module may receive a string to be hashed. At step S4, the first module may divide the string into a sequence of blocks. For example, the first module may divide the string into blocks of bits with an equal length.
At step S6, a second module may receive the sequence of blocks. At step S8, the second module may associate the blocks with respective monoid elements in a first list of first monoid elements to produce a second list of second monoid elements.
At step S10, a third module may receive a first one of the second monoid elements, an initial monoid element and a first function. At step S12, the third module may apply the function to the initial monoid element and to a first one of the second monoid elements to produce a first calculated monoid element.
At step S14, the third module may evaluate an action of the initial monoid element on the first function to produce a second function. At step S16, a fourth module may receive a second one of the second monoid elements, the first calculated monoid element and the second function. At step S18, the fourth module may apply the second function to the first calculated monoid element and to the second one of the second monoid elements to produce a second calculated monoid element.
While various aspects and embodiments have been disclosed herein, other aspects and embodiments will be apparent to those skilled in the art. The various aspects and embodiments disclosed herein are for purposes of illustration and are not intended to be limiting, with the true scope and spirit being indicated by the following claims.

Claims

What is claimed is:

1. A device effective to generate a hash of a string, the device comprising:

a memory, wherein the memory is effective to include

a first function,

a first list of first monoid elements, and

an initial monoid element;

a first module effective to receive the string and divide the string into a sequence of blocks;

a second module in communication with the first module and the memory, the second module effective to associate blocks in the sequence of blocks with respective monoid elements in the first list of first monoid elements to produce a second list of second monoid elements;

a third module in communication with the second module and with the memory, the third module effective to

receive a first one of the second monoid elements,

receive the initial monoid element,

receive the first function,

apply the first function to the initial monoid element and the first one of the second monoid elements to produce a first calculated monoid element, and

evaluate an action of the initial monoid element on the first function to produce a second function;

a fourth module in communication with the second module and the third module, the fourth module effective to

receive a second one of the second monoid elements,

receive the first calculated monoid element,

receive the second function, and

apply the second function to the first calculated monoid element and to the second one of the second monoid elements to produce a second calculated monoid element.