A video identifier uniquely identifying a video captured by a camera is generated. The video includes video frames and optionally concurrently captured audio as well as video metadata describing the video. Video data is extracted from at least two of the video's frames. By combining the extracted video data in an order specified by an identifier generation protocol, an extracted data object is generated. The extracted data object is hashed to generate the unique media identifier, which is stored in association with the video. The identifier generation protocol may indicate the portions of the video data to extract, such as video data corresponding to particular video frames and audio data corresponding to particular audio samples. The extracted data object may include a size of particular video frames, a number of audio samples in the video, or the duration of the video, for example.