Slashdot Mirror
Feature:Obscurity as Security
0 Introduction With the popularity of the open-source mindset, a general contempt has drizzled upon all forms of obscurity. The concept of security through obscurity (STO) in particu lar has been decimated. Security through obscurity, which relies on the ignorance of attackers rather than the strength of defenders, is dead in all but practic e. The victory of the opposing full disclosure approach is so complete that proposed ta ctics die at the mere hint they are a form of STO.
This paper suggests security through obscurity can and does work in certain strictly limited ways, and should not be eliminated unthinkingly from the admin's arsenal. It further implies that the boundaries between STO and 'real' security are blurry and deserve evaluation. However, this paper in no way proposes obscurity as a method for keeping secrets in the long term.
1 Full disclosure does not apply to instantiated data Instantiated data - the data used by specific instances of an algorithm - do not fall within the scope of full disclosure. Were this not so, then even the simplest password would violate the ban on security through obscurity. Passwords are secrets known only to their creators, and password entry is commonly obscured, as in the case of the 'shadow' login of UNIX. While the login protocol may be open, passwords themselves are a form of STO, with obscurity localized in the password string.
Instantiated data are exempt from full disclosure because the risk from their failure is limited. When a script cracks a password, the damage done to the secure system extends only as far as that password's scope. The cracker cannot use the compromised string to gain power directly in another system, even if that system runs the same password protocol. Nor can anything be inferred about the value of one password merely from the value of another with equal or lower permissions.
A similar example of instantiated data obscurity is the private key that forms the basis of asymmetric cryptography. So obscure is this information that it is rare for even the owner to be familiar with its precise value. But such obscurity is a necessary element of modern security schemes. Strong security does not eliminate obscurity - rather, it localizes obscurity to instantiated data. The phrase in cryptology, 'carry all security in the key' might be better phrased 'carry all obscurity in the key'.
2 Full disclosure does not apply to time-limited secrets Secrets that expire after a short lifetime can be protected by a wider array of techniques than long-standing secrets. The defense of information that will be irrelevant in a matter of hours or days may not warrant fully peer-reviewed security. Consider the famous Navajo code-talkers of World War II. Among the Americans coordinating the at tack against Japanese-held islands in the Pacific were a number of Navajo Indians, who spoke a slangy version of the complex Navajo tongue. Commands from HQ were issued through these code-talkers, who encrypted and decrypted with an alacrity that belittled the automated methods of the day. This is an excellent example of time-limited security through obscurity. Secret languages are excellent security in the short-term, but however cryptic Navajo may be, it is a code subject to human betrayal. Use of Navajo against the Japanese much beyond the 3-year window of the war would have been unwise. But because the secrets of American strategy in the Pacific were irrelevant after the conclusion of the fighting, the long-term weakness of obscure Navajo as a security measure was unimportant.
3 Obscurity serves as a tripwire Perhaps the classic example of wrongheaded STO is the administrator who modifies his web server to listen on a nonstandard port - thereby confusing attackers, as the theory goes. Considering the degree to which tasks such as port scanning can be automated, the naivete of this defense seems plain. The cracker might be forced to check all 64512 unreserved ports, but eventually the concealed web server will be found. This appears to be a weakness of STO, but if manipulated correctly, it is in fact a great strength. Imagine that our same admin had also invoked a tripwire script and set it to listen on one or more unused ports. When the tripwire is probed with a SYN packet from a cracker trying to locate the web server, instantly the system goes to full alert. The packet is logged and the admin's pager sounds like an alarm.
Such tripwire approaches work because they do not expect obscurity to keep information hidden. Rather, they obscure information as a ploy to force invaders into showing their hand. Because the obscured implementation differs on each system, crackers must resort to guess-check scanning before attacks can commence. But tripwires are deployed throughout the system, anticipating this very move. Running an automated kit suddenly becomes a risky proposition, and even talented crackers must gamble on, for example, whether 'root' is really the name of the primary account or merely a hotline to the authorities.
Lighthearted implementations of this approach are a staple in the popular "Indiana Jones" films. In one scene, Jones is confronted with a hallway of lettered tiles, all seemingly alike. To cross safely he must step only on those tiles with letters corresponding to the secret word 'Jehovah'. The penalty for a misstep is to crash through the floor and plummet into a gaping pit. Attackers not privy to the password would find an exhaustive search less than optimal in this case. When traps are mingled with genuine data, STO can be a powerful disincentive. Such measures do not make a given machine resistant to breach in the long term, any more than medieval moats could ultimately protect their castles. But like moats, tripwire obscurity provides a critical buffer against attackers, allowing defenders room to breathe.
4 Asymmetric cryptography exhibits traits of STO Despite the notion that asymmetric cryptography such as RSA is 'real' security, in some aspects these methods resemble STO. Indeed, this entire class of cryptography is founded on the hopeful guess that a certain mathematical problem is intractable. The back door into cryptographic methods that rely on multiplying primes is, quite simply, to develop a swift means of factoring those multiples. This NP-time problem must be solved before a private key can b e derived from its corresponding public key, and the notorious difficulty of NP problems leads some supporters to characterize asymmetric cryptography as 'prova bly secure'. This is far from the case - there is uncertainty among mathematicia ns as to whether this problem will even prove non-trivial once approached from t he right angle. Startling progress has been made in solving similar 'impossible' problems using innovative ploys - for example, DNA computers can now solve the Traveling Salesman problem in linear time. Given that asymmetric encryption is used widely in the world's e-commerce infrastructure, the repercussions when this piece of obscurity is cracked are disturbing to contemplate.
One telling argument against STO is that it promotes a false sense of security, leading admins into complacency. But the complexity of asymmetric cryptography, combined with reports of its infallibility, can produce much the same effect. Co nsider this social-engineering exploit of digital signing. Using a tool such as m akecert, the cracker generates a root certificate with the name 'Verisign Class 1 Primary CA' and uses it to sign an end-entity certificate with the subject 'CN=Rob Malda, E=malda@slashdot.org' (CT:Please don't. I'm used to posers pretending to be me in Quake, but not on email ;) The cracker then sends the email to an enemy, using a client that does not validate e-mail addresses and spoofing the return address friendly name. The inexpert recipient, thinking all is in order and knowing that digital signatures never lie, trusts the root certificate and hence forth carries on a conversation with a false CmdrTaco. Only scrutiny of the headers will reveal the mail is actually going to a different address. The widely made claim that public-key cryptography is 'real' security and completely unrelated to 'false' STO delivers a more powerful illusion of security than anything an XOR'd password file can provide.
Even brute-force cryptanalysis has parallels in STO. Suppose we wish to conceal the passwords for a number of Swedish bank accounts. We resolve to write them to a secret location on our hard drive, perhaps a few unused bytes in a file sector. Only we, who know the lucky offset, can read the data. This form of concealment is a typical case of secruity through obscurity. The integrity of our secret depends on the ignorance of the cracker, and a trial of all 2^n possible locatio ns compromises the system. But in what way is this fundamentally different from the 'genuine' security of n-bit encryption? To break this form of security, 2^n keys are generated and tried agains t the cipher text until the result is a plain body. Is the difference between this 'true' security and the 'false' STO merely than n is considerably larger in encryption than in the case of hard drives? But this implies that our real error lay, not in reliance upon obscurity, but in having a hard drive of insufficient size!
5 Conclusions Security in the absence of obscurity is not strictly possible, but good systems both localize and advertise their points of obscurity. When the admin is fully a ware of the obscurity in a system, tripwires and instantiated data can provide a useful complement to more rigorous security techniques. Obscurity cannot keep information safe or concealed for long, but it can make attacks risky and destroy the effectiveness of automatic kits. These benefits should not be dismissed as an article of faith.
Turning off ICMP ping access to a host you want to keep hidden will usually ward off casual script kiddies. In this case, you're obscuring the fact that the machine exists at all.
However, this is always part of a larger overall scheme to keep intruders out.
I think this was a very informative article. I believe it brought out some points that I hadn't thought of before.
Alot of us here at /. don't know everything about security already. I am a programmer and I really like to learn new things. Slashdot isn't just news. It is whatever Rob wants to post. Thanks for the great essay.
geach
> DNA computers can now
> solve the Traveling Salesman problem in
> linear time.
The Traveling Salesman Problem is NP-Complete. If the DNA computers are able to solve it in linear time, P = NP, and the most important problem in Computer Science would be solved. I believe you meant: "DNA computers can now solve _some_ instances of the TSP in linear time, which is far different from your previous claim. There are, of course, some algorithms that give you a good approximation to the solution, but they don't "solve" the problem either.
Some people need things spelled out for them.
.. stupid pun.
Yes I know
http://www.confuzn.com
Maybe it wasn't blatantly obvious to a Microsoft employee.
... but it shouldn't be the ONLY security measure.
The criticism of STO is usually directed against systems that use STO as the primary or only security measure.
-- Robert
What a truely afwul set of sentiments... I
The whole concept of STO is based around the idea that your attacker does not know the system that you are using to protect your data.
This is radically different from not knowing a particular piece of information (ie the key) in order to access data.
In the first case an inexpert crypto designer may find that their 'security' system infact contains a large number of clues as to its structure. Take for example a simple substitution cypher, while it might appear to the naked eye to be a random collection letters an experianced attacker would simply build a histogram and break the code based upon the distribution.
Moreover STO can quite easily become an argument for leaving holes (ie possible buffer overflows) open because "nobody knows about it". Quite simply this sort of sentiment has been shown to be very wrong over the years.
I find the arguments about hidden trip wires more interesting - but I would argue that this does not represent STO. The form of security may well be known to the attacker but the actual events which may trigger security alerts could be considered as an equivalent to a key.
STO has had its day - no information which is genuinly important should be protected in this manner.
Given that the normal definition of security is that it should cost the attacker more to breach the defenses than the information itself is worth - information with a very short lifespan may be eligable for some forms of STO and I'm sure that everyone occasionally follows this maxim.
But as a principal and as a technique I would like to see STO burried once and for all.
Tom
Steganography (hidden writing) is another example of a system that relies heavily on STO. A modern example would be using low order bits on music CD's, *.WAV, and maybe *.jpeg files to move banned information past censors.
-- Robert
First off, the author misunderstands what is meant by STO. It does not mean Security through secrecy. All security depends upon a secret- be it the factorization of a composite, a secret key or password or passphrase, or the combination of a safe. The fundamental security is how difficult is it for an attacker to guess that secret.
So, the logic goes, make it more difficult for the attacker to know what secret they need to guess. Hide the security algorithm from them. Does the safe require a combination, a key, a palm print, or some combination?
The problem is that, by obscuring the implementation, weakness that can signifigantly reduce the amount of secret key the attacker needs to guess are hidden ("Um, it's a bad idea to put the door hinges on the outside of the safe. I don't bother picking the lock- I pop the hinges and simply remove the door.").
And this is the advantage open-source has. It's peer review limits the existance of such backdoors. And fixed faster when they are found.
Do not think for a moment that restricting access to the source code makes it less likely such vulnerabilities will be found. The "black hats" (be they the evil hackers or the evil NSA) always seem to have enough time to reverse engineer the software from the binary. The "white hats" generally have better things to do with their time. By making it harder for the legitimate people to look for security holes, you are simply making it more likely that the people finding the security holes will exploit them, and not announce them. By making it illegal to reverse engineer the products, you're gaurenteeing this.
If you don't beleive me, I recommend Bruce Schneier's "Applied Cryptography".
Acording to the dictionaries I looked it up in after my Anthro professor made an ass of himself on that topic, decimate can also be legitimately used to indicate the detruction of a "large but unspecified portion of a population" (my own wording). It is however, incorrect to say X decimated all of Y, or X decimated 40% of Y.
This isn't intended to be news, Mr. Gibson. This is a feature. Give the guy a break. You may want to disable features in your preferences if you're only looking for hardcore news. And I'm sure you don't have Jennicam or Segfault in your slashboxes either, right?
/.
As a public service, you may also want to avoid the following stories (they contain a great deal of common knowledge - be careful!)
Essay on Open Source as an Art Form
Sun Claims MS Steals Vision
High Tech Junk
I, like many others I'm sure, was not aware of the Navajo story and also simply enjoyed the way the article was written. I give the guy credit, being a Microserf and posting on
Really, this article has very little to do with security through obscurity. STO, as implemented by Microsoft, is basically the premise that, because their code is not publicly available, the bugs in it will not be obvious, therefore not easily exploited. Proponents of STO argue that open source systems are more vulnerable because anyone can get the source and find the bugs in it, and thereby exploit these bugs. But the real problem is simply that because the systems which use STO are never as well debugged as their peer-reviewed open-source counterparts, an as-yet-undiscovered bug could be lurking around the next packet. Users must rely on the assurances of vendors, motivated by profit, that their systems are safe; on the other hand the users of open source systems are assured of better quality and quick fixes since the user population is itself selfishly motivated to make the system better and safer.
Granted, this is nothing new, but I thought I'd post something more on topic than the article itself. Stating that encrypted passwords are a form of security through obscurity, as the author does, is just plain silly. If you're going to talk about encryption and STO, it's more relevant to delve into the fact that a closed-source encryption algorithm (a la Clipper) is inherently unsafe because it isn't peer reviewed and therefore has a much greater likelihood of eventually being broken because of the authors' undiscovered mistakes, than does an open-source one which has been examined by a wide audience.
But then, what do you expect...
What I would like to see is a step by step HowTo on security, for both individual hosts and networks.. Kinda like a "Security for Dummies" guide!
For a secret key crypto algorithm, as the name suggest there is a SECRET. It's NOT STO. One of the most famous algorithm in this category is DES wich is well publicized and cryptanalysed, this algorithm implied the secret key to be secret but you can have everything else even the S-BOX, and your are clueless.
I agree with 'carry all obscurity in the key'. But this is better than carry obscurity everywhere. For my house i prefer to have to take care for the key and not for the key AND the door.
When you say to illustrate your talk: "When the tripwire is probed with a SYN packet from a cracker trying to locate the web server, instantly the system goes to full alert. The packet is logged and the admin's pager sounds like an alarm."
It's not STO it may be well know from the attacker without allowing him to bypass this trap.
Your exemple about digital signature is only a way to demonstrate that you have a weak protocol to verify public key. RE-read applied crypto!
Abscence of secret is imposible, but it's different from obscurity.
In a perfect world, this knowledge *would* be old hat to every sysadmin... But this world is not perfect, so not all the info can be taken for granted. I've been reading /. for over a year, been messing with linux and such for about the same period, but I am more of a computer gamer, so I don't have the m@d aDm1n sk1llz. This stuff is new to me, and I bet its a good reminder to those who are veteran sysadmins who may have forgotten this stuff. So, uh, like lighten up.
http://www.somethingpositive.net Funny + bitter = comedy gold
So security may decrease obscurity and therefore my actual security...?
Currently the way you can register a certificate there is no trust between the certificate holder and certification authority, in short certificate this way are bogus, they are just repository of dubious information.
Sure you may put traps in a system to find intruders, but the rest of the system should be secure. Obscurity will gain some time, but it's not the solution, remember it's the way things work that should be open, not the sensitive data itself.
Security is theoretically an impossible task. Given enough time and enough access any code can be broken any hiding spot can be found. Practically, security is about building the cost up high enough that it becomes too expensive to crack. Hence the code talkers where too difficult (timewise) to crack for the benefits. Enigma, the German code system, remained valuable for a significant period of time, hence cracking it for each and every day, was economically viable. Even an STO system as proposed, i.e. switching in to full alert when a wrong pattern is tried, would be worth cracking if the value was high enough.
So long and thanks for all the fish . . . !!!
While this was an interesting article, it wasn't a good defence against STO. The author appears to be arguing that STO, while isn't a good security defence, it can make a good security buffer. These are totally different things. So really he's saying that STO is good to have in your toolbox, it's not a good defence - this is what we've been saying all along.
,hacker Perl another Just)'
Having said that, his arguments are totally bogus. Saying that passwords are obscurity is nonesense. When we speak of STO we're talking about source code, not passwords, keyfiles, etc. Trying to defend STO by talking about the success of the navajo indian code is stupidity in the extreme. There are working practices available _today_ without using STO, so why would anyone bother with a "time limited" crypto?
So just what _was_ this microserf trying to defend? It seems very unclear to me.
Matt.
perl -e 'print scalar reverse q(\)-:
Matt. Want XML + Apache + Stylesheets? Get AxKit.
I grant you that Security Through Obscurity is far more interesting than real cryptographic or algorithmic security, allowing the administrators to play stimulating cat-and-mouse games with the attackers.
The point of cryptographic security is that a very large amount of carefully verified work, the work of experts which cannot be easily duplicated, can be invested in the cryptosystem. The system can then be used by anyone, expert or not, any number of times, by just providing a passphrase. STO requires an expert to devise a new intricate ploy each time.
Cryptography relies on certain algorithms having a minimum order-of-magnitude cost, and hence is vulnerable to spectacular algorithmic advances, but the problems are never meant to be intractable in the sense of "mysterious". A properly peer-reviewed cryptosystem is not weakened even if all of the scientists who invented it subsequently become traitors.
Pavlos
PS. Your point about engendering a false sense of security is correct, but the reason is that the users of the system wchoose weak passwords, leak them, etc.
PSS. Your point about encryption vs. hiding data in your drive is a revelation. I have already ordered my 340282366920938463463374607431GB hard drive!
I take some exception to the definitions used in the article. Obfuscation of information has never to my knowledge been equated with "security through obfuscation." Equating the two makes makes both terms meaningless.
Security through obfuscation relies on a cracker's ignorance of a system vulnerability for protection, as opposed to disclosing the systems specs and subjecting them to rigorous peer review, allowing the vulnerability to be exposed, analyzed, and fixed.
Encryption is the protection of DATA (whether it is a password, data file, or filesystem) through obfuscation of the DATA. Obfuscating DATA is not the same as obfuscating a system architecture in the hopes no one figures it out. To define the two as the same is no different than defining apples and cucumbers to mean the same thing, and leads to the same meaningless results (an inability to differentiate between the two until new terms are invented to compensate for the obfuscated and undermined definitions of the old words). The desire to not disclose confidential data residing on a hard drive does not imply that one is relying on "security through obfuscation" rather than strong, publicly reviewed security approaches. The two concepts are in many ways completely orthogonal to one another.
About the only thing the article got right is the notion that, if the data need only be protected for a brief time, inherently less secure approaches may be used with some success. What is entirely glossed over, however, is that in using a less secure but perhaps more expedient approach one is still taking a terrible gamble, as there is a greater possibility the data will be compromized earlier than desired than if a more secure approach had been used. The probability may be small because of the limited time frame involved (making the risk "worth it" perhaps) but the possibility is nevertheless quite real. What I do not understand is WHY anyone would want to do something like that, when well documented, secure ways exist for protecting both transient and long term data and systems exist, making that sort of gamble unnecessary to begin with.
The Future of Human Evolution: Autonomy
An excelent article. However, I don't believe your example of a social engineering attack on digital signatures is quite right.
The recipient's email client should check the authority signature of the sender's certificate against the known trusted Verisign certificate. In this case they wouldn't match. You can't make them match unless you know Verisign's private key.
The user will be warned that the identity of the sender could not be verified.
Lachlan.
I agree...it was a well thought-out article. Not all of us know everything there is to know about security.
Try not to be an "info-snob" and give the guy a break...
**** Yet Another Useless Post from the Bastard ****
... but what part of Security Through Obscurity is any more mature than some "admin" chanting "I bet you don't know my password, ner ner"?
m p/sh.root.sh :)
I knew there was a reason we were told to keep passwords "uncrackable" (in the brute-force-utility sense of Crack), or to use Kerberos or other means of keeping things secure...
As someone who's had a machine broken into by means of an ethernet sniffer on someone with a weak (crackable) password used in two places, who was saved from a root login by various ttys being insecure, I no longer even let my passwords out from my current domain in plaintext; sometimes they don't go that far either. Ssh is only one means of doing this, but it's a bloomin' nice means.
hackmeplease:vOyo1GrTWU6Ck:10001:10001::/tmp:/t
to them too
~Tim
--
~Tim
--
Rushing on down to the circle of the turn
That P=NP?
Yeah, you'd think news like that would rate its *own* item :-)
(Note: I didn't see anything *on the referenced site* that *claimed* that this method solved the Travelling Salesman problem in linear time. Hint: more cities need longer and more chains.)
I'd take objection to his calling the use of NP-complete problems "security through obscurity", specifically his statement that we're depending on the hardness of the problems for security and that they may not be that hard if we approach them right. From what I recall, what we're depending on in reality is the fact that NP-complete problems are harder than any other known problems, and provide an upper bound on the hardness of problems. We don't know that NP-complete problems are neccesarily hard to solve, but we do know that any other problems are easier to solve. Even if someone invents a linear-time method of solving an NP-complete problem they're still harder than any other problems, the upper bound just moved down a lot. This is a problem for cryptography, but it's not solvable without rewriting the rules of mathematics.
As for calling a secret key "security through obscurity", he's missing the point. STO canonically refers to keeping the details of the underlying algorithms and/or implementation unknown. It does not typically refer to the idea that there's some piece of information that a legitimate user possesses that an attacker does not.
Consider some simple, general purpose Turing machine, so simple you have to write the "program" on the tape as well as your data to make it go (just like a card deck :-) ). Write out your data to be encrypted, your encryption program, and your password onto the tape. Run your machine so that the result is a tape with encrypted data, the program, and the password. With this data either you or your enemy can reverse the process. What part of the tape do you obscure? Usually the password, but in our system that's just a part of the tape.
If you use a unique and clever algorithm for each encryption run, and the same password, you would need to obscure the algorithm to be safe.
One can construct a theoretical framework where it's all STO. By obscuring only the password we simply make the job easier for our customary way of doing things. I don't have to remember and type in my whole decryption/access program, just a short string. If we have a very good encryption algorithm we force the attacker to guess the key, hence we force them to fight by our rules. IMHO it all comes down to that.
Why? To me, decimating 40% of the group would mean splitting off 40% of it and decimating that 40%, killing 4% of the total group. However, this is surely not the intended meaning in this case.
--
Fuck the system? Nah, you might catch something.
... all is in the name of the company.
Well, it is actually, but I will agree that security in the absence of secrets is not strictly possible. There is a difference.
--Flam
Computers are useless. They can only give you answers - Pablo Picasso
DO NOT block ICMP ECHO_REQUEST / ECHO_RESPONSE ("ping") packets. If you do, you will confuse systems, such as some routers, which use pings to determine shortest paths. A Net-connected host is required to respond to pings.
You might be interested in this link..
i tyOS.wri
http://www.ecst.csuchico.edu/~dranch/LINUX/Trin
Depending on who you ask, of course. I just happened upon some discussion of this very topic in Stephen Gould's Wonderful Life. To summarize, yes, "decimate" did originally mean "kill one in ten" (of an army that failed to win, not necessarily a mutinous army), but modern usage has changed to the point that it means "kill lots of".
But I agree that the author's use of "decimate" doesn't read very well.
Full disclosure does not apply to instantiated data
True, but that's not what we're talking about. We're talking about the code that manipulates that data. Saying that STO doesn't apply to passwords is irrelevant.
Full disclosure does not apply to time-limited secrets
Your example is a time-limited method, not merely a time-limited secret. In context, Navaho was used for a very short time. Expecting to use some encryption method for only a short time and not have it cracked is probably a good example against your argument, rather than for. The Japanese didn't have PentiumIIIs and Linux, so a few years was not much time to work on a crack. Doing something like that today would have the algorithm (new and untested, as per your specs) reverse engineered very shortly. You run the risk of having your messages decrypted in realtime before you stop using that algorithm.
Obscurity serves as a tripwire
This example makes no sense. Such trip approaches work because they detect scans; it has nothing to do with the web server, or what port it's on. I'd be willing to bet that a cracker would be able to complete his scan and root your insecure web server before the sysadmin can respond to the page.
Your Indiana Jones example is bogus: attackers wouldn't exhaustively search. They would intentionally break all the tiles, thus revealing which ones were supported. Crackers are not interested in drama. Not until they break in, anyway.
"STO can be a powerful disincentive" is not true; cracker tools don't care.
"But like moats, tripwire obscurity provides a critical buffer against attackers" is not true, either; tripwire only provides detection.
Asymmetric cryptography exhibits traits of STO
"...quite simply, to develop a swift means of factoring those multiples." Isn't that a direct quote from Bill? I would guess you are not a mathematician. (Neither am I) These methods are believed secure because it is believed there is no such "swift means". In math, that usually means you can't just program around it. It means you cannot do it. DNA computers notwithstanding. My DNA computer can barely play my mp3s, much less decrypt my password.
Incorrectly used crypto programs are also not the issue. The issue is that even "correctly" used STO is insecure.
I am not a cryptographer, nor a mathematician. But even I can see your arguments do not stand up on their own merits.
Saying that some instances can be solved in linear time is meaningless anyway... linear describes the growth of complexity when compared to the size of the dataset - when all you have is a series of points then talking about its complexity is impossible.
I believe he meant to say some subsets (special cases) of the problem can be solved in linear time, which is no big news anyway. For example, the TS problem is easy to solve in linear time in the special case that the graph is a circle.
The question is moot anyway, because the notion that the computer solves the TS problem in "linear time" is correct but deceptive. In Fundamental Algorithms, all CS majors are taught to think of the Theta(N) (order of growth) as the "running time" of an algorithm; they then forget that "running time" is a metaphor for a number of computations. A more correct term for Theta(N) would be "increase in computational resources as input size grows".
A DNA computer uses the chemical and structural properties of DNA to perform an exponential number of calculations in parallel. Thus, it is not computing a linear solution to the Traveling Salesman problem, but merely throwing vastly more computational resources at it. The former is an algorithms problem; the latter is an engineering problem.
(BTW: I suspect that the amount of DNA you need does, in fact, increase exponentially with the data set size but in general this is not a consideration since you can put an insane quantity of DNA in a vat.)
~k.lee
(remove nospam for email)
Damn where have you been? Theres a lot of great sites with tutorials on protecting yourself. Number one a lot of things should be common sense. Delete default accounts, use strong passwords, keep up on latest exploits via a security list, etc. Heres some links for ya ;)
But before I dew((do)doo)d00)
All this STO is big freaking joke.
Well maybe...just maybe if I hide my network vulnerabilities, people will just feel bad that I'm a shitty sys admin too lazy to fix the holes in my system
www.securityfocus.com -- Excellent resource for up-to-date news
www.securitysearch.net -- The Yahoo Search Engine of the Security World
www.enteract.com/~lspitz -- Very Informative
www.hackernews.com -- The CNN of the Hacking World
Want Root?
If everything vaguely related to computers were common knowledge to every /. user, there wouldn't be much point in having /. at all. I'm sure there are many areas in computers you wouldn't have a clue in, and another /. user will hopefully do you the favor of pointing out what an idiot you are when you don't know something that to them was obvious.
Can we say that info wants to be free, to obstruct (censor) info is a bug, and to enough eyes all bugs are transparent (routed around)?
If I put my gold in a safe and there's a 1 in 6 billion chance of 'guessing' the combination, that means there's a good chance that SOMEONE on the planet can take it - which brings us to security thru superior firepower.
I want to put my gold in a safe that NOBODY can access except me - perhaps a theoritically impossible goal - in which case all security is
just varying degrees of obscurity but we can put up with infinitesimally small amounts of risk for most practical uses. So the issue may resolve to mere semantics.
But I may be hallucinating again...
Chuck
try { do() || do_not(); } catch (JediException err) { yoda(err); }
1 - Instantiated data
Passwords are the basic means of checking authorization, whether the protocol is obscure or not. I don't see why "password would violate the ban on security through obscurity".
I don't see either how shadow login can be considered an obscure protocol. The author admits himself that the protocol is open. Just because the passwords are hidden does not make the protocol obscure. Using the same logic one may argue that any kind of security system is obscure because it restricts access to data.
2 - time-limited secrets
That is correct. However, this approach is rather risky. You never know how long it will take for attackers to crack it. In fact, it would not be secure to use it more then once...
3 - obscurity as tripwire
OK. I get the point. But how can you connect to a web server if you don't know its port?
Besides, "Such measures do not make a given machine resistant to breach in the long term..."
The author concedes that this tactics can be used to *detect* the attack but not to stop it.
4 - Assymetric encryption
That is his strongest point. Assymetric encryption is indeed a form of security through obscurity. Just imagine what would happen if you find an algorithm to quickly factor large numbers into primes... So yes, he does make his point that any security system cannot be completely free of obscurity.
___
If you think big enough, you'll never have to do it.
Others have pointed this out, but I don't think everyone will get the difference even through they are right, so here is my attempt, dumbed down a bit for the less technical.
Imangine for a moment that I capture Rob (cmdTaco ie founder of /.) and tortue him until he gives me the root password on the main /. server. I now have a seceret, and I can get into /., but I do not have enough information to get into User Friendly Even though(if) both run the same version on linux.
Not imangine that I capture an enginerr from Microsoft and torture him until I get a previously unknown security hole in Windows NT. I can now break into any NT server in the world, (assuming the reqrisites for the hole are in place, obviously a system in a locked room not attached to a netwrok is safe)
See the difference? In one area the terriorist got the ability to break into one machine, in the other the terriorist got the ability to break into virtually any machine.
Now It is possibal that some bug exists in Linux that will allow anyone to get into it. With linux, once I discover how someone got into my machine I can fix it, with NT I have to wait for microsoft. So in reality what makes open source better in the face of attack is that I can fix it in a few hours whereas with STO I have to wait for a vender to fix it. If I'm a minor player and nobody else is attacking me, with STO my vender can leave me in the lurch, whereas with open source I can fix it myself.
Although the author's article did not increase my respect for obscurity, his implicit point - that it's a good idea to question conventional wisdom - is a good one. I witnessed a prime example of this while watching the panel sessions at the 1999 IEEE Symposium on Security and Privacy. Several of the speakers professed new respect for the "penetrate and patch" technique. Among the government-funded security research community, which spent much of the last decade or so searching for foolproof methods for producing software demonstrably free of security holes, the conventional wisdom used to be that penetrate and patch was the height of inept foolishness. But, as several panelists pointed out, in the real world it is the de facto standard, because (as any Microsoft employee probably knows) it requires no burdensome initial investment in detailed design, formal verification, and heavy-duty software engineering practices that might delay a release. Considering that the "foolproof" methods have turned out to be commercially impractical, a renewed interest in penetrate and patch may be a good thing.
I do not speak for my employer.
- Tim
Any what do you do if your traps go off? Take the server off line?
There is an old but delightful movie called "How to steal a million" that is based on exactly that scenario. Basically, if your traps go off every fifteen minutes, you will not be paying any attention to them very soon.
Kaa
Kaa
Kaa's Law: In any sufficiently large group of people most are idiots.
But there is a catch. The trick to the DNA "solution" is that it is a massively parallel solution. The time to get the solution may be linear, but the amount of DNA you need grows exponentially. If you simulate this on a single computer, the problem takes exponential time.
:-P
However quantum computing offers similar tricks using a superposition of quantum states to do an exponential amount of computing without taking an exponential amount of time. The last that I heard that technology was looking more and more feasible in the long-term. But it is still a good 20 years off even if it can be made to work.
As for P=NP, I honestly believe that they are different. As for a proof, well this post is too short...
Cheers,
Ben Tilly
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
Apparently, the author does not understand this significant distinction. Secrecy != obscurity. In this article, "obscurity" is defined so broadly as to be useless... anything that isn't spammed out across the 'net is "obscurity".
In the world of serious computer security, "obscurity" refers to keeping the *mechanism* for storing information secret, not the information itself. In practice, the mechanism should be able to keep the information secret even if the inner workings of the mechanism are known.
For example, the algorithms used in the US government's ill-fated "Clipper chip" were kept secret - security by obscurity. When, under pressure from industry, the algorithms were finally released, significant weaknesses were immediately discovered. RSA, on the other hand, is not obscure. Even having the source code for the actual program used to encrypt data with RSA does not significantly reduce the time required to decrypt it (consider that a PGP-encrypted message states its nature in plaintext, right at the top of the message!)
Another, more MS-vs-OSS example is buffer overflow attacks on daemon programs. The "security through obscurity" approach is to hide the source code, so potential buffer overflows are not obvious. But hiding the source does not *eliminate* them... it just hides them. With patience and educated guesses, they can and will be discovered. By opening the source, potential overflows can be found and discovered. One need look no farther than the recent security reports on the most popular closed-source web server (IIS) and the most popular open-source web server (Apache). Which one has had multiple severe, easily exploitable security holes reported lately? In other words, the obscurity of the IIS source made it harder to find weaknesses, but not impossible. In Apache's case, thousands of eyes have pored over every line of source, and the potential weaknesses were found and eliminated long ago. Which makes you feel safer - code thoroughly studied for weaknesses by thousands of programmers, or code where only the authors have examined it?
---
Hand me that airplane glue and I'll tell you another story.
The problem with STO, where the actual "algorithm" (any steps taken to create that part of your security) is secret, is that you don't know if it is secure.
Because it is not, or hardly (only collegues) peer-reviewed, no one has told you if you made any obvious mistakes, and no one can assign an upper- and lowerbound to the difficulty of breaking your "algorithm".
The algorithm you describe where the admin assigns a different port to the HTTP server is not STO; it can be analyzed, and flaws can be found. (And a great many there are)
There are of course problems with these attempts to use a general concept, such as port numbers here, as a key in a secure protocol.
Probably the biggest is that it is not seen as a secret. If Mr. CFO goes to the companies' secret website at port 6301, employee John Doe can walk in an spot the port number in the web browsers' location bar, because the web browser hadn't thought it was a secret.
Probably Mr. CFO is also an average user who doesn't completely grasp the fact that the URL is now an important secret, so he writes it down on a post-it note attached to his monitor.
The other problem is that "innocent" users, such as search engines, may also scan a whole lot of ports to find a webserver, so a) Mr. Sysadmin will get a lot of false alerts on his pager and b) the information will end up for all to see in some Big Search-engine's Database.
The same goes for Joe Hacker who may be detected but has still taken all the necessary information within 4 seconds.
EJB
sure, don't block ping but even worse don't block ICMP host unreachable as this is used for MTU path discovery and can cause some very wierd errors. (and some frustrated users who have no idea why their transit is screwy) - Matt.
DNA computers avoid the problem of superpolynomial space requiring superpolynomial time by exploiting massive parallelism; unfortunately, these DNA computers require superpolynomial space to solve problems, which is arguably just as bad as superpolynomial time.
Kyle
--
Kyle R. Rose, MIT LCS
[ home ]
Clarification on passwords as STO: If passwords were always known only to their creators, then that would be plain security, not STO. But many administrators and organizations "issue" passwords, so that they are known both to their users and also a "select" group at the issuing organization. This is STO because the knowledge of the password by the "liegitimate others" in addition to the user can (like all STO info) be compromised. Further, the principle of non-repudiation is voilated: a user whose password was misued can always blame it on others who officially had access. Passwords created by, and known only to, their users don't have this problem, since there is only pure secrecy, no obscurity.
-
Suppose I hide the exam answers in /home/ebcdic/old/letters. That's STO. But the way you find them is exhaustive search through my directory, just as the way you find my login password is by exhaustive search of character sequences.
The difference of course is the scale of the search. A one character password is no better than an obscure directory.
The important thing is to be able to quantify, or at least make explicit, the effort needed to break in to the system. With prime-product based public key, you can say something like "breaking this requires either solving the discrete log problem or X amount of work using the best known algorithm".
Get a clue. For example, read Berkeley security class notes
Okay, nevermind the curious definition of STO adopted by the author.
:)
A former coworker and I were discussing STO, and he argued, rather successfully I think, that STO is probably the best way to go for organizations like the NSA, for the following reasons.
First, the NSA employs a great many security experts and crackers. They have enough resources to perform in-house peer review.
Second, the odds of someone outside of the NSA being a friend who would disclose any discovered weaknesses to the NSA for them to fix is not very high.
There is the issue of moles and such leaking the info, or the system being reverse-engineered (by sniffing air-bound packets?) The idea is that, by using their resources and internal peer-review, that they could create an algorithm that would be secure even if the algorithm was known.
So it's not really STO, in the classic sense, but rather _Additional_ security through obscurity. Make your algorithm secure even if known, but don't give your enemies the algorithm for them to play with just to prove your point.
Of course we both agreed that you should never use a STO-dependent system to talk to your bank or credit card company.
The enemies of Democracy are
First of all STO is not real security. It cannot be your only or primary means of security. But in many cases STO is a convenient solution that should not be ignored.
For instance one problem with scripts is the fact that they often have passwords encoded in everywhere. What to do about it? Well in some random spot under an innocuous name, put a program that when passed a series of semi-open secrets by the appropriate user(s) (and possibly only when called by the appropriate program) will return a password, and log attempts to call it inappropriately. In your scripts you can call on that program.
This means that you no longer have the passwords hanging around everywhere, and it additionally means that when you change passwords, you can just change that one program and all of your scripts will continue to work.
This is not, of course, appropriate for a high-security situation or a broadly used solution, but when your need is a trade-off between convenience and true security this judicious use of STO is a hole, sure. But it is a hole that is reasonably hard to take advantage of. (Although if you know the rules for the program it then becomes trivial!)
Cheers,
Ben Tilly
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
I toatally agree.
BUT, you're simply redifining 'obscurity' to mean something different than STO defines it to be. STO conventionally means that the attacker doesn't understand your particular setup and/or system; it is 'secure' because your system is of an obscure type. If you want to re-define obscure to apply to secret keys and one-way hashes then you are totally correct; if you are trying to debunk the notion that STO isn't real security, you have failed.
Putting a webserver on another port doesn't buy you much safety. As a worse case scenario, an attacker would be ignored after he attempted to contact an unauthorized port -- the attacker simply needs more IP addresses to complete her attack. Try to say the same thing about the shadow password file.
You can't.
The wheel is turning but the hamster is dead.
The wheel is turning, but the hamster is dead.
First off, while Priestly does appear to have done some research, apparently he missed researching the definition of "Security Through Obscurity". Large chunks of the article are trying to say STO is essential because you have to keep keys secret. STO refers to systems where algorhithms are kept secret, not keys or data. By extension, if bugs and security holes are kept secret, that too is STO, since it's information about the algorithm. There goes point number 1.
Point number 2 is somewhat valid, if you only need security for a short time, you can get away with STO. However, such situations are rare, and you are just as well off with real security, so why risk STO? Back in WWII, encrypting messages for broadcast was difficult and expensive, so they needed to come up with other ways (Navahos, Enigma, etc.), it no longer is a problem. Speaking of WWII, the German Enigma cypher is a classic example of the utter failure of STO, in a time-limited environment no less.
Point number 3 is not security. Having tripwires in place might be handy against script kiddies, but a well informed hacker can avoid them. Even an uninformed hacker has a statistical chance of avoiding them; just by trying random ports, they might come across the real port before they find any tripwires. Unlike a medieval moat, a digital moat can be just jumped over without any planning or special equipment.
Point number 4 is again based on the just plain wrong "But you keep keys hidden, that's STO" argument, but it makes a few other points as well. Yes, if someone finds a fast way to factor huge products of two primes, public key systems fall apart. Since the best minds in the world have been working on this problem for centuries without finding much, the chance of anyone finding a good solution right away is slim. In the mean time, open, non-STO public key systems with large keys are very secure.
The phony certificate issue is not an issue of "Open Complicated Systems vs STO" it's an issue of "Untrained users can compromise security". Public key systems offer easy ways of protecting against forged certificates, as long as they get used. User training and dillegence is a critical part of any good security system, without it, you don't have security.
The "Swedish Bank Account Number" example isn't an example of STO at all (unless you neglect to mention to anyone that the algorithm is an XOR of a key with the data). It's an issue of key management. On the other hand, using a simple algorithm like XOR would allow a cracker to get some useful information without needing to discover the whole key. More modern security algorithms don't have this hole.
In conclusion, Priestly has shown little understanding of the real issues of security. He has come up with one case where STO is not worse than real security (but also not better), and a bunch of arguments based on misunderstandings that show he should hit some more textbooks.
----
----
Open mind, insert foot.
see, told you so
Remember the LinuxPPC challenge? The root password will *not* in general help in getting into a Linux box.
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
Factoring is not NP complete.
:-P
Make that not known to be NP complete. It is clearly NP. The question is whether it is complete. To which I note that if, for instance, P=NP then factoring would trivially be an NP-complete problem.
Although it does seem doubtful that it would be NP-Complete.
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
I wouldn't say it was obvious... there's a difference between planned StO and having it just turn out that way.
I guess the StO approach gets a bad rep for being the security model you're using when you aren't using a security model.
At any rate, I guess that an awful lot of people rely on obscurity as their safety net. When you do leave a security hole by mistake, at least there's the chance that nobody will notice.
Anyway, isn't obscurity the main weapon of the CIA et al? "need-to-know" and all? You don't see them talking about their spying arrangements openly, just so that people can mail in helpful suggestions...
> To continue my rant, the factoring is not "obscure". RSA would be "obscure" if it relied on some "magic" number - that is, in finding this single "magic" number, one could decode *all* messages encrypted with RSA. Since the public key is, well, public, the strength of the algorithm lies in the difficulty of factoring an arbitrary large composite number that has only 4 factors.
Actually, I think he was referring to the fact that the PRIVATE key must be kept obscure. Naturally. This likens to his issue of passwords being obscure. You can't tell someone your password, or it's useless. Same with RSA. You can't give out your private key, or it's useless.
In any case, yes, I would say that by this definition, ALL security relies on some amount of obscurity. But big deal. This is more or less axiomatic, and the article's point seems to be moot. If that's all he was trying to say, I think it's safe to say we knew that. But that doesn't say that simple obscurity (such as the web page on a different port) is a good bit of security. It's not. It's highly insecure. But it is cheap, isn't it? As in all things, you must evaluate the need along with the price.
---
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
The Clipper algorithm, called "Skipjack", has now been released and cryptoanalyzed by the public cryptography community. Interestingly, it has been found to have possible exploits at 14 rounds, and has exactly 15 rounds. The question of whether the NSA has unknown technologies capable of breaking it at full strength is unanswerable, but suspicions are that the answer is "yes". But it currently cannot be broken via publically-available means.
-E
Send mail here if you want to reach me.
not everyone is paranoid enough to check the authority signature. yes, they should, but i'm not sure everyone will go to the bother, or that everyone knows how. For a lot of people, the words "digisign security certificate below" followed by the results of a cat /dev/random ought to be enough that they will just _assume_ it's valid without ever bothering to check. I think that was what the original point in the article was.
Irritable, left-wing and possibly humorous bumper stickers and t-shirts
One of the remarkably few papers presented by Microsoft at this year's Siggraph conference was on watermarking of models. The idea of watermarking, of course, is to embed some signature of the creator of the actor/model/whatever in the object itself, in a way that is robust. Hughes Hoppe, along with Emil Praun and Adam Finkelstein of Princeton, did indeed come up with a way of doing so that is all those things, by copying (extending? embracing?) a technique from the audio and image watermarking body of knowledge -- he encoded the watermark in the most salient features of the model, at various frequencies. The author of the model saves the original model, the watermark parameters, and releases the watermarked model to the customer. An interesting part of this, though, is that the watermarking algorithm -- or in this case -- the parameters passed to the algorithm, must be secret or it would be trivial to defeat. Furthermore, there is an interesting question when it comes to proving that someone has stolen the model. The original author must produce both the original model, and the watermark algorithm, to verify to the rest of the world that the suspect model is indeed a copy. Now, I would expect Microsoft (say) to object to this -- because if they release the details of the algorithm then anybody could defeat it. On the other hand, are you going to trust the alleged owner of the original when he says "Oh yes, the watermark demonstrates that it's my model. I'm sorry, but I cannot prove this to you." Even if they do that, it is difficult (though not impossible) to conceive of a watermarking system that doesn't allow post-hoc watermarking; that is, generation of a 'original' from the suspect copy. Hoppe does note this in his article, but it's just in passing. Finally, for you other Microsoft-haters out there, in Future Work Hoppe includes "an automated agent such as a web crawler to search for possible stolen watermarked documents." Here's the article
I love Mondays. On a Monday, anything is possible.
Wrt to daytime: Host requirements are something entirely different.
If you completely disable ICMP, TCL will break, because PMTU discovery doesn't work anymore.
It's safe to disable some ICMP types, but don't disable it completely. More info can be found here:
http://www.worldgate.com/~marcs/mtu/
--
OS lover
OS lover
This is certainly one of my pet peeves... IDIOT firewall admins who turn off ICMP entirely, or worse, turn off everything but ICMP echo. ICMP exists for a reason. Sure, there are some parts that can be turned off without a problem, but you need to understand what the f*** you're doing -- which is at least 105% of the problem.
/* Echo Reply */ /* Echo Request */ /* Information Request */ /* Information Reply */ /* Address Mask Request */ /* Address Mask Reply */
As for that BS about routers using "ping"... no they don't -- or more accurately, none that are worth their weight in twinkies. There are much better ways to judge distance -- oh, say, like the TTL in any IP packet. (Note: bind does this already.) Additionally, if you knew anything at all about ICMP, you'd know there is no (zero, none!) transmittion assurance for ICMP traffic. Nothing is going to alert you an ICMP message never got to it's dest. nor will anything ever retransmit an ICMP message. (RFC) Rule #1: NEVER SEND AN ICMP MESSAGE ABOUT AN ICMP MESSAGE.
For the record, the parts that can be turned off without breaking the network stack are:
ICMP_ECHOREPLY 0
ICMP_ECHO 8
ICMP_INFO_REQUEST 15
ICMP_INFO_REPLY 16
ICMP_ADDRESS 17
ICMP_ADDRESSREPLY 18
Note: Turning off address mask info will break HP open spew.
Secrecy and obscurity are fundamentally different in an information-theoretic sense. If you want to ask whether a particular fact, compromise of which might break your system, is a proper secret or merely security, ask yourself this: how difficult is it to measure the *entropy* of that fact, expressed as a number of bits unknown to the attacker?
If it's, say, a randomly-generated 56-bit DES key, then the answer is easy: 56 bits. If it's a 1024-bit RSA public key, then it's somewhat harder, but the answer will be around the 1000-bit range.
If it's a passphrase, it's probably around 40 bits or worse - people are very bad at choosing passphrases, so some care has to go into making guessing attacks difficult.
But if it's a particular implementation issue, or an encryption algorithm you're keeping secret, how big is the algorithm in bits? In other words, how big and how regular is the space of algorithms from which it's drawn? Are there perhaps a thousand algorithms that you might have been equally likely to choose instead (10 bits)? Or ten thousand, but some are more likely than others (13 bits or less)? It's almost impossible to make a sensible estimate, and so actually working out how much security you get from keeping it secret isn't possible. *That's* what security through obscurity is and why it's bad.
--
Xenu loves you!
This article reads like FUD applied to cryptography.
;P
Firstly, secrecy and obscurity are not synonymous. This point has been made by others, so I won't labour it. Suffice to say that the product of two large primes is not as easily reverse-engineered as binary software.
Secondly, the fact that secrets can be time-limited is exactly the reason why PGP, and other encryption software, usually recommends a default key length shorter than the maximum allowable.
Thirdly, it is the threat of plummeting to certain death that gives the Indiana Jones technique its strength. That is to say, it is the fear of retribution, rather than the obscurity, which provides the security in this case.
Fourthly, what a lot you have to learn about asymmetric crpytography! When I wish to authenticate the origin of a message, I don't just check its "This Key Generated for 'Verisign Clarse One Primary CA' by Genuine Microsoft Products" tag. And as for keeping your keys at an 'unknown' offset on your hard drive, well, if your mathematical principles had been followed in the design of cryptographic techniques used today, I think we'd be using methods much faster than brute force to crack them, don't you?
I'm awfully glad this guy works for Microsoft.
Hamish
"Wise men talk because they have something to say; fools, because they have to say something" - Plato
"The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers."
--Bill Gates from "The Road Ahead," p. 265.
"Wise men talk because they have something to say; fools, because they have to say something" - Plato
On code talkers
The Navajo code talkers actually spoke in code as well as Navajo; a native Navajo speaker would have been able to understand the structure of their sentences, but not knowing the code, would not have easily been able to understand their meaning.
On tripwires
Tripwires have their disadvantages. You can't actually drop the cracker into a pit in a computer system. What you can do is try to make it harder for them to get in: drop packets from them, or answer them more slowly, etc. The trouble is, if the attacker can trick the tripwire, they can turn this into a denial-of-service attack.
On NP and P
You refer to the notorious difficulty of NP problems. But essentially all problems solved by computers are in NP; problems are in NP if a nondeterministic computer can solve them in polynomial time. Most of them are in the subclass of NP called 'P', which means they take polynomial time on a deterministic computer.
There's a class of problems called NP-complete problems. Any problem in NP can be reduced to any NP-complete problem in polynomial time (deterministically). Presently NP includes some problems that take exponential time as far as we know. If we found a polynomial-time deterministic algorithm to solve an NP-complete problem, then we could use it to solve all problems in NP in polynomial time.
Factoring numbers is not known to be NP-complete. It is known to be in NP, but it is possible that it is in P, even if NP != P. The Traveling Salesman Problem, on the other hand, is known to be NP-complete.
However, nobody has found a quicker-than-exponential-time method to factor numbers yet. RSA is "provably secure" in the sense that any method to break RSA in a reasonable time can also be used to factor numbers in a reasonable time. (Other public-key cryptosystems use discrete logarithms in finite groups, not factoring numbers.)
Your DNA computer point is ill-made. You still need O(k^N) pieces of DNA to solve TSP in linear time. This means that it is still trivial to construct instances of TSP that cannot be solved in reasonable time in reasonable amounts of space. (If k is 1.1, then N must be 48 to take 100 DNA units, 145 to take a million DNA units, 574 to take 6x10^23 DNA units, and so forth. It is trivial to construct an instance of TSP that requires more DNA than the Earth's mass to solve in linear time, using presently-known methods.
You say, "the repercussions when this piece of obscurity is cracked", referring to the secret of factoring numbers in polynomial time. But, as you point out earlier in the same paragraph, nobody knows whether this secret exists at all.
On human factors
Your point that no computer technology is proof against people giving away the farm is well-taken. Of course, if I accept CA certificates from whoever sends them to me, I will have security problems, regardless of the technological security measures I try to use. The same is true if I type arbitrary commands for anyone who calls me on the phone. "echo + + > .rhosts, OK, I did that; what next?"
On brute-force cryptanalysis
Your point about brute-force cryptanalysis is also missing the point. If I have a hundred-gigabyte hard disk, there are 10^11 or so places on the disk that the secret information can be hidden. That's equivalent to a 36.5-bit key. If I go all out and buy a DVD jukebox with 10 terabytes, that's still only 10^13 places to hide the secret bank-account number, equivalent to a 43.2-bit key.
On the other hand, if I encrypt my data with Twofish with a 256-bit key, there are 2^256 "places" my data could be "hidden". That's about 10^77 "places". 10^77 hydrogen atoms weigh about 10^54 grams. The mass of the sun is about 10^33 grams. So if you built a hard disk that stored one byte per hydrogen atom, you could obtain an equivalent degree of security by taking 1,000,000,000,000,000,000,000 stars the size of the sun for raw materials for your hard drive. (It turns out you'd need to use a significant part of the matter in the universe to build such a hard drive.)
So yes, your real error lies in having a hard drive of insufficient space. But 'insufficient space' simply doesn't begin to convey the magnitude of the difference. It's sort of like describing downtown Hiroshima in 1945 as unseasonably warm, although that simile falls short of conveying the degree of the understatement by several tens of orders of magnitude. It's like saying that the universe is a little bit bigger than a hydrogen atom.
There's another difference: the effort required to assemble several galaxies into a data storage device is roughly proportional to the size of the resulting data storage device. So is the effort of searching it. With encryption, on the other hand, using a key that is twice as long generally causes the encryption to take about twice as long, while squaring the difficulty of brute-force search. So I can use my Apple //e to encrypt something with a 128-bit key, and all the computers in the world working for billions of years won't be able to recover it.
kragen@pobox.com (mailing lists)
You make good points, but they don't really back up the points that Mr. Priestly is making. Your arguments suggest the use of StealthPGP. In George Orwell's 1984, Smith relied on a piece of white dust or hair or something (I can't quite remember), but it didn't stop the Thought Police knowing his every move.
"Wise men talk because they have something to say; fools, because they have to say something" - Plato
My Little Pony wrote:
Any what do you do if your traps go off? Take the server off line? Can you say "Denial of Service"?
No, but any IP caught scanning closed ports goes into the deny table for a while. ipchains is SOOOO handy that way.
Lacking <sarcasm> tags,
systems fall apart. Since the best minds in the world have been working on this problem for centuries without finding much, the chance of anyone finding a good solution right away is slim.
just think for a second: what would you do if you where one of those bright minds of number theory and you would find a solution to the factoring problem? would you:
i guess if one would find a solution to the factoring problem then he would maybe choose the second way... and how do we know how many people already sailing in the south pacific?
and not let us assume you are the e.g. NSA who bought that algorithm.. you would plea for regulations on "strong" encryption..in the hope that people who really have to hide things think it is still secure..while they already know the key...
mond.
Several years ago, I was about to buy a safe for my law office. As I lifted the safe off my shelf and on to the cart, I realized that it wouldn't be much use . . .
Someone, please! Moderate these posts up!
Because of people blindly blocking all ICMP, PMTUD (path maximum transmission unit discovery) is horribly broken for a large percentage of the internet.
The problem appears when you have a link between yourself and the destination that uses an MTU less than or not equal to (I can't remember which) the common 1500. What usually happens is small transfers work ok, but large transfers don't. So, you may be able to (for example) log in and get a directory listing from FTP sites, and even download small files, but trying to download large files just doesn't work properly. This has frustrated many people, as the problem is not easy to figure out. And once you do figure it out, the only way to fix things is to complain to the offending firewall operator, who will usually give a response like "Everything works fine for me. Must be a problem with your system.", or something similar.
"You're violating RFC xxxx" is just no match for "It works fine for me."
The only real solution is education.
So spread the word. Save the net.
I suggest buying a copy of Bruce Schneier's book "Applied Cryptography". He also has a web site (http://www.counterpane.com ) which has a lot of information that has trickled up through the ranks since the time that he wrote his book.
You are referring to what are called "side-channel attacks" when you talk about bribing the folks who do the encoding, and you are correct, side-channel attacks are the only effective attack against modern cryptographic techniques. You are referring to what is called a "man in the middle attack" when you set yourself up as the intended recipient of the encoded message, but there are known techniques for dealing with "man in the middle attacks" (read Bruce's book).
A cryptographic algorithm itself does not rely upon obscurity. The data is not obscure, it is effectively randomized. It does rely upon secrecy, in particular, upon the secrecy of the key. But secrecy is a different thing from obscurity -- obscurity is hiding a needle in a haystack in hopes that nobody will find it, while secrecy is carrying the needle around with you in your wallet. The difference is that someone might accidentally stumble over the needle in the haystack, but the needle in your wallet is never going to be stumbled upon by any intruder. Of course, if you leave it sitting on top of your dresser (like most people do with their "secret" keys), it's no longer safe from somebody stealing it! But that's a different issue altogether.
-E
Send mail here if you want to reach me.
Obscurity strives for complexity and the appearance of security without any substantial way to analyze how the system is secure.
The fact that there's no mathematical basis for understanding the intractability of algorithms used in cryptography (or analyzing computing effort in general) is troubling. However, the current state of cryptography is a collection of techniques which are known to work well in practice and are, so far as anyone knows, secure in well understood ways. If you compose a system using components with known properties, you can make an overall system with known properties.
The real problem with using obscurity is that it strives for complexity for its own sake, whereas real security relies on simplicity. To paraphrase Hoare: "there are two ways of designing a system: keep it simple so there are no obvious problems, or keep it complex so the problems are not obvious".
I am definitely not aware a crypto expert. So this could be the opinion of Joe Everybody, when listening to the STO argument.
The STO person says: "I will protect your secrets, but I will not tell you how, because that is a secret."
The OSS person says: "I will protect your secrets, and I can mathematically prove that your secrets are safe (within known bounds); and you can let anyone of your own choice verify this."
Now it's my choice whose solution I want to buy. Well, I can only say to the STO person: "Why don't you prove mathematically that your solution is safe?"
STO requires you to trust the STO person, while OSS requires you to trust mathematics.
>The disadvantage of one time pads is that they require huge keys, and thus key distribution becomes a major pain.
No, the BIG disadvantage with one-time pads is that you need a secure channel on which to send the pad to the other person. Since you need that, and the pad is as large as the message, what's the point? Why not simply send the message over the secure channel?
In any case, you are right. No amount of resources can decrypt this system without first obtaining the pad, or enough of it to make it possible to apply other techniques.
---
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
Those people who are claiming that STO should be defined as "security *only* because the algorithm/implementation is unknown to attackers" and then go on to say that STO is not good security as are largely arguing a truism. (If I recall my debating terms correctly.)
The logic for STO goes as follows:
(a) There is a bad method of keeping secrets
(b) We will make the secrets safer by not telling anyone about (a)
This is almost definitionally a bad way to keep secrets as (b) -- not telling -- is almost certainly an even *worse* way to keep a secret than (a)!
The two most frequent counter arguments seem to be:
i. Open algorithms prevent (a)
ii. Relying on (b) will eventually fail
Argument (i) is merely a statement of how to get good security ("if the algorithm is secure even when the attacker has the algorithm and a plaintext/encrypted text sample, it must be secure"), which actually runs counter to the initial premise that security is *ONLY* due to obfuscation. If you had good security, it definitionally wouldn't be STO!
Argument (ii) is the correct criticism of STO if STO requires the "only" clause.
A generous interpretation of the author's original point -- STO jargon misconception aside -- is that obfuscating details from an attacker may enhance security. Consider the matrix:
(Hey! How about a "pre" tag!)
A: is trivial
B: is STO
C: is "open encryption"
D: presumably, is stronger even than C
As an example, if I have a choice of strong, open encryption systems, why tell an attacker that I'm using Twofish instead of IDEA? Even if that obfuscated fact is revealed, the fallback of (C) is secure. In the meantime, however, I've layered on additional complexity for a would be attacker.
Of course, practically speaking, (C) is sufficient, but there's certainly no need to go out of our way to tell potential attackers all the details.
-XDG
There is one serious problem with your approach. You say IDEA and DES are strong encryption systems. Well, why do you know this? Because people have been able to review them prove their strength. If you use a secret algorithm, you will not be able to know if they are actually strong... Therefore, there is no option D.
The simplest passwords (the ones that assume nobody will guess your mother's maiden name, or the DOB of your firstborn, etc) are security through obscurity.
But if you choose a password of a good length consisting of truely random alphanumeric characters, it's not obscurity because you can accurately calculate the odds of an attacker guessing it.
The whole problem of security-through-obscurity is that obscurity looks better than it really is, and its true value is impossible to calculate (Except in the negative. As in, after you've been "owned"). This leads people to overestimate the effectiveness of the obscurity, which in turn leads to a false sense of security.
I think it's important to note that the Navajo translations were never sent out plaintext. After being translated into Navajo, the messages were still encrypted before they were sent.
Being a computer person, I'm not familiar enough with "ancient" practices to know whether or not to classify the use of code-talkers as security or obscurity. In any case, using a code-talker with a modern cipher would actually be detremental, reducing encryption speed by a factor of about a billion. Modern ciphers are designed to be secure for decades regardless of the language used in the plaintext. The code-talker element of this item is completely irrelevant today.
As for the argument about time-limited secrets, there's no obscurity involved (at least, not anymore). If you can figure that an adversary can try 2**72 keys before the secret becomes useless due to time, and you have a 128-bit key, then there is only a 1 in 2**56 chance of them guessing the key before the data expires. A "one in 72 quadrillion" chance is security, not obscurity.
First of all, if the attacker uses one of the various stealth scanning techniques, the system you've described is completely worthless. Some scanners don't complete the three-way handshake and your script would never be run. Others don't even send a SYN at all.
Second, if you can detect the scan, what are you going to do about it? You could block the IP, but the attacker could always attack you from another location. And there's no guarantee that the attacker is at the IP the scan originates from, as packets can be forged (to make you block the wrong hosts), and there are even a couple of ways to bounce a port scan off an innocent machine.
Third, if your web server is vulnerable, the alarm isn't going to save you. By the time you intervene your box would probably have been owned and used to scan hundreds of other innocent hosts. All because you overestimated the effectiveness of obscurity, leading to a false sense of security.
The only cryptographic systems that are "provably secure" are the One Time Pad and certain other secret splitting algorithms. These cannot be broken no matter what mathematical problems you solve and no matter how much computing power you have. This is for information-theoretic reasons that I won't go in to here.
More common are systems that are provably equivalent to some hard problem. That is, if you can break the system, you can also do something else that is very hard (and vice versa).
The whole point of proving something is equivalent to a hard problem is so that you can better estimate the difficulty breaking the system. If the best minds in the world have worked for centuries trying to figure out how to factor large numbers, and progress is at a fairly constant (slow) rate, you can get a pretty accurate estimate of how hard it is to factor a number of a given size. And if your cryptosystem is provably equivalent to factoring, the same estimate applies to your cryptosystem.
Most cryptosystems depend on symmetric algorithms (like 3DES) that aren't provably equivalent to anything. This is why so much study is done on ciphers, trying to find weaknesses, before a cipher can be considered "secure". The more study is done, the better the estimate of the security of the cipher. Most cryptologists would tell you NOT to use the AES candidates yet, because they aren't well-studied enough. Most cryptologists, when their data is on the line, would prefer to see it encrypted with Triple-DES because it is such a well-studied cipher. If the best cryptographic minds in the world have studied a cipher for over two decades and have not found any major weaknesses then you can be pretty sure that there aren't going to be any suprises.
In practice there is no such thing as perfect security. The best a person can hope for is to make a realistic estimate of the difficulty of breaking the system. In the case of obscurity, realistic estimates are impossible, or simply not attempted. In the case of obscurity the best a person can do is make an optimistic estimate in order to justify the effort of obscuring a system. Such optimistic estimates tend to be wrong.
Some thoughts on your post:
1) The DNA computing solution to the TSP didn't use nucleotides, but synthetic strands of DNA made with unique sequences to represent the nodes of the graph. The sample space is therefore full as long as a suitable # of copies of fragments are placed in solution (hence the parallelism of the solution).
2) Mixing is affected by the number of free DNA fragments, but only in the probability that two molecules will interact with DNA ligase in such a way as to ligate successfully. This, of course is more dependent on *concentration* of DNA and enzymes than the number of copies of DNA fragments considered in isolation.
3) As alluded in 2, "Increasing the vat" will not necessarily get you *faster* mixing. Biochem textbooks go into this in painful detail in their discussion of enzyme kinetics. Basically, at some reaction condition an enzyme reaches "maximum velocity" and will not catalyze a reaction any faster than that rate, no matter what you do. Substrate concentration plays a role, as does product concentration, so while increasing DNA conc. will increase the "mixing rate" to a point, this effect will ultimately plateau.
4) Given 3, you won't necessarily have more duplicates to check unless you allow the ligation reaction to run for a longer period of time. This is true if your ligase enzymes are already at their maximum velocity (which is commonly achieved).
4a) This is sort of a nit-pick, but the number of "wrong answers" that need to be checked is ultimately a non-issue. The standard DNA manipulations used in a bio lab would allow you to filter out all but the solutions to this problem in a single step (gel electrophoresis of DNA allows molecules to be separated by size at very fine resolutions).
5) As the problem domain is made more complicated, there are longer fragments of DNA to screen. However, DNA breakage is not a practical concern, given that living organisms have DNA strands that are many kilobases, if not megabases long. We're talking about concatamers of N*20 bases here, where N is the number of nodes in the TSP. You're problem domain would have to be *huge* for this to be a real problem. Even then, the number of broken strands would be vastly outnumbered by intact strands.
6) As someone else noted P or NP is irrelevant to this type of solution to the TSP. The DNA solution is fundamentally parallel, but to measure it with a problem set defined for Turing machines is like comparing apples to oranges. The DNA approach makes Turing NP-complete problems tractable in "real" linear time (linear because it ultimately take linear time to sequence DNA fragments). But as so many others have noted, the solution space for this problem is not linear, since the real work is done by enzymes in a massively-parallel fashion. It just happens to be a cheap massively parallel computer =)
If anyone wants to debate this further, I'm game. Contact me at trobertsNO_SPAM@du.NO_SPAMedu
-Tim
Let's try not to let fact interfere with our speculation here, OK?
I was also rather disappointed by the fact that 90% of the article really just dealt with passwords/keys, which really is not the point at all.
BUT, one point IS valid, and I've seen few people mention it:
Time-limited use of STO can still succeed in some cases. If the current implementation of security is only going to exist for a short period of time before being replaced, it could be sufficient, because it takes time to crack the system and find the hole.
As long as you know that the odds of finding the hole before you replace the security system is very small, time-limited STO can be a reasonable compromise between efficiency and security.
Thus, STO can be a valid TEMPORARY security measure.
The danger, of course, is in growing complacent and deciding that the STO is secure just because no one is breaking into it, and leaving it in place for too long.
I seem to recall that it's only the Mircosoft MTU handling that breaks totally when the packet-too-big responses are blocked: the RFC says that in the absence of a response then the MTU should be decreased to the guaranteed low value for all TCP/IP implementations, but apparently Mircosoft's stack just sits there forever expecting the world to adapt to what it wants.
... Sigh.
So, the poor sod running Mircosoft gear can't even get a slow email out asking the offending ISP to allow packet-too-big through
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
So what would happen if i just fft the thingy and invert it back? Filter out some of the higher frequencies (but not enough to destroy the image/sound etc..) .. even w/out knowing where exactly the tags are hidden, wouldn't that mess up the original signature? Or for instance to and D->A->D conversion.. Since obviously they don't want the watermark to mess up the picture/sound looking at it in frequency space may turn up the suspicious looking tags? Am I missing something?
-avi
What you seem to be talking about (I'm really stretching to fathom whatever it is you're trying to say) is a subset of TSP which assumes the triangle inequality (i.e., distances obey geometric rules). Unfortunately, this is a small subset of TSP for which numerous good results are known. Additionally you seem to imply that you were solving the problem on complete graphs, a *severely* restricted subset of TSP for which extremely good results (i.e., linear time in the size of the graph, IIRC) are known.
Some of you might be interested in looking at the Travelling Salesman page at the Stony Brook Algorithms Repository (which I helped put together (sorry for the shameless plug, but ignorance is a terrible thing to let fester)).
"Cause there's 40 different shades of black, so many fortresses and ways to attack, so why you complainin'?"
This guy is mixing up obscurity with secrets ...
(password), shared secrets (asym. crypt) and
algorithms (factoring numbers). Of course
these are the weak things in cryptogarphy,
but this has nothing to do with obscurity,
becaus we *know* them. And using another port
for a web server is a lousy example
Please make him read Bruce Schneier!!!
The example of the Navajo code talkers in WWII is a very poor one. Today that code would be cracked in no time flat. The mass of computing power and knowledge of techniques in cracking such schemes available today as well as the number of people world wide who would be working on such an interesting project would render the code broken very rapidly. How long could that code possibly last today before somebody would suggest that it was similar to some Navajo that she had heard (here I'm using she just to be contrary to the author of the article) somewhere? The code would last a few days before it was found out and maybe a few weeks before a translation program that could do a reasonable word for word translation was available. Even if it was a newly invented language, it would still follow patterns and thus be easily suceptable to automated cracking attempts. Using current schemes is completely different. Passwords must be cracked on a trial and error method. Sure it's possible that somebody comes up w/ a fast implementation for factoring, but if such a thing were to happen, then encryption schemes would change. If you notice, we don't use the same method to encrypt passwords as we did back a few years ago. Think how fast a system could be cracked if that were the truth?
"STO can be a powerful disincentive"
Is it just me, or is this a bit counterintuitive for everybody else out there? If you're a cracker who's bored on a Saturday night and trawling for boxes to get into and you find one that you could only get into by using some kind of brute force cracker to get in are you going to want to do that? Or, are you going to want to crack into some box you find that's mysterious & that you don't know the inner operations of? I personally would prefer to try and find the cock-ups of the designers of the STO'd system and get in that way. I have a feeling that most crackers would prefer this as well, with the exception of Script Kiddies who don't have much of a chance of getting in unless you use a poor STO based system anyway.
I agree with you, if you are the kind of person that can write encryption algorithms of strength comparable to DES and IDEA.
That means, for example, that you understand the DES and IDEA algorithm, and the reasons why they are strong. When you read the DES or IDEA source files, you understand fully why it works that way, and you can change it, and apply new ideas to it. For example, you can create a variation on DESIII and propose DESIV.
If you are that kind of person, you may indeed make your own encryption algorithm. That puts you in the category of specialists, the experts, so to say.
If you are not this level, you may be sure that creating your own encryption scheme is not such a good idea.
Your own encryption scheme will most likely perform worse than the component schemes you have used. It is the same with compression algorithms. Try, for example, to zip or gzip an mpeg-compressed video file. The resulting file will usually be of the same size or bigger than the original file; defeating the object of compressing files. Because the mpeg algorithm heavily takes advantage of the fundamental properties of video data, it is able to compress this kind of data substantially. If you miss the point, and fail to understand the fundamentals of video data, your attempts to compress will not only be much worse than mpeg, you will also be unable to take advantage of the body of research that has been done already on the mpeg algorithm. Therefore, you will not be able to assess the fundamental properties of your algorithm, and the conditions in which it will perform properly or badly.
Even strong encryption algorithms seem to be of varying strength. For example, I see experts writing about weak keys, and other kind of problems that you may encounter; and the strategies that these algorithms implement to alleviate these problems.
If you concoct your own algorithm, you will be unable to assess the conditions in which your own algorithm may seriously lose strength.
Maybe applying 128-bit DES after 128-bit IDEA, reduces the bit strength to an overall 32-bit strength BOGUS algorithm? I don't know. To find out, you need to understand the fundamentals of these algorithms.
The question remains: How good are you at the subject? If you are any less than absolutely excellent, I advise you to stay away from writing your own encryption algorithm and to stop fooling yourself.