BHA-160: Constructional Design of Hash Function based on NP-hard

Problem

Ali AlShahrani
Faculty of Computing Studies, Arab Open University
Riyadh, Saudi Arabia
a.shahrani@arabou.edu.sa

Abstract theory. Generally, Braid Groups had been widely used

as a tool to create various cryptographic primitives.
Secure hash function is used to protect the integrity There are a few of them such as a public key
of the message transferred on the unsecured network. cryptosystem, key exchange, authentication and digital
Changes on the bits of the sender’s message are signature [2] [3]. Creating an ideal hash function using
recognised by the message digest produced by the hash braid groups is connected to the general question of
function. Hash function is mainly concerned with data finding a function to map the braid groups to the
integrity, where the data receiver needs to verify sequence of {0,1}. The result of the secured hash
whether the message has been altered by function must be random enough and reveal no
eavesdropping by checking the hash value appended information about the argument of the hash function.
with the message. To achieve this purpose, we have to
use a secure hash function that is able to calculate the The objective of this paper, therefore, is to create a
hash value of any message. In this paper, we introduce secured hash function based on braid group's theory.
an alternative hash function based on NP-hard The mechanism used in the core of this function is the
problem. The chosen NP-hard problem is known as braid multiplication, by which we multiply a pre-
Braid Conjugacy problem. This problem has proved to defined braid by the braid generated from message
be secure against cryptanalysis attacks. transformation (transformation of the message's content
to a braid form). However, the designed hash function
then can be attached to any cryptosystem for message
1. Introduction integrity purposes with a high level of security.

Hash function is the core of any cryptosystem. It is

used for message integrity or for authenticating the data 2. Literature Review
exchanging process between the connected parties. The
design of a secure hash function consists of a special Hash functions have been applied for many security
one-way function that receives any variable length applications and protocols such as PGP, SSL, SSH,
input and produces a fixed length output. A one-way IPsec, TLS and S/MIME [4]. In order to provide these
function is defined as a function that can simply take applications with a high level of security, we have to
the input message and compute (generate) the design a secure hash function against existing attacks.
corresponding hash value, but, it is computationally Let us now discuss the following scenario to
infeasible to recover the original message using the understand the usage of a hash function: Alice wants to
hash value. A hash function is called ideal if the hash send a message m to Bob. Alice needs to use the hash
value h cannot be distinguished from the values given function Fh to calculate the hash value h of her message
by a random oracle [1]. such that Fh(m) = h, and appends the hash value h with
the message. On the other hand, Bob (the receiver)
Apart from hash functions, some cryptosystems are needs to recalculate h using the same hash function. By
dependent on mathematically hard problems. An comparing the two hash values, Bob can judge whether
example of a mathematical hard problem is the braid
the message has been altered or not. The message different primitive logical function. According to the
considered "Altered" if Fh(m)Alice ≠ Fh(m)Bob. research done by [10] and [11], MD5 is not secure to
be used in a security applications since it is not
The strength of any hash function can be measured collision-free. Therefore, MD5 in no longer
by the complexity of its calculation and operation [5]. recommended for new applications where collision-
Recently, cryptosystems aimed to use some resistance is required.
mathematical NP-hard problems in order to increase MD2 and MD5 are meant for digital signature
the complexity of their structure against the attackers. applications where a large message has to be
A problem is assigned to the NP (Nondeterministic "compressed" in a secure manner. They are classified
Polynomial time) - hard problem class, if it is solvable in a bit-operations based hash function category, since
in polynomial time by a nondeterministic oracle they depend on crossing, shifting and addition to the
machine. Therefore, if we built a hash function based message's bits.
on a NP-hard problem, we will certain that the
attackers cannot attack this function since it is based on The Secure Hash Algorithm (SHA-1) is another
a "hard-to solve" mathematical problem. example of hash algorithms. It is one of the most
widely used hash functions in the world. Indeed, four
more variants have since been issued with increased
2.1 Hash Function output range and a slightly different design: SHA-224,
SHA-256, SHA-384 and SHA-512 (sometimes they are
A hash function Fh, is a transformation that takes an collectively referred as SHA-2). However, SHA-1
arbitrary size input m, and returns with a string of a takes a message with a maximum less than 264 as an
fixed size, which is called the hash value h (where h = input producing a 160-bit message digest.
Fh(m)) [6].
The overall process of SHA-1 consists of five steps,
A cryptographically secure hash function should starting from appending some of the padding bits to
have the basic requirements in its design, which are: make the message congruent to a 448 modulo 512,
 Fh can be applied to an input of data of any size. ending with a 160-bit message digest. Through these
 Fh produces a fixed-length of output. steps, the message length must be appended to the
 Fh (m) is relatively easy to compute for any given message as well as XOR operations being applied to
the message's bits.
m.
 Fh (m) is one-way. Research done by Chinese researchers showed that
 Fh (m) is collision-free. SHA-1 has been broken [12]. They presented new
collision search attacks on the hash function SHA-1
and showed that the collision of SHA-1 can be found
MD2, MD5 and SHA [7] are good examples of well with a complexity of less than 269.
known hash functions. In 1989, Ron Rivest introduced
the MD2 Message Digest Algorithm that takes as input, 2.2 Braid Group
a message of arbitrary length and produces as output, a
128-bit message digest by appending some redundancy The second category of our hash function's
to the message, and then iteratively applies 32 bytes to classification is the hash function based on the NP-hard
16 bytes compression function. Researches done by [8] problem. In this category, the heart of the hash function
and [9] proved that the MD2 is not a one-way function, depends on a mathematical nondeterministic
therefore, it is not collision-free and they also showed polynomial-time hard problem.
that it does not reach the ideal security level of 2128.
However, the use of MD2 for new applications is Braid groups had been widely used as a tool to
discouraged. create various cryptographical primitives. There are a
few of them, such as a public key cryptosystem, key
Similarly, MD5 takes as input, a message of exchange, authentication and digital signature.
arbitrary length and produces a 128-bit message digest, However, Conjugacy Problems are NP-hard problems
however, it is aimed at 32-bit machines instead of 8-bit in braid group theory. We say that braid a and b are
machines in MD2. The algorithm consists of four conjugate if we have a = s b s-1 for some braid s.
distinct rounds with a similar structure, but each uses a Conjugacy Search Problem is one of the conjugacy
problems in braid theory. This problem lies, that for but should also include the mathematical hard
some braids (a,b) є Bn X Bn (where Bn is braid group) problems. We have found that the braid group’s theory
is the best way to do this, as it provides mathematical
such that x and y are conjugate, find r є Bn such that b hard problems and also some advantages in
= rar-1. computational aspects.

Any braid can be decomposed as a product of The proposed structure consists of an initial vector
simple braids. One type of simple braid is the Artin called initial braid and blocks of text (represented as
generators σi, these have a single crossing between i-th braid) to be the inputted into the hash function. We
and (i+1)-st strand as in Figure 1. Besides, the n-braid apply a braid operation (multiplication) on the braid
group Bn can be presented by the Artin generators groups to concentrate two different braids that then
produce a completely new unique braid. By repeating
σ1,…, σn -1 and relations σi σj = σj σi for |i - j| > 1 and
this process, we will get a random braid that cannot be
σi σj σi = σj σi σj for |i - j| = 1. traced back to get the initial value of the hash function.
n This condition is able to fulfill the important properties
of a secured hash function.
i+1
i The architecture of the proposed hash function will
follow the steps as follows as in Figure 2:
1
 Generate a random braid BIV, to be as an initial
vector of the hash function.
Figure 1: Artin generator σi  Generate another braid by manipulating the bits
from the text blocks.
Many operations can be applied on two braids. For  Do a multiplication operation on the initial braid
example, braid multiplication is the most used and the braid generated beforehand.
operation over braid. The multiplication of braids a by  Repeat the iteration until the last text blocks.
b where (a,b) є Bn results in a new braid which is
unique. The process of ascertaining the original two
braids (braid a and b), given the resulted braid after the Plain Text Blocks p0 P1 P2 .... pn
multiplication, is known to be a hard-problem. The
multiplication of two braids is carried out by placing F(x)
the braid a under the braid b. Di Bi
Braid Braid
As we previously mentioned, many cryptosystem's B
IV Groups Groups
primitives have been built on braid group theory, but
no hash function based on braid has been implemented
yet. However, many researches are done in the braid
group, and most of these researches showed the Braid Multiplication
strength of this theory against attacks.

Di+1
3. The Proposed BHA-160 Hash Function
Reduce Braid to 160-bit
Architecture
Currently, most of the existing hash functions are
focusing on scrambling and shifting of the bits in the Message
input blocks. With the intention of randomizing the bits Digest Di+1
of the input blocks, usually they are using the exclusive
OR (XOR) operation, and some additions in their
implementation. For our work, we proposed a new
approach of hash function architecture. In our opinion, Figure 2: Architecture of the proposed hash
hash function is not just scrambling or shifting the bits, function (BHA-160)
3.1 BHA-160 Processing Stages  Stage 2: Convert to Artin Generators, σ
This process is the beginning of mapping the input into
The algorithm of BHA-160, takes as input a a braid representation. As we can see in Figure 5, B[i]
message of arbitrary length thereby producing as represents the braid index or, in other words, the
output, a 160-bit message digest. The input is location where crossing occurs in braid groups.
processed in 192 bit blocks. The combined braid, as
illustrated in the architecture, is achieved from the By mapping the input into a braid representation, we
braid multiplication and will be processed in order to need to calculate the value of the crossing. With the
reduce the size of the digest to 160-bit. The overall number of strands n = 128, we convert the first 7 bits
processing of a message to produce a digest consists of from binary to positive decimal. The 8th bit indicates
four stages. The stages are: the sign of the number that can be negative or positive.
The positive sign indicates a positive crossing and the
 Stage 1: Append Padding Bits negative sign indicates a negative crossing.
The 192 bit block is padded to make sure the length is
always in the desired length. The padding process is 8 bit
done by taking the first 8-bit block from the input ....
message (which is less from the desired length) and
then cyclic left shift the bits of the block by 2 bits as B=1 B=2 B=3 B=12
shown in Figure 3.

σB[1] σB[2] σB[3] σB[12]

11010100 .... 01010011 01001101 00110101
Figure 5: Relation between blocks of bits with
Artin generators

192-bit
 Stage 3: Braids Multiplication
Figure 3: Padding process for BHA-160 The inputs of this stage are two braids with 12-byte
size (12 crossing). The first braid represents the plain
After appending the padding bits, we will XOR every text block after the transformation (transforming the
8-bit in 192-bit block. The result of this stage is 12 8- plain text block to Artin representation Bi. The second
bit blocks. Figure 4 presents the input setup of BHA- braid will be the initial value of BIV that is represented
160 in the first stage. as braids Di with 24-byte (BIV that will be used for one
time only, in the beginning of this stage). However, the
192 BIT initial value of Di will be reduced to 12-byte size to be

8 bit
multiplied by Bi. The braid reduction occurs by
.... XORing D2i-1 and D2i for all values of 1≤ i ≤12.
Therefore, the resulted braid, after reduction, is a 12-
byte braid size which is represented as D'i.
Xor Xor

The combined braid, resulted from multiplying the two

braids D'i and Bi as shown in Figure 6, will therefore
....
be in the size ranging from 0-24 crossing, since there is
B=1 B=2 B=12 a possibility for zero crossing. However, the combined
braid then will be multiplied by the next input block
Figure 4: Input Setup of BHA-160 after reduction to 12-byte instead of using the same
value of BIV.
 Stage 4: Message Digest Reduction and 4. Performance Analysis
Production
This is the final stage where we produce the message The performance of BHA-160 is examined against
digest of the corresponding plain text. However, this well-known hash functions, including: MD2, MD5,
stage will be executed when we reach the last input SHA-1, SHA-256, SHA-512. The experiment at each
block. The output will be in the size of 192-bit, point is the mean of 10 measurements. The experiments
meanwhile, we are looking for 160-bit size. Therefore, of all hash functions are implemented on Core i7-
we will reduce the output size to 160-bit by keeping the 4500U of a CPU of 2.4GHz, running Java 6 under
first 160-bit and ignoring the remaining bits as portrait Windows 7. The performance results are presented in
in Figure 7. Figure 8.

Di
σD1 σD2 .... σD24

D'i = D2i-1 D2i

D'i σD'1 .... σD'12 σB1 .... σB12 Bi

12 - Crossing 12 - Crossing

Di+1
Figure 8: Performance of standard hash functions
σD1 σD2 σD3 .............. σD24 against BHA-160
.
0 – 24 Crossing
The performance results shows that our BHA-160 is in
the middle class, where it could outperform MD2 and it
X: Braid Multiplication is almost close to the performance of other functions.
However, we realised that a tradeoff between security
Figure 6: Braid Multiplication and performance exists. Manipulating braids includes
performing complex mathematical operations. In
addition, the key size of BHA-160 is relatively larger
than the key size used by most of the hash functions
192 - BIT
included in this study.
σD1 σD2 σD3 .............. σD20 .... σD24
. ..

5. Discussion
160 - BIT Two important parameters should be discussed, they
σD1 σD2 σD3 .............. σD20 are: the security and the performance of the proposed
. architecture. In terms of security, the 8-bit block of
plain text will produce an Artin representation of a
Figure 7: Message Digest Reduction string in a 128 braid (27=128), which is big enough for
security purposes, since the advice size for braid to be
used for cryptography purposes is an 80 strings braid.
Mathematically, the braid theory proved to be secure
since it is virtually impossible to retrieve one of the [6] Y. Cui, J. Jiang, Z. Lai, Z. Hu, W. Wong, Supervised
multiplied braids after a braid multiplication operation. discrete discriminant hashing for image retrieval,
Pattern Recognition, Volume 78, June 2018, Pages 79-
90.
In terms of performance, a block of 192-bit will require
one braid multiplication of two 128-strings braids, and [7] W. Stalling, Cryptography and network security:
24 XOR operations. This can be considered a minimal
operation that needs to be applied on every 192-bit principles and practices, Prentice Hall 2nd ED. 1999.
plain text block.
[8] N. Rogier and Chauvaud, The Compression Function of
MD2 is not Collision Free, Selected Areas in
Cryptography '95, 1995.
5. Conclusions
In conclusion, there is a presentation of less security [9] F. Muller, The MD2 Hash Function is not One-Way,
level by bit-operations harsh functions that have a Advanced in Cryptology-Asia Crypt '2004, 2004.
dependence on bits of XORing message as compared to
[10] V. Klima, Finding MD5 Collision-a toy for a Notebook,
the hash functions that are based on problems that are Cryptology ePrint Archive, Report 2005/075.
NP-hard. However, the proposed hash function is
proved that it is secure due to the fact that it is based on [11] X. Wang, D. Feng, X. Lai, H. Yu, Collision for Hash
mathematical problems that are hard to solve hence it is Functions MD4, MD5, HAVAL-128 and RIPEMD,
worth to be evaluated. The proposed hash function’s Cryptology ePrint Archive, Report 2004/199.
internal stages tend to depend on the mapping of bits
into braid representation as well as multiplying the [12] X. Wang, Y. Yin, H. Yu, Finding Collisions in the Full
resulted braids to each other. These stages form the SHA-1, Crypto 2005.
core of the entire architecture of the hash function that
is proposed and they could be able to fulfill the
significant features of a hash function that is secured.

References
[1] P. Hofmann and B. Schneier, Attacks on
Cryptographic Hashes in Internet Protocols,
facs.org. November 2005. [Online]. Available:
http://www.faqs.org/rfcs/rfc4270.html [Accessed
March 20, 2018]

[2] K. Ko, S. Lee, J. Cheon, J. Han, J. Kang and C. Park,

New Public-Key cryptosystem using braid groups, In
advance in Cryptology: Crypto 2000.

[3] I. Al-Siaq, Public Key Cryptosystems based on

Numerical Methods, Global Journal of Pure and
Applied Mathematics, Vol.13, No.7 pp (2017) pp
3105-3112.
[4] R. Dobai, J. Korenek, L. Sekanina, Evolutionary
design of hash function pairs for network filters,
Applied Soft Computing, Volume 56, July 2017,
Pages 173-181.

[5] G. Yu, Y. Zhao, C. Lu, J. Wang, HashGO: hashing

gene ontology for protein function prediction,
Computational Biology and Chemistry, Volume 71,
December 2017, Pages 264-273.