**A More Compact AES**

*David Canright and Dag Arne Osvik*

We explored ways to reduce the number of bit operations required to implement AES. One way involved optimizing the composite field approach for entire rounds of AES. Another way was integrating the Galois multiplications of MixColumns with the linear transformations of the S box. Combined with careful optimizations, these reduced the number of bit operations to encrypt one block by 9.0%, compared to earlier work that used the composite field only in the S-box. For decryption, the improvement was 13.5%. This work may be useful both as a starting point for a bit-sliced software implementation, where reducing operations increases speed, and also for hardware with limited resources.

**A new approach for FCSRs**

*François Arnault and Thierry Berger and Cédric Lauradoux and Marine Minier and Benjamin Pou*sse

The Feedback with Carry Shift Registers (FCSRs) have been proposed as an alternative to Linear Feedback Shift Registers (LFSRs) for the design of stream ciphers. FCSRs have good statistical properties and they provide a built-in non-linearity. However, two attacks have shown that the current representations of FCSRs can introduce weaknesses in the cipher. We propose a new “ring'” representation of FCSRs based upon matrix definition which generalizes the Galois and Fibonacci representations. Our approach preserves the statistical properties and circumvents the weaknesses of the Fibonacci and Galois representations. Moreover, the ring representation leads to automata with a quicker diffusion characteristic and better implementation results. As an application, we describe a new version of F-FCSR stream ciphers.

**An Efficient Residue Group Multiplication for The $\eta_T$ Pairing Over ${\mathbb F}_{3^m}$
**

*Yuta Sasaki and Satsuki Nishina and Masaaki Shirase and Tsuyoshi Takagi*

When we implement the $\eta_T$ pairing, which is one of the fastest pairings, e need multiplications in a base field ${\mathbb F}_{3^m}$ and in a group $G$. We have regarded elements in $G$ as those in ${\mathbb F}_{3^{6m}}$ to implement the $\eta_T$ pairing in the past. Gorla et al. proposed a multiplication algorithm in ${\mathbb F}_{3^{6m}}$ that takes 5 multiplications in ${\mathbb F}_{3^{2m}}$, namely 15 multiplications in ${\mathbb F}_{3^{m}}$. This algorithm then reaches the theoretical lower bound of the number of multiplications. On the other hand, we may also regard elements in $G$ as those in the residue group ${\mathbb F}_{3^{6m}}^{\,*}\,/\,{\mathbb F}_{3^{m}}^{\,*}$ in which $\beta a$ is equivalent to $a$ for $a \in {\mathbb F}_{3^{6m}}^{\,*}$ and $\beta \in {\mathbb F}_{3^{m}}^{\,*}$. This paper propose an algorithm for computing a multiplication in the residue group. Its cost is asymptotically 12 multiplications in ${\mathbb F}_{3^{m}}$ as $m \rightarrow \infty$, which reaches beyond the lower bound the algorithm of Gorla et al. reaches.

**An Improved Recovery Algorithm for Decayed AES Key Schedule Images**

*Alex Tsow*

A practical algorithm that recovers AES key schedules from decayed memory images is presented. Halderman et al. [9] established this recovery capability, dubbed the cold-boot attack, as a serious vulnerability for several widespread software-based encryption packages. Our algorithm recovers AES-128 key schedules tens of millions of times faster than the original proof-of-concept release. In practice, it enables reliable recovery of key schedules at 70% decay, well over twice the decay capacity of previous methods. The algorithm is generalized to AES 256 and is empirically shown to recover 256-bit key schedules that have suffered 65% decay. When solutions are unique, the algorithm effciently validates this property and outputs the solution for memory images decayed up to 60%.

**BTM: A Single-Key, Inverse-Cipher-Free Mode for Deterministic Authenticated Encryption
**

*Tetsu Iwata and Kan Yasuda*

We present a new blockcipher mode of operation named BTM, which stands for Bivariate Tag Mixing. BTM falls into the category of Deterministic Authenticated Encryption, which we call DAE for short. BTM makes all-around improvements over the previous two DAE constructions, SIV (Eurocrypt 2006) and HBS (FSE 2009). Specifically, our BTM requires just one blockcipher key, whereas SIV requires two. Our BTM does not require the decryption algorithm of the underlying blockcipher, whereas HBS does. The BTM mode utilizes bivariate polynomial hashing for authentication, which enables us to handle vectorial inputs of dynamic dimensions. BTM then generates an initial value for its counter mode of encryption by mixing the resulting tag with one of the two variables (hash keys), which avoids the need for an implementation of the inverse cipher.

