cryptanalyse.theory.txt

                  
   CRYPTANALYSE   
                  


Adversary models :
  - assumptions faites pour déclarer qu'un algo est secure ou non 
  - détermine un niveau de sécurité
  - provable security : secure selon un adversary model donné, avec preuve théorique
  - types :
    - model où adversary est computationnaly unbounded
      - perfect security : unconditional security + confusion parfaite
      - information theoretic / unconditional security
      - security exige mêmes requirements que One-TP (seul algo theoretically secure) : 
        - truly random clef
        - secure channel
        - une unit de clef utilisée qu'une fois pour une unit du plaintext :
            - donc clef aussi grande que plaintext et pas réutilisée
    - model où computional power de l'adversary est désigné de manière non concrète mais mathématique selon une fonction
      polynomiale
        - complexity-theoretic security : 
          - fonction désignant le meilleur break est mathématiquement < celle du computationnal power, pour toute variable
    - standard/bare/plain model : 
      - adversary computationnaly bounded
      - ressources :
        - temps
        - mémoire
        - data : nombre de plaintexts ou ciphertexts requis
      - types : 
        - "infeasible" / "computationnaly secure" / practical security :
          - crackable théoriquement, mais pas dans la pratique à cause du temps requis, et selon une timeframe donnée
            - peut aussi définir selon non une timeframe, mais des ressources données
          - Work factor : Wᵈ, temps requis pour cracker, avec computationnal power évoluant avec temps
            - peut être de manière absolue, ou marginale (à chaque permutation)
            - une attaque réduisant bits of security, mais ayant un plus fort work factor n'est donc pas un break
          - Historical work factor : W͞ᵈ, temps requis pour cracker, avec computationnal power d'un temps donné (figé)
        - provable secure :
          - si infeasible parce que basé sur un "hard problem" 
        - semantically secure :
          - computationnaly secure, mais ne prend pas en compte CCA
          - équivaut à IND-CPA
          - considéré pas assez
    - black-box/oracle model : adversary ne connaît pas l'une des primitives du cryptographic mechanism (représenté comme un oracle), mais connaît le mechanism.
      La primitive a des assumptions (par ex., être secure, etc.)
        - ex : one-way compression function basée sur un block cipher. Pour analyser si mechanism est secure, assume que le
          block cipher est un oracle secure.
    - random oracle model : ajoute l'assumption que l'une des fonctions est un random oracle, c'est-à-dire un PRNG avec une
      distribution parfaitement uniforme
    - PKI utilise un model déclarant les certificate authorities sont trusted
    - ad-hoc model :
        - suppose que telle ressource d'un adversary est limitée (par exemple son temps disponible)
        - heuristic security
        - considéré pas assez 
    - limitation à une propriété indésirable :
      - malleability
      - ciphertext indistinguishability

Malleability : 
  - pour un m₁ inconnu ou peu-connu et un c₁ connu, forger un c₂, tel que Dᵈ(c₂) déchiffre vers un m₂ meaningful et non-suspect
  - peut être fait selon CPA, CCA1 ou CCA2 (NM-CPA, NM-CCA1, NM-CCA2)
  - peut être sur des hash functions ou sur algos sym.
  - protection contre CCA1 ou inférieur n'implique pas protection contre malleability
  - protection contre CCA2 implique protection contre malleability
  - indésirable en général, sauf pour homomorphic ciphers
  - ex :
    - sur un simple stream cipher xorant la keystream, xor le ciphertext revient à xor le plaintext
    - si l'on connaît quelques propriétés du plaintext, on peut le xor de manière avantageuse pour un attaquant

Homomorphic cipher :
  - cipher, où une opération sur c, implique une opération identique ou closely-related sur m
    - en général il s'agit de c Opération Eₑ(m₂), qui équivaut à faire m₁ Opération m₂
    - est donc malleable par design
  - permet de manipuler le plaintext sans avoir à le déchiffrer
    - si plaintext a format précis, permet bonne manipulation
  - applications : voting schemes, secure cloud computing (serveur compute données, sans pouvoir les déchiffrer), PIR

Ciphertext indistinguishability :
  - étant donné c₁, impossible de deviner que c₁ a plus de chance de venir de m₁ que de m₂
  - peut être :
    - under CPA (IND-CPA)
      - c₁ est obtenu par un m₁ choisi
    - under CCA1 (IND-CCA)
      - m₁ est obtenu par un c₁ choisi (non-adaptive)
    - under CCA2 (IND-CCA2)
      - m₁ est obtenu par un c₁ choisi (adaptive)
  - si est l'un, les autres inférieurs sont compris (ex : si IND-CCA -> IND-CPA)
  - IND-CPA implique une semantic security, et inversement
  - si NM-CPA, alors IND-CPA, mais pas forcément IND-CCA2
  - IND-CCA2 implique NM-CCA2, et inversement

