Helmholtz Center for Information Security
CISPA – Helmholtz-Zentrum für InformationssicherheitNot a member yet
3406 research outputs found
Sort by
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
Get PDFThe leafage of a chordal graph is the minimum integer such that can be realized as an intersection graph of subtrees of a tree with leaves.
We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs.
Fomin, Golovach, and Raymond~[ESA~, Algorithmica~] proved, among other things, that \textsc{Dominating Set} on chordal graphs admits an algorithm running in time .
We present a conceptually much simpler algorithm that runs in time .
We extend our approach to obtain similar results for \textsc{Connected Dominating Set} and \textsc{Steiner Tree}.
We then consider the two classical cut problems \textsc{MultiCut with Undeletable Terminals} and \textsc{Multiway Cut with Undeletable Terminals}.
We prove that the former is \textsf{W}[1]-hard when parameterized by the leafage and complement this result by presenting a simple -time algorithm.
To our surprise, we find that \textsc{Multiway Cut with Undeletable Terminals} on chordal graphs can be solved, in contrast, in -time
Lockable Obfuscation from Circularly Insecure Fully Homomorphic Encryption
No full textIn a lockable obfuscation scheme, a party called the obfuscator takes as input a circuit \Circ, a lock value , and a message , and outputs an obfuscated circuit.
Given the obfuscated circuit, an evaluator can run it on an input and learn the message if \Circ(x) = y.
For security, we require that the obfuscation reveals no information on the circuit as long as the lock has high entropy even given the circuit \Circ.
The only known constructions of lockable obfuscation schemes require indistinguishability obfuscation (\iO) or the learning with errors (LWE) assumption.
Furthermore, in terms of technique, all known constructions, excluding \iO-based, are build from provably secure variations of graph-induced multilinear maps.
We show a generic construction of a lockable obfuscation scheme built from a (leveled) fully homomorphic encryption scheme that is circularly insecure.
Specifically, we need a fully homomorphic encryption scheme that is secure under chosen-plaintext attack (IND-CPA) but for which
there is an efficient cycle tester that can detect encrypted key cycles.
Our finding sheds new light on how to construct lockable obfuscation schemes and shows why cycle tester constructions were helpful in the design of lockable obfuscation schemes.
One of the many use cases for lockable obfuscation schemes are constructions for IND-CPA secure but circularly insecure encryption schemes. Our work shows that there is a connection in both ways between circular insecure encryption and lockable obfuscation
Amplifying Membership Exposure via Data Poisoning
No full textAs in-the-wild data are increasingly involved in the training stage, machine learning applications become more susceptible to data poisoning attacks. Such attacks typically lead to test-time accuracy degradation or controlled misprediction. In this paper, we investigate the third type of exploitation of data poisoning - increasing the risks of privacy leakage of benign training samples. To this end, we demonstrate a set of data poisoning attacks to amplify the membership exposure of the targeted class. We first propose a generic dirty-label attack for supervised classification algorithms. We then propose an optimization-based clean-label attack in the transfer learning scenario, whereby the poisoning samples are correctly labeled and look “natural” to evade human moderation. We extensively evaluate our attacks on computer vision benchmarks. Our results show that the proposed attacks can substantially increase the membership inference precision with minimum overall test-time model performance degradation. To mitigate the potential negative impacts of our attacks, we also investigate feasible countermeasures
The State of the SameSite: Studying the Usage, Effectiveness, and Adequacy of SameSite Cookies
Get PDFChromium-based browsers now restrict cookies' scope to a same-site context by changing the default policy for cookies, thus requiring developers to adapt their websites. The extent of the adoption and effectiveness of the SameSite policy has not been studied yet, and, in this paper, we undertake one of the first evaluations of the state of the SameSite cookie policy. We conducted a set of large-scale, longitudinal, both automated and manual measurements of the Alexa top 1K, 10K, 100K, and 500K sites across the main rollout dates of the SameSite policies, covering both SameSite usage and cross-site functionality breakage caused by the new default policy. Also, we performed an extensive evaluation of threats against the new Lax-by-default policy's effectiveness, looking at the adequacy of the coverage provided by the Lax policy and bypass caused by website developers' mistakes.
Our study shows that the growth of sites using a SameSite policy has slowed down considerably after the enforcement dates. Then, the new Lax-by-default policy has affected about 19% of the functionalities implemented via cross-site requests without an explicit SameSite policy, most of which are for online ads. Third, our study observes a significant mismatch between the request contexts covered by Lax and the ones actually used by websites in the wild, making it possible to perform XS attacks also against popular websites such as Tumblr, Twitch, SoundCloud, Mailchimp, and Pixiv. Even when using Lax or Strict policies, much of their effectiveness depends on developers' awareness of SameSite policies' implications, who could introduce vulnerabilities or inconsistent policies, leading to SameSite policy bypasses. For example, we identified bypass in IMDB, Paypal, and Meetup. Also, we discovered a widespread SSO IdP abuse that attackers could use to attack target websites even when using stricter SameSite policies. Finally, in this paper, we also look at SameSite implementations in popular browsers and the default configuration in web frameworks
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
Get PDFSubexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. The goal of this paper is to introduce a framework for obtaining n^{O(\sqrt{k})} time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems.
Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an n^{O(\sqrt{k})} time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity.
For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply 2^{\sqrt{k}polylog(k)}n^{O(1)} time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain 2^{\sqrt{k}polylog(k)}n^{O(1)} time (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set.
Our algorithms are designed with possible generalization to -minor free graphs in mind. To obtain the same n^{O(\sqrt{k})} time algorithms on H-minor free graphs, the only missing piece is the vertex version of a contraction decomposition theorem that we currently have only for planar graphs
V-Range: Enabling Secure Ranging in 5G Wireless Networks
Get PDFA number of safety- and security-critical applications such as asset tracking, smart ecosystems, autonomous vehicles and driver assistance functions, etc., are expected to benefit from the position information available through 5G. Driven by the aim to support such a wide-array of location-aware services and applications, the current release of 5G seeks to explore ranging and positioning as an integral part of 5G technology. In recent years, many attacks on positioning and ranging systems have been demonstrated, and hence it is important to build 5G systems that are resilient to distance and location manipulation attacks. No existing proposal either by 3GPP or the research community addresses the challenges of secure position estimation in 5G. In this paper, we develop V-Range, the first secure ranging system that is fully compatible with 5G standards and can be implemented directly on top of existing 5G-NR transceivers. We design V-Range, a system capable of executing secure ranging operations resilient to both distance enlargement and reduction attacks. We experimentally verify that V-Range achieves high precision, low-latency, and can operate in both the sub-6GHz and mm-wave bands intended for 5G. Our results show that an attacker cannot reduce or increase the distance by more than the imprecision of the system, without being detected with high probability
Constrained Proximity Attacks on Mobile Targets
No full textProximity attacks allow an adversary to uncover the location of a victim by repeatedly issuing queries with
fake location data. These attacks have been mostly studied in scenarios where victims remain static and there
are no constraints that limit the actions of the attacker. In such a setting, it is not difficult for the attacker to
locate a particular victim and quantifying the effort for doing so is straightforward. However, it is far more
realistic to consider scenarios where potential victims present a particular mobility pattern. In this paper, we
consider abstract (constrained and unconstrained) attacks on services that provide location information on
other users in the proximity. We derive strategies for constrained and unconstrained attackers, and show that
when unconstrained they can practically achieve success with theoretically optimal effort. We then propose
a simple yet effective constraint that may be employed by a proximity service (for example, running in the
cloud or using a suitable two-party protocol) as countermeasure to increase the effort for the attacker several
orders of magnitude both in simulated and real-world cases
Incompressibility of H-free edge modification problems: Towards a dichotomy
Get PDFGiven a graph G and an integer k, the H-free Edge Editing problem is to find whether there exist at most k pairs of vertices in G such that changing the adjacency of the pairs in G results in a graph without any induced copy of H. Nontrivial polynomial kernels are known to exist for some graphs H with at most 4 vertices, but starting from 5 vertices, polynomial kernels are known only if H is either complete or empty. This suggests the conjecture that there is no other H with at least 5 vertices where H-free Edge Editing admits a polynomial kernel. Towards this goal, we obtain a set of nine 5-vertex graphs such that if for every , H-free Edge Editing is incompressible and the complexity assumption holds, then H-free Edge Editing is incompressible for every graph H with at least five vertices that is neither complete nor empty. We obtain similar results also for H-free Edge Deletion/Completion
Dynamic Backdoor Attacks Against Machine Learning Models
Get PDFMachine learning (ML) has made tremendous progress during the past decade and is being adopted in various critical real-world applications. However, recent research has shown that ML models are vulnerable to multiple security and privacy attacks. In particular, backdoor attacks against ML models have recently raised a lot of awareness. A successful backdoor attack can cause severe consequences, such as allowing an adversary to bypass critical authentication systems.
Current backdooring techniques rely on adding static triggers (with fixed patterns and locations) on ML model inputs which are prone to detection by the current backdoor detection mechanisms. In this paper, we propose the first class of dynamic backdooring techniques against deep neural networks (DNN), namely Random Backdoor, Backdoor Generating Network (BaN), and conditional Backdoor Generating Network (c-BaN). Triggers generated by our techniques can have random patterns and locations, which reduce the efficacy of the current backdoor detection mechanisms. In particular, BaN and c-BaN based on a novel generative network are the first two schemes that algorithmically generate triggers. Moreover, c-BaN is the first conditional backdooring technique that given a target label, it can generate a target-specific trigger. Both BaN and c-BaN are essentially a general framework which renders the adversary the flexibility for further customizing backdoor attacks.
We extensively evaluate our techniques on three benchmark datasets: MNIST, CelebA, and CIFAR-10. Our techniques achieve almost perfect attack performance on backdoored data with a negligible utility loss. We further show that our techniques can bypass current state-of-the-art defense mechanisms against backdoor attacks, including ABS, Februus, MNTD, Neural Cleanse, and STRIP
AmpFuzz: Fuzzing for Amplification DDoS Vulnerabilities
Get PDFAmplification DDoS attacks remain a prevalent and severe
threat to the Internet, with recent attacks reaching the Tbps range. However, all amplification attack vectors known to date were either found by researchers through laborious manual analysis or could only be identified postmortem following large attacks. Ideally, though, an attack vector is discovered and mitigated before the first attack can occur. To this end, we present AMPFUZZ, the first systematic approach to finding amplification vectors in UDP services in a protocol-agnostic way. AMPFUZZ is based on the state-of-the-art greybox fuzzing boosted by a novel technique to make fuzzing UDP-aware, which significantly increases performance. We evaluate AMPFUZZ on 28 Debian network services, where we (re-)discover 7 known and 6 previously
unreported amplification vulnerabilities