If two hosts are using a transparent IP level authentication and encryption, is their communication subject to both MITM or replay attacks? Encryption process for any outgoing packet to the specified "remote IP":

-original payload P is encrypted (the bytes after the IP header) using RC4 with the preestablished key KEY to obtain encrypted payload C=RC4(P, KEY)

-The encrypted payload C is concatenated with the 16 byte output of MD5(C|KEY), and the IP header is adjusted accordingly (increasing the packet total length, re-calculate the checksum) so that the outgoing packet will have payload C | MD5(C|KEY) and destination "remote IP"

Decryption process for any incoming packet from specified "remote IP":

-Check the packet payload for the MD5 authentication with the same given "key"
Specifically, divide the received packet payload (those bytes after the IP header) as two parts C, A where A is the last 16 bytes of the packet payload and C is the rest.

-If MD5(C|KEY) == A, decrypt C using RC4 to obtain
P=RC4(C, KEY), change the payload of the incoming packet from C|A to P, and adjust the IP header accordingly (decrease the packet total length, re-calculate the checksum) so that the incoming packet will be restored to its original form without keyed md5 authentication before sent to the receiving process
1) Are replay attacks possible?
Yes. For example, if Alice wants to tell Bob "Pay Eve \$100", then P = "Pay Eve $100"
C = RC4(P, KEY)
Packet = IP(C | MD5(C|KEY) )
By capturing and replaying Packet, Eve can make Bob pay her \$100 over and over again.


2) Are Man-In-The-Middle attacks possible?
More specifically, "Is there a possibility to intercept messages and impersonate at-least one of the parties? Is it possible for the attacker to put himself between the sender and receiver by breaking the encryption?"

This question is more complicated. In short, it depends.

If the attacker gets hold of plaintext / ciphertext pairs for the RC4 (either through encryption oracle or decryption oracle), he simply takes P xor C to find the keystream. RC4 key reconstruction attacks can be used to find the MD5 key. The attacker may then act as a full MITM, intercepting and viewing messages and optionally modifying them before passing them on.

I am also uncomfortable with that MAC construction, so I'll get back to you on that one.