Duhové tabulky

26.5.2006 17:39 | Přečteno: 2524× | Lisp

• O čem to je: o duhových tabulkách (rainbow tables)
• Co to je: způsob, jak po patřičné přípravě rychle(ji) dekódovat třeba zahashované heslo
• Kde to je popsáno pořádně: Oechslin a vůbec, máte Google
• Proč to dávám do blogu, když v tom není nic nového:
  • Abych snížil procento blogů o politice (tento je až na tuto větu 100% politika free)
  • Protože pořád ještě narážím na případy, kdy někdo hashuje hesla standardním algoritmem bez soli - třeba je osvěty trochu třeba
  • Abych to našel, až to budu zase potřebovat

Znám hash nějakého hesla a algoritmus, kterým se hashuje. Chci z něj získat heslo (o kterém mohu něco předpokládat, třeba že má pět znaků z určité množiny). Jsou dvě krajní možnosti:

1. Projedu všechna možná hesla, zkusím, zda sedí hash. Trvá to dlouho, spotřeba paměti minimální
2. Vezmu tabulku hashí, heslo v ní vyhledám, a je to. Trvá to krátce, potřebuju dost velkou a neskladnou tabulku.

Existuje trik, kterým lze dosáhnout kompromisu: nadefinuju si funkci, která převádí hash zpátky na (jiné) možné heslo, a opakovaně aplikuju hashování a tuto funkci. Po určitém počtu opakování (nebo jindy, kdy se mi zachce) uložím koncovou hash či heslo a přiřadím jí počáteční. Tak mi vznikne tabulka menší než v případu 2. Pokud chci dekódovat hash, aplikuju obdobnou proceduru, dokud nenajdu výsledek v tabulce (pak vezmu počáteční heslo a propracovávám se zpátky k původnímu) nebo usoudím, že to nemá cenu (pak mám smůlu)

Evidentně čím více řádků, tím větší šance, že to tam bude, a tím větší tabulka. Čím více sloupců, tím větší šance, že to tam bude, a tím déle to trvá. Jaké je procento pokrytí možných hesel viz odkazovaný článek.

Má to pár háčků, část z nich lze řeší právě zduhatěním algoritmu: pro každý krok se použije jiná funkce hash -> heslo. Pak je ovšem potřeba zkoušet různé polohy hashe v tabulce.

Řečeno přesněji (aneb implementace v Lispu - spíš instruktivní než pro použití):

(defstruct (rainbow-table (:type vector)) rows
   colors startpoints reducing-function cipher-function)


(defun cipher (key table)
  "Do the hashing step"
  (funcall (rainbow-table-cipher-function table) key))

(defun reduce-hash (hash color table)
  "Call reducing function"
  (funcall (rainbow-table-reducing-function table) hash color))

(defun cipher-and-reduce (key color table)
  "Returns next key in a row"
  (reduce-hash (cipher key table) color table))

(defun traverse-chain (start-key start-color table 
                                 &optional (end-color (colors-in table)))
  "Return final key for given start key and table"
  (loop for color from start-color to end-color
        for key = start-key then (cipher-and-reduce key color table)
        finally (return key)))

(defun setup-rows (table start-keys-generator)
  "Initialize the table"
  (let ((start-rows (make-hash-table)))
    (loop for row from 0 to (1- (rows-in table))
          for start-key = (funcall start-keys-generator row)
          do (setf (gethash 
                     (traverse-chain start-key 0 table) start-rows)
                   start-key))
    (setf (rainbow-table-startpoints table) start-rows)))

(defun lookup-start-key (end-key table)
  "Return start key to end key, or nil if end key is not in table."
  (gethash end-key (rainbow-table-startpoints table)))

(defun lookup-key (key start-color table)
  (let ((start-key (lookup-start-key key table)))
    (when start-key (traverse-chain start-key 0 table (1- start-color)))))

(defun decipher (hash table)
  (loop for start-color from 0 to (1- (colors-in table))
        for result =  (lookup-key
               (traverse-chain
                 (reduce-hash hash start-color table) start-color table)
               start-color table)
        do (when (and result
                      (eql (cipher result table) hash))
             (return result))
        finally nil))

Obrana: pořádná hesla (je to pořád jenom brute force attack), solit hashe (pak se hůř předpřiravují tabulky)

       

Komentáře

[Kyosuke]

To vypadá na docela zajímavou metodu, díky za ten paper. Ale radši si do opšnů defstructu přidám (:conc-name rt-)

[Kyosuke]

Mimochodem, „The following functions were used but not defined: ROWS-IN COLORS-IN“ je v pořádku?

[Tom.š Ze.le.in]

Ne, tak to dopadá, když to člověk přepisuje za běhu z defclass do defstruct.

[Kníže Ignor]

Mně to pdfko nejde stáhnout - vždycky zamrznu kolem 40%. Takže asi zůstanu hloupej. Ledeže by mi to chtěl někdo třeba poslat mailem (ignor TEČKA knize ZAVINÁČ seznam.cz) Nebo si to můžu v pondělí stáhnout odjinud, ale alespoň uvidím, jak jsou tady lidi hodný

[Jan Zahornadsky]

Aby tě místní hodní lidé do rána neuspamovali

[Kníže Ignor]

Končím soutěž. Každý, kdo mi to do tohoto okamžiku poslal a došlo mi to, odemne dostane 1000 Kč, ať vidíte, že umím bejt vděčnej. Detaily s výherci vyřešíme mailem.