Interleaving is a key component of many digital communication systems involving error correction schemes. It provides a kind of time diversity to protect the transmitted data against bursts of errors. Recently, interleavers have become an even more integral part of the code design itself, if we consider for example turbo and turbo-like codes. In a non-cooperative context, a passive adversary has to solve the problem of estimating the interleaver parameters. In this paper, we propose an algorithm that is able to estimate the size, the starting position (frame synchronization) of the interleaver, and some information about the interleaver function. This is accomplished blindly at the output of a binary symmetric channel (BSC). Moreover, an improvement of the proposed method is introduced when a soft information on the decided bits is available. A theoretical analysis of the proposed technique is given. This allows us to express the optimal detection threshold and the theoretical probability of detection. This analysis gives us insight on the behavior of our method and allows us to improve our algorithm to get better performance. Some experimental results are run to validate the probability of success of our algorithm.