Free Republic
Browse · Search
News/Activism
Topics · Post Article

Skip to comments.

Zero Knowledge Proof may Answer Computer Security Question
Scientific Computing ^ | 08/28/2013 - 7:08pm | Bill Steele, Cornell University

Posted on 09/03/2013 9:35:49 AM PDT by null and void

In the age of the Internet, it’s getting harder and harder to keep secrets. When you type in your password, there’s no telling who might be watching it go by. However, new research at Cornell may offer a pathway to more secure communications.

The answer is to not send sensitive information at all. Rafael Pass, associate professor of computer science, has developed a new protocol, or set of rules, to create what computer scientists call a “zero knowledge proof.”

“I think zero knowledge proofs are one of the most amazing notions in computer science,” Pass said. “What we have done is to combine it with another notion — that it’s easier to prove that a computation can be done correctly than it is to actually compute it.”

The result is a way to prove that you know something without saying out loud what it is you know. Instead of insecurely typing the password for your bank account, you just prove to the bank that you know the password. You could pass an exam by proving that you know the answer, without actually writing the answer down so the person sitting next to you can’t copy it.

Applications include password authentication, cryptography, auctions, financial transactions and online voting. “At this point it’s purely theoretical,” Pass cautioned, “but it is teaching us a lot more about how zero knowledge works. That’s what makes me excited.” Pass and colleagues will describe their work at the 54th Annual IEEE Symposium on Foundations of Computer Science, October 27 to 29 in Berkeley, CA.

In its simplest form, such a proof consists of answering questions that depend on having the secret knowledge. To prove you have been in my house, I might ask you what color my cat is. The idea has been around since 1985, and there are already many ways to do it. Early versions required only a few messages being passed back and forth, but were insecure if an attacker participated in many proofs at the same time, as can easily be done on the Internet. An attacker could pick up a little bit of information from each exchange, piecing together the whole secret. Some newer methods will remain secure over many simultaneous exchanges, but instead require many messages being passed back and forth. The new protocol gets the job done with as few as 10 exchanges, Pass said, while remaining secure over many simultaneous exchanges. The researchers supply a rigorous mathematical proof that the protocol is a true zero-knowledge system, and that it works with just a small number of exchanges.

The proof that a zero-knowledge protocol works is the ability to construct a “simulator” that generates a fake conversation indistinguishable from a real one using the protocol, showing that whatever attack the intruder uses against the real conversation produces the same result as attacking the simulation. In other words, the intruder can learn nothing from the real conversation that he couldn’t have learned for himself by running the simulator. But running the simulator requires a lot of computer time, especially if there are many exchanges. The new protocol instead sends a “P-certificate,” certifying that the simulator has been proven to work. A computer program is just a series of logical steps; that it generates a particular output can be proven like any other mathematical statement.

The next step, Pass said, will be to apply the idea to the “man-in-the-middle” attack, where an intruder slips in between two parties to a conversation, making them think they’re talking directly to each other, not only to listen in but sometimes to change the messages as they pass through.

The idea of a zero knowledge proof was introduced by Shafi Goldwasser, Silvio Micali and Charles Rackoff at MIT. This year Goldwasser and Micali received the Turing Award (the equivalent of a Nobel Prize in computer science) for this and related discoveries.


TOPICS: Culture/Society
KEYWORDS: computersecurity; passwords; securityquestion
Interesting.

Although I am always a little skeptical about any claim to uncrackability.

1 posted on 09/03/2013 9:35:49 AM PDT by null and void
[ Post Reply | Private Reply | View Replies]

To: null and void

“...Turing Award (the equivalent of a Nobel Prize in computer science)...”

Given the completely besmirched reputation of the word “Nobel”, ‘twould be better for the Nobel prizes actually requiring intellect and achievement (physics, medicine, etc) to be renamed. The peace and literature prizes have reduced the reputation of the present name to the equivalent of “Yugo” in the automotive world.


2 posted on 09/03/2013 9:42:47 AM PDT by Da Coyote
[ Post Reply | Private Reply | To 1 | View Replies]

To: Da Coyote

Slightly off topic, see tagline...


3 posted on 09/03/2013 9:45:10 AM PDT by null and void (I'm betting on an Obama Trifecta: A Nobel Peace Prize, an Impeachment, AND a War Crimes Trial...)
[ Post Reply | Private Reply | To 2 | View Replies]

To: null and void

Zero Knowledge Proof sounds like a Zero-Sum Gain, IMO...


4 posted on 09/03/2013 9:46:29 AM PDT by Errant
[ Post Reply | Private Reply | To 1 | View Replies]

To: null and void

The Internet is consistent proof of the existence of Zero Knowledge...


5 posted on 09/03/2013 9:50:11 AM PDT by mikrofon (Monday BUMP)
[ Post Reply | Private Reply | To 1 | View Replies]

To: null and void

Making an attacker have to intercept multiple tests, would definitely make it harder.

The downside is that now when I forget my password, and don’t realize I forgot my password, I’ll be sitting through multiple tests before I realize what I no longer know.


6 posted on 09/03/2013 9:51:50 AM PDT by DannyTN
[ Post Reply | Private Reply | To 1 | View Replies]

To: null and void

Making an attacker have to intercept multiple tests, would definitely make it harder.

The downside is that now when I forget my password, and don’t realize I forgot my password, I’ll be sitting through multiple tests before I realize what I no longer know.


7 posted on 09/03/2013 9:51:50 AM PDT by DannyTN
[ Post Reply | Private Reply | To 1 | View Replies]

To: null and void
“I think zero knowledge proofs are one of the most amazing notions in computer science,” Pass said. “What we have done is to combine it with another notion — that it’s easier to prove that a computation can be done correctly than it is to actually compute it.”

This isn't new. algore used this method in the eighties to prove global warming.

8 posted on 09/03/2013 9:53:43 AM PDT by quimby
[ Post Reply | Private Reply | To 1 | View Replies]

To: Da Coyote

Agreed, but many of the Nobel Prizes wimped out on the revolutionary, or controversial science things. When they gave it to Einstein, it was for the photo-electric effect, not relativity, either special or general.

Meta questions for authentication have been used for years. One of the prime problems with passwords is currently requiring passwords that cannot be remembered, even with “security” hints. More than seven letters, upper and lower case, with a number and a symbol...If it is a password that is used infrequently or lost good luck! Writing them down is becoming a necessity, violating the physical security of the password in favor of the electronic security.

This is interesting stuff.

DK


9 posted on 09/03/2013 9:58:29 AM PDT by Dark Knight
[ Post Reply | Private Reply | To 2 | View Replies]

To: Dark Knight

So in a sense, wouldn’t this be like directly using those “secret” questions to gain site access instead of simply to retrieve or reset p/w’s?


10 posted on 09/03/2013 10:03:30 AM PDT by mikrofon (Security BUMP)
[ Post Reply | Private Reply | To 9 | View Replies]

To: mikrofon

It’s Tuesday.


11 posted on 09/03/2013 10:12:03 AM PDT by SoothingDave
[ Post Reply | Private Reply | To 5 | View Replies]

To: DannyTN

You don’t have to know your password. You just have to prove that you should know it.


12 posted on 09/03/2013 10:12:42 AM PDT by SoothingDave
[ Post Reply | Private Reply | To 6 | View Replies]

To: null and void

Sounds like ‘20 Questions’.

Is it animal, vegetable or mineral?

Is it bigger than a breadbox?

Can you put it in your pocket?.......


13 posted on 09/03/2013 10:12:47 AM PDT by Red Badger (It is dangerous to be right in matters where established men are wrong. .....Voltaire)
[ Post Reply | Private Reply | To 1 | View Replies]

To: mikrofon

I think this is just a personalized version of the Eliza idea. Can a computer hold a conversion with a person that is indistinguishable from another person? Can you think of something about a piece of information about a person that does not require disclosing the original info? Oddly enough that is the prime question in reincarnation, because once you disclose the type of information you will seek, people that want to deceive will target that type of info.

The bottom line is always from that great line...three people can keep a secret...if two are dead.

DK


14 posted on 09/03/2013 10:14:05 AM PDT by Dark Knight
[ Post Reply | Private Reply | To 10 | View Replies]

To: null and void

what they are saying could maybe be said as the following

it might be more secure for your bank to NOT ask for a “password” but to somehow crypticly ask, and you cryptically answer, your “security questions” - the ones you set up with them for the questions they would ask to confirm it was you who was admitting your forgot your password


15 posted on 09/03/2013 10:17:49 AM PDT by Wuli
[ Post Reply | Private Reply | To 1 | View Replies]

To: SoothingDave

Ref. my point ;)


16 posted on 09/03/2013 10:20:11 AM PDT by mikrofon (The Internets are never wrong...)
[ Post Reply | Private Reply | To 11 | View Replies]

To: SoothingDave
"You don’t have to know your password. You just have to prove that you should know it."

It's not going to ask you for your password, but it's going to ask you about your password. And if I've forgotten it again, I'll be answering the questions wrong.

17 posted on 09/03/2013 10:23:17 AM PDT by DannyTN
[ Post Reply | Private Reply | To 12 | View Replies]

To: SoothingDave
"You don’t have to know your password. You just have to prove that you should know it."

It's not going to ask you for your password, but it's going to ask you about your password. And if I've forgotten it again, I'll be answering the questions wrong.

18 posted on 09/03/2013 10:23:18 AM PDT by DannyTN
[ Post Reply | Private Reply | To 12 | View Replies]

To: rdb3; Calvinist_Dark_Lord; Salo; JosephW; Only1choice____Freedom; amigatec; Still Thinking; ...

19 posted on 09/03/2013 10:30:40 AM PDT by ShadowAce (Linux -- The Ultimate Windows Service Pack)
[ Post Reply | Private Reply | To 1 | View Replies]

To: null and void

“Instead of insecurely typing the password for your bank account, you just prove to the bank that you know the password.”

And how does my bank KNOW I’m right? It has to KNOW my password.

So if my password is “0bama is a jerk”
will it ask me what the 4th word is? And I type ‘jerk’?

Will it ask me how many A’s in the password? and I type 3?

Splain some more.


20 posted on 09/03/2013 10:38:25 AM PDT by I want the USA back
[ Post Reply | Private Reply | To 1 | View Replies]

To: ShadowAce

by the way the GNOME project has now switched its default search engine from Google to Duckduckgo for “privacy” issues. (and DDG will profit share from sponsored ads)


21 posted on 09/03/2013 10:49:32 AM PDT by GeronL
[ Post Reply | Private Reply | To 19 | View Replies]

To: I want the USA back

I think something like that, maybe.

Perhaps more like the security questions?

What is your favorite movie?
What was the name of your first pet?
What color was your first car?
Who was your favorite teacher?
etc.


22 posted on 09/03/2013 10:56:04 AM PDT by null and void (I'm betting on an Obama Trifecta: A Nobel Peace Prize, an Impeachment, AND a War Crimes Trial...)
[ Post Reply | Private Reply | To 20 | View Replies]

To: null and void

Take zero knowledge proof, subtract any verification at all, and you have liberalism.


23 posted on 09/03/2013 11:14:51 AM PDT by Talisker (One who commands, must obey.)
[ Post Reply | Private Reply | To 1 | View Replies]

To: Dark Knight
Meta questions for authentication have been used for years. One of the prime problems with passwords is currently requiring passwords that cannot be remembered, even with “security” hints. More than seven letters, upper and lower case, with a number and a symbol...If it is a password that is used infrequently or lost good luck! Writing them down is becoming a necessity, violating the physical security of the password in favor of the electronic security.

Agreed. Current password regimes in many corporations has become a nightmare.

We could use crypography to solve the problem, but people are too dumb to use even fairly straightforward crypto like PGP/GPG intelligently.

example:

you and your bank exchange public keys using something like PGP when you set up your account with them.

When you go to the banks site, they encrypt a question to your public key. (what is 1+1?)

You decrypt the message and encrypt the answer back to them.

All of this could be fairly easily be implemented in browsers using plugins, but you'd need people to be capable of managing keys, and also physical security. It's not rocket science, but ou do have to be capable of understanding what is going on, and managing your keys or you're screwed.

24 posted on 09/03/2013 11:21:10 AM PDT by zeugma (Is it evil of me to teach my bird to say "here kitty, kitty"?)
[ Post Reply | Private Reply | To 9 | View Replies]

To: null and void

So instead of typing in my password to access my account, I have to answer 10 questions first? No thanks.


25 posted on 09/03/2013 12:39:36 PM PDT by vrwc1
[ Post Reply | Private Reply | To 1 | View Replies]

To: null and void

Why reinvent the wheel. For me the best security is “something I have” combined “something I know”. This is how my SSH security works as well as my one time password generator.

For example I could have my private key and I has a passphrase to unlock my private key. So if you had my private key you’d still need the passphrase (which doesn’t traverse the network but is only used locally). If you had my passphrase you’d still need my private key. It’s not perfect security but way better than simple passwords.

Or, perhaps even better, a one time password generator program. I enter my passphrase and it spits out a one time passsword that I use one time, and then is no longer valid. Again I need to remember a passphrase to open up the one time password generator but that passphrase remains local to my machine.


26 posted on 09/03/2013 12:40:40 PM PDT by 2 Kool 2 Be 4-Gotten
[ Post Reply | Private Reply | To 1 | View Replies]

To: null and void

The answer is 42.


27 posted on 09/03/2013 12:41:17 PM PDT by dfwgator
[ Post Reply | Private Reply | To 1 | View Replies]

To: null and void

I have to think some more about it, but it has to be better than “What is the name of your first pet?” “My first pet was a fish...?”


28 posted on 09/03/2013 12:43:33 PM PDT by Cyber Liberty (Uncle Miltie: Obama poisoned race relations for a generation. Everything is racial now.)
[ Post Reply | Private Reply | To 1 | View Replies]

To: 2 Kool 2 Be 4-Gotten

The chip in your hand is the something you have, and you type in something you know, your pass phrase, to allow it to generate an access password.

What could possibly go wrong?


29 posted on 09/03/2013 12:51:31 PM PDT by null and void (I'm betting on an Obama Trifecta: A Nobel Peace Prize, an Impeachment, AND a War Crimes Trial...)
[ Post Reply | Private Reply | To 26 | View Replies]

To: Dark Knight

I reached that level, and number of passwords, many years ago.

I’ve been using a program that pops up every time a password is needed with the correct one. I’ve named them so that I know I have the right one. Have over a hundred, nearly all different, and like speed dial, doubt if I even know many of the any more, though I do print out a ledger from time to time in case something goes wrong with the program. So far, in many years, nothing has.

In case you are wondering why I’d keep that kind of stuff on the hard drive, it’s already there, just not organized. After installing the program it gathered together all the passwords I’d used and ‘lined them up’ with the website it went to.


30 posted on 09/03/2013 12:52:30 PM PDT by Balding_Eagle (SWAT stands for Storing Weapons for patriots to Attack Tyranny.)
[ Post Reply | Private Reply | To 9 | View Replies]

To: Cyber Liberty

This is my pet dog, Edick; my pet cat, Edick and my pet fish, Edick...


31 posted on 09/03/2013 12:53:02 PM PDT by null and void (I'm betting on an Obama Trifecta: A Nobel Peace Prize, an Impeachment, AND a War Crimes Trial...)
[ Post Reply | Private Reply | To 28 | View Replies]

To: Balding_Eagle

Same here. I use ‘keepass’. I like giving really massive passwords to websites and see if they choke on them.


32 posted on 09/03/2013 1:01:57 PM PDT by zeugma (Is it evil of me to teach my bird to say "here kitty, kitty"?)
[ Post Reply | Private Reply | To 30 | View Replies]

To: zeugma

I have been thinking of Keepass myself, will it remember for real? I’d hate to have to remember a long string of numbers and letters if it failed.


33 posted on 09/03/2013 1:04:45 PM PDT by GeronL
[ Post Reply | Private Reply | To 32 | View Replies]

To: null and void

Access denied! Access denied! Access denied! Too many attempts, account FROZEN!

Frozen??

Frozen.


34 posted on 09/03/2013 1:24:27 PM PDT by Cyber Liberty (Uncle Miltie: Obama poisoned race relations for a generation. Everything is racial now.)
[ Post Reply | Private Reply | To 31 | View Replies]

To: GeronL

Works great for me. I’ve used it for years. Make sure that your keepass passphrase is a good one. 20 characters minimum. Its a large secret to protect lots of smaller secrets. You’ll be amazed at how quickly you can type one good long password once you get some practice at it.


35 posted on 09/03/2013 1:54:59 PM PDT by zeugma (Is it evil of me to teach my bird to say "here kitty, kitty"?)
[ Post Reply | Private Reply | To 33 | View Replies]

To: zeugma

thanks


36 posted on 09/03/2013 2:02:06 PM PDT by GeronL
[ Post Reply | Private Reply | To 35 | View Replies]

To: null and void
To prove you have been in my house, I might ask you what color my cat is.

I think it was Benjamin Franklin who said, "In the dark, all cats are grey."

Still, he was referring to the benefits of older women. That was from his 1745 publication, Advice to a Young Man on the Choice of a Mistress

Seriously, how about using a pass phrase, as opposed to a password. A pass phrase could be a sentence in a book you're fond of, say, a 1745 publication by Benjamin Franklin (grin) or a song lyric. However, to avoid a dictionary attack, alter some letters. So for example, the phrase "In the dark, all cats are grey." could be written as "1n th3 d@rk, @ll c@t$ @re gr3y." The longer the better. Use spaces just as you would when writing the sentence.

37 posted on 09/03/2013 3:33:07 PM PDT by Alas Babylon!
[ Post Reply | Private Reply | To 1 | View Replies]

To: null and void; ShadowAce
I'm not sure I see why this is so novel. Let's say the idea is to assure my bank that I am who I claim to be, namely the owner of the bank account I wish to access.

What is a password, but an indirect assurance that I am who I claim to be? Okay, here's my thought process...

1. What my bank wants me to prove is that I'm the owner of the account. I can't do that from home, but I can submit a password that only the account owner knows. The password is not me, but it's something I know.

2. So big deal, this Zero Knowledge says I'm NOT going to send the password, but instead I'll answer a set of questions, say, "What color is the front door of the bank?" and I answer "green"; "What's the max MPH that my car's speedometer can indicate?" and I answer "120"; and so on...

I really don't see the difference, categorically. It's just a set of questions instead of one question ("What's the password?"). That is, it's just asking for a series of simpler "passwords", instead of one tough password.

So what am I missing, that makes this approach fundamentally different, and worthy of a Turing prize?

38 posted on 09/03/2013 4:31:14 PM PDT by dayglored (Listen, strange women lying in ponds distributing swords is no basis for a system of government!)
[ Post Reply | Private Reply | To 1 | View Replies]

To: GeronL

I’ve been using Keepass for years.

With Keepass to store you only have to remember only one complex password which is the one to open it. All my others are 15-20 chrs with special characters and all that, where allowed. Those passwords are rarely typed. They are copied and pasted from Keepass so a keylogger would not read them. I think that this is as good as its gets with current technology.

Just be sure to set it to open on Windows secure desktop - review all the security settings .. And of course keep multiple current backups of the Keepass DB.


39 posted on 09/03/2013 6:18:03 PM PDT by expat1000
[ Post Reply | Private Reply | To 33 | View Replies]

To: dayglored

1) It sounds like there is a mathematical engine on the asking side that drives the next question based on some “public key”. (The Bank)
2) The computer submitting the answer (The Customer) doesn’t know in advance which question will be asked, but given a question it knows how to compute an answer - something it can derive based on the question in #1 but only because it has a secret key.
3) Even after listening to several days worth of transactions, an attacker (The Hacker) seeking the password still couldn’t figure it out.

So, a horribly rough allegory might be the old idea of someone giving a page, paragraph and word ordinal. Both the bank and the customer would have a rare book and would be able to synchronize but an observer without the book wouldn’t be able to guess what the next answer should be, even after listening to several challenges and responses.


40 posted on 09/06/2013 10:31:27 PM PDT by mbj
[ Post Reply | Private Reply | To 38 | View Replies]

Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.

Free Republic
Browse · Search
News/Activism
Topics · Post Article

FreeRepublic, LLC, PO BOX 9771, FRESNO, CA 93794
FreeRepublic.com is powered by software copyright 2000-2008 John Robinson