keepassxc

1
/*
2
 *  Copyright (C) 2017 KeePassXC Team <team@keepassxc.org>
3
 *
4
 *  This program is free software: you can redistribute it and/or modify
5
 *  it under the terms of the GNU General Public License as published by
6
 *  the Free Software Foundation, either version 2 or (at your option)
7
 *  version 3 of the License.
8
 *
9
 *  This program is distributed in the hope that it will be useful,
10
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
 *  GNU General Public License for more details.
13
 *
14
 *  You should have received a copy of the GNU General Public License
15
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
16
 */
17

18
/* Conforms to RFC 4648. For details, see: https://tools.ietf.org/html/rfc4648
19
 * Use the functions Base32::addPadding/1, Base32::removePadding/1 or
20
 * Base32::sanitizeInput/1 to fix input or output for a particular
21
 * applications (e.g. to use with Google Authenticator).
22
 */
23

24
#include "Base32.h"
25

26
#include <QHash>
27
#include <QVariant>
28

29
constexpr quint64 MASK_40BIT = quint64(0xF8) << 32;
30
constexpr quint64 MASK_35BIT = quint64(0x7C0000000);
31
constexpr quint64 MASK_25BIT = quint64(0x1F00000);
32
constexpr quint64 MASK_20BIT = quint64(0xF8000);
33
constexpr quint64 MASK_10BIT = quint64(0x3E0);
34

35
constexpr char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
36
constexpr quint8 ALPH_POS_2 = 26;
37

38
constexpr quint8 ASCII_2 = static_cast<quint8>('2');
39
constexpr quint8 ASCII_7 = static_cast<quint8>('7');
40
constexpr quint8 ASCII_A = static_cast<quint8>('A');
41
constexpr quint8 ASCII_Z = static_cast<quint8>('Z');
42
constexpr quint8 ASCII_a = static_cast<quint8>('a');
43
constexpr quint8 ASCII_z = static_cast<quint8>('z');
44
constexpr quint8 ASCII_EQ = static_cast<quint8>('=');
45

46
QVariant Base32::decode(const QByteArray& encodedData)
47
{
48
    if (encodedData.size() <= 0) {
49
        return QVariant::fromValue(QByteArray(""));
50
    }
51

52
    if (encodedData.size() % 8 != 0) {
53
        return {};
54
    }
55

56
    int nPads = 0;
57
    for (int i = -1; i > -7; --i) {
58
        if ('=' == encodedData[encodedData.size() + i]) {
59
            ++nPads;
60
        }
61
    }
62

63
    int specialOffset;
64
    int nSpecialBytes;
65

66
    switch (nPads) { // in {0, 1, 3, 4, 6}
67
    case 1:
68
        nSpecialBytes = 4;
69
        specialOffset = 3;
70
        break;
71
    case 3:
72
        nSpecialBytes = 3;
73
        specialOffset = 1;
74
        break;
75
    case 4:
76
        nSpecialBytes = 2;
77
        specialOffset = 4;
78
        break;
79
    case 6:
80
        nSpecialBytes = 1;
81
        specialOffset = 2;
82
        break;
83
    default:
84
        nSpecialBytes = 0;
85
        specialOffset = 0;
86
    }
87

88
    Q_ASSERT(encodedData.size() > 0);
89
    const int nQuanta = encodedData.size() / 8;
90
    const int nBytes = nSpecialBytes > 0 ? (nQuanta - 1) * 5 + nSpecialBytes : nQuanta * 5;
91

92
    QByteArray data(nBytes, Qt::Uninitialized);
93

94
    int i = 0;
95
    int o = 0;
96

97
    while (i < encodedData.size()) {
98
        quint64 quantum = 0;
99
        int nQuantumBytes = 5;
100

101
        for (int n = 0; n < 8; ++n) {
102
            auto ch = static_cast<quint8>(encodedData[i++]);
103
            if ((ASCII_A <= ch && ch <= ASCII_Z) || (ASCII_a <= ch && ch <= ASCII_z)) {
104
                ch -= ASCII_A;
105
                if (ch >= ALPH_POS_2) {
106
                    ch -= ASCII_a - ASCII_A;
107
                }
108
            } else {
109
                if (ASCII_2 <= ch && ch <= ASCII_7) {
110
                    ch -= ASCII_2;
111
                    ch += ALPH_POS_2;
112
                } else {
113
                    if (ASCII_EQ == ch) {
114
                        if (i == encodedData.size()) {
115
                            // finished with special quantum
116
                            quantum >>= specialOffset;
117
                            nQuantumBytes = nSpecialBytes;
118
                        }
119
                        continue;
120
                    } else {
121
                        // illegal character
122
                        return {};
123
                    }
124
                }
125
            }
126

127
            quantum <<= 5;
128
            quantum |= ch;
129
        }
130

131
        const int offset = (nQuantumBytes - 1) * 8;
132
        quint64 mask = quint64(0xFF) << offset;
133
        for (int n = offset; n >= 0 && o < nBytes; n -= 8) {
134
            data[o++] = static_cast<char>((quantum & mask) >> n);
135
            mask >>= 8;
136
        }
137
    }
138

139
    Q_ASSERT(encodedData.size() == i);
140
    Q_ASSERT(nBytes == o);
141

142
    return QVariant::fromValue(data);
143
}
144

