| Home / Indice sezione | www.icosaedro.it | |
Crittografia - Algoritmi digestUltimo aggiornamento: 2008-01-15
Prima di affrontare gli algoritmi di crittazione a chiavi asimmetriche, descriviamo una categoria di algoritmi nota come algoritmi di digest. Il digest (o impronta) di un messaggio M è un numero D(M) calcolato a partire da questo messaggio e che ha le seguenti proprietà:
In parole semplici, l'algoritmo digest rimescola i bit del messaggio e poi ne ritorna un certo numero definito. Ad esempio, un algoritmo potrebbe essere semplicemente quello di invertire i bit del messaggio e prenderne i primi 128. E' chiaro però che questo algoritmo non soddisferebbe i requisiti 2 e 3 dei punti precedenti: tutti i messaggi che iniziano con lo stesso preambolo produrrebbero lo stesso digest e sarebbe davvero facile produrre un messaggio con un digest prederminato. I veri algoritmi digest sono perciò ben più complessi e vengono attentamente progettati dagli esperti crittografi.
I digest sono utili in diverse applicazioni, vediamone rapidamente alcune giusto per farcene un'idea. Penso anche che ragionare su questi semplici schemi crittografici sia un importante allenamento ai prossimi articoli, un po' più impegnativi dal punto di vista formale.
M, D(M)
A ---------------> B
Il ricevente B ripete il calcolo del digest del messaggio e verifica che
questo digest coincida con il MAC. Se i due digest differiscono, qualcosa
è andato storto nella comunicazione e il messaggio deve essere scartato.
M, D(K+M)
A ---------------> B
M, D(K+M) N, D(?+N)
A -------------> I -----------> B
Se un intruso I si inserisce nella comunicazione e intercetta il messaggio M,
l'intruso può modificare il messaggio e trasmettere il messaggio modificato
N a B. Tuttavia l'intruso non sarà in grado di calcolare il corretto digest
D(K+N) perché non conosce la chiave K.
NOTA 1. L'operatore "+" che appare qui non è la somma algebrica, ma il ben più
banale concatenamento dei bit del numero di sinistra con quelli del numero di
destra.
NOTA 2. Gli esperti raccomandano schemi più sicuri ma più complicati per il
calcolo dell'HMAC, per esempio D(K+D(K+M)) oppure D(K1+D(K2+M)). Naturalmente
i due soggetti A e B devono concordare sia lo schema, sia la chiave.
NOTA 3. Il messaggio viene trasmesso in chiaro sul canale insicuro.
A volte non solo si vuole garantire l'integrità e l'autenticità, ma si
desidera anche la segretezza. A questo problema rispondono le tecniche
crittografiche che vedremo nei prossimi articoli.
CHL
Server ---------------> Client
D(PASS+CHL)
Server <--------------- Client
Tra gli algoritmi digest più noti ci sono: MD5, SHA-1, RIPE-MD. Nella bibliografia dedicata agli algoritmi ho messo i riferimenti alla documentazione relativa.
Da uno degli autori di RSA (Rivest, lo vedremo nella prossima sezione dedicata agli algoritmi di crittazione a chiavi pubbliche) uno dei più noti algoritmi digest. L'MD5 genera digest a 128 b, ed è documentato nell'RFC 1321: insieme alla descrizione dell'algoritmo, viene fornito anche il sorgente in linguaggio C che lo implementa.
Il programma PGP (di cui parleremo nella sezione delle implementazioni)
usava questo algoritmo digest. Poi alcune critiche a questo algoritmo
hanno fatto nascere dubbi sulla sua reale robustezza. A dimostrazione
di questo fatto Hans Dobbertin [DOBBERTIN96-1] [DOBBERTIN96-2]
mostra due versioni dello stesso messaggio che differiscono per un
solo carattere (un prezzo che cambia da $176,495 a $276,495) ma che
producono lo stesso digest MD5. Di per sè questo risultato non
dimostra che sia facile invertire l'MD5, e lo stesso autore rassicura su
questo fatto. Tuttavia ciò suggerisce come sia prudente, per il
futuro, utilizzare altri algoritmi digest. Ecco l'articolo postato sul
newsgroup sci.crypt dallo stesso Dobbertin (per favorire
la leggibilità mi sono permesso di riformattare i paragrafi in
modo da ridurre le linee più lunghe a una lunghezza accettabile
per la visualizzazione e la stampa):
From: <dobbertin@skom.rhein.de>
Newsgroups: sci.crypt
Subject: MD5 discussion
Date: 11 Jun 1996 14:22:03 GMT
Organization: CompuServe Incorporated
Lines: 38
Message-ID: <4pjvec$1c6@dub-news-svc-4.compuserve.com>
NNTP-Posting-Host: hd43-009.compuserve.com
Content-Type: text/plain
Keywords: MD5
Content-length: 2222
X-Newsreader: AIR Mosaic (16-bit) version 3.10.08.25
In view of the continuing discussion about MD5, I want to make a few
comments, which hopefully can help to avoid some misunderstandings
and misinterpretations:
1. In February 1996 my paper "Cryptanalysis of MD4" appeared (Fast
Software Encryption, Cambridge Proceedings, Lecture Notes in Computer
Sciences, vol. 1039, Springer-Verlag, 1996, pp. 71-82). In this paper,
as an example two versions of a contract are given with the same MD4
hash value. Alf sells his house to Ann, in the first version the
price is $176,495 and in the second it is $276,495. The contracts
have been prepared by Alf. Now if Ann signs the first version with
$176,495 then Alf can altered to price to $276.495 ... In principle
this risk occurs, if you use a hash function for which (senseful)
collisions can be found, whenever you allow another person to have
influence on the contents of a document you are signing. Certainly
this does not happen very often in practical applications. But
sometimes you *must* have an agreement about a text (contract) which
is then signed by two or more parties. And these are often just the
most important applications!
2. I suspect that the recent attack on MD5 compress can be refined
and extended such that it might lead to MD5 collisions (matching the
right IV) and perhaps then even to similar results as already obtained
for MD4. Certainly this requires a lot of hard additional work.
3. If you write a message for your own (nobody else has influence
on it) and sign it using MD5 (and a strong public key algorithm,
of course) then there is no danger that it can be altered (at least
according to our knowledge today)! Thus it is true that I guess almost
all of you will have no risk using MD5, for instance in PGP. However,
if you accept 2., then in some cases there could be problems ...
4. After all I have reservations against keeping MD5 as a (de facto)
standard, because 2. might indicate that there is a serious security
problem with MD5.
5. My conclusions are: no reason for panic, but in future
implementations better move away from MD5.
6. Presently a paper discussion the status of MD5 in detail is
in preparation.
- Hans Dobbertin
L'MD5 nella pratica. A corredo del sistema operativo GNU/Linux è
disponibile il comando md5sum che calcola il digest MD5 di
un file:
$ md5sum dati
d78b4ef9a20ca1a3d1e14cbd344788bc dati
Il digest è espresso con 32 cifre nella base esadecimale, per un totale di 128 b, come ci dovevamo aspettare.
Questo algoritmo digest è raccomandato come standard dal NIST (National Institute of Standard and Technology), l'uffico federale statunitense che emana le normative tecniche in uso nella pubblica amministrazione di quel paese. L'algoritmo assomiglia all'MD5, ma genera 160 b e viene considerato più robusto. Nota: SHA-1 è stato parzialmente progettato da NSA, cosa non proprio del tutto rassicurante.
L'SHA-1 nella pratica. A corredo del sistema operativo GNU/Linux è
disponibile il comando sha1sum che calcola il digest SHA-1
di un file:
$ sha1sum dati
45db713c2b5929d31fab17c169331c3bc482a3b9 dati
Il digest è espresso con 40 cifre esadecimali, per un totale di 160 b, come ci dovevamo aspettare.
Nato dal progetto europeo RACE Integrity Primitive Evaluation (RIPE), nella versione originale generava digest a 128, poi elevati a 160 nella versione rinforzata. Tra gli autori c'è anche lo stesso Hans Dobbertin, uno dei principali critici dell'MD5 (v. il paragrafo precedente sull'MD5).
I documenti RFC, che costituiscono la documentazione ufficiale di Internet,
sono reperibili in
www.rfc-editor.org.
| Umberto Salsi | Commenti | Contatto | Mappa | Home / Indice sezione |
Still no comments to this page. Use the Comments link above to add your contribute.