Page 5 - tmp

Addition Structured Hash and its Applications

Stefan Crnojević
Supervisor: Mateja Opačić
Regional Centre for Talented Youth Belgrade II, Serbia, scrnojevic@yahoo.com

balancedness, regularity, and especially the nonlinearity
of the small compression function’s truth table. This is a
1 Introduction sound approach if these properties are preserved when the
input-output space is increased, as it is the case here. The
mentioned properties are implied by the pre-image
Modern cryptographic one-way hash functions usually resistance and, given no structural flaws they are supposed
play a huge role in our everyday communication on any to imply the pre-image resistance. The original structure of
type of a secure network. Security of every cryptosystem the compression function came from the linear addition
depends on the security of all its primitives equally, one of operation, which highly modified stream can be noticed in
which is highly likely to be a cryptographic one-way hash the main part of the algorithm in fig. 1. The mapping is
function. Even after a lot of extensive research, we still from {0,1} to {0,1} , where n ∈ ℕ \ {1, 2}. Therefore, the
n
4n
aren't able to make a comprehensive method to prove if input is divided into four equal streams, P1 (not marked)
such functions are secure or not, so each one must be being the hash state and the other three being the input
studied intensively in order to reveal its shortcomings. streams, marked P2, P3 and P4. The first main nonlinear
Therefore, diversity in new approaches in the design, and step of the compression function (marked ρ i ) is the
the structure of the designed itself is needed in order to replacement of the bitwise AND operation of the original
preserve the security of everyday communication. The main addition algorithm with 4-to-1 function of a different
aim of this project is to try to present such contribution.
probability distribution that, apart from one bit of P1 and
one bit of P2, also takes the corresponding bits of P3 and P4
of the same index as a part of its input. The second one is
2 The Contribution the overwriting of the first bit of P1 with the current total-
XOR of all the bits in P1 (marked tx). The rest of the
The hash functions mentioned take an input of arbitrary modifications are added to preserve the great statistical
length and the output of fixed length in the interval from properties of the original addition algorithm and to ensure
160 to 512 bits, or even more due to the potential brute- even higher nonlinearity after the two main nonlinear steps.
force attacks. Apart from having to work efficiently for any
given input, cryptographic hash functions must provide that
it is infeasible to produce the original data from the given
hash. This property, along with the property of infeasibility
of changing the input in any way and not altering the hash,
defines the first pre-image resistance. The function I
created, named Addition Structured Hash, apart from
passing truth table tests which these properties must imply
on, does even more. It can output an arbitrary size hash for
any given input, while at the same time preserving its pre-
image resistances.

3 The Inner Workings

The modern cryptographic one-way hash functions are Fig. 1, the ASH compression function
made of two parts: the compression function and the
extender function. The compression function is a one-way
function that works with the inputs and outputs of fixed and
smaller size and should be pre-image resistant, while the 4 Conclusion
extender is made to preserve its properties. My function
uses a classical extender, utilized by all the functions that
are considered to be secure today: the Merkle-Damgård The space complexity of ASH is minimal – only the input
extender. Nevertheless, the approach I have taken to create storage is required in practice. The running time is faster
than that of adding four n-bit numbers. Therefore, a large
the compression function is entirely new and original. The
main cause of the arbitrary digest hash function is the number of applications is possible in the mentioned real-
time cryptosystems apart from the other usages. Besides the
possibility of a new approach in the function testing.
Namely, if the input-output space is small enough, its algorithm itself, the basic approach and the idea of the
algorithm’s new structure are a great contribution as well
properties can be measured more precisely. Therefore,
while testing, the great attention is dedicated to testing the for some other new contributions and ideas may arise from
them.