Video steganography is the method of hiding the presence of data within the cover video. In this paper, a novel video steganography technique is revealed, where with the help of Sudoku puzzle of order 9 × 9, extracted image frames of a cover video are utilized to hide encrypted data. The novelties of the work imply that as the input information is first encrypted into cipher text using a new modified substitution and permutation network (SPN)-type block cipher, then, that cipher text is embedded in the video using Sudoku puzzle as a key. This new and robust encryption model is like a block cipher in comparison with Advanced Encryption Standard (AES) that provides enhanced resistance in case of fault attack. This new SPN-type architecture differs with AES architecture in the step of round key mixing function. Its computation complexity is much higher compared to original AES to find 128 bits of tenth round key. Therefore, our proposed work combines both cryptographic and steganographic technique and Sudoku puzzle to enhance the security in maximum level with optimal computational complexity and good embedding capacity rate. © 2019, Springer-Verlag London Ltd., part of Springer Nature.