> 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.
>Note that this high level insight isn't really a contribution of the paper
The problem with this statement is that nobody outside of the design staff understood how the algorithm was weak, or (AFAIK) precisely what the criteria for "weak" actually were. Moreover -- after the export standards were relaxed and GEA-2 had shipped, nobody came forward and said "remove this now totally obsolete algorithm from your standards because we weakened it in this way and it only has 40-bit security" which is why it is present in phones as recent as the iPhone 8 (2018) and potentially may be vulnerable to downgrade attacks.
There are some stupid ways to weaken a cipher that would make it obvious that something was weak in the design, e.g., just truncating the key to 40 bits (as IBM did with DES from 64->56 bits, by reducing the key size and adding parity bits.) The designers didn't do this. They instead chose a means of doing this that could only be detected using a fairly sophisticated constraint solver which (may not have been) so easily available at the time. So I don't entirely agree with this assessment.
> nobody outside of the design staff understood how the algorithm was weak
And, as I mention, pointing that out was a contribution of the paper.
> or (AFAIK) precisely what the criteria for "weak" actually were
I think this 40 bit limit is well documented for other encryption algorithms. I couldn't find it in any (old) US regulation text though after a cursory search.
The "U.S. edition" supported full size (typically 1024-bit or larger) RSA public keys in combination with full size symmetric keys (secret keys) (128-bit RC4 or 3DES in SSL 3.0 and TLS 1.0). The "International Edition" had its effective key lengths reduced to 512 bits and 40 bits respectively (RSA_EXPORT with 40-bit RC2 or RC4 in SSL 3.0 and TLS 1.0)
> And, as I mention, pointing that out was a contribution of the paper.
Maybe I didn't make it clear. The open question prior to this paper was not "precisely how did the algorithm implement a specific level of security", the question was: what is that specific level of security? This was totally unknown and not specified by the designers.
Notice that the specification doesn't define the desired security, in the same way that it defines, say, the key size. It just handwaves towards 'should be exportable'. I can't find a copy of the requirements document anymore, but the quote given in the spec doesn't specify anything more than that statement.
>I think this 40 bit limit is well documented for other encryption algorithms. I couldn't find it in any (old) US regulation text though after a cursory search.
In the United States (note: GEA-1 was not a US standard) some expedited licenses were granted to systems that used effective 40 bit keys. In practice (for symmetric ciphers) this usually meant RC2 and RC4 with explicitly truncated keys. GEA-1 does not have a 40-bit key size -- a point I made in the previous post. It has a 64-bit key size. Nowhere does anyone say "the requirement for this design is effective 40-bit security": they don't say anything at all. It could have had 24 bit security, 40 bit security, 56 bit security or even 64-bit security.
ETA: Moreover, there is more to this result than 40-bit effective keysize. A critical aspect of this result is that the attackers are able to recover keys using 65 bits of known keystream. The uncompromised GPRS algorithms require several hundred (or over 1000) bits. Note that these known plaintext requirements are somewhat orthogonal to keysize: capturing 65 bits of known keystream is possible in protocols like GPRS/IP due to the existence of structured, predictable packet headers -- as the authors point out. Capturing >1000 bits may not be feasible at all. That's really significant and interesting, and not the result one would expect if the design goal was simply "effective 40-bit key size". One has to wonder if "ability to perform passive decryption using small amounts of known plaintext" is also included in the (missing) security design requirements document. I bet it isn't.
> In the United States (note: GEA-1 was not a US standard) some expedited licenses were granted to systems that used effective 40 bit keys. In practice (for symmetric ciphers) this usually meant RC2 and RC4 with explicitly truncated keys. GEA-1 does not have a 40-bit key size -- a point I made in the previous post. It has a 64-bit key size. Nowhere does anyone say "the requirement for this design is effective 40-bit security": they don't say anything at all. It could have had 24 bit security, 40 bit security, 56 bit security or even 64-bit security.
Really? How would you get 64-bit security from a 40-bit key?
> 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.
I've taken the phones from a table in the paper. There weren't any more recent phones in the list. The listed phones are probably still common, even in the first world.
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.
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.
> According to a study by Tomcs ́anyi et al. [11], that analyzes the use of the ciphering algorithm in GRPS of 100 operators worldwide, most operators prioritize the use of GEA-3(58) followed by the non-encrypted mode GEA-0(38). Only a few operators rely on GEA-2(4), while no operator uses GEA-1(0).
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:
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: 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.