Lars Ramkild Knudsen ( February 21, 1962 ) is a Danish mathematician and cryptography researcher , professor at the Department of Mathematics at the Danish Technical University . His research includes the development and analysis of block ciphers , hash functions, and message authenticity codes ( MACs ).
| Lars Ramkild Knudsen | |
|---|---|
 | |
| Date of Birth | February 21, 1962 (57 years old) |
| A country | |
| Scientific field | mathematics , cryptography , information theory |
| Place of work | Danish Technical University |
| Alma mater | Aarhus University |
| supervisor | |
| Known as | author of many crypto attacks, developer of SAFER and SQUARE ciphers, one of the founders of integral cryptanalysis and cryptanalysis of impossible differentials |
| Awards and prizes | [d] ( 2013 ) |
| Site | |
Knudsen is one of the founders of and integral cryptanalysis . Lars is one of the developers of Grøstl .
Content
Biography
Lars Knudsen was born on February 21, 1962 in Denmark . His career began with several early banking jobs. However, in 1984, Lars entered the Danish University of Aarhus ( Eng. Aarhus University ). He studied mathematics and computer science, on the advice of his scientific adviser Ivan Bjerre Damgard (born Ivan Bjerre Damgard). According to Lars, it was thanks to his supervisor that he made a choice in favor of studying differential cryptanalysis.
In 1992 he received a master's degree, and already in 1994 - a Ph.D. [1] From 1997 to 2001, he worked at the University of Bergen , Norway . He was twice elected Director of the International Association of Cryptographic Research ( IACR ) from January 2001 to December 2003 and from January 2004 to December 2006 . From 2003 to 2010, he was Assistant Editor of the Journal of Cryptology, which is the official journal of IACR. He spoke at IACR conferences and seminars. His reports are present at 7 scientific conferences. Knudsen is currently a professor, head of the department of mathematics at the Technical University of Denmark . He heads the group of cryptanalysts at the University and is one of the developers of ciphers, IEEE cryptographic protocols for forensics and security. One of the leaders of the FICS research center (Foundations in Cryptology and Security).
Lars Knudsen took an active part in the competition for the new crypto standard AES . On it, he was the only cryptanalyst who represented at once two projects: DEAL (Norway, Canada) and Serpent (Great Britain, Israel, Norway). The incident with the fact that Knudsen is always featured as a representative of Norway is explained by the extreme mobility of the Danish scientist who has already managed to work in France , Switzerland and Belgium over the past few years. At the time of the AES competition, Lars taught cryptology at the University of Bergen , Norway.
It is also known that its Erdös number is 3.
Research
Throughout the world, Lars Knudsen is known for the famous attacks on the SAFER and SQUARE ciphers, his work on the cryptanalysis of impossible differentials and integral cryptanalysis. Knudsen first proposed using truncated differentials to attack the 6-round DES . Later this method was also used for attacks on Skipjack and SAFER with a truncated number of rounds. Lars also developed the DEAL and Serpent ciphers (the latter together with the Englishman Ross Anderson and the Israeli Eli Biham ). Another Knudsen development is Grøstl , a hash function , one of the five finalists of the NIST SHA-3 contest.
Integral Cryptanalysis
Integral cryptanalysis is a type of cryptanalysis partially applicable for attacks on block ciphers based on permutation-permutation networks . It was formulated by Lars Knudsen in the search for an attack on the SQUARE cipher, so in the literature it is often called the Square attack. The method has been extended and applied to Square-like ciphers CRYPTON , Rijndael , and SHARK . Square attack modifications have also been applied to the Hierocrypt-L1 , IDEA , Camellia , Skipjack , MISTY1 , MISTY2 , SAFER ++, KHAZAD and FOX ciphers (now called ).
Integral cryptanalysis is based on the principle of considering a set of plaintexts, in which one part remains constant, and the second varies in all possible ways. For example, an attack may use a set of 256 plaintexts in which everything except 8 bits varies. Obviously, the XOR of this set is zero. XOR of the corresponding set of ciphertexts gives us information about the operation of the encryption algorithm. This method of using a large set of plaintexts instead of a pair, as in differential cryptanalysis , gave the name "integral".
Cryptanalysis of impossible differentials
Cryptanalysis of impossible differentials is a type of differential cryptanalysis applied to block ciphers . In ordinary differential cryptanalysis, a difference with a certain finite probability is considered, in cryptanalysis of impossible differentials, a difference with a probability of 0, that is, “impossible”, is considered.
This technique was first described by Lars Knudsen in an application for the AES contest using the DEAL cipher. The name of the technique was given by Eli Biham , Alex Biryukov and Adi Shamir at the CRYPTO'98 conference.
This method has been widely used and was used in attacks on IDEA , Khufu and Khafre , E2 ciphers, Serpent , MARS , Twofish , Rijndael , CRYPTON , varieties, Hierocrypt-3 , TEA , XTEA , Mini-AES , ARIA , Camellia , and SHACAL-2 .
SAFER Cipher Attack
SAFER K-64 is an iteratively block cipher. The algorithm works with a 64-bit block and a 64-bit key. Knudsen found a weak point in the distribution of keys. Their generation in the algorithm was not at all difficult. The first subkey is the user key itself. The following subkeys are generated by the procedure . Operation <<< - a cyclic left shift of 3 bits inside each key byte .
Constant obtained from the formula where j is the constant byte number . The weakness of this algorithm was that for almost every key there is at least one (sometimes even 9) other key that, when encrypting some other message, gives us the same encrypted text, i.e. . Knudsen found that the number of different plaintexts that are encrypted with identical ciphertexts is approximately - of possible texts. As a result, using analysis from before plaintext you can find 8 bits of the original key, consisting of 64 bits. Then this algorithm was improved by Knudsen himself to SAFER SK-64.
There is a joke that SK stands for Stop Knudsen, or in the translation Stop Knudsen. It appeared due to the fact that the new algorithm made the Knudsen attack unsuccessful. In fact, SK stands for Strengthened Key Schedule, meaning "Enhanced Key Extension."
Attack on SQUARE cipher
In 1997, Lars Knudsen, along with his colleagues Joan Daemen and Eng. Vincent Rijmen, developed an attack on the SQUARE block cipher [2] . The algorithm itself consisted of 6 rounds, including 4 operations, linear string conversion , non-linear byte replacement, transposition and addition with the key. They chose an attack based on selected plaintext . The main idea was to select sets of text. It was found that out of the 256 selected plaintexts, there are two that uniquely determine the encryption key with overwhelming success if the cipher consisted of 4 rounds. Then the attack was continued for 5 and 6 rounds and successfully completed, although it was impossible due to the lack of modern technology. However, it was considered relevant, as it was considered one of the fastest.
Block Cipher Hash Function
In his article “Hash functions based on block ciphers and quaternary codes” [3] (“Hash functions based on block ciphers and quaternary codes”) Lars Knudsen showed that the development of an effective hash function with minimal internal memory based on m is bit block cipher is a difficult task. Moreover, none of the hash functions examined by him provided better protection than the 2 ^ m obtained by the brute force method. By changing the model a bit (for example, by increasing the size of the internal memory, as well as by introducing output transformations), we can obtain a compression function and, thus, a hash function for which security can be proved on the basis of probable assumptions made by Knudsen. The method he proposed was the best at the moment (namely, the encryption speed is equal to or 4 for hashing one block), and provided a high level of security, or higher efficiency at the same security levels. For the large value of the internal memory, speeds are close to those that can be obtained. In addition, the hash function provides a high degree of parallelism , which will give an even more efficient implementation.
RMAC Research
RMAC [4] is an authentication system based on block ciphers. Currently, block cipher algorithms approved to be used in RMAC are AES and triple- DES . In his work, Knudsen analyzed this system and found that the scheme allows some control over one of the two keys of the main block cipher to be attacked and this allows for several key-related attacks on RMAC. He also described an effective attack on RMAC when used with tri- DES and a general attack on RMAC, which can be used to find one key out of two faster than exhaustive search. His attack on RMAC-DES requires typed messages, which is practically possible with today's processing speed.
3gpp- MAC Research
In his work, Knudsen examined the falsification and attack on the recovery key using the 3gpp- MAC authentication scheme [5] proposed in the 3gpp specification. He proposed three main classes of attacks. Attacks in the first class use a large number of "selected MACs", in the second class use a large number of "known MACs", and in the third class a large number of MAC checks are required, but very few "known MACs" and do not require "selected MACs" at all. The first class provides both falsification and attack on the recovery key, while the second and third classes only attack on the key. Both simple keys (single-key) and double keys (two-key) are taken into account. The attack of falsification is related to both types of keys, while the attack on the recovery key applies only to the second option (two-key).
CRUSH hash analysis
The structure of the CRUSH hash function [6] is shown in the figure. A function consists of a data buffer, a Bijection Selection Component of logical (Boolean) functions, and a bijective function B (an effective block cipher for which text is taken from a data buffer). Knudsen has shown that CRUSH or the more general Iterated Halving method does not satisfy the requirements of good hash functions, either in terms of security or execution. He showed how to generate collisions and second prototypes to use Iterated Halving. The possibility of creating such collisions is based on function B. The complexity of these attacks is extremely small and amounts to only a dozen deciphers of function B, regardless of size. Attacks are used when using any block cipher, including AES with 192-bit and AES with 256-bit keys.
The most famous works
- 1996 - together with Bart Prenel ( English Bart Preneel ) proposed a way to create hash functions based on block ciphers . In his work, Knudsen demonstrated the new attack LOKIDBH , which broke the last subclass of a wide class of effective hash functions previously proposed in the literature.
- I examined nonlinear approximations in linear cryptanalysis and received a generalization of Matsui's cryptanalytic methods. This allowed for greater flexibility in crypto attacks. Achievements have been demonstrated by the attack on LOKI91 .
- Studied in detail the SAFER cipher for stability [7] . He developed an attack that led to a significant modification of the encryption algorithm and the emergence of SAFER -SK (as a joke, Lars friends decrypted SK as Stop Knudsen, although in reality this means Strengthened Key schedule).
- 1997 - in the article “The Block Cipher Square” [8] proposed an attack on the 128-bit SQUARE cipher, which marked the beginning of a new branch of cryptanalysis - integrated cryptanalysis. Studied in detail the IDEA cipher with a reduced number of rounds. Published a paper on the weaknesses of this algorithm.
- 1998 - in the development team ( Ross Anderson , Eli Beeham ) proposed the symmetric block encryption algorithm Serpent [9] , which became one of the finalists of the second stage of the AES contest. Developed a DEAL encryption algorithm [10] based on DES .
- 1999 - conducted research on fast hardware encryption .
- 2000 - together with Willy Meyer ( born Willi Meier ) published a detailed analysis of the next AES candidate - RC6 .
- 2001 - initiated research in the field of online ciphers and Hash-CBC designs. He studied the stability of the Skipjack algorithm.
- 2002 - made a presentation “Advances in Cryptography” at EUROCRYPT 2002, and also dealt with digital signatures and error correction codes. Investigated the security of Feistel ciphers with six rounds or less.
- 2003 - 2004 - researched 3gpp-MAC and RMAC , and also spoke at ESORICS and AES conferences.
- 2005 - published the concept of the cryptographic hash function , and also developed attacks on MD2 and RMAC .
- 2007 - published a detailed analysis of the CRUSH hash function.
- 2009 - made a presentation on random on randomization to enhance the security of digital signatures, as well as on on a cryptanalysis report .
In total, Lars Knudsen has published over 70 works on a very wide range of topics, such as the R-MAC scheme, the SHA-1 and MD2 hash functions, many block ciphers - DES , DFC , IDEA , , , MISTY1 , RC2 , RC5 , RC6 , SC2000 , Skipjack , SQUARE and SAFER . He also spoke at conferences on error-correcting codes . He participated in the development of robot navigation systems.
Colleagues
Currently, Lars Knudsen is heading the cryptography section at the Danish Technical University. As of May 2014, this working group includes (Ph.D.):
- Andrey Bogdanov ( born Andrey Bogdanov ) - professor,
- Christian Rechberger - professor,
- Elmar Tischhauser - Professor,
as well as several post-docs and graduate students.
Notes
- ↑ Lars Knudsen. Block Cipher - Analysis, Design and Applications, Ph.D. Thesis, 1994. (English) : journal. - 1994 .-- 1 July.
- ↑ Joan Daemen, Lars Knudsen and Vincent Rijmen. The block cipher Square (neopr.) . - 1997.
- ↑ Lars Knudsen and Bart Preneel. Hash functions based on block ciphers and quaternary codes : journal. - 1996.
- ↑ Lars R. Knudsen and Tadayoshi Kohno. Analysis of RMAC (neopr.) . - 2007.
- ↑ Lars R. Knudsen and Chris J Mitchell. Analysis of 3gpp-MAC and two-key 3gpp-MAC (unspecified) . - 2003.
- ↑ Matt Henricksen and Lars R. Knudsen. Cryptanalysis of the CRUSH Hash Function (neopr.) . - 2007.
- ↑ Lars Knudsen. A Key-schedule Weakness in SAFER K-64 (unspecified) .
- ↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. The Block Cipher SQUARE (neopr.) .
- ↑ Lars Knudsen, Eli Biham, Ross Anderson. Serpent: A New Block Cipher Proposal (neopr.) .
- ↑ Lars Knudsen. DEAL - A 128-bit Block Cipher (Neopr.) . - Department of Informatics, University of Bergen, Norway, 1998 .-- February 21 ( vol. Technical report no. 151 ). Archived March 28, 2009. Archived March 28, 2009 on Wayback Machine
Literature
- Schneier B. Chapter 14. And more block ciphers // Applied cryptography. Protocols, algorithms, C source code = Applied Cryptography. Protocols, Algorithms and Source Code in C. - M .: Triumph, 2002. - S. 382-384. - 816 s. - 3000 copies. - ISBN 5-89392-055-4 .
- Matt Henricksen and Lars R. Knudsen. Cryptanalysis of the CRUSH Hash Function.
- Lars R. Knudsen and Tadayoshi Kohno. Analysis of RMAC.
- Lars Knudsen and Bart Preneel . Hash functions based on block ciphers and quaternary codes.
- Lars Knudsen and Chris J Mitchell. Analysis of 3gpp-MAC and two-key 3gpp-MAC.
- Joan Daemen , Lars Knudsen and Vincent Rijmen . The block cipher Square.