Cracking the GPS Galileo Satellite

Glyn writes "Newswise is reporting the the encryption in the Galileo GPS signal has been broken. The pseudo random number generator used to obscure the information stored in the Galileo GPS signal has been broken. From the article: 'Members of Cornell's Global Positioning System (GPS) Laboratory have cracked the so-called pseudo random number (PRN) codes of Europe's first global navigation satellite, despite efforts to keep the codes secret. That means free access for consumers who use navigation devices -- including handheld receivers and systems installed in vehicles -- that need PRNs to listen to satellites.'"

Comments

Offtopic but....

[rolfwind]

Afraid that cracking the code might have been copyright infringement, Psiaki's group consulted with Cornell's university counsel. "We were told that cracking the encryption of creative content, like music or a movie, is illegal, but the encryption used by a navigation signal is fair game," said Psiaki.

Sigh, how did READING the bits on your own CDs/DVDs ever become illegal? Freedom of speech implies a freedom to read what you want. (Yes, I understand the DMCA, but I'm still in shock - I always considered laws making it illegal to read "signals", etcetera "not intended for you" very British but very unAmerican. And I say British because I'm getting those quotes from British laws circa WW2 and probably before.)

Props to Cornell.

Get your filthy American hands off our data!

[Anonymous Coward]

If a European tried doing something like this with a US GPS satellite, they'd get arrested for being a terrorist long before they had chance to write a paper on it.

Re:uncrackable encryption

[Groo Wanderer]

"But anyway, there is no such thing as an encryption scheme that cannot be cracked. It is just a matter on how much time it will take to crack it.
Encryption will always be crackable, we are just playing with the fact it would take 512 or so years to crack a particular scheme with the actual technology."

Actually, there is almost no encryption scheme that can stand up for a weekend to the 'suitcase full of cash' cracking methodology.

                -Charlie

Legal second opinion (from an engineer)

[justthisdude]

I'm no big fan of copyright, but I think Cornell needs a better lawyer. Clearly, no one can copyright a location (although this would make for a great scene: "Where am I?" "I can't tell you; it's copyrighted." I bet Dick Cheney is already drooling, but I digress). What they are protecting is the output signal from their satellites' atomic clocks, and measurements of their exact orbits. A mobile device computes its own position by comparing path delays to themselves from many satellites' known locations. The timing signal and satellite ephemeris are creative content that can be protected just like a map or satellite picture can be copyrighted, while the location depicted isn't. TFA compares decoding the timing signal to looking at a lighthouse and deducing your own position, which is clearly free. That same arguement would support decoding satellite signals of CNN to deduce world events. World events are clearly free, but the video isn't.

A stronger arguement can be made: since they have agreed to make the codes open source they have no right to enforce copyright. You just can't say they aren't creating anything.

Re:uncrackable encryption

[SillyNickName4me]

2^128 is a very big number. If the entire planet was turned into a vast computer with circuits an atom across it would take longer than the life of the universe to break an AES key by brute force.

First of all, yes, 2^128 is a very big number indeed. The rest of your statement however makes absolutely no sense whatsoever.

The size of a computer and the circuits within have little to do with how capable that computer is of performign the specific operations for breaking AES efficiently. Neither does your statement take into account the potential of weaknesses in the algorithm that might eliminate part of the keyspace. Do I have proof of such weaknesses? Nope, but the question is if I need that, the large majority of algorithms turns out to have such flaws. so unless you have mathematical proof that they do not exist in this case, the assumption that they exist is a safe one.

I vaguely remember people arguing that breaking DES was not feasable only some 25 years ago, and at the time they were probably somewhat right. Yet, nowadays it is breakable in hours by the kind of technology that private civilians can afford.

So all in all, it is safe to assume that AES is safe for the moment, but there is no telling what future technology will do. The likelyhood however is that both a breach of AES will be found, and hardware will be made that makes the AES problem relatively simple to solve.

Re:uncrackable encryption

[nojayuk]

"...the cluelessness of the Gallileo business model. Charging for something someone else is giving away is so 1990s. It only makes sense if there is something going on here we have not been told about."

