>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?
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.