Explain Linearization attack.

144views

written 8.4 years ago by

teamques10 ★ 68k

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.

ADD COMMENT EDIT

include <stdio.h>