Unicity distance :
  - entropie/longueur minimale du ciphertext pour que, selon un nombre de clef donné et un algo donné, pour l'ensemble des
    clefs possibles (bruteforce), un seul plaintext soit probable (et non possible -> intelligible).
  - en d'autres termes, taille minimale du ciphertext pour permettre une attaque selon le perfect security model
  - est une contre-mesure contre bruteforce
  - l'unicity distance peut être ∞ : par ex., one-time pad, auquel cas bruteforce est impossible
  - ensemble des plaintexts probables : "ciphertext ambiguity"
    - si tous plaintexts probables : ambiguity maximale
      - empêche bruteforce
    - ex d'ambiguity maximale ;
      - One-Time Pad
      - ou algo :
        - sans break
        - avec :
          - taille plaintext est < taille clef, pour une clef donnée, non-réutilisée
          - distribution aléatoire uniforme
          - par conséquent, K couvre l'ensemble des P possibles

Attaques :
  - Certificational/theoretical attack : 
    - attaque diminuant degrés de sécurité sans rendre computationnaly insecure :
      - timeframe trop grande
      - data trop exigeantes pour une application réelle
      - mémoire demandées trop grande (très rarement le cas)
    - mais indiquant potentiels futurs attaques
  - Practical attack : attaque rendant computationnaly insecure

Hard problem :
  - assumptions qu'un problème mathématique est insoluble (en général de théorie des nombres) tel que :
      - integer factorization problem
      - discrete logarithm computation

Adversary actif/passif :
  - passive (eavesdropping), menaçant confidentialité
  - active (Byzantine), menaçant aussi authentication et intégrité

Break :
  - pour un adversary model donné, avoir des bits de security < ceux maximum de ce model
    - pour algo symétrique : bits de security maximum est brute-force => key-length
    - pour collision-free hash function : bits de security maximum est brithday attack => key-length * 2
    - pour algo asymétrique : ???
    - pour PRNG : ???
  - Pour éviter break :
    - Diffusion parfaite + Confusion parfaite
        - possible de baser la confusion en général basée sur des computationnal hardness assumption : problème math non résolus
  - break de rounds :
    - un break peut ne cibler qu'un nombre limité de rounds d'un block cipher
      - revient à dire : si algo n'utilisant que n rounds, telle serait l'attaque
    - n'implique théoriquement aucun break sur algo utilisant un nombre de rounds supérieur
    - cependant, souvent nombre de rounds broken augmente, et donc il faut se méfier

But d'une attaque :
  - deviner algo
    - aujourd'hui plupart des algos sont connus (security by design)
    - cependant des algos peuvent rester secrets :
      - security-in-depth :
        - NSA suite A cryptography
      - security through obscurity, par exemple algos propriétaires
  - deviner plaintext
    - cependant, on cherche souvent plutôt à cracker la clef
  - deviner clef

Algos connus :
  - possibilités :
    - émettre série d'hypothèses sur l'algo
      - dont techniques fonctionnant sur un ensemble d'algos
    - deviner l'algo

