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