DateJanuary 22, 2008

Crackme 3 - RSA

This KeyGenMe is pretty nice since it's got some public key cryptography inside it.

You can download the original exe file, my KeyGen source file and the tools used from here.

The goal is to break an RSA protection to build a valid KeyGen. Let's start by opening the executable file with PeID and its Krypto Analyzer Plugin:

peid-pallas

As you can see there is some calls to Miracl library functions and it could identify an SHA hash function inside the binary. Let's keep this in mind while analyzing further with IDA. I recommend you to download some Miracl signatures for IDA so that it can identify the library functions for us.

Open the KeyGenMe with IDA and locate the GetDlgItemTextA call which will retrieve our typed Serial. Analyze the code around it to see what's going on:

.text:004027B2                 push    [ebp+var_488]
.text:004027B8                 push    [ebp+var_490]
.text:004027BE                 push    [ebp+var_494]
.text:004027C4                 push    [ebp+var_498]
.text:004027CA                 call      miracl_powmod

Powmod function prototype:

void 	powmod (big x, big y, big n, big w);

The powmod function computes w = x^y (mod n). It actually looks like RSA algorithm where x is the serial we typed in the TextBox. Now I will rename the vars for the sake of clarity:

.text:004027B2 push    [ebp+result]
.text:004027B8 push    [ebp+modulus]
.text:004027BE push    [ebp+public_key]
.text:004027C4 push    [ebp+INPUT_SERIAL]
.text:004027CA call      miracl_powmod

All these variables pushed onto the stack are mirvars and since we know its structure we can have a look at them to figure out their size:

debug025:00914F58 dword_914F58 dd 20h
debug025:00914F5C dd offset unk_914F64
debug025:00914F60 db    0
debug025:00914F61 db    0
debug025:00914F62 db    0
debug025:00914F63 db    0
debug025:00914F64 unk_914F64 db  49h ;

The first dword of a mirvar represents its length in 32bit words. So 20h means that the modulus is 1024 bits long.

From the pointer above (0x00914F64) we can take out the modulus value:

N=6601E15E4F6C572B0B38EDF792D426BBA6DEDB98D600C5763C5F2123A361F
49C0CAEA628887077DE01D1DE826D2496DF38802024BC00A64940C8EAB4F1D8
60443C8DE0CEB6B7611888F660B022AA32C3450BC2B6E035D6354654E8EF4666
31F0D180E978DB6960EB4061EAB52D0B281C580B8DA8FE76AB54D5AD85223DB
E1449

Repeating this process we will extract the public exponent: E in RSA scheme.

E=2B7893403C69D8FEB1C4A36D219298438722F2CEB82792230A0B9B8F2DD680
4DB9E64381AEDC6B070AF501522781368C6D76A176223F98FADBFF5F26B5FBAD
814C62143C2A430667CEDDD19C91F20E8EDCAA2A1773F71A18DA3CFAD34B75A6
23724349417E963347C9971E0EFB6E613691F2715523A53AA7CEC4E970584135F3

These two values were hardcoded into the original file each byte XOR'ed with 0x01.

If we scroll up in the disassembly we will see some interesting code:

.text:0040263D call    ds:GetVolumeInformationA
.text:00402643 push    [ebp+VolumeSerialNumber]
.text:00402649 push    offset asc_40D0FC ; "%x"
.text:0040264E lea     eax, [ebp+strVolumeSerialNumber]
.text:00402654 push    eax             ; char *
.text:00402655 call    _sprintf

Interesting, the above code is retrieving our HDD serial number and printing it as an hex ascii string into a local variable.
Then some modifications to this string will be applied:

With the help of Krypto Analyzer we could locate the SHA routine starting at 0x00401030 address which will be soon called
after retrieving the HDD serial number. Having a further look into xrefs to the identified SHA functions we may recognize
a typical hash stucture:

SHA_Init	@	0x00401000
SHA_Process	@	0x004023A4
SHA_Result	@	0x00402435

Ok, the HDD serial number is retrieved, printed to an ASCII hex string and then hashed. I checked the hash with a standard SHA-1 implementation and it differed from the 20-byte hash calculated by the keygenme. So I checked also SHA-0 which just differs from SHA-1 in a rotation but it didn't match either. I didn't want to waste so much time in identifying the used hash function so I decided to rip out the code from the binary itself (see sha.asm file in my sources) and build an object which will be linked against my KeyGen to produce exactly the same hash value.

After the hash of our HDD serial string was computed, the KeygenMe creates some miracl variables and a bignum which I'll call 'A'

A = 920CC8F0512FB63B8C2F89397A129BAA3D663BD1890C8EE23AAC836A316E231B
C = hash(strHDD_Serial) ^ 7 (mod A)

Now, the serial we typed in the TextBox will be the object of the RSA computation:

INPUT_SERIAL ^ E (mod N)

and compared with the previously calculated value C. If both match, then we have entered the right Serial.

So we have to find a serial which satisfies: C = INPUT_SERIAL ^ E (mod N) given C, E and N. This is clearly an RSA scheme:

RSA Encryption
rsa-encryption

RSA Decryption
rsa-decryption1

rsa-decryption2

Thus:

INPUT_SERIAL = C ^ D (MOD N)

We can see that to find a valid Serial we must know D (private exponent) and therefore we've got to compute it somehow.

N = P*Q, where P and Q are two large primes
E*D = 1 (MOD P-1)
E*D = 1 (MOD Q-1)
So, given P,Q and E we could easily obtain D. The problem is that factorizing N (1024-bit number) into P*Q is not feasible since it would take a nice amount of years.

There are some vulnerabilities in RSA algorithm regarding the size of the chosen exponents. One of them is exploited by the Wiener Attack which is able to find in polynomial time the secret exponent (D) if two conditions are given:

  • Q < P and P < 2*Q
  • D < 1/3*N^1/4

Sometimes low private exponents are chosen to speed up the decryption process. However if it falls inside these bounds we can compute it very fast. I will use the RAT (RSA Attacking Tool) by bLaCk-eye which is a very powerful tool to attack RSA in several ways. Besides he distributes this application with its source code and I recommend you to have a look at it.

If we give N and E to RAT it will immediately say the value of the private exponent which happens to be:

pallas-rat

D = B33F

Thus, we just have to code the following actions in our KeyGen:

  • Retrieve the HDD serial number
  • Compute C=hash(strHDD_Serial) ^ 7 (mod A)
  • Serial = C^D (mod N)

Please note that only the first 8 bytes of the hash output are used for the above calculation.

pallaskeygen

And paste this number into Pallas KeyGenMe:

pallas-ok

 

For a further understanding of the process have a look at the source code included.

ARM Development Board - LPC2138-01

LPC2138-01

I have designed a new development board which is supposed to be used in many of the projects I am/will be involved in. It's been built around an NXP LPC2138 microcontroller which has the following main features:

  • 16/32 bit ARM7TDMI-S microcontroller (LQFP64 package)
  • 32 KB of internal SRAM and 512 KB of on-chip flash program memory. 128-bit wide interface/accelerator enables high-speed 60 Mhz operation.
  • In-System Programming/In-Application Programming (ISP/IAP) via on-chip bootloader software. Single flash sector or full chip erase in 400 ms and programming of 256 B in 1 ms.
  • Two 8-channel 10-bit ADCs with conversion times as low as 2.44 us per channel.
  • Two 32-bit timers/external event counters (with four capture and four compare channels each), PWM unit (six outputs) and watchdog.
  • Multiple serial interfaces including two UARTs (16C550), two Fast I2C-bus (400 kbit/s), SPI and SSP with buffering and variable data length capabilities.
  • Vectored interrupt controller with configurable priorities and vector addresses.
  • Up to forty-seven 5 V tolerant general purpose I/O pins in tiny LQFP64 package.
  • Up to nine edge or level sensitive external interrupt pins available.
  • 60 MHz maximum CPU clock available from programmable on-chip PLL with settling time of 100 us.
  • On-chip integrated oscillator operates with external crystal in range of 1 MHz to 30 MHz and with external oscillator up to 50 MHz.
  • Power saving modes include Idle and Power-down.
  • Individual enable/disable of peripheral functions as well as peripheral clock scaling down for additional power optimization.
  • Processor wake-up from Power-down mode via external interrupt or BOD.
  • Single power supply chip with POR and BOD circuits:
    • CPU operating voltage range of 3.0 V to 3.6 V (3.3 V +- 10 pct) with 5 V tolerant I/O pads.

This microcontroller is suitable for most of my projects due to its high processing power (up to 60 MIPS) and its large amount of memory. Also, the board itself has some kind of features that I couldn't find in any other development board:

  • Audio playing support with earphones connector. Connected to the DAC output of the microcontroller through an audio amplifier circuit. It is possible to use the DAC output for another purposes.
  • Audio recording support with microphone connector. Connected to one of the ADCs channels of the microcontroller through an audio amplifier and signal conditioning circuit. It is possible to use the ADC input for another purposes.
  • Selectable power supply input: directly from USB or from external battery for standalone applications (Vin ranging from 3.3V to 20V).
  • RS232 interface through DB9 connector.
  • USB communication through USB Type-B connector (on-board USB-Serial converter). RX and TX leds.
  • 8 General Purpose LED's connected to the microcontroller through an output buffer which can be disabled through a jumper in case that these GPIO pins are needed.
  • Reset Button
  • General purpose button connected to one of the external interrupts of the microcontroller.
  • In Circuit Programming interface up to 115200 bps.
  • 12 MHz crystal for operation up to 60 MHz.
  • MMC/SD memory card interface connected to the SPI bus of the microcontroller.
  • Integrated Li-Ion / Li-Po Battery charger. It can charge batteries from USB or external power supply with LED charge indicators.
  • All the GPIO pins are available in the board. Including JTAG interface for programming / debugging in circuit.
  • Battery level monitoring. The input voltage is connected to one of the ADC inputs of the microcontroller through a voltage divisor so that it can be measured by software.

Software:

As the ARM architecture is being more and more popular there are lots of development tools available for all the platforms.

On Windows machines you can use WinARM which is a collection of tools to develop software for the ARM-family of controllers/processors including GNU C/C++ compiler (gcc / g++), GNU Binutils, GDB server, ...

Most of these tools are part of GNU arm-elf toolchain distributions so you can easily develop /program the LPC2138 microcontroller under GNU/Linux.

Also, you can find some good commercial software for ARM microcontrollers/microprocessors like the ARM RealView Development Suite.

In some applications an RTOS (Real Time Operating System) is needed and there are some of them available for this microcontroller. I would stand out the following ones: FreeRTOS (free for non-commercial purposes) and RealView RL-ARM.

Daniel.