Abstract We study the use of symmetric cryptography in the MTProto 2.0 protocol, Telegram’s equivalent of the TLS protocol. We give positive and negative results. On the one hand, we formally and in detail specify a slight variant of Telegram’s “record protocol” and prove that it achieves security in a suitable bidirectional secure channel model, albeit under unstudied assumptions; this model itself advances the state of the art for secure channels. On the other hand, we first motivate our slight deviation from MTProto as deployed by giving two attacks on the original protocol specification: one of practical, one of theoretical interest. Then, we give two attacks on the implementation, which are outside of our formal model: one targeting the client, one targeting the server. The client-side attack enables plaintext recovery by exploiting timing side channels, of varying strength, in three official Telegram clients. On its own this attack is thwarted by the secrecy of header fields that are established by Telegram’s key exchange protocol. We thus chain this attack with an attack against the implementation of the key exchange protocol on Telegram’s servers. This final attack breaks the authentication properties of Telegram’s key exchange, allowing a MitM attack. More mundanely, it also reduces the cost of the client-side plaintext-recovery attack. In totality, our results provide the first comprehensive study of MTProto’s use of symmetric cryptography, as well as highlight weaknesses in its key exchange.

Recent work (Falzon and Tang USENIX 2025) has shown that a protocol participant who behaves honestly but strategically chooses its inputs can break input privacy in the Private Join and Compute functionality. In this work, we expand our understanding of attacks in this setting by investigating a broader class of functionalities, namely: Private Set Union (PSU), PSU-Cardinality (PSU-CA), and Meta’s multi-key private matching (MKPM) functionality. We begin with a simple yet novel attack on PSU that fully reconstructs the intersection using only two protocol invocations and forms the conceptual foundation for our more complex attacks. We also show that any attack on PSI-Cardinality, such as that of Guo et al. (USENIX 2023), lifts to an attack on PSU-CA that recovers the intersection with only three additional queries. For the MKPM protocol, we distinguish its intended matching functionality from the protocol-specific leakage, give an attack against the intended functionality, and then show that exploiting the additional leakage enables even stronger attacks, including partial reconstruction of the other party’s records from a single protocol invocation. We conclude by discussing possible mitigations for deploying such systems. Our analysis demonstrates limitations of existing secure multi-party computation security definitions and highlights the real-world privacy risks associated with deploying these functionalities in practice.

Anonymous communication is vital for enabling individuals to participate in social discourse without fear of marginalization or persecution. An important but often overlooked part of anonymous communication is the bootstrapping of new communication channels. If Alice wants to communicate with Bob, she must first learn his in-system identifier. In synchronous designs, message exchange is only possible once both communication partners have agreed to communicate. Thus, Alice must notify Bob of her intent, Bob must learn her in-system identifier, and Bob must acknowledge her notification. This bootstrapping process is generally assumed to occur out-of-band, but if it discloses metadata, communication partners are revealed even if the channel itself is fully anonymized. We propose Sabot, the first anonymous bootstrapping protocol that achieves both strong cryptographic privacy guarantees and bandwidth-efficient communication. In Sabot, clients cooperatively generate a private relationship matrix, which encodes who wants to contact whom. Clients communicate with k ≥ 2 servers to obtain ''their'' part of the matrix and augment the received information using Private Information Retrieval (PIR) to learn about their prospective communication partners. Compared to previous solutions, Sabot achieves stronger privacy guarantees and reduces the bandwidth overhead by an order of magnitude.

Content-defined chunking (CDC) algorithms split streams of data into smaller blocks, called chunks, in a way that preserves chunk boundaries when the data is partially changed. CDC is ubiquitous in applications that deduplicate data such as backup solutions, software patching systems, and file hosting platforms. Much like compression, CDC can introduce leakage when combined with encryption: fingerprinting attacks can exploit chunk length patterns to infer information about the data.

Redis (Remote Dictionary Server) is a general purpose, in-memory database that supports a rich array of functionality, including various Probabilistic Data Structures (PDS), such as Bloom filters, Cuckoo filters, as well as cardinality and frequency estimators. These PDS typically perform well in the average case. However, given that Redis is intended to be used across a diverse array of applications, it is crucial to evaluate how these PDS perform under worst-case scenarios, i.e., when faced with adversarial inputs. We offer a comprehensive analysis to address this question. We begin by carefully documenting the different PDS implementations in Redis, explaining how they deviate from those PDS as described in the literature. Then we show that these deviations enable a total of 10 novel attacks that are more severe than the corresponding attacks for generic versions of the PDS. We highlight the critical role of Redis' decision to use non-cryptographic hash functions in the severity of these attacks. We conclude by discussing countermeasures to the attacks

Ghosh, Kamara, and Tamassia (GKT) (ASIA CCS 2021) proposed a graph encryption scheme supporting shortest path queries. This work presents a query recovery attack against the scheme when the adversary is given the original graph and the leakage of certain subsets of queries. The attack falls within the security model used by GKT, and is the first targeting schemes supporting shortest path queries. The attack uses classical graph algorithms to compute the canonical names of the single-destination shortest path spanning trees of the underlying graph and uses these canonical names to precompute the set of candidate queries that match each response. When all shortest path queries to a single node have been observed, the canonical names for the corresponding query tree are computed, and the responses are matched to the candidate queries from the offline phase. The output is guaranteed to contain the correct query. For a graph on n vertices, the attack runs in time O ( n 3 ) and matches the time complexity of the GKT scheme’s setup. The attack’s practicality is demonstrated through an implementation and evaluation on the real-world datasets used in the original paper and on random graphs.

The increasing importance of graph databases and cloud storage services prompts the study of private queries on graphs. We propose PathGES, a graph encryption scheme (GES) for single-pair shortest path queries. PathGES is efficient and mitigates the state-of-the-art attack by Falzon and Paterson (2022) on the GES by Ghosh, Kamara, and Tamassia (2021), while only incurring an additional logarithmic factor in storage overhead. PathGES leverages a novel data structure that minimizes leakage and server computation.

Nextcloud is a leading cloud storage platform with more than 20 million users. Nextcloud offers an end-to-end encryption (E2EE) feature that is claimed to be able “to keep extremely sensitive data fully secure even in case of a full server breach”. They also claim that the Nextcloud server “has Zero Knowledge, that is, never has access to any of the data or keys in unencrypted form”. This is achieved by having encryption and decryption operations that are done using file keys that are only available to Nextcloud clients, with those file keys being protected by a key hierarchy that ultimately relies on long passphrases known exclusively to the users. We provide the first detailed documentation and security analysis of Nextcloud's E2EE feature. Nextcloud's strong security claims motivate conducting the analysis in the setting where the server itself is considered malicious. We present three distinct attacks against the E2EE security guarantees in this setting. Each one enables the confidentiality and integrity of all user files to be compromised. All three attacks are fully practical and we have built proof-of-concept implementations for each. The vulnerabilities make it trivial for a malicious Nextcloud server to access and manipulate users' data. We have responsibly disclosed the three vulnerabilities to N extcloud. The second and third vulnerabilities have been remediated. The first was addressed by temporarily disabling file sharing from the E2EE feature until a redesign of the feature can be made. We reflect on broader lessons that can be learned for designers of E2EE systems.

Poly1305 is a widely-deployed polynomial hash function. The rationale behind its design was laid out in a series of papers by Bernstein, the last of which dates back to 2005. As computer architectures evolved, some of its design features became less relevant, but implementers found new ways of exploiting these features to boost its performance. However, would we still converge to this same design if we started afresh with today’s computer architectures and applications? To answer this question, we gather and systematize a body of knowledge concerning polynomial hash design and implementation that is spread across research papers, cryptographic libraries, and developers’ blogs. We develop a framework to automate the validation and benchmarking of the ideas that we collect. This approach leads us to five new candidate designs for polynomial hash functions. Using our framework, we generate and evaluate different implementations and optimization strategies for each candidate. We obtain substantial improvements over Poly1305 in terms of security and performance. Besides laying out the rationale behind our new designs, our paper serves as a reference for efficiently implementing polynomial hash functions, including Poly1305.

Abstract Reliable probabilistic primality tests are fundamental in public-key cryptography. In adversarial scenarios, a composite with a high probability of passing a specific primality test could be chosen. In such cases, we need worst-case error estimates of the test. However, in many scenarios, the numbers are randomly chosen and thus have a significantly smaller error probability. We are hence interested in average-case error estimates. In this paper we establish such bounds for the strong Lucas primality test, as there exist only worst-case, but no average-case error bounds. This allows us to use this test with more confidence. Let us examine an algorithm that draws odd k-bit integers uniformly and independently, runs t independent iterations of the strong Lucas test with randomly chosen parameters, and outputs the first number that passes all t consecutive rounds. We attain numerical upper bounds on the probability that a composite is returned. Moreover, we examine a slight modification of this algorithm that only considers integers that are not divisible by small primes, yielding improved bounds. In addition, we classify the numbers that contribute most to our estimate.

Physically Unclonable Functions (PUFs) in silicon have received significant attention since their initial proposal, with a wide variety of different designs available. This is largely due to their ability to provide device-specific outputs which can be used in diverse applications such as authentication, attestation, and cryptographic key generation. Existing designs for silicon PUFs are based on exploiting manufacturing variation in delay lines or the behaviour of memory cells to provide device-unique outputs. This paper proposes a new kind of PUF which we refer to as a Gate Tunnelling PUF. Our PUF design exploits the effect of manufacturing variation on quantum gate tunnelling current to generate unique, reproducible, yet unpredictable PUF outputs. A significant benefit of our design is its realisability in standard CMOS technology, leading to easy integration of our Gate Tunnelling PUF with other security and general system functions in single-chip designs. We have prototyped our Gate Tunnelling PUF design, producing test devices in arrays of 3584 output bits. Initial results are very promising, showing good randomness, uniqueness, reproducibility and temperature stability. These properties suggest that our devices’ outputs require minimal post-processing to be used for cryptographic keys.

This paper initiates a new direction in the design and analysis of searchable symmetric encryption (SSE) schemes. We provide the first comprehensive security model and definition for SSE that takes into account leakage from the entirety of the SSE system, including not only from access to encrypted indices but also from access to the encrypted database documents themselves. Such system-wide leakage is intrinsic in end-to-end SSE systems, and can be used to break almost all state-of-the-art SSE schemes (Gui et al., IEEE S&P 2023). We then provide a static SSE construction meeting our new security notion. The proposed SSE scheme involves a combination of novel techniques: bucketization to hide volumes of responses to queries, and delayed, pseudorandom write-backs to disrupt access pattern. Our implementation and analysis of the proposed scheme demonstrates that it offers very strong security against general classes of (system-wide) leakage-abuse attacks with moderate overhead. Our scheme scales smoothly to databases containing hundreds of thousand of documents and millions of keyword-document pairs. To the best of our knowledge, this is the first end-to-end SSE scheme that effectively suppresses system-wide leakage while maintaining practical efficiency.

Telegram is a popular messenger with more than 550 million active users per month and with a large ecosystem of different clients. The wide adoption of Telegram by protestors relying on private and secure messaging provides motivation for developing a profound understanding of its cryptographic design and how this influences its security properties. Telegram has its own bespoke transport layer security protocol, MTProto 2.0. This protocol was recently subjected to a detailed study by Albrecht et al. (IEEE S&P 2022). They gave attacks on the protocol and its implementations, along with a security proof for a modified version of the protocol.

MEGA is a leading cloud storage platform with more than 250 million users and 1000 Petabytes of stored data. MEGA claims to offer user-controlled, end-to-end security. This is achieved by having all data encryption and decryption operations done on MEGA clients, under the control of keys that are only available to those clients. This is intended to protect MEGA users from attacks by MEGA itself, or by adversaries who have taken control of MEGA’s infrastructure.We provide a detailed analysis of MEGA’s use of cryptography in such a malicious server setting. We present five distinct attacks against MEGA, which together allow for a full compromise of the confidentiality of user files. Additionally, the integrity of user data is damaged to the extent that an attacker can insert malicious files of their choice which pass all authenticity checks of the client. We built proof-of-concept versions of all the attacks. Four of the five attacks are eminently practical. They have all been responsibly disclosed to MEGA and remediation is underway.Taken together, our attacks highlight significant shortcomings in MEGA’s cryptographic architecture. We present immediately deployable countermeasures, as well as longer-term recommendations. We also provide a broader discussion of the challenges of cryptographic deployment at massive scale under strong threat models.

Symmetric Searchable Encryption (SSE) schemes enable keyword searches over encrypted documents. To obtain efficiency, SSE schemes incur a certain amount of leakage. The vast majority of the literature on SSE considers only leakage from one component of the overall SSE system, the encrypted search index. This component is used to identify which documents to return in response to a keyword query. The actual fetching of the documents is left to another component, usually left unspecified in the literature, but generally envisioned as a simple storage system matching document identifiers to encrypted documents.This raises the question: do SSE schemes actually protect the security of data and queries when considered from a system-wide viewpoint? We answer this question in the negative. We do this by introducing a new inference attack that achieves practically efficient, highly scalable, accurate query reconstruction against end-to-end SSE systems. In particular, our attack works even when the SSE schemes are built in the natural way using the state-of-the-art techniques (namely, volume-hiding encrypted multi-maps) designed to suppress leakage and protect against previous generations of attack.A second question is whether the state-of-the-art leakage suppression techniques can instead be applied on a system-wide basis, to protect both the encrypted search index and the encrypted document store, to produce efficient SSE systems. We also answer this question in the negative. To do so, we implement SSE systems using those state-of-the-art leakage suppression methods, and evaluate their performance. We show that storage overheads range from 100× to 800× while bandwidth overheads range from 20× to100×, as compared to a naïve baseline system.Our results motivate the design of new SSE systems that are designed with system-wide security in mind from the outset. In this regard, we show that one such SSE system due to Chen et al. (IEEE INFOCOM 2018), with provable security guarantees based on differential privacy, is also vulnerable to our new attack.In totality, our results force a re-evaluation of how to build end-to-end SSE systems that offer both security and efficiency.

We present a set of attacks on the OpenPGP specification and implementations of it which result in full recovery of users' private keys. The attacks exploit the lack of cryptographic binding between the different fields inside an encrypted private key packet, which include the key algorithm identifier, the cleartext public parameters, and the encrypted private parameters. This allows an attacker who can overwrite certain fields in OpenPGP key packets to perform cross-algorithm attacks, causing a user's software to, for example, misinterpret an ECC private key as being a DSA key. It also allows an attacker to replace the legitimate public parameters with adversarially chosen ones, e.g. allowing them to select the DSA group. We refer to this class of attacks as Key Overwriting (KO) attacks. We provide a detailed analysis of the vulnerability of different OpenPGP libraries to KO attacks, showing in particular that in some cases additional key validation steps performed by libraries that should prevent the attacks in fact allow variant attacks. We also assess the applicability of KO attacks in the context of specific OpenPGP-based applications that reflect different threat models. Finally, we explain how KO attacks can be completely prevented (and the need for key validation obsoleted) at the OpenPGP specification level by expanding the existing proposal of using AEAD schemes for key packet protection to have all the security-relevant public fields included as Associated Data.

We study the security of Probabilistic Data Structures (PDS) for handling Approximate Membership Queries (AMQ); prominent examples of AMQ-PDS are Bloom and Cuckoo filters. AMQ-PDS are increasingly being deployed in environments where adversaries can gain benefit from carefully selecting inputs, for example to increase the false positive rate of an AMQ-PDS. They are also being used in settings where the inputs are sensitive and should remain private in the face of adversaries who can access an AMQ-PDS through an API or who can learn its internal state by compromising the system running the AMQ-PDS.

Computing the count of distinct elements in large data sets is a common task but naive approaches are memory-expensive. The HyperLogLog (HLL) algorithm (Flajolet et al., 2007) estimates a data set's cardinality while using significantly less memory than a naive approach, at the cost of some accuracy. This trade-off makes the HLL algorithm very attractive for a wide range of applications such as database management and network monitoring, where an exact count may not be needed. The HLL algorithm and variants of it are implemented in systems such as Redis and Google Big Query. Recently, the HLL algorithm has started to be proposed for use in scenarios where the inputs may be adversarially generated, for example counting social network users or detection of network scanning attacks. This prompts an examination of the performance of the HLL algorithm in the face of adversarial inputs. We show that in such a setting, the HLL algorithm's estimate of cardinality can be exponentially bad: when an adversary has access to the internals of the HLL algorithm and has some flexibility in choosing what inputs will be recorded, it can manipulate the cardinality estimate to be exponentially smaller than the true cardinality. We study both the original HLL algorithm and a more modern version of it (Ertl, 2017) that is used in Redis. We present experimental results confirming our theoretical analysis. Finally, we consider attack prevention: we show how to modify HLL in a simple way that provably prevents cardinality estimate manipulation attacks.

We study the use of symmetric cryptography in the MTProto 2.0 protocol, Telegram’s equivalent of the TLS record protocol. We give positive and negative results. On the one hand, we formally and in detail model a slight variant of Telegram’s “record protocol” and prove that it achieves security in a suitable bidirectional secure channel model, albeit under unstudied assumptions; this model itself advances the state-of-the-art for secure channels. On the other hand, we first motivate our modelling deviation from MTProto as deployed by giving two attacks – one of practical, one of theoretical interest – against MTProto without our modifications. We then also give a third attack exploiting timing side channels, of varying strength, in three official Telegram clients. On its own this attack is thwarted by the secrecy of salt and id fields that are established by Telegram’s key exchange protocol. To recover these, we chain the third attack with a fourth one against the implementation of the key exchange protocol on Telegram’s servers. In totality, our results provide the first comprehensive study of MTProto’s use of symmetric cryptography.

