Tuesday, May 08, 2018

[mmpffczs] Generating Keccak round constants

We investigate the round constants for the Keccak hash function (of which SHA-3 is a subset).  We work mostly from the officially published SHA-3 standard which was a little bit easier to understand than the reference specification.

These round constants are used in Keccak's iota step-mapping function.  The internal function rc(t) is a linear-feedback shift register (LFSR) with 8 bits of state and a period of 255.  Its period is 255 if its state is seeded with a nonzero value, which it is, namely the value 1.  Here is its full period, grouped in chunks of 7 for reasons which will be made clear shortly.  We write the 0 bit as period "." and the 1 bit as "1" to be able to easily distinguish them: 1...... .1.11.. .1111.1 ....111 11111.. 1....1. 1..1111 1.1.1.1 .111... ..11... 1.1.11. .11..1. 111111. 1111..1 1.111.1 11..1.1 .1..1.1 ...1..1 .11.1.. .11..11 1..1111 ...11.1 1....1. ..1.111 .1.1111 .11.111 11....1 1.1..11 .1.11.1 1.1.1.. ...1..1 11.11.. 1..1..1 1...... 111.1.. 1...111 ...

The Keccak round constants are easiest to understand in binary.  We write binary constants below with the least significant bit on the left (little-endian), opposite the standard convention of writing numbers.

Round
01...............................................................
1.1.....1.......1................................................
2.1.1...1.......1...............................................1
3...............1...............1...............................1
411.1...1.......1................................................
51..............................1................................
61......1.......1...............1...............................1
71..1...........1...............................................1
8.1.1...1........................................................
9...1...1........................................................
101..1...........1...............1................................
11.1.1...........................1................................
1211.1...1.......1...............1................................
1311.1...1.......................................................1
141..1...1.......1...............................................1
1511.............1...............................................1
16.1.............1...............................................1
17.......1.......................................................1
18.1.1...........1................................................
19.1.1...........................1...............................1
201......1.......1...............1...............................1
21.......1.......1...............................................1
221..............................1................................
23...1...........1...............1...............................1

Of the 64 bit positions for each 64-bit constant, only 7 can ever be set, seen in the rough columns of 1s at bit positions 2^j-1 above.  Whether a position is set or not is taken from the output of the LFSR defined above (which is why we grouped the output in chunks of 7).  It is curious that Keccak uses such sparse binary round constants; the best explanation I can imagine is that it reduces the gate count in unrolled hardware implementations.  It's nice that Keccak is secure despite such weak round constants which barely modify values each round and differ so little between rounds.

The last round (of 64-bit Keccak, i.e., w=64) always uses the round constant with index 23 above.  If you wish to do Keccak with fewer than 24 rounds, then start somewhere in the middle, ending at round 23.  If you wish to do Keccak with more than 24 rounds, then start at a negative round index.  This is kind of bizarre, but I think the reason is something along the lines of being able to reuse cryptanalytic results from reduced-round variants.  Incidentally, negative round indices means that the rc(t) function must be able to handle negative t, so your (mod 255) operation must give a proper positive result for negative input.  Because 255 (the period of the LFSR) and 7 (the number of bits consumed per round constant) are relatively prime, the round constants cycle with a period of 255.  The period could have been less if the number of LFSR bits consumed per round constant shared factors with 255=3*5*17.  Here is the full list of round constants (in big-endian hexadecimal) for as many rounds of Keccak you care to do:

