Rainbow table

Une rainbow table (littéralement table arc-en-ciel) est, en cryptanalyse, une structure de données créée en 2003 par Philippe Oechslin de l'EPFL[1] pour retrouver un mot de passe à partir de son empreinte. Il s'agit d'une amélioration des compromis temps-mémoire proposés par Martin Hellman dans les années 1980.

Aperçu

La table, qui ne dépend que de la fonction de hachage considérée, est constituée d'une grande quantité de paires de mots de passe. Pour obtenir chacune de ces paires, on part d'un mot de passe, et on calcule son empreinte. Une « fonction de réduction » qui varie selon la position dans la table permet de recréer un nouveau mot de passe à partir de cette empreinte. On itère ce processus, et après un nombre fixe d'itérations, on obtient un mot de passe qui forme le deuxième élément de la paire. La table, créée une fois pour toutes, permet la recherche d'un mot de passe, connaissant son empreinte par la fonction de hachage considérée.

L'algorithme développé par Oechslin optimise la détection des collisions et le parcours dans la table. Des solutions pour réduire la taille de la table ont également été proposées. Plusieurs tables peuvent être produites pour améliorer les chances de réussite.

L'algorithme, déjà efficace avec des mots de passe correctement hachés (le mot de passe Windows "Fgpyyih804423" est retrouvé en 160 secondes[2]) l'est a fortiori avec les mots de passe de LAN Manager, qui utilisent LM hash (et donc un niveau de sécurité très faible). Ces derniers sont ainsi trouvés en l'espace de quelques secondes s'ils sont alphanumériques. Les tables peuvent être utilisées avec toute autre fonction de hachage comme MD5 ou encore SHA-1, ces dernières étant nettement plus robustes du point de vue cryptographique que LAN Manager et nécessitent des tables plus grandes.

Rappels concernant la problématique

Une des principales menaces concernant l'usage de mots de passe est la compromission des bases contenant les mots de passe utilisateur. Un attaquant profite d'une brèche quelconque pour récupérer la table de mots de passe d'un système. Il pourrait être raisonnable de penser qu'un attaquant capable de compromettre la table de mots de passe d'un système dispose déjà d'un accès suffisant à celui-ci pour que cette dernière ne présente qu'un intérêt limité pour lui. Les études comportementales montrent que la réutilisation par les utilisateurs du même mot de passe pour différents sites ou systèmes est endémique[3], c'est pourquoi un attaquant qui compromet les mots de passe d'un système donné est souvent en mesure d'en déduire les mots de passe pour d'autres sites.

Pour lutter contre ce phénomène, les normes de sécurité modernes proscrivent la conservation des mots de passe en texte brut par les systèmes gestionnaires d'authentification, au contraire elles incitent à ce que ne soient conservés que des versions hachées des mots de passe.

Les fonctions de hachage cryptographiques employées à cet effet sont spécifiquement conçues pour être mathématiquement difficiles à inverser, c'est pourquoi l'attaquant en est souvent réduit à employer des méthodes d'attaque par force brute.

Là encore les fonctions de hachage sont optimisées pour augmenter le temps de chaque tentative de comparaison.

Une des méthodes principales retenues pour diminuer le temps de réalisation de ce type d'attaques repose sur l'utilisation de compromis temps-mémoire. La table arc-en-ciel (en anglais : rainbow table) est une forme sophistiquée de ce type d'attaque.

Les attaques par compromis temps-mémoire

Table de hachage

Compromis temps-mémoire d'Hellman

Rainbow table

Création de la table

La rainbow table est constituée de paires de mots de passe (i.e. chaque ligne possède un mot de passe de départ et un mot de passe d'arrivée). Pour calculer la table, on établit des chaînes grâce à un mot de passe initial. Celui-ci subit une série de réductions et de hachage afin d'obtenir des éléments intermédiaires (mots de passe et empreintes correspondantes). La fonction de réduction transforme une empreinte en un nouveau mot de passe. Afin d'éviter des problèmes de collision, plusieurs fonctions de réduction sont utilisées. Après plusieurs milliers d'itérations, on obtient un mot de passe en bout de chaîne. C'est celui-ci qui est stocké avec le mot de passe à l'origine de cette chaîne. Le reste de la chaîne n'est pas conservé afin de limiter la mémoire nécessaire. Il est toutefois possible de les retrouver en calculant l'ensemble de la chaîne à partir de l'élément en tête de liste.

On recommence avec un autre mot de passe pour établir une nouvelle chaîne et ainsi de suite jusqu'à constituer une table dont les statistiques sont suffisantes pour garantir le succès de l'attaque.

Une rainbow table avec trois fonctions de réduction

Plus formellement, le calcul d'une chaîne se fait comme suit à partir d'un mot de passe initial P et de fonctions de réduction (différentes à chaque itération pour limiter les collisions) :

Recherche du mot de passe

On considère une empreinte H engendrée à partir d'un mot de passe P. La première étape consiste à prendre H, lui appliquer la dernière fonction de réduction utilisée dans la table, et regarder si ce mot de passe apparaît dans la dernière colonne de la table. Si cette occurrence n'est pas trouvée alors on peut déduire que l'empreinte ne se trouvait pas à la fin de la chaîne considérée. Il faut revenir un cran en arrière. On reprend H, on lui applique l'avant-dernière fonction de réduction, on obtient un nouveau mot de passe. On hache ce mot de passe, on applique la dernière fonction de réduction et on regarde si le mot de passe apparaît dans la table.

Cette procédure itérative continue jusqu'à ce que le mot de passe calculé en fin de chaîne apparaisse dans la table (si rien n'est trouvé, l'attaque échoue). Une fois le mot de passe découvert dans la dernière colonne, on récupère le mot de passe qui se trouve dans la première colonne de la même ligne. On calcule à nouveau la chaîne tout en comparant à chaque itération l'empreinte obtenue à partir du mot de passe courant avec l'empreinte H du mot de passe inconnu P. S'il y a égalité, alors le mot de passe courant correspond à celui recherché et l'attaque a réussi ; plus précisément, on a trouvé un mot de passe dont l'empreinte est la même que celle de P, ce qui est suffisant.

Exemple
  • À partir d'une empreinte ("re3xes"), on calcule la dernière réduction utilisée dans la table et on regarde si le mot de passe apparaît dans la dernière colonne de la table (étape 1)
  • Si le test échoue ("rambo" n'apparaît pas dans la table), on passe au point 2 où l'on calcule une chaîne avec les deux dernières réductions.
  • Si ce test échoue à nouveau, on recommence avec 3 réductions, 4 réductions, etc. jusqu'à trouver une occurrence du mot de passe dans la table. Si aucune chaîne ne correspond alors l'attaque échoue.
  • Si le test réussit (étape 3, ici "linux23" apparaît en fin de chaîne et également dans la table), on récupère le mot de passe à l'origine de la chaîne qui a abouti à "linux23". Il s'agit ici de "passwd".
  • On génère la chaîne (étape 4) et on compare à chaque itération l'empreinte avec l'empreinte recherchée. Le test est concluant, on trouve ici l'empreinte "re3xes" dans la chaîne. Le mot de passe courant ("culture") est celui qui a engendré la chaîne : l'attaque a réussi.

Contre-mesures

L'efficacité des tables diminue de façon significative lorsque les fonctions de hachage sont combinées à un sel. Dans le cadre d'un système de mots de passe, le sel est une composante aléatoire ou un compteur qui change en fonction de l'utilisateur. Si deux utilisateurs ont le même mot de passe, le sel permet d'éviter que les empreintes soient identiques. De manière informelle, le sel consiste en une opération du type :

empreinte = h(mot_de_passe + sel) 

où l'opération + peut être une concaténation ou une opération plus complexe.

Cette mesure augmente la complexité de l'attaque : il faut non seulement inverser la fonction grâce aux tables, mais il faut encore explorer l'ensemble des possibilités induites par la présence du sel. Si l'attaque réussit, il faut encore retirer le sel du mot de passe.

En pratique, certaines applications n'utilisent pas de sel et sont vulnérables. En outre, le sel doit avoir une longueur suffisante pour augmenter sensiblement la complexité. Un sel trop court (par exemple 4 bits) ne multiplierait la complexité que d'un facteur de 16. Dans le système GNU/Linux, la fonction de hachage utilisée est du MD5 avec un sel de 8 caractères en ASCII ce qui rend l'attaque impossible en pratique.

Notes et références

  1. (en) Philippe Oechslin, « Making a Faster Cryptanalytic Time-Memory Trade-Off », dans Advances in Cryptology - CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003. Proceedings, Springer, coll. « Lecture Notes in Computer Science », vol. 2729, 2003 (ISBN 978-3-540-40674-7 et 978-3-540-45146-4), p. 617-630 DOI 10.1007/978-3-540-45146-4_36. texte intégral en ligne
  2. (en) Jeff Atwood, « Rainbow Hash Cracking », Coding Horror, 8 septembre 2007
  3. John Fontana, Password's rotten core not complexity but reuse, Zdnet.com, 22 mars 2013, consulté le 24 octobre 2013

Voir aussi

Sur les autres projets Wikimedia :

Articles connexes

Liens externes

Read other articles:

Radio station in Park Falls, Wisconsin WPFPPark Falls, WisconsinFrequency980 kHzBranding103.1 Jack FMProgrammingFormatVariety hitsAffiliationsJack FM networkOwnershipOwnerThe Marks Group(Park Falls Community Broadcasting Corporation)Sister stationsWCQMHistoryFirst air date1953 (1953)Former call signsWPFP (1953-1968)WNBI (1968–2010)Technical informationFacility ID48847ClassDPower1,000 watts day105 watts nightTransmitter coordinates45°55′4.00″N 90°26′58.00″W / 4...

 

Beethoven's musical work known as Spring Sonata Beethoven in 1801 The Violin Sonata No. 5 in F major, Op. 24, is a four movement work for violin and piano by Ludwig van Beethoven. It was first published in 1801. The work is commonly known as the Spring Sonata (Frühlingssonate), although the name Spring was apparently given to it after Beethoven's death.[1] The sonata was dedicated to Count Moritz von Fries, a patron to whom Beethoven also dedicated two other works of the same year—...

 

Bulgarian footballer Hristofor Hubchev Personal informationFull name Hristofor Hristoforov HubchevDate of birth (1995-11-24) 24 November 1995 (age 27)Place of birth Madrid, Spain[1]Height 1.81 m (5 ft 11+1⁄2 in)Position(s) Left-back / Centre-backTeam informationCurrent team Spartak VarnaYouth career0000–2013 Levski Sofia2013–2014 Bonner SCSenior career*Years Team Apps (Gls)2014–2016 Montana 36 (0)2016 Beroe 0 (0)2017–2018 Dunav Ruse 30 (0)2018–2019 ...

Чжао Даюй Особисті дані Народження 17 січня 1961(1961-01-17)[1]   Ґуанчжоу, КНР Смерть 18 березня 2015(2015-03-18)[2] (54 роки)   Ґуанчжоу, КНР Зріст 162 см Громадянство  КНР Позиція нападник Професіональні клуби* Роки Клуб І (г) 1978–1986 «Гуанчжоу Баюн»  ? (?) 1987–1988 «Міцубісі ...

 

Nurjaya Ali MuktiGelarKiaiNama lainKH Nurjaya KH JayaInformasi pribadiLahirNurjaya Ali MuktiCisoka, Tangerang, BantenAgamaIslamKebangsaanIndonesiaOrang tuaZakir (ayah)ZamanModernAlmamaterPondok Pesantren Darul IbtidaDikenal sebagaiPimpinan Pondok Pesantren Nurul HikmahNama lainKH Nurjaya KH JayaPekerjaanUlama Kiai Haji Nurjaya Ali Mukti (Arab: نورجيا علي موكتي) adalah seorang ulama, kiai, da'i, pendakwah dan pemimpin Pondok Pesantren Nurul Hikmah.[1][2&...

 

Village in Kantō, JapanTsumagoi 嬬恋村VillageTsumagoi village office FlagSealLocation of Tsumagoi in Gunma PrefectureTsumagoi Coordinates: 36°31′0.6″N 138°31′48.5″E / 36.516833°N 138.530139°E / 36.516833; 138.530139CountryJapanRegionKantōPrefectureGunmaDistrictAgatsumaArea • Total337.58 km2 (130.34 sq mi)Population (September 2020) • Total9,546 • Density28/km2 (73/sq mi)Time zoneUTC+9 (J...

Lophatherum Lophatherum gracile Klasifikasi ilmiah Kerajaan: Plantae Upakerajaan: Trachaeophyta Divisi: Magnoliophyta Kelas: Liliopsida Subkelas: Liliidae Ordo: Poales Famili: Poaceae Subfamili: Panicoideae Tribus: Zeugiteae Genus: LophatherumBrongn. Spesies[1][2] Lophatherum gracile Brongn. Lophatherum sinense Rendle Sinonim[1] Acroelytrum Steud. Allelotheca Steud. Lophatherum adalah genus Keluarga dalam suku rumput-rumputan (Poaceae) yang tersebar di Asia dan Austral...

 

American swimmer Dana VollmerVollmer in 2009Personal informationFull nameDana Whitney Vollmer[1]National team United StatesBorn (1987-11-13) November 13, 1987 (age 36)Syracuse, New York, U.S.Height6 ft 1 in (185 cm)Weight150 lb (68 kg)Websitewww.danavollmer.com SportSportSwimmingStrokesButterfly, freestyleClubCalifornia AquaticsCollege teamUniversity of California, Berkeley;University of Florida Medal record Women's swimming Representing &#...

 

Tales of Mobile (テイルズオブモバイル, Teiruzu Obu Mobairu) is the collective name of several mobile phone-based games available only to Japanese NTT DoCoMo FOMA 900i cellphone users that often feature characters and story elements from the popular Tales role-playing video game series. As these games are offered as a download-only phone service in Japan, none of them has been made available outside Japan. Role-playing games Tales of Tactics Tales of Tactics (テイルズオブタク...

Historic district in Alabama, United States United States historic placeFort Payne Main Street Historic DistrictU.S. National Register of Historic PlacesU.S. Historic district Buildings on 1st Street in November 2017Show map of AlabamaShow map of the United StatesLocationRoughly Gault Ave. from 2nd St. NE. to 2nd St. NW., Fort Payne, AlabamaCoordinates34°26′28″N 85°43′21″W / 34.44111°N 85.72250°W / 34.44111; -85.72250Area6 acres (2.4 ha)Architectural&#...

 

French musician and actor (1928–1991) Gainsbourg redirects here. For his daughter, the actress, see Charlotte Gainsbourg. For the 2010 biopic, see Gainsbourg: A Heroic Life. For the Paris Métro station, see Serge Gainsbourg (Paris Métro). Serge GainsbourgGainsbourg in 1981BornLucien Ginsburg(1928-04-02)2 April 1928Paris, FranceDied2 March 1991(1991-03-02) (aged 62)Paris, FranceOther names Julien Grix Gainsbarre Occupations Singer songwriter actor composer director author poet Ye...

 

Nguyễn Thanh NghịChức vụBộ trưởng Bộ Xây dựngNhiệm kỳ8 tháng 4 năm 2021 – nay2 năm, 243 ngàyThủ tướngPhạm Minh ChínhTiền nhiệmPhạm Hồng HàKế nhiệmđương nhiệmThứ trưởngLê Quang Hùng (8/2014-2022)Nguyễn Văn Sinh (2/2018-nay)Bùi Hồng Minh (6/2021-nay)Nguyễn Tường Văn (11/2022-nay)Bùi Xuân Dũng (9/2023-nay) Thứ trưởng Bộ Xây dựng (lần 2)Nhiệm kỳ5 tháng 10 năm 2020 –...

Place in Styria, SloveniaŠentvid pri GrobelnemŠentvid pri GrobelnemLocation in SloveniaCoordinates: 46°13′33.19″N 15°27′40.96″E / 46.2258861°N 15.4613778°E / 46.2258861; 15.4613778Country SloveniaTraditional regionStyriaStatistical regionSavinjaMunicipalityŠmarje pri JelšahArea • Total1.14 km2 (0.44 sq mi)Elevation283.1 m (928.8 ft)Population (2002) • Total182[1] Šentvid pri Grobelnem (prono...

 

Music genres This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Heavy metal genres – news · newspapers · books · scholar · JSTOR (April 2011) (Learn how and when to remove this template message) A number of heavy metal genres have developed since the emergence of heavy metal (often shortened to metal) during th...

 

Simha, AbhayaAbhaya SimhaBorn (1981-06-12) 12 June 1981 (age 42)MangaloreOccupationFilm directorYears active2007 - PresentSpouseRashmi Abhaya Simha Abhaya Simha is a Kannada film director and screenwriter. He was born and brought up in Mangalore, Karnataka, INDIA. He did his graduation from St. Aloysius College, Mangalore. He studied Kannada, English Literature and Journalism. After that he specialized in Film Direction from Film and Television Institute of India, Pune. He started h...

Para la santa del siglo II, véase Germana. Santa Germana Cousin Información personalNombre de nacimiento Germana María de Jesús CousinNacimiento 1579Pibrac, FranciaFallecimiento 15 de junio de 1601Pibrac, FranciaSepultura Basílica de Santa Germana Nacionalidad FrancesaReligión Cristianismo Información profesionalOcupación Catequista Información religiosaCanonización 1867 por el papa Pío IXFestividad 15 de junioVenerada en Iglesia católicaPatronazgo Diócesis de Toulouse  ...

 

Bandar Udara Internasional BroomeBerkas:Broome International Airport logo.pngIATA: BMEICAO: YBRMInformasiJenisPublicPengelolaBandar Udara Internasional BroomeLokasiBroome, Western AustraliaKetinggian dpl mdplKoordinat17°56′59″S 122°13′40″E / 17.94972°S 122.22778°E / -17.94972; 122.22778Koordinat: 17°56′59″S 122°13′40″E / 17.94972°S 122.22778°E / -17.94972; 122.22778Situs webwww.broomeair.com.auPetaLua error in M...

 

Il Museo d'arte contemporanea (MAC) di Gibellina è un museo civico, intitolato a Ludovico Corrao, sito nella città belicina, in viale Segesta. La nuova sede del MAC di Gibellina La collezione d'arte contemporanea si forma attraverso il contributo di numerosi artisti ed è raccolta nel Museo d'arte contemporanea Ludovico Corrao, con una collezione di circa 2.000 opere d’arte.[1] Indice 1 Storia 2 Note 3 Voci correlate 4 Altri progetti 5 Collegamenti esterni Storia Museo d'arte cont...

Olympic NiceFounded1989LeagueFrench ChampionshipFrench Women's Chp.Based inNiceColors   ChampionshipsMen:8 French Leagues4 French Cups1 French League CupWomen:4 French Leagues2 French CupsWebsiteolympicnice.fr Olympic Nice Natation diver Olympic Nice Natation is a French water polo and swimming club from Nice, founded in 1989.[1] Its men's team won eight national championships in a row between 1997 and 2004,[2] while its women's team has been successful in recent yea...

 

For the Argentine-born Chilean footballer, see Pablo Hernández (footballer, born 1986). Spanish footballer (born 1985) In this Spanish name, the first or paternal surname is Hernández and the second or maternal family name is Domínguez. Pablo Hernández Hernández playing for Valencia in 2008Personal informationFull name Pablo Hernández Domínguez[1]Date of birth (1985-04-11) 11 April 1985 (age 38)[2]Place of birth Castellón de la Plana, Spain[3]Heigh...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!