Virus Encoded in Video

Yes, that's possible.

The malware probably wouldn't be embedded in the video itself, but the video file would be specially crafted to exploit a vulnerability in the codec or media player, to gain code execution. The exploit would then download a file and run it, infecting the machine.

These types of exploits have been common amongst popular document formats, e.g. PDF. Their proliferation makes them a good target for exploit writers, because people use them a lot and assume they're safe. At the end of the day, any file type could potentially contain an exploit, since an application that runs executable code is involved at some point.

Exploits like this are usually buffer overflow attacks, which alter control flow by overwriting data structures outside the normal memory range of a buffer.

More info:

• Buffer overflows on OWASP
• Buffer overflow protection
• Exploit Writing 101 on CoreLAN

There is a pretty nice play-by-play of a real-life example of this on h-online (german it publisher). In this case it's a purposed flash video that contains several different attacks to infect the computer trying to display the video

Besides @Polynomial's buffer overflow possibility, the "video file" could actually be a trojan executable. Here's a simple example:

• An executable file is named such that it appears to be a video, like:

  "movie.avi                     .exe"

• The executable extracts the video data embedded in it, starts your video player, and meanwhile deploys its malicious payload.

To the user, it appears that they've clicked a video file and it opened in their video player just like normal. Instead, they've been tricked into running the trojan.

Edit to add: This is the inverse of your question title. Instead of a virus encoded in a video, a video is encoded in a virus.