As a growing number of individuals are exposed to surveillance cameras, the need to prevent captured videos from being used inappropriately has increased. Privacy-related information can be protected through video encryption during transmission or storage, and several algorithms have been proposed for such purposes. However, the simple way of evaluating the security by counting the number of brute-force trials is not proper for measuring the security of video encryption algorithms, considering that attackers can devise specially crafted attacks for specific purposes by exploiting the characteristics of the target video codec. In this paper, we introduce a new attack for recovering contour information from encrypted H.264 video. The attack can thus be used to extract face outlines for the purpose of personal identification. We analyze the security of previous video encryption schemes against the proposed attack and show that the security of these schemes is lower than expected in terms of privacy protection. To enhance security, an advanced block shuffling method is proposed, an analysis of which shows that it is more secure than the previous method and can be an improvement against the proposed attack.