H(spl)ashing With A Sponge

H(spl)ashing With A Sponge

So how do you implement an efficient hashing method on a device with limited capabilities? Well, one method is to use a Sponge function (as defined in SHA-3/Keccak):

With the sponge construction we use a fixed-length permutation (or transformation) and a padding rule. This construction thus takes a variable length input and map it to a variable-length output. The input is (Z2)* of any length and then converts it into (Z2)n, where n is defined as part of the process. Overall the method uses a finite-state machine process, and iterates through the states with the addition of the input data.

The sponge construction uses a function F which has a variable-length input and a defined output length. It operates on a fixed number of bits (b) — the width. The sponge construction then operates on a state of b=r+c bits. r is defined as the bitrate and c as the capacity.

Initially an input string is padded using a reversible padding rule (such as adding NULL characters), and then segmented into blocks of r bits. Next the b bits of the state are set to zero, and the sponge construction next defines:

• Absorbing phase. This is where the r-bit input blocks are X-ORed into the first r bits of the state, interleaved with applications of the function f. After all the input blocks have been processed, we then move to a squeezing phase.
• Squeezing phase. This is where the first r bits of the state are outputted as blocks and, interleaved with the function f. The number of bits of the output are defined as part of the process.

Overall the last c bits of a state are never changed by the input blocks and never output within the squeezing phase.

For an 88-bit hash we have (SPONGENT-088–080–00 — Spongent-88/80/8: n=88 bits, b=88 bits, c=80 bits, r=8 bits, R=45):

#define rate		8
#define capacity	80
#define hashsize	88
#define nRounds		45

and for 128-bit (SPONGENT-128–128–008 — Spongent-128/128/8: n=128 bits, b=136 bits, c=128 bits, r=8 bits, R=70):

#define rate		8
#define capacity	128
#define hashsize	128
#define nRounds		70

and for 160-bit (SPONGENT-160–160–016 — Spongent-160/160/16: n=160 bits, b=176 bits, c=160 bits, r=16 bits, R=90)

#define rate		16
#define capacity	160
#define hashsize	160
#define nRounds		90

and for 256-bit (SPONGENT-256–256–016 — Spongent-256/256/16: n=256 bits, b=272, c=256 bits, r=16 bits, R=140)

#define rate		16
#define capacity	256
#define hashsize	256
#define nRounds		140

The following shows a Python version of the code [here]:

import spongent
import binascii

mystr="Sponge + Present = Spongent"
m=int(binascii.hexlify(mystr.encode()),16)

print ("Message:\t",mystr)

spongent80 =  spongent.SPONGENT(n=88, c=80, r=8, R=45)
print ("SPONGENT-088-080-008:\t",hex(spongent80.hash(m, prefix_zeros=1)))

spongent128 = spongent.SPONGENT(n=128, c=128, r=8, R=70)
print ("SPONGENT-128-128-008:\t",hex(spongent128.hash(m, prefix_zeros=1)))

spongent160 = spongent.SPONGENT(n=160, c=160, r=16, R=90)
print ("SPONGENT-160-160-016:\t",hex(spongent160.hash(m, prefix_zeros=1)))

spongent224 = spongent.SPONGENT(n=224, c=224, r=16, R=120)
print ("SPONGENT-224-224-016:\t",hex(spongent224.hash(m, prefix_zeros=1)))

spongent256 = spongent.SPONGENT(n=256, c=256, r=16, R=140)
print ("SPONGENT-256-256-016:\t",hex(spongent256.hash(m, prefix_zeros=1)))

But, Python is a little slow, so here is the C code:

For a more advanced discussion of the sponge function: