"Death Knell" for GPRS and GSM encryption, which was already considered widely broken in many different ways in practice, this just adds one to the pile.
I would like to know why encryption designed in the 80's has failed so spectacularly despite claims that it would take "longer then the age of the universe" to break...
Were experts naieve about the progress of computation? Can we trust experts now that claim data is mathematically protected in a way unbreakable for millions of years?
The “age of the universe” estimate typically refers to how long it would take to brute force a cipher, i.e. try all possible decryption keys until a valid key is found. Such attacks are almost never practical because we can’t wait that long. So thinking of encryption this way, comparing encryption algorithms by their brute force resistance, is fairly useless. Instead, most real-world attacks rely on implementation flaws and side-channel attacks, which allow an attacker to make an educated guess or even avoid having to guess in the first place. These vulnerabilities can’t be so easily quantified in terms of how long it will take to break, which is why most algorithms don’t talk about it much in their advertising, even though ease of implementation and side-channel resistance are some of the most important attributes.
However, there are algorithms that do make a concerted effort to mitigate these problems and advertise themselves as such, such as Ed25519.
GSM is the first (civilian) cellular system to have any encryption at all. The fact that all the primitives are broken comes from the fact that all of them are custom and optimized for hardware implementation on for the time very resource constrained device, also the design predates the open cryptology research community and thus there were not many existing primitives that could just be used unchanged (one can imagine specifying something derived from DES as A3 and A8, but that is moot as the Comp128 in the spec is only an recommendation and these can be freely chosen by the network, I believe most current SIMs use somewhat convoluted algorithm based on AES and SHA256 as that is what is used for EPS-AKA procedure in LTE). As for the authentication being unilateral, nobody probably expected that to be a problem. And the weird way how the A5 stream cipher is used to encrypt the radio frames (which do not have cryptographic authentication, except the fact that what gets encrypted are FEC symbols, not the raw data) shows that the designers were somewhat familiar with military encryption systems, which often have similar availability-vs-authenticity tradeoff.
And well, given the track record of AES, we can probably consider AES secure for foreseeable future. And for many other modern symmetric algorithms (Salsa/ChaCha, Keccak…) one can produce quite believable arguments that they are as secure as AES.
Apart from the one-time pad or something equivalent, I don't think anybody can fully guarantee (to the point of mathematical proof) that any particular encryption is mathematically unbreakable. The existence of true one-way functions is technically an open question in the first place.
And even if you make the (probably reasonable) conjecture that one-way functions do in fact exist, there's still a lot that isn't known about the fundamental computational hardness of various problems used for encryption.
Most statements about the strength of particular encryption methods are educated guesses based on current mathematical understanding. Some particular encryption may be unbreakable for millions of years assuming no breakthroughs in mathematics that would allow significant shortcuts in breaking the cipher. For some mathematical problems those breakthroughs may seem more likely than for others.
Would be glad to hear if someone with current understanding of cryptography has more insight, though.
Obviously cryptographers were not naive about future technology. One example that comes to my mind is this: in a 1981 paper discussing Triple DES, the authors state: “A generalized meet in the middle attack would then require 2^112 operations and be well beyond the foreseeable technology for at least 50 years, and possibly forever.” - Merkle, R. and M. Hellman, "On the Security of Multiple Encryption", Communications of the ACM, vol. 24, no. 7, pp. 465–467, July 1981
While I would not count on any Triple DES encrypted data remaining secret forever, their other prediction has held up for the time being – 2^112 operations is still completely out of reach 43 years later. Of course there are other ways to attack TDES and it is rightfully considered obsolete.
That was publicly and openly stated by a Nokia researcher during a local university guest lecture in the late 90s. He also strongly implied that wired traffic between base stations was specified to be plaintext for easy wiretapping.
> . Could a public encryption standard be made secure enough to protect against everything but a massive brute force attack, but weak enough to still permit an attack of some nature using very sophisticated (and expensive) techniques?
And this, I believe, is the main reason crypto algorithms are usually broken after 20 years. They were designed to be breakable with very expensive tech, and over time that tech gets cheaper and 20 years later it's within reach of phd students and it gets broken.
If it weren't designed with deliberate weakness, some crypto might still have design or implementation flaws, but the majority would last thousands of years since the underlying math its based on doesn't suddenly get weaker.
Note that this applies to A5/2; the stronger A5/1 took much longer to break, and this is an attack on A5/3 which was backported from 3G (UMTS) to GSM/GPRS.
