Posted on Leave a comment

Driver fingerprinting

When your driving style is as unique as your signature

Perhaps it doesn’t come as a surprise that we all have unique driving styles. My father is a calm, sometimes even slow driver. My mother is more temperamental in her driving ways – always cutting the line where she can (this was a highly useful skill when we were late to school). When I close my eyes, I can immediately tell whether my mother or father is behind the wheel.

But so can anybody – using in-vehicle logs. Turns out that these driving styles can translate to bits and bytes that our in-vehicle sensors record.

In-vehicle sensors

There are a number of systems built in our cars for various purposes – to regulate emission, to optimize engine performance or to log and detect malfunctions. Think of your dashboard for example – you can see your speed, consumption and RPM all at a glance! The data required for these comes from in-vehicle sensors. This data is converted and processed by ECUs (Electronic Control Unit), which are essentially small computers inside our cars. The ECUs communicate with each other through the so-called CAN-bus (CAN – Controller Area Network).

The CAN-bus whisperer: OBD dongle

The data sent over the CAN-bus can be easily captured. For example, so-called ”insurance dongles” (or On-Board Diagnostics dongles) can collect and send in-vehicle sensor data to insurance companies. They use this information to give you discounts for example, if you drive safely.

Another similar approach to lowering insurance premiums is using telematics data, as described here. The biggest difference however, is that telematics data are currently subject to data protection laws, unlike CAN logs.

The OBD dongles connect to the ODBII interface of the vehicle.
These devices are not expensive at all (prices start at 10$), and can come with mobile apps so you can look at your data from your phone!

In some cases, we cannot access CAN logs directly through an OBD port (or at least not all parts of it). There is usually a gateway regulating access to these data.

Even though CAN-bus data can be readily accessible (and not encrypted), the interpretation of the messages is still a challenge.
There is no global standard, and the structure of the messages varies from manufacturer to manufacturer.
Without the cooperation of manufacturers, it is hard to reverse engineer these messages… but not impossible! For example we can use our phone to record the speed while driving. Then, we can extract the brake signal (which records how far we press the brake pedal) by searching for a signal that usually decreases right before the observed speed decreases (of course it does not need to always match, there are multiple scenarios where one can lose speed without braking…). A similar search can be conducted for the gaspedal signal as well.
Of course this is one approach, but if you want to know how to reverse-engineer signals using machine learning techniques, check out my talented colleagues’ paper (Lestyan et al., 2019)!

Driver fingerprinting

So what can we do with the obtained CAN-bus data? Turns out, that we can use it to determine who was behind the wheel.

How it works

Driver fingerprinting or driver re-identification uses the data collected from the CAN logs (called traces) to correctly identify drivers. From these traces, we can extract the data from one sensor to obtain a time series (measuring speed for example).

The input of such a model can consist of multiple time series, like in the example image below. However, to obtain these time series, first we need to reverse-engineer them. Then, we can use Machine Learning to make predictions on the driver’s identity.

For my 2018 Scientific Students’ Association paper I used the measurements of 5 sensors (namely brake, clutch, gaspedal, rpm and speed). Brake, clutch and gaspedal sensors measure the position of the respective pedals. As for the rest: rpm records the revolutions per minute and speed measures the vehicle’s speed. I was also able to work on data collected from 33 drivers, whereas state-of-the-art driver re-identification papers only published results on models that had to distinguish 2-15 drivers. My model achieved a 66% mean accuracy, given a mere 10 second trace as input!

One might think that this time-window can be pushed down even further – theorizing that the distinguishing part in everyone’s driving could be the part where they accelerate or shift gears, which is about 2-3 seconds long. However, when driving in a city there are a lot of situations where one must stand still (in morning traffic, in front of a stoplight, or while letting that old lady cross the street). Related work suggests that all the information needed to identify a
driver can be obtained from the measurements of a single turn. This confirms the intuition that someone’s driving can be quite accurately distinguished based on how they slow down, switch gears and accelerate.

After writing this paper me and my colleagues were motivated to extend this research by eliminating the first step: reverse engineering the raw data.

Driver re-identification on raw data

In our paper titled Automatic Driver Identification from In-Vehicle Network Logs we demonstrated that it is possible to achieve the same results without having to reverse engineer and pre-select signals from the CAN log.

We collected 72 time series from unknown sensors and trained a Deep Learning model on each of them. Not all time series were equally good inputs for the re-identification task, which is why we combined the top-10 performing classifiers into one mixture model. We achieved a mean accuracy of 75-85% for CAN traces whose length varied between 20 and 120 seconds. This approach outperforms the model that was trained on extracted signals, which might indicate that among the 72 time-series there are some that are even better for distinguishing drivers than the ones that were originally extracted! However, we don’t know their meaning, and thus their possible connection to the drivers’ fingerprints.

Great! Acquiring an OBD dongle that can read CAN logs is not only cheap, it turns out you don’t have to understand the data to build a working driver-fingerprinting classifier with it.

Privacy implications

So now that we know that our in-vehicle data could potentially identify us, why should we protect it? I mean, aside from well-wishing insurance companies who give us discounts, who could possibly get our data?

Except if… car companies were motivated to sell CAN logs to 3rd parties. And currently they could do so. Without our consent (because it is not considered to be personal data as of yet). Uh-oh.

Driving data: the car industry’s new cash cow?

Many sources suggest the lucrativity of driving data – McKinzey&Co, a management consulting firm, estimates that ”data from connected cars will be worth up to $750 billion by 2030”. Companies are already preparing for the market
for data from cars, which is expected to be even bigger than the market for the cars themselves according to this Forbes article.

Future ideas include selling data to map provider firms (Google Maps, Waze, etc.) looking to provide more accurate
traffic information, or selling consumption-related and other statistics to operators of larger vehicle fleets.
And if driver identification is possible, it opens all kinds of doors. For instance, you can use driver identification to notify you any time someone else is driving your car. Or your car could “memorize” your driving fingerprint, and adjust your seat, and radio to your liking as soon as you turn the corner. Neat, right? But wait, something is missing from the list – the biggest cash-grabber of them all: ad revenues. In the hands of 3rd party advertisers, our cars could be yet another gateway to personalised advertisements.

Just like with any other personal information that could potentially identify us: using such data should require our consent!

GDPR and awareness

Because of how new these findings are, it is still unclear whether drivers are completely informed about the wealth of personal information that their CAN logs potentially reveal. Hopefully this post was an eye-opener to the reader that CAN log data are not only personal, but that there is also a great incentive to sell/use them.

Although car companies stress that the collected network logs are “anonymized”, the proper anonymization of such high-dimensional data is notoriously difficult in practice without significantly degrading accuracy (Aggarwal et al., 2005). Even aggregated metrics aren’t always completely safe (Dinur and Nissim, 2003).

More about reconstruction attacks in theory and in practice.

The feasibility to identify (and/or profile) a driver means that CAN logs are indeed personal data and, as such, are subject to the European General Data Protection Regulation (GDPR) as of 25 May 2018. It is a fundamental duty of companies handling such data to adequately inform drivers and protect their personal data. Failing to do so does not only ruin customer trust, but can also result in a fine up to 20 million Euros.

Closing thoughts

We have seen that it is fairly easy to access this data, and will probably become even more accessible in the not-so-distant future of connected vehicles.

Massachusets has voted (Nov. 4th, 2020) on standardizing access to car data (to extend the state’s right-to-repair law)! This could set a standard for the vehicles to come…

We have also seen that even without the reverse-engineering of the logs, identifying drivers is still possible. Turns out, our phones aren’t the only devices that store and/or process information which could potentially identify us. 🙂

I don’t know what driving fingerprint I possess, but I hope I can eventually get the best from both of my parents: my father’s calm (but ultimately safe) driving and my mother’s mad parking skills!

A special thank you to the following people who have provided me with useful feedback and suggestions:
Gergely Ács, Andris Gazdag, Ferenc Huszár and Viktor Remeli.

Posted on Leave a comment

Gépi Tanulás & Személyes Adatok Védelme

Ez a blogposzt az utolsó egy három részes sorozatból mely a gépi tanulás adatvédelmi kockázatairól kíván közérthető nyelven egy átfogó képet nyújtani. Az első egy bevezető volt a gépi tanulás világába, a második a létező támadásokat ölelte át. Ebben a záró részben a lehetséges védekezéseket mutatjuk be.

Continue reading Gépi Tanulás & Személyes Adatok Védelme
Posted on Leave a comment

Gépi Tanulás & Személyes Adatok Támadása

Ez a blogposzt a második egy három részes sorozatból mely a gépi tanulás adatvédelmi kockázatairól kíván közérthető nyelven egy átfogó képet nyújtani. Az első egy bevezető volt a gépi tanulás világába, ez a létező támadásait öleli át, míg az utolsó rész a lehetséges védekezéseket mutatja majd be.

Continue reading Gépi Tanulás & Személyes Adatok Támadása

Posted on Leave a comment

Gépi Tanulás

Ez a blogposzt az első egy három részes sorozatból mely a gépi tanulás adatvédelmi kockázatairól kíván közérthető nyelven egy átfogó képet nyújtani. Ez az első egy bevezető a gépi tanulás világába. A következő a létező támadásokat fogja átölelni, míg az utolsó záró rész a lehetséges védekezéseket mutatja majd be.

Continue reading Gépi Tanulás

Posted on Leave a comment

Interdependent privacy in effect: the collateral damage of third-party apps on Facebook

by Iraklis Symeonidis, COSIC, KU Leuven
and Gergely Biczók, CrySyS Lab, BME

Recent technological advancements have enabled the collection of large amounts of personal data at an ever-increasing rate. Data analytics companies such as Cambridge Analytica (CA) and Palantir can collect rich information about individuals’ everyday lives and habits from big data-silos, enabling profiling and micro-targeting of individuals such as in the case of political elections or predictive policing. As it has been reported at several major news outlets already in 2015, approximately 50 million Facebook (FB) profiles have been harvested by Aleksandr Kogan’s app, “thisisyourdigitallife”, through his company Global Science Research (GSR) in collaboration with CA. This data has been used to draw a detailed psychological profile for every person affected, which in turn enabled CA to target them with personalized political ads potentially affecting the outcome of the 2016 US presidential elections. Whether CA used similar techniques at the time of the Brexit vote, elections in Kenya and an undisclosed Eastern European country (and several other countries) is under investigation. Both Kogan and CA deny allegations and say they have complied regulations and acted in good faith.

This blog post does not take sides in this debate, rather, it provides technical insight into the data collection mechanism, namely collateral information collection, that has enabled harvesting the FB profiles of the friends of app users. In this context, the term collateral damage refers to the privacy loss these friends suffer. In a larger nexus, this issue is part of interdependent privacy when your privacy depends unavoidably on the actions of others (in this case, your friends). Continue reading Interdependent privacy in effect: the collateral damage of third-party apps on Facebook

Posted on Leave a comment

Az aggregált adat és a GDPR

Az előző posztban megnéztük hogyan definiálja a GDPR a személyes adat fogalmát és mi számít személyes adatnak a definíció szerint. Ebben a posztban egy mérnöki (és talán jogi) szempontból jóval izgalmasabb kérdést vizsgálunk: Személyes adatnak minősülhet-e az aggregált/statisztikai adat?

A probléma azért érdekes, mert a legtöbb cég/kormány/szervezet többnyire aggregált adatokat oszt meg, bízva abban, hogy ezek nem személyes adatok. Valóban, a GDPR így nyilatkozik a statisztikai adatról (26. preambulum): "[...] Az adatvédelem elveit [...] az anonim információkra nem kell alkalmazni, nevezetesen olyan információkra, amelyek nem azonosított vagy azonosítható természetes személyre vonatkoznak, valamint az olyan személyes adatokra, amelyeket olyan módon anonimizáltak, amelynek következtében az érintett nem vagy többé nem azonosítható. Ez a rendelet ezért nem vonatkozik az ilyen anonim információk kezelésére, a statisztikai vagy kutatási célú adatkezelést is ideértve." Később (162. preambulum): "[...] Statisztikai célúnak minősül a személyes adatok statisztikai felmérések vagy statisztikai eredmények kiszámításának céljából történő gyűjtése és kezelése. [...] A statisztikai célból következik, hogy a statisztikai célú adatkezelés eredménye nem személyes adat, hanem összesített [aggregált] adat, és hogy ezt az eredményt vagy a személyes adatokat nem használják fel konkrét természetes személyekre vonatkozó intézkedések vagy döntések alátámasztására." Mindazonáltal a GDPR is elismeri a 89. cikkben, hogy a statisztikai adatok nem feltétlenül anonim adatok, és azokra az adatvédelmi szabályozás már alkalmazandó.

Ebben a posztban megmutatjuk, hogy aggregált adatokból valóban rekonstruálhatók személyes adatok (pontosabban egyének rekordjai egy adatbázisban amin az aggregált adatot számolták), és így aggregált (összesített) adat is lehet személyes adat, akár még a GDPR 4. cikkének értelmezésében is. Példaként azt is megmutatjuk, hogy ha egy telekom cég kiadná a mobiltelefon-tornyok látogatottságát az idő függvényében (vagyis minden egyes toronynál levő előfizetők számát fél óránként), akkor ebből az aggregált adatból az egyes előfizetők által meglátogatott tornyok (helyek) listája közel 80%-os pontossággal rekonstruálható. Így az ilyen összesített adat lehet személyes (sőt akár érzékeny), és ebben az esetben az ilyen adat megfelelő anonimizációja/torzítása lehet szükséges.

Mi az aggregált adat?

A GDPR ugyan nem definiálja az aggregált (összesített) adat fogalmát, de valószínűleg több egyén adatán számolt statisztikai/összesített adatot ért alatta. Például az 1. táblázatban aggregált adat a betegek vércukrának átlaga, vagy szórása, vagy eloszlása, stb. Valójában az aggregált/statisztikai adatok előállíthatók több elemi ún. számláló lekérdezések (counting query) eredményeinek valamilyen függvényeként. Ilyen lekérdezés például: Hány olyan beteg van az adatbázisban akik Alzheimerben szenvednek? Vagy, hány olyan beteg van akiknek a vércukra 4.1 és 4.2 közé esik? Az ilyen lekérdezéseket egy mintával definiáljuk (pl. betegség attribútum értéke "Alzheimer", vagy vércukor attribútum értéke egy adott tartományba esik), és eredményük azon rekordok száma az adatbázisban, amelyekre az adott minta illeszkedik (úgy mondjuk, hogy az ilyen rekordokat a lekérdezés lefedi). Például az 1. táblázaton alkalmazva az első lekérdezés eredménye 1, mivel csak egy beteg szenved Alzheimerben (vagyis ez a lekérdezés csak a 3. rekordot fedi le). A második lekérdezés eredménye viszont 0, mivel egy beteg vércukra sem esik 4.1 és 4.2 közé.

A számláló lekérdezésekkel szinte az összes statisztikai adat kiszámolható. Például ha kiváncsiak vagyunk betegségek eloszlására/hisztogramjára az adatbázisban (vagyis az egyes betegségek gyakoriságára), akkor minden betegség előfordulását meg kell számolni az adatbázisban (annyi lekérdezés szükséges ahány betegség lehetséges). Építhetők finomabb eloszlások specifikusabb mintával; pl. Hány olyan beteg van az adatbázisban akik Alzheimerben szenvednek és 40 évnél fiatalabb és Budapesten laknak? Numerikus attribútumra (pl. vércukor) hasonló az eljárás, de ott a minta értéktartományokat tartalmaz (pl. hány olyan beteg van akiknek a vércukra 4.1 és 4.2 közé esik?). Az ilyen eloszlásokból pedig további statisztikák számolhatók; átlagok, szórások, medián, max, min, stb.

Rekord Nem Irányítószám Vércukor Betegség
1. Kovács Attila 1123 4.3 Meningitis
2. Kovács Attila 1123 5.2 Crohn-betegség
3. Kovács Ferenc 1114 6.1 Alzheimer
4. Kovács Ferenc 8423 3.2 Crohn-betegség
5. Kovács Ferenc 1114 7.1 Lábfejtörés
6. Nagy Tibor 1113 6.2 Crohn-betegség

1. táblázat: Kórházi adatok

A számláló lekérdezések univerzitása miatt általában elég ha csak a számláló lekérdezések eredményeit osztják meg (mint aggregált adatot), amit aztán további statisztikai adatok számításához felhasználhatnak a kérdezők. Ezért a továbbiakban csak ilyen lekérdezésekre fókuszálunk, és aggregált (statisztikai) adat alatt számláló lekérdezések eredményeinek összességét értjük.

FONTOS: A vizsgálat célja csakis az aggregált adat, nem az adatbázis amin az aggregátumot számoljuk. Más szavakkal a kérdés, hogy személyes adatnak minősülhetnek-e az aggregátumok (bizonyos mintára illeszkedő rekordok száma) egy olyan támadó számára, aki nem fér hozzá az adatbázishoz?

Interaktív és nem interaktív lekérdezések

Van amikor a cég megengedi, hogy a kérdezők (támadók) specifikálják a lekérdezéseket a korábbi lekérdezéseik függvényében (interaktív, online eset), de van amikor csak előre meghatározott lekérdezések eredményeit teszik közzé (nem interaktív, offline eset). Nyilván az interaktív eset veszélyesebb adatvédelmi szempontból, hiszen akkor a támadó a lekérdezéseit a korábbi lekérdezések eredményeinek a függvényében állíthatja össze (adaptív támadás).

Célzott támadás

Tekintsük Zsuzsa nénit az előző posztból, aki a Facebookon talál egy K. Ferenc nevű felhasználót. K. Ferenc megosztott képei alapján egy kis községben lakik, aminek az irányítószámát is megadta (8423), a 20-as éveiben jár, és krónikus bőrkiütésben szenved (a pontos betegségét ez alapján még nem ismeri). Zsuzsa néni ugyan az 1. táblázathoz nem fér hozzá, de jogosult az alábbi lekérdezéshez: Hány olyan beteg van aki az $X$ irányítószám alatt lakik és a betegsége $Y$? Ezután lefuttatja az összes olyan kérést, ahol $X=8423$ és $Y$ pedig egy olyan betegség, aminek tünete a krónikus bőrkiütés. Ha csak egy ilyen lekérdezés értéke 1 a többié pedig 0, akkor Zsuzsa néni megtalálta K. Ferenc pontos betegségét (erre jó esély van ha K. Ferenc vidéki, és a községben ahol él más nem volt a kórházban krónikus bőrkiütéssel).

Ismét látható, hogy a támadó háttértudása (a publikus információ, hogy egy fiatal K. Ferenc krónikus bőrkiütésben szenved és egy ismert községben lakik) lehetővé teheti személyes adatok visszafejtését aggregált adatokból. Ahogyan azt az előző posztban is megmutattuk, manapság a legtöbb emberről rengeteg nyilvános adat elérhető maguk vagy mások által, így a hasonló támadások létezését lehetetlen kizárni. Például előfordulhat, hogy Zsuzsa néni nemcsak bőrkiütést hanem egyéb más tünetet is megfigyel K. Ferencről a képei alapján, így a szóba jöhető betegségek száma kevesebb, vagyis még kevesebb lekérdezésből még nagyobb eséllyel kiderítheti K. Ferenc pontos betegségét. Például videón szereplő személyek pulzusa megállapítható pusztán a videóból az illetők tudta nélkül.

Naívan gondolhatnánk, hogy az ilyen támadások megelőzhetők ha nem válaszolunk meg olyan lekérdezéseket, amelyek eredménye túl kicsi (vagyis túl kevés rekordot fednek le). Sajnos ez nem mindig segít; pl. az 1. táblázatban az összes Crohn betegek száma 3 (első lekérdezés), a budapesti Crohn betegek száma 2 (második lekérdezés), akkor a kettő különbsége adja a vidéki Crohn betegek számát amire csak egy rekord illeszkedik (K. Ferenc), és amit így már nem kell lekérdezni (differencing attack). Az ilyen "problémás" lekérdezések detekciója nem mindig könnyű, mivel általános esetben két lekérdezés ekvivalenciája eldönthetetlen, valamint az egyes rekordok kiszámíthatóságának eldöntése adott aggregátumokból gyakran nehéz probléma.

A következőkben több személyt érintő globális (mass) támadásokra fókuszálunk, és a fenti differencing támadás ötletét általánosítjuk; megmutatjuk, hogy ha elég sok lekérdezést válaszolnak meg, akkor egy támadó képes lehet az eredeti rekordokat visszaállítani a lekérdezések összességéből függetlenül az egyes eredmények nagyságától. Először ezt egy olyan példán mutatjuk be, ahol a támadó a lekérdezéseket ő maga választja. Látni fogjuk, hogy kb. a rekordok számával megegyező lekérdezésekből a rekordok jó része helyreállítható. A második példában a támadó nem interaktív, vagyis nem képes a lekérdezéseket megválasztani, de így is rekonstruálhatja a rekordok több mint 70%-át az adat jellemzőit (mint háttértudást) kihasználva.

Globális támadás 1: Rekordok interaktív helyreállítása

A támadás alapötlete, hogy minden egyes megválaszolt lekérdezéssel növeljük egy sikeres differencing támadás esélyét valamely rekordra. Kicsit pontosabban, minden megválaszolt lekérdezés egy egyenletet definiál a lefedett rekordokon mint ismeretleneken. Ha elég sok egyenletünk (megválaszolt lekérdezésünk) van, akkor azok egyértelműen megoldhatóvá válnak és az ismeretlenek (rekordok) meghatározhatók.

Vegyük példaként a 2. és 3. táblázatot, ahol a 2. táblázat a 3. táblázatban szereplő egyének kvázi azonosítóit tartalmazza. A 3. táblázat első attribútuma az illető korának felel meg (ugyanaz mint a 2. táblázat 3. oszlopa), a többi attribútumok pedig Budapest főbb helyeit (POI) reprezentálják, és értékük 1, ha az illető meglátogatta az adott helyet, egyébként nulla. Tegyük fel, hogy a két táblázat rekordjai ugyanahhoz a személyhez tartoznak (vagyis a 3. táblázat $i$-ik sora és 4. táblázat $i$-ik sora ugyanazon személy adatai).

Rekord Nem Kor Lakhely
1. Férfi 23 Budapest
2. 43 Budapest
3. Férfi 45 Budapest
4. 36 Budapest
... ... ... ...

2. táblázat: Demográfiai adatok (kvázi azonosítók)

A 2. táblázathoz hozzáfér a támadó, viszont a 3. táblázathoz nem. Tegyük fel továbbá, hogy a támadó az alábbi $Q([X,Y],Z)$ lekérdezést hajthatja végre: Hány olyan személy van a 3. táblázatban, akiknek kora az $[X, Y]$ intervallumba esik és meglátogatták a $Z$ helyet? Vagyis $Q([X,Y], Z)$ azon rekordok számát jelöli, ahol a kor értéke legalább $X$ és legfeljebb $Y$, valamint $Z$ attribútum/hely értéke 1. Tegyük fel, hogy nem válaszolunk meg túl kevés rekordot lefedő lekérdezéseket (pl. ha $Q([X,Y],Z) < 10$), az adatbázisban pedig több száz rekord van. A támadó célja a 3. táblázat rekonstruálása a lekérdezések eredményeit és a 2. táblázatot felhasználva.

Rekord Kor Móricz Zsigmond körtér Allee Mom Park ... Széll Kálmán tér
1. 23 0 1 1 ... 0
2. 43 1 1 1 ... 0
3. 45 0 0 0 ... 1
4. 36 0 0 1 ... 1
... ... ... ... ... ...

3. táblázat: Helyzeti adatok

Először csak egy oszlopot rekonstruálunk, a többi hasonlóan történik. Legyen $Z$ egy előre kiválasztott hely (pl. $Z$ = "Allee"). A cél a 3. táblázat $Z$ értékének megfelelő oszlopának rekonstruálása, amit $x_1, x_2, \ldots, x_n$ ismeretlenekkel jelölünk és ahol $n$ az összes rekordok száma a táblázatban (vagyis $x_i=1$ ha a támadó szerint az $i$-ik rekord meglátogatta a Z helyet, egyébként $x_i=0$). A támadás lényegében egy egyszerű lineáris egyenletrendszer megoldásából áll:

  1. Válaszd a kor lehetséges értékeinek egy véletlen intervallumát (pl. $[X=32;Y=40]$)?
  2. Kérdezd a $Q([X,Y],Z)$ értékét
  3. Ismételd meg a fenti műveleteket $t$-szer, így kapod $t$ darab lekérdezés eredményeit: $Q_1([X_1, Y_1], Z), Q_2([X_2, Y_2], Z), \ldots, Q_t([X_t, Y_t], Z)$
  4. Minden $Q_j$ lekérdezéshez határozd meg azon $S_j \subseteq \{1,2, \ldots, n\}$ rekordok halmazát a 2. táblázatból, amelyet a $Q_j$ lekérdezés lefed (vagyis a koruk a $[X_j, Y_j]$ intervallumba esik).
  5. Old meg az alábbi $t$ egyenletből és $n$ feltételből álló lineáris egyenletrendszert: $$ \begin{matrix} \sum_{i \in S_1} x_i = Q_1([X_1, Y_1], Z),\\ \sum_{i \in S_2} x_i = Q_2([X_2, Y_2], Z), \\ \vdots\\ \sum_{i \in S_t} x_i = Q_t([X_t, Y_t], Z), \end{matrix} $$ $$\text{ahol:}\; 0 \leq x_i \leq 1$$

  6. Kerekítsd $x_i$ értékeit: $x_i = 1$ ha $x_i > 1/2$, máskülönben $x_i = 0$

Bebizonyítható, hogy $t= n \log^2 n$ megválaszolt lekérdezés esetén a 6. lépésben kapott $x_i$ értékek nagy része helyes (tehát $x_1, x_2, \ldots, x_n$ megegyezik a 3. táblázat $Z$ értének megfelelő oszlopával), és így az eredeti adatbázis $Z$ értékének megfelelő oszlopa rekonstruálható. Pl. ha az adatbázisban 128 rekord van, akkor abból legalább 124 helyreállítható így.

Természetesen a 3. táblázat egy visszaállított oszlopa önmagában még nem minősül személyes adatnak, hiszen ahhoz minden visszaállított értékhez hozzá kellene rendelni egy természetes személyt. Ezért a fenti támadás megismételhető több, mondjuk $k>20$ oszlopra/helyre. Ha valaki szerepel az adatbázisban, akkor annak 5-10 helye már egyértelműen azonosítja azt, ezért az illető publikusan elérhető Facebook/Instagram profilja összevethető a rekonstruált rekordokkal; jó eséllyel csak az ő rekonstruált rekordja fogja a Facebook profiljában szereplő helyek együttesét tartalmazni. Mivel a rekonstrukciós pontosság magas, a támadás sikervalószínűsége elég nagy. Így ha a támadás plauzibilis (a támadó valóban hozzáfér a 2. táblázathoz és a személyek közösségi profiljához), akkor a lekérdezések összessége személyes adatnak minősülhet a GDPR szerint.


  1. A 4. lépésben megoldandó egyenletrendszer azért lineáris, mert a lekérdezések (subset-sum query) az attribútum-értékek lineáris függvénye (jelen esetben összege). Az egyenletrendszer bármely LP solver-rel megoldható (pl. CPLEX, glpk, stb.).
  2. Az eredeti adatbázis visszaállíthatósága $t= n \log^2 n$ lekérdezés esetén garantált, ahol minden lekérdezés minden rekordot 1/2 eséllyel tartalmaz. Ez a fenti példában nem feltétlen igaz, hiszen ott a kor alapján választunk egyenletes eloszlás szerint nem pedig magukat a rekordokat 1/2 valószínűséggel (ebből az is következik, hogy a fenti támadás nem adaptív). Ennek ellenére a gyakorlatban a támadás jó eséllyel működik.
  3. A megoldandó egyenletrendszer $n$ változót és $t= n \log^2 n$ egyenletet/feltételt tartalmaz. Létezik olyan támadás, ami $t= n$ lekérdezéssel hasonló rekonstrukciós pontosságot ér el, viszont itt a lekérdezéseket determinisztikusan és nem véletlenszerűen választják.
  4. Ezek a támadások akkor is működhetnek, ha a lekérdezések értékéhez véletlen zajt adunk hozzá (query perturbation). Ebben az esetben egyenletek helyett egyenlőtlenségek rendszerét kell megoldani, aminek megoldása az első támadással a legrosszabb esetben $O(n^5 \log^4 n)$ lépést, míg a másodikkal csak $O(n\log n)$ lépést igényel. Ha a zaj által okozott abszolút hiba legfeljebb $E$, akkor $n - 4E^2$ rekord helyreállítható. Pl. ha $n=256$ és $E=3$, akkor 220 rekord helyreállítható. Viszont érdekes módon $E > \sqrt{n}$ torzítás már megakadályozhatja a rekordok rekonstrukcióját.

Globális támadás 2: Telekom (CDR) adatok nem interaktív helyreállítása

A fenti támadás azért működik, mert a támadó a lekérdezéseket (pontosabban azok mintáját) képes megválasztani. Ebben az is segíti, hogy hozzáfér minden rekord kvázi azonosítóihoz (2. táblázathoz), és így pontosan tudja, hogy melyik lekérdezés melyik rekordokat fedi le. Ha ezt nem tudná, akkor az 5. lépésben definiált egyenletrendszer nem lenne megoldható, hiszen nem tudná, hogy pontosan melyik ismeretlenek (rekordok) szerepelnek az egyenletek bal oldalán. Felmerül a kérdés: sikeres lehet-e egy olyan nem interaktív támadás, ahol a lekérdezéseket a támadó nem tudja megválasztani, a rekordok többségének kvázi azonosítóit nem ismeri, és csak előre definiált lekérdezések eredményét ismerheti? Ez egy gyengébb támadó jóval kevesebb háttértudással, és így sokkal inkább plauzibilis a gyakorlatban. Ha egy ilyen plauzibilis támadó sikervalószínűsége elég nagy, akkor gyanítható, hogy az aggregált adat személyesnek minősül még a GDPR 4. cikkének értelmében is. Ezt megerősítve a következőkben bemutatunk egy közelmúltban publikált támadást egy gyakorlati alkalmazáson a fenti plauzibilis támadót feltételezve.

Az adat

Napjainkban népszerű statisztikai adat az emberek térbeli sűrűsége, vagyis bizonyos helyek (POI-k) látogatottsága az idő függvényében. Ez az aggregált adat értékes, hiszen felhasználható közlekedési hálózat optimalizációjára, új szolgáltatások (pl. áruházak) telepítési helyének meghatározásához, de akár járványok terjedésének modellezéséhez is. Egy populáció ilyen térbeli eloszlása jól becsülhető a használatban levő mobiltelefonok helyzeti információiból; amikor egy előfizető hívást vagy adatforgalmat kezdeményez/fogad, rögzítésre kerül a telefontorony (és az időpont), amellyel az előfizető telefonja kapcsolatban van. Mivel az ilyen tornyok elég sűrűn helyezkednek el (főleg sűrűn lakott területen), így a tornyok pozíciójából az előfizetők térbeli helyzete jól becsülhető.

Ezt felismerve sok telekom cég monetizálná az ilyen hívási (ún. CDR) meta-adatokat. Viszont, ahogy az előző posztban is utaltunk rá, egy ilyen adatbázis nagy valószínűséggel sok személyes adatot tartalmaz, hiszen egy előfizető 4-5 tornya már jó eséllyel egyedi azonosítónak számít. Ezért a telekom cégek többsége a CDR adatot nem osztja meg, hanem csak az abból számolt aggregátumokat; minden toronyhoz az ott tartózkodott előfizetők számát minden fél órában (vagyis minden toronyhoz egy idősort). A következőkben megmutatjuk, hogy az ilyen statisztikai adat is lehet személyes.

A támadás célja

Adott $n$ előfizető akiknek hívási adataikat rögzítik $m$ toronynál az eredeti CDR adatbázisban. Az egyes tornyokat jelölje $T_1, T_2, \ldots, T_m$. Ebből az adatbázisból a cég minden $t$ időpontban kiszámolja a $\mathbf{P}^t = (p_1^t, p_2^t, \ldots, p_m^t)$ torony-látogatottságokat, ahol $p_j^t$ jelöli az $T_j$ toronynál levő előfizetők számát a $t$-edik időintervallumban/időpontban (pl. egy fél óra alatt). A cég csakis a $\mathbf{P}^t$-t osztja meg másokkal, bízva abban, hogy az ilyen aggregált adat nem minősül személyes adatnak.

Legyen $Y_{i,j}^t = 1$, ha az $i$-edik előfizető meglátogatta $T_j$ tornyot a $t$ időtartományban, máskülönben 0. Így $\mathbf{Y}^t$ egy $n \times m$ méretű bináris mátrix ami az egyes előfizetők toronylátogatásait reprezentálja $t$ időpontban. A támadás célja az $Y_{i,j}^t$ értékek rekonstruálása minden $i$ előfizetőre, $T_j$ toronyra, és $t$ időpontra úgy, hogy (1) $\sum_{i=1}^n Y_{i,j}^t = p_{j}^t$, vagyis az $\mathbf{Y}^t$ mátrix $j$ oszlopában található elemek összege a $T_j$ tornyot meglátogatott előfizetők száma egy időpontban, valamint (2) $\sum_{j=1}^m Y_{i,j}^t = 1$, vagyis egy előfizető egy időpontban (itt fél órában) csak egy tornyot látogathat meg. Ha többet látogat meg, akkor vesszük a legtöbbet meglátogatott tornyot az adott fél órában. Mivel vannak előfizetők akik nem minden fél órában használják a telefonjukat, az ilyen fél órákban a feltételezett toronylátogatásokat interpolációval becsüljük az ismert toronylátogatásokból.

A támadás alapötlete és menete

Ugyan a támadás első hallásra meghökkentő, az adat jellegét megnézve már nem tűnik olyan hihetetlennek. Valójában az adat három fő tulajdonságát használják ki:

  1. Predikálhatóság: Minden előfizető tornya egy adott időpontban jól becsülhető a korábban meglátogatott tornyokból; az időben következő torony szinte mindig közel van földrajzilag az éppen meglátogatott toronyhoz. Ezt azt is jelenti, hogy az előfizetők (ill. rekordjaik) jól szeparálhatók, hiszen ha két rekord $t$ időpontban távol van egymástól, azok jó eséllyel a $(t+1)$-ben is távol lesznek egymástól.

  2. Regularitás: Az előfizetők többsége minden nap hasonló (gyakran ugyanazon) tornyokat látogatja meg hasonló időkben, mivel a legtöbb ember napi rutinjai azonosak.

  3. Egyediség: Az előfizetők egymástól elég különböző tornyokat látogatnak meg, amit már több tanulmány szemléltetett; egy több milliós populációban egy előfizető bármely 4 meglátogatott tornya (az időpont órás pontosságával) egyedivé teszi őt az előfizetők között az esetek 98%-ában.

A három tulajdonságot szemlélteti az alábbi ábra, ahol 5 különböző előfizető térbeli helyzete látható két egymást követő nap.

alt text

A támadás először a rekordok predikálhatóságát felhasználva rekonstruálja a rekordokat (azaz az $\mathbf{Y}^t$ mátrixot) minden $t$-re egy napon belül, feltéve, hogy $\mathbf{P}^t$ ismert. Ezt megismétli minden egyes napra külön-külön. Végül a rekordok regularitását és egyediségét felhasználva az azonos előfizetőhöz tartozó rekonstruált rekordokat összerendeli a napok között.

Rekordok rekonstruálása adott $t$ időpontban

Tegyük fel, hogy a $(t-1)$-beli toronylátogatások ismertek $\mathbf{Y}^{t-1}$ formájában, valamint az összes torony látogatottsága $t$-ben $\mathbf{P}^t$ formájában. Hogyan tudnánk ezekből rekonstruálni $\mathbf{Y}^{t}$-t? Ha egy előfizető a $(t-1)$-ben a $T_j$ tornyot látogatta meg, akkor jó eséllyel a $t$ időpontban a $T_j$ toronyhoz közelebbi tornyokat fogja meglátogatni, vagyis lesznek tornyok amiket nagyobb eséllyel látogat meg, és lesznek amiket kisebb eséllyel a korábban meglátogatott tornyok (pl. $T_j$) függvényében. Így minden előfizető-torony $(i,j)$ párhoz hozzá tudunk rendelni egy $c_{i,j}^t$ "költséget" az idő függvényében, aminek értéke nagyobb, ha az $i$ előfizető kisebb eséllyel látogatta meg a $T_j$ tornyot, és kisebb, ha nagyobb eséllyel látogatta azt meg a $t$ időpontban. Keressük azt az előfizetők és tornyok közötti összerendelést $t$ időpontban (vagyis $\mathbf{Y}^{t}$-t), ami az összes előfizetőhöz az általuk legnagyobb eséllyel meglátogatott tornyokat rendeli. Lényegében az alábbi optimalizációs problémát kell megoldanunk minden $t$ időpontban, ahol az ismeretlenek $\mathbf{Y}^{t}$ mátrix elemei:

$$ \begin{matrix} \text{Adott}\; P^t = (p_1^t, p_2^t, \ldots, p_m^t), \\ \text{minimalizáld}\; \sum_{i=1}^n \sum_{j=1}^m c_{i,j}^t \times Y_{i,j}^t\; \text{összeget,}\\ \text{feltéve, hogy }\; Y_{i,j}^t \in \{0,1\},\: \sum_{i=1}^n Y_{i,j}^t = p_{j}^t,\: \sum_{j=1}^m Y_{i,j}^t = 1 \end{matrix} $$

A feladatot elképzelhetjük mint az alábbi gráf probléma megoldását minden $t$ időpontban. A gráf bal oldalán vannak az előfizetőknek megfelelő csúcsok, a jobb oldalon pedig a tornyoknak megfelelő csúcsok. Élek csakis a két oldal között lehetnek, ahol minden él súlya megegyezik az adott előfizető-torony pár költségével. Egy $i$ előfizető és $j$ torony között akkor van él, ha az $i$ előfizető meglátogatta $j$ tornyot a $t$ időpontban. A feladat a bal és jobb oldali csúcsok összekötése úgy, hogy (1) minden jobb oldalon levő csúcshoz (toronyhoz) csakis annyi bal odalon levő csúcsot (előfizetőt) köthetünk, ahányan meglátogatták azt a tornyot $t$ időpontban (ez adott $\mathbf{P}^t$ által), (2) egy bal oldali csúcshoz (előfizetőhöz) csakis egy jobb oldali csúcs (torony) rendelhető, mivel egy előfizető bármely időpontban csak egyetlen tornyot látogathat meg, (3) az összes így kapott él súlyának összege (összköltség) minimális legyen (vagyis keressük a globálisan legvalószínűbb toronylátogatásokat). Ez egy összerendelési probléma (assigment problem) ami hatékonyan megoldható a magyar módszerrel, viszont ehhez a gráf minimális átalakítása szükséges.

Egész pontosan a magyar algoritmus olyan esetekben működik, ahol egy bal oldali csúcshoz csakis egy jobb oldali csúcs tartozhat, és egy jobb oldalihoz csakis egy bal oldali. Az így kapott súlyozott teljes páros gráfon képes az eljárás minimális/maximális összsúlyú teljes párosítást keresni. Ez könnyen elérhető a mi esetünkben, ha minden tornyot annyi csúccsal reprezentálunk, ahányan meglátogatták azt a $t$ időpontban, valamint egy adott előfizetőt egy torony "replikált" csúcsaihoz azonos költséggel rendelünk (más szavakkal egy $i$ előfizetőt a $T_j$ toronyhoz tartozó csúcs bármelyikéhez csakis $c_{i,j}^t$ súlyú éllel köthetünk). Ebből következik, hogy az átalakított gráf bal és jobb oldalán levő csúcsok száma megegyezik. A két gráf közötti különbséget szemlélteti az alábbi ábra, ahol $p_1^t=2$ és $p_2^t=1$ (vagyis az első tornyot ketten látogatták meg $t$-ben, ezért azt két darab csúccsal reprezentáljuk az átalakított gráfban, míg a másodikat csak eggyel).

Eredeti gráf Átalakított gráf
alt text alt text

A támadás menete a következő: A $t=1$ időpontban tetszőlegesen kitöltjük az $\mathbf{Y}^1$ mátrixot azokkal a feltételekkel, hogy (1) $Y_{i,j}^1 \in \{0,1\}$, (2) $\sum_{i=1}^n Y_{i,j}^1 = p_{j}^1$, és (3) $\sum_{j=1}^m Y_{i,j}^1 = 1$. Ezek után alkalmazzuk a fenti optimalizációs eljárást, és rekonstruáljuk $\mathbf{Y}^t$-t minden $t>1$ időpontra egymás után egy napon belül, majd ezt az eljárást megismételjük minden napra külön-külön. A kérdés már csak az, hogyan kell a $c_{i,j}^t$ költség-értékeket beállítani? Az alábbiakban látni fogjuk, hogy ennek beállítása napszaktól függ: mivel nappal az előfizetők másként mozognak mint éjszaka, ezért $c_{i,j}^t$ értéke ennek megfelelően különböző a nappali és éjszakai időszakokban.

Éjszakák és nappalok

Éjszaka az emberek többsége otthon van, és nem mozog; ahogy a szerzők is megmutatták, az előfizetők több mint 60%-a csak egyetlen tornyot, míg 20%-a csak két különböző tornyot látogat meg az éjszaka folyamán. Sőt (nem meglepő módon) az emberek 90%-ának ez egyben megegyezik a leggyakrabban meglátogatott (otthonukhoz közel levő) toronnyal.

Ennek megfelelően feltételezhető, hogy éjszaka minden torony költsége arányos a legutolsó időpontban meglátogatott toronytól mért távolságával. Pontosabban legyen egy $T_j$ torony földrajzi pozíciója $q_j$ minden $1 \leq j \leq m$-re. Ha egy $i$ előfizető a $t-1$ időpontban a $T_j$ tornyot látogatta meg (vagyis $Y_{i,j}^{t-1} = 1$), akkor $c_{i,k}^t = \text{distance}(q_j, q_k)$ minden $1 \leq k \leq m$-re.

Nappal viszont az emberek gyakran mozognak, ezért a költségek máshogy alakulnak. Nappal egy előfizető által meglátogatott torony jól becsülhető az utolsó időpontban meglátogatott toronyból, valamint az előfizető mozgási sebességéből. Pontosabban ha egy $i$ előfizető a $(t-2)$ időpontban a $T_{s}$ tornyot, $t-1$-ben pedig a $T_{j}$ tornyot látogatta meg (vagyis $Y_{i,s}^{t-2} = 1$, $Y_{i,j}^{t-1} = 1$), akkor $c_{i,k}^t = \text{distance}(q_k, q_j + (q_j - q_s))$ minden $1 \leq k \leq m$-re.

Rekordok összerendelése egymást követő napokon

Egy megoldás lehet ha a $\mathbf{Y}^t$-t a fenti módszerrel rekonstruáljuk tetszőleges $t$ időpontig figyelembe véve a nappalok és éjszakák közötti különbségeket. A gyakorlatban viszont a rekordok regularitása és egyedisége miatt jobb eredményt kapunk, ha az egész folyamatot minden nap újrakezdjük, és az egyes napokat egymástól függetlenül rekonstruáljuk, végül az azonos előfizetőhöz tartozó rekordokat összkapcsoljuk az egyes napok között a következő módszerrel.

Vegyünk két rekonstruált rekordot két egymást követő nap. Ha a két rekord ugyanahhoz az előfizetőhöz tartozik, akkor a két rekord relatív (egymáshoz viszonyított) információ tartalma kicsi, mivel mindkét rekordban hasonló gyakorisággal látogatták meg ugyanazon tornyokat (regularitás miatt). Vagyis ha az egyik nap ismerjük az előfizető rekordját, akkor a következő napi rekordja már nem hordoz túl sok információt az előző napihoz képest. Precízebben, ha kiszámoljuk a két rekord entrópiájának átlagát, illetve a két rekord összefűzéséből kapott összesített rekord entrópiáját, a két értéknek hasonlónak kell lenniük ha a rekordok is hasonlóak, és a kettő közötti különbséget nevezzük információs nyereségnek (information gain). Tehát ha két rekord hasonló, akkor a kettő relatív információs nyeresége 0-hoz közeli, máskülönben 1-hez közeli.

Miután két egymást követő nap rekonstruáltuk az összes rekordot (ezeket az egy naphoz tartozó $\mathbf{Y}^t$ mátrixok azonos sorszámú sorainak az összefűzéséből kapjuk), akkor kiszámoljuk az összes így kapott rekord és a következő nap hasonló módon kapott rekordjai közötti információs nyereséget. A feladat ezután a különböző napok rekordjainak összepárosítása úgy, hogy a kapott párosítások összköltsége (a páronkénti információs nyereségek összege) minimális legyen. Ez szintén a fentihez hasonló összerendelési probléma, és szintén megoldható a magyar módszerrel. Ez az összerendelés azért fog működni, mert minden rekord egyedi, és az azonos előfizetőhőz tartozó rekordok minden nap nagyon hasonlóak.


A szerzők kipróbálták a fenti támadást két adatbázison. Az első (Operator) 100 000 előfizető CDR adatát tartalmazta, vagyis minden előfizetőhöz rögzítették az időpontot és tornyot amikor az illető a mobilhálózatot használta 1 hetes időtartományban. A második (App) adatbázis 15 000 felhasználó tornyát rögzítette 2 hetes időtartományban, amikor azok elindítottak egy adott alkalmazást. Mindkét adatbázis ugyanabból a városból származik, amely 8000 toronnyal van lefedve. Mindkét esetben kiszámolták, hogy csakis $\mathbf{P}^t$-t felhasználva átlagosan egy előfizető hány torony-látogatását tudják helyesen rekonstruálni (vagyis a látogatás tornyát és idejét). Az eredményt az alábbi ábra mutatja.

alt text

Stage1/Stage2 jelenti az éjszakai időtartománynak megfelelő rekordrészek átlagos rekonstrukciós pontosságát, míg Stage3 az egész támadás átlagos pontosságát a rekordrészek összefűzése után. Látható, hogy átlagosan egy rekord 91%-át sikeresen rekonstruálták az App adatbázisból számolt statisztikai adatból, míg ez az érték 73% az Operator adatbázis esetén.

Mivel a rekonstrukciós pontosság magas és 4-5 rekonstruált toronylátogatás már 95%-os eséllyel egyedi egy előfizetőre nézve akár egy több milliós populációban, ezért a támadás sikervalószínűsége nagy. Sőt, az előfizetők azonosításához szükséges 4-5 torony meghatározása könnyű publikus Facebook/Instagram/Twitter profilokat felhasználva. Mivel más háttérinformáció nem szükséges az előfizetőkről, a támadás plauzibilis is, vagyis az egyes tornyok látogatottsága az idő függvényében ($\mathbf{P}^t$) jó eséllyel személyes adatnak minősül a GDPR 4. cikke szerint is.


Láthattuk, hogy statisztikai adatok azért minősülhetnek személyesnek, mert azokból az eredeti adatbázis rekordjainak nagy része gyakran helyreállítható. Ennek oka, hogy ha túl sok aggregált adatot adunk ki (pl. túl sok lekérdezést válaszolunk meg), akkor még ha egyenként nem is, de a válaszok együttvéve jelentős információt szivárogtatnak ki az adatbázis egyes rekordjairól. Azt is láthattuk, hogy a lekérdezések tiltása az eredményeik nagysága alapján (vagyis amikor túl kicsi eredményű lekérdezést nem válaszolunk meg) nem feltétlen nyújt védelmet az ilyen támadások ellen, mivel nem a lekérdezések értéke, hanem a megválaszolt különböző lekérdezések száma és a támadó háttértudása (pl. az adat jellemzői) számítanak.

Hogyan védekezhetünk? Alapvetően két megközelítés létezik:

  1. A lekérdezések auditálása (query auditing), vagyis annak ellenőrzése, hogy a megválaszolandó lekérdezések lehetővé teszik-e valamely rekord rekonstruálását (pl. a fentihez hasonló egyenletrendszer megoldásával). A megközelítés feltevése, hogy ismerjük a legjobb rekonstrukciós eljárást, és megnézzük, hogy az sikeres lenne-e ha megválaszolnánk a lekérdezéseket. Ez a GDPR-nak meg is felelhet, ha a rekonstrukció sikervalószínűsége nem túl magas és a rekonstrukciós eljárás "plauzibilis" a gyakorlatban (vagyis a potenciális támadók valóban nem fognak ennél jobbat használni). Viszont az eddigiek tükrében két problémával érdemes számolni: (1) A legtöbb auditálási eljárás feltételezi, hogy a támadónak nincs háttértudása a rekordokról. Ahogy fent láttuk, ez a gyakorlatban nem mindig igaz; pl. ismerhet néhány rekordot, vagy ismeretlen rekordokról lehet részleges tudása (ld. predikálhatóság, regularitás, egyediség). Ez a támadót segítheti, hiszen például a vártnál kevesebb lekérdezésből képes lehet az ismeretlen rekordokat visszaállítani. Ugyanakkor ezt a háttértudást a gyakorlatban szinte lehetetlen modellezni az egyének magukról vagy másokról megosztott információk sokasága miatt. (2) Ha mégis sikerül detektálni a problémás lekérdezést (ami egyébként nehéz), akkor dönthetünk úgy, hogy azt nem válaszoljuk meg. Ekkor viszont nem adunk ki adott esetben értékes adatot, aminél van jobb megoldás is (ld. alább).
  2. A lekérdezések eredményeinek zajosítása/randomizálása (query perturbation), vagyis mielőtt kiadnánk a lekérdezések eredményét, hozzáadunk azokhoz egy zérus várható értékű $\lambda$ szórású zajt. Ha $\lambda$ (és így a zaj várható nagysága) kisebb, az érték pontosabb, viszont a fenti támadások nagyobb eséllyel működhetnek. Ha $\lambda$ nagyobb, akkor az adat jobban védett a nagyobb zaj miatt, és a fenti támadások kisebb eséllyel működnek (viszont a kiadott adat is pontatlanabb). Ez egy alapvető kompromisszum a statisztikai adatok hasznossága (pontossága) és a személyes adatok védelme között az informatikában. A zaj nagyságának megfelelő beállítása nem könnyű és szakértelmet igényel, ami a manapság egyre szélesebb körben alkalmazott Differential privacy-nek is az alapja. A gyakorlatban ezt a megközelítést alkalmazta már a Google, majd később az Apple és Uber is.

A CrySyS laborban lekérdezések auditálásával illetve lekérdezések eredményeinek torzításával is aktívan foglalkozunk.

Posted on Leave a comment

A személyes adat és a GDPR

Ebben a posztban először áttekintjük a személyes adat fogalmát példákkal illusztrálva, ahogyan azt a 2018. május 25-én érvénybe lépő új európai adatvédelmi rendelet (GDPR) definiálja. A GDPR kötelezettségei bárkire vonatkoznak, aki európai uniós polgár személyes adatát tárolja vagy dolgozza fel (függetlenül ezek helyétől), és a kötelezettségek mulasztása jelentős anyagi és jogi következményekkel járhat. Viszont az adat személyes jellegének megítélése korántsem könnyű, amit különböző példákkal is szemléltetünk. Megmutatjuk, hogy egy Budapest nagyságú városban a tömegközlekedést használó emberek által meglátogatott állomások listája egyedi, és kevesebb mint 5 állomás ismerete elég ahhoz, hogy egy ilyen adatbázisban bárki azonosítson egy utast. Más szavakkal kizárólag az állomások listája utasonként (név, cím, stb. nélkül) jó eséllyel személyes adatnak minősül. A probléma aktualitását a közeljövőben Budapesten is bevezetésre kerülő elektronikus jegyrendszer adja, ami lehetővé teszi az utasok által meglátogatott állomások rögzítését.

Mi a személyes adat?

Az általános európai adatvédelmi rendelet (General Data Protection Regulation (GDPR)) értelmében személyes adatnak minősül minden olyan információ, ami egy azonosított vagy azonosítható természetes személyre vonatkozik (Cikk 4(1)). Például ha egy kórházi adatbázisban szerepel a betegek neve, lakóhelyük irányítószáma, valamint a betegség diagnózisa (1. táblázat), akkor ez személyes adat ha „valaki” (egy támadó, aki az adatbázishoz hozzáfér) képes meghatározni, hogy egy rekord (sor) melyik személyhez tartozik. Első pillantásra az 1. táblázat személyes adatnak tűnik a megjelenő nevek mint azonosítók miatt. A valódi válasz egy kicsit árnyaltabb, mivel előfordulhat, hogy minden névhez több olyan természetes személy tartozik a populációban (pl. Magyarország), akik ugyanabban a kerületben laknak és az adatbázisban nem szerepelnek.

Rekord Név Irányítószám Betegség
1. Fehér Csaba 1123 Appendicitis
2. Kovács Kálmán 1117 Meningitis
3. Nagy Tibor 1113 Gastroenteritis
4. Kovács Ferenc 1114 Alzheimer
.. ... ... ...

1. táblázat: Kórházi adatok

Tegyük fel, hogy Terike néni szomszédja Kovács Ferenc, aki Budapesten lakik. Terike néni nagy valószínűséggel nem fogja tudni megmondani, hogy a 4. rekord a szomszédjához tartozik, mivel több Kovács Ferenc is élhet a XI. kerületben azonos adatokkal, és nem tudja, milyen betegségben szenved a szomszédja. Ha viszont Terike néni és szomszédja egy 100 fős községben lakik vidéken, ahol csak egyetlen Kovács Ferenc lakik (2. táblázat), akkor Terike néni teljes bizonyossággal kikövetkeztetheti, hogy a 4. rekord a szomszédjához tartozik. A név és irányítószám külön-külön „kvázi” azonosítója a vidéki K. Ferencnek, de együtt már egyedi azonosítók Terike néni számára. A budapesti K. Ferencnek (1. táblázat) viszont együttesen is csak kvázi azonosítója a két attribútum.

Rekord Név Irányítószám Betegség
1. Tóth Csaba 1123 Appendicitis
2. Nagy Kálmán 1117 Meningitis
3. Nagy Tibor 1113 Gastroenteritis
4. Kovács Ferenc 8423 Alzheimer
.. ... ... ...

2. táblázat: Kórházi adatok vidéki betegekkel

Vagyis a 2. táblázat tartalmazhat személyes adatot (Kovács Ferenc, aki egy kis községben lakik), még akkor is, ha a többi rekord nem minősül személyes adatnak Terike néni számára (pl. mert a többi beteg Budapesti, és rekordjaikhoz több természetes személy illeszkedik).

Most tegyük fel, hogy Zsuzsa néni nővér, aki nem ismeri K. Ferencet, és hozzáfér a 1. táblázathoz. Mivel Zsuzsa néni férje NAV ellenőr, ezért hozzáfér minden budapesti demográfiai adatához is (3. táblázat), és látja, hogy Budapesten a XI. kerületben három K. Ferenc él, akik rendre 26, 35, es 65 évesek. Tehát az 1. táblázat 4. rekordja a 3. táblázat 3. rekordjához tartozik, mivel az Alzheimer ritka 26 és 35 éves korban. Vagyis Zsuzsa néni jó eséllyel újra azonosította a kórházi adatbázis 4. rekordját, és így az személyes adat Zsuzsa néni számára (ahol az egyedi azonosítók a név, irányítószám és betegség együtt).

Rekord Név Adóazonosító jel Irányítószám Születési idő
1. Nagy Olivér 2346758913 8417 1965-12-12
2. Kovács Ferenc 6730861841 1114 1991-03-01
3. Kovács Ferenc 9770861942 1114 1952-05-08
4. Kovács Ferenc 4730361143 1114 1982-11-28
5. Nagy Rajmund 8462051823 1434 1954-11-30
6. Papp Lajos 7351233971 5423 1988-05-24
... ... ... ... ...

3. táblázat: Demográfiai adatok

Utolsó példaként vegyünk egy átalakított kórházi adatbázist (4. táblázat), ami abban különbözik az elsőtől, hogy minden beteghez tárolják a születési dátumot is, viszont a nevük helyett csak a nemüket (férfi/nő) rögzítik.

Rekord Nem Irányítószám Születési dátum Betegség
1. Férfi 1123 1943-01-02 Appendicitis
2. Férfi 1117 1976-08-12 Meningitis
3. Férfi 1113 1981-01-31 Gastroenteritis
4. Férfi 1114 1971-03-01 Bronchitis
... ... ... ... ...

4. táblázat: Kórházi adatok átalaktíva

Első ránézésre egy ilyen adatbázis már nem tartalmaz személyes adatot, hiszen a nevet (mint attribútumot) eltávolítottuk. Paradox módon, egy ilyen adatbázis is tartalmazhat személyes adatot, mivel a születési dátum, nem, és írányítószám együttese azonosíthat valakit (ugyan sok ezer ember született azonos napon mint K. Ferenc vagy lakik azonos irányítószám alatt, azon emberek száma akik azonos napon születtek és az irányítószámuk is azonos K. Ferenc irányítószámával már jóval kevesebb). Több tanulmányban is megmutatták, hogy egy több milliós populációban az egyének közel 63%-ának egyedi a nem- irányítószám-születési dátum együttese, vagyis jó eséllyel nincs még egy olyan ember Magyarországon, aki azonos nemű, akkor született, és ott lakik mint az Olvasó.

Tegyük fel, hogy Gizi néni (vagy férje) egy állami szervnél dolgozik, ahol hozzáfér az állampolgárok pontos születési idejéhez és lakhelyéhez (3. táblázat). A fentiek miatt egy olyan kórházi adatbázisban mint a 4. táblázat akár a betegek 63%-ához hozzárendelheti a pontos identitásukat, hiszen minden kórházi rekordhoz hozzá tudja rendelni a neki megfelelő állampolgári adatokat ha az irányítószám, születési dátum és nem (mint attribútumok) implicit vagy explicit módon megjelennek mindkét adatbázisban. Ebben az esetben a név, irányítószám és nem együttese egyedi azonosítója az emberek 63%-ának Gizi néni számára.

Plauzibilitás és sikervalószínűségek

Jogosan felmerülhet a kérdés: ha Zsuzsa néni jó eséllyel újra tudja azonosítani az 1. táblázat 4. rekordját, de Terike néni nem, akkor az személyes adat-e a GDPR szerint? Hasonlóan ha Gizi néni minden embert 63%-os valószínűséggel azonosít, de egyiket sem teljes bizonyossággal, akkor a 4. táblázat bármely rekordja személyes adatnak minősül vagy sem? Hasonló bizonytalanság fellép Zsuzsa néni esetében, hiszen ritkán, de fiatal felnőttek is szenvedhetnek Alzheimer kórban. Terike néni hihetőbb támadónak tűnik mint a többiek, hiszen neki „csak” a kórházi adatokhoz kell hozzáférnie és nincs szüksége a 3. táblázatra, hogy a szomszédja adatát lokalizálja az 1. táblázatban. Ugyanakkor Zsuzsa és Gizi néni K. Ferencen kívül számos más személyt is újra azonosíthatnak, hiszen hozzáférnek a demográfiai adatokhoz. A GDPR nem definiál explicit felső korlátot arra, hogy mennyire kell egy támadónak plauzibilisnek lennie, és arra sem, hogy ilyen támadásoknak milyen minimális sikervalószínűségűeknek kell lenniük ahhoz, hogy egy (vagy több) rekord azonosítható legyen (azaz személyesnek minősüljön). Viszont megköveteli, hogy a sikervalószínűségek ésszerűen alacsony értékek legyenek az adatbázisban szereplő minden személyre a lehető legtöbb plauzibilis támadót figyelembe véve (Recital 26).

A plauzibilitás és sikervalószínűségek becslésénél figyelembe kell venni, hogy a potenciális támadók nem feltétlenül ismerik a (kvázi) azonosítók összes elemét (pl. csak az irányítószámot, de a születési dátumot nem), valamint ezek megtanulása túl költséges lehet számukra. Például ha a való életben létezik egy Terike néni (vagyis plauzibilis, hogy ismeri a szomszédja néhány adatát és hozzáfér a 2. táblázathoz), akkor K. Ferenc rekordja a 2. táblázatban személyes adatnak minősülhet. Ha Zsuzsa és Gizi néni létezése hihető (vagyis plauzibilis, hogy hozzáférnek a 3. és 4. táblázathoz és ez számukra nem okoz túl nagy költséget), akkor K. Ferenc rekordja az 1. és 4. táblázatban is személyes adatnak minősülhet.