**Compact McEliece Keys from Goppa Codes**

*Rafael Misoczki and Paulo S. L. M. Barreto
*The classical McEliece cryptosystem is built upon the class of Goppa codes, which remains secure to this date in contrast to many other families of codes but leads to very large public keys. Previous proposals to obtain short McEliece keys have primarily centered around replacing that class by other families of codes, most of which were shown to contain weaknesses, and at the cost of reducing in half the capability of error correction. In this paper we describe a simple way to reduce significantly the key size in McEliece and related cryptosystems using a subclass of Goppa codes, keeping the capability of correcting the full designed number of errors while also improving the efficiency of cryptographic operations to subquadratic time.

**Cryptanalysis of Dynamic SHA(2)**

*Jean-Philippe Aumasson and Orr Dunkelman and Sebastiaan Indesteege and Bart Preneel*

In this paper, we analyze the hash functions Dynamic SHA and Dynamic SHA2, which have been selected as first round candidates in the NIST Hash Competition. These hash functions rely heavily on data-dependent rotations, similar to certain block ciphers, e.g., RC5. Our analysis suggests that in the case of hash functions, where the attacker has more control over the rotations, this approach is less favorable. We present practical, or close to practical, collision attacks on both Dynamic SHA and Dynamic SHA2. Moreover, we present a preimage attack on Dynamic SHA that is faster than exhaustive search.

**Cryptanalysis of hash functions with structures**

*Dmitry Khovratovich*

Affiliations: University of Luxembourg

Hash function cryptanalysis has acquired many methods, tools and tricks from other areas, mostly block ciphers. In this paper another trick from block cipher cryptanalysis, the structures, is used for speeding up the collision search. We investigate the memory and the time complexities of this approach under different assumptions on round functions. The power of the new attack is illustrated with the cryptanalysis of the hash functions Grindahl and the analysis of the SHA-3 candidate Fugue (both functions as 256 and 512 bit versions). The collision attack on Grindahl-512 is the first collision attack on this function.

**Cryptanalyses of Narrow-Pipe Mode of Operation in AURORA-512 Hash Functi**on

*Yu Sasaki*

We present cryptanalyses of the AURORA-512 hash function, which is a SHA-3 candidate. We first describe a collision attack on AURORA-512. We then show a second-preimage attack on AURORA-512/-384 and explain that the randomized hashing can also be attacked. We finally show a full key-recovery attack on HMAC-AURORA-512 and universal forgery on HMAC AURORA-384. Our attack exploits weaknesses in a narrow-pipe mode of operation of AURORA-512 named ``Double-Mix Merkle-Damg\aa{}rd (DMMD)," which produces 512-bit output by updating two 256-bit chaining variables in parallel. We do not look inside of the compression function. Hence, our attack can work even if the compression function is regarded as a random oracle. The time complexity of our collision attack is approximately $2^{236}$ AURORA-512 operations, and $2^{236}\times 512$ bits of memory is required. Our second preimage attack works on any given message. The time complexity is approximately $2^{290}$ AURORA-512 operations, and $2^{288}\times 512$ bits of memory is required. Our key recovery attack on HMAC-AURORA-512, which uses 512-bit secret keys, requires $2^{257}$ queries, $2^{259}$ off-line AURORA-512 operations, and a negligible amount of memory. The universal forgery on HMAC-AURORA-384 is also possible by combining the second-preimage and key-recovery attacks.

**Cryptanalysis of the full MMB Block Cipher**

*Meiqin Wang and Jorge Nakahara Jr and Yue Sun
*The block cipher MMB was designed by Daemen, Govaerts and Vandewalle, in 1993, as an alternative to the IDEA block cipher. We exploit and describe unusual properties of the modular multiplication in $\Z_{2^{32}-1}$, but the {\bf main contributions} of this paper are detailed differential, square and linear cryptanalysis of MMB. Concerning differential cryptanalysis, we can break the full 6-round MMB with $2^{118}$ chosen plaintexts, $2^{95.91}$ full 6-round MMB encryptions and $2^{64}$ counters, effectively bypassing the ciphers countermeasures against DC. For the square attack, we can recover the 128-bit user key for 4-round variant of MMB with $2^{34}$ chosen plaintexts, $2^{126.32}$ 4-round encryptions and $2^{64}$ memory requirements. Concerning linear cryptanalysis, we present a key-recovery attack on 3-round variant of MMB requiring $2^{114.56}$ known-plaintexts and $2^{126}$ encryptions. Moreover, we detail a ciphertext-only attack on 2-round MMB using $2^{93.6}$ ciphertexts and $2^{93.6}$ parity computations. These attacks do not depend on weak-key or weak-subkey assumptions, and are thus, independent of the (redesigned) key schedule algorithm.

