shithub: riscv

Download patch

ref: c039b52fc3d7c225fe8b6f88f21df83ac26d5984
parent: ee89c82dd35475b93dd67773b7d10e461921a734
author: cinap_lenrek <cinap_lenrek@felloff.net>
date: Sun Dec 31 04:06:42 EST 2017 

libc: constant time implementation for encode(2) routines, fix base32

the string encoding functions touch secret key material
in a bunch of places (devtls, devcap), so make sure we do
not leak information by cache timing side channels, making
the encoding and decoding routines constant time.

we also expose the alphabets through encXchr()/decXchr()
functions so caller can find the end of a encoded string
before calling decode function (for libmp).

the base32 encoding was broken in several ways. inputs
lengths of len%5 == [2,3,4] had output truncated and
it was using non-standard alphabet. documenting the alphabet
change in the manpage.


--- a/sys/include/libc.h
+++ b/sys/include/libc.h
@@ -369,6 +369,12 @@
 extern	int	enc32(char*, int, uchar*, int);
 extern	int	dec16(uchar*, int, char*, int);
 extern	int	enc16(char*, int, uchar*, int);
+extern	int	dec64chr(int);
+extern	int	enc64chr(int);
+extern	int	dec32chr(int);
+extern	int	enc32chr(int);
+extern	int	dec16chr(int);
+extern	int	enc16chr(int);
 extern	int	encodefmt(Fmt*);
 extern	void	exits(char*);
 extern	double	frexp(double, int*);
--- a/sys/man/2/encode
+++ b/sys/man/2/encode
@@ -1,6 +1,8 @@
 .TH ENCODE 2
 .SH NAME
-dec64, enc64, dec32, enc32, dec16, enc16, encodefmt \- encoding byte arrays as strings
+dec64, enc64, dec32, enc32, dec16, enc16, \
+dec64chr, enc64chr, dec32chr, enc32chr, dec16chr, enc16chr, \
+encodefmt \- encoding byte arrays as strings
 .SH SYNOPSIS
 .B #include <u.h>
 .br
@@ -25,8 +27,28 @@
 int	enc16(char *out, int lim, uchar *in, int n)
 .PP
 .B
+int	dec64chr(int c)
+.PP
+.B
+int	enc64chr(int o)
+.PP
+.B
+int	dec32chr(int c)
+.PP
+.B
+int	enc32chr(int o)
+.PP
+.B
+int	dec16chr(int c)
+.PP
+.B
+int	enc16chr(int o)
+.PP
+.B
 int	encodefmt(Fmt*)
 .SH DESCRIPTION
+The functions described here handle encoding and decoding of
+bytes to printable ASCII strings as specified by RFC4648. 
 .PP
 .IR Enc16 ,
 .I enc32
@@ -47,6 +69,20 @@
 for base 32, if the input buffer length is not a multiple
 of 8.
 .PP
+.IR Dec16chr ,
+.I dec32chr
+and
+.I dec64chr
+return the value for a symbol of the alphabet or -1 when the
+symbol is not in the alphabet.
+.PP
+.IR Enc16chr ,
+.I enc32chr
+and
+.I enc64chr
+encode a symbol of the alphabet given a value.
+if the value is out of range then zero is returned.
+.PP
 .I Encodefmt
 can be used with
 .IR fmtinstall (2)
@@ -62,7 +98,8 @@
 flag forces lower case.
 .TP
 .B <