145
QByteArray Base32::encode(const QByteArray& data)
146
{
147
    if (data.size() < 1) {
148
        return {};
149
    }
150

151
    const int nBits = data.size() * 8;
152
    const int rBits = nBits % 40; // in {0, 8, 16, 24, 32}
153
    const int nQuanta = nBits / 40 + (rBits > 0 ? 1 : 0);
154
    const int nBytes = nQuanta * 8;
155
    QByteArray encodedData(nBytes, Qt::Uninitialized);
156

157
    int i = 0;
158
    int o = 0;
159
    int n;
160
    quint64 mask;
161
    quint64 quantum;
162

163
    // 40-bits of input per input group
164
    while (i + 5 <= data.size()) {
165
        quantum = 0;
166
        for (n = 32; n >= 0; n -= 8) {
167
            quantum |= (static_cast<quint64>(data[i++]) << n);
168
        }
169

170
        mask = MASK_40BIT;
171
        int index;
172
        for (n = 35; n >= 0; n -= 5) {
173
            index = (quantum & mask) >> n;
174
            Q_ASSERT(0 <= index && index <= 31);
175
            encodedData[o++] = alphabet[index];
176
            mask >>= 5;
177
        }
178
    }
179

180
    // < 40-bits of input at final input group
181
    if (i < data.size()) {
182
        Q_ASSERT(8 <= rBits && rBits <= 32);
183
        quantum = 0;
184
        for (n = rBits - 8; n >= 0; n -= 8) {
185
            quantum |= static_cast<quint64>(data[i++]) << n;
186
        }
187

188
        switch (rBits) {
189
        case 8: // expand to 10 bits
190
            quantum <<= 2;
191
            mask = MASK_10BIT;
192
            n = 5;
193
            break;
194
        case 16: // expand to 20 bits
195
            quantum <<= 4;
196
            mask = MASK_20BIT;
197
            n = 15;
198
            break;
199
        case 24: // expand to 25 bits
200
            quantum <<= 1;
201
            mask = MASK_25BIT;
202
            n = 20;
203
            break;
204
        default: // expand to 35 bits
205
            Q_ASSERT(32 == rBits);
206
            quantum <<= 3;
207
            mask = MASK_35BIT;
208
            n = 30;
209
        }
210

211
        while (n >= 0) {
212
            int index = (quantum & mask) >> n;
213
            Q_ASSERT(0 <= index && index <= 31);
214
            encodedData[o++] = alphabet[index];
215
            mask >>= 5;
216
            n -= 5;
217
        }
218

219
        // add pad characters
220
        while (o < encodedData.size()) {
221
            encodedData[o++] = '=';
222
        }
223
    }
224

225
    Q_ASSERT(data.size() == i);
226
    Q_ASSERT(nBytes == o);
227
    return encodedData;
228
}
229

230
QByteArray Base32::addPadding(const QByteArray& encodedData)
231
{
232
    if (encodedData.size() <= 0 || encodedData.size() % 8 == 0) {
233
        return encodedData;
234
    }
235

236
    const int rBytes = encodedData.size() % 8;
237
    // rBytes must be a member of {2, 4, 5, 7}
238
    if (1 == rBytes || 3 == rBytes || 6 == rBytes) {
239
        return encodedData;
240
    }
241

242
    QByteArray newEncodedData(encodedData);
243
    for (int nPads = 8 - rBytes; nPads > 0; --nPads) {
244
        newEncodedData.append('=');
245
    }
246

247
    return newEncodedData;
248
}
249

250
QByteArray Base32::removePadding(const QByteArray& encodedData)
251
{
252
    if (encodedData.size() <= 0 || encodedData.size() % 8 != 0) {
253
        return encodedData; // return same bad input
254
    }
255

256
    int nPads = 0;
257
    for (int i = -1; i > -7; --i) {
258
        if ('=' == encodedData[encodedData.size() + i]) {
259
            ++nPads;
260
        }
261
    }
262

263
    QByteArray newEncodedData(encodedData);
264
    newEncodedData.remove(encodedData.size() - nPads, nPads);
265
    newEncodedData.resize(encodedData.size() - nPads);
266

267
    return newEncodedData;
268
}
269

270
QByteArray Base32::sanitizeInput(const QByteArray& encodedData)
271
{
272
    if (encodedData.size() <= 0) {
273
        return encodedData;
274
    }
275

276
    QByteArray newEncodedData(encodedData.size(), Qt::Uninitialized);
277
    int i = 0;
278
    for (auto ch : encodedData) {
279
        switch (ch) {
280
        case '0':
281
            newEncodedData[i++] = 'O';
282
            break;
283
        case '1':
284
            newEncodedData[i++] = 'L';
285
            break;
286
        case '8':
287
            newEncodedData[i++] = 'B';
288
            break;
289
        default:
290
            if (('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') || ('2' <= ch && ch <= '7')) {
291
                newEncodedData[i++] = ch;
292
            }
293
        }
294
    }
295
    newEncodedData.resize(i);
296

297
    return addPadding(newEncodedData);
298
}
299