As a response to the lack of efficient and secure stream ciphers, ECRYPT (a 4-year
Network of Excellence funded by the European Union) manages and coordinates a multi-
year effort called eSTREAM to identify new stream ciphers suitable for widespread adop-
tion. Polar Bear, one of the eSTREAM candidates, is a new synchronous stream cipher
proposed by Johan Håstad, and Mats Näslund. In this thesis, the first known attack
is presented. It is a guess-and-determine attack with a computational complexity of
O(2^78.8) that recovers the initial state. We propose that this weakness is fixed by adding
a key-dependent pre-mixing of the dynamic permutation in conjunction with the key
schedule. Further suggested tweaks strengthen the security and improves performance
on long sequences. The updated Polar Bear specification that will be sent to eSTREAM
before June 30, 2006, is based on tweaks suggested in this thesis. We have also optimized
the source code of Polar Bear, which enables it to run almost twice as fast. We have not
found any other weaknesses in Polar Bear, and it seems resistant to all known generic
attacks.