PDA

View Full Version : Bday Attack on Flexlm's ECC?


tr1stan
February 23rd, 2009, 08:14
Hello,

I'm playing with Flexlm 11.4 and the CRO feature for some time now and I'm
curious about how Flexlm generates the public and private key for the ECC.
What I found out yet is that it is based on the 3 encryption seed LM_SEED1-3.
So a question came to my mind, because I know LM_SEED1 and 2 from a
target but not LM_SEED3. So is it possible to reveal LM_SEED3 by doing a
birthday attack on the ECC implementation?
I think of doing the following:
1. generate 32bit random values and patch them into LM_CODE.H
2. compile lmcrypt.exe
3. sign a license with my version of lmcrypt
4. compare the result with original license file

Of course you need the vendor keys the cro keys and LM_SEED 1 and 2.
All this information can be revealed aside from LM_SEED3.
Is my assumption correct?
If yes, then it would normaly takes around 2^16 random guesses to find LM_SEED3
which is not really much even if you have to compile and sign a license in a loop.

RCER
February 26th, 2009, 00:57
tr1stan

your assumption is incorrect, The seeds which you can recover from your target are encryption seed 1 and 2, and these are diferent from LM_SEED 1 and 2

it seems that you need to do a little more homework

regards

tr1stan
February 26th, 2009, 15:41
hi rcer,

you're right. After digging a little bit more I found the way how Flexlm
generates encryption seed 1-4 based on LM_SEED1-3.
They use LM_SEED1-3 as input to the FIPS186-2 RNG which generates
a 256 bit random value and from this output they use the first 128 bit
as the encryption seed.
As Crackz meantioned it in one of his tutorials you would need 2^96
brute force rounds to find the correct LM_SEEDs. But it is still possible
to do a birthday attack on these seeds with around 2^48 rounds.
I'm working on such a tool which looks promising so far.

Any ideas are welcome of course

regards
tr1stan

zhide1983
March 5th, 2009, 03:35
Do you have a concept about 2^96?

dongs
March 5th, 2009, 06:40
A birthday attack is meant to be used to find collisions; what you intend to do is find a preimage --- that should take about 2^(96-1) time.

On a sidenote, doesn't FlexLM check for very large and very small values for each seed? I seem to remember only 24 bits were allowed, rendering it 2^72 instead.

zhide1983
March 5th, 2009, 12:00
Do you mean the lmseed.dat generated by lmseed?
Can vendor use their own 96 bit seeds?

tr1stan
March 5th, 2009, 13:15
@dongs: well i try to find a seed triple (with random guesses) which produce the same output as the original lm_seeds. It can be collision, even this is not
realistic because the input is less than the output of the CSPRNG but anyway.
You're right that Flexlm filters the lm_seeds. Only seeds between 0x00F00000-0xFFF00000 are allowed.

@zhide1983: the vendor can choose the seeds or calculate it's own by using lmrand1.exe which comes with the SDK.

Btw: using the Certicom's security builder for generating the encryption_seeds is really fast, so doing a some kind of a brute forcer is quite fast.