The ChaCha20-Poly1305 AEAD scheme is being increasingly widely deployed in practice. Practitioners need proven security bounds in order to set data limits and rekeying intervals for the scheme. But the formal security analysis of ChaCha20-Poly1305 currently lags behind that of AES-GCM. The only extant analysis (Procter, 2014) contains a flaw and is only for the single-user setting. We rectify this situation. We prove a multi-user security bound on the AEAD security of ChaCha20-Poly1305 and establish the tightness of each term in our bound through matching attacks. We show how our bound differs both qualitatively and quantitatively from the known bounds for AES-GCM, highlighting how subtle design choices lead to distinctive security properties. We translate our bound to the nonce-randomized setting employed in TLS 1.3 and elsewhere, and we additionally improve the corresponding security bounds for GCM. Finally, we provide a simple yet stronger variant of ChaCha20-Poly1305 that addresses the deficiencies highlighted by our analysis.

Abstract There is growing evidence that SARS-CoV-2 can be transmitted beyond close proximity contacts, in particular in closed and crowded environments with insufficient ventilation. To help mitigation efforts, contact tracers need a way to notify those who were present in such environments at the same time as infected individuals. Neither traditional human-based contact tracing powered by handwritten or electronic lists, nor Bluetooth-enabled proximity tracing can handle this problem efficiently. In this paper, we propose CrowdNotifier, a protocol that can complement manual contact tracing by efficiently notifying visitors of venues and events with SARS-CoV-2-positive attendees. We prove that CrowdNotifier provides strong privacy and abuse-resistance, and show that it can scale to handle notification at a national scale.

Primality testing is a basic cryptographic task. But developers today are faced with complex APIs for primality testing, along with documentation that fails to clearly state the reliability of the tests being performed. This leads to the APIs being incorrectly used in practice, with potentially disastrous consequences. In an effort to overcome this, we present a primality test having a simplest-possible API: the test accepts a number to be tested and returns a Boolean indicating whether the input was composite or probably prime. For all inputs, the output is guaranteed to be correct with probability at least 1 - 2-128. The test is performant: on random, odd, 1024-bit inputs, it is faster than the default test used in OpenSSL by 17%. We investigate the impact of our new test on the cost of random prime generation, a key use case for primality testing. The OpenSSL developers have adopted our suggestions in full; our new API and primality test are scheduled for release in OpenSSL 3.0.

Secure distance measurement and therefore secure Time-of-Arrival (ToA) measurement is critical for applications such as contactless payments, passive-keyless entry and start systems, and navigation systems. This paper initiates the study of Message Time of Arrival Codes (MTACs) and their security. MTACs represent a core primitive in the construction of systems for secure ToA measurement. By surfacing MTACs in this way, we are able for the first time to formally define the security requirements of physical-layer measures that protect ToA measurement systems against attacks. Our viewpoint also enables us to provide a unified presentation of existing MTACs (such as those proposed in distance-bounding protocols and in a secure distance measurement standard) and to propose basic principles for protecting ToA measurement systems against attacks that remain unaddressed by existing mechanisms. We also use our perspective to systematically explore the tradeoffs between security and performance that apply to all signal modulation techniques enabling ToA measurements.

Abstract We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the $${\text {DDH}} $$ DDH assumption hold for them. Our first construction is symmetric and comes with a $$\kappa $$ κ -linear map $$\mathbf{e }: {{\mathbb {G}}}^\kappa \longrightarrow {\mathbb {G}}_T$$ e:Gκ⟶GT for prime-order groups $${\mathbb {G}}$$ G and $${\mathbb {G}}_T$$ GT . To establish the hardness of the $$\kappa $$ κ -linear $${\text {DDH}} $$ DDH problem, we rely on the existence of a base group for which the $$\kappa $$ κ -strong $${\text {DDH}} $$ DDH assumption holds. Our second construction is for the asymmetric setting, where $$\mathbf{e }: {\mathbb {G}}_1 \times \cdots \times {\mathbb {G}}_{\kappa } \longrightarrow {\mathbb {G}}_T$$ e:G1×⋯×Gκ⟶GT for a collection of $$\kappa +1$$ κ+1 prime-order groups $${\mathbb {G}}_i$$ Gi and $${\mathbb {G}}_T$$ GT , and relies only on the 1-strong $${\text {DDH}} $$ DDH assumption in its base group. In both constructions, the linearity $$\kappa $$ κ can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness-indistinguishability, and zero knowledge), and additively homomorphic encryption for the group $$\mathbb {Z}_N^{+}$$ ZN+ . At a high level, we enable “bootstrapping” multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.

We show that the problem of reconstructing encrypted databases from access pattern leakage is closely related to statistical learning theory. This new viewpoint enables us to develop broader attacks that are supported by streamlined performance analyses. First, we address the problem of ε-approximate database reconstruction (ε-ADR) from range query leakage, giving attacks whose query cost scales only with the relative error ε, and is independent of the size of the database, or the number N of possible values of data items. This already goes significantly beyond the state-of-the-art for such attacks, as represented by Kellaris et al. (ACM CCS 2016) and Lacharité et al. (IEEE S&P 2018). We also study the new problem of ε-approximate order reconstruction (ε-AOR), where the adversary is tasked with reconstructing the order of records, except for records whose values are approximately equal. We show that as few as O(ε-1log ε-1) uniformly random range queries suffice. Our analysis relies on an application of learning theory to PQ-trees, special data structures tuned to compactly record certain ordering constraints. We then show that when an auxiliary distribution is available, ε-AOR can be enhanced to achieve ε-ADR; using real data, we show that devastatingly small numbers of queries are needed to attain very accurate database reconstruction. Finally, we generalize from ranges to consider what learning theory tells us about the impact of access pattern leakage for other classes of queries, focusing on prefix and suffix queries. We illustrate this with both concrete attacks for prefix queries and with a general lower bound for all query classes. We also show a very general reduction from reconstruction with known or chosen queries to PAC learning.

This work provides a systematic analysis of primality testing under adversarial conditions, where the numbers being tested for primality are not generated randomly, but instead provided by a possibly malicious party. Such a situation can arise in secure messaging protocols where a server supplies Diffie-Hellman parameters to the peers, or in a secure communications protocol like TLS where a developer can insert such a number to be able to later passively spy on client-server data. We study a broad range of cryptographic libraries and assess their performance in this adversarial setting. As examples of our findings, we are able to construct 2048-bit composites that are declared prime with probability (1/16) by OpenSSL's primality testing in its default configuration; the advertised performance is (2-80). We can also construct 1024-bit composites that always pass the primality testing routine in GNU GMP when configured with the recommended minimum number of rounds. And, for a number of libraries (Cryptlib, LibTomCrypt, JavaScript Big Number, WolfSSL), we can construct composites that always pass the supplied primality tests. We explore the implications of these security failures in applications, focusing on the construction of malicious Diffie-Hellman parameters. We show that, unless careful primality testing is performed, an adversary can supply parameters (p,q,g) which on the surface look secure, but where the discrete logarithm problem in the subgroup of order q generated by g is easy. We close by making recommendations for users and developers. In particular, we promote the Baillie-PSW primality test which is both efficient and conjectured to be robust even in the adversarial setting for numbers up to a few thousand bits.

We present attacks that use only the volume of responses to range queries to reconstruct databases. Our focus is on practical attacks that work for large-scale databases with many values and records, without requiring assumptions on the data or query distributions. Our work improves on the previous state-of-the-art due to Kellaris et al. (CCS 2016) in all of these dimensions. Our main attack targets reconstruction of database counts and involves a novel graph-theoretic approach. It generally succeeds when R , the number of records, exceeds $N^2/2$, where N is the number of possible values in the database. For a uniform query distribution, we show that it requires volume leakage from only O(N2 łog N) queries (cf. O(N4łog N) in prior work). We present two ancillary attacks. The first identifies the value of a new item added to a database using the volume leakage from fresh queries, in the setting where the adversary knows or has previously recovered the database counts. The second shows how to efficiently recover the ranges involved in queries in an online fashion, given an auxiliary distribution describing the database. Our attacks are all backed with mathematical analyses and extensive simulations using real data.

