FIPS PUB 202
FEDERAL INFORMATION PROCESSING STANDARDS
PUBLICATION

SHA-3 Standard: Permutation-Based Hash and
Extendable-Output Functions

CATEGORY: COMPUTER SECURITY

SUBCATEGORY: CRYPTOGRAPHY

Information Technology Laboratory
National Institute of Standards and Technology
Gaithersburg, MD 20899-8900
This publication is available free of charge from:
http://dx.doi.org/10.6028/NIST.FIPS.202
August 2015

U.S. Department of Commerce
Penny Pritzker, Secretary
National Institute of Standards and Technology
Willie May, Under Secretary of Commerce for Standards and Technology and Director

FOREWORD
The Federal Information Processing Standards (FIPS) Publication Series of the National
Institute of Standards and Technology (NIST) is the official series of publications relating
to standards and guidelines adopted and promulgated under the provisions of the Federal
Information Security Management Act (FISMA) of 2002.
Comments concerning FIPS publications are welcomed and should be addressed to the
Director, Information Technology Laboratory, National Institute of Standards and
Technology, 100 Bureau Drive, Stop 8900, Gaithersburg, MD 20899-8900.
Charles H. Romine, Director
Information Technology Laboratory

ii

Abstract
This Standard specifies the Secure Hash Algorithm-3 (SHA-3) family of functions on
binary data. Each of the SHA-3 functions is based on an instance of the KECCAK
algorithm that NIST selected as the winner of the SHA-3 Cryptographic Hash Algorithm
Competition. This Standard also specifies the KECCAK-p family of mathematical
permutations, including the permutation that underlies KECCAK, in order to facilitate the
development of additional permutation-based cryptographic functions.
The SHA-3 family consists of four cryptographic hash functions, called SHA3-224,
SHA3-256, SHA3-384, and SHA3-512, and two extendable-output functions (XOFs),
called SHAKE128 and SHAKE256.
Hash functions are components for many important information security applications,
including 1) the generation and verification of digital signatures, 2) key derivation, and 3)
pseudorandom bit generation. The hash functions specified in this Standard supplement
the SHA-1 hash function and the SHA-2 family of hash functions that are specified in
FIPS 180-4, the Secure Hash Standard.
Extendable-output functions are different from hash functions, but it is possible to use
them in similar ways, with the flexibility to be adapted directly to the requirements of
individual applications, subject to additional security considerations.

Key words: computer security, cryptography, extendable-output function, Federal
Information Processing Standard, hash algorithm, hash function, information security,
KECCAK, message digest, permutation, SHA-3, sponge construction, sponge function,
XOF.

iii

Federal Information
Processing Standards Publication 202
August 2015
Announcing the

SHA-3 STANDARD: PERMUTATION-BASED HASH
AND EXTENDABLE OUTPUT FUNCTIONS
Federal Information Processing Standards Publications (FIPS PUBS) are issued by the National
Institute of Standards and Technology (NIST) after approval by the Secretary of Commerce
pursuant to Section 5131 of the Information Technology Management Reform Act of 1996
(Public Law 104-106), and the Computer Security Act of 1987 (Public Law 100-235).
1. Name of Standard: SHA-3 Standard: Permutation-Based Hash and Extendable-Output
Functions (FIPS PUB 202).
2. Category of Standard: Computer Security Standard, Cryptography.
3. Explanation: This Standard (FIPS 202) specifies the Secure Hash Algorithm-3 (SHA-3)
family of functions on binary data. Each of the SHA-3 functions is based on an instance of the
KECCAK algorithm that NIST selected as the winner of the SHA-3 Cryptographic Hash
Algorithm Competition. This Standard also specifies the KECCAK-p family of mathematical
permutations, including the permutation that underlies KECCAK, which can serve as the main
components of additional cryptographic functions that may be specified in the future.
The SHA-3 family consists of four cryptographic hash functions and two extendable-output
functions (XOFs). The cryptographic hash functions are called SHA3-224, SHA3-256, SHA3384, and SHA3-512; and the XOFs are called SHAKE128 and SHAKE256.
For hash functions, the input is called the message, and the output is called the (message) digest
or the hash value. The length of the message can vary; the length of the digest is fixed. A
cryptographic hash function is a hash function that is designed to provide special properties,
including collision resistance and preimage resistance, that are important for many applications
in information security. For example, a cryptographic hash function increases the security and
efficiency of a digital signature scheme when the digest is digitally signed instead of the message
itself. In this context, the collision resistance of the hash function provides assurance that the
original message could not have been altered to a different message with the same hash value,
and hence, the same signature. Other applications of cryptographic hash functions include
pseudorandom bit generation, message authentication codes, and key derivation functions.

