22-01-2013, 12:20 PM
An RC4-Based Hash Function for Ultra-Low Power Devices
1An RC4-Based Hash.pdf (Size: 466.29 KB / Downloads: 35)
Abstract
In this paper, a new hash function based on RC4
stream cipher is proposed. The proposed RC4-based hash
function has several advantages over many well-known hash
functions. Its efficiency is much better than many widely used
known hash function (e.g., MD5 and SHA-l). The application
of the proposed hash function can be extended to the ultra-low
devices for Ubiquitous computing, which most other hash
functions do not apply. The structure of the proposed hash
function is absolutely different from the broken hash function
class (e.g., SHA family) so that people cannot use the existing
attack strategies to break the proposed hash function. The
proposed hash function is very simple and rules out all possible
generic attacks. We proved that this hash function is secure
and efficient.
INTRODUCTION
Cryptographic hash functions play a fundamental role in
modem cryptography. Hash functions take a variable-sized
message as input and produce a small fixed-sized string as
output. Message authentication is a particular use of the
hash function and the security strength of the message
authentication depends on the cryptographic strength of the
underlying hash functions. Message authentication is a
procedure to verify that received messages come from the
alleged source and have not been altered.
Hash functions are usually designed from scratch or
made out of a block cipher in a black box manner [1]. Some
of the well-studied hash functions constructed from scratch
are SHA-family [2, 3], MD4 [4], MD5 [5], RIPEMD [6],
Tiger [7], HA VAL [8] etc. Whereas PGV hash function [9],
MDC2 [10] etc. are designed in a black box manner.
Recently, Antoine Joux presented a collision in SHA-O
[2] and Wang et al. reported collisions in several other
widely-used hash functions: SHA-I, MD4, MD5, HAVAL-
128, and RIPEMD [11, 12].
HASH FUNCTION
A hash function H is a transformation that takes an input
m and returns a fixed-size string, which is called the hash
value h (that is, h = H(m) . Hash functions with just this
property have a variety of general computational uses, but
when employed in cryptography, the hash functions are
usually designed to have some additional properties.
The basic requirements of a cryptographic hash function
are list below:
• The input can be of any length
• The output has a fixed length
• H(x) is relatively easy to compute for any given x
• H(x) is a one-way mapping
• H(x) is strongly collision-free
A hash function H is said to be one-way if it is hard to
invert, which means that, given a hash value h, it is
computationally infeasible to find some input x such that
H(x) = h. A strongly collision-free hash function H is
computationally infeasible to find any two messages x and y
such that H(x) = H(y).
The hash value h represents concisely the longer
message or document from which it was computed; this
value is called the message digest.
Message authentication code (MAC) is a mechanism to
achieve authentication. A message authentication code is an
authentication tag (also called a checksum) derived by
applying an authentication scheme, together with a secret
key, to a message.
Generate authentication value
The output of the step 2 is a 258-byte length RC4 state.
It can be used as the output of the hash function to be the
authentication value already. However, normally we want to
have a shorter value to be the authentication value. For this
reason we have this step to reduce the length of the
authentication value.
There are many ways can be used to reduce the length of
the output. We use the following rule to generate the
authentication value: take one bit from each one byte (e.g.
the last bit of each byte) of the output of the step 2,
combined with the index i and j. The length of the final
authentication value is 34-byte (256bit + 16bit).
CONCLUSION
This paper proposes a new hash function based on RC4
stream cipher. The efficiency of the proposed RC4 based
hash function is much better than widely used known hash
function and its structure is absolutely different from the
broken hash function class (e.g., SHA family). It is very
simple and rules out all possible generic attacks. More than
that, the application of the proposed hash function can be
applied 10 ultra-low power devices for ubiquitous
computing, including wireless sensor networks and radiofrequency
identification, which most other hash functions
do not apply. We proved that this hash function is secure
and efficient.