**Cryptanalysis of the LANE Hash Function**

*Shuang Wu and Dengguo Feng and Wenling Wu*

The LANE hash function is designed by Sebastiaan Indesteege and Bart Preneel. It is now a first round candidate of NIST's SHA-3 competition. The LANE hash function contains four concrete designs with different digest length of 224, 256, 384 and 512.

The LANE hash function uses two permutations P and Q, which consist of different number of AES-like rounds. LANE-224/256 uses 6-round P and 3-round Q. LANE-384/512 uses 8-round P and 4-round Q. We will use LANE-n-(a,b) to denote a variant of LANE with a-round P, b-round Q and a digest length n.

We have found a semi-free start collision attack on reduced-round LANE-256-(3,3) with complexity of 2^62 compression function evaluations and 2^69 memory. This technique can be applied to LANE-512-(3,4) to get a semi-free start collision attack with the same complexity of 2^62 and 2^69 memory. We also propose a collision attack on LANE-512-(3,4) with complexity of 2^94 and 2^133 memory.

**Differential Fault Analysis of Rabbit**

*Aleksander Kircanski and Amr Youssef
*Rabbit is a high speed scalable stream cipher with 128-bit key and a 64-bit initialization vector. It has passed all three stages of the ECRYPT stream cipher project and is a member of eSTREAM software portfolio. In this paper, we present a practical fault analysis attack on Rabbit. The fault model in which we analyze the cipher is the one in which the attacker is assumed to be able to fault a random bit of the internal state of the cipher but cannot control the exact location of injected faults. Our attack requires around $128-256$ faults, precomputed table of size $2^{41.6}$ bytes and recovers the complete internal state of Rabbit in about $2^{38}$ steps.

**Format-Preserving Encryption**

*Mihir Bellare and Thomas Ristenpart*

In the encryption of credit-card data as well as other applications, we may want to encipher in such a way that a certain property of the plaintext is preserved in the ciphertext. This paper initiates a treatment of this type of format-preserving encryption. We introduce a primitive that we call a general cipher that allows us to capture encryption preserving arbitrary formats. We specify an as-strong-as-possible notion of security for it that says that none but the desired property is leaked. We then provide an efficient construction of a general cipher that we call FPF.

**Herding, Second Preimage and Trojan Message Attacks Beyond Merkle-Damgaard**

*Elena Andreeva and Charles Bouillaguet and Orr Dunkelman and John Kelsey
*In this paper we present new techniques to analyze the structure of hash functions other than the Merkle-Damgaard construction. We extend the herding attack to concatenated hashes, zipper

hashes, and hash functions which iterate the message blocks several times. We follow with introducing the herding attack on tree hashes, showing how this attack can be applied in a completely different way. Furthermore, we show some new second preimage attacks (herding-based on the hash-twice, time-memory-data tradeoff based on tree hashes). Finally, we present a new type of attack - the trojan message attack, which allows for producing second preimages of unknown messages (from a small space) when they are appended with a fixed suffix.

**Highly Regular m-ary Powering Ladders**

*Marc Joye
*This paper describes new exponentiation algorithms with applications to cryptography. The proposed algorithms can be seen as m-ary generalizations of the so-called Montgomery ladder. Both left-to-right and right-to-left versions are presented. Similarly to Montgomery ladder, the proposed algorithms always repeat the same instructions in the same order and so offer a natural protection against certain implementation attacks. Moreover, as they are available in any radix m and in any scan direction, the proposed algorithms offer improved performance and greater flexibility.

**Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES
**

*Florian Mendel and Thomas Peyrin and Christian Rechberger and Martin Schläffer*

In this paper, we propose two new ways to mount attacks on the SHA-3 candidates Grøstl, and ECHO, and apply these attacks also to the AES. Our results improve upon the original rebound attack. Using two new techniques, we are able to extend of the number of rounds in which available degrees of freedom can be used. As a result, we present the first attack on 7 rounds for the Grøstl-256 compression function, as well as an improved known-key distinguisher for 7 rounds of the AES and the internal permutation used in ECHO.

**Improved Integral Attacks on MISTY1**

*Xiaorui Sun and Xuejia Lai
*We present several integral attacks on MISTY1 using the $FO$ Relation. The $FO$ Relation is a more precise form of the Sakurai-Zheng Property such that the functions in the $FO$ Relation depend on 16-bit inputs instead of 32-bit inputs used in previous attacks, and that the functions do not change for different keys while previous works used different functions.

We use the $FO$ Relation to improve the 5-round integral attack. The data complexity of our attack, $2^{34}$ chosen plaintexts, is the same as previous attack, but the running time is reduced from $2^{48}$ encryptions to $2^{29.58}$ encryptions. %This improvement can greatly reduce the running time of the attack. The attack is then extended by one more round with data complexity of $2^{34}$ chosen plaintexts and time complexity of $2^{107.26}$ encryptions. By exploring the key schedule weakness of the cipher, we also present a chosen ciphertext attack on 6-round MISTY1 with all the $FL$ layers with data complexity of $2^{32}$ chosen ciphertexts and time complexity of $2^{126.09}$ encryptions. Compared with other attacks on 6-round MISTY1 with all the $FL$ layers, our attack has the least data complexity.

**Information Theoretically Secure Multi Party Set Intersection Re-Visited**

*Arpita Patra and Ashish Choudhary and C. Pandu Rangan
*We re-visit the problem of secure multiparty set intersection in information theoretic settings. In \cite{LiSetMPCACNS07}, Li et.al have proposed a protocol for multiparty set intersection problem with $n$ parties, that provides information theoretic security, when $t < \frac{n}{3}$ parties are corrupted by an active adversary having {\it unbounded computing power}. In \cite{LiSetMPCACNS07}, the authors claimed that their protocol takes six rounds of communication and communicates ${\cal O}(n^4m^2)$ field elements, where each party has a set containing $m$ field elements. However, we show that the round and communication complexity of the protocol in \cite{LiSetMPCACNS07} is much more than what is claimed in \cite{LiSetMPCACNS07}. We then propose a {\it novel} information theoretically secure protocol for multiparty set intersection with $n > 3t$, which significantly improves the "actual" round and communication complexity (as shown in this paper) of the protocol given in \cite{LiSetMPCACNS07}. To design our protocol, we use several tools which are of independent interest.

**More On Key Wrapping**

*Rosario Gennaro and Shai Halevi
*We address the practice of key-wrapping, where one symmetric cryptographic key is used to encrypt another. This practice is used extensively in key-management architectures, often to create an "adapter layer" between incompatible legacy systems. Although in principle any secure encryption scheme can be used for key wrapping, practical constraints (which are commonplace when dealing with legacy systems) may severely limit the possible implementations, sometimes to the point of ruling out any "secure general-purpose encryption." It is therefore desirable to identify the security requirements that are "really needed" for the key-wrapping application, and have a large variety of implementations that satisfy these requirements.

This approach was developed in a work by Rogaway and Shrimpton at EUROCRYPT 2006. They focused on allowing deterministic encryption, and defined a notion of *deterministic authenticated encryption* (DAE), which roughly formalizes "the strongest security that one can get without randomness." Although DAE is weaker than full blown authenticated encryption, it seems to suffice for the case of key wrapping (since keys are random and therefore the encryption itself can be deterministic). Rogaway and Shrimpton also described a mode of operation for block ciphers (called SIV) that realizes this notion.

We continue in the direction initiated by Rogaway and Shirmpton. We first observe that the notion of DAE still rules out many practical and ``seemingly secure'' implementations. We thus look for even weaker notions of security that may still suffice. Specifically we consider notions that mirror the usual security requirements for symmetric encryption, except that the inputs to be encrypted are random rather than adversarially chosen. These notions are all strictly weaker than DAE, yet we argue that they suffice for most applications of key wrapping.

As for implementations, we consider the key-wrapping notion that mirrors authenticated encryption, and investigate a template of Hash-then-Encrypt (HtE), which seems practically appealing: In this method the key is first "hashed" into a short nonce, and then the nonce and key are encrypted using some standard encryption mode. We consider a wide array of "hash functions", ranging from a simple XOR to collision-resistant hashing, and examine what "hash function" can be used with what encryption mode.

