Breaking Software Protection – DSA/DSS

1. Introduction

In this third part of the series, we will see something similar to the second article but a little bit more advanced. This article will cover the Digital Signature Algorithm (DSA) and Digital Signature Standard (DSS).

What should you learn next?

From SOC Analyst to Secure Coder to Security Manager — our team of experts has 12 free training plans to help you hit your goals. Get your free copy now.

Get Your Plan

2. Tools Needed

3. What is DSA/DSS?

Digital Signature Algorithm (DSA) is a public-key signature scheme developed by the U.S. National Security Agency (NSA). It was proposed by the U.S. National Institute of Standards and Technology (NIST) back in 1991 and has become a U.S. Federal Information Processing Standard (FIPS 186) called the Digital Signature Standard (DSS). It is considered to be the first digital signature scheme recognized by any government. DSA is a variant of the ElGamal Signature Scheme.

A. Parameters

• P = A prime number in range 512 to 1024 bits which must be a multiple of 64
• Q = A 160 bit prime factor of P-1
• G = H^((P-1)/Q) mod P. H is any number < P-1 such that H^((P-1)/Q) mod P > 1
• X = A random number < Q
• Y = G^X mod P

Public keys are: (Q, P, G and Y). Private key is X (To find X one must solve the DLP Problem).

B. Signing

To sign a message (M) follow these steps:

1. Generate a random number K where (K < Q)
2. Compute: R = (G^K mod P) mod Q
3. Compute: S = (K^-1*(SHA(M) + X*R)) mod Q

   The pair C(R,S) is the signature of M.

C. Verifying

Given the signature C(R,S) one would verify it as follows:

1. Compute: W = S^-1 mod Q
2. Compute: U1 = (SHA(M) * W) mod Q
3. Compute: U2 = (R*W) mod Q
4. Compute: V = ((G^U1 * Y^U2) mod P) mod Q
5. Confirm that V == R

D. Example

Using the tool that I've recently made, "DSAKEYGENERATOR", we'll be able to see the previous steps in action. The tool is user friendly and gives full control, meaning you can either generate keys and test them and/or input your own keys and work on them.

1. Prime P bits size from 512 to 1024.
2. Generate new keys.
3. To test the keys.
4. Calculate Y in case you've already had the keys from somewhere else.
5. Generate new G and X keys, Y will also be calculated automatically.

Clicking "TEST" will cause a new window to show up:

1. A checkbox that generates a random K every one second (checked by default and must be unchecked when trying to sign).
2. Button to sign a message.
3. Button to verify a message.

4. Target analyses

Here we have the challenge as you see in the picture below:

We load up the challenge in PEiD:

That's something new, we have a non-packed/protected .NET application, not like the previous two challenges which were made in MASM, but that's not a problem.

Since it's a .NET application, we cannot use OllyDbg, instead we'll use .NET Reflector.

So load up the assembly in Reflector and keep expanding until you reach Form1:

There are a lot of methods as you might see, but what interests us more is the method btn_check_Click since it's related to the only button in this challenge. Click that method and you shall see:

The code is easy to understand, we have the typed name put in a variable 'text' and the typed serial in 'input' name length must be between 3 and 15. Serial length must be between 0x4f (79d) and 0x51 (81d). After that a method called isHex(string x) does some checking, let's find out what's inside:

This method uses Regex's isMatch method to see if the typed serial matches the Regex string "^[0-9A-Fa-f]{40}[-][0-9A-Fa-f]{40}?$". Let me explain each Regex symbol:

• ^: Start of string.
• [0-9A-Fa-f]: One from 0 to 9, A to F or a to f.
• {40}: Exactly 40 characters.
• [-]: one hyphen.
• ?: Once or none.
• $: End of string

So the serial must contain 40 hexadecimal characters, a hyphen '-' and another 40 hexadecimal characters.

If name and serial are okay, the serial will be split into two parts, the first part before the hyphen and the second part after the hyphen, and put in a string array called strArray.

After that, a method is called to check whether the serial is right or wrong; this method has three string parameters verify(string name, string rx, string sx) and returns a bool.

Let's get inside that method:

If we compare the variables (integer8, exp, integer10 and integer11) with the verifying steps of DSA we'll know that:

• modulus = order Q
• n = prime P
• integer3 = generator G
• integer4 = public key Y
• integer6 = rx = R = strArray[0] which is the first part of the serial
• integer8 = sx = S = strArray[1] which is the second part of the serial
• integer8 = W
• exp = u1
• integer10 = u2
• integer11 = v

Now we have everything we need, the only problem is that it will take so much time to solve DLP since P, G and Y are 512 bits size. So what we are going to do is to change the challenge's keys with new ones that we will have their private key X, meaning we are going to patch the target. And that's the job of Reflexil.

First open DSAKeygenerator and generate some 512 bit keys. Leave it open.

Assuming you have already downloaded Reflexil. Extract the rar file and you'll find a dll inside a folder, it's called "Reflexil.Reflector.AIO.dll". Move it to somewhere else where it won't be deleted (C for example). Now go back to Reflector and do as shown in the pictures below:

Choose the dll file and close.

Now go back to menu Tools and click Reflexil.

Right Click on Offset 0 and click Edit.

Change the operand at offset 0 with the generated Q in DSAKeygenerator. The same to offset 13 with P, offset 26 with G and offset 39 with Y.

I've got the following keys generated in DSAKeygenerator:

Q = EEFBBFE158DBB7C602BE9540B89FF681EED0310D

P = 86CC13E777A3ED808B3B17B3AC6C78D5ABA5F15746B1A68C72B6F530A6B723390B486228E0F715DBB593206801DF48E3E56DF57336E2BD6219EE8DEFD001F6E7

G = 1E342C53DBE73C97FF8D8022B8EB18329181B821B10A5DBFC2688DDCC9DB5DF84079DA58E81FEEA43AAD38A8C1D3901E25859C7AB63AFEE1145EFD02DCC9B1AA

X = AF12001D2043D47E8E1B661958177B6068C8FAA2

Y = 2C166A5F90BD4B40D159CD48CC4391A8322BF3839DB58DA6EB0EEDF9D322AC3446EBAB0362F6BFB7127320C6CCED2CF77C915A1B56E5CE57A1758B53DAFA9C45

The result in Reflexil must look like:

Now on the assembly browser, right click on the main assembly (1) and do as follows:

Now that we have the challenge patched with the new keys, we must generate the signature (R,S) using DSAKeygenerator (Hope you didn't close it! If so just fill each key with the one on top without clicking the 'generate keys' button) and click TEST as shown below:

I've changed M to "Jamal Chahir" and unchecked the "RAND" checkbox so that I can get a fixed R and S. Now all we've got to do is fill in the name and serial in the patched challenge with what we've got:

Name: Jamal Chahir

Serial: R-S = 5DD88D3FE73B83F8027BB0AD3A53D404F887840B-E189F0BAC17C03EDA24FD5FD837FA397D6501321

The above picture shows that we have successfully registered the application.

That's it.

5. Conclusion

The whole idea behind this article was to show you that the key size is no problem once you completely understand the algorithm. But there still plenty of ways to manage that problem, depending on how the programmer thinks.

Download links:

FREE role-guided training plans

Get 12 cybersecurity training plans — one for each of the most common roles requested by employers.

Download Now

Sources:

• http://en.wikipedia.org/wiki/Digital_Signature_Algorithm