Journal Articles |
|
2. | Lamberger, Mario; Nad, Tomislav; Rijmen, Vincent Numerical Solvers and Cryptanalysis Journal Article Journal of Mathematical Cryptology, 3 (3), pp. 249–263, 2009, ISSN: 1862-2984. @article{DBLP:journals/jmc/LambergerNR09, title = {Numerical Solvers and Cryptanalysis}, author = {Mario Lamberger and Tomislav Nad and Vincent Rijmen}, url = {https://www.tnad.at/wp-content/uploads/2016/04/numericalsolversandcryptanalysis.pdf, PDF}, doi = {10.1515/JMC.2009.015}, issn = {1862-2984}, year = {2009}, date = {2009-09-29}, journal = {Journal of Mathematical Cryptology}, volume = {3}, number = {3}, pages = {249--263}, abstract = {In this paper, we present an approach to apply numerical methods in the cryptanalysis of modern cryptographic algorithms. We focus on the stream cipher Trivium. It is a stream cipher recommended by the eStream project in the hardware category. We use numerical methods to attack a reduced version of Trivium – called Bivium A. We first set up a system of equations describing the internal state of the cipher and convert it into a system over the reals. Four different techniques for the conversion are discussed. At this point we are able to apply numerical methods. We choose the DIRECT algorithm by D. R. Jones et al. and the Interior Reflective Newton Method by Coleman and Li. Results, occurring problems in this approach and possible future research directions are discussed.}, keywords = {}, pubstate = {published}, tppubtype = {article} } In this paper, we present an approach to apply numerical methods in the cryptanalysis of modern cryptographic algorithms. We focus on the stream cipher Trivium. It is a stream cipher recommended by the eStream project in the hardware category. We use numerical methods to attack a reduced version of Trivium – called Bivium A. We first set up a system of equations describing the internal state of the cipher and convert it into a system over the reals. Four different techniques for the conversion are discussed. At this point we are able to apply numerical methods. We choose the DIRECT algorithm by D. R. Jones et al. and the Interior Reflective Newton Method by Coleman and Li. Results, occurring problems in this approach and possible future research directions are discussed. |
Inproceedings |
|
14. | Kölbl, Stefan; Mendel, Florian; Nad, Tomislav; Schläffer, Martin Differential Cryptanalysis of Keccak Variants Inproceedings Stam, Martijn (Ed.): Cryptography and Coding -IMACC 2013, pp. 141–157, Springer, 2013, ISBN: 978-3-642-45238-3. @inproceedings{DBLP:conf/ima/KolblMNS13, title = {Differential Cryptanalysis of Keccak Variants}, author = {Stefan Kölbl and Florian Mendel and Tomislav Nad and Martin Schläffer}, editor = {Martijn Stam}, url = {https://www.tnad.at/wp-content/uploads/2016/04/differential-cryptanalysis-of-keccak-variants.pdf, PDF}, doi = {10.1007/978-3-642-45239-0_9}, isbn = {978-3-642-45238-3}, year = {2013}, date = {2013-12-27}, booktitle = {Cryptography and Coding -IMACC 2013}, volume = {8308}, pages = {141--157}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/ima/2013}, abstract = {In October 2012, NIST has announced Keccak as the winner of the SHA-3 cryptographic hash function competition. Recently, at CT-RSA 2013, NIST brought up the idea to standardize Keccak variants with different parameters than those submitted to the SHA-3 competition. In particular, NIST considers to reduce the capacity to the output size of the SHA-3 standard and additionally, standardize a Keccak variant with a permutation size of 800 instead of 1600 bits. However, these variants have not been analyzed very well during the SHA-3 competition. Especially for the variant using an 800-bit permutation no analysis on the hash function has been published so far. In this work, we analyze these newly proposed Keccak variants and provide practical collisions for up to 4 rounds for all output sizes by constructing internal collisions. Our attacks are based on standard differential cryptanalysis contrary to the recent attacks by Dinur at al. from FSE 2013. We use a non-linear low probability path for the first two rounds and use methods from coding theory to find a high-probability path for the last two rounds. The low probability path as well as the conforming message pair is found using an automatic differential path search tool. Our results indicate that reducing the capacity slightly improves attacks, while reducing the permutation size degrades attacks on Keccak. }, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } In October 2012, NIST has announced Keccak as the winner of the SHA-3 cryptographic hash function competition. Recently, at CT-RSA 2013, NIST brought up the idea to standardize Keccak variants with different parameters than those submitted to the SHA-3 competition. In particular, NIST considers to reduce the capacity to the output size of the SHA-3 standard and additionally, standardize a Keccak variant with a permutation size of 800 instead of 1600 bits. However, these variants have not been analyzed very well during the SHA-3 competition. Especially for the variant using an 800-bit permutation no analysis on the hash function has been published so far. In this work, we analyze these newly proposed Keccak variants and provide practical collisions for up to 4 rounds for all output sizes by constructing internal collisions. Our attacks are based on standard differential cryptanalysis contrary to the recent attacks by Dinur at al. from FSE 2013. We use a non-linear low probability path for the first two rounds and use methods from coding theory to find a high-probability path for the last two rounds. The low probability path as well as the conforming message pair is found using an automatic differential path search tool. Our results indicate that reducing the capacity slightly improves attacks, while reducing the permutation size degrades attacks on Keccak. |
13. | Mendel, Florian; Nad, Tomislav; Schläffer, Martin Improving Local Collisions: New Attacks on Reduced SHA-256 Inproceedings Johansson, Thomas; Nguyen, Phong Q (Ed.): Advances in Cryptology - Eurocrypt 2013, pp. 262–278, Springer, 2013. @inproceedings{DBLP:conf/eurocrypt/MendelNS13, title = {Improving Local Collisions: New Attacks on Reduced SHA-256}, author = {Florian Mendel and Tomislav Nad and Martin Schläffer}, editor = {Thomas Johansson and Phong Q. Nguyen}, url = {https://www.tnad.at/wp-content/uploads/2016/04/improving-local-collisions-new-attacks-on-reduced-sha-256.pdf, PDF}, doi = {10.1007/978-3-642-38348-9_16}, year = {2013}, date = {2013-05-26}, booktitle = {Advances in Cryptology - Eurocrypt 2013}, volume = {7881}, pages = {262--278}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/eurocrypt/2013}, abstract = {In this paper, we focus on the construction of semi-free-start collisions for SHA-256, and show how to turn them into collisions. We present a collision attack on 28 steps of the hash function with practical complexity. Using a two-block approach we are able to turn a semi-freestart collision into a collision for 31 steps with a complexity of at most 2^{65.5}. The main improvement of our work is to extend the size of the local collisions used in these attacks. To construct differential characteristics and confirming message pairs for longer local collisions, we had to improve the search strategy of our automated search tool. To test the limits of our techniques we present a semi-free-start collision for 38 steps.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we focus on the construction of semi-free-start collisions for SHA-256, and show how to turn them into collisions. We present a collision attack on 28 steps of the hash function with practical complexity. Using a two-block approach we are able to turn a semi-freestart collision into a collision for 31 steps with a complexity of at most 2^{65.5}. The main improvement of our work is to extend the size of the local collisions used in these attacks. To construct differential characteristics and confirming message pairs for longer local collisions, we had to improve the search strategy of our automated search tool. To test the limits of our techniques we present a semi-free-start collision for 38 steps. |
12. | Eichlseder, Maria; Mendel, Florian; Nad, Tomislav; Rijmen, Vincent; Schläffer, Martin Linear Propagation in Efficient Guess-and-Determine Attacks Inproceedings Lilya Budaghyan Tor Helleseth, Matthew Parker G (Ed.): International Workshop on Coding and Cryptography, pp. 193 - 202, 2013. @inproceedings{Eichlseder2013, title = {Linear Propagation in Efficient Guess-and-Determine Attacks}, author = {Maria Eichlseder and Florian Mendel and Tomislav Nad and Vincent Rijmen and Martin Schläffer}, editor = {Lilya Budaghyan, Tor Helleseth, Matthew G. Parker}, url = {https://www.tnad.at/wp-content/uploads/2016/04/linear-propagation-in-efficient-guess-and-determine-attacks.pdf, PDF}, year = {2013}, date = {2013-04-15}, booktitle = {International Workshop on Coding and Cryptography}, pages = {193 - 202}, abstract = {t The most successful attacks on cryptographic hash functions are based on differential cryptanalysis, where the main problem is to find a differential characteristic. Finding a differential characteristic is equivalent to solving a system of nonlinear equations. Solving these equations is usually done by a guess-anddetermine approach. Recently, automated tools performing a guess-and-determine approach based on the concept of generalized conditions have been used to attack many hash functions. The core part of such tools is the propagation of information. In this paper, we propose a new approach to propagate information for affine functions and compare it to the approach used in recent hash function attacks. We apply our method to the linear functions σi and Σi used in SHA-2 and to the linear layer of SHA-3. We show that our approach performs much better than the previously used methods.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } t The most successful attacks on cryptographic hash functions are based on differential cryptanalysis, where the main problem is to find a differential characteristic. Finding a differential characteristic is equivalent to solving a system of nonlinear equations. Solving these equations is usually done by a guess-anddetermine approach. Recently, automated tools performing a guess-and-determine approach based on the concept of generalized conditions have been used to attack many hash functions. The core part of such tools is the propagation of information. In this paper, we propose a new approach to propagate information for affine functions and compare it to the approach used in recent hash function attacks. We apply our method to the linear functions σi and Σi used in SHA-2 and to the linear layer of SHA-3. We show that our approach performs much better than the previously used methods. |
11. | Mendel, Florian; Nad, Tomislav; Schläffer, Martin Finding Collisions for Round-Reduced SM3 Inproceedings Dawson, Ed (Ed.): Topics in Cryptology - CT-RSA 2013, pp. 174–188, Springer, 2013. @inproceedings{DBLP:conf/ctrsa/MendelNS13, title = {Finding Collisions for Round-Reduced SM3}, author = {Florian Mendel and Tomislav Nad and Martin Schläffer}, editor = {Ed Dawson}, url = {https://www.tnad.at/wp-content/uploads/2016/04/finding-collisions-for-round-reduced-sm3.pdf, PDF}, doi = {10.1007/978-3-642-36095-4_12}, year = {2013}, date = {2013-02-25}, booktitle = {Topics in Cryptology - CT-RSA 2013}, volume = {7779}, pages = {174--188}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/ctrsa/2013}, abstract = {t. In this work, we provide the first security analysis of reduced SM3 regarding its collision resistance. SM3 is a Chinese hash function standard published by the Chinese Commercial Cryptography Administration Office for the use of electronic authentication service systems and hence, might be used in several cryptographic applications in China. Sofar only few results have been published for the SM3 hash function. Since the design of SM3 is very similar to the MD4 family of hash functions and in particular to SHA-2, a revaluation of the security of SM3 regarding collision resistance is important taking into account recent advances in the cryptanalysis of SHA-2. In this paper, we extend the methods used in the recent collision attacks on SHA-2 and show how the techniques can be effectively applied to SM3. Our results are a collision attack on the hash function for 20 out of 64 steps and a free-start collision attack for 24 steps of SM3, both with practical complexity.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } t. In this work, we provide the first security analysis of reduced SM3 regarding its collision resistance. SM3 is a Chinese hash function standard published by the Chinese Commercial Cryptography Administration Office for the use of electronic authentication service systems and hence, might be used in several cryptographic applications in China. Sofar only few results have been published for the SM3 hash function. Since the design of SM3 is very similar to the MD4 family of hash functions and in particular to SHA-2, a revaluation of the security of SM3 regarding collision resistance is important taking into account recent advances in the cryptanalysis of SHA-2. In this paper, we extend the methods used in the recent collision attacks on SHA-2 and show how the techniques can be effectively applied to SM3. Our results are a collision attack on the hash function for 20 out of 64 steps and a free-start collision attack for 24 steps of SM3, both with practical complexity. |
10. | Mendel, Florian; Nad, Tomislav; Scherz, Stefan; Schläffer, Martin Differential Attacks on Reduced RIPEMD-160 Inproceedings Gollmann, Dieter; Freiling, Felix C (Ed.): Information Security, ISC 2012, pp. 23–38, Springer, 2012, ISBN: 978-3-642-33382-8. @inproceedings{DBLP:conf/isw/MendelNSS12, title = {Differential Attacks on Reduced RIPEMD-160}, author = {Florian Mendel and Tomislav Nad and Stefan Scherz and Martin Schläffer}, editor = {Dieter Gollmann and Felix C. Freiling}, url = {https://www.tnad.at/wp-content/uploads/2016/04/differential-attacks-on-reduced-ripemd-160.pdf, PDF}, doi = {10.1007/978-3-642-33383-5_2}, isbn = {978-3-642-33382-8}, year = {2012}, date = {2012-09-12}, booktitle = {Information Security, ISC 2012}, volume = {7483}, pages = {23--38}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/isw/2012}, abstract = {In this work, we provide the first security analysis of reduced RIPEMD-160 regarding its collision resistance with practical complexity. The ISO/IEC standard RIPEMD-160 was proposed 15 years ago and may be used as a drop-in replacement for SHA-1 due to their same hash output length. Only few results have been published for RIPEMD-160 so far and most attacks have a complexity very close to the generic bound. In this paper, we present the first application of the attacks of Wang et al. on MD5 and SHA-1 to RIPEMD-160. Due to the dual-stream structure of RIPEMD-160 the application of these attacks is nontrivial and almost impossible without the use of automated tools. We present practical examples of semi-free-start near-collisions for the middle 48 steps (out of 80) and semi-free-start collisions for 36 steps of RIPEMD-160. Furthermore, our results show that the differential characteristics get very dense in RIPEMD-160 such that a full-round attack seems unlikely in the near future. }, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } In this work, we provide the first security analysis of reduced RIPEMD-160 regarding its collision resistance with practical complexity. The ISO/IEC standard RIPEMD-160 was proposed 15 years ago and may be used as a drop-in replacement for SHA-1 due to their same hash output length. Only few results have been published for RIPEMD-160 so far and most attacks have a complexity very close to the generic bound. In this paper, we present the first application of the attacks of Wang et al. on MD5 and SHA-1 to RIPEMD-160. Due to the dual-stream structure of RIPEMD-160 the application of these attacks is nontrivial and almost impossible without the use of automated tools. We present practical examples of semi-free-start near-collisions for the middle 48 steps (out of 80) and semi-free-start collisions for 36 steps of RIPEMD-160. Furthermore, our results show that the differential characteristics get very dense in RIPEMD-160 such that a full-round attack seems unlikely in the near future. |
9. | Mendel, Florian; Nad, Tomislav; Schläffer, Martin Collision Attacks on the Reduced Dual-Stream Hash Function RIPEMD-128 Inproceedings Canteaut, Anne (Ed.): Fast Software Encryption, FSE 2012, pp. 226–243, Springer, 2012, ISBN: 978-3-642-34046-8. @inproceedings{DBLP:conf/fse/MendelNS12, title = {Collision Attacks on the Reduced Dual-Stream Hash Function RIPEMD-128}, author = {Florian Mendel and Tomislav Nad and Martin Schläffer}, editor = {Anne Canteaut}, url = {https://www.tnad.at/wp-content/uploads/2016/04/collision-attacks-on-the-reduced-dual-stream-hash-function-ripemd-128.pdf, PDF}, doi = {10.1007/978-3-642-34047-5_14}, isbn = {978-3-642-34046-8}, year = {2012}, date = {2012-09-11}, booktitle = {Fast Software Encryption, FSE 2012}, volume = {7549}, pages = {226--243}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/fse/2012}, abstract = {In this paper, we analyze the security of RIPEMD-128 against collision attacks. The ISO/IEC standard RIPEMD-128 was proposed 15 years ago and may be used as a drop-in replacement for 128-bit hash functions like MD5. Only few results have been published for RIPEMD-128, the best being a preimage attack for the first 33 steps of the hash function with complexity 2^{124.5}. In this work, we provide a new assessment of the security margin of RIPEMD-128 by showing attacks on up to 48 (out of 64) steps of the hash function. We present a collision attack reduced to 38 steps and a near-collisions attack for 44 steps, both with practical complexity. Furthermore, we show non-random properties for 48 steps of the RIPEMD-128 hash function, and provide an example for a collision on the compression function for 48 steps. For all attacks we use complex nonlinear differential characteristics. Due to the more complicated dual-stream structure of RIPEMD-128 compared to its predecessor, finding high-probability characteristics as well as conforming message pairs is nontrivial. Doing any of these steps by hand is almost impossible or at least, very time consuming. We present a general strategy to analyze dual-stream hash functions and use an automatic search tool for the two main steps of the attack. Our tool is able to find differential characteristics and perform advanced message modification simultaneously in the two streams. }, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we analyze the security of RIPEMD-128 against collision attacks. The ISO/IEC standard RIPEMD-128 was proposed 15 years ago and may be used as a drop-in replacement for 128-bit hash functions like MD5. Only few results have been published for RIPEMD-128, the best being a preimage attack for the first 33 steps of the hash function with complexity 2^{124.5}. In this work, we provide a new assessment of the security margin of RIPEMD-128 by showing attacks on up to 48 (out of 64) steps of the hash function. We present a collision attack reduced to 38 steps and a near-collisions attack for 44 steps, both with practical complexity. Furthermore, we show non-random properties for 48 steps of the RIPEMD-128 hash function, and provide an example for a collision on the compression function for 48 steps. For all attacks we use complex nonlinear differential characteristics. Due to the more complicated dual-stream structure of RIPEMD-128 compared to its predecessor, finding high-probability characteristics as well as conforming message pairs is nontrivial. Doing any of these steps by hand is almost impossible or at least, very time consuming. We present a general strategy to analyze dual-stream hash functions and use an automatic search tool for the two main steps of the attack. Our tool is able to find differential characteristics and perform advanced message modification simultaneously in the two streams. |
8. | Eisenbarth, Thomas; Gong, Zheng; Güneysu, Tim; Heyse, Stefan; Indesteege, Sebastiaan; Kerckhof, Stéphanie; Koeune, François; Nad, Tomislav; Plos, Thomas; Regazzoni, Francesco; Standaert, François-Xavier; van tot Oldenzeel, Loïc Oldeneel Compact Implementation and Performance Evaluation of Block Ciphers in ATtiny Devices Inproceedings Mitrokotsa, Aikaterini; Vaudenay, Serge (Ed.): Progress in Cryptology - Africacrypt 2012, pp. 172–187, Springer, 2012, ISBN: 978-3-642-31409-4. @inproceedings{DBLP:conf/africacrypt/EisenbarthGGHIKKNPRSO12, title = {Compact Implementation and Performance Evaluation of Block Ciphers in ATtiny Devices}, author = {Thomas Eisenbarth and Zheng Gong and Tim Güneysu and Stefan Heyse and Sebastiaan Indesteege and Stéphanie Kerckhof and François Koeune and Tomislav Nad and Thomas Plos and Francesco Regazzoni and François-Xavier Standaert and Loïc van Oldeneel tot Oldenzeel}, editor = {Aikaterini Mitrokotsa and Serge Vaudenay}, url = {https://www.tnad.at/wp-content/uploads/2016/04/compact-implementation-and-performance-evaluation-of-block-ciphers-in-attiny-devices.pdf, PDF}, doi = {10.1007/978-3-642-31410-0_11}, isbn = {978-3-642-31409-4}, year = {2012}, date = {2012-06-12}, booktitle = {Progress in Cryptology - Africacrypt 2012}, volume = {7374}, pages = {172--187}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/africacrypt/2012}, abstract = {The design of lightweight block ciphers has been a very active research topic over the last years. However, the lack of comparative source codes generally makes it hard to evaluate the extent to which different ciphers actually reach their low-cost goals, on different platforms. This paper reports on an initiative aimed to partially relax this issue. First, we implemented 12 block ciphers on an ATMEL ATtiny45 device, and made the corresponding source code available on a webpage, with an open-source license. Common design goals and interface have been sent to all designers in order to enhance the comparability of the implementation results. Second, we evaluated the performances of these implementations according to different metrics, including energy-consumption measurements. Although inherently limited by slightly different design choices, we hope this initiative can trigger more work in this direction, e.g. by extending the list of implemented ciphers, or adding countermeasures against physical attacks in the future.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } The design of lightweight block ciphers has been a very active research topic over the last years. However, the lack of comparative source codes generally makes it hard to evaluate the extent to which different ciphers actually reach their low-cost goals, on different platforms. This paper reports on an initiative aimed to partially relax this issue. First, we implemented 12 block ciphers on an ATMEL ATtiny45 device, and made the corresponding source code available on a webpage, with an open-source license. Common design goals and interface have been sent to all designers in order to enhance the comparability of the implementation results. Second, we evaluated the performances of these implementations according to different metrics, including energy-consumption measurements. Although inherently limited by slightly different design choices, we hope this initiative can trigger more work in this direction, e.g. by extending the list of implemented ciphers, or adding countermeasures against physical attacks in the future. |
7. | Mendel, Florian; Nad, Tomislav Boomerang Distinguisher for the SIMD-512 Compression Function Inproceedings Bernstein, Daniel J; Chatterjee, Sanjit (Ed.): Progress in Cryptology - Indocrypt 2011, pp. 255–269, Springer, 2011, ISBN: 978-3-642-25577-9. @inproceedings{DBLP:conf/indocrypt/MendelN11b, title = {Boomerang Distinguisher for the SIMD-512 Compression Function}, author = {Florian Mendel and Tomislav Nad}, editor = {Daniel J. Bernstein and Sanjit Chatterjee}, url = {https://www.tnad.at/wp-content/uploads/2016/04/boomerang-distinguisher-for-the-simd-512-compression-function.pdf, PDF}, doi = {10.1007/978-3-642-25578-6_19}, isbn = {978-3-642-25577-9}, year = {2011}, date = {2011-12-06}, booktitle = {Progress in Cryptology - Indocrypt 2011}, volume = {7107}, pages = {255--269}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/indocrypt/2011}, abstract = {In this paper, we present a distinguisher for the permutation of SIMD-512 with complexity 2^{226.52}. We extend the attack to a distinguisher for the compression function with complexity 2^{200.6}. The attack is based on the application of the boomerang attack for hash functions. Starting from the middle of the compression function we use techniques from coding theory to search for two differential characteristics, one for the backward direction and one for the forward direction to construct a second-order differential. Both characteristics hold with high probability. The direct application of the second-order differential leads to a distinguisher for the permutation. Based on this differential we extend the attack to distinguisher for the compression function.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we present a distinguisher for the permutation of SIMD-512 with complexity 2^{226.52}. We extend the attack to a distinguisher for the compression function with complexity 2^{200.6}. The attack is based on the application of the boomerang attack for hash functions. Starting from the middle of the compression function we use techniques from coding theory to search for two differential characteristics, one for the backward direction and one for the forward direction to construct a second-order differential. Both characteristics hold with high probability. The direct application of the second-order differential leads to a distinguisher for the permutation. Based on this differential we extend the attack to distinguisher for the compression function. |
6. | Mendel, Florian; Nad, Tomislav; Schläffer, Martin Finding SHA-2 Characteristics: Searching through a Minefield of Contradictions Inproceedings Lee, Dong Hoon; Wang, Xiaoyun (Ed.): Advances in Cryptology - Asiacrypt 2011, pp. 288–307, Springer, 2011, ISBN: 978-3-642-25384-3. @inproceedings{DBLP:conf/asiacrypt/MendelNS11, title = {Finding SHA-2 Characteristics: Searching through a Minefield of Contradictions}, author = {Florian Mendel and Tomislav Nad and Martin Schläffer}, editor = {Dong Hoon Lee and Xiaoyun Wang}, url = {https://www.tnad.at/wp-content/uploads/2016/04/finding-sha-2-characteristics-searching-through-a-minefield-of-contradictions.pdf, PDF}, doi = {10.1007/978-3-642-25385-0_16}, isbn = {978-3-642-25384-3}, year = {2011}, date = {2011-12-01}, booktitle = {Advances in Cryptology - Asiacrypt 2011}, volume = {7073}, pages = {288--307}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/asiacrypt/2011}, abstract = {In this paper, we analyze the collision resistance of SHA-2 and provide the first results since the beginning of the NIST SHA-3 competition. We extend the previously best known semi-free-start collisions on SHA-256 from 24 to 32 (out of 64) steps and show a collision attack for 27 steps. All our attacks are practical and verified by colliding message pairs. We present the first automated tool for finding complex differential characteristics in SHA-2 and show that the techniques on SHA-1 cannot directly be applied to SHA-2. Due to the more complex structure of SHA-2 several new problems arise. Most importantly, a large amount of contradicting conditions occur which render most differential characteristics impossible. We show how to overcome these difficulties by including the search for conforming message pairs in the search for differential characteristics.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we analyze the collision resistance of SHA-2 and provide the first results since the beginning of the NIST SHA-3 competition. We extend the previously best known semi-free-start collisions on SHA-256 from 24 to 32 (out of 64) steps and show a collision attack for 27 steps. All our attacks are practical and verified by colliding message pairs. We present the first automated tool for finding complex differential characteristics in SHA-2 and show that the techniques on SHA-1 cannot directly be applied to SHA-2. Due to the more complex structure of SHA-2 several new problems arise. Most importantly, a large amount of contradicting conditions occur which render most differential characteristics impossible. We show how to overcome these difficulties by including the search for conforming message pairs in the search for differential characteristics. |
5. | Mendel, Florian; Nad, Tomislav; Schläffer, Martin Cryptanalysis of Round-Reduced HAS-160 Inproceedings Kim, Howon (Ed.): Information Security and Cryptology - ICISC 2011, pp. 33–47, Springer, 2011, ISBN: 978-3-642-31911-2. @inproceedings{DBLP:conf/icisc/MendelNS11, title = {Cryptanalysis of Round-Reduced HAS-160}, author = {Florian Mendel and Tomislav Nad and Martin Schläffer}, editor = {Howon Kim}, url = {https://www.tnad.at/wp-content/uploads/2016/04/cryptanalysis-of-round-reduced-has-160.pdf, PDF}, doi = {10.1007/978-3-642-31912-9_3}, isbn = {978-3-642-31911-2}, year = {2011}, date = {2011-11-30}, booktitle = {Information Security and Cryptology - ICISC 2011}, volume = {7259}, pages = {33--47}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/icisc/2011}, abstract = {HAS-160 is an iterated cryptographic hash function that is standardized by the Korean government and widely used in Korea. In this paper, we present a semi-free-start collision for 65 (out of 80) steps of HAS-160 with practical complexity. The basic attack strategy is to construct a long differential characteristic by connecting two short ones by a complex third characteristic. The short characteristics are constructed using techniques from coding theory. To connect them, we are using an automatic search algorithm for the connecting characteristic utilizing the nonlinearity of the step function. }, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } HAS-160 is an iterated cryptographic hash function that is standardized by the Korean government and widely used in Korea. In this paper, we present a semi-free-start collision for 65 (out of 80) steps of HAS-160 with practical complexity. The basic attack strategy is to construct a long differential characteristic by connecting two short ones by a complex third characteristic. The short characteristics are constructed using techniques from coding theory. To connect them, we are using an automatic search algorithm for the connecting characteristic utilizing the nonlinearity of the step function. |
3. | Mendel, Florian; Nad, Tomislav A Distinguisher for the Compression Function of SIMD-512 Inproceedings Roy, Bimal K; Sendrier, Nicolas (Ed.): Progress in Cryptology - Indocrypt 2009, pp. 219–232, Springer, 2009, ISBN: 978-3-642-10627-9. @inproceedings{DBLP:conf/indocrypt/MendelN09, title = {A Distinguisher for the Compression Function of SIMD-512}, author = {Florian Mendel and Tomislav Nad}, editor = {Bimal K. Roy and Nicolas Sendrier}, url = {https://www.tnad.at/wp-content/uploads/2016/04/a-distinguisher-for-the-compression-function-of-simd-512.pdf, PDF}, doi = {10.1007/978-3-642-10628-6_15}, isbn = {978-3-642-10627-9}, year = {2009}, date = {2009-12-11}, booktitle = {Progress in Cryptology - Indocrypt 2009}, volume = {5922}, pages = {219--232}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/indocrypt/2009}, abstract = {SIMD is one of the round 2 candidates of the public SHA-3 competition hosted by NIST. It was designed by Leurent et al.. In this paper, we present a distinguisher attack on the compression function of SIMD-512. By linearizing the compression function we construct a linear code. Using techniques from coding theory to search for low Hamming weight codewords, we can find differential characteristics with low Hamming weight (and hence high probability). In the attack the differences are introduced only in the IV. Such a characteristic is the base for our distinguisher, which can distinguish the compression function of SIMD-512 from random with a complexity of 5·2^{425.28} compression function calls. Furthermore, we can distinguish the output transformation of SIMD-512 from random with a complexity of about 22·2^{425.28} compression function calls. So far this is the first cryptanalytic result for the SIMD hash function.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } SIMD is one of the round 2 candidates of the public SHA-3 competition hosted by NIST. It was designed by Leurent et al.. In this paper, we present a distinguisher attack on the compression function of SIMD-512. By linearizing the compression function we construct a linear code. Using techniques from coding theory to search for low Hamming weight codewords, we can find differential characteristics with low Hamming weight (and hence high probability). In the attack the differences are introduced only in the IV. Such a characteristic is the base for our distinguisher, which can distinguish the compression function of SIMD-512 from random with a complexity of 5·2^{425.28} compression function calls. Furthermore, we can distinguish the output transformation of SIMD-512 from random with a complexity of about 22·2^{425.28} compression function calls. So far this is the first cryptanalytic result for the SIMD hash function. |
1. | Mendel, Florian; Nad, Tomislav; Schläffer, Martin Collision Attack on Boole Inproceedings Abdalla, Michel; Pointcheval, David; Fouque, Pierre-Alain; Vergnaud, Damien (Ed.): Applied Cryptography and Network Security, ACNS 2009, pp. 369–381, Springer, 2009, ISBN: 978-3-642-01956-2. @inproceedings{DBLP:conf/acns/MendelNS09, title = {Collision Attack on Boole}, author = {Florian Mendel and Tomislav Nad and Martin Schläffer}, editor = {Michel Abdalla and David Pointcheval and Pierre-Alain Fouque and Damien Vergnaud}, url = {https://www.tnad.at/wp-content/uploads/2016/04/collision_attack_on_boole.pdf, PDF}, doi = {10.1007/978-3-642-01957-9_23}, isbn = {978-3-642-01956-2}, year = {2009}, date = {2009-05-20}, booktitle = {Applied Cryptography and Network Security, ACNS 2009}, volume = {5536}, pages = {369--381}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, crossref = {DBLP:conf/acns/2009}, abstract = {Boole is a hash function designed by Gregory Rose and was submitted to the NIST Hash competition. It is a stream cipher based hash function which produces digests up to 512 bits. Different variants exist, namely Boole16, Boole32 and Boole64 where the number refers to word size in bits. Boole64 is considered as the official submission. In this paper we demonstrate a collision attack with complexity 2^{65} for the 64-bit variant and 2^{33} for the 32-bit variant. The amount of memory required is negligible. Since the attack on Boole32 is practical, we present an example for a collision.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Boole is a hash function designed by Gregory Rose and was submitted to the NIST Hash competition. It is a stream cipher based hash function which produces digests up to 512 bits. Different variants exist, namely Boole16, Boole32 and Boole64 where the number refers to word size in bits. Boole64 is considered as the official submission. In this paper we demonstrate a collision attack with complexity 2^{65} for the 64-bit variant and 2^{33} for the 32-bit variant. The amount of memory required is negligible. Since the attack on Boole32 is practical, we present an example for a collision. |
Miscellaneous |
|
16. | Georgiev, Martin; Shmatikov, Vitaly Gone in Six Characters: Short URLs Considered Harmful for Cloud Services Miscellaneous http://www.cs.cornell.edu/~shmat/shmat_urls.pdf, 2016. BibTeX | Links: @misc{miscGeorgievS0416, title = {Gone in Six Characters: Short URLs Considered Harmful for Cloud Services}, author = {Martin Georgiev and Vitaly Shmatikov}, url = {http://www.cs.cornell.edu/~shmat/shmat_urls.pdf, PDF}, year = {2016}, date = {2016-04-18}, howpublished = {http://www.cs.cornell.edu/~shmat/shmat_urls.pdf}, keywords = {}, pubstate = {published}, tppubtype = {misc} } |
Presentations |
|
15. | Nad, Tomislav Bitcoin – Cryptographic Principles and the Collapse of Mt. Gox Presentation CSACH Switzerland, , 11.04.2014. @misc{csachBitcoin, title = {Bitcoin – Cryptographic Principles and the Collapse of Mt. Gox}, author = {Tomislav Nad}, editor = {CSACH Switzerland}, year = {2014}, date = {2014-04-11}, booktitle = {CSACH Switzerland}, howpublished = {CSACH Switzerland}, keywords = {}, pubstate = {published}, tppubtype = {presentation} } |
4. | Nad, Tomislav The CodingTool Library Presentation Workshop on Tools for Cryptanalysis, , 22.06.2010. BibTeX | Links: @misc{Nad2010CodingToolLibrary, title = {The CodingTool Library}, author = {Tomislav Nad}, editor = {Workshop on Tools for Cryptanalysis}, url = {https://www.tnad.at/wp-content/uploads/2016/04/the-codingtool-library.pdf, PDF}, year = {2010}, date = {2010-06-22}, booktitle = {Workshop on Tools for Cryptanalysis}, howpublished = {Workshop on Tools for Cryptanalysis}, keywords = {}, pubstate = {published}, tppubtype = {presentation} } |
Publications
Journal Articles |
|
2. | Numerical Solvers and Cryptanalysis Journal Article Journal of Mathematical Cryptology, 3 (3), pp. 249–263, 2009, ISSN: 1862-2984. |
Inproceedings |
|
14. | Differential Cryptanalysis of Keccak Variants Inproceedings Stam, Martijn (Ed.): Cryptography and Coding -IMACC 2013, pp. 141–157, Springer, 2013, ISBN: 978-3-642-45238-3. |
13. | Improving Local Collisions: New Attacks on Reduced SHA-256 Inproceedings Johansson, Thomas; Nguyen, Phong Q (Ed.): Advances in Cryptology - Eurocrypt 2013, pp. 262–278, Springer, 2013. |
12. | Linear Propagation in Efficient Guess-and-Determine Attacks Inproceedings Lilya Budaghyan Tor Helleseth, Matthew Parker G (Ed.): International Workshop on Coding and Cryptography, pp. 193 - 202, 2013. |
11. | Finding Collisions for Round-Reduced SM3 Inproceedings Dawson, Ed (Ed.): Topics in Cryptology - CT-RSA 2013, pp. 174–188, Springer, 2013. |
10. | Differential Attacks on Reduced RIPEMD-160 Inproceedings Gollmann, Dieter; Freiling, Felix C (Ed.): Information Security, ISC 2012, pp. 23–38, Springer, 2012, ISBN: 978-3-642-33382-8. |
9. | Collision Attacks on the Reduced Dual-Stream Hash Function RIPEMD-128 Inproceedings Canteaut, Anne (Ed.): Fast Software Encryption, FSE 2012, pp. 226–243, Springer, 2012, ISBN: 978-3-642-34046-8. |
8. | Compact Implementation and Performance Evaluation of Block Ciphers in ATtiny Devices Inproceedings Mitrokotsa, Aikaterini; Vaudenay, Serge (Ed.): Progress in Cryptology - Africacrypt 2012, pp. 172–187, Springer, 2012, ISBN: 978-3-642-31409-4. |
7. | Boomerang Distinguisher for the SIMD-512 Compression Function Inproceedings Bernstein, Daniel J; Chatterjee, Sanjit (Ed.): Progress in Cryptology - Indocrypt 2011, pp. 255–269, Springer, 2011, ISBN: 978-3-642-25577-9. |
6. | Finding SHA-2 Characteristics: Searching through a Minefield of Contradictions Inproceedings Lee, Dong Hoon; Wang, Xiaoyun (Ed.): Advances in Cryptology - Asiacrypt 2011, pp. 288–307, Springer, 2011, ISBN: 978-3-642-25384-3. |
5. | Cryptanalysis of Round-Reduced HAS-160 Inproceedings Kim, Howon (Ed.): Information Security and Cryptology - ICISC 2011, pp. 33–47, Springer, 2011, ISBN: 978-3-642-31911-2. |
3. | A Distinguisher for the Compression Function of SIMD-512 Inproceedings Roy, Bimal K; Sendrier, Nicolas (Ed.): Progress in Cryptology - Indocrypt 2009, pp. 219–232, Springer, 2009, ISBN: 978-3-642-10627-9. |
1. | Collision Attack on Boole Inproceedings Abdalla, Michel; Pointcheval, David; Fouque, Pierre-Alain; Vergnaud, Damien (Ed.): Applied Cryptography and Network Security, ACNS 2009, pp. 369–381, Springer, 2009, ISBN: 978-3-642-01956-2. |
Miscellaneous |
|
16. | Gone in Six Characters: Short URLs Considered Harmful for Cloud Services Miscellaneous http://www.cs.cornell.edu/~shmat/shmat_urls.pdf, 2016. |
Presentations |
|
15. | Bitcoin – Cryptographic Principles and the Collapse of Mt. Gox Presentation CSACH Switzerland, , 11.04.2014. |
4. | The CodingTool Library Presentation Workshop on Tools for Cryptanalysis, , 22.06.2010. |