iv

The four SHA-3 hash functions specified in this Standard supplement the hash functions that are
specified in FIPS 180-4 [1]: SHA-1 and the SHA-2 family. Together, both Standards provide
resilience against future advances in hash function analysis, because they rely on fundamentally
different design principles. In addition to design diversity, the hash functions in this Standard
provide some complementary implementation and performance characteristics to those in FIPS
180-4.
For XOFs, the length of the output can be chosen to meet the requirements of individual
applications. The XOFs can be specialized to hash functions, subject to additional security
considerations, or used in a variety of other applications. The approved uses of XOFs will be
specified in NIST Special Publications.
The KECCAK-p permutations were designed to be suitable as the main components for a variety
of cryptographic functions, including keyed functions for authentication and/or encryption. The
six SHA-3 functions can be considered as modes of operation (modes) of the KECCAKp[1600,24] permutation. In the future, additional modes of this permutation or other KECCAK-p
permutations may be specified and approved in FIPS publications or in NIST Special
Publications.
4. Approving Authority: Secretary of Commerce.
5. Maintenance Agency: U.S. Department of Commerce, National Institute of Standards and
Technology (NIST), Information Technology Laboratory (ITL).
6. Applicability: This Standard is applicable to all Federal departments and agencies for the
protection of sensitive unclassified information that is not subject to Title 10 United States Code
Section 2315 (10 USC 2315) and that is not within a national security system as defined in Title
40 United States Code Section 11103(a)(1) (40 USC 11103(a)(1)). Either this Standard or
Federal Information Processing Standard (FIPS) 180 must be implemented wherever a secure
hash algorithm is required for Federal applications, including as a component within other
cryptographic algorithms and protocols. This Standard may be adopted and used by non-Federal
Government organizations.
7. Specifications: Federal Information Processing Standard (FIPS) 202, SHA-3 Standard:
Permutation-Based Hash and Extendable-Output Functions (affixed).
8. Implementations: Federal departments and agencies shall only use implementations of the
KECCAK-p permutations within FIPS-approved or NIST-recommended modes of operation, such
as the SHA-3 functions that are specified in this Standard. The SHA-3 functions may be
implemented in software, firmware, hardware or any combination thereof. Only implementations
of these functions that are validated by the Cryptographic Algorithm Validation Program will be
considered as complying with this Standard. Information about the validation program can be
obtained at http://csrc.nist.gov/groups/STM/cavp/index.html.

v

9. Implementation Schedule: This Standard is effective immediately. Applications or
extensions of this Standard that depend upon the release of new or revised NIST Special
Publications are effective upon final publication of the supporting Special Publications.
10. Patents: Implementations of the SHA-3 functions in this Standard may be covered by U.S. or
foreign patents.
11. Export Control: Certain cryptographic devices and technical data regarding them are
subject to Federal export controls. Exports of cryptographic modules implementing this Standard
and technical data regarding them must comply with these Federal regulations and be licensed by
the Bureau of Export Administration of the U.S. Department of Commerce. Information about
export regulations is available at: http://www.bis.doc.gov/index.htm.
12. Qualifications: Although this Standard specifies mathematical functions that are suitable
components for information security applications, conformance to this Standard does not assure
that a particular implementation is secure. The responsible authority in each agency or
department shall assure that an overall implementation provides an acceptable level of security.
This Standard will be reviewed every five years in order to assess its adequacy.
13. Waiver Procedure: The Federal Information Security Management Act (FISMA) does not
allow for waivers to a FIPS that is made mandatory by the Secretary of Commerce.
14. Where to Obtain Copies of the Standard: This publication is available electronically at
http://csrc.nist.gov/publications/. Other computer security publications issued by NIST are
available at the same web site.

vi

Federal Information Processing Standards Publication 202
Specifications for the

SHA-3 STANDARD: PERMUTATION-BASED
HASH AND EXTENDABLE-OUTPUT FUNCTIONS
1

INTRODUCTION ................................................................................................................................................1

2

GLOSSARY ..........................................................................................................................................................2
2.1
2.2
2.3
2.4

3

TERMS AND ACRONYMS ....................................................................................................................2
ALGORITHM PARAMETERS AND OTHER VARIABLES ..........................................................................4
BASIC OPERATIONS AND FUNCTIONS .................................................................................................5
SPECIFIED FUNCTIONS .......................................................................................................................6

KECCAK-P PERMUTATIONS..........................................................................................................................7
3.1

3.2

3.3
3.4

STATE ................................................................................................................................................7
3.1.1 Parts of the State Array ........................................................................................................8
3.1.2 Converting Strings to State Arrays .......................................................................................9
3.1.3 Converting State Arrays to Strings ..................................................................................... 10
3.1.4 Labeling Convention for the State Array ............................................................................ 11
STEP MAPPINGS ............................................................................................................................... 11
3.2.1 Specification of θ ................................................................................................................ 11
3.2.2 Specification of ρ ................................................................................................................ 12
3.2.3 Specification of π ................................................................................................................ 14
3.2.4 Specification of χ ................................................................................................................ 15
3.2.5 Specification of ι ................................................................................................................. 15
KECCAK-p[b, nr] .............................................................................................................................. 16
COMPARISON WITH KECCAK-f ......................................................................................................... 17

4

SPONGE CONSTRUCTION ............................................................................................................................ 17

5

KECCAK ............................................................................................................................................................. 19
5.1
5.2

6

SPECIFICATION OF pad10*1 ............................................................................................................. 19
SPECIFICATION OF KECCAK[c] ......................................................................................................... 20

SHA-3 FUNCTION SPECIFICATIONS .......................................................................................................... 20
6.1
6.2
6.3

SHA-3 HASH FUNCTIONS ................................................................................................................ 20
SHA-3 EXTENDABLE-OUTPUT FUNCTIONS ..................................................................................... 20
ALTERNATE DEFINITIONS OF SHA-3 EXTENDABLE-OUTPUT FUNCTIONS ....................................... 21

7

CONFORMANCE .............................................................................................................................................. 21

A

SECURITY ......................................................................................................................................................... 23
A.1
A.2

B

SUMMARY........................................................................................................................................ 23
ADDITIONAL CONSIDERATION FOR EXTENDABLE-OUTPUT FUNCTIONS .......................................... 24

EXAMPLES........................................................................................................................................................ 25
B.1
B.2

CONVERSION FUNCTIONS ................................................................................................................ 26
HEXADECIMAL FORM OF PADDING BITS .......................................................................................... 27

C

OBJECT IDENTIFIERS ................................................................................................................................... 28

D

REFERENCES ................................................................................................................................................... 28

vii

Figures
Figure 1: Parts of the state array, organized by dimension [8] ...................................................... 8
Figure 2: The x, y, and z coordinates for the diagrams of the step mappings .............................. 11
Figure 3: Illustration of θ applied to a single bit [8] .................................................................... 12
Figure 4: Illustration of ρ for b = 200 [8] ..................................................................................... 13
Figure 5: Illustration of π applied to a single slice [8] ................................................................. 14
Figure 6: Illustration of χ applied to a single row [8] .................................................................. 15
Figure 7: The sponge construction: Z = SPONGE[f, pad, r](N, d) [4] ............................................ 18
Tables
Table 1: KECCAK-p permutation widths and related quantities ..................................................... 7
Table 2: Offsets of ρ [8] ............................................................................................................... 13
Table 3: Input block sizes for HMAC.......................................................................................... 22
Table 4: Security strengths of the SHA-1, SHA-2, and SHA-3 functions ................................... 23
Table 5: Illustration of h2b .......................................................................................................... 27
Table 6: Hexadecimal Form of SHA-3 Padding for Byte-Aligned Messages ............................. 28

viii

1 INTRODUCTION
This Standard specifies a new family of functions that supplement SHA-1 and the SHA-2 family
of hash functions specified in FIPS 180-4 [1]. This family, called SHA-3 (Secure Hash
Algorithm-3), is based on KECCAK [2]—the algorithm1 that NIST selected as the winner of the
public SHA-3 Cryptographic Hash Algorithm Competition [3]. The SHA-3 family consists of
four cryptographic hash functions and two extendable-output functions. These six functions
share the structure that is described in [4], namely, the sponge construction; functions with this
structure are called sponge functions.
A hash function is a function on binary data (i.e., bit strings) for which the length of the output is
fixed.2 The input to a hash function is called the message, and the output is called the (message)
digest or hash value. The digest often serves as a condensed representation of the message. The
four SHA-3 hash functions are named SHA3-224, SHA3-256, SHA3-384, and SHA3-512; in
each case, the suffix after the dash indicates the fixed length of the digest, e.g., SHA3-256
produces 256-bit digests. The SHA-2 functions, i.e., SHA-224, SHA-256, SHA-384 SHA-512,
SHA-512/224, and SHA-512/256, offer the same set of digest lengths. Thus, the SHA-3 hash
functions can be implemented as alternatives to the SHA-2 functions, or vice versa.
An extendable-output function (XOF) is a function on bit strings (also called messages) in which
the output can be extended to any desired length. The two SHA-3 XOFs are named SHAKE128
and SHAKE256.3 The suffixes “128” and “256” indicate the security strengths that these two
functions can generally4 support, in contrast to the suffixes for the hash functions, which indicate
the digest lengths. SHAKE128 and SHAKE256 are the first XOFs that NIST has standardized.
The six SHA-3 functions are designed to provide special properties, such as resistance to
collision, preimage, and second preimage attacks. The level of resistance to these three types of
attacks is summarized in Sec. A.1. Cryptographic hash functions are fundamental components in
a variety of information security applications, such as digital signature generation and
verification, key derivation, and pseudorandom bit generation.
The digest lengths in FIPS-approved hash functions are 160, 224, 256, 384, and 512 bits. When
an application requires a cryptographic hash function with a non-standard digest length, an XOF
is a natural alternative to constructions that involve multiple invocations of a hash function
and/or truncation of the output bits. However, XOFs are subject to the additional security
consideration that is described in Sec. A.2.
Each of the six SHA-3 functions employs the same underlying permutation as the main
component in the sponge construction. In effect, the SHA-3 functions are modes of operation

1

More precisely, the competition called for four hash functions, and KECCAK is a larger family of functions.
For many hash functions, there is a (very large) bound on the length of the input data.
3
The name “SHAKE” was proposed in [5] to combine the term “Secure Hash Algorithm” with “KECCAK.”
4
An exception is when the output length is sufficiently small; see the discussion in Sec. A.1.
2

1

(modes) of the permutation. In this Standard, the permutation is specified as an instance of a
family of permutations, called KECCAK-p, in order to provide the flexibility to modify its size
and security parameters in the development of any additional modes in future documents.
The four SHA-3 hash functions differ slightly from the instances of KECCAK that were proposed
for the SHA-3 competition [3]. In particular, a two-bit suffix is appended to the messages, in
order to distinguish the SHA-3 hash functions from the SHA-3 XOFs, and to facilitate the
development of new variants of the SHA-3 functions that can be dedicated to individual
application domains.
The two SHA-3 XOFs are also specified in a manner that allows for the development of
dedicated variants. Moreover, the SHA-3 XOFs are compatible with the Sakura coding scheme
[6] for tree hashing [7], in order to support the development of parallelizable variants of the
XOFs, to be specified in a separate document.
Most of the notation and terminology in this Standard is consistent with the specification of
KECCAK in [8].

2 GLOSSARY
2.1 Terms and Acronyms
bit

A binary digit: 0 or 1. In this Standard, bits are indicated in the Courier
New font.

byte

A sequence of eight bits.

capacity

In the sponge construction, the width of the underlying function minus the
rate.

column

For a state array, a sub-array of five bits with constant x and z coordinates.

digest

The output of a cryptographic hash function. Also called the hash value.

domain separation

For a function, a partitioning of the inputs to different application domains
so that no input is assigned to more than one domain.

extendable-output
function (XOF)

A function on bit strings in which the output can be extended to any
desired length.

FIPS

Federal Information Processing Standard.

FISMA

Federal Information Security Management Act.

hash function

A function on bit strings in which the length of the output is fixed. The
output often serves as a condensed representation of the input.
2

hash value

See digest.

HMAC

Keyed-Hash Message Authentication Code.

KDF

Key derivation function.

KECCAK

The family of all sponge functions with a KECCAK-f permutation as the
underlying function and multi-rate padding as the padding rule. KECCAK
was originally specified in [8].

lane

For a state array of a KECCAK-p permutation with width b, a sub-array of
b/25 bits with constant x and y coordinates.

message

A bit string of any length that is the input to a SHA-3 function.

multi-rate padding

The padding rule pad10*1, whose output is a 1, followed by a (possibly
empty) string of 0s, followed by a 1.

NIST

National Institute of Standards and Technology.

plane

For a state array of a KECCAK-p permutation with width b, a sub-array of
b/5 bits with a constant y coordinate.

rate

In the sponge construction, the number of input bits processed or output
bits generated per invocation of the underlying function.

round

The sequence of step mappings that is iterated in the calculation of a
KECCAK-p permutation.

