12 ms·

Cryptanalysis of GPRS Encryption Algorithms GEA-1 suggest intentional weakness

487 points by anonymfus 5y ago

aliasEli 5y ago
These algorithms are pretty weak but can still be used for securing the communications with current phones.
- daveguy 5y ago
  If the security level is artificially limited to 40 bits as the article suggests, then it is not good for securing any communications. It was relatively easy to crack DES-56 at rest before the turn of the century. A teraflop machine can defeat 40 bit encryption on the order of seconds. Edit: fixed the incorrect "RSA-56" encryption. Thanks graderjs.
  - graderjs 5y ago
    I think you might mean DES-56, or RC5, but not RSA.
    - jhgb 5y ago
      I imagine that technically RSA-56 would be easy to crack as well.
    - axoltl 5y ago
      To be fair you could probably break 56 bit RSA with a pen and paper.
      - graderjs 5y ago
        Pen and paper? I doubt it. You're welcome to try (show working ;p ;) xx) here's a sample RSA-56 problem I created for you: 39551945224675453 (56-bit semiprime)
    - daveguy 5y ago
      Yes, good catch. I did mean DES-56. I got the encryption name confused with the company that issued the challenge. The RSA algorithm is completely different.
- meepmorp 5y ago
  Also, note, GEA-2 doesn't seem to have the same kind of key weakening. I have no idea about the relative prevalence and configurability of those algorithms in the wild, though.
weinzierl 5y ago
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.
slownews45 5y ago
Too many coincidences for this to be by chance. IBM had Commercial Data Masking Facility which did key shortening to turn a 56 bit cipher into a 40 bit one. Now we've got this weird interaction which similarly reduces key length. Seems pretty obviously intentional?
- fragbait65 5y ago
  I agree, it is probably intentional, but I think it remains to be proven that it was malicious? Maybe 40 bit was seen as sufficient at the time, but are there any engineering reasons to actually shorten the key intentionally, does it improve the transfer rate in any way? I can't think of any, but I'm no expert, so maybe somebody else can chime in?
  - raphlinus 5y ago
    Depending on your definition of "malicious," I think it clears that bar. The problem is not making a good-faith argument that 40 bits was sufficient (which was done for some extent for export-approved 40 bit SSL), but that it misleads people into believing that it's 64 bit encryption while it only has 40 bits of strength for people who are in on the backdoor. And as far as the other half of your question, no, there's no possible benefit (other than to the backdoor owners) from a smaller keyspace, as it goes through the motion of encrypting with the larger one.
    - fragbait65 5y ago
      Thanks for the explanation!
    - deleted 5y ago
      [deleted]
  - slownews45 5y ago
    At the time 40 bits was not considered a backdoor, it was considered a weakness that would allow folks like NSA (with big budgets and intercept capabilities) to wiretap the way they had other communication approaches. Some situations, rather than designing new codecs, they would just weaken key gen side. The IBM effort there was public to allow for easier export, but also an approach that could be used to hide the weakness which in other settings may have been beneficial. It's possible however that folks involved understood what was going on to a degree but that it was seen as necessary to avoid export / import restrictions. More recently I think places like China ask that the holders of key material be located in country and make the full keys available or accessible to their security services. Not sure how AWS squares that circle unless they outsource their data centers in China to a third party that can then expose the keys for China to use.
nimish 5y ago
It should not be surprising that a system that is subject to lawful intercept requirements has weak encryption, especially pre-lift of the export ban.
- mytailorisrich 5y ago
  This is really to intercept over the air (so not necessarily for fully 'legal' intercept but also intelligence services). If law enforcement needs to wiretap a specific phone/SIM they only need to request it to the operator. Over-the-air encryption is irrelevant. Nowadays operators can duplicate all packets and send copies to law enforcement/security services in real time so that they can monitor 100% of a given phone's traffic from their offices.
  - cs2733 5y ago
    Exactly, this is for third party access or at least I've assumed for a long time all communications using standard tools have always been open for scrutinity. It's nothing new either - for as long as there is postal service your mail could be open by order of this or that government oficial. Not even the Pony Express was immune to that ;-) If you want greater secrecy do like the paranoid intel community has been doing since at least the cold war and exchange messages on seemingly disconnected channels - say 2 different newspaper columns, wordpress blogs or even websites made to look like robot-generated SEO spam, using code that was previously agreed in person, with everyone keeping hardcopies if necessary.
- ganzuul 5y ago
  It was supposed to take 6 hours using Finland's fastest supercomputer at the time. So said my professor.
gentleman11 5y ago
Pardon my ignorance, what is gprs and GEA-1 and what is it’s significance?
- ronsor 5y ago
  GPRS is the general packet radio service, used for (very slow) data and SMS transfer in combination with the old GSM protocol.
  - gentleman11 5y ago
    So, it encrypts sms messages and is still in use?
    - giantrobot 5y ago
      It doesn't encrypt SMS. It's over the air encryption for packet data (not calls or SMS) like WEP or WPA on WiFi. On GSM networks SMS was transmitted in leftover signaling space on voice circuits.
      - secondcoming 5y ago
        RACH: https://en.m.wikipedia.org/wiki/Random-access_channel https://en.m.wikipedia.org/wiki/Random-access_channel
      - ronsor 5y ago
        IIRC "SMS over GPRS" was an optional extension
- meepmorp 5y ago
  GPRS is the mobile data standard for GSM mobile phones. It's from the 2G era, and is old and slow. GEA-1 is an encryption algorithm used with GPRS.
  - gentleman11 5y ago
    So it’s no longer in use?
corty 5y ago
The real interesting question is the proprietary crapto in 4G and 5G. How long until that backdoor is proven?
efitz 5y ago
Why the heck don’t consumers have a seat at the table while all the 5G technology is being developed? I want open protocols and publicly documented cryptosystems based on published protocols. Instead we are just enabling the surveillance state.
- oneplane 5y ago
  Because of money and or mix of politics and imagined power. In addition, the systems are vast and complex, too big for one person to capture and understand. This means you get into the area of design teams, business teams, politics and geo stuff by default. Even re-implementing the specification (or most of it) in FOSS is extremely hard, and that's with all the information being publicly available. Designing it is an order of magnitude harder. Besides the systems in isolation, we also have to deal with various governments, businesses, and legacy and migration paths in both cases. Ironically, because all of this and the huge amount of people involved, consumers _are_ involved in this. It's not like the GSM, 3GPP etc. don't use their own stuff.
- mindcrime 5y ago
  I want open protocols and publicly documented cryptosystems based on published protocols. Instead we are just enabling the surveillance state. I think you just answered your own question.
  - Pokepokalypse 5y ago
    we don't tend to vote in our own best interest; whether it's politics, or economically.
- gruez 5y ago
  How does "open protocols and publicly documented cryptosystems" help when the carriers are mandated by law to have backdoors so they can fulfill "lawful intercept" requests? You're better off treating it as untrusted and using your own encryption on top (eg. Signal).
  - 5y ago
this_user 5y ago
All of the GSM algorithms were weak, and deliberately so. It is well known that the French wanted it that way, while the German side wanted a bit more safety on account of the ongoing Cold War. So compromises like the infamous A5 algorithm were created whose security was mainly based on the algorithm itself being kept a secret - the cardinal sin of cryptography.
- raxxorrax 5y ago
  I think stripping government from the ability to influence cryptography was a very important step. They try to get access again, so the fight is far from over. Those government that did probably violated their own laws, we deal with criminals here.
usrusr 5y ago
Post Showden this hardly qualifies as a smoking gun surprise, but it's nice to see a concrete example identified and examined. It's like nearfield archaeology, the difference between reading accounts of the use of greek fire in some antique battle vs finding identifiable remains of the manufacturing process.
Merrill 5y ago
At the time when digital cellular was first designed, the main objective was to design sufficiently strong authentication to stem the rampant theft of service then occurring on the analog cellular systems. In the US this was estimated at roughly $2 billion/annum. Encrypting traffic for privacy purposes was less important. Prior analog cellular telephony systems were unencrypted, as were analog and digital wireline services. Thus, the privacy cryptography was intended to be strong enough to make it a little more inconvenient/expensive to eavesdrop on digital cellular than it was on analog cellular or wireline services without significantly impeding law enforcement.
- userbinator 5y ago
  You make very good points. End-to-end encryption was never the goal for cellular networks in the first place.
  - MikeUt 5y ago
    It may not have been the goal of governments or telephone companies, but I'm sure users would have appreciated it. There's a reason this was done so discreetly.
Cadwhisker 5y ago
For those who don't know what GEA-1 or GEA-2 is, it's used in mobile phone traffic. There's a clearer write-up of this discovery and its implications here: https://www.miragenews.com/a-backdoor-in-mobile-phone-encryption-from-90s-578914/ https://www.miragenews.com/a-backdoor-in-mobile-phone-encryp...
Phemist 5y ago
The paper mentions a reference implementation of the GEA/1 / GEA/2 was used to generate the keystream data, but does not mention how to get a hold of this. Does anyone here know? Or am I correct in assuming the implementatiom is kept under pretty heavy lock due to its proprietary nature?
jibanes 5y ago
makes me wonder about GEA/3, GEA/4 and GEA/5.

487 points by anonymfus 5y ago

aliasEli 5y ago

These algorithms are pretty weak but can still be used for securing the communications with current phones.

daveguy 5y ago
If the security level is artificially limited to 40 bits as the article suggests, then it is not good for securing any communications. It was relatively easy to crack DES-56 at rest before the turn of the century. A teraflop machine can defeat 40 bit encryption on the order of seconds. Edit: fixed the incorrect "RSA-56" encryption. Thanks graderjs.
- graderjs 5y ago
  I think you might mean DES-56, or RC5, but not RSA.
  - jhgb 5y ago
    I imagine that technically RSA-56 would be easy to crack as well.
  - axoltl 5y ago
    To be fair you could probably break 56 bit RSA with a pen and paper.
    - graderjs 5y ago
      Pen and paper? I doubt it. You're welcome to try (show working ;p ;) xx) here's a sample RSA-56 problem I created for you: 39551945224675453 (56-bit semiprime)
  - daveguy 5y ago
    Yes, good catch. I did mean DES-56. I got the encryption name confused with the company that issued the challenge. The RSA algorithm is completely different.
meepmorp 5y ago
Also, note, GEA-2 doesn't seem to have the same kind of key weakening. I have no idea about the relative prevalence and configurability of those algorithms in the wild, though.

weinzierl 5y ago

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.

slownews45 5y ago

Too many coincidences for this to be by chance. IBM had Commercial Data Masking Facility which did key shortening to turn a 56 bit cipher into a 40 bit one. Now we've got this weird interaction which similarly reduces key length. Seems pretty obviously intentional?

fragbait65 5y ago
I agree, it is probably intentional, but I think it remains to be proven that it was malicious? Maybe 40 bit was seen as sufficient at the time, but are there any engineering reasons to actually shorten the key intentionally, does it improve the transfer rate in any way? I can't think of any, but I'm no expert, so maybe somebody else can chime in?
- raphlinus 5y ago
  Depending on your definition of "malicious," I think it clears that bar. The problem is not making a good-faith argument that 40 bits was sufficient (which was done for some extent for export-approved 40 bit SSL), but that it misleads people into believing that it's 64 bit encryption while it only has 40 bits of strength for people who are in on the backdoor. And as far as the other half of your question, no, there's no possible benefit (other than to the backdoor owners) from a smaller keyspace, as it goes through the motion of encrypting with the larger one.
  - fragbait65 5y ago
    Thanks for the explanation!
  - deleted 5y ago
    [deleted]
- slownews45 5y ago
  At the time 40 bits was not considered a backdoor, it was considered a weakness that would allow folks like NSA (with big budgets and intercept capabilities) to wiretap the way they had other communication approaches. Some situations, rather than designing new codecs, they would just weaken key gen side. The IBM effort there was public to allow for easier export, but also an approach that could be used to hide the weakness which in other settings may have been beneficial. It's possible however that folks involved understood what was going on to a degree but that it was seen as necessary to avoid export / import restrictions. More recently I think places like China ask that the holders of key material be located in country and make the full keys available or accessible to their security services. Not sure how AWS squares that circle unless they outsource their data centers in China to a third party that can then expose the keys for China to use.

nimish 5y ago

It should not be surprising that a system that is subject to lawful intercept requirements has weak encryption, especially pre-lift of the export ban.

mytailorisrich 5y ago
This is really to intercept over the air (so not necessarily for fully 'legal' intercept but also intelligence services). If law enforcement needs to wiretap a specific phone/SIM they only need to request it to the operator. Over-the-air encryption is irrelevant. Nowadays operators can duplicate all packets and send copies to law enforcement/security services in real time so that they can monitor 100% of a given phone's traffic from their offices.
- cs2733 5y ago
  Exactly, this is for third party access or at least I've assumed for a long time all communications using standard tools have always been open for scrutinity. It's nothing new either - for as long as there is postal service your mail could be open by order of this or that government oficial. Not even the Pony Express was immune to that ;-) If you want greater secrecy do like the paranoid intel community has been doing since at least the cold war and exchange messages on seemingly disconnected channels - say 2 different newspaper columns, wordpress blogs or even websites made to look like robot-generated SEO spam, using code that was previously agreed in person, with everyone keeping hardcopies if necessary.
ganzuul 5y ago
It was supposed to take 6 hours using Finland's fastest supercomputer at the time. So said my professor.

gentleman11 5y ago

Pardon my ignorance, what is gprs and GEA-1 and what is it’s significance?

ronsor 5y ago
GPRS is the general packet radio service, used for (very slow) data and SMS transfer in combination with the old GSM protocol.
- gentleman11 5y ago
  So, it encrypts sms messages and is still in use?
  - giantrobot 5y ago
    It doesn't encrypt SMS. It's over the air encryption for packet data (not calls or SMS) like WEP or WPA on WiFi. On GSM networks SMS was transmitted in leftover signaling space on voice circuits.
    - secondcoming 5y ago
      RACH: https://en.m.wikipedia.org/wiki/Random-access_channel https://en.m.wikipedia.org/wiki/Random-access_channel
    - ronsor 5y ago
      IIRC "SMS over GPRS" was an optional extension
meepmorp 5y ago
GPRS is the mobile data standard for GSM mobile phones. It's from the 2G era, and is old and slow. GEA-1 is an encryption algorithm used with GPRS.
- gentleman11 5y ago
  So it’s no longer in use?

corty 5y ago

The real interesting question is the proprietary crapto in 4G and 5G. How long until that backdoor is proven?

efitz 5y ago

Why the heck don’t consumers have a seat at the table while all the 5G technology is being developed? I want open protocols and publicly documented cryptosystems based on published protocols. Instead we are just enabling the surveillance state.

oneplane 5y ago
Because of money and or mix of politics and imagined power. In addition, the systems are vast and complex, too big for one person to capture and understand. This means you get into the area of design teams, business teams, politics and geo stuff by default. Even re-implementing the specification (or most of it) in FOSS is extremely hard, and that's with all the information being publicly available. Designing it is an order of magnitude harder. Besides the systems in isolation, we also have to deal with various governments, businesses, and legacy and migration paths in both cases. Ironically, because all of this and the huge amount of people involved, consumers _are_ involved in this. It's not like the GSM, 3GPP etc. don't use their own stuff.
mindcrime 5y ago
I want open protocols and publicly documented cryptosystems based on published protocols. Instead we are just enabling the surveillance state. I think you just answered your own question.
- Pokepokalypse 5y ago
  we don't tend to vote in our own best interest; whether it's politics, or economically.
gruez 5y ago
How does "open protocols and publicly documented cryptosystems" help when the carriers are mandated by law to have backdoors so they can fulfill "lawful intercept" requests? You're better off treating it as untrusted and using your own encryption on top (eg. Signal).
- 5y ago

this_user 5y ago

All of the GSM algorithms were weak, and deliberately so. It is well known that the French wanted it that way, while the German side wanted a bit more safety on account of the ongoing Cold War. So compromises like the infamous A5 algorithm were created whose security was mainly based on the algorithm itself being kept a secret - the cardinal sin of cryptography.

raxxorrax 5y ago
I think stripping government from the ability to influence cryptography was a very important step. They try to get access again, so the fight is far from over. Those government that did probably violated their own laws, we deal with criminals here.

usrusr 5y ago

Post Showden this hardly qualifies as a smoking gun surprise, but it's nice to see a concrete example identified and examined. It's like nearfield archaeology, the difference between reading accounts of the use of greek fire in some antique battle vs finding identifiable remains of the manufacturing process.

Merrill 5y ago

At the time when digital cellular was first designed, the main objective was to design sufficiently strong authentication to stem the rampant theft of service then occurring on the analog cellular systems. In the US this was estimated at roughly $2 billion/annum. Encrypting traffic for privacy purposes was less important. Prior analog cellular telephony systems were unencrypted, as were analog and digital wireline services. Thus, the privacy cryptography was intended to be strong enough to make it a little more inconvenient/expensive to eavesdrop on digital cellular than it was on analog cellular or wireline services without significantly impeding law enforcement.

userbinator 5y ago
You make very good points. End-to-end encryption was never the goal for cellular networks in the first place.
- MikeUt 5y ago
  It may not have been the goal of governments or telephone companies, but I'm sure users would have appreciated it. There's a reason this was done so discreetly.

Cadwhisker 5y ago

For those who don't know what GEA-1 or GEA-2 is, it's used in mobile phone traffic. There's a clearer write-up of this discovery and its implications here: https://www.miragenews.com/a-backdoor-in-mobile-phone-encryption-from-90s-578914/ https://www.miragenews.com/a-backdoor-in-mobile-phone-encryp...

Phemist 5y ago

The paper mentions a reference implementation of the GEA/1 / GEA/2 was used to generate the keystream data, but does not mention how to get a hold of this. Does anyone here know? Or am I correct in assuming the implementatiom is kept under pretty heavy lock due to its proprietary nature?

jibanes 5y ago

makes me wonder about GEA/3, GEA/4 and GEA/5.