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]

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.

Encryption

[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:Galileo != GPS

[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]

much ado about nothing

[tonigonenstein]

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]

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.

Re:Galileo != GPS

[Tugrik]

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

What about firmware upgrade ?

[i-neo]

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 ?

Re:Galileo != GPS

[HuguesT]

Actually NAVSTAR is not the only one available. The Russians also have a satellite navigation system called GLONASS [wikipedia.org]. GLONASS is purely military, AFAIK, but has been in operation since the 80s.

Re:Amateur Galileo receiver?

[HuguesT]

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.

 

Well, don't forget the third "GPS"

[Tavor]

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:uncrackable encryption

[Anonymous Coward]

Nobody is giving sub-meter precision away. The US GPS only provides that kind of precision to its military users. Sub- meter precision with the civilian GPS codes requires differential GPS, which needs fixed receivers and transmitters in relatively close proximity, so it can never cover the whole world.

Imagine...

[Cinquero]

Imagine working for years and noone is paying you.

So much about the lighthouse bullshit.

Suckers.

Re:uncrackable encryption

[YGingras]

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.

Are you really that clueless? I would not take 512 years to bruteforce a 320 bit key, it would take simply longer than the current age of the universe. Assuming of course that you are required to put a single computer per square centimeter of our planet surface (including oceans) and that you can't use more than one planet. The math is simple: the surface [wikipedia.org] is about 5.1e18 cm^3 and there is about 4.0065e38 keys to try [wikipedia.org] before you get your answer.

With limits on the speed of light you can only do so many operations per second but lets assume all your boxen are 100GHz custom built and that they can try a key per cycle. You'd need about 1.069d11 years to crack the key. Now do your homework and check how old the universe is.

Here is how I computed it:
(let ((keys (* 1.1774 (sqrt (expt 2d0 320))))
            (boxen (* 510065600.0 (expt 1000 2) (expt 100 2)))
            (cycles (* 100 1d9)))
    (/ keys boxen cycles 3600 24 365))

Play with the params and see how excesivly secure a 512 bit key would be.

Re:uncrackable encryption

[Gorath99]

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:Encryption

[FireFury03]

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.

Re:Never Understood the Logic of Galileo

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

Re:uncrackable encryption

[YGingras]

Asymmetric schemes like RSA are a lot easier to crack than 3DES and other symmetric. A solid scheme would use very large (~4096 bits) asymmetric to exchange a symmetric key. If that sounds like SSL, well now you know why.