Slashdot Mirror
Math Advance Suggest RSA Encryption Could Fall Within 5 Years
holy_calamity writes "The two encryption systems used to secure the most important connections and digital files could become useless within years, reports MIT Technology Review, due to progress towards solving the discrete logarithm problem. Both RSA and Diffie-Hellman encryption rely on there being no efficient algorithm for that problem, but French math professor Antoine Joux has published two papers in the last six months that suggest one could soon be found. Security researchers that noticed Joux's work recommend companies large and small begin planning to move to elliptic curve cryptography, something the NSA has said is best practice for years. Unfortunately, key patents for implementing elliptic curve cryptography are controlled by BlackBerry."
otherwise hackers will use it to mess up the internets.
...the NSA will have a backdoor into that epileptic curve whatnot too.
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
https://www.schneier.com/essay-198.html
OpenSSL has had a good working implementation of ECDSA/ECDH for years: http://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography
What exactly does BlackBerry have chained down that we don't have an open solution for?
/* * pope1 */
I recently took a survey put out there by a researcher studying those working in the security community. One of the questions was about what threats really keep me up at night. My answer? That someone proves P = NP.
Hmm ... considering Blackberry/RIM's precarious hold on existence, I have a hunch those patents will be in other hands very soon.
Article is dated 8/2 (Friday), yesterday would be the first tradable day on the information.
the NSA had already solved the discrete logarithm problem...
[...] elliptic curve cryptography, something the NSA has said is best practice for years.
...or cracked elliptic curve cryptography.
If Pandora's box is destined to be opened, *I* want to be the one to open it.
Your first sentence sounds weird to me, and it isn't supported by your second. AES can't be a suitable replacement for RSA because AES is a secret-key system and RSA is a public-key one.
I'm not a crypto person, but RSA and elliptic-curve systems are the only two public-key systems I can think of. (There are others that allow secure exchange of a secret key, but that's different.)
Why elliptic curves when we can go back to good old fashioned original RSA that uses prime number factoring as the problem? No patent nonsense to worry about there.
Maybe it might be time for an algorithm challenge, similar to how AES got decided, and the lastest hash algorithm got chosen.
Of course, asymmetric algorithms are a lot harder to make that are secure than symmetric ones.
I wonder about, instead of naming one, naming three. That way, if in the future one gets compromised, the broken one would just not be used, or for very sensitive stuff, all three can be cascaded (not for bit length, but to keep things signed or encrypted in case one gets severely weakened.)
Ed25519 by Dan Bernstein solves the patent issue and offers efficient and simple implementations.
You need upvotes, but I'm out of modpoints.
You are very correct. Take for instance OpenVPN. It uses RSA to exchange an random AES session key. RSA and AES/DES/3DES have different uses, and replacing RSA with AES is simply not possible.
You can't patent math.
The interesting thing is that I think TFA confuses DSA with RSA. DSA would be useless if the discrete logarithm was solved but is not really threatened by quantum computers. RSA is relatively fine with this development because their major weakness is integer factorization, but would be hosed by quantum computers.
Without a statement as to whether the NSA has been involved in elliptic curve stuff (though I will point out that they have nearly as much motivation to make things hard for, say, the USSR/China [depending on era] to crack as they do to make things easy for them to crack), did you read your link? It isn't really talking about elliptic curve crypto at all.
It's describing a potential flaw in a random-number generator whose algorithm is based around elliptic curve crypto. Even if every worry presented by the article is true, that means absolutely nothing about whether elliptic curve is secure against the NSA.
(Actually it almost suggests that it is, because if EC was breakable then the NSA wouldn't have as much motivation to get a known key into the RNG standard.)
Wow, that is so wrong.
RSA is an asymmetric (aka publick key) cipher - because it requires two keys - one to encrypt, one to decrypt. AES, DES, 3DES are symmetric ciphers because you use the same key to encrypt and decrypt.
RSA and EC (elliptic curve) encryption is useful if you want to send data to someone without the hassles of secretly sharing the key ahead of time - e.g., I can encrypt a message using the public key and only the private key can decrypt it. Or I can use my private key to encrypt a message, and the public key can be used to decrypt it (the latter is often used to sign stuff, except the message is typically a hash instead of the original message).
The reason you use AES, DES, 3DES is because public key encryption is hideously slow. In the case of RSA, you're exponentiating one horrendously large number with other horrendously large numbers. (If your message is long, that horrendously large number Is big).
That's why what every public key encryption thing does is it encrypts the message with a fast symmetric cipher like AES, then encrypts the key (much shorter) with RSA or EC. If I want to send you a document, I encrypt it with AES, then use your public key to encrypt the AES key I used.
It's also why signing uses a hash - it's easier to encrypt the hash than the message. And verification just means recomputing the hash, and then decrypting the encrypted hash with the public key, producing the original hash to which can be compared to the just computed one.
The breakthrough in math would be a way to factor a large number quickly - which is what RSA relies on for security - it's easy to multiply two big numbers, but it's very time consuming to factor it.
There's a fundamental difference between breaking the algorithm mathematically and the key space being too small. People left DES and 3-DES because the key size was too small and a brute force became feasible. The same is becoming true for RSA, but this is completely different than solving the discrete logarithm problem that underpins RSA and Diffie-Hellman. Solving that would be an amazing feat of mathematics. So please stop trying to show off to /. how you're smarter than everyone else.
Wow, that is so wrong.
How is it wrong? He's not referring to the operating principles, only to the fact that RSA and DES are about equally dated. You've just wasted time and space providing him with information he's already had.
Ezekiel 23:20
From what I remember some mathematician had figured out a shorter way to solve the discrete problem and built a black box to do it. The main characters then stole his machine.
Well, there's spam egg sausage and spam, that's not got much spam in it.
Is there someone you think is better qualified?
PlusFive Slashdot reader for Android. Can post comments.
http://arxiv.org/abs/1306.4244
Adam Van Ymeren said it well. An algorithm's age doesn't necessarily speak to how secure it is. DES is considered insecure because it has a fixed key size that can be brute-forced, not because it is a fundamentally weak crypto system.
By contrast, the same objection does not apply to RSA, at least AFAIK: the key size can be scaled arbitrarily, so as computing resources grow so can the difficulty of the problem. I'm not familiar enough with the area to know how the discrete log helps RSA (integer factoring is the usual weakness I associate with that algorithm), but at least what the summary suggests is a fairly fundamental breaking of the algorithm. I didn't read TFA, but possibly key sizes would have to be scaled up prohibitively to remain secure.
DES vs AES is not the same situation at all as RSA vs EC.
They are discrete logs over different groups. Joux's work and related stuff being referred to is for (Z/nZ)*, that is the discrete log over the group of units under in the integers modulo n. That problem is of course, closely connected to prime factorization. In contrast, ECC uses the discrete log over elliptic curve groups, which are also abelian groups but as of yet do not have any similar sort of breakthrough. In fact, this isn't a new situation. Discrete log has been harder over elliptic curves than over (Z/nZ)* since the mid 1990s. It is however worth noting one potential vulnerability that both share: any form of discrete log is efficiently solveable on quantum computer. So if one is thinking in the really long-term then ECC doesn't look much better.
Your first sentence sounds weird to me, and it isn't supported by your second. AES can't be a suitable replacement for RSA because AES is a secret-key system and RSA is a public-key one.
Sigh. We're discussing an encryption algorithm that is aging and was designed to run under limited computational resources... and now that resources have increased many-fold since the original, it is no longer secure. I then compared it to other encryption schemes that are less resource-constrained which have been coming into wider use. I said nothing about key exchange systems or anything else... I was making a general comment about encryption schemes; Your confusion is because you are drawing your own conclusions, rather than staying on point: Which is that every encryption algorithm, regardless of type or usage-scenario, has a shelf life.
#fuckbeta #iamslashdot #dicemustdie
Discrete log has been believed to almost certainly not be NP-complete since well before this. We have much better than exponential time algorithms for discrete log so it would contradict the exponential time hypothesis for it to be NP complete http://en.wikipedia.org/wiki/Exponential_time_hypothesis . Second, discrete log is closely related to factoring which llives in NP intersect co-NP. Since factoring lives in that intersection, if factoring is NP complete then then the polynomial hierarchy would collapse http://en.wikipedia.org/wiki/Polynomial_hierarchy which is largely believed to not be the case.
AES can't be a suitable replacement for RSA
True, but he isn't making any such claim.
Ezekiel 23:20
Maybe this will finally spur the abolishment of software patents.
Patents have now become an issue of national security.
The thing I'm not sure about right now is whether the RSA method itself is becoming insecure or if standard-size keys can simply be brute-forced. If it's a question of key size, then why not use larger keys?
The last time I checked, it is possible to increase the size of RSA keys quite a bit. Most frontends for PGP/GPG only allow keys up to 4096-bit to be created but several years ago I was able to generate valid key pairs up to 11296-bit. I had to modify the GPG source code and recompile it before it would let me create oversize keys but my 11296-bit key is still compatible with stock GPG.
"It is a denial of justice not to stretch out a helping hand to the fallen; that is the common right of humanity."
Sigh. AES requires less resources to implement than DES (in software, anyway). It also happens that it is more secure due to better design and longer keylength (possibly it is less secure than 3DES, that is open to debate).
The real reason we have replaced DES with AES (and RC4) is neither because resources are constrained or because DES is broken (it's not), it is because the key length is only 56-bit, so while it is secure from a cryptographic standpoint, it can be bruteforced (expensively) and is insecure from a practical standpoint (when dealing with a commited adversary).
That both AES and RC4 (which is kind of insecure in design, but most widely used in SSL) are much faster than DES is also a huge advantage when you are using them for bulk encyrption as they are used in SSL and OpenSSH.
Deprecated - I don't think that word means what you think it means. RSA can't be deprecated when there isn't a replacement. Elliptic curve cryptography has only really become a realistic replacement fairly recently, and nobody outside of government rushed to give Blackberry lots of money to use it because there wasn't a compelling reason to do so. Governments DID, which suggests to the conspiracy theorist that they might know of such a reason.
It's been long recommended you don't use short keys with RSA (which were used in the past for speed) but the algorithm itself is secure (as far as we know), no matter how much hardware you throw at it. This story is about the possibility of a mathematical advance (note, the possibility, it hasn't happened yet) that could make the RSA algorithm itself insecure, for any key length.
A breakthrough in solving the discrete logarithm problem would be a big deal. It could also very well lead to breakthroughs in integer factorisation.
You still can't replace an outdated public-key encryption key system with a symmetric system. Because, in real life, usage scenarios and key exchange systems actually matter - in fact, they are the most crucial aspect of the whole thing, otherwise we'd use true random one-time pads and be safe from any attack with any level of computing power forever.
Forget magic. Any technology distinguishable from divine power is insufficiently advanced.
I didn't say that you said that AES could replace RSA: I said that your AES/DES analogy didn't support your statement that RSA is or should be deprecated. That may sound like I'm nitpicking here, but I'm really not: it's pretty fundamental to my point. And the reason is this:
This absolutely need not be true. RSA for instance is based in part around a hardness assumption: that given a very large number n which is the product of p and q, it is far harder to find p and q from n then it is to find n from p and q. Assume for the sake of argument that this is the only hardness assumption RSA depends on. (If the summary isn't misleading it apparently also depends on the hardness of discrete log, but I don't know how.)
If the hardness assumption holds, then RSA as such will never be insecure. Why? Suppose you say "here is a computer capable of factoring a number n with b bits." I'll say "OK, fine; I'll use 100*b bits (or something)"; because multiplying is so much easier than factoring, your computer will still be able to carry out that task but it won't be able to crack my key.
In other words, if the hardness assumption holds, RSA doesn't have a specific difficulty: it can scale with computational power. That's why you see people using 2048-bit keys now instead of 512-bit keys a couple of decades ago.
The only things that the age of the algorithm has to say about the security of it is (1) if the difficulty cannot scale with computational power (true of DES, not true of RSA) and (2) being out longer gives people more time to find flaws in its assumptions.
But here's the thing: #2 isn't necessarily bad or speak against the algorithm. It is conceivable that the assumptions just fundamentally hold. If they do, being out longer will not impact the security at all. If anything, being out longer with no one discovering anything should give a higher assurance that an algorithm is secure than a newer one would.
I don't think I've ever heard a blanket statement about RSA being insecure -- only things like certain key sizes or certain implementations or PRNGs being insecure. (Wikipedia also lists a couple of side-channel and plain-text attacks, but those are also arguably quality-of-implementation issues, and similar attacks exist for EC systems.) The intro to the Wikipedia article says nothing about RSA being insecure. "Deprecated" and "discouraged" both fail to appear on the page.
The strongest statement against RSA I've heard is just that EC is better.
Except that the DES vs AES case is not even close to being the same case, as Adam Van Ymeren said in response to you, and then I elaborated on elsewhere and above.
The reason it's not even close is that DES does not scale with computational power, because it has a fixed key size.
I'm surprised to see other people going in the direction I've been going for about 3 years now. Really. I thought I was quite alone in my path, LOL.
I need to read this paper still, but if it's taking the same path I did, then it's not a peachy as some think.
I'm only am amateur, so take this from the point of view as someone who kicks back with a beer and enjoys solving impossible computational problems.
I don't think it's that close to being broken... I think it'll take a huge computing effort (think multi-terabyte databases) to generate the tables across the PQ space required so that existing problems can be used to quickly find paths and intersections. At the beginning you're looking at only a VERY SMALL speedup from modern sieving, but once the tables get generated (years of effort) you'll eventually see faster and faster improvements. At least, that's with my algorithm, which I'm sure is far from perfect and only works on a certain set of primes right now. Which is about 20%. Which is far from optimal.
So yeah, progress. But I'm unconvinced that this will work for all primes.
I'm going to read the paper now... which I'm sure is far better than what I've been doing.
I said no... but I missed and it came out yes.
The story is talking about the possibility of a mathematical breakthrough that would make solving the discrete logarithm problem (and possibly the integer factorisation problem) much, much easier. RSA relies on it being much easier to raise something to an integer power than to find a discrete logarithm (inverse operations). If you figure out how to make the two operations of similar difficulty then any encryption scheme based on them is hopelessly broken for any key size.
There does not appear to exist any single piece of evidence that DLP (discrete logarithm problem)
will benefit from algorithms running in polynomial time. The recent work of Antoine Joux that they
are referring to (one of which I assume to be http://arxiv.org/pdf/1306.4244v1.pdf) provides
improvements of quasi-polynomial agorithms for breaking DLP. But there is no reason to believe
that these improvements can lead to a polynomial-time attack. And as long as this does not happen,
those attacks can still be defeated by increasing the key size.
If it's a question of key size, then why not use larger keys? The last time I checked, it is possible to increase the size of RSA keys quite a bit.
Because large RSA keys do unfortunate things to performance. You double the key length, and it takes 6-7 times longer to run the decryption.
upon the advice of my lawyer, i have no sig at this time
(if you can get a trusted version with no 'escrow' technology built in, that is)
As I recall, the guys who wrote PGP back in the day almost went to prison for publishing the source code - despite the fact that the RSA algorithm in use was already publicly documented (in Scientific American IIRC). "The Powers that Be" learned from that debacle and have far more reliable mechanisms for gaining access to everything you do in the clear if they want it (for example, the TCM in my new HP PC is turned on and enforcing - I can turn it off, but what other little goodies have manufacturers hidden in the firmware for me to discover?).
Moral of the story - IPv4 is exhausted, go to IPv6. BIND4 is obsolete, go to BIND8. NFS is dated and insecure, go to NFSv4. RSA is at risk of being compromised by advances in mathematics, go to [something better]. Really - is cryptography supposed to be carved in stone? I know that worked for the Egyptians, but anything related to the technology field...
1 + 1 = 3
This is a correct answer. Do you know why?
The mind conceives, the body achieves, the spirit manifests.
More to the point, how the FUCK does one weasel a patent on crypto (which is just math, and therefore, unpatentable) through the system? I would think the USPO would just round file anything coming in that has to do with crypto on general principle...
HA! I just wasted some of your bandwidth with a frivolous sig!
wait, what?
CLI paste? paste.pr0.tips!
Algorithms for either can normally be converted to do the other. If either falls, the other is likely not far behind.
Ffunction ption, fine. For signatures and hashes, cascading WRAKENS it. An attacker only has to crack ANY of the algorithms to crack the whole. To prove that to yourself, try it with one of the algorithms defined as:
function Weak(msg) {
return 1;
}
Compare these two:
Weak(MD5(msg))
MD5(msg)
For encryption, that's fine. For signatures and hashes, cascading WEAKENS it. An attacker only has to crack ANY of the algorithms to crack the whole. To prove that to yourself, try it with one of the algorithms defined as:
function Weak(msg) {
return 1;
}
Compare these two:
Weak(MD5(msg))
MD5(msg)
Correct me if I'm wrong but you are not allowed to patent mathematical processes. "Elliptic curve cryptography" sure sounds like a "mathematical process" to me and a pack of especially smart and vicious patent lawyers should be able to blast RIM and Blackberry away in short order (by patent litigation standards which is aeons long). Sounds like a job for Amazon whose entire business model, the one they make money on anyway, depends upon the integrity of SSL which depends upon Diffie-Hellman and RSA for key exchange, if my flawed memory serves. Gotta blow the dust off my SSL book....
It's really quite a simple choice: Life, Death, or Los Angeles.
Send Robert Redford and Sidney Poitier out to steal whatever device Joux is using to help solve these algorithms, before the mafia does.
It's not only the key, which is too small. The blocksize is also too small. DES has a blocksize of only 64 bits. Even the 128 bit blocksize of AES is a bit on the short side. My rule of thumb for how many blocks of data you can safely encrypt with with a single key is two raised to one quarter of the blocksize. If the blocksize is 64 bits, that gives you 512KB, if the blocksize is 128 bits you can go all the way to 64GB. With typical full disk encryption schemes using a single AES key for an entire harddisk, which could be a few TB in size, I think this is something to be concerned about.
It is just a rule of thumb though. It is not like something happens as you cross that boundary. Whether you encrypt 63GB or 65GB with a single AES key doesn't make much of a difference in terms of security. The more data you encrypt with the same key, the larger the risk of collisions is. A collision is when you by chance encrypt the same input block twice, and when does happen the cipher blocks will be identical and leak information about the collision having happened. When you reach 64GB, the probability of such a collision is about 1 in 2^64. Having that probability go any higher than that is unreasonable for a 128 bit cipher, which is why I use the rule of thumb, that I do use.
If somebody were to encrypt all the information in the world using just a single AES key, it is not unlikely that the probability of a collision would be more than 50%.
Oh, and 10DES is not something, which would be used by anybody, who knows what they are doing. The number of times you use DES needs to be an odd number. The actual security is equivalent to the number of usages of DES divided by two and rounded up. That means 2DES is no more secure than DES, and 10DES is no more secure than 9DES. So you'd go with either 9DES or 11DES. Moreover you can replace every other DES with a simple XOR with a constant with almost no loss of security, you might even gain a little bit of security that way due the XOR using 64 bit of key material but a DES operation using only 56 bits.
So rather than using 10DES (with an actual keysize of 560 bits and an effective keysize of 280 bits) you could alternate between XOR and DES such that you have 6 rounds of XOR and 5 rounds of DES (with an actual keysize of 664 and an effective keysize of 360 bits). This approach with 6 rounds of XOR and 5 rounds of DES is almost twice as fast as 10DES and to the best of my knowledge also more secure.
Do you care about the security of your wireless mouse?
That's a common misconception. The actual law is:
You cannot patent the laws of nature, including the laws of physics and mathematics.
A car MAKES USE of the laws of physics, but it may be patentable if it's a new invention. You cannot patent X + 1 = X - (-1) because that's mathematical truth, it existed before you noticed it. Just as you can patent a new invention that USES the laws of physics, you can patent some system that uses math. In this case, a system for securely delivering secret messages across a public network. Of course it still has to be a new and useful invention in order to be patentable.
“Our conclusion is there is a small but definite chance that RSA and classic Diffie-Hellman will not be usable for encryption purposes in four to five years,” said Stamos
Laymen terms: There is a small, but non-zero probability that an asteroid will collide into the earth and destroy civilization in the next 4 or 5 years
My thought: There is a non-zero probability of INSERT_UNLIKELY_EVENT happening in the next 4 or 5 years. Should we panic? Nah. That is called life... There are no guarantees. If we worried about unlikely events happening...we'd be in a state of paranoia, fear, and constant worry of the next catastrophe. Oh wait....wrong thread.
That article gives no reason to be worried about elliptical curves. What it does give reason to be worried about is magical constants and the use of asymmetrical primitives for something that can be done with symmetrical primitives. The concern about the magical constants is why some algorithms use digits of e or pi for the constants. And since random number generators can be build using symmetrical primitives, it is suspicious when somebody choose to use asymmetrical primitives. That later decision need to be accompanied by a new formal security definition and a proof that such security definition cannot be achieved using symmetrical primities.
The combination of asymmetrical primitives where none are needed and magical constants of unknown origin is extremely suspicious. Even if you cannot prove it to be the case, it seems very likely that those magical constants are in fact a public key, and somebody knows the corresponding secret key.
Which asymmetrical primitive they chose for the construction is of no importance to the story though.
Do you care about the security of your wireless mouse?
I thought the bulk of encryption was usually done with some streaming cipher.
Yes, we need to check everything. That being said, this feels like game theory. Don't you get the sense that the NSA wants us to doubt the technology. If cryptography was widely used most of what the NSA does would be made obsolete.
There is another promising public key encryption method known as NTRUEncrypt (http://en.wikipedia.org/wiki/NTRUEncrypt). It's lattice based, and apparently it will still be effective in a post quantum computing world where RSA/Elliptic curve methods will fail.
I use Certicom's ECC Libraries everyday mostly for ECMQV (key agreement with user authentication) and also signatures. They charge nothing or almost nothing for the use of their patents in some industries. They do charge for their libraries and acting as a CA. For embedded devices with limited resources and bandwidth I can do things that are simply in-feasible with RSA. Certicom's math is beautiful. The curves that they chose and the neat properties they have make it possible to perform asymmetric encryption on devices with tiny amounts of RAM. I hate patents but I have no moral objection to paying Black Berry for what they provide.
> Unfortunately, key patents for implementing elliptic curve cryptography are controlled by BlackBerry.
"Who's gonna go broke now, bitches?!?!?"
(-1: Post disagrees with my already-settled worldview) is not a valid mod option.
By its very nature, encryption is a never-ending arms race.
The RSA encryption is
c = m^e (mod n), where m is message, c is ciphertext, e is public exponent, and n is p*q
Decryption is
m = c^d (mod n) where d is the private exponent.
The process of computing d given m,n and c is exactly the discrete logarithm problem. Given n and e, which are public, you can pick an arbitrary m and generate a corresponding c.
I haven't read the patents, but not necessarily. I can't patent gears Just because a system is made up of gears, doesn't mean the system as a whole isn't patentable. Similarly, just because the software includes logic operations and equations doesn't mean the system isn't a new invention and patentable.
A new configuration of gears and levers, doing something new, is patentable.
A new configuration of logic operations, equations and and interfaces, doing something new, is patentable.
The question is "is it a new invention"? There's no distinction in law or in common sense between hardware and software. Either it's a new invention or not. Mathematical TRUTHS aren't new inventions just as facts about physics aren't new inventions. Someone might have DISCOVERED them, but they didn't invent them.
On the other hand, a device with 10,000 gears may well be a new invention. So too, a device made of 10,000 lines of code may be a new invention.
In fifteen years of programming, largely R&D, I've come up with one, maybe two completely new solutions to old problems which are significant. One replaces CAPTCHAS with something that testers have had no problem using from ten feet away. A legally blind customer uses it on his site. I believe the law is correct in considering this a new invention.
IEEE Std 1363a defines a method to to Elliptic Curve Crypto that is not patent encumbered.
ipv6 is my vpn
What you have described is true when both parties hold the relevant keys, and they believe that the keys have not been compromised - this is when I can trust that I really have your public key and not one substituted by an adversary. To solve this problem of key distribution the DH key exchange algorithm is normally used, and this relies on the hardness of discrete logs. If the DH problem is weak (which now appears to be the case) then RSA would be borken in the sense that you could not exchange keys to use it.
Slashdot: where don knuth is an idiot because he cant grasp the awesome power of php
I have been reading his papers for some time now, and the guy is definitely making progress. Recent work, however, in the field of multilinear maps seems to point into a new direction: multiparty Diffie-Hellman agreement. That would be a lot harder to break. Basically, in such a scheme, when wanting or needing to establish a classical Diffie-Hellman agreement, you'd invite a trusted third party in. Eventually, that scheme may get broken, too; yet, it may grant implementors and users another 10-to-20-year truce. As for TFA on technologyreview.com, it sounds a bit like fear-mongering, to my taste.
Religous speak to God. Insane are spoken to by God. When all shut up, one can finally hear Shostakovich in peace
The value of the counter is not expected to be secret. Additionally, I don't think CTR mode is suitable for full disk encryption (which tend to be the case where the largest amount of data is encrypted using a single key).
A more accurate way to state it is, that it is advances in computing power that created a need for AES. Today we have so much computing power, that DES can be broken by brute force, so we need something stronger.
As far as I know there has never been found an attack faster than brute force against DES. A weakness has been found in an earlier version of the cipher, but NSA provided a fix for this weakness before the DES standard was finalized. It is unclear how much NSA understood about the weakness before they provided the fix. Nothing was published about the weakness at the time, it was discovered independently many years later.
Do you care about the security of your wireless mouse?
Adam Van Ymeren said it well [slashdot.org]. An algorithm's age doesn't necessarily speak to how secure it is.
I'm aware of that, but that's hardly relevant here. When girlintraining said "A" ("RSA merely being old is sufficient to make it broken"), tlhIngan said "no, B is wrong" (B being an entirely different set of claims, probably something like "RSA should be replaced by AES" - which, of course, she DIDN'T claim but which seems to be the way in which tlhIngan misunderstood it).
That fact that girlintraining's A can *still* be wrong doesn't mean that tlhIngan's riposte, addressing a completely different issue, isn't still misplaced. (It's amusing how you've just managed to completely ignore the point of my comment in *exactly* the same way that tlhIngan ignored girlintraining's comment. What's happening to reading comprehension these days?)
Ezekiel 23:20
No, what it shows is that the NSA is sneaky. "I don't understand why the NSA was so insistent about including Dual_EC_DRBG in the standard." Because it's a distraction. It has a visible flaw and thus draws attention away from the other methods in the standard which presumably have other, more subtle flaws.
Altough the real lesson is to not use a weapon supplied by your enemy to fight him.
Forget magic. Any technology distinguishable from divine power is insufficiently advanced.
I suspect we're talking past each other a bit. :-) Here's my interpretation:
tlhlngan said "Wow, [girlintraining's post] is so wrong", and you responded to tlhlngan by saying "How is it wrong?". And while "wrong" was the arguably the wrong word to use on tlhlngan's part, the DES/AES comparison by girlintraining was irrelevant.
However, and here is where I think I may have made a jump (perhaps justified, perhaps not), while girlintraining's statement about DES/AES wasn't wrong if taken completely literally, it did reflect a misunderstanding on girlintraining's part (unless I yet have something to learn). And in that sense, I think "wrong" is a perfectly fine word for tlhlngan to have used. (I didn't know what that misunderstanding was at the point of tlhlngan's post, but I felt it was reasonably clear there was one.)
So when you asked "why's it wrong", I answered the question I interpreted it as -- but not what you asked. :-)
For keys that need to be 'safe up to 10 years away, recommend a minimum RSA key size of 16,384 bits.
I said from the beginning... the recent move of MS to require a minimum of 2048 bits is too little too late -- we need an order of magnitude increase in RSA key lengths to keep RSA as secure as it was 10 years ago.
Even an 'efficient' algorithm for attacking the problem is likely to have certain resource constraints.
Sorry, but this is just wrong.
The whole point of public key encryption is that you don't need to do a key exchange. You have the public key, which is, well, public. The problem then becomes trusting you have the correct public key. Signatures provided by some other trusted party are used for this, usually in certificates. There still needs to be some per-established trusted root or web of trust to enable this. Identity-based public key encryption even does away with the need for this, allowing the generation of arbitrary public keys for someone (although there are other security issues with this sort of encryption scheme which I won't go into here).
Diffie Hellman key exchange is unauthenticated and completely vulnerable to a man in the middle attack. It is used to create a shared secret between two parties, which becomes a shared key, usually for symmetric encryption. It's very old now but still amazingly cool - I love the somewhat counter-intuitive fact that two parties can create a shared secret amongst themselves using only public communications. As long as you accept that neither party has any idea at all who they are creating the shared secret with.
[citation needed]
Wrong. The reason you don't see that is because the performance sucks, and because nobody really saw the need to increase the keysize even further, when the blocksize remained the same.
That's why you would alternate between DES and XOR. Using this method with two rounds of XOR and one round of DES is standardized. I don't know if it has been used with more rounds.
Do you care about the security of your wireless mouse?
Whoops, was working from memory and it has been a looong time. DH key exchange is indeed completely different to what I said above - as you've said it is an alternative way to set up a secret channel. Certifying trust on a public key is indeed the important issue, and solved in a different way.
I'm guessing the alternative issues on IBE are the need to trust the CA, which puts it roughly in the same level of messiness as using digital signatures on public keys anyway. Is that Matt Palmer at the National Archive?
Slashdot: where don knuth is an idiot because he cant grasp the awesome power of php
Easy to confuse all this crypto stuff! I work with it regularly and still have to look quite basic stuff up if I haven't touched it for a while! Yes, I am that Matt Palmer, but no longer at the National Archives...I'm now doing contract security architecture for a consultancy.
The issues on IBE are kind of like trusting a CA, except there are no certificates and therefore no CA. There is a very powerful trusted party who can decrypt anyone's information. The way it works is, there are some all powerful master secrets, from which some public parameters are generated.
Anyone with the public parameters can generate a new public key for anyone (e.g. using your email address as the public key) and encrypt a message for you. The issue is that to decrypt the message, you have to ask the trusted party for a valid private key for that public key, which it can automatically generate for you given knowledge of the public key, using the master secrets.
One security issue of this system is how does the trusted party authenticate that you really are who you claim to be, and how does it distribute that private key to you. Another, possibly more serious objection, is that the trusted party can fundamentally generate private keys for anyone using their parameters, so they can decrypt everyone's data. You have to *really* trust that trusted party.
The only place I've seen IBE commercially used is by Voltage Security. One use case is to allow payment terminals to automatically generate a new public key for each payment. Since the payment provider is supposed to be able to decrypt all of these communications (they are the trusted party), then this works quite nicely.
Public key encryption requires trap door functions. We can't even prove they exist. Most people believe they exist. If you can prove they do exist then you also prove that NP!=P. But proving NP!=P does not imply the existence of trap door functions.
So what this means is we try and find trap door functions. Things that appear to be easy if you have some piece of information, but really hard if you don't. There have been such functions suggested in the past that proved to be easy in both directions in the end (knapsack problems for example).
TL;DR Its much harder to find practical public key methods than symmetrical key ones.
If information wants to be free, why does my internet connection cost so much?
This article and http://threatpost.com/crypto-gains-ramp-up-calls-to-get-ahead-of-inevitable-rsa-algorithm-downfall/101560 both imply that we need to jump to ECC and get off of RSA. Since there are direct quotes from Mr. Stamos in one of these articles, it sounds like he is the source of the confusion. Actually the recent advances weaken ECC more than RSA, and RSA is only weakened if the discrete log advances are followed by similar advances in factoring. There is no known theoretical reason for this to be guaranteed to happen, but folklore shows that it has indeed happened in the past: discrete log breakthroughs are intertwined with factoring breakthroughs, but there are only vague handwaving explanations about why this should be true.
So the problem is that RSA may well break soon, but ECC is already to some extent broken by Joux et al. Any advice to throw out RSA in favor of ECC seems wrong to me. What you really need is a totally new potentially hard problem to base new crypto algorithms on, and you maybe only have months to come up with the idea, and then only a few years to get the idea into practice, or else it's a return to snailmail if we haven't completely dismantled it before then.
See http://www.treefrogenterprises.com/research/funwithecc.html for more.
Keeping information about cryptographic designs secret, when it should be public, is in no way unique to NSA. Secrecy does not prove malicious intent, it does not prove incompetence, it does not prove presence of backdoors or vulnerabilities. NSA contributed to DES. The reasoning behind this contribution was kept secret. It took many years before somebody else figured out which security bug in the original design was fixed by the contribution from NSA.
Do you care about the security of your wireless mouse?
Under a chosen plain text attack, an attacker would know m.
IEEE Std 1363a defines a method to to Elliptic Curve Crypto that is not patent encumbered.
I don't think what is patented in the TSA is the method, but its implementation (quote below).
Implementations of ECC were pioneered and patented by a company called Certicom that is now a subsidiary of the phone manufacturer BlackBerry.
So my question is that is there only ONE implementation for the algorithm???
Opps, TFA, not TSA...
The whole thing is unsubstantiated FUD. I base my judgment on the slides at
https://media.blackhat.com/us-13/us-13-Stamos-The-Factoring-Dead.pdf
The whole argument boils down to:
a) there has recently been huge progress [*] in solving the Discrete Log Problem over fields of small characteristic;
b) progress in solving the DLP have historically implied progress in factorization, and vice versa;
c) factorization breaks RSA, and solving the DLP breaks DSA;
d) thus RSA and DSA are dead, move to ECDSA.
The fallacy of it is that in b) and c), the DLP is exclusively over fields of huge characteristics (thousands of bits), making the algorithms in a) powerless. The slides do not hint at the faintest research lead towards moving to huge characteristics. Best argument is that "renewed interest could result in further improvements".
One the positive side, the author is honest: "I’m not a mathematician, I just play one on stage".
François Grieu
[*] See e.g. this recent paper and its references
Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, Emmanuel Thomé: A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
http://hal.inria.fr/docs/00/83/54/46/PDF/quasi.pdf
outside of a few remnants like poems and rhymes, we don't speak or write old or middle english any more.
in any case:
poets have always felt free
to play with words in ways slightly odd
as even a young child could see
so bugger off ya curmudgeonly old sod
RSA for instance is based in part around a hardness assumption: that given a very large number n which is the product of p and q, it is far harder to find p and q from n then it is to find n from p and q. Assume for the sake of argument that this is the only hardness assumption RSA depends on. (If the summary isn't misleading it apparently also depends on the hardness of discrete log, but I don't know how.)
In RSA you get the public key e based on your n (and the totient of n). After that you encrypt a message m into cyphertext c using your public key e by performing c = m^e (mod n). In addition, to decrypt the cyphertext using a private key d (which is the multiplicative inverse of e mod the totient of n), you perform m = c^d (mod n). RSA assumes that given c and m, it's still pretty hard to find e or d. Otherwise, given the public key, you can figure out the private key by encrypting a message with the public key and performing the discrete log.
Warning: Opinions known to be heavily biased.
You are correct, comparing AES to RSA is like comparing GPUs to CPUs and claiming one is better than the other. They solve different problems.
Good point; There are implementation techniques and specific curves which are patented and it is possible to make an implementation that is not patented. For example: http://dnscurve.org/crypto.html
ipv6 is my vpn
https://en.wikipedia.org/wiki/RSA_encryption
p and q are the starter prime numbers that the person using RSA picks. n = p*q, and its bit length is your RSA key length. e is some number that is relatively prime to (p - 1)(q - 1). d is picked so that de = 1 mod (p-1)(q-1). Your public RSA key becomes the pair e and n. The others: p, q, (p - 1)(q -1), and d remain private.
It would ruin it as an encryption method because an attacker could use their own m, use the public e and n, and thus obtain their own c without intercepting anyone else's encrypted traffic. Then they can calculate d, and can decrypt anything encrypted using e and n.
Also see: http://tools.ietf.org/html/rfc6090
9. Intellectual Property
Concerns about intellectual property have slowed the adoption of ECC
because a number of optimizations and specialized algorithms have
been patented in recent years.
All of the normative references for ECDH (as defined in Section 4)
were published during or before 1989, and those for KT-I were
published during or before May 1994. All of the normative text for
these algorithms is based solely on their respective references.
ipv6 is my vpn
You do know that RSA has a size parameter, do you? And that without a mathematical breakthrough in prime factorization, engineering advances can easily be completely nullified by just increasing said size parameter? This is not a block-cipher, that as tome time becomes insecure due to faster computers, something far more fundamental is needed to break RSA.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
ALL cryptography depends on P != NP. For any usable cipher, deciphering is going to be in P. This means that breaking it with known plaintext is in NP. (The argument is somewhat hairier for unknown plaintext, but you can do NP things that will almost certainly crack the cipher.) If it's possible to solve all NP problems efficiently, it's possible to break any cipher efficiently.
"When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
Many people in industry are thinking that we need to be very careful in the near-future when using public-key cryptography. A catastrophic event is a possibility. See the next month workshop about catastrophic events related to cryptography and their possible solutions: CATACRYPT ( http://catacrypt.org/ ) near London. You're welcome to participate. With a committee where a lot of very important contributors. This talk at Black Hat this summer is thus very interesting. It was anticipated by a talk at CCC in Berlin in December 2011, see 28th Chaos Communication Congress (28C3), Berlin, 29 December 2011: talk by Renaud Devalière and Jean-Jacques Quisquater, in cooperation with David Samyde, The future of cryptology: which 3 letters algorithm(s) could be our Titanic? RMS Olympic, RMS Titanic, HMHS Britannic vs Discrete Logarithm, Integer factorization, Conjectured hard problems: talk is at http://www.youtube.com/watch?v=t4n7yUBtTt0 There was also a high-level workshop this year in January in Menlo Park about the end of RSA. The slides are here: http://catacrypt.org/rsa-isat-brief%20-%20Public.pdf with permission.
...and allow us to acquire the solution in a dramatically more efficient manner!
Now, I should emphasize that such an approach is purely theoretical. So far, no one has been able to accomplish such constructions, yet..
You could probably adjust your definition of "function" and "algorithm" to claim they are the same thing. Neither of those is a term used in the relevant law, so it's beside the point.
...". One might very well use some math in a particular build of the invention. The invention, the new way of blocking spambots, isn't a mathematical law any more than a new design for a mouse trap is a law of physics.
The terms used in the law are "laws of nature" and "useful invention"
Suppose I develop something using the human ability to recognize music which works much better than CAPTCHA. That might well be a new invention, depending on the details. "music is better than captcha" is NOT a mathematical fact. The laws of math make no statements on the subject of "the best way to tell a human from a computer is
This is incorrect. Its easy to prove in the case of a one time pad. If you don't have the key, then all possible messages are valid plain texts, there is no way N=NP can help you tell which one is correct. Symmetric key systems do not require N!=NP, they rely on the fact that there is a "secret function". Without knowledge of that function (ie the key), you cannot invert that function.
If information wants to be free, why does my internet connection cost so much?
In fifteen years of programming, largely R&D, I've come up with one, maybe two completely new solutions to old problems which are significant. One replaces CAPTCHAS with something that testers have had no problem using from ten feet away. A legally blind customer uses it on his site. I believe the law is correct in considering this a new invention.
Your thing might be a valid invention under USPO rules. It is an application of something, and quite likely not even directly tied to any encryption algorithm. Software patents are complete bullshit too, IMHO, since you aren't releasing source code in your patent application, and aren't really sharing you work with the world at large as intended. but that is neither here nor there since there is (quite strangely) no mention of software patents in anything laid down by the founding fathers.
I was speaking about elliptical curve encryption, and any sort of claim that blackberry could make about it. An encryption algorithm is math, pretty much as pure as it gets. That sort of thing should not ever be patentable. Not under software patents, not as bullshit 'business process' patents, not as anything.
HA! I just wasted some of your bandwidth with a frivolous sig!
Assume for the sake of argument that this is the only hardness assumption RSA depends on. (If the summary isn't misleading it apparently also depends on the hardness of discrete log, but I don't know how.)
The hardness of RSA ONLY hinges on the hardness of discrete log, as the discrete log is the inverse function of RSA encryption. The dependence on the hardness of factorization follows from this.
The neat thing about RSA is that the discrete log becomes very easy if you know the factorization of the divisor, so figuring out a way to factor large numbers puts you on (nearly?) equal footing with the person constructing the keys.
Sure. The first such class is called EXPTIME-complete.
And you never knew until MIT rediscovered it.
If the hardness assumption holds, then RSA as such will never be insecure. Why? Suppose you say "here is a computer capable of factoring a number n with b bits." I'll say "OK, fine; I'll use 100*b bits (or something)"; because multiplying is so much easier than factoring, your computer will still be able to carry out that task but it won't be able to crack my key.
Except for the reason that we aren't using 100*b bits today, which is that the whole encryption/decryption process (not just the multiplication, which is trivial) also gets a lot slower. You want to be able to access your online bank securely on your cell phone in a very performance, power and time-constrained environment while it still being secure against someone who could throw a botnet or beowulf cluster or rack of custom ASICs at it for a long period of time. Your phone has to do the math every time, while they can pick one in thousand key exchanges to crack. In short, the practical security of RSA depends on there being a massive difference in difficulty so you can use it trivially while withstanding the most committed of adversaries. If 1 second encrypting = 1 year decrypting on a supercomputer, is it then secure? How long would you wait to log in to your bank?
Live today, because you never know what tomorrow brings