Practical (Second) Preimage Attacks on the TCS_SHA-3 Family of Cryptographic Hash Functions

Article information

Journal of Information Processing Systems. 2016;12(2):310-321

Publication date (electronic) : 2014 December 31

doi : https://doi.org/10.3745/JIPS.03.0021

Gautham Sekar ^*^,, Soumyadeep Bhattacharya ^**

^*Indian Statistical Institute, Chennai Centre, SETS Campus, MGR Knowledge City, CIT Campus, Taramani, Chennai 600113, India (sgautham@isichennai.res.in)

^**Institute of Mathematical Sciences, CIT Campus, Taramani, Chennai 600113, India (sbhtta@imsc.res.in)

Corresponding Author: Gautham Sekar (sgautham@isichennai.res.in)

Received 2013 October 21; Accepted 2014 January 17.

Abstract

TCS_SHA-3 is a family of four cryptographic hash functions that are covered by a United States patent (US 2009/0262925). The digest sizes are 224, 256, 384 and 512 bits. The hash functions use bijective functions in place of the standard compression functions. In this paper we describe first and second preimage attacks on the full hash functions. The second preimage attack requires negligible time and the first preimage attack requires O(2³⁶) time. In addition to these attacks, we also present a negligible time second preimage attack on a strengthened variant of the TCS_SHA-3. All the attacks have negligible memory requirements. To the best of our knowledge, there is no prior cryptanalysis of any member of the TCS_SHA-3 family in the literature.

Keywords: Cryptanalysis; Hash Function; (Second) Preimage Attack

1. Introduction

A hash function H takes an arbitrary length bit string M as input and outputs a fixed length bit string h (called hash value or digest). A cryptographic hash function is meant to satisfy certain security properties, the most important of which are listed below.

– First preimage resistance: given h, it is computationally infeasible to find an M such that H(M) = h.
– Second preimage resistance: given an M and H(M), it is computationally infeasible to find an M′ ≠ M such that H(M) = H(M′).
– Collision resistance: it is computationally infeasible to find an M and an M′, with M′ ≠ M, such that H(M) = H(M′).

The general model for cryptographic hash functions involves what is called a compression function. The function transforms a fixed-length bit string into a shorter, fixed-length bit string. The input message of a hash function, which is of arbitrary length, is partitioned into blocks of a fixed length (called the block length). However, before this can be done, it is required that the length of the message is a multiple of the block length. Given this and some security considerations, the message is ‘padded’ with bits in one of several ways (some padding schemes can be found in [1]). The message blocks are sequentially processed, with the compression function acting on the message blocks until all the blocks are processed. The end result is output as the digest. The general model for describing hash functions can be found in greater detail in [1].

A cryptographic hash function family is proposed by Vijayarangan of the Tata Consultancy Services (hereinafter called ‘TCS’) in [2]. The family is comprised of four hash functions, as four digest sizes (224, 256, 384, and 512 bits) are allowed. In [2], the hash functions are all actually called SHA-3, except in one or a few instances (see e.g., Clause 0095 of [2], where a member hash function is called TCS_SHA-3). However, as the name SHA-3 (with ‘SHA’ standing for ‘Secure Hash Algorithm’) has been in use by the National Institute of Standards and Technology (NIST), USA [3], we use the less common ‘TCS_SHA-3’ to denote the SHA-3 of [2]. Further, we denote by TCS_SHA-3-d the member that produces d-bit digests.

The design of TCS_SHA-3 deviates from the general model in that the compression function is replaced by a bijective function. This function uses a linear feedback shift register (LFSR) and a T-function. The design goals, as stated in [2], are to ‘prevent hash collisions’ and to ‘provide a secure hash function.’ This paper establishes that the design goals have not been met.

Motivation behind this work

The TCS, headquartered in India, is one of the largest IT services providers in the world, with annual revenue of more than $10 billion for 2011–2012 [4]. In May 2012, the company was named the fourth most valuable IT services brand worldwide, based on image, reputation and intellectual property assessments [5]. The company’s annual research report for 2007–2008 mentions the following [6]:

“In the current year, major work has been done on cryptographic algorithms and hash functions, which form the basis of all data security today. Past research products [from the E-Security group of the TCS Innovation Labs, Hyderabad, India,]… are in active use around the country (India) by various customers in the banking and financial services industry. Organizations using our technology, directly or indirectly, include the RBI [(Reserve Bank of India)], National Securities Depositories [sic] Limited (NSDL), Ministry of Company [sic] Affairs (MCA), and many public sector banks.”

Since TCS_SHA-3 is a product of the above-mentioned E-Security group of the TCS Innovation Labs [6], there appears to be sufficient motivation to evaluate the security of the hash function family.

Contributions of this paper

This paper makes three contributions. First, we report a second preimage attack that requires negligible time and negligible memory for nearly guaranteed success. Second, we describe a first preimage attack on the TCS_SHA-3-d that requires O(2²⁷ · d) time and negligible memory. Third, we present a second preimage attack, which also requires negligible time and negligible memory for nearly guaranteed success, on a strengthened variant of the TCS_SHA-3.

To the best of our knowledge, there is no prior published attack on the (strengthened) TCS_ SHA-3.

Organization of this paper

Section 2 describes the TCS_SHA-3 family of hash functions. A second preimage attack and the first preimage attack are respectively described in Sections 3 and 4. In Section 5, we present the second preimage attack on the strengthened TCS_SHA-3. We conclude in Section 6. Appendix A provides the results of our simulations of the first preimage attack.

2. Specifications

We will first list the notation and conventions, which are used in the rest of this paper, in Table 1.

Table 1

Notation and conventions

The TCS_SHA-3-d takes a message M of arbitrary length as input and returns a digest h (also denoted TCS_SHA-3-d(M)) of size d bits after the following sequence of processes, which include six ‘rounds.’

Padding: The input M is partitioned into k = ⌈|M|/d⌉ blocks (denoted M₁, …, M_k), where each is d bits in length. Clause 0068 of [2] states that an initialization vector (IV) of length d is added to a message if and only if the size of the message is less than d. The designer should have evidently mean the following: if and only if |M_k| < d, for any k ≥ 1, then M_k is added with the IV. Otherwise, the TCS_SHA-3 can only be applied to single block messages or multiple block messages, in which each one satisfies the condition d | |M|. For the simulations of Appendix A, we made the assignments IV = 1₂ || {0₂}^d^–1, d = 224, 256, 384, 512. The assignments are motivated by a case provided in [2] where the IV is chosen to be 1₂ || {0₂}²²³ when the size of the message is less than 224 bits. In our simulations, as well as in the aforesaid example case, the IV is XORed with the corresponding message block. In summary, the padding rule is defined as follows: for any k ≥ 1,

(1) Mk→Mk*:=Mk⊕IVif∣Mk∣ <d,Mk→Mk*:=Mkif∣Mk∣ =d.

An implicit assumption in the above discussion is that |M_k| is nonzero. Furthermore, when |M_k| = d, we infer that there is no extra ‘padding block’ that is appended to M. This is because, in such a case, there is no message block to which the IV (= 1₂ || {0₂}^d^–1) could be ‘added’.
Round 1: The first round has k steps; the steps are as follows:
1. Step 1 when k > 1: An arbitrarily chosen d′-bit (such that d′ ≤ d) constant c is XORed with M₁. The output, c ⊕ M₁, is input to a bijective function F (defined later in this section). Thus, a d-bit string, F(c ⊕ M₁), is output.
  
  Step 1 when k = 1: The arbitrarily chosen constant c is XORed with M1*. The output, c⊕M1*, is input to F. Thus, a d-bit string, F(c⊕M1*), is output.
2. Steps 2 to k (i.e., when k ≥ 2): Step i, 2 ≤ i ≤ k – 1, is given by the following recursion:
  
  (2) zi1=F(zi-11⊕Mi), z11:=F(c⊕M1);
  
  zl1 denotes the output of step l, 1 ≤ l ≤ k – 1, of round 1.
  
  Step k is given by:
  
  (3) zk1=F(zk-11⊕Mk*),
  
  where zk1 denotes the output of step k of round 1.
