hash_function.theory.txt

                                  ┏━━━━━━━━━━━━━━━━━━━━┓
                                  ┃   HASH FUNCTIONS   ┃
                                  ┗━━━━━━━━━━━━━━━━━━━━┛

Soit :
  - p₁ et p₂ des plaintexts
  - H(p) la fonction de hashage
  - d₁ et d₂ leur digests/hash value

Hash function :
  - fonction produisant une hash value pour un input donné

One-way function :
  - hash function étant first-preimage-resistant : "computationnally infeasible" de trouver x en connaissant f(x)
  - peuvent utiliser comme input additionnel e et d :
    - non-keyed hash function : sans clef
      - "plain" hash function : avec rien
        - peut être cryptographic ou non
      - one-way compression function : avec un hash précédent (nombre fixe au début)
    - keyed hash function : une clef
        - MAC : clef symmétrique (PSK), cf MAC.txt
        - digital signature : paire clef privée/clef publique
  - exemple 1 :
    - f(x) = 3^x % n, où r est un très grand nombre premier
    - r est connu, x est la clef, f(x) ce qu'on recherche
    - est aussi une bijection
  - exemple 2 :
    - soit :
      - p et q deux très grands nombres premiers (+ 100 chiffres)
      - r leur produit
      - f(x) = x³ % r
    - et :
      - p et q sont inconnus
      - f(x) est connu, et on recherche x
    - prend beaucoup de temps, car il est difficile de trouver les facteurs de r ("integer factorization problem")
    - une fois p ou q connu (et donc l'autre aussi), bien plus rapide
    - si ni p - 1, ni q - 1 n'est divisible par 3, il s'agit d'une bijection également et on peut retrouver f(x)

One-way compression function :
  - non-keyed mais cryptographic hash function où f(p₁, h₁) -> d₁
    - h₁ est l'IV (fixed value) au début, puis un hash précédent
    - h₁ doit avoir les mêmes propriétés de non-prédictabilité et non-inversion que p₁
    - utilisé dans Merkle–Damgård construction ou ses variantes
  - d₁ est de même taille que p₁ ou h₁ :
  - en général basé sur un block cipher :
    - F est Cipher et h₁ ou p₁ (selon le hash-mode of operation) est e
    - doit alors utiliser un hash-mode of operation
    - mais pourrait en principe utiliser une one-way function fondée sur un problem tel qu'integral factorization problem

Merkle-Damgård construction :
  - cryptographic mechanism permettant de construire une hash function à partir d'une one-way compression function, avec comme
    avantages :
    - permette hash de message de taille variable
    - réduire collision-resistance de la hash function à celle de F à condition d'utiliser un padding scheme MD-compliant (cf
      crypto_padding.txt)
    - provoquer diffusion via avalanche effect
  - fonctionnement :
    - divise plaintext en p₁,...,pₙ
    - ajoute un padding scheme (appelé "MD-strengthening")
    - applique f(p₁,h₁) à chaque bloc du plaintext (hash-round)
    - utilise un hash-mode of operation entre chaque F si F est un block cipher
    - utilise une finalization fonction F' sur l'output final pour augmenter sa diffusion, ou contraindre sa taille finale
  - utilisé par notamment MD5, SHA1, SHA2
  - problèmes :
    - susceptibles aux attacks spécifiques à cette construction :
      - length-extension attacks
      - herding attacks
    - mais des algos existent prenant en compte ces attaques, et étant resistant à elles.
    - multicollisions possibles via length extension

