To secure the secret communication, a robust video steganography algorithm is proposed. The major objectives of the proposed method (PM) are: (1) perceiving the region of interest (ROI) keypoints’ locations in video frames for concealing the secret data and (2) determining the appropriate amount of data to be embedded into the perceived ROI keypoints’ region. In the PM, keypoints are initially extracted from each video frame using scale-invariant feature transform (SIFT) and a speeded-up robust features (SURF) descriptor against a set of predefined geometrical and signal processing attacks. Next, ROI keypoints are generated by comparing the SIFT and SURF keypoint descriptors of the original frame and attacked versions of the frame. Then ROI keypoints are divided into four least significant bit (LSB) groups to determine the embedding capacity of each ROI keypoint. Subsequently, the secret data are encrypted using a symmetric key-based shift cipher to provide an additional security layer for secret communication. Finally, the encrypted secret data have been embedded into the ROI keypoints using the LSB substitution method based on the four LSB groups’ values. The PM is tested on 22 standard benchmark videos. The efficiency of the PM is evaluated in terms of the perceptual invisibility, robustness, and concealing capacity. From experimental results, it is observed that the PM outperforms contemporary methods by attaining significant outcomes.