Preventing active re-identification attacks on social graphs via sybil subgraph obfuscation

in Knowledge and Information Systems (2022), 64

Active re-identification attacks constitute a serious threat to privacy-preserving social graph publication, because of the ability of active adversaries to leverage fake accounts, a.k.a. sybil nodes, to ... [more ▼]

Active re-identification attacks constitute a serious threat to privacy-preserving social graph publication, because of the ability of active adversaries to leverage fake accounts, a.k.a. sybil nodes, to enforce structural patterns that can be used to re-identify their victims on anonymised graphs. Several formal privacy properties have been enunciated with the purpose of characterising the resistance of a graph against active attacks. However, anonymisation methods devised on the basis of these properties have so far been able to address only restricted special cases, where the adversaries are assumed to leverage a very small number of sybil nodes. In this paper, we present a new probabilistic interpretation of active re-identification attacks on social graphs. Unlike the aforementioned privacy properties, which model the protection from active adversaries as the task of making victim nodes indistinguishable in terms of their fingerprints with respect to all potential attackers, our new formulation introduces a more complete view, where the attack is countered by jointly preventing the attacker from retrieving the set of sybil nodes, and from using these sybil nodes for re-identifying the victims. Under the new formulation, we show that k-symmetry, a privacy property introduced in the context of passive attacks, provides a sufficient condition for the protection against active re-identification attacks leveraging an arbitrary number of sybil nodes. Moreover, we show that the algorithm K-Match, originally devised for efficiently enforcing the related notion of k-automorphism, also guarantees k-symmetry. Empirical results on real-life and synthetic graphs demonstrate that our formulation allows, for the first time, to publish anonymised social graphs (with formal privacy guarantees) that effectively resist the strongest active re-identification attack reported in the literature, even when it leverages a large number of sybil nodes. [less ▲]

Post-collusion security and distance bounding

in Post-collusion security and distance bounding (2019, November 11)

Verification of cryptographic protocols is traditionally built upon the assumption that participants have not revealed their long-term keys. However, in some cases, participants might collude to defeat ... [more ▼]

Verification of cryptographic protocols is traditionally built upon the assumption that participants have not revealed their long-term keys. However, in some cases, participants might collude to defeat some security goals, without revealing their long-term secrets. We develop a model based on multiset rewriting to reason about collusion in security protocols. We introduce the notion of postcollusion security, which verifies security properties claimed in sessions initiated after collusion occurred. We use post-collusion security to analyse terrorist fraud on protocols for securing physical proximity, known as distance-bounding protocols. In a terrorist fraud attack, agents collude to falsely prove proximity, whilst no further false proximity proof can be issued without further collusion. Our definitions and the Tamarin prover are used to develop a modular framework for verification of distance-bounding protocols that accounts for all types of attack from literature. We perform a survey of over 25 protocols, which include industrial protocols such as Mastercard’s contactless payment PayPass and NXP’s MIFARE Plus with proximity check. For the industrial protocols we confirm attacks, propose fixes, and deliver computer-verifiable security proofs of the repaired versions [less ▲]

Automated Identification of Desynchronisation Attacks on Shared Secrets

in Automated Identification of Desynchronisation Attacks on Shared Secrets (2018, September)

Key-updating protocols are a class of communication protocol that aim to increase security by having the participants change encryption keys between protocol executions. However, such protocols can be ... [more ▼]

Key-updating protocols are a class of communication protocol that aim to increase security by having the participants change encryption keys between protocol executions. However, such protocols can be vulnerable to desynchronisation attacks, a denial of service attack in which the agents are tricked into updating their keys improperly, so that they are no longer able to communicate. In this work we introduce a method that can be used to automatically verify (or falsify) resistance to desynchronisation attacks for a range of protocols. This approach is then used to identify previously unreported vulnerabilities in two published RFID grouping protocols. [less ▲]

New Directions in Attack Tree Research: Catching up with Industrial Needs

in Mauw, Sjouke (Ed.) Proceedings of the 4th International Workshop on Graphical Models for Security (2018, January)

Attack trees provide a systematic way of characterizing diverse system threats. Their strengths arise from the combination of an intuitive representation of possible attacks and availability of formal ... [more ▼]

Attack trees provide a systematic way of characterizing diverse system threats. Their strengths arise from the combination of an intuitive representation of possible attacks and availability of formal mathematical frameworks for analyzing them in a qualitative or a quantitative manner. Indeed, the mathematical frameworks have become a large focus of attack tree research. However, practical applications of attack trees in industry largely remain a tedious and error-prone exercise. Recent research directions in attack trees, such as attack tree generation, attempt to close this gap and to improve the attack tree state-of-thepractice. In this position paper we outline the recurrent challenges in manual tree design within industry, and we overview the recent research results in attack trees that help the practitioners. For the challenges that have not yet been addressed by the community, we propose new promising research directions. [less ▲]

Distance-Bounding Protocols: Verification without Time and Location

in Proceedings of IEEE Symposium on Security and Privacy (SP), San Francisco 21-23 May 2018 (2018)

Distance-bounding protocols are cryptographic protocols that securely establish an upper bound on the physi- cal distance between the participants. Existing symbolic verification frameworks for distance ... [more ▼]

Distance-bounding protocols are cryptographic protocols that securely establish an upper bound on the physi- cal distance between the participants. Existing symbolic verification frameworks for distance-bounding protocols consider timestamps and the location of agents. In this work we introduce a causality-based characterization of secure distance-bounding that discards the notions of time and location. This allows us to verify the correct- ness of distance-bounding protocols with standard pro- tocol verification tools. That is to say, we provide the first fully automated verification framework for distance- bounding protocols. By using our framework, we con- firmed known vulnerabilities in a number of protocols and discovered unreported attacks against two recently published protocols. [less ▲]

Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph

in Fundamenta Informaticae (2017), 152(3), 273-287

A class of precomputation-based distance-bounding protocols

Presentation (2016, March 16)

Distance-bounding protocols serve to thwart various types of proximity-based attacks, such as relay attacks. A particular class of distance-bounding protocols measures round trip times of a series of one ... [more ▼]

Distance-bounding protocols serve to thwart various types of proximity-based attacks, such as relay attacks. A particular class of distance-bounding protocols measures round trip times of a series of one-bit challenge-response cycles, during which the proving party must have minimal computational overhead. This can be achieved by precomputing the responses to the various possible challenges. We formalize this class of precomputation-based distance-bounding protocols. By designing an abstract model for these protocols, we can study their generic properties, such as security lower bounds in relation to space complexity. Further, we present a novel family of protocols in this class that resists well to mafia fraud attacks. [less ▲]

A Class of Precomputation-based Distance-bounding Protocols

in Proceedings of the 1st IEEE European Symposium on Security and Privacy (2016)

Distance-bounding protocols serve to thwart various types of proximity-based attacks, such as relay attacks. A particular class of distance-bounding protocols measures round trip times of a series of one ... [more ▼]

Distance-bounding protocols serve to thwart various types of proximity-based attacks, such as relay attacks. A particular class of distance-bounding protocols measures round trip times of a series of one-bit challenge-response cycles, during which the proving party must have minimal computational overhead. This can be achieved by precomputing the responses to the various possible challenges. In this paper we study this class of precomputation-based distance-bounding protocols. By designing an abstract model for these protocols, we can study their generic properties, such as security lower bounds in relation to space complexity. Further, we develop a novel family of protocols in this class that resists well to mafia fraud attacks. [less ▲]

Characterizing 1-metric antidimensional trees and unicyclic graphs

in Computer Journal (2016), 59(8), 1264--1273

k-Metric antidimension: A privacy measure for social graphs

in Information Sciences (2016), 328