// Least Significant First byte order is assumed

/*
The SecurID hash -- designed in 1985 by John Brainard, still at 
RSA Labs -- has been used, unchanged, to generate PRN token-codes (aka, 
"one-time passwords") in all of the more than 8 million SecurID hand-held 
authentication devices that RSA have been sold over the past 14 years.
*/

/* (c) 1999-3001 I.C. Wiener */

#include <u.h>
#include <libc.h>
#include <bio.h>

typedef union {
	uvlong Q[1];
	ulong D[2];
	ushort W[4];
	uchar B[8];
} Octet;

#define bswap32(x) 		(rol32((ulong)(x), 8) & 0x00ff00ff | ror32((ulong)(x), 8) & 0xff00ff00)

static uchar
ror8(uchar x, int n)
{
	return (x>>(n&7)) | (x<<((-n)&7));
}

static ulong
ror32(ulong x, int n)
{
	return (x>>(n&31)) | (x<<((-n)&31));
}

static ulong
rol32(ulong x, int n)
{
	return (x << (n & 31)) | (x >> ((-n) & 31));
}

static uvlong
rol64(uvlong x, int n)
{
	return (x << (n & 63)) | (x >> ((-n) & 63));
}

static uvlong
bswap64(uvlong x)
{
	ulong a = (ulong) x, b = (ulong) (x >> 32);

	return (((uvlong) bswap32(a)) << 32) | bswap32(b);
}

void
securid_expand_key_to_4_bit_per_byte(Octet source, uchar *target)
{
	int i;

	for(i = 0; i < 8; i++){
		target[i*2] = source.B[i] >> 4;
		target[i*2 +1] = source.B[i] & 0x0F;
	}
}

void
securid_expand_data_to_1_bit_per_byte(Octet source, uchar *target)
{
	int i, j, k;

	for(i = 0, k = 0; i < 8; i++)
		for(j = 7; j >= 0; j--)
			target[k++] = (source.B[i] >> j) &1;
}

void
securid_reassemble_64_bit_from_64_byte(uchar * source, Octet * target)
{
	int i = 0, j, k = 0;

	for(target->Q[0] = 0; i < 8; i++)
		for(j = 7; j >= 0; j--)
			target->B[i] |= source[k++] << j;
}

void
securid_permute_data(Octet * data, Octet key)
{
	uchar bit_data[128];
	uchar hex_key[16];

	int i, j, k, b, m, bit;
	uchar *hkw, *permuted_bit;

	memset(bit_data, 0, sizeof(bit_data));
	securid_expand_data_to_1_bit_per_byte(*data, bit_data);
	securid_expand_key_to_4_bit_per_byte(key, hex_key);

	for(bit = 32, hkw = hex_key, m = 0; bit <= 32; hkw += 8, bit -= 32){
		permuted_bit = bit_data + 64 + bit;
		for(k = 0, b = 28; k < 8; k++, b -= 4){
			for(j = hkw[k]; j; j--){
				bit_data[(bit + b + m + 4) & 0x3F] = bit_data[m];
				m = (m + 1) & 0x3F;
			}

			for(i = 0; i < 4; i++)
				permuted_bit[b + i] |= bit_data[(bit + b + m + i) & 0x3F];
		}
	}
	securid_reassemble_64_bit_from_64_byte(bit_data + 64, data);
}

void
securid_do_4_rounds(Octet * data, Octet * key)
{
	uchar t;
	int round, i, j;

	for(round = 0; round < 4; round++){
		for(i = 0; i < 8; i++) {
			for(j = 0; j < 8; j++) {
				if((((key->B[i] >> (j ^ 7)) ^ (data->B[0] >> 7)) & 1) != 0) {
					t = data->B[4];
					data->B[4] = 100 - data->B[0];
					data->B[0] = t;
				}
				else
					data->B[0] = (uchar)(ror8((uchar)(
						ror8(data->B[0], 1) - 1), 1) - 1) ^ data->B[4];
				data->Q[0] = bswap64(rol64(bswap64(data->Q[0]), 1));
			}
		}
		key->Q[0] ^= data->Q[0];
	}
}

void
securid_convert_to_decimal(Octet * data, Octet key)
{
	ulong i;
	uchar c, hi, lo;

	c = (key.B[7] & 0x0F) % 5;

	for(i = 0; i < 8; i++) {
		hi = data->B[i] >> 4;
		lo = data->B[i] & 0x0F;
		c = (c + (key.B[i] >> 4)) % 5;
		if(hi > 9)
			data->B[i] = ((hi = (hi - (c + 1) * 2) % 10) << 4) | lo;
		c = (c + (key.B[i] & 0x0F)) % 5;
		if(lo > 9)
			data->B[i] = (lo = ((lo - (c + 1) * 2) % 10)) | (hi << 4);
	}
}

void
securid_hash_data(Octet * data, Octet key, uchar convert_to_decimal)
{
	securid_permute_data(data, key);	// data bits are permuted
						// depending on the key 
	securid_do_4_rounds(data, &key);	// key changes as well 
	securid_permute_data(data, key);	// final permutation is based on the new key 

	if(convert_to_decimal)
		securid_convert_to_decimal(data, key);	// decimal conversion depends on the key too 
}

void
securid_hash_time(ulong time, Octet * hash, Octet key)
{
	hash->B[0] = (uchar) (time >> 16);
	hash->B[1] = (uchar) (time >> 8);
	hash->B[2] = (uchar) time;
	hash->B[3] = (uchar) time;
	hash->B[4] = (uchar) (time >> 16);
	hash->B[5] = (uchar) (time >> 8);
	hash->B[6] = (uchar) time;
	hash->B[7] = (uchar) time;

	securid_hash_data(hash, key, 1);
}

uchar
hex(char c)
{
	uchar n = c - '0';

	if(n < 10)
		return n;
	n -= 7;
	if((n > 9) && (n < 16))
		return n;
	n -= 32;
	if((n > 9) && (n < 16))
		return n;
	sysfatal("bad hex\n");
	return -1;				/* shut up 8c */
}

uchar
read_line(Biobuf *bi, Octet * outb)
{
	uchar n;
	ulong i;
	char *line, *s;

	if((line = Brdline(bi, '\n')) == nil)
		return 1;
	line[Blinelen(bi) -1] = 0;

	s = line;
	if(*s == '#')
		s++;
	if(strncmp(line, "0000:", 5) == 0)
		return 1;
	for(i = 0; i < 38; i++) {
		n = hex(*s++) << 4;
		n |= hex(*s++);
		outb->B[i] = n;
	}

	/*
	 * securid bullshit import file decryption (how much do they pay their programmers???) 
	 * anyway, I replaced their 16 stupid xor-D69E36D2/rol-1 "rounds" with one rol-16/xor 
	 * doing exactly the same thing (I wonder what they used to generate their token secrets? ;) 
	 *
	 * btw, we ignore the last two bytes that are just a silly checksum 
	 */
	for(i = 0; i < 9; i++)
		outb->D[i] = rol32(outb->D[i], 16) ^ 0x88BF88BF;
	return 0;
}

void
main(int argc, char *argv[])
{
	signed long i, j, k, t, serial;
	Octet key, hi, hj, input, data[5];
	Biobuf *bi;
	char *s;

	if(argc != 4){
		fprint(2, "usage: securid <tokenfile.asc> <serial no> <current number on token>\n");
		exits("usage");
	}

	if((bi = Bopen(argv[1], OREAD)) == nil)
		sysfatal("%s cannot open\n", argv[1]);

	serial = bswap32(strtoul(argv[2], &s, 16));
	/* although it's base-16, it's still just a decimal number  */

	input.D[0] = strtoul(argv[3], &s, 16);
	/* although it's base-16, it's still just a decimal number as well */

	for(;;){
		if(read_line(bi, data))
			sysfatal("unexpected EOF\n");
		j = data->D[1];	
		// print("%08X\n", j); 
		if(read_line(bi, data))
			sysfatal("unexpected EOF\n");
		if(j == serial){
			key.Q[0] = data->Q[0];
			break;
		}
	}
	Bterm(bi);

	if(j != serial) {
		print("Token not found.\n");
		exits("no token");
	}

	/* (t & -4) for 60 sec periods, (t & -8) for 120 sec periods, etc. */
	t = (time(nil) / 60 - 0x806880) * 2;

	k = 0;
	for(i = (t & -4), j = (t & -4) - 4; i < (t & -4) + 0x40560; i += 4, j -= 4){
		securid_hash_time(i, &hi, key);
		securid_hash_time(j, &hj, key);
		if((hi.B[0] == input.B[2]) && (hi.B[1] == input.B[1]) && (hi.B[2] == input.B[0])){
			j = i;
			k = (i - (t & -4)) / 2;
			break;
		}
		else
		if((hi.B[3] == input.B[2]) && (hi.B[4] == input.B[1]) && (hi.B[5] == input.B[0])){
			j = i;
			k = (i - (t & -4)) / 2 + 1;
			break;
		}
		else
		if((hj.B[0] == input.B[2]) && (hj.B[1] == input.B[1]) && (hj.B[2] == input.B[0])){
			i = j;
			k = (j - (t & -4)) / 2;
			break;
		}
		else
		if((hj.B[3] == input.B[2]) && (hj.B[4] == input.B[1]) && (hj.B[5] == input.B[0])){
			i = j;
			k = (j - (t & -4)) / 2 + 1;
			break;
		}
	}
	if(i != j)
		sysfatal("Either your clock is off by more than 1 year or invalid token secret file\n");

	if(k){
		fprint(2, "\nToken is %s your clock by %d minute%s.\n\n",
			(k > 0) ? "ahead of" : "behind", abs(k),
			(abs(k) == 1) ? "" : "s");
	}

	for(j = 0; j < 40; j += 4) {
		securid_hash_time(i + j, &hi, key);
		print("%lX : %02X%02X%02X\n", i + j, hi.B[0], hi.B[1], hi.B[2]);
		print("%lX : %02X%02X%02X\n", i + j, hi.B[3], hi.B[4], hi.B[5]);
	}
	exits(nil);
}