Slashdot Mirror
Factorization of a 768-Bit RSA Modulus
dtmos writes "The 768-bit, 232-digit number RSA-768 has been factored. 'The number RSA-768 was taken from the now obsolete RSA Challenge list as a representative 768-bit RSA modulus. This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one. Because the first factorization of a 512-bit RSA modulus was reported only a decade ago it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours . . . . Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.'"
Isnt it AES?
I don't believe you. Post your account credentials so I can check for myself.
I hope this is a joke. If not, you are confusing the strength of symmetric key encryption and public key encryption. The latter requires larger key sizes because the public and private key pair are mathetmically related whereas in symmetric encryption, there is a single key, and it ought to be randomly generated, and have no mathematical relation to any other value.
The key sizes are given for RSA/DSA encryption. Elliptical curve crypto can use much smaller key sizes while maintaining equivalent security levels. Unfortunately, most ECC is patent encumbered.
Isnt it AES?
Ha, all my important documents are encrypted in Lucifer
ALL HAIL SATAN!
WTF? 2^1024 != 2^768*1000
Screw you slashdot for making me type more than my perfectly concise statement above that gets the effing point across just fine.
Maybe they force him to use 128-bit RSA. He didn't really specify.
Don't worry, your money will be safe in my offshore account.
God invented whiskey so the Irish would not rule the world.
I was always a fan of twofish, My Niece on the other hand like the red and blue fishes better
So I just did a Wikipedia Crash course on RSA (I knew it was for public/private key encryption) and how it all works mathematically.
But I still don't know what they mean by Factorization, or what that exactly means.
I'm guessing they found all and compiled and tested the possible values and now have a nice big chart? Is 768-bit RSA now considered "broken"?
AES is a symmetric block cipher, meaning, you both need a shared key. While yes, the actual encryption on the data may be AES (I don't know this for sure), you still need to use a public key encryption method like RSA in order to handshake and transfer keys to each other before using AES.
Yes, but he's likely referring to the strength of the SSL connection to his bank. While authentication is done with public key crypto (probably 1024 or 2048 bit key), the actual data stream is encrypted with some symmetric cyrpto algo such as AES or RC4 at 128 or 256 bits.
1024 bit RSA keys are already considered insecure due to the possibility of finding more efficient algorithms. 2048 is considered secure enough.
I was always a fan of twofish, My Niece on the other hand like the red and blue fishes better
Atleast she doesn't do blowfish.
We are forced to use 128-bit encryption for online banking!
Maybe you need to get a better bank! I just logged into a top 5 Canadian bank and they are using AES-256 with a 1024-bit RSA cert.
Which is same as his onshore account?
A lot of banks here still only support 128-bit, most of them only support 128-bit RC4 and don't have support for any kind of AES, let alone 256-bit.
PayPal used to do AES256, but they also don't support it anymore, which seems quite ridiculous.
http://spamdecoy.net - free throwaway anonymous email - avoid spam!
I'd agree with that for government and it's true that the military should phase out 1024, but does the general public need to worry?
How much is your data worth? Back it up now.
Keep in mind that AES-256 only uses a 128-bit key and has recently been broken (down to 118 bits of security or something like that?). AES-256 is currently less secure than AES-128.
128-bit keys for symmetric ciphers, such as we use for banking equate to much large key sizes for asymmetric ciphers such as RSA. You are comparing apples and volkswagens.
linquendum tondere
Well, djb wrote a particular algorithm, Curve25519, that's in the public domain.
(Yeah, yeah, save your comments about djb's personality. Like it or not, the guy's a crypto and security genius.)
My blog
AES-256 uses a 256-bit key. It has a fixed block size of 128 bits, but that's unrelated to the key length.
There is a related-key weakness in AES-256 and AES-192, bringing their effective strength down to 2^119 and 2^176 respectively. So AES-192 is your best bet right now, though 2^119 or 2^128 are not exactly feasible attack keyspaces either.
uhh, no.
AES-256 uses a 256 bit key. It may have a weaker than expected key schedule for using that key, as Schneier has opined (do I know what that means? Not a chance), but it's certainly 256 bits long.
And the worms ate into his brain.
And you know this how?
That would be RBC ;) BMO uses 3DES-196, TD also uses AES-256, but with a 2048 cert. Scotia Bank and CIBC use RC4-128 though. I guess the OP uses one of those two, and figured "if my bank does this, they all must!"
ASCII stupid question, get a stupid ANSI
Yes, but he's likely referring to the strength of the SSL connection to his bank. While authentication is done with public key crypto (probably 1024 or 2048 bit key), the actual data stream is encrypted with some symmetric cyrpto algo such as AES or RC4 at 128 or 256 bits.
That is only helpful if the person sniffing the SSL connection doesn't capture the initial handshake.
The problem with symmetric crypto is key exchange. With SSL the client generates a premaster key, encrypts it with the server's public key, and sends it to the server. Then the client and server use this to derive a session key (at least, that is my reading of the relevant docs - I think the specifics depend on the exact cipher used). So, if you can crack the RSA key, then you can obtain the session key, which makes the entire session obtainable.
To use symmetric crypto you either need a shared secret, or you need to use a key-exchange technique. I believe all the key-exchange techniques are vulnerable to factoring (or P=NP issues in general), although their details vary. If factoring becomes easy we'll never be able to encrypt communications between parties unless they have a secure channel to exchange keys (typically involving plane tickets).
Disclaimer, I'm not a cryptographer and if somebody has more to add I'm all ears.
The new Intel proc's rock at AES encrypt/decrypt. Which will likely make it the speed king over blowfish.
Storm
He said patent encumbered, not copyrighted.
Something can be open source and if it implements something protected by patent in the US or in other nations with laws that allow software patents or have agreements to make US patents enforceable, then it can still be illegal to distribute, and you'd probably be liable for damages if you built commercial software, but IANAL.
I think the patent encumbrances of ECC are the reason it's mysteriously absent from a lot of commercial software that deals with security and even a lot of Linux distros and software. I'd have to double-check, but for example, I don't think Windows Certificate Services supports ECC.
P.S.: Isn't it horrible that Error Correcting Codes and Elliptic Curve Cryptography have the same acronym? IMHO, we should rename one of the TLAs before it becomes a PITA.
Yeah, I'm aware. I'm just pointing out what the first post was likely referring to.
The number RSA-768 was taken from the now obsolete RSA Challenge list as a representative 768-bit RSA modulus.
In fact, the challenge list is defunct, the challenge having been canceled by RSA. The challenges are still scientifically interesting, so to call them obsolete is factually inaccurate.
You're so wrong I'm not bothering to provide a correction. If your laziness and opinionated ignorance is that great, it's probably a waste of time. Google is your friend.
I thought they share a key with the http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange
So it doesn't matter if someone captures the initial handshake.
Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.
Or immediately if you are encrypting things now which you want to remain secret throughout the decade and beyond.
Ceci n'est pas une signature.
So it doesn't matter if someone captures the initial handshake.
It matters if they can break the public key encryption, and thus discover the shared private key.
The enemies of Democracy are
No bank enforcing that policy would be in business long. 128 bit RSA keys can be broken in milliseconds with code written by a mildly persistent 6th grader.
Fwoosh.
> Atleast she doesn't blow fish.
Fixed that for ya.
If I am understanding correctly, the problem is that p is usually a pseudoprime, rather than a true prime. If you can factorize that, solving for a, b, and thus K becomes far easier.
The pseudoprime bit is because determining whether an arbitrary large number is prime is computationally expensive, but there are shortcuts that will detect most non-primes, but some numbers called pseudoprimes with very large factors slip through, which are usually good enough, as even though they aren't a true prime, there isn't an easy way to factor large numbers, and it therefore takes a long time. But as computers progress, what was impractical before becomes practical.
upon the advice of my lawyer, i have no sig at this time
Or you could just use tiny atoms...but have you priced those lately? I'm not made of money!
I am no expert in cryptography, but I remember my CS friends talking about 2 locks on a briefcase.
The shared key is encrypted with key A by Adam and sent to Betty (who can not open it without key A). Betty encrypts this with key B and sends it back to Adam. Adam decrypts this with key A and sends in back to Betty. Since the message now is only encrypted with key B, Betty can open it and get the shared key.
Or is this only a educational exercise and in actuality if you eavesdrop all of these transactions you can determine key A and B?
Wait. There are intel chips now that do AES ? Like VIA's padlock ? 256 bit AES ?
Religion is what happens when nature strikes and groupthink goes wrong.
I'm unsure exactly what system is used but public keys may be used more thoroughly than you describe.
Example 1 : There are perhaps both presever and preclient keys that must be xored together, which are created separately on each side, and sent using the other's public key, thus ensuring that an eavesdropper must break both server and client public keys.
Example 2 : A sever could generate a session RSA key, digitally sign the session public key, and send both the session public and the server public key as well as the certificate authority's signature for the server public key. The client first verifies the signature for the server's public key and the session public key, then creates a symmetric session prekey like you describe, encrypts that symmetric key with the session public key, and send it to the server.
You may break this in three ways according to conventional wisdom :
(1) quickly break the session public key and listen live,
(2) slowly break the server public key and execute a man-in-the-middled attack to listen live,
(3) record the whole conversation, slowly break the session public key, and listen offline.
I'm pretty sure people breaking these large keys are not breaking them fast enough for (1), which already provides significant privacy.
You may also force them to break both the server and client key for (2) or (3) by symmetrizing the process with preserver and preclient keys, as described in Example 1 above.
Indeed, Example 2 may offer minimal advantages over Example 2 if virtually all connections originate from strangers, ala online banks. Remember, if you make the attacker break n separate keys, your increasing the computations cost for both attacker and legit users by the same factor. If otoh you just use larger key size, then attackers spend far more additional time than users.
The Christian religion has been and still is the principal enemy of moral progress in the world. -- Bertrand Russell
The whole point of this story is that the math behind public keys can be broken after this amount of computation, given a 768 bit key. DH is not special in this regard.
- Michael T. Babcock (Yes, I blog)
Whenever something comes up involving work with very large numbers, I have to try to explain this seemingly simple concept to people and usually they look at me like I'm either insane or an idiot. The people that have a decent grasp of math and some common sense, though, get their minds blown and have a new respect for encryption, which is rewarding.
Eh, the one doesn't really have anything to do with the other. What you're talking about is 128 bit AES, which is symmetric encryption, which is shifting, xoring, and otherwise the making of chaotic of a block of data (16 bytes, in this case). RSA asymmetric encryption/decryption is more like a calculation that you miss certain parts of and therefore can really only be performed one way. To put it another way: symmetric encryption sees a block of data as a bits to be pushed around, while asymmetric encryption sees a block of data as a number to perform a calculation on. A really big number. Strengths of keys in amount of bits are useless in a comparison of both algorithms.
Religion is what happens when nature strikes and groupthink goes wrong.
Public key and regular symmetric block ciphers differ completely in usage and attack.
Public key crypto is typically used to hide a random session key for a symmetric block cipher which is then used for the rest of the "conversation".
That is to say, your bank transactions are being encrypted with some block cipher like 3DES or AES whose random session keys are exchanged privately between your computer and the bank using public key crypto.
If your bank's public key were broken (this story), anyone could get the session keys by evesdropping on your initial connection to the bank. If the block cipher were broken, anyone could grab your data no matter the security of the public key.
- Michael T. Babcock (Yes, I blog)
Yahoo Canada's sign-in is 1024-bit RSA using SHA-1 signatures, and a 128 bit RC4 session key.
- Michael T. Babcock (Yes, I blog)
The problem is that this is an oversimplification. See the WP entry on Diffie-Hellman.
The values sent between Alice and Bob are inter-related via the discrete log problem - so if you can (relatively) quickly calculate discrete logs you can obtain the session key.
This particular article is about factoring and not discrete logs. A magic way to quickly factor numbers wouldn't necessarily break D-H. However, this article wasn't about a magic way of breaking RSA, but brute-force factorization. If you can brute-force 1kbit of RSA, you can brute-force the equivalent strength in D-H or DSA. The bitwise strength of the two probably isn't identical, but the principle is the same.
The real threat is if somebody comes up with some kind of quantum technique to factor or discrete-log big numbers. If that happens all kinds of NP problems get solved in realtime and that messes up everything. The slow growth in brute-force speed is fully anticipated, but there are practical upper-limits on computing power (if every quark in the universe is a logic gate and is compressed into a near-singularity, the system only goes so fast).
If symmetric key cryptography gets broken in general, what likely will happen is that the well heeled businesses would have a link between sites using quantum encryption. This link is extremely slow, so it would be used to set up session keys. Then the conventional Internet links would be used for the bulk data transfer.
People who don't have the cash for fiber optics would have to use lower tech means. One means would be have people generate a one time pad, and instead of PGP/gpg keysigning parties, people would trade chunks of random numbers with each other. Later on, people would go home and XOR the keyfile they got with the keyfile for a persistant key, and that would then be used with some other system (sha-512 hash of date/time + the keyfile) for a message based key. This way, a known plaintext attack wouldn't reveal the long term key (similar to a shared WPA2-PSK secret).
Where things would get hairy with no public key encryption are one to many transactions, such as communicating with a bank. This probably would end up getting solved by some type of smart card system where the bank's servers have a large amount of shared keys, while the customer would have a smart card that would handle the session key generation, but prevent the shared key from leaving the secure container.
There are plenty of alternatives to public-key crypto based on factoring. And it's pretty certain that it won't become "easy" for decades if ever, since quantum computers are coming along so slowly
// MD_Update(&m,buf,j);
I think the patent encumbrances of ECC are the reason it's mysteriously absent from a lot of commercial software that deals with security and even a lot of Linux distros and software. I'd have to double-check, but for example, I don't think Windows Certificate Services supports ECC.
http://blogs.technet.com/pki/archive/2008/01/23/how-to-set-up-a-ca-with-a-cng-ecc-certificate.aspx
Since Vista and Windows 2008 it does, but through CNG not through the more familiar CryptoAPI / CSP.
Even then it is limited to certain NIST curves - forget about doing any enhanced EC cryptography through that API.
What is funny is that in 1991, the NeXT had an implementation of ECC Fast Elliptic Encryption as part of the OS (think NeXTStep 2). However due to ITAR regs, it was removed from subsequent versions.
RSA Labs explains the meaning of factorization in the old Challenge FAQ:
http://www.rsa.com/rsalabs/node.asp?id=2094
Look at the section, "What does it mean when a Challenge Number is factored?"
It is interesting to note that this section of the FAQ makes an example of RSA-768 being cracked in 2010 -- turns out they were very close, whether they tried to be or not (the article states that the number was actually factored in Dec 2009).
There is a related-key weakness in AES-256 and AES-192, bringing their effective strength down to 2^119 and 2^176 respectively.
Only for related key attacks. Never ever leave out the context when talking about broken cryptographic algorithms.
Check it out, if you just generate a random key for each file you encrypt, then no such attack can take place.
AES-128 is certainly strong enough for the first couple of years anyway.
GNFS doesn't work by trivial division by all possible divisors. In fact, GNFS is exponentially faster than trial division.
Factoring N with GNFS works by searching for a collection of square equations, i.e. ones trivially factorable into two parts, which are equal mod N. Once several of these are found you take the GCD of their values and the result is one of the factors. For an RSA number there are four possible results, two are useful (the factors) two are not (1 and N). GCD is very very easily to calculate fast. If you get a trivial result you try another set. It only takes a few candidates before the chance of failure is acceptably infinitesimal.
I believe all the key-exchange techniques are vulnerable to factoring (or P=NP issues in general), although their details vary.
There's an exception: quantum key-exchange. You send the key, and the receiver can tell at the other end whether it was sniffed en route. If it was, they don't use it.
Since then, however, ITAR regs have been altered; I don't think the Fast Elliptic Encryption in NeXTStep 2 would be subject to todays ITAR regs.
My blog
Too bad it's already been cracked.
https://www.eff.org/https-everywhere
"If factoring becomes easy" --- factoring is just one problem whose difficulty can be used to create a difficult-to-break encryption system. The discrete log problem is essentially different from factoring, and would still be secure if factoring were easy; there are other such problems that can also be used.
They found a vulnerability *in a piece of hardware they developed* --- there are other valid receivers beyond the one they developed. This means quantum crypto is still possible, just not with the kind of receiver they broke.
There are potentially three sets of crypto used - RSA, optional ephemeral Diffie-Hellman for more secure key exchange, and the symmetric crypto for message body encryption (typically 3DES or AES.) Symmetric crypto uses relatively short keys, typically 128 or equivalent-to-112 bits; the public-key algorithms use longer keys, but they have special forms so they _need_ to be longer.
Diffie-Hellman key exchange is roughly similar in strength to RSA encryption or signatures.
More importantly, if the Bad Guy can crack your RSA keys, then the Bad Guy can impersonate you in Diffie-Hellman key exchanges by doing a man-in-the-middle attack and forging signatures on the DH key parts.
So if you're using a 768-bit certificate for some reason, or a 1024-bit certificate and the NSA is out to get you, you're vulnerable. (If the KGB is out to get you, it's moot, because they'll sneak into your house or data center and put a keylogger in your keyboard. And if the Mafia's out to get you, they'll just threaten to break your kneecaps.)
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
No, that's not the problem. Yeah, one time in a million or billion you might have RSA key parts that aren't really primes, but you can decide how paranoid you want to be, and that's not a practical attack. This factoring is taking the RSA public key n=pq and using a combination of good algorithms and lots of brute force to find p and q, and works even when p and q are genuine primes. If p were a fake prime, it might take less horsepower to find it, but this is cracking the hard problem, not just the occasionally-lucky case.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
This isn't just brute force - the algorithm research has meant that our ability to factor large numbers has been growing a *lot* faster than Moore's law. That doesn't directly apply to breaking DH, except to the extent that factoring is useful in breaking discrete logarithms or the algorithms used are useful for it.
The catch is that you usually keep an RSA key around for a while; DH is often used with ephemeral parameters as well as ephemeral keys, so even if you had a year-long DH crack, it might only let you steal one message. On the other hand, cracking RSA signatures lets you do a man-in-the-middle attack where you substitute your forged DH parameters (which you know) for the target's supposedly-securely-signed parameters.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Something like 256bits extra bits of encryption for every 5 or 10 years.
So well probably need approx 25Kbit keys if we are even to have a chance of keeping something encrypted for 100 years. 3Mbit keys for a 1000 years...
Westmere and onward have instructions that implement the cryptographic primitives used by Rijndael (of which AES comprises three modes); MixColumns, SubBytes, and ShiftRows (and the alternative Inverse variants for decryption). Keying, encryption, and decryption will be significantly faster.
True - wasn't thinking of this offhand. I wouldn't really classify this as an algorithmic key-exchange technique since it depends on physics more than math.
It also has some significant limitations - being able to get photons from one point to the other without any routing (or you have to trust the routers). It isn't easy to send single photons over any kind of distance. It isn't impossible, but it isn't like it can be used to get a key from one arbitrary location to another one 100 miles away. Just getting it to an arbitrary location 10 miles away would probably be a big challenge. Fiber optics work over moderate distances, but that doesn't get you to arbitrary locations.
I think that in practice one-time-pads used to secure session keys would actually be more practical. You just generate a tape with 1TB of random data on it and fly it to your remote office, and now you can change 128-bit keys every 10 mins for a VERY long time. With only moderate conservation of session keys two friends could exchange 1GB flash drives and be set for life. If this sort of thing were standardized in software your bank could give you a flash drive when you get an account and you'd have a secure channel for a long time as well.
Actually, this sort of system could be far more secure than SSL/RSA (no need to trust a CA when the bank hands you the key at the same time you hand them your cash). The only trick is keeping people from copying your key data without your notice.
The way it's usually done is that the public keys are used to encrypt just the symmetric session-specific key (since public key crypto is too slow to encrypt anything substantial) and then the symmetric keys, which are 128 or 256 bits long, encrypt the actual content. So it's not just authentication, it's the setting up of the encrypted connection that public keys are used for.
It's generally believed that if you can attack factoring, you can attack discrete logarithms, so Diffie-Hellman in integer prime-number bases is still risky, so if Quantum Computers ever get good enough to bother RSA, they'll be a real pain. On the other hand, Elliptic Curves may still be safe. Nobody's sure quite how safe (right now EC keys can be significantly shorter than factoring-based RSA or DH, but that may fall if there are theoretical breakthroughs, which is much less likely with factoring), but they may be enough, and at least the patents will have run out before Quantum Computers get good enough to factor numbers more interesting than 15.
But otherwise you're stuck with secret-key symmetric cryptography, or One-Time Pads. Remember Kerberos and the various other systems that depend on a Master Key locked safely in a Key Distribution Center? Remember couriers with briefcases handcuffed to their arms? Yuk! There were good reasons to use public keys instead!
There has been some work done on quantum-computer attacks on symmetric key systems, but AFAIK the best that it looks like they'll do in general is to effectively halve the key length, so that's easy enough to work around.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
The basic Elliptic Curve Crypto math was published in 1986 and isn't patented, but there have been a lot of implementation techniques that let you use the stuff efficiently which have been patented. However, even many of those patents have expired already or will soon (plus some of them have problems with prior art that could sink them, but the prime example of that is the Apple/NeXT patent which expires Real Soon.) There are a bunch of patents that issued in 2001 that may be a problem, but even those expire in 2021 unless the US does a Disney and extends them.
The good news is that effective Quantum Cryptography is a ways off - it's unlikely that the next decade will give us widespread effective QC that can reliably factor big numbers, so we aren't likely to need wholesale replacement of free crypto with patented crypto before then.
On the other hand, if QC can also crack ECC, that'd be annoying.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Disclaimer, I'm not a cryptographer and if somebody has more to add I'm all ears.
I am a cryptographer, and your last paragraph has a few details wrong, although the general idea is correct.
I believe all the key-exchange techniques are vulnerable to factoring (or P=NP issues in general), although their details vary.
In fact, even symmetric key crypto is vulnerable to P=NP issues. A nondeterministic Turing machine can break symmetric key crypto just by guessing the (shared symmetric) key.
If factoring becomes easy we'll never be able to encrypt communications between parties unless they have a secure channel to exchange keys (typically involving plane tickets).
There are many public key cryptosystems known, based upon a variety of hard problems. Some of these problems are identical to factoring, some of them (such as discrete logarithms over finite fields) are closely related (but not identical) to factoring, and some of them (like lattice rounding) have, as far as we know, no relationship to factoring.
If factoring becomes easy, we'll just switch to another public key cryptosystem based on a different hard problem. In particular, lattice-based cryptosystems are believed to be secure even against quantum computers.
nm
So, 10^80 atoms in the universe, which is around 2^265, so 2^768/2^265 = 2^503, or a universe 2.6x10^151 times larger than ours (with all of the caveats I've pointed out elsewhere in this thread about how that's a very rough guesstimate.)
Thanks for pointing out my craziness. :)