PDA

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