mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2012-07-31, 06:00   #1
Rodrigo
 
Rodrigo's Avatar
 
Jun 2010
Pennsylvania

32·103 Posts
Default GIMPS and cryptography

I just heard the following exchange on the Security Now! podcast, and I'm curious to get your reaction to it. Please pardon the extended quote -- the bulk of it is background so that you can understand what it's leading up to. The meat is in the last paragraph or two:

Quote:
Leo: Now, let me read you this paragraph because I'm sure this is where this story comes from. One senior intelligence official who until recently was involved with the program says that the "Bluffdale center will have another important and far more secret role." It's critical, he says, "for breaking codes. And code-breaking is crucial because much of the data that the center will handle - financial information, stock transactions, business deals, foreign military and diplomatic secrets, legal documents, confidential personal communications" - I guess not so confidential - "will be heavily encrypted. According to another top official also involved with the program" - and this is what I think is bogus - "the NSA made an enormous breakthrough several years ago in its ability to cryptanalyze, or break, unfathomably complex encryption systems employed not only by governments around the world, but also many average computers in the U.S."

Steve: Well, I don't know.
Leo: Do you think so? Think it's credible?
Steve: We have no way of knowing.
Leo: We can't know.
Steve: The one thing that I remember from the early reports was that they already have a huge amount of data encrypted using older, weaker codes - for example, 64-bit encryption - and now we have the technology to feasibly crack that. So they've got communications from foreign powers encrypted in - I mean, old communications encrypted in the then strongest codes of the time. So what we need to remember is, when storage is available, the encryption we use needs to be strong relative to our ability to decrypt into the future until a point where it no longer matters. And so my best guess is that they've got way, I mean, 64-bit encryption is, you know, we pooh-pooh it, but it was strong then. It's still strong now. We're just staying way ahead of what's feasible by going to 128 and 256, which is, you know, 128 is already really, I mean, that's, like, plenty strong.
Leo: Yeah. In fact, he says, "a lot of foreign government stuff we've never been able to break is 128 or less. Break all that and you'll find out a lot more of what you didn't know - stuff we've already stored...."
Steve: Exactly. So my guess is they're rubbing their hands together about bringing this processing power to bear on stuff that's a decade or two old. There can be really juicy tidbits that still matter in data that is only that old.
Leo: Sure. They've stored it. They just couldn't crack it until now.
Steve: Right, right. I think the stuff we're doing today is probably safe, given everything we know.
Leo: And the guy who wrote this article [James Bamford] is the author of "The Shadow Factory: The Ultra-Secret NSA from 9/11 to the Eavesdropping on America," if you want to read more. He has a little bit of an ax to grind. I mean, he wants everybody to get scared. I think, though, if there's anything, this would argue for using encryption more, not less, because they are watching.
Steve: Yeah. Exactly. Not assuming privacy. Unfortunately, we can no longer...
Leo: We don't have it.
Steve: Yeah.
Leo: Yeah, we don't have it. If you don't mind if spooks in Utah are reading your mail, no big deal. But if you do, I would say public key cryptography with long...
Steve: 2048-bit public key and a 256-bit symmetric key. That's going to be...
Leo: That's going to be fine for a while.
Steve: It really is.
Leo: I hope.
Steve: I guess...
Leo: Unless you and I are being paid by the federal government to say that.
Steve: The only breakthrough I could see, Leo, would be if they actually had a factoring breakthrough.
Leo: Right.
Steve: That would be...
Leo: It would be a mathematical - it would be a breakthrough in mathematical theory, I think.
Steve: Yeah, well, see, and the thing I like about our symmetric crypto is it is so simple. I mean, we did a beautiful podcast on AES where I explained in detail what that algorithm is. And it's just - it's like there's nowhere for bad guys to hide in that algorithm. It's just so clear and clean. And we all know what the vulnerability, such as it is, of current public key crypto is. It's the factoring problem, which the smartest people in the country who are in the private sector have looked at, private and education, and have not been able to crack. Now, maybe the NSA has cracked factoring. And if they've cracked factoring, then, yeah, well, public key crypto, at least the standard RSA style, there are other types, but that's then gone. But again, maybe.
Leo: Maybe. It's an interesting idea.
Steve: Yeah, I mean, that's the vulnerability. Factoring is the vulnerability because that's what we all depend on right now. I mean, that's the Achilles heel. Not the symmetric crypto, but the asymmetric crypto. And the reason those keys, the asymmetric crypto keys have to be 1024 or 2048 bits long is that the actual strength is not nearly as great as it is with symmetric crypto, where a 128-bit key is fine. We need to have, like, 10 times that many bits to get the equivalent strength. So that would be the Achilles heel. And maybe somebody's with his headphones on, listening to us say this right now, Leo, going, oh, shoot. Figured it out.
(emphasis added)

Somebody once claimed to me that GIMPS is part of a "black" program to help government spooks break private encryption. It was all I could do to stop myself from laughing in his face, but reading this gave me pause.

What do you think? Does the work done by GIMPS have applications in cryptography? Seems to me that we're far, far away from bit levels that the three-letter agencies would find useful, but I'm willing to listen to people who know more about this than I do. Assuming that you could talk about it -- and assuming that if you did speak, you'd be telling the truth...

Last fiddled with by Rodrigo on 2012-07-31 at 06:02 Reason: wording improvement
Rodrigo is offline   Reply With Quote
Old 2012-07-31, 06:08   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts
Default

It has applications in creating strong pseudo-random number generators -- e.g. the Mersenne twister. Large primes have no impact (AFAIK, please correct me if I'm wrong) on actually factoring numbers. (Random number generators have use in creating cryptographic keys, no use in breaking them.)

Also: http://www.mersenneforum.org/forumdisplay.php?f=97

Last fiddled with by Dubslow on 2012-07-31 at 06:11
Dubslow is offline   Reply With Quote
Old 2012-07-31, 06:42   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·33·5·11 Posts
Default

Quote:
Originally Posted by Rodrigo View Post
Somebody once claimed to me that GIMPS is part of a "black" program to help government spooks break private encryption.
Well, now you know not to trust what that person claims. Finding large primes does not help break encryption. Heck, factoring large numbers doesn't either -- it just lets governments know what the state of the art is (outside of secret agencies). Secret material should be protected with encryption far stronger than what can be factored by conventional means.
CRGreathouse is online now   Reply With Quote
Old 2012-07-31, 15:55   #4
Rodrigo
 
Rodrigo's Avatar
 
Jun 2010
Pennsylvania

32·103 Posts
Default

Quote:
Originally Posted by Dubslow View Post
It has applications in creating strong pseudo-random number generators -- e.g. the Mersenne twister. Large primes have no impact (AFAIK, please correct me if I'm wrong) on actually factoring numbers. (Random number generators have use in creating cryptographic keys, no use in breaking them.)

Also: http://www.mersenneforum.org/forumdisplay.php?f=97
Thank you Dubslow, that made for a fascinating morning of reading. Curious that there's been some level of crypto discussion around here lately.

Rodrigo
Rodrigo is offline   Reply With Quote
Old 2012-07-31, 16:03   #5
Rodrigo
 
Rodrigo's Avatar
 
Jun 2010
Pennsylvania

32·103 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Well, now you know not to trust what that person claims. Finding large primes does not help break encryption. Heck, factoring large numbers doesn't either -- it just lets governments know what the state of the art is (outside of secret agencies). Secret material should be protected with encryption far stronger than what can be factored by conventional means.
Yeah, when I heard it I did think it sounded pretty "out there". Thanks for the info and advice.

Rodrigo
Rodrigo is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
..New algorithm shakes up cryptography"? jwaltos Operation Kibibit 5 2016-01-30 09:33
CUDA and cryptography ET_ GPU Computing 10 2012-09-24 10:27
Metrosexual/Bi-Curious Cryptography article ewmayer Math 4 2012-09-09 06:43
128-bit OS'es and GIMPS? ixfd64 Software 22 2011-10-31 22:23
Distributed Internet Cryptography ewmayer Math 1 2006-08-21 20:53

All times are UTC. The time now is 02:20.

Sat Dec 5 02:20:51 UTC 2020 up 1 day, 22:32, 0 users, load averages: 1.52, 1.51, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.