round constant

For each round of a KECCAK-p permutation, a lane value that is
determined by the round index. The round constant is the second input to
the ι step mapping.

round index

The value of the integer index for the rounds of a KECCAK-p permutation.

row

For a state array, a sub-array of five bits with constant y and z coordinates.

SHA-3

Secure Hash Algorithm-3.

SHAKE

Secure Hash Algorithm KECCAK.

sheet

For a state array of a KECCAK-p permutation with width b, a sub-array of
b/5 bits with a constant x coordinate.

slice

For a state array, a sub-array of 25 bits with a constant z coordinate.

3

sponge construction The method originally specified in [4] for defining a function from the
following: 1) an underlying function on bit strings of a fixed length, 2) a
padding rule, and 3) a rate. Both the input and the output of the resulting
function are bit strings that can be arbitrarily long.
sponge function

A function that is defined according to the sponge construction, possibly
specialized to a fixed output length.

state

An array of bits that is repeatedly updated within a computational
procedure. For a KECCAK-p permutation, the state is represented either as
a three-dimensional array or as a bit string.

state array

For a KECCAK-p permutation, a 5-by-5-by-w array of bits that represents
the state. The indices for the x, y, and z coordinates range from 0 to 4, 0 to
4, and 0 to w-1, respectively.

step mapping

One of the five components of a round of a KECCAK-p permutation: θ, ρ,
π, χ, or ι.

string

For a nonnegative integer m, a sequence of m symbols.

width

In the sponge construction, the fixed length of the inputs and the outputs
of the underlying function.

XOF

See extendable-output function.

XOR

The Boolean Exclusive-OR operation, denoted by the symbol .

2.2 Algorithm Parameters and Other Variables
A

A state array.

A[x, y, z]

For a state array A, the bit that corresponds to the triple (x, y, z).

b

The width of a KECCAK-p permutation in bits.

c

The capacity of a sponge function.

d

The length of the digest of a hash function or the requested length of the
output of an XOF, in bits.

f

The generic underlying function for the sponge construction.

ir

The round index for a KECCAK-p permutation.

J

The input string to RawSHAKE128 or RawSHAKE256.

4

l

For a KECCAK-p permutation, the binary logarithm of the lane size, i.e.,
log2(w).

Lane (i, j)

For a state array A, a string of all the bits of the lane whose x and y
coordinates are i and j.

M

The input string to a SHA-3 hash or XOF function.

N

The input string to SPONGE[f, pad, r] or KECCAK[c].

nr

The number of rounds for a KECCAK-p permutation.

pad

The generic padding rule for the sponge construction.

Plane (j)

For a state array A, a string of all the bits of the plane whose y coordinate
is j.

r

The rate of a sponge function.

RC

For a round of a KECCAK-p permutation, the round constant.

w

The lane size of a KECCAK-p permutation in bits, i.e., b/25.

2.3 Basic Operations and Functions
0s

For a positive integer s, 0s is the string that consists of s consecutive 0s. If
s = 0, then 0s is the empty string.

len(X)

For a bit string X, len(X) is the length of X in bits.

X[i]

For a string X and an integer i such that 0 ≤ i < len(X), X[i] is the bit of X
with index i. Bit strings are depicted with indices increasing from left to
right, so that X[0] appears at the left, followed by X[1], etc. For example,
if X = 101000, then X[2] = 1.

Truncs (X)

For a positive integer s and a string X, Truncs (X) is the string comprised of
bits X[0] to X[s – 1]. For example, Trunc2(10100) = 10.

XY

For strings X and Y of equal bit length, X  Y is the string that results from
applying the Boolean exclusive-OR operation to X and Y at each bit
position. For example, 1100 ⊕ 1010 = 0110.

X || Y

For strings X and Y, X || Y is the concatenation of X and Y. For example,
11001 || 010 = 11001010.

m/n

For integers m and n, m/n is the quotient, i.e., m divided by n.
5

m mod n

For integers m and n, m mod n is the integer r for which 0 ≤ r < n and mr
is a multiple of n. For example, 11 mod 5 = 1, and 11 mod 5 = 4.

x

For a real number x, x is the least integer that is not strictly less than x.
For example, 3.2 = 4, 3.2 = 3, and 6 = 6.

log2(x)

For a positive real number x, log2(x) is the real number y such that 2y = x.

min(x, y)

For real numbers x and y, min(x, y) is the minimum of x and y. For
example, min(9, 33) = 9.

2.4 Specified Functions
The following higher-level functions are specified in this Standard:
θ, ρ, π, χ, ι

