Archivi categoria: Divagazioni semiserie

The first collision for full SHA-1

by Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov

SHA-1 is a widely used 1995 NIST cryptographic hash function standard that was officially deprecated by NIST in 2011 due to fundamental security weaknesses demonstrated in various analyses and theoretical attacks.

Despite its deprecation, SHA-1 remains widely used in 2017 for document and TLS certificate signatures, and also in many software such as the GIT versioning system for integrity and backup purposes.

A key reason behind the reluctance of many industry players to replace SHA-1 with a safer alternative is the fact that finding an actual collision has seemed to be impractical for the past eleven years due to the high complexity and computational cost of the attack.

In this paper, we demonstrate that SHA-1 collision attacks have finally become practical by providing the first known instance of a collision. Furthermore, the prefix of the colliding messages was carefully chosen so that they allow an attacker to forge two PDF documents with the same SHA-1 hash yet that display arbitrarily-chosen distinct visual contents.

We were able to find this collision by combining many special cryptanalytic techniques in complex ways and improving upon previous work. In total the computational effort spent is equivalent to 263.1 SHA-1 compressions and took approximately 6 500 CPU years and 100 GPU years. As a result while the computational power spent on this collision is larger than other public cryptanalytic computations, it is still more than 100 000 times faster than a brute force search.

Read the full paper: The first collision for full SHA-1

Le origini dei RDBMS

Se dovessi scegliere una tecnologia comune a tutti i programmatori forse sarebbe quella dei database relazionali. Anche se naturalmente non esiste niente che metta d’accordo proprio tutti, posso affermare che la stragrande maggioranza di essi, nel corso della loro carriera, hanno scritto almeno una volta un breve pezzo di codice che abbia a che fare con un database, di qualunque dimensione e tipo.

Del resto possiamo scindere il software nei suoi componenti di base: i dati e il funzionamento. Come impariamo i linguaggi di programmazione per esprimere il funzionamento di un programma, così impariamo a registrare e a rendere permanenti i nostri preziosi dati.

Quando si mettono i dati in una qualunque forma organizzata, ecco che abbiamo una sorta di database. Quando poi li organizziamo sotto forma di relazione, ecco che abbiamo un database relazionale. A questo punto quando aggiungiamo funzionalità per gestire e ottimizzare l’accesso ai dati, ecco che abbiamo un sistema per la gestione di basi di dati relazionali, altrimenti detto relational database management system o RDBMS.

Sicuramente molte persone hanno una certa dimestichezza con questi sistemi. Esistono prodotti considerati dei veri pilastri del settore come Oracle, Microsoft SQL Server, PostgreSQL e MySQL.
In effetti, si fondono così perfettamente nelle attività più disparate che si potrebbero dare facilmente per scontato. Ma da dove vengono e perché? E come si sono evoluti nel corso degli anni? Oggi, diamo uno sguardo indietro alle origini dei RDBMS.

I primi database

Potrebbe sorprendervi sapere che il concetto di database è in realtà antecedente al computing moderno. Potreste leggere questo articolo per i dettagli, ma basti dire che è possibile rintracciare le radici di questo concetto fino al censimento del 1880 negli Stati Uniti. Gli innovatori di quell’epoca inventarono “macchine per la tabulazione” che praticavano dei buchi nelle cosiddette “schede perforate”. Queste carte, insieme ai metodi per la loro memorizzazione, diventarono le prime vere “basi di dati” (o database).

Nei primi anni ’60, un uomo di nome Charles Bachman automatizzò questo concetto. In seguito ricevette un premio Turing per i suoi sforzi nella creazione di un qualcosa chiamato “Integrated Data Store” o IDS. Utilizzando infatti i concetti presi dai database delle schede perforate, come “file”, “campo” e “chiave”, creò un sistema che disaccoppiava la logica dell’applicazione dall’archiviazione dei dati in file. Anche adesso, dopo più di 50 anni, lo riconosceremmo comunque come un database.

Traendo spunto da Bachman, negli anni ’60 sono emersi due tipi di database: i database di rete e i database gerarchici. In breve, il modello gerarchico struttura i dati in alberi, mentre il modello di rete usa una struttura più libera che permette la modellazione diretta delle relazioni “molti a molti”.

La rivoluzione relazionale

Edgar F. Codd (1923 – 2003), un informatico britannico e una delle figure informatiche più di spicco del secolo scorso, ha concepito il modello di database relazionale che usiamo oggi. E’ possibile leggere su di lui anche sul il sito di IBM dal momento che ha lavorato lì.
Quando Codd pubblicò il suo articolo sulle basi di dati relazionali nel 1970, il mondo aveva già sperimentato modelli di database esistenti, abbastanza a lungo da comprendere sia i loro benefici che le loro carenze. Il principale tra questi difetti era la difficoltà causata dall’accoppiamento tra i dati e la conservazione fisica di tali dati. In altre parole, i record stessi dicevano ai ricercatori dove cercare quelli successivi.

All’epoca, sia la potenza di elaborazione che lo spazio di archiviazione avevano un costo molto alto. Questi sistemi andavano bene all’inizio quando i dati venivano memorizzavano, ma i nuovi processi di elaborazione e la necessità di nuove query di ricerca richiedevano una rielaborazione costosa e dispendiosa in termini di tempo.

Codd cambiò tutto questo: il suo modello relazionale ha disaccoppiato la forma dei dati dall’archiviazione fisica di quegli stessi dati. Solo questo fu sufficiente per portare miglioramenti significativi. Ma le “12 regole di Codd” (in realtà 13 perché le indicizzava a zero) sarebbero arrivate più tardi. Queste regole richiedono l’eliminazione di qualsiasi duplicazione dei dati, ottimizzando efficacemente anche il costo dello storage.

L’ascesa di SQL

Occorre fare ancora un po’ di strada prima di arrivare ai database moderni, anche se cominciamo a intravederne la forma.

Chi ha frequentato un corso universitario sui database, avrà sicuramente sentito parlare della Forma Normale di Boyes-Codd (BCNF). Quel Codd è lo stesso Edgar F. Codd che ha generato il modello relazionale.

Il suo complice, un certo Raymond Boyce, lavorava con Codd e un altro signore di nome Donald Chamberline presso IBM. Tutti e tre hanno svolto un lavoro significativo nel campo dei database. Boyce e Chamberlin crearono insieme un modo standard per richiedere le informazioni da questi “database relazionali”. Lo chiamavano “Structured English Query Language” o più brevemente “SEQUEL”. In seguito divenne ancora più breve: “Structure Query Language” o “SQL”.

Sebbene non fosse l’unico modo per creare le query di ricerca, divenne ben presto il più utilizzato. Molti fattori contribuirono al suo successo, in particolare una caratteristica: la natura dichiarativa di SQL. I programmatori delle applicazioni devono solo dichiarare quali record desiderano senza specificare come recuperarli. Il “come” diventa un dettaglio di implementazione del RDBMS.

L’esplosione di Internet

L’origine del modello relazionale ebbe luogo presso IBM negli anni ’70, così come il concepimento di SQL. Ma la sua crescita esponenziale ebbe luogo negli anni ’80, così come l’ascesa di vari fornitori commerciali di RDBMS. Durante quegli anni, quando tutti si adeguarono attorno allo standard SQL, emersero molti prodotti e fornitori di database RDBMS, registrando un grande successo commerciale tra le imprese.

Tuttavia questi piccoli RDBMS durarono poco: attraverso un processo di accrescimento, i concorrenti più grandi assorbirono quelli più piccoli facendo così emergere e maturare quelli che conosciamo oggi.

Tutto questo successe proprio nel momento in cui Internet appariva sulla scena. Se l’esplosione che seguì SQL negli anni ’80 fu qualcosa, nessuno era preparato a ciò che sarebbe accaduto dopo. Man mano che i siti web diventavano applicazioni web, i dati diventavano importanti per le comunicazioni in modi senza precedenti. All’improvviso, quasi tutti gli sviluppatori sulla Terra sembravano aver bisogno dell’accesso client-server a un RDBMS.

Questa continua richiesta ha spinto i fornitori a ottimizzare e a  espandere le funzionalità e più in generale a soddisfare gli sviluppatori di applicazioni. I venditori si sono così buttati su ogni tipo di offerta e hanno incoraggiato una situazione tale che il RDBMS occupava il ruolo di “centro dell’universo”.

La competizione rivista

Quando Codd elaborò il suo modello relazionale, ha cercato di affrontare i costosi colli di bottiglia dell’epoca: lo spazio su disco e la potenza di elaborazione. I modelli relazionali hanno permesso di economizzare intensamente lo spazio ma, a volte, a scapito di un’intensa complessità per determinati tipi di dati. In altre parole, non tutto si presta bene allo storage relazionale e alla normalizzazione. I registri di log di grandi dimensioni, ad esempio, non traggono alcun vantaggio dalla normalizzazione.

Non appena il concetto di “larga scala del web” è cresciuto nella nostra coscienza collettiva, alcuni hanno iniziato a rivedere l’assunto onnipresente di RDBMS per ogni applicazione scegliendo approcci diversi come i database documentali che memorizzano ed elaborano i dati in modi meno “tradizionali”, riscuotendo anche un certo consenso fino ad emergere una linea di pensiero anti-SQL.

È con questo adeguato senso di simmetria che arriviamo al presente: prima che l’RDBMS acquisisse la sua importanza nel mondo dell’informatica, c’erano pochi concorrenti. Ora, circa 40 anni dopo, ancora una volta ci sono pochi concorrenti. Poche cose hanno inciso tanto quanto l’RDBMS ma la storia scritta tra altri 40 anni forse la vedrà solo come una delle tante opzioni per l’età della “larga scala del web”.

Fonte: A Look at the History of RDBMS di Erik Dietrich