Slashdot Mirror

Brute force EC does not require the memory size and bandwidth needed for things such as factoring in the Number Field Sieve (NFS). See:

Robert D. Silverman's paper

for more details. In short: Given two equivalently hard keys, one EC and one RSA, the EC key will require memory and less memory/CPU bandwidth and will be cracked for less cost using the state of the art methods we known today. NOTE: These art includes: THINKLE and NFS improvements including those discussed in the paper (on which this discussion thread hangs).

Worse for EC: It is an active field of research. Every so often somebody publishes yet another eliptic curve special class that can be cracked much faster than brute force. In some cases it is very hard to determine if a given EC belongs to a weak key class. While these are mostly theoritical, the smart cryptologist will view them as troubling for EC key securiy at best.

The NSA factors numbers, and their work is top-secret. When I read stories like this, I wonder if people are just discovering things that the NSA has known about for years. If the NSA could factor 2 Kbit keys, would they tell people? Probably not.

I hate to tell you this, but no one has patents on formulae. Do you think Newton patented his laws of motion?

You can prove mathematically how long n-bit encryption of n-bytes will take with n-procs at an average of n-mips. No one actually has to brute force it. You can't prove the existance of E.T. without searching through radio signals. They are fundamentally different things. RSA is doing this for publicity's sake not for any inherent or hopeful application.

...would be able to solve certain problems that would take an ordinary computer an enormously long time

From http://www.rsasecurity.com/rsalabs/index.html:

Why is WEP Broken?
The weakness in WEP stems back to a key derivation problem in the standard. ... While the WEP standard had specified using different keys for different data packets, the key derivation function (how to derive a key from a common starting point) was flawed.

To all you undergrads doing math exams this week: yes, you really do have to know how to do this in the real world!

factorization is easy

Factoring is the underlying, presumably hard problem upon which several public-key cryptosystems are based, including the RSA algorithm. (...) It has not been proven that factoring must be difficult, and there remains a possibility that a quick and easy factoring method might be discovered, though factoring researchers consider this possibility remote.

The problem is this. Let n be a given integer. We want to find out if n is prime. The method that we choose is the following. For each integer m = 2,3, ..., floor(sqrt(n)) we ask if m divides (evenly into) n. If all of the answers are `No,' then we declare n to be a prime number, else it is composite.

We will now look at the computational complexity of this algorithm. That means that we are going to find out how much work is involved in doing the test. For a given integer n the work that we have to do can be measured in units of divisions of a whole number by another whole number. In those units, we obviously will do about sqrt(n) units of work.

It seems as though this is a tractable problem, because, after all, n is of polynomial growth in n. For instance, we do less than n units of work, and that's certainly a polynomial in n, isn't it? So, according to our definition of fast and slow algorithms, the distinction was made on the basis of polynomial vs. faster-than-polynomial growth of the work done with the problem size, and therefore this problem must be easy. Right? Well no, not really.

Reference to the distinction between fast and slow methods will show that we have to measure the amount of work done as a function of the number of bits of input to the problem. In this example, n is not the number of bits of input. For instance, if n = 59, we don't need 59 bits to describe n, but only 6. In general, the number of binary digits in the bit string of an integer n is close to (log n)/(log 2).

If we express the amount of work done as a function of B; we find that the complexity of this calculation is approximately 2**(B/2) , and that grows much faster than any polynomial function of B.

The reason cryptosystems based on factorization are thought to be safe is because we can choose arbitrarily large values of n and we presume that there is no more efficient way to factor integers.

Now, if someone were to find a way to factor integers faster than O(n), we could still keep increasing n but that alone might not be sufficient.

Lets see if RSA labs will start another contest like DES III with a 10 grand prize. Heh, I say a year from now, we'll have new d.net clients :)

pUt th3 cr4cKp1p3 d0wN!

Lets see if RSA labs will start another contest like DES III with a 10 grand prize. Heh, I say a year from now, we'll have new d.net clients :)

pUt th3 cr4cKp1p3 d0wN!

To really drive the point home about how hard it is to factor these big numbers, check out the prize list for The RSA Factoring Challenge. If anyone doesn't believe that it's difficult, well, there's a total of about $635,000 waiting for the person who can prove that it's not!

Newer Smart Cards are capable of public key cryptography. They are not just an information store, like a magnetic stripe, but actually perform public key crypto on an embedded processor on the card which is powered by the reader. This way your public key never leaves the card.

Some of the better manufacturers of Smart Cards add all sorts of physical security to the chips as well...to the point where you can't even take the chip apart and scan the die with a electron microsope or special probes to try to read or trick the bits out of memory.

My guess is that the current Visa cards do NOT use onboard cryptography yet...that these are general purpose cards which for now store your credit card number and address for convenience because the infrastructure is not yet in place AFAIK to support public key credit card transactions. They may or may not already have crypto software onboard that could be used with a PKCS#11 driver, but the credit card companies just want to get them and the readers deployed, and then will provide a software update or something to actually add crypto features in your transaction in the next couple years. See the PKCS#11 standard written by RSA (on their web site) for the standard crypto API which has been adopted for smartcards.

Note that smart cards have been around for a while in europe, although they were typically not used in a cryptographically sophistically way.

See www.pki-page.org and http://www.rsasecurity.com/rsalabs/pkcs/pkcs-11/

Braddock Gaskill
Security Consultant
braddock@braddock.com

1. Win the RSA factoring challenge, put the money in a swiss bank account, and feed Illuminati(tm) back the account number.
2. Use genetic programming to predict the stock market, making billions of dollars from the $500,000 won in the factoring challenge.
3. Buy and sell peoples lives, based on loyalty to myself and Illuminati(tm).
4. Voila, world domination

'Course, I'm not sure Perl would be the best tool for the job...

The article treats RSA and DSA as one entity, and doesn't explain how they differ. I did some research and found that RSA is a cryptographic algorithm based on public and private key pairs, which we already know. So far, so good. Then I searched for DSA and found that it stands for Digital Signature Algorithm. Furthermore, that page says that DSA is only usable for signing, and not actual encryption.
This leads on to my question: The article says that SSH1 used the patented RSA key, but SSH2 uses DSA keys to work around the patent. How is it that SSH2 can use a signature algorithm to do real encryption?

See the RSA Crypto FAQ.

That is incorrect.

There are numerous algorithms that are more efficient that dumb brute force. That doesn't mean that will find the answer quickly, but vastly quicker than naive brute force attempts.

See the RSA FAQ, What are the best factoring methods in use today?

See the RSA Security FAQ, How Much Does It Cost?

The current record factorings were done with the GNFS (General Number Field Sieve).

GNFS consists of a sieving phase that searches a fixed set of prime numbers for candidates that have a particular algebraic relationship, modulo the number to be factored. This is followed by a matrix solving phase that creates a large matrix from the candidate values, then solves it to determine the factors.

The sieving phase may be done in distributed fashion, on a large number of processors simultaneously. The matrix solving phase requires massive amounts of storage and is typically performed on a large supercomputer.

Some pointers:

• Integer factorization
• RSA-155 English press release
• Description of the task, from Singh's The Codebook Challenge
• RSA-129 factoring
• What are the best factoring methods in use today? (RSA Security FAQ)
• A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths by Bob Silverman

In case you haven't noticed...It isn't easy, and cannot be fully solved using a distributed.net technique.

to factor a 760-bit number in one year would require 215,000 Pentium-class machines, each with 4 Gigabytes of physical RAM.

to factor a 1620-bit number in one year would require 1.6 x 10^15 Pentium-class machines, each with 120 Terrabytes of physical RAM.

Good luck.

The current record factorings were done with the GNFS (General Number Field Sieve).

GNFS consists of a sieving phase that searches a fixed set of prime numbers for candidates that have a particular algebraic relationship, modulo the number to be factored. This is followed by a matrix solving phase that creates a large matrix from the candidate values, then solves it to determine the factors.

The sieving phase may be done in distributed fashion, on a large number of processors simultaneously. The matrix solving phase requires massive amounts of storage and is typically performed on a large supercomputer.

Some pointers:

• Integer factorization
• RSA-155 English press release
• Description of the task, from Singh's The Codebook Challenge
• RSA-129 factoring
• What are the best factoring methods in use today? (RSA Security FAQ)
• A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths by Bob Silverman

In case you haven't noticed...It isn't easy, and cannot be fully solved using a distributed.net technique.

to factor a 760-bit number in one year would require 215,000 Pentium-class machines, each with 4 Gigabytes of physical RAM.

to factor a 1620-bit number in one year would require 1.6 x 10^15 Pentium-class machines, each with 120 Terrabytes of physical RAM.

Good luck.

Enter the name(s) of the submitter(s), the challenge number factored, the two factors, and an e-mail address at which RSA Labs may contact you.

From the FAQ:

As shown, to factor a 760-bit number in one year would require 215,000 Pentium-class machines, each with 4 Gigabytes of physical RAM. These are estimates based on today's best factoring technology.

I don't think distributed.net will make much progress based on current algorythms. Most people just do'nt have that much memory to donate to the cause. Might be time to invest in memory makers if you think they will buy it.

laughably easy?

So I created Whisper. Whisper is password based, rather than public key based, because it's easier for people to understand. (Of course you must pick a strong password if you want it to be secure against a determined attack.)

I've not yet found anyone who can't Whisper. What I need at the moment are people to audit the crypto (it's basically PKCS-5). Also I am currently planning a new version, so please suggest any features you want on the SourceForge page.

Of course if you want to help develop it, that would be welcome too.

It appears your requirements are to simplify the login and security process. Regardless of the solution on the front end, you will need to develop a means of synchronizing passwords across the enterprise. This is a task in itself. I am certain someone here knows of a software package that does this.

Biometrics, while having some very cool technology, does have some drawbacks. Mainly, they depend on people to remain somewhat consistent across your workforce. While this would seem easy enough, consider that fingerprint scanners assume you have one. That eliminates most people missing hands, although they may be capable of doing the job.

Retinal scanners, and voice print have some issues with consistency (i.e. colds, hangovers, etc.) that can present an issue especially if you are not in a very high level security area. (You will become immediately unpopular the first time your boss cannot get her presentation, because of a head cold).

Now there are ways around all of these issues. However, if you have to handle the exceptions in the normal process of business, then what is the point?

You may want to try a key fob RSA SecurID.[I am sure there are other companies too] The fob changes its code every 30 seconds in synchronization with its host. A friend consults at a company that uses this to create a connection from anywhere. They have it set up to use a pin, key fob, IP combination to authenticate. If any one piece is changed, the access is rendered useless. After signing in, you are set to go. Now she did end up with two fobs but I believe that one is the "normal" environment, and the other authenticates the high security system when she needs access there.

Good luck, and I would be interested in hearing what you decide upon.

- There's so much I still don't understand...as it should be

The AES finalists were:

MARS (IBM) (their case)
RC6 (RSA) (their case)
Rijndael (their case) (how to pronounce it)
Serpent (their case)
Twofish (Counterpane) (their case)

rjh writes:

I'm very hesitant to declare RSA to be "one of the best types around". RSA is built on several conjectures, none of which have been proven, namely:
1. The only way to make a general break of RSA is to factor large composite numbers
2. Factorization of large numbers is an NP-complete problem,
3. P != NP

#1 is incorrect, there are a few ways to break RSA, only one of which is to factor large composite numbers (another is this Leo person's method). Assuming effective key management, no method has been found which is significantly easier than the factorization problem (although some are no harder). For more detail, see http://www.rsasecurity.com/rsalabs/faq/3-1-3.html.

#2 is also incorrect. Factorization is probably not NP-Complete, but RSA never depends on it being NP-Complete, merely on it being really hard to solve. Factorization is provably NP, but has not been shown to be NP-Complete. This is potentially a good thing, if #3 ever falls through for the NP-Complete set, the fact that it isn't NP-Complete means that Factorization will probably still be hard.

#3, of course, has not been proven. It also has not been disproven, despite hundreds of mathematicians trying for decades. A good analysis of the issue is at http://ic-www.arc.nasa.gov/ic/projects/bayes-group /NP/ijcai91/paper/IJCAI91-paper.html.

Just because #3 hasn't been proven doesn't mean it's not a useful assumption. People routinely bet their lives on much flimsier ones.


----

Hate to say it, but that's not true. If you've got something like Back Orifice (or a keystroke sniffer, or even a shoulder surfer) on your machine, then the jig is up. You need to use something which incorporates biometrics in order to be really sure your communications are secure and identifiable. Heck, even a SecuurID is better than a plain password dialog.

-B

VeriSign will give you a X.509 Cert (possibly in a PKCS#7 Message Format).

VeriSign might deliver Certs on SmartCard-like token, which are accessed from Netscape via a PKCS#11 compliant driver.

VeriSign will give you a X.509 Cert (possibly in a PKCS#7 Message Format).

VeriSign might deliver Certs on SmartCard-like token, which are accessed from Netscape via a PKCS#11 compliant driver.

Check out this link to see how this movie is also going to involve RSA's secureID cards. This movie should rock. Good actors, good technology :)

Ian

Factoring n into p and q is necessary for breaking the RSA code. If you factor n into p and q, you can generate the inverse of a. RSA relies on the fact that factoring the product of two primes is extremely "difficult" while multiplying p and q to get n is "easy".
For more info on what easy and difficult really mean, read up on Big-O notation (i.e. O(n) is linear running time, O(2^n) is exponential growth) and NP completeness. :)
Factoring:
Well, of course, you can brute force p and check to see whether you get an integer q. If you're using large primes (300 digits or so) for p and q, prepare to be long dead before you get q with our current computing.

I won't go into detail, but here are some popular factoring methods for you to look for, and a link:
Pollard Rho method
Pollard P-1 method
ECM (Elliptic Curve method)
Multiple Polynomial Quadratic Sieve (MPQS)
According to the link below, "The best general-purpose factoring algorithm today is the Number Field Sieve"(NFS)

For more info including Big-O notation (i.e. an idea of how fast the algorithms work as the size of n increases), check out:
http://www.rsasecurity.com/rsalab s/faq/2-3-4.html

Yes, I know you are kidding, but RSA's excellent Crypto FAQ has a section with all the references you should need for factoring algorhithms:
http://www.rsasecurity.com/rsalab s/faq/2-3-4.html

Also, http://www.rsasecurity.com/rsalab s/faq/2-3-5.html has some good info about what the future holds for factoring.

----

Yes, I know you are kidding, but RSA's excellent Crypto FAQ has a section with all the references you should need for factoring algorhithms:
http://www.rsasecurity.com/rsalab s/faq/2-3-4.html

Also, http://www.rsasecurity.com/rsalab s/faq/2-3-5.html has some good info about what the future holds for factoring.

----

Yes, I know you are kidding, but RSA's excellent Crypto FAQ has a section with all the references you should need for factoring algorhithms:
http://www.rsasecurity.com/rsalab s/faq/2-3-4.html

Also, http://www.rsasecurity.com/rsalab s/faq/2-3-5.html has some good info about what the future holds for factoring.

----

Releasing the RSA to the public domain is great, but what i really care about is the free tshirt!

Get used to your e-mails being insecure. I know people are going to say "encryption", but think about this:

Before Quantum Cryptography becomes available, Quantum Computing will have arrived (many suggest within a few years) and it will render insecure most or all encryption methods using conventional computers. It has been proven that a quantum computer will be able to factor large primes (see reference in RSA's overview which, interestingly, predicts that quantum cryptography will be realised before quantum cryptoanalysis -- but they would say that, I guess ...).

(Find more about Quantum Cryptoanalysis on AltaVista.)

Sorry guys, but encryption will soon be a thing of the past (before it rises again in a different form on a different infrastructure). Bye, bye privacy, bye e-commerce, bye.

Learn to live with it.

(For the record: there is a different issue in some of the comments: should the Govt snoop your e-mails as a matter of routine? I don't think they should, any more than I think they should read all the postcards that are sent through the mail.)

---

"Where do you come from?"

Then you could say bye-bye to rc5-64. Perhaps before long you could eat rc5-64s like popcorn and go on to the other challenges at RSA.

For Plasmoid: the RSA FAQ us a really good place to start, esp. if you've heard a lot of crypto-talk, but gotten lost among the alphebet-soup anagrams and what-means-what. Also, although you've probably been told this a cazillion times already, Schneier's Applied Cryptography is a helluva book-- comprehensive and well written-- worth every penny. He also writes a newsletter, The Crypto-Gram. Backissues are availible at the Counterpane website. You also might want to check out newsgroups like sci.crypt.

That's all I gots for you, kidd-o. Good luck on the prog.

I know it ain't this way anymore, but once upon a very long time ago, it used to be law that the results of research paid for with taxpayer dollars were public domain; unpatentable and uncopyrightable. Anybody who wanted to make a buck off the technology was free to create an added-value package using it (e.g., MatLab). The demolition of this policy, allowing university and corporate researchers to take proprietary ownership of technology developed with OUR TAX DOLLARS (e.g., RSA) is one of the biggest betrayals of the public trust by the U.S. government in recent times.

Who in the US is gonna have a party on 29 Sep 2000?

That's when the hated RSA patent expires....

I think we should organize a giant SSL installfest on that day! Any takers? ;)

Your Working Boy,

I'm surprised you made a claim like this without backing it up...

R is definitely for Rivest. Check the "What is RSA?" section of RSA's cryptography FAQ. I quote directly:

RSA is a public-key cryptosystem that offers both encryption and digital signatures (authentication). Ron Rivest, Adi Shamir, and Leonard Adleman developed RSA in 1977 [RSA78]; RSA stands for the first letter in each of its inventors' last names.

• Overview of Stream Ciphers
• Shift-Register Stream Ciphers
• Several Stream Ciphers
• Crypto FAQ on Stream Ciphers

Remember stream ciphers != block ciphers.

RC4 and SEAL are notable stream ciphers; the usual distinction between a stream cipher and a block cipher is that block ciphers work with "blocks" (or "packets") of material, whereas stream ciphers work with far smaller "blocks," commonly a single word or byte. The pathological example of a stream cipher should encrypt bit-by-bit; on computers with word sizes of 32 bits, it would make considerable sense to treat a 32 bit word as the "atomic unit" being encrypted.

Whether the "atom" is a bit, byte, or word, the critical issue is that the unit of encryption is liable to be a whole lot smaller than the 56 bytes one might have in an Ethernet packet...

I don't understand the importance of this inclusion as I figured that it was already in their secure server version. As far as I understand RSA will not allow you to license their stuff in the USA without it's use.

Our company uses a similar system called "SecurID" tokens, which generate a unique number every twenty seconds or so that you use with a PIN to login to a system...

There is a problem though: Tokens. By that I mean the plurality of tokens possible, at one point I had three seperate tokens (all which look identical apart from a serial number in the back). As more places use tokens, the problems will get worse. What we really need is a standard for a token based system where you could have different services that need security transmit some kind of token generator into a token - like the SecurID token generator for the Pilot, so you could select the token account you want from one physical token.

• The security of the data during transmission
• The Authentication of the end-users

Using two factor authentication solves this problem quickly, and contrary to the poster's expectation, it doesn't set back projects 2-3 years. In fact, it usually accelerates them because all of the password management functionality is taken care of. No need to check for "easy" passwords, no need for "difficult" passwords.

If you look at RSA Security SecurID products, you'll see how it can be used to authenticate users with one time passphrases, making cracking tools, brute force and even sniffing attempts useless.

I've had the opportunity to install these servers in Banks and government agencies and know firsthand of the relief they have since they don't have to always worry about password exchange (most employees keep their password on sticky notes) between employees.

--
Let's not all suck at the same time please

RC5 is an encryption algorithm from RSA Labs. A RC5 'key' is a specific decryption code that might decrypt an encrypted message. RSA is sponsoring a contest to see if anyone can crack a message encrypted with RC5.

The reason this is even mentioned is because there is a group that is working on this contest using a 'brute force' attack. distributed.net has a client you can download that will allow you to participate in this contest, along with thousands of other people.

This client is designed to use all CPU time that would otherwise be 'wasted'. People tend to use it as a benchmark, even though it's not very representative of actual computing power, since it uses a small number of instructions repeatedly.

If you have more questions, feel free to email me at decibel@distributed.net

dB!
distributed.net Human Interface

RC5 is an encryption algorithm from RSA Labs. A RC5 'key' is a specific decryption code that might decrypt an encrypted message. RSA is sponsoring a contest to see if anyone can crack a message encrypted with RC5.

The reason this is even mentioned is because there is a group that is working on this contest using a 'brute force' attack. distributed.net has a client you can download that will allow you to participate in this contest, along with thousands of other people.

This client is designed to use all CPU time that would otherwise be 'wasted'. People tend to use it as a benchmark, even though it's not very representative of actual computing power, since it uses a small number of instructions repeatedly.

If you have more questions, feel free to email me at decibel@distributed.net

dB!
distributed.net Human Interface

RSA Security's own site says that the patent on RSA runs out in 2000. see: http://www.rsasecurity.com/rsalabs /faq/6-3-1.html