The five step mappings that comprise a round.

KECCAK[c]

The KECCAK instance with KECCAK-f [1600] as the underlying permutation
and capacity c.

KECCAK-f [b]

The family of seven permutations originally specified in [8] as the
underlying function for KECCAK. The set of values for the width b of the
permutations is {25, 50, 100, 200, 400, 800, 1600}.

KECCAK-p[b, nr]

The generalization of the KECCAK-f [b] permutations that is defined in this
Standard by converting the number of rounds nr to an input parameter.

pad10*1

The multi-rate padding rule for KECCAK, originally specified in [8].

RawSHAKE128

An intermediate function in the alternate definition of SHAKE128.

RawSHAKE256

An intermediate function in the alternate definition of SHAKE256.

rc

The function that generates the variable bits of the round constants.

Rnd

The round function of a KECCAK-p permutation.

SHA3-224

The SHA-3 hash function that produces 224-bit digests.

SHA3-256

The SHA-3 hash function that produces 256-bit digests.

SHA3-384

The SHA-3 hash function that produces 384-bit digests.

SHA3-512

The SHA-3 hash function that produces 512-bit digests.

SHAKE128

The SHA-3 XOF that generally supports 128 bits of security strength, if

6

the output is sufficiently long; see Sec. A.1.
SHAKE256

The SHA-3 XOF that generally supports 256 bits of security strength, if
the output is sufficiently long; see Sec. A.1.

SPONGE[f, pad, r]

The sponge function in which the underlying function is f, the padding
rule is pad, and the rate is r.

3 KECCAK-p PERMUTATIONS
In this section, the KECCAK-p permutations are specified, with two parameters: 1) the fixed
length of the strings that are permuted, called the width of the permutation, and 2) the number of
iterations of an internal transformation, called a round. The width is denoted by b, and the
number of rounds is denoted by nr. The KECCAK-p permutation with nr rounds and width b is
denoted by KECCAK-p[b, nr]; the permutation is defined for any b in {25, 50, 100, 200, 400, 800,
1600} and any positive integer nr.
A round of a KECCAK-p permutation, denoted by Rnd, consists of a sequence of five
transformations, which are called the step mappings. The permutation is specified in terms of an
array of values for b bits that is repeatedly updated, called the state; the state is initially set to the
input values of the permutation.
The notation and terminology for the state are described in Sec. 3.1. The step mappings are
specified in Sec. 3.2. The KECCAK-p permutations, including the round function Rnd, are
specified in Sec. 3.3. The relationship of the KECCAK-p permutations to the KECCAK-f
permutations that were defined for KECCAK in [8] is described in Sec. 3.4.

3.1 State
The state for the KECCAK-p[b, nr] permutation is comprised of b bits. The specifications in this
Standard contain two other quantities related to b: b/25 and log2(b/25), denoted by w and l,
respectively. The seven possible values for these variables that are defined for the KECCAK-p
permutations are given in the columns of Table 1 below.
b
w
l

25
1
0

50
2
1

100
4
2

200
8
3

400
16
4

800
32
5

1600
64
6

Table 1: KECCAK-p permutation widths and related quantities
It is convenient to represent the input and output states of the permutation as b-bit strings, and to
represent the input and output states of the step mappings as 5-by-5-by-w arrays of bits. If S
denotes a string that represents the state, then its bits are indexed from 0 to b–1, so that
S = S[0] || S[1] || … || S[b-2] || S[b-1].

7

If A denotes a 5-by-5-by-w array of bits that represents the state, then its indices are the integer
triples (x, y, z) for which 0 ≤ x < 5, 0 ≤ y < 5, and 0 ≤ z < w. The bit that corresponds to (x, y, z) is
denoted by A[x, y, z]. A state array is a representation of the state by a three-dimensional array
that is indexed in this manner.
3.1.1 Parts of the State Array

Figure 1: Parts of the state array, organized by dimension [8]

8

The state array for a KECCAK-p permutation, and its lower-dimensional sub-arrays, are illustrated
in Figure 1 above for the case b = 200, so that w = 8. The two-dimensional sub-arrays are called
sheets, planes, and slices, and the single-dimensional sub-arrays are called rows, columns, and
lanes. The algebraic definitions of these sub-arrays are given in the Glossary, in Sec. 2.1.
3.1.2 Converting Strings to State Arrays
Let S denote a string of b bits that represents the state for the KECCAK-p[b, nr] permutation. The
corresponding state array, denoted by A, is defined as follows:
For all triples (x, y, z) such that 0 ≤ x < 5, 0 ≤ y < 5, and 0 ≤ z < w,
A[x, y, z] = S [w(5y + x) + z].
For example, if b= 1600, so that w= 64, then
A[0, 0, 0] = S [0]
A[0, 0, 1] = S [1]
A[0, 0, 2] = S [2]
⋮
A[0, 0, 61] = S [61]
A[0, 0, 62] = S [62]
A[0, 0, 63] = S [63]

