"TWINKLE is just proof that there *ARE* fast ways to factor composites into their primes."
TWINKLE is no such proof. TWINKLE was estimated to be able to crack 512-bit, maybe 768-bit keys but even Adi said it wouldn't scale to 1,204-bit keys....I can break 5 bit RSA keys in my head, that doesn't make RSA insecure, it just means that parameters need careful selection.
"The McEliese cryptosystem seems to be secure and it is based on a NP-complete problem"
I assume you mean McEliece? Your confusing NP-completeness with strength - look at the number of PK ciphers built upon NP-Complete problems (e.g. the knapsack ciphers etc) and you'll soon see that NP-Complete doesn't secure automatically imply secure
People need to, still, chose their algorithms and parameters carefully. Use DH or Elgamal with 2,048-bit keys for strategic data.
Actually, I beg to differ. Security Engineering by Dr Ross Anderson is IMHO a far more rigorous treatment of this subject. Details are here. It's even just as easy to read as Schneiers book...Of course, Bruce is a far better at self marketting.
I am looking forward to getting Schneiers new Practical Cryptography book though (here).
John Young has posted quite a lot of information about his log policy before....It's pretty widely known that he deletes them very regularly to prevent this kind of thing.
People have asked why logs aren't just sent to/dev/null - that's because John does scan the logs for "interesting" visitors - see e.g. his previous stories about catching various US departments and agencies (FBI, Whitehouse) looking at his site.
The site is currently down I wonder if it has been slashdotted, or.......
The only way to be sure a prime is real is attempt to factor it.
That's just not true (and hasn't been for 5 years or so!). Read the Maurer paper or HAC (you can even read the relevant chapter here).
Maurer's algorithm prove's in a mathematical sense if a number is prime or not. It's not probablistic, it's definitive.
I've give you the relevant links to bring you up to date and don't believe that posting further on this topic will provide usefull until you read the links.
Read Handbook of Applied Cryptography (pretty much the definitive source for number theory as used in cryptography) - Algorithm 4.6.2 is entitled "Maurer's algorithm for generating provable prime's" and disagrees with your point "The only way to generate a real prime is factor it".
Oh, and how do you "factor a real prime"?;))))
Yes, Knuth vol 2 is a good reference - but it is lacking in this respect. It doesn't even mention Maurer's algorithm.
I would suggest reading up on Maurer's paper and then writing to Mr Knuth.:).
"number of primes is in the realm of 3.7e151" - yep, that's for 512-bit primes.
I think we know how well a distributed attack can work against RSA and DH (these things have been tried in the past). We can break up to (about) 768-bit keys but would struggle to get near 1,024 bits. 2,048-bits is a complete non started.
(And yes, this is using the Public key to "narrow the search". Your 150 odd systems will still be pissing in the wind, unfortunately....).
Which means that every x-box has a copy of the same MS public key to verify the codes authenticity, no? The private key ISN'T stored in the device, but rather in some vault in MS and is only dragged out to sign programs.
I agree entirely - M-R is good enough for virtually all purposes....I just like picking up on crypto newbies who claim "there is no known way to generate a 2048 bit true prime that can't be factored in the same about of time it takes to generate it.";)
You aren't "proving" it. Miller-Rabin is a probabilistic algorithm. It doesn't guarantee anything (unless it indicates that the number is composite - non prime).
I wasn't referring to Miller-Rabin (which indeed doesn't produce provable primes), but rather Maurer's algorithm (See HAC Algorithm 4.62 on Pg 153). Section 4.3 in HAC specifically discusses only true primality tests.
Timings were thanks to a recent thread on sci.crypt entitled "Provable Generation of Primes with Maurer".
The RSA signature used to sign/for comparison purposes used with Xbox execuatables is 2048 bits long.
Common secure internet traffic, carrying thousands of credit card numbers as we speak, uses 128 bit keys (almost always).
You are confusing symmetric and asymmetric ciphers. SSL (or "secure internet traffic", if you must) uses 128-bit symmetric keys coupled with larger (1,024-bits or greater usually) asymmetric keys.
In case some of your forget: it gets exponetionally harder as the length of the key increases.
"In case some of you forget" should be rephrased to "I'm going to state something authoritative now and hope I'm right". The 2,048-bit key you are alluding to is a asymmetric key (RSA). The fastest algorithms for factoring and computing discrete logs are sub-exponential!
They certainly have, check out the names here for example. Gollmann, Leyland, Needham and Petitcolas are all pretty well known in crypto circles. Which asks the question: how can MS employ such bright people and still churn out insecure crap?
Although 2048 doesn't sound much more than 576, these are of course powers of two we are talking about. I fear the people attacking it aren't quite imagining what these kind of numbers mean.
Don't forget that there are sub-exponential algorithms for solving RSA/DH - so adding a bit of key doesn't double the time to solve. 2048 is still currently impossible though!
"RSA requires that you have two true primes to generate they key but the problem is there is no known way to generate a 2048 bit true prime that can't be factored in the same about of time it takes to generate it."
Wrong. Entirely wrong in fact. You should read the Handbook of Applied Cryptography (kindly made available online here). See e.g. section 4.3. Proving a 2048-bit number is prime (I think you mean 2x 1,024-bit numbers, but....) should take a minute or two - not excessive for a one-off operation!
"forget it however there are several publications that indicate that the number of solid pseudo-primes that are 512 bits long is about 2^40 so its key strength is about the same as 40 bits."
Erm, where do you get this stuff from? What's a "solid pseudo-prime"?;) Also, the number of 512-bit primes is expected to be around 3.7x10^151 (see e.g. here).
"Since we are talking about a 4x as many bits, a good guess of the strenght of a 2048 bit pseudo-prime would be about as hard as guessing a 160 bit DES like key".
Hardly - Certicom reckon that a 128-bit symmetric key is equiv. to a 3072-bit RSA key. Don't forget that, with symmetric keys, the strength usually doubles with each added bit of key material - the same isn't true for RSA or DH keys as there is now a sub-exponential algorithm for solving these problems....
The rest of your post doesn't get much better, but I'm off to eat sunday lunch now....Seriously, read HAC - it's good for you.
Sounds fine to me, at least for personal email accounts. If it's PGP signed, at least you can then verify the sender & get back to him/her.
How? Just because a message is signed doesn't mean that you know who the sender is. The mapping of e-mail addresses to PGP keys isn't one-to-one.
it's PGP signed spam, you can block it
And what prevents spammers creating "one time signature keys" that allow them to sign a message once and then dispose of the key? How precisely will you block a spammer from doing this?
...effectively or get back to the spammer's ISP
How does signing a message in any way help you "prove" the origin of the message (e.g. does it offer anything more than the usual SMTP headers etc?).
Without imposing a lot more structure upon the use of PGP and e-mail (e.g. only accepting mail that's been signed with someone already in your keyring or trusted) then just saying "I'll accept signed messages" adds precisely zero.
I assume that your e-mail client will throw away any mails that aren't signed by a trusted key then? This is even worse than whitelists...Not only do you have to implicitly allow e-mail address you have to go through the pain of making users create and distribute key pairs (and possibly worry about the web of trust).
Just saying that "getting a signed mail" is enough is a naive approach: since one mail only needs to be signed once and can be sent to millions of recipients in one go this hardly raises the barrier for spammers. Even if spammers need to create a new keypair every time they want to send a new message this still won't slow them down - you can create "canned" keys in milliseconds.
There may well be a (non-hashcash like) cryptographic solution to the problem of spam, but just signing isn't a sociably acceptable solution IMHO.
The definitive text on cryptography, The Handbook of Applied Cryptography, defines the OTP as a type of encryption...I know this is Slashdot but I don't think your arbitrary definitions help here.
Sending a CD worth of random data via a secure channel in advance and then sending an encrypted message with the knowledge that it will be unbreakable is sometimes worth prior thought. Sure, it may not be usefull for the masses who require this kind of security or don't know their going to communicate in the future but to claim that this cipher "isn't encryption" is bull.
No - Mix + Mash ciphers aren't automagically immune, see quote from Schneier:
"While quantum computation can make problems such as factoring and discrete logarithms (which public-key cryptography are based on) easy, they can only reduce the complexity of any arbitrary computation by a square root. So, for example, if a 128-bit key length was long enough pre quantum computation, then a 256-bit key will be long enough post quantum computation."
-- B.Schneier, 10th Oct 1998 posting to soc.history.what-if USENET group
E.g. 3DES will be pretty much toast, as will AES128.
RSA is based upon the Integer Factorization Problem (IFP) (*).
Elgamal / DH are based upon the Discrete Log Problem (*)
Eliptic Curves Cryptography is based upon, erm, Eliptic Curves.
(*) Note: there are no proofs that RSA or DH/Elgamal are actually as hard as the underlying IFP or DLP - e.g. they could be broken even if factoring is "hard".
To quote the author: "I get a lot of email containing the word "Lisp", and (so far) no spam that does".
He obviously doesn't getting the "Lesbians with a Lisp" pr0n......
Re:PGPFreeware? So what?
on
Can GnuPG Deliver?
·
· Score: 3, Informative
About once or twice a year a bug of security significance is uncovered in PGP (e.g. the ADK bug, the RNG on UNIX bug, the keystorage bug etc) and this would render the latest 7.02 next to useless.
Why can't people amend the source code and recompiler themselves? They don't have access to the source code.
Also remember that PGP is now very (over-) complicated and includes various drivers and kernel hooks. Every new version of an MS operating system (Win2k, WinME, WinXP) breaks compatibility.
The best current hope is the CKT builds of PGP, that are based on the 6.5.8 code. These have all known bugs fixed and still work on all Win32 operating systems. This is also the only version that is actively maintained!
Non-geeks had trouble with NAI PGP
on
Can GnuPG Deliver?
·
· Score: 3, Insightful
Often people say that "GPG needs a frontend before non-geeks can use it". That point is probably true, but even though NAI PGP has had a "mature" GUI based front end for several revisions, normal users are still incapable of getting their head around creating keys, the difference between public and private keys, the difference between signing and encryption etc etc.
A usability study was undertaken by researchers at Carnegie Mellon in which they found that virtually 0 non geeks managed to use PGP successfully anyway.
Sure, OpenPGP based programs need to achieve better reach, but simply copying the NAI PGP design won't achieve this goal....
"I am 100% sure it is NP and 95% sure it is NP-Complete"
Factoring is known to be NP but there is no proof of NP-Complete - see e.g. Bob Silvermans post - he suggests that the conses is that factoring != NP-Complete.
That's true. I would be the first to concede that 3des can be broken with 3 chosen plaintexts, 2^56 blocks of memory, 2^111 encryptions and 2^111 operations (e.g. table lookups).
At the moment however, that attack is clearly infeasible, so I continue to recommend 3DES as "the best we've got" (at least until AES has gained further confidence in the crypto community).
Slashdot Mirror
...Well, that's what the article says. I guess they haven't heard about pipelining, multiple execution units, SIMD etc etc.
"TWINKLE is just proof that there *ARE* fast ways to factor composites into their primes."
TWINKLE is no such proof. TWINKLE was estimated to be able to crack 512-bit, maybe 768-bit keys but even Adi said it wouldn't scale to 1,204-bit keys....I can break 5 bit RSA keys in my head, that doesn't make RSA insecure, it just means that parameters need careful selection.
"The McEliese cryptosystem seems to be secure and it is based on a NP-complete problem"
I assume you mean McEliece? Your confusing NP-completeness with strength - look at the number of PK ciphers built upon NP-Complete problems (e.g. the knapsack ciphers etc) and you'll soon see that NP-Complete doesn't secure automatically imply secure
People need to, still, chose their algorithms and parameters carefully. Use DH or Elgamal with 2,048-bit keys for strategic data.
Unless you use a key only once, (possible, but definitly an odd way to do it)
Not at all - have a search for ephemeral keys. Not applicable to RSA (usually too slow), but can be used with Elgamal very easily/quickly.
It's the best book on the topic available.
Actually, I beg to differ. Security Engineering by Dr Ross Anderson is IMHO a far more rigorous treatment of this subject. Details are here. It's even just as easy to read as Schneiers book...Of course, Bruce is a far better at self marketting.
I am looking forward to getting Schneiers new Practical Cryptography book though (here).
John Young has posted quite a lot of information about his log policy before....It's pretty widely known that he deletes them very regularly to prevent this kind of thing.
People have asked why logs aren't just sent to /dev/null - that's because John does scan the logs for "interesting" visitors - see e.g. his previous stories about catching various US departments and agencies (FBI, Whitehouse) looking at his site.
The site is currently down I wonder if it has been slashdotted, or.......
The only way to be sure a prime is real is attempt to factor it.
That's just not true (and hasn't been for 5 years or so!). Read the Maurer paper or HAC (you can even read the relevant chapter here).
Maurer's algorithm prove's in a mathematical sense if a number is prime or not. It's not probablistic, it's definitive.
I've give you the relevant links to bring you up to date and don't believe that posting further on this topic will provide usefull until you read the links.
Read Handbook of Applied Cryptography (pretty much the definitive source for number theory as used in cryptography) - Algorithm 4.6.2 is entitled "Maurer's algorithm for generating provable prime's" and disagrees with your point "The only way to generate a real prime is factor it".
Oh, and how do you "factor a real prime"? ;))))
Yes, Knuth vol 2 is a good reference - but it is lacking in this respect. It doesn't even mention Maurer's algorithm.
I would suggest reading up on Maurer's paper and then writing to Mr Knuth. :).
"number of primes is in the realm of 3.7e151" - yep, that's for 512-bit primes.
I think we know how well a distributed attack can work against RSA and DH (these things have been tried in the past). We can break up to (about) 768-bit keys but would struggle to get near 1,024 bits. 2,048-bits is a complete non started.
(And yes, this is using the Public key to "narrow the search". Your 150 odd systems will still be pissing in the wind, unfortunately....).
Which means that every x-box has a copy of the same MS public key to verify the codes authenticity, no? The private key ISN'T stored in the device, but rather in some vault in MS and is only dragged out to sign programs.
I agree entirely - M-R is good enough for virtually all purposes....I just like picking up on crypto newbies who claim "there is no known way to generate a 2048 bit true prime that can't be factored in the same about of time it takes to generate it." ;)
You aren't "proving" it. Miller-Rabin is a probabilistic algorithm. It doesn't guarantee anything (unless it indicates that the number is composite - non prime).
I wasn't referring to Miller-Rabin (which indeed doesn't produce provable primes), but rather Maurer's algorithm (See HAC Algorithm 4.62 on Pg 153). Section 4.3 in HAC specifically discusses only true primality tests.
Timings were thanks to a recent thread on sci.crypt entitled "Provable Generation of Primes with Maurer".
The RSA signature used to sign/for comparison purposes used with Xbox execuatables is 2048 bits long.
Common secure internet traffic, carrying thousands of credit card numbers as we speak, uses 128 bit keys (almost always).
You are confusing symmetric and asymmetric ciphers. SSL (or "secure internet traffic", if you must) uses 128-bit symmetric keys coupled with larger (1,024-bits or greater usually) asymmetric keys.
In case some of your forget: it gets exponetionally harder as the length of the key increases.
"In case some of you forget" should be rephrased to "I'm going to state something authoritative now and hope I'm right". The 2,048-bit key you are alluding to is a asymmetric key (RSA). The fastest algorithms for factoring and computing discrete logs are sub-exponential!
MS have clearly hired proper cryptographers.
They certainly have, check out the names here for example. Gollmann, Leyland, Needham and Petitcolas are all pretty well known in crypto circles. Which asks the question: how can MS employ such bright people and still churn out insecure crap?
Although 2048 doesn't sound much more than 576, these are of course powers of two we are talking about. I fear the people attacking it aren't quite imagining what these kind of numbers mean.
Don't forget that there are sub-exponential algorithms for solving RSA/DH - so adding a bit of key doesn't double the time to solve. 2048 is still currently impossible though!
God, where to start....
"RSA requires that you have two true primes to generate they key but the problem is there is no known way to generate a 2048 bit true prime that can't be factored in the same about of time it takes to generate it."
Wrong. Entirely wrong in fact. You should read the Handbook of Applied Cryptography (kindly made available online here). See e.g. section 4.3. Proving a 2048-bit number is prime (I think you mean 2x 1,024-bit numbers, but....) should take a minute or two - not excessive for a one-off operation!
"forget it however there are several publications that indicate that the number of solid pseudo-primes that are 512 bits long is about 2^40 so its key strength is about the same as 40 bits."
Erm, where do you get this stuff from? What's a "solid pseudo-prime"?"Since we are talking about a 4x as many bits, a good guess of the strenght of a 2048 bit pseudo-prime would be about as hard as guessing a 160 bit DES like key".
Hardly - Certicom reckon that a 128-bit symmetric key is equiv. to a 3072-bit RSA key. Don't forget that, with symmetric keys, the strength usually doubles with each added bit of key material - the same isn't true for RSA or DH keys as there is now a sub-exponential algorithm for solving these problems....
The rest of your post doesn't get much better, but I'm off to eat sunday lunch now....Seriously, read HAC - it's good for you.
Sounds fine to me, at least for personal email accounts. If it's PGP signed, at least you can then verify the sender & get back to him/her.
How? Just because a message is signed doesn't mean that you know who the sender is. The mapping of e-mail addresses to PGP keys isn't one-to-one.
it's PGP signed spam, you can block it
And what prevents spammers creating "one time signature keys" that allow them to sign a message once and then dispose of the key? How precisely will you block a spammer from doing this?
How does signing a message in any way help you "prove" the origin of the message (e.g. does it offer anything more than the usual SMTP headers etc?).
Without imposing a lot more structure upon the use of PGP and e-mail (e.g. only accepting mail that's been signed with someone already in your keyring or trusted) then just saying "I'll accept signed messages" adds precisely zero.
I assume that your e-mail client will throw away any mails that aren't signed by a trusted key then? This is even worse than whitelists...Not only do you have to implicitly allow e-mail address you have to go through the pain of making users create and distribute key pairs (and possibly worry about the web of trust).
Just saying that "getting a signed mail" is enough is a naive approach: since one mail only needs to be signed once and can be sent to millions of recipients in one go this hardly raises the barrier for spammers. Even if spammers need to create a new keypair every time they want to send a new message this still won't slow them down - you can create "canned" keys in milliseconds.
There may well be a (non-hashcash like) cryptographic solution to the problem of spam, but just signing isn't a sociably acceptable solution IMHO.
The definitive text on cryptography, The Handbook of Applied Cryptography, defines the OTP as a type of encryption...I know this is Slashdot but I don't think your arbitrary definitions help here.
Sending a CD worth of random data via a secure channel in advance and then sending an encrypted message with the knowledge that it will be unbreakable is sometimes worth prior thought. Sure, it may not be usefull for the masses who require this kind of security or don't know their going to communicate in the future but to claim that this cipher "isn't encryption" is bull.
No - Mix + Mash ciphers aren't automagically immune, see quote from Schneier:
"While quantum computation can make problems such as factoring and discrete logarithms (which public-key cryptography are based on) easy, they can only reduce the complexity of any arbitrary computation by a square root. So, for example, if a 128-bit key length was long enough pre quantum computation, then a 256-bit key will be long enough post quantum computation."
-- B.Schneier, 10th Oct 1998 posting to soc.history.what-if USENET group
E.g. 3DES will be pretty much toast, as will AES128.
are there any problems that I missed?
RSA is based upon the Integer Factorization Problem (IFP) (*).
Elgamal / DH are based upon the Discrete Log Problem (*)
Eliptic Curves Cryptography is based upon, erm, Eliptic Curves.
(*) Note: there are no proofs that RSA or DH/Elgamal are actually as hard as the underlying IFP or DLP - e.g. they could be broken even if factoring is "hard".
To quote the author: "I get a lot of email containing the word "Lisp", and (so far) no spam that does".
He obviously doesn't getting the "Lesbians with a Lisp" pr0n......
About once or twice a year a bug of security significance is uncovered in PGP (e.g. the ADK bug, the RNG on UNIX bug, the keystorage bug etc) and this would render the latest 7.02 next to useless.
Why can't people amend the source code and recompiler themselves? They don't have access to the source code.
Also remember that PGP is now very (over-) complicated and includes various drivers and kernel hooks. Every new version of an MS operating system (Win2k, WinME, WinXP) breaks compatibility.
The best current hope is the CKT builds of PGP, that are based on the 6.5.8 code. These have all known bugs fixed and still work on all Win32 operating systems. This is also the only version that is actively maintained!
Often people say that "GPG needs a frontend before non-geeks can use it". That point is probably true, but even though NAI PGP has had a "mature" GUI based front end for several revisions, normal users are still incapable of getting their head around creating keys, the difference between public and private keys, the difference between signing and encryption etc etc.
A usability study was undertaken by researchers at Carnegie Mellon in which they found that virtually 0 non geeks managed to use PGP successfully anyway.
Sure, OpenPGP based programs need to achieve better reach, but simply copying the NAI PGP design won't achieve this goal....
We are discussing the NFS as used to solve the DLP/ IFP. NFS in this situation for any "bit depths" (key lengths?) is subexponential.
"I am 100% sure it is NP and 95% sure it is NP-Complete"
Factoring is known to be NP but there is no proof of NP-Complete - see e.g. Bob Silvermans post - he suggests that the conses is that factoring != NP-Complete.
That's true. I would be the first to concede that 3des can be broken with 3 chosen plaintexts, 2^56 blocks of memory, 2^111 encryptions and 2^111 operations (e.g. table lookups).
At the moment however, that attack is clearly infeasible, so I continue to recommend 3DES as "the best we've got" (at least until AES has gained further confidence in the crypto community).