Mordan is a program that can be used to determine the internal state of the java.util.Random() random number generator

mordan.c

/* ---------------------------------------------------------------------
 * mordan.c
 * revision 0.4
 * ---------------------------------------------------------------------
 * November 2005, Yorick Koster, ITsec Security Services
 * ---------------------------------------------------------------------
 * Mordan is a program that can be used to determine the internal state
 * of the java.util.Random() random number generator. In order to do so,
 * mordan requires two integer values (created with Random.nextInt())
 * or one long value (created with Random.nextLong()).
 *
 * If mordan is able to determine the internal state, it will output the
 * next 8 random values that java.util.Random() will create. Currently,
 * Mordan is only tested against java.util.Random(). It may work against
 * other random number generators as well.
 * ---------------------------------------------------------------------
 */

#include <stdio.h>

typedef enum _runmode
{
	none,
	crack_int,
	crack_long
} runmode;

unsigned long long int seed = 0ULL;

/* returns the next nbits random bits */
int next(int nbits);
/* returns the next random integer value */
int nextint(void);
/* returns the next long (Java) value */
long long int nextlong(void);
/* determine the internal state of the RNG */
unsigned long long int crack(unsigned int x, unsigned int y);
/* convert a string to a long long int */
long long int strtolli(const char *ptr);
/* display usage information */
void usage(const char *name, FILE *out);

int main(int argc, char *argv[], char *envp[])
{
	runmode mode = none;
	int i;
	int x = 0;
	int y = 0;
	long long int xy = 0LL;

	/* check if long long int is at least 64 bits */
	if(sizeof(long long int) < 8)
	{
		fprintf(stderr, "Sorry, running on an unsupported platform.\n");
		return 1;
	}

	/* determine the mode based on the number of arguments */
	switch(argc)
	{
	case 2:
		mode = crack_long;
		break;
	case 3:
		mode = crack_int;
		break;
	default:
		usage(argv[0], stderr);
		return 1;
	}

	/* determine the values of x & y from the command line */
	switch(mode)
	{
	case crack_long:
		xy = strtolli(argv[1]);
		/* calculate x & y from this long value */
		x = (int)((xy >> 32) & 0xffffffffLL);
		y = (int)(xy & 0xffffffffLL);
		/* correct x if (y < 0), see nextlong() */
		if(y < 0)
		{
			x += 1;
		}
		break;
	case crack_int:
		x = (int)strtolli(argv[1]);
		y = (int)strtolli(argv[2]);
		break;
	default:
		/* we should not be here */
		fprintf(stderr, "Unsupported mode!\n");
		return 1;
	}

	/* try to determine the interbal state of the RNG */
	if(crack(x, y) != (unsigned long long int)-1)
	{
		/* display next 8 values */
		for(i = 0; i < 8; i++)
		{
			switch(mode)
			{
			case crack_long:
				printf("%lld\n", nextlong());
				break;
			case crack_int:
				printf("%d\n", nextint());
				break;
			default:
				/* we should not be here */
				fprintf(stderr, "Unsupported mode!\n");
				return 1;
			}
		}
		/* success! */
		return 0;
	}

	return 1;
}

/* this is the Java implementation of next() */
/* nbits is the number of bits to output     */
int next(int nbits)
{
	unsigned long long int prev;

	do {
		prev = seed;
		seed = ((prev * 0x5deece66dULL) + 11ULL) & 0xffffffffffffULL;
	} while(seed == prev);

	return (int)(seed >> (48 - nbits));
}

int nextint()
{
	/* return the next integer (32 bits) */
	return next(32);
}

long long int nextlong()
{
	/* create a long value from two integer values */
	long long int ret;
	ret = (long long int)next(32);
	ret <<= 32;
	ret += (long long int)next(32);
	return ret;
}

unsigned long long int crack(unsigned int x, unsigned int y)
{
	int i;
	unsigned long long int seednew;

	/* try to determine the 48-bit seed                         */
	/* the first 32 most significant bits are already known (x) */
	for(i = 0; i <= 0xffff; i++)
	{
		seednew = ((unsigned long long int)x << 16) + i;
		seed = seednew;
		if((int)y == nextint())
		{
			/* the internal state is known, return */
			return seednew;
		}
	}

	/* failed! */
	return (unsigned long long int)-1;
}

/* converts a string to a long long int */
long long int strtolli(const char *ptr)
{
	int isnegative = 0;
	long long int ret = 0LL;

	if(ptr != NULL)
	{
		/* strip garbage characters */
		while(*ptr)
		{
			/* check if the value is negative */
			if(*ptr == '-')
			{
				isnegative = 1;
				ptr++;
				break;
			}
			if(*ptr >= '0' && *ptr <= '9')
			{
				break;
			}
			ptr++;
		}

		/* read the value from the string */
		while(*ptr)
		{
			if(*ptr >= '0' && *ptr <= '9')
			{
				ret *= 10LL;
				ret += (long long int)(*ptr - '0');
			}
			else
			{
				break;
			}
			ptr++;
		}
	}

	/* the string starts with a minus */
	if(isnegative)
	{
		ret *= -1LL;
	}

	return ret;
}

void usage(const char *name, FILE *out)
{
	fprintf(out, "Usage: %s long | int int\n", name);
}