A[1, 0, 0] = S [64]
A[1, 0, 1] = S [65]
A[1, 0, 2] = S [66]
⋮
A[1, 0, 61] = S [125]
A[1, 0, 62] = S [126]
A[1, 0, 63] = S [127]

A[0, 1, 0] = S [320]
A[0, 1, 1] = S [321]
A[0, 1, 2] = S [322]
⋮
A[0, 1, 61] = S [381]
A[0, 1, 62] = S [382]
A[0, 1, 63] = S [383]

A[1, 1, 0] = S [384]
A[1, 1, 1] = S [385]
A[1, 1, 2] = S [386]
⋮
A[1, 1, 61] = S [445]
A[1, 1, 62] = S [446]
A[1, 1, 63] = S [447]

A[4, 1, 0] = S [576]
A[4, 1, 1] = S [577]
A[4, 1, 2] = S [578]
⋮
A[4, 1, 61] = S [637]
A[4, 1, 62] = S [638]
A[4, 1, 63] = S [639]

A[0, 2, 0] = S [640]
A[0, 2, 1] = S [641]
A[0, 2, 2] = S [642]
⋮
A[0, 2, 61] = S [701]
A[0, 2, 62] = S [702]
A[0, 2, 63] = S [703]

A[1, 2, 0] = S [704]
A[1, 2, 1] = S [705]
A[1, 2, 2] = S [706]
⋮
A[1, 2, 61] = S [765]
A[1, 2, 62] = S [766]
A[1, 2, 63] = S [767]

A[4, 2, 0] = S [896]
A[4, 2, 1] = S [897]
A[4, 2, 2] = S [898]
⋮
A[4, 2, 61] = S [957]
A[4, 2, 62] = S [958]
A[4, 2, 63] = S [959]

…

A[4, 0, 0] = S [256]
A[4, 0, 1] = S [257]
A[4, 0, 2] = S [258]
⋮
A[4, 0, 61] = S [317]
A[4, 0, 62] = S [318]
A[4, 0, 63] = S [319]

and

and

etc.

9

3.1.3 Converting State Arrays to Strings
Let A denote a state array. The corresponding string representation, denoted by S, can be
constructed from the lanes and planes of A, as follows:
For each pair of integers (i, j) such that 0 ≤ i < 5 and 0 ≤ j < 5, define the string Lane (i, j) by
Lane (i, j) = A[i, j, 0] || A[i, j, 1] || A[i, j, 2] || … || A[i, j, w-2] || A[i, j, w-1].
For example, if b = 1600, so that w = 64, then
Lane (0, 0) = A[0, 0, 0] || A[0, 0, 1] || A[0, 0, 2] || … || A[0, 0, 62] || A[0, 0, 63]
Lane (1, 0) = A[1, 0, 0] || A[1, 0, 1] || A[1, 0, 2] || … || A[1, 0, 62] || A[1, 0, 63]
Lane (2, 0) = A[2, 0, 0] || A[2, 0, 1] || A[2, 0, 2] || … || A[2, 0, 62] || A[2, 0, 63]
etc.
For each integer j such that 0 ≤ j < 5, define the string Plane (j) by
Plane (j) = Lane (0, j) || Lane (1, j) || Lane (2, j) || Lane (3, j) || Lane (4, j).
Then
S = Plane (0) || Plane (1) || Plane (2) || Plane (3) || Plane (4).
For example, if b = 1600, so that w = 64, then
S=

A[0, 0, 0] || A[0, 0, 1] || A[0, 0, 2] || … || A[0, 0, 62] || A[0, 0, 63]
|| A[1, 0, 0] || A[1, 0, 1] || A[1, 0, 2] || … || A[1, 0, 62] || A[1, 0, 63]
|| A[2, 0, 0] || A[2, 0, 1] || A[2, 0, 2] || … || A[2, 0, 62] || A[2, 0, 63]
|| A[3, 0, 0] || A[3, 0, 1] || A[3, 0, 2] || … || A[3, 0, 62] || A[3, 0, 63]
|| A[4, 0, 0] || A[4, 0, 1] || A[4, 0, 2] || … || A[4, 0, 62] || A[4, 0, 63]
|| A[0, 1, 0] || A[0, 1, 1] || A[0, 1, 2] || … || A[0, 1, 62] || A[0, 1, 63]
|| A[1, 1, 0] || A[1, 1, 1] || A[1, 1, 2] || … || A[1, 1, 62] || A[1, 1, 63]
|| A[2, 1, 0] || A[2, 1, 1] || A[2, 1, 2] || … || A[2, 1, 62] || A[2, 1, 63]
|| A[3, 1, 0] || A[3, 1, 1] || A[3, 1, 2] || … || A[3, 1, 62] || A[3, 1, 63]
|| A[4, 1, 0] || A[4, 1, 1] || A[4, 1, 2] || … || A[4, 1, 62] || A[4, 1, 63]
⋮
|| A[0, 4, 0] || A[0, 4, 1] || A[0, 4, 2] || … || A[0, 4, 62] || A[0, 4, 63]
|| A[1, 4, 0] || A[1, 4, 1] || A[1, 4, 2] || … || A[1, 4, 62] || A[1, 4, 63]
|| A[2, 4, 0] || A[2, 4, 1] || A[2, 4, 2] || … || A[2, 4, 62] || A[2, 4, 63]
|| A[3, 4, 0] || A[3, 4, 1] || A[3, 4, 2] || … || A[3, 4, 62] || A[3, 4, 63]
|| A[4, 4, 0] || A[4, 4, 1] || A[4, 4, 2] || … || A[4, 4, 62] || A[4, 4, 63] .

10

z

3.1.4 Labeling Convention for the State Array

0
y

1

2

3

…

1
w−

2
1
0
4
3
3 4 0 1 2
x

Figure 2: The x, y, and z coordinates for the diagrams of the step mappings
In the diagrams of the state that accompany the specifications of the step mappings, the lane that
corresponds to the coordinates (x, y) = (0, 0) is depicted at the center of the slices. The complete
labeling of the x, y, and z coordinates for those diagrams is shown in Figure 2 above.

3.2 Step Mappings
The five step mappings that comprise a round of KECCAK-p[b, nr] are denoted by θ, ρ, π, χ, and ι.
Specifications for these functions are given in Secs. 3.2.1-3.2.5.
The algorithm for each step mapping takes a state array, denoted by A, as an input and returns an
updated state array, denoted by A′, as the output. The size of the state is a parameter that is
omitted from the notation, because b is always specified when the step mappings are invoked.
The ι mapping ir has a second input: an integer called the round index, denoted by ir, which is
defined within Algorithm 7 for KECCAK-p[b, nr], in Sec. 3.3. The other step mappings do not
depend on the round index.
3.2.1 Specification of θ
Algorithm 1: θ(A)
Input:
state array A.
Output:
state array A′.
11

Steps:
1. For all pairs (x, z) such that 0 ≤ x < 5 and 0 ≤ z < w, let
C[x, z] = A[x, 0, z] ⊕ A[x, 1, z] ⊕ A[x, 2, z] ⊕ A[x, 3, z] ⊕ A[x, 4, z].
2. For all pairs (x, z) such that 0 ≤ x < 5 and 0 ≤ z < w let
D[x, z] = C[(x1) mod 5, z] ⊕ C[(x+1) mod 5, (z – 1) mod w].
3. For all triples (x, y, z) such that 0 ≤ x < 5, 0 ≤ y < 5, and 0 ≤ z < w, let
A′[x, y, z] = A[x, y, z] ⊕ D[x, z].
The effect of θ is to XOR each bit in the state with the parities of two columns in the array. In
particular, for the bit A[x0, y0, z0], the x-coordinate of one of the columns is (x0  1) mod 5, with
the same z-coordinate, z0, while the x-coordinate of the other column is (x0 + 1) mod 5, with zcoordinate (z0  1) mod w.
In the illustration of the θ step mapping in Figure 3 below, the summation symbol, ∑, indicates
the parity, i.e., the XOR sum of all the bits in the column.

Figure 3: Illustration of θ applied to a single bit [8]
3.2.2 Specification of ρ
Algorithm 2: ρ(A)
Input:
state array A.
Output:
state array A′.
Steps:
1. For all z such that 0 ≤ z < w, let A′ [0, 0, z] = A[0, 0, z].
2. Let (x, y) = (1, 0).

12

3. For t from 0 to 23:
