A Lightweight 256-Bit Hash Function for Hardware and Low-End Devices: Lesamnta-LW - Information Security and Cryptology-ICISC 2010 - page 166

a432337f 945e1f8f 92539a11 24b90062
6971c64c d6e3f449 2c2f0da9 33769295
eb506df2 708cebfe b83ab7bf 97df0f17
9223b802 7fa29140 0ff45228 01fe8a45
ed016ee8 1da02ddd ee8aba1b 46c4c223
53cd0d24 d1b46d24 c1fb4124 c3f2a4a4
c3b39814 c3bbbf82 759191b0 0eb23236
b7fd6c86 a0d48750 141a90ea 6f65b45d
e0d2092b 470fd445 e5df4528 1cbbe8a5
eea9c2b4 c618f4d6 aee8345a 783be0cb
5412e979 3c712e0f 87567c21 2619bca4
df0efb14 c02c13e2 75e3643c d571a007
9a766de0 134ecdbc d9a41537 9becdb46
a556b1a8 14aad635 efabe566 abde566c
ceb6064d f4e87f69 286e7ccd e8337039
2bf51d27 85a6fa44 cb7913c8 196f2279

ConstantGenerator(word C[64])
begin
word c;
c = ffffffff; /*in hexadecimal*/
fori=0to(64*3)-1
/* Galois LFSR */
if c & 00000001 == 00000001
c = (c >> 1) ^ dbcdcc80;
else
c=c>>1;
end if
if i mod 3 == 0
C[i/3] = c;
end if
end for
end

Fig. 3. The round constants C ( i ) s ( in hex ) and a pseudocode for generating them

Let the message M be the 24-bit ( l = 24) ASCII string “ abc ”, which is
equivalent to the following binary string: .

01100001 01100010 01100011

Then the resulting 256-bit message digest is

2558c1d3 7f9f307b e3cddad4 a23c8654
518f6079 7eb491e7 3758727d fc83de65

.

B Proof of Theorem 1

Our analysis uses the following result by Suzuki et al. [43] on multi-collisions.

Proposition 1. Suppose that there are q bal ls and t buckets and that the balls
are thrown one by one at random into the buckets. For 2 ( t, q, s )

be the event that there exists at least one bucket that contains at least s bal ls.
Then,

≤ s ≤ q ,let

Col

t s− 1 q

.

1

Pr[ Col ( t, q, s )] ≤

s

Corollary 1. Let t =2 s and q =2 s− 2 .Then,for s

≥ 4 ,

1

(2 s , 2 s− 2 ,s )] Pr[ ≤ .

Col

s ! · 2 s

2 s− 2 . From Proposition 1, Proof. If s ≥ 4, then 2 ≤ s ≤

2 s− 2
s

(2 s− 2 ) s
s !

1
(2 s ) s− 1

1
2 s ( s− 1)

1

(2 s , 2 s− 2 ,s )] Pr[ ≤ ≤ = .

Col

2 s s ! ·