Search

Your search keyword '"Orr Dunkelman"' showing total 30 results
Start Over Author "Orr Dunkelman" Language english
30 results on '"Orr Dunkelman"'

1. The QARMAv2 Family of Tweakable Block Ciphers

Author

Roberto Avanzi, Subhadeep Banik, Orr Dunkelman, Maria Eichlseder, Shibam Ghosh, Marcel Nageler, and Francesco Regazzoni

Subjects
Tweakable Block Ciphers, Lightweight Cryptography, Reflection Ciphers, Memory Encryption, Memory Integrity, Message Authentication Codes, Computer engineering. Computer hardware, TK7885-7895
Abstract

We introduce the QARMAv2 family of tweakable block ciphers. It is a redesign of QARMA (from FSE 2017) to improve its security bounds and allow for longer tweaks, while keeping similar latency and area. The wider tweak input caters to both specific use cases and the design of modes of operation with higher security bounds. This is achieved through new key and tweak schedules, revised S-Box and linear layer choices, and a more comprehensive security analysis. QARMAv2 offers competitive latency and area in fully unrolled hardware implementations. Some of our results may be of independent interest. These include: new MILP models of certain classes of diffusion matrices; the comparative analysis of a full reflection cipher against an iterative half-cipher; our boomerang attack framework; and an improved approach to doubling the width of a block cipher.

Published
2023
Full Text
View/download PDF

2. Practical Related-Key Forgery Attacks on Full-Round TinyJAMBU-192/256

Author

Orr Dunkelman, Shibam Ghosh, and Eran Lambooij

Subjects
TinyJAMBU, Differential cryptanalysis, Related-Key, Forgery, NIST-LWC, Computer engineering. Computer hardware, TK7885-7895
Abstract

TinyJAMBU is one of the finalists in the NIST lightweight cryptography competition. It is considered to be one of the more efficient ciphers in the competition and has undergone extensive analysis in recent years as both the keyed permutation as well as the mode are new designs. In this paper we present a related-key forgery attack on the updated TinyJAMBU-v2 scheme with 256- and 192-bit keys. We introduce a high probability related-key differential attack where the differences are only introduced into the key state. Therefore, the characteristic is applicable to the TinyJAMBU mode and can be used to mount a forgery attack. The time and data complexity of the forgery are 233 using 214 related-keys for the 256-bit key version, and 243 using 216 related-keys for the 192-bit key version. For the 128-bit key we construct a related-key differential characteristic on the full keyed permutation of TinyJAMBU with a probability of 2−16. We extend the relatedkey differential characteristics on TinyJAMBU to practical-time key-recovery attacks that extract the full key from the keyed permutation with a time and data complexity of 224, 221, and 219 for respectively the 128-, 192-, and 256-bit key variants. All characteristics are experimentally verified and we provide key nonce pairs that produce the same tag to show the feasibility of the forgery attack. We note that the designers do not claim related-key security, however, the attacks proposed in this paper suggest that the scheme is not key-commiting, which has been recently identified as a favorable property for AEAD schemes.

Published
2023
Full Text
View/download PDF

3. Attacking the IETF/ISO Standard for Internal Re-keying CTR-ACPKM

Author

Orr Dunkelman, Shibam Ghosh, and Eran Lambooij

Subjects
CTR-ACPKM, Multi-user Attack, Entropy Loss, Key Collision, Computer engineering. Computer hardware, TK7885-7895
Abstract

Encrypting too much data using the same key is a bad practice from a security perspective. Hence, it is customary to perform re-keying after a given amount of data is transmitted. While in many cases, the re-keying is done using a fresh execution of some key exchange protocol (e.g., in IKE or TLS), there are scenarios where internal re-keying, i.e., without exchange of information, is performed, mostly due to performance reasons. Originally suggested by Abdalla and Bellare, there are several proposals on how to perform this internal re-keying mechanism. For example, Liliya et al. offered the CryptoPro Key Meshing (CPKM) to be used together with GOST 28147-89 (known as the GOST block cipher). Later, ISO and the IETF adopted the Advanced CryptoPro Key Meshing (ACKPM) in ISO 10116 and RFC 8645, respectively. In this paper, we study the security of ACPKM and CPKM. We show that the internal re-keying suffers from an entropy loss in successive repetitions of the rekeying mechanism. We show some attacks based on this issue. The most prominent one has time and data complexities of O(2κ/2) and success rate of O(2−κ/4) for a κ-bit key. Furthermore, we show that a malicious block cipher designer or a faulty implementation can exploit the ACPKM (or the original CPKM) mechanism to significantly hinder the security of a protocol employing ACPKM (or CPKM). Namely, we show that in such cases, the entropy of the re-keyed key can be greatly reduced.

Published
2023
Full Text
View/download PDF

4. Finding Collisions against 4-Round SHA-3-384 in Practical Time

Author

Senyang Huang, Orna Agmon Ben-Yehuda, Orr Dunkelman, and Alexander Maximov

Subjects
SHA-3 hash function, collision attack, deduce-and-sieve algorithm, SAT solver, Computer engineering. Computer hardware, TK7885-7895
Abstract