Egy adat személyes jellege tehát attól függ, hogy milyen potenciális támadók férhetnek hozzá az adathoz és azok képesek-e meghatározni legalább egy rekord tulajdonosát mint természetes személyt. Ennek megítéléséhez szükséges minden plauzibilis támadás feltérképezése és azok sikervalószínűségeinek becslése.


  • A fenti adatok nem azért minősülnek személyesnek, mert érzékeny információt tartalmaznak (pl. betegség), hanem azért, mert egy plauzibilis támadó képes megmondani, hogy melyik rekord melyik természetes személyhez tartozik, függetlenül az adat jellegétől. Más szavakkal, ha a fenti táblázatok nem tartalmaznák a betegséget mint attribútumot, attól még személyes adatnak minősülhetnek és vonatkozhatnak rá a GDPR kötelezettségei.
  • Általánosan igaz, hogy a belső alkalmazottak (a fenti esetben nővérek) gyakran a legvalószínűbb támadók, hiszen részükről kevés technikai felkészültséget igényel az adatlopás (eleve hozzáférésük van az adatbázisokhoz) függetlenül attól, hogy milyen biztonsági megoldásokkal (tűzfal, jelszó, antivírus szoftver, hálózati szegregálás, stb.) védik a kórházi és állami rendszereket külső „hacker” támadásoktól (miközben ezen védelmek sem nyújtanak garanciát külső támadásokkal szemben).
  • A gyakorlatban szükséges lehet az egyes támadások kockázatának elemzése, amit a GDPR is megkövetel az Adatvédelmi hatásvizsgálat (Data Protection Impact Assessment) részeként. Egy ilyen elemzés a plauzibilitás és sikervalószínűségek becslésén túl szükségessé teheti a támadásban érintett személyek/rekordok számának (scale) valamint a személyeknek okozott potenciális materiális/erkölcsi/fizikai károk (impact) becslését is. Például Gizi és Zsuzsa néni kevésbé plauzibilisek mint Terike néni, de lényegesen több személyt újra azonosíthatnak, és így az általuk okozott potenciális kár is lényegesen nagyobb lehet (például ha továbbadják az újra-azonosított adatokat).

Személyes adatok mérése

Hogyan állapíthatjuk meg, hogy egy adatbázis személyes adatokat tartalmaz és így a GDPR hatásköre alá esik? Néhány esetben ez könnyű, például amikor egy rekord valamely plauzibilis támadó által könnyen megismerhető egyedi azonosítót tartalmaz (pl. TAJ szám vagy bankszámlaszám). Akkor sem túl nehéz, ha létezik olyan publikusan elérhető másik adatbázis (3. táblázat), amely tartalmazza az azonosítók értékeit néhány rekordra; vagyis Zsuzsa és Gizi néni plauzibilis.

Általános esetben viszont meg kell becsülni minden plauzibilis támadó sikervalószínűségét, ami általában lehetetlen (ez persze nem ment fel a GDPR kötelezettsége alól, amely előír egy ilyen „best-effort" jellegű elemzést az adat felhasználásától függően). Honnan lehetne tudni, hogy a támadók akik hozzáférhetnek a kórházi adatokhoz (pl. alkalmazott, biztosító, bank, stb.) mit tudhatnak egy betegről, ami a beteg egyedi azonosítója lehet a populációban?

Vegyük Zsuzsa néni esetét K. Ferenccel, de most Zsuzsa néni csak a 3. és 5. táblázatokhoz fér hozzá. Zsuzsa néni látja a 3. táblázatban, hogy a XI. kerületben három K. Ferenc nevű ember él. Mivel Zsuzsa néni lelkes Facebook/Instagram felhasználó, ezért talál egy K. Ferenc nevű felhasználót, aki a megosztott képei alapján a XI. kerületben lakik, a 20-as éveiben jár, és krónikus bőrkiütésben szenved (a pontos betegségét ez alapján még nem ismeri). Így az 5. táblázat 4. rekordja valószínűleg a 3. táblázat 2. rekordjához tartozik, mivel az 5. táblázatban a másik két betegségnek nem tünete a bőrkiütés. Vagyis ebben az esetben az 5. táblázat 4. rekordja személyes adatnak minősülhet, amelynek egyedi azonosítója a neve, az irányítószáma, a születési éve, és a betegségének egy tünete (bőrkiütés).

Rekord Nem Irányítószám Születési dátum Betegség
1. Kovács Attila 1123 1943-*-02 Meningitis
2. Kovács Attila 1123 1943-*-02 Appendicitis
3. Kovács Ferenc 1114 19*-*-* Influenza
4. Kovács Ferenc 1114 19*-*-* Crohn-betegség
5. Kovács Ferenc 1114 19*-*-* Lábfejtörés
6. Nagy Tibor 1313 1981-*-* Meningitis

5. táblázat: Kórházi adatok

Látható, hogy nagyon nehéz feltételezéséket tenni egy támadó háttértudására és így meghatározni a plauzibilitását. Napjainkban egyre több adatot osztanak meg az emberek magukról és egymásról, akarva vagy akaratlan; így nem lehet tudni, hogy ki rendelkezik elég tudással ahhoz, hogy megtalálja az illető rekordját egy adatbázisban.

Adatok egyedisége az adatbázisban és a populációban

A fenti nehézségek ellenére a GDPR előírhatja az adatok azonosíthatóságának „best-effort" elemzését, aminek megítélése sajnos elég szubjektív, hiszen mindig kimaradhat egy Terike/Zsuzsa/Gizi néni a felsorolásból, akinek létezése csak később lesz nyilvánvaló. Vagyis az adat azonosíthatósága (és személyes jellege) idővel változhat. Ennek a rendelet tudatában van, és ezért ezekben az esetekben újabb analízist ír elő.

Az azonosíthatóság eldöntéséhez szükséges tudnunk, hogy egy rekord attribútum-értékei mennyire egyediek a populációban (és nem az adatbázisban), ahonnan a rekord számazik. Visszautalva az első példára, ha több Kovács Ferenc nevű ember él a XI. kerületben, akkor az 1. táblázat 4. rekordja nem személyes adat Terike néni (és valószínűleg senki más) számára. Annak eldöntése, hogy egy rekord egyedi-e az adott populációban viszont általában nehéz, hiszen ritkán ismerjük a populáció minden tagját. Ugyan léteznek statisztikai modellek és eszközök rekordok egyediségének becslésére egy populációban, ezen modellek többsége legjobb esetben is csak az átlagos, de nem a legrosszabb esetekre adnak valamilyen mérőszámot rekordok egyediségére.

A személyes adatok egy egyszerűbb és objektívebb indikátora a gyakorlatban a rekordok egyedisége az adatbázisban (és nem a populációban). Egy rekord egyedi, ha attribútumok egy részhalmazának értékei (amit egy plauzibilis támadó ismerhet, és így azonosíthatja a rekord tulajdonosát) egyediek rá nézve az adatbázisban, vagyis nincs más rekord aminek ilyen attribútum-értékei lennének. A fenti példában, ha K. Ferenc egyedi a nemét, irányítószámát, és születési dátumát nézve a 2. táblázatban, akkor Terike néni könnyen lokalizálhatja vidéki szomszédjának rekordját. Ha viszont k rekord rendelkezik ilyen attribútum értékekkel, akkor Terike néni nem tudja meghatározni, hogy melyik rekord tartozik a szomszédjához, feltéve, hogy nincs más információja szomszédja betegségének tüneteiről (pontosabban ha tippel, akkor az esélye, hogy eltalálja a szomszédja rekordját 1/k). Ezt illusztrálja az 6. táblázat, ahol k = 2.

Rekord Nem Irányítószám Születési dátum Betegség
1. Férfi 1123 1943-*-02 Meningitis
2. Férfi 1123 1943-*-02 Appendicitis
3. Férfi 8423 1971-01-* Bronchitis
4. Férfi 8423 1971-01-* Appendicitis
5. 1313 1981-*-* Appendicitis
6. 1313 1981-*-* Meningitis

6. táblázat: Kórházi adatok, k = 2

Természetesen, ha egy rekord egyedi az adatbázisban, az nem jelenti azt, hogy egyedi a populációban is (ld. a budapesti Kovács Ferenc esetét az 1. táblázatban). Azaz, egyedi rekordok az adatbázisban nem feltétlen minősülnek személyes adatnak, de nem túl biztató ilyen rekordok jelenléte; főleg, ha a populáción belüli egyediségét nem lehet cáfolni vagy az adatbázis tartalmazza a populáció nagy részét (ami nem ritka manapság). Ezért a gyakorlatban legtöbbször csak az adatbázison belüli egyediséget használják az adat személyességének mérésére; ha egy adatbázisban vannak olyan rekordok, amelyek egyediek valamely plauzibilis támadó számára (Terike néni aki ismeri a lakhelyet, nevet és születési dátumot), akkor jó eséllyel tartalmaz személyes adatot az adatbázis.

Komplex, sok attribútumú személyes adatok

Napjaink legtöbb adathalmaza lényegesen több attribútumot tartalmaz mint a fenti kórházi adatbázis. Például tartalmazhatja egy személy által meglátogatott helyeket, megvásárolt termékeket, megnézett filmeket, stb. Az összes attribútum száma ilyenkor megegyezik az összes lehetséges hellyel, megvásárolható termékkel, vagy létező filmmel, melyek száma akár több ezer is lehet, értékük pedig 1 ha a kérdéses személy meglátogatta/megvásárolta/megtekintette az adott helyet/árut/filmet, máskülönben 0. Egy ilyen adatbázist illusztrál a 7. táblázat, ahol az attribútumok Budapest főbb helyeinek (POI) felel meg.

Rekord Móricz Zsigmond körtér Allee Mom Park ... Széll Kálmán tér
1. 0 1 1 ... 0
2. 1 1 1 ... 0
3. 0 0 0 ... 1
4. 0 0 1 ... 1
... ... ... ... ... ...

7. táblázat: Komplex adatbázis

Az ilyen adathalmazok szinte mindig személyes adatnak minősülnek, mivel (1) a rekordok általában egyediek az attribútumok nagy száma miatt (2) a sok attribútum közül elég csak néhanyat ismerni ahhoz, hogy a illető rekordját lokalizálni tudjuk, (3) az ilyen nagy adathalmazok gyakran a populáció nagy részét lefedik. Például tegyük fel, hogy bárki megismerhet K darab, egy bizonyos személy által meglátogatott helyet az illető Facebook/Instagram profilját elemezve. Tegyük fel továbbá, hogy egy távközlési szolgáltató szeretné megosztani egy másik céggel a minden egyes előfizetője által meglátogatott helyek (cella tornyok) listáját úgy, hogy más attribútumot (név, telefonszám, stb.) nem oszt meg az előfizetőkről. Személyes adat-e az előfizetőnkénti meglátogatott helyek listája? Nagy valószínűséggel igen, hiszen kevesebb mint 5-10 torony (POI) ismerete egyedivé tesz egy rekordot. Ezt a jelenséget a következőkben illusztráljuk egy hasonló példán.

Esettanulmány: Tömegközlekedési adatok

Példaként nézzünk egy komplexebb adathalmazt, ami egy 1.5 millió lakosú város közlekedési (metró- és busz-) hálózatának használatát tartalmazza. Adott két adatbázis, amelynek minden egyes sora megfelel egy elektronikus jegynek/bérletnek (smart kártya), és tartalmazza azon állomások listáját, ahol a jegyet/bérletet érvényesítették/leolvasták (az elektronikus jegyek többnyire időalapúak, egyetlen jegy az érvényességi idején belül több állomáson is leolvasásra kerülhet). A továbbiakban tegyük fel, hogy egy utas csakis egy jegyet/bérletet használt a megfigyelt időtartamban (1 hét), vagyis minden sor megfelel egy utas által meglátogatott állomások egy részhalmazának (tehát egy állomás csak egyszer szerepelhet egy rekordban).

A metró adatbázisban összesen 66 állomás (attribútum) és 846 648 utas (rekord) található. A busz adatbázisban 861 állomás (attribútum) és 771 195 utas (rekord). Az adatbázisok főbb jellemzőit a 8. táblázat mutatja.

Metró Busz
Utasok száma 846,648 771,195
Állomások száma 66 861
Legtöbb állomás utasonként 27 54
Átlagos állomások száma utasonként 1.93 2.64
Állomások számának szórása utasonként 1.67 2.51

8. táblázat: Metró- és buszállomások látogatottsága

Két főbb támadást képzelhetünk el:

  1. A támadó ismeri egy tetszőleges utas K tetszőleges állomását, és lokalizálni szeretné az utas rekordját.
  2. A támadó ismeri egy tetszőleges utas K legtöbbször látogatott állomását (vagyis az utas TOP K állomását), és lokalizálni szeretné az utas rekordját.

A cél mindkét esetben az utas többi állomásának kiolvasása a megtalált rekordból . Mindkét támadás plauzibilis ha K nem túl nagy, hiszen szinte bármely utas nyilvános közösségi profiljából (Facebook/Instagram/Twitter stb.) könnyen meghatározhatók az általuk meglátogatott helyek, és így az azokhoz legközelebb elhelyezkedő állomások listája (pl. lakóhely, munkahely, konditerem, szórakozóhely). A sikervalószínűség mindkét esetben K értékétől függ, amit az alábbiakban a rekordok adatbázisbeli egyediségével becslünk.

TOP K állomások egyedisége

Először minden utas TOP K állomását meghatározzuk, majd megnézzük, hogy hány utasnak egyedi a TOP K állomása az adatbázisban. Az alábbi táblázat mutatja, hogy az adatbázis rekordjainak hány százaléka egyedi a TOP K állomásukat tekintve azon rekordok közül, amelyek tartalmaznak legalább K állomást. Zárójelben feltüntettük, hogy egy ilyen támadó számára hány rekord egyedi az adatbázisban.

Top-K Metró Busz
Top-2 0.03% (84 egyedi rekord) 5.56% (25 673 egyedi rekord)
Top-3 21.4% (43 315 egyedi rekord) 41.4% (119 783 egyedi rekord)
Top-4 82.1% (120 368 egyedi rekord) 79.4% (192 163 egyedi rekord)
Top-5 97.4% (129 608 egyedi rekord) 96.3% (216 135 egyedi rekord)

Például ha egy utas rekordja legalább 3 metróállomást tartalmaz, akkor ez a rekord 21.4%-os eséllyel egyedi az adatbázisban. Ugyanez az érték már 41.4% a busz-adatbázisban. Ha az összes rekordot nézzük és a támadó legfeljebb a TOP 3 állomást képes azonosítani minden rekordból, akkor számára 43 315 rekord lesz egyedi a metró-adatbázisban, ami az összes rekord kb. 5%-a. A gyakorlatban a TOP-3 állomás könnyen meghatározható egy személyről, de sokan jóval több információt megosztanak magukról közösségi portálokon (pl. képek formájában), ezért náluk akár K > 5 támadó is lehet plauzibilis több mint 95%-os sikervalószínűséggel, feltéve ha az adatbázis elég nagy és nagyjából lefedi az egész populációt.

Tetszőleges K állomás egyedisége

Milyen valószínűséggel lesz egy utas rekordja egyedi az adatbázisban egy olyan támadó számára, aki ismerheti az utas bármely K állomását (feltéve, hogy a rekord legalább K állomást tartalmaz)?

A fenti valószínűség számításához szükséges a rekordokban előforduló összes K állomás egyediségének vizsgálatára (vagyis hány más rekordban fordulnak elő), ami túl sokáig tartana. Ezért inkább véletlen mintavételezéssel becsüljük K állomás egyediségét. A részleteket mellőzve, erre itt egy egyszerű módszert mutatunk.

Első lépésként véletlenszerűen kiválasztunk egy rekordot (minden olyan rekordot ugyanolyan eséllyel, ami legalább K állomást tartalmaz), majd annak K tetszőleges állomását szintén véletlenszerűen (minden K állomást a rekordból ugyanolyan eséllyel). Végül megnézzük, hogy hány másik utas rekordja tartalmazza ezt a K állomást. A kísérlet sikeres, ha nincs más utas akinek rekordjában szerepel ez a K állomás (vagyis az első lépésben kiválasztott rekord egyedi a második lépésben kiválasztott állomásait tekintve). Ezt a kísérletet megismételjük elég sokszor (pl. 30000 ismétlés már elég pontos becslést ad), és kiszámoljuk a sikeres kísérletek százalékos arányát, amelyet az alábbi táblázat mutat. Zárójelben feltüntettük, hogy ez hány rekordot érint, vagyis hány rekord tartalmaz legalább K állomást.

K Metró Busz
2 12.7% (327 873 rekordra) 23.8% (425 602 rekordra)
3 20.2% (205 111 rekordra) 35.7% (273 759 rekordra)
4 32.4% (125 995 rekordra) 48.6% (198 875 rekordra)
5 52.7% (74 402 rekordra) 52.7% (142 150 rekordra)
6 74.1% (42 014 rekordra) 62.2% (100 779 rekordra)
7 87.7% (22 787 rekordra) 83.8% (70 370 rekordra)

Például ha egy utas rekordja legalább 3 metróállomást tartalmaz (ez 205 111 rekordra igaz, ami az összes rekord 24.2%-a), akkor ez a rekord 20.2%-os eséllyel lesz egyedi a metró adatbázisban.

Látható, hogy a busz adatbázis jóval több egyedi rekordot (és így potenciálisan több személyes adatot) tartalmaz mint a metró adatbázis. Ennek egyik fő oka, hogy több buszállomás létezik (861) mint metróállomás (66), és nyilván egy utas nagyobb eséllyel lesz egyedi ha több különböző állomást látogathat meg. Ahogy ezt a következőkben is megerősítjük, az utasok egymástól valóban elég eltérő metró- és buszállomásokat látogatnak meg.

Egyediség egyéb indikátorai

Az egyediség egy másik és gyorsabban számolható (de kevésbé pontos) indikátora lehet a sok egyedi rekordot tartalmazó adatbázisok két globális tulajdonsága: az adatritkaság (sparseness) és az állomások gyakoriságának heavy tailed eloszlása.

Egy adathalmaz ritka, ha minden utas csak néhány állomást látogatott meg. Ez a mi esetünkben valóban igaz, hiszen az átlagos állomás-szám rekordonként kevesebb mint 3 mindkét adathalmazra, aminek a szórása szintén kisebb mint 3 (8. táblázat).

A heavy-tailed tulajdonság nagyjából azt jelenti, hogy a legtöbb állomás gyakorisága alacsony az adathalmazban. Precízebben fogalmazva, ha ábrázoljuk az állomások elfordulási számának (gyakoriságának) eloszlását az adatbázisban, akkor ezen eloszlás sűrűségfüggvényének a farka „vastagabb", mint egy exponenciális eloszlás sűrűségfüggvényének farka. Ilyen ismertebb eloszlások pl. a power law és a log-normál. A következő ábrák illusztrálják a metró és busz adathalmazok heavy-tailed tulajdonságát. Ábrázoltuk az állomások gyakoriságának a komplemens kumulatív eloszlásfüggvényét (CCDF), valamint az erre legjobban illeszkedő exponenciális és heavy-tailed modellt. Az ábrák jól mutatják, hogy az exponenciális modell lényegesen rosszabbul illeszkedik mint a legjobb heavy-tailed modellek, amelyek a mi esetünkben a pozitív log-normál és Weibull eloszlások voltak. Azaz, a rekordok többsége nagy valószínűséggel egyedi! Az illeszkedést a powerlaw python csomaggal számoltuk. Érdemes megjegyezni, hogy a vizsgált heavy-tailed eloszlásoknak több paraméterük van mint az exponenciális eloszlásnak, ezért overfitting miatt a heavy-tailed eloszlások lehet, hogy csak az adatbázist modellezik pontosabban de nem a populációt (habár ennek esélye kicsi, mivel az adatbázisok jelen esetben elég nagyok).

Metró Busz
alt text alt text


Láthattuk, hogy az adatok azonosíthatóságának és így személyes jellegének megítélése attól függ, hogy ki férhet hozzá az adathoz, és milyen előzetes (háttér)tudással rendelkezik az adattulajdonosokról. Másrészt, a támadó plauzibilitását (az egyénekről alkotott háttértudását) nehéz igazolni. Ennek oka, hogy napjainkban rengeteg adat érhető el az emberekről, amit részben ők maguk részben más cégek vagy személyek osztanak meg akarva vagy akaratlanul. Az azonosíthatóság sikervalószínűségét sem mindig könnyű számolni, főleg ha az adat komplex (sok attribútumot tartalmaz).

Példaként megmutattuk, hogy egy Budapest nagyságú városban a tömegközelekedést használó emberek által meglátogatott állomások listája egyedi, és kevesebb mint 5 állomás ismerete elég ahhoz, hogy egy ilyen adatbázisban bárki azonosítson egy utast, és kiolvassa az összes általa érintett állomást. Így ez az adatbázis nagy valószínűséggel rengeteg személyes adatot tartalmaz. Ez azt is jelenti, hogy ha a rendszert üzemeltető cég meg szeretné osztani ezt az adatbázist egy harmadik féllel adatelemzés céljából (pl. hogy lássák hova kell új állomást építeni), ahhoz vagy az utasok beleegyezését kell kérniük, vagy anonimizálni kell az adatbázist úgy, hogy már nem azonosítható benne senki és így nem vonatkoznak rá a GDPR kötelezettségei. Ez a kérdés könnyen aktuálissá válhat Budapesten is a közelgő elektronikus jegyrendszer bevezetésével.

Posted on Leave a comment

Hungarian passwords in the Adobe leaked password list

This article reflects results of joint work with Ukatemi guys.
(A magyar nyelvű változat az angol után található.)

Adobe was compromised this September. Stolen data was first found in September and disclosed in early October by Brian Krebs. Later on, some 10 days ago somebody has leaked a 9GB (uncompressed) authentication database stolen from Adobe.

The database was analyzed recently based on the properties of the encryption scheme. contains the results of the analysis: the top 100 frequently used encrypted passworts and the most probable guesses for the raw password.
Press write-up is also available on the research:

We were however curious about the passwords chosen by Hungarians. In the Adobe leak, there are 209 125 email addresses with .hu CCTLD domain name. By the same way how the previous research was carried out, we created a list of most frequent passwords among this 200 thousands of users and tried to pinpoint the most likely cleartext password based on the password hint information and email addresses.

Note, however, that due to the much smaller corpus (200k instead of 154M accounts), we had much lower number of password hints, and thus the confidence of our results is lower.
In the table below, we show the frequency, how many times a password was used in the .hu corpus, and for comparison, we also show the frequency in the full database. If a password is often used in the whole database, then it is most likely not a specific hungarian word, but some internationally known word,phrase or code. In addition to the most likely password, we give secondary ideas in cases where we are not confident enough, and some information about the meaning of the specific word, if it relates to Hungarian language or culture.

Ezév szeptemberében vették észre, hogy valamilyen ismeretlen csoport feltörte a világszerte ismert Adobe szoftvergyártót (többek között az Acrobat Reader, Photoshop és Flash Player gyártóját), és elloptak a cégtől forráskódokat valamint nagyméretű felhasználói adatokat tartalmazó adatbázisokat. Október elején került napvilágra az adatlopás ténye, és október végén hírek kaptak napvilágra arról, hogy a cég 154 millió felhasználójának adatai is napvilágra kerültek. Pár nappal később egyre több helyen volt elérhető ez az ellopott 9GB méretű információhalmaz. Az adatok tartalmazzák a felhasználók e-mail címeit, kódolt jelszavát és ún. jelszó-tanácsát is. A kódolt jelszó egy szimmetrikus rejtjelezővel, egy erősnek számító 3DES algoritmussal van rejtjelezve, a jelszó-tanács egy védelem nélküli szöveg.
A rejtjelezett jelszót kulcs nélkül nem lehet dekódolni, és a kulcs egyelőre nem szivárgott ki. Ezért a jelszavak elvileg nem feltörhetőek. Sajnos azonban az iparági gyakorlattól eltérően a tárolási mód sérülékenységeket rejt magában. A rejtjelezett kulcsok nem salt-oltak és ECB módban “IV” nélkül rejtejelezettek. Ezek a szakkifejezések azt mondják ki: ha két felhasználónak azonos a jelszava, akkor a rejtjelezett párjuk is azonos.

Ez pedig gond. Sok felhasználó esetén sokan használnak azonos jelszót. Ha két felhasználó azonos jelszót használ, akkor a kódolt jelszavuk is azonos lesz. Ha találunk két felhasználót, akiknek azonos a kódolt jelszavuk, és az egyik a jelszó-tanács mezőben az írja, hogy “A jelszó három a betű és az 12 számsor”, akkor nagy valószínűséggel tudjuk, hogy a másik felhasználónak is aaa12 a jelszava. Nincs lehetőségünk a teljes bizonyosság megszerzésére, tehát ez a trükk főleg olyan jelszavakra működik, ahol a jelszavakat sokan használják és sok a jelszó-tanács (password hint) is.

Ennek megfelelően külföldön már pár napja publikáltak egy listát a leggyakoribb 100 rejtelezett jelszóról és annak megfejtett párjairól. A .hu domain névvvel regisztrált email című felhasználók száma meghaladja a 200 000 elemet a listában, közösen az Ukatemi startup cégünk embereivel azt vizsgáltuk meg, hogy mik a magyar jelszóválasztási szokások, és hogyan illeszkednek a nemzetközi környezethez.

Az alábbi listában megtekinthető a magyarok (.hu email) által leggyakrabban használt jelszavak kódolt változata, a darabszám, ahányszor .hu domainről használták, a darabszám, ahányszor nemzetközileg használták (ez is érdekes lehet, hisz vannak magyarok .com cím alatt is, és vannak jelszavak, amik nemzetközi szinten is használatosak). Feltűntettük a legvalósznűbb becslésünket a jelszóra (ami nem biztos, mert nem ellenőrizhető jogszerűen), és a tippjeinket, ha a legbiztosabb ötlet nem igaz. A külföldiek számára kis értelmezést is elhelyeztünk a jelszó jelentéséről.
Összesen csak kb. 3 jelszó esetén nem volt elég adat a nagyjából biztonságos azonosításra, ezeknél valamilyen okból senki, vagy szinte senki nem jelölt meg jelszó-emlékeztetőt.


  • Sok felhasználó jelszava “citrom” – nem túl kreatív és veszélyes
  • Sok jelszó-tanács nagyon egyszerű ” a van ellentéte” “nem narancs” “A tudom ellentéte”
  • Sok tanács kiad plusz információt “Ugyanaz, mint az címemen” – ez külön segítség, hogy mit támadhatunk meg még a jelszóval.
    “Mint mindenhol” – ez is egyértelműen gond, nemcsak, hogy ugyanazt a jelszót használja a felhasználó, de még segíti is a támadót, hogy továbbmenjen.

  • Sok felhasználó “nevem” “barátnő neve” “második nevem” szöveget írt, mondván, esetleg az email címéből ez nem következik. Ugyanakkor, a többi azonos jelszót
    használó felhasználónak elég egy szempillantást venni az email címeire, és triviális, hogy ha 20 emberből 10-nek csilla szerepel a címében, akkor a jelszó csilla, vagy annak becézése lesz. És innentől egy vadidegenről azt is tudhatjuk, hogy mi a neve, barátnője neve, második neve stb., ami segítség ún. social engineering támadásokhoz is.

FRISSÍTÉS: Találtunk pár apróbb hibát, ezeket “FIXED” felirattal javítjuk

Mintaként nézzük meg a következő rövidített listát (lecseréltük X-re a nem releváns részeket):


A “nevem” “name” “Asszony” és “kislanyom” alapján egyértelmű, hogy egy női nevet keresünk. Ezután pedig elég ránézni az e-mail címek listájára, hogy észrevegyük mennyire sok “csilla” szerepel rajta. Persze tévedhetünk, hiszen van egy “lindus” email című is, de a “csilla” elsöprő többségben van.

A jelszavak listájából látszik, hogy nagy az átfedés a nemzetközileg is használt jelszavakkal pl. “123456”, de vannak lokálisak is “szerelem”. A legtöbb jelszó továbbra is név vagy becenév, alig van ettől eltérő az első százban. Tanács: Sose használjuk emberek neveit, beceneveit, vagy azok módosításait, mert ezek a leggyakoribbak. Legyünk kreatívabbak, még mindig igaz, hogy a cseresznye151pok sokkalta biztonságosabb, mint a kr1sztinaIloveyou. A legjobb, ha valami generátorral készítünk jelszavakat, ezek sem tudnak csodát tenni, de egy DooYee7goe5EeFa nagyon erős. Összehasonlíthatatlanul erősebb az eddigi vicces példáknál.

A helyzet tehát az, hogy aki regisztrált az Adobe-nál bármilyen okból, és a jelszavát máshol is használta, azonnal jelszót kell változtatnia a többi helyen.

Rank No. in .hu No. in all Encrypted PW Most likely password Is it in top100/english? remarks, other guesses
1 3191 1911938 EQ7fIpT7i/Q= 123456 Y
2 525 932 pbn7wO3zb+8= jelszo password in hungarian
3 461 43497 4V+mGczxDEA= 12345 Y
4 394 446162 j9p+HwtWWT86aMjgZFLzYg== 123456789 Y
5 348 13401 uQM9dmQq8vE= qwertz hungarian keyboard layout has y=z
6 337 345834 L8qbAD3jl3jioxG6CatHBw== password Y
7 289 201580 j9p+HwtWWT/ioxG6CatHBw== 12345678 Y
8 273 31555 dA8D8OYD55E= asdfgh Y
9 248 113884 7LqYzKVeq8I= 111111 Y
10 214 76187 diQ+ie23vAA= 000000 Y
11 213 44282 xz6PIeGzr6g= aaaaaa Y
12 209 54651 WqflwJFYW3+PszVFZo1Ggg== macromedia Y
13 202 20961 WlMTLimQ5b4= asdasd Y
14 201 61453 ukxzEcXU6Pw= 1234 Y
15 189 320 q1A6iHNzTFg= valami something in hungarian
16 186 313 MWv89Ddd99M= piglet
17 176 1467 3zV1jrgwEro= attila hungarian male name
18 175 284 MiWs/2HM40w= lacika hungarian male name
19 173 124253 dQi0asWPYvQ= 1234567 Y
20 153 37407 yp2KLbBiQXs= 666666 Y
21 151 274 z5rLiwD12co= almafa appletree in hungarian
22 150 260 N4+iUEuZbPw= cica cat in hungarian
23 137 214 MAEvnIZOuSk= peti peter in short
24 135 6662 uIMAMQyXI/g= something international, 6600 hits
25 134 239 dvqulUaGiQg= zolika zoltan in short, male name
26 126 273 AhfBRgIzdos= tamas maybe tomi tomika, male name
27 125 294 W/jzwDNnaOw= lofasz should be censored
28 124 367 MSycWzt2SLPqvJr9l/X59g== szerelem love in hungarian
29 123 220 rA3xnflDDXI= esztike maybe eszter, hungarian female name
30 119 83411 PMDTbP0LZxu03SwrFUvYGA== photoshop Y
31 118 13044 upIXKNY/ZKY= xxxxxx
32 116 234 zjrHRH4etC0= macika maybe maci, stands for bear or teddy
33 107 234 m0/4nMkmJyM= gabi maybe gabika, female or male name in short
34 106 15910 e21tszGBy4k= matrix Y
35 104 187 P9f9Bgw46Hk= nincs means it does not exist
36 102 194 zwakdT5tFhk= titok secret in hungarian
37 100 192 /jNYdvynVr0= csillag star in hungarian
38 100 1162 +bZCz+Mm7WHioxG6CatHBw== budapest capital of Hungary
39 97 235 iqVZniq2Z6fioxG6CatHBw== cicamica like pussycat
40 97 443 bDjmWzVDGMo= dani male name in short
41 97 17989 NtCzq/i0Ffc= abc Y
42 95 9014 LEdwuvBMkVzioxG6CatHBw== garfield
43 92 16374 QSay9kzQVz8= samsung Y
44 92 155 FClbZZD1l1A= FIXED: nemtom I dunno in short
45 91 149 Xe2T3yCUsCc= balazs maybe balu, balika
46 90 155 lwXlGk4RTzc= mazsola kind name
47 89 247 D0B1TLHoZoTioxG6CatHBw== szeretet love (one version) in hungarian
48 88 197 Yg/0iyYFi+A= janika male name in short
49 86 12160 rkyaRFa+eak= qwe123
50 86 421 FvWPZ2OI8V0= tigris maybe tigris1
51 84 17176 oa/GBGqIApo= killer Y
52 84 4540 TYrTfuuBGm0= monika female name in short
53 83 142 p6kbkduAMhPioxG6CatHBw== FIXED: macilaci/TD>

Yogi Bear
54 82 153 iolWV4U4baM= madar bird in hungarian
55 81 131 TiMyOmRnnYk= mokus second guess: manoka mokus is for squirrel
56 80 214 ugYjb/7SO9DioxG6CatHBw== FIXED: nemtudom “I don’t know”
57 79 11707 rNhveK0RH5Q= ferrari
58 79 1267 ghZhzPTEyrU= viktor
59 79 6920 QkLIDf6naxw= no hint, strange
60 78 27387 XpDlpOQzTSE= 121212 Y
61 78 4829 XWs+3joEULU= 0123456 maybe 012345
62 76 18049 b5LJqTmQmvQ= 555555 Y
63 74 377 syBP2PbOprLioxG6CatHBw== FIXED: freemail
64 73 9787 C6fdPcrsYlU= 123asd or asd123
65 72 20572 ueE89xIj8RTioxG6CatHBw== internet Y
66 72 17454 MEXwK6GOWHk= andrea Y
67 72 130832 5djv7ZCI2ws= qwerty Y
68 71 7991 E3P4TkKmrIE= no hint, strange
69 70 82694 e6MPXQ5G6a8= 123123 Y
70 70 43673 Ypsmk6AXQTk= 654321 Y
71 69 111 WHnoclxstks= some woman’s name, bea, betti, zsuzsa or monika are most likely
72 69 3246 SSCHXSLigpo= roland
73 69 2618 I+sy2I0+oHg= delfin
74 69 230 2e2bx0WPm8o= andi
75 68 10742 ewOK16tiXAs= enimem
76 68 22103 OrzNCxMfwrw= fdsa Y
77 68 139 8Nd+cNdQ360= csilla hungarian female name
78 66 959 remGyraE2+rioxG6CatHBw== viktoria hungarian female name
79 66 5213 SVXt5Rlot1U= clever or something related to iq, cleverness, and a brand of computer mouse
80 66 16177 F9nqBYx2LhA= asdfghj Y
81 66 13531 DuMurYI43dU= blabla blahblah in hungarian
82 65 737 vEldih7WrfY= vivien female name
83 65 129 o2D+z1QYuHo= FIXED: nyuszi bunny in hugarian
84 65 7070 U1yPApWcaOA= barbara female name
85 63 27856 pTkQrKZ/JYM= dragon Y
86 62 128 vQGGxx87Fyk= levente male name
87 62 95 7DOklOXTFPo= zsolesz or other forms of zsolt, like zsolti
88 61 70795 kCcUSCmonEA= abc123 Y
89 61 81 gkfBa7HrOnY= citrom funny, many “” users chose that, hungarian: lemon
90 61 15805 fbO2Wx232qY= secret Y
91 60 102 kiQXbvrKbiA= robi or robert, robby, roby, or similar
92 60 88 GsQ/41R7pXw= FIXED: kriszti female name
93 60 194 /EoAhM0rWA8= kata maybe katalin, kati, female name
94 59 179 mkRrr6/R2oE= richard
95 59 14159 PwB5ue3qkgs= oliver
96 59 181 Kt3DWt8h3tg= ildiko hungarian female name
97 57 6734 u57swGYZlf/ioxG6CatHBw== juventus
98 57 146 MoedSZDdCmk= zsuzsi or zsuzsanna, hungarian name like suzy
99 56 20022 ziypr2hyamc= 123qwe Y
100 56 97 pp3j26xZbvTioxG6CatHBw== kiskacsa stands for duck in hungarian. fix: kacsa->kiskacsa “small duck”
101 56 P2x/N9v5UaM= melinda female name in short

Edited by: Boldizsar Bencsath