MIF29 cryptographie et sécurité
Introduction à la sécurité
Romuald THION
Semestre printemps 2023-2024 UCBL
Introduction à la sécurité
Objectifs de la seconde partie de MIF29
- 👉 Placer la cryptographie dans le contexte général de la sécurité,
- 👉 Apprécier les limites des solutions cryptographiques,
- 👉 Utiliser et critiquer des bibliothèques cryptographiques,
- 👉 Utiliser et critiquer des solutions d’authentification.
Définitions de la sécurité
Notion de risque
Évaluer la sécurité = évaluer un risque. Exemples.
- 🚧 Gestion de projet :
- e.g., ne pas livrer, livrer en retard
- ☢️ Sûreté de fonctionnement et des personnes :
- e.g., accident
- 💵 Finance :
- e.g., perte de capital
- 💻 sécurité des systèmes informatiques
- ❓
Définition EBIOS du risque
Un risque, au sens de la méthode EBIOS, est le produit :
- 😨 d’événements redoutés,
- mesurés par une gravité
- échelle : négligeable, limitée, importante, critique.
- 🧑💻 de scenarii de menaces,
- mesurés par une vraisemblance
- échelle : minime, significative, forte, maximale.
L’évaluation du risque
Les métriques CIA, ce qu’on va évaluer :
- 🔒 Confidentiality (confidentialité)
- e.g., public, limité, secret
- ✅ Integrity (intégrité)
- e.g., détectable, maîtrisé, intègre
- ⚙️ Availability (disponibilité)
- e.g., 99.99%
La confidentialité et l’intégrité sont des propriétés garanties en partie par la cryptographie.
Le traitement du risque
- L’éviter, id est changer de contexte,
- Le réduire, id est diminuer l’impact ou la vraisemblance (à l’aide de mesures),
- Le prendre (voire l’augmenter), id est assumer les conséquences,
- Le transférer, id est faire assumer la responsabilité, s’assurer.
Les mesures techniques, comme la cryptographie, constituent un moyen de traiter les risques en le réduisant. Garde au technosolutionnisme !
Les vulnérabilités : CWE, CAPEC et CVE
CWE™ is a community-developed list of software and hardware weakness types. It serves as a common language, a measuring stick for security tools, and as a baseline for weakness identification, mitigation, and prevention efforts.
CAPEC™ helps by providing a comprehensive dictionary of known patterns of attack employed by adversaries to exploit known weaknesses in cyber-enabled capabilities. It can be used by analysts, developers, testers, and educators to advance community understanding and enhance defences.
https://cve.mitre.org/ ou https://www.cve.org/
The mission of the CVE® Program is to identify, define, and catalog publicly disclosed cybersecurity vulnerabilities. There is one CVE Record for each vulnerability in the catalog.
Exemples relatifs à la cryptographie
Exemples de vulnérabilités associées :
- CWE-780
- CWE-208
Sécurité et cryptographie
Kerckhoffs’s principle [The system] should not require secrecy, and it should not be a problem if it falls into enemy hands.
La taille ça compte
e.g. Crypto++ 5.6.0 Benchmarks, 2009
- AES/CCM 28.6 cycles per byte
- RSA 1024/2048
- Encryption: 140.000/290.000 cycles
- Decryption: 2.680.000/11.120.000 cycles
- Signature: 2.710.000/11.080.000 cycles
- Verification : 130.000/290.000 cycles
> openssl speed rsa
sign verify sign/s verify/s
rsa 1024 bits 0.000099s 0.000006s 10136.7 160581.8
rsa 2048 bits 0.000665s 0.000020s 1504.1 49263.4
> openssl aes
The 'numbers' are in 1000s of bytes per second processed.
type 1024 bytes 8192 bytes 16384 bytes
aes-128-cbc 696482.13k 691938.10k 706554.54k
aes-192-cbc 589946.54k 590230.87k 590812.50k
aes-256-cbc 497920.70k 495173.19k 501377.80k🚀 Ainsi, chiffrer avec aes-128-cbc prend environ 4.3
cycles par byte (grâce à AES-NI)
(pour un message de 1kB)
Si on veut chiffrer 2^{128} messages
de 1kB avec aes-128-cbc au rythme de 700.000 par seconde
\approx 2^{19}, il faudrait 2^{109} secondes ! 💤
Ordres de grandeur
- Années/secondes
- une année : 31.557.600 \approx 2^{25} secondes,
- 2^{32} secondes \approx 136 années
- Age de
l’univers observable :
- 13.8 \times 10^{9} \approx 2^{34} années
- soit 2^{59} secondes
- Nombre
d’atomes d’hydrogène dans l’univers :
- 10^{80} \approx 2^{266} atomes
Quelles tailles pour les clefs ?
🔖 Voir aussi https://www.keylength.com/.
Définitions mathématiques de la sécurité
Le but est de prouver qu’un crypto-système est sûr (par réduction) ou, à l’inverse, de démontrer qu’une attaque est réalisable en pratique.
Semantic security
\mathrm{SSadv}^\star[\mathcal{A}, \mathcal{E}] = |Pr[W] - 1/2| où Pr[W] = Pr[\hat{b}=b] est la probabilité de gagner le jeu.
Definition 2.2 (semantic security). A cipher \mathcal{E} is semantically secure if for all efficient adversaries \mathcal{A}, the value \mathrm{SSadv}^\star[\mathcal{A}, \mathcal{E}] = \epsilon is negligible.
- efficient : Probabilistic Polynomial (Turing) Time
- negligible : pour tout c, \lim_{n \to \infty}f(n)\times n^c = 0 (Wikipedia)
On veut que la probabilité \epsilon soit astronomiquement faible.
textbook RSA n’est pas sémantiquement sûr
- \mathcal{A} a reçu la clef privée
- \mathcal{A} choisit deux messages m_0, m_1
- à la réception de c, \mathcal{A} calcule c_0 = E(pk, m_0)
- \mathcal{A} renvoie c = c_0
\mathrm{SSadv}^\star[\mathcal{A}, \mathcal{E}] = 1, il n’y a pas sécurité si le chiffrement à clef publique n’est pas randomisé !
Retour sur l’exercice 82 (TP2)
On a plusieurs problèmes :
- 🎲 pas de randomisation, les chiffrés sont prédictibles.
- 🔬 un espace réduit {49 \choose
6} = 13.983.816 \approx 2^{24}
- assez réduit pour permettre une attaque à la racine n-ième.
Voir démonstration.
Padding (ou plutôt hardening) pour RSA
- 🎲 Intégrer un aléa dans les messages
- assure que le message est de taille proche de \lambda
- rend le chiffrement non déterministe
- 🔙 Lors du déchiffrement, retirer l’aléa
Optimal Asymmetric Encryption Padding est le mode recommandé (PKCS#1 v2.2). Attention aux failles des versions précédentes (PKCS#1 v1.5.) qui sont vulnérables !
Optimal Asymmetric Encryption - How to Encrypt with RSA
\mathcal{E}^{G,H}(m) = \mathcal{E}(m \oplus G(s) \mid \mid s \oplus H(m \oplus G(s)))
Théorème 4.1 (informel) sous les hypothèses que G: 2^{k_0} \to 2^{n} et H : 2^{n} \to 2^{k_0} sont des fonctions idéalement aléatoire, alors casser \mathcal{E}^{G,H} est aussi difficile que casser le chiffrement \mathcal{E} d’origine.
Signature
Un système de signature (G, S, V) est sûr si la probabilité \mathrm{SIGadv}[\mathcal{A}, \mathcal{S}] où de gagner le jeu avec V(pk , m, σ) = \mathsf{accept} et m \notin \{m_1, m_2, \ldots\} est négligeable.
textbook RSA ne permet pas la signature sûre
On inverse naïvement les rôles des clefs privées et publiques dans RSA: on définit S(sk, m) = m^d et V(pk, m, \sigma) = \mathsf{accept} \text{ iff } \sigma^e = m.
On montre que \mathcal{A} peut forger une signature pour m de son choix :
- \mathcal{A} envoie m' = r^e . m, avec r aléatoire
- \mathcal{A} reçoit \sigma' = m'^d = (r^e . m)^d = r . m^d
- \mathcal{A} calcule \sigma' / r = m^d, une signature valide de m 💥
Démonstrations
Collision de hash
Voir TP introduction à la sécurité.
Factorisation de Fermat
Oracle de parité
Démonstration à l’Oracle de parité, pré-figurative de l’attaque de Bleichenbacher sur PKCS#1 v1.5.
Conclusion
Slogan Don’t roll your own crypto
Anyone can invent an encryption algorithm they themselves can’t break; it’s much harder to invent one that no one else can break. Bruce SCHNEIER
Sécurité des implémentations
Objectif général des attaques précédentes :
- Réduire l’ordre de grandeur de l’espace de
recherche,
- peut rendre praticable si le paramètre de sécurité est trop bas
- Rendre non négligeable l’avantage de l’attaquant
- jusqu’à casser le système (e.g., signature naïve RSA)
D’autres vulnérabilités peuvent survenir dans l’implémentation :
- par erreur, mauvaise conception
- en sortant du modèle mathématique de l’attaquant
Exemples de vulnérabilités d’implémentation
CVE-2015-9235: verification Bypass in jsonwebtoken
https://github.com/advisories/GHSA-c7hr-j4mj-j2w6
Versions 4.2.1 and earlier of jsonwebtoken are affected by a verification bypass vulnerability. This is a result of weak validation of the JWT algorithm type, occurring when an attacker is allowed to arbitrarily specify the JWT algorithm.
Side-channel attacks
Side-channel analysis is a class of cryptanalytic attacks that exploit the physical environment of a cryptosystem to recover some leakage about its secret
Masking against Side-Channel Attacks: A Formal Security Proof, Emmanuel Prouff and Matthieu Rivain, EUROCRYPT 2013.
Timing attack sur exponentiating by squaring (a.k.a. square-and-multiply ou binary exponentiation).
def fast_power(base, power, modulo):
result = 1
while power > 0:
if power % 2 != 0:
power = power - 1
result = result * base
power = power // 2
base = (base * base) % modulo
# assert result == pow(base, power, modulo)
return resultLe nombre de multiplications dépend du nombre de bits à 1 dans l’écriture binaire de l’exposant
Dans le cas du déchiffrement RSA, l’exposant est la clef secrète :
- Temps d’exécution dépendant du secret,
- Consommation électrique dépendante du secret,
- Prédiction de branchement dépendante du secret (cf https://meltdownattack.com/)
🔥 The devil is in the details : démonstration sur
fast_power et compare (TP).
Contre-mesures
Extrait de Algorithms, Key Size and Protocols Report (2018), H2020-ICT-2014, ECRYPT-CSA.
- Constant-time algorithms
- Constant power consumption
- Reduce secret data-dependent branches (pas de if sur un secret)
- Reduce secret data-dependent lookups (S-BOX en cache pour AES)
- Masking
Mais ça peut être difficile à réaliser exemple en C.
10 Rules for a good Crypto API?
- Easy to learn, even without crypto background
- Easy to use, even without documentation
- Hard to misuse. Incorrect use should lead to visible errors
- Hard to circumvent errors – except during testing/development
- Easy to read and maintain code that uses it
- Sufficiently powerful to satisfy non-security requirements
- Easy to extend Hard to change/override core functionality
- Appropriate to audience – this means people with no crypto experience
- Assist with/handle end-user interaction
- However, where possible integrate into standard APIs so normal developers never have to interact with crypto APIs in the first place