Today, about 10% of TLS connections are still using CBC-mode cipher suites, despite a long history of attacks and the availability of better options (e.g. AES-GCM). In this work, we present three new types of attack against four popular fully patched implementations of TLS (Amazon's s2n, GnuTLS, mbed TLS and wolfSSL) which elected to use "pseudo constant time" countermeasures against the Lucky 13 attack on CBC-mode. Our attacks combine several variants of the PRIME+PROBE cache timing technique with a new extension of the original Lucky 13 attack. They apply in a cross-VM attack setting and are capable of recovering most of the plaintext whilst requiring only a moderate number of TLS connections. Along the way, we uncovered additional serious (but easy to patch) bugs in all four of the TLS implementations that we studied; in three cases, these bugs lead to Lucky 13 style attacks that can be mounted remotely with no access to a shared cache. Our work shows that adopting pseudo constant time countermeasures is not sufficient to attain real security in TLS implementations in CBC mode.

We analyse the security of database encryption schemes supporting range queries against persistent adversaries. The bulk of our work applies to a generic setting, where the adversary's view is limited to the set of records matched by each query (known as access pattern leakage). We also consider a more specific setting where rank information is also leaked, which is inherent inherent to multiple recent encryption schemes supporting range queries. We provide three attacks. First, we consider full reconstruction, which aims to recover the value of every record, fully negating encryption. We show that for dense datasets, full reconstruction is possible within an expected number of queries N log N + O(N), where N is the number of distinct plaintext values. This directly improves on a quadratic bound in the same setting by Kellaris et al. (CCS 2016). Second, we present an approximate reconstruction attack recovering all plaintext values in a dense dataset within a constant ratio of error, requiring the access pattern leakage of only O(N) queries. Third, we devise an attack in the common setting where the adversary has access to an auxiliary distribution for the target dataset. This third attack proves highly effective on age data from real-world medical data sets. In our experiments, observing only 25 queries was sufficient to reconstruct a majority of records to within 5 years. In combination, our attacks show that current approaches to enabling range queries offer little security when the threat model goes beyond snapshot attacks to include a persistent server-side adversary.

We explore the use of the Mantin biases (Mantin, Eurocrypt 2005) to recover plaintexts from RC4-encrypted traffic. We provide a more fine-grained analysis of these biases than in Mantin’s original work. We show that, in fact, the original analysis was incorrect in certain cases: the Mantin biases are sometimes non-existent, and sometimes stronger than originally predicted. We then show how to use these biases in a plaintext recovery attack. Our attack targets two unknown bytes of plaintext that are located close to sequences of known plaintext bytes, a situation that arises in practice when RC4 is used in, for example, TLS. We provide a statistical framework that enables us to make predictions about the performance of this attack and its variants. We then extend the attack using standard dynamic programming techniques to tackle the problem of recovering longer plaintexts, a setting of practical interest in recovering HTTP session cookies and user passwords that are protected by RC4 in TLS. We perform experiments showing that we can successfully recover 16-byte plaintexts with 80% success rate using $$2^{31}$$ ciphertexts, an improvement over previous attacks.

This work presents a systematic analysis of symmetric encryption modes for SSH that are in use on the Internet, providing deployment statistics, new attacks, and security proofs for widely used modes. We report deployment statistics based on two Internet-wide scans of SSH servers conducted in late 2015 and early 2016. Dropbear and OpenSSH implementations dominate in our scans. From our first scan, we found 130,980 OpenSSH servers that are still vulnerable to the CBC-mode-specific attack of Albrecht et al. (IEEE S&P 2009), while we found a further 20,000 OpenSSH servers that are vulnerable to a new attack on CBC-mode that bypasses the counter-measures introduced in OpenSSH 5.2 to defeat the attack of Albrecht et al. At the same time, 886,449 Dropbear servers in our first scan are vulnerable to a variant of the original CBC-mode attack. On the positive side, we provide formal security analyses for other popular SSH encryption modes, namely ChaCha20-Poly1305, generic Encrypt-then-MAC, and AES-GCM. Our proofs hold for detailed pseudo-code descriptions of these algorithms as implemented in OpenSSH. Our proofs use a corrected and extended version of the "fragmented decryption" security model that was specifically developed for the SSH setting by Boldyreva et al. (Eurocrypt 2012). These proofs provide strong confidentiality and integrity guarantees for these alternatives to CBC-mode encryption in SSH. However, we also show that these alternatives do not meet additional, desirable notions of security (boundary-hiding under passive and active attacks, and denial-of-service resistance) that were formalised by Boldyreva et al.

s2n is an implementation of the TLS protocol that was released in late June 2015 by Amazon. It is implemented in around 6,000 lines of C99 code. By comparison, OpenSSL needs around 70,000 lines of code to implement the protocol. At the time of its release, Amazon announced that s2n had undergone three external security evaluations and penetration tests. We show that, despite this, s2n — as initially released — was vulnerable to a timing attack in the case of CBC-mode ciphersuites, which could be extended to complete plaintext recovery in some settings. Our attack has two components. The first part is a novel variant of the Lucky 13 attack that works even though protections against Lucky 13 were implemented in s2n. The second part deals with the randomised delays that were put in place in s2n as an additional countermeasure to Lucky 13. Our work highlights the challenges of protecting implementations against sophisticated timing attacks. It also illustrates that standard code audits are insufficient to uncover all cryptographic attack vectors.

The HIVE hidden volume encryption system was proposed by Blass et al. at ACM-CCS 2014. Even though HIVE has a security proof, this paper demonstrates an attack on its implementation that breaks the main security property claimed for the system by its authors, namely plausible hiding against arbitrary-access adversaries. Our attack is possible because of the HIVE implementation's reliance on the RC4 stream cipher to fill unused blocks with pseudorandom data. While the attack can be easily eliminated by using a better pseudorandom generator, it serves as an example of why RC4 should be avoided in all new applications and a reminder that one has to be careful when instantiating primitives.

The Transport Layer Security (TLS) protocol aims to provide confidentiality and integrity of data in transit across untrusted networks. TLS has become the de facto secure protocol of choice for Internet and mobile applications. DTLS is a variant of TLS that is growing in importance. In this paper, we present distinguishing and plaintext recovery attacks against TLS and DTLS. The attacks are based on a delicate timing analysis of decryption processing in the two protocols. We include experimental results demonstrating the feasibility of the attacks in realistic network environments for several different implementations of TLS and DTLS, including the leading OpenSSL implementations. We provide countermeasures for the attacks. Finally, we discuss the wider implications of our attacks for the cryptographic design used by TLS and DTLS.

IPsec allows a huge amount of flexibility in the ways in which its component cryptographic mechanisms can be combined to build a secure communications service. This may be good for supporting different security requirements but is potentially bad for security. We demonstrate the reality of this by describing efficient, plaintext-recovering attacks against all configurations of IPsec in which integrity protection is applied {\em prior} to encryption -- so-called MAC-then-encrypt configurations. We report on the implementation of our attacks against a specific IPsec implementation, and reflect on the implications of our attacks for real-world IPsec deployments as well as for theoretical cryptography.

Abstract In this paper, we explore the ‘interface’ between identity‐based public key cryptography (ID‐PKC) and mobilead hocnetworks (MANETs). In particular, we examine the problem of naming and namespace design in an identity‐based key infrastructure (IKI). We examine the potential impact that different types of identifiers may have on the utility ofad hocnetworks where an IKI provides the underlying key infrastructure. We also highlight a number of open problems inherent in extending namespaces to allow inter‐operability amongst heterogeneous trust domains. Copyright © 2009 John Wiley & Sons, Ltd.

Abstract In this paper, we examine issues of trust and reputation in mobile ad hoc networks (MANETs). We look at a number of the trust and reputation models that have been proposed, and we highlight open problems in this area. Copyright © 2009 John Wiley & Sons, Ltd.

This paper presents a variety of plaintext-recovering attacks against SSH. We implemented a proof of concept of our attacks against OpenSSH, where we can verifiably recover 14 bits of plaintext from an arbitrary block of ciphertext with probability $2^{-14}$ and 32 bits of plaintext from an arbitrary block of ciphertext with probability $2^{-18}$. These attacks assume the default configuration of a 128-bit block cipher operating in CBC mode. The paper explains why a combination of flaws in the basic design of SSH leads implementations such as OpenSSH to be open to our attacks, why current provable security results for SSH do not cover our attacks, and how the attacks can be prevented in practice.

This paper studies the error linear complexity spectrum of binary sequences with period2n. A precise categorization of those sequences having two distinct critical points in their spectra, as well as an enumeration of these sequences, is given. An upper bound on the maximum number of distinct critical points that the spectrum of a sequence can have is proved, and a construction which yields a lower bound on this number is given. In the process simpler proofs of some known results on the linear complexity andk-error linear complexity of sequences with period2nare provided.

In both the commercial and defence sectors a compelling need is emerging for the rapid, yet secure, dissemination of information across traditional organisational boundaries. In this paper we present a novel trust management paradigm for securing pan-organisational information flows that aims to address the threat of information leakage. Our trust management system is built around an economic model and a trust-based encryption primitive wherein: (i) entities purchase a key from a Trust Authority (TA) which is bound to a voluntarily reported trust score r, (ii) information flows are encrypted such that a flow tagged with a recipient trust score R can be decrypted by the recipient only if it possesses the key corresponding to a voluntarily reported score r < = R, (iii) the economic model (the price of keys) is set such that a dishonest entity wishing to maximise information leakage is incentivised to report an honest trust score r to the TA. This paper makes two important contributions. First, we quantify fundamental tradeoffs on information flow rate, information leakage rate and error in estimating recipient trust score R. Second, we present a suite of encryption schemes that realise our trust-based encryption primitive and identify computation and communication tradeoffs between them.

This paper studies the error linear complexity profiles of binary sequences with period 2n. We give a precise categorization of those sequences having 2 distinct critical points in their profiles, as well as an enumeration of these sequences. We also give an upper bound on the maximum number of distinct critical points that the profile of a sequence can have, along with several constructions for sequences having many distinct critical points.

We describe new attacks which break any RFC- compliant implementation of IPsec making use of encryption-only ESP in tunnel mode. The new attacks are both efficient and realistic: they are ciphertext-only and need only the capability to eavesdrop on ESP-encrypted traffic and to inject traffic into the network. We report on our experiences in applying the attacks to a variety of implementations of IPsec.

The majority of current security architectures for grid systems use public key infrastructure (PKI) to authenticate identities of grid members and to secure resource allocation to these members. Identity-based cryptography (IBC) has some attractive properties which seem to align well with the demands of grid computing. This paper presents a comprehensive investigation of the use of identity-based techniques to provide an alternative grid security architecture. We propose a customised identity-based key agreement protocol which fits nicely with the grid security infrastructure (GSI) and provides a more lightweight secure job submission environment for grid users. Single sign-on and delegation services are also supported in a very natural way in our identity-based architecture.

In this paper, we demonstrate the application of trusted computing to securing peer-to-peer (P2P) networks. We identify a central challenge in providing many of the security services within these networks, namely the absence of stable verifiable peer identities. We employ the functionalities provided by trusted computing technology to establish a pseudonymous authentication scheme for peers and extend this scheme to build secure channels between peers for future communications. In support of our work, we illustrate how commands from the trusted computing group (TCG) specifications can be used to implement our approach in P2P networks.

A binary sequence satisfies a one-dimensional (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/) runlength constraint if every run of zeros has length at least d/sub 1/ and at most k/sub 1/ and every run of ones has length at least d/sub 2/ and at most k/sub 2/. A two-dimensional binary array is (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/)-constrained if it satisfies the one-dimensional (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/) runlength constraint horizontally and the one-dimensional (d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/) runlength constraint vertically. For given d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/,d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/, the two-dimensional capacity is defined as C(d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/) = lim/m,n/spl rarr//spl infin/ log/sub 2/ N(m,n|d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/)/mn where N(m,n|d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/)denotes the number of m/spl times/n binary arrays that are (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/)-constrained. Such constrained systems may have applications in digital storage applications. We consider the question for which values of d/sub i/ and k/sub i/ is the capacity C(d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/) positive and for which values is the capacity zero. The question is answered for many choices of the d/sub i/ and the k/sub i/.

This paper describes the crest-factor analysis of carrier interferometry MC-CDMA and OFDM systems. The maximum crest factor of CF signals grows as log(N). Thus there appears to be an impressive reduction in the crest factor of CI signals. The crest factor performance for carrier interferometry systems is the same as in standard systems, in the sense that the statistical distributions of CF are identical. Hence, the carrier interferometry approach has no CF gain in the asymptotic regime. This analysis is advantageous in terms of BER and diversity.

Codes which reduce the peak-to-average power (PAPR) in multicode code-division multiple-access (MC-CDMA) communications systems are systematically studied. The problem of designing such codes is reformulated as a new coding-theoretic problem: codes with low PAPR are ones in which the codewords are far from the first-order Reed-Muller code. Bounds on the tradeoff between rate, PAPR, and error-correcting capability of codes for MC-CDMA follow. The connections between the code design problem, bent functions, and algebraic coding theory (in particular, the Kerdock codes and Delsarte-Goethals codes) are exploited to construct code families with flexible parameters for the small values of n of practical interest. In view of their algebraic structure, these codes enjoy efficient encoding and decoding algorithms. The correspondence concludes by listing open problems in algebraic coding theory and Boolean functions motivated by the correspondence.

Binary sequences with high linear complexity are of interest in cryptography. The linear complexity should remain high even when a small number of changes are made to the sequence. The error linear complexity spectrum of a sequence reveals how the linear complexity of the sequence varies as an increasing number of the bits of the sequence are changed. We present an algorithm which computes the error linear complexity for binary sequences of period /spl lscr/=2/sup n/ using O(/spl lscr/(log/spl lscr/)/sup 2/) bit operations. The algorithm generalizes both the Games-Chan (1983) and Stamp-Martin (1993) algorithms, which compute the linear complexity and the k-error linear complexity of a binary sequence of period /spl lscr/=2/sup n/, respectively. We also discuss an application of an extension of our algorithm to decoding a class of linear subcodes of Reed-Muller codes.

Single-track circuit codes (STTCs) are circuit codes with codewords of length n such that all the n tracks which correspond to the n distinct coordinates of the codewords are cyclic shifts of the first track. These codes simultaneously generalize single-track Gray codes and ordinary circuit codes. They are useful in angular quantization applications in which error detecting and/or correcting capabilities are needed. A parameter k, called the spread of the code, measures the strength of this error control capability. We consider the existence of STCCs for small lengths n/spl les/17 and spreads k/spl les/6, constructing some optimal and many good examples. We then give a general construction method for STCCs which makes use of ordinary circuit codes. We use this construction to construct examples of codes with 360 and 1000 codewords which are of practical importance. We also use the construction to prove a general result on the existence of STCCs for general spreads.

Previously, a class of generalized Reed-Muller (RM) codes has been suggested for use in orthogonal frequency-division multiplexing. These codes offer error correcting capability combined with substantially reduced peak-to mean power ratios. A number of approaches to decoding these codes have already been developed. Here, we present low complexity, suboptimal alternatives which are inspired by the classical Reed decoding algorithm for binary RM codes. We simulate these new algorithms along with the existing decoding algorithms using additive white Gaussian noise and two-path fading models for a particular choice of code. The simulations show that one of our new algorithms outperforms all existing suboptimal algorithms and offers performance that is within 0.5 dB of maximum-likelihood decoding, yet has complexity comparable to or lower than existing decoding approaches.

Controlling the peak-to-mean envelope power ratio (PMEPR) of orthogonal frequency-division multiplexed (OFDM) transmissions is a notoriously difficult problem, though one which is of vital importance for the practical application of OFDM in low-cost applications. The utility of Golay complementary sequences in solving this problem has been recognized for some time. In this paper, a powerful theory linking Golay complementary sets of polyphase sequences and Reed-Muller codes is developed. Our main result shows that any second-order coset of a q-ary generalization of the first order Reed-Muller code can be partitioned into Golay complementary sets whose size depends only on a single parameter that is easily computed from a graph associated with the coset. As a first consequence, recent results of Davis and Jedwab (see Electron. Lett., vol.33, p.267-8, 1997) on Golay pairs, as well as earlier constructions of Golay (1949, 1951, 1961), Budisin (1990) and Sivaswamy (1978) are shown to arise as special cases of a unified theory for Golay complementary sets. As a second consequence, the main result directly yields bounds on the PMEPRs of codes formed from selected cosets of the generalized first order Reed-Muller code. These codes enjoy efficient encoding, good error-correcting capability, and tightly controlled PMEPR, and significantly extend the range of coding options for applications of OFDM using small numbers of carriers.

The first lower bound on the peak-to-average power ratio (PAPR) of a constant energy code of a given length n, minimum Euclidean distance and rate is established. Conversely, using a nonconstructive Varshamov-Gilbert style argument yields a lower bound on the achievable rate of a code of a given length, minimum Euclidean distance and maximum PAPR. The derivation of these bounds relies on a geometrical analysis of the PAPR of such a code. Further analysis shows that there exist asymptotically good codes whose PAPR is at most 8 log n. These bounds motivate the explicit construction of error-correcting codes with low PAPR. Bounds for exponential sums over Galois fields and rings are applied to obtain an upper bound of order (log n)/sup 2/ on the PAPRs of a constructive class of codes, the trace codes. This class includes the binary simplex code, duals of binary, primitive Bose-Chaudhuri-Hocquenghem (BCH) codes and a variety of their nonbinary analogs. Some open problems are identified.

We present previous results making a connection between generalised Reed-Muller codes and Golay (1949) complementary pairs and sets of sequences. We apply this work to obtain a flexible range of OFDM coding schemes enjoying efficient encoding and decoding and tightly controlled peak-to-mean envelope power ratio. We give an outline of previous work on decoding algorithms for these codes.

In this paper, we introduce new construction methods for Perfect Factors. These are based on the theory of cyclic codes, interleaving techniques and the Lempel homomorphism. The constructions enable us to settle the existence question for Perfect Factors for window sizes at most six.

We propose new families of pseudorandom binary sequences based on Hadamard difference sets and MDS codes. We obtain, for p=4k-1 prime and t an integer with 1/spl les/t/spl les/(p-1)/2, a set of p/sup t/ binary sequences of period p/sup 2/ whose peak correlation is bounded by 1+2t(p+1). The sequences are balanced, have high linear complexity, and are easily generated.

Two approaches to bounding the partial auto- and crosscorrelations of binary sequences are considered. The first approach uses the discrete Fourier transform and bounds for character sums to obtain bounds on partial autocorrelations of m-sequences and on the partial auto- and crosscorrelations for the small Kasami sets and dual-BCH families of sequences. The second approach applies to binary sequences obtained by interleaving m-sequences. A bound on the peak partial correlation of such sequences is derived in terms of the peak partial autocorrelation of the underlying m-sequences. The bound is applied to GMW, No (1987), and other families of sequences for particular parameters. A comparison of the two approaches shows that the elementary method gives generally weaker results but is more widely applicable. On the other hand, both methods show that well-known sequence families can have favorable partial correlation characteristics, making them useful in certain spread-spectrum applications.

We present a new construction for snake-in-the-box codes and circuit codes. Our technique is based on arranging necklaces, i.e., equivalence classes of words under cyclic shifting, to form codes and gives 21 new codes of lengths 8-17, all having more words than the best previously known codes. Included among these are two snake-in-the-box codes: one of length 8 with 96 words, the other of length 10 with 340 words. We also report 15 new codes with small parameters. We prove the optimality of two of these codes and an already-known code. These last results were obtained using straightforward computer search.

This paper argues that the cipher systems based on cellular automata (CA) proposed by S. Nandi et al. (1994) are affine and are insecure. A reply by S. Nandi and P. Pal Chaudhuri is given. The reply emphasizes the point that the regular, modular, cascadable structure of local neighborhood CA can be employed for building low cost cipher system hardware. This cost effective engineering solution can achieve desired level of security with larger size CA.

Single-track Gray codes are a special class of Gray codes which have advantages over conventional Gray codes in certain quantization and coding applications. The problem of constructing high period single-track Gray codes is considered. Three iterative constructions are given, along with a heuristic method for obtaining good seed-codes. In combination, these yield many families of very high period single-track Gray codes. In particular, for m/spl ges/3, length n=2/sup m/, period 2/sup n/-2n codes are obtained.

A particular class of Gray codes, called single-track Gray codes, is introduced. These codes have advantages over conventional Gray codes in certain practical applications. A simple construction for single-track Gray codes is given and it is shown how to obtain such codes for a large range of parameters of practical interest.

We present two related methods of construction for de Bruijn (1946) sequences, both based on interleaving "smaller" de Bruijn sequences. Sequences obtained using these construction methods have the advantage that they can be "decoded" very efficiently, i.e., the position within the sequence of any particular "window" can be found very simply. Sequences with simple decoding algorithms are of considerable practical importance in position location applications.

Given positive integers r, s, u, and /spl upsi/, an (r, s; u, /spl upsi/) perfect map (PM) is defined to be a periodic r/spl times/s binary array in which every u/spl times//spl upsi/ binary array appears exactly once as a periodic subarray. Perfect maps are the natural extension of the de Bruijn sequences to two dimensions. In the paper the existence question for perfect maps is settled by giving constructions for perfect maps for all parameter sets subject to certain simple necessary conditions. Extensive use is made of previously known constructions by finding new conditions which guarantee their repeated application. These conditions are expressed as bounds on the linear complexities of the periodic sequences formed from the rows and columns of perfect maps.>