But d'une attaque selon les attack model :
  - dans tous le cas, utilise une clef inconnu K (but de l'attaque), et non sa propre clef
  - il s'agit d'attaques passives, attaquant seulement confidentialité
  - + les ciphertexts ou plaintexts obtenus sont petits et peu nombreux, + dur de cracker
  - ciphertexts et plaintexts peuvent être en partie ou en entier.

Conséquence de l'attaque :
  - total break : devine la clef
  - global deduction : découvre une fonction D' et E' équivalents à Dᵈ et Eₑ, mais sans deviner d ou e
  - instance/local deduction : découvre le plaintext en partie/entier (ou ciphertext)
  - information deduction : découvre propriété du plaintext (ou ciphertext)
  - distinguishing algorithm : possibilité de distinguer l'algo d'une permutation aléatoire

Attack model/type :
  - infos disponibles pour une attaque 
  - du moins facile, avec le moins d'infos, au plus facile avec le plus d'infos :
   - ciphertext only attack (COA) / known ciphertext attack : peut obtenir des ciphertexts chiffrés avec K
   - known/given plaintext attack (KPA) : ciphertext + plaintext (imposé) : peut obtenir des plaintexts ("crib") et leur ciphertext chiffrés avec K
      - autre cas, connaît : 
        - une partie de plaintext car suit toujours un format
        - une propriété statistique car par ex., est un texte intelligible
   - chosen plaintext attack (CPA) : ciphertext + plaintext (de son choix) : peut choisir des plaintexts, et on obtient les ciphertexts chiffrés avec K
   - chosen ciphertext attack (CCA) : choisit le ciphertext et l'algo donne le plaintext
     - il faut pour cela avoir un decryption oracle, qui connaisse clef secrète
     - souvent dans hardware crypto tamper-resistant
     - autre ex. de but pratique dans la réalité : accès temporaire au déchiffrement avec la clef, sans la connaître.
  - par conséquent, si protection contre CCA, protection aussi contre CPA, KPA et COA, et ainsi de suite.
  - à noter que but de ces attaques est de trouver la clef, et s'applique aux algos sym. :
    - pour hash functions, différentes attaques, car but est d'inverser le hash ou créer des collisions
    - pour MAC et digital signatures, différentes attaques, car but est de créer une pair (m1,d1) valide, sans connaître
      private key

Attaques actives/passives :
  - attaque peut être :
    - adaptive : 
        - nouveau ciphertext ou plaintext demandé/imposé dépend du dernier obtenu
        - que pour CPA et CCA donc (et collision attaques pour hashs, et chosen-message attack pour MAC/digital signatures)
    - non-adaptive/statique/batch: 
        - contraire (obtenu au hasard, ou selon un critère autre que le dernier obtenu)
  - plus difficile de se prémunir d'une attaque adaptive => si protection contre adaptive attack, protection contre
    non-adaptive attacks
  - non-adaptive CCA dont appelés lunchtime/midnight/indifferent attacks, ou CCA1, et adaptive CCA sont appelés CCA2

But de beaucoup d'attaques est de trouver des patterns :
  - par conséquent, un ciphertext avec une uniformité aléatoire parfaite est immunisé contre celles-ci

Frequency analysis :
  - principe :
    - ciphertext-only attack pour détecter une transposition, ou cracker une substitution
    - sur une grammaire donnée du plaintext (par exemple une langue, un format de fichier, etc.)
    - unités utilisés :
      - sur lettres isolées
      - sur groupe de lettres (digrams, trigrams, etc.). Par exemple, q souvent suivi de u.
      - variable
    - possibilité de prendre en compte la place de l'unité dans le mot (si l'on peut deviner les espaces et la ponctuation)
  - contre-mesure :
    - utilisation d'homophones ou équivalent (ex : homophonic cipher)
    - polygraphic substitution
    - polyalphabetic substitution
    - ajout de nulls dans le plaintext

Informatique quantique :
  - augmente tellement la force computationnelle de brute-force attaques que :
    - diminue extrêmement les bits de sécurité d'algo asymétrique non-elliptique
    - divise par deux les bits de sécurité de symmetric algo et asymétrique elliptique

Attaques :
  - on peut ne cracker qu'une partie de la clef, mais cela peut :
    - faire deviner une partie du plaintext
    - aider un prochain crackage
  - si 100% de la clef n'est pas utilisée lors du chiffrement :
    - on ne peut en deviner qu'une partie.

Toy cipher : 
  - cipher présenté par un cryptanalyste pour des raisons purement théoriques de démonstration, et non pour être utilisé

Détecter usage de chiffrement :
   - détecter distribution random uniforme, par analyse statistique
     - cependant, compressed data (dont .jpg) random aussi
       - cependant, peut détecter header
         - cependant, chiffrement parfois header aussi (ex : PGP, PEM)
            - cependant peut mettre un faux header de compression pour contourner détection

Entities/parties :
  - personne logique (pouvant correspondre à personne réelle) dans une situation de communication
  - noms souvent utilisés :
   -   Alice  --------- Mallory/Oscar/Marvin/ ---------> Bob
      (sender)    +     Mallet/Moriarty/Trudy         (receiver)
                  |     (active adversary,                | 
                  |      man-in-the-middle)               |       
                 Eve                                    Trent       
            (passive adversary,                   (trusted arbitre,
              eavesdropper)                     certificate authority)
               
               Peggy/Pat --> Victor/Vanna
               (prouve)      (vérifie)
     
     Carol/Carlos/     Chuck          Gordon     Isaac  Justin/Julian  Steve    Zoe
     Charlie          (malicious 3rd (gvt agent) (ISP)  (Système       (Stego)  (Dernière personne
   (3rd participant)  participant)                      judiciaire)             de la chaine de crypto)