Symmetric cryptographic primitives such as block and stream ciphers are the building blocks in many cryptographic
protocols. Having such blocks which provide provable security against various types of attacks is often hard. On the
other hand, if possible, such designs are often too costly to be implemented and are usually ignored by practitioners.
Moreover, in RFID protocols or sensor networks, we need lightweight and ultra-lightweight algorithms. Hence,
cryptographers often search for a fair trade-off between security and usability depending on the application. Contrary
to public key primitives, which are often based on some hard problems, security in symmetric key is often based on some
heuristic assumptions. Often, the researchers in this area argue that the security is based on the confidence level the
community has in their design. Consequently, everyday symmetric protocols appear in the literature and stay secure
until someone breaks them. In this thesis, we evaluate the security of multiple symmetric primitives against statistical
and algebraic attacks. This thesis is composed of two distinct parts:
In the first part, we investigate the security of RC4 stream cipher against statistical attacks. We focus on its applications
in WEP and WPA protocols. We revisit the previous attacks on RC4 and optimize them. In fact, we propose a framework
on how to deal with a pool of biases for RC4 in an optimized manner. During this work, we found multiple new weaknesses
in the corresponding applications. We show that the current best attack on WEP can still be improved. We compare our
results with the state of the art implementation of the WEP attack on Aircrack-ng program and improve its success rate.
Next, we propose a theoretical key recovery and distinguishing attacks on WPA, which cryptographically break the protocol.
We perform an extreme amount of experiments to make sure that the proposed theory matches the experiments. Finally,
we propose a concrete theoretical and empirical proof of all our claims. These are currently the best known attacks on WEP
In the second part, we shed some lights on the theory behind ElimLin, which is an algorithm for solving multivariate polynomial
systems of equations. We attack PRESENT and LBlock block ciphers with ElimLin algorithm and compare their security using this
algebraic technique. Then, we investigate the security of KATAN family of block ciphers and multi-purpose cryptographic primitive
ARMADILLO against algebraic attacks. We break reduced-round versions of several members of KATAN family by proposing a
novel pre-processing technique on the original algebraic representation of the cipher before feeding it to a SAT solver. Finally,
we propose a devastating practical key recovery attack against the ARMADILLO1 protocol, which breaks it in polynomial time
using a few challenge-response pairs.