A Detailed Look at Crypt Filters
Describes how crypt filters are implemented and cracked using standard tools
 

21-Nov-2000

by Nolan Blender

This essay explains how crypt filters work.

Rating

( )Beginner ( )Intermediate (X)Advanced ( )Expert

This essay covers the mostly undocumented crypt filter option, and describes how to produce keygens for products that implement this added protection of FLEXlm.


A Detailed Look at Crypt Filters
Describes how crypt filters are implemented and cracked using standard tools
Written by Nolan Blender

Introduction

This essay describes the theory, operation, and cracking of the FLEXlm user crypt filter code. I am going to provide the information on how this protection works, how it is is generally implemented, and how this added protection can be cracked.

Tools required

FLEXlm 6.1 SDK for Windows, Microsoft Visual C++ 6.0, Numega SoftICE 4.05, IDA 4.14, The FLEXlm 6.1f signatures for IDA, mksym.bat, symfix.idc, UltraEdit32.

Target's URL/FTP

http://www.globetrotter.com - this is an essay without a specific target other than the demonstration "blenderd" program.

Program History

Globetrotter's FLEXlm has a history of continuous improvement. The first implementation was highly insecure and didn't even hide the encryption seeds. Later versions used the vendorcode5 xor trick. Other versions used the lm_new method of hiding the seeds (described in other essays). The crypt filters provide a reasonably strong defense against cracking - they are even immune to the memory sniffing techniques that many crackers employ.

Essay

For this essay I am going to use the FLEXlm 6.1 SDK, although the principle is the same for later versions (to 7.0d at least) of the FLEXlm toolkit.

What are crypt filters?

Crypt filters are an added protection mechanism that can be implemented in FLEXlm protected applications. Programs that use this protection have to use the FLEXible API, and some additional programming knowledge is required. Standard FLEXlm keys rely only on the values of the encryption seeds which are defined in lm_code.h. Once these seed values are discovered, FLEXlm keys can be made for products for which the seeds are known. Crypt filters add an additional encryption to the key so that simply knowing the encryption seeds is no longer sufficient to generate valid keys.

Implementation

The implementation of user crypt filters requires making the relevant filter programs, then modifying the keygen, daemon, and runtime executables so that they utilize this additional code. There are two additional modules; one for the generator program, and one that is linked against the shippable executable. The module that is linked against shippable (that is, ones that will go to the end customer) is special in that it requires the correct result value as input so that it is not possible to search for memory echoes of the correct key value. I will explain this in depth later.

The first step is to create the Filter Generator files. For this example, I created a directory "filter_gen" in the i86_n3 dir to hold the new source files. The seeds I used were 1471 2134 4211. I am providing this information so you can follow along, but normally you would not have access to this information.

D:\blenderd\i86_n3\filter_gen>../lmrand1 -filter_gen 1471 2134 4211
** Filter-Generator: Additional security -- not needed by most companies **

This generates 2 source files, which you must *never edit*:
lmappfil.c: must be linked into vendor daemon, and all applications
            calling lc_checkout().  These applications must call
                lc_set_attr(lm_job, LM_A_USER_CRYPT_FILTER,
                                        (LM_A_VAL_TYPE)user_crypt_filter);
            after lc_new_job().  Also, lsvendor.c must have
                extern void user_crypt_filter();
                void (*ls_a_user_crypt_filter)() = user_crypt_filter;

lmkeyfil.c: this must be linked into all license generators:
            makekey, lmcrypt, programs that call lc_cryptstr().
            In these programs, after lc_init(), call
                lc_set_attr(lm_job, LM_A_USER_CRYPT_FILTER_GEN,
                                (LM_A_VAL_TYPE)user_crypt_filter_gen);

The seeds you picked are (in hex) : 0x5bf 0x856 0x1073. Make sure that you save these seeds somewhere safe. You can recreate these files by re-running this program with the same seeds. (Use -q in the future to skip this message). At this point, we have two C files conveniently generated by lmrand1.exe - lmappfil.c and lmkeyfil.c. lmappfil.c contains the code which will be linked against the shipping applications, and lmkeyfil contains the code that will be linked against the keygens, and not shipped to customers. lmappfil.c contains special anti-cracking code that prevents memory echo sniffing, where lmkeyfil.c contains the filter algorithm only.