Galileo makes high-precision access available to paying customers, the US NAVSTAR reserves that level of accuracy only for US and allied military systems. Some of the Galileo cluster will orbit at higher inclinations than the existing NAVSTAR cluster, making GPS more usable in the far North and far South (although I understand some planned future NAVSTAR satellite deployments will fill in the gaps here too). Galileo can't be switched off or degraded on a whim by a single government unlike the NAVSTAR system, allowing it to be trusted to control civilian aircraft in crowded skies.

The users of GPS will end up with multi-function receivers that can work interoperably with NAVSTAR and Galileo since it would be pointless commercially to do otherwise. Unless NAVSTAR goes commercial or the DoD stops degrading the signal the high-precision customers like airlines and such will use Galileo and pay for the convenience and predictability.

Re:uncrackable encryption

[NormalVisual]

Unless NAVSTAR goes commercial or the DoD stops degrading the signal the high-precision customers like airlines and such will use Galileo and pay for the convenience and predictability.

Selective availability (intentional degradation) was turned off on the Navstar system back in 2000, although there's nothing that says it won't get turned back on again sometime in the futures. In addition, differential GPS transmitters cover a large portion of the U.S., and DGPS is quite a bit more accurate than the data you get directly from the satellites, and works even when selective availability is active.

Re:uncrackable encryption

[Anonymous Coward]

And before you go running off to make a patent, white papers exist on the internet dating back to 1990 on using One Time Pads for internet/computer authentication mechanisms. And the fact that I wrote all this up here also serves as prior art.

This is laughable. You are trying to use the only perfectly secure encryption scheme, while breaking the rules which allow it to be the only perfectly secure encryption scheme.

So your mechanism is only as secure as the weakest parts, which in this case is plain text email or maybe SSL encrypted email, in which case, just use SSL and have the user provide their own strong password. You are getting NO GAIN for something which is MORE of a PAIN.

BTW, specifically in regards to GSM mobile phones (I don't know about others), GSM phone crypto uses a small Linear Feedback Shift Register configuration (40bit equivalent) for Pseudo Random Number Generation. To make matters worse, it is seeded (partially or fully?) with the IMEI number of that phone. IMEI numbers can be broken down a great deal if you know the make of the phone and then more if you know the model. The bit depth of IMEI suddenly drops. In 1999 GSM could be cracked in less than a second on a basic home PC. In addition to that, I personally know of a GSM eavesdropping/recording device being used outside of government/law-enforcement and I also know of someone who makes a similar device which is separate from the other I have mentioned. GSM at least, can hardly be considered to be providing strong comms. GSM crypto only "protects" the wireless link between the mobile phone and base station, NOT the wired link between cells or landlines, etc, so you trust your Telco? BTW, do you trust the French? This is their crypto scheme (A5) and they intentionally made it weak. Germany, try as they might, being so close the then Soviet Union, wanted it to be strong. The fact is, most governments don't want their people having strong crypto and you are essentially providing nothing.

Why bother? You are taking the strengths of OTP, weakening them to something ranging from plain text to strengths we already have (SSL) and yet you are keeping the impracticalities of OTP. I have to wait to have my password broadcast to the World before I can log in? What exactly are you providing again?

Really, why bother?

Hate to make a plug for myself but I came up with a one time pad authentication method for logging into websites. It's as secure as can be socially accepted. Key words there.

Every single time, in the past 11 years or so that I've been into crypto and crypto forums, that I heard someone say something like, "I think I have a good scheme", it has turned out to be a complete joke. I now get a chuckle whenever I read something like that, before I go on and read the "good scheme". So thank you for the chuckle. By the way, you can't have prior art when someone before you has it. It's not yours, it's thiers. Even if it does suck.

Re:How about the US GPS encrypted channels?

[Vreejack]

NAVSTAR encryption serves two purposes, reduction of precision for outsiders and anti-jamming. Bill Clinton removed the precision constraints, but the anti-spoofing/jamming codes are changed very often.

Two caveats: the anti-jam/spoof feature can improve reception in areas of high interference caused by physical geometry (reflective surfaces, for example), and the US gov. can always cripple precision in local areas if it wishes (e.g., Baghdad).