Round 2: Like round 1, round 2 also proceeds iteratively. The number of steps, s, is such that k “is not always the same as” s (see [2]). The input to round 2 is zk1, the final output of round 1. The steps are as follows:
1. Step 1: The d′-bit constant c is XORed with zk1. The output, c⊕zk1, is input to the bijective function F. Thereby, a d-bit string, F(c⊕zk1), is generated as output.
2. Steps 2 to s (i.e., when s ≥ 2): Step i, 2 ≤ i ≤ s, is given by the recursion:
  
  (4) zi2=F(zi-12⊕zk1), z12:=F(c⊕zk1);
  
  zl2 denotes the output of step l, 1 ≤ l ≤ s, of round 2.
Rounds 3 to 6: These rounds are similar to round 2. The number of steps in each of these rounds is, again, s. The input to round j, 3 ≤ j ≤ 6, is zsj-1 (i.e., the final output round j - 1 when zlj-1 denotes the output of step l, 1 ≤ l ≤ s, of round j - 1). The steps are as follows:
1. Step 1: Constant c is XORed with zsj-1. The output, c⊕zsj-1, is input to the bijective function F. Thereby, a d-bit string, F(c⊕zsj-1), is generated as output.
2. Steps 2 to s (i.e., when s ≥ 2):¹ Step i, 2 ≤ i ≤ s, is given by the recursion:
  
  (5) zij=F(zi-1j⊕zsj-1), z1j=F(c⊕zsj-1);
  
  zlj denotes the output of step l, 1 ≤ l ≤ s, of round j.

The d-bit digest h is simply the final output, zs6. Fig. 1 shows the working of TCS_SHA-3 works. As stated earlier, [2] only says that k is not always the same as s. Therefore, s may be greater than k. We make this clarification because Fig. 1 may misleadingly suggest that s is always less than k.²^, Algorithm 1 describes the function F: {0₂, 1₂}^d → {0₂, 1₂}^d.

Fig. 1

The working of TCS_SHA-3 (k ≥ 2) works.

Algorithm 1

The bijective function F:{0₂, 1₂}^d → {0₂, 1₂}^d

3. Second Preimage Attack on TCS_SHA-3

Let M=M1‖M2‖M3‖⋯‖Mk*, k ≥ 2, (when k = 2, M=M1‖M2*;; in general, when k = l > 2, M=M1‖M2‖⋯‖Ml*), denote the given message and h its hash value. Let y_i denote the input to the ith invocation of the function F (see Fig. 2). Let M′=M′1‖M′2‖M3‖⋯‖Mk*, with M1′≠M1 and M2′≠M2, denote another message, h′ its hash value, and yi′ the corresponding input to the ith invocation of F. It immediately follows from Fig. 2 that if y2′=y2, and then the outputs of round 1 are identical. This, in turn, implies that h′ = h (see Fig. 1) and we have a second preimage. The condition y2′=y2 implies that:

Fig. 2

Round 1 of TCS_SHA-3.

(6) F(M1⊕c)⊕M2=F(M1′⊕c)⊕M2′.

It is straightforward to see that the conditions:

(7) M2′=F(M1′⊕c)⊕M1′,

(8) M1′=M2⊕F(M1⊕c),

satisfy (6) and when M1′≠M1, we have a second preimage.⁴ Under reasonable assumptions of uniformity, the event M1′=M1 occurs with negligible probability.

4. First Preimage Attack on TCS_SHA-3

Fig. 3 illustrates Algorithm 1 for the (sample) case when d = 256.

Fig. 3

The bijective function F of TCS_SHA-3-256; S, T and L are 32-bit to 32-bit functions.

From Fig. 3, we see that the TCS_SHA-3-256 (and the TCS_SHA-3 per se) has poor diffusion properties. A difference in α_i, for any i ∈ {1, 2, …, d/32}, affects λ_i alone. A single-bit difference in α_i, for any i ∈ {1, 2, …, d/32}, is ideally expected to affect 16 bits of λ_i.

Let us consider the case when k = 1. Then, given an input difference ΔΓi(M1*) for some i ∈ {0, 1, …, d/32 – 1}, the differential characteristic is shown in Fig. 4. Algorithm 2 exploits this differential characteristic to recover M₁ from its corresponding digest value. In step 3 of this algorithm, in place of {0₂}³²ⁱ and {0₂}³²⁽^d ^{/ 32 –} ⁱ ^{– 1)}, one can respectively have any 32i-bit and 32(d/32 – i − 1)-bit value. We have used of {0₂}³²ⁱ and {0₂}³²⁽^d ^{/ 32 –} ⁱ ^{– 1)} for ease of understanding how the attack works.

Fig. 4

Differential characteristic for TCS_SHA-3-d when k = 1; non-zero differences are confined to the grey boxes.

Algorithm 2

Recovering M₁ from h when k = 1

Algorithm 2 requires that the attacker knows whether |M₁| = d or |M₁| < d. However, even without this information the attacker can, at the very least, recover all but the most significant bit of M₁ by simply computing M1=M1*⊕IV. This is explained as follows: suppose that |M₁| < d. Then, by computing M1=M1*⊕IV the attacker correctly recovers M₁. Now suppose that |M₁| = d. This time, the attacker is supposed to compute M₁ = M^*. Nevertheless, by computing M1=M1*⊕IV, the attacker is still able to correctly recover d – 1 least significant bits of M₁ because the IV is simply 1₂ || {0₂}^d^–1.

As we can see, Algorithm 2 has d/32 · 2³² = d · 2²⁷ iterations. Since d ≤ 512, single block messages can be recovered from their respective hash values in O (512 · 2²⁷) = O (2³⁶) time. Therefore, it may be extremely risky to use the TCS_SHA-3 for something like password hashing (a well-known application of cryptographic hash functions, see [9]).

For the case when k > 1, if the message blocks M₁, …, M_k–₁ are available to the attacker, then M_k may be recovered. The attack procedure is now given by Algorithm 2 with M₁ replaced by M_k and M1* by Mk*. Once again, the attacker is able to recover, at the very least, all but the most significant bit of M_k.

5. Cipher Block Chaining in Algorithm 1: Impact on Security

In Algorithm 1, the 32-bit words α₁, α₂, …, α_d_/32 are processed independently of one another (see Fig. 3). This is an inference that we draw from [2], which does not explicitly mention there being any dependence between the processing of α_i and the processing of α_i₊₁, 1 ≤ i ≤ d/32 − 1. Furthermore, [2] provides several implementation results, but the corresponding implementation is missing. We were therefore unable to verify the correctness of the implementation results of [2]. If the implementation results are correct, then the processing of α_i and the processing of α_i₊₁, 1 ≤ i ≤ d/32 − 1, may not be independent (see e.g., [2]). However, even in such a case, the existence of dependence must have been clearly mentioned in [2] in any of the clauses preceding Clause 0087.

When there is dependence in the form of chaining, given the structural similarities between TCS_SHA-3 and Khichidi-1 (see [7]), it appears reasonable to expect the chaining mechanisms in the two cases to be identical. From [7] then, we see that Fig. 2 changes to Fig. 5 when k = 2.⁵^,,⁶^, Clearly this would also mean that FIGURE 3 of [2] is incorrect.

Fig. 5

Round 1 of TCS_SHA-3 (k = 2) with 32-bit cipher block chaining; α_1, _j = Γ_d_/32–_j (M₁) and α2,j=Γd/32-j(M2*), for all j ∈ {1, 2, …, d/32}.

Note: If one goes by [7], then in Fig. 5, Γ0(z11) is not XORed with α_{2, 1}, instead Γ_d_/32–1 (c) is assigned the value of Γ0(z11) once M₁ is processed. This may be inferred, for example, from the statement, ‘H0(i)=H7(i)’ in [7] (which, in fact, happens to be the only statement in the Khichidi-1 algorithms of [7] to describe the chaining process in 224-bit Khichidi-1). If, on the other hand, the statement had read ‘H0(i+1)=H7(i)’, then the chaining process would have appeared meaningful. Therefore, we presume that the chaining statements in the Khichidi-1 algorithms of [7] are typographically flawed in the manner described above.

However, the case of the aforementioned independent processing of the 32-bit blocks complies with FIGURE 3 of [2] and thus enhances our belief in the correctness of the above-mentioned inference of independent processing of the α_i′s (1 ≤ i ≤ d/32). Yet we shall now examine the impact of cipher block chaining in Algorithm 1.

Let M=M1‖M2‖M3‖⋯‖Mk*, k ≥ 2 (when k = 2, M=M1‖M2*; in general, when k = l > 2, M=M1‖M2‖⋯‖Ml*), denote the message and h its hash value. Let M′=M1′‖M2′‖M3‖⋯‖Mk*, with M1′≠M1 and M2′≠M2, denote another message and h′ its hash value. We now define the following for all j ∈ {1, 2, …, d/32}:

(9) αi,j:=Γd/32-j(Mi)when i<k,αi,j:=Γd/32-j(Mk*)when i=k.

Suppose that the conditions M1′≠M1 and M2′≠M2 are such that α1,i=α1,i′ for all i ∈ {1, 2, …, d/32 – 1} and α2,i=α2,i′ and for all i ∈ {2, …, d/32}. Then, from Fig. 5, it follows that h′ = h when the following condition is satisfied:

(10) g(α1,d/32⊕θ)⊕α2,1=g(α′1,d/32⊕θ)⊕α′2,1.

It is straightforward to see that the conditions:

(11) α2,1′=g(α′1,d/32⊕θ)⊕α′1.d/32,

(12) α′1,d/32=α2,1⊕g(α1,d/32⊕θ),

satisfy (10) and when α′_1, _d/₃₂ ≠ α_1, _d_/32, we have a second preimage. Under reasonable assumptions of uniformity, the event α′_1, _d/₃₂ = α_1, _d_/32 occurs with negligible probability.

6. Conclusions and Open Problems

In this paper, we have presented what we see as being the first practical (second) preimage attacks on the TCS_SHA-3 family of patented cryptographic hash functions. The second preimage attack requires negligible time and negligible memory for nearly guaranteed success. The attack works when the number of message blocks is at least two. The first preimage attack requires O(2³⁶) time and negligible memory. This attack is most efficient (going by data requirements) on single block messages -- negligible data is required in such cases. We have also reported a negligible time/memory second preimage attack on the TCS_SHA-3 that is strengthened with 32-bit cipher block chaining. This attack also works only when the number of message blocks is at least two.

Our findings establish, amongst other things, that the TCS_SHA-3 may be particularly unsuitable for password hashing (unless, for example, it is strengthened with 32-bit cipher block chaining).

It may be an interesting exercise to find countermeasures to our attacks.

Notes

Perhaps the only criterion that s must satisfy is s > 1; otherwise, the TCS_SHA-3-d will have only one round.

The (second) preimage attacks that we report in this paper are independent of the value of s, which is due to reasons that would be understood from Sections 3 and 4.

We omit the full description of the LFSR as it is elaborate and not relevant to our analysis (to be understood from Sections 3 and 4). In [2], the LFSR is described in Clauses 0078-0083.

⁴

A similar correcting block attack on the hash function Khichidi-1 [7] has been reported by Mouha [8].

⁵

The bijective function g: {0₂, 1₂}³² → {0₂, 1₂}³² of Fig. 5 is given by Algorithm 3.

Algorithm 3

The bijective function g:{0₂, 1₂}³² → {0₂, 1₂}³²

⁶

See Fig. 5. Clause 0069 of [2] states that |c| ≤ d. If |c| = e < d, then c ← {0₂}^d–e || c. We find no mention in [2] that it is the most significant word of c that is XORed with α_{1, 1}; we simply make such an assumption without the loss of generality.

References

1. Preneel B. Analysis and design of cryptographic hash functions. PhD dissertation Katholieke Universiteit Leuven; Belgium: 1993.

2. Vijayarangan N. Method for designing a secure hash function and a system thereof. US Patent 20090262925. Oct. 22. 2009.

3. National Institute of Standards and Technology. Cryptographic hash algorithm competition http://csrc.nist.gov/groups/ST/hash/sha-3/index.html.

4. Tata Consultancy Services. TCS annual report 2011–2012 http://www.tcs.com/investors/Documents/Annual%20Reports/TCS_Annual_Report_2011-2012.pdf.

5. Tata Consultancy Services. TCS recognized as Big Four IT Services brand http://www.tcs.com/news_events/press_releases/Pages/TCS_recognized_Big_Four_IT_Services_brand.aspx.

6. Tata Consultancy Services. TCS annual report 2007–2008 http://www.tcs.com/investors/Documents/Annual%20Reports/TCS_Annual_Report_2007_2008.PDF.

7. Vijayarangan N. A new hash algorithm: Khichidi-1 2008. http://ehash.iaik.tugraz.at/uploads/d/d4/Khichidi-1.pdf.

8. Mouha N. Automated techniques for hash function and block cipher cryptanalysis. Ph.D. dissertation Katholieke Universiteit Leuven; Belgium: 2012.

9. Preneel B. The state of cryptographic hash functions. Lectures on Data Security Heidelberg: Springer; 1999. p. 158–182.

10. National Institute of Standards and Technology. Khichidi-1 package http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Khichidi-1.zip.

Appendices

Appendix A Experiments

We took a few sample outputs of TCS_SHA-3 and attempted to verify their first preimages. Simulations were performed on a NVIDIA GeForce GT 540M graphics processing unit (GPU) having 96 CUDA cores (2 multiprocessors × 48 CUDA cores / multiprocessor) and a clock rate of 1.34 GHz. The CUDA C compiler nvcc 4.2 was used. Below is a list of assignments made for the simulations and their justifications (see also ^{footnotes 1}^,–³ and Section 4).

– See ^{footnote 6}. As the value of c has no bearing on the analysis or the experiments, we assign the value {0₂}^d to c.
– The IV is 1₂ || {0₂}^d^–1 (see Section 2).
– The value of s is taken to be the value of s in Khichidi-1 (see [7] and khichidi.c in the URL provided in [10]), and is therefore equal to 2.
– The value of η_i is 1 for all i ∈ {1, 2, …, 6}; the number of LFSR shifts in round i of Khichidi-1 is also 1 for all i ∈ {1, 2, …, 6} (see [7] and khichidi.c in the URL provided in [10]).

The system time taken to find the first preimage for each output, given the above set of assignments, is provided in Table 2. These system times are expected to remain unaltered when a different IV or c is used.

Table 2

First preimage samples

As shown in Sections 2 and 4, it follows that the time/memory complexity of our first preimage attack does not change when one or more of the above-listed assignments are altered.

Biography

Gautham Sekar

He received his bachelor’s degree in Electronics and Instrumentation Engineering from the Birla Institute of Technology and Science, Pilani, in June 2006. He simultaneously graduated with a master’s degree in Physics from the same institute. In November 2006, he joined the COSIC (Computer Security and Industrial Cryptography) group of the Katholieke Universiteit Leuven, Belgium, as a pre-doctoral student and from October 2007 to March 2011 he worked there as a doctoral student under the supervision of Prof. Dr. Bart Preneel. Upon obtaining his Ph.D., he worked at the National University of Singapore as a Research Scientist until March 2012. Since then, he is a Visiting Assistant Professor at the Indian Statistical Institute, Chennai Centre. In May 2007, he received the Dr. Ranjit Singh Chauhan Undergraduate Research Award from the Birla Institute of Technology and Science, Pilani. His research interests include cryptography, cryptanalysis, and information security in general.

Soumyadeep Bhattacharya http://orcid.org/0000-0002-9386-7513

He received his bachelor’s degree in Electrical and Electronics Engineering and master’s degree in Physics from the Birla Institute of Technology and Science, Pilani, in June 2010. He is currently a Senior Research Fellow in Theoretical Physics at The Institute of Mathematical Sciences, Chennai. His research interests are statistical physics and parallel computing.

