Exetools  

Go Back   Exetools > General > General Discussion

Notices

Reply
 
Thread Tools Display Modes
  #1  
Old 09-18-2017, 02:15
TempoMat TempoMat is offline
Friend
 
Join Date: Jan 2006
Posts: 87
Rept. Given: 10
Rept. Rcvd 6 Times in 6 Posts
Thanks Given: 4
Thanks Rcvd at 28 Times in 21 Posts
TempoMat Reputation: 6
Strange RSA modulus N value

I have an old Delphi application I’m trying to reverse.
The app uses the FGIntRSA RSADecrypt procedure plus slightly modified FGIntRSA Base64 chars to validate the UserName and RegCode

Code:
The Exponent N=49608307214148501933851667872461788859314634414960570968576805395
And the possible prime divisors are:
PRIME FACTOR: 3
PRIME FACTOR: 5
PRIME FACTOR: 5573
PRIME FACTOR: 1694327
PRIME FACTOR: 1606452225507735500339279
PRIME FACTOR: 218026387802762543011518916577
Looking at the 'standard' definition of the RSA Key generation example from:
https://en.wikipedia.org/wiki/RSA_(cryptosystem)
Quote:
Key generation
The keys for the RSA algorithm are generated the following way:
  1. Choose two distinct prime numbers p and q.
    For security purposes, the integers p and q should be chosen at random, and
    should be similar in magnitude but 'differ in length by a few digits to make
    factoring harder. Prime integers can be efficiently found using a primality test.
  2. Compute n = pq.
    n is used as the modulus for both the public and private keys. Its length,
    usually expressed in bits, is the key length
.
It is clear that this modulus N does fall out of this definition.

Consequently I’m unable to find the correct factors p and q to retrieve the Private Exponent D.

Also the app does not use the most common Public Exponents like 65537 (0x10001) or 7967 (0x1F1F) but rather 57167651080132926337657020661 (0x B8B7F8FED9427AB1E07720F5)

The original keys from the disassembly of the app are

Code:
Exponent E: r=JwZQM2jP7kIt3U
Modulus N:  j9I4D7HqaQTdXNtl3mgWtnkQiz6aN+RKlqoe
Base64 CharSet=  0123456789+=aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
If anyone wants to play with it.
Reply With Quote
  #2  
Old 09-18-2017, 21:25
Kerlingen Kerlingen is offline
VIP
 
Join Date: Feb 2011
Posts: 324
Rept. Given: 0
Rept. Rcvd 276 Times in 98 Posts
Thanks Given: 0
Thanks Rcvd at 308 Times in 95 Posts
Kerlingen Reputation: 200-299 Kerlingen Reputation: 200-299 Kerlingen Reputation: 200-299
It's not RSA, it's ElGamal.
Reply With Quote
The Following User Gave Reputation+1 to Kerlingen For This Useful Post:
MistHill (11-03-2017)
The Following 4 Users Say Thank You to Kerlingen For This Useful Post:
an0rma1 (12-18-2017), e0qs (12-16-2017), MistHill (11-03-2017), tonyweb (09-18-2017)
  #3  
Old 09-19-2017, 06:54
TempoMat TempoMat is offline
Friend
 
Join Date: Jan 2006
Posts: 87
Rept. Given: 10
Rept. Rcvd 6 Times in 6 Posts
Thanks Given: 4
Thanks Rcvd at 28 Times in 21 Posts
TempoMat Reputation: 6
Quote:
Originally Posted by Kerlingen View Post
It's not RSA, it's ElGamal.
I don't think it is ElGamal.

The Elgamal Encrypt/Decrypt procedures from the FGInt library do not use the 3 padding bits "111" as in the RSA.
Also I have keygened a few applications that use almost the same version of the FGInt library so I could easily identify the decryption routine and confirmed it with a compare.

Furthermore the Elgamal procedures use for conversions "only" the procedure "FGIntToBase256String" whereas the RSA En/Decrypt procedures use "Base2StringToFGInt", FGIntToBase2String, "convertBase256to2"

The program is very old and the original homepage is no more available.
I have therefore attached it here, if you want to try your hands on it.
The main application is compressed with Aspack, so it should not be a problem for a pro like you to unpack it.

By the way it uses BlowFish to save the entered UserName and RegCode in an app_name.fdb file and the RegData are checked on application restart.

My observation is that Kanal plugin in PEID is not able to detect older implementations of the FGIntRSA routines, especially when the RSA values are not in plain ASCII texts.

Using the RE-SIGS v0.18 PUBLIC by dihuxx in IDA to create MAP-file helped to resolve some of the FGIntRSA procedures.

Regards,
TemPoMat
Attached Files
File Type: rar ATMEF.rar (944.5 KB, 14 views)
Reply With Quote
The Following 2 Users Say Thank You to TempoMat For This Useful Post:
tonyweb (09-19-2017), zeuscane (09-19-2017)
  #4  
Old 09-20-2017, 03:23
aliali aliali is offline
Friend
 
Join Date: Jan 2002
Posts: 59
Rept. Given: 4
Rept. Rcvd 8 Times in 4 Posts
Thanks Given: 1
Thanks Rcvd at 13 Times in 8 Posts
aliali Reputation: 8
The conversion from base64 (Custom Base64 CharSet) to decimal for "Exponent E" is correct.

But, I think there is a conversion error on converting "Modulus N":

Code:
j9I4D7HqaQTdXNtl3mgWtnkQiz6aN+RKlqoe
To:

Code:
49608307214148501933851667872461788859314634414960570968576805395
I got:

Code:
49608213082142399816039386263750142317464556599709660835501230612
BTW, I can't download the attachment to validate my results. So, Can you provide the hexadecimal for "Modulus N".

Regards
Reply With Quote
  #5  
Old 09-20-2017, 17:29
TempoMat TempoMat is offline
Friend
 
Join Date: Jan 2006
Posts: 87
Rept. Given: 10
Rept. Rcvd 6 Times in 6 Posts
Thanks Given: 4
Thanks Rcvd at 28 Times in 21 Posts
TempoMat Reputation: 6
[QUOTE=aliali;110541]

Quote:
I got:

Code:
49608213082142399816039386263750142317464556599709660835501230612
This is correct because the conversion is first Base64toByteArray and then FGInt256toBinary.
The correct modulus N is then obtained from the conversion of the binary to hexadecimal.

Now if we use this number which should actually be the correct Modulus N we get the following factors:
Code:
PRIME FACTOR: 2
PRIME FACTOR: 2
PRIME FACTOR: 3
PRIME FACTOR: 193
PRIME FACTOR: 21419781123550258987927196141515605491133228238216606578368407
Quote:
BTW, I can't download the attachment to validate my results. So, Can you provide the hexadecimal for "Modulus N".
Here is a mega link
Reply With Quote
  #6  
Old 11-03-2017, 17:00
MistHill MistHill is offline
Family
 
Join Date: Dec 2012
Posts: 31
Rept. Given: 12
Rept. Rcvd 42 Times in 13 Posts
Thanks Given: 26
Thanks Rcvd at 135 Times in 28 Posts
MistHill Reputation: 42
It's ElGamal as Kerlingen said.
Take a look at: https://github.com/SnakeDoctor/FGInt
Code:
Femta.exe :: 0047E8F0
==
FGIntElGamal.pas :: Procedure ElGamalDecrypt(E : String; Var x, p : TFGInt; Var D : String);
Reply With Quote
The Following 2 Users Say Thank You to MistHill For This Useful Post:
e0qs (12-16-2017), tonyweb (11-04-2017)
  #7  
Old 12-12-2017, 22:36
TempoMat TempoMat is offline
Friend
 
Join Date: Jan 2006
Posts: 87
Rept. Given: 10
Rept. Rcvd 6 Times in 6 Posts
Thanks Given: 4
Thanks Rcvd at 28 Times in 21 Posts
TempoMat Reputation: 6
Thanks to Kerlingen And MistHill

Thanks to Kerlingen (my apology to you) for the correct assertion that it is ElGamal and not RSA and also to MishHill for the confirmation.

I have check the FGIntElGamal.pas from Walied Othman and could see that the 3 padding bits "111" are also used in both the encryption and decryption procedures.

I will work from here and see if I can generate valid keys for this application and write a keygen for it if possible.

Best Regards,
TemPoMat
Reply With Quote
The Following User Says Thank You to TempoMat For This Useful Post:
e0qs (12-16-2017)
  #8  
Old 12-17-2017, 15:38
raduga_fb raduga_fb is offline
Family
 
Join Date: Nov 2012
Posts: 69
Rept. Given: 3
Rept. Rcvd 121 Times in 21 Posts
Thanks Given: 1
Thanks Rcvd at 128 Times in 32 Posts
raduga_fb Reputation: 100-199 raduga_fb Reputation: 100-199
You can use
000000000000000000000000000870
...
000000000000000000000000000879
for Registration Code. It is not related to Registration Name.
Reply With Quote
The Following 3 Users Say Thank You to raduga_fb For This Useful Post:
an0rma1 (12-18-2017), MistHill (12-22-2017), TempoMat (02-25-2018)
  #9  
Old 12-22-2017, 10:36
MistHill MistHill is offline
Family
 
Join Date: Dec 2012
Posts: 31
Rept. Given: 12
Rept. Rcvd 42 Times in 13 Posts
Thanks Given: 26
Thanks Rcvd at 135 Times in 28 Posts
MistHill Reputation: 42
Good, raduga_fb found bugs in the application.
1. the customized Base64 encoding/decoding has problem.
UserCode 000000000000000000000000000870~879 and 87a, 87A, 87b, 87B result same after decoded.
2. validation logic
The success flag is set if UserCode length greater than 0x1D. But next it will jump over the UserName check if ElGamalDecrypt() failed.

We need to counterfeit a UserCode with the correct checksum, and cause ElGamalDecrypt() return NULL, the trick is done.

Some "valid" UserCode:
00000000000000000000000000004s
000000000000000000000000000+6s
0000000000000ca210e81sg92ku=gs
000000000000YRi210e81sg92kuaFs
000000000000JS0mA591h7l9nhR2Yc
000000000000Mt4tE4AMIojgpaJbQc
0000000000000AstE4AMIojgpaJbDCq
00000000000007yc93CdcfKwlGnPsRk
Reply With Quote
The Following User Says Thank You to MistHill For This Useful Post:
TempoMat (02-25-2018)
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Strange Instruction CTS BE thomasantony General Discussion 2 03-23-2005 04:41


All times are GMT +8. The time now is 15:14.


Always Your Best Friend: Aaron, JMI, ahmadmansoor, ZeNiX, chessgod101
( 1998 - 2024 )