Lightweight Hash Functions
Lightweight hash function are lightweight cryptographic primitives.
The NIST provides figures for hardware implementation of the SHA3 finalists aimed at optimizing the area^{[1]}. For a 0.09 µm technology, the best they can achieve is 9,200 GE for Grøstl^{[2]}; Keccak^{[3]} (the winner of the competition) requiring at least 15,200 GE. These are way too much for, say, RFID tags. That is why lightweight hash functions have been proposed.
Hash Function Design
Desirable Properties
Here, "impossible" means "impossible for an adversary having some reasonable computing power" where "reasonable" is actually a complex concept. Consider a hash function H; we want it to be (at least):
 Collision resistant: it is "impossible" to find x and y such that H(x)=H(y).
 Preimage resistant: given a digest d, it is "impossible" to find x such that H(x)=d.
 Second preimage resistant: given y, it is "impossible" to find x≠y such that H(x)=H(y).
MerkleDamgård
Basic idea
Consider a compression function h mapping {0,1}^{n}x{0,1}^{k} to {0,1}^{n}, a fixed and public initialization vector IV of {0,1}^{n} and a message (m_{0}, m_{1}, ..., m_{L1}) where each m_{i} is a block of k bits. Then we can build a hashfunction H where:
 c_{0} = IV
 c_{i+1} = h(c_{i}, m_{i})
 H(m) = d = c_{L}
One of the main interest of this construction is that such a compression function h can easily be built out of a block cipher using an appropriate mode, for instance DaviesMeyer. However, if it is used in this simple way, it is vulnerable to, for example, length extension attacks.
Strengthened MerkleDamgård
To prevent attacks based on the extension of the input message, a stronger construction should be used. The idea is to append the length of the input message to the end of the message itself combined with a padding so as to have a padded message with a length which is a multiple of k. That way, lengthextensionbased attacks are prevented. This construction is the *strengthened MerkleDamgård* construction.
Sponge
The sponge construction is a method to build a hash function from a publicly known unkeyed permutation (PSponge) or random function (TSponge). It was introduced by Bertoni et al., the Keccak team, in 2007 ^{[4]}. Sponges can also be used to provided stream ciphers or even authenticated encryption, see the duplex construction.
General Idea
The principle of a sponge is fairly simple and is described on the Figure on the right. The message is first padded (more on that later) and sliced into blocks of r bits. Then, an internal state of (r+c) bits is initialized so as to contain only zeroes. r is called (bit)rate and c is called capacity. The digest is obtained by 'absorbing' the padded message and then 'squeezing' the internal state. The absorption phase consists in:
 Replacing the first r bits of the internal by the xor of these bits and one rbits block with (or possibly by the rbits block directly)
 Replacing the internal state by its image by the update function.
Then, the squeezing is made of d/r steps where d is the size of the digest in bits. Each step consists in:
 Storing the first r bits of the internal state
 Replacing the internal state by its image by the update function.
The rbits block thus obtained are concatenated to obtain the digest.
It has been proven that the truncated output of a sponge can be distinguished from that of a random oracle with a probability which is essentially N/2^{c/2} where c is the capacity and N is the number of calls to the update function. This is the socalled flat sponge claim.^{[5]}
The padding used is usually very simple. Although the designers of the sponge do not suggest one in particular in their seminal paper^{[3]}, the one used in practice consists simply in adding one bit equal to 1 at the end of the message and then fill it with zeroes until it reaches a length which is a multiple of r. It is, as we can see, much simpler than the one used in a strengthened MerkleDamgård construction.
PSponge and TSponge
P(ermutation)Sponge and T(ransformative)Sponge are sponge models using respectively a random permutation and a random function to update their internal state. In the paper in which the sponge functions were introduced^{[4]}, it was shown that sponges with capacity c, rate r and digest size n absorbing messages of length m<2^{c/2} are such that different attacks require the following number of calls to the update function.
Case  Preimage  Second Preimage  Collision  Cycle finding 

TSponge  min(n, c+r)  min(n, clog_{2}(m))  min(n, c)/2  (c+r)/2 
PSponge  c1  min(n, c/2)  c+r 
JHlike construction
What we call JHlike sponge is a structure similar to that of the hash function JH^{[6]}, finalist of the SHA3 competition. It differs from the regular sponge by having the message blocks injected twice: first, like in a sponge, before the call to the updating function and then on the opposite side of the internal state after this call. Both times, the same message block is injected.
The JH hash function uses a strengthened MerkleDamgårdstyle padding consisting in appending the length of the message to the last block, unlike the simple padding of the sponge. Note however that functions based on the same construction may use different paddings. For instance, SipHash only appends the length of the message modulo 256.
Notations
We call internal state size the size in bits of the complete internal state of a sponge (rate plus capacity) and the size of the chaining value in the case of a MerkleDamgård construction. The rate is the size of the message block treated at each round.
Summary
Presentation  Cryptographic Properties  Implementation Properties  

name  designers  reference (design)  digest size  rate  internal state size  structure  preimage  second preimage  collisions  attacks  technology used  area (#GE)  throughput (Kb/s @ 100kHz)  power consumption (µW)  reference (implementation) 
ARMADILLO  Badel et al.  CHES 10^{[7]}  80  48  256  MerkleDamgård  2^{80}  2^{80}  2^{40} 

0.18 µm  4030 / 2923  109 / 27    Specification^{[7]} 
128  64  384  2^{128}  2^{128}  2^{64}  6025 / 4353  1000 / 250    
160  80  480  2^{160}  2^{160}  2^{80}  7492 / 5406  100 / 250    
192  96  576  2^{192}  2^{192}  2^{96}  8999 / 6554  100 / 25    
256  128  768  2^{256}  2^{256}  2^{128}  11914 / 8653  100 / 25    
DMPRESENT  Poschmann  PhD Thesis (09)^{[9]}  64  80  64  MerkleDamgård (DaviesMeyer)  64  None  None 

2213 / 1600  242.42 / 14.63  6.28 / 1.83  Specification (6.5.2)^{[9]}  
128  2530 / 1886  387.88 / 22.9  7.49 / 2.94  
GLUON  Berger et al.  AFRICACRYPT 12^{[11]}  128  8  136  TSponge  2^{128}  2^{64}  2^{64} 

2071  12.12    Specification^{[11]}  
160  16  176  2^{160}  2^{80}  2^{80}  2799.3  32    
224  32  256  2^{224}  2^{112}  2^{112}  4724  58.18    
LesamntaLW  Hirose et al.  ICICS'10^{[13]}  256  128  256  MerkleDamgaard  2^{256}  2^{256}  2^{128} 

        
PHOTON  Guo et al.  CRYPTO 11^{[15]}  80  20 / 16  100  PSponge  2^{64}  2^{40}  2^{40} 

0.18 µm  865 / 1168  2.82 / 15.15    Specification^{[15]} 
128  16  144  2^{112}  2^{64}  2^{64}  1122 / 1708  1.61 / 10.26    
160  36  196  2^{124}  2^{80}  2^{80}  1396 / 2117  2.70 / 20  
224  32  256  2^{192}  2^{112}  2^{112}  1736 / 2786  1.86 / 15.69    
256  32  288  2^{224}  2^{128}  2^{128}  2177 / 4362  3.21 / 20.51    
QUARK  Aumasson et al.  CHES 10^{[16]}  136  8  136  PSponge  2^{128}  2^{64}  2^{64} 

0.18 µm  1379 / 2392  1.47 / 11.76  2.44 / 4.07  Specification^{[16]} 
176  16  176  2^{160}  2^{80}  2^{80}  1702 / 2819  2.27 / 18.18  3.10 / 4.76  
256  32  256  2^{224}  2^{112}  2^{112}  2296 / 4640  3.13 / 50.0  4.35 / 8.39  
SipHash24  Aumasson et al.  INDOCRYPT 12^{[17]}  64  64  256  JHstyle TSponge  2^{64}  2^{64}  None^{[note 2]} 

3700 / 13500      Specification^{[17]}  
SPNHash  Choy et al.  AFRICACRYPT 12^{[18]}  128  256  128  JHstyle PSponge  2^{128}  2^{??}^{[note 3]}  2^{64} 

0.18 µm  2777 / 4600  36.1 / 55.7    Specification^{[18]} 
256  512  256  2^{256}  2^{??}^{[note 3]}  2^{128}  4625 / 8500  35.8 / 111.3    
SPONGENT  Bogdanov et al.  CHES 11^{[19]}  80  8  88  PSponge  2^{80}  2^{40}  2^{40} 

0.13 µm  738 / 1127  0.81 / 17.78  1.57 / 2.31  Specification ^{[19]} 
128  8  136  2^{120}  2^{64}  2^{64}  1060 / 1687  0.34 / 11.43  2.20 / 3.58  
160  16  176  2^{144}  2^{80}  2^{80}  1329 / 2190  0.40 / 17.78  2.85 / 4.47  
224  16  240  2^{208}  2^{112}  2^{112}  1728 / 2903  0.22 / 13.33  3.73 / 5.97  
256  16  272  2^{240}  2^{128}  2^{128}  1950 / 3281  0.17 / 11.43  4.21 / 6.62 
Descriptions
ARMADILLO
 Article: ARMADILLO: a MultiPurpose Cryptographic Primitive Dedicated to Hardware, CHES 10^{[7]}
 Authors: Stephane Badel, Nilay Dagtekin, Jorge Nakahara Jr, Khaled Ouafi, Nicolas Reffe, Pouyan Sepehrdad, Petr Susil, Serge Vaudenay
ARMADILLO is a multipuprose primitive intended to be used as a FILMAC (application I), for hashing and digital signatures (application II) and as a PRNG and PRF (application III). It has been broken by NayaPlasencia and Peyrin^{[8]} who managed to find collisions when it is used as a hash function in very small time (few seconds on a regular PC).
This primitive was in the process of being patented by oridao when the article was published.
DMPRESENT
 Article: Lightweight Cryptography: Cryptographic Engineering for a Pervasive World, Poschmann's PhD thesis (09)^{[9]}
 Author: Poschmann, Alex
DMPRESENT is simply a MerkleDamgård scheme where the compression function is the block cipher PRESENT in DaviesMeyer mode. DMPRESENT80 is based on PRESENT80 and DMPRESENT128 on PRESENT128. No security claims are made about collision or second preimages as we can read in Section 6.5.1 of Poschmann's PhD Thesis^{[9]}:
Such hash functions will only be of use in applications that require the oneway property and 64bit security.
GLUON
 Article: The GLUON Family: A Lightweight Hash Function Family Based on FCSRs, AFRICACRYPT 12^{[11]}
 Authors: Thierry P. Berger, Joffrey D'Hayer, Kevin Marquet, Marine Minier, and Gael Thomas
GLUON is a Tsponge, meaning that it is a sponge with a noninjective update function. The said function is based on the software oriented streamciphers XFCSRv2 and FFCSRHv3: the internal state of the sponge is padded and loaded into a socalled FCSR (Feedback with Carry Shift Register) which is clocked a fixed amount of time. Then, some cells of the FCSR are xored to form the first word of the next internal state, the FCSR is clocked, the same words are xored to form the second word of the next internal state, etc.
The update function of GLUON64 is many to one and has a behaviour which is very different from that of a random function.
LesamntaLW
 Article: A Lightweight 256Bit Hash Function for Hardware and LowEnd Devices: LesamntaLW, ICISC 10^{[13]}
 Authors: Shoichi Hirose, Kota Ideguchi, Hidenori Kuwakado, Toru Owada, Bart Preneel, Hirotaka Yoshida
 Target: software
LesamntaLW is a softwareoriented hash function built using a MerkleDamgaard construction with a custom 256bit block cipher. This block cipher is a generalized Feistel Network with 4 branches, only one of which receives the output of the Feistel function. This Feistel function reuses the SBox and the Mixcolumns operation of the AES. It is an ISO standard (291925).
PHOTON
 Article: The PHOTON Family of Lightweight Hash Functions, CRYPTO 11^{[15]}
 Authors: Jian Guo, Thomas Peyrin, and Axel Poschmann
Photon is a PSponge based on an AESlike permutation. For the smallest security parameter (PHOTON80/20/16), the bitrate during absorption is 20 but it is equal to 16 during the squeezing phase. The throughput figures given correspond to throughput when outputting long messages as these are the ones usually given. However, the figures for shorter messages are smaller (i.e. better) for PHOTON.
The permutation consists in 12 iterations (for every security parameters) of the following sequence of transformations performed over a square of dxd nibbles of 4bits (8bits for the largest version). As we can see, the AES cipher has obviously been a great influence for the design of the permutation.
 AddConstant: a round dependent constant is xored into every nibble and then a cell dependent constant is xored as well.
 SubCells: A Sbox is applied on every nibbles. If the nibbles are 4bits long then the PRESENT Sbox is used, otherwise it is the AES's.
 ShitRows: Identical to the AES's.
 MixColumnsSerial: The nibbles are considered like elements of GF(2^{4}) (or GF(2^{8}) for the largest security parameter) and each column is multiplied by a MDS matrix designed so as to be efficiently implemented in hardware.
The design of the permutation used to update the sponge is close to the LED cipher which was designed later by the same people. As said above, the AES was also a great influence.
More information on this primitive (including a reference implementation) can be found on this googlesite set up by its authors.
QUARK
 Article: Quark: a lightweight hash, CHES 10^{[16]}
 Authors: JeanPhilippe Aumasson, Luca Henzen, Willi Meier, Maria NayaPlasencia
QUARK is a PSponge with a hardware oriented permutation inspired by the lightweight block ciphers KTANTAN and KATAN and the hardware oriented stream cipher Grain. The smallest version (136 bits long digest) is called UQUARK, the middle one (176 bits long digest) DQUARK and the longest (256 bits long digest) SQUARK.
The update function maps an element of {0,1}^{b} to {0,1}^{b} by loading each half in a distinct NSFR of length b/2 and then clocking these 4xb times. The NSFR's are connected to each other and to a small LFSR of length log(4b), see Figure on the side. The functions f,g and h are boolean functions chosen for their nonlinearity, resilience, algebraic degree and density. f and g are identical for all versions and borrowed from Grainv1 while h depends on the instance.
The authors claim these possible uses:
The following primitives can then be realized:
 Message authentication code (MAC);
 Pseudorandom generator;
 Stream cipher;
 Randomaccess stream cipher;
 Key derivation function.
Furthermore, the Quark instances can easily be modified to operate in the duplex construction [...] to allow the realization of functionalities as authenticated encryption or reseedable pseudorandom generators.
A modified version of the sponge used is used in CQUARK, an authenticated encryption scheme.
SipHash
 Article: SipHash: a fast shortinput PRF, INDOCRYPT 12^{[17]}
 Authors: Aumasson, J. P., & Bernstein, D. J.
SipHash has a ARX structure which was inspired by BLAKE and Skein. It provides a family of keyed functions mapping {0,1}^{*} to {0,1}^{64} and is aimed at a use as MAC or in hash tables. It has a structure similar to JH, like SPNHash and uses a padding taking the length of the message into account as well. However, it consists simply in adding a byte with the length of the message modulo 256.
It is not claimed to be collision resistant and obviously is not due to the small digest size.
SPNHash
 Article: SPNhash: improving the provable resistance against differential collision attacks, AFRICACRYPT 12^{[18]}
 Authors: Choy, J., Yap, H., Khoo, K., Guo, J., Peyrin, T., Poschmann, A., & Tan, C. H.
The main interest of this hash function is its provable security against differential collision attacks. It is a JHlike structure using, as its name indicates, a permutation based on SPN. The structure of the SPN is based on that of the AES: first, 8x8 Sboxes are applied on each byte of the internal state. The Sbox used is exactly that of the AES. Then, a more complex mixing layer is applied; its design being the main focus of the article; optimal diffusion and lightweightness in hardware being both evaluated. At last, round constants are xored in the internal state in fashion similar to those of LED and PHOTON. These operations are iterated 10 times for all security parameters.
The authors also mention a 512 bits version of the design but it is not fully specified and hence hardware benchmarking was rendered impossible as we can see on page 10 of the original paper:^{[18]}
512bit SPNHash. The choice of matrix for the 16 × 16 MDS is left open to the reader.
The padding used is the same as in a strengthened MerkleDamgård: the length of the message is appended to the last block.
SPONGENT
 Article: SPONGENT: A lightweight hash function, CHES 11^{[19]}
 Authors: Bogdanov, A., Knežević, M., Leander, G., Toz, D., Varıcı, K., & Verbauwhede
SPONGENT can be seen as a PSponge where the permutation is a modified version of the block cipher PRESENT. These primitives actually have several designers in common.
The number of rounds of the PRESENTlike permutation ranges from 45 for SPONGENT88 to 140 for SPONGENT256. Each round consists in:
 xoring of the content of a LFSR clocked at each round (can be seen as a round constant)
 applying an Sbox layer with a 4x4 Sbox satisfying the same criteria as the PRESENT Sbox
 permuting the bits in a fashion similar to PRESENT.
There is no attack on SPONGENT to the best of our knowledge except for linear distinguishers for reducedround versions^{[20]}.
Notes
 ↑ ^{1.0} ^{1.1} ^{1.2} ^{1.3} To the best of our knowledge.
 ↑ The authors claim:
We comment that SipHash is not meant to be, and (obviously) is not, collisionresistant.
 ↑ ^{3.0} ^{3.1} The authors point out that the JH structure circumvents the MitM attack on PSponges causing secondpreimage resistance to be of 2^{c/2} for PSponges. However, they do not make a clear security claim so it remains unclear whether they claim 2^{c/2} (as in a flat sponge claim) or something else (2^{c}?).
References
 ↑ Kavun, E. B., & Yalcin, T. (2012, March). On the suitability of SHA3 finalists for lightweight applications. In ser. The Third SHA3 Candidate Conference. pdf at nist.gov
 ↑ Gauravaram, P., Knudsen, L. R., Matusiewicz, K., Mendel, F., Rechberger, C., Schläffer, M., & Thomsen, S. S. (2008). Grøstl–a SHA3 candidate. Submission to NIST. pdf at uclouvain.be
 ↑ ^{3.0} ^{3.1} Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2008). Keccak specifications. Submission to NIST, 42. pdf at noekeon.org
 ↑ ^{4.0} ^{4.1} Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2007, May). Sponge functions. In ECRYPT hash workshop (Vol. 2007). pdf at psu.edu
 ↑ Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2008). On the indifferentiability of the sponge construction. In Advances in Cryptology–EUROCRYPT 2008 (pp. 181197). Springer Berlin Heidelberg. pdf at eprint.iacr.org
 ↑ Wu, H. (2011). The hash function JH. Submission to NIST (round 3). pdf at uclouvain.be
 ↑ ^{7.0} ^{7.1} ^{7.2} Badel, S., Dağtekin, N., Nakahara Jr, J., Ouafi, K., Reffé, N., Sepehrdad, P., ... & Vaudenay, S. (2010). ARMADILLO: a multipurpose cryptographic primitive dedicated to hardware. In Cryptographic Hardware and Embedded Systems, CHES 2010 (pp. 398412). Springer Berlin Heidelberg. pdf at psu.edu
 ↑ ^{8.0} ^{8.1} NayaPlasencia, M., & Peyrin, T. (2012, January). Practical cryptanalysis of ARMADILLO2. In Fast Software Encryption (pp. 146162). Springer Berlin Heidelberg. pdf at christinaboura.info
 ↑ ^{9.0} ^{9.1} ^{9.2} ^{9.3} Poschmann, A. Lightweight Cryptography: Cryptographic Engineering for a Pervasive World. PhD Thesis from Faculty of Electrical Engineering and Information Technology RuhrUniversity Bochum, Germany. pdf at eprint.iacr.org
 ↑ Koyama, T., Sasaki, Y., & Kunihiro, N. (2013). Multidifferential cryptanalysis on reduced DMPRESENT80: collisions and other differential properties. In Information Security and Cryptology–ICISC 2012 (pp. 352367). Springer Berlin Heidelberg. pdf at springer
 ↑ ^{11.0} ^{11.1} ^{11.2} Berger, T. P., D’Hayer, J., Marquet, K., Minier, M., & Thomas, G. (2012). The GLUON family: a lightweight Hash function family based on FCSRs. In Progress in CryptologyAFRICACRYPT 2012 (pp. 306323). Springer Berlin Heidelberg. pdf at inria.fr
 ↑ Perrin, L., & Khovratovich, D. (2014, March). Collision Spectrum, Entropy Loss, TSponges, and Cryptanalysis of GLUON64. In Fast Software Encryption 2014 (to appear). pdf at eprint.iacr.org
 ↑ ^{13.0} ^{13.1} Hirose, S., Ideguchi, K., Kuwakado, H., Owada, T., Preneel, B., & Yoshida, H. (2010, December). A lightweight 256bit hash function for hardware and lowend devices: LesamntaLW. In International Conference on Information Security and Cryptology (pp. 151168). Springer Berlin Heidelberg. pdf at springer.com
 ↑ Sasaki, Y., & Aoki, K. (2011, November). Improved integral analysis on tweaked lesamnta. In International Conference on Information Security and Cryptology (pp. 117). Springer Berlin Heidelberg. pdf at springer.com
 ↑ ^{15.0} ^{15.1} ^{15.2} Guo, J., Peyrin, T., & Poschmann, A. (2011). The PHOTON family of lightweight hash functions. In Advances in Cryptology–CRYPTO 2011 (pp. 222239). Springer Berlin Heidelberg. pdf at google.com
 ↑ ^{16.0} ^{16.1} ^{16.2} Aumasson, J. P., Henzen, L., Meier, W., & NayaPlasencia, M. (2013). Quark: A lightweight hash. Journal of cryptology, 26(2), 313339. pdf at springer
 ↑ ^{17.0} ^{17.1} ^{17.2} Aumasson, J. P., & Bernstein, D. J. (2012). SipHash: a fast shortinput PRF. In Progress in CryptologyINDOCRYPT 2012 (pp. 489508). Springer Berlin Heidelberg. pdf at eprint.iacr.org
 ↑ ^{18.0} ^{18.1} ^{18.2} ^{18.3} Choy, J., Yap, H., Khoo, K., Guo, J., Peyrin, T., Poschmann, A., & Tan, C. H. (2012). SPNhash: improving the provable resistance against differential collision attacks. In Progress in CryptologyAFRICACRYPT 2012 (pp. 270286). Springer Berlin Heidelberg. pdf at ntu.edu.sg
 ↑ ^{19.0} ^{19.1} ^{19.2} Bogdanov, A., Knežević, M., Leander, G., Toz, D., Varıcı, K., & Verbauwhede, I. (2011). SPONGENT: A lightweight hash function. In Cryptographic Hardware and Embedded Systems–CHES 2011 (pp. 312325). Springer Berlin Heidelberg.pdf at kuleuven.be
 ↑ ^{20.0} ^{20.1} Abdelraheem, M. A. (2013). Estimating the probabilities of lowweight differential and linear approximations on PRESENTlike ciphers. In Information Security and Cryptology–ICISC 2012 (pp. 368382). Springer Berlin Heidelberg. pdf at springer