Line data Source code
1 : // SPDX-FileCopyrightText: 2025 KeePassXC Team <team@keepassxc.org>
2 : // SPDX-FileCopyrightText: 2026 Anne Jan Brouwer
3 : // SPDX-License-Identifier: GPL-3.0-or-later
4 :
5 : /**
6 : * @file
7 : * @brief Implements the Base32 codec: quantum-by-quantum decode and encode
8 : * loops with the tail-shape table that fixes KeePassXC's mis-padded cases.
9 : *
10 : * Conforms to RFC 4648, see https://tools.ietf.org/html/rfc4648. Ported from
11 : * KeePassXC `src/core/Base32.cpp`; the differences are documented at each
12 : * site.
13 : *
14 : * @see base32.h
15 : */
16 :
17 : #include "base32.h"
18 :
19 : #include <optional>
20 :
21 : namespace {
22 :
23 : /**
24 : * @name Top-symbol masks
25 : * Mask selecting the top 5 bits of an encode quantum of the given width; the
26 : * encoder shifts it down 5 bits per output symbol. A full input group is 40
27 : * bits; the short final group is widened to 10, 20, 25 or 35 bits.
28 : * @{
29 : */
30 : constexpr quint64 MASK_40BIT = quint64(0xF8) << 32;
31 : constexpr quint64 MASK_35BIT = quint64(0x7C0000000);
32 : constexpr quint64 MASK_25BIT = quint64(0x1F00000);
33 : constexpr quint64 MASK_20BIT = quint64(0xF8000);
34 : constexpr quint64 MASK_10BIT = quint64(0x3E0);
35 : /** @} */
36 :
37 : /** @brief The 32 RFC 4648 symbols, indexed by 5-bit value. */
38 : constexpr char kAlphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
39 : /** @brief Alphabet position of '2', the first digit symbol. */
40 : constexpr quint8 ALPH_POS_2 = 26;
41 :
42 : /** @brief ASCII code of '2', the lowest digit symbol. */
43 : constexpr quint8 ASCII_2 = static_cast<quint8>('2');
44 : /** @brief ASCII code of '7', the highest digit symbol. */
45 : constexpr quint8 ASCII_7 = static_cast<quint8>('7');
46 : /** @brief ASCII code of 'A', the first letter symbol. */
47 : constexpr quint8 ASCII_A = static_cast<quint8>('A');
48 : /** @brief ASCII code of 'Z', the last upper-case letter symbol. */
49 : constexpr quint8 ASCII_Z = static_cast<quint8>('Z');
50 : /** @brief ASCII code of 'a'; lower case is folded onto upper case. */
51 : constexpr quint8 ASCII_a = static_cast<quint8>('a');
52 : /** @brief ASCII code of 'z', the last lower-case letter symbol. */
53 : constexpr quint8 ASCII_z = static_cast<quint8>('z');
54 : /** @brief ASCII code of '=', the padding character. */
55 : constexpr quint8 ASCII_EQ = static_cast<quint8>('=');
56 :
57 : /**
58 : * @brief Length of the trailing run of '=' characters.
59 : *
60 : * Stops at the first non-'=': counting every '=' in the last few positions
61 : * would treat an interior one as padding, and removePadding() would then
62 : * truncate real data.
63 : * @param encodedData Base32 text.
64 : * @return Number of trailing '=', at most 6.
65 : */
66 238 : auto countPadding(const QByteArray &encodedData) -> int {
67 : int nPads = 0;
68 238 : for (qsizetype i = encodedData.size() - 1;
69 499 : i >= 0 && i > encodedData.size() - 7; --i) {
70 482 : if (encodedData.at(i) != '=') {
71 : break;
72 : }
73 261 : ++nPads;
74 : }
75 238 : return nPads;
76 : }
77 :
78 : /**
79 : * @brief What the padding says about the last quantum.
80 : *
81 : * A base32 encoder pads to a multiple of 8 with 0, 1, 3, 4 or 6 '='; any
82 : * other count cannot come from one. KeePassXC fell through to "no special
83 : * bytes" for 2, 5 and 7 and returned wrong-length data.
84 : */
85 : struct Tail {
86 : int bytes = 0; ///< Bytes the final quantum carries; 0 for a full one.
87 : int offset = 0; ///< Bits of the final quantum that are padding.
88 : };
89 :
90 : /// The tail shape for @p nPads trailing '=', or nothing for a count no
91 : /// encoder produces.
92 204 : auto tailShape(int nPads) -> std::optional<Tail> {
93 204 : switch (nPads) {
94 129 : case 0:
95 129 : return Tail{};
96 26 : case 1:
97 26 : return Tail{4, 3};
98 13 : case 3:
99 13 : return Tail{3, 1};
100 18 : case 4:
101 18 : return Tail{2, 4};
102 15 : case 6:
103 15 : return Tail{1, 2};
104 3 : default:
105 3 : return std::nullopt;
106 : }
107 : }
108 :
109 : /// The alphabet position of @p ch (upper or lower case, digits 2-7), or
110 : /// nothing when it is not a base32 symbol.
111 14241 : auto symbolValue(quint8 ch) -> std::optional<quint8> {
112 14241 : if ((ASCII_A <= ch && ch <= ASCII_Z) || (ASCII_a <= ch && ch <= ASCII_z)) {
113 : ch -= ASCII_A;
114 13819 : if (ch >= ALPH_POS_2) {
115 : // Fold lower case onto the same alphabet positions as upper case.
116 : ch -= ASCII_a - ASCII_A;
117 : }
118 13819 : return ch;
119 : }
120 422 : if (ASCII_2 <= ch && ch <= ASCII_7) {
121 421 : return static_cast<quint8>(ch - ASCII_2 + ALPH_POS_2);
122 : }
123 1 : return std::nullopt;
124 : }
125 :
126 : } // namespace
127 :
128 259 : auto Base32::decode(const QByteArray &encodedData) -> QByteArray {
129 : // Strict: a well-formed base32 string is always padded to a multiple of 8.
130 259 : if (encodedData.isEmpty() || encodedData.size() % 8 != 0) {
131 55 : return {};
132 : }
133 204 : const int nPads = countPadding(encodedData);
134 204 : const std::optional<Tail> tail = tailShape(nPads);
135 204 : if (!tail) {
136 3 : return {};
137 : }
138 :
139 201 : const qsizetype nQuanta = encodedData.size() / 8;
140 : const qsizetype nBytes =
141 201 : tail->bytes > 0 ? (nQuanta - 1) * 5 + tail->bytes : nQuanta * 5;
142 :
143 201 : QByteArray data(nBytes, Qt::Uninitialized);
144 : // Written through a raw pointer to avoid QByteArray's detach check on every
145 : // subscript in the hot loop.
146 : char *out = data.data();
147 :
148 : qsizetype i = 0;
149 : qsizetype o = 0;
150 : // Everything from the first '=' onward must be padding. Reuse the pad count
151 : // computed above rather than scanning the tail a second time.
152 201 : const qsizetype firstPad = encodedData.size() - nPads;
153 :
154 2008 : while (i < encodedData.size()) {
155 : quint64 quantum = 0;
156 : int nQuantumBytes = 5;
157 :
158 16276 : for (int n = 0; n < 8; ++n) {
159 14469 : const auto ch = static_cast<quint8>(encodedData.at(i++));
160 14469 : if (ASCII_EQ == ch) {
161 228 : if (i - 1 < firstPad) {
162 : // '=' before the trailing run is not padding, it is malformed input.
163 3 : return {};
164 : }
165 226 : if (i == encodedData.size()) {
166 : // Finished with the short final quantum.
167 71 : quantum >>= tail->offset;
168 : nQuantumBytes = tail->bytes;
169 : }
170 226 : continue;
171 : }
172 14241 : const std::optional<quint8> value = symbolValue(ch);
173 14241 : if (!value) {
174 1 : return {};
175 : }
176 14240 : quantum <<= 5;
177 14240 : quantum |= *value;
178 : }
179 :
180 1807 : const int offset = (nQuantumBytes - 1) * 8;
181 1807 : quint64 mask = quint64(0xFF) << offset;
182 10677 : for (int n = offset; n >= 0 && o < nBytes; n -= 8) {
183 8870 : out[o++] = static_cast<char>((quantum & mask) >> n);
184 8870 : mask >>= 8;
185 : }
186 : }
187 :
188 : return data;
189 : }
190 :
191 23 : auto Base32::encode(const QByteArray &data) -> QByteArray {
192 23 : if (data.isEmpty()) {
193 1 : return {};
194 : }
195 :
196 22 : const qsizetype nBits = data.size() * 8;
197 22 : const int rBits = static_cast<int>(nBits % 40); // in {0, 8, 16, 24, 32}
198 22 : const qsizetype nQuanta = nBits / 40 + (rBits > 0 ? 1 : 0);
199 22 : const qsizetype nBytes = nQuanta * 8;
200 22 : QByteArray encodedData(nBytes, Qt::Uninitialized);
201 : // Raw pointer: see the note in decode().
202 : char *out = encodedData.data();
203 :
204 : qsizetype i = 0;
205 : qsizetype o = 0;
206 : int n = 0;
207 : quint64 mask = 0;
208 : quint64 quantum = 0;
209 :
210 : // QByteArray elements are signed char: widening them directly (as KeePassXC
211 : // does) sign-extends any byte >= 0x80 and the resulting high bits corrupt
212 : // the neighbouring bytes of the quantum. Cast through quint8.
213 : const auto byteAt = [&data](qsizetype index) -> quint64 {
214 221 : return static_cast<quint64>(static_cast<quint8>(data.at(index)));
215 : };
216 :
217 : // 40 bits of input per input group.
218 58 : while (i + 5 <= data.size()) {
219 : quantum = 0;
220 216 : for (n = 32; n >= 0; n -= 8) {
221 180 : quantum |= byteAt(i++) << n;
222 : }
223 :
224 : mask = MASK_40BIT;
225 324 : for (n = 35; n >= 0; n -= 5) {
226 288 : out[o++] = kAlphabet[(quantum & mask) >> n];
227 288 : mask >>= 5;
228 : }
229 : }
230 :
231 : // Fewer than 40 bits of input in the final input group.
232 22 : if (i < data.size()) {
233 : quantum = 0;
234 58 : for (n = rBits - 8; n >= 0; n -= 8) {
235 41 : quantum |= byteAt(i++) << n;
236 : }
237 :
238 17 : switch (rBits) {
239 5 : case 8: // expand to 10 bits
240 5 : quantum <<= 2;
241 : mask = MASK_10BIT;
242 : n = 5;
243 5 : break;
244 4 : case 16: // expand to 20 bits
245 4 : quantum <<= 4;
246 : mask = MASK_20BIT;
247 : n = 15;
248 4 : break;
249 4 : case 24: // expand to 25 bits
250 4 : quantum <<= 1;
251 : mask = MASK_25BIT;
252 : n = 20;
253 4 : break;
254 4 : default: // expand to 35 bits
255 4 : quantum <<= 3;
256 : mask = MASK_35BIT;
257 : n = 30;
258 : }
259 :
260 91 : while (n >= 0) {
261 74 : out[o++] = kAlphabet[(quantum & mask) >> n];
262 74 : mask >>= 5;
263 74 : n -= 5;
264 : }
265 :
266 : // Add the pad characters.
267 79 : while (o < encodedData.size()) {
268 62 : out[o++] = '=';
269 : }
270 : }
271 :
272 : return encodedData;
273 : }
274 :
275 224 : auto Base32::addPadding(const QByteArray &encodedData) -> QByteArray {
276 224 : if (encodedData.isEmpty() || encodedData.size() % 8 == 0) {
277 : return encodedData;
278 : }
279 :
280 95 : const int rBytes = static_cast<int>(encodedData.size() % 8);
281 : // rBytes must be a member of {2, 4, 5, 7}.
282 95 : if (1 == rBytes || 3 == rBytes || 6 == rBytes) {
283 : return encodedData;
284 : }
285 :
286 : QByteArray newEncodedData(encodedData);
287 255 : for (int nPads = 8 - rBytes; nPads > 0; --nPads) {
288 194 : newEncodedData.append('=');
289 : }
290 :
291 : return newEncodedData;
292 : }
293 :
294 35 : auto Base32::removePadding(const QByteArray &encodedData) -> QByteArray {
295 35 : if (encodedData.isEmpty() || encodedData.size() % 8 != 0) {
296 : return encodedData; // return the same bad input
297 : }
298 :
299 : QByteArray newEncodedData(encodedData);
300 34 : newEncodedData.resize(encodedData.size() - countPadding(encodedData));
301 :
302 : return newEncodedData;
303 : }
304 :
305 224 : auto Base32::sanitizeInput(const QByteArray &encodedData) -> QByteArray {
306 224 : if (encodedData.isEmpty()) {
307 : return encodedData;
308 : }
309 :
310 210 : QByteArray newEncodedData(encodedData.size(), Qt::Uninitialized);
311 : // Raw pointer: see the note in decode().
312 : char *out = newEncodedData.data();
313 : qsizetype i = 0;
314 14467 : for (auto ch : encodedData) {
315 14257 : switch (ch) {
316 1 : case '0':
317 1 : out[i++] = 'O';
318 1 : break;
319 11 : case '1':
320 11 : out[i++] = 'L';
321 11 : break;
322 13 : case '8':
323 13 : out[i++] = 'B';
324 13 : break;
325 14232 : default:
326 14232 : if (('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') ||
327 500 : ('2' <= ch && ch <= '7')) {
328 14144 : out[i++] = ch;
329 : }
330 : }
331 : }
332 210 : newEncodedData.resize(i);
333 :
334 210 : return addPadding(newEncodedData);
335 : }
|
QtPass
Developer documentation