-base 32
+base 32. The default is upper case, same as
+.BR H .
 .TP
 .B [
 base 64 (same as MIME)
@@ -80,8 +117,19 @@
 
 .EE
 .SH SOURCE
+.B /sys/src/libc/port/u16.c
+.br
 .B /sys/src/libc/port/u32.c
 .br
 .B /sys/src/libc/port/u64.c
 .br
 .B /sys/src/libc/port/encodefmt.c
+.SH HISTORY
+In Jan 2018, base 32 encoding was changed from non-standard
+to standard RFC4648 alphabet.
+.TP
+old:
+.B "23456789abcdefghijkmnpqrstuvwxyz"
+.TP
+new:
+.B "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567"
--- a/sys/src/libc/port/encodefmt.c
+++ b/sys/src/libc/port/encodefmt.c
@@ -48,17 +48,14 @@
 	// convert
 	out = buf;
 	switch(f->r){
-	case '<':
-		rv = enc32(out, len, b, ilen);
-		break;
 	case '[':
 		rv = enc64(out, len, b, ilen);
 		break;
+	case '<':
+		rv = enc32(out, len, b, ilen);
+		break;
 	case 'H':
 		rv = enc16(out, len, b, ilen);
-		if(rv >= 0 && (f->flags & FmtLong))
-			for(p = buf; *p; p++)
-				*p = tolower(*p);
 		break;
 	default:
 		rv = -1;
@@ -66,6 +63,10 @@
 	}
 	if(rv < 0)
 		goto error;
+
+	if((f->flags & FmtLong) != 0 && f->r != '[')
+		for(p = buf; *p; p++)
+			*p = tolower(*p);
 
 	fmtstrcpy(f, buf);
 	if(buf != obuf)
--- a/sys/src/libc/port/u16.c
+++ b/sys/src/libc/port/u16.c
@@ -1,8 +1,30 @@
 #include <u.h>
 #include <libc.h>
-static char t16e[] = "0123456789ABCDEF";
 
+#define between(x,min,max)	(((min-1-x) & (x-max-1))>>8)
+
 int
+enc16chr(int o)
+{
+	int c;
+
+	c  = between(o,  0,  9) & ('0'+o);
+	c |= between(o, 10, 15) & ('A'+(o-10));
+	return c;
+}
+
+int
+dec16chr(int c)
+{
+	int o;
+
+	o  = between(c, '0', '9') & (1+(c-'0'));
+	o |= between(c, 'A', 'F') & (1+10+(c-'A'));
+	o |= between(c, 'a', 'f') & (1+10+(c-'a'));
+	return o-1;
+}
+
+int
 dec16(uchar *out, int lim, char *in, int n)
 {
 	int c, w = 0, i = 0;
@@ -10,14 +32,8 @@
 	uchar *eout = out + lim;
 
 	while(n-- > 0){
-		c = *in++;
-		if('0' <= c && c <= '9')
-			c = c - '0';
-		else if('a' <= c && c <= 'z')
-			c = c - 'a' + 10;
-		else if('A' <= c && c <= 'Z')
-			c = c - 'A' + 10;
-		else
+		c = dec16chr(*in++);
+		if(c < 0)
 			continue;
 		w = (w<<4) + c;
 		i++;
@@ -44,8 +60,8 @@
 		c = *in++;
 		if(out + 2 >= eout)
 			goto exhausted;
-		*out++ = t16e[c>>4];
-		*out++ = t16e[c&0xf];
+		*out++ = enc16chr(c>>4);
+		*out++ = enc16chr(c&15);
 	}
 exhausted:
 	*out = 0;
--- a/sys/src/libc/port/u32.c
+++ b/sys/src/libc/port/u32.c
@@ -1,21 +1,44 @@
 #include <u.h>
 #include <libc.h>
 
+#define between(x,min,max)	(((min-1-x) & (x-max-1))>>8)
+
 int
+enc32chr(int o)
+{
+	int c;
+
+	c  = between(o,  0, 25) & ('A'+o);
+	c |= between(o, 26, 31) & ('2'+(o-26));
+	return c;
+}
+
+int
+dec32chr(int c)
+{
+	int o;
+
+	o  = between(c, 'A', 'Z') & (1+(c-'A'));
+	o |= between(c, 'a', 'z') & (1+(c-'a'));
+	o |= between(c, '2', '7') & (1+26+(c-'2'));
+	return o-1;
+}
+
+int
 dec32(uchar *dest, int ndest, char *src, int nsrc)
 {
-	char *s, *tab;
 	uchar *start;
-	int i, u[8];
+	int i, j, u[8];
 
 	if(ndest+1 < (5*nsrc+7)/8)
 		return -1;
 	start = dest;
-	tab = "23456789abcdefghijkmnpqrstuvwxyz";
 	while(nsrc>=8){
 		for(i=0; i<8; i++){
-			s = strchr(tab,(int)src[i]);
-			u[i] = s ? s-tab : 0;
+			j = dec32chr(src[i]);
+			if(j < 0)
+				j = 0;
+			u[i] = j;
 		}
 		*dest++ = (u[0]<<3) | (0x7 & (u[1]>>2));
 		*dest++ = ((0x3 & u[1])<<6) | (u[2]<<1) | (0x1 & (u[3]>>4));
@@ -29,8 +52,10 @@
 		if(nsrc == 1 || nsrc == 3 || nsrc == 6)
 			return -1;
 		for(i=0; i<nsrc; i++){
-			s = strchr(tab,(int)src[i]);
-			u[i] = s ? s-tab : 0;
+			j = dec32chr(src[i]);
+			if(j < 0)
+				j = 0;
+			u[i] = j;
 		}
 		*dest++ = (u[0]<<3) | (0x7 & (u[1]>>2));
 		if(nsrc == 2)
@@ -50,60 +75,57 @@
 int
 enc32(char *dest, int ndest, uchar *src, int nsrc)
 {
-	char *tab, *start;
+	char *start;
 	int j;
 
-	if(ndest <= (8*nsrc+4)/5 )
+	if(ndest <= (8*nsrc+4)/5)
 		return -1;
 	start = dest;
-	tab = "23456789abcdefghijkmnpqrstuvwxyz";
 	while(nsrc>=5){
 		j = (0x1f & (src[0]>>3));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x1c & (src[0]<<2)) | (0x03 & (src[1]>>6));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x1f & (src[1]>>1));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x10 & (src[1]<<4)) | (0x0f & (src[2]>>4));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x1e & (src[2]<<1)) | (0x01 & (src[3]>>7));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x1f & (src[3]>>2));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x18 & (src[3]<<3)) | (0x07 & (src[4]>>5));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x1f & (src[4]));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		src  += 5;
 		nsrc -= 5;
 	}
 	if(nsrc){
 		j = (0x1f & (src[0]>>3));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x1c & (src[0]<<2));
 		if(nsrc == 1)
 			goto out;
 		j |= (0x03 & (src[1]>>6));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x1f & (src[1]>>1));
