4 ms·

Excerpt from the abstract: "This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms." [..] "This unusual pat

Excerpt from the abstract: "This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms." [..] "This unusual pattern indicates that the weakness is intentionally hidden to limit the security level to 40 bit by design." So in other words: GPRS was intentionally backdoored.

baybal2 5y ago
As were its other cyphers. Even in their best case effort, 64 bit keys were in the realm of supercomputer level bruteforcing by late nineties if just few more cypher quality degradations, and key leaks were know.
est31 5y ago
> So in other words: GPRS was intentionally backdoored. Note that this high level insight isn't really a contribution of the paper, given that the authors of the algorithm basically admitted this themselves. Excerpt from the paper: It was explicitly mentioned as a design requirement that “the algorithm should be generally exportable taking into account current export restrictions” and that “the strength should be optimized taking into account the above require- ment” [15, p. 10]. The report further contains a section on the evaluation of the design. In particular, it is mentioned that the evaluation team came to the conclusion that, “in general the algorithm will be exportable under the current national export restrictions on cryptography applied in European countries” and that “within this operational context, the algorithm provides an adequate level of security against eavesdropping of GSM GPRS services” Basically, export regulations from that era implied that you had to make your algorithm weak intentionally. The main contribution of the paper was to give a public cryptoanalysis and point out the specific location of the flaw. I think it's highly interesting. Another excerpt: Further, we experimentally show that for randomly chosen LFSRs, it is very unlikely that the above weakness occurs. Concretely, in a million tries we never even got close to such a weak instance. Figure 2 shows the distribution of the entropy loss when changing the feedback polynomials of registers A and C to random primitive polynomials. This implies that the weakness in GEA-1 is un- likely to occur by chance, indicating that the security level of 40 bits is due to export regulations. Also, even though operators don't deploy GEA-1 any more, according to the paper many semi-recent phones still support GEA-1 (e.g. iPhone 8, Samsung Galaxy S9, OnePlus 6T, ...). The paper describes a possible downgrade attack that allows the session key to be obtained which can be used to extract prior communication that happened under more secure encryption algorithms (section 5.3). This is big. The paper authors managed to get a test added to the conformance test suite that checks that GEA-1 is not supported, so hopefully future phones will drop the GEA-1 support.
- kodablah 5y ago
  > Basically, export regulations from that era implied that you had to make your algorithm weak intentionally I think the question then becomes, is the regulation still satisfied if the specifics of the intentional limitation/weakness/exploit are undocumented? It's likely moot these days, but curious nonetheless.
- SSLy 5y ago
  >operators don't deploy GEA-1 any more in 1st world maybe
  - est31 5y ago
    Yeah I omitted maybe too much in the summary. The paper mentions that 2G is used in some places as a fallback, so operators still support it if the phone doesn't support newer standards. In fact in Germany, the country of one of the paper's authors, precisely this is happening: 3G is being turned off while 2G is used as fallback for devices that don't support LTE. Apparently there are some industrial use cases of 2G that still rely on it. In Switzerland, they are instead turning off 2G and keeping 3G as the fallback. IDK how the situation is in third world countries, but note that India at least is in the top ten when it comes to LTE coverage. https://www.speedtest.net/insights/blog/india-4g-availability-2019/ https://www.speedtest.net/insights/blog/india-4g-availabilit...
    - slim 5y ago
      Also 2G is less battery hungry. We use it for our professional applications on Android
      - AstralStorm 5y ago
        That blanket statement is unwarranted. Due to various signal limitations, newer protocol can have fewer retransmissions and may use less transmit power. Especially later revisions of 4G and all 5G due to MIMO and signal power estimates for roaming. Also may allow the use of local WiFi to save power. It would be nice to use newer protocols on lower frequencies for range but regulation is what it is. Trust the phone to do the right thing.

baybal2 5y ago

As were its other cyphers. Even in their best case effort, 64 bit keys were in the realm of supercomputer level bruteforcing by late nineties if just few more cypher quality degradations, and key leaks were know.

est31 5y ago

> So in other words: GPRS was intentionally backdoored. Note that this high level insight isn't really a contribution of the paper, given that the authors of the algorithm basically admitted this themselves. Excerpt from the paper: It was explicitly mentioned as a design requirement that “the algorithm should be generally exportable taking into account current export restrictions” and that “the strength should be optimized taking into account the above require- ment” [15, p. 10]. The report further contains a section on the evaluation of the design. In particular, it is mentioned that the evaluation team came to the conclusion that, “in general the algorithm will be exportable under the current national export restrictions on cryptography applied in European countries” and that “within this operational context, the algorithm provides an adequate level of security against eavesdropping of GSM GPRS services” Basically, export regulations from that era implied that you had to make your algorithm weak intentionally. The main contribution of the paper was to give a public cryptoanalysis and point out the specific location of the flaw. I think it's highly interesting. Another excerpt: Further, we experimentally show that for randomly chosen LFSRs, it is very unlikely that the above weakness occurs. Concretely, in a million tries we never even got close to such a weak instance. Figure 2 shows the distribution of the entropy loss when changing the feedback polynomials of registers A and C to random primitive polynomials. This implies that the weakness in GEA-1 is un- likely to occur by chance, indicating that the security level of 40 bits is due to export regulations. Also, even though operators don't deploy GEA-1 any more, according to the paper many semi-recent phones still support GEA-1 (e.g. iPhone 8, Samsung Galaxy S9, OnePlus 6T, ...). The paper describes a possible downgrade attack that allows the session key to be obtained which can be used to extract prior communication that happened under more secure encryption algorithms (section 5.3). This is big. The paper authors managed to get a test added to the conformance test suite that checks that GEA-1 is not supported, so hopefully future phones will drop the GEA-1 support.

kodablah 5y ago
> Basically, export regulations from that era implied that you had to make your algorithm weak intentionally I think the question then becomes, is the regulation still satisfied if the specifics of the intentional limitation/weakness/exploit are undocumented? It's likely moot these days, but curious nonetheless.
SSLy 5y ago
>operators don't deploy GEA-1 any more in 1st world maybe
- est31 5y ago
  Yeah I omitted maybe too much in the summary. The paper mentions that 2G is used in some places as a fallback, so operators still support it if the phone doesn't support newer standards. In fact in Germany, the country of one of the paper's authors, precisely this is happening: 3G is being turned off while 2G is used as fallback for devices that don't support LTE. Apparently there are some industrial use cases of 2G that still rely on it. In Switzerland, they are instead turning off 2G and keeping 3G as the fallback. IDK how the situation is in third world countries, but note that India at least is in the top ten when it comes to LTE coverage. https://www.speedtest.net/insights/blog/india-4g-availability-2019/ https://www.speedtest.net/insights/blog/india-4g-availabilit...
  - slim 5y ago
    Also 2G is less battery hungry. We use it for our professional applications on Android
    - AstralStorm 5y ago
      That blanket statement is unwarranted. Due to various signal limitations, newer protocol can have fewer retransmissions and may use less transmit power. Especially later revisions of 4G and all 5G due to MIMO and signal power estimates for roaming. Also may allow the use of local WiFi to save power. It would be nice to use newer protocols on lower frequencies for range but regulation is what it is. Trust the phone to do the right thing.