Abstract A major research area in discrete geometry is to consider the best way to partition the d -dimensional Euclidean space $$\mathbb {R}^d$$ R d under various quality criteria. In this paper we introduce a new type of space partitioning that is motivated by the problem of rounding noisy measurements from the continuous space $$\mathbb {R}^d$$ R d to a discrete subset of representative values. Specifically, we study partitions of $$\mathbb {R}^d$$ R d into bounded-size tiles colored by one of k colors, such that tiles of the same color have a distance of at least t from each other. Such tilings allow for error-resilient rounding, as two points of the same color and distance less than t from each other are guaranteed to belong to the same tile, and thus, to be rounded to the same point. The main problem we study in this paper is characterizing the achievable tradeoffs between the number of colors k and the distance t , for various dimensions d . On the qualitative side, we show that in $$\mathbb {R}^d$$ R d , using $$k=d+1$$ k = d + 1 colors is both sufficient and necessary to achieve $$t>0$$ t > 0 . On the quantitative side, we achieve numerous upper and lower bounds on t as a function of k . In particular, for $$d=3,4,8,24$$ d = 3 , 4 , 8 , 24 , we obtain sharp asymptotic bounds on t , as $$k \rightarrow \infty $$ k → ∞ . We obtain our results with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Bapat’s connector-free lemma, and Čech cohomology.

Abstract Feistel structures are an extensively researched type of cryptographic schemes. In this paper, we describe improved attacks on Feistel structures with more than 4 rounds. We achieve this by a new attack that combines the main benefits of meet-in-the-middle attacks (which can reduce the time complexity by comparing only half blocks in the middle) and dissection attacks (which can reduce the memory complexity but have to guess full blocks in the middle in order to perform independent attacks above and below it). For example, for a 7-round Feistel structure on n -bit inputs with seven independent round keys of n /2 bits each, a MITM attack can use ( $$2^{1.5n}$$ 2 1.5 n , $$2^{1.5n}$$ 2 1.5 n ) time and memory, while dissection requires ( $$2^{2n}$$ 2 2 n , $$2^{n}$$ 2 n ) time and memory. Our new attack requires only ( $$2^{1.5n}$$ 2 1.5 n , $$2^{n}$$ 2 n ) time and memory, using a few known plaintext/ciphertext pairs. When we are allowed to use more known plaintexts, we develop new techniques which rely on the existence of multi-collisions and differential properties deep in the structure in order to further reduce the memory complexity. Our new attacks are not just theoretical generic constructions—in fact, we can use them to reduce the memory complexity of the best known attacks on several concrete cryptosystems such as round-reduced CAST-128 (where we reduce the complexity from $$2^{111} $$ 2 111 to $$2^{64}$$ 2 64 ) and full DEAL-256 (where we reduce the complexity from $$2^{200}$$ 2 200 to $$2^{144}$$ 2 144 ), without affecting their time and data complexities. An extension of our techniques applies even to some non-Feistel structures—for example, in the case of FOX, we reduce the memory complexity of all the best known attacks by a factor of $$2^{16}$$ 2 16 .

Privacy is a fundamental human right, but it is also one of the more complicated rights. Not only privacy is very context-oriented and society-oriented, it is hard to define privacy without involving adversaries trying to break it. The conceived tension between ''national security'' or ''public order'' and the basic human right of privacy, impacts the adoption of Privacy Enhancing Technologies (PETs), and at times, hinders the ability to offer privacy to users.

Biometric data is considered to be very private and highly sensitive. As such, many methods for biometric template protection were considered over the years — from biohashing and specially crafted feature extraction procedures, to the use of cryptographic solutions such as Fuzzy Commitments or the use of Fully Homomorphic Encryption (FHE).A key question that arises is how much protection these solutions can offer when the adversary can inject samples, and observe the outputs of the system. While for systems that return the similarity score, one can use attacks such as hill-climbing, for systems where the adversary can only learn whether the authentication attempt was successful, this question remained open.In this paper, we show that it is indeed possible to reconstruct the biometric template by just observing the success/failure of the authentication attempt (given the ability to inject a sufficient amount of faces). Our attack achieves negligible template reconstruction loss and enables full recovery of facial images through a generative inversion method, forming a pipeline from binary scores to high-resolution facial images that successfully pass the system more than 98% of the time. Our results are, of course, independent of the protection mechanism used by the system.

Abstract Boomerang attacks are extensions of differential attacks that make it possible to combine two unrelated differential properties of the first and second part of a cryptosystem with probabilities p and q into a new differential-like property of the whole cryptosystem with probability $$p^2q^2$$ p 2 q 2 (since each one of the properties has to be satisfied twice). In this paper, we describe a new version of boomerang attacks which uses the counterintuitive idea of throwing out most of the data in order to force equalities between certain values on the ciphertext side. In certain cases, this creates a correlation between the four probabilistic events, which increases the probability of the combined property to $$p^2q$$ p 2 q and increases the signal-to-noise ratio of the resultant distinguisher. We call this variant a retracing boomerang attack since we make sure that the boomerang we throw follows the same path on its forward and backward directions. To demonstrate the power of the new technique, we apply it to the case of 5-round AES. This version of AES was repeatedly attacked by a large variety of techniques, but for twenty years its complexity had remained stuck at $$2^{32}$$ 2 32 . At Crypto’18, it was finally reduced to $$2^{24}$$ 2 24 (for full key recovery), and with our new technique, we can further reduce the complexity of full key recovery to the surprisingly low value of $$2^{16.5}$$ 2 16.5 (i.e., only 90, 000 encryption/decryption operations are required for a full key recovery). In addition to improving previous attacks, our new technique unveils a hidden relationship between boomerang attacks and two other cryptanalytic techniques, the yoyo game and the recently introduced mixture differentials.

Alibaba Cloud was the second cloud provider to offer preemptible (spot) instances, and yet their price traces have never been analyzed. We analyzed thousands of price traces collected for over 3 years to find sharp and coordinated behavioral changes in the pricing.

A major research area in discrete geometry is to consider the best way to partition the $d$-dimensional Euclidean space $\mathbb{R}^d$ under various quality criteria. In this paper we introduce a new type of space partitioning that is motivated by the problem of rounding noisy measurements from the continuous space $\mathbb{R}^d$ to a discrete subset of representative values. Specifically, we study partitions of $\mathbb{R}^d$ into bounded-size tiles colored by one of $k$ colors, such that tiles of the same color have a distance of at least $t$ from each other. Such tilings allow for \emph{error-resilient} rounding, as two points of the same color and distance less than $t$ from each other are guaranteed to belong to the same tile, and thus, to be rounded to the same point. The main problem we study in this paper is characterizing the achievable tradeoffs between the number of colors $k$ and the distance $t$, for various dimensions $d$. On the qualitative side, we show that in $\mathbb{R}^d$, using $k=d+1$ colors is both sufficient and necessary to achieve $t>0$. On the quantitative side, we achieve numerous upper and lower bounds on $t$ as a function of $k$. In particular, for $d=3,4,8,24$, we obtain sharp asymptotic bounds on $t$, as $k \to \infty$. We obtain our results with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Bapat's connector-free lemma, and Čech cohomology.

We focus on attacks against a biometric authentication system aimed at reconstructing a biometric sample of the subject from the protected template. Such systems include three blocks: feature extraction, binarization, and protection. We propose a new white-box reversing attack on the binarization block that approximates a biometric template given the binary string obtained by the binarization block. The experiments show that the proposed attack reconstructs very accurate approximations that pass the verification threshold when compared to templates produced from the same and different samples of the subject. We then integrate this attack with known attacks on the other two blocks, namely, a variant of a guessing attack to extract the binary string and biometric inversion attack to reconstruct a sample from its template. We instantiate this end-to-end attack on a face authentication system using fuzzy commitments for protection. Facial images reconstructed by the end-to-end attack greatly resemble the original ones. In the simplest attack scenario, more than 83% of these reconstructed templates succeed in unlocking an account (when the system is configured to 0.1% FMR). Even in the “hardest” settings (in which we take a reconstructed image from one system and use it in a different system, with a different feature extraction process) the reconstructed image offers 170 to 210 times higher success rates than the system's FMR.

The problem of online checkpointing is a classical problem with numerous applications that has been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. Bringmann, Doerr, Neumann, and Sliacan studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k and smaller than ln 4-o(1)≈ 1.39 for the sparse subset of k ’s, which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k . In this article, we solve the main problems left open in the above-mentioned paper by proving that ln 4 is a tight upper and lower bound on the asymptotic discrepancy for all large k and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k ≤ 10. In the last part of the article, we describe some new applications of this online checkpointing problem.

Biometrics traits such as faces, fingerprints, and irises, are becoming prevalent in computer security applications: from authentication systems to identification systems. Given the sensitive nature of biometrics, a great deal of effort is put into protecting the biometric data after it is acquired - from secure sketch and fuzzy extractors to the use of secure multiparty computations (in protocols such as SCiFI or GSHADE). While these solutions make sure that the extracted values (e.g., binary strings or vectors) that correspond to the biometrics are kept privately and securely, their practical implementations are not optimal with respect to privacy guarantees in the process of extracting the information from the raw biometric data. This paper analyses current solutions for protected systems and discusses the existing and potential problems in the security and privacy of their feature extraction and the binarization processes. As an illustrative example, we show a PoC of an attack on a feature extraction solution from facial images, used in several protected systems, and show that it reveals information which is very close to the training image of the user. As we argue in this paper, other solutions provide privacy for the system's users but make use of external set of biometric data which is often quite large, thus facing privacy and ownership issues associated with the external set of people. The take home message of this paper is: Many of the existing “privacy preserving” solutions neglect the privacy and security aspects of the feature extraction and binarization processes. Hence, we urge future research to close this gap in the security and privacy of biometric systems.

The problem of online checkpointing is a classical problem with numerous applications which had been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. At ICALP'13 Bringmann et al. studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k, and smaller than ln4-o(1)~~1.39 for the sparse subset of k's which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k. In this paper we solve the main problems left open in the ICALP'13 paper by proving that ln4 is a tight upper and lower bound on the asymptotic discrepancy for all large k, and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k <= 10.

Recent advances in deep learning (DL) allow for solving complex AI problems that used to be considered very hard. While this progress has advanced many fields, it is considered to be bad news for Completely Automated Public Turing tests to tell Computers and Humans Apart (CAPTCHAs), the security of which rests on the hardness of some learning problems. In this paper, we introduce DeepCAPTCHA, a new and secure CAPTCHA scheme based on adversarial examples, an inherit limitation of the current DL networks. These adversarial examples are constructed inputs, either synthesized from scratch or computed by adding a small and specific perturbation called adversarial noise to correctly classified items, causing the targeted DL network to misclassify them. We show that plain adversarial noise is insufficient to achieve secure CAPTCHA schemes, which leads us to introduce immutable adversarial noise-an adversarial noise that is resistant to removal attempts. In this paper, we implement a proof of concept system, and its analysis shows that the scheme offers high security and good usability compared with the best previously existing CAPTCHAs.

Over the last 20 years, the privacy of most GSM phone conversations was protected by the A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They are being replaced now by the new A5/3 and A5/4 algorithms, which are based on the block cipher KASUMI. In this paper we describe a new type of attack called a sandwich attack , and use it to construct a simple related-key distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2 −14 . By using this distinguisher and analyzing the single remaining round, we can derive the complete 128-bit key of the full KASUMI with a related-key attack which uses only 4 related keys, 2 26 data, 2 30 bytes of memory, and 2 32 time. These completely practical complexities were experimentally verified by performing the attack in less than two hours on a single-core of a PC. Interestingly, neither our technique nor any other published attack can break the original MISTY block cipher (on which KASUMI is based) significantly faster than exhaustive search. Our results thus indicate that the modifications made by ETSI’s SAGE group in moving from MISTY to KASUMI made it extremely weak when related-key attacks are allowed, but do not imply anything about its resistance to single-key attacks. Consequently, there is no indication that the way KASUMI is implemented in GSM and 3G networks is practically vulnerable in any realistic attack model.

This work presents an attack on the privacy of some voting systems. We show that by combining information from several sources, some of it publicly available, and some of it can be easily collected ad-hoc, an adversary can greatly reduce the size of a voter's anonymity set. In many cases the obtained information is sufficient to deduce the content of a vote (or approximate a small set of possible values).

Biometric authentication is more secure than using regular passwords, as biometrics cannot be "forgotten" and contain high entropy. Thus, many constructions rely on biometric features for authentication, and use them as a source for "good" cryptographic keys. At the same time, biometric systems carry with them many privacy concerns.

The majority of current attacks on reduced-round variants of block ciphers seeks to maximize the number of rounds that can be broken, using less data than the entire codebook and less time than exhaustive key search. In this paper, we pursue a different approach, restricting the data available to the adversary to a few plaintext/ciphertext pairs. We argue that consideration of such attacks (which received little attention in recent years) improves our understanding of the security of block ciphers and of other cryptographic primitives based on block ciphers. In particular, these attacks can be leveraged to more complex attacks, either on the block cipher itself or on other primitives (e.g., stream ciphers, MACs, or hash functions) that use a small number of rounds of the block cipher as one of their components. As a case study, we consider the Advanced Encryption Standard (AES)-the most widely used block cipher. The AES round function is used in many cryptographic primitives, such as the hash functions Lane, SHAvite-3, and Vortex or the message authentication codes ALPHA-MAC, Pelican, and Marvin. We present attacks on up to four rounds of AES that require at most three known/chosen plaintexts. We then apply these attacks to cryptanalyze an AES-based stream cipher (which follows the leak extraction methodology), and to mount the best known plaintext attack on six-round AES.

In 2004, we introduced the related-key boomerang/ rectangle attacks, which allow us to enjoy the benefits of the boomerang attack and the related-key technique, simultaneously. The new attacks were used since then to attack numerous block ciphers. While the claimed applications are significant, most of them have a major drawback. Their validity cannot be verified experimentally due to their high complexity. Together with the lack of rigorous justification of the probabilistic assumptions underlying the technique, this lead Murphy to claim that attacks using the related-key boomerang/rectangle technique are not legitimate. This paper contains two contributions. The first is a rigorous analysis of the related-key boomerang/rectangle attacks, including devising provably optimal distinguishers and computing their success rate, and discussing the underlying independence assumptions. The second contribution is an extensive experimental verification of the related-key boomerang attack against the GSM block cipher, KASUMI. Our experiments reveal that the success probability of the distinguisher, when averaged over different choices of the keys, is close to the theoretical prediction. However, the exact probability depends on the key, such that for some por- tion of the keys, the distinguisher holds with a higher probability than expected, while for the rest of the keys, the distinguisher fails completely.

The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced by the new A5/3 (and the soon to be announced A5/4) algorithm based on the block cipher KASUMI, which is a modified version of MISTY. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2− 14. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, 226 data, 230 bytes of memory, and 232 time. These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity. Interestingly, neither our technique nor any other published attack can break MISTY in less than the 2128 complexity of exhaustive search, which indicates that the changes made by ETSI’s SAGE group in moving from MISTY to KASUMI resulted in a much weaker cipher.

For years, the cryptographic community has searched for good nonlinear functions. Bent functions, almost perfect nonlinear functions, and similar constructions have been suggested as a good base for cryptographic applications due to their highly nonlinear nature. In the first part of this paper, we examine using these functions as block ciphers, and present several distinguishers between almost perfect nonlinear permutations and random permutations. In the second part of the paper, we suggest a criterion to measure the effective linearity of a given block cipher. We devise a general distinguisher for block ciphers based on their effective linearity. Finally, we show that for several constructions, our distinguishing attack is better than previously known techniques.