**More on the Security of Linear RFID Authentication Protocols**

*Matthias Krause and Dirk Stegemann
*The limited computational resources available in RFID tags implied an intensive search for light weight authentication protocols in the last years. The most promising suggestions were those of the $\textsf{HB}$-familiy ($\textsf{HB}^+$, $\textsf{HB}^{\#}$, Trusted$\textsf{HB}$, ...) initially introduced by Juels and Weis, which are provably secure (via reduction to the Learning Parity with Noise (LPN) problem) against passive and some kinds of active attacks. Their main drawbacks are large amounts of communicated bits and the fact that all known $\textsf{HB}$-type protocols have been proven to be insecure with respect to certain types of active attacks. As a possible alternative, authentication protocols based on choosing random elements from $L$ secret linear $n$-dimensional subspaces of $GF(2)^{n+k}$ (so called CKK-protocols) were introduced by Cicho\'{n}, Klonowski, and Kuty\l owski. These protocols are special cases of (linear) $(n,k,L)$-protocols which we investigate in this paper. We present several active and passive attacks against $(n,k,L)$-protocols, thereby giving some evidence that the security of $(n,k,L)$-protocols can be reduced to the hardness of the {\it learning unions of linear subspaces} (LULS) problem. We then present a learning algorithm for LULS based on solving overdefined systems of degree $L$ in $Ln$ variables. Under the hardness assumption that LULS-problems cannot be solved significantly faster, linear $(n,k,L)$-protocols (with properly chosen $n,k,L$) could be interesting for practical applications.

**New Cryptanalysis of Irregularly Decimated Stream Ciphers**

*Bin Zhang
*In this paper we investigate the security of irregularly decimated stream ciphers. We present an improved correlation analysis of various irregular decimation mechanisms, which allows us to get much larger correlation probabilities than previously known methods. Then new correlation attacks are launched against the shrinking generator with Krawczyk's parameters, LILI-$\amalg$, DECIM$^{\textit{v2}}$ and DECIM-{$128$} to access the security margin of these ciphers. We show that the shrinking generator with Krawczyk's parameters is practically insecure; the initial internal state of LILI-$\amalg$ can be recovered reliably in $2^{72.5}$ operations, if $2^{24.1}$-bit keystream and $2^{74.1}$-bit memory are available. This disproves the designers' conjecture that the complexity of any divide-and-conquer attack on LILI-$\amalg$ is in excess of $2^{128}$ operations and requires a large amount of keystream. We also examine the main design idea behind DECIM, i.e., to filter and then decimate the output using the ABSG algorithm, by showing a class of correlations in the ABSG mechanism and mounting attacks faster than exhaustive search on a $160$-bit (out of $192$-bit) reduced version of DECIM$^{\textit{v2}}$ and on a $256$-bit (out of $288$-bit) reduced version of DECIM-{$128$}. Our result on DECIM is the first nontrivial cryptanalytic result besides the time/memory/data tradeoffs. While our result confirms the underlying design idea, it shows an interesting fact that the security of DECIM rely more on the length of the involved LFSR than on the ABSG algorithm.

**New Results on Impossible Differential Cryptanalysis of Reduced Round Camellia-128**

*Hamid Mala and Mohsen Shakiba and Mohammad Dakhil-alian*

Camellia, a 128-bit block cipher which has been accepted by ISO/IEC as an international standard, is increasingly being used in many cryptographic applications. In this paper, using the redundancy in the key schedule and accelerating the filtration of wrong pairs, we present a new impossible differential attack to reduced-round Camellia. By this attack 12-round Camellia-128 without FL/FL-1 functions and whitening is breakable with a total complexity of about 2^116.6 encryptions and 2^116.3 chosen plaintexts. In terms of the numbers of the attacked rounds, our attack is better than any previously known attack on Camellia-128.

**On Repeated Squarings in Binary Fields**

*Kimmo U. Järvinen*

In this paper, we discuss the problem of computing repeated squarings (exponentiations to a power of 2) in finite fields with polynomial basis. Repeated squarings have importance, especially, in elliptic curve cryptography where they are used in computing inversions in the field and scalar multiplications on Koblitz curves. We explore the problem specifically from the perspective of efficient implementation using field-programmable gate arrays (FPGAs) where the look-up table structure helps to reduce both area and delay overheads. We propose several repeated squarer architectures and demonstrate their practicability for FPGA-based implementations. Finally, we show that the proposed repeated squarers can offer significant speedups and even improve resistivity against side-channel attacks.

**Optimization strategies for hardware-based cofactorization**

*Daniel Loebenberger and Jens Putzka*

We use the specific structure of the inputs to the cofactorization step in the general number field sieve (GNFS) in order to optimize the runtime for the cofactorization step on a hardware cluster. An optimal distribution of bitlength-specific ECM modules is proposed and compared to existing ones. With our optimizations we obtain a speedup between 17% and 33% of the cofactorization step of the GNFS when compared to the runtime of an unoptimized cluster.

**Practical Collisions for SHAMATA**

*Sebastiaan Indesteege and Florian Mendel and Bart Preneel and Martin Schlaeffer*

In this paper we present a practical collision attack on the SHA-3 submission SHAMATA. SHAMATA is a stream cipher-like hash function design with components of the AES, and it is one of the fastest submitted hash functions. In our attack we show weaknesses in the message injection and state update of SHAMATA. It is possible to find certain message differences that do not get changed by the message expansion and non-linear part of the state update function. This allows us to find a differential path with a complexity of about $2^{96}$ for SHAMATA-256 and about $2^{110}$ for SHAMATA-512, using a linear low-weight codeword search. Using an efficient guess-and-determine technique we can significantly improve the complexity of this differential path for SHAMATA-256. With a complexity of about $2^{40}$ we are even able to construct practical collisions for the full hash function SHAMATA-256.

**Practical pseudo-collisions for hash functions ARIRANG-224/384**

*Jian Guo and Krystian Matusiewicz and Lars R. Knudsen and San Ling and Huaxiong Wang
*In this paper we analyse the security of the SHA-3 candidate ARIRANG. We show that bitwise complementation of whole registers turns out to be very useful for constructing high-probability differential characteristics in the function. We use this approach to find near-collisions with Hamming weight 32 for the full compression function as well as collisions for the compression function of ARIRANG reduced to 26 rounds, both with complexity close to $2^0$ and memory requirements of only a few words. We use near collisions for the compression function to construct pseudo-collisions for the complete hash functions ARIRANG-224 and ARIRANG-384 with complexity $2^{23}$ and close to $2^0$, respectively. We implemented the attacks and provide examples of appropriate pairs of $H,M$ values. We also provide possible configurations which may give collisions for step-reduced and full ARIRANG.

**Real Traceable Signatures**

*Sherman S.M. Chow*

Traceable signature scheme extends a group signature scheme with an enhanced anonymity management mechanism. The group manager can compute a tracing trapdoor which enables anyone to test if a signature is signed by a given misbehaving user, where the only way to do so for group signatures requires revealing the signer of all signatures. Nevertheless, it is not tracing in a strict sense. For all existing schemes, $T$ tracing agents need to recollect all $N'$ signatures ever produced and perform $RN'$ ``checks'' for $R$ revoked users. This involves a high volume of transfer and computations. Increasing $T$ maximizes the degree of parallelism for tracing but also the probability of ``missing'' some signatures.

We propose a new and efficient way of tracing -- the tracing trapdoor allows the reconstruction of tags such that each of them can uniquely identify a signature of a misbehaving user. Identifying $N$ signatures out of the total of $N'$ signatures ($N << N')$ just requires the agent to construct $N$ small tags and send them to the signatures holder. $N$ here gives a trade-off between the number of unlinkable signature a member can produce and the efforts for the agents to trace the signatures. We present schemes with simple design borrowed from anonymous credential systems, which are secure in random oracle model and in common reference string model respectively.

**Weak Keys of the Block Cipher PRESENT for Linear Cryptanalysis**

*Kenji Ohkuma*

The block cipher PRESENT designed as an ultra-light weight cipher has the 31-round SPN structure with S-box layers with 16-parallel 4-bit S-boxes and diffusion layers with a bit permutation. The designers evaluated the maximum linear characteristic deviation is not more than $2^{-43}$ for 28 rounds and concluded that the linear cryptanalysis is not vulnerable to PRESENT. But we have found that 32% of PRESENT keys are weak for linear cryptanalysis, and the linear deviation can be much larger than the linear characteristic value by multi-path effect. And we evaluated that a 28-round path with a linear deviation $2^{-39.3}$ for the weak keys. Furthermore, we found that the linear cryptanalysis is applicable up to 24-round reduced version of PRESENT for the weak keys.