Padding of Original Message in MD5

what should I do if my original message is greater than 64 bits? what is the process of padding in MD5?

As described in Internet Security: Cryptographic Principles, Algorithms and Protocols, page 138, the second step in MD5 is to append the length of the message:

Can someone help me understand exactly what happens when the message length is greater than $2^{64}$ bits?

-
you mean greater than $2^{64}$ bits long, right? You realize that that is $2048$ petabytes, right? I'm hoping this isn't a problem you are actually facing. :) – mikeazo Apr 30 '13 at 15:48
@mikeazo: you never know when you may need the MD5 digest of exabytes of data! – Reid Apr 30 '13 at 16:53
Could you please cite your sources? (i.e. From where did you take this image?) – Paŭlo Ebermann Apr 30 '13 at 17:29
@PaŭloEbermann, I updated with the source. – mikeazo May 1 '13 at 1:14

I think the RFC, Section 3.2 has a little more clear description.

A 64-bit representation of b (the length of the message before the padding bits were added) is appended to the result of the previous step. In the unlikely event that b is greater than 2^64, then only the low-order 64 bits of b are used. (These bits are appended as two 32-bit words and appended low-order word first in accordance with the previous conventions.)

So, if the message length is b2 b1 b0 (where b2 is the most significant) where each b is 32 bits, then b0 b1 is appended as the message length. In otherwords, if the message is too large, just truncate the length (not the message) at 64 bits.

-

If the original message length $N$ is $2^{64}$ bits or longer, you encode the value $N \bmod 2^{64}$ in the final padding block, rather than just $N$. Alternatively, you can just always encode $N \bmod 2^{64}$; if $N < 2^{64}$, then they're the same value.

Now, this distinction between $N$ and $N \bmod 2^{64}$ doesn't happen at 64 bits, it's at $2^{64}= 18,446,744,073,709,551,626$ bits, or about 2000000 Terabytes. No one has ever hashed a message that long with MD5; even if we assume an MD5 compression function can be computed in 1nsec (massively overoptimistic), it'd take over a year to hash a message that large (and parallelism doesn't help).

-

As explained in other answers, the length is taken modulo $2^{64}$ for MD5, but messages longer than $2^{64}$ bits can be safely ignored for any practical purpose.

However, some hash functions use a different solution and forbid you to input a message longer than what can be stored in the counter. For instance the FIPS 180-4 standard defining SHA-1 states:

SHA-1 may be used to hash a message, $M$, having a length of $l$ bits, where $0≤l<2^{64}$.

-