From frank@funcom.com Sat, 30 Oct 1999 20:40:25 +0200 (CEST)
Date: Sat, 30 Oct 1999 20:40:25 +0200 (CEST)
From: Frank Andrew Stevenson frank@funcom.com
Subject: [Livid-dev] Working attack on DiskKey Hash

Through private communication with list readers, I was more
or less challenged... ( Or so it felt to me ) To find an
attack whereby the encrypted (temporary) diskkey can be
retrieved from the hash found at the start of the Disk
key data block.

At first it seemed to me that it required a workload of 2^40.
And there didn't seem much in the way for speeding up such
an attack. But througe careful study of the structure in the
mangling cipher and the CSS I have now come up with the
following attack.

Guess the initals state of LFSR1, and B[0] - the first byte
of the second stage of the mangling cipher. From this starting
point k[0] and B[4] , first byte of mangling key, and fifth
byte of second stage can be found. Now k[4] can be found,
that is the fifth byte in the mangling key. Through a table
all permissible k[1] second mangling keys can be found.

Since the mangling key is the output of the ordinary CSS cipher,
LFSR1s output is completely known. We have also just found byte
1,2,5 of the CSS cipher output. This gives us 2  possibilities
of 1,2,5 byte output from LFSR2. Luckily there is a 1 <-> 1
mapping of these bytes and the initial state.

So through a table with 2^24 entries the initial state of 
LSFR2 can be found. By now completing the mangle cipher 
1 out 256 LFSR2 startstates will emerge as a candidate,
and can be checked the usual (slow) way. There will 'only'
be 2^17 such checks so performance is not a concern.

The whole attack has a complexity of 2^24 (mayby 25), with
a memory requirnement of 64MB. On a PIII/450 it will recover
a set of possible keys in less than in 20 seconds.

Sample run on 200MHz R4000 (?)
   
odin:~> time ./unhash fb 81 26 01 fe
CSS hash finder - gobbles memory ( 64 MB RAM ) Good luck

Searching for hash: fb 81 26 01 fe
Initializing k[1] lookup table
Initializing and clearing 64MB of RAM
Calculating big table. Wait, this takes time
--------------------------------
################################
Table init completed, now reversing hash

 Possible tmp key 21 5b 31 89 82
 Possible tmp key 3f 9d fa de f3
 Possible tmp key 53 4d fe 99 1e
114.602u 1.595s 1:59.12 97.5% 0+0k 0+0io 0pf+0w

This recovers 3 possible keys for the given hash.
I believe the wrong ones are easy to eliminate
by trying to decode the datastreams. ( It takes
almost 2 minutes on this CPU, but at least it runs
on bigendians as well )
 
  frank


--------- Fully functional DiskKey Hash cracker ------------

[Compressed File Removed]


This sentence is unique in this respect; it can safely
be attributed to my employer, Funcom Oslo AS.
E3D2BCADBEF8C82F A5891D2B6730EA1B PGPmail preferred, finger for key
There is no place like N59 50.558' E010 50.870'. (WGS84)