Alternate Approach to FlexLM Brute-Force

[Windoze]

Hello,

I was looking through the old leaked FlexLM v9.2 source and had an idea...

What we want is LM_SEED1 - 3 but they are nowhere in the shipped files.
But we can get ENCRYPTION_SEED1 and ENCRYPTION_SEED2 from the target.
They are directly generated from the LM_SEEDS via a FIPS186 random generator.
The algorithm used in this RNG is SHA1. This should be much faster to brute force than the elliptic curve crypto.

Did anyone try this approach before? Do you think this is possible?

- Windoze

[Vladimir]

Yes, surely it seems be any approach to solve problem.

I had a similar project on my desk that uses Flexlm 11.x, I tried doing Brute-F but when I got the estimated time , the numbers were jaw dropping.

I had IDA sig along with til for major of Flexlm function(which i planned to release on exetools very soon if every thing goes well.)

[nathan]

Did you actually give it a try or it is just an high level idea so far ?

[nathan]

And may be this could be a good starting point https://forum.exetools.com/showthread.php?t=19605

[Windoze]

Originally Posted by nathan

Did you actually give it a try or it is just an high level idea so far ?

It's just an idea at the moment

[JohnDoe]

I think to bruteforce SHA-1 with 160bit key is a quite challenging task.
Despite successful theoretical attacks on the algorithm in practice, it will take a huge amount of time

[Rasmus]

Originally Posted by JohnDoe

I think to bruteforce SHA-1 with 160bit key is a quite challenging task.
Despite successful theoretical attacks on the algorithm in practice, it will take a huge amount of time

Yeah, not new news

[chants]

Do you know multiple hashes from the same key with different known plaintext?

E.g
Fixed text+salt1+password->sha1 hash1
Fixed text+salt2+password->sha1 hash2
...

Then a SAT solver starts to beat brute force and with enough salt and hash pairs starts to become practical.

I've wanted to do this exact idea on IDA7.2 since we have 2 decompiler installers with identical filename guids and almost surely same passwords. Sure a single hash is hard to break but it would be really interesting to know when this attack becomes practical. I dont think it's been researched much.
Just a thought as if there is a context where 80 or so input bit are unknown but dozens of pairs are available then brute force will take a century but a SAT solver would might take minutes. I say might because presumably the equations sharing input bits should reduce the search much more quickly. You dont need the whole 160 bit hash either. Probability wise you need around the same % as % input bits are unknown. Unknown input bits×160/512. Again I dont know as I need time for such research but sometime I might do this for publication even. It's too interesting not to try

[Windoze]

The algorithm used by FlexLM is as follows: (Pseudocode)

byte in1[32] = {0};
in1[0..3] = Seed1;
in1[4..7] = Seed2;
in1[8..11] = Seed3;
hash1 = SHA1(in1);

byte in2[64] = {0};
in2[0..19] = hash1;
hash2 = SHA1(in2);

if (hash2[0..3] == EncryptionSeed1 && hash2[4..7] == EncryptionSeed2) {
    Seeds found :)
}

So it is a double SHA1. Also since the second hash has 64 input-bytes you need 2 rounds. So it is 3 rounds of SHA1 in total for each try.

Also some of the Seed Values can be skipped, since FlexLM will not accept them.

l_reasonable_seed(unsigned int seed)
{
	if (!seed || 
		(seed == 1234567890) ||
		(seed == 123456789) ||
		(seed == 0x11223344) ||
		(seed == 0x00112233) ||
		(seed == 0x44556677) ||
		(seed == 0xdeadbeef) ||
		(seed == 0x12345678) ||
		(seed == 0x87654321) ||
		(seed == 0xabcdef01) ||
		(seed == 0x90abcdef) ||
		(seed == 0x01234567) ||
		(seed == 0x76543210) ||
		(seed >  0xfff00000) || /* small negative number */
		(seed <  0x00f00000) ) /* small number */
			return 0;
	return 1; /* success */
}

[FoxB]

from l_prikey.c :

/*
* l_genseed
* hardware dependent. Generate random seeds.
* Exits with error message to stderr upon error
*/
int
l_genseed( void)
{.....

explain about

if (hash2[0..3] == EncryptionSeed1 && hash2[4..7] == EncryptionSeed2) {
Seeds found