The next step is to copy these files to the machind directory. After this, the makefile in the i86_n3 directory (or whatever platform you're building for) must be modified to include rules for the new files. I added these lines for the object files in makefile :-

lmappfil.obj : ..\machind\lmappfil.c ..\machind\lmclient.h
        $(CC) $(CFLAGS) $(INCS) /c ..\machind\lmappfil.c

lmkeyfil.obj : ..\machind\lmkeyfil.c ..\machind\lmclient.h
        $(CC) $(CFLAGS) $(INCS) /c ..\machind\lmkeyfil.c

For this exercise, I've only modified lmcrypt.exe (the key generator) blenderd.exe (the daemon) and lmflex.exe (the client). User filters are only applicable to the FLEXible interface. Now that the build rules for the filter objects have been added, we'll approach the license generator first. First, we'll change the build rules so that lmcrypt.exe is linked with lmkeyfil.obj :-

lmcrypt.exe : lmcrypt.obj lmkeyfil.obj
        $(LD) $(LFLAGS) /out:$*.exe lmcrypt.obj lmkeyfil.obj \
                $(LIBS) $(CLIBS)

Linking against the new object is not sufficient to get the keygen to work though. We have to add a call to lc_set_attr so that FLEXlm knows to use this filter. First, add a prototype to lmcrypt.c :-

extern void user_crypt_filter_gen();

Then after the call to lc_init() :-

 	lc_set_attr(lm_job, LM_A_USER_CRYPT_FILTER_GEN,
	 (LM_A_VAL_TYPE) user_crypt_filter_gen);

This tells FLEXlm to use our crypt filter when generating keys. The client must be similarly modified to link against lmappfil.obj.
In makefile :-

lmflex.exe : lmflex.obj lm_new.obj lmappfil.obj
        $(LD) $(LFLAGS) /out:$*.exe lmflex.obj lm_new.obj lmappfil.obj \
                $(LIBS) $(CLIBS)

In lmflex.c we have to do similar things to what we did in the keygen so the client uses the filter as well. This prototype must be added :-

extern void user_crypt_filter();

and after lc_new_job() :-

lc_set_attr(lm_job, LM_A_USER_CRYPT_FILTER, user_crypt_filter);

Now we can test the new filter with an uncounted license - first put this in license.dat :-

FEATURE f1 blenderd 1.0 permanent uncounted 0 HOSTID=ANY ck=0

then run lmcrypt license.dat. If LM_LICENSE_FILE is set to the license.dat file, we should be able to check out feature f1.

Modifying the daemon. The makefile must be modified to include lmappfil.obj in the daemon first.

blenderd.exe :  lmrand1.exe lsvendor.obj  lmappfil.obj
        $(LD) $(LFLAGS) /out:$*.exe lsvendor.obj lm_new.obj lmappfil.obj \
                 $(DAEMON_LIBS) $(CLIBS)

In lsvendor.c :-

extern void user_crypt_filter();

and later :-

void (*ls_a_user_crypt_filter)() = user_crypt_filter;

This makes the vendor daemon use the crypt filter. Understanding what the lmappfil and lmkeyfil really do. The first program we'll examine is lmappfil.

Although the code is written to be non-obvious about what is happening, a careful examination of the code reveals what is really happening. The input value (inchar) is first xored with a value, then the bits permuted. If this value is the same as ec (which I suspect stands for "expected code") that value is returned. If a bit is encountered which is different from the expected code, then the value is immediately xored with some junk value then returned. Since the "expected code" is one from the key, it's not easy to figure out from tracing what the expected code should be.

A careful examination of the program reveals that there's really 20 different xor/permutation operations. Variables identified by "num" (for example, num0, num1, num2) are used to test the input value "idx" or the index into the xor/permute table. Values identified by "bit" are really masks for bit operations - although these are stored as 16 bit values, this is only done to confuse the issue since only the lower 8 bits are used, since the character being tested "c" is an 8 bit value.

So effectively :-

bit0 = 0x01
bit1 = 0x02
bit2 = 0x04
bit3 = 0x08
bit4 = 0x10
bit5 = 0x20
bit6 = 0x40
bit7 = 0x80

Let's look at the first part of the permutation check :-

	if (idx == num4)
	{
		if (in_c & bit1)	c |= bit0;
		if ((c & bit0) != (expchar & bit0)) { *inchar ^= 0x74; return;}
	}

c was initially 0, so here we can see that the program is mapping the value at bit 1 in in_c to bit0 in expchar, which is really ec & 0xff. What this means is that ec is being checked one bit at a time for correctness, and if there's a bad bit, junk is returned. Since the expected char is really successive bytes in the license key, the correct sequence will not show up in memory unless a correct key was supplied initially. It's still possible to attack this type of filtering though.

Attacking the daemon

At this point, we'll assume that we don't know the specific values used for the filter/encryption seeds, and have to derive them ourselves. Now that we've ascertained what is basically happening in the algorithm, we can now more effectively reverse the program. In this case, we'll attack the vendor daemon blenderd.exe, since usually the daemon is supplied, and there's usually
less additional code to decompile than in the applications.

First, the daemon was disassembled using IDA 4.14, then the FLEXlm 6.1f signature was applied. symfix.idc was then applied to rename the internal functions. A map was then created, and mksym (which really calls the SoftICE utils msym and nmsym) was used to generate the .nms file. The first task is to locate the encryption seeds, a process which has been documented before in Dan's essay, and an earlier essay of mine. l_sg is first located, and the call to the lm_new routine located - this is a call to pointer.

00406486  push    [ebp+arg_8]
00406489  push    [ebp+arg_4]
0040648C  push    ecx
0040648D  call    eax
0040648F  add     esp, 0Ch

The call is at 40648D - at that point we'll overwrite the job ptr on the stack with a zero, step over the call, and examine the data in the third argument to recover the real encryption seeds. A license with a valid structure is first created so the program will call the decrypting routine for the encryption seeds.

SERVER this_host ANY
VENDOR blenderd
FEATURE f2 blenderd 1.0 permanent 20 123456789ABC ck=0

The symbol table is then loaded in using the SoftICE symbol loader, then the EXE loaded in. A breakpoint is then set at 40648D. The program is then run with arguments that will cause it to try to check out that license.

blenderd -t 6.1 3 -c license.dat

At the breakpoint, the value at esp is set to 0, and then the address at esp+8 is examined, and the call stepped over. You should now have the encryption seeds. The next step is to find where the crypt filter really resides in the program. Since it's unique for each vendor, it's not going to have a signature in the file. How can we identify it then?.

Well, for one thing, there must be a call to lc_set_attr telling FLEXlm where this routine resides. Let's set a breakpoint in lc_set_attr, and watch the calls to this routine. By looking at our IDA disassembly we can locate _lc_set_attr at 0x404374 and set a breakpoint in SoftICE. If we do this, we see that the crypt filter is located at 4019ec since we see lc_set_attr called with a second argument of 0x4a (LM_A_USER_CRYPT_FILTER) and that value.

Now we can examine that routine and disassemble in earnest. Using IDA, we go to that location, and can see immediately that it's not yet considered to be a function. This is because there were no "call" references to this address and IDA has no reason to consider it a seperate function. By pressing "p" with the pointer at this address, we can convert it to a function.

The next step is to change the stack variable names - we know what the arguments to this function are so let's name them appropriately - arg_4 becomes inchar, arg_8 becomes idx, arg_c becomes ec. The job structure (arg_0) isn't used anywhere, so it wasn't converted into a stack variable - we won't bother because we don't care about variables that aren't used.

We can then step through the listing, and rename variables, since we know their values and equivalent names in the original code. Ones that were num0-19 are easy. The x_0 to x_19 variables were renamed to include the hex values, so less
back and forth work would be needed when deriving the xor table. This is a typical entry - in this case, the value for idx13 is xored with 0x37 :-

00401A15 loc_401A15:               ; CODE XREF: sub_4019EC+1Ej
00401A15   cmp     esi, num13
00401A1B   jnz     short loc_401A26
00401A1D   xor     dl, myval_37
00401A23   mov     [ebp+var_2], dl

After doing a bit of work, we can see how the disassembly will relate to the original source.

00401B5C loc_401B5C:               ; CODE XREF: sub_4019EC+165j
00401B5C   cmp     esi, ecx        ; ecx is num4
00401B5E   mov     ecx, bit0
00401B64   jnz     short loc_401B86 ; Skip over this if not num4
00401B66   test    byte ptr bit1, dl ; Check bit 1
00401B6C   jz      short loc_401B71
00401B6E   mov     [ebp+var_1], cl ; char c
00401B71 
00401B71 loc_401B71:               ; CODE XREF: sub_4019EC+180j
00401B71   mov     dl, [ebp+ec]
00401B74   mov     bl, [ebp+var_1] ; char c
00401B77   and     edx, ecx
00401B79   and     ebx, ecx
00401B7B   cmp     bl, dl
00401B7D   jz      short loc_401B86 ; Check to see if that bit is the same on both ec and the 
                                    ; derived char
00401B7F 
00401B7F loc_401B7F:               ; CODE XREF: sub_4019EC+8A1j
00401B7F   xor     al, 74h         ; Fill with crud if no good
00401B81   jmp     loc_403C6F      ; Then bail out

It's clear by looking at this that we can figure out what input bits are mapped to what output bits for what index. Here, the check is done against num4, so it must be for index 4. The test is done against bit 1, and the bit anding operation is done against bit0 (it was stored in ecx earlier). This means that the permutation will move the bit in location 1 to location 0. By examining the entire subroutine, the table can be fully recovered. Once we have the tables, we can write an equivalent filter for the key generator. If you have followed this exercise and have the lmkeyfil.c program, you'll see that the behavior of the
routine below is identical to that of lmkeyfil.c.

In the following program, the actual algorithm is implemented for blenderd :-

#include <lmclient.h>;
typedef struct permute_s
{
	int shiftvals[8];
} permute_t;

int xorvals[]=
{
	0x14, 0x39, 0x38, 0x11,
	0x32, 0x32, 0x33, 0x1d,
	0x3e, 0x20, 0x18, 0x39,
	0x19, 0x37, 0x09, 0x1b,
	0x16, 0x15, 0x2e, 0x1a
};
	
permute_t tab1[] = {
        {4,5,7,1,2,6,0,3}, /* idx 00 */
        {0,6,5,1,4,3,2,7}, /* idx 01 */
        {5,3,7,0,6,1,2,4}, /* idx 02 */
        {3,6,1,5,0,4,2,7}, /* idx 03 */
        {4,0,6,1,7,5,3,2}, /* idx 04 */
        {1,7,2,4,0,3,5,6}, /* idx 05 */
        {3,7,0,6,4,2,5,1}, /* idx 06 */
        {3,6,5,1,4,2,7,0}, /* idx 07 */
        {6,4,5,7,0,3,1,2}, /* idx 08 */
        {7,5,2,3,4,0,1,6}, /* idx 09 */
        {6,1,3,2,4,0,5,7}, /* idx 10 */
        {1,2,4,7,3,0,5,6}, /* idx 11 */
        {0,2,7,6,1,5,3,4}, /* idx 12 */
        {5,0,4,7,6,2,3,1}, /* idx 13 */
        {7,6,4,5,2,0,3,1}, /* idx 14 */
        {5,2,4,7,1,3,0,6}, /* idx 15 */
        {0,4,3,5,7,1,2,6}, /* idx 16 */
        {3,7,0,1,2,6,4,5}, /* idx 17 */
        {2,3,7,1,4,6,0,5}, /* idx 18 */
        {7,5,1,3,6,2,0,4}  /* idx 19 */
};
/*-------------------------------------------------------------*
 * user_crypt_filter_gen
 *-------------------------------------------------------------*/
int user_crypt_filter_gen(job, inchar, idx)
LM_HANDLE *job;
char *inchar;
int idx;
{
	char tmpchr;
	char outchr;
	/* Initial XOR transform */
	tmpchr = *inchar ^ xorvals[idx];
	/* Final permutation */
	permute(&tmpchr, tab1[idx].shiftvals, &outchr);
	*inchar = outchr;
	return(0);
}
/*-------------------------------------------------------------*
 *
 * permute: permute the bits in inchar to outchar using the bit
 * order in shiftvals
 *-------------------------------------------------------------*/
int permute(char *inchar, int *shiftvals, char *outchar)
{
	int outval = 0;
	int i;
	int shbit; /* Test bit */
	shbit = 1;
	for (i = 0; i < 8; i++)
	{
		if (*inchar & shbit)
		{
			outval |= (1<<(shiftvals[i]));
		}
		shbit = shbit<<1;
	}
	*outchar = (char) (outval & 0xff);
	return(0);
}

This is the contents of mksym.bat :-

"c:\program files\numega\softicent\util16\msym" %1.map
"c:\program files\numega\softicent\nmsym" %1.sym

This is the contents of symfix.idc :-

#include <idc.idc>;
static main()
{
    auto ea, old_name, old_cmt, sav_cmt;
    auto errcode;
    sav_cmt = "NOSUCHFUNCT";
    ea = SegStart( ScreenEA() );
    while (ea != BADADDR) {
        old_cmt = GetFunctionCmt( ea,1);
        if (strlen(old_cmt) > 1)
        {
            if (old_cmt != sav_cmt)
            {
    	    	Message ( atoa(ea)+"   "+old_cmt );
   	    	Message ("\n");
   	    	errcode = MakeName(ea, old_cmt);
   	    	if (errcode == 0)
   	    	{
   	    		errcode = MakeName(ea, "alt"+old_cmt);
   	    	}
    	    	if (errcode == 0)
    	    	{
   	    		errcode = MakeName(ea, "alt1"+old_cmt);
  	    	}
   	    	sav_cmt = old_cmt;
   	    }
       	}
        ea = NextAddr(ea);
    }
    Message("Done.\n");
}

Final Notes

Although this protection is vastly improved by adding crypt filters, it can still be defeated by careful analysis and emulation of the behavior of the routines in question. Since the lmkeyfil routine is not supplied to the end user, cracking must be accomplished by understanding what is going on in the program.

Ob Duh

I won't even bother explaining to you that this is a FLEXlm essay by Nolan Blender and that you won't find any application to steal here.