Helmholtz Center for Information Security
CISPA – Helmholtz-Zentrum für InformationssicherheitNot a member yet
3406 research outputs found
Sort by
HyperDbg: Reinventing Hardware-Assisted Debugging
Get PDFSoftware analysis, debugging, and reverse engineering have a crucial impact in today's software industry. Efficient and stealthy debuggers are especially relevant for malware analysis. However, existing debugging platforms fail to address a transparent, effective, and high-performance low-level debugger due to their detectable fingerprints, complexity, and implementation restrictions.
In this paper, we present StealthDbg, a new hypervisor-assisted debugger for high-performance and stealthy debugging of user and kernel applications. To accomplish this, StealthDbg relies on state-of-the-art hardware features available in today's CPUs, such as VT-x and extended page tables. In contrast to other widely used existing debuggers, we design StealthDbg using a custom hypervisor, making it independent of OS functionality or API. We propose hardware-based instruction-level emulation and OS-level API hooking via extended page tables to increase the stealthiness. Our results of the dynamic analysis of 10,853 malware samples show that StealthDbg's stealthiness allows debugging on average 22% and 26% more samples than WinDbg and x64dbg, respectively. Moreover, in contrast to existing debuggers, StealthDbg is not detected by any of the 13 tested packers and protectors. We improve the performance over other debuggers by deploying a VMX-compatible script engine, eliminating unnecessary context switches. Our experiment on three concrete debugging scenarios shows that compared to WinDbg as the only kernel debugger, StealthDbg performs step-in, conditional breaks, and syscall recording, 2.98x, 1319x, and 2018x faster, respectively. We finally show real-world applications, such as a 0-day analysis, structure reconstruction for reverse engineering, software performance analysis, and code-coverage analysis
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Get PDFFor a graph G, a subset S ⊆ V (G) is called a resolving set if for any two vertices u, v ∈ V (G), there
exists a vertex w ∈ S such that d(w, u) ̸= d(w, v). The Metric Dimension problem takes as input a
graph G and a positive integer k, and asks whether there exists a resolving set of size at most k. This
problem was introduced in the 1970s and is known to be NP-hard [GT 61 in Garey and Johnson’s
book]. In the realm of parameterized complexity, Hartung and Nichterlein [CCC 2013] proved that
the problem is W[2]-hard when parameterized by the natural parameter k. They also observed
that it is FPT when parameterized by the vertex cover number and asked about its complexity
under smaller parameters, in particular the feedback vertex set number. We answer this question
by proving that Metric Dimension is W[1]-hard when parameterized by the feedback vertex set
number. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the
problem is W[1]-hard parameterized by the treewidth. Regarding the parameterization by the
vertex cover number, we prove that Metric Dimension does not admit a polynomial kernel under
this parameterization unless NP ⊆ coNP/poly. We observe that a similar result holds when the
parameter is the distance to clique. On the positive side, we show that Metric Dimension is FPT
when parameterized by either the distance to cluster or the distance to co-cluster, both of which are
smaller parameters than the vertex cover number
A World Wide View of Browsing the World Wide Web
Get PDFIn this paper, we perform the first large-scale study of how people spend time on the web. Our study is based on anonymous, aggregate telemetry data from several hundred million Google Chrome users who have explicitly enabled sharing URLs with Google and who have usage statistic reporting enabled. We analyze the distribution of web traffic, the types of websites that people visit and spend the most time on, the differences between desktop and mobile browsing behavior, the geographical differences in web usage, and the most popular websites in regions worldwide. Our study sheds light on online user behavior and how the research community can more accurately analyze the web in the future
Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness
Get PDFEnd-to-end (geometric) deep learning has seen first successes in approximating the solution of combinatorial optimization problems. However, generating data in the realm of NP-hard/-complete tasks brings practical and theoretical challenges, resulting in evaluation protocols that are too optimistic. Specifically, most datasets only capture a simpler subproblem and likely suffer from spurious features. We investigate these effects by studying adversarial robustness -a local generalization property- to reveal hard, model-specific instances and spurious features. For this purpose, we derive perturbation models for SAT and TSP. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound, allowing us to determine the true label of perturbed samples without a solver. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning. Although such robust solvers exist, we show empirically that the assessed neural solvers do not generalize well w.r.t. small perturbations of the problem instance
Assume, Guarantee or Repair - A Regular Framework for Non Regular Properties
Get PDFWe present Assume-Guarantee-Repair (AGR) - a novel framework which verifies that a program satisfies a set of properties and also repairs the program in case the verification fails.
We consider communicating programs - these are simple C-like programs, extended with synchronous actions over communication channels.
Our method, which consists of a learning-based approach to assume-guarantee reasoning, performs verification and repair simultaneously: in every iteration, AGR either makes another step towards proving that the (current) system satisfies the required properties, or alters the system in a way that brings it closer to satisfying the properties. To handle infinite-state systems we build finite abstractions,
for which we check the satisfaction of complex properties that contain first-order constraints, using both syntactic and semantic-aware methods.
We implemented AGR and evaluated it on various communication protocols. Our experiments present compact proofs of correctness and quick repairs
NTRU--um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus
Get PDFNTRUEncrypt is one of the first lattice-based encryption schemes.
Furthermore, the earliest fully homomorphic encryption (FHE) schemes rely on the NTRU problem. Currently, NTRU is one of the leading candidates in the NIST post-quantum standardization competition. What makes NTRU appealing is the age of the cryptosystem and relatively good performance.
Unfortunately, FHE based on NTRU became impractical due to efficient attacks on NTRU instantiations with ``overstretched'' modulus.
In particular, currently, NTRU-based FHE schemes to support a reasonable circuit depth require instantiating NTRU with a very large modulus.
Breaking the NTRU problem for such large moduli turns out to be easy.
Due to these attacks, any serious work on practical NTRU-based FHE essentially stopped.
In this paper, we reactivate research on practical FHE that can be based on NTRU. We design an efficient bootstrapping scheme in which the noise growth is small enough to keep the modulus to dimension ratio relatively small, thus avoiding the negative consequences of ``overstretching'' the modulus.
Our bootstrapping algorithm is an accumulator-type bootstrapping scheme analogous to AP/FHEW/TFHE.
Finally, we show that we can use the bootstrapping procedure to compute
any function over .
Consequently, we obtain one of the fastest FHE bootstrapping schemes able to compute any function over elements of a finite field alongside reducing the error
On the Adaptive Security of the Threshold BLS Signature Scheme
Get PDFThreshold signatures are a crucial tool for many distributed protocols. As shown by Cachin, Kursawe, and Shoup (PODC `00), schemes with unique signatures are of particular importance, as they allow to implement distributed coin flipping very efficiently and without any timing assumptions. This makes them an ideal building block for (inherently randomized) asynchronous consensus protocols.
The threshold-BLS signature of Boldyreva (PKC `03) is both unique and very compact, but unfortunately lacks a security proof against adaptive adversaries. Thus, current consensus protocols either rely on less efficient alternatives or are not adaptively secure. In this work, we revisit the security of the threshold BLS signature by showing the following results, assuming t adaptive corruptions:
- We give a modular security proof that follows a two-step approach: 1) We introduce a new security notion for distributed key generation protocols (DKG). We show that it is satisfied by several protocols that previously only had a static security proof. 2) Assuming any DKG protocol with this property, we then prove unforgeability of the threshold BLS scheme. Our reductions are tight and can be used to substantiate real-world parameter choices.
- To justify our use of strong assumptions such as the algebraic group model (AGM) and the hardness of one-more-discrete logarithm (OMDL), we prove an impossibility result: Even in the AGM, a strong interactive assumption is required in order to prove the scheme secure
On Pairing-Free Blind Signature Schemes in the Algebraic Group Model
No full textStudying the security and efficiency of blind signatures is an important goal for privacy sensitive applications. In particular, for large-scale settings (e.g., cryptocurrency tumblers), it is important for schemes to scale well with the number of users in the system. Unfortunately, all practical schemes either 1) rely on (very strong) number theoretic hardness assumptions and/or computationally expensive pairing operations over bilinear groups, or 2) support only a polylogarithmic number of concurrent (i.e., arbitrarily interleaved) signing sessions per public key. In this work, we revisit the security of two pairing-free blind signature schemes in the Algebraic Group Model (AGM) + Random Oracle Model (ROM). Concretely,
1.
We consider the security of Abe’s scheme (EUROCRYPT ‘01), which is known to have a flawed proof in the plain ROM. We adapt the scheme to allow a partially blind variant and give a proof of the new scheme under the discrete logarithm assumption in the AGM+ROM, even for (polynomially many) concurrent signing sessions.
2.
We then prove that the popular blind Schnorr scheme is secure under the one-more discrete logarithm assumption if the signatures are issued sequentially. While the work of Fuchsbauer et al. (EUROCRYPT ‘20) proves the security of the blind Schnorr scheme for concurrent signing sessions in the AGM+ROM, its underlying assumption, ROS, is proven false by Benhamouda et al. (EUROCRYPT ‘21) when more than polylogarithmically many signatures are issued. Given the recent progress, we present the first security analysis of the blind Schnorr scheme in the slightly weaker sequential setting. We also show that our security proof reduces from the weakest possible assumption, with respect to known reduction techniques
How Byzantine is a Send Corruption?
No full textConsensus protocols enable n parties, each holding some input string, to agree on a common output even in the presence of corrupted parties. Recent work has pushed to understand the problem when a majority of parties may be corrupted thus providing higher resilience, and under various forms of corruptions. Zikas, Hauser, and Maurer introduced a model in which receive-corrupt parties may not receive messages sent to them, and send-corrupt parties may have their sent messages dropped. Otherwise, receive-corrupt and send-corrupt parties behave honestly and their inputs and outputs are constrained by the security definitions. Zikas, Hauser, and Maurer gave a perfectly secure, linear-round protocol for n>trcv+tsnd+3tbyz
, where trcv
, tsnd
, and tbyz
represent thresholds on receive-, send-, and byzantine-corruptions.
We present the first expected constant-round protocol in the general corruption model tolerating n>trcv+2tsnd+2tbyz
. In comparison, all current sublinear round consensus protocols fail if there exists even a single party which cannot communicate with some honest parties, but whose output must be consistent with the honest parties. While presenting our protocol, we explore the pathology of send-corruptions and characterize the difficulty of dealing with them in sublinear-round protocols. As an illustrative and surprising example (even though not in sublinear rounds), we show that the classical Dolev-Strong broadcast protocol degrades from tolerating tbyz<n
corruptions in the byzantine-only model to tbyz<n/2−tsnd
when send-corrupt parties’ outputs must be consistent with honest parties; we also show why other recent dishonest-majority broadcast protocols degrade similarly.
We prove that our new consensus protocol achieves an optimal threshold of n>trcv+tsnd+2tbyz
when we constrain the adversary to either drop all or none of a sender’s messages in a round (we denote this model by spotty send corruptions). To our knowledge, our protocol for the spotty send corruption model is thus the first sublinear-round consensus protocol for a majority of online faulty parties in any model. Because we are unable to prove optimality of our protocol’s corruption budget in the general case, we leave open the question of optimal corruption tolerance for both send-corruptions and byzantine-corruptions
Committed to Trust: A Qualitative Study on Security & Trust in Open Source Software Projects
No full textOpen Source Software plays an important role in many software ecosystems. Whether in operating systems, network stacks, or as low-level system drivers, software we encounter daily is permeated with code contributions from open source projects. Decentralized development and open collaboration in open source projects introduce unique challenges: code submissions from unknown entities, limited personpower for commit or dependency reviews, and bringing new contributors up-to-date in projects' best practices & processes. In 27 in-depth, semi-structured interviews with owners, maintainers, and contributors from a diverse set of open source projects, we investigate their security and trust practices. For this, we explore projects' behind-the-scene processes, provided guidance & policies, as well as incident handling & encountered challenges. We find that our participants' projects are highly diverse both in deployed security measures and trust processes, as well as their underlying motivations. Based on our findings, we discuss implications for the open source software ecosystem and how the research community can better support open source projects in trust and security considerations. Overall, we argue for supporting open source projects in ways that consider their individual strengths and limitations, especially in the case of smaller projects with low contributor numbers and limited access to resources