View previous topic :: View next topic 
Author 
Message 
MoiraA Guest

Posted: Wed Jun 25, 2003 1:10 am Post subject: How secure is PGP? 


Hi
I'm wondering if anyone can point me in the direction of some information which would solve an argument!
I'm trying to persuade this guy that PGP will allow him to send completely confidential email, but he's convinced the 7.4 meg download from pgpi does not have enough "room" within the program to physically contain the massive primes needed to prevent factoring being achieved with a brute force attack.
In other words, he's saying that he doubts the hard disk space occupied by the program, allows a large enough amount of prime numbers to be stored, as it "couldn't cope" with the number of digits in a prime say, 100 numbers long. He's also saying that there can only be so many primes, and fast computers nowadays could try them all within a reasonable time frame. I'm sure these theories are flawed ..... but I don't know enough about computers to argue.
I've recently read a book on the history of public key encryption, which Eddie also borrowed, but as it was written by Simon Singh a couple of years ago he feels that possibly there are now super computers capable of carrying out calculations which even in 2001 would have taken longer than the life of the universe to complete. However, to my knowledge noone has yet discovered an algorithm for factoring  unless anyone knows differently?
Can I just say, this guy is not operating illegally in murky corners of the net .... it's just become a theoretical argument!
Moira


Back to top 


alt.don SF Boss
Joined: 04 Mar 2003 Posts: 16777079

Posted: Wed Jun 25, 2003 1:25 am Post subject: 


Hello Moira, pgp is itself very safe and secure. As it stands an R6 which is equal to 64bit encryption is vulnerable. An R7 which is 128 bit is still robust and secure. Though it is prone to cracking given enough cpu cycles and a large enough sample from the one source. That is unlikely to happen though Moira as the average person does not send that many emails which could be intercepted. Either way you are talking about the government now or a truly talented hacker of which there are very little. This is the reason the US government has imposed export sanctions on cryptography Moira. Once you start getting into 256 and 512 bit encryption about the only way to crack them is to get access to the keys themselves. I hope this has clarified the question a little.


Back to top 


flw Forum Fanatic
Joined: 27 May 2002 Posts: 16777215 Location: U.S.A.

Posted: Wed Jun 25, 2003 2:28 am Post subject: 


Hopefully Justin will post on this topic since its his strength. As a reminder when ever I see this type of post that puts all the focus on the key length when there are many other factors involved in a secure encrytped data transaction whether email or ecommerce.
Good Security involves multiple layers of different methods and technologies along with good practices.


Back to top 


squidly Trusted SF Member
Joined: 07 Oct 2002 Posts: 16777215 Location: Umm.. I dont know.. somewhere

Posted: Wed Jun 25, 2003 3:00 am Post subject: 


Most programs that use encryption generate the primes as they are needed, it’s not that difficult and math is what puters are best at. A for pgp it uses several different algorithms to keep the content safe from crackers. And if you look at the size of on unsigned int (8 bits) you are looking at a maximum of value of somewhere around 65000. Now if you ad in there a long double (16 bits) I think it can handle the large primes (well over 100 digits). Also with the public key system all that he has really worry about is the security of his private key.
What someone does is they encrypt the message with his public key and he uses his private key to decrypt them.
Yes, there is a limit to the largest prime a computer can store, that is there the algorithms come in. Most of the public algorithms have been around for years and have been looked over by the most brilliant minds in the field. Many of the algorithms (the ones you have never heard of) have been debunked, debugged, and cracked. That is why they are not in general usage. Most of the cryptographic attacks against a key based system almost require entry in to the keyescrow system to get to, that or man in the middle attacks when he is putting his key into escrow and as soon as the man in the middle gets sick of watching emails the knowledge that they PUBLIC key was compromised will be known.
Now on to the mathematics. With a 64bit key, it would take aprox 2^10 years to brute force the private key. A distributed net program that was designed to crack the DES (single DES not 3DES) took computer decades to crack, and that was something along the lines of a 32bit key. If he chooses the AES key or a BLOFISH key then we are looking at 2^10^10 years to crack given current tech. That is also using a supercomputer; even the legendary Cray computers are not capable of cracking AES encryption quickly
HTH
Last edited by squidly on Wed Jun 25, 2003 4:18 am; edited 1 time in total 

Back to top 


flw Forum Fanatic
Joined: 27 May 2002 Posts: 16777215 Location: U.S.A.

Posted: Wed Jun 25, 2003 3:15 am Post subject: 


Quote: 
even the legendary cray comptuers are not capable of cracking AES encryption quickly 
I understand your point but I have never seen (only heard on forums) about a documented case of 3DES or AES being cracked in a real world environment. If you happen to know of a site that documents this I'd love to see it.
Excellant point on securing the primary key because it is the weakest link in any modern encryption methodology. i.e. doesn't matter if it is 3DES or AES if I have your keys No need to break anything.


Back to top 


squidly Trusted SF Member
Joined: 07 Oct 2002 Posts: 16777215 Location: Umm.. I dont know.. somewhere

Posted: Wed Jun 25, 2003 3:49 am Post subject: 


fastlanwan wrote: 
Quote: 
even the legendary cray comptuers are not capable of cracking AES encryption quickly 
I understand your point but I have never seen (only heard on forums) about a documented case of 3DES or AES being cracked in a real world environment. If you happen to know of a site that documents this I'd love to see it.
Excellant point on securing the primary key because it is the weakest link in any modern encryption methodology. i.e. doesn't matter if it is 3DES or AES if I have your keys No need to break anything. 
The NSA has been attempting to crack sence they were made. But When I say quickly I guess I should have said "quickly if at all". Thanks for the point.


Back to top 


JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlândia, MG, Brazil

Posted: Wed Jun 25, 2003 4:34 am Post subject: How secure is PGP? ...well, now... 


fastlanwan wrote: 
Hopefully Justin will post on this topic since its his strength. As a reminder when ever I see this type of post that puts all the focus on the key length when there are many other factors involved in a secure encrytped data transaction whether email or ecommerce.
Good Security involves multiple layers of different methods and technologies along with good practices. 
What fastlanwan has said is the most important facet, in regards to using cryptography properly. Please keep this mind. PGP is only as secure as the user's knowledge of such. Cryptography can easily be misused. An overall sufficient security margin lies in layers, not in cryptography, or even key lengths, alone. Consider the onion analogy.
Key length is only a figment of a secure reality. I stand by this 100%.
As for PGP, it is a secure application, to sum things up. It contains the most robust arsenal of algorithms available, including AES, 3DES, and Blowfish. My personal recommendation is GnuPG, rather than PGP, as it is open source, free, and doesn't contain the patented IDEA algorithm. IDEA, although a strong algorithm, is now much slower and weaker than algorithms, such as Blowfish, which is much faster and secure. It seems illogical to use IDEA, because of analysis such as this. You can obtain a copy of GnuPG at: http://www.gnupg.org
If you need a nice, clean Windows shell for this otherwise command line interface, I suggest GPGshell, of which you can download from: http://www.jumaros.de/rsoft/gpgshell.html
For various other PGP/GnuPGrelated plugins, check out the The International PGP Home Page
The size of the program has no inherent relativity to the size of primes it can generate. PGP is not an algorithm. It simply provides a housing for a collection of algorithms, including asymmetric algorithms, which handle prime numbers. To think that PGP couldn't provide you with sufficient strength, via prime numbers, is rather absurd, considering you actually research the program's internal semantics. No disrespect intended here to your friend, by any means. :] It's always best to research before you make an uneducated assumption. That applies to various other things, aside from cryptography.
Currently, the most efficient algorithm for factoring primes is known as the NFS, or Number Field Sieve. NFS has overshadowed the use of its elder, the Quadratic Sieve, and is the most commonly utilized factoring algorithm, to date. This algorithm consists of two primary steps. The first step lies in the fact that certain mathematical properties must be. This is achieved by searching through applicable equations that satisfy such. This step can easily be deployed in parallel and is often done in this manner, over a myriad of machines. When I say myriad, I'm talking in the thousands, even. The second step is rather husky matrix multiplication, with the intent of producing the factors the prime in question. If you are interested in learning NFS, in mathematical detail, I suggest you check out: http://www.std.org/~msm/common/nfspaper.pdf
The most current research on factoring methodology, of cryptographic significance, stems from a mathematician by the name of Dan Bernstein.
His advancements claim to put at risk keys as large as 2048 bits. The aim of his research, essentially, was to increase the speed of the primary NFS steps. Aside from adding minor speed increase, it falls short of providing a proof for the practical factorization of large primes, in this modern time of computing and mathematical technology. However, in short, this research isn't a factoring breakthrough, nor does it pose an imminent threat to 2048bit keys. It will be quite some time before this research will become applicable. If you care to read more on his methodology, you can read the technical paper in PS or PDF format.
Currently, the largets prime factored would be that of 512 bits, which took place in 1999. The factorization of 572bit keys should be possible, in the near future. Even 768bit keys are generally safe, although, a minimum of 1024 bits is recommended. In my honest opinion, based on speed/security tradeoffs, I recommend the use of a 2048bit key, as a minimum. Also, based on the decades of analysis backing the RSA algorithm, I certainly recommend this asymmetric algorithm as your choice.
So, he is incorrect. With current analysis and research, PGP provides sufficient strength through the use of primes. A factoring breakthrough is not impossible though, so keeping key sizes at a hefty, yet conservative, size, is a good tactic to incorporate into your use of cryptography. Anything is possible in the near future, although, for the time being, you can be safe and secure, essentially.
As for symmetric algorithms, such as AES, 3DES, Blowfish, Twofish, Serpent, et cetera, the generally recommended minimum key length is 90 bits, as 90 bits is a somewhat reasonable choice, in terms of speed and sufficient security. Although, 128 bits is the most logical choice for a minimum key size, for two main reasons. First of all, it increases the complexity from 2^90 to 2^128, a significant increase of 30 bits. Second of all, a 128bit key is approximately as fast as a 64bit key.
The largest key length to be brute forced, thus far, via a distributed network, is 64 bits, which took several years. So, in all theory, 90 bit keys will prove sufficient for time to come. 128bit key usage is still the best practice, from a cryptographic perspective.
Therefore, I recommend the following selections for key length, in both asymmetric (RSA) and symmetric (AES, 3DES, et cetera) algorithms:
Asymmetric: 2048bit (Preferably RSA)
Symmetric: 128bit (Preferably 3DES, AES, Twofish, or Blowfish)
Those numbers will be important to you.
So, to conclude, PGP is secure. How secure? If deployed correctly  sufficiently secure.
If you have any other questions regarding PGP, factoring, or algorithm properties, in general, feel free to let me know. I'll be glad to assist.
Best regards, Moira.
Justin
Last edited by JustinT on Mon Jun 30, 2003 1:09 am; edited 2 times in total 

Back to top 


linux_lad Trusted SF Member
Joined: 11 Apr 2003 Posts: 16777215 Location: California

Posted: Wed Jun 25, 2003 4:42 am Post subject: Re: How secure is PGP? 


MoiraA wrote: 
Hi
I'm wondering if anyone can point me in the direction of some information which would solve an argument!
I'm trying to persuade this guy that PGP will allow him to send completely confidential email, but he's convinced the 7.4 meg download from pgpi does not have enough "room" within the program to physically contain the massive primes needed to prevent factoring being achieved with a brute force attack.
In other words, he's saying that he doubts the hard disk space occupied by the program, allows a large enough amount of prime numbers to be stored, as it "couldn't cope" with the number of digits in a prime say, 100 numbers long. He's also saying that there can only be so many primes, and fast computers nowadays could try them all within a reasonable time frame. I'm sure these theories are flawed ..... but I don't know enough about computers to argue.
I've recently read a book on the history of public key encryption, which Eddie also borrowed, but as it was written by Simon Singh a couple of years ago he feels that possibly there are now super computers capable of carrying out calculations which even in 2001 would have taken longer than the life of the universe to complete. However, to my knowledge noone has yet discovered an algorithm for factoring  unless anyone knows differently?
Can I just say, this guy is not operating illegally in murky corners of the net .... it's just become a theoretical argument!
Moira 
PGP isn't really any more or less secure than other encryption tools that use the same algorithms, it's just one of the easiest to use. As to the prime number question, the primes are not stored on the program, they are generated and stored on the client. These primes form the keys and each is only a few thousand bytes (but far beyond the capablity of all the computers in the world working in unison to factor the product of). In order to solve a large problem, you would have to factor it after you multiplied the keys. When there was no commercial release of PGP, the source code was freely available. You can still get the source code on request and you can still download v2.62 with the source code and compile yourself.
As I always say, rubberhose or monblanc attacks are much faster, and produce much more reliable results. Unless someone discovers a way to factor big numbers (highly unlikely), your friend is pretty safe.


Back to top 


aberent Trusted SF Member
Joined: 08 May 2003 Posts: 2 Location: Toronto

Posted: Wed Jun 25, 2003 4:46 am Post subject: RE:How secure is PGP? 


Justin is correct as usual.
My opinion on the subject is:
PGP is very secure; it’s been around for years and is well tested. On the other hand PGP is very complicated to use for an average user. This is perhaps its only weakness.


Back to top 


JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlândia, MG, Brazil

Posted: Wed Jun 25, 2003 4:49 am Post subject: NSA hype. 


squidly wrote: 
The NSA has been attempting to crack sence they were made. But When I say quickly I guess I should have said "quickly if at all". Thanks for the point. 
From my perspective and experience with the two algorithms, 3DES is the most secure and trustworthy algorithm available. Though this is my opinion, the proof is evident, of which leads other cryptographers to agree as well. No other algorithm has undergone such an extensive level of cryptanalysis and retained its overall security. No other algorithm compares in confidence. Only current research in MITM attacks has reduced the complexity of 3DES to between 2^108  2^112, which is still a sufficient key length, nonetheless.
As for AES, or Rijndael, it has yet to achieve this level of trust. Although an very secure and efficienty algorithm, it still lacks the analysis that we cryptographers look for, when judging the use of an algorithm. A fairly new attack, known as XSL, has been proposed, against AES, but only in theory. It's very likely that this will not be practical, although, it does raise interesting questions. The logic is based on the use of multivariate quadratic equations. You can read up on this at: http://www.minrank.org/aes/
All in all, there is too much hype about the NSA. I can't provide any proofs as to what they are and are not doing, however, I can be smug enough to say that 3DES and AES are both still secure, in terms of sufficiency, and will likely be for quite some time. Mathematical research and computing technology will likely prevail, eventually, however, the manner and timespan in which they do so will remain spontaneous and questionable.
Last edited by JustinT on Sat Sep 20, 2003 11:37 pm; edited 1 time in total 

Back to top 


JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlândia, MG, Brazil

Posted: Wed Jun 25, 2003 4:53 am Post subject: Re: RE:How secure is PGP? 


aberent wrote: 
My opinion on the subject is:
PGP is very secure; it’s been around for years and is well tested. On the other hand PGP is very complicated to use for an average user. This is perhaps its only weakness. 
Indeed. Because of the vast amount of parameters within PGP, a sufficient understanding of cryptography is truly necessary to understand how these various options work and for what reasons you should use them. This can be very unfriendly to the average user in search of a simple encryption solution, without all the hassle.
Thanks for pointing this out, aberent.


Back to top 


MoiraA Guest

Posted: Wed Jun 25, 2003 7:38 pm Post subject: 


Thank you everybody, what fantastic answers! It's quite overwhelming  I'm printing out this thread to take round to church housegroup tonight (where I know Eddie from). It's EXACTLY what I've been looking for  and there are lots of interesting links to follow up as well.
I don't think it's a case of Eddie making assumptions without doing research .... his theories were the result of much thought and what research he was able to do. He's also got hold of the idea that since noone knew Enigma messages had been decyphered until 29 years after the war ended, when Winterbotham's book The Ultra Secret was published, if PGP messages were being cracked by government, we wouldn't necessarily know about it now.
I take the point about key length being immaterial if someone gets hold of your key ..... or if someone installs a keystroke logging program on your computer, for instance. I have a copy of pgp and note that the digital signature at least takes care of a third party masquerading as Alice or Bob.
I find the program reasonably easy to use ..... in fact once it's set up, it's incredibly easy. I don't send a lot of PGP mail, but I like knowing I have the means to send completely confidential email if I need to, although you still have to trust the person at the other end not to be careless. A lot of the time I'd like to send encrypted mail, but the recipient is someone who doesn't know anything about public key cryptography and therefore wouldn't use PGP.
Justin, a special thank you for taking so much trouble over this. It's BRILLIANT to have all this information!
Moira


Back to top 


JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlândia, MG, Brazil

Posted: Wed Jun 25, 2003 8:17 pm Post subject: Anytime... 


MoiraA wrote: 
I don't think it's a case of Eddie making assumptions without doing research .... his theories were the result of much thought and what research he was able to do. He's also got hold of the idea that since noone knew Enigma messages had been decyphered until 29 years after the war ended, when Winterbotham's book The Ultra Secret was published, if PGP messages were being cracked by government, we wouldn't necessarily know about it now.