The Keccak sponge function family, designed by Bertoni et al. in 2007, was selected by the U.S. National Institute of Standards and Technology (NIST) in 2012 as the next generation of Secure Hash Algorithm (SHA-3). Due to its theoretical and practical importance, cryptanalysis of SHA-3 has attracted a lot of attention. Currently, the most powerful collision attack on SHA-3 is Jian Guo et al.’s linearisation technique. However, this technique is infeasible for variants with a smaller input space, such as SHA-3-384. In this work we improve upon previous results by utilising three ideas which were not used in previous works on collision attacks against SHA-3. First, we use 2-block messages instead of 1-block messages, to reduce constraints and increase flexibility in our solutions. Second, we reduce the connectivity problem into a satisfiability (SAT) problem, instead of applying the linearisation technique. Finally, we propose an efficient deduce-and-sieve algorithm on the basis of two new non-random properties of the Keccak non-linear layer. The resulting collision-finding algorithm on 4-round SHA-3-384 has a practical time complexity of 259.64 (and a memory complexity of 245.94). This greatly improves upon the best known collision attack so far: Dinur et al. achieved an impractical 2147 time complexity. Our attack does not threaten the security margin of the SHA-3 hash function. However, the tools developed in this paper could be used to analyse other cryptographic primitives as well as to develop new and faster SAT solvers.

Published
2022
Full Text
View/download PDF

5. Collaboration between Government and Research Community to Respond to COVID-19: Israel’s Case

Author

Mor Peleg, Amnon Reichman, Sivan Shachar, Tamir Gadot, Meytal Avgil Tsadok, Maya Azaria, Orr Dunkelman, Shiri Hassid, Daniella Partem, Maya Shmailov, Elad Yom-Tov, and Roy Cohen

Subjects
COVID-19, hackathon, datathon, evidence-based regulation, innovative regulation, privacy, Management. Industrial management, HD28-70, Business, HF5001-6182
Abstract

ABSTRACT: Triggered by the COVID-19 crisis, Israel’s Ministry of Health (MoH) held a virtual datathon based on deidentified governmental data. Organized by a multidisciplinary committee, Israel’s research community was invited to offer insights to help solve COVID-19 policy challenges. The Datathon was designed to develop operationalizable data-driven models to address COVID-19 health policy challenges. Specific relevant challenges were defined and diverse, reliable, up-to-date, deidentified governmental datasets were extracted and tested. Secure remote-access research environments were established. Registration was open to all citizens. Around a third of the applicants were accepted, and they were teamed to balance areas of expertise and represent all sectors of the community. Anonymous surveys for participants and mentors were distributed to assess usefulness and points for improvement and retention for future datathons. The Datathon included 18 multidisciplinary teams, mentored by 20 data scientists, 6 epidemiologists, 5 presentation mentors, and 12 judges. The insights developed by the three winning teams are currently considered by the MoH as potential data science methods relevant for national policies. Based on participants’ feedback, the process for future data-driven regulatory responses for health crises was improved. Participants expressed increased trust in the MoH and readiness to work with the government on these or future projects.

Published
2021
Full Text
View/download PDF

6. Cryptanalysis of GOST2

Author

Tomer Ashur, Achiya Bar-On, and Orr Dunkelman

Subjects
Block ciphers, Cryptanalysis, GOST, GOST2, Reflection attack, Fixed-point attack, Related-key attack, Impossible reflection attack, Computer engineering. Computer hardware, TK7885-7895
Abstract

GOST 28147 is a 256-bit key 64-bit block cipher developed by the USSR, later adopted by the Russian government as a national standard. In 2010, GOST was suggested to be included in ISO/IEC 18033-3, but was rejected due to weaknesses found in its key schedule. In 2015, a new version of GOST was suggested with the purpose of mitigating such attacks. In this paper, we show that similar weaknesses exist in the new version as well. More specifically, we present a fixed-point attack on the full cipher with time complexity of 2237 encryptions. We also present a reflection attack with time complexity of 2192 for a key that is chosen from a class of 2224 weak keys. Finally, we discuss an impossible reflection attack which improves on exhaustive search by a factor of 2e, and several possible related-key attacks.

Published
2017
Full Text
View/download PDF

7. Reconstructing an S-box from its Difference Distribution Table

Author

Orr Dunkelman and Senyang Huang

Subjects
S-box, DDT, LAT, the sign determination problem, Computer engineering. Computer hardware, TK7885-7895
Abstract

In this paper we study the problem of recovering a secret S-box from its difference distribution table (DDT). While being an interesting theoretical problem on its own, the ability to recover the S-box from the DDT of a secret S-box can be used in cryptanalytic attacks where the attacker can obtain the DDT (e.g., in Bar-On et al.’s attack on GOST), in supporting theoretical analysis of the properties of difference distribution tables (e.g., in Boura et al.’s work), or in some analysis of S-boxes with unknown design criteria (e.g., in Biryukov and Perrin’s analysis). We show that using the well established relation between the DDT and the linear approximation table (LAT), one can devise an algorithm different from the straightforward guess-and-determine (GD) algorithm proposed by Boura et al. Moreover, we show how to exploit this relation, and embed the knowledge obtained from it in the GD algorithm. We tested our new algorithm on random S-boxes of different sizes, and for random 14-bit bijective S-boxes, our results outperform the GD attack by several orders of magnitude.

Published
2019
Full Text
View/download PDF

8. Advances in Cryptology – EUROCRYPT 2022 : 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 – June 3, 2022, Proceedings, Part II

Author

Orr Dunkelman, Stefan Dziembowski, Orr Dunkelman, and Stefan Dziembowski

Subjects
Cryptography, Data encryption (Computer science), Application software, Computer networks, Coding theory, Information theory
Abstract

The 3-volume-set LNCS 13275, 13276 and 13277 constitutes the refereed proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2022, which was held in Trondheim, Norway, during 30 May – 3 June, 2022. The 85 full papers included in these proceedings were accepted from a total of 372 submissions. They were organized in topical sections as follows: Part I: Best Paper Award; Secure Multiparty Computation; Homomorphic Encryption; Obfuscation; Part II: Cryptographic Protocols; Cryptographic Primitives; Real-World Systems Part III: Symmetric-Key Cryptanalysis; Side Channel Attacks and Masking, Post-Quantum Cryptography; Information-Theoretic Security.

Published
2022

9. Selected Areas in Cryptography : 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers

Author

Orr Dunkelman, Michael J. Jacobson, Jr, Colin O'Flynn, Orr Dunkelman, Michael J. Jacobson, Jr, and Colin O'Flynn

Subjects
Data encryption (Computer science)--Congresses, Computer security--Congresses
Abstract

This book contains revised selected papers from the 27th International Conference on Selected Areas in Cryptography, SAC 2020, held in Halifax, Nova Scotia, Canada in October 2020. The 27 full papers presented in this volume were carefully reviewed and selected from 52 submissions. They cover the following research areas: design and analysis of symmetric key primitives and cryptosystems, including block and stream ciphers, hash functions, MAC algorithms, and authenticated encryption schemes, efficient implementations of symmetric and public key algorithms, mathematical and algorithmic aspects of applied cryptology, and secure elections and related cryptographic constructions

Published
2021

10. Progress in Cryptology – LATINCRYPT 2017 : 5th International Conference on Cryptology and Information Security in Latin America, Havana, Cuba, September 20–22, 2017, Revised Selected Papers

Author

Tanja Lange, Orr Dunkelman, Tanja Lange, and Orr Dunkelman

Subjects
Cryptography, Data encryption (Computer science), Software engineering, Computers and civilization, Application software, Logic design, Coding theory, Information theory
Abstract

This book constitutes the refereed post-conference proceedings of the 5th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2017, held in Havana, Cuba, in September 2017.The 20 papers presented were carefully reviewed and selected from 64 submissions. They are organized in the following topical sections: security protocols; public-key implementation; cryptanalysis; theory of symmetric-key cryptography; multiparty computation and privacy; new constructions; and adversarial cryptography.

Published
2019

11. No Bot Expects the DeepCAPTCHA! Introducing Immutable Adversarial Examples, with Applications to CAPTCHA Generation

Author

Orr Dunkelman, Julio C. Hernandez-Castro, Daniel Perez-Cabo, Margarita Osadchy, and Stuart J. Gibson

Subjects
CAPTCHA, Computer Networks and Communications, Computer science, business.industry, Deep learning, 020206 networking & telecommunications, 02 engineering and technology, Computer security, computer.software_genre, Adversarial system, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Artificial intelligence, Safety, Risk, Reliability and Quality, business, QA, computer
Abstract

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 CAPTCHAs (Completely Automated Public Turing tests to tell Computers and Humans Apart), the security of which rests on the hardness of some learning problems.\ud In this paper we introduce DeepCAPTCHA, a new and secure CAPTCHA scheme based on adversarial examples, an inherit limitation of the current Deep Learning 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 work we implement a proof of concept system, and its analysis shows that the scheme offers high security and good usability compared to the best previously existing CAPTCHAs.

Published
2017

12. Selected Areas in Cryptography - SAC 2015 : 22nd International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers

Author

Orr Dunkelman, Liam Keliher, Orr Dunkelman, and Liam Keliher

Subjects
Cryptography, Data encryption (Computer science), Data protection, Algorithms, Coding theory, Information theory, Computer science—Mathematics, Discrete mathematics
Abstract

This book contains revised selected papers from the 22nd International Conference on Selected Areas in Cryptography, SAC 2015, held in Sackville, NB, Canada in August 2015. The 26 full papers and 3 short papers presented in this volume were carefully reviewed and selected from 91 submissions. They are organized in topical sections named: privacy enhancing technologies; cryptanalysis of symmetric-key primitives; implementation of cryptographic schemes; short papers; privacy preserving data processing; side channel attacks and defenses; new cryptographic constructions; authenticated encryption; on the hardness of mathematical problems; and cryptanalysis of authenticated encryption schemes.

Published
2016

13. Progress in Cryptology – INDOCRYPT 2016 : 17th International Conference on Cryptology in India, Kolkata, India, December 11-14, 2016, Proceedings

Author

Orr Dunkelman, Somitra Kumar Sanadhya, Orr Dunkelman, and Somitra Kumar Sanadhya

Subjects
Cryptography, Data encryption (Computer science), Data protection, Algorithms, Electronic data processing—Management, Computer science—Mathematics, Discrete mathematics
Abstract

This book constitutes the refereed proceedings of the 17th International Conference on Cryptology in India, INDOCRYPT 2016, held in Kolkata, India, in December 2016. The 23 revised full papers presented in this book were carefully reviewed and selected from 84 submissions. The focus of the conference includes works on Public-Key Cryptography, Cryptographic Protocols, Side-Channel Attacks, Implementation of Cryptographic Schemes, Functional Encryption, Symmetric-Key Cryptanalysis, Foundations, and New Cryptographic Constructions.

Published
2016

14. Cryptanalysis of SP Networks with Partial Non-Linear Layers

Author

Nathan Keller, Itai Dinur, Achiya Bar-On, Orr Dunkelman, Boaz Tsaban, Virginie Lallemand, Department of Mathematics [Ramat Gan], Bar-Ilan University [Israël], Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), Computer Science Department [Rehovot], Weizmann Institute of Science [Rehovot, Israël], Department of Computer Science [Haifa], University of Haifa [Haifa], Security, Cryptology and Transmissions (SECRET), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Eurocrypt 2015 : 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)

Subjects
Masking (art), Differential cryptanalysis, Computer science, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, 01 natural sciences, law.invention, Nonlinear system, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, law, Linear cryptanalysis, 0202 electrical engineering, electronic engineering, information engineering, Overhead (computing), 020201 artificial intelligence & image processing, Layer (object-oriented design), Cryptanalysis, Block cipher
Abstract

International audience; Design of SP networks in which the non-linear layer is applied to only a part of the state in each round was suggested by Gérard et al. at CHES 2013. Besides performance advantage on certain platforms, such a design allows for more efficient masking techniques that can mitigate side-channel attacks with a small performance overhead.In this paper we present generic techniques for differential and linear cryptanalysis of SP networks with partial non-linear layers, including an automated characteristic search tool and dedicated key-recovery algorithms. Our techniques can be used both for cryptanalysis of such schemes and for proving their security with respect to basic differential and linear cryptanalysis, succeeding where previous automated analysis tools seem to fail.We first apply our techniques to the block cipher Zorro (designed by Gérard et al. following their methodology), obtaining practical attacks on the cipher which where fully simulated on a single desktop PC in a few days. Then, we propose a mild change to Zorro, and formally prove its security against basic differential and linear cryptanalysis. We conclude that there is no inherent flaw in the design strategy of Gérard et al., and it can be used in future designs, where our tools should prove useful.

Published
2015
Full Text
View/download PDF

15. New Attacks on Feistel Structures with Improved Memory Complexities

Author

Orr Dunkelman, Nathan Keller, Adi Shamir, Itai Dinur, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL), Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Haifa], University of Haifa [Haifa], Computer Science Department [Rehovot], Weizmann Institute of Science [Rehovot, Israël], Department of Mathematics [Bar-Ilan], Bar-Ilan University [Israël], École normale supérieure - Paris (ENS Paris), Département d'informatique de l'École normale supérieure (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt

Subjects
Discrete mathematics, business.industry, Computer science, Order (ring theory), Cryptography, 0102 computer and information sciences, 02 engineering and technology, Type (model theory), Man-in-the-middle attack, 01 natural sciences, law.invention, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, law, Known-plaintext attack, Ciphertext, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, CAST-128, business, Cryptanalysis, Time complexity, ComputingMilieux_MISCELLANEOUS, Block cipher
Abstract

Feistel structures are an extremely important and 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.5n}\)) time and memory, while dissection requires (\(2^{2n}\), \(2^{n}\)) time and memory. Our new attack requires only (\(2^{1.5n}\), \(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 multicollisions and differential properties deep in the structure in order to further reduce the memory complexity.

Published
2015
Full Text
View/download PDF

16. Improved Top-Down Techniques in Differential Cryptanalysis

Author

Masha Gutman, Orr Dunkelman, Adi Shamir, Itai Dinur, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL), Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Haifa], University of Haifa [Haifa], Computer Science Department [Rehovot], Weizmann Institute of Science [Rehovot, Israël], École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Département d'informatique de l'École normale supérieure (DI-ENS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
Discrete mathematics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Distribution (mathematics), Differential cryptanalysis, Black box, Diagonal, Value (computer science), Hamming weight, Time complexity, Mathematics, Block cipher
Abstract

International audience; The fundamental problem of differential cryptanalysis is to find the highest entries in the Difference Distribution Table (DDT) of a given mapping F over n-bit values, and in particular to find the highest diagonal entries which correspond to the best iterative characteristics of F. The standard bottom-up approach to this problem is to consider all the internal components of the mapping along some differential characteristic, and to multiply their transition probabilities. However, this can provide seriously distorted estimates since the various events can be dependent, and there can be a huge number of low probability characteristics contributing to the same high probability entry. In this paper we use a top-down approach which considers the given mapping as a black box, and uses only its input/output relations in order to obtain direct experimental estimates for its DDT entries which are likely to be much more accurate. In particular, we describe three new techniques which reduce the time complexity of three crucial aspects of this problem: Finding the exact values of all the diagonal entries in the DDT for small values of n, approximating all the diagonal entries which correspond to low Hamming weight differences for large values of n, and finding an accurate approximation for any DDT entry whose large value is obtained from many small contributions. To demonstrate the potential contribution of our new techniques, we apply them to the SIMON family of block ciphers, show experimentally that most of the previously published bottom-up estimates of the probabilities of various differentials are off by a significant factor, and describe new differential properties which can cover more rounds with roughly the same probability for several of its members.

Published
2015
Full Text
View/download PDF

17. Reflections on slide with a twist attacks

Author

Orr Dunkelman, Itai Dinur, Adi Shamir, Nathan Keller, Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), Department of Computer Science [Haifa], University of Haifa [Haifa], Computer Science Department [Rehovot], Weizmann Institute of Science [Rehovot, Israël], Department of Mathematics [Bar-Ilan], Bar-Ilan University [Israël], Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt

Subjects
Discrete mathematics, business.industry, Applied Mathematics, Cryptography, 0102 computer and information sciences, 02 engineering and technology, Fixed point, Encryption, 01 natural sciences, Computer Science Applications, law.invention, GOST (block cipher), [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, law, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Reflection attack, Slide attack, Cryptanalysis, business, Algorithm, ComputingMilieux_MISCELLANEOUS, Mathematics, Block cipher
Abstract

Slide attacks use pairs of encryption operations which are slid against each other. Slide with a twist attacks are more sophisticated variants of slide attacks which slide an encryption operation against a decryption operation. Designed by Biryukov and Wagner in 2000, these attacks were used against several cryptosystems, including DESX, the Even---Mansour construction, and Feistel structures with four-round self-similarity. They were further extended in 2012 to the mirror slidex framework, which was used to attack the 20-round GOST block cipher and several additional variants of the Even---Mansour construction. In this paper, we revisit all the previously published applications of these techniques and show that in almost all cases, the same or better results can be achieved by a simpler attack which is based on the seemingly unrelated idea of exploiting internal fixed points. The observation that such fixed points can be useful in cryptanalysis of block ciphers is known for decades and is the basis of the reflection attack presented by Kara in 2007. However, all the examples to which reflection attacks were applied were based on particular constructions such as Feistel structures or GOST key schedules in which it was easy to explicitly list and count the fixed points. In this paper, we generalize Kara's reflection attack by using the combinatorial result that random involutions on $$2^n$$2n values are expected to have a surprisingly large number of $$O(2^{n/2})$$O(2n/2) fixed points (whereas random permutations are expected to have only O(1) fixed points). This makes it possible to reduce the complexity of the best known attack on additional cryptographic schemes in which it is difficult to explicitly characterize and count the internal fixed points.

Published
2015
Full Text
View/download PDF

18. Improved Linear Sieving Techniques with Applications to Step-Reduced LED-64

Author

Nathan Keller, Adi Shamir, Itai Dinur, Orr Dunkelman, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL), Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Haifa], University of Haifa [Haifa], Computer Science Department [Rehovot], Weizmann Institute of Science [Rehovot, Israël], Department of Mathematics [Bar-Ilan], Bar-Ilan University [Israël], École normale supérieure - Paris (ENS Paris), Département d'informatique de l'École normale supérieure (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt

Subjects
CBC-MAC, Differential cryptanalysis, Computer science, 0102 computer and information sciences, 02 engineering and technology, Related-key attack, Key whitening, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Cipher, 010201 computation theory & mathematics, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Meet-in-the-middle attack, Correlation attack, Algorithm, Block cipher
Abstract

International audience; In this paper, we present advanced meet-in-the-middle (MITM) attacks against the lightweight block cipher LED-64, improving the best known attacks on several step-reduced variants of the cipher in both single-key and related-key models. In particular, we present a known-plaintext attack on 2-step LED-64 with complexity of 248 and a related-key attack on 3-step LED-64 with complexity of 249. In both cases, the previously known attacks have complexity of 260, i.e., only 16 times faster than exhaustive key search.While our attacks are applied to the specific scheme of LED-64, they contain several general methodological contributions: First, we present the linear key sieve technique, which allows to exploit linear dependencies between key bits to obtain filtering conditions in MITM attacks on block ciphers. While similar ideas have been previously used in the domain of hash functions, this is the first time that such a technique is applied in block cipher cryptanalysis. As a second contribution, we demonstrate for the first time that a splice-and-cut attack (which so far seemed to be an inherently chosen-plaintext technique) can be used in the known-plaintext model, with data complexity which is significantly below the code-book size. Finally, we extend the differential MITM attack on AES-based designs, and apply it independently in two stages from both sides of the cipher, while using the linear key sieve and other enhancements.

Published
2014
Full Text
View/download PDF

19. Topics in Cryptology - CT-RSA 2012 : The Cryptographers' Track at the RSA Conference 2012, San Francisco, CA, USA, February 27 - March 2, 2012, Proceedings

Author

Orr Dunkelman and Orr Dunkelman

Subjects
Cryptography, Data encryption (Computer science), Computer science—Mathematics, Discrete mathematics, Data protection, Computer networks, Algorithms
Abstract

This book constitutes the refereed proceedings of the Cryptographers'Track at the RSA Conference 2012, CT-RSA 2012, held in San Francisco, CA, USA, in February/March 2012. The 26 revised full papers presented were carefully reviewed and selected from 113 submissions. The papers are organized in topical sections on side channel attacks, digital signatures, public-key encryption, cryptographic protocols, secure implementation methods, symmetric key primitives, and secure multiparty computation.

Published
2012

20. Low-Data Complexity Attacks on AES

Author

Nathan Keller, Vincent Rijmen, Orr Dunkelman, Pierre-Alain Fouque, Charles Bouillaguet, Patrick Derbez, Laboratoire d'informatique de l'école normale supérieure (LIENS), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics [Bar-Ilan], Bar-Ilan University [Israël], Departement of Electrical Engineering-SCD [Leuven] (ESAT-SCD), Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt

Subjects
CBC-MAC, Theoretical computer science, Computer science, Hash function, Cryptography, 02 engineering and technology, Related-key attack, Encryption, 01 natural sciences, law.invention, Cryptanalysis, law, 0202 electrical engineering, electronic engineering, information engineering, Cryptographic hash function, Reflection attacks, Hardware_ARITHMETICANDLOGICSTRUCTURES, Key schedule, Avalanche effect, Cryptographic primitive, Advanced Encryption Standard (AES), Computer Science Applications, Symmetric-key algorithm, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Correlation attack, Block size, Information Systems, Block cipher mode of operation, Triple DES, Differential cryptanalysis, Stream cipher attack, 0102 computer and information sciences, Ciphertext stealing, Data_CODINGANDINFORMATIONTHEORY, Library and Information Sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Malleability, Brute-force attack, Ciphertext, Message authentication code, Stream cipher, Block cipher, business.industry, Advanced Encryption Standard, Plaintext, MDC-2, Adversary, Known-plaintext attack, Substitution-permutation network, business, Slide attacks
Abstract

International audience; 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.

Published
2012
Full Text
View/download PDF

21. A Practical Attack on KeeLoq

Author

Dieter De Moitie, Elke De Mulder, Ingrid Verbauwhede, Nathan Keller, Orr Dunkelman, Sebastiaan Indesteege, Guy A. E. Vandenbosch, Eli Biham, Wim Aerts, and Bart Preneel

Subjects
KeeLoq, Key-recovery attack, Authentication, Computer science, Applied Mathematics, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Computer security, computer.software_genre, 01 natural sciences, cosic, Computer Science Applications, law.invention, 010201 computation theory & mathematics, law, Authentication protocol, 0202 electrical engineering, electronic engineering, information engineering, Key (cryptography), Cryptanalysis, computer, Software, Key size, Block cipher
Abstract

KeeLoq is a lightweight block cipher with a 32-bit block size and a 64-bit key. Despite its short key size, it is used in remote keyless entry systems and other wireless authentication applications. For example, there are indications that authentication protocols based on KeeLoq are used, or were used by various car manufacturers in anti-theft mechanisms. This paper presents a practical key recovery attack against KeeLoq that requires 2 16 known plaintexts and has a time complexity of 2 44.5 KeeLoq encryptions. It is based on the principle of slide attacks and a novel approach to meet-in-the-middle attacks. We investigated the way KeeLoq is intended to be used in practice and conclude that our attack can be used to subvert the security of real systems. In some scenarios the adversary may even reveal the master secret used in an entire class of devices from attacking a single device. Our attack has been fully implemented. We have built a device that can obtain the data required for the attack in less than 100 minutes, and our software experiments show that, given the data, the key can be found in 7.8 days of calculations on 64 CPU cores. © 2010 International Association for Cryptologic Research. ispartof: Journal of Cryptology vol:25 issue:1 pages:136-157 status: published

Published
2012

22. Another Look at Complementation Properties

Author

Gaëtan Leurent, Orr Dunkelman, Charles Bouillaguet, Pierre-Alain Fouque, Laboratoire d'informatique de l'école normale supérieure (LIENS), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL), Faculty of Mathematics and Computer Science, Weizmann Institute of Science [Rehovot, Israël], Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Seokhie Hong and Tetsu Iwata, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
Theoretical computer science, Round function, Hash function, Brute-force search, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Cipher, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, XTEA, Slide attack, Algorithm, Key schedule, Block cipher, Mathematics
Abstract

The original publication is available at www.springerlink.com; International audience; In this paper we present a collection of attacks based on generalisations of the complementation property of DES. We find symmetry relations in the key schedule and in the actual rounds, and we use these symmetries to build distinguishers for any number of rounds when the relation is deterministic. This can be seen as a generalisation of the complementation property of DES or of slide/related-key attacks, using different kinds of relations. We further explore these properties, and show that if the relations have easily found fixed points, a new kind of attacks can be applied. Our main result is a self-similarity property on the Sha-3 candidate Lesamnta, which gives a very surprising result on its compression function. Despite the use of round constants which were designed to thwart any such attack, we show a distinguisher on the full compression function which needs only one query, and works for any number of rounds. We also show how to use this self-similarity property to find collisions on the full compression function of Lesamnta much faster than generic attacks. The main reason for this is the structure found in these round constants, which introduce an interesting and unexpected symmetry relation. This casts some doubt on the use of highly structured constants, as it is the case in many designs, including the AES and several Sha-3 candidates. Our second main contribution is a new related-key differential attack on round-reduced versions of the XTEA block-cipher. We exploit the weakness of the key-schedule to suggest an iterative related-key differential. It can be used to recover the secret key faster than exhaustive search using two related keys on 37 rounds. We then isolate a big class of weak keys for which we can attack 51 rounds out of the cipher's 64 rounds. We also apply our techniques to ESSENCE and PURE.

Published
2010
Full Text
View/download PDF

23. A Practical Attack on KeeLoq

Author

Nathan Keller, Bart Preneel, Sebastiaan Indesteege, Orr Dunkelman, Eli Biham, and Smart, N

Subjects
Key-recovery attack, KeeLoq, Computer science, Computer security, computer.software_genre, cosic, law.invention, law, Key (cryptography), Key derivation function, Slide attack, Cryptanalysis, computer, Key size, Block cipher
Abstract

KeeLoq is a lightweight block cipher with a 32-bit block size and a 64-bit key. Despite its short key size, it is widely used in remote keyless entry systems and other wireless authentication applications. For example, authentication protocols based on KeeLoq are supposedly used by various car manufacturers in anti-theft mechanisms. This paper presents a practical key recovery attack against KeeLoq that requires 2 16 known plaintexts and has a time complexity of 2 44.5 KeeLoq encryptions. It is based on the slide attack and a novel approach to meet-in-the-middle attacks. The fully implemented attack requires 65 minutes to obtain the required data and 7.8 days of calculations on 64 CPU cores. A variant which requires 2 16 chosen plaintexts needs only 3.4 days on 64 CPU cores. Using only 10 000 euro, an attacker can purchase a cluster of 50 dual core computers that will find the secret key in about two days. We investigated the way KeeLoq is intended to be used in practice and conclude that our attack can be used to subvert the security of real systems. An attacker can acquire chosen plaintexts in practice, and one of the two suggested key derivation schemes for KeeLoq allows to recover the master secret from a single key. © 2008 Springer-Verlag Berlin Heidelberg. ispartof: pages:1-18 ispartof: Lecture Notes in Computer Science vol:4965 pages:1-18 ispartof: EUROCRYPT 2008 location:TURKEY, Istanbul date:14 Apr - 17 Apr 2008 status: published

Published
2008

24. A New Attack on the LEX Stream Cipher

Author

Orr Dunkelman, Nathan Keller, and Pieprzyk, J

Subjects
Computer science, Running key cipher, Stream cipher attack, Fluhrer, Mantin and Shamir attack, eSTREAM, Arithmetic, Key whitening, Algorithm, Stream cipher, cosic, Transposition cipher, Block cipher
Abstract

In [6], Biryukov presented a new methodology of stream cipher design, called leak extraction . The stream cipher LEX, based on this methodology and on the AES block cipher, was selected to phase 3 of the eSTREAM competition. The suggested methodology seemed promising, and LEX, due to its elegance, simplicity and performance was expected to be selected to the eSTREAM portfolio. In this paper we present a key recovery attack on LEX. The attack requires about 236.3 bytes of key-stream produced by the same key (possibly under many different IVs), and retrieves the secret key in time of 2112 simple operations. Following a preliminary version of our attack, LEX was discarded from the final portfolio of eSTREAM.

Published
2008

25. A Differential-Linear Attack on 12-Round Serpent

Author

Nathan Keller, Sebastiaan Indesteege, Orr Dunkelman, Chowdhury, DR, Rijmen, V, and Das, A

Subjects
Differential-linear attack, Cipher, Computer science, Serpent (cipher), Linear cryptanalysis, Meet-in-the-middle attack, Slide attack, Computer security, computer.software_genre, Time complexity, computer, cosic, Block cipher
Abstract

Serpent is an SP Network block cipher submitted to the AES competition and chosen as one of its five finalists. The security of Serpent is widely acknowledged, especially as the best known attack so far is a differential-linear attack on only 11 rounds out of the 32 rounds of the cipher. In this paper we introduce a more accurate analysis of the differential-linear attack on 11-round Serpent. The analysis involves both theoretical aspects as well as experimental results which suggest that previous attacks had overestimated complexities. Following our findings we are able to suggest an improved 11-round attack with a lower data complexity. Using the new results, we are able to devise the first known attack on 12-round Serpent.

Published
2008

26. Analysis of two Attacks on Reduced-Round Versions of the SMS4

Author

Deniz Toz, Orr Dunkelman, Chen, L, Ryan, MD, and Wang, G

Subjects
Triple DES, Computer science, Wireless network, Boomerang attack, Slide attack, National standard, Computer security, computer.software_genre, Time complexity, computer, cosic, Block cipher, WLAN Authentication and Privacy Infrastructure
Abstract

SMS4 is a 128-bit block cipher used in WAPI (the Chinese national standard for wireless networks). Up until recently, the best attacks on SMS4 known, in terms of the number of rounds, were the rectangle attack on 14 rounds and the impossible differential attack on 16 rounds (out of 32 rounds) presented by Lu. While analyzing them, we noticed that these attacks have flaws and that their complexity analysis is inaccurate. In this paper we make a more comprehensive analysis of these attacks and further improve these results.

Published
2008

27. Fast Software Encryption : 16th International Workshop, FSE 2009 Leuven, Belgium, February 22-25, 2009 Revised Selected Papers

Author

Orr Dunkelman and Orr Dunkelman

Subjects
Cryptography, Data encryption (Computer science), Computer programming, Data structures (Computer science), Information theory, Coding theory, Algorithms, Computer science—Mathematics
Abstract

FastSoftwareEncryption2009wasthe16thin a seriesofworkshopsonsymm- ric key cryptography. Starting from 2002, it is sponsored by the International Association for Cryptologic Research (IACR). FSE 2009 was held in Leuven, Belgium, after previous venues held in Cambridge, UK (1993, 1996), Leuven, Belgium (1994, 2002), Haifa, Israel (1997), Paris, France (1998, 2005), Rome, Italy (1999), New York, USA (2000), Yokohama, Japan (2001), Lund, Sweden (2003), New Delhi, India (2004), Graz, Austria (2006), Luxembourg, Lux- bourg (2007), and Lausanne, Switzerland (2008). The workshop's main topic is symmetric key cryptography, including the designoffast andsecuresymmetrickeyprimitives,suchas block ciphers,stream ciphers, hash functions, message authentication codes, modes of operation and iteration, as well as the theoretical foundations of these primitives. This year, 76 papers were submitted to FSE including a large portion of papers on hash functions, following the NIST SHA-3 competition, whose wo- shop was held just after FSE in the same location. From the 76 papers, 24 were accepted for presentation. It is my pleasure to thank all the authors of all s- missions for the high-quality research, which is the base for the scienti?c value of the workshop. The review process was thorough (each submission received the attention of at least three reviewers), and at the end, besides the accepted papers, the Committee decided that the merits of the paper “Blockcipher-Based Hashing Revisited” entitled the authors to receive the best paper award. I wish to thank all Committee members and the referees for their hard and dedicated work.

