0
7.6kviews
Explain Linearization attack.

Subject: System Web Security

Topic: Software Security

Difficulty: Medium

1 Answer
3
134views
  • In cryptography, the extended Sparse Linearization (XSL) attack is a method of cryptanalysis for block ciphers.
  • Since AES is already widely used in commerce and government for the transmission of secret information, finding a technique that can shorten the amount of time it takes to retrieve the secret message without having the key could have wide implications.
  • The method has a high work-factor, which unless lessened, means the technique does not reduce the effort to break AES in comparison to an exhaustive search. Therefore, it does not affect the real-world security of block ciphers in the near future.
  • In overview, the XSL attack relies on first analyzing the internals of a cipher and deriving a system of quadratic simultaneous equations. These systems of equations are typically very large, for example 8,000 equations with 1,600 variables for the 128-bit AES.
  • Several methods for solving such systems are known. In the XSL attack, a specialized algorithm, termed extended Sparse Linearization, is then applied to solve these equations and recover the key.
  • The attack is notable for requiring only a handful of known plaintexts to perform; previous methods of cryptanalysis, such as linear and differential cryptanalysis, often require unrealistically large numbers of known or chosen plaintexts.

  • Example:

    Consider the below code

    include <stdio.h>

    int main(intargc, const char *argv[])
    {
        inti;
        char serial[9] = “S123N456\n”;
        for(I = 0;I < 8;++i)
        {
            if(argv[1][i] ! = serial[i]) break;
        }
        if(i==8)
        {
        printf(“\n Serial  number is   correct !\n\n”);
        }
    }
    
    • Program checks for serial number S123N456
    • For efficiency, check made one character at a time
    • Correct string takes longer than incorrect
    • Attacker tries all 1 character strings
    • Finds S takes most time
    • Attacker then tries all 2 char strings $S^*$

      Finds S1 takes most time

    • Attacker is able to recover serial number one character at a time.

    • What is the advantage of attacking serial number one character at a time?

      Suppose serial number is 8 characters and each has 128 possible
      values

    i. Then $128^8 = 25^6$ possible serial numbers

    ii. Attacker would guess the serial number in about $2^{55}$ tries- a lot of work

    iii. Using the linearization attack, the work is about 8*(128/2) = $2^9$ which is trivial

  • A real-world linearization attack

    TENEX (an ancient timeshare system)

    i. Passwords checked one character at a time

    ii. Careful timing was not necessary

    iii. could arrange for a “page fault” when next unknown character guessed correctly

    iv. The page fault register was user accessible

    v. Attack was very easy in practice.

Please log in to add an answer.