+		*dest++ = enc32chr(j);
+		j = (0x10 & (src[1]<<4));
 		if(nsrc == 2)
 			goto out;
-		*dest++ = tab[j];
-		j = (0x10 & (src[1]<<4));
-		if(nsrc == 3)
-			goto out;
 		j |= (0x0f & (src[2]>>4));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x1e & (src[2]<<1));
-		if(nsrc == 4)
+		if(nsrc == 3)
 			goto out;
 		j |= (0x01 & (src[3]>>7));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x1f & (src[3]>>2));
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 		j = (0x18 & (src[3]<<3));
 out:
-		*dest++ = tab[j];
+		*dest++ = enc32chr(j);
 	}
 	*dest = 0;
 	return dest-start;
--- a/sys/src/libc/port/u64.c
+++ b/sys/src/libc/port/u64.c
@@ -1,31 +1,35 @@
 #include <u.h>
 #include <libc.h>
 
-enum {
-	INVAL=	255
-};
+#define between(x,min,max)	(((min-1-x) & (x-max-1))>>8)
 
-static uchar t64d[256] = {
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,   62,INVAL,INVAL,INVAL,   63,
-      52,   53,   54,   55,   56,   57,   58,   59,   60,   61,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,    0,    1,    2,    3,    4,    5,    6,    7,    8,    9,   10,   11,   12,   13,   14,
-      15,   16,   17,   18,   19,   20,   21,   22,   23,   24,   25,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,   26,   27,   28,   29,   30,   31,   32,   33,   34,   35,   36,   37,   38,   39,   40,
-      41,   42,   43,   44,   45,   46,   47,   48,   49,   50,   51,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,
-   INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL
-};
-static char t64e[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+int
+enc64chr(int o)
+{
+	int c;
 
+	c  = between(o,  0, 25) & ('A'+o);
+	c |= between(o, 26, 51) & ('a'+(o-26));
+	c |= between(o, 52, 61) & ('0'+(o-52));
+	c |= between(o, 62, 62) & ('+');
+	c |= between(o, 63, 63) & ('/');
+	return c;
+}
+
 int
+dec64chr(int c)
+{
+	int o;
+
+	o  = between(c, 'A', 'Z') & (1+(c-'A'));
+	o |= between(c, 'a', 'z') & (1+26+(c-'a'));
+	o |= between(c, '0', '9') & (1+52+(c-'0'));
+	o |= between(c, '+', '+') & (1+62);
+	o |= between(c, '/', '/') & (1+63);
+	return o-1;
+}
+
+int
 dec64(uchar *out, int lim, char *in, int n)
 {
 	ulong b24;
@@ -36,9 +40,8 @@
 	b24 = 0;
 	i = 0;
 	while(n-- > 0){
-
-		c = t64d[*(uchar*)in++];
-		if(c == INVAL)
+		c = dec64chr(*in++);
+		if(c < 0)
 			continue;
 		switch(i){
 		case 0:
@@ -58,8 +61,8 @@
 			*out++ = b24>>16;
 			*out++ = b24>>8;
 			*out++ = b24;
-			i = -1;
-			break;
+			i = 0;
+			continue;
 		}
 		i++;
 	}
@@ -89,34 +92,34 @@
 	char *e = out + lim;
 
 	for(i = n/3; i > 0; i--){
-		b24 = (*in++)<<16;
-		b24 |= (*in++)<<8;
+		b24 = *in++<<16;
+		b24 |= *in++<<8;
 		b24 |= *in++;
 		if(out + 4 >= e)
 			goto exhausted;
-		*out++ = t64e[(b24>>18)];
-		*out++ = t64e[(b24>>12)&0x3f];
-		*out++ = t64e[(b24>>6)&0x3f];
-		*out++ = t64e[(b24)&0x3f];
+		*out++ = enc64chr(b24>>18);
+		*out++ = enc64chr((b24>>12)&0x3f);
+		*out++ = enc64chr((b24>>6)&0x3f);
+		*out++ = enc64chr(b24&0x3f);
 	}
 
 	switch(n%3){
 	case 2:
-		b24 = (*in++)<<16;
-		b24 |= (*in)<<8;
+		b24 = *in++<<16;
+		b24 |= *in<<8;
 		if(out + 4 >= e)
 			goto exhausted;
-		*out++ = t64e[(b24>>18)];
-		*out++ = t64e[(b24>>12)&0x3f];
-		*out++ = t64e[(b24>>6)&0x3f];
+		*out++ = enc64chr(b24>>18);
+		*out++ = enc64chr((b24>>12)&0x3f);
+		*out++ = enc64chr((b24>>6)&0x3f);
 		*out++ = '=';
 		break;
 	case 1:
-		b24 = (*in)<<16;
+		b24 = *in<<16;
 		if(out + 4 >= e)
 			goto exhausted;
-		*out++ = t64e[(b24>>18)];
-		*out++ = t64e[(b24>>12)&0x3f];
+		*out++ = enc64chr(b24>>18);
+		*out++ = enc64chr((b24>>12)&0x3f);
 		*out++ = '=';
 		*out++ = '=';
 		break;