Differing from applying steganography on storage cover media, steganography on Voice over IP (VoIP) must often delicately balance between providing adequate security and maintaining low latency for real-time services. This paper presents a novel real-time steganography model for VoIP that aims at providing good security for secret messages without sacrificing real-time performance. We achieve this goal by employing the well-known least-significant-bits (LSB) substitution approach to provide a reasonable tradeoff between the adequate information hiding requirement (good security and sufficient capacity) and the low latency requirement for VoIP. Further, we incorporate the m-sequence technique to eliminate the correlation among secret messages to resist the statistical detection based on the fact that the distribution of the LSBs in the stego-speech is not uniform and to provide a short-term security protection of secret messages. To accurately recover secret messages at the receiver side, we design a synchronization mechanism based on the RSA key agreement and the synchronized sequence transmission using techniques of the protocol steganography, which can effectively enhance the flexibility of the covert communication system and be extended to other steganography schemes based on real-time systems. We evaluate the effectiveness of our model with ITU-T G.729a as the codec of the cover speech in StegTalk, a covert communication system based on VoIP. The experimental results demonstrate that our techniques provide good security and transparency for transmitting secret messages while adequately meeting the real-time requirement of VoIP.1