Delphi RNG reversing [Archive] - RCE Messageboard's Regroupment

View Full Version : Delphi RNG reversing

LaptoniC

October 10th, 2011, 08:13

Hi,
I am trying to reverse a program which uses RSA-512. I checked how this program generated its keys and found out that it uses component. This component creates the key like this.

Code:

MakeRandom proc uses esi ebx szOutWORD, szLen 

	mov esi,szOut

	mov ebx,szLen

    

@loop:    

    mov     eax, 0DFh

	call    Random ; System::Random(int)

	add     al, 20h

	mov     [esi], al

	inc     esi

	dec  ebx

	jnz      @loop

	ret

MakeRandom endp



Random proc

	xor     ecx, ecx

	imul    edx, RandSeed[ecx], 8088405h

	inc     edx

	mov     RandSeed[ecx], edx

	mul     edx

	mov     eax, edx

	ret

Random endp

Random function is standard delphi random function. RandSeed is calculated by using QueryPerformanceCounter.
After we get the random string, we search the next prime number by using Rabin-Miller algorithm by doing 4 iterations.

Code:

invoke MakeRandom,addr szKey1,20h

invoke MakeRandom,addr szKey2,20h

There is no randomization function between each key so if we find the seed we can recover both keys at the same time.
So key space is actually FFFFFFFFh however again this is something takes very long time due to big number calculations. I am using drizz's big number library.

So, I am not so good about cryptography. Is there any kind of optimizations that will help me to decrease the time for key search. For now searching 1000 seeds take around 1 minute 6 seconds.
I will appreciate any optimizations and opinions. Thanks.

drizz

October 11th, 2011, 08:53

Hi,

Quote:

[Originally Posted by LaptoniC;91199]After we get the random string, we search the next prime number by using Rabin-Miller algorithm by doing 4 iterations.

Rabin-Miller is too expensive to be solely used to determine if a number is probable prime. If you look at bnIsPrime my testing is divided into:
1) test if number is odd
2) test if it's dividable by small primes
3) use fermats little theorem for first few prime numbers
4) use rabin-miller

You could do [1] and [2](one part) directly without any conversion to bn format

for example:

Code:

	lea edi,szKey1

	test byte ptr [edi],1; if LSB is not at [edi][0] use  [edi][15]

	jz @NOTPRIME

	; calc digit sum

	xor ebx,ebx

	mov ecx,16; 512/32

	xor eax,eax

	.repeat

		adc ebx,[edi][ecx*4-4]

		dec ecx

	.until zero?

	adc ebx,eax

	; div 3

	mov eax,ebx

	mov edx,0AAAAAAABh

	mul edx

	shr edx,1

	mov eax,ebx

	; edx*3

	lea edx,[edx*2+edx]

	;

	sub eax,edx

	jz @NOTPRIME

	; div 5

	mov eax,ebx

	mov edx,0CCCCCCCDh

	mul edx

	shr edx,2

	mov eax,ebx

	; edx*5

	lea edx,[edx*4+edx]

	;

	sub eax,edx

	jz @NOTPRIME

You may be wondering what this is, as I myself have NOT seen similar testing in any other library.
This is your schoolboy divisibility rules applied to big numbers
If Digit sum is divisible by 3 then the whole number is divisible by 3 (base 2^32).

Code:

	2^32 = 0 (mod 2)  first digit

	2^32 = 1 (mod 3)  sum of digits

	2^32 = 1 (mod 5)  sum of digits

So the best way to speed up prime searching would be to do these tests in parallel:
test if odd szKey1
test if odd szKey2
simplified divisibility test(from above) szKey1
simplified divisibility test(from above) szKey2
;-- now convert both to bn
divisibility test szKey1
divisibility test szKey2
fermat test szKey1
fermat test szKey2
rm test szKey1
rm test szKey2
;-- arrive here if all tests passed

HTH,
drizz

tofu-sensei

October 11th, 2011, 09:32

this reminds me of the asprotect blunder back in the days

maybe you can further reduce the key space, depending on how exactly randseed is initialized.

LaptoniC

October 11th, 2011, 10:05

@drizz,
Thanks for the help. What can you suggest me? Should I use bnIsPrime function or the code you posted. Let me tell again the number I check is 32 digits .I use

Code:

invoke bnFromBytesEx,addr szKey1,20h,_P,0

should I change any thing in the code you posted?
I used Rabin-Miller with 4 iterations because the component uses so. Besides prime number search can you suggest any optimizations especially for seed searching? I think I shouldn't check for szKey2 because if I find Key1 I can easily recover Key2. Key2 depends on the seed which is used by making Key1.

@tofu-sensei
The problem is RNG seed is taken from QueryPerformanceCounter. This function doesn't return any predictable value afaik. By comparing the values of this function we can get very precise timers. This component initializes seed by using this function. The sample program randomize two times. I don't know maybe if we approximate the the time we can recover the part of seed? However I don't know maybe the programmer generated key several times.

Here is my complete code

Code:



		invoke bnInit,512

		bnCreateX _P,_Q,_N,_E,_two,bnRem

		invoke bnMovzx,_E,10001h

		invoke bnMovzx,_two,2

		invoke bnFromHex,addr szOrgKey, _N



;Just Make P and find nearest prime

; Then if N mod P = 0 we found the key

; if not change the seed and try another prime

 		

@myloop:		

		invoke MakeRandom,addr szKey1,20h

		;invoke MakeRandom,addr szKey2,20h ; Q not needed now

		

		invoke bnFromBytesEx,addr szKey1,20h,_P,0

		

		

		

		invoke bnMod, _P, _two,bnRem

		mov eax,bnRem

		mov ecx,(BN PTR [eax]).dwArray

		test ecx,ecx

		jnz @F

		invoke bnInc,_P

@@:

		invoke bnAdd, _P,_two ;p=p+2

		invoke bnRabinMillerpt,_P,4

		test eax,eax

		jz @B 

; we have a prime number!!! 

	

		invoke bnMod, _N, _P,bnRem

		mov eax,bnRem

		mov ecx,(BN PTR [eax]).dwArray

		test ecx,ecx

		jz @found

		;inc counter

		dec counter

		jz @found

		push counter

		pop  RandSeed

		jmp @myloop

		

		





@found:			

		invoke bnToHex,_P,addr bnint

drizz

October 11th, 2011, 12:22

oops, I've just noticed a little bug with bnIsPrime (returns bn handle if number is even - so make sure it isn't)

btw, is p=szKey1 and q=szKey2? If so you don't need to search for both (you have N)

1:
set randseed
szkey=makerandom
p=bn(szkey)
p=search next prime p
if isprime(n/p) then done else goto 1

edit:
If p and q are 512 then this is RSA-1024.

Code:

	xor ebx,ebx

	

	.while 1

		mov RandSeed,ebx

		inc ebx

		

		KEYLEN equ 20h

		invoke MakeRandom,addr szKey1,KEYLEN

		invoke bnFromBytesEx,addr szKey1,KEYLEN,p,0



		mov eax,p

		.if BN_IS_EVEN(eax)

			invoke bnInc,eax

		.endif

		

		.while 1

			mov eax,p

			invoke bnIsPrime,eax

			.break .if eax

			invoke bnAddDw,p,2

		.endw

		

		invoke bnDiv,n,p,quo,rem

		

		mov eax,rem

		.continue .if !BN_IS_ZERO(eax)



		mov eax,quo

		.if BN_IS_ODD(eax)

			invoke bnIsPrime,eax

			.if eax

				;;;; BINGO!

				invoke printbn,quo

				.break

			.endif

		.endif

		

	.endw

LaptoniC

October 11th, 2011, 14:22

Thanks again for the reply.

yes p=szKey1 and q=szKey2. That is why I don't need to search for szKey2(q)

Quote:

set randseed
szkey=makerandom
p=bn(szkey)
p=search next prime p
if isprime(n/p) then done else goto 1

