I'm not talking about back doors. I'm talking
about bloating it up so damn much, that you
have stupid security bugs. For those with short
memories, there was a bug involving their
implementation of ADK's that would allow somebody
to essentially get an extra copy of encrypted messages that they could read. All this
for a feature like ADK, that no sane person
would want in their encryption product (basically
a form of allegedly voluntary backdoor in the encryption).
I want a program with source that I can read
and understand. Not some big bloated crap
that even their developer's can't understand.
I think you (as well as the people trying to
chase out this web site) are also misinterpreting
the intent of the zoning laws.
In the case you
mention, the people you claim will be coming
around are not the clientel. They are thieves.
The zoning laws address the negative
effects of the presence of your clientel,
not some guy breaking into your house who never
bought anything at your business.
Under your interpretation of zoning laws,
any shop with valuables could get zoned out
because it might draw thieves.
Either the NSA can factor or it can't.
If they can,
then using modern encryption doesn't really burden
them. If they can't, then no amount of ass-kissing and not using encryption is going to let them break the encryption of the terrorists who are going to be using REAL software without the government-mandated backdoors (murder is illegal too; did they respect that law?).
Think they just need a few more computers and a few less messages to sift through? You need to do a little more research about modern crypto. We're talking about things like the heat death of the universe happening before all computers in the world could finish factoring numbers that large (if factoring is "hard").
Outlawing encryption will not have any effect on these people. They don't respect our laws. The only effect will be to break the security of on-line transactions (over SSL for example). Backdoored schemes are broken schemes. A panel of a dozen great minds in the industry have already shown this: Rivest, Schneier, Diffie, etc.
Read the paper here.
If you want stable and safe on-line transactions,
you don't want the government mandating backdoors in encryption products.
I want to stop terrorists as much as the next
guy, but let's thinks about measures that will
actually HELP US DO THAT before acting. Things that are inconvenient and intrusive don't
necessarily increase safety.
As long as it follows published encryption algorithms, that's all that matters. After all, if it doesn't follow the standard, then it's kind of hard to decrypt it.
This is so wrong that I don't even know where
to start.
The program can use published algorithms everywhere, but if it RSA encrypts your message
in the FBI's public key, and mails it to them (as well as encrypting as it should be and mailing to your friend), then it isn't exactly a secure email program. The only way to know if the program is doing stuff like this is to READ THE SOURCE.
To trust that a security-related program does not have a back door, you need the source. Period.*
*You could try to watch outgoing network
connections, but this is a hack as you may not
be able to figure out what it is sending since
it could be encrypted. Having the source is
a much more reliable method of spotting back
doors.
Frankly, if that helps stop bombs from going off at olympic games and helps track down illegal
malitias, hate groups, etc. then Im all for it!
This is exactly the non-sense that keeps average people in support of things like Carnivore: the false sense of security. Hard-core terrorists have been using encryption for a while, and aren't going to be bothered by Carnivore.
Terrorism is the boogeyman that they always bring out to justify increased surveillance.
The end result is a loss in privacy and no
effect on stopping intelligent criminals.
This is why DSL *will* save you (us). With DSL you have choice, and you can pick a great ISP like Speakeasy. With cable, you're stuck with
whoever is serving your area.
No. You're stuck with whoever
is serving your area, regardless of whether it is cable or DSL. It's not like DSL goes everywhere
and Speakeasy serves everyone. If you're lucky
enough to be near a central office, then
yes, you can pick Speakeasy.
Agreed on the buying the OpenBSD CD's (only
one shirt though:)
I've never purchased a Linux distro (it's been
a few years since I ran Linux at all).
I've purchased OpenBSD 2.7 and 2.9 (about $30us
each) in the last ten months or so.
I've never paid for Microsoft products.
Once I was given a free (legitimate) student copy of Visual J++ for a class (the worst compiler I
have ever interacted with). That went in the
trash but I kept the free NT Workstation 4.0
disc it came with (which I've used some).
Overall, I like OpenBSD much better for what I
use it for (firewall/NAT and pen testing).
I could download the new versions,
but I feel like supporting them with some cash.
Given that my ipf logs on my old cable modem
connection showed at least a half-dozen hostile
probes per day (Sub7, portmap, linuxconf,
bind, etc.), I wouldn't settle for any other
OS security-wise.
One possibility other than the ones already mentioned is to use libcrypto.a from the OpenSSL library (www.openssl.org). There is a part of that called 'bn' that is used for arbitrarily large integers (like in RSA keys).
Bitch all you want about Theo forking off of things. The fact is, in both of the things you name (SSH and BSD), his fork is superior in terms of what he wanted (security and license terms).
The guy isn't a diplomat, but his work is rock solid. I hardly think your claim about OpenSSH being OpenBSD centric is valid. People from OpenBSD do most of the work on it. I doubt it takes too long to make patches for ports to other BSD's. It's not like they can go to ssh.com and ask them for the source or something. OpenSSH allowed the open source people to continue using the protocol through version 2. They should be praised; not derided.
Theo was right to kick IPF out of OpenBSD if this guy is going to screw around with his licensing terms. The OpenBSD people have been clear from the start what their licensing terms were. This IPF guy has been deliberately vague and misleading about his terms. Now that it has come to light, the result should not be surprising.
The reality of this IPF fork is that it will be a quality project that more people will be able to use (because it will be a BSD license and not this semi-closed game playing from Mr. Reed).
It ISN'T NP-hard. Remember that an NP-hard problem is one where, even if you had a proposed solution, you can't verify the answer in
polynomial time.
Your definition of NP-hard is way off. A problem being NP-hard
means that all problems in NP are reducible to
that problem. In plain english, it means that
a quick solution to an NP-hard problem would
yield a quick solution to all problems in NP.
A problem that is both NP-hard and in the
set NP is called NP-complete.
Satisfiability is NP-hard (as it is NP-complete),
and it can be verified in polynomial time (just
verify that the formula evaluates to true given
the binding). In fact, any NP-complete problem
can be verified in polynomial time as having
this property is one way to define the set NP
(languages with polynomial time verification
proofs).
Verifying a factorization answer is easy: just multiply. That's polynomial time, therefore factoring isn't NP-hard.
Again, this is way off.
Most problems in NP are known to be either
NP-complete or in the set P. Factoring is one
of the few that is not known to be in either
category. I believe graph isomorphism is another.
You can't just say factoring "isn't" NP-hard.
It hasn't been proven that it is not. Researchers
don't think it is, but until it is proven to be
in P, this is just a hunch.
That's as opposed to Travelling Salesman where even if you have a proposed path, you'd have to check all possible paths to decide if yours was the minimum.
Here you are confusing problems and languages.
Technically, when I mentioned 'problem' earlier,
I should have said 'language'. Problems must
be phrased as languages to apply complexity
theory to them. When you frame Travelling Salesman
as a language, it looks something like:
"Does this graph have a salesman path of length
less than x?" Languages must have yes/no answers,
unlike the open-ended Travelling Salesman problem.
Phrased as a language, even Travelling Salesman
has polynomial time verification (as it should
as it is NP-complete).
This business of keeping security flaws secret
amongst members of this "elite" group is hardly
meaningful given that the bulk of security
flaws in these companies' products are probably
found by people who are outside of the group.
This policy will only matter in the event
that someone within one of these companies
is the first person to discover the flaw.
Given that many flaws will be found by people
outside of this group, and that it only takes
one source to leak a flaw, I doubt this
supposed secrecy will be very secret.
Unlike SRP, B-SPEKE et al, Kerberos is *not* a ZKP password protocol.
You're right that Kerberos isn't a zero knowledge
protocol. You're wrong about SRP, B-SPEKE, etc.
Those aren't zero knowledge either. Sure it may
be hard to mount dictionary attacks on them,
but that does not make them zero knowledge.
I wrote more about this in a thread of its
own called "Zero Knowledge" on this article.
Other ZKP (Zero Knowledge Protocols) protocols such as SRP allow you to prove your identity to a server without ever sending any sensitive data (like your password) over
the network. Implementing Kerberos, SRP or other ZKP protocols into SSH would make man in the middle
attacks more difficult.
Neither SRP nor Kerberos are zero knowledge
protocols. A zero knowledge protocol ('proof'
is actually a better term than 'protocol' here)
is a very specific mathematical thing. It involves
a prover proving something to a verifier in
such a way that the verifier does not gain the
prover's knowledge; only the fact the the prover
has that knowledge.
As an example, it is possible to do a zero
knowledge proof to some verifier that I know the
discrete logarithm of a given number (mod some
prime p) without giving away what
that logarithm is. The verifier does not learn
anything from this. The official definition
says that the verifier himself could have
simulated anything I said during the proof.
This official definition (a simulation argument)
is what is missing with things like SRP and
Kerberos.
Ignorant security "experts" (Seifried and
others) spout off stuff
like "well, it doesn't look like you send out
any important info, so it's zero knowledge".
Zero knowledge is a not a flashy adjective to
toss around to impress people; it's a mathematically precise term. It requires formalism (a simulation argument) for a protocol to earn
this designation, not just some rambling and
hand-waving.
Bruce Schneier's book Applied Cryptography
has sort of a brief introduction to the topic.
For more info, one should look into the cryptographic
literature. I believe Schneier's book lists
some good papers on the subject in the references.
It lacks any mechanism for non-blocking I/O,
forcing you to use threads to handle multiple
incoming connections on a server.
C/C++ have non-blocking I/O and select() which
allow handling of multiple connections in
one thread/process without a problem.
This is impossible in Java (you will block
on a socket that has no data, starving a
connection that does have data ready).
Considering that the average programmer is not
savvy enough to write threaded programs
correctly (without races/deadlocks), I would
hardly call Java's network interface incredible
in this respect.
Anti-virus software is great after the first
wave of destruction hits from a new virus.
If your company is part of that first wave,
anti-virus software does nothing at all to
protect you.
Managers may love whatever scheduling capabilities
that Exchange/Outlook by them, but they are
deluding themselves if they think anti-virus
software solves all of the security woes that
Outlook will bring them. The gain from the
features must be weighed against the VERY
real security flaws of Exchange/Outlook that will
not be solved by any amount of anti-virus
software.
Any realistic cost assessment should account
for the possibility of all desktop machines
getting wiped clean by the next generation
of Outlook viri (that delete everything in
sight, and don't even have to be opened or read
to be triggered). The Lovebug was just the
tip of the iceberg. Scheduling meetings at the
click of the button may not be worth this.
Re:Difference between NP-complete and NP-hard?
on
Does P = NP?
·
· Score: 1
Someone already responded to this, but I think
I have a more clear answer:
By definition, a language L is NP-complete
if it is both in the class NP and is NP-hard.
So a language that is NP-complete is always
NP-hard. Not all languages that are NP-hard
are NP-complete, since they may not be in
the class NP.
Roughly speaking, NP-hard means that it is as
hard as any other language in NP. Put another
way, if you can solve an NP-hard problem
quickly, you can solve any problem in NP
quickly.
In the case of this article, this clique
partitioning problem is known to be NP-hard,
but I don't think it is known to be in NP,
which explains why they aren't referring to
it as NP-complete.
Generally, the usefulness of Quantum Computers would come from the inability of a classical computer to solve NP-hard from problems, since
there have been solutions found in Quantum algorithms for simulating NP-hard problems in polynomial time. Of course, it can't be proved that
NP-hard can't be solved in polynomial time on a classical computer.
Actually, neither one of these statements is
correct. First of all, noone has come up with a
quantum algorithm for solving even one of the
NP-hard
problems in polynomial time. Yes, there is a
quantum algorithm for factoring, but factoring
is not NP-hard. I know a bit about this since
I worked on a quantum algorithm for solving
SAT (an NP-hard problem), and studied a good
bit of the previous literature on this.
Second, your statement that it can't be proven
that NP-hard problems can't be solved in
polynomial time on a classical computer is
also false. If one day, it is proven that
P != NP, then this is exactly what will be
proven: NP-hard problems have no polynomial
time solutions.
Quantum computing won't change this (in the
forseeable future) for two reasons:
# of Qubits
The current state of the art quantum computer
does not have enough qubits to really do
anything useful. The progress rate (how often
the number of qubits is upped) is not fast,
and I suspect it will slow at the larger numbers
as it gets much harder to make sure that some
cosmic ray doesn't hit your machine screwing
it all up ("measuring" the state).
No quantum keysearch algorithm
Quantum computing isn't some silver bullet
that solves every crypto problem instantly.
Quantum computers are very fast at factoring
and at taking discrete logarithms, which most
modern public key algorithms are based on.
However, to this day there aren't any general
quantum algorithms for exhausting a keyspace
quickly. Don't believe the inaccurate "does
everything but in parallel" descriptions that
the tech media keeps spouting off. It's
not telling the whole story on how quantum
algorithms work. To do things in parallel,
the bogus answers (keys here) must cancel
each other out (like in vector addition),
leaving the real answer. You can't just
say, "try all keys at once". It's not that
simple.
Isn't this the same moron that claimed to
have invented Syn cookies the other week?
His credibility was bad already. This ridiculous
drivel is even more over the top. I'd like
to see him probe my internal network to
"reveal my machine's TRUE local private-network IP address". Assuming he could (OpenBSD with
NAT/IPFilter providing no services; doubtful),
he would discover that my 'secret private network
IP' is something in 192.168.0.*. There's some
pretty useful information: an internal network
that doesn't use valid IP addresses!
Enough submissions about this guy's 'advanced
technology' already.
Don't get your panties in a bunch about me posting this question here. I'm posting it there as well,
but I thought it more interesting than most of
what had been posted here on/. about it.
What do you have to say about complexity and
its detrimental impact on security systems?
PGP seems to be a case study in this in that the
recent bug has no effect on the older, simpler
PGP 2.6. As requests for features by everyone
from paranoid hackers (bigger keys) to corporations (ADK's) come in, it is natural
to want to add things to software. The problem
is that as the software gets more complex,
dangerous flaws get much harder to spot (even
in open source software). Once a bug like this
creeps in, the "feature-rich" software is
significantly less useful than the old version
in that it doesn't accomplish its original
goal: privacy.
How do you think one should go about trying
to achieve a good balance of features/complexity
and security?
Just make sure, when you get someone's
public key, that it comes from an "authentic"
source
This is potentially bad reasoning.
The whole problem with this vulnerability
is that it is difficult to detect if someone
has altered a V4 public key with an ADK because
one of the places for inserting ADK's is not
included in the checksum (fingerprint) of
the key. So they key will appear to be
perfectly self-signed even after tampering.
If you mean by "authentic" source, that your
trusted friend emails you his key, this is not
safe.
Email is alterable. An adversary can insert
an ADK into the mailed key, that will not
be visible to you without specific scrutiny
with a hex editor or special GPG incantations.
Use GPG (or PGP 2.6) with old style V3 keys
to prevent all of these attacks.
I you use an old V3 RSA key (the ones that
PGP 2.6 creates), then there is no way they
are inadvertantly encrypting stuff that
an adversary can read (while thinking it is
to you).
Ir you are using a new-style key (v4 of any
of the two crypto algorithms), then your
analysis is correct. Someone with the broken
software may inadvertantly send mail thinking
that it is only readable by you, when in fact
it is readable by anyone who tampered with
their copy of your public key.
This is very much worth knowing with all of
the misguided "I use GPG so I am safe"
posts floating around. Only old V3 keys are safe
from other peoples' bunk software.
ReconRich writes: Quantum computers are theorized to solve all NP problems in tractable time
Quantum computers are not some panacea to solve all of the worlds hard problems. They are good for a select few problems (search, factoring, discrete log, basically). They are not faster on all problems. Specifically, there is no quantum algorithm for solving even one of the NP-complete problems, nor is there a quantum algorithm for doing quick brute-force keyspace searches.
Also, arguing that public key crypto is somehow weak because it is tied to the problem of P vs. NP is not particulary scary to most theoreticians. I think quantum computers will be viable before P is found equal to NP, and even quantum computers will take a LONG time to be able to handle modern key sizes.
Digital content distribution is never going to be secured with encryption or anything else for that matter.
It is pointless to develop stronger and stronger crypto for these kinds of problems because ultimately, the digital content is presented in the clear for the end user. The only way to prevent the user from copying the digital content at this point is by mandating the use of specific software (or hardware) players that don't have hooks for output redirection or copying. This will never work for two reasons:
Software can be reverse engineered
Motivated hackers can disassemble the player, find the buffer holding the unencrypted content, and provide hooks to copy this buffer. In the case of hardware players, the process is similar. "Tamper-proof" hardware is anything but (Ross Anderson has a nice paper illustrating this here). Note that layers of industrial strength crypto mean absolutely nothing at this point.
Analog Route
If the above "perfect copy" method doesn't work or is too difficult, one can always revert to analog methods: take a picture of the image, record the music from the speaker with a microphone, etc.
Basically, once you give someone unencrypted information, there is no way to take it back. If they want to copy it at that point, they will.
Slashdot Mirror
I'm not talking about back doors. I'm talking about bloating it up so damn much, that you have stupid security bugs. For those with short memories, there was a bug involving their implementation of ADK's that would allow somebody to essentially get an extra copy of encrypted messages that they could read. All this for a feature like ADK, that no sane person would want in their encryption product (basically a form of allegedly voluntary backdoor in the encryption).
I want a program with source that I can read and understand. Not some big bloated crap that even their developer's can't understand.
Complexity breeds insecurity, intended or not.
In the case you mention, the people you claim will be coming around are not the clientel. They are thieves. The zoning laws address the negative effects of the presence of your clientel, not some guy breaking into your house who never bought anything at your business.
Under your interpretation of zoning laws, any shop with valuables could get zoned out because it might draw thieves.
Either the NSA can factor or it can't. If they can, then using modern encryption doesn't really burden them. If they can't, then no amount of ass-kissing and not using encryption is going to let them break the encryption of the terrorists who are going to be using REAL software without the government-mandated backdoors (murder is illegal too; did they respect that law?).
Think they just need a few more computers and a few less messages to sift through? You need to do a little more research about modern crypto. We're talking about things like the heat death of the universe happening before all computers in the world could finish factoring numbers that large (if factoring is "hard").
Outlawing encryption will not have any effect on these people. They don't respect our laws. The only effect will be to break the security of on-line transactions (over SSL for example). Backdoored schemes are broken schemes. A panel of a dozen great minds in the industry have already shown this: Rivest, Schneier, Diffie, etc. Read the paper here.
If you want stable and safe on-line transactions, you don't want the government mandating backdoors in encryption products.
I want to stop terrorists as much as the next guy, but let's thinks about measures that will actually HELP US DO THAT before acting. Things that are inconvenient and intrusive don't necessarily increase safety.
This is so wrong that I don't even know where to start.
The program can use published algorithms everywhere, but if it RSA encrypts your message in the FBI's public key, and mails it to them (as well as encrypting as it should be and mailing to your friend), then it isn't exactly a secure email program. The only way to know if the program is doing stuff like this is to READ THE SOURCE.
To trust that a security-related program does not have a back door, you need the source. Period.*
*You could try to watch outgoing network connections, but this is a hack as you may not be able to figure out what it is sending since it could be encrypted. Having the source is a much more reliable method of spotting back doors.
This is exactly the non-sense that keeps average people in support of things like Carnivore: the false sense of security. Hard-core terrorists have been using encryption for a while, and aren't going to be bothered by Carnivore.
Terrorism is the boogeyman that they always bring out to justify increased surveillance. The end result is a loss in privacy and no effect on stopping intelligent criminals.
No. You're stuck with whoever is serving your area, regardless of whether it is cable or DSL. It's not like DSL goes everywhere and Speakeasy serves everyone. If you're lucky enough to be near a central office, then yes, you can pick Speakeasy.
I've never purchased a Linux distro (it's been a few years since I ran Linux at all).
I've purchased OpenBSD 2.7 and 2.9 (about $30us each) in the last ten months or so.
I've never paid for Microsoft products. Once I was given a free (legitimate) student copy of Visual J++ for a class (the worst compiler I have ever interacted with). That went in the trash but I kept the free NT Workstation 4.0 disc it came with (which I've used some).
Overall, I like OpenBSD much better for what I use it for (firewall/NAT and pen testing). I could download the new versions, but I feel like supporting them with some cash.
Given that my ipf logs on my old cable modem connection showed at least a half-dozen hostile probes per day (Sub7, portmap, linuxconf, bind, etc.), I wouldn't settle for any other OS security-wise.
One possibility other than the ones already mentioned is to use libcrypto.a from the OpenSSL library (www.openssl.org). There is a part of that called 'bn' that is used for arbitrarily large integers (like in RSA keys).
The guy isn't a diplomat, but his work is rock solid. I hardly think your claim about OpenSSH being OpenBSD centric is valid. People from OpenBSD do most of the work on it. I doubt it takes too long to make patches for ports to other BSD's. It's not like they can go to ssh.com and ask them for the source or something. OpenSSH allowed the open source people to continue using the protocol through version 2. They should be praised; not derided.
Theo was right to kick IPF out of OpenBSD if this guy is going to screw around with his licensing terms. The OpenBSD people have been clear from the start what their licensing terms were. This IPF guy has been deliberately vague and misleading about his terms. Now that it has come to light, the result should not be surprising.
The reality of this IPF fork is that it will be a quality project that more people will be able to use (because it will be a BSD license and not this semi-closed game playing from Mr. Reed).
Your definition of NP-hard is way off. A problem being NP-hard means that all problems in NP are reducible to that problem. In plain english, it means that a quick solution to an NP-hard problem would yield a quick solution to all problems in NP. A problem that is both NP-hard and in the set NP is called NP-complete.
Satisfiability is NP-hard (as it is NP-complete), and it can be verified in polynomial time (just verify that the formula evaluates to true given the binding). In fact, any NP-complete problem can be verified in polynomial time as having this property is one way to define the set NP (languages with polynomial time verification proofs).
Verifying a factorization answer is easy: just multiply. That's polynomial time, therefore factoring isn't NP-hard.
Again, this is way off. Most problems in NP are known to be either NP-complete or in the set P. Factoring is one of the few that is not known to be in either category. I believe graph isomorphism is another. You can't just say factoring "isn't" NP-hard. It hasn't been proven that it is not. Researchers don't think it is, but until it is proven to be in P, this is just a hunch.
That's as opposed to Travelling Salesman where even if you have a proposed path, you'd have to check all possible paths to decide if yours was the minimum.
Here you are confusing problems and languages. Technically, when I mentioned 'problem' earlier, I should have said 'language'. Problems must be phrased as languages to apply complexity theory to them. When you frame Travelling Salesman as a language, it looks something like: "Does this graph have a salesman path of length less than x?" Languages must have yes/no answers, unlike the open-ended Travelling Salesman problem. Phrased as a language, even Travelling Salesman has polynomial time verification (as it should as it is NP-complete).
This policy will only matter in the event that someone within one of these companies is the first person to discover the flaw.
Given that many flaws will be found by people outside of this group, and that it only takes one source to leak a flaw, I doubt this supposed secrecy will be very secret.
You're right that Kerberos isn't a zero knowledge protocol. You're wrong about SRP, B-SPEKE, etc. Those aren't zero knowledge either. Sure it may be hard to mount dictionary attacks on them, but that does not make them zero knowledge.
I wrote more about this in a thread of its own called "Zero Knowledge" on this article.
Neither SRP nor Kerberos are zero knowledge protocols. A zero knowledge protocol ('proof' is actually a better term than 'protocol' here) is a very specific mathematical thing. It involves a prover proving something to a verifier in such a way that the verifier does not gain the prover's knowledge; only the fact the the prover has that knowledge.
As an example, it is possible to do a zero knowledge proof to some verifier that I know the discrete logarithm of a given number (mod some prime p) without giving away what that logarithm is. The verifier does not learn anything from this. The official definition says that the verifier himself could have simulated anything I said during the proof. This official definition (a simulation argument) is what is missing with things like SRP and Kerberos.
Ignorant security "experts" (Seifried and others) spout off stuff like "well, it doesn't look like you send out any important info, so it's zero knowledge". Zero knowledge is a not a flashy adjective to toss around to impress people; it's a mathematically precise term. It requires formalism (a simulation argument) for a protocol to earn this designation, not just some rambling and hand-waving.
Bruce Schneier's book Applied Cryptography has sort of a brief introduction to the topic. For more info, one should look into the cryptographic literature. I believe Schneier's book lists some good papers on the subject in the references.
It lacks any mechanism for non-blocking I/O, forcing you to use threads to handle multiple incoming connections on a server.
C/C++ have non-blocking I/O and select() which allow handling of multiple connections in one thread/process without a problem.
This is impossible in Java (you will block on a socket that has no data, starving a connection that does have data ready).
Considering that the average programmer is not savvy enough to write threaded programs correctly (without races/deadlocks), I would hardly call Java's network interface incredible in this respect.
Managers may love whatever scheduling capabilities that Exchange/Outlook by them, but they are deluding themselves if they think anti-virus software solves all of the security woes that Outlook will bring them. The gain from the features must be weighed against the VERY real security flaws of Exchange/Outlook that will not be solved by any amount of anti-virus software.
Any realistic cost assessment should account for the possibility of all desktop machines getting wiped clean by the next generation of Outlook viri (that delete everything in sight, and don't even have to be opened or read to be triggered). The Lovebug was just the tip of the iceberg. Scheduling meetings at the click of the button may not be worth this.
By definition, a language L is NP-complete if it is both in the class NP and is NP-hard.
So a language that is NP-complete is always NP-hard. Not all languages that are NP-hard are NP-complete, since they may not be in the class NP.
Roughly speaking, NP-hard means that it is as hard as any other language in NP. Put another way, if you can solve an NP-hard problem quickly, you can solve any problem in NP quickly.
In the case of this article, this clique partitioning problem is known to be NP-hard, but I don't think it is known to be in NP, which explains why they aren't referring to it as NP-complete.
Actually, neither one of these statements is correct. First of all, noone has come up with a quantum algorithm for solving even one of the NP-hard problems in polynomial time. Yes, there is a quantum algorithm for factoring, but factoring is not NP-hard. I know a bit about this since I worked on a quantum algorithm for solving SAT (an NP-hard problem), and studied a good bit of the previous literature on this.
Second, your statement that it can't be proven that NP-hard problems can't be solved in polynomial time on a classical computer is also false. If one day, it is proven that P != NP, then this is exactly what will be proven: NP-hard problems have no polynomial time solutions.
The current state of the art quantum computer does not have enough qubits to really do anything useful. The progress rate (how often the number of qubits is upped) is not fast, and I suspect it will slow at the larger numbers as it gets much harder to make sure that some cosmic ray doesn't hit your machine screwing it all up ("measuring" the state).
Quantum computing isn't some silver bullet that solves every crypto problem instantly. Quantum computers are very fast at factoring and at taking discrete logarithms, which most modern public key algorithms are based on. However, to this day there aren't any general quantum algorithms for exhausting a keyspace quickly. Don't believe the inaccurate "does everything but in parallel" descriptions that the tech media keeps spouting off. It's not telling the whole story on how quantum algorithms work. To do things in parallel, the bogus answers (keys here) must cancel each other out (like in vector addition), leaving the real answer. You can't just say, "try all keys at once". It's not that simple.
His credibility was bad already. This ridiculous drivel is even more over the top. I'd like to see him probe my internal network to "reveal my machine's TRUE local private-network IP address". Assuming he could (OpenBSD with NAT/IPFilter providing no services; doubtful), he would discover that my 'secret private network IP' is something in 192.168.0.*. There's some pretty useful information: an internal network that doesn't use valid IP addresses!
Enough submissions about this guy's 'advanced technology' already.
Don't get your panties in a bunch about me posting this question here. I'm posting it there as well, but I thought it more interesting than most of what had been posted here on /. about it.
PGP seems to be a case study in this in that the recent bug has no effect on the older, simpler PGP 2.6. As requests for features by everyone from paranoid hackers (bigger keys) to corporations (ADK's) come in, it is natural to want to add things to software. The problem is that as the software gets more complex, dangerous flaws get much harder to spot (even in open source software). Once a bug like this creeps in, the "feature-rich" software is significantly less useful than the old version in that it doesn't accomplish its original goal: privacy.
How do you think one should go about trying to achieve a good balance of features/complexity and security?
This is potentially bad reasoning.
The whole problem with this vulnerability is that it is difficult to detect if someone has altered a V4 public key with an ADK because one of the places for inserting ADK's is not included in the checksum (fingerprint) of the key. So they key will appear to be perfectly self-signed even after tampering.
If you mean by "authentic" source, that your trusted friend emails you his key, this is not safe. Email is alterable. An adversary can insert an ADK into the mailed key, that will not be visible to you without specific scrutiny with a hex editor or special GPG incantations.
Use GPG (or PGP 2.6) with old style V3 keys to prevent all of these attacks.
I you use an old V3 RSA key (the ones that PGP 2.6 creates), then there is no way they are inadvertantly encrypting stuff that an adversary can read (while thinking it is to you).
Ir you are using a new-style key (v4 of any of the two crypto algorithms), then your analysis is correct. Someone with the broken software may inadvertantly send mail thinking that it is only readable by you, when in fact it is readable by anyone who tampered with their copy of your public key.
This is very much worth knowing with all of the misguided "I use GPG so I am safe" posts floating around. Only old V3 keys are safe from other peoples' bunk software.
Quantum computers are not some panacea to solve all of the worlds hard problems. They are good for a select few problems (search, factoring, discrete log, basically). They are not faster on all problems. Specifically, there is no quantum algorithm for solving even one of the NP-complete problems, nor is there a quantum algorithm for doing quick brute-force keyspace searches.
Also, arguing that public key crypto is somehow weak because it is tied to the problem of P vs. NP is not particulary scary to most theoreticians. I think quantum computers will be viable before P is found equal to NP, and even quantum computers will take a LONG time to be able to handle modern key sizes.
It is pointless to develop stronger and stronger crypto for these kinds of problems because ultimately, the digital content is presented in the clear for the end user. The only way to prevent the user from copying the digital content at this point is by mandating the use of specific software (or hardware) players that don't have hooks for output redirection or copying. This will never work for two reasons:
Motivated hackers can disassemble the player, find the buffer holding the unencrypted content, and provide hooks to copy this buffer. In the case of hardware players, the process is similar. "Tamper-proof" hardware is anything but (Ross Anderson has a nice paper illustrating this here). Note that layers of industrial strength crypto mean absolutely nothing at this point.
If the above "perfect copy" method doesn't work or is too difficult, one can always revert to analog methods:
take a picture of the image, record the music from the speaker with a microphone, etc.
Basically, once you give someone unencrypted information, there is no way to take it back. If they want to copy it at that point, they will.