sha3.cpp raw
1 // Copyright (c) 2020-present The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5 // Based on https://github.com/mjosaarinen/tiny_sha3/blob/master/sha3.c
6 // by Markku-Juhani O. Saarinen <mjos@iki.fi>
7
8 #include <crypto/sha3.h>
9 #include <crypto/common.h>
10
11 #include <algorithm>
12 #include <bit>
13 #include <cassert>
14 #include <iterator>
15 #include <span>
16
17 void KeccakF(uint64_t (&st)[25])
18 {
19 static constexpr uint64_t RNDC[24] = {
20 0x0000000000000001, 0x0000000000008082, 0x800000000000808a, 0x8000000080008000,
21 0x000000000000808b, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009,
22 0x000000000000008a, 0x0000000000000088, 0x0000000080008009, 0x000000008000000a,
23 0x000000008000808b, 0x800000000000008b, 0x8000000000008089, 0x8000000000008003,
24 0x8000000000008002, 0x8000000000000080, 0x000000000000800a, 0x800000008000000a,
25 0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008
26 };
27 static constexpr int ROUNDS = 24;
28
29 for (int round = 0; round < ROUNDS; ++round) {
30 uint64_t bc0, bc1, bc2, bc3, bc4, t;
31
32 // Theta
33 bc0 = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20];
34 bc1 = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21];
35 bc2 = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22];
36 bc3 = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23];
37 bc4 = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24];
38 t = bc4 ^ std::rotl(bc1, 1); st[0] ^= t; st[5] ^= t; st[10] ^= t; st[15] ^= t; st[20] ^= t;
39 t = bc0 ^ std::rotl(bc2, 1); st[1] ^= t; st[6] ^= t; st[11] ^= t; st[16] ^= t; st[21] ^= t;
40 t = bc1 ^ std::rotl(bc3, 1); st[2] ^= t; st[7] ^= t; st[12] ^= t; st[17] ^= t; st[22] ^= t;
41 t = bc2 ^ std::rotl(bc4, 1); st[3] ^= t; st[8] ^= t; st[13] ^= t; st[18] ^= t; st[23] ^= t;
42 t = bc3 ^ std::rotl(bc0, 1); st[4] ^= t; st[9] ^= t; st[14] ^= t; st[19] ^= t; st[24] ^= t;
43
44 // Rho Pi
45 t = st[1];
46 bc0 = st[10]; st[10] = std::rotl(t, 1); t = bc0;
47 bc0 = st[7]; st[7] = std::rotl(t, 3); t = bc0;
48 bc0 = st[11]; st[11] = std::rotl(t, 6); t = bc0;
49 bc0 = st[17]; st[17] = std::rotl(t, 10); t = bc0;
50 bc0 = st[18]; st[18] = std::rotl(t, 15); t = bc0;
51 bc0 = st[3]; st[3] = std::rotl(t, 21); t = bc0;
52 bc0 = st[5]; st[5] = std::rotl(t, 28); t = bc0;
53 bc0 = st[16]; st[16] = std::rotl(t, 36); t = bc0;
54 bc0 = st[8]; st[8] = std::rotl(t, 45); t = bc0;
55 bc0 = st[21]; st[21] = std::rotl(t, 55); t = bc0;
56 bc0 = st[24]; st[24] = std::rotl(t, 2); t = bc0;
57 bc0 = st[4]; st[4] = std::rotl(t, 14); t = bc0;
58 bc0 = st[15]; st[15] = std::rotl(t, 27); t = bc0;
59 bc0 = st[23]; st[23] = std::rotl(t, 41); t = bc0;
60 bc0 = st[19]; st[19] = std::rotl(t, 56); t = bc0;
61 bc0 = st[13]; st[13] = std::rotl(t, 8); t = bc0;
62 bc0 = st[12]; st[12] = std::rotl(t, 25); t = bc0;
63 bc0 = st[2]; st[2] = std::rotl(t, 43); t = bc0;
64 bc0 = st[20]; st[20] = std::rotl(t, 62); t = bc0;
65 bc0 = st[14]; st[14] = std::rotl(t, 18); t = bc0;
66 bc0 = st[22]; st[22] = std::rotl(t, 39); t = bc0;
67 bc0 = st[9]; st[9] = std::rotl(t, 61); t = bc0;
68 bc0 = st[6]; st[6] = std::rotl(t, 20); t = bc0;
69 st[1] = std::rotl(t, 44);
70
71 // Chi Iota
72 bc0 = st[0]; bc1 = st[1]; bc2 = st[2]; bc3 = st[3]; bc4 = st[4];
73 st[0] = bc0 ^ (~bc1 & bc2) ^ RNDC[round];
74 st[1] = bc1 ^ (~bc2 & bc3);
75 st[2] = bc2 ^ (~bc3 & bc4);
76 st[3] = bc3 ^ (~bc4 & bc0);
77 st[4] = bc4 ^ (~bc0 & bc1);
78 bc0 = st[5]; bc1 = st[6]; bc2 = st[7]; bc3 = st[8]; bc4 = st[9];
79 st[5] = bc0 ^ (~bc1 & bc2);
80 st[6] = bc1 ^ (~bc2 & bc3);
81 st[7] = bc2 ^ (~bc3 & bc4);
82 st[8] = bc3 ^ (~bc4 & bc0);
83 st[9] = bc4 ^ (~bc0 & bc1);
84 bc0 = st[10]; bc1 = st[11]; bc2 = st[12]; bc3 = st[13]; bc4 = st[14];
85 st[10] = bc0 ^ (~bc1 & bc2);
86 st[11] = bc1 ^ (~bc2 & bc3);
87 st[12] = bc2 ^ (~bc3 & bc4);
88 st[13] = bc3 ^ (~bc4 & bc0);
89 st[14] = bc4 ^ (~bc0 & bc1);
90 bc0 = st[15]; bc1 = st[16]; bc2 = st[17]; bc3 = st[18]; bc4 = st[19];
91 st[15] = bc0 ^ (~bc1 & bc2);
92 st[16] = bc1 ^ (~bc2 & bc3);
93 st[17] = bc2 ^ (~bc3 & bc4);
94 st[18] = bc3 ^ (~bc4 & bc0);
95 st[19] = bc4 ^ (~bc0 & bc1);
96 bc0 = st[20]; bc1 = st[21]; bc2 = st[22]; bc3 = st[23]; bc4 = st[24];
97 st[20] = bc0 ^ (~bc1 & bc2);
98 st[21] = bc1 ^ (~bc2 & bc3);
99 st[22] = bc2 ^ (~bc3 & bc4);
100 st[23] = bc3 ^ (~bc4 & bc0);
101 st[24] = bc4 ^ (~bc0 & bc1);
102 }
103 }
104
105 SHA3_256& SHA3_256::Write(std::span<const unsigned char> data)
106 {
107 if (m_bufsize && data.size() >= sizeof(m_buffer) - m_bufsize) {
108 // Fill the buffer and process it.
109 std::copy(data.begin(), data.begin() + (sizeof(m_buffer) - m_bufsize), m_buffer + m_bufsize);
110 data = data.subspan(sizeof(m_buffer) - m_bufsize);
111 m_state[m_pos++] ^= ReadLE64(m_buffer);
112 m_bufsize = 0;
113 if (m_pos == RATE_BUFFERS) {
114 KeccakF(m_state);
115 m_pos = 0;
116 }
117 }
118 while (data.size() >= sizeof(m_buffer)) {
119 // Process chunks directly from the buffer.
120 m_state[m_pos++] ^= ReadLE64(data.data());
121 data = data.subspan(8);
122 if (m_pos == RATE_BUFFERS) {
123 KeccakF(m_state);
124 m_pos = 0;
125 }
126 }
127 if (data.size()) {
128 // Keep the remainder in the buffer.
129 std::copy(data.begin(), data.end(), m_buffer + m_bufsize);
130 m_bufsize += data.size();
131 }
132 return *this;
133 }
134
135 SHA3_256& SHA3_256::Finalize(std::span<unsigned char> output)
136 {
137 assert(output.size() == OUTPUT_SIZE);
138 std::fill(m_buffer + m_bufsize, m_buffer + sizeof(m_buffer), 0);
139 m_buffer[m_bufsize] ^= 0x06;
140 m_state[m_pos] ^= ReadLE64(m_buffer);
141 m_state[RATE_BUFFERS - 1] ^= 0x8000000000000000;
142 KeccakF(m_state);
143 for (unsigned i = 0; i < 4; ++i) {
144 WriteLE64(output.data() + 8 * i, m_state[i]);
145 }
146 return *this;
147 }
148
149 SHA3_256& SHA3_256::Reset()
150 {
151 m_bufsize = 0;
152 m_pos = 0;
153 std::fill(std::begin(m_state), std::end(m_state), 0);
154 return *this;
155 }
156