Helmholtz Center for Information Security
CISPA – Helmholtz-Zentrum für InformationssicherheitNot a member yet
3406 research outputs found
Sort by
Are HTTPS Configurations Still a Challenge?: Validating Theories of Administrators’ Difficulties with TLS Configurations
No full textHTTPS has been the standard for securing online communications for over 20 years. Despite the availability of tools to make the configuration process easier (e.g., Let’s Encrypt, Certbot), SSL Pulse scans show that still more than 50% of the most popular websites are poorly configured, which emphasizes room for improvement. Although a few recent studies looked at the remaining challenges for administrators in configuring HTTPS from a qualitative perspective, there is little work that produced quantitative results. Therefore, we conducted a survey with 96 experienced administrators (as opposed to a student sample) to investigate to which extent configuration problems revealed in prior studies actually exist in the wild. Our results confirm that Let’s Encrypt and ACME clients, such as Certbot, simplify configuration and maintenance for administrators, thus increasing the security of HTTPS configurations. Moreover, we extend the current body of work by examining the trust administrators put into Let’s Encrypt and Certbot. We found that trust and usability issues are currently barriers to the widespread adoption of Certbot
Discovering Significant Patterns under Sequential False Discovery Control
Get PDFWe are interested in discovering those patterns from data with an empirical frequency that is significantly differently than expec- ted. To avoid spurious results, yet achieve high statistical power, we propose to sequentially control for false discoveries during the search. To avoid redundancy, we propose to update our expect- ations whenever we discover a significant pattern. To efficiently consider the exponentially sized search space, we employ an easy- to-compute upper bound on significance, and propose an effective search strategy for sets of significant patterns. Through an extens- ive set of experiments on synthetic data, we show that our method, Spass, recovers the ground truth reliably, does so efficiently, and without redundancy. On real-world data we show it works well on both single and multiple classes, on low and high dimensional data, and through case studies that it discovers meaningful results
Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming
No full textSubset-Sum is an NP-complete problem where one must decide if a multiset of n integers contains
a subset whose elements sum to a target value m. The best known classical and quantum algorithms
run in time Oe(2n/2
) and Oe(2n/3
), respectively, based on the well-known meet-in-the-middle technique.
Here we introduce a novel classical dynamic-programming-based data structure with applications
to Subset-Sum and a number of variants, including Equal-Sums (where one seeks two disjoint
subsets with the same sum), 2-Subset-Sum (a relaxed version of Subset-Sum where each item in
the input set can be used twice in the summation), and Shifted-Sums, a generalization of both of
these variants, where one seeks two disjoint subsets whose sums differ by some specified value.
Given any modulus p, our data structure can be constructed in time O(np), after which queries
can be made in time O(n) to the lists of subsets summing to any value modulo p. We use this
data structure in combination with variable-time amplitude amplification and a new quantum pair
finding algorithm, extending the quantum claw finding algorithm to the multiple solutions case, to
give an O(20.504n
) quantum algorithm for Shifted-Sums. This provides a notable improvement on
the best known O(20.773n
) classical running time established by Mucha et al. [27]. We also study
Pigeonhole Equal-Sums, a variant of Equal-Sums where the existence of a solution is guaranteed
by the pigeonhole principle. For this problem we give faster classical and quantum algorithms with
running time Oe(2n/2
) and Oe(22n/5
), respectively
On the Existence of Universal Lottery Tickets
Get PDFThe lottery ticket hypothesis conjectures the existence of sparse subnetworks of large randomly initialized deep neural networks that can be successfully trained in isolation. Recent work has experimentally observed that some of these tickets can be practically reused across a variety of tasks, hinting at some form of universality. We formalize this concept and theoretically prove that not only do such universal tickets exist but they also do not require further training. Our proofs introduce a couple of technical innovations related to pruning for strong lottery tickets, including extensions of subset sum results and a strategy to leverage higher amounts of depth. Our explicit sparse constructions of universal function families might be of independent interest, as they highlight representational benefits induced by univariate convolutional architectures
Auditing Membership Leakages of Multi-Exit Networks
Get PDFRelying on the fact that not all inputs require the same amount of computation to yield a confident prediction, multi-exit networks are gaining attention as a prominent approach for pushing the limits of efficient deployment. Multi-exit networks endow a backbone model with early exits, allowing to obtain predictions at intermediate layers of the model and thus save computation time and/or energy. However, current various designs of multi-exit networks are only considered to achieve the best trade-off between resource
usage efficiency and prediction accuracy, the privacy risks stemming from them have never been explored. This prompts the need for a comprehensive investigation of privacy risks in multi-exit networks.
In this paper, we perform the first privacy analysis of multi-exit networks through the lens of membership leakages. In particular, we first leverage the existing attack methodologies to quantify the multi-exit networks’ vulnerability to membership leakages. Our experimental results show that multi-exit networks are less vulnerable to membership leakages and the exit (number and depth) attached to the backbone model is highly correlated with the attack performance. Furthermore, we propose a hybrid attack that exploits the exit information to improve the performance of existing attacks. We evaluate membership leakage threat caused by our hybrid attack under three different adversarial setups, ultimately arriving at a model-free and data-free adversary. These results clearly demonstrate that our hybrid attacks are very broadly applicable, thereby the corresponding risks are much more severe than shown by existing membership inference attacks. We further present a defense mechanism called TimeGuard specifically for multi-exit networks and show that TimeGuard mitigates the newly proposed attacks perfectly
SGXFuzz: Efficiently Synthesizing Nested Structures for SGX Enclave Fuzzing
Get PDFIntel's Software Guard Extensions (SGX) provide a non-introspectable trusted execution environment (TEE) to protect security-critical code from a potentially malicious OS. This protection can only be effective if the individual enclaves are secure, which is already challenging in regular software, and this becomes even more difficult for enclaves as the entire environment is potentially malicious. As such, many enclaves expose common vulnerabilities, e.g., memory corruption and SGX-specific vulnerabilities like null-pointer dereferences. While fuzzing is a popular technique to assess the security of software, dynamically analyzing enclaves is challenging, as enclaves are meant to be non-introspectable. Further, they expect an allocated multi-pointer structure as input instead of a plain buffer.
In this paper, we present SGXFuzz, a coverage-guided fuzzer that introduces a novel binary input structure synthesis method to expose enclave vulnerabilities even without source-code access. To obtain code coverage feedback from enclaves, we show how to extract enclave code from distribution formats. We also present an enclave runner that allows execution of the extracted enclave code as a user-space application at native speed, while emulating all relevant environment interactions of the enclave. We use this setup to fuzz enclaves using a state-of-the-art snapshot fuzzing engine that deploys our novel structure synthesis stage. This stage synthesizes multi-layer pointer structures and size fields incrementally on-the-fly based on fault signals. Furthermore, it matches the expected input format of the enclave without any prior knowledge. We evaluate our approach on 30 open and closed-source enclaves and found a total of 79 new bugs and vulnerabilities
The landscape of distributed complexities on trees and beyond
Get PDFWe study the local complexity landscape of locally checkable labeling (LCL) problems on constant-degree graphs with a focus on complexities below log* n.
Our contribution is threefold:
- Our main contribution is that we complete the classification of the complexity landscape of LCL problems on trees in the LOCAL model, by proving that every LCL problem with local complexity o(log* n) has actually complexity O(1). This result improves upon the previous speedup result from o(log log* n) to O(1) by [Chang, Pettie, FOCS 2017].
- In the related LCA and VOLUME models [Alon, Rubinfeld, Vardi, Xie, SODA 2012, Rubinfeld, Tamir, Vardi, Xie, 2011, Rosenbaum, Suomela, PODC 2020], we prove the same speedup from o(log* n) to O(1) for all bounded degree graphs.
- Similarly, we complete the classification of the LOCAL complexity landscape of oriented d-dimensional grids by proving that any LCL problem with local complexity o(log* n) has actually complexity O(1). This improves upon the previous speed-up from o((log* n)^{1/d}) by Suomela in [Chang, Pettie, FOCS 2017]
Helping or Hindering? How Browser Extensions Undermine Security
Get PDFBrowser extensions enhance the functionality of native Web applications on the client side. They provide a rich end-user experience by utilizing feature-rich JavaScript APIs, otherwise inaccessible for native applications. However, prior studies suggest that extensions may degrade the client-side security to execute their operations, such as by altering the DOM, executing untrusted scripts in the applications' context, and performing other security-critical operations for the user. In this study, we instead focus on extensions that tamper with the security headers between the client-server exchange, thereby undermining the security guarantees that these headers provide to the application. To this end, we present our automated analysis framework to detect such extensions by leveraging static and dynamic analysis techniques. We statically identify extensions with the permission to modify headers and then instrument the dangerous APIs to investigate their runtime behavior with respect to modifying headers in-flight. We then use our framework to analyze the three snapshots of the Chrome extension store from Jun 2020, Feb 2021, and Jan 2022. In doing so, we detect 1,129 distinct extensions that interfere with security-related request/response headers and discuss the associated security implications. The impact of our findings is aggravated by the extensions, with millions of installations dropping critical security headers like Content-Security-Policy or X-Frame-Options
Microarchitectural Leakage Templates and Their Application to Cache-Based Side Channels
Get PDFThe complexity of modern processor architectures has given rise to sophisticated interactions among their components. Such interactions may result in potential attack vectors in terms of side channels, possibly available to userland exploits to leak secret data. Exploitation and countering of such side channels requires a detailed understanding of the target component. However, such detailed information is commonly unpublished for many CPUs.
In this paper, we introduce the concept of Leakage Templates to abstractly describe specific side channels and identify their occurrences in binary applications. We design and implement PLUMBER, a framework to derive the generic Leakage Templates from individual code sequences that are known to cause leakage (e.g., found by prior work). PLUMBER uses a combination of instruction fuzzing, instructions' operand mutation and statistical analysis to explore undocumented behavior of microarchitectural optimizations and derive sufficient conditions on vulnerable code inputs that if hold can trigger a distinguishing behavior. Using PLUMBER we identified novel leakage primitives based on Leakage Templates (for ARM Cortex-A53 and -A72 cores), in particular related to previction (a new premature cache eviction), and prefetching behavior. We show the utility of Leakage Templates by re-identifying a prefetcher-based vulnerability in OpenSSL 1.1.0g first reported by Shin et al. [40]
Platypus: A Central Bank Digital Currency with Unlinkable Transactions and Privacy-Preserving Regulation
Get PDFDue to the popularity of blockchain-based cryptocurrencies, the increasing digitalization of payments, and the constantly reducing role of cash in society, central banks have shown an increased interest in deploying central bank digital currencies (CBDCs) that could serve as a digital cash-equivalent. While most recent research on CBDCs focuses on blockchain technology, it is not clear that this choice of technology provides the optimal solution. In particular, the centralized trust model of a CBDC offers opportunities for different designs. In this paper, we depart from blockchain designs and instead build on ideas from traditional e-cash schemes. We propose a new style of building digital currencies that combines the transaction processing model of e-cash with an account-based fund management model. We argue that such a style of building digital currencies is especially well-suited to CBDCs. We also design the first such digital currency system, called Platypus, that provides strong privacy, high scalability, and expressive but simple regulation, which are all critical features for a CBDC. Platypus achieves these properties by adapting techniques similar to those used in anonymous blockchain cryptocurrencies like Zcash to fit our account model and applying them to the e-cash context