at 14:00
Tel-Aviv University - Computer Science Colloquium
Sunday, June 4, 14:15-15:15
at 14:00
Room 12 (Note the unusual place!)
Schreiber Building
A5/1 is the strong version of the encryption algorithm used
by about 130 million GSM customers in Europe to protect the
over-the-air privacy of their cellular voice and data
communication. The best published attacks against it require
between $2^{40}$ and $2^{45}$ steps. This level of security makes it
vulnerable to hardware-based attacks by large organizations,
but not to software-based attacks on multiple targets by hackers.
In this paper we describe new attacks on A5/1, which are
based on subtle flaws in the tap structure of the registers, their
noninvertible clocking mechanism, and their frequent resets.
After a $2^{48}$ parallelizable data preparation stage (which has
to be carried out only once), the actual attacks can be carried
out in real time on a single PC.
The first attack requires the output of the A5/1 algorithm during
the first two minutes of the conversation, and computes the key in
about one second. The second attack requires the output of the
A5/1 algorithm during about two seconds of the conversation,
and computes the key in several minutes. The two attacks are related,
but use different types of time-memory tradeoffs. The attacks were
verified with actual implementations, except for the preprocessing
stage which was extensively sampled rather than completely executed.
Joint work with Alex Biryukov and David Wagner.
For colloquium schedule, see http://www.math.tau.ac.il/~zwick/colloq.html