| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <20250926065617.14361-1-409411716@gms.tku.edu.tw>
Date: Fri, 26 Sep 2025 14:56:17 +0800
From: Guan-Chun Wu <409411716@....tku.edu.tw>
To: 409411716@....tku.edu.tw
Cc: akpm@...ux-foundation.org,
axboe@...nel.dk,
ceph-devel@...r.kernel.org,
ebiggers@...nel.org,
hch@....de,
home7438072@...il.com,
idryomov@...il.com,
jaegeuk@...nel.org,
kbusch@...nel.org,
linux-fscrypt@...r.kernel.org,
linux-kernel@...r.kernel.org,
linux-nvme@...ts.infradead.org,
sagi@...mberg.me,
tytso@....edu,
visitorckw@...il.com,
xiubli@...hat.com
Subject: [PATCH v3 3/6] lib/base64: rework encode/decode for speed and stricter validation
The old base64 implementation relied on a bit-accumulator loop, which was
slow for larger inputs and too permissive in validation. It would accept
extra '=', missing '=', or even '=' appearing in the middle of the input,
allowing malformed strings to pass. This patch reworks the internals to
improve performance and enforce stricter validation.
Changes:
- Encoder:
* Process input in 3-byte blocks, mapping 24 bits into four 6-bit
symbols, avoiding bit-by-bit shifting and reducing loop iterations.
* Handle the final 1-2 leftover bytes explicitly and emit '=' only when
requested.
- Decoder:
* Based on the reverse lookup tables from the previous patch, decode
input in 4-character groups.
* Each group is looked up directly, converted into numeric values, and
combined into 3 output bytes.
* Explicitly handle padded and unpadded forms:
- With padding: input length must be a multiple of 4, and '=' is
allowed only in the last two positions. Reject stray or early '='.
- Without padding: validate tail lengths (2 or 3 chars) and require
unused low bits to be zero.
* Removed the bit-accumulator style loop to reduce loop iterations.
Performance (x86_64, Intel Core i7-10700 @ 2.90GHz, avg over 1000 runs,
KUnit):
Encode:
64B ~90ns -> ~32ns (~2.8x)
1KB ~1332ns -> ~510ns (~2.6x)
Decode:
64B ~1530ns -> ~64ns (~23.9x)
1KB ~27726ns -> ~982ns (~28.3x)
Co-developed-by: Kuan-Wei Chiu <visitorckw@...il.com>
Signed-off-by: Kuan-Wei Chiu <visitorckw@...il.com>
Co-developed-by: Yu-Sheng Huang <home7438072@...il.com>
Signed-off-by: Yu-Sheng Huang <home7438072@...il.com>
Signed-off-by: Guan-Chun Wu <409411716@....tku.edu.tw>
---
lib/base64.c | 150 +++++++++++++++++++++++++++++++++++++--------------
1 file changed, 110 insertions(+), 40 deletions(-)
diff --git a/lib/base64.c b/lib/base64.c
index b20fdf168..fd1db4611 100644
--- a/lib/base64.c
+++ b/lib/base64.c
@@ -93,26 +93,43 @@ static const s8 base64_rev_tables[][256] = {
int base64_encode(const u8 *src, int srclen, char *dst, bool padding, enum base64_variant variant)
{
u32 ac = 0;
- int bits = 0;
- int i;
char *cp = dst;
const char *base64_table = base64_tables[variant];
- for (i = 0; i < srclen; i++) {
- ac = (ac << 8) | src[i];
- bits += 8;
- do {
- bits -= 6;
- *cp++ = base64_table[(ac >> bits) & 0x3f];
- } while (bits >= 6);
- }
- if (bits) {
- *cp++ = base64_table[(ac << (6 - bits)) & 0x3f];
- bits -= 6;
+ while (srclen >= 3) {
+ ac = ((u32)src[0] << 16) |
+ ((u32)src[1] << 8) |
+ (u32)src[2];
+
+ *cp++ = base64_table[ac >> 18];
+ *cp++ = base64_table[(ac >> 12) & 0x3f];
+ *cp++ = base64_table[(ac >> 6) & 0x3f];
+ *cp++ = base64_table[ac & 0x3f];
+
+ src += 3;
+ srclen -= 3;
}
- while (bits < 0) {
- *cp++ = '=';
- bits += 2;
+
+ switch (srclen) {
+ case 2:
+ ac = ((u32)src[0] << 16) |
+ ((u32)src[1] << 8);
+
+ *cp++ = base64_table[ac >> 18];
+ *cp++ = base64_table[(ac >> 12) & 0x3f];
+ *cp++ = base64_table[(ac >> 6) & 0x3f];
+ if (padding)
+ *cp++ = '=';
+ break;
+ case 1:
+ ac = ((u32)src[0] << 16);
+ *cp++ = base64_table[ac >> 18];
+ *cp++ = base64_table[(ac >> 12) & 0x3f];
+ if (padding) {
+ *cp++ = '=';
+ *cp++ = '=';
+ }
+ break;
}
return cp - dst;
}
@@ -128,39 +145,92 @@ EXPORT_SYMBOL_GPL(base64_encode);
*
* Decodes a string using the selected Base64 variant.
*
- * This implementation hasn't been optimized for performance.
- *
* Return: the length of the resulting decoded binary data in bytes,
* or -1 if the string isn't a valid Base64 string.
*/
int base64_decode(const char *src, int srclen, u8 *dst, bool padding, enum base64_variant variant)
{
- u32 ac = 0;
- int bits = 0;
- int i;
u8 *bp = dst;
- s8 ch;
-
- for (i = 0; i < srclen; i++) {
- if (src[i] == '=') {
- ac = (ac << 6);
- bits += 6;
- if (bits >= 8)
- bits -= 8;
- continue;
- }
- ch = base64_rev_tables[variant][(u8)src[i]];
- if (ch == -1)
+ s8 input1, input2, input3, input4;
+ u32 val;
+
+ if (srclen == 0)
+ return 0;
+
+ /* Validate the input length for padding */
+ if (unlikely(padding && (srclen & 0x03) != 0))
+ return -1;
+
+ while (srclen >= 4) {
+ /* Decode the next 4 characters */
+ input1 = base64_rev_tables[variant][(u8)src[0]];
+ input2 = base64_rev_tables[variant][(u8)src[1]];
+ input3 = base64_rev_tables[variant][(u8)src[2]];
+ input4 = base64_rev_tables[variant][(u8)src[3]];
+
+ /* Return error if any Base64 character is invalid */
+ if (unlikely(input1 < 0 || input2 < 0 || (!padding && (input3 < 0 || input4 < 0))))
+ return -1;
+
+ /* Handle padding */
+ if (unlikely(padding && ((input3 < 0 && input4 >= 0) ||
+ (input3 < 0 && src[2] != '=') ||
+ (input4 < 0 && src[3] != '=') ||
+ (srclen > 4 && (input3 < 0 || input4 < 0)))))
+ return -1;
+ val = ((u32)input1 << 18) |
+ ((u32)input2 << 12) |
+ ((u32)((input3 < 0) ? 0 : input3) << 6) |
+ (u32)((input4 < 0) ? 0 : input4);
+
+ *bp++ = (u8)(val >> 16);
+
+ if (input3 >= 0)
+ *bp++ = (u8)(val >> 8);
+ if (input4 >= 0)
+ *bp++ = (u8)val;
+
+ src += 4;
+ srclen -= 4;
+ }
+
+ /* Handle leftover characters when padding is not used */
+ if (!padding && srclen > 0) {
+ switch (srclen) {
+ case 2:
+ input1 = base64_rev_tables[variant][(u8)src[0]];
+ input2 = base64_rev_tables[variant][(u8)src[1]];
+ if (unlikely(input1 < 0 || input2 < 0))
+ return -1;
+
+ val = ((u32)input1 << 6) | (u32)input2; /* 12 bits */
+ if (unlikely(val & 0x0F))
+ return -1; /* low 4 bits must be zero */
+
+ *bp++ = (u8)(val >> 4);
+ break;
+ case 3:
+ input1 = base64_rev_tables[variant][(u8)src[0]];
+ input2 = base64_rev_tables[variant][(u8)src[1]];
+ input3 = base64_rev_tables[variant][(u8)src[2]];
+ if (unlikely(input1 < 0 || input2 < 0 || input3 < 0))
+ return -1;
+
+ val = ((u32)input1 << 12) |
+ ((u32)input2 << 6) |
+ (u32)input3; /* 18 bits */
+
+ if (unlikely(val & 0x03))
+ return -1; /* low 2 bits must be zero */
+
+ *bp++ = (u8)(val >> 10);
+ *bp++ = (u8)((val >> 2) & 0xFF);
+ break;
+ default:
return -1;
- ac = (ac << 6) | ch;
- bits += 6;
- if (bits >= 8) {
- bits -= 8;
- *bp++ = (u8)(ac >> bits);
}
}
- if (ac & ((1 << bits) - 1))
- return -1;
+
return bp - dst;
}
EXPORT_SYMBOL_GPL(base64_decode);
--
2.34.1
Powered by blists - more mailing lists