1//! Hexadecimal and Base64 codecs designed for cryptographic use.
2//! This file provides (best-effort) constant-time encoding and decoding functions for hexadecimal and Base64 formats.
3//! This is designed to be used in cryptographic applications where timing attacks are a concern.
4const std = @import("std");
5const testing = std.testing;
6const StaticBitSet = std.bit_set.Static;
7
8pub const Error = error{
9 /// An invalid character was found in the input.
10 InvalidCharacter,
11 /// The input is not properly padded.
12 InvalidPadding,
13 /// The input buffer is too small to hold the output.
14 NoSpaceLeft,
15 /// The input and output buffers are not the same size.
16 SizeMismatch,
17};
18
19/// (best-effort) constant time hexadecimal encoding and decoding.
20pub const hex = struct {
21 /// Encodes a binary buffer into a hexadecimal string.
22 /// The output buffer must be twice the size of the input buffer.
23 pub fn encode(encoded: []u8, bin: []const u8, comptime case: std.fmt.Case) error{SizeMismatch}!void {
24 if (encoded.len / 2 != bin.len) {
25 return error.SizeMismatch;
26 }
27 for (bin, 0..) |v, i| {
28 const b: u16 = v >> 4;
29 const c: u16 = v & 0xf;
30 const off = if (case == .upper) 32 else 0;
31 const x =
32 ((87 - off + c + (((c -% 10) >> 8) & ~@as(u16, 38 - off))) & 0xff) << 8 |
33 ((87 - off + b + (((b -% 10) >> 8) & ~@as(u16, 38 - off))) & 0xff);
34 encoded[i * 2] = @truncate(x);
35 encoded[i * 2 + 1] = @truncate(x >> 8);
36 }
37 }
38
39 /// Decodes a hexadecimal string into a binary buffer.
40 /// The output buffer must be half the size of the input buffer.
41 pub fn decode(bin: []u8, encoded: []const u8) error{ SizeMismatch, InvalidCharacter, InvalidPadding }!void {
42 if (encoded.len % 2 != 0) {
43 return error.InvalidPadding;
44 }
45 if (bin.len < encoded.len / 2) {
46 return error.SizeMismatch;
47 }
48 _ = decodeAny(bin, encoded, null) catch |err| {
49 switch (err) {
50 error.InvalidCharacter, error.InvalidPadding => |e| return e,
51 else => unreachable,
52 }
53 };
54 }
55
56 /// A decoder that ignores certain characters.
57 /// The decoder will skip any characters that are in the ignore list.
58 pub const DecoderWithIgnore = struct {
59 /// The characters to ignore.
60 ignored_chars: StaticBitSet(256) = undefined,
61
62 /// Decodes a hexadecimal string into a binary buffer.
63 /// The output buffer must be half the size of the input buffer.
64 pub fn decode(
65 self: DecoderWithIgnore,
66 bin: []u8,
67 encoded: []const u8,
68 ) error{ NoSpaceLeft, InvalidCharacter, InvalidPadding }![]const u8 {
69 return decodeAny(bin, encoded, self.ignored_chars);
70 }
71
72 /// Returns the decoded length of a hexadecimal string, ignoring any characters in the ignore list.
73 /// This operation does not run in constant time, but it aims to avoid leaking information about the underlying hexadecimal string.
74 pub fn decodedLenForSlice(decoder: DecoderWithIgnore, encoded: []const u8) !usize {
75 var hex_len = encoded.len;
76 for (encoded) |c| {
77 if (decoder.ignored_chars.isSet(c)) hex_len -= 1;
78 }
79 if (hex_len % 2 != 0) {
80 return error.InvalidPadding;
81 }
82 return hex_len / 2;
83 }
84
85 /// Returns the maximum possible decoded size for a given input length after skipping ignored characters.
86 pub fn decodedLenUpperBound(hex_len: usize) usize {
87 return hex_len / 2;
88 }
89 };
90
91 /// Creates a new decoder that ignores certain characters.
92 /// The decoder will skip any characters that are in the ignore list.
93 /// The ignore list must not contain any valid hexadecimal characters.
94 pub fn decoderWithIgnore(ignore_chars: []const u8) error{InvalidCharacter}!DecoderWithIgnore {
95 var ignored_chars = StaticBitSet(256).empty;
96 for (ignore_chars) |c| {
97 switch (c) {
98 '0'...'9', 'a'...'f', 'A'...'F' => return error.InvalidCharacter,
99 else => if (ignored_chars.isSet(c)) return error.InvalidCharacter,
100 }
101 ignored_chars.set(c);
102 }
103 return DecoderWithIgnore{ .ignored_chars = ignored_chars };
104 }
105
106 fn decodeAny(
107 bin: []u8,
108 encoded: []const u8,
109 ignored_chars: ?StaticBitSet(256),
110 ) error{ NoSpaceLeft, InvalidCharacter, InvalidPadding }![]const u8 {
111 var bin_pos: usize = 0;
112 var state: bool = false;
113 var c_acc: u8 = 0;
114 for (encoded) |c| {
115 const c_num = c ^ 48;
116 const c_num0: u8 = @truncate((@as(u16, c_num) -% 10) >> 8);
117 const c_alpha: u8 = (c & ~@as(u8, 32)) -% 55;
118 const c_alpha0: u8 = @truncate(((@as(u16, c_alpha) -% 10) ^ (@as(u16, c_alpha) -% 16)) >> 8);
119 if ((c_num0 | c_alpha0) == 0) {
120 if (ignored_chars) |set| {
121 if (set.isSet(c)) {
122 continue;
123 }
124 }
125 return error.InvalidCharacter;
126 }
127 const c_val = (c_num0 & c_num) | (c_alpha0 & c_alpha);
128 if (bin_pos >= bin.len) {
129 return error.NoSpaceLeft;
130 }
131 if (!state) {
132 c_acc = c_val << 4;
133 } else {
134 bin[bin_pos] = c_acc | c_val;
135 bin_pos += 1;
136 }
137 state = !state;
138 }
139 if (state) {
140 return error.InvalidPadding;
141 }
142 return bin[0..bin_pos];
143 }
144};
145
146/// (best-effort) constant time base64 encoding and decoding.
147pub const base64 = struct {
148 /// The base64 variant to use.
149 pub const Variant = packed struct {
150 /// Use the URL-safe alphabet instead of the standard alphabet.
151 urlsafe_alphabet: bool = false,
152 /// Enable padding with '=' characters.
153 padding: bool = true,
154
155 /// The standard base64 variant.
156 pub const standard: Variant = .{ .urlsafe_alphabet = false, .padding = true };
157 /// The URL-safe base64 variant.
158 pub const urlsafe: Variant = .{ .urlsafe_alphabet = true, .padding = true };
159 /// The standard base64 variant without padding.
160 pub const standard_nopad: Variant = .{ .urlsafe_alphabet = false, .padding = false };
161 /// The URL-safe base64 variant without padding.
162 pub const urlsafe_nopad: Variant = .{ .urlsafe_alphabet = true, .padding = false };
163 };
164
165 /// Returns the length of the encoded base64 string for a given length.
166 pub fn encodedLen(bin_len: usize, variant: Variant) usize {
167 if (variant.padding) {
168 return (bin_len + 2) / 3 * 4;
169 } else {
170 const leftover = bin_len % 3;
171 return bin_len / 3 * 4 + (leftover * 4 + 2) / 3;
172 }
173 }
174
175 /// Returns the maximum possible decoded size for a given input length - The actual length may be less if the input includes padding.
176 /// `InvalidPadding` is returned if the input length is not valid.
177 pub fn decodedLen(b64_len: usize, variant: Variant) !usize {
178 var result = b64_len / 4 * 3;
179 const leftover = b64_len % 4;
180 if (variant.padding) {
181 if (leftover % 4 != 0) return error.InvalidPadding;
182 } else {
183 if (leftover % 4 == 1) return error.InvalidPadding;
184 result += leftover * 3 / 4;
185 }
186 return result;
187 }
188
189 /// Encodes a binary buffer into a base64 string.
190 /// The output buffer must be at least `encodedLen(bin.len)` bytes long.
191 pub fn encode(encoded: []u8, bin: []const u8, comptime variant: Variant) error{NoSpaceLeft}![]const u8 {
192 var acc_len: u4 = 0;
193 var b64_pos: usize = 0;
194 var acc: u16 = 0;
195 const nibbles = bin.len / 3;
196 const remainder = bin.len - 3 * nibbles;
197 var b64_len = nibbles * 4;
198 if (remainder != 0) {
199 b64_len += if (variant.padding) 4 else 2 + (remainder >> 1);
200 }
201 if (encoded.len < b64_len) {
202 return error.NoSpaceLeft;
203 }
204 const urlsafe = variant.urlsafe_alphabet;
205 for (bin) |v| {
206 acc = (acc << 8) + v;
207 acc_len += 8;
208 while (acc_len >= 6) {
209 acc_len -= 6;
210 encoded[b64_pos] = charFromByte(@as(u6, @truncate(acc >> acc_len)), urlsafe);
211 b64_pos += 1;
212 }
213 }
214 if (acc_len > 0) {
215 encoded[b64_pos] = charFromByte(@as(u6, @truncate(acc << (6 - acc_len))), urlsafe);
216 b64_pos += 1;
217 }
218 while (b64_pos < b64_len) {
219 encoded[b64_pos] = '=';
220 b64_pos += 1;
221 }
222 return encoded[0..b64_pos];
223 }
224
225 /// Decodes a base64 string into a binary buffer.
226 /// The output buffer must be at least `decodedLenUpperBound(encoded.len)` bytes long.
227 pub fn decode(bin: []u8, encoded: []const u8, comptime variant: Variant) error{ InvalidCharacter, InvalidPadding }![]const u8 {
228 return decodeAny(bin, encoded, variant, null) catch |err| {
229 switch (err) {
230 error.InvalidCharacter, error.InvalidPadding => |e| return e,
231 else => unreachable,
232 }
233 };
234 }
235
236 //// A decoder that ignores certain characters.
237 pub const DecoderWithIgnore = struct {
238 /// The characters to ignore.
239 ignored_chars: StaticBitSet(256) = undefined,
240
241 /// Decodes a base64 string into a binary buffer.
242 /// The output buffer must be at least `decodedLenUpperBound(encoded.len)` bytes long.
243 pub fn decode(
244 self: DecoderWithIgnore,
245 bin: []u8,
246 encoded: []const u8,
247 comptime variant: Variant,
248 ) error{ NoSpaceLeft, InvalidCharacter, InvalidPadding }![]const u8 {
249 return decodeAny(bin, encoded, variant, self.ignored_chars);
250 }
251
252 /// Returns the decoded length of a base64 string, ignoring any characters in the ignore list.
253 /// This operation does not run in constant time, but it aims to avoid leaking information about the underlying base64 string.
254 pub fn decodedLenForSlice(decoder: DecoderWithIgnore, encoded: []const u8, variant: Variant) !usize {
255 var b64_len = encoded.len;
256 for (encoded) |c| {
257 if (decoder.ignored_chars.isSet(c)) b64_len -= 1;
258 }
259 return base64.decodedLen(b64_len, variant);
260 }
261
262 /// Returns the maximum possible decoded size for a given input length after skipping ignored characters.
263 pub fn decodedLenUpperBound(b64_len: usize) usize {
264 return b64_len / 3 * 4;
265 }
266 };
267
268 /// Creates a new decoder that ignores certain characters.
269 pub fn decoderWithIgnore(ignore_chars: []const u8) error{InvalidCharacter}!DecoderWithIgnore {
270 var ignored_chars = StaticBitSet(256).empty;
271 for (ignore_chars) |c| {
272 switch (c) {
273 'A'...'Z', 'a'...'z', '0'...'9' => return error.InvalidCharacter,
274 else => if (ignored_chars.isSet(c)) return error.InvalidCharacter,
275 }
276 ignored_chars.set(c);
277 }
278 return DecoderWithIgnore{ .ignored_chars = ignored_chars };
279 }
280
281 fn eq(x: u8, y: u8) u8 {
282 return ~@as(u8, @truncate((0 -% (@as(u16, x) ^ @as(u16, y))) >> 8));
283 }
284
285 fn gt(x: u8, y: u8) u8 {
286 return @truncate((@as(u16, y) -% @as(u16, x)) >> 8);
287 }
288
289 fn ge(x: u8, y: u8) u8 {
290 return ~gt(y, x);
291 }
292
293 fn lt(x: u8, y: u8) u8 {
294 return gt(y, x);
295 }
296
297 fn le(x: u8, y: u8) u8 {
298 return ge(y, x);
299 }
300
301 fn charFromByte(x: u8, comptime urlsafe: bool) u8 {
302 return (lt(x, 26) & (x +% 'A')) |
303 (ge(x, 26) & lt(x, 52) & (x +% 'a' -% 26)) |
304 (ge(x, 52) & lt(x, 62) & (x +% '0' -% 52)) |
305 (eq(x, 62) & if (urlsafe) '-' else '+') | (eq(x, 63) & if (urlsafe) '_' else '/');
306 }
307
308 fn byteFromChar(c: u8, comptime urlsafe: bool) u8 {
309 const x =
310 (ge(c, 'A') & le(c, 'Z') & (c -% 'A')) |
311 (ge(c, 'a') & le(c, 'z') & (c -% 'a' +% 26)) |
312 (ge(c, '0') & le(c, '9') & (c -% '0' +% 52)) |
313 (eq(c, if (urlsafe) '-' else '+') & 62) | (eq(c, if (urlsafe) '_' else '/') & 63);
314 return x | (eq(x, 0) & ~eq(c, 'A'));
315 }
316
317 fn skipPadding(
318 encoded: []const u8,
319 padding_len: usize,
320 ignored_chars: ?StaticBitSet(256),
321 ) error{InvalidPadding}![]const u8 {
322 var b64_pos: usize = 0;
323 var i = padding_len;
324 while (i > 0) {
325 if (b64_pos >= encoded.len) {
326 return error.InvalidPadding;
327 }
328 const c = encoded[b64_pos];
329 if (c == '=') {
330 i -= 1;
331 } else if (ignored_chars) |set| {
332 if (!set.isSet(c)) {
333 return error.InvalidPadding;
334 }
335 }
336 b64_pos += 1;
337 }
338 return encoded[b64_pos..];
339 }
340
341 fn decodeAny(
342 bin: []u8,
343 encoded: []const u8,
344 comptime variant: Variant,
345 ignored_chars: ?StaticBitSet(256),
346 ) error{ NoSpaceLeft, InvalidCharacter, InvalidPadding }![]const u8 {
347 var acc: u16 = 0;
348 var acc_len: u4 = 0;
349 var bin_pos: usize = 0;
350 var premature_end: ?usize = null;
351 const urlsafe = variant.urlsafe_alphabet;
352 for (encoded, 0..) |c, b64_pos| {
353 const d = byteFromChar(c, urlsafe);
354 if (d == 0xff) {
355 if (ignored_chars) |set| {
356 if (set.isSet(c)) continue;
357 }
358 premature_end = b64_pos;
359 break;
360 }
361 acc = (acc << 6) + d;
362 acc_len += 6;
363 if (acc_len >= 8) {
364 acc_len -= 8;
365 if (bin_pos >= bin.len) {
366 return error.NoSpaceLeft;
367 }
368 bin[bin_pos] = @truncate(acc >> acc_len);
369 bin_pos += 1;
370 }
371 }
372 if (acc_len > 4 or (acc & ((@as(u16, 1) << acc_len) -% 1)) != 0) {
373 return error.InvalidCharacter;
374 }
375 const padding_len = acc_len / 2;
376 if (premature_end) |pos| {
377 const remaining =
378 if (variant.padding)
379 try skipPadding(encoded[pos..], padding_len, ignored_chars)
380 else
381 encoded[pos..];
382 if (ignored_chars) |set| {
383 for (remaining) |c| {
384 if (!set.isSet(c)) {
385 return error.InvalidCharacter;
386 }
387 }
388 } else if (remaining.len != 0) {
389 return error.InvalidCharacter;
390 }
391 } else if (variant.padding and padding_len != 0) {
392 return error.InvalidPadding;
393 }
394 return bin[0..bin_pos];
395 }
396};
397
398test "hex" {
399 var default_rng = std.Random.DefaultPrng.init(testing.random_seed);
400 var rng = default_rng.random();
401 var bin_buf: [1000]u8 = undefined;
402 rng.bytes(&bin_buf);
403 var bin2_buf: [bin_buf.len]u8 = undefined;
404 var hex_buf: [bin_buf.len * 2]u8 = undefined;
405 for (0..1000) |_| {
406 const bin_len = rng.intRangeAtMost(usize, 0, bin_buf.len);
407 const bin = bin_buf[0..bin_len];
408 const bin2 = bin2_buf[0..bin_len];
409 inline for (.{ .lower, .upper }) |case| {
410 const hex_len = bin_len * 2;
411 const encoded = hex_buf[0..hex_len];
412 try hex.encode(encoded, bin, case);
413 try hex.decode(bin2, encoded);
414 try testing.expectEqualSlices(u8, bin, bin2);
415 }
416 }
417}
418
419test "base64" {
420 var default_rng = std.Random.DefaultPrng.init(testing.random_seed);
421 var rng = default_rng.random();
422 var bin_buf: [1000]u8 = undefined;
423 rng.bytes(&bin_buf);
424 var bin2_buf: [bin_buf.len]u8 = undefined;
425 var b64_buf: [(bin_buf.len + 3) / 3 * 4]u8 = undefined;
426 for (0..1000) |_| {
427 const bin_len = rng.intRangeAtMost(usize, 0, bin_buf.len);
428 const bin = bin_buf[0..bin_len];
429 const bin2 = bin2_buf[0..bin_len];
430 inline for ([_]base64.Variant{
431 .standard,
432 .standard_nopad,
433 .urlsafe,
434 .urlsafe_nopad,
435 }) |variant| {
436 const b64_len = base64.encodedLen(bin_len, variant);
437 const encoded_buf = b64_buf[0..b64_len];
438 const encoded = try base64.encode(encoded_buf, bin, variant);
439 const decoded = try base64.decode(bin2, encoded, variant);
440 try testing.expectEqualSlices(u8, bin, decoded);
441 }
442 }
443}
444
445test "hex with ignored chars" {
446 const encoded = "01020304050607\n08090A0B0C0D0E0F\n";
447 const expected = [_]u8{ 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F };
448 var bin_buf: [encoded.len / 2]u8 = undefined;
449 try testing.expectError(error.InvalidCharacter, hex.decode(&bin_buf, encoded));
450 const bin = try (try hex.decoderWithIgnore("\r\n")).decode(&bin_buf, encoded);
451 try testing.expectEqualSlices(u8, &expected, bin);
452}
453
454test "base64 urlsafe" {
455 const input = [_]u8{ 0xfb, 0xff };
456 var enc_buf: [4]u8 = undefined;
457 var dec_buf: [2]u8 = undefined;
458 const encoded = try base64.encode(&enc_buf, &input, .urlsafe);
459 try testing.expectEqualSlices(u8, "-_8=", encoded);
460 const decoded = try base64.decode(&dec_buf, encoded, .urlsafe);
461 try testing.expectEqualSlices(u8, &input, decoded);
462}
463
464test "base64 with ignored chars" {
465 const encoded = "dGVzdCBi\r\nYXNlNjQ=\n";
466 const expected = "test base64";
467 var bin_buf: [base64.DecoderWithIgnore.decodedLenUpperBound(encoded.len)]u8 = undefined;
468 try testing.expectError(error.InvalidCharacter, base64.decode(&bin_buf, encoded, .standard));
469 const bin = try (try base64.decoderWithIgnore("\r\n")).decode(&bin_buf, encoded, .standard);
470 try testing.expectEqualSlices(u8, expected, bin);
471}