Oh, of course not. I'm sure he researched it quite a bit, to form such strong opinions. I simply mean, based on the paranoia of many, that it's not a matter of PGP being secure, but rather, considering the algorithms in question. In order to analyze the security, you must break it down into individual segments. The Enigma was a rather secure device, at the time of its initiation, based on current technology. However, technology advanced much faster than thought. It did so, much faster than cryptographic technology, thus bringing devastation to the overconfidence placed in the Enigma. It was a device of limitation and much symmetry, of which couldn't remain resilient to rising cryptographic analysis. The Enigma was produced with little cryptographic knowledge backing it. Cryptography, as a militaryinduced tool, was a rather new and growing idea, so there was little knowledge to be held, especially where mathematics, in correlation to cryptography, was concerned. Prior to the 1970's, a great majority of cryptography was overrated, and often broken within a short period of time from its induction, because of the lack of analysis and knowledge thereof.
PGP is a much different case. It's not an algorithm, in itself, yet an arsenal of timetested algorithms, ranging in speed, security, and efficiency. You have two different models  asymmetric and symmetric, respectively.
You are dealing with anything from prime numbers to intense matrix multiplication. The security lies in the mathematics. The NSA, known to be the largest employer of mathematicians in the world, views cryptography in this way. Only when a mathematical breakthrough occurs that poses an imminent threat to asymmetric or symmetric cryptography, should we begin to worry. As of now, all we have to work with is current analysis, as brute forcing isn't extremely beneficial, with current computing technology. This analysis hasn't proved fatal to any major algorithm, yet. The point is, not only do NSA mathematicians and personnel have the mathematical knowledge of modern algorithms, but so do cryptographers outside of this agency, such as Bruce Schneier, Vincent Rijmen, and Matt Blaze. Their analysis, as well as others', will provide us with enough confidence to continue mass use of applications, such as PGP, from a mathematical perspective. Anything is possible however, but that is just part of science and the rules of uncertainty. Breakthroughs do occur. However, as I've said, you can rest assured that using PGP, and the algorithms that subside, is safe.
Quote: 
I take the point about key length being immaterial if someone gets hold of your key ..... or if someone installs a keystroke logging program on your computer, for instance. I have a copy of pgp and note that the digital signature at least takes care of a third party masquerading as Alice or Bob.

Exactly. Key management plays a vital role in the overall security of using cryptography. In fact, it is the most fragile area to deal with, theoretically.
Key length is truly important, don't get me wrong, but it's only effective, provided you take into account all of the other measures of security necessary. You provided a great example, with the keystroke logger. This goes to show that cryptography doesn't always rely on key lengths, or anything related to cryptography at all. It's how cryptography is placed, in unison, with security as a whole.
Quote: 
Justin, a special thank you for taking so much trouble over this. It's BRILLIANT to have all this information!

You are quite welcome, Moira. I do go posthappy many times, as you can probably tell, but I am glad to see that I can share what I've learned in hopes that it will benefit others, as yourself. No problem at all! Glad to be of service, anytime.
Best regards,
Justin


Back to top 


MoiraA Guest

Posted: Wed Jun 25, 2003 9:16 pm Post subject: 


Thanks again Justin, that has arrived just in time to print out and take round as well!
It took me a while to find this thread  LOL! I thought I posted it in the Newbie corner, didn't realise I had ventured onto such a technical forum as this!
Moira


Back to top 


JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlândia, MG, Brazil

Posted: Wed Jun 25, 2003 9:20 pm Post subject: Cheers... 


MoiraA wrote: 
Thanks again Justin, that has arrived just in time to print out and take round as well!
It took me a while to find this thread  LOL! I thought I posted it in the Newbie corner, didn't realise I had ventured onto such a technical forum as this!
Moira 
Ah, no problem at all.
Hehe, yes, discussions can be very technical here, although, I do my best to clarify my answers, where needed. If there is anything you don't quite understand that I've said, feel free to let me know and I'll break it down to be much more understandable. :]
Cheers,
Justin


Back to top 


ShaolinTiger Forum Fanatic
Joined: 18 Apr 2002 Posts: 16777215 Location: Kuala Lumpur, Malaysia

Posted: Wed Jun 25, 2003 11:29 pm Post subject: 


You did post it in the newbie section Moira but it's not exactly a newbie quesion and you phrased it in a manner that implied some knowledge.
It deserves to be in here and in here you will get suitable answers


Back to top 