Variantes de Merkle-Damgård construction :
  - wide-pipe construction :
    - effectue deux Merkle-Damgård construction en parallèle (pas d'interaction), avec même plaintext, mais un IV différent.
    - pour le dernier block, merge les deux outputs (par ex. en tronquant moitié de chacun), et effectue dernier bloc
    - but : contre length-extension attack et multicollisions
  - fast-pipe construction :
    - effectue un seul Merkle-Damgård mais le feedback a des transformations supplémentaires :
           ----(hₙ)-----+
                        |          +-----(h'ₙ)-->
                      One-way      |                     One-way-compression function : comprend éventuels hash-mode of operat.
            pₙ ---> compression ---X--⊕--(hₙ)--->        X : splitte en deux
                     function         |
                                      |
           ----(h'ₙ)------------------+
    - but : comme wide-pipe construction, mais plus rapide
    - ressemble en fait à un Feistel network

Hash-mode of operation :
  - étudié selon l'Ideal Cipher Model :
    - black-box model supposant que F est un oracle, block cipher quelconque et secure (confusion et diffusion parfaite)
  - Hash-rate :
    - calcule le nombre de F nécessaire pour n bits d'input pour avoir n bits d'output
    - R = input_size / ( output_size * nombre ), où nombre est nombre de F nécessaire pour obtenir output_size.
  - types :
    - soit :
      - key_size celle de Cipher
      - output_size celle de Cipher
    - single-block-length compression function :
      - d₁ est même taille qu'input de F
      - exemples :
        - Davis-Meyer :
                     -----------------------+-------+
                                            |       |
                     Plaintext (key) ---> Cipher ---⊕---> Hash --->
          - découpe plaintext en bloc de taille key_size
          - ⊕ peut être une autre modular operation
          - Hash-Rate : key_size / output_size
          - problème :
            - time-point attack :
              - soit Cipher(p₁,h₁), où p₁ est le plaintext/key et h₁ le précédent hash :
                - pour tout p₁, soit h₂ == Cipher⁻¹(p₁,0)
                - alors Cipher(h₂) == 0
                - alors Cipher(h₂)⊕ h₂ == h₂
                - en connaissant plaintext, on peut donc trouver un hash précédent, qui fasse que hash présent soit égal à lui
              - cependant, n'est utilisé par aucune practical attack
          - utilisé par MD5, SHA-1 et SHA-2
        - Matyas-Meyer-Oseas :
                     -----------------+
                                      |
                                    (key)
                                      |
                     Plaintext ---> Cipher ---⊕---> Hash --->
                          |                   |
                          +-------------------+
          - h₁ peut subir une transformation pour réduire sa taille à key_size
          - Hash-rate : 1
        - Miyaguchi–Preneel
                     -----------------+-------+
                                      |       |
                                    (key)     |
                                      |       |
                     Plaintext ---> Cipher ---⊕---> Hash --->
                          |                   |
                          +-------------------+
          - h₁ peut subir une transformation pour réduire sa taille à key_size
          - Hash-rate : 1
          - ⊕ est associatif, donc ⊕ désigne ici deux xor, dans l'ordre que l'on veut
          - Utilisé par Whirlpool
          - il existe une variante où plaintext est la clef, ayant alors mêmes propriétés que David-Meyer
    - double-block-length compression function : d₁ est double de taille qu'input de F (et F est basé sur un block cipher)

Trapdoor function :
  - one-way function, où :
    - l'on peut trouver effectuer f(x) (connaît donc e)
    - mais pas découvrir x en connaissant f(x) sans connaître une trapdoor information (soit d)
  - soit :
    - e == d
      - par ex., one-way compression function
    - e != d (mais souvent related), et impossible de trouver d à partir de e : algo asym.
      - on peut donc chiffrer, mais pas déchiffrer sans d
      - exemple : cf ex précédent : p et q sont d, et r est e

One-way permutation :
  - one-way function étant aussi une permutation

Cryptographic hash function :
  - hash function étant collision-resistant, ou au moins preimage-resistant

Non-invertible function :
  - comme one-way function, sauf que l'on peut deviner des valeurs probable m parmi M.
  - ex : x² = y, √y peut être x ou -x.

Consistent hashing:
  - associe each hash with a number from 1 to n, so that decreasing n doesn't invalidate the association from 1 to new n
  - used by memcached so that hashes are distributed to several servers, without cache mess if a server is added/removed

Buts :
  - non-keyed :
    - plain hash functions pour toute, cryptographic ou non, selon usage, sauf si précisé
    - vérifier intégrité (channel non-reliable) : checksum/MDC(Modification Detection Code)
      - Cas spéciaux :
        - check digits : en base décimale, et peut être computed de tête.
          - ex : dernier chiffre de l'ISBN d'un livre.
        - error correcting code : indique dans son propre corps, en cas d'erreur, une part des erreurs commises, permettant une correction sans nouvelle demande des data.
    - vérifier identité du plaintext (sans risque d'intégrité malicieuse pour le digest) :
      - pour avoir empreinte petite : fingerprint.
        - Cas spécial :
          - watermark : prouve un copyright ou empêche physiquement la copie, avec stéganographie (toujours cryptographic)
      - pour efficience : hash tables
      - pour besoin confidentiel : hash de passwords (toujours cryptographic)
  - keyed :
    - identité + message authentication :
      - (chiffrement symmétrique) MAC
    - identité + message authentication + entity authentication (donc aussi non-répudiation)
      - (chiffrement asymmétrique) digital signature

Digest/Tag/Hash value :
  - produit d'une hash function

Attaques une hash function (du plus facile au plus dur) :
  - différents de COA/KPA/CPA/CCA, car but est pas de trouver la clef, mais d'inverser la hash function ou créer des collisions
  - types :
    - First preimage attack :
      - à partir d'un d₁ donné, trouver un p₁ viable
      - contraire : first preimage resistance / one-way function
      - =~ COA
      - implique que digest doit être diffus
    - Second preimage attack :
      - à partir d'un p₁ donné, trouver un p₂, tel que d₁ == d₂
      - contraire : second preimage resistance / weak collision resistance
      - =~ KPA
      - implique qu'il faut qu'il y ait confusion entre le rapport entre plaintext et digest
    - Collision attack :
      - à partir d'un p₁ choisi, trouver un p₂, tel que d₁ == d₂
      - contraire : collision resistance / strong collision resistance / collision-free
      - =~ CPA
      - sensible au "birthday attack", qui fait que le digest, par rapport au second preimage attack, doit être 2 fois plus grand pour être strong-collision resistant
      - un break doit être plus rapide qu'une brute-force par birthday attack, donc 2^(n/2) (et non 2^n)
    - Autres attaques, plus simples encore :
      - spécifique aux Merkle-Damgård hash functions :
        - Chosen prefix collision attack / length-extension attack :
          - à partir d'un p₁ et p₂ choisis, trouve un p₃, tel que H(p₁∥ p₃) == H(p₂∥ p₃)
        - Herding attack :
          - après avoir trouver une collision pour p₂, trouver un suffixe p₃, tel que pour tout p₄, H(p₄∥ p₃) == H(p₂)
  - Preimage attacks sont les deux premières, collisions attack les deux dernières
  - La résistance signifie qu'il est infeasible d'attaquer.
  - multicollisions : signifie que si collision attack avec une collision, plus facile de trouver une seconde

But d'une attaque par collision :
  - substituer un p₂ illégitime à la place d'un p₁ légitime, ayant le même hash. Exemples :
    - password ayant le même hash
    - document p₂ ayant le même hash qu'un document p₁ digitally-signed (dont le hash a été chiffré avec une clef privée), permet de signer aussi p₂.
Qualité d'une attaque par collision :
  - meaningful : le p₂ substitué doit avoir un sens et une utilité pour l'attaquant
  - non suspect : le p₂ doit sembler légitime et ne pas éveiller de doute (par exemple, ne pas être d'apparence aléatoire)
  - reusable : peut être réutilisé pour une autre attaque. Cf rainbow tables

Avalanche effect :
  - pas souhaité dans certaines applications, où plaintext doit être similaire à hash, comme fingerprints et watermarks.

Utiliser plusieurs digests avec plusieurs algos pour un seul message :
  - pour éviter collision si l'un des algo est broken

Pigeonhole principle :
  - soit deux ensembles N et M, où taille de N > taille de M
  - si chaque m correspond à un n,
  - alors au moins un m doit avoir deux n possibles.
  - Conséquences : si taille du plaintext > taille du hash (quasi toujours le cas), alors collusions toujours possibles.
Birthday attack :
  - collision attack par brute-force
  - chaque essai p₂,...,pₙ pour trouver une collusion avec p₁, cherche donc aussi une collusion avec les précédents pₙ.
  - Ainsi, il faut juste 2^(n/2) essais et non 2^n (n = longueur du digest en bits)
  - Le digest doit donc être deux fois plus grand pour être strong collision resistant que pour être weak collision resistant.
  - si mauvaise "balance" (diffusion) de la hash function, réduit la time complexity pour l'attaque


HASH LIST ==>                     #Result of hashing a list of values, where each value gets its own hash.
                                  #Goal:
                                  #  - incremental hashing write|read
                                  #  - e.g. verifying integrity incrementally
                                  #"Top|root|master hash":
                                  #  - single hash of all hashes
                                  #  - goal:
                                  #     - total (i.e. non-incremental) hashing write|read
                                  #     - e.g. verifyint integrity of hash list
                                  #"Hash|Merkle tree":
                                  #  - like top hash but using a tree of hashes where each parent hashes its children
                                  #     - often uses binary tree
                                  #  - should restrict specific depth and branching factor:
                                  #     - otherwise second pre-image attacks are easier to forge
                                  #     - can alternatively prepend some fixed byte to each value and some other byte to each
                                  #       internal hash
                                  #  - pro:
                                  #     - can compute single bottom-level hash to top hash with fewer operations
                                  #     - i.e. faster computation: O(log n) instead of O(n)
                                  #     - also does not need all hashes to be known, just O(log n) of them
                                  #  - con:
                                  #     - inverse when it comes to computing all bottom-level hashes at once
                                  #     - building tree is O(n*log n)

HASH CHAIN ==>                    #List of hashes where each node hashes the previous hash.
                                  #Goal:
                                  #  - increasing time complexity to verify nodes from O(1) to O(n)
                                  #  - e.g. can be used to generate one-time keys (against eavesdropping)

BINARY HASH CHAIN ==>             #Hash chain where each hash also gets some extra input
                                  #Goal:
                                  #  - incremental hashing write|read
                                  #  - similarly to a hash tree, but with:
                                  #     - lower time complexity to add nodes: O(1)
                                  #     - higher time complexity to verify nodes: O(n)