[e-privacy] Verifica di hash

[Francesco Poli]

On Fri, 6 Dec 2002 23:09:39 +0100
brain <xbrain at ciaoweb.it> wrote:

[...]
> + sono in possesso di un unico dato, l'hash di k crittato con k:
> C_k(H_k)
> + mi calcolo H_x
> + tento di decrittare C_k(H_k) con x: D_x(C_k(H_k))
> + se x e' esatta, abbiamo x = k, ma anche:
>   D_x(C_k(H_k)) = D_k(C_k(H_k) = H_k e H_x = H_k,
>   dunque la verifica funziona.
> + MA se x != k... chi ci garantisce che D_x(C_k(H_k) != H_x, e
>   dunque la verifica non riesca lo stesso?
[...]

Effettivamente, se  x != k  si ha  D_x(C_k(H_k)) != H_k  e  H_k != H_x 
(quest'ultima e` solo estremamente probabile, ma non sicura, giusto?).
Nel caso improbabile in cui  H_k == H_x  si ha sicuramente 
  D_x(C_k(H_k)) != H_k  =>  D_x(C_k(H_k)) != H_x
Se invece  H_k != H_x  (come e` estremamente probabile), le due
disuguaglianze di prima non garantiscono che  D_x(C_k(H_k)) != H_x
Supponiamo infatti che  D_x(C_k(H_k)) == H_x
Ne segue
  C_k(H_k) == C_x(H_x)
Ma
  D_x(C_k(H_k)) != H_k
e quindi
  C_k(H_k) != C_x(H_k)
per cui
  C_x(H_x) != C_x(H_k)
cioe`
  H_x != H_k
coerente con l'ipotesi iniziale.
Non mi pare si possa cadere in assurdo...

Sembrerebbe quindi che la verifica che fai sia sicura in caso di esito
negativo, ma non sicura (soltanto molto affidabile) in caso di esito
positivo.
Infatti se la verifica da` esito negativo, si ha
  D_x(C_k(H_k)) != H_x
da cui segue necessariamente
  x != k
perche' se, per assurdo, supponiamo  x == k  si ottiene  D_k(C_k(H_k))
!= H_k  cioe`  H_k != H_k  che non puo` essere.
Se invece la verifica da` esito positivo, si ha  D_x(C_k(H_k)) == H_x 
che puo` significare
  x == k
oppure (improbabile)
  x != k   con   C_k(H_k) == C_x(H_x)

Questa verifica puo` dunque dare dei falsi positivi, ma non dei falsi
negativi.

D'altronde la stessa verifica che si fa con una funzione di hash ha
queste caratteristiche
  H_a != H_b  =>  a != b
  H_a == H_b  =>  a == b  oppure (improbabile) a != b
Dico bene?

-- 
      Francesco Poli      <frx at firenze.linux.it>
======================================================
You're compiling a program and, all of a sudden, boom!
  -- from APT HOWTO, version 1.8.0