In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, Very Smooth Hash (VSH) is a secure
cryptographic hash function
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography:
* the probability of a particular n-bit output re ...
invented in 2005 by Scott Contini, Arjen Lenstra and Ron Steinfeld.
[
]
Provably secure
Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.
Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...
means that finding collisions is as difficult as some known hard mathematical problem. Unlike other secure
collision-resistant
In cryptography, collision resistance is a property of cryptographic hash functions: a hash function ''H'' is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs ''a'' and ''b'' where ''a'' ≠ '' ...
hashes, VSH is efficient and usable in practice.
Asymptotically
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
, it only requires a single multiplication per log(''n'') message-bits and uses RSA-type arithmetic. Therefore, VSH can be useful in embedded environments where code space is limited.
Two major variants of VSH were proposed. For one, finding a
collision
In physics, a collision is any event in which two or more bodies exert forces on each other in a relatively short time. Although the most common use of the word ''collision'' refers to incidents in which two or more objects collide with great fo ...
is as difficult as finding a nontrivial modular square root of a very smooth number modulo ''n''. The other one uses a prime modulus ''p'' (with no
trapdoor
A trapdoor is a sliding or hinged door in a floor or ceiling. It is traditionally small in size. It was invented to facilitate the hoisting of grain up through mills, however, its list of uses has grown over time. The trapdoor has played a pivot ...
), and its security proof relies on the hardness of finding discrete logarithms of very smooth numbers modulo ''p''. Both versions have similar efficiency.
VSH is not suitable as a substitute for a
random oracle
In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time th ...
, but can be used to build a secure randomized trapdoor hash function. This function can replace the
trapdoor function
In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trap ...
used in the
Cramer–Shoup signature scheme, maintaining its provable security while speeding up verification time by about 50%.
VSN and VSSR
All cryptographic hash functions that are now widely used are not based on hard mathematical problems. Those few functions that are constructed on hard mathematical problems are called
provably secure
Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.
Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...
.
Finding collisions is then known to be as hard as solving the hard mathematical problem. For the basic version of Very Smooth Hash function, this hard problem is to find modular square roots (VSSR) of certain special numbers (VSN).
This is assumed to be as hard as
factoring integers
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are suf ...
.
For a fixed constant ''c'' and ''n'' an integer ''m'' is a Very Smooth Number (VSN) if the largest prime factor of ''m'' is at most (log ''n'')
''c''.
An integer ''b'' is a Very Smooth Quadratic Residue modulo ''n'' if the largest prime in ''bs factorization is at most (log ''n'')
''c'' and there exists an integer ''x'' such that
. The integer ''x'' is said to be a
Modular Square Root of ''b''.
We are interested only in non-trivial square roots, those where ''x''
2 ≥ ''n''. If ''x''
2 < ''n'', the root can be easily computed using algorithms from fields of
characteristics 0, such as real field. Therefore, they are not suitable in cryptographic primitives.
Very Smooth Number Nontrivial Modular Square Root (VSSR) is the following problem: Let ''n'' be the product of two unknown primes of approximately the same size and let
. Let
be the sequence of primes. VSSR is the following problem: Given ''n'', find
such that
and at least one of ''e''
0,...,''e''
''k'' is odd.
The VSSR assumption is that there is no
probabilistic polynomial (in
) time algorithm which solves VSSR with
non-negligible probability. This is considered a useless assumption for practice because it does not tell for what size of moduli VSSR is computationally hard. Instead The computational VSSR assumption is used. It says that solving VSSR is assumed to be as hard as
factoring a hard-to-factor
bit modulus, where
is somewhat smaller than the size of
.
Examples of VSN and VSSR
Let the parameters be fixed as follows:
and
.
Then
is a Very Smooth Number with respect to these parameters because
is greater than all
's prime factors. On the other hand,
is not a VSN under
and
.
The integer
is Very Smooth Quadratic Residue modulo
because it is Very Smooth Number (under
) and we have
such that
(mod
). This is a trivial modular square root, because
and so the modulus is not involved when squaring.
The integer
is also Very Smooth Quadratic Residue modulo
. All prime factors are smaller than 7.37 and the Modular Square Root is
since
(mod
). This is thus a non-trivial root. The VSSR problem is to find
given
and
. And we suppose that this is computationally as hard as factoring
.
VSH algorithm, basic versions
Let
be a large RSA composite and let
the sequence of primes. Let
, the block length, be the largest integer such that
. Let
be an
-bit message to be hashed consisting of bits
and assume that
. To compute the hash of
:
# ''x''
0 = 1
# Let
, the smallest integer greater or equal to
, be the number of blocks. Let
for
(padding)
# Let
with
be the binary representation of the message length
and define
for
.
# for ''j'' = 0, 1,..., ''L'' in succession compute
# return ''x''
''L'' + 1.
The function in step 4 is called the compression function.
Properties of VSH
* The message length does not need to be known in advance.
* Finding a collision in VSH is as hard as solving VSSR. Thus VSH is (strongly)
collision-resistant
In cryptography, collision resistance is a property of cryptographic hash functions: a hash function ''H'' is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs ''a'' and ''b'' where ''a'' ≠ '' ...
, which also implies second preimage resistance. VSH has not been proven to be preimage-resistant.
* The compression function is not collision-resistant. Nonetheless, the hash function VSH is collision-resistant based on the VSSR assumption. An altered version of VSH, called VSH*, uses a collision-resistant compression function and is about 5 times quicker when hashing short messages.
* Since the output length of VSH is the length of a secure RSA modulus, VSH seems quite suitable in practice for constructing "hash-then-sign" RSA signatures for arbitrarily long messages. However, such a signature must be designed carefully to ensure its security. The naive approach could be easily broken under
CPA (chosen-plaintext attack).
*
Efficiency
Efficiency is the often measurable ability to avoid wasting materials, energy, efforts, money, and time in doing something or in producing a desired result. In a more general sense, it is the ability to do things well, successfully, and without ...
: The cost of each iteration is less than the cost of 3 modular multiplications. The basic version of VSH altogether requires single multiplication per
message bits.
Variants of VSH
Several improvements, speedups and more efficient variants of VSH have been proposed.
None of them changes the underlying concept of the function. These improvements are called:
* Cubing VSH (instead of squaring).
* VSH with increased number of small primes.
* VSH with precomputed products of primes.
* Fast VSH.
* Fast VSH with increased block length.
VSDL and VSH-DL variant
The VSH-DL is a discrete logarithm variant of VSH that has no
trapdoor
A trapdoor is a sliding or hinged door in a floor or ceiling. It is traditionally small in size. It was invented to facilitate the hoisting of grain up through mills, however, its list of uses has grown over time. The trapdoor has played a pivot ...
, its security depends on the difficulty of finding discrete logarithm modulo a prime ''p''.
Very Smooth Number Discrete Logarithm (VSDL) is a problem where given a very smooth number, we want to find its
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
modulo some number ''n''.
Similarly as in previous section, by
we denote the
-th prime. Let furthermore
be a fixed constant and
,
be primes with
and let
. VSDL is the following problem: given
, find integers
such that
with
for
and at least one of
non-zero.
The VSDL assumption is that there is no
probabilistic polynomial (in
) time algorithm which solves VSDL with
non-negligible probability. There is a strong connection between the hardness of VSDL and the hardness of computing discrete logarithm modulo
, which is reminiscent of, but somewhat weaker than, the connection between VSSR and integer factorization.
Security of VSH
Strong
collision resistance
In cryptography, collision resistance is a property of cryptographic hash functions: a hash function ''H'' is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs ''a'' and ''b'' where ''a'' ≠ '' ...
is the only property proven for VSH. This does not imply preimage-resistance or other
important hash function properties, and the authors state that "VSH should not be used to model
random oracle
In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time th ...
s," and cannot be substituted into constructions that depend upon them (
RSA signatures, some
MACs).
VSH should not be considered a general-purpose hash function as usually understood in
security engineering
Security engineering is the process of incorporating security controls into an information system so that the controls become an integral part of the system’s operational capabilities. It is similar to other systems engineering activities in tha ...
.
Multiplicative property
VSH is multiplicative: Let ''x'', ''y'', and ''z'' be three bit strings of equal length, where ''z''
consists only of zero bits and the strings satisfy ''x AND y = z''. It is easy to see that
''H(z)H(x OR y) ≡ H(x)H(y) (mod n)''. As a result, VSH succumbs to a classical time-memory
trade-off attack that applies to multiplicative and additive hashes.
This fact can be used to construct a preimage attack against VSH of
bits which has
complexity rather than
as expected.
Attack against truncated version
VSH produces a very long hash (typically 1024 bits). There are no indications that
a truncated VSH hash offers security that is commensurate with the hash length.
There exists a partial collision attack on VSH truncated to least significant ''l'' bits.
[
]
The complexity of this attack against VSH is:
* Pre-computing the table offline:
time and space.
* Finding collisions:
iterations.
* Total cost: roughly
, rather than
as expected from a hash function with good pseudorandomness properties.
This probably rules out the applicability of VSH in digital signature schemes which produce signatures shorter than the VSH hash result, such as elliptic-curve signature schemes.
See also
*
Cryptographic hash functions
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography:
* the probability of a particular n-bit output ...
*
Provably secure cryptographic hash function
In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on mathematical problems, and whose security thus follows from rigorous mathematical proofs, c ...
References
{{Cryptography navbox , hash
Cryptographic hash functions