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 | |
|---|---|
| 0 | 1............................................................... |
| 1 | .1.....1.......1................................................ |
| 2 | .1.1...1.......1...............................................1 |
| 3 | ...............1...............1...............................1 |
| 4 | 11.1...1.......1................................................ |
| 5 | 1..............................1................................ |
| 6 | 1......1.......1...............1...............................1 |
| 7 | 1..1...........1...............................................1 |
| 8 | .1.1...1........................................................ |
| 9 | ...1...1........................................................ |
| 10 | 1..1...........1...............1................................ |
| 11 | .1.1...........................1................................ |
| 12 | 11.1...1.......1...............1................................ |
| 13 | 11.1...1.......................................................1 |
| 14 | 1..1...1.......1...............................................1 |
| 15 | 11.............1...............................................1 |
| 16 | .1.............1...............................................1 |
| 17 | .......1.......................................................1 |
| 18 | .1.1...........1................................................ |
| 19 | .1.1...........................1...............................1 |
| 20 | 1......1.......1...............1...............................1 |
| 21 | .......1.......1...............................................1 |
| 22 | 1..............................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 :
Post a Comment