tor  0.4.0.1-alpha
binascii.c
Go to the documentation of this file.
1 /* Copyright (c) 2001, Matej Pfajfar.
2  * Copyright (c) 2001-2004, Roger Dingledine.
3  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4  * Copyright (c) 2007-2019, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
14 #include "orconfig.h"
15 
16 #include "lib/encoding/binascii.h"
17 #include "lib/log/log.h"
18 #include "lib/log/util_bug.h"
19 #include "lib/cc/torint.h"
21 #include "lib/intmath/muldiv.h"
22 #include "lib/malloc/malloc.h"
23 
24 #include <stddef.h>
25 #include <string.h>
26 #include <stdlib.h>
27 
33 const char *
34 hex_str(const char *from, size_t fromlen)
35 {
36  static char buf[65];
37  if (fromlen>(sizeof(buf)-1)/2)
38  fromlen = (sizeof(buf)-1)/2;
39  base16_encode(buf,sizeof(buf),from,fromlen);
40  return buf;
41 }
42 
43 /* Return the base32 encoded size in bytes using the source length srclen.
44  *
45  * (WATCH OUT: This API counts the terminating NUL byte, but
46  * base64_encode_size does not.)
47  */
48 size_t
49 base32_encoded_size(size_t srclen)
50 {
51  size_t enclen;
52  tor_assert(srclen < SIZE_T_CEILING / 8);
53  enclen = BASE32_NOPAD_BUFSIZE(srclen);
54  tor_assert(enclen < INT_MAX && enclen > srclen);
55  return enclen;
56 }
57 
59 void
60 base32_encode(char *dest, size_t destlen, const char *src, size_t srclen)
61 {
62  unsigned int i, v, u;
63  size_t nbits = srclen * 8;
64  size_t bit;
65 
66  /* We need enough space for the encoded data and the extra NUL byte. */
67  tor_assert(base32_encoded_size(srclen) <= destlen);
68  tor_assert(destlen < SIZE_T_CEILING);
69 
70  /* Make sure we leave no uninitialized data in the destination buffer. */
71  memset(dest, 0, destlen);
72 
73  for (i=0,bit=0; bit < nbits; ++i, bit+=5) {
74  /* set v to the 16-bit value starting at src[bits/8], 0-padded. */
75  size_t idx = bit / 8;
76  v = ((uint8_t)src[idx]) << 8;
77  if (idx+1 < srclen)
78  v += (uint8_t)src[idx+1];
79  /* set u to the 5-bit value at the bit'th bit of buf. */
80  u = (v >> (11-(bit%8))) & 0x1F;
81  dest[i] = BASE32_CHARS[u];
82  }
83  dest[i] = '\0';
84 }
85 
89 int
90 base32_decode(char *dest, size_t destlen, const char *src, size_t srclen)
91 {
92  /* XXXX we might want to rewrite this along the lines of base64_decode, if
93  * it ever shows up in the profile. */
94  unsigned int i;
95  size_t nbits, j, bit;
96  char *tmp;
97  nbits = ((srclen * 5) / 8) * 8;
98 
99  tor_assert(srclen < SIZE_T_CEILING / 5);
100  tor_assert((nbits/8) <= destlen); /* We need enough space. */
101  tor_assert(destlen < SIZE_T_CEILING);
102 
103  /* Make sure we leave no uninitialized data in the destination buffer. */
104  memset(dest, 0, destlen);
105 
106  /* Convert base32 encoded chars to the 5-bit values that they represent. */
107  tmp = tor_malloc_zero(srclen);
108  for (j = 0; j < srclen; ++j) {
109  if (src[j] > 0x60 && src[j] < 0x7B) tmp[j] = src[j] - 0x61;
110  else if (src[j] > 0x31 && src[j] < 0x38) tmp[j] = src[j] - 0x18;
111  else if (src[j] > 0x40 && src[j] < 0x5B) tmp[j] = src[j] - 0x41;
112  else {
113  log_warn(LD_GENERAL, "illegal character in base32 encoded string");
114  tor_free(tmp);
115  return -1;
116  }
117  }
118 
119  /* Assemble result byte-wise by applying five possible cases. */
120  for (i = 0, bit = 0; bit < nbits; ++i, bit += 8) {
121  switch (bit % 40) {
122  case 0:
123  dest[i] = (((uint8_t)tmp[(bit/5)]) << 3) +
124  (((uint8_t)tmp[(bit/5)+1]) >> 2);
125  break;
126  case 8:
127  dest[i] = (((uint8_t)tmp[(bit/5)]) << 6) +
128  (((uint8_t)tmp[(bit/5)+1]) << 1) +
129  (((uint8_t)tmp[(bit/5)+2]) >> 4);
130  break;
131  case 16:
132  dest[i] = (((uint8_t)tmp[(bit/5)]) << 4) +
133  (((uint8_t)tmp[(bit/5)+1]) >> 1);
134  break;
135  case 24:
136  dest[i] = (((uint8_t)tmp[(bit/5)]) << 7) +
137  (((uint8_t)tmp[(bit/5)+1]) << 2) +
138  (((uint8_t)tmp[(bit/5)+2]) >> 3);
139  break;
140  case 32:
141  dest[i] = (((uint8_t)tmp[(bit/5)]) << 5) +
142  ((uint8_t)tmp[(bit/5)+1]);
143  break;
144  }
145  }
146 
147  memset(tmp, 0, srclen); /* on the heap, this should be safe */
148  tor_free(tmp);
149  tmp = NULL;
150  return 0;
151 }
152 
153 #define BASE64_OPENSSL_LINELEN 64
154 
165 size_t
166 base64_encode_size(size_t srclen, int flags)
167 {
168  size_t enclen;
169 
170  /* Use INT_MAX for overflow checking because base64_encode() returns int. */
171  tor_assert(srclen < INT_MAX);
172  tor_assert(CEIL_DIV(srclen, 3) < INT_MAX / 4);
173 
174  enclen = BASE64_LEN(srclen);
175  if (flags & BASE64_ENCODE_MULTILINE)
176  enclen += CEIL_DIV(enclen, BASE64_OPENSSL_LINELEN);
177 
178  tor_assert(enclen < INT_MAX && (enclen == 0 || enclen > srclen));
179  return enclen;
180 }
181 
186 size_t
187 base64_decode_maxsize(size_t srclen)
188 {
189  tor_assert(srclen < INT_MAX / 3);
190 
191  return CEIL_DIV(srclen * 3, 4);
192 }
193 
195 static const char base64_encode_table[64] = {
196  'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
197  'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
198  'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
199  'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f',
200  'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
201  'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
202  'w', 'x', 'y', 'z', '0', '1', '2', '3',
203  '4', '5', '6', '7', '8', '9', '+', '/'
204 };
205 
214 int
215 base64_encode(char *dest, size_t destlen, const char *src, size_t srclen,
216  int flags)
217 {
218  const unsigned char *usrc = (unsigned char *)src;
219  const unsigned char *eous = usrc + srclen;
220  char *d = dest;
221  uint32_t n = 0;
222  size_t linelen = 0;
223  size_t enclen;
224  int n_idx = 0;
225 
226  if (!src || !dest)
227  return -1;
228 
229  /* Ensure that there is sufficient space, including the NUL. */
230  enclen = base64_encode_size(srclen, flags);
231  if (destlen < enclen + 1)
232  return -1;
233  if (destlen > SIZE_T_CEILING)
234  return -1;
235  if (enclen > INT_MAX)
236  return -1;
237 
238  /* Make sure we leave no uninitialized data in the destination buffer. */
239  memset(dest, 0, destlen);
240 
241  /* XXX/Yawning: If this ends up being too slow, this can be sped up
242  * by separating the multiline format case and the normal case, and
243  * processing 48 bytes of input at a time when newlines are desired.
244  */
245 #define ENCODE_CHAR(ch) \
246  STMT_BEGIN \
247  *d++ = ch; \
248  if (flags & BASE64_ENCODE_MULTILINE) { \
249  if (++linelen % BASE64_OPENSSL_LINELEN == 0) { \
250  linelen = 0; \
251  *d++ = '\n'; \
252  } \
253  } \
254  STMT_END
255 
256 #define ENCODE_N(idx) \
257  ENCODE_CHAR(base64_encode_table[(n >> ((3 - idx) * 6)) & 0x3f])
258 
259 #define ENCODE_PAD() ENCODE_CHAR('=')
260 
261  /* Iterate over all the bytes in src. Each one will add 8 bits to the
262  * value we're encoding. Accumulate bits in <b>n</b>, and whenever we
263  * have 24 bits, batch them into 4 bytes and flush those bytes to dest.
264  */
265  for ( ; usrc < eous; ++usrc) {
266  n = (n << 8) | *usrc;
267  if ((++n_idx) == 3) {
268  ENCODE_N(0);
269  ENCODE_N(1);
270  ENCODE_N(2);
271  ENCODE_N(3);
272  n_idx = 0;
273  n = 0;
274  }
275  }
276  switch (n_idx) {
277  case 0:
278  /* 0 leftover bits, no pading to add. */
279  break;
280  case 1:
281  /* 8 leftover bits, pad to 12 bits, write the 2 6-bit values followed
282  * by 2 padding characters.
283  */
284  n <<= 4;
285  ENCODE_N(2);
286  ENCODE_N(3);
287  ENCODE_PAD();
288  ENCODE_PAD();
289  break;
290  case 2:
291  /* 16 leftover bits, pad to 18 bits, write the 3 6-bit values followed
292  * by 1 padding character.
293  */
294  n <<= 2;
295  ENCODE_N(1);
296  ENCODE_N(2);
297  ENCODE_N(3);
298  ENCODE_PAD();
299  break;
300  // LCOV_EXCL_START -- we can't reach this point, because we enforce
301  // 0 <= ncov_idx < 3 in the loop above.
302  default:
303  /* Something went catastrophically wrong. */
305  return -1;
306  // LCOV_EXCL_STOP
307  }
308 
309 #undef ENCODE_N
310 #undef ENCODE_PAD
311 #undef ENCODE_CHAR
312 
313  /* Multiline output always includes at least one newline. */
314  if (flags & BASE64_ENCODE_MULTILINE && linelen != 0)
315  *d++ = '\n';
316 
317  tor_assert(d - dest == (ptrdiff_t)enclen);
318 
319  *d++ = '\0'; /* NUL terminate the output. */
320 
321  return (int) enclen;
322 }
323 
326 int
327 base64_encode_nopad(char *dest, size_t destlen,
328  const uint8_t *src, size_t srclen)
329 {
330  int n = base64_encode(dest, destlen, (const char*) src, srclen, 0);
331  if (n <= 0)
332  return n;
333  tor_assert((size_t)n < destlen && dest[n] == 0);
334  char *in, *out;
335  in = out = dest;
336  while (*in) {
337  if (*in == '=' || *in == '\n') {
338  ++in;
339  } else {
340  *out++ = *in++;
341  }
342  }
343  *out = 0;
344 
345  tor_assert(out - dest <= INT_MAX);
346 
347  return (int)(out - dest);
348 }
349 
350 #undef BASE64_OPENSSL_LINELEN
351 
354 #define X 255
355 #define SP 64
356 #define PAD 65
357 
362 static const uint8_t base64_decode_table[256] = {
363  X, X, X, X, X, X, X, X, X, SP, SP, SP, X, SP, X, X, /* */
364  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
365  SP, X, X, X, X, X, X, X, X, X, X, 62, X, X, X, 63,
366  52, 53, 54, 55, 56, 57, 58, 59, 60, 61, X, X, X, PAD, X, X,
367  X, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
368  15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, X, X, X, X, X,
369  X, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
370  41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, X, X, X, X, X,
371  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
372  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
373  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
374  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
375  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
376  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
377  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
378  X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
379 };
380 
393 int
394 base64_decode(char *dest, size_t destlen, const char *src, size_t srclen)
395 {
396  const char *eos = src+srclen;
397  uint32_t n=0;
398  int n_idx=0;
399  size_t di = 0;
400 
401  if (destlen > INT_MAX)
402  return -1;
403 
404  /* Make sure we leave no uninitialized data in the destination buffer. */
405  memset(dest, 0, destlen);
406 
407  /* Iterate over all the bytes in src. Each one will add 0 or 6 bits to the
408  * value we're decoding. Accumulate bits in <b>n</b>, and whenever we have
409  * 24 bits, batch them into 3 bytes and flush those bytes to dest.
410  */
411  for ( ; src < eos; ++src) {
412  unsigned char c = (unsigned char) *src;
413  uint8_t v = base64_decode_table[c];
414  switch (v) {
415  case X:
416  /* This character isn't allowed in base64. */
417  return -1;
418  case SP:
419  /* This character is whitespace, and has no effect. */
420  continue;
421  case PAD:
422  /* We've hit an = character: the data is over. */
423  goto end_of_loop;
424  default:
425  /* We have an actual 6-bit value. Append it to the bits in n. */
426  n = (n<<6) | v;
427  if ((++n_idx) == 4) {
428  /* We've accumulated 24 bits in n. Flush them. */
429  if (destlen < 3 || di > destlen - 3)
430  return -1;
431  dest[di++] = (n>>16);
432  dest[di++] = (n>>8) & 0xff;
433  dest[di++] = (n) & 0xff;
434  n_idx = 0;
435  n = 0;
436  }
437  }
438  }
439  end_of_loop:
440  /* If we have leftover bits, we need to cope. */
441  switch (n_idx) {
442  case 0:
443  default:
444  /* No leftover bits. We win. */
445  break;
446  case 1:
447  /* 6 leftover bits. That's invalid; we can't form a byte out of that. */
448  return -1;
449  case 2:
450  /* 12 leftover bits: The last 4 are padding and the first 8 are data. */
451  if (destlen < 1 || di > destlen - 1)
452  return -1;
453  dest[di++] = n >> 4;
454  break;
455  case 3:
456  /* 18 leftover bits: The last 2 are padding and the first 16 are data. */
457  if (destlen < 2 || di > destlen - 2)
458  return -1;
459  dest[di++] = n >> 10;
460  dest[di++] = n >> 2;
461  }
462 
463  tor_assert(di <= destlen);
464 
465  return (int)di;
466 }
467 #undef X
468 #undef SP
469 #undef PAD
470 
475 void
476 base16_encode(char *dest, size_t destlen, const char *src, size_t srclen)
477 {
478  const char *end;
479  char *cp;
480 
481  tor_assert(srclen < SIZE_T_CEILING / 2 - 1);
482  tor_assert(destlen >= BASE16_BUFSIZE(srclen));
483  tor_assert(destlen < SIZE_T_CEILING);
484 
485  /* Make sure we leave no uninitialized data in the destination buffer. */
486  memset(dest, 0, destlen);
487 
488  cp = dest;
489  end = src+srclen;
490  while (src<end) {
491  *cp++ = "0123456789ABCDEF"[ (*(const uint8_t*)src) >> 4 ];
492  *cp++ = "0123456789ABCDEF"[ (*(const uint8_t*)src) & 0xf ];
493  ++src;
494  }
495  *cp = '\0';
496 }
497 
503 int
504 base16_decode(char *dest, size_t destlen, const char *src, size_t srclen)
505 {
506  const char *end;
507  char *dest_orig = dest;
508  int v1,v2;
509 
510  if ((srclen % 2) != 0)
511  return -1;
512  if (destlen < srclen/2 || destlen > INT_MAX)
513  return -1;
514 
515  /* Make sure we leave no uninitialized data in the destination buffer. */
516  memset(dest, 0, destlen);
517 
518  end = src+srclen;
519  while (src<end) {
520  v1 = hex_decode_digit(*src);
521  v2 = hex_decode_digit(*(src+1));
522  if (v1<0||v2<0)
523  return -1;
524  *(uint8_t*)dest = (v1<<4)|v2;
525  ++dest;
526  src+=2;
527  }
528 
529  tor_assert((dest-dest_orig) <= (ptrdiff_t) destlen);
530 
531  return (int) (dest-dest_orig);
532 }
size_t base64_decode_maxsize(size_t srclen)
Definition: binascii.c:187
static int hex_decode_digit(char c)
Definition: compat_ctype.h:43
#define LD_GENERAL
Definition: log.h:58
size_t base64_encode_size(size_t srclen, int flags)
Definition: binascii.c:166
void base32_encode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:60
static const uint8_t base64_decode_table[256]
Definition: binascii.c:362
#define tor_free(p)
Definition: malloc.h:52
#define tor_fragile_assert()
Definition: util_bug.h:221
Integer definitions used throughout Tor.
Headers for util_malloc.c.
#define X
Definition: binascii.c:354
int base64_encode(char *dest, size_t destlen, const char *src, size_t srclen, int flags)
Definition: binascii.c:215
int base32_decode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:90
tor_assert(buffer)
#define SIZE_T_CEILING
Definition: torint.h:126
static const char base64_encode_table[64]
Definition: binascii.c:195
const char * hex_str(const char *from, size_t fromlen)
Definition: binascii.c:34
Header for binascii.c.
void base16_encode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:476
#define BASE64_LEN(n)
Definition: binascii.h:28
Header for muldiv.c.
#define BASE32_CHARS
Definition: binascii.h:53
int base64_encode_nopad(char *dest, size_t destlen, const uint8_t *src, size_t srclen)
Definition: binascii.c:327
int base64_decode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:394
Locale-independent character-type inspection (header)
int base16_decode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:504
Headers for log.c.
Macros to manage assertions, fatal and non-fatal.