Spelen met de PTT telefoon-CD 1. De PTT telefoon-CD werkt niet onder Linux Vorige maand nam ik van iemand voor Hfl 25,- een CD over, en daar heb ik veel plezier van gehad - zoiets is leuker dan vijf boekjes met cryptogrammen. Het had er alle schijn van dat deze CD de telefoonnummers van Nederland bevatte. Op mijn Linux PC voerde ik onder de DOS emulator dosemu het commando "install" van deze CD uit, hetgeen resulteerde in een programma genaamd "ptt.exe". So far so good. Bij het opstarten van ptt.exe verscheen echter een rood venster, dat mij vermaande "Deze versie is single-user", waarna het programma beeindigd werd. Wat flauw nu. En ik werkte toch echt in mijn eentje op deze PC. Zou de PTT niet van Unix houden? De help desk opgebeld. "U heeft zeker een network driver in CONFIG.SYS?". Wel, niet echt, maar mijn toegang tot het Linux filesysteem, inclusief het `mount point' van de CD, ziet er voor DOS uit als een `network driver'. En ik heb geen `driver' om onder DOS mijn CD's te lezen. Is deze CD nu geheel onbruikbaar? 2. Maar de beveiliging is kinderlijk eenvoudig Die avond keek ik nog eens naar die CD. Er waren programma's genaamd pttdm.e, pttds.e, pttwm.e, pttws.e. Zouden dat misschien DOS en Windows versies zijn, in `single-user' en `multi-user' uitvoering? Het file pttds.e was even groot als de geinstalleerde ptt.exe, maar niet hetzelfde. Ik drukte de byte-gewijze XOR tussen beide files af. 0146, 0147, 0150, 0151, .... Interessant. Als we hetzelfde algorithme nu loslaten op pttdm.e, er rekening mee houdend dat het eerste byte van een .exe file bekend is? En ja hoor, dat levert een werkende ptt.exe op, kennelijk de `multi-user' versie. Alles bij elkaar had dat zeven minuten gekost. 3. Een probleem: de PTT wil niet zoeken zonder stad. Enige tijd later wilde ik het adres van iemand weten waarvan ik alleen de naam had - een weinig voorkomende naam. Hij woonde in de buurt van Amsterdam, maar niet in Amsterdam, niet in Amstelveen, en PTT inlichtingen kunnen niets zeggen als je de stad niet kent. Gelukkig is daar de telefoon-CD! Maar ptt.exe wil ook niet zoeken zonder een stad. Dan zelf maar een zoekprogrammaatje schrijven. Maar de gegevens staan versleuteld op de CD. Dan eerst maar de versleuteling kraken. Gezien bovenstaande ervaring kan dat niet moeilijk zijn. Maar dat viel een beetje tegen. Om tien uur 's ochtends begonnen, had ik pas 's nachts om drie uur het gezochte adres. 4. Hoe ontcijfer ik een CD? In principe zijn er twee heel verschillende manieren om dit probleem aan te pakken. Je kunt de informatie zelf net zolang besnuffelen totdat je begrijpt hoe die opgeborgen is, en je kunt het bijgeleverde programma disassembleren en zien hoe dat programma de informatie decodeert. Ik heb dit verhaal aan een aantal mensen verteld, en ondertussen begrepen dat anderen de tweede weg met succes bewandeld hebben. Op het net is een programma foon.exe beschikbaar dat de CD direct leest. Maar, mogelijk in de luren gelegd door het gemak waarmee pttdm.e te lezen was, koos ik voor de eerste weg. Het directory a/asd (kennelijk voor Amsterdam) bevat de files adres.dat, adres.idx, adres.occ, naam.dat, naam.idx, naam.occ, postcode.dat, postcode.idx, postcode.occ en asd.am, asd.as, asd.dm, asd.ds. Het ziet er naar uit dat de *.dat, *.occ, *.idx bestanden, die samen veel kleiner zijn dan het 8.4MB grote asd.dm, index bestanden zijn op naam, adres en postcode, en dat de kleine asd.as, asd.ds de `single-user' versies zijn van de grotere asd.am, asd.dm. 5. De indeling in blokken Het file asd.am is 8502 bytes groot, en asd.dm 8407375. De eerste zal wel hulpinformatie bevatten, en we concentreren ons op de tweede. De frequentieverdeling is tamelijk scheef - de minstvoorkomende byte komt 23676 keer voor, de meestvoorkomende byte 57610. Dat lijkt niet op de uitvoer van een goed compressie programma. Stel dat het ASCII tekst was, versluierd door te XOR-en met een reeks bytes - de sleutel. Een expliciet gegeven `one-time pad' kan niet gebruikt zijn, daarvoor is het programma te klein. Maar een rij bytes gegenereerd door een random-generator zou onpraktisch zijn - tenslotte moet ptt.exe er snel in kunnen zoeken. Dus valt een periodiciteit, of althans een eenvoudige regel, te verwachten. Nu is een kenmerk van ASCII dat het voorste bit 0 is, en dus het voorste bit van de byte waarmee ge-XOR-d wordt direct zichtbaar is. Ik rekende de correlatie uit tussen de 4096 voorste bits van bytes 0 tot 4095, en de 4096 voorste bits van bytes i tot 4095+i voor i=1,2,3,... Het resultaat was verrassend: een hoge correlatie voor i=6389, 12668, 19297, 25195, 31424, 37401, 44210, ... Om te beginnen bevestigt dit het vermoeden van een via XOR versluierd file, maar er is geen periodiciteit. Integendeel, het file is versluierd in blokken van ongeveer 6000 bytes. De waarde van de correlatie was ook interessant: telkens ongeveer 0.25: vijf van de acht bits komen overeen. Dus het file is geen zuiver ASCII file maar heeft (bij random verdeling) ongeveer 25% bytes die een 1 als voorste bit hebben. Zoeken in asd.am naar de getallen 0, 6389, 12668, 19297, ... laat zien dat die daar voorkomen als 4-byte getallen na 0, 6, 12, 18, ... bytes. Inspectie van de tussengelegen bytes laat de successieve verschillen 6389-0, 12668-6389, ... zien. Kortom: asd.am is een niet-versluierd file met 6-byte records met de structuur struct { int4 offset; /* 4 bytes, meest significante het laatst */ int2 length; /* 2 bytes, idem */ } die ons de indeling in blokken van asd.dm vertelt. Natuurlijk is het lengte-veld redundant. Inspectie van asd.as leert dat deze dezelfde structuur heeft. Dit file beschrijft de blokken van asd.ds, die ook via autocorrelatie binnen asd.ds gevonden worden (maar nu correlatie over slechts 512 bits); deze blokken zijn ruim 800 bytes groot. 6. Cijfers Verschillende pogingen om correlaties tussen de i-de posities van elk van de blokken uit te rekenen, geven duidelijke resultaten aan het begin, en steeds minder duidelijke naar mate i groter wordt. Dit, en het feit dat de blokken ongelijke lengten hebben suggereert sterk dat een blok bestaat uit een aantal records, waarbij de records variabele lengte hebben. Laten we zoeken naar het telefoonnummer. Gezocht een opeenvolgende groep cijfers. Als ik aannam dat de i-de positie van elk blok bestond uit de werkelijke waarde ge-XOR-d met een byte x_i, en dat de werkelijke waarde een cijfer was, dan volgt hieruit een beperking op x_i. Dit uitproberend bleken er vijf waarden van i te zijn (0,12,13,14,15) waarvoor alle 1417 beperkingen consistent zijn. Omdat ik naar een opeenvolgend groepje zocht keek ik naar i=12,13,14,15. De mogelijke waarden voor x_i waren respectievelijk: 0-7, 48-49, 30-31, 12-13. Dat er paren x,x+1 optreden is niet gek: als c de code van een cijfer is, dan is (c ^ 1) ook zo'n code. Maar het groepje van acht 0-7 laat zien dat op die plaats nooit een cijfer 8 of 9 voorkomt. Decoderen met als waarden x_12 = 0, x_13 = 48, x_14 = 30, x_15 = 12 levert de reeks getallen 5046, 5009, 5005, 5068, 5083, 5004, 5069, 6001, 6001, 5074, ..., bijna altijd met tweede cijfer 0, hoewel ook bijv. 5833 voorkomt. Dit lijkt helemaal niet op een stuk telefoonnummer, maar zou heel goed de postcode geweest kunnen zijn. Postcodes in Amsterdam beginnen met 10.., dus waarschijnlijk is x_12 = 4, x_13 = 48. Om deze theorie te controleren kijken we in een andere stad. 7. Postcodes Op dit moment is het nuttig om te vermelden dat op de telefoon-CD een niet-versleuteld file wpl.dat staat, waarvan de structuur onmiddelljk duidelijk is. De records zien er als volgt uit: struct { char wpl[40]; /* naam van de plaats */ char number[5]; /* kengetal */ char lowpc[4]; /* laagst voorkomende postcode */ char highpc[4]; /* hoogst voorkomende postcode */ char filename[6]; /* bestandsnaam */ int2 seq; /* volgnummer, minst significant eerst */ } Afdrukken levert iets in de volgende geest: 0. 06 06 06 1. AADORP 0546 7610-7611 aadorp 2. AAG 01188 4363 aagtekerke 3. AAG 01186 4363 aagtekerke 4. AAG 01187 4363 aagtekerke 5. AALDEN 05917 7854 aalden 6. AALDEN 05934 7854 aalden 7. AALDEN 05935 7854 aalden 8. AALG 04187 5308 aalst gld 9. AALG 04185 5308 aalst gld 10. AALZUM 05190 9120-9121 aalzum ... 5300. WAT 05212 8438 wateren 5301. GDW 079 2735 gelderswoude 5302. LNDE 05287 7925 linde dr 5303. LNDE 05230 7925 linde dr 5304. LNDE 05231 7925 linde dr 5305. LNDE 05286 7925 linde dr 10001. ADB 01177 4527 draaibrug 10002. ADB 01170 4527 draaibrug 10003. ADB 01175 4527 draaibrug 10004. ADB 01178 4527 draaibrug 10005. AEGUM 05105 9006 eagum ... 12156. ZWO 03242 3890-3899 zuiderflevo 12157. ZWO 03200 3890-3899 zuiderflevo 12158. ZYD 02262 1736 blokhuizen 12159. ZYD 02240 1736 blokhuizen (Kortom, er zit een sprong in de rij met volgnummers, van 5305 naar 10001. Ik weet niet welke betekenis dat heeft.) Dit file laat zien welke steden slechts 1 postcode hebben. Nu volgt heel snel dat x_12 = 4, x_13 = 48, x_14 = 31, x_15 = 13. Dit bevestigt de theorie dat het bestand ge-XOR-d is met een rij getallen, en stelt ons in staat om de eerste postcode te lezen in elk blok van elk bestand. 8. Kengetallen Echter, in Aalden, met postcode 7854 zien we in drie blokken 7854, maar in het vierde 1778. Misschien is hier een verschuiving opgetreden, en volgen de 54 hierna. Dan zou x_16 = 0, x_17 = 11. Hernieuwde inspectie van Amsterdam leert nu dat in de gevallen waarin de postcode er niet uit ziet als 1CCCLL met C een cijfer en L een letter, er 201012, 201078, 201015, ... staat. Misschien staat het kengetal voor de postcode. Dan zou x_10 = 205 en x_11 = 0. Die waarde van x_11 lijkt wel goed, we vinden een 6 bij Aadorp, en dat is het laatste cijfer van het kengetal 0546, maar het cijfer daarvoor is niet goed. Ook bij Alblasserdam, met kengetal 01859 zien we u-umlaut 859. Deze rare byte (op de tiende plaats) is telkens 0xff, onafhankelijk van de stad. Laten we deze overslaan, en ervoor kijken. Dus bij nader inzien is x_10 onbekend. Maar ook daarvoor staat soms zo'n rare byte. In Alblasserdam (met kengetal 01859) wordt 859 voorafgegaan door (hexadecimaal) 0a, 22, ff, 31 maar 9 wordt voorafgegaan door 35, 1a, 35, ff. In Abcoude (met kengetal 02946) wordt 946 voorafgegaan door 11, 22, ff, 32 maar 6 wordt voorafgegaan door 36, 1b, 34, ff. Dit suggereert dat we x_9 = x_10 = 0 moeten nemen, maar een byte ff in het gedecodeerde file moeten overslaan. Dit leidt tot groot succes, en afmaken van het kengetal leert ook dat x_7 = 4, x_8 = 34. Inspectie van Amsterdam leert dat het byte voor de " 020" telkens 0 is. Als dat ook zo is wanneer " 020" op positie 7 begint dan is x_6 = 0. Dit klopt ook op andere plaatsen (1188 in Aagtekerke, " 06" in Aalzum, enz.). 9. Compressie? Maar nadere inspectie van Abcoude leert dat die rare byte niet altijd ff is. Soms is hij ef (op de 9e plaats), en dan staat er onzin op de 14e en 15e plaats. In Amsterdam, Den Haag, Rotterdam en Utrecht treedt dit verschijnsel niet op, maar in Eindhoven komt bf voor op de 10e plaats, waarbij onzin op de 17e plaats komt. In Haarlem komt df voor op de 9e plaats, waarbij onzin op de 15e en 16e plaats komt; ook fb op de 10e plaats, met onzin op de 13e en 14e plaats. Het lijkt erop dat die rare bytes bitmaps zijn die van achteraf worden afgelezen. Is een bit 1 dan is er niets aan de hand, is het 0 dan gebeurt er iets speciaals. Nu begrijpen we ook waarom die rare byte niet altijd op dezelfde plaats komt: staat op de 0e plaats fd (ja, puristen, dit is fout, maar ik nummer mijn plaatsen vanaf 0, en heb hier geen zin om plaats i de (i+1)e plaats te noemen, dat is te verwarrend), dan staat de volgende rare byte op de 10e plaats, staat er ff, dan staat de volgende rare byte op de 9e plaats. Kortom, elk 1 bit slaat op 1 byte, elk 0 bit slaat op 2 bytes, en na alle 8 bits te hebben afgewerkt komt de volgende rare byte. En passant hebben we vastgesteld dat x_0 = 0, en kijkend naar het volgende voorkomen van een rare byte (en aannemend dat die meestal ff zal zijn) vinden we x_18 = 0x73, x_19 = 0x72, x_20 = 0x65. De twee bytes die aangewezen worden door het 0-bit in een raar byte zijn f7,f0 in het geval van Haarlem (na het kengetal 023 en het eerste cijfer van de postcode 2, terwijl de postcodes in Haarlem 2000-2037 zijn); in het geval van Abcoude zijn ze e8,f3 op een plaats waar de postcode 1390 of 1391 verwacht wordt. In het geval van Eindhoven zijn ze fe,f0. Je zou kunnen fantaseren dat dit een soort Lempel-Ziv compressie is, met een pointer naar vanwaar geciteerd wordt, en een veld dat de lengte aangeeft. Dat zou ook kunnen verklaren waarom dit verschijnsel zo weinig voorkomt aan het begin van een blok: er valt nog bijna niets te citeren. De f7,f0 zouden dan het kengetal 023 kunnen citeren teneinde de postcode 2023 te maken. Speculatie. We gaan voort op de ingeslagen weg: de waarde van de vorige rare byte voorspelt waar de volgende komt, en we gokken dat die meestal ff zal zijn. Dit levert x_27 = 0, x_28 = 0x1c, x_36 = 0x75, x_37 = 0, x_45 = 0x82, x_46 = 0xd8, x_47 = 0x30. De variatie in de rare byte groeit. 10. Gebruik het telefoonboek. In het eerste blok van Amsterdam volgt na de postcode "A,". Nu leert inspectie van het telefoonboek dat de eerste (gewone) regel "a, e. vd, m polostr 82/1 .... 6168591", dus misschien volgt na de postcode de naam. Het programma ptt.exe weet van dit persoon ook nog de postcode 1057WT te vermelden, geheel in overeenstemming met het tot dusver gevondene. Probeer voor de volgende bytes "E." en "VD". De eerste poging werkt direct; in het derde blok komt nu bij de naam "AANN", vast een aannemersbedrijf. Nu volgen de x_i snel, dankzij AANNEMERSBEDRyF HILHORST AMSTERDAM BV. Het blijkt dat de velden Naam, Straat, Huisnummer, en Telefoonnummer van elkaar gescheiden worden door het teken @. Het ACCOUNTANTSKANTOOR KOTTERMAN NEURINK & CO bevestigt de Lempel-Ziv theorie: de tweede ANT staat weergegeven door 07,00. Ook in de ACOB,.,WONINGBOUWVERENIGING wordt de tweede ING weergegeven door 0a,00. Het programma ptt.exe kent ook een tweede Van der A, namelijk "a, e. vd, r bloemgartensngl 30, 1069PR amsterdam, 020-6195528" (die niet in mijn telefoonboek van Mei 1994 voorkomt - zeker pas telefoon gekregen). De 10 van de postcode, en wat daar misschien nog aan vooraf gaat, wordt geciteerd door ee,fb; de "A,E.VD,@" door 00,05. Al weet ik nog niet wat voor die postcode staat, het is hetzelfde aan het begin van elk van de blokken, en we zouden kunnen vermoeden dat ee,fb hier 14 bytes citeert. De conclusie ligt voor de hand: de laatste 4 bits zijn het lengte veld van Lempel-Ziv en geven de lengte min 3 weer, en de resterende 12 bits stellen een pointer voor. Ook na "ABRAAS,F H.,@NIERSSTR@30" worden drie spaties geciteerd met eb,f0 en na het telefoonnummer wordt het begin van het volgende entry met ee,fb geciteerd. Dus de pointer telt niet hoeveel bytes het geleden was, maar wijst naar een vaste plaats in de buffer, waarbij ee,fb helemaal naar het begin wijst. Als kort na ee,f de pointer 00,0 komt, dan is vast de f het meest significante deel. Laten we aannemen dat een buffer ter lengte 4096 vanaf fee gevuld wordt door een cyclisch ronddraaiende pointer. De eerste poging werkt nog niet geheel. (Achteraf snap ik niet meer waarom niet - deze beschrijving is precies goed.) 11. 6000 XOR bytes gevonden Het werk dat ik eerst met de hand deed om rare bytes te vinden, kan natuurlijk ook geautomatiseerd worden. Het oude criterium: zovaak mogelijk 0xff, werkt op den duur niet meer, en houdt bovendien geen rekening met de hele verdeling van gevonden waarden maar alleen met de waarde met de hoogste frequentie. Laten we bij nader inzien die byte x_i kiezen waarvoor zoveel mogelijk 1 bits gevonden worden op plaats i. Het voorafgaande handwerk had de x_i gevonden voor i tussen 6 en 81, en dit argument is voldoende voor i tot aan 1020 of zo, waar een foute keuze weldra troep oplevert. Nu dat x_i voor i tussen 6 en 1000 bekend is, moeten we opnieuw kijken naar hoe de Lempel-Ziv precies werkt. Met eb,f0 worden drie spaties geciteerd. Dus de buffer moet al vanaf feb gevuld zijn. Met 05,00 wordt vanaf 0 geciteerd, dus na 18 symbolen moet de pointer bij 000 zijn, dus hij begon op fee. (Dit alles aannemende dat op de derde plaats inderdaad het lengtegedeelte 1 is.) Later blijkt dat met e8,f3 zes spaties worden geciteerd (bij het VERENIGD CARGADOORSKANTOOR BV bestaat de postcode uit spaties), en met e7,f4 zeven spaties (in JANSMA,J O.,@ENGELENSTR@5 3@ te Heerenveen) dus de voorgeschiedenis voordat gestart wordt op fee bevat in elk geval zeven spaties in fe7-fed. Nu werkt Lempel-Ziv tot ieders tevredenheid. Twee bytes voor het nulbyte dat aan het kengetal voorafgaat, staat meestal een spatie, maar een F bij een faxnummer. Dit blijkt bij blokken die met ff beginnen. Begint een blok met fd dan is alles 2 verschoven, en dit levert ons x_4 = 0xfb. Bij A-LINE TECHNOLOGIES blijkt dat dit type byte behalve spatie of F ook een T kan bevatten, voor telex. Het kengetal bij telex is 9900. Bij A-PARTNERS IN DIENSTVERLENING BV blijkt dat er ook een A kan staan, voor autotelefoon. Ik heb ook een N gezien (maar alleen bij 06 nummers) - weet nog niet wat dat betekent. De eerste 8 bytes van elk entry (afgezien van de byte gewoon/fax) lijken binaire informatie te bevatten. Meestal staan er nullen, maar soms, als er in de telefoongids een regel met extra informatie staat, dan staan hier andere bytes. Men zou kunnen vermoeden dat het pointers naar een ander file zijn. Maar welk file komt in aanmerking? Misschien die asm.as en asm.ds die ik eerst voor single-user versies aanzag? Gelukkig blijken die met dezelfde rij bytes ge-XOR-d te zijn, en zijn die files direct leesbaar. Inderdaad bevatten ze de extra opmerkingen. Aangezien dit file niet met binaire getallen begint vinden we nu direct x_i voor i<8 (door AUDIO EN ALARM te lezen in het eerste entry). Het begin van de eerste drie blokken van het file asd.dm ziet er nu zo uit ("rare bytes" gemarkeerd met : en compressiewijzers met _; rechts het resultaat, met "binaire" bytes vervangen door _): 0: fd: 00 ee_ f1_ bc 00 0 _____ __ 0 9: 2 ff: 0 1 0 5 7 W T 201057WT 18: A ff: , E . V D , @ A,E.VD,@ 27: M ff: P O L O S T M POLOST 36: R f7: @ 8 2 eb_ f0_ 1 @ R@82 1@ 45: 6 1 bf: 6 8 5 9 1 @ 6168591@ 54: ee_ fb_ 6 f7: 9 P R 00_ 05_ _____ __ 0201069PRA,E.VD,@ 63: R B L ff: O E M G R BLOEMG 72: A R T E ff: N S N G ARTENSNG 81: L @ 3 0 be: 18_ 00_ 9 5 L@30@6195 90: 5 2 8 20_ 0c_ 1 ff: 9 C 528@_____ __ 0201019C 99: E A & A ff: , . EA & A,. 108: , O N T W E ff: R P ,ONTWERP 0: fd: 00 ee_ f1_ bc 00 0 _____ __ 0 9: 2 ff: 0 1 0 1 8 V E 201018VE 18: A ff: A L D E R E N AALDEREN 27: ff: N E T , R . V NET,R.V 36: A ff: N , @ N W K AN,@NW K 45: E ff: I Z E R S G R EIZERSGR 54: @ fb: 9 4 eb_ f0_ 1 2 @ @94 12@ 63: 6 3 e7: 8 0 6 26_ 00_ ee_ 6380612@ 72: fc_ 6 V D fe: 00_ 03_ I N _____ __ 0201016VDAALDERIN 81: G , M . , ff: @ 3 E G,M.,@3E 90: L O O I fe: 1b_ 00_ D LOOIERSD 99: W S T R @ 6 f9: 9 eb_ WSTR@69 108: f0_ 27_ 00_ 2 5 2 8 4 bd: 2@625284 0: fd: 00 ee_ f1_ bc 00 0 _____ __ 0 9: 2 ff: 0 1 0 1 4 A W 201014AW 18: A ff: A N N E M E R AANNEMER 27: S ff: B E D R  F SBEDRF 36: H ff: I L H O R S T HILHORST 45: ff: A M S T E R D AMSTERD 54: A ff: M B V , . , AM BV,., 63: @ ff: S C H A K E L @SCHAKEL 72: S ff: T R @ 2 6 @ 6 STR@26@6 81: 8 ff: 2 2 4 3 8 @ 6 822438@6 90: 00 7b: 00 02 f2_ f7_ 8 3 H ____ __ 0201083H 99: G 00_ 0f_ ff: L L E N GAANNEMERSBEDRF HILLEN 108: & R e7: O O S 65_ 00_ & ROOSEN Pogingen om de "rare byte volger" verder dan 1000 te krijgen gaan moeizaam. Verderop in elk blok komt veel compressie voor, en het criterium van veel enen in een raar byte is niet goed meer. Een premie op het aantal "goede" symbolen (letters, cijfers, spatie, punt, comma) helpt nog tot 1400 of zo, en ik moet "met de hand" een aantal XOR waarden fixeren. Wat kleine verfijningen aan het oude algoritme hebben echter plotseling groot succes, en leveren twee minuten later foutloos de x_i voor i tot ongeveer 6100 op. In plaats van rare bytes volgen, en een premie voor goede symbolen, gebruikte ik alleen nog maar een premie voor goede symbolen, en voegde @ en - toe aan de goede symbolen. Voorbij 6100 gaat het weer moeizaam, en met veel handwerk kom ik tot 6400. Het probleem is dat het aantal blokken afneemt, zodat de statistiek over een kleinere verzameling is. Ik probeer Amsterdam, Rotterdam, Den Haag, Utrecht, Eindhoven en Haarlem simultaan te behandelen, maar dat helpt niet veel en maakt alleen het programma veel trager. Het lijkt duidelijk dat een backtracker nodig is. Het probleem doet wat denken aan het decoderen van convolutiecodes. 12. Structuur in de XOR bytes Het probleem doemt nu al op: hoe moet ik in vredesnaam de laatste XOR bytes vinden? De meeste blokken in Amsterdam hebben een lengte van goed 6000, maar sommige blokken zijn langer dan 7000. Statistiek over alle steden leerde dat de grootste blokken in Amsterdam, Rotterdam, Den Haag, Utrecht, Venlo, Eindhoven, Maastricht, Nijmegen, Haarlem voorkomen. Maar in de laatstgenoemde vijf steden zijn alle blokken kleiner dan 6700, terwijl de eerstgenoemde vier als maximum 7720, 7476, 7158, 7009 halen. Het op een na grootste blok in Amsterdam heeft lengte 7445. Kortom: de laatste 1000 XOR waarden moeten uit heel weinig gegevens gevonden worden, en de laatste 275 vormen een effectief "one-time pad", en kunnen alleen gevonden worden door vergelijking met bekende plaintext. Zoeken naar de string met bytes in het programma ptt.exe levert niets op. Zouden de bytes door een random generator geproduceerd zijn? De frequentie verdeling van de eerste 6000 waarden is 0: 663 110 78 58 63 44 49 33 80 39 78 73 42 19 42 30 16: 30 22 23 20 40 24 39 25 19 16 20 19 43 25 22 27 32: 17 41 35 35 26 16 38 26 28 45 32 24 75 22 26 13 48: 47 16 18 15 10 14 21 16 11 7 18 6 15 17 8 26 64: 35 63 23 29 31 29 29 28 11 20 22 17 6 37 39 11 80: 24 20 25 11 28 29 23 17 25 5 27 19 21 21 12 23 96: 15 7 16 16 10 18 18 19 19 29 9 37 12 18 20 40 112: 22 28 39 20 25 31 31 19 14 25 11 15 19 20 17 11 128: 45 26 16 13 9 10 7 10 34 18 26 17 18 22 49 22 144: 11 18 9 8 4 11 15 5 16 10 13 9 15 15 12 13 160: 3 9 10 14 17 11 12 14 16 15 11 11 14 7 18 7 176: 11 15 15 3 4 11 10 7 10 10 11 7 11 11 16 7 192: 18 24 14 15 18 14 10 9 32 26 11 37 13 21 18 13 208: 14 5 17 27 22 4 12 12 22 4 24 8 16 4 64 14 224: 6 27 4 9 11 7 8 8 10 10 7 17 5 15 18 14 240: 8 9 12 9 9 14 16 7 34 24 24 32 23 24 19 35 met opvallend veel nullen, en veel meer (3461) even dan (2539) oneven waarden. Laten we de posities van de nullen plotten. 0:.. . . ... . . . . . 60: . . . . . . .. .. .. . . . .. .. . . 120: .. .. . .. . . . . .. . . 180: . . .. . . .. .. .. . .. . . 240: ... ... .. . . .. 300: . . . .. .. . .. . . .. . . . . 360: . . .. ... . . 420: . . .. 480: . 540: . 600: . . 660: . . 720: . 780: 840: 900: 960: . ... . . 1020: . .. . . . . . . . . . 1080: . . . . .. . .. . . . .. 1140: .. . . . .. . . . .. . 1200: . . .. .. . . . . .. . . . . . 1260: . . .. . . .. . . 1320:.. . . . . . . . . . . . . . . 1380: . . . . . . . 1440: .. .. 1500: . . . . 1560: 1620: . 1680: 1740: . 1800: 1860: 1920: 1980: . ... . . . . . 2040: . . . . .. . . .. .. . . . 2100: . .. . . . . .. . . . 2160:. . . . . . . . . . . . 2220: . . . . . .. 2280: .. . . .. .. .. . . .. .. . . . 2340: . .. ... . .. .. .. . .. . 2400: . . . . 2460: 2520: . 2580: . 2640: . . . 2700: . 2760: 2820: 2880: 2940: . 3000: .. . . .. .. .. . . 3060: .. . . . . . . . . .. . .. .. 3120: . .. . . .. .. . . . . . . . . 3180: . . . . . . ... .. . . . . ... ... . 3240: . . . . . . . . .. .. 3300: . . .. . .. . . . . . . 3360: . .. . . .. . . . . 3420: . .. . . . . . 3480: . . . 3540: 3600: 3660: . .. 3720: 3780: 3840: 3900: . . 3960: . . . . ... 4020:. ... . . . . .. 4080: .. . . . . . . . . . . . . . . 4140: . . .. . . . .. . . . 4200: . . . . . . . . . 4260: . . . . .. .. . .. .. . . 4320: . . .. . .. . . .. . .. . .. . 4380: . . . . 4440: . . . 4500: . . 4560: 4620: . . .. . 4680: 4740: . 4800: 4860: 4920: . . . 4980: . . ... . .. . . 5040: . . . . . . .. . . 5100: . . ... .. . . ... ... .. . .. . . 5160: . . .. . . . . .. . . .. . . 5220:.. . .. .. . . . . . 5280: . .. .. . ... . ... .. 5340:.. . .. . . .. . ... .. . . . 5400: . .. . 5460: . . 5520: . . 5580: . 5640: .. . 5700: . 5760: 5820: 5880: 5940: Ha! Een duidelijk patroon - 500 plaatsen met veel nullen afgewisseld door 500 plaatsen met weinig nullen. Maar niet precies periodiek. Wat zou de pseudo-periode eigenlijk zijn? Kijk op hoeveel plaatsen x[i] en x[i+delta] gelijk zijn, met delta tussen de 900 en de 1100. Dit aantal blijkt altijd kleiner dat 300, behalve voor delta=975,999,1001,1003 met respectievelijk 310,938,489,328 gelijke waarden. Kortom, delta=999 springt er duidelijk uit, met delta=1001 als goede tweede. Bekijk de frequentieverdeling en het patroon van nullen van de rij x[i]^x[i+999]. We vinden 0: 938 84 140 64 86 32 54 45 48 35 86 51 43 23 32 17 16: 24 23 42 44 66 8 46 13 25 16 8 22 105 11 45 23 32: 17 14 21 2 17 22 41 38 22 19 31 7 17 19 9 12 48: 70 14 24 1 20 11 52 3 13 6 16 16 29 17 32 11 64: 18 23 18 24 32 33 25 24 11 20 5 13 29 58 75 5 80: 27 3 21 5 18 11 31 4 11 17 16 12 10 12 29 11 96: 23 26 16 13 22 68 28 24 6 26 12 19 19 9 8 26 112: 30 23 38 34 28 8 45 45 27 4 28 18 40 8 38 23 128: 53 32 13 15 7 5 0 17 17 67 34 16 13 17 32 35 144: 11 6 24 11 12 1 8 12 7 6 7 1 22 2 6 6 160: 5 5 1 13 9 3 13 17 30 48 32 14 8 0 11 0 176: 18 13 18 0 7 2 2 1 15 12 3 11 11 10 6 24 192: 25 8 9 22 14 8 1 1 17 16 17 10 12 18 7 11 208: 1 0 2 7 3 10 13 5 24 15 11 18 2 30 8 18 224: 0 28 6 17 6 8 11 2 0 3 6 12 33 3 14 2 240: 7 12 14 19 10 12 13 5 7 30 12 20 23 2 17 31 en 0: . ........ . . . . . . 60: . . . . . . . . . . . . .. 120: . . . . .. . . .. . 180: . .. . . . . . .. . . 240: . . .. . . ................ 300: ... . ... . . ... . . . . . .. . 360: ... . .. . . . . . . . . . . . . . 420: . . . . . . ... . . . . . 480: . . . . . . .. 540:. . . . . 600: . 660: .... . . . . . .. 720: . . 780: . . 840: . 900: . 960: . . . . . ........ 1020: . . . . . . . . . . 1080: . . . . . . . . .. . . . . 1140: .. . . .. . . .. . 1200: . . . . .. . . . . 1260: .. . . ................ ... 1320:. ... . . ... . . . . . .. . ... . .. . . . 1380: . . . . . . . . . . . . . . 1440:. . ... . . . . . . . . . 1500: . . .. . 1560: . . . . 1620: . .... . . . 1680: . . .. . 1740: . 1800: . . . 1860: 1920: . . . 1980: . . . ........ . . . . 2040: . . . . . . . . . . . 2100:. . . .. . . . . .. . 2160: . .. . . .. . . . . . .. 2220:. . . . .. 2280: . . ................ ... . ... . . . 2340:.. . . . . . .. . ... . .. . . . . . . . . 2400: . . . . . . . . . . . . 2460:.. . . . . . . . . . 2520: . . .. . . 2580: . . . 2640: . .... . . . 2700: . . .. . 2760: . . . 2820: . 2880: 2940: . . . . . 3000: . ........ . . . . . . 3060: . . . . . . . . . . . . .. 3120: . . . . .. . . .. . 3180: . .. . . . . . .. . . 3240: . . .. . . ............. 3300:... ... . ... . . ... . . . . . .. 3360:. ... . .. . . . . . . . . . . . . 3420:. . . . . . . ... . . . . 3480:. . . . . . . 3540:.. . . . . . 3600: 3660: . .... . . . . . 3720: .. . . 3780: . . 3840: . 3900: . 3960: . . . . . ........ 4020: . . . . . . . . . 4080: . . . . . . . . . .. . . . . 4140: .. . . .. . . .. . 4200: . . . . .. . . . . 4260: .. . . ................ ... 4320: . ... . . ... . . . . . .. . ... . .. . . 4380: . . . . . . . . . . . . . . . 4440: . . ... . . . . . . . . . 4500: . . .. . 4560: . . . . 4620: . .... . . . 4680: . . .. . 4740: . 4800: . . . 4860: 4920: . . 4980:. . . . ........ . . . 5040: . . . . . . . . . . . 5100: . . . . .. . . . . .. . 5160: . .. . . .. . . . . . 5220:.. . . . . .. 5280: . . ................ ... . ... . . 5340: ... . . . . . .. . ... . .. . . . . . . . 5400: . . . . . . . . . . . . 5460: . . 5520: . . 5580: . 5640: .. . 5700: . 5760: 5820: 5880: 5940: Ja, maar, dit is periodiek! Met periode 1001! Controleren leert inderdaad dat x[i] ^ x[i+999] ^ x[i+1001] ^ x[i+2000] = 0 voor i < 4449, en deze recurrente betrekking levert de resterende x[i] op. We zijn klaar! Ik decodeer alle .dm files van de telefoon CD nu in een groot file (413MB, 108MB gecomprimeerd), en grep naar de gezochte naam. Een kwartier later was heel Nederland doorzocht en de naam gevonden. Alles bijelkaar had dit 17 uur gekost. 13. Fouten op de CD-ROM KLUGT,G D.VD,@GRONINGENLN@12 122@@355309@ heeft een scheider @ teveel voor het telefoonnummer. Het programma ptt.exe kan dan ook het telefoonnummer niet vinden. Als het voorlaatste entry voor een stad een verwijzing heeft, dan ook het laatste entry, en beide verwijzingen zijn gelijk. Het is zeer onwaarschijnlijk dat dit de bedoeling is. Zo zijn de laatste twee entries in Altforst: 6541AK 080- 719111 ZUIDGELDERSE NUTSBEDRVEN NV WINSELINGSEWG 10 openingstd ma t/m vr 9-16 u@@@ voor verhuismeldingen@03440@10020@ voor storingen d en n bereikbaar@ 080@777222@ 6628AB 08874- 1715 ZWALUW, J., VD KERKSTR 1 openingstd ma t/m vr 9-16 u@@@ voor verhuismeldingen@03440@10020@ voor storingen d en n bereikbaar@ 080@777222@ Een programmeerfout. 14. Opmerkingen 14A. De compressie In ztm.as staat "DORP/DRIEMANSPOLDER, 8" waarin 18 spaties geciteerd worden. Dus, er moeten minstens 18 spaties klaar staan bij de start van Lempel-Ziv. Meer kan niet voorkomen omdat het lengteveld in Lempel-Ziv alleen de waarden 3-18 kan aannemen. 14B. Het typeveld Types A en N komen alleen bij 06 nummers voor, en omgekeerd komen bij 06 alleen de types A en N voor. Kortom, A betekent: mobiel 06-nummer (autotelefoon, pieper, e.d.) en N betekent niet-mobiel 06-nummer. 14C. De naam. De abonneenaam wordt soms voorafgegaan door een tekst die eindigt in een #, die in de gids als kopje afgedrukt wordt. Bijvoorbeeld ... amusement en erotiek#zimbabwe zoenln amusement en erotiek#zin in een trio tje, maar dan wel live amusement en erotiek#zoek je een lekkere studente ... 14D. Het huisnummer Het huisnummerveld bestaat uit een string van 0-9 posities: het eigenlijke huisnummer, mogelijk gevolgd door een of meer spaties en een subnummer (meestal etagenummer). In de gids wordt / als scheider gebruikt: 19/hs. Het subnummer, indien aanwezig, begint op positie 5. Heeft het huisnummer 4-i cijfers, dan wordt het door i+1 spaties gevolgd. Heeft het huisnummer 5 of meer posities, dan kan er geen subnummer zijn. Aldus vindt men in Hoofddorp GRAAN VOOR VISCH 159052ET waar eigenlijk 15905/2 had moeten staan. Staat er toch een spatie op positie 5 of verder, dan geeft het programma ptt.exe dit niet weer als subnummer: J J E KRIST, WHEREDK,BY WAGENWG 7, PURMEREND. Ook "US ARKJE" en "PAX VOBIS" hebben geen subnummer. Staan er meer spaties dan is er vaak sprake van een serie huisnummers: 57-59 wordt weergegeven door "57 59", waarbij het tweede nummer op positie 6 begint. Een subnummer staat soms ook helemaal achteraan in het veld van 9 posities: "178 3" voor 178/3. Overigens is dit wat rommelig geregeld - allerlei kleine variaties komen voor. Het huisnummer wordt afgekapt op 9 posities, en kan ook niet-cijfers bevatten: MAZZELTOV, PARKEERGA, TO130BOOT, TO78AST, ACHTER301, 39006CARV, 10000KEET, BLOEMKIOS, GREENPOIN. Soms eindigt de straatnaam op ,XX waarbij XX eigenlijk bij het huisnummerveld hoort: LANDINRICHTINGSDIENST FLAKKEE, LANGEWG,BY CAPELLEWG, OUDE TONGE of S J DIEKEMA, DONDERSEWG,BY ALICELN, NORG. Eindigt de straatnaam op ,AB (aan boord) dan is het meestal de naam van een schip: UNIT CLEANING SERVICE, NOORDERSLUISWG,AB LAMAROTTE, IJMUIDEN. In plaats van ",AB" staat er soms " AB": W H VAN TIEM, WAALBANDK AB 84732ELI, BENEDEN LEEUWEN Er staat ",TO" voor "tegenover": FRUITKIOSK DINY EN HENK, V BAERLESTR,TO 92/KIOSK, AMSTERDAM T/O CONCERTGEBOUW. Hele grote getallen komen voor: INDUSTRIEWG 1102729, DEVENTER of SEVENINGSEWG 9999914, KAMPEN. (In het eerste geval stel ik me voor dat nummer 11 onderverdeeld moest worden; in het laatste geval dat de 99999 een negatief getal moet aanduiden.) 15. Naschrift Op het net is ook programmatuur beschikbaar (geschreven door `RTZ') die de PTT CD-ROMs leest. Bovenbeschreven decodering was voor de Dec1994 versie, maar de codering van de Maart1995 versie is weer wat anders, en ook deze is gekraakt. Ik schreef de auteur en vroeg hoe hij te werk was gegaan. Hieronder zijn antwoord. From: snrwo1@xs4all.nl (René Wonnink) Subject: Re: ptt cd-rom Als antwoord op je vragen het volgende: Eerst heb ik gekeken met een windows programma welke bestanden er worden gelezen door het programma. Daar viel mij toen het volgende op: beide programma's lezen een aantal blokken van 1 kb in van zichzelf en van het andere programma (ik heb het dan over ptt.exe en pttw.exe). Waarom de programma's dat deden was mij toen nog niet duidelijk. Alle bestanden behalve de echte data bestanden (die een extentie van DM hebben) kon ik interpreteren door ze te bekijken (met een hex editor) nadat ik wist waar en wanneer er uit gelezen werd. De meeste van die files zijn overigens uiteindelijk alleen maar indexen naar het data bestand (de DM bestanden). Toen ik de DM bestanden bekeek vermoedde ik dat de gelezen datablokken werden xor'ed met de al eerder genoemde blokken die in de initialisatie worden ingelezen. Helaas bleek het niet zo simpel. Van de ingelezen blokken worden maar een gedeelte van de bytes gebruikt om een xor blok op te bouwen. Bovendien zijn het er twee en wel twee met een verschillende lengte. Iin van 999 bytes en iin van 1001 bytes. Deze worden over de blokken van de dm file 'gelegd' met xor operaties maar met hun eigen cyclus, dus je kunt niet de blokken eerst samennemen. De eerste keer had ik geluk om de blokken te vinden door het dos programma op te starten en meteen weer te verlaten. Daarna startte ik een eigen programma op die de 640 kb van de pc dumpte in een file. Doordat ik de eerste paar bytes proefondervindelijk had gevonden dacht ik dat ik kon zoeken naar de blokken in die file, en voila ik vond ze. Door verder het windows programma met een debugger te tracen en op goed geluk breakpoints te zetten kon ik zien wat er nu eigenlijk gebeurde. Het heeft mij totaal best wel wat tijd gekost, ik ben enkele weken 's avonds zoet geweest ermee, maar dat kwam hoofdzakelijk doordat ik totaal geen ervaring had in het tracen van een programma waarvan je de source niet hebt. Ook het gebruik van de debugger heeft de nodige tijd gekost, iets wat zich echter wel heeft terugbetaald bij het 'kraken' van de maart1995 versie. Maart1995: Iin blik op de dm files gaf al aan dat de xorblokken (als die nog steeds gebruikt werden) waren gewijzigd. De rest zag er vrijwel hetzelfde uit. Met weer kijken met de debugger zag ik dat de manier waarop de blokken weer werden teruggecodeerd totaal anders leek. Niets was echter minder waar. De blokken worden nog steeds opgebouwd op de al eerder beschreven manier, maar er zijn een stuk meer nodig, omdat van ieder gelezen blok er veel minder bytes worden 'gepakt'. Waarom ze bij de ptt denken dat het dan moeilijker zou zijn begrijp ik niet, alhoewel ik zelf geen ervaring heb met cryptographie. De blokken zijn bij de maart95 overigens 1019 en 1021 bytes lang. Verder is er veranderd dat de decodering niet de blokken over elkaar legt maar iedere keer een offset uitrekent, afhankelijk van de plaats in het blok. Dus het eerste byte van een DM blok wordt bijv. met de 227ste byte van het eerste blok gexor'ed en het 345de byte van het tweede blok. Volgende byte weer een andere offset, tot de 1019 en 1021 bytes geweest zijn, en dan weer van voren af aan. Dus ieder blok in de DM file wordt hetzelfde gecodeerd. Ik was al bang dat dat niet meer het geval zou zijn, want dat vind ik zelf toch wel een betere bescherming, omdat je dan met het analyseren zoals jij het hebt gedaan, moeilijker tot resultaten zult komen. Het is overigens wel grappig dat mijn decodeer routine maar een aantal regels (C) coding in beslag nemen. Een nieuwe versie van de maart 95 cdrom is beschikbaar op mijn home page: http://www.xs4all.nl/~snrwo1/index.html Er zat een bug in de woonplaats Capelle aan den IJssel op de maart 95 editie. Daarom heeft de ptt een bugfix beschikbaar die je kunt installeren. Groeten, Rene (Wonnink)