Background

Lightweight Crypto and PRESENT

Lightweight Cryptography

• Low footprint in hardware and software

• i.e. small size & low cost

The Lightweight Cryptography Zoo

• TEA (Wheeler et al. 1994)
• XTEA (Needham et al. 1997)
• mCrypton (Lim et. al. 2005)
• HIGHT (Hong et al. 2006)
• SEA (Standaert et al. 2006)
• CLEFIA (Shirai et al. 2007)
• PRESENT (Bogdanov et al. 2007)
• Hummingbird (Engels et al. 2010)
• KLEIN (Gong et al. 2011)
• SIMON (NSA)(Beaulieu et al. 2013)
• SPECK (NSA)(Beaulieu et al. 2013)
• PICO (Bansod et al. 2016)
• QTL (Li et al. 2016)

Present

• "PRESENT: An Ultra-Lightweight Block Cipher" (Bogdanov et al. 2007)

• ISO/IEC standard since 2012

• Block Cipher

• 31-round Substitution-Permutation Network (SPN)

• 64-bit block size

• 80-bit or 128-bit key

Attacks on Present

• Differential (Wang 2008)
• Algebraic + differential (Albrecht et.al 2009)
• Statistical Saturation (Collard et al. 2009)
• Linear (Okhuma 2009)
• Multidimensional Linear (Cho 2010)
• Truncated Differential (Blondau et al. 2014)
• Known-Key (Blondau et al. 2015)
• Biclique (Jeong et al. 2012)
• Biclique (Sereshgi et al. 2015)

Background

PRESENT and Linear Cryptanalysis

Structure of PRESENT

Round

Linear Cryptanalysis

• Approximate the S-Boxes with linear equations $$\pi(\alpha, \beta) = \alpha \cdot x \oplus \beta \cdot S(x) = 0$$

• That hold with prob $p = \frac{1}{2}+\epsilon$

Linear trails

$$ \alpha \cdot P \oplus \beta \cdot C \oplus \gamma \cdot K = 0 $$

Success probability?

• The best approximation: $\epsilon = 2^{-42}$

• Rule of thumb: need $\frac{1}{\epsilon^2}$ plaintexts

• => $2^{84}$ plaintexts needed to have any chance of finding the right subkey faster than brute force

• More than $2^{64}$ in plaintext space $\Rightarrow$ secure against linear cryptanalysis!

The Attack

Multidimensional linear cryptanalysis

Use more than 1 linear approximation

But how to combine them?

• M. Hermelin, K. Nyberg and J. Cho

• Instead of a bias for your single approximation

• "Capacity"

Capacity

$$ C_p = \sum_i \frac{(p_i - u_i)^2}{u_i} $$

Magic Formula from

"Multidimensional Extension of Matsui’s Algorithm 2"

(Hermelin, M., Cho, J., Nyberg, K. 2009)

$$ N = \frac{\sqrt{4 M \alpha_{\chi^2}} + 4 \Phi^{-2}(2 P_s - 1)}{C_p} $$

or

$$ \alpha_{\chi^2} = \frac{(N C_p - 4\Phi^{-2}(2 P_s -1))^2}{4M} \approx 8 $$

Attack on 26 rounds PRESENT

• Advantage $\alpha_{\chi^2} = \log_2(\frac{2^{32}}{2^0}) = 32$ bits

• With prob $P_s = 0.95$

• Have $M = 9 \cdot (2^8-1)$ linear approximations

• With capacity $C_p^{[25-2]} = 2^{-55.38}$

$$ N = \frac{\sqrt{4 M \alpha_{\chi^2} \cdot} + 4 \Phi^2(2 P_s - 1)}{C_p} \approx 2^{64.98} $$

• But only $2^{64}$ plaintexts in the whole plaintext space! :'(

Attack on 26 rounds PRESENT

• Use full plaintext space $N = 2^{64}$

• Success prob $P_s = 0.95$

• Have $M = 9 \cdot (2^8-1)$ linear approximations

• With capacity $C_p^{[25-2]} = 2^{-55.38}$

$$ \alpha_{\chi^2} = \frac{(N C_p - 4\Phi^{-2}(2 P_s -1))^2}{4M} \approx 8 $$

• $rank(K_r) \leq 2^{32-8} = 2^{24}$

  • $\Rightarrow$ "Time complexity": $2^{24} \cdot 2^{(80-32)} = 2^{72}$

Results

Theoretical results

Although still unrealistic, less than the predicted $2^{84}$

Conclusions

• The S-boxes and bit permutations are designed for efficient hardware implementation

• Consequences for security

• Proven to be secure against linear and differential cryptoanalysis?

• Not multidimensional linear analysis

• Ok... but com'on! 26 out of 31 rounds and $2^{64}$ known plaintexts? so what?
• Fast forward a few years:
  • (Blondau 2014): Truncated Differential on 26 rounds
  • (Blondau 2015): Known-Key Distinguisher on Full PRESENT
  • Probably shouldn't use PRESENT as a primitive for Hashing: