FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION (See section 10, rule 13)
1. Title of the invention: GENERATION OF RANDOMIZED MESSAGES FOR
CRYPTOGRAPHIC HASH FUNCTIONS
2. Applicant(s)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY Indian Nirmal Building, 9th Floor, Nariman
SERVICES LIMITED Point, Mumbai, Maharashtra 400021,
India
3. Preamble to the description
COMPLETE SPECIFICATION
The following specification particularly describes the invention and the manner in which it
is to be performed.

TECHNICAL FIELD
[001] The present subject matter relates, in general, to information security and
cryptography and, in particular, to generation of randomized message for use in cryptographic hash functions.
BACKGROUND
[002] A cryptographic hash function is a mathematical function that takes an arbitrary
length message and returns a fixed-size bit string, referred to as hash value or message digest, such that an accidental or intentional change to the message will, with very high probability, changes the hash value.
[003] Cryptographic hash functions play a significant role in secure and efficient digital
information processing. Therefore, the cryptographic hash functions are employed by various corporate sectors in many information processing applications, such as efficient digital signature generation and verification, message integrity, password protection, signcryption mechanism, cryptographic commitment protocols, key derivation functions (KDFs), and message authentication codes (MACs).
[004] The cryptographic hash functions generally have three security properties, namely,
collision resistance, preimage resistance, and second preimage resistance. The requirement of these properties depends on an application in which the cryptographic hash function is used. This implies, a security attack that weakens any of these properties could undermine the security of the application, which needs that property. For example, a collision attack on a hash function defeats the security of the digital signatures and a preimage attack on a hash function compromises the security of applications, such as password protection and MACs. Thus, the cryptographic hash functions are designed to prevent any such attack that compromises on security of an application.
[005] The cryptographic hash functions, such as message digest algorithm (MD5) and
secure hash algorithm-1 (SHA-1) are widely used by various corporate sectors to have secure and efficient implementation of the information processing applications. However, certain

cryptographic hash functions, such as MD5 and SHA-1 are susceptible to the security attacks, such as collision attacks. Further, cryptographic libraries of some licensed software frameworks may not support stronger hash functions for application security and until the time they start supporting stronger hash functions these frameworks may use susceptible hash functions for application security.
SUMMARY
[006] This summary is provided to introduce concepts related to generation of
randomized messages for use in hash functions. These concepts are further described below in the detailed description. This summary is not intended to identify essential features of the claimed subject matter nor is it intended for use in determining or limiting the scope of the claimed subject matter.
[007] Method(s) and a system(s) for generating randomized message are described herein.
In an implementation, a random value is obtained based on a randomization criterion to randomize a message. Further, a last data block of the message is populated with a randomization parameter to obtain a randomized message. The randomization parameter is computed using the random value.
BRIEF DESCRIPTION OF THE DRAWINGS.
[008] The detailed description is described with reference to the accompanying figures. In
the figures, the left-most digit(s) of a reference number identifies the figure in which the
reference number first appears. The same numbers are used throughout the drawings to reference
like features and components.
[009] Fig. 1 illustrates a computing environment implementing a randomized message
generation system, in accordance with an embodiment of the present subject matter.
[0010] Fig. 2 illustrates a method for generating randomized messages, in accordance with
an implementation of the present subject matter
DETAILED DESCRIPTION
[0011] Method(s) and a system(s) to generate message digests for secure information
processing applications, such as digital signatures, are described herein. The systems and

methods described herein can be implemented on computing devices, such as a server, a desktop, a mobile device, a notebook or a portable computer.
[0012] Generally, cryptographic hash functions, also referred to as hash functions, are
employed for secure and efficient implementation of information processing applications, such
as digital signature generation and verification, message integrity, password protection,
signcryption mechanism, cryptographic commitment protocols, key derivation functions (KDFs),
and message authentication codes (MACs). The cryptographic hash functions generally have
three security properties, namely, collision resistance, preimage resistance, and second preimage
resistance. A hash function, H, is considered to be collision resistant if it is hard to find two
distinct messages that hash to the same output; that is, the hash function, H, is not collision
resistant if for two distinct messages a and b such that H(a)= H(b), and a≠b.
[0013] However, certain popular hash functions, such as message digest algorithm
(MD5) and secure hash algorithm-1 (SHA-1) are not collision resistant. Therefore, such hash functions may be considered insecure for applications, for example, digital signatures that require collision resistance property. In order to provide enhanced protection for applications, such as digital signatures, against collision attacks on the cryptographic hash functions, a mode of operation that randomizes message inputs to the hash functions is employed. Such a mode of operation is referred to as randomized hash function mode. Randomized hash function modes are often employed in digital signature applications as they strengthen the security of digital signatures.
[0014] These randomized hash function modes operate such that digital signature
security depends on a security property related to second preimage resistance of the hash function, which is much harder to break as compared to the collision resistance. In other words, even if an attacker finds a collision in a hash function, he would not be able to use the collision to forge signature schemes that use the randomized hash function mode to compute a message digest.
[0015] In the randomized hash function mode a common salt, which is a random value
may be used for both signing and hashing to save on communication bandwidth involved in transporting a separate salt to a verifier of the signing system. Though such randomized hash

functions prove to be suitable for limited bandwidth applications, at the same time, they are observed to be susceptible to security attacks, such as online forgery attacks. In the online forgery attacks, an attacker in an online setting, can forge digital signature schemes by exploiting easy to find fixed points that exist in the compression functions of popular hash functions, such as MD5, SHA-1 and SHA-256. These online forgery attacks have a computational cost of birthday complexity on the size of the hash value and therefore these attacks may also be called online birthday forgery attacks. Thus, online forgery attacks exploit structural weakness in the underlying components of these hash functions. Further, the online forgery attacks directly apply to the usage of common salt generated for every signature also for hashing, which is recommended to save communication bandwidth, thereby showing the possibility of collision attacks in the online setting to forge digital signatures.
[0016] According to an embodiment of the present subject matter, systems and methods
for generation of randomized messages are described. The randomized messages are generated for an input message, which may be, for example, a document meant for digital signing. In an implementation, the message is randomized to ensure the security and efficiency of an underlying information processing application. For randomizing the message, the message is divided into predetermined number of data blocks based on a block length of a compression function. The compression function is a component of a cryptographic hash function used for processing each message block iteratively until the whole input message is processed. Further, a random value is obtained to perform the randomization of the message. The random value may be concatenated to itself a predetermined number of times based on the block size of the compression function.
[0017] The divided message is randomized based on the concatenated random value.
Further, it is determined if a last data block of the message can accommodate a randomization parameter and padding bits. In case it is determined that last data block does not have sufficient space to accommodate the randomization parameter and the padding bits, an additional data block is appended at the end of the message, which now serves as the last data block. To prevent the message from online forgery attacks, the last data block is populated with the randomization parameter. The randomization parameter is computed based on the random value. For example,

based on the space available in the last data block, the random value may be concatenated to itself a sufficient number of times to obtain the randomization parameter. Thus, the randomized message may include the data blocks, which are randomized using the randomization criterion and the last data block includes the randomization parameter.
[0018] Additionally, randomness by way of a random factor may also be appended at the
beginning of the message. The random factor may be based on the random value and a block length of the compression function. In said case, in addition to randomized data blocks and the randomization parameter in the last data block, the randomized message also includes the random factor as the first data block.
[0019] The described modes of the randomized hashing provide resistance against
various security attacks, such as collision attacks, forgery attacks on the digital signatures due to
collision attacks on the hash functions, fixed point based online forgery attacks on the digital
signatures in birthday complexity and generic online forgery attacks in birthday complexity for
the scenarios where the random value used for signing is also used for randomized hashing.
Since it may not possible for an attacker to predict with a high probability the salt or the random
value to be used by a signer to sign randomized hash of one of the colliding messages, the
attacker cannot find collisions for these randomized hash function modes before signature
computation. Therefore, offline forgery attacks on the digital signatures are not applicable as an
attacker can not make use of an offline collision to query the signer on one of the colliding
messages and show this signature as the one for the other colliding message.
[0020] Further, since the random value always exists in the last block, an attacker who
finds precomputed fixed points must be able to fix the fresh random value to be used by the signer in every signature computation. However, this might not be possible for the attacker for two reasons. Firstly, an attacker should be able to predict the random value to be used by the signer for signing each message query request of the attacker. As mentioned earlier, it is not possible for the attacker to predict the random value with a high probability and thus the attacker may not carry out an online forgery attack. Secondly, the signer uses fresh random value in every signature computation and therefore, the random value in the colliding fixed point block must be exactly the same as the one used by the signer for that particular collision. To summarize, the

