Traditional encryption is based on secrecy provided by secret-key. But this leads to generation of same cipher text when the encryption scheme is applied to same plaintext with same key. Thus, replay of messages can be effortlessly identified by an adversary which can be a weak link in any communication. Probabilistic encryption is an approach to overcome this weakness where different cipher texts are generated each time same plaintext is encrypted using the same key.Extending the probabilistic approach, which is generally employed in asymmetric encryption, this paper proposes a new chaos-based probabilistic symmetric encryption scheme with customizable block-size suitable for image encryption. It employs a Random Bits Insertion phase followed by four rounds of two-staged diffusion involving simple XOR (exclusive-OR) operation making it computationally efficient. Random Bits Insertion makes the scheme probabilistic. This phase also helps in increasing entropy and making intensity distribution more uniform in cipher. The generated cipher text is twice the size of plain text. An increase in cipher text space is inevitable for probabilistic encryption and it provides an advantage as the apparent message space for the attacker is increased. The observations show that the scheme offers high strength to resist statistical and cryptanalytic attacks.