RC[-231] = 0x8000000080008082
RC[-230] = 0x800000008000800a
RC[-229] = 0x8000000000000003
RC[-228] = 0x8000000080000009
RC[-227] = 0x8000000000008082
RC[-226] = 0x0000000000008009
RC[-225] = 0x8000000000000080
RC[-224] = 0x0000000000008083
RC[-223] = 0x8000000000000081
RC[-222] = 0x0000000000000001
RC[-221] = 0x000000000000800b
RC[-220] = 0x8000000080008001
RC[-219] = 0x0000000000000080
RC[-218] = 0x8000000000008000
RC[-217] = 0x8000000080008001
RC[-216] = 0x0000000000000009
RC[-215] = 0x800000008000808b
RC[-214] = 0x0000000000000081
RC[-213] = 0x8000000000000082
RC[-212] = 0x000000008000008b
RC[-211] = 0x8000000080008009
RC[-210] = 0x8000000080000000
RC[-209] = 0x0000000080000080
RC[-208] = 0x0000000080008003
RC[-207] = 0x8000000080008082
RC[-206] = 0x8000000080008083
RC[-205] = 0x8000000080000088
RC[-204] = 0x0000000000008089
RC[-203] = 0x0000000000008009
RC[-202] = 0x8000000000000009
RC[-201] = 0x0000000080008008
RC[-200] = 0x0000000080008001
RC[-199] = 0x800000000000008a
RC[-198] = 0x800000000000000b
RC[-197] = 0x0000000000000089
RC[-196] = 0x0000000080000002
RC[-195] = 0x800000000000800b
RC[-194] = 0x000000008000800b
RC[-193] = 0x000000000000808b
RC[-192] = 0x0000000080000088
RC[-191] = 0x800000000000800a
RC[-190] = 0x0000000080000089
RC[-189] = 0x8000000000000001
RC[-188] = 0x8000000000008088
RC[-187] = 0x8000000000000081
RC[-186] = 0x0000000000000088
RC[-185] = 0x0000000080008080
RC[-184] = 0x0000000000000081
RC[-183] = 0x800000000000000b
RC[-182] = 0x0000000000000000
RC[-181] = 0x0000000000000089
RC[-180] = 0x000000008000008b
RC[-179] = 0x8000000080008080
RC[-178] = 0x800000000000008b
RC[-177] = 0x8000000000008000
RC[-176] = 0x8000000080008088
RC[-175] = 0x0000000080000082
RC[-174] = 0x000000000000000b
RC[-173] = 0x800000000000000a
RC[-172] = 0x0000000000008082
RC[-171] = 0x8000000000008003
RC[-170] = 0x800000000000808b
RC[-169] = 0x800000008000000b
RC[-168] = 0x800000008000008a
RC[-167] = 0x0000000080000081
RC[-166] = 0x0000000080000081
RC[-165] = 0x0000000080000008
RC[-164] = 0x0000000000000083
RC[-163] = 0x8000000080008003
RC[-162] = 0x0000000080008088
RC[-161] = 0x8000000080000088
RC[-160] = 0x0000000000008000
RC[-159] = 0x0000000080008082
RC[-158] = 0x0000000080008089
RC[-157] = 0x8000000080008083
RC[-156] = 0x8000000080000001
RC[-155] = 0x0000000080008002
RC[-154] = 0x8000000080000089
RC[-153] = 0x0000000000000082
RC[-152] = 0x8000000080000008
RC[-151] = 0x8000000000000089
RC[-150] = 0x8000000080000008
RC[-149] = 0x8000000000000000
RC[-148] = 0x8000000000000083
RC[-147] = 0x0000000080008080
RC[-146] = 0x0000000000000008
RC[-145] = 0x8000000080000080
RC[-144] = 0x8000000080008080
RC[-143] = 0x8000000000000002
RC[-142] = 0x800000008000808b
RC[-141] = 0x0000000000000008
RC[-140] = 0x8000000080000009
RC[-139] = 0x800000000000800b
RC[-138] = 0x0000000080008082
RC[-137] = 0x0000000080008000
RC[-136] = 0x8000000000008008
RC[-135] = 0x0000000000008081
RC[-134] = 0x8000000080008089
RC[-133] = 0x0000000080008089
RC[-132] = 0x800000008000800a
RC[-131] = 0x800000000000008a
RC[-130] = 0x8000000000000082
RC[-129] = 0x0000000080000002
RC[-128] = 0x8000000000008082
RC[-127] = 0x0000000000008080
RC[-126] = 0x800000008000000b
RC[-125] = 0x8000000080000003
RC[-124] = 0x000000000000000a
RC[-123] = 0x8000000000008001
RC[-122] = 0x8000000080000083
RC[-121] = 0x8000000000008083
RC[-120] = 0x000000000000008b
RC[-119] = 0x000000000000800a
RC[-118] = 0x8000000080000083
RC[-117] = 0x800000000000800a
RC[-116] = 0x0000000080000000
RC[-115] = 0x800000008000008a
RC[-114] = 0x0000000080000008
RC[-113] = 0x000000000000000a
RC[-112] = 0x8000000000008088
RC[-111] = 0x8000000000000008
RC[-110] = 0x0000000080000003
RC[-109] = 0x8000000000000000
RC[-108] = 0x800000000000000a
RC[-107] = 0x000000000000800b
RC[-106] = 0x8000000080008088
RC[-105] = 0x000000008000000b
RC[-104] = 0x0000000080000080
RC[-103] = 0x000000008000808a
RC[-102] = 0x8000000000008009
RC[-101] = 0x0000000000000003
RC[-100] = 0x0000000080000003
RC[-99] = 0x8000000000000089
RC[-98] = 0x8000000080000081
RC[-97] = 0x800000008000008b
RC[-96] = 0x0000000080008003
RC[-95] = 0x800000008000800b
RC[-94] = 0x8000000000008008
RC[-93] = 0x0000000000008008
RC[-92] = 0x8000000000008002
RC[-91] = 0x8000000000000009
RC[-90] = 0x0000000080008081
RC[-89] = 0x000000000000808a
RC[-88] = 0x000000008000800a
RC[-87] = 0x0000000000000080
RC[-86] = 0x8000000000008089
RC[-85] = 0x800000000000808a
RC[-84] = 0x8000000080008089
RC[-83] = 0x0000000080008000
RC[-82] = 0x8000000000008081
RC[-81] = 0x000000008000800a
RC[-80] = 0x0000000000000009
RC[-79] = 0x8000000080008002
RC[-78] = 0x000000008000000a
RC[-77] = 0x0000000080008002
RC[-76] = 0x8000000080000000
RC[-75] = 0x0000000080000009
RC[-74] = 0x0000000000008088
RC[-73] = 0x0000000000000002
RC[-72] = 0x0000000080008008
RC[-71] = 0x0000000080008088
RC[-70] = 0x8000000080000001
RC[-69] = 0x000000008000808b
RC[-68] = 0x8000000000000002
RC[-67] = 0x8000000080008002
RC[-66] = 0x0000000080000083
RC[-65] = 0x0000000000008089
RC[-64] = 0x0000000000008080
RC[-63] = 0x8000000080000082
RC[-62] = 0x8000000000000088
RC[-61] = 0x800000008000808a
RC[-60] = 0x000000000000808a
RC[-59] = 0x0000000080008083
RC[-58] = 0x000000008000000b
RC[-57] = 0x0000000080000009
RC[-56] = 0x0000000000008001
RC[-55] = 0x0000000080000089
RC[-54] = 0x8000000000000088
RC[-53] = 0x8000000080008003
RC[-52] = 0x0000000080008001
RC[-51] = 0x8000000000000003
RC[-50] = 0x8000000080000080
RC[-49] = 0x8000000080008009
RC[-48] = 0x8000000080000089
RC[-47] = 0x000000000000000b
RC[-46] = 0x8000000000000083
RC[-45] = 0x0000000080008009
RC[-44] = 0x0000000080000083
RC[-43] = 0x0000000000008000
RC[-42] = 0x000000008000800b
RC[-41] = 0x0000000000008002
RC[-40] = 0x0000000000000003
RC[-39] = 0x000000008000008a
RC[-38] = 0x8000000080000002
RC[-37] = 0x0000000000008001
RC[-36] = 0x0000000080000000
RC[-35] = 0x8000000080000003
RC[-34] = 0x0000000000000083
RC[-33] = 0x800000008000808a
RC[-32] = 0x0000000000008003
RC[-31] = 0x0000000000008008
RC[-30] = 0x800000000000808b
RC[-29] = 0x8000000080000082
RC[-28] = 0x8000000000000001
RC[-27] = 0x8000000000008001
RC[-26] = 0x800000008000000a
RC[-25] = 0x8000000080008008
RC[-24] = 0x800000008000800b
RC[-23] = 0x8000000000008081
RC[-22] = 0x0000000080008083
RC[-21] = 0x0000000080000082
RC[-20] = 0x0000000000000082
RC[-19] = 0x8000000080000081
RC[-18] = 0x8000000080000002
RC[-17] = 0x0000000000008088
RC[-16] = 0x000000000000008b
RC[-15] = 0x0000000000008083
RC[-14] = 0x8000000000000008
RC[-13] = 0x000000008000008a
RC[-12] = 0x800000008000008b
RC[-11] = 0x000000008000808a
RC[-10] = 0x8000000000008080
RC[-9] = 0x0000000080000088
RC[-8] = 0x8000000000008083
RC[-7] = 0x0000000000000002
RC[-6] = 0x0000000080008081
RC[-5] = 0x0000000000008003
RC[-4] = 0x0000000000008081
RC[-3] = 0x8000000080008000
RC[-2] = 0x0000000000008002
RC[-1] = 0x000000000000008a
RC[0] = 0x0000000000000001
RC[1] = 0x0000000000008082
RC[2] = 0x800000000000808a
RC[3] = 0x8000000080008000
RC[4] = 0x000000000000808b
RC[5] = 0x0000000080000001
RC[6] = 0x8000000080008081
RC[7] = 0x8000000000008009
RC[8] = 0x000000000000008a
RC[9] = 0x0000000000000088
RC[10] = 0x0000000080008009
RC[11] = 0x000000008000000a
RC[12] = 0x000000008000808b
RC[13] = 0x800000000000008b
RC[14] = 0x8000000000008089
RC[15] = 0x8000000000008003
RC[16] = 0x8000000000008002
RC[17] = 0x8000000000000080
RC[18] = 0x000000000000800a
RC[19] = 0x800000008000000a
RC[20] = 0x8000000080008081
RC[21] = 0x8000000000008080
RC[22] = 0x0000000080000001
RC[23] = 0x8000000080008008

