Flexlm: Recover LM_SEEDS based on encryption seeds

#1 03-01-2009, 17:27

Hi folks,

really nice forum here... much information...

Well I'm working on a simple attack on flexlm's CRO feature.
I know how to recover encryption seed 1 and 2 and that
the encryption seeds 1-4 are generated from LM_SEED1-3.

On CrackZ site there is an essay about a weakness in the early implementation
of generating the encryption seeds.

Well my Flexlm version is 11.4 and what i discovered so far is that
they changed the generation algo using the FIP186-2 RNG so there is no
known way to recover the LM_SEEDs from the encryption seeds.

My question is, does anyone of you tried a birthday attack on the generation
of the encryption seeds? Or any other attack?
It could really take a while recovering the correct LM_SEEDs because you
need around 2^48 different LM_SEED tries to find the the correct encryption seed.
I coded a small app which does exactly this, but I haven't had luck until now.

regards
tr1stan

dirkmill · #2 03-01-2009, 19:39

hi tr1stan,

i'm afraid your efforts regarding cro/trl are pointless.
if you have a look at the following code you will understand the problem:

Code:

l_genrand(job, lmseed1, lmseed2, lmseed3, NEWSEEDSIZ, newseeds);
for (i = 0;i < 4; i++){
   seed1 |= newseeds[i] << (i * 8);
   seed2 |= newseeds[i+4] << (i * 8);
   seed3 |= newseeds[i+8] << (i * 8);
   seed4 |= newseeds[i+12] << (i * 8);
   croseeds[0][0] |= (newseeds[i+16] << (i * 8));
   croseeds[0][1] |= (newseeds[i+20] << (i * 8));
   croseeds[0][2] |= (newseeds[i+24] << (i * 8));
};

the only knowledge accessible in a production build of an isv's flexlm binaries are seed1 and seed2 (usually called encseed[0]/[1] in the tuts) and some partial information about seed3/4 recoverable from lm_new.
l_genrand is based on certicom security-builder routines for the generation of random "newseeds" based on lmseed1/2/3 as prng-seeds. this function is costly and one-way.

also your estimation of the size of the keyspace in case of a birthday attack seems to be off by a huge amount. the size of returned data as can be seen above is way larger (28 bytes at least) than you expected, so a birthday attack is unlikely to be cheaper than a full brute-forcing of the input-space namely lmseed1/2/3.

sorry to crush your hopes

dirkmill

#3 03-01-2009, 21:00

dirkmill,

I think you're right if it comes to the complete result of certicom's security
builder which is 256bit long

My idea was to do a random guess on the three lm_seeds generating
the result (the 256bit output) and compare the first 64bit output with my
valid encryption_seed1 and 2.
The probabily that i then found the correct lm_seed1/2/3 is much higher.
And because all other seeds are derived from the lm_seeds I don't have to
worry about the 256bit output anymore.

If you want to have a fast crack you should patch the desired application

tr1stan

#4 03-03-2009, 16:12

I know someone have an idea to attack lm_seed1/2/3 ��but he said he need much more fast commputer ��at last he abandon��
Maybe��in the future we can do it��

#5 03-04-2009, 02:57

Hmm. It seems like it isn't that far-fetched to start an online distributed project to compute rainbow tables mapping outputs of l_genrand back to lmseeds.