Abstract:
Ein zentrales Problem der digitalen Kommunikation ist die Absicherung der Authentizität und Integrität digitaler Dokumente, wie etwa Webseiten, E-Mails oder Programmen. So soll beispielsweise für den Empfänger einer E-Mail nachvollziehbar sein, dass die empfangene E-Mail tatsächlich vom angegebenen Absender stammt (Authentizität) und nicht durch Dritte verändert wurde (Integrität). Digitale Signaturen sind ein Hauptwerkzeug der Kryptographie und IT-Sicherheit, um diese Eigenschaften zu gewährleisten.
Hierzu wird vom Absender ein geheimer Schlüssel verwendet, um für das zu sichernde Dokument eine Signatur zu erstellen, die mithilfe eines öffentlich bekannten Verifikationsschlüssels jederzeit überprüft werden kann. ... mehrDie Sicherheitseigenschaften solcher digitaler Signaturverfahren garantieren sowohl, dass jede Änderung am Dokument dazu führt, dass diese Überprüfung fehlschlägt, als auch dass eine Fälschung einer Signatur praktisch unmöglich ist, d.h. ohne den geheimen Schlüssel kann keine gültige Signatur berechnet werden. Somit kann bei einer erfolgreichen Verifikation davon ausgegangen werden, dass das Dokument tatsächlich vom angegebenen Absender erstellt und seit der Berechnung der Signatur nicht verändert wurde, da nur der Absender über den geheimen Schlüssel verfügt.
Aggregierbare Signaturen bieten zusätzlich die Möglichkeit Signaturen mehrerer Dokumente zu einer einzigen Signatur zusammenzuführen bzw. zu aggregieren. Diese Aggregation ist dabei jederzeit möglich. Eine aggregierte Signatur bezeugt weiterhin sicher die Integrität und Authentizität aller ursprünglichen Dokumente, benötigt dabei aber nur so viel Speicherplatz wie eine einzelne Signatur. Außerdem ist die Verifikation einer solchen aggregierten Signatur üblichrweise schneller möglich als die sukzessive Überprüfung aller Einzelsignaturen. Somit kann die Verwendung eines aggregierbaren Signaturverfahrens anstelle eines gewöhnlichen Verfahrens zu erheblichen Verbesserungen der Performanz und des Speicherverbrauchs bei Anwendungen von Signaturen führen.
In dieser Dissertation werden zwei zusätzliche Eigenschaften von aggregierbaren Signaturverfahren namens Fehlertoleranz und Deaggregationssicherheit untersucht. Fehlertoleranz bietet eine Absicherung des Verfahrens gegen fehlerhafte Signier- und Aggregationsvorgänge und Deaggregationssicherheit schützt vor ungewollten Löschungen. Beide Eigenschaften werden im Folgenden erläutert.
Fehlertoleranz:
Durch System- und Programmfehler, sowie inkorrektes oder auch bösartiges Nutzerverhalten ist es möglich, dass fehlerhafte Einzelsignaturen zu einer bestehenden aggregierten Signatur hinzugefügt werden. Alle bisherige aggregierbaren Signaturverfahren haben jedoch den Nachteil, dass bereits das Aggregieren einer einzigen fehlerhaften Einzelsignatur dazu führt, dass auch die aggregierte Signatur fehlerhaft und somit unbrauchbar wird. Die aggregierte Signatur kann danach nicht mehr korrekt verifiziert werden. Insbesondere kann aus ihr nun keinerlei Aussage mehr über die Integrität und Authentizität der Dokumente abgeleitet werden, die vor dem Hinzufügen der fehlerhaften Einzelsignatur korrekt signiert wurden. Dies hat zur Folge, dass alle gegebenen Sicherheitsgarantien verloren gehen und es wird ein aufwändiges Neusignieren aller Dokumente notwendig, welches unter Umständen und je nach Anwendung nur schwer bis überhaupt nicht möglich ist.
In dieser Dissertation wird das erste fehlertolerante aggregierbare Signaturverfahren vorgestellt, bei dem das Hinzufügen einzelner falscher Signaturen bis zu einer gewissen Grenze keine schädlichen Auswirkungen hat. Eine aggregierte Signatur wird erst dann ungültig und unbrauchbar, sobald die Anzahl hinzugefügter fehlerhafter Signaturen diese Grenze überschreitet und behält davor weiterhin seine Gültigkeit für die korrekt signierten Dokumente. Dazu wird ein Verfahren vorgestellt, mit dem jedes beliebige aggregierbare Signaturverfahren in ein fehlertolerantes Verfahren transformiert werden kann. Das zugrundeliegende Verfahren wird dabei nur als Black-Box verwendet und der Schutz gegen Fälschungsangriffe übertragt sich beweisbar und ohne Einschränkung auf das neue fehlertolerante Verfahren.
Des Weiteren wird als Anwendung von fehlertoleranten Verfahren gezeigt, wie aus ihnen ein sicheres Log-Verfahren konstruiert werden kann.
Deaggregationssicherheit: Erlangt ein Angreifer Zugriff auf eine aggregierte Signatur für einen bestimmten Datensatz, so sollte es ihm nicht möglich sein aus diesem Aggregat eine gültige Signatur für einen Teil der geschützten Dokumente abzuleiten, indem er einzelne Signaturen entfernt oder deaggregiert. Solche Angriffe können für viele Anwendungsfälle problematisch sein, da so Signaturen für Mengen von Dokumenten berechnet werden könnten, die nicht von den eigentlichen Erstellern beabsichtigt waren und nie von ihnen selbst signiert wurden. Wird ein aggregierbares Signaturverfahren etwa verwendet um eine Datenbank abzusichern, so sollte es Angreifern nicht möglich sein einzelne Einträge daraus zu entfernen.
In dieser Dissertation werden mehrere Deaggregationssicherheitsbegriffe entwickelt, vorgestellt und untersucht. Dazu wird eine Hierarchie von verschieden starken Sicherheitsbegriffen entwickelt und die Zusammenhänge zwischen den einzelnen Begriffen werden formal untersucht. Dabei wird auch gezeigt, dass der von aggregierbaren Signaturverfahren garantierte Schutz gegen Fälschungen keinerlei Sicherheit gegen Deaggregationsangriffe gewährleistet. Des Weiteren wird die Deaggregationssicherheit einer Reihe von bekannten und wichtigen aggregierbaren Signaturverfahren näher betrachtet. Die von diesen Verfahren gebotene Sicherheit wird exakt klassifiziert, indem entweder Angriffsmöglichkeiten demonstriert werden oder formal bewiesen wird, welcher Sicherheitsbegriff der Hierarchie vom Verfahren erfüllt wird.
Außerdem wird die Verbindung von Fehlertoleranz und Deaggregationssicherheit untersucht. Dabei stellt sich heraus, dass beide Begriffe nicht zueinander kompatibel sind, indem bewiesen wird, dass fehlertolerante aggregierbare Signaturverfahren keinerlei Sicherheit gegen Deaggregationsangriffe bieten können. Somit muss bei Anwendungen von aggregierbaren Verfahren genau abgewogen werden, welche der beiden Eigenschaften notwendig ist und ob zusätzliche Sicherheitsmaßnahmen angewendet werden müssen, um dieses Problem für die konkrete Anwendung zu beheben.
Abstract (englisch):
A prominent problem of digital communication is the protection of the authenticity and integrity of digital documents, like websites, emails or programs. For example, the receiver of an email must be able to verify that the email was actually sent by the alleged sender (authenticity) and that it was not changed by a third party during transmission (integrity). Digital signature schemes are a central tool of cryptography and IT security used to achieve these properties.
For this, the sender uses a secret key to compute a signature for the document that is to be protected. ... mehrThis signature can then be verified at any time using a publicly known verification key. The security guarantees of such digital signature schemes ensure both that every change of the document results in a failed verification and that forging signatures is practically impossible, i.e. it is not possible to compute valid signatures without the secret key. This way, if the verification of a signature succeeds, one can be sure that the document was created by the alleged sender and was not modified since the signature was computed, because only the sender knows the secret key.
Aggregate signature schemes offer the additional functionality that existing signatures of multiple documents can be compressed or aggregated into one single signature. This aggregate signature still securely attests to the authenticity and integrity of all documents, but only uses as much memory space as one individual signature of a single document. Moreover, an aggregate signature can usually be verified faster than successively verifying each individual signature. Hence, using an aggregate signature scheme instead of a regular signature scheme can result in substantial improvements in the necessary memory space and performance of the application that uses the signature scheme.
In this thesis, two additional properties of aggregate signature schemes called fault-tolerance and deaggregation security are discussed. Fault-tolerance secures the scheme against incorrect signing and aggregation operations and deaggregation security offers protection against unwanted deletions. Both properties are explained in the following paragraphs.
Fault-Tolerance:
Through system and program errors, as well as incorrect or malicious user behavior, it is possible that invalid or faulty signatures get added to an already aggregated signature. However, all known aggregate signature schemes have one disadvantage in common: the aggregation of a faulty signature renders the whole aggregate invalid and therefore unusable. After the faulty signature was added, the aggregate signature can no longer be correctly verified. In particular, no information whatsoever about the authenticity and integrity of the previously correctly signed documents can be inferred. As a consequence, all given security guarantees are lost and all documents need to be signed again, which can be very costly or even impossible, depending on the circumstances and application.
In this thesis, we present the first fault-tolerant aggregate signature scheme for which the aggregation of faulty signatures up to a specific limit has no negative effect. An aggregate signature only then becomes invalid if the number of added faulty signatures exceeds this limit and otherwise stays valid for all previously correctly signed documents. We present a construction that can be used to transform any aggregate signature scheme into a fault-tolerant one. Here, the underlying scheme is only used as a black-box and we prove that the security against forgery attacks is transferred without restrictions to the resulting fault-tolerant scheme. Furthermore, as an application of fault-tolerant aggregate signatures, we show how a secure and robust logging scheme can be constructed from such a scheme.
Deaggregation Security: If an attacker gets a hold of an aggregate signature for a specific set of documents, then he should not be able to compute a valid signature for a subset of the documents by removing or deaggregating individual signatures. Such attacks can be problematic in many applications, since this way signatures could be created that validate sets of documents that were never intended by the document owners and were never properly and intentionally signed by them. For example, suppose that an aggregate signature scheme is used to protect a database. Here, an attacker should not be able to selectively remove individual entries.
In this thesis, we present and discuss several definitions of deaggregation security. We present a hierarchy of deaggregation security definitions of varying strength and discuss their relationships formally. We also show that the security against forgery attacks offered by aggregate signature schemes implies no protection whatsoever against deaggregation attacks. Furthermore, we investigate the deaggregation security of a number of known and important aggregate signature schemes. We exactly classify the security provided by them by either demonstrating attack possibilities or by formally proving which definition of the deaggregation security hierarchy is fulfilled by them.
Moreover, we discuss the connection between fault-tolerance and deaggregation security. As it turns out, fault-tolerance and deaggregation security are incompatible, which we show by proving that no fault-tolerant scheme can offer any form of deaggregation security. Therefore, if an aggregate signature scheme is used in an application, great care needs to be taken in deciding which of the two properties is necessary and if additional security measures need to be implemented to solve this problem for the specific application.
