detects if a MAC address was generated using macchanger --random

detect-macchanger.c

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#ifdef _OPENMP
#include <omp.h>
#endif

/*
 * macchanger --random uses the following code to generate random MAC addresses:
 *    srandom(seed);
 *    MAC[0] = (random() % 255) & 0xFC | 2
 *    MAC[1] = random() % 255
 *    MAC[2] = random() % 255
 *    MAC[3] = random() % 255
 *    MAC[4] = random() % 255
 *    MAC[5] = random() % 255
 * Here seed is generated from `/dev/urandom`, so it's completely random.
 * But the `srandom` only expects 32 bits seed, so we can just brute force it
 * to check if a MAC address was likely generated by macchanger.
 *
 * Sadly glibc's `srandom` implementation isn't the fastes,
 * as it calles `random` 344 times to warm up the PRNG,
 * so we'll use some math to create a faster version.
 * glibc's `random` uses a Lagged Fibonacci generator:
 *     https://www.mathstat.dal.ca/~selinger/random/
 * The nth number of a Lagged Fibonacci sequence can be computed in constant
 * time, as shown in:
 * https://web.archive.org/web/20130208161623/
 * http://fusharblog.com/solving-linear-recurrence-for-programming-contest/
 * The code bellow uses the above approach to brute force the MAC addresses:
 */

static uint32_t jumpTables[6][31];

typedef struct {
	uint32_t at[31][31];
} Mat;

static Mat
mat_mul(Mat A, Mat B)
{
	Mat C = {0};
	for (size_t i = 0; i < 31; ++i)
	for (size_t j = 0; j < 31; ++j)
	for (size_t k = 0; k < 31; ++k)
		C.at[i][j] += A.at[i][k] * B.at[k][j];
	return C;
}

static Mat
mat_pow(Mat A, size_t p)
{
	if (p == 1)
		return A;
	if (p & 1)
		return mat_mul(A, mat_pow(A, p-1));
	Mat X = mat_pow(A, p/2);
	return mat_mul(X, X);
}

static void
init_jump_tables(void)
{
	Mat T = { 0 };
	for (size_t i = 1; i < 31; ++i)
		T.at[i-1][i] = 1;
	T.at[30][31 - 31] = 1;
	T.at[30][31 -  3] = 1;

	Mat Tn = mat_pow(T, 341);
	for (size_t i = 0; i < 6; ++i){
		for (size_t j = 0; j < 31; ++j)
			jumpTables[i][j] = Tn.at[0][j];
		Tn = mat_mul(Tn,T);
	}
}


static inline int
match_mac(unsigned seed, unsigned char targets[6])
{
	uint64_t res = 0;
	int32_t r[344+6];
	size_t i;

	r[0] = seed;
	for (i=1; i<31; i++) {
		r[i] = (16807LL * r[i-1]) % 2147483647;
		if (r[i] < 0) {
			r[i] += 2147483647;
		}
	}
	for (i=31; i<34; i++) {
		r[i] = r[i-31];
	}

	for (i=0; i<6; i++) {
		uint32_t sum = 0;
		for (size_t j = 34-31; j < 34; j++)
			sum += r[j] * jumpTables[i][j-3];
		sum >>= 1;
		if (i == 0)
			sum = (sum %255) & 0xFC | 2;
		else
			sum %= 255;
		if (targets[i] != sum)
			return 0;
	}
	return 1;
}



int
main(int argc, char **argv)
{
	init_jump_tables();

	unsigned char target[6];
	if (argc != 2 ||
	    sscanf(argv[1], "%2x:%2x:%2x:%2x:%2x:%2x",
	           target,target+1,target+2,target+3,target+4,target+5) != 6) {
		fprintf(stderr, "Usage: %s xx:xx:xx:xx:xx:xx\n", argv[0]);
		return EXIT_FAILURE;
	}

	target[0] |= 2; // ignore bia
	uint32_t found = 0;
	#pragma omp parallel for schedule(static)
	for (size_t i = 1; i < 1ull<<32; ++i) {
		if ((i & 0x1fffff) == 0) {
#ifdef _OPENMP
			if (omp_get_thread_num() == 0) {
				size_t max = ((1ull<<32) / omp_get_num_threads());
#else
			{
				size_t max = 1ull<<32;
#endif
				printf("\r%f%%", i*100.0f/max);
				fflush(stdout);
			}
		}
		if (match_mac(i, target)) {
			printf("\nThe address was likely generated by "
				"macchanger, the seed was: %zu\n", i);
			exit(EXIT_SUCCESS);
		}
	}


	puts("\nThe address likely wasn't generated by macchanger");
	return EXIT_SUCCESS;
}