So according to this code, dividing is faster than mod ? Because if the mod returns 0 it means p is the KEY. No need to check quo whether it is prime or not. we can recover q by using MakeRandom function and seed we have.

I think what we have is RSA-512 because N is 511 bits which is 154 digits in base10 and 128 digits in base 16. However I am not so good about crypto what you say can be right

drizz

October 11th, 2011, 16:20

Quote:

[Originally Posted by LaptoniC;91209]So according to this code, dividing is faster than mod ?

If you look at the source, both procs use binary long division, bnMod has some stuff omitted but not much of a performance gain. And I wrote it in a hurry see reason below

Quote:

[Originally Posted by LaptoniC;91209]I think what we have is RSA-512 because N is 511 bits which is 154 digits in base10 and 128 digits in base 16. However I am not so good about crypto what you say can be right

Sorry, I made a mistake while editing the post to respond to your edit and I was in a hurry to watch football (euro2012 qual

). p an q are 256bit.

LaptoniC

October 11th, 2011, 22:54

Thanks drizz for the comments I will try your code and let you know.

PS: Last night I was also watching football match Turkey vs Azerbaijan

drizz

October 12th, 2011, 12:19

Quote:

[Originally Posted by LaptoniC;91207]Besides prime number search can you suggest any optimizations especially for seed searching?

Make the code multithreaded (threads = cores; or threads = 2*cores with HT), have each thread work on a different range of randseeds. Preferably make the program read range settings from a file / store settings on exit. Run it on multiple computers

dzioba-2

October 13th, 2011, 04:42

This discussion has caught my attention, I want to say a few words on the rand seed generation and the QueryPerformance* functions.

QueryPerformanceCounter() returns a 64 bit word containing number of clock cycles since boot. They did not make an extreme blunder and use the high dword of this value, did they?

That would be too lucky, i guess.

QueryPerformanceFrequency() gives the frequency of the before mentioned counter. Now it would be interesting to find out exactly what is the underlying hw clock used for this. On very many systems this functions is returning 3579545 = ~3.5MHz, clearly not the cpu clock rate. However, on some machines it is the actual cpu rate, e.g. resulting in a 2.8GHz value.

Lets make some assumptions on how the rand seed value initialization behaves if we got a usual case of 3579545 clock rate.
2^32 / 3579545 = 1200 seconds = 20 minutes, so it is a good randomization source for such a simple rng. There is no way at all to guess the initialization value based on system up time, since the lo dword spins around each 20 minutes! Now, if Delphi rng was using the hi dword to init, it would be much prettier, wouldn't it

This is off topic, but does anyone know where this frequency number come from? Is it a direct value from some hw clock, or does it come with a divider applied and whats the reason why some systems in fact run at the actual cpu rate?

tofu-sensei

October 13th, 2011, 05:52

Quote:

[Originally Posted by dzioba-2;91216]QueryPerformanceCounter() returns a 64 bit word containing number of clock cycles since boot. They did not make an extreme blunder and use the high dword of this value, did they?

i checked out of curiosity, only the low dword is used.

LaptoniC

October 15th, 2011, 01:54

I am trying your code but I have a problem

If RandSeed is 0 RandomBytes are

Code:

2026E04D5CB56744737E32892FDB2D61EC72CC69BBDCC06444698757D85E8B41

This is a odd number. However your code

Code:

		invoke bnFromBytesEx,addr szKey1,KEYLEN,_P,0

		mov eax,_P

		.if BN_IS_EVEN(eax)

			invoke bnInc,eax

		.endif

which translates to this

Code:

TEST DWORD PTR DS:[EAX+8],1

JE SHORT DialogAs.00401248

PUSH EAX                                ; /Arg1 => 034C07E0

CALL DialogAs.004015F0                  ; \DialogAs.004015F0

Makes the number even although the number was odd. I don't know the reason of this maybe it is a bug in your code or how the masm compiles the code. I changed the macro and converted code to

Code:

		test dword ptr [eax+8],1

		jnz @F		

		invoke bnInc,eax



@@:

PS: Could you write a sample code about the optimization you talked above to use multiple cores.Thanks.

drizz

October 16th, 2011, 15:23

Quote:

[Originally Posted by LaptoniC;91221]Makes the number even although the number was odd. I don't know the reason of this maybe it is a bug in your code or how the masm compiles the code.

Yes, it seems jwasm produces different code than masm. Probably because ! is an escape operator when used in text items....

Quote:

[Originally Posted by LaptoniC;91221]PS: Could you write a sample code about the optimization you talked above to use multiple cores.Thanks.

It's nothing special, just this code wrapped in a proc upon which you create multiple threads with different input parameters.

Code:

;; NOTE: WRITTEN WITHOUT COMPILING, EXECUTING and TESTING!

RANGEPARAMS struct

	RStart dd ?

	REnd dd ?

	RPos dd ?

           RSeed dd ?

RANGEPARAMS ends



KEYLEN equ 20h



ThreadProc proc uses esi edi ebx lpParamtr RANGEPARAMS

	local szKey[KEYLEN]:BYTE

	local RandSeed1WORD



	mov esi,lpParam

	assume esitr RANGEPARAMS

	mov ebx,[esi].RStart

	.while ebx < [esi].REnd

@NextSeed:	

		mov [esi].RPos,ebx

		inc ebx

		

		;invoke MakeRandom,addr szKey1,KEYLEN

		; modified so that reversing byte order is not needed 

		

		;MakeRandom proc uses esi szOut, szLen 

		lea edi,szKey

		mov ecx,KEYLEN

		push [esi].RPos

		pop RandSeed1

	@loop:    

		mov     eax, 0DFh

		imul    edx, RandSeed1, 8088405h

		inc     edx

		mov    RandSeed1, edx

		mul     edx

		;call    Random1 ; System::Random(int)

		add     dl, 20h

		dec     ecx

		mov     [edi+ecx], dl

		jnz     @loop



		; Make odd

		or byte ptr [edi],1

		

		; CHECK IF THIS IS DONE IN THE COMPONENT!

		; THIS IS A REQUIREMENT FOR RSA PRIMES!

		;or byte ptr [edi+KEYLEN-1],80h

		

		jmp @Sum



@Next:	

		; Add 2

		xor eax,eax

		add [edi][0*4],dword ptr 2

		adc [edi][1*4],eax

		adc [edi][2*4],eax

		adc [edi][3*4],eax

		adc [edi][4*4],eax

		adc [edi][5*4],eax

		adc [edi][6*4],eax

		adc [edi][7*4],eax

		

		; overflow test

		jc @NextSeed

		

@Sum:	

		; Digit sum

		mov ecx,[edi][0*4]

		add ecx,[edi][1*4]

		adc ecx,[edi][2*4]

		adc ecx,[edi][3*4]

		adc ecx,[edi][4*4]

		adc ecx,[edi][5*4]

		adc ecx,[edi][6*4]

		adc ecx,[edi][7*4]

		adc ecx,0

		; div 3

		mov eax,0AAAAAAABh

		mul ecx

		shr edx,1

		; edx*3

		lea edx,[edx*2+edx]

		sub edx,ecx

		jz @Next

		; div 5

		mov eax,0CCCCCCCDh

		mul ecx

		shr edx,2

		; edx*5

		lea edx,[edx*4+edx]

		sub edx,ecx

		jz @Next



		invoke bnFromBytes,addr szKey,KEYLEN,p,0

		

		invoke bnIsPrime,p

		test eax,eax

		jz @Next



		invoke bnMod,n,p,rem

		

		mov eax,rem

		.continue .if !BN_IS_ZERO(eax)



		invoke bnDiv,n,p,quo,0

		; BINGO!

		invoke printbn,quo

				



		.break

		

	.endw

Some portions of bnIsPrime are very slow...
The library is also in a need of revision/rewrite (x64 :-) )...

LaptoniC

October 18th, 2011, 07:32