Article information Continued

(open-access) :

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Require: d-bit input α
Ensure: d-bit output λ
1.	Partition: α → α₁ \|\| α₂ \|\| ··· \|\| α_d_/32 such that \|α_i\| = 32 for all 1 ≤ i ≤ d/32;
2.	Shuffle: α_i → β₁, for all 1 ≤ i ≤ d/32, such that β_i₍_j₎ = α_i₍_j_/2) if 2 \| j and β_i₍_j₎ = α_i₍₁₆₊₍_j_–1)/2)) otherwise;
3.	Apply T-function: βi→γi:=2 βi2+βi mod 232, mod 2³², for all 1 ≤ i ≤ d/32;
4.	Apply LFSR: γ_i → λ_i, for all 1 ≤ i ≤ d/32, such that \|λ_i \| = 32;³
5.	Concatenate: λ := λ₁ \|\| λ₂ \|\| ··· \|\| λ_d_/32;

Require: Whether \|M₁\| = d or \|M₁\| < d
Ensure: d-bit output M₁
1.	for i = 0 → d/32 − 1 do
2.	for j = {0₂}³² → {1₂}³² do
3.	l ← {0₂}³²⁽^d^/3–ⁱ^–1) \|\| j \|\| {0₂}³²ⁱ;
4.	Compute ħ := TCS_SHA-3-d(l);
5.	if Γ_i (ħ) = Γ_i (h) then
6.	Γi(M1*)←j;
7.	break;
8.	else
9.	j ← j + 1;
10.	i ← i + 1;
11.	Compute M1=Γd/32-1(M1)‖Γd/32-2(M1)‖⋯‖Γ0(M1);
12.	if \|M₁\| < d then
13.	Output M1=M1*⊕IV;
14.	else
15.	Output M₁ = M^*;

Require: 32-bit input α
Ensure: 32-bit output λ
1.	Shuffle: α → β such that β ₍_j₎ = α₍_j_/2) if 2 \| j and β ₍_j₎ = α₍₁₆₊₍_j_–1)/2) otherwise;
2.	Apply T-function: β → γ := 2 β² + β mod 2³²;
3.	Apply LFSR: γ → λ such that \|λ\| = 32;

Digest length (bits)	Output of hash function (in hex)	Preimage	Time taken (second)
224	F18DE455 827C1EE6 00000000 00000000 00000000 00000000 00000000	‘password’	28.66
256	F18DE455 827C1EE6 00000000 00000000 00000000 00000000 00000000 00000000	‘password’	28.67
384	F18DE455 827C1EE6 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000	‘password’	28.74
512	F18DE455 827C1EE6 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000	‘password’	28.80
224	2C2B32B7 305056B5 709FF3A9 7A99955B 3D271585 78E21E7E 2848DD92	‘The quick brown fox Jumps’	91.28
256	2C2B32B7 305056B5 709FF3A9 7A99955B 3D271585 78E21E7E CC1779EB A3ED2089	‘The quick brown fox jumps over’	103.80
384	2C2B32B7 305056B5 709FF3A9 7A99955B 3D271585 78E21E7E CC1779EB 37407107 89D12C8B EA6630B4 3929A26F 00000000	‘The quick brown fox jumps over the lazy dog’	141.08
512	2C2B32B7 305056B5 709FF3A9 7A99955B 3D271585 78E21E7E CC1779EB 37407107 89D12C8B EA6630B4 3929A26F 00000000 00000000 00000000 00000000 00000000	‘The quick brown fox jumps over the lazy dog’	141.14

Symbol/notation	Meaning
Γ_i(ω)	ith 32-bit word (i = 0 denotes the least significant word) of d-bit ω
\| x \|	length, in bits, of x
x₍ _i ₎	ith bit (i = 0 denotes the least significant bit) of x
x \|\| y	concatenation of two 32-bit words, x and y
⊕	exclusive OR (XOR)
0₂, 1₂	bit 0, bit 1