How to recognize algoritam in software? It is MD5, SHA-1, RSA or something else?

Mike the resident crypto wizard wrote something of this sort loooong back... [Hajo Mike! Where art thou?}

Look here:http://www.woodmann.net/fravia/mike.htm

Signed,
-- FoxThree

In addition, I have written a tutorial (nothing special) on a target that use MD5:
http://www.woodmann.net/fravia/Zai_TabMail.htm

it might help you...

regards,
ZaiRoN

I read your tutor. It's great. Well done! But MD5 and SHA-1 are similar? Don't you think that?

Bruce Lee

thx.

What do you mean with *similar*?
Maybe the *design* is similar but those are two distinct algorithms.

For example:
- Initialization constant:
MD5 : 0123456789ABCDEFFEDCBA9876543210
SHA-1: 0123456789ABCDEFFEDCBA9876543210F0E1D2C3
- Message digest:
MD5 produces a 128-bit message digest
SHA-1 produces a 160-bit message digest
...

ZaiRoN

The simplest way is to recognize constants used by the algorithm. Almost all block-cipher algorithms and hash-functions have predefined constants used in calculations.

For example, MD4/MD5/SHA use constants 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0 (the last is only in SHA) for initialization. So, if you see such constants in the program most probably it uses something of MD4/MD5/SHA kind.

Another example: RC5 uses constants 0xb7e15163 and 0x9e3779b9 in 32-bit version, and constants 0xb7e151628aed2a6b and 0x9e3779b97f4a7c15 in 64-bit version.

Of course, encryption/hash algorithm is not defined by constants only, but they allow to restrict set of possible candidates.

Regards, Bruce Lee

I have had some troubles dealing with big number algorithm... is there a way of identifying them as well? like RSA and stuff?

thanks
crUsAdEr

You can usually recognize which algorithm is being used by the type of parameters needed for input. RSA needs two primes p,q selected at random which are then multiplied to give a value for n (n=pq). Better implementations of RSA will have certain smoothness tests for n that deter various factoring attacks (Pollard's p-1 and p+1 method for example). Phi(n)=(p-1)(q-1) is the next to be computed. A variable e is selected at random such that 1 < e < Phi(n) and gcd(e, Phi(n)) = 1. The pair (n,e) is the public key. Lastly, d is computed as d = e^(-1) modulo Phi(n). The private key is (n,d) or (p,q,d).

So if we count everything up, that's p,q,n,Phi(n),e, and d. If you're reversing a program, the best way to detect if RSA is being used is to figure out if any of these computed values are being using in some sort of encryption or decryption function. There's no quick way to do this, but if you know the mathematics behind the major schemes that are used in practice (RSA, DL, or EC) you can study an assembly listing and almost always guess as to which one is used.

RSA encryption can be spotted easily. Let m be the plaintext and E(m) the encryption function. c = E(m) = m^(e) modulo n. Let D(c) be the decryption function. m = D(c) = c^(d) modulo n. It's easy to spot since modular exponentiation can only be done efficiently a certain number of ways. The most commonly used algorithm is the Square and Multiply algorithim. But sometimes you'll come across Right-to-left Binary Exponentiation (which works on finite Abelian groups, identity=1), Left-to-right Binary Exponentiation, Left-to-right k-ary Exponentiation (also called the Window Method), Sliding Window Exponentiation, Simultaneous multiple Exponentiation, Montgomery Exponentiation, and the list goes on. Check Chapter 14 (Efficient Implementation) of the Handbook of Applied Cryptography for a complete rundown of each algorithm.

The trick is to recognize if one of these is being used. Program them yourself in a language like C, and then compile your programs. Reverse engineer your test applications to see how the algorithms will look in targets written in C.

The same thing goes for implementations of the Discrete Logarithm Problem. A common example of the DLP exists in many programs that need two users to share a private key for symmetric encryption. To agree on a secret key, the two users use the Diffie-Hellman Key Exchange, which is an instance of the DLP. Tell tale signs in programs that this is being done: A predetermined group G is used with an element g (in G) as a generator of the group. So <g> = G. The order of g is computed and saved for later use. On one user's side, the program selects a random 'a' in [1,ord(g)]. If the order of g is unknown, an upper bound is used instead. Then g^(a) is computed in the group, and is sent to another user. The program then waits for the other person (who selects a random 'b' in [1,ord(g)] and computes g^(b) in the group) to send over g^(b). The target program then lifts g^(b) to the a-th power and that becomes the shared secret that was passed over an insecure channel. Look for fast exponentiation algorithms that work in finite Abelian groups (also in Chapter 14 of the Handbook).

It takes some practice to spot them, and sometimes it's impossible to tell because of strange implementations (ie: non-standard polynomial splitting algorithms for finite fields [or their extensions]), but at least we can always make a good guess.

Just know the math behind the different cryptosystems, and write some of your own programs that you can disassemble and study. Commercial programs that use strong crypto usually have functions like "Square_And_Multiply" in the dead list.. if the programmers suddenly had a momentary lapse of judgement.. always use this to your advantage!

Wouldn't you know it... the first activity on this board in three weeks and it happens when I'm away

All the responses have been great, IMO. If you think MD5 and SHA are similar, that's because the guys who made SHA took MD5's design and expanded it.

One highly underrated way of finding out what algorithm has been used is checking the docs and/or writing the software author! It's surprising how often this works.

Hi mike!

Are you joking?

ZaiRoN

Nope. It's like virus writers who brag about their creations; often the same thing goes for bad crypto! Of course, don't expect him to give you details, but even a broad overview can help you make sense of what you're seeing.

Also, I recommend taking the approach of a "fellow shareware author" trying to "emulate his excellent protection."