Skip to content

Instantly share code, notes, and snippets.

@ykoster
Created June 4, 2019 06:40
Show Gist options
  • Save ykoster/d8f8df51f637d2a9ce392495d84207a9 to your computer and use it in GitHub Desktop.
Save ykoster/d8f8df51f637d2a9ce392495d84207a9 to your computer and use it in GitHub Desktop.
Mordan is a program that can be used to determine the internal state of the java.util.Random() random number generator
/* ---------------------------------------------------------------------
* 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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment