Constructing Second Preimages in the WaMM Hash Algorithm

David A. Wilson
dwilson at alum dot mit dot edu
1 November 2008

The WaMM Hash Function is a candidate for the NIST SHA-3 specification developed by John Washburn. Please see the WaMM website for a detailed algorithm specification.

WaMM effectively acts on message blocks of size 8192 bits (1 kB), and internally keeps 8192 bits of state expressed as a 32x32 matrix of bytes. (Some other pieces of state information are kept, but they are not relevant to this discussion.) During each update step, the next 8192 message bits are XORed into the internal state; the WaMM transform is then applied to the internal state, and the process is repeated until the end of the message. There is then a finalizing step in which the message length is XORed and the transform applied again.

This structure allows a specially crafted message block of 8192 bits to arbitrarily replace the entire internal state. This allows arbitrary second preimages to be constructed for any multi-block message.

An example of two colliding messages are as follows. Each message is 16384 bits long. A 512-bit message digest was used, but the analysis holds for any digest length. (The below values were selected to have (m1 XOR S) = (m'1 XOR S') = the zero vector.)
Message:  
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
3D A8 82 8A D4 DD CF 45 9F 8F 91 54 95 1B C3 54 A7 83 7F 22 92 87 47 D3 FC DF 61 A0 19 A1 83 FC 
A1 0C E6 EE 38 41 33 A9 03 F3 F5 B8 F9 7F 27 B8 0B E7 E3 86 F6 EB AB 37 60 43 C5 04 7D 05 E7 60 
5D C8 A2 AA F4 FD EF 65 BF AF B1 74 B5 3B E3 74 C7 A3 9F 42 B2 A7 67 F3 1C FF 81 C0 39 C1 A3 1C 
71 DC B6 BE 08 11 03 79 D3 C3 C5 88 C9 4F F7 88 DB B7 B3 56 C6 BB 7B 07 30 13 95 D4 4D D5 B7 30 
9E 09 E3 EB 35 3E 30 A6 00 F0 F2 B5 F6 7C 24 B5 08 E4 E0 83 F3 E8 A8 34 5D 40 C2 01 7A 02 E4 5D 
24 8F 69 71 BB C4 B6 2C 86 76 78 3B 7C 02 AA 3B 8E 6A 66 09 79 6E 2E BA E3 C6 48 87 00 88 6A E3 
72 DD B7 BF 09 12 04 7A D4 C4 C6 89 CA 50 F8 89 DC B8 B4 57 C7 BC 7C 08 31 14 96 D5 4E D6 B8 31 
A9 14 EE F6 40 49 3B B1 0B FB FD C0 01 87 2F C0 13 EF EB 8E FE F3 B3 3F 68 4B CD 0C 85 0D EF 68 
8D F8 D2 DA 24 2D 1F 95 EF DF E1 A4 E5 6B 13 A4 F7 D3 CF 72 E2 D7 97 23 4C 2F B1 F0 69 F1 D3 4C 
CE 39 13 1B 65 6E 60 D6 30 20 22 E5 26 AC 54 E5 38 14 10 B3 23 18 D8 64 8D 70 F2 31 AA 32 14 8D 
51 BC 96 9E E8 F1 E3 59 B3 A3 A5 68 A9 2F D7 68 BB 97 93 36 A6 9B 5B E7 10 F3 75 B4 2D B5 97 10 
39 A4 7E 86 D0 D9 CB 41 9B 8B 8D 50 91 17 BF 50 A3 7F 7B 1E 8E 83 43 CF F8 DB 5D 9C 15 9D 7F F8 
09 74 4E 56 A0 A9 9B 11 6B 5B 5D 20 61 E7 8F 20 73 4F 4B EE 5E 53 13 9F C8 AB 2D 6C E5 6D 4F C8 
59 C4 9E A6 F0 F9 EB 61 BB AB AD 70 B1 37 DF 70 C3 9F 9B 3E AE A3 63 EF 18 FB 7D BC 35 BD 9F 18 
25 90 6A 72 BC C5 B7 2D 87 77 79 3C 7D 03 AB 3C 8F 6B 67 0A 7A 6F 2F BB E4 C7 49 88 01 89 6B E4 
8E F9 D3 DB 25 2E 20 96 F0 E0 E2 A5 E6 6C 14 A5 F8 D4 D0 73 E3 D8 98 24 4D 30 B2 F1 6A F2 D4 4D 
3B A6 80 88 D2 DB CD 43 9D 8D 8F 52 93 19 C1 52 A5 81 7D 20 90 85 45 D1 FA DD 5F 9E 17 9F 81 FA 
06 71 4B 53 9D A6 98 0E 68 58 5A 1D 5E E4 8C 1D 70 4C 48 EB 5B 50 10 9C C5 A8 2A 69 E2 6A 4C C5 
33 9E 78 80 CA D3 C5 3B 95 85 87 4A 8B 11 B9 4A 9D 79 75 18 88 7D 3D C9 F2 D5 57 96 0F 97 79 F2 
C6 31 0B 13 5D 66 58 CE 28 18 1A DD 1E A4 4C DD 30 0C 08 AB 1B 10 D0 5C 85 68 EA 29 A2 2A 0C 85 
A1 0C E6 EE 38 41 33 A9 03 F3 F5 B8 F9 7F 27 B8 0B E7 E3 86 F6 EB AB 37 60 43 C5 04 7D 05 E7 60 
2F 9A 74 7C C6 CF C1 37 91 81 83 46 87 0D B5 46 99 75 71 14 84 79 39 C5 EE D1 53 92 0B 93 75 EE 
76 E1 BB C3 0D 16 08 7E D8 C8 CA 8D CE 54 FC 8D E0 BC B8 5B CB C0 80 0C 35 18 9A D9 52 DA BC 35 
BB 26 00 08 52 5B 4D C3 1D 0D 0F D2 13 99 41 D2 25 01 FD A0 10 05 C5 51 7A 5D DF 1E 97 1F 01 7A 
D1 3C 16 1E 68 71 63 D9 33 23 25 E8 29 AF 57 E8 3B 17 13 B6 26 1B DB 67 90 73 F5 34 AD 35 17 90 
AB 16 F0 F8 42 4B 3D B3 0D FD FF C2 03 89 31 C2 15 F1 ED 90 00 F5 B5 41 6A 4D CF 0E 87 0F F1 6A 
25 90 6A 72 BC C5 B7 2D 87 77 79 3C 7D 03 AB 3C 8F 6B 67 0A 7A 6F 2F BB E4 C7 49 88 01 89 6B E4 
7E E9 C3 CB 15 1E 10 86 E0 D0 D2 95 D6 5C 04 95 E8 C4 C0 63 D3 C8 88 14 3D 20 A2 E1 5A E2 C4 3D 
A2 0D E7 EF 39 42 34 AA 04 F4 F6 B9 FA 80 28 B9 0C E8 E4 87 F7 EC AC 38 61 44 C6 05 7E 06 E8 61 
28 93 6D 75 BF C8 BA 30 8A 7A 7C 3F 80 06 AE 3F 92 6E 6A 0D 7D 72 32 BE E7 CA 4C 8B 04 8C 6E E7 
19 84 5E 66 B0 B9 AB 21 7B 6B 6D 30 71 F7 9F 30 83 5F 5B FE 6E 63 23 AF D8 BB 3D 7C F5 7D 5F D8 
C6 31 0B 13 5D 66 58 CE 28 18 1A DD 1E A4 4C DD 30 0C 08 AB 1B 10 D0 5C 85 68 EA 29 A2 2A 0C 85 
Digest value:
CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC 1C CC CC CC 5B CC CC CC CC 
CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC 1C CC CC CC CC CC CC CC CC CC CC CC 5B CC CC CC CC 

Message:  
80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
C3 75 74 C9 32 E5 0D 7B 83 FA 78 FC 1F 16 89 FC 6B B1 F6 F2 6C 7F E1 E7 BC 3C 08 C3 FA A4 65 BC 
AD 5F 5E B3 1C CF F7 65 6D E4 62 E6 09 00 73 E6 55 9B E0 DC 56 69 CB D1 A6 26 F2 AD E4 8E 4F A6 
9C 4E 4D A2 0B BE E6 54 5C D3 51 D5 F8 EF 62 D5 44 8A CF CB 45 58 BA C0 95 15 E1 9C D3 7D 3E 95 
16 C8 C7 1C 85 38 60 CE D6 4D CB 4F 72 69 DC 4F BE 04 49 45 BF D2 34 3A 0F 8F 5B 16 4D F7 B8 0F 
43 F5 F4 49 B2 65 8D FB 03 7A F8 7C 9F 96 09 7C EB 31 76 72 EC FF 61 67 3C BC 88 43 7A 24 E5 3C 
3C EE ED 42 AB 5E 86 F4 FC 73 F1 75 98 8F 02 75 E4 2A 6F 6B E5 F8 5A 60 35 B5 81 3C 73 1D DE 35 
F1 A3 A2 F7 60 13 3B A9 B1 28 A6 2A 4D 44 B7 2A 99 DF 24 20 9A AD 0F 15 EA 6A 36 F1 28 D2 93 EA 
CB 7D 7C D1 3A ED 15 83 8B 02 80 04 27 1E 91 04 73 B9 FE FA 74 87 E9 EF C4 44 10 CB 02 AC 6D C4 
15 C7 C6 1B 84 37 5F CD D5 4C CA 4E 71 68 DB 4E BD 03 48 44 BE D1 33 39 0E 8E 5A 15 4C F6 B7 0E 
5B 0D 0C 61 CA 7D A5 13 1B 92 10 94 B7 AE 21 94 03 49 8E 8A 04 17 79 7F 54 D4 A0 5B 92 3C FD 54 
1F D1 D0 25 8E 41 69 D7 DF 56 D4 58 7B 72 E5 58 C7 0D 52 4E C8 DB 3D 43 18 98 64 1F 56 00 C1 18 
8A 3C 3B 90 F9 AC D4 42 4A C1 3F C3 E6 DD 50 C3 32 78 BD B9 33 46 A8 AE 83 03 CF 8A C1 6B 2C 83 
F7 A9 A8 FD 66 19 41 AF B7 2E AC 30 53 4A BD 30 9F E5 2A 26 A0 B3 15 1B F0 70 3C F7 2E D8 99 F0 
22 D4 D3 28 91 44 6C DA E2 59 D7 5B 7E 75 E8 5B CA 10 55 51 CB DE 40 46 1B 9B 67 22 59 03 C4 1B 
D8 8A 89 DE 47 FA 22 90 98 0F 8D 11 34 2B 9E 11 80 C6 0B 07 81 94 F6 FC D1 51 1D D8 0F B9 7A D1 
E6 98 97 EC 55 08 30 9E A6 1D 9B 1F 42 39 AC 1F 8E D4 19 15 8F A2 04 0A DF 5F 2B E6 1D C7 88 DF 
74 26 25 7A E3 96 BE 2C 34 AB 29 AD D0 C7 3A AD 1C 62 A7 A3 1D 30 92 98 6D ED B9 74 AB 55 16 6D 
17 C9 C8 1D 86 39 61 CF D7 4E CC 50 73 6A DD 50 BF 05 4A 46 C0 D3 35 3B 10 90 5C 17 4E F8 B9 10 
FA AC AB 00 69 1C 44 B2 BA 31 AF 33 56 4D C0 33 A2 E8 2D 29 A3 B6 18 1E F3 73 3F FA 31 DB 9C F3 
06 B8 B7 0C 75 28 50 BE C6 3D BB 3F 62 59 CC 3F AE F4 39 35 AF C2 24 2A FF 7F 4B 06 3D E7 A8 FF 
AD 5F 5E B3 1C CF F7 65 6D E4 62 E6 09 00 73 E6 55 9B E0 DC 56 69 CB D1 A6 26 F2 AD E4 8E 4F A6 
07 B9 B8 0D 76 29 51 BF C7 3E BC 40 63 5A CD 40 AF F5 3A 36 B0 C3 25 2B 00 80 4C 07 3E E8 A9 00 
1C CE CD 22 8B 3E 66 D4 DC 53 D1 55 78 6F E2 55 C4 0A 4F 4B C5 D8 3A 40 15 95 61 1C 53 FD BE 15 
EA 9C 9B F0 59 0C 34 A2 AA 21 9F 23 46 3D B0 23 92 D8 1D 19 93 A6 08 0E E3 63 2F EA 21 CB 8C E3 
A9 5B 5A AF 18 CB F3 61 69 E0 5E E2 05 FC 6F E2 51 97 DC D8 52 65 C7 CD A2 22 EE A9 E0 8A 4B A2 
8F 41 40 95 FE B1 D9 47 4F C6 44 C8 EB E2 55 C8 37 7D C2 BE 38 4B AD B3 88 08 D4 8F C6 70 31 88 
7B 2D 2C 81 EA 9D C5 33 3B B2 30 B4 D7 CE 41 B4 23 69 AE AA 24 37 99 9F 74 F4 C0 7B B2 5C 1D 74 
FA AC AB 00 69 1C 44 B2 BA 31 AF 33 56 4D C0 33 A2 E8 2D 29 A3 B6 18 1E F3 73 3F FA 31 DB 9C F3 
EB 9D 9C F1 5A 0D 35 A3 AB 22 A0 24 47 3E B1 24 93 D9 1E 1A 94 A7 09 0F E4 64 30 EB 22 CC 8D E4 
79 2B 2A 7F E8 9B C3 31 39 B0 2E B2 D5 CC 3F B2 21 67 AC A8 22 35 97 9D 72 F2 BE 79 B0 5A 1B 72 
82 34 33 88 F1 A4 CC 3A 42 B9 37 BB DE D5 48 BB 2A 70 B5 B1 2B 3E A0 A6 7B FB C7 82 B9 63 24 7B 
12 C4 C3 18 81 34 5C CA D2 49 C7 4B 6E 65 D8 4B BA 00 45 41 BB CE 30 36 0B 8B 57 12 49 F3 B4 0B 
Digest value:
CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC 1C CC CC CC 5B CC CC CC CC 
CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC 1C CC CC CC CC CC CC CC CC CC CC CC 5B CC CC CC CC 

Recommendation

The WaMM hash function allows the cryptanalyst too much control over its internal state. One obvious recovery method would be to reduce the number of bits processed at each stage (that is, to perform the WaMM transform more frequently). If, for example, the algorithm only copied 4096 bytes to the internal state before performing the transform--leaving half the state untouched--a specially chosen message block could not rewrite the entire state. However, this naturally results in a performance decrease, and it is not necessarily a cureall--similar vulnerabilities may still exist by allowing control of a portion of the state. A separate analysis would be needed for any specific modified version of the algorithm.