The final 24 constants agree with those published at Team Keccak.  If you need more than 255 rounds, RC[-232] loops back to RC[23] and so forth.

Observations: In 24-round normal Keccak, rounds 5 and 22 use the same round constant, as do rounds 6 and 20.  Keccak with 25 rounds or more additionally sees the same round constant on rounds -1 and 8.  27 rounds or more sees duplication at rounds -3 and 3.  At 255 rounds (full period), there are 128 unique round constants, with every constant repeated twice except the zero constant which only occurs at round -182.

32-bit Keccak (w=32) uses the lower 32 bits of the round constants above.  7 bits of the LFSR are still consumed for each constant; 1/7 of the bits are thrown away.  There are by default 22 rounds total with last round having round index 21.  Duplicated pairs are rounds (6,20) and (11,19).  Doing more rounds causes more repeated round constants: doing 6 additional rounds (22 + 6 = 28 total) sees triplication of constants in rounds -6, 6, and 20.  16-bit Keccak has 20 rounds, duplication at (0,5), (4,12), (7,10), and (11,19) and first triplication with 6 extra rounds (-6,-4,6).  8-bit Keccak (18 rounds) sees repeated constants in rounds (0,5), (2,8), (4,12,13), and (7,10).

If we wish to extend Keccak to 128-bit lane width (w) or more, we would want to consume more than 7 LFSR bits per round, maybe also use a longer-period LFSR.  This should be safe, as these round constants are Nothing-Up-My-Sleeve numbers, so other numbers should also be safe to use.  A deeper Keccak will probably want other modifications also, for example the rho step-mapping function.  Its 25 triangular numbers, representing rotation amounts, grow only up to 300, but we would like larger rotations for better diffusion if the lane width is significantly longer than 300.

Here is an implementation in Haskell of the generation of these Keccak round constants.  We represented bit strings as lists of Bool.

No comments :