Image Image Image




Post new topic Reply to topic  [ 14 posts ] 
Author Message
 Post subject: Protocol Authors [confidentiality]
PostPosted: Mon Nov 05, 2007 11:42 am 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
For all authors of the protocol, there will be simple mean to provide confidentiallity but also allow later revealing that (of course everyone is free to participate with his real name from the very beginning).

This should be some public/private key scheme (where nickname and public key are provided for the document). Feel free to suggest how this should look exactly.

The requirements are:
1) author provides nickname, that is included in the list of authors
2) author provides number, or other key, or other mean that is included as part of the specification (in any of the apendices)
3) the "key" described in 2) need to make possible at any point of time the author to reveal it's confidentiallity, i.e. claim that he is the guy behind the provided nickname, and have a 100% mean to prove that (as well as makes impossible for anyone else beside the real author to claim authorship)

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sat Dec 29, 2007 10:54 am 
Offline
PokerAI fellow
User avatar

Posts: 686
Location: Midwest, USA
Favourite Bot: N/A
A simple way of doing this would be to pick a secret phrase like:
"Timmy's real name is John Doe."
And then provide a MD5 hash for it publicly.

So I could provide the hash "a7fb80df741d9e4d32dcc7ccf8163cdd" and that could be published. At a later date, if I wish to reveal my identity, I simply provide the original secret phrase and anyone can check that it matches the hash.

I think MD5 would be a good choice because:
It's readily available.
It uses a plain text format.
It's easy to understand the process.

To make a hash hard to crack it'd need to be long and fairly random (i.e. don't phrase it exactly like my example, be creative). My above secret text is 30 characters, so to brute force it you'd need to try about (letters + numbers + punctuation = 95^30 length) 2.15 * 10^59. Probably feasible to crack in another century or two? If you'd like more security you can probably just add some random garbage to the end.

Or if you go with a more complicated real encryption algorithm it will also be crackable. And you can't use an uncrackable one time pad for this purpose. :lol:

MD5 in Wikipedia
Online MD5 calculator

Of course I'm not a security expert, so it's very possible I missed something.


Top
 Profile  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sat Dec 29, 2007 3:10 pm 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
The complexity of breaking the hash should be similar to the hash size (i.e. 2^128 for MD5) and not the initial string length: Many strings/passwords produce one and the same hash, and we cannot have a requirement that the string, known by the author only, "make sense" (like in your example).

All in all, MD5 is not very strong.

Therefore it might be that MD5 is a tradeoff between compromising your privacy against making it easier for 3rd party inproperly claiming ownership.

Quote:
The hash() function is a one-way encryption algorithm that can be decrypted only by brute force. MD5 hashing as a method of securing passwords and other data falls apart when one does a Google search of "MD5 crack." For unsalted hashes, the time needed to crack a single MD5 hash online is about 40 minutes (http://passcracking.com). Depending on your personal computer speeds, this can be done faster with a tool like md5crack (http://www.checksum.org/download/MD5Crack). In fact, in 1994 Paul van Oorschot and Mike Wiener showed that a brute force attack on a 128-bit hash function requires 264 (2.1019) evaluations to crack; at the time such a crack would take less than a month with a $10 million investment in hardware.

To deal with the shortcomings of 128-bit hash functions, stronger encryption algorithms have been invented. Today's 160-bit encryption algorithms such as SHA1 (secure hash algorithm, http://www.w3.org/PICS/DSig/SHA1_1_0.html) and RipeMD160 (http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html) increase the time required for a brute force attack. For areas where a 160-bit hash is still not strong enough, SHA also comes in 256-bit, 384-bit, and 512-bit data lengths for added security in one-way encryption



But all in all I think this is good idea to go for MD5. I don't think someone will have such a huge cracking desire to claim ownership of 3rd party open source work :)

And in case of issues, there are still ways to resolve disputes.

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sat Dec 29, 2007 10:00 pm 
Offline
PokerAI fellow
User avatar

Posts: 686
Location: Midwest, USA
Favourite Bot: N/A
indiana wrote:
The complexity of breaking the hash should be similar to the hash size (i.e. 2^128 for MD5) and not the initial string length: Many strings/passwords produce one and the same hash, and we cannot have a requirement that the string, known by the author only, "make sense" (like in your example).
Why can't you have the requirement? Why can't you say the hash must contain your nickname here as well as your real, and add in some random fluff for good measure? That was kind of the whole point of what I was saying. If it "makes sense", then the only way of cracking it is to actually try that exact phrase. And if one does somehow get it cracked, they've only proven who the real author is, they haven't found a way to take credit themselves.

If you don't have the requirement to "make sense" then someone cracking it only needs to find a password that fits, they don't need to find the correct password. And that doesn't prove they are the author, it just proves that they know a string that hashes to that hash. (They could be the author, they could have stolen the authors password, they could have just cracked it) And, probably more importantly, once the author reveals this string everyone has it and he's no longer special.

I guess what's bothering me about it now is would it be possible for a cracker to take a phrase like "Timmy is so and so" and then just add random characters to the end until it matches the original hash? If that's the case, then MD5 is probably a bad idea.


Top
 Profile  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sat Dec 29, 2007 10:59 pm 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
Timmy wrote:
indiana wrote:
The complexity of breaking the hash should be similar to the hash size (i.e. 2^128 for MD5) and not the initial string length: Many strings/passwords produce one and the same hash, and we cannot have a requirement that the string, known by the author only, "make sense" (like in your example).


Why can't you have the requirement? Why can't you say the hash must contain your nickname here as well as your real, and add in some random fluff for good measure? That was kind of the whole point of what I was saying. If it "makes sense", then the only way of cracking it is to actually try that exact phrase. And if one does somehow get it cracked, they've only proven who the real author is, they haven't found a way to take credit themselves.



I said it's tradeoff between protecting privacy and authorship. I.e. I didn't like the idea of encoding name because if it is easily crackable, this can compromise privacy of the authors, i.e. reveal who they are before they want that. Encoding forum name might be ok, but I wanted to have this thing independant of this forum, i.e. of course I plan to run this forum forever, but who knows.

That is all if MD5 is *easily* crackable, I'm not 100% sure on that thou.

But in any case, you are right, if we have requirement that the etxt cotains certain things, not real name but maybe email, so that not just any string will work.

On a second thought, and as I just mentioned e-mail, maybe this whole encoding thing was just a bad idea - and it might be enough if authors just specify nickname plus few e-mails.

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sun Dec 30, 2007 9:48 am 
Offline
PokerAI fellow
User avatar

Posts: 686
Location: Midwest, USA
Favourite Bot: N/A
indiana wrote:
I.e. I didn't like the idea of encoding name because if it is easily crackable, this can compromise privacy of the authors, i.e. reveal who they are before they want that. Encoding forum name might be ok, but I wanted to have this thing independant of this forum, i.e. of course I plan to run this forum forever, but who knows.

That is all if MD5 is *easily* crackable, I'm not 100% sure on that thou.
First of all, I don't understand the part about forum name.

Second of all, I'm not a cryptologist, but I'm pretty sure the proposed scheme would be virtually uncrackable.

Let's do some math here. Consider the NSA@Home MD5 cracking project. This guy threw together a bunch of FPGAs and claims to be able to search "the full 8-character keyspace (from a 64-character set) in about a day." That's about 1e17 passwords a year. These units are pretty cheap, and only use about 240w of electricity. Let's say you really want to crack my hash above, and you construct about a million of these units (at a cost of under a billion or so dollars). Now you are cracking about 1e23 hashes a year.

So to crack my above hash (95^30) / (64^8*365*1000000) / 2, takes an average of 1e36 years.

Unless I'm missing something very big, these will be uncrackable, even after thousands of years of technology advancement.

Chances are that before you'd be able to crack the actual password, you'd instead find several suitable collisions that made sense (but were not the correct password).


Top
 Profile  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sun Dec 30, 2007 10:45 am 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
Okay, if no other insights come along, we can stick to MD5 (or SHA-1) plus e-mail.

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Tue Jul 08, 2008 6:07 am 
Offline
Level1 member
User avatar

Posts: 48
Favourite Bot: Private
Timmy wrote:
indiana wrote:
So to crack my above hash (95^30) / (64^8*365*1000000) / 2, takes an average of 1e36 years.

Unless I'm missing something very big, these will be uncrackable, even after thousands of years of technology advancement.

Chances are that before you'd be able to crack the actual password, you'd instead find several suitable collisions that made sense (but were not the correct password).


Forgive me but I couldnt help notice all the drug references........you need help. :shock:


Top
 Profile E-mail  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sun Jul 20, 2008 5:09 pm 
Offline
PokerAI fellow
User avatar

Posts: 2342
Favourite Bot: My next one
Timmy wrote:
So to crack my above hash (95^30) / (64^8*365*1000000) / 2, takes an average of 1e36 years.

The thing is, MD5 isn't a bijective function so one would not really need to use brute force. Collision attacks (finding another string that MD5s to your hash) exists for MD5, requiring the collided passphrase to mean something in english is a whole other matter though, although definitely not that hard on a 128 bit hash.

I'd suggest a simple fix : hashing the same passphrase to both 128 bit MD5 and SHA-1 and providing both hashes. Should be enough security for anyone. You could make the requirement that the passphrase need to mean something in english and you're good to go.


Top
 Profile E-mail  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sun Jul 20, 2008 5:16 pm 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
Double hashing + requirement that it means something (or even include predefined things, e.g. family name / home town etc) would make it easier to crack? Or not really?

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sun Jul 20, 2008 5:30 pm 
Offline
PokerAI fellow
User avatar

Posts: 2342
Favourite Bot: My next one
Double hashing + requiring it means something/includes something makes it virtually impossible to crack.

The double hashing part solves the collision attacks problem as you would need a double collision (one on the MD5 space, one on the SHA-1 space) that would hash to the same string. An order of magnitude harder than just MD5 or just SHA-1.

Requiring it means something is mostly for us.

Edit : Apparently there's some more research that have been done in the field of dual hashing MD5/SHA-1 and some of my enthousiasm should be ponderated. I'm quoting this pdf :

Quote:
Attendees of the NIST conference were reminded to avoid the fallacy of dual hashing. Some people incorrectly believe that the way to overcome MD5 and SHA1 flaws is to compute both the MD5 hash and the SHA1 hash.They operate under the false assumption that combined strength of these two hashes is greater than either hash. It has been shown that this dual hash approach is at best only slightly stronger than SHA1 itself.

Basically they go on to say that MD5 is too weak to collision to truly make the dual hash work.

They go on and suggest :
Quote:
The one possible exception to immediate elimination of MD5 is MD5 hashed passwords (such as etc/shadow passwords) and MD5 HMAC. MD5 hashed passwords and MD5 HMAC should be phased out before the end of 2007, if not sooner.They should be replaced with SHA1 and/or SHA256 hash passwords and HMAC. See #4 and #5 for guidelines on how to choose SHA1 and/or SHA256.


Dual SHA-1/256 should be the way to go for (as perfect as could be) security.


Top
 Profile E-mail  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sun Jul 20, 2008 9:29 pm 
Offline
PokerAI fellow
User avatar

Posts: 686
Location: Midwest, USA
Favourite Bot: N/A
aiaiai wrote:
Collision attacks (finding another string that MD5s to your hash) exists for MD5, requiring the collided passphrase to mean something in english is a whole other matter though, although definitely not that hard on a 128 bit hash.
Could you provide references on this please?

As far as I know, rainbow tables are the biggest threat to password cracking. They are completely inapplicable to us, because even with rainbow tables the initial computing has to been done with brute force.

I also thought that current MD5 collision finding techniques usually worked on 64 byte boundaries, which would also make them inapplicable to us.


Top
 Profile  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Sun Jul 20, 2008 10:11 pm 
Offline
PokerAI fellow
User avatar

Posts: 2342
Favourite Bot: My next one
This pdf (found here) describes some of the latest collisions generating techniques that includes tunneling. Some exploits (pre-tunneling probably) can be found here.

As for the 64 bytes boundaries, isn't that a requirement of MD5 anyway ? Maybe I'm missing something.


Top
 Profile E-mail  
 
 Post subject: Re: Protocol Authors [confidentiality]
PostPosted: Mon Jul 21, 2008 3:25 am 
Offline
PokerAI fellow
User avatar

Posts: 686
Location: Midwest, USA
Favourite Bot: N/A
I think the MD5 algorithm calls for padding the message to a 64 byte multiple, minus 8 bytes to store the length. AFAIK, most collision techniques call for adding an entire block onto the end, which means we'd be immune if we had messages smaller then 56 bytes.

I haven't checked out your link yet (thanks BTW), so I may very well be totally wrong. :)


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 14 posts ] 


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to: