This paper reveals a duality between constructions of two basic cryptographic primitives, pseudo-random string generators and one-way hash functions. Applying the duality, we present a construction for universal one-way hash functions assuming the existence of one-way permutations. Under a stronger assumption, the existence of distinction-intractable permutations, we prove that the construction constitutes a collision-intractable hash function. Using ideas behind the construction, we propose practical one-way hash functions, the fastest of which compress nearly 2n-bit long input into n-bit long output strings by applying only twice a one-way function.