Cracking the GPS Galileo Satellite 364
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 (Score:4, Informative)
Re:Galileo != GPS (Score:5, Informative)
There is: the "American GPS" is named NAVSTAR according to this site [kowoma.de]
Well, don't forget the third "GPS" (Score:5, Informative)
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 (Score:4, Informative)
Re:Galileo != GPS (Score:5, Funny)
Re:Galileo != GPS (Score:2)
Re:Galileo != GPS (Score:2)
I really hope you didn't intend this as an insult to Americans. As stated elsewhere, the American GPS is named NAVSTAR. Almost nobody uses the full name because for years and years the NAVSTAR GPS was the only one in existence. It isn't arrogance on the part of Americans as your statement seems imply; it's simply because for a long time the shorter term GPS was not ambiguous.
Re:Galileo != GPS (Score:3, Informative)
Re:Galileo != GPS (Score:2)
Use of the term "soccer" (as opposed to competing terms "socca" & "socker") dates from around 1890. The Princeton rules of American Football were formulated in 1867, the same year the American Football was patented.
Encryption (Score:4, Informative)
Re:Encryption (Score:2)
Apparently not obscure enough...
Re:Encryption (Score:2)
Whether it was intended to be used as such as part of Galileo is another question.
Re:Encryption (Score:2)
What is a PRNG if not a hash function? You hash each number in the sequence to get the next number. Since you don't want just anybody who knows the hash algorithm to be able to predict your sequence, you generate a longer than necessary number and only reveal part of it, keeping some of the bits secret. If Galileo was cracked, somebody must have figured out the secret bits as well as the function.
Re:Encryption (Score:2)
Re:Encryption (Score:2)
You must be wrong. It says so in the paper.
Re:Encryption (Score:4, Funny)
Re:Encryption (Score:5, Informative)
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:Encryption (Score:2)
No, it isn't.
A "security by obscurity" device is one that you can't tell how is it built and still use it as a "security device".
For instance "rot 13" is a "security by obscurity" device. Once you tell a cypher is made out "rotting13" a clear token, you are gone.
On the other hand, "Caesar's cypher" is not a "security by obscurity" device. Caesar's cypher, you know, is the general procedure which rot 13 is an special case. You can tell "this is cyp
Offtopic but.... (Score:5, Insightful)
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.
Re:Offtopic but.... (Score:2)
Re:Offtopic but.... (Score:2)
Strange that it is America that is forcing Britain to accept these laws
Re:Offtopic but.... (Score:2)
There is a really good article about DMCA in the current release of IEEE Spectrum, pointing out all the bad things that it introduced (no hardware DVD copiers, no digital VCRs capable of skipping ads, etc.)
As opposed to the psycho US country (Score:3, Insightful)
much ado about nothing (Score:5, Informative)
Re:much ado about nothing (Score:2, Insightful)
You're right, it can't be broken. Maybe they don't want to get sued during the test phase by some guy who drove his car in a trench because he was feeding his navigator with the Galileo signal.
Two Interesting Points (Score:5, Informative)
Re:Two Interesting Points (Score:2, Redundant)
There is no navigation data in the signal. Its a time signal/timestamp that gets transmitted.
The "logic" of your navigation system is inside the "box" in your car/ship/.. The box calculates the position depending on the timesignal.
If your system can't read the time signal you can not calculate your position.
If the time signal is encrypted it may become a DMCA matter in US. Would be nice t
Re:Two Interesting Points (Score:2)
Umm, so you're claiming that a timestamp can be copyrighted?
Re:Two Interesting Points (Score:2)
I don't happen to know what it is at the moment, but I must be given the copyright on it anyway because as we all know Property Rights Must Be Protected.
-
Re:Two Interesting Points (Score:2)
I think the cartographers would beg to differ on this count.
Re:Two Interesting Points (Score:2)
Not at all. It is not the geographically data itself that they get copyright on (or no one else could maka map of an area were you have copyright on your map). It is your expresion of that data into your specific map that you get copyright on. Anyone is free to make their own map (or whatever) based on the information on someone else map. They can't copy that specific map with its layouts and so on.
Deep pocket (Score:2)
Get your filthy American hands off our data! (Score:5, Insightful)
Re:Get your filthy American hands off our data! (Score:2)
They'd possibly get a medal in the east, loads of cash from certain people in the west.
Nope (Score:2)
Re:Nope (Score:3, Interesting)
This is not true (anymore). ISTR the sequence of events went something like:
Re:Nope (Score:3, Insightful)
I dare say that turning off or seriously degrading GPS would cause a few deaths too. That said, it wouldn't be the first stupid thing governments and millitaries have done. I would much prefer to get my positining data from a variety of sources, not just a single millitary system, that way no one organisation could decide to pull the plug. Also, ESA aren't millitary, so usi
Re:Get your filthy American hands off our data! (Score:2)
> for their own freedom just as much as they're ready to deny anybody else's, if
> needed. Shame on your country, a day will come when all this sick laws will
> screw you up for real internationally.
Don't confuse the "US People" with the "US Government". Less than half of the US voted becuase they're so disillusioned with all comers. Our sick laws screw us up at home everyday, why should we worry about it screwing us
Re:Get your filthy American hands off our data! (Score:2)
What about firmware upgrade ? (Score:5, Informative)
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 ?
NATTFA (Score:2)
(Not According To The FA)
The article says that the Cornell GPS group tried to get the information but failed, as did several other groups - so :
does not seem to apply. Furthermore, there are other parts of the article that hint that the signal encryption used is indeed the definitive one.
Now, as to the satellite/receiver firmware being updated - that is certainly always a possibility and nothing in the article contraindicates that.
Amateur Galileo receiver? (Score:3, Interesting)
Re:Amateur Galileo receiver? (Score:2, Funny)
Yep. There's only the one satellite, (a demo and a placeholder, a bit like Vista beta
Re:Amateur Galileo receiver? (Score:5, Informative)
The current sole Galileo system in orbit is a test system. The final systems will be significantly different.
How about the US GPS encrypted channels? (Score:4, Insightful)
Re:How about the US GPS encrypted channels? (Score:4, Interesting)
which is a pity -apparently it works better under tree cover than civilian GPS.
Re:How about the US GPS encrypted channels? (Score:2)
Re:How about the US GPS encrypted channels? (Score:5, Insightful)
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:How about the US GPS encrypted channels? (Score:2)
Isnt That Illegal? (Score:3, Insightful)
Given that these codes are in place to sell premium products to consumers and recoup the investment made with putting the satellites in orbit - how is this any different to breaking codes for satellite TV and/or DRM?
I really hope the folks at Cornell start working on something that would have a legitimate use such as the ability to make a backup of a legally purchased HD-DVD movie... oh wait... that would be illegal :-(
Re:Isnt That Illegal? (Score:2)
The Commercial Service, Public Regulated Service and Safety of Life Service all use different (more secure) encryption means.
Re:Isnt That Illegal? (Score:2)
Makes you wonder why they bother in the first place. Sounds like a lot of effort, infrastructure and middlemen to construct something that's obviously going to be bypassed very shortly. Ah, the middle men, that's where it came from....
Legal second opinion (from an engineer) (Score:4, Insightful)
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:Legal second opinion (from an engineer) (Score:2)
With that said, the very first thing they teach you in law school is "it depends"...everything in the law is a balancing act, and is subject to human judgement. Sometimes it's a very lopsided balancing act, but there's almost always room for argument.
Openly available signals (Score:2, Redundant)
You would expect it to work that way, but NO. Today, it really is possible to transmit information into publicly receivable media and still be able to prohibit the use of it and to do the research necessary to make the signal useful (
Algorithm is being replaced (Score:5, Interesting)
In practical terms (Score:2)
No i couldnt get to TFA to read it.
I don't understand (Score:2, Interesting)
Re:I don't understand (Score:2)
Re:and North Korean rocket scientists appreciate t (Score:3, Insightful)
Re:and North Korean rocket scientists appreciate t (Score:2, Funny)
*grin*
Re:and North Korean rocket scientists appreciate t (Score:2)
But they get the credit regardless of where their rockets land.
Re:and North Korean rocket scientists appreciate t (Score:2)
-- Werner von Braun (paraphrased by Tom Lehrer)
Re:and North Korean rocket scientists appreciate t (Score:2)
-- Werner von Braun (modified by Mort Sahl)
Accuracy not critical with nukes on soft targets (Score:3, Insightful)
Or, alternatively, you could just about hit here [google.com] with a trebuchet from North Korea, and there are 11 million people there.
North Korean nuclear strategy is likely to revolve around killing lots of people, not taking out hardened military targets with precision weapons. For that, accuracy me
Re:Accuracy not critical with nukes on soft target (Score:3, Interesting)
Actually, like most such strategies, North Korean nuclear strategy is most likely to revolve around not having to actually fire such weapons; if you at any point need to actually launch, you've already lost, they can only be used to make the enemy and the rest of the world lose too.
Taken to the natural conclusion, see the Dr Strangelove version of Doomsday Machine. No precision needed at all, and you dont even need a trebuchet.
Re:Accuracy not critical with nukes on soft target (Score:2)
The assumption is that the North Korean government is sane.
I seriously doubt any government that systematically starves its own people to death over a few decades would have any trouble watching the same people die in a "glorious" fire.
Re:Accuracy not critical with nukes on soft target (Score:4, Insightful)
Lol! I was just going to post a joke about how we are suppossed to believe the standard demonization that our enemy is a "madman."
I seriously doubt any government that systematically starves its own people to death over a few decades would have any trouble watching the same people die in a "glorious" fire.
You should doubt it.
Only in movies do insane people end up runnning countries. Letting the population starve is not a symptom of insanity - it is a symptom of a ruling class lacking accountability to the citizens.
The North Koreans are not insane, they just have a different perspective than the one our news media feeds us. Were Bush and Rumsfeld insane because they ignored counsel from the pentagon about how securing Iraq would require 2x-3x more troops than they wanted to allocate? No, they just saw the facts differently - incorrect they were, but not insane.
Same thing goes for North Korea's government. For example - they still consider themselves to be at war, no truce was ever signed - only an armistice which is just a little bit stronger than a "cease fire." To an American, 10,000 miles away, it sure seems like the korean war is over - but anyone who gets near the DMZ and sees the patrols on both sides (or has even just seen the movie Joint Security Area), it isn't so clear any more. North Korea has always felt like it needs to be prepared for an attack at any time and has thus kept its military at a full state of rediness.
North Korea has made a lot of dumb decisions, but that doesn't mean they are insane any more than Bush's (mis)handling of the war in Iraq means he is insane.
Re:Accuracy not critical with nukes on soft target (Score:2)
I guess you have a different definintion of sanity than I do.
I understand your point - that the two Kim's of NK are really more ruthless than anything - but their actions lead one to not trust in them when it comes to sensabilities that you and I have.
NK, IMHO will lob a nuke much more readilly than say china - even though China has killed millions more humans in the last 50 years. Russa as well - Stalin's purges killed 30 million or so, but there
Re:Accuracy not critical with nukes on soft target (Score:2)
Re:Accuracy not critical with nukes on soft target (Score:2)
Good to go!
I think the idea came from a lot of editorials. There were 2 Canadians and an upset cow, in a sling getting ready to go over the border. The quotes were 'Canadians develop weapons of mass destruction, that can be launched within minutes.'
Re:and North Korean rocket scientists appreciate t (Score:2)
Re:and North Korean rocket scientists appreciate t (Score:3, Insightful)
In wartime the US can, will and does turn off the GPS in the warzone. Galilieo isn't under the same controls, and for that reason is popular with some governments for their guided weapons programs. Further, the civilian GPS receivers still have certain height and velocity restrictions artificially put in by the US to prevent guided missile uses. Only recently was an ag
Re:and North Korean rocket scientists appreciate t (Score:3, Funny)
For the glorious leader! (Score:2)
uncrackable encryption (Score:2, Insightful)
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.
Re:uncrackable encryption (Score:5, Insightful)
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 (Score:5, Interesting)
Re:uncrackable encryption (Score:5, Funny)
Rubber-hose decryption works well, too.
Re:uncrackable encryption (Score:5, Funny)
Re:uncrackable encryption (Score:2)
Re:uncrackable encryption (Score:2)
Re:uncrackable encryption (Score:3, Interesting)
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.
http://www.tacocat.net/
The idea is to get your password sent to you by some method and upon successful authentication, the password is reset and retransmitted. The socially accepted part is sending the password to you in such a way that you'll actually be able to use it. The most common form of sending new passwords today is via e
Re:uncrackable encryption (Score:5, Insightful)
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 (Score:3, Interesting)
I was hoping that the website would explain this. Did you RTFM? Assuming you did not. The advantage that still exists is that OTP, even over SMS is much harder to intercept than standing behind someone at an airport kioske or sniffing wireless networks... I didn't say it was 100% secure, in fact I think I even make mention that it is still not perfect. But it's a hell of a lot better than common practice today.
I would think it would be preferred if someone would be willing to move
Re:uncrackable encryption (Score:5, Informative)
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
Oh, and since you'll end up with 256^1000 messages of 1k length, you'll need a bigger harddisk
Re:uncrackable encryption (Score:2)
That would be better rewritten as current technology and know-how. Obviously tech improves for instance, back in the 90's, nearly all attempts at cracking where based on a serial approach. Now, they are based on a distributed approach. In addition, the general algorythms that we know and use in the general public are almost certainly different than what other very targeted groups know and use.
Re:uncrackable encryption (Score:3, Informative)
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
Re:uncrackable encryption (Score:3, Informative)
Re:uncrackable encryption (Score:5, Insightful)
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 (Score:4, Interesting)
Security is the difference in access-pain for those with permisison vs. those without. Putting something where nobody can get to it is not ultimate security, thats no security at all.
As for the satellite, I presume the European one is offering more accuracy and that it can't be shut off by the US Government. Well not because they unilaterally decide to.
Also I'm surprised if anyone in US would be able to use this cracked satellite data in the US due to DMCA. But everyone else in the world can, lol.
Re:uncrackable encryption (Score:5, Insightful)
"...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 (Score:5, Insightful)
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:Encryption Doesn't Work (Score:3, Funny)
Re:Never Understood the Logic of Galileo (Score:5, Informative)
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.
what non-military use? (Score:3, Interesting)
a. standard GPS
b. standard GPS plus a differential signal (good for airport approaches)
c. carrier-phase (sub-centimeter but slow, for surveying)
I'll grant that differential signals can make airports easy targets.
For what are you needing the combination of precision, accuracy, fast measurements, and a location that hasn't been set up with a differential transmitter?
Re:Never Understood the Logic of Galileo (Score:3, Insightful)
I suppose a free market wouldn't, but it's hard to say, given how we don't really have a working model of a free market to study. Except perhaps the truly lawless places on the planet.
And that GDP growth you're talking about? It's gone mostly to the people who are already wealthy. To the average American that statistic is a lie.
Regarding job creation:
Re:Never Understood the Logic of Galileo (Score:3, Insightful)
1. Galileo is not just a copy of the GPS system. It has higher precision than GPS and so opens up new applications that simply aren't possible at the moment. It also works better in some countries where GPS simply doesn't work very well. In fact the two systems will coexist, and future receivers are likely to support both which will give even better accuracy.
2. The A380 isn't just a "me-too" project - there isn't a si
Re:Digital road tolling (Score:3, Insightful)
Ohh, those silly Europeans... that kind [engadget.com] of thing [blueoregon.com] would never [gpsworld.com] happen in the US [xpd8.net]!
Re:Digital road tolling (Score:2)
And as for a toll "for each kilometer a vehicle runs, in any road", we have taxes on gas for serve to mean a cost per kilometer/type of vehicle.
I'm aware of those objections to digital road tolling, and I agree with them. It doesn't