Clever Geek Handbook
📜 ⬆️ ⬇️

Linked Key Attack

Related-key attack [1] - a type of cryptographic attack in which a cryptanalyst selects a connection between a pair of keys, but the keys themselves are not known to him. Data is encrypted with both keys. In the well-known plaintext variant, the cryptanalyst knows the plaintext and ciphertext of the data encrypted with two keys. The intent of the attacker is to find the actual secret keys. It is assumed that the attacker knows or selects some mathematical relation that binds keys together. The ratio has the formK {\ displaystyle K} KB {\ displaystyle B} B= {\ displaystyle =} =F {\ displaystyle F} F (K {\ displaystyle K} KA {\ displaystyle A} A ) [2] whereF {\ displaystyle F} F - function selected by the attacker,K {\ displaystyle K} KA {\ displaystyle A} A andK {\ displaystyle K} KB {\ displaystyle B} B - related keys. For each encryption, the relationship between the keys is selected individually. There are many ways to find this ratio correctly [3] . Compared to other attacks in which an attacker can only manipulate plaintext and / or encrypted text, the choice of the relationship between secret keys provides an additional degree of freedom for the attacker. The disadvantage of this freedom is that such attacks can be more difficult in practice. However, designers usually try to create “ideal” primitives that can be automatically used without further analysis in the widest possible set of protocols or operating modes. Thus, resisting such attacks is an important goal of designing block ciphers, and in fact it was one of the stated goals of designing the Rijndael algorithm.

Key Extension

Most encryption algorithms modify the source key for later use. This modification is called a key extension . There are examples of algorithms in which the key extension procedure is extremely complicated compared to encryption itself, among which are HPC and FROG algorithms. The name of the procedure is determined by the fact that the original encryption key usually has a size significantly smaller than the set of subkeys used in the rounds of the algorithm, i.e. the extended key.

Purpose of the key extension procedure

.

It turns out that the encryption algorithm can be logically divided into two subalgorithms: the encryption transforms themselves and the key extension procedure. The key expansion procedure has a number of requirements [4] :

  • It is required that the key extension procedure computes the keys in parallel with encryption transformations: this will allow both parallelizing the calculations in multiprocessor systems and not wasting memory to store the entire extended key during encryption in conditions of limited resources.
  • In many applications of symmetric encryption algorithms often have to change the keys in the encoder. Accordingly, a very complicated key expansion procedure will not allow using the encryption algorithm in these cases.
  • The degree to which the algorithm is susceptible to attacks on related keys is also highly dependent on the key extension procedure.

Classic Attack on Linked Keys [1]

This type of attack was first proposed by Israeli scientist Eli Biham in 1992 in a New Types of Cryptanalytic Attacks Using Related Keys article. The related key attack described by him resembles a shear attack . A shift attack ( English slide attack ) is a cryptographic attack , which is, in general, an attack based on selected plaintext , which allows cryptanalysis of block multi-round ciphers regardless of the number of rounds used. Suggested by Alex Biryukov and David Wagner in 1999 [5] . Shift attack uses two plaintextsP {\ displaystyle P}   andP′ {\ displaystyle P '}   satisfying the following relationship:P′=F(P,kone) {\ displaystyle P '= F (P, k_ {1})}   whereF() {\ displaystyle F ()}   Is the function of the round , andkone {\ displaystyle k_ {1}}   - Connect the 1st round. A related key attack uses a similar key relationship. Suppose that the desired encryption key K after modification by its key extension procedureEx(K) {\ displaystyle Ex (K)}   gives a sequence of subkeys:Ex(K)={kone,k2,...,kr-one,kr} {\ displaystyle Ex (K) = \ left \ {{k_ {1}, k_ {2}, \ ldots, k_ {r-1}, k_ {r}} \ right \}}   wherer {\ displaystyle r}   - the number of rounds of the encryption algorithm. Suppose a key existsK′ {\ displaystyle K '}   , the extension of which gives the following sequence:Ex(K′)={k2,k3,...,kr,kone} {\ displaystyle Ex (K ') = \ left \ {{k_ {2}, k_ {3}, \ ldots, k_ {r}, k_ {1}} \ right \}}   , i.e. a sequence of subkeys created based on a keyK′ {\ displaystyle K '}   , cyclically shifted relative to the sequence of the desired keyK {\ displaystyle K}   for 1 round [6] .

The essence of the attack

  1. Suppose a cryptanalyst knows2n2 {\ displaystyle 2 ^ {\ frac {n} {2}}}   steam(P,C) {\ displaystyle \ left ({P, C} \ right)}   plaintext and their corresponding ciphertexts (encrypted using the keyK {\ displaystyle K}   ), wheren {\ displaystyle n}   - the size of the block of encrypted data, presented in bits .
  2. In addition, cryptanalysts know2n2 {\ displaystyle 2 ^ {\ frac {n} {2}}}   pairs of texts(P′,C′) {\ displaystyle \ left ({P ', C'} \ right)}   encrypted using a keyK′ {\ displaystyle K '}   related toK {\ displaystyle K}   the above ratio.
  3. For each text ratio(P,C) {\ displaystyle \ left ({P, C} \ right)}   and(P′,C′) {\ displaystyle \ left ({P ', C'} \ right)}   cryptanalyst needs to find solutions to the system of equations [7] :

{F(P,k∗)=P′F(C,k∗)=C′{\ displaystyle {\ begin {cases} F (P, k ^ {*}) = P '\\ F (C, k ^ {*}) = C' \ end {cases}}}  

Which one of2n2 {\ displaystyle 2 ^ {\ frac {n} {2}}}   textsP {\ displaystyle P}   matches each text fromP {\ displaystyle P}   , the cryptanalyst does not know in advance. But, the probability that two randomly selected texts will satisfy the desired ratio isone2n {\ displaystyle {\ frac {1} {2 ^ {n}}}}   .Then the required pair(P,P′) {\ displaystyle \ left ({P, P '} \ right)}   after analysis no more than2n2+one {\ displaystyle 2 ^ {{\ frac {n} {2}} + 1}}   texts, in accordance with the paradox of birthdays . Condition2n2+one {\ displaystyle 2 ^ {{\ frac {n} {2}} + 1}}   texts is not strict, it is evaluative and will be performed only on average [8] .

Keyk∗ {\ displaystyle k ^ {*}}   found from the above system is the desired subkeykone {\ displaystyle k_ {1}}   . Depending on the key generation operation, knowledgekone {\ displaystyle k_ {1}}   can give a cryptanalyst many opportunities for unauthorized access to information. For example, the key formation of the algorithm is constructed in such a way thatkone {\ displaystyle k_ {1}}   represents just the left 32-bit part of the keyK {\ displaystyle K}   . Since this algorithm uses a 64-bit key, after calculatingkone {\ displaystyle k_ {1}}   to findK {\ displaystyle K}   just brute force is enough232 {\ displaystyle 2 ^ {32}}   options. [9]

Round functionF() {\ displaystyle F ()}   the algorithm being attacked must be weak enough to calculatek∗ {\ displaystyle k ^ {*}}   , which applies to most modern encryption algorithms. In addition, the complexity of the attack can be significantly reduced in relation to the case described above, it all depends on the selected plaintext encryption algorithm. For example, calculations are simplified for algorithms based on a balanced Feistel network .

Attacks on various encryption algorithms

Attack on DES

DES ( English d ata e ncryption s tandard ) is an algorithm for symmetric encryption developed by IBM and approved by the US government in 1977 as an official standard ( FIPS 46-3). The block size for DES is 64 bits . The algorithm is based on a Feistel network with 16 cycles ( rounds ) and a key having a length of 56 bits . The algorithm uses a combination of non-linear (S-blocks) and linear (permutations of E, IP, IP-1) transformations.

The DES encryption algorithm is resistant to such an attack. During the encryption process for the main encryption function , it is required to calculate sixteen 48-bit keys, which are the result of converting the 56-bit source key ( for more details, see “Generating keyski {\ displaystyle k_ {i}}   "). The number of shifts in the key calculation algorithmki {\ displaystyle k_ {i}}   does not match in all rounds. Typically, key registers are shifted two bits after each round and only one bit after the first, ninth, and fifteenth rounds. However, if you change this switching scheme, set the shift to be the same in all rounds, then the resulting cryptosystem becomes vulnerable to an attack with associated keys. The least secure to attack is a modified DES, in which the key is shifted by two bits after each stage [10] .

 
Change switching pattern

The table describes the number of shifts before each round of key generation and the version with a modified number of shifts that is vulnerable to attack on related keys. In order to crack this version of the algorithm, a cryptanalyst will need only 2 17 selected plaintexts for selected keys or 2 33 known plaintexts for selected keys. To crack a modified DES, it is necessary to perform 1.43 * 2 53 operations, which is a small gain compared to exhaustive search, where the number of operations is 2 56 [11] . In 1998, using the EFF DES cracker supercomputer worth $ 250,000, DES was hacked in less than three days [12] . EFF DES cracker used full bust for cracking [13] . Huge requirements for time and data volume do not allow to implement an attack on connected keys, without the help of expensive equipment. But, nevertheless, the attack is interesting for two reasons:

  • This is the first attempt at a cryptanalytic attack on the subkey generation algorithm in DES.
  • The complexity does not depend on the number of stages of the cryptographic algorithm; it is equally effective against DES with 16, 32 or 1000 stages.

Attack on AES

Advanced Encryption Standard ( AES ), also known as Rijndael (pronounced [rɛindaːl] (Randal [14] )) is a symmetric block encryption algorithm (block size 128 bits, key 128/192/256 bits), adopted as the encryption standard by the US government according to the results of the AES contest . This algorithm is well analyzed and is now widely used, as was the case with its predecessor DES . AES is presented in three versions, each of which provides a certain level of security, depending on the length of the secret key. The key can be 128, 192 and 256 bits long. Since 2001, after choosing AES as a cryptographic standard, progress in its cryptanalysis is extremely low [15] . The best results were obtained in the course of conducting attacks based on related keys in 2009. Alex Biryukov, along with Dmitry Khovratovich, provided the first cryptanalytic attack based on associated keys on full-round AES-192 and AES-256, the developed method works faster than a complete search.

The developed attack on AES-256 is suitable for all types of keys and has a complexity of about 2 96. An attack on AES-192 was also presented. In both attacks, the number of active S-blocks of the key generation algorithm is minimized. This operation is applied using a boomerang attack . Differential characteristics for the boomerang were established by searching for local collisions in the cipher [16] . The main feature of AES-256, which is decisive for the attacks under consideration, is that the encryption algorithm has 14 rounds and a 256-bit key that doubles in the internal state. Therefore, the key generation algorithm consists of only 7 rounds, and each round in turn has 8 S-blocks. Similarly for AES-192 due to the fact that the key becomes one and a half times larger in the internal state, the key generation algorithm consists of only 8, not 12 rounds. Each round has only 4 S-blocks.

 
The best attacks on AES-192 and AES-256

Attack on AES-256

The following steps must be performed 2 25.5 times [17] :

  1. Prepare a clear text structure as follows.
  2. Encrypt it on keysKA {\ displaystyle K_ {A}}   andKB {\ displaystyle K_ {B}}   and save the resulting setsSA {\ displaystyle S_ {A}}   andSB {\ displaystyle S_ {B}}   .
  3. It is necessary to carry out the operationxorΔC {\ displaystyle xor ~ \ Delta _ {C}}   for all ciphertexts inSA {\ displaystyle S_ {A}}   and decrypt the changed ciphertexts with the keyKC {\ displaystyle K_ {C}}   .SC {\ displaystyle S_ {C}}   - A new set of plaintexts.
  4. Similarly forSB {\ displaystyle S_ {B}}   and keyKD {\ displaystyle K_ {D}}   .SD {\ displaystyle S_ {D}}   - A new set of plaintexts.
  5. Comparison of all pairs of plaintexts fromSC {\ displaystyle S_ {C}}   andSD {\ displaystyle S_ {D}}   with a length of 56 bits.
  6. For all others, check for differences in probability valuespi,0 {\ displaystyle p_ {i, 0}}   ati>one {\ displaystyle i> 1}   .If it is equal on both sides of a 16-bit filter, then for key pairs or else they are called a quartet(KA,KB) {\ displaystyle \ left ({K_ {A}, K_ {B}} \ right)}   and(KC,KD) {\ displaystyle \ left ({K_ {C}, K_ {D}} \ right)}   at∇ki,70=0 {\ displaystyle \ nabla k_ {i, 7} ^ {0} = 0}   ,Δki,00 {\ displaystyle \ Delta k_ {i, 0} ^ {0}}   will also be equal on both sides.
  7. It is necessary to select quartets whose differences cannot be affected by active S-blocks in the first round and active S-blocks in the key generation algorithm.
  8. Filtering out the wrong quartets, partially restore the key value.

Each structure has all sorts of options for the values ​​of the zero column, zero row, and constant value in other bytes. Of the 2 72 texts in each structure, 2 144 pairs can be compared. Of these pairs, 2 (144-8 * 9) = 2 72 will pass the first round. Thus, we get 1 desired quartet of 2 (96-72) = 2 24 structures and 3 necessary quartets of 2 25,5 structures. We calculate the number of quartets of the past 6 steps, there will be about 2 (144-56-16) = 2 72 pairs. The next step is to apply a 16-bit filter, so we get the total number of possible quartets 2 (72 + 25.5−6) = 2 91.5 [18] .

Attack on AES-192

The key creation algorithm in this case has better diffusion. Therefore, the boomerang attack uses two traces of 6 rounds each. Let us analyze 2 73 structures with 2 48 texts according to the following scheme [19] :

  1. Compare all pairs of possible plaintexts for key pairs(KA,KB) {\ displaystyle \ left ({K_ {A}, K_ {B}} \ right)}   and(KC,KD) {\ displaystyle \ left ({K_ {C}, K_ {D}} \ right)}   .
  2. Compare and save all quartets for ciphertexts.
  3. For each assumed key byte:k0,3 {\ displaystyle k ^ {0,3}}   ,k2,3 {\ displaystyle k ^ {2,3}}   andk0,five {\ displaystyle k ^ {0.5}}   atKA {\ displaystyle K_ {A}}   ;k0,five {\ displaystyle k ^ {0.5}}   atKA {\ displaystyle K_ {A}}   andKB {\ displaystyle K_ {B}}   :
    1. compute the values ​​for these bytes in all keys from the differential trace. Get key differences inΔK0 {\ displaystyle \ Delta K ^ {0}}   and∇Keight {\ displaystyle \ nabla K ^ {8}}   ;
    2. choose quartets that contradict∇Keight {\ displaystyle \ nabla K ^ {8}}   ;
    3. prepare counters for the uncalculated key bytes that correspond to the active S-blocks in the first two and last:K0,0 {\ displaystyle K ^ {0,0}}   ,k0,one {\ displaystyle k ^ {0,1}}   ,kone,2 {\ displaystyle k ^ {1,2}}   ,k3,0 {\ displaystyle k ^ {3,0}}   - in keysKA {\ displaystyle K_ {A}}   andKC {\ displaystyle K_ {C}}   ,k0,0 {\ displaystyle k ^ {0,0}}   ,k0,one {\ displaystyle k ^ {0,1}}   ,k0,2 {\ displaystyle k ^ {0,2}}   ,k0,3 {\ displaystyle k ^ {0,3}}   - in keysKA {\ displaystyle K_ {A}}   andKB {\ displaystyle K_ {B}}   , only 16 bytes;
    4. for each quartet, set the possible values ​​for their unknown bytes and increase the counters;
    5. create a group of 16 key bytes with maximum numbers;
    6. try all possible values ​​of the so far unknown 9 bytes of the key inK0 {\ displaystyle K ^ {0}}   and check this key for correctness. If unsuccessful, proceed to the first step [19] .

Both of these attacks are mainly of theoretical interest and in practice do not pose a real threat to applications using AES.

Practical Application

The described attacks using bound keys do not look practical. In many developments, they do not win much compared to exhaustive search, in addition, they require a large number of assumptions. This attack has long been considered quite powerful, but purely theoretical [20] . However, now experts such as John Kelsey and Bruce Schneier [20] believe that attacks on related keys can be of practical use. Some implementations of cryptographic algorithms or network protocols (for example, authentication or key exchange protocols) may already be susceptible to attack using associated keys [20] . One potential use is hash analysis. Theoretically, attacks on bound keys can be dangerous if you use symmetric encryption algorithms to build hash functions. There is currently no specific application for hash functions, but hash function developers should consider when designing that such a weakness exists. In any case, it is strongly recommended that cryptanalysis on related keys be taken into account when developing encryption algorithms and their implementation [21] . It was noted in [20] that the main condition for the attack looks rather strange: a cryptanalyst can write a key, that is, modify the unknown key sought in the required way, but cannot read it. However, some implementations of cryptographic algorithms or network protocols can be attacked using associated keys. In any case, it is strongly recommended to take into account cryptanalysis on related keys [20] when developing encryption algorithms and their implementation. It is also noted that attacks on bound keys can be very dangerous if you use symmetric encryption algorithms to build hash functions.

There are other potential vulnerabilities introduced into the encryption algorithm by the poorly designed key extension procedure, in particular [22] :

  • instability to attacks in the middle of the meeting class because these attacks exploit the fact that the first part of the encryption transformations of the attacked algorithm uses a different set of key bits. rather than the second part.
  • weak keys - keys whose encryption using is equivalent to decryption, or having other characteristics that significantly simplify the opening.
  • equivalent keys - different keys, but giving the same encryption result on a certain subset of plaintexts.
  • key classes - arise when a cryptanalyst can relatively easily determine the subset of the key set to which the desired key belongs, and, accordingly, thus reduce the area of ​​complete enumeration of the key.

See also

  • Matched Key Attack

Notes

  1. ↑ 1 2 Panasenko S., 2009 , p. 54.
  2. ↑ Biryukov, Khovratovich, 2009 , p. eight.
  3. ↑ Bellare, 2003 , p. 491.
  4. ↑ Panasenko S., 2009 , p. 53.
  5. ↑ Biryukov, Wagner, 1999 , p. 245-259.
  6. ↑ Biryukov, Khovratovich, 2009 , p. 7.
  7. ↑ Biham, 1994 , p. sixteen.
  8. ↑ Panasenko S., 2009 , p. 55.
  9. ↑ Panasenko S., 2009 , p. 56.
  10. ↑ Biham, 1994 , p. 15.
  11. ↑ Biham, 1994 , p. 17.
  12. ↑ Computerworld, 1998 .
  13. ↑ DES Cracker Project (neopr.) . EFF. - "On Wednesday, July 17, 1998 the EFF DES Cracker, which was built for less than $ 250,000, easily won RSA Laboratory's" DES Challenge II "contest and a $ 10,000 cash prize.". Date of treatment July 8, 2007. Archived on May 7, 2017.
  14. ↑ "... In accordance with Flemish rules, the name reads" Randal "- " Computerra ", December 1999, No. 49
  15. ↑ Biryukov, Khovratovich, 2009 , p. one.
  16. ↑ Biryukov, Khovratovich, 2009 , p. 2.
  17. ↑ Biryukov, Khovratovich, 2009 , p. 9.
  18. ↑ Biryukov, Khovratovich, 2009 , p. ten.
  19. ↑ 1 2 Biryukov, Khovratovich, 2009 , p. 12.
  20. ↑ 1 2 3 4 5 John Kelsey, 1996 .
  21. ↑ Biham, 1994 , p. 2.
  22. ↑ Panasenko S., 2009 , p. 59.

Literature

  • Schneier B. Applied Cryptography. Protocols, algorithms, source codes in the C language. - Triumph, 2002 .-- 816 p. - ISBN 5-89392-055-4 , 0-471-11709-9.
  • Eli Biham . New types of cryptanalytic attacks using related keys // Springer-Verlag: log. - 1994. - No. 4 . - P. 229-246 . - ISSN 1432-1378 . - DOI : 10.1007 / BF00203965 .
  • Alex Biryukov , Dmitry Khovratovich. Related-Key Cryptanalysis of the Full AES-192 and AES-256 (Eng.) // Springer Berlin Heidelberg: Journal. - 2009. - P. 1-18 . - ISSN 978-3-642-10366-7 . - DOI : 10.1007 / 978-3-642-10366-7_1 .
  • Alex Biryukov, David Wagner. Slide Attacks // Fast Software Encryption. 6th International Workshop, FSE'99 Rome, Italy, March 24–26, 1999 Proceedings. - Springer Berlin Heidelberg, 1999 .-- ISBN 978-3-540-66226-6 . (inaccessible link)
  • Panasenko C. Cryptanalytic attacks on associated keys // CIO-World: Journal. - 2007.
  • Panasenko C. Encryption Algorithms. Special reference . - BHV-Petersburg. - 2009. - S. 53-59.
  • Alexander Tyrenko. DES algorithm hacked in three days // Computerworld Russia: journal. - 1998. - No. 28-29 .
  • John Kelsey, Bruce Schneier, David Wagner. Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES (English) // Advances in Cryptology - CRYPTO '96, 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22 1996, Proceedings: Journal. - 1996.
  • Mihir Bellare and Tadayoshi Kohno. A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications . - EUROCRYPT. - 2003. - S. 491-506.
Source - https://ru.wikipedia.org/w/index.php?title=About_related_keys&oldid=97956940


More articles:

  • Rykova (village)
  • Greater Kosogol
  • Chemyakina (Irkutsk Oblast)
  • Pledge (Irkutsk Oblast)
  • Korsukova
  • Far Zakora
  • New (Galich district)
  • 41 (number)
  • Assembler Insert
  • Russian Youth Ice Hockey Team

All articles

Clever Geek | 2019