Cecilia Urbina: A5/1

A5 / 1 is used to provide privacy in outdoor communication with the GSM standard. An algorithm that encrypts the conversation between two GSM terminals when the message travels through the air.

History

A5/1 is used in Europe and the U.S. A5/1 is a very weak encryption algorithm, developed in 1987, when GSM was not even considered for use in Europe. A5 / 2 is a safer alternative that was developed in 1989.

Security

There are some well-known attacks to the algorithm A5 / 1. In some attacks, expensive preprocessing stages are required, after the code is attacked in minutes or seconds. The weakness of the algorithm had been passive attacks using the assumption of known plaintext. In 2003 were identified serious weaknesses that could be exploited ciphertext attacks (active attack). Eli Biham and Nathan Keller demonstrated attacks against A5 / 1 and A5 / 3 that allow the attacker to decipher the conversation in real time from a GSM phone.

Attacks with knowledge of the plaintext

In 1997, Golic presented an attack based on solving sets of linear equations of computational complexity 2 ^ 4016.
Also in 2000, Eli Biham and Orr Dunkelman published an attack with a complexity of 2 ^ 3991. This attack requires 32 GB of data stored after a previous stage of computing 2 ^ 38.

Description

The transmission in GSM is performed in data blocks. Each block contains 114 bits available for information. A5 / 1 produces a 228-bit sequence of stream, which will serve as key encryption for message clear by Vernam algorithm (114 bits for a sense of call, and 114 for the other). It requires a user key of 64 bits (which is stored in the phone's SIM) together with an initialization vector 22 bits publicly known.

http://es.scribd.com/doc/25241410/46/Esquema-del-algoritmo-de-cifra-A5-1

The sequence of 86 bits (64 and 22 key vector) enters three shift registers LFSR linear feedback, for generating the encryption key by scrolling irregular following a majority function F. The output generated by the XOR

http://en.wikipedia.org/wiki/A5/1

http://calliope.uwaterloo.ca/~ggong/ECE710T4/lec8-ch6b.pdf

Initializing A5

1. The three shift registers are set to zeros. The output and function are most disabled.
2. The least significant bit of each row applies XOR each bit of the key for 64 cycles. At this point, the LFSR normally works.
3. The least significant bit of each row applies XOR each bit vector Initialization for 22 cycles. The LFSR is working normally.
4. The majority function F is enabled for 100 cycles and moving logs, the Movement is made taking the result of F.
5. Using the majority function, and enabling the output of each shift register bitsduring 228 cycles. The most significant bits of each register are operated by XOR output, the result of this operation results in a bit of the encryption key.

Majority function

F (C1, C2, C3) = C1 C2 ⊕ C1 C3 ⊕ C2 C3 where C1, C2, C3 are the clock bits for records R1, R2, R3, respectively.
If the bit clock of a record matches the function majority, that record moves. Otherwise, the register keeps its value.
This function majority forces at least 2 of the moving records at any time.
Clock sequence is irregular and depends on the key and Frame Number.

Message Encryption

The clear message is operated by XOR with the first sequence of 144 bits (load data).