Taula de l'arc de Sant Martí
Una taula de l'arc de Sant Martí és una taula precomputada per a la memòria cau les sortides d'una funció hash criptogràfica, normalment per trencar hash de contrasenya. Les contrasenyes normalment s'emmagatzemen no en forma de text senzill, sinó com a valors hash. Si aquesta base de dades de contrasenyes hash cau en mans d'un atacant, poden utilitzar una taula de l'arc de Sant Martí precomputada per recuperar les contrasenyes de text sense format. Una defensa comuna contra aquest atac és calcular els hash mitjançant una funció de derivació de claus que afegeix una "sal" a cada contrasenya abans d'haver-la, amb diferents contrasenyes que reben diferents sals, que s'emmagatzemen en text sense format juntament amb el hash.
Les taules Rainbow són un exemple pràctic de compensació espai-temps: utilitzen menys temps de processament de l'ordinador i més emmagatzematge que un atac de força bruta que calcula un hash en cada intent, però més temps de processament i menys emmagatzematge que una taula simple que emmagatzema el hash de totes les contrasenyes possibles.
Les taules Rainbow van ser inventades per Philippe Oechslin [1] com una aplicació d'un algorisme anterior i més senzill de Martin Hellman.[2]
Rerefons
[modifica]Per a l'autenticació d'usuaris, les contrasenyes s'emmagatzemen com a text sense format o com a hash. Com que les contrasenyes emmagatzemades com a text sense format es roben fàcilment si l'accés a la base de dades es veu compromès, les bases de dades solen emmagatzemar hash. Així, ningú – inclòs el sistema d'autenticació – pot aprendre una contrasenya només mirant el valor emmagatzemat a la base de dades.
Quan un usuari introdueix una contrasenya per a l'autenticació, es calcula un hash per a aquesta i després es compara amb el hash emmagatzemat per a aquest usuari. L'autenticació falla si els dos hash no coincideixen; a més, l'autenticació fallaria igualment si s'introduïa un valor hash com a contrasenya, ja que el sistema d'autenticació ho faria hash per segona vegada.[3]
Aprendre una contrasenya d'un hash és trobar una cadena que, quan s'introdueix a la funció hash, crea el mateix hash. Això és el mateix que invertir la funció hash.[4]
Encara que els atacs de força bruta (per exemple, els atacs de diccionari) es poden utilitzar per intentar invertir una funció hash, poden arribar a ser inviables quan el conjunt de possibles contrasenyes és prou gran. Una alternativa a la força bruta és utilitzar taules de cadena hash precalculades. Les taules Rainbow són un tipus especial d'aquestes taules que superen certes dificultats tècniques.[5]
Taules de l'arc de Sant Martí
[modifica]Les taules de l'arc de Sant Martí resolen eficaçment el problema de les col·lisions amb cadenes hash ordinàries substituint la funció de reducció única R per una seqüència de funcions de reducció relacionades R1 a Rk. D'aquesta manera, perquè dues cadenes xoquin i es fusionin han d'assolir el mateix valor en la mateixa iteració : en conseqüència, els valors finals d'aquestes cadenes seran idèntics. Una passada final de postprocessament pot ordenar les cadenes a la taula i eliminar qualsevol cadena "duplicada" que tingui els mateixos valors finals que altres cadenes. Aleshores es generen noves cadenes per omplir la taula. Aquestes cadenes no estan lliures de col·lisions (es poden solapar breument), però no es fusionaran, reduint dràsticament el nombre total de col·lisions.[6][7]
Usos comuns
[modifica]Gairebé totes les distribucions i variacions d'Unix, Linux i BSD utilitzen hash amb sals, tot i que moltes aplicacions utilitzen només un hash (normalment MD5) sense sal. La família Microsoft Windows NT/2000 utilitza el mètode hashing LAN Manager i NT LAN Manager (basat en MD4) i també és sense sal, cosa que la converteix en una de les taules generades més popularment. Les taules Rainbow han vist un ús reduït a partir del 2020, ja que el salat és més comú i els atacs de força bruta basats en GPU s'han tornat més pràctics. Tanmateix, les taules de l'arc de Sant Martí estan disponibles per a contrasenyes NTLM de vuit i nou caràcters.[8]
Referències
[modifica]- ↑ Oechslin, P. «Making a Faster Cryptanalytic Time-Memory Trade-Off». A: Advances in Cryptology - CRYPTO 2003 (en anglès). 2729, 2003, p. 617–630 (LNCS). DOI 10.1007/978-3-540-45146-4_36. ISBN 978-3-540-40674-7.
- ↑ Hellman, M. IEEE Transactions on Information Theory, 26, 4, 1980, pàg. 401–406. DOI: 10.1109/TIT.1980.1056220. ISSN: 0018-9448.
- ↑ Manber, U. «Còpia arxivada». Computers & Security, 15, 2, 1996, pàg. 171–176. Arxivat de l'original el 2016-05-06. DOI: 10.1016/0167-4048(96)00003-X [Consulta: 28 agost 2015].
- ↑ Kelsey, J. «Secure applications of low-entropy keys». A: Information Security (en anglès). 1396, 1998, p. 121 (LNCS). DOI 10.1007/BFb0030415. ISBN 978-3-540-64382-1.
- ↑ Provos, Niels; Mazières, David Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference [Monterey, CA, USA], 06-06-1999.
- ↑ Alexander, Steven Login, 29, 3, 6-2004.
- ↑ Ferguson, Neils. Practical Cryptography (en anglès). Indianapolis: John Wiley & Sons, 2003. ISBN 978-0-471-22357-3.
- ↑ «A Case for Modern Rainbow Table Usage» (en anglès). rainbowcrackalack.com. Positron Security., 26-02-2021.