attacker may have no control over the random value in the fixed point block although he can control the padding bits by fixing them before the attack and the message bits in the fixed point by xoring them with the random value. Thus, an attacker can not execute fixed point based online forgery attack in birthday complexity. Additionally, in cases where the fresh random value used in every signature generation is also used for randomized hashing, the generic online forgery attacks may be prevented in birthday complexity.
[0021] The above systems and methods are further described in conjunction with the
following. It should be noted that the description and figures merely illustrate the principles of the present subject matter. It will thus be appreciated that various arrangements that embody the principles of the present subject matter, although not explicitly described or shown herein, can be devised from the description and are included within its scope. Moreover, all statements herein reciting principles, aspects, and embodiments of the present subject matter, as well as specific examples thereof, are intended to encompass equivalents thereof.
[0022] Fig. 1 illustrates a computing environment 100 implementing a randomized
message generation (RMG) system 105, according to an embodiment of the present subject
matter. The RMG system 105 may be coupled to a plurality of computing devices 110-1, 110-
2,..110-N via a network 115. The computing devices 110-1, 110-2,…. 110-N may be referred to
as the computing device(s) 110. The network 115 may be a wireless network, wired network or a
combination thereof. The network 115 can be implemented as one of the different types of
networks, such as intranet, local area network (LAN), wide area network (WAN), the internet,
and such. The network 115 may either be a dedicated network or a shared network, which
represents an association of the different types of networks that use a variety of protocols, for
example, Hypertext Transfer Protocol (HTTP), HTTP Secure (HTTPS), Transmission Control
Protocol/Internet Protocol (TCP/IP), etc., to communicate with each other.
[0023] The RMG system 105 and the computing devices 110 can be implemented using
devices that include, but are not limited to, desktop computers, hand-held devices, such as mobile phones, smart phones, touch phones tablets and the like, multiprocessor systems, personal digital assistants (PDAs), laptops, network computers, cloud servers, minicomputers, mainframe computers, and the like.

[0024] For the purpose of explanation, and not as a limitation, the foregoing description
is with reference to implementation of hash functions in digital signature applications. It will be understood that the described systems and methods may be implemented for other information processing applications as well. Further, the computing environment 100 may be understood as a digital signature environment, where the RMG system 105 may be understood as a computing system corresponding to a signer who is to digitally sign a document, which is verified by one of the computing devices 110. Thus, the RMG system 105 may be understood as a signing entity, while the computing devices may be understood as the verifying entity. Additionally, it will be appreciated that the RMG system 105 may be a signing entity in one case and a verifying in other.
[0025] Further, for the sake of clarity, certain notations used herein are explained in this
paragraph. If a and b are any two bit strings then a||b is the concatenation of a and b. For example, if a = 0001 and b = 011 then a||b = 0001||011 = 0001011. Further, for any bit string a, |a| denotes the size of a in bits. For example, let a = 10001011 then |a| = 8 bits. For any bit string a and a positive integer N, aN represents the concatenation of a to itself for N times. For example, 0300 is the concatenation of bit 0 to itself for 300 times. For any bit string a, a[t] denotes the first t most significant bits of a.
[0026] In an implementation, the RMG system 105 includes interface(s) 120 and one or
more processor(s) 125. The interfaces 120 may include a variety of software and hardware interfaces, for example, interfaces for peripheral device(s), such as a keyboard, a mouse, a camera, a microphone, touch pad, and stylus. Further, the interfaces 120 may enable the RMG system 105, to communicate with other computing systems, such as web servers and external databases. The interfaces 120 can facilitate multiple communications within a wide variety of networks, and protocol types, including wired networks, for example, local area network (LAN), cable, etc., and wireless networks, such as Wireless LAN (WLAN), cellular, or satellite. For the purpose, the interfaces 120 may include one or more ports for connecting a number of computing systems to each other or to another server computer.
[0027] The processor 125 may be implemented as one or more microprocessors,
microcomputers, microcontrollers, digital signal processors, central processing units, state

machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor 125 fetches and executes computer-readable instructions stored in a memory.
[0028] The functions of the various elements shown in the figure, including any
functional blocks labeled as “processor(s)”, may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared.
[0029] In another embodiment, the RMG system 105 may include a memory 130. The
memory 130 may be communicatively coupled to the processor 125. The memory 130 may
include any non-transitory computer-readable medium known in the art including, for example,
volatile memory, such as static random access memory (SRAM) and dynamic random access
memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable
programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes.
[0030] Further, the RMG system 105 may include module(s) 135 and data 140. The
modules 135 and the data 140 may be coupled to the processor 125. The modules 135, amongst
other things, include routines, programs, objects, components, data structures, etc., which
perform particular tasks or implement particular abstract data types. The modules 135 may also
be implemented as, signal processor(s), state machine(s), logic circuitries, and/or any other
device or component that manipulate signals based on operational instructions.
[0031] Further, the modules 135 can be implemented in hardware, instructions executed
by a processing unit, or by a combination thereof. The processing unit can comprise a computer, a processor, a state machine, a logic array or any other suitable devices capable of processing instructions. The processing unit can be a general-purpose processor which executes instructions to cause the general-purpose processor to perform the required tasks or, the processing unit can be dedicated to perform the required functions.
[0032] In another aspect of the present subject matter, the modules 135 may be machine-
readable instructions (software) which, when executed by a processor/processing unit, perform

any of the described functionalities. The machine-readable instructions may be stored on an electronic memory device, hard disk, optical disk or other machine-readable storage medium or non-transitory medium. In one implementation, the machine-readable instructions can be also be downloaded to the storage medium via a network connection.
[0033] Further, the data 140 serves, amongst other things, as a repository for storing data
processed, received, and generated by one or more of the modules 135. The modules 135 further include, for example, a primary randomization module 145, a secondary randomization module 150, and other module(s) 155. The other modules 155 may include programs that supplement applications on the RMG system 105, for example, programs in the operating system. It will be understood that the certain modules may be provided on separate devices, which in combination may form the RMG system 105. The data 140 includes, for example, random values 160 and other data 165. The other data 165 may include data generated as a result of the execution of one or more modules in the other modules 155.
[0034] Consider that the RMG system 105 is corresponding to a signer, who is to
digitally sign a document and provide to a verifying entity, say, computing device 110, which verifies the digital signature for authenticity. To ensure security and efficient application of the digital signature the RMG system 105 may employ a cryptographic hashing function, such as SHA-1. Further, the RMG system 105 may receive the document to be signed, or in other words a message, and generate a corresponding randomized message. The RMG system 105 may employ a cryptographic hash function such that the cryptographic hash function and its compression function are not vulnerable to attacks, such as short-cut second preimage attacks and related attacks that contradict second preimage resistance of the compression function or hash function and any property related to the second preimage resistance of the compression function and hash function. In an example, the digital signature may be generated using a standard digital signature algorithm, such as DSA or ECDSA. The cryptographic hash function may have a framework based on Merkle-Damgård construction. Further, the cryptographic hash functions may include a compression function, for example, a compression function based on Davies-Meyer construction, such as SHA-1, which is a single block length block cipher based compression function. Upon receiving a message to be hashed, the primary randomization

module 145 may obtain a random value, also referred to as salt, prior to computation of the message digest and generation of the corresponding digital signature. The obtained random value may be stored in the random values 160. In an example, the random value has a bit size of at least 128 bits and at most equivalent to a block length of the compression function. The random value may be generated based on a randomization criterion. In an implementation, the randomization criterion may be to reuse the random value generated as part of the signature process for message randomization purpose. In such a case there is no need to generate a new random value for message randomization and communicate to the verifying entity. Further, the same random value may also be used by digital signature schemes, such as digital signature algorithms (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) as part of the signature. In an example, the primary randomization module 145 implements a random number generator of DSA or ECDSA to generate a secret random number, which is protected from unauthorized disclosure and modification. It will be understood that for each message a separate secret random number may generated. For example, the random number may be derived from the secret random number using a procedure outlined as part of the DSA signature generation. In said example, a random value r is computed from a per-message secret random number k by using the expression r = gk mod q where mod is a modulus operator and q is a prime divisor of p-1 such that 2N-1 < q < 2N where N is the bit length of q and p is a prime modulus such that 2L-1 < p < 2L. The standard choices of L and N are provided in Section 4.2 of DSS FIPS 186-3. This random value r may also be used for randomized hashing and it is also part of the signature to be sent to the verifier. Although generation of the random value r has been explained in detail with respect to DSA, it will be understood that other techniques and procedures may also be used, for example, procedures based on ECDSA.
[0035] In another implementation, in case the signature scheme employed by the signing
entity does not generate the random value, the randomization criterion may specify that the random value is to be generated. In this scenario, the primary randomization module 145 may include a random bit generator, for example, random bit generators as specified in NIST’s Special Publication (SP) 800-90 standard [SP 800-90]. In said implementation, the random value may be communicated to the verifying entity along with the digital signature.

[0036] Upon obtaining the random value, the primary randomization module 145 may
concatenate the random value to itself a predetermined number of times, based on a block length of the compression function being employed by the cryptographic hash function to obtain a concatenated random value, which may also be stored in the random values 160. The random value may be concatenated to itself such that the bit size of the concatenated random value is equivalent to the block length of the compression function. For example, a 128-bit random value is concatenated to itself four times to obtain a 512-bit random value which is the block length of the compression functions of hash functions SHA-1 and SHA-256. Further, the primary randomization module 145 may divide the message into a predetermined number of data blocks based on the block size of the compression function. The predetermined number of data blocks may be computed such that a bit size of each of the data blocks is equivalent to the block length of the compression function. In an example, the last block of the message may contain fewer bits than the block length of the compression function.
[0037] Further, once the message is divided in to the predetermined number of data
blocks, the secondary randomization module 150 may randomize each of the data blocks based on the concatenated random value. In an example, each of the data blocks may be mixed with concatenated random value using a mixing function. This ensures that every bit of the message is randomized. For instance, an exclusive-or (XOR) operation may be the mixing function and XOR operation may be performed between each of the data blocks and the concatenated random value. For example, if a message, M, contains three data blocks, where M = M1|| M2|| M3 and each block is of 512 bits. Further, consider a random value r, where |r|= 128 bits, then concatenated random value will be r4, which will be the concatenation of r for four times so that |r4| is 512 bits, then the message may be randomized using the randomization criterion, which may represented as:
(M1 xor r4) || (M2 xor r4) || (M3 xor r4). Though XOR operation has been used in the present example, it will be understood that any mixing function that provides for sufficient randomization to ensure security without complicating the process and compromising the efficiency may be used.

[0038] Further, upon randomizing each of the data blocks, the secondary randomization
module 150 determines whether a current last block of the message has enough space to accommodate a randomization parameter to obtain a randomized message and the padding bits required by the hash function. The randomization parameter is based on the random value and provides for randomization of the last data block. In an implementation, the padding bits include a bit 1 followed by bits that represent an original length of the message in the binary encoded format. The bit size of this binary encoded format depends on the hash function being used. For example, if the hash function is SHA-1, then the size of the original message is represented in a 64-bit encoded format. For instance, if the original message is abc which is 24 bits in length then the number 24 is represented in the binary encoded format as 000....0011000 which is a 64-bit representation of abc.
[0039] Further, the secondary randomization module 150 may determine a bit size of the
random value. For example, the secondary randomization module 150 may determine the bit size of the random value such that the minimum value is 128 bits and maximum value is of the block size of the compression function. The secondary randomization module 150 may compute a sum total of the bit size of the random value and the minimum bit size of the padding bits to determine if the available space in the current data block can accommodate the padding bits and the random value. If the sum total is greater than the available space, an additional data block may be appended to the end of the message. It will be understood that the appended data block serves as the last data block of the message and may contain the repetitions of the random value r until the starting position of the padding bits. Further, this repetitive random value may provide randomization parameter. To determine the randomization parameter, the secondary randomization module 150 may determine a number of bits available after adding the padding bits to the last data block. In an example, the last block includes the random value until a position from where the padding bits start. Thus, based on the number of bits available after considering the padding bits, the random value may be concatenated to itself. In case the number of bits is just enough to accommodate the random value, the random value may not be concatenated to itself and the random value itself serves as the randomization parameter. In another case, where

the random value is to be concatenated, the concatenated random value serves as the randomization parameter.
[0040] Further, if the sum total of the bit size of the random value and the bit size of the
padding bits is less than or equal to the available space, no additional data block may be appended. In such a case, the last data block may include message bits already present in the last data block mixed with the random value using the mixing function and the randomization parameter that may include repetition of the random value to a necessary length. In addition the last block includes the padding bits.
[0041] Referring to the example mentioned above, considering that an additional data
block is added and 512 bits are available. As computed above, the bit size of the padding bits is 65 bits. In said example, 447 bits may be used for the randomization parameter and 65 bits may be used for padding bits. Thus, the random value may be concatenated to itself to obtain the randomization parameter, which is 447 bits long. Further, the previous block, i.e., the second last data block, which may contain fewer than 512 bits of the message mixed with the random value, may also contain randomization parameter whose size depends on the number of message bits available. Additionally, the size of the randomization parameter would be less than the sum of |r| and minimum size of the padding bits.
[0042] Additionally, the secondary randomization module 150 may further prepend a
data block, which serves as the first data block for the randomized message. The first data block includes a random factor, which is computed based on the random value and a block length of the compression function. In an example, the first data block may include the random value concatenated to itself the predetermined number of times based on the block length of the compression function. For instance, the random value is concatenated to itself the predetermined number of times such that the bit size of the concatenated random value is equivalent to the block length of the compression function. In said example, this concatenated random value may serve as the random factor. In another example, in the first block instead of repeating the random value to fill in the block, a predetermined number of zeros may be appended to the random value to make a first block. It will be understood that the predetermined number of zeroes may be determined based on the block length of the compression function and the bit size of the random

value. The predetermined number of zeroes may be determined based on the available space in
the first data block after considering the random value. In said example, the random value having
predetermined number of zeroes appended to it may be taken as the random factor.
[0043] In an implementation, the secondary randomization module 150 may hash the
randomized message to obtain the message digest. Further, using the message digest, the digital signature may be obtained by applying a signature technique used for generating the digital signatures, such as the standard DSA algorithm. The digital signature, the message, and the random value, which may be part of the digital signature itself, may be transmitted to the verifying entity, such as the computing device 110. The computing device 110 may in turn verify the digital signature by using a verifying algorithm.
[0044] Thus, the randomization mode where the randomization is suffixed to the message
and subsequent hashing described above may be illustrated as:

where SRMX(r, M) is the randomness mode, r is the random value, M1.... ML are the individual data blocks of the message M according to the block size of the compression function f of the cryptographic hash function H, || is the concatenation operator, and is the linear XOR mixing function, and pad denotes padding bits.
[0045] In the above illustration it is assumed that a length of the message M is an integral
multiple of the block length of the compression function f and hence message M can be split into
the blocks M1, M2 ML of equal length. In one example, the last data block ML+1 includes the
randomization parameter and padding bits. For instance, if | ML | = 512 bits then ML is xored with
[ 319]
r512 and ML+1 = r512 || padding bits. In an alternate illustration (not shown), the last data block may also include the message bits that were part of the message. For instance, if | ML | ≤ 319 bits

then ML is xored with concatenated random value and this xored value is appended with the
randomization parameter, which may include random value, r, concatenated to itself for
sufficient number of times followed by the appending of 65-bit padding. Thus, in said example
there may be no need to append an extra data block ML+1 and ML serves as the last data block.
[0046] Considering the case, where the randomness is not only suffixed, but also
prefixed, the randomness mode of the cryptographic hash function may be illustrated as:

where PSRMX(r, M) is the randomness mode where randomness is both suffixed and prefixed, r
is the random value, M1.... ML are the individual data blocks of the message M according to the
block size of the compression function f of the cryptographic hash function H, || is the
concatenation operator, and is the linear XOR mixing function, and pad denotes padding bits.
[0047] Thus, the present subject matter describes randomization hash function modes
that provide enhanced security in the information processing applications, such as digital signatures. Further, according to the present subject matter, the randomness may be appended towards the end of the message, in addition to randomness applied to the rest of the message blocks. Additionally, the randomness may not only be suffixed, but may also be prefixed to the message. The addition of randomness at the end of the message in both these modes prevents online birthday forgery attacks that exploit fixed points in the compression functions of SHA family of hash functions. Since, the random value is chosen by the signing entity and is freshly generated for each digital signature, the attacker can not predict the random value. That is, although an attacker can find birthday number of fixed points and do a collision matching with the randomized hash values, after they are signed and the corresponding digital signatures are sent to the attacker, the attacker cannot use the random value for which online birthday collision

took place in the last data block as that would change the precomputed fixed point block for which collision occurred.
[0048] Also, the generic online forgery attacks may be prevented for the applications
where the random value generated for signing is also used for randomized hashing because the signature verification algorithm fails if a different random value is used during verification compared to the one used by the signer. For this usage, an attacker must contradict Target Collision Resistance (TCR) property of the hash function, where the attacker first chooses a message M and then he is given a random value r. Subsequently, the task of the attacker is to find N such that H(PSRMX(r,M)) = H(PSRMX(r,N)) or H(SRMX(r,M)) = H(SRMX(r,N)). However, by using online queries it is not possible for an attacker to break this property in birthday complexity for the described randomization modes, H(PSRMX(r,M)) or H(SRMX(r,M)), even if the compression function has fixed points. Therefore, the attacker has to break the second preimage resistance property of the hash function or compression function or a related property in order to break the TCR property of the proposed randomized hash function modes. However, generic attacks on the proposed randomized hash functions can be performed in birthday complexity to compromise the e-TCR property where the attacker first chooses a message M and then he is given a random value r. Subsequently, the task of the attacker is to find the pair (r', N) such that H(PSRMX(r,M)) = H(PSRMX(r',N)) or H(SRMX(r,M)) = H(SRMX(r',N)), where (r,M) is not equal to (r',N). Nevertheless, contradicting this property in birthday complexity does not help the attacker to forge digital signatures, where the same salt is used for both hashing and signing, which is the main application for which protection is sought against birthday online forgery attacks as well as forgery attacks due to offline collisions in the hash functions. If a particular signature scheme has no option of using the random value generated by the signature scheme also for the hashing, the random value has to be generated explicitly for the hashing purpose. Further, the generated random value may also need to be signed along with the hash value for TCR property to hold, for the randomization mode where randomness is only appended at the end, i.e., SRMX. In such cases, signing of both the random value and the hash value may require changes to the standard signature algorithms, which may not be feasible. Further, in this scenario, the digital signature application may require an e-TCR

property of the randomized hash function mode. Furthermore, the randomization mode having randomness appended at the end as well as the beginning, i.e., PSRMX may offer better resistance against short-cut attacks that aim to break e-TCR property. This may be because an attacker has to exercise control not only over the message mixing and suffix parts but also prefix, parts in case of PSRMX. In addition, the generic second preimage attacks that make use of expandable messages requiring far higher than birthday complexity are applicable on the presented randomized hash function modes.
[0049] Further, corporate sectors that use of cryptographic libraries of software
frameworks that do not support stronger hash functions, may employ the described mode of
randomized hash functions until migration to stronger hash functions, such as SHA-256, takes
place. Further, the described mode of randomized hashing may also be integrated with the
stronger hash functions providing stronger security for digital signature applications..
[0050] Fig. 2 illustrates a method 200 for generating randomized messages used for
obtaining a message digest, in accordance with an implementation of the present subject matter.
[0051] The method may be described in the general context of computer executable
instructions. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, functions, etc., that perform particular functions or implement particular abstract data types. The method may also be practiced in a distributed computing environment where functions are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, computer executable instructions may be located in both local and remote computer storage media, including memory storage devices.
[0052] The order in which the method is described is not intended to be construed as a
limitation, and any number of the described method blocks can be combined in any order to implement the method, or an alternative method. Additionally, individual blocks may be deleted from the methods without departing from the spirit and scope of the subject matter described herein. Furthermore, the method can be implemented in any suitable hardware, software, firmware, or combination thereof.

[0053] At block 205, a message to be hashed using a hash function employed by a
computing system, such as the random message generation system, may be received. For example, the message may be a document to by digitally signed by a signer associated with the computing system.
[0054] At block 210, a block length of a compression function of the hash function may
be determined. For example, the primary randomization module 145 may determine the block length of the compression function.
[0055] At block 215, the message is divided into a predetermined number of data blocks
based on the block length of the compression function. The predetermined number of data blocks may be computed such that a bit size of each of the data blocks is equivalent to the block length of the compression function. For example, the primary randomization module 145 may divide the message into the predetermined number of data blocks.
[0056] At block 220, a random value for randomizing the message may be obtained
based on a randomization criterion. The randomization criterion may define whether random value generated for a signature algorithm can be used or a different one is to be generated. For example, the primary randomization module 145 may obtain the random value based on the randomization criterion.
[0057] At block 225, the random value is concatenated to itself a predetermined number
of times based on the block length of the compression function. In an example, the random value may be concatenated to itself such that the bit size of the concatenated random value is equivalent to the block length of the compression function. In an implementation, the primary randomization module 145 may concatenate the random value the predetermined number of times to obtain the concatenated random value.
[0058] At block 230, each of the predetermined number of data blocks of the message is
randomized using the concatenated random value. For example, a mixing function may be used to mix the bits in the data blocks with the concatenated random value for randomizing the message. In an implementation, the secondary randomization module 150 may randomize the data blocks using the concatenated random value.

[0059] At block 235, it is ascertained whether a current last data block of the message
can accommodate a randomization parameter. Additionally, it may be determined whether the last data block can accommodate padding bits. The randomization parameter may be computed using the random value. Based on the space available in the last block, the randomization parameter may be the random value itself or may include the random value concatenated to itself a predetermined number of times. The padding bits may include a bit 1 followed by bits that represent an original length of the message in the binary encoded format. In an implementation, the secondary randomization module 150 may ascertain whether the current last data block of the message can accommodate a randomization parameter. If it is determined that the current last data block of the message can not accommodate the randomization parameter, the method 200 proceeds to (‘No branch’) block 240.
[0060] At block 240, an additional data block is appended at the end of the message,
which now serves as the last data block of the message. The additional data block has a bit size
equivalent to the block length of the compression function. In an implementation, the secondary
randomization module 150 may append the additional data block to the message.
[0061] If at block 235, it is determined that the current last block can accommodate the
randomization parameter, the method 200 proceeds to (‘Yes’ branch) block 245. At block 245, the randomization parameter is populated in the last block of the message to obtain the randomized message. It will be understood that in cases where no additional data block is appended, the current last block is the data block to which the randomization parameter is populated; and the cases where the additional data block is appended, the randomization parameter is populated in the newly added data block.
[0062] In an implementation, in addition to appending randomness in the last data block,
another data block may be prepended at the beginning of the message to obtain the randomized message. At block 250, a first data block may be populated with a random factor to obtain the randomized message. The random factor is computed based on the random value obtained at block 220 and the block length of the compression function obtained at block 210. For instance, random factor may be the concatenated random value determined at block 225. In another example, the random factor may include a predetermined number of zeroes appended to the

random value. In an implementation, the secondary randomization module 150 may append this
new data block as the first block of the message.
[0063] Further, the randomized message may be used as an input by the hash function
provide a message digest, which in turn may serve as input for the DSA.
[0064] Although embodiments for generation of randomized messages have been
described in a language specific to the structural features and/or methods, it is understood that
the invention is not necessarily limited to the specific features or methods described. Rather, the
specific features and methods are disclosed as exemplary embodiments for generation of
randomized messages.
References:
1. Elaine Barker and John Kelsey. NIST Special Publication 800-90A.
Recommendation for Random Number Generation Using Deterministic Random Bit Generators, 2012. http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
2. Quynh Dang. NIST Special-Publication 800-106 Randomized Hashing for Digital Signatures,
2009.
http://csrc.nist.gov/publications/nistpubs/800-106/NIST-SP-800-106.pdf
3. Praveen Gauravaram and Lars R. Knudsen. On Randomizing Hash Functions to Strengthen the Security of Digital Signatures. In Advances in Cryptology – EUROCRYPT 2009, A. Joux, Ed. Lecture Notes in Computer Science, vol. 5479. Springer, Pages 88–105, 2009.
4. Praveen Gauravaram and Lars R. Knudsen. Security Analysis of Randomize-Hash-then-Sign Digital Signatures. Journal of Cryptology 25(4), pages 748-779, 2012.
5. National Institute of Standards and Technology (NIST), Federal Information Processing Standard (FIPS PUB 180-4) Secure Hash Standard, 2012. http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf
6. National Institute of Standards and Technology (NIST), Federal Information Processing Standard (FIPS PUB 186-3) Digital Signature Standard (DSS), 2009. Available at http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
7. Shai Halevi and Hugo Krawczyk. Strengthening Digital Signatures Via Randomized Hashing. In Advances in Cryptology – CRYPTO 2006, C. Dwork, Ed. Lecture Notes in Computer Science, vol. 4117.

Springer, Pages 41–59, 2006. Full version is at http://webee.technion.ac.il/~hugo/rhash/rhash.pdf
8. Shai Halevi and Hugo Krawczyk. The RMX Transform and Digital Signatures. Available at http://www.ee.technion.ac.il/~hugo/rhash/rhash-nist.pdf, 2006.
9. John Kelsey and Bruce Schneier. Second preimages on n-bit Hash Functions for Much Less than 2n Work. In Advances in Cryptology-EUROCRYPT 2005, R. Cramer, Ed. Lecture Notes in Computer Science, vol. 3494. Springer, pages 474-490, 2005.
10. Xioyun Wang and Hongbo Yu. How to Break MD5 and Other Hash Functions. In Advances in Cryptology-EUROCRYPT 2005, R. Cramer, Ed. Lecture Notes in Computer Science, vol. 3494. Springer, pages 19–35, 2005.
11. Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu. Finding Collisions in the Full SHA-1. In Advances in Cryptology-CRYPTO 2005, V. Shoup, Ed. Lecture Notes in Computer Science, vol. 3621. Springer, pages 17-36, 2005.

I/We claim:
1. A randomized message generation system (105) comprising::
processor(s) (125);
a primary randomization module (145) coupled to the processors (125), the primary randomization module (145) obtains a random value based on a randomization criterion to randomize a message; and
a secondary randomization module (150) coupled to the processors (125), the secondary randomization module (150) populates a last data block of the message with a randomization parameter to obtain a randomized message for use in a cryptographic hash function, wherein the randomization parameter is computed using the random value.
2. The randomized message generation system (105) as claimed in claim 1, wherein the
secondary randomization module (150) further determines:
space occupied by padding bits in the last data block;
available space in the last data block based on the space occupied by the padding bits and message bits in the last data block to compute the randomization parameter.
3. The randomized message generation system (105) as claimed in claim 1, wherein the primary
randomization module (145) is further:
determines a block length of a compression function, wherein the compression function is a component of the cryptographic hash function used for hashing the randomized message;
divides the message into a predetermined number of data blocks based on the block length of the compression function; and
concatenates the random value to itself a predetermined number of times, based on the block length of the compression function.
4. The randomized message generation system (105) as claimed in claim 3, wherein the secondary randomization module (150) randomizes each of the predetermined number of data blocks using the concatenated random value, wherein the concatenated random value is mixed with a data block using a mixing function.
5. The randomized message generation system (105) as claimed in claim 1, wherein the secondary randomization module (150) is further:

ascertains whether a current last block of the message can accommodate the randomization parameter; and
appends an additional data block at the end of the message, when the current last block can not accommodate the randomization parameter.
6. The randomized message generation system (105) as claimed in claim 1, wherein the
secondary randomization module (150) is further:
appends a data block at the beginning of the message; and
populates the data block with a random factor, wherein the random factor is based on the random value and a block length of a compression function.
7. A method for generating randomized messages for cryptographic hash functions comprising:
obtaining a random value based on a randomization criterion to randomize a message; and
populating a last data block of the message with a randomization parameter to obtain a randomized message, wherein the randomization parameter is computed using the random value.
8. The method for generating randomized messages as claimed in claim 7, wherein the last data block further includes padding bits.
9. The method for generating randomized messages as claimed in claim 7, wherein the method further comprises:
ascertaining whether a current last block of the message can accommodate the randomization parameter; and
appending an additional data block at the end of the message, when the current last block can not accommodate the randomization parameter.
10. The method for generating randomized messages as claimed in claim 7, wherein the method
further comprises:
dividing the message into a predetermined number of data blocks based on the block length of a compression function;
concatenating the random value to itself a predetermined number of times, based on the block length; and

randomizing each of the predetermined number of data blocks using the concatenated random value.
11. The method for generating randomized messages as claimed in claim 7, wherein the method
further comprises:
appending a data block at the beginning of the message; and
populating the data block with a random factor, wherein the random factor is based on the random value and a block length of a compression function.
12. A non-transitory computer-readable medium having embodied thereon a computer program
for executing a method for authenticating a user, the method comprising:
obtaining a random value based on a randomization criterion to randomize a message; and
populating a last data block of the message with a randomization parameter to obtain a randomized message, wherein the randomization parameter is computed using the random value.