Thanks drizz for the ideas and code. I tested your code and seems it didn't make much difference. As you pointed out most of the time is spent on IsPrime function. I hope you can find time and motivation to update your library

FrankRizzo

October 18th, 2011, 21:06

One of the things that I ALWAYS do when faced with something like this, is to google any weird constants that they use in the code. In this case, 8088405h, and it returned this:

http://ideone.com/W6Lq9QR6

Which states that they use the QueryPerformanceCounters value as a RANGE. If that's the case, then your keyspace just dropped dramatically.

LaptoniC

October 19th, 2011, 02:27

As I said in earlier post this program uses QueryPerformanceCounter for initial seed. However I didn't get what you mean by

Quote:

If that's the case, then your keyspace just dropped dramatically.

How we can predict the result of QueryPerformanceCounter? Could you elaborate on this topic?

FrankRizzo

October 19th, 2011, 09:22

What I was saying was that if they use the value of Query... for range limiting the acceptable values, and that value is LOW, then that limits the range of the random numbers, and might reduce the area you have to search.

LaptoniC

October 19th, 2011, 10:08

I want to know what is predictable the range of QueryPerformanceCounter if you know. I didn't come up with any predictable range. That is why I am searching 0-FFFFFFFFh range. Another problem is we also don't know how many times author generated big number. Each generation also affects RandomSeed. However, I am open to new ideas always.

ShyKittten

February 7th, 2012, 18:31

Why do you search the next prime number ?

prime(M) + b = M with M the 1st random number and b a small number
prime(N) + c = N with N the 2nd random number and c a small number

So :
- choose a seed
- compute M and N
- if (M*N - P) is small enough, you probably find the seed (with P = prime(M)*prime(N)), In other words : Take the most significant 32 bits of N and M, multiply, if the result is close to the most significant bits of P, take the next 32 bits of N and M, multiply...

Bruteforce would be easy...

LaptoniC

February 11th, 2012, 02:26

What is the relation between M, N and P?
Program generates P and Q (primes of RSA) by using Random function and searching next prime like this

Code:

P=Random(Seed)

P=FindNextPrime(P)

Q=Random(Seed)

Q=FindNextPrime(Q)

N=P*Q

The idea is if we can find fast method to find IsPrime function we can speed up searching. Because if we can recover the seed either seed of P or seed of Q we will find the prime numbers. Other than that I didn't get what you mean by M and N. drizz's code is very detailed and fast but I abandoned the project until I get my new computer.

ShyKittten

February 12th, 2012, 07:59

In my previous post : P = M*N.

You say :

Code:



P=Random(Seed)

P=FindNextPrime(P)

Q=Random(Seed)

Q=FindNextPrime(Q)

N=P*Q

My idea :

Code:



P'=Random(Seed)

Q'=Random(Seed)

N'=P'*Q'

if(|N'-N| small enough)

{

       P=FindNextPrime(P')

       Q=FindNextPrime(Q')

       if(N==P*Q)

       {

              Correct Seed !

       }

}

I use it to break RSA-1024 with similar weak RNG (<1h to check all the 32-bits values).

LaptoniC

February 13th, 2012, 06:31

What is that small enough number? I have searched prime gaps and found that biggest gap is 4724 for 75 digits so theoretically that number will be 4724^2= 22316176 ( http://www.trnicely.net/gaps/g4k.html ) is this info true or it is lower than that?

ShyKittten

February 13th, 2012, 14:30

http://en.wikipedia.org/wiki/Prime_gap#Conjectures_about_gaps_between_primes ("no!")

Quote:

g(pn) = O((ln pn)^2)

If P and Q were independents, you would choose the gap carefully,
But, here, P and Q are linked together by the seed so few (P',Q') (and probably only 1) will pass the test even if you choose a too big gap...

LaptoniC

March 30th, 2012, 23:58

Thanks. It worked

winndy

March 2nd, 2013, 06:42

Thanks
Here is the tutorial by Laptonic
http://forum.exetools.com/showthread.php?t=14836