Introduzione e proprietà

• Le funzioni di hash sono funzioni crittografiche che devono avere le seguenti caratteristiche:
  1. Facile Computazione
  2. Funzionanti su ogni Stringa
  3. Output di lunghezza prefissata
• Ci sono 3 proprietà fondamentali:
  • Collision - Free
  • Preimage Resistant
  • Second preimage Resistant
• Di seguito una immagine che rappresenta le proprietà citate

Collision-Free

<aside> 💡 Collision Free significa che dati due input X ed Y non devo avere che

</aside>

• Problema: Ho infiniti input e $2^x$ possibili output dove $x$ è il numero di bit dell’output. Cosa si fa?
  • Nulla, le collisioni esistono e ci sono ma non è possibile evitarle per un problema computazionale
  • Ci sono probabilità di avere collisioni, ma sono cosi basse e remote che possiamo correre il rischio, non ci pensiamo insomma
  • Per prassi quindi crediamo che, date le basse probabilità, quando parliamo di funzioni hash, $\text{se }H(X)=H(Y) \text{ allora }X=Y$

Preimage Resistant

<aside> 💡 Dato l’hash non si è in grado di risalire al valore iniziale

</aside>

• Si dice quindi che la funzione deve essere one way

Second Preimage Resistant

<aside> 💡 Second preimage resistance is the property of a hash function that it is computationally infeasible to find any second input that has the same output as a given input.

</aside>

Collisione Free vs Second Preimage

• La differenza tra queste due caratteristiche è che:
  • collision free dice che dati due input diversi non bisogna avere due hash uguale
  • second preimage dice che dato un input di cui sappiamo hash, non è possibile trovare un altro input che mi dia lo stesso hash
• Le funzioni hash trovano impiego notevole nei seguenti ambiti:
  • BlockChain
  • MerkleTree

MerkleTree

• un albero hash ****o albero di Merkle ****è un albero in cui ogni nodo foglia è etichettato con l’hash crittografico di un blocco di dati e ogni nodo non foglia è etichettato con l'hash crittografico delle etichette dei suoi nodi figli.

  <aside> 💡

  </aside>

  <aside> 💡

  questa struttura permette di garantire l’integrità di tutte le foglie perchè se modifico anche solo una foglia, l’hash root cambia completamente.

  </aside>

• questi alberi vengono utilizzati per garantire la sicurezza dei dati in strutture come blockchain etc

• il merkle Tree utilizza gli Hash Pointers

  Hash Pointers

  • Servono a costruire strutture dati come i MerkleTree
  • Permettono di vedere se ci sono manomissioni in grandi quantità di dati
  • permettono inoltre di verificare membership di un elemento ad una struttura dati

SHA1 - Shattered