A weakness in the algorithm used to encrypt cellphone data in the 1990s and 2000s allowed hackers to spy on some internet traffic, according to a new research paper.
The paper has sent shockwaves through the encryption community because of what it implies: The researchers believe that the mathematical probability of the weakness being introduced on accident is extremely low. Thus, they speculate that a weakness was intentionally put into the algorithm. After the paper was published, the group that designed the algorithm confirmed this was the case.
Researchers from several universities in Europe found that the encryption algorithm GEA-1, which was used in cellphones when the industry adopted GPRS standards in 2G networks, was intentionally designed to include a weakness that at least one cryptography expert sees as a backdoor. The researchers said they obtained two encryption algorithms, GEA-1 and GEA-2, which are proprietary and thus not public, "from a source." They then analyzed them and realized they were vulnerable to attacks that allowed for decryption of all traffic.
When trying to reverse-engineer the algorithm, the researchers wrote that (to simplify), they tried to design a similar encryption algorithm using a random number generator often used in cryptography and never came close to creating an encryption scheme as weak as the one actually used: "In a million tries we never even got close to such a weak instance," they wrote. "This implies that the weakness in GEA-1 is unlikely to occur by chance, indicating that the security level of 40 bits is due to export regulations."
Researchers dubbed the attack "divide-and-conquer," and said it was "rather straightforward." In short, the attack allows someone who can intercept cellphone data traffic to recover the key used to encrypt the data and then decrypt all traffic. The weakness in GEA-1, the oldest algorithm developed in 1998, is that it provides only 40-bit security. That's what allows an attacker to get the key and decrypt all traffic, according to the researchers.
"To meet political requirements, millions of users were apparently poorly protected while surfing for years."
A spokesperson for the organization that designed the GEA-1 algorithm, the European Telecommunications Standards Institute (ETSI), admitted that the algorithm contained a weakness, but said it was introduced because the export regulations at the time did not allow for stronger encryption.
"We followed regulations: we followed export control regulations that limited the strength of GEA-1," a spokesperson for ETSI told Motherboard in an email.
Håvard Raddum, one of the researchers who worked on the paper, summed up the implications of this decision in an email to Motherboard.
"To meet political requirements, millions of users were apparently poorly protected while surfing for years," he said.
Raddum and his colleagues found that GEA-1's successor, GEA-2 did not contain the same weakness. In fact, the ETSI spokesperson said that when they introduced GEA-2 the export controls had been eased. Still, the researchers were able to decrypt traffic protected by GEA-2 as well with a more technical attack, and concluded that GEA-2 "does not offer a high enough security level for today's standards," as they wrote in their paper.
Lukasz Olejnik, an independent cybersecurity researcher and consultant who holds a computer science PhD from INRIA, told Motherboard that "this technical analysis is sound, and the conclusions as to the intentional weakening of the algorithm rather serious."
The good news is that GEA-1 and GEA-2 are not widely used anymore after cellphone providers adopted new standards for 3G and 4G networks. The bad news is that even though ETSI prohibited network operators from using GEA-1 in 2013, the researchers say that both GEA-1 and GEA-2 persist to this day because GPRS is still used as a fallback in certain countries and networks.
"In most countries, [the risk is] not very high, and significantly lower risk than at the start of the 2000’s since GEA-3 and GEA-4 are used today," Raddum said. "But handsets still support GEA-1. Scenarios where a mobile phone today can be tricked into using GEA-1 exist."
In fact, the researchers tested several modern phones to see if they would still support the vulnerable algorithms and "surprisingly" found that they still do. The researchers said that it's the baseband manufacturers who are responsible for implementing standards.
"The use of GEA-1 has still far-reaching consequences on the user’s privacy," the researchers wrote, "and should be avoided at all costs."
Subscribe to our cybersecurity podcast, CYBER.