Concealed Data Aggregation

Main Page --> S2006-IPI --> 15. Security in DTN

Concealed Data Aggregation for Reverse Multicast Traffic in Sensor Networks

NOT THE FINAL VERSION

UNDER HEAVY DEVELOPMENT

Szenario:

Wir haben ein Sensor Netzwerk gegeben, welches eine baumartige Struktur besitzt, so daß ein "Reverse Multicast" möglich ist. Die einzelnen Knoten haben folgende Eigenschaften:

den Aufgaben entsprechende Sensoren (z.B. Wärmesensoren für die Erkennung von Waldbränden)
eine einfache CPU ( meist keine FPU, auf niedrigen Energieverbrauch optimiert)
eine Funk-Netzwerkschnittstelle
die Stromversorgung erfolgt durch Batterie oder Solarzellen
die Knoten sind nicht fälschungssicher

Die Sensorknoten werden über ein Gebiet verteilt und formen ein selbstorganisierendes Multihop-Netzwerk. Wir gehen davon aus, daß die Knoten in dem Sensornetzwerk stationär sind, obwohl auch mobile Knoten denkbar sind.

Folgende Anforderungen sind für das Szenario entscheidend:

Reduzierung des Energieverbrauchs
die Möglichkeit der Zusammenfassung von Daten in den Knoten
statistische Berechnungen auf den Daten im Netzwerk

Das hier dargestellte Netzwerk ist statisch mit dicht verteilten Knoten. Durch den Graphen Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G = (N{,}L)} kann dieses Netzwerk beschrieben werden. Dabei sind Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left| N \right|} die Knoten und Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left| L \right|} die Kanten. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R \in N} ist der Zielknoten, mit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A_t} bezeichnen wir die Menge der Aggregator-Knoten, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F_t} kennzeichnet die Menge der Forwarding-Knoten, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_t} die Menge der Sensorknoten und Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle I_t} bezeichnet die Menge der Idle-Knoten. Die Menge der Aggregator-Knoten zum Zeitpunkt Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t} kann sich von der Menge der Aggregator-Knoten zum Zeitpunkt Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t + 1} unterscheiden. Dieses Verhalten trifft auch auf die Forwarding-, Sensor- und Idle-Knoten zu. Nur der Zielknoten ist zu jedem Zeitpunkt fest. In diesem Szenario gehen wir von einem Verhältnis des Energieverbrauchs der einzelnen Operationen aus:

Senden/Empfangen 100 Energieeinheiten
Berechnungen 10 Energieeinheiten
Schlafzustand 1 Energieeinheit.

Das Problem:

Wir möchten Nachrichten in unserem Netzwerk vertraulich übermitteln, das heißt der Netzwerkverkehr muß gegen Abhören geschützt werden. Dafür müssen wir zu Verschlüsselung greifen. Weitere wichtige Sicherheitsaspekte sind die Integrität der Knoten, sprich die Fälschungssicherheit der Knoten, was durch die Authentifizierung der Knoten untereinander gewährleistet werden könnte. Dieses Problem wird an dieser Stelle aber nicht betrachtet, da wir im folgenden mit der fehlenden Fälschungssicherheit zu leben lernen werden.

Die Lösung:

Die einfachste Methode, die Daten auf dem Weg zu verschlüsseln, ist eine Hop-by-Hop-Verschlüsselung. Das heißt, jeder Knoten verschlüsselt die Daten und sendet sie anschließend an den nächsten Knoten. Der entschlüsselt sie wieder, aggregiert die Daten eventuell, verschlüsselt sie wieder und sendet sie weiter. Für ein zuverlässiges Sicherheitskonzept ist es notwendig für jedes Knotenpaar innerhalb des Netzwerks unterschiedliche Schlüssel zu verwenden. Die statistischen Berechnungen lassen sich leicht auf den Knoten realisieren, da alle erhaltenen Daten auf dem Knoten unverschlüsselt sind. Ein großes Problem ist allerdings die Unflexibilität. Wenn ein Forwarding-Knoten ausfällt, lassen sich die Daten, die über diesen Knoten geleitet wurden, nicht über andere Knoten leiten, da dafür die entsprechenden Schlüsselpaare fehlen. Wenn sehr zentrale Knoten in unserem Netzwerk ausfallen, gehen dadurch große Teile des Netzwerkes verloren. Schlüssel für Alternativrouten zu berechnen und auf den einzelnen Knoten vorrätig zu halten, ist aus Kapaziätsgründen keine Lösung. Ein weiterer Nachteil ergibt sich aus der Manipulierbarkeit der Knoten, welche sich aus der fehlenden Fälschungssicherheit ergibt. Wenn ein Angreifer nur einen Knoten unter seine Kontrolle bringen kann, ist der gesamte Netzwerkverkehr der über diesen Knoten läuft, durch die vollständige Entschlüsselung aller empfangenen Daten, kompromittiert. Dies wird besonders kritisch, wenn zentrale Knoten angegriffen werden, da in diesem Fall ein Großteil des Netzwerkverkehrs mitgelauscht werden kann. Ein großes Problem bereitet auch der Energieaufwand für Ver- und Entschlüsselung, der der Reduzierung des Energiebedarfs zuwiderläuft.

Ein andere Möglichkeit die Daten zu verschlüsseln, ist die End-zu-End-Verschlüsselung. Vorteilhaft sind der niedrigere Energieverbrauch, da auf den Forwarding-Knoten nicht entschlüsselt werden müssen, beziehungsweise nicht entschlüsselt werden können. Das Routing kann flexibel gehalten werden, da keine Notwendigkeit besteht, die Daten über bestimmte Knoten zu routen. Jeder sich in der Nähe befindliche Knoten, kann als Forwarding-Knoten fungieren und die verschlüsselten Daten weiterleiten. Wenn ein Knoten kompromittiert wird, stellt dies kein gravierendes Problem dar, da nur die auf dem Knoten gewonnen Daten unverschlüsselt, alle von anderen Knoten empfangenen Daten sind verschlüsselt und können nicht einfach entschlüsselt werden. Das gesamte System bietet eine Gute Verschlüsselung der Daten. Problematisch wird bei steigender Zahl der Knoten die hohe Komplexität des Systems, welche aber beherrschbar bleibt. Doch wie lassen sich in einem Netzwerk mit End-zu-End-Verschlüsselung Berechnungen auf den gesammelten Daten anstellen? Dafür lassen sich sogenannte Privacy-Homomorphismen verwenden. Mit Hilfe derer auf den verschlüsselten Daten Berechnungen angestellt werden können ohne diese in irgendeiner Weise zu entschlüsseln. Daten können mit Hilfe der Privacy-Homomorphismen auch aggregiert werden, um sie gebündelt weiterzuleiten, was unter anderem die Energieeffizienz erhöht. Es sind effiziente sysmetrische Verschlüsselungen bekannt, unter anderem der Privacy-Homomorphismus von Domingo-Ferrer, auf den im folgenden näher eingegangen wird. Wünschenswert wäre eine effiziente asymmetrische Verschlüsselung um die Vorteile einer Public-Private-Key-Verschlüsselung nutzen zu können, doch leider ist bisher keine effizienter Ansatz bekannt.

Doming-Ferrer-PH:

Aufbau:

die öffentlichen Parameter:
- eine nichtnegative ganze Zahl Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d \geq 2}
- eine große Ganzzahl Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g} sollte vielen kleinen Divisoren haben und gleichzeitig sollten vielen kleinen Ganzzahlen, die kleiner als Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g} sind, existieren, die modulo Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g} invertiert werden können

der geheime Schlüssel:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k = (r{,}g^')}
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r \in {Z}_g} ist so zu wählen, daß Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r^{-1} \bmod g} existiert und Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \log_{g^'} g} eine Ganzzahl mit kleinem Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g^'} ist
Klartext: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {Z} _{g^'}}
Ciphertext: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ({Z}_g)^d}

Verschlüsselung:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {a} \in {Z}_{g^'}} wird zufällig in ein Geheimnis Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_1,\ldots,a_d} zerlegt, so daß Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a = \sum_{j=1}^d a_j\ \bmod\ g^'} und Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_j \in {Z}_{g^'}} gilt

Nun wird folgende Berechnung durchgeführt: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E_k(a) = (a_1r^1\ \bmod\ g, a_2r^2\ \bmod\ g,\ldots,a_dr^d\ \bmod\ g)}

Entschlüsselung:

Um Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_j \bmod\ g} zu erhalten, muß die j-te Koordinate durch Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r^{-j} \bmod g} berechnet werden.

Um Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} zu erhalten, muß Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D_k (E_k (a)) = \sum_{j=1}^d (a_j\ \bmod\ g^')} berechnet werden.

Die Ciphertext-Operation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ +} wird komponentenweise durchgeführt.

Für die Ciphertext-Operation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \times} werden alle Terme in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z_g} kreuzmultipliziert, wobei wir beim Grad Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m_1} von Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} und dem Grad Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m_2} und einen Term mit dem Grad Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (m_1 + m_2)} erhalten. Terme mit dem gleichen Grad werden einfach addiert.

Data Aggregation:

Die Sensor-Knoten Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_1 \ldots S_n \in S_t} verschlüsseln ihre aufgezeichneten Daten Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_1, \ldots, s_n} woraus sich Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s^'_1 = E_{(r,g^')}(s_1), \ldots, s^'_n = E_{(r,g^')}(s_n)} ergibt. Danach werden die verschlüsselten Daten an einen Aggregator_knoten Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A \in A_t} gesendet. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} führt auf den verschlüsselten Daten Operationen aus und berechnet Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y^' = f(s^'_1, \ldots, s^'_n)} . Anschließend wird Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y^'} zum Zielknoten Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R} gesendet. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R} entschlüsselt Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y^'} und leitet die akkumulierten Daten mit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y = D_{(r,g^')}(y^')} ab. In diesem Verfahren ist es unerheblich, wie viele Hops die Quell-Knoten, die die Daten verschlüsseln, entfernt sind. Da die Auswahl der Aggregator-Knoten nicht fest steht und immer wider neu ausgehandelt werden kann, werden die Daten zeitlich nicht synchronisiert sein.

Was machen wir mit dem Schlüssel?

Der einfachste Weg wäre der eines netzwerkweiten Schlüssel einem Network-Shared-Key. Damit würden wir eine größtmögliche Routing-Flexibilität erreichen und hätten ein simples Keymanagement. Doch würde das auf Kosten der Sicherheit erkauft werden. Wenn nur ein Knoten korrumpiert wird, ist sofort das gesamte Netzwerk betroffen, da damit der Netzwerkschlüssel bekannt ist und der ganze Netzwerkverkehr überall mitgelauscht und entschlüsselt werden kann.

Ein anderer Ansatz ist das Topology-Aware-Group-Keying. Damit wird das Netzwerk in verschiedene Regionen aufgeteilt, die jeden einen Netzwerkschlüssel haben. Da die Größe der Regionen kann flexibel festgelegt werden. Durch diesen Ansatz haben wir weiterhin eine hohe Routingflexibilität. Das Keymanagement fällt relativ moderat aus und ist von der Anzahl der Regionen abhängig. Wenn nun ein Knoten im Netzwerk korrumpiert wird, verlieren wir die Sicherheit genau einer Region. Alle anderen Regionen sind davon nicht betroffen. Allerdings lassen sich die Daten nur innerhalb einer Region beliebig routen. Das Problem bei diesem Ansatz besteht in der Abwägung von Sicherheit und Routingflexibilität. Es nicht möglich gleichzeitig höchste Sicherheit und höchste Flexibilität gleichzeitig zu haben.

Die Schlüsselverteilung

Da wir ein selbstorganisierendes Netzwerk haben wollen, bleibt die Frage, wie die Schlüssel verteilt werden können, ohne in die Konfiguration eines jeden Knoten eingreifen zu müssen, oder Schwachstellen, die das gesamte Netzwerk kompromittieren würden, aufzutun. Die Schlüsselverteilung läuft dabei in 4 Phasen ab:

1. Pre-Configuration:

Bevor die Sensorknoten ausgeliefert werden, wird jeder Knoten vorkonfiguriert und mit dem gleichen Schlüsselpool Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K^*} und deren Schlüssel IDs $ID_{k},k\in K^{*}$ . Dabei gilt $|K^{*}|\ll |K|$ und $|K^{*}|\ll |N|$ . Die größe des Schlüsselpools ist von der Größe des Speicherplatzes auf den Knoten begrenzt. $|K*|$ ist unabhängig von $|N|$ und skaliert auch in großen Netzwerken.

2. Roll-Out:

Die Knoten werden zufällig in einer Region verteilt und der Sink-Node sollte im Zentrum plaziert werden. Jeder KNoten enthält den gleichen Schlüsselpool $K^{*}$ und die zugehörigen IDs.

3. Bootstrapping

Eine Teilmenge von Knoten, nahe des Sink-Nodes wählt eine Schlüsselliste $\{k_{1},\ldots ,k_{r}\}\in K^{*}$ aus und sendet deren IDs $ID_{k_{1}}\Vert \ldots \Vert ID_{k_{r}}$ an alle umliegenden Knoten. Die Knoten, die diese Liste empfangen löschen entweder ihren gesamten Schlüsselpool, oder wählen zufällig einen Schlüssel aus der Liste $k\in \{k_{1},\ldots ,k_{r}\}$ aus. $ID_{k_{1}}\Vert \ldots \Vert ID_{k_{r}}\to del(K^{*})$ , mit $P\left(i,l\right)$ oder $del(K^{*})\setminus \{k\}$ , sonst. Was die Knoten tun, hängt von einer Wahrscheinlichkeitsfunktion, basierend auf der Distanz und Maximaldistanz der Knoten, ab. Werden noch andere Schlüssellisten empfangen, werden diese ignoriert. Die Knoten senden $ID_{k_{1}}\|\dots \|ID_{k_{r}}$ an alle noch weiter entfernten Knoten.

4. Cleansing

Die Knoten, die keine Nachrichten $ID_{k_{1}}\Vert \ldots \Vert ID_{k_{r}}$ nach einer bestimmten Zeit nach dem Roll-Out empfangen haben, löschen ihren gesamten Schlüsselpool $K^{*}$ , so daß unerreichbare Knoten keine sensiblen Daten mehr speichern.

Main Page --> S2006-IPI --> 15. Security in DTN

Concealed Data Aggregation

Contents