Published
2009

28. Memory-Efficient Algorithms for Finding Needles in Haystacks

Author

Itai Dinur, Nathan Keller, Adi Shamir, and Orr Dunkelman

Subjects
Random graph, Uniform distribution (continuous), 0102 computer and information sciences, 02 engineering and technology, Directed graph, 01 natural sciences, Vertex (geometry), Combinatorics, Piecewise linear function, 010201 computation theory & mathematics, Search algorithm, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Time complexity, Event (probability theory), Mathematics
Abstract

One of the most common tasks in cryptography and cryptanalysis is to find some interesting event a needle in an exponentially large collection haystack of $$N=2^n$$ possible events, or to demonstrate that no such event is likely to exist. In particular, we are interested in finding needles which are defined as events that happen with an unusually high probability of $$p \gg 1/N$$ in a haystack which is an almost uniform distribution on N possible events. When the search algorithm can only sample values from this distribution, the best known time/memory tradeoff for finding such an event requires $$O1/Mp^2$$ time given OM memory. In this paper we develop much faster needle searching algorithms in the common cryptographic setting in which the distribution is defined by applying some deterministic function f to random inputs. Such a distribution can be modelled by a random directed graph with N vertices in which almost all the vertices have O1 predecessors while the vertex we are looking for has an unusually large number of OpN predecessors. When we are given only a constant amount of memory, we propose a new search methodology which we call NestedRho. As p increases, such random graphs undergo several subtle phase transitions, and thus the log-log dependence of the time complexity T on p becomes a piecewise linear curve which bends four times. Our new algorithm is faster than the $$O1/p^2$$ time complexity of the best previous algorithm in the full range of $$1/N

Full Text
View/download PDF

29. On the Joint Security of Encryption and Signature in EMV

Author

Kenneth G. Paterson, Mario Strefler, Nigel P. Smart, Jean Paul Degabriele, Anja Lehmann, Department of Computer Science [Royal Holloway], Royal Holloway [University of London] (RHUL), IBM Research Laboratory [Zurich], IBM Research [Zurich], Department of Computer Science [Bristol], University of Bristol [Bristol], Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Orr Dunkelman, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)

Subjects
Computer science, business.industry, Hash function, 0102 computer and information sciences, 02 engineering and technology, Computer security, computer.software_genre, Encryption, 01 natural sciences, Oracle, Signature (logic), Random oracle, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, business, Joint (audio engineering), computer, Protocol (object-oriented programming)
Abstract

International audience; We provide an analysis of current and future algorithms for signature and encryption in the EMV standards in the case where a single key-pair is used for both signature and encryption. We give a theoretical attack for EMV’s current RSA-based algorithms, showing how access to a partial decryption oracle can be used to forge a signature on a freely chosen message. We show how the attack might be integrated into EMV’s CDA protocol flow, enabling an attacker with a wedge device to complete an offline transaction without knowing the cardholder’s PIN. Finally, the elliptic curve signature and encryption algorithms that are likely to be adopted in a forthcoming version of the EMV standards are analyzed in the single key-pair setting, and shown to be secure.

Published
2012
Full Text
View/download PDF

30. Plaintext-Checkable Encryption

Author

Aline Gouget, Sébastien Canard, Georg Fuchsbauer, Fabien Laguillaumie, Orange Labs [Caen], Orange Labs, Computer Science Department [Bristol], University of Bristol [Bristol], GemAlto Research Labs, GEMALTO (GEMALTO), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Equipe AMACC - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS), Orr Dunkelman, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), and Normandie Université (NU)

Subjects
Plaintext-aware encryption, Computer science, business.industry, Plaintext, 0102 computer and information sciences, 02 engineering and technology, Data_CODINGANDINFORMATIONTHEORY, Encryption, 01 natural sciences, Deterministic encryption, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Symmetric-key algorithm, 010201 computation theory & mathematics, Probabilistic encryption, Ciphertext, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, business, Ciphertext-only attack, Computer network
Abstract

International audience; We study the problem of searching on encrypted data, where the search is performed using a plaintext message or a keyword, rather than a message-specific trapdoor as done by state-of-the-art schemes. The use cases include delegation of key-word search e.g. to a cloud data storage provider or to an email server, using a plaintext message. We define a new cryptographic primitive called plaintext-checkable encryption (PCE), which extends public-key encryption by the following functionality: given a plaintext, a ciphertext and a public key, it is universally possible to check whether the ciphertext encrypts the plaintext under the key. We provide efficient generic random-oracle constructions for PCE based on any probabilistic or deterministic encryption scheme; we also give a practical construction in the standard model. As another application we show how PCE can be used to improve the efficiency in group signatures with verifier-local revocation (VLR) and backward unlinkability. These group signatures provide efficient revocation of group members, which is a key issue in practical applications.

Published
2012
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results