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.'"

Galileo != GPS

[matt4077 (581118)]

Galileo is the European System, GPS is the American. "GPS" is kind of generic, so I guess it's going to be the name for the whole category, but I'd be nice if we could use something different to distingish between "some" GPS and the "American" GPS.

Re:Galileo != GPS

[by Anonymous Coward]

> I'd be nice if we could use something different to distingish between "some" GPS and the "American" GPS.

There is: the "American GPS" is named NAVSTAR according to this site [kowoma.de]

Well, don't forget the third "GPS"

[Tavor (845700)]

Not many people remember it, but there was a third competing system for Global Positioning.
GLObal NAvigation Satellite System [wikipedia.org]
Started by the Soviets, cont. by the Russian Federation, and now with India on board,it is expected to be fully operational again in 2008. (Like all things expected to be complete in 1991, the money situation made them push it back further than Vista.)

Re:Galileo != GPS

[Tugrik (158279)]

If you want to get technical, the "American" system is called NAVSTAR GPS, which stands for NAVigation Signal Timing And Ranging Global Positioning System.

Re:Galileo != GPS

[Professor_UNIX (867045)]

I'd be nice if we could use something different to distingish between "some" GPS and the "American" GPS.

To paraphrase Michael Bolton, "Why doesn't he change his name, he's the one that sucks!"

Encryption

[by Anonymous Coward]

AFAIK the PRNs are not really encryption keys. They're merely a technical detail that can be kept secret. GPS and Galileo are spread spectrum applications and the PRNs define the way the signal is spread. If you don't know the spreading function, you can't tell the (unencrypted) signal from the noise. It's really security by obscurity.

Re:Encryption

[FireFury03 (653718)]

It's really security by obscurity.

It's not really intended to be security anyway - everyone knows the normal NAVSTAR, WAAS and EGNOS PRNs (you have to in order to use the services) - the PRNs are used to differentiate between individual satellites, which all transmit on the same frequencies. I guess they just decided not to publish the Galileo PRNs until they'd got further into the project.

Offtopic but....

[rolfwind (528248)]

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.

much ado about nothing

[tonigonenstein (912347)]

The article is inacurate and makes a big deal about nothing (BTW did you notice it was written by a guy from Cornell ?) First, Galileo is not ready yet. The article claim they plan to charge for the keys. This is plain wrong, the base precision signal (which is the one we are talking about) will be available free of charge. The system is simply in testing phase right now and they don't want anyone playing with it, that's all. Second, this PRN sequence is not supposed to be difficult to crack at all, since it will actually be made public in time. This is in no way an achievement. It is was the high precision signal, this would be another matter.

Two Interesting Points

[FrankDrebin (238464)]

1. The Cornell team anaylzed signals from a demonstration satellite that by itself is not useful for navigation, and according to the documentation transmits the same power-envelope, but not the same PRN's, as the operational system.
2. According to Cornell's lawyers, the DMCA was not a concern because navigation data is not, and cannot be, copyrighted.

Get your filthy American hands off our data!

[by 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.

What about firmware upgrade ?

[i-neo (176120)]

Cornell demonstration is pretty useless.

First Galileo is only in testing phase, therefore nothing tells you the signal encryption they are using is the definitive one. I would rather think they are testing and they don't care if someone is getting it.

Second have you ever heard of firmware upgrade ? I guess encryption will be updated when the satelites will be in production, and there will not be any problem since it is not being used in any device yet.

Thank you Cornell people for this useless article. Another Cornell box ?

Algorithm is being replaced

[joshua42 (103889)]

Acoording to a friend working on the Galileo project they came up with a new encryption algorithm specification a week ago. Quite annoying with such changes this late in the project, they thought. I guess this news kind of explains it.

Re:uncrackable encryption

[Groo Wanderer (180806)]

"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

Re:uncrackable encryption

[Gorath99 (746654)]

I fact, that is pretty much the only attack that will work against a correct implementation of OTP [wikipedia.org], an encryption scheme that actually is unbreakable (though rather unpractical for most applications).

Re:uncrackable encryption

[Nutria (679911)]

I fact, that is pretty much the only attack that will work against a correct implementation of OTP

Rubber-hose decryption works well, too.

Re:uncrackable encryption

[arivanov (12034)]

So does Sodium Pentothal though sometimes there are decryption errors. If there is more time there is a guaranteed decryption scheme known as "heroin once a day for a week, followed no more heroin until you tell the key".

Re:uncrackable encryption

[Gorath99 (746654)]

Actually, there is no way to proof there is an encryption scheme that cannot be cracked.

There isn't? Proof it! ;-)

Seriously, there are ways. The reason most encryption schemes can at least be brute forced is that for any given ciphertext, there are very few possble sensible (non-garbage) plaintexts. So, if you try all possible keys and look at all the resulting plaintexts, the one that is sensible will almost certainly be the original plaintext.

With OTP this won't work as there is a simple proof that for any given ciphertext, every single message of the same lenght is a possible plaintext. So if you have a ciphertext of 1k characters and you try every possible key, you'll end up with every possible text of 1k characters. This includes bits of Shakespeare, Britney Spears porn, texts describing who killed JFK (at least one of which will be amazingly be true :-) ), quotes from the Bible, excerpts from the linux code and much, much more. There's no way of knowing what was the original message.

Oh, and since you'll end up with 256^1000 messages of 1k length, you'll need a bigger harddisk ;-)

Re:uncrackable encryption

[by 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 [lycos.com] 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:uncrackable encryption

[SillyNickName4me (760022)]

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 (567177)]

"...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 (565491)]

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:Amateur Galileo receiver?

[HuguesT (84078)]

Yes, you are missing the fact that there is only one Galileo satellite in orbit right now, and this one doesn't include all the technology that will make Galileo an interesting system, namely the high-precision onboard atomic clock. In all generality you need timings from at least 4 different satellites visible from everywhere to be able to locate a point in 3D. This means about 12 at a base minimum must be in orbit for the system to be useful. The final system will have 30.

The current sole Galileo system in orbit is a test system. The final systems will be significantly different.

 

Re:How about the US GPS encrypted channels?

[Vreejack (68778)]

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

Re:Never Understood the Logic of Galileo

[by Anonymous Coward]

It's obvious that the EU will force all mobile phones, cars, planes, etc. sold in Europe to use Galileo. The free market would never adopt a new alternative that is not technically or functionally superior, is going against an entrenched competitor with a huge install base, and costs money where the alternative is free.

You need to check your assumptions.

The EU doesn't mandate GPS/Galileo in anything. The US does.

Galileo is functionally superior. The free precision will be better than with just GPS.

There is no installed base in high precision applications because there is no product on the market. Only the US military has global high precision positioning.

Galileo's normal precision code will be free, just as the base level precision of GPS is free.

Galileo's high precision code will be available commercially, whereas the GPS high precision codes are not available to non-military users.

me-too project [...] A380

The A380 is not a me-too project. Americans only even know that name because it is a real threat to Boeing, who chose not to build a plane of that capacity. It's not someone else's plane, only slightly bigger, either. It's the continuation of Airbus engineering, which is very different from Boeing's.

In other words, we just added an entire China

Unfortunately for you, that "China" you added belongs to foreign investors.