Could Randomness Theory Hold Key To Internet Security? (cornell.edu) 50
"In a new paper, Cornell Tech researchers identified a problem that holds the key to whether all encryption can be broken — as well as a surprising connection to a mathematical concept that aims to define and measure randomness," according to a news release shared by Slashdot reader bd580slashdot:
"Our result not only shows that cryptography has a natural 'mother' problem, it also shows a deep connection between two quite separate areas of mathematics and computer science — cryptography and algorithmic information theory," said Rafael Pass, professor of computer science at Cornell Tech...
Researchers have not been able to prove the existence of a one-way function. The most well-known candidate — which is also the basis of the most commonly used encryption schemes on the internet — relies on integer factorization. It's easy to multiply two random prime numbers — for instance, 23 and 47 — but significantly harder to find those two factors if only given their product, 1,081. It is believed that no efficient factoring algorithm exists for large numbers, Pass said, though researchers may not have found the right algorithms yet.
"The central question we're addressing is: Does it exist? Is there some natural problem that characterizes the existence of one-way functions?" he said. "If it does, that's the mother of all problems, and if you have a way to solve that problem, you can break all purported one-way functions. And if you don't know how to solve that problem, you can actually get secure cryptography...."
In the paper, Pass and doctoral student Yanyi Liu showed that if computing time-bounded Kolmogorov Complexity is hard, then one-way functions exist. Although their finding is theoretical, it has potential implications across cryptography, including internet security.
Researchers have not been able to prove the existence of a one-way function. The most well-known candidate — which is also the basis of the most commonly used encryption schemes on the internet — relies on integer factorization. It's easy to multiply two random prime numbers — for instance, 23 and 47 — but significantly harder to find those two factors if only given their product, 1,081. It is believed that no efficient factoring algorithm exists for large numbers, Pass said, though researchers may not have found the right algorithms yet.
"The central question we're addressing is: Does it exist? Is there some natural problem that characterizes the existence of one-way functions?" he said. "If it does, that's the mother of all problems, and if you have a way to solve that problem, you can break all purported one-way functions. And if you don't know how to solve that problem, you can actually get secure cryptography...."
In the paper, Pass and doctoral student Yanyi Liu showed that if computing time-bounded Kolmogorov Complexity is hard, then one-way functions exist. Although their finding is theoretical, it has potential implications across cryptography, including internet security.
Oh, more theories. Great. (Score:2)
Re:Oh, more theories. Great. (Score:4)
Blowfish is symmetric.
Although annoying not saying so, this story applies to asymmetric encryption.
Re: (Score:1, Insightful)
Re: (Score:2)
Blowfish is symmetric.
Although annoying not saying so, this story applies to asymmetric encryption.
Blowfish is encryption, so perhaps the annoying writers should stop using words like "all encryption" then.
Re: (Score:3)
I was incorrect. Skimming the paper, their result applies to a subset of encryption systems excluding public key and things like one time pads.
The "all encryption" is a line from the Cornell press release. Never trust a non-technical summary for technical details.
You don't pay much attention to tech, do you? (Score:5, Informative)
>No one can break this stuff, including the designer
FYI, my 6 year old can come up with a code she can't break. Which is really just another way of saying "write a a math problem you can't solve".
Actually, let's try this. I'll be back in a minute. ... ...
"Seven thousand times a million!"
That problem can't be cracked by its creator.
"The person who can up with it (who thought it was secure) doesn't know how easy it can be broken" is not a valid argument for the strength of an encryption scheme.
The designer of Blowfish, a Slashdotter named Bruce Schneier, does understand Blowfish well enough that he was telling people to stop using it a long time ago because he understood it has certain weaknesses.
> Oh, since I'm not aware of it, it doesn't mean it hasn't already been broken, yeah. Sure. No one can break this stuff
The fact that you apparently didn't read Slashdot, Wired, or even turn on CNN the week that it was broken doesn't mean it didn't happen. It was a big enough story that the popular press pick it up in August 2016; maybe you were gone camping.
The attack is called Sweet32. It's not reduced rounds, it a real world practical attack - and not even hard. It's not a complicated attack. The most immediate problem, the thing we had to fix within a couple days, was site-to-site VPNs using Blowfish. IIS servers offering streams downloads of large files using Blowfish were also something we were looking for. What Sweet32 is all about is that Blowfish is fairly simply to break if you 850 GB of data encrypted with the same key. A site-to-site VPN might provide that in minutes, certainly in hours.
Re: (Score:2)
Sweet32 isn't some sort of magic button that cracks 64bit block ciphers, it requires some effort and some luck and the right conditions.
The advice to stop using potentially vulnerable ciphers is based on concerns that further work might reveal further weaknesses. If you wait until a cipher is fully broken, it's too late.
Sweet32 is different. Why Sweet32 was big news (Score:3)
> The advice to stop using potentially vulnerable ciphers is based on concerns that further work might reveal further weaknesses. If you wait until a cipher is fully broken, it's too late.
That type of thing is why I tell client's ans others that the configured cipher suites should be reviewed every 3-12 months. To stay ahead of developing issues. Sweet32 is not that.
We'll contact customers when a cipher is no longer recommend because it's not as strong as expected. I didn't have to contact customers f
Re: (Score:3)
The part you're missing is that that just retrieves the key for the session you have already been granted. It doesn't get you MY session key. To get MY key, you'll need some of the plaintext (not so hard on a website, more problematic for anything else), and you'll need to get me to transfere enough data without re-keying so you can spot a collision (good luck!).
A good enough reason to switch ciphers if there's a better one out there (there are), but not a reason to fear that your past sessions may have bee
Re: (Score:2)
> you'll need to get me to transfere enough data without re-keying so you can spot a collision (good luck!).
That's what the JavaScript loop is for, to cause your browser to do lots of requests. And again, that's why site-to-site VPNs were the immediate, "can't leave the office today until it's fixed", problem. Because VPNs transfer a lot of data quickly, sometimes quickly enough that Sweet32 can be done in a few minutes.
> The part you're missing is that that just retrieves the key for the session yo
Re: (Score:2)
But you have to get the javascript into the page I'm reading. If you break in to the server to do that, you don't need to crack the crypto, you already control the endpoint. The VPN situation can be a problem if the VPN didn't follow best practices with periodic re-keying using asymetric crypto for key exchange.
Re: (Score:2)
That's about right. Certain popular VPN software didn't re-key.
Of course something to keep in mind is a general thing about security that many people don't realize or forget:
They see an issue that let's an attacker run JavaScript in a sandbox and they think "no big deal, it's sandboxed".
They see a site (which is most sites nowadays) that sends the password clear text rather than a hash, but it's no big deal because it's within a TLS session.
Each or these seems like not that big of a deal. Together, they le
Re: (Score:2)
Wake me up when someone comes up with something real, not more BS theories.
Well, the theory is not BS, but it is theory. It has absolutely no practical impact at this time. What is completely BS is the headline and the article styling this as somehow a thing with practical impact in the foreseeable future. It is not.
So what does this mean mathematically? (Score:2)
Re: (Score:3)
It means some problems are one way (secure hashes can exist) if t-time bounded Kolmogorov Complexity is NP.
Re: (Score:1)
This statement makes little sense to me.
"Hashes are reversible."
Nonsense. A hash takes a load of arbitrary-length data, and converts it to a load of fixed-length data. I did this with an information input -- the input is masked, but I didn't want them to have to type the same data in every time. When you type it right, the hash (sum of the ordinal of every character) comes to 1704. If you see 1704, maybe you typed it wrong, probably you typed it right.
But what is this hash? 1704? What if I have a _lot_ of d
Re: (Score:2)
That's true that for any good hash function, multiple inputs will produce the same hash.
In most instances where a hash is used, security is broken if the attacker finds /creates an input that results in the same hash. That's what they mean by reversing the hash.
You mentioned the password example - the server checks if the password I entered has the same hash as needed for your account; it doesn't matter if the password I entered is the same as what you enter or not. I get into your account if the hashes o
Re: (Score:1)
I explicitly did not use a password example (though I see how it could come across as such). As such, in my example, perhaps I have a checksum (a form of hash, perhaps "not cryptographically secure" -- definitely not in this case) instead of a hash. To me they're both the same: data in -> different, reproduceable, "unique" data out. (Perhaps "unique" is what makes it cryptographically secure.)
Note that when I say the number of rounds doesn't matter, what I mean is you're going from data of length m to ha
Re: (Score:2)
" not correct.) If you don't know a number of rounds"
Ah, the old "you don't know how I encrypted it" idea. Also known as "security by obscurity". That's actually been tried a few thousand times, and we've learned something about that - it doesn't work.
One trivial reason why is because in many cases the attacker can provide the input - they can send a web request, they can sign up for an account, which will put their inlut into your "encrypted" database, whatever. So thry know the input for their record is
Re: (Score:2)
Btw, you said
--
For mapping a password hash back to a password, for one round, this might be worth considering. For mapping a password hash back to a password with a variable number of rounds, this is not worth considering.
--
And then said:
--
I explicitly did not use a password example
--
Re: (Score:2)
Does this mean that factorization is not a NP problem but a P one?
A theoretician may get excited about this. In actual reality, whether the backwards direction is EXP or high-order P does not matter one bit.
YES!!! (Score:1)
FUCK YOU BETTERIDGE!!!
Re: (Score:1)
Problem Class (Score:1)
"The central question we're addressing is: Does it exist? Is there some natural problem that characterizes the existence of one-way functions?" he said. "If it does, that's the mother of all problems, and if you have a way to solve that problem, you can break all purported one-way functions. And if you don't know how to solve that problem, you can actually get secure cryptography...."
I don't really follow the reasoning. How does characterizing the existence of one-way functions give you the solution to all one-way function? ("you can break all purported one-way functions")
By analogy I bring up the P=NP complexity question - IF P=NP, merely knowing the proof may not necessarily give you a technique to easily develop an efficient solution to any arbitrary NP class problem.
Proof by contradiction (Score:2)
The reasoning is essentially this:
If you could break every hash, you could also solve t-time bounded Kolmogorov Complexity.
Therefore:
If t-time bounded Kolmogorov Complexity isn't solvable, then secure hash algorithms exist.
Re: (Score:2)
I just don't get how this is revolutionary or evolutionary. Don't we know this?
Re: (Score:2)
I just don't get how this is revolutionary or evolutionary. Don't we know this?
It is not. It is just somebody without a clue that wanted a sensationalist headline.
Re: (Score:3)
Integer factorization (undoing multiplication) is BELIEVED to be hard, but not known to be.
Elliptic curve is believed to be, but not known to be.
MD4, MD5, and SHA1 are all based on an algorithm called Merkle-Damgard, in college I figured out how to break any Merkle-Damgard hash. (Others had figured out the same thing).
As far as I know, this is the first such proof that one-way functions do exist at all. That's important for two reasons:
Until now, the search for provably secure one-way functions was tempere
Re: (Score:2)
>Knowing provable hash functions are related to Kolmogorov Complexity, that gives a good indication of which way to go to find them.
If it leads to better ways of computing KC, that will also be a win. Alas the paper (https://eprint.iacr.org/2020/423.pdf) will be a tough read for most Slashdotters.
Re: (Score:3)
IF P=NP, merely knowing the proof may not necessarily give you a technique to easily develop an efficient solution to any arbitrary NP class problem.
Actually, yes, more or less it would do exactly that. Every NP class problem is mappable to any other in polynomial time. That's part of establishing they are members of the NP class so you have that already.
So if you solve one NP problem in polynomial time, you can use the same polynomial time solution + polynomial time mapping to arrive at a polynomial time solution to the others. It may not be 'efficient' but it'll be polynomial time, which for an arbitrary NP class problem is pretty efficient.
In this pa
+1 (Score:4, Interesting)
Re: (Score:3, Interesting)
WTF is this? There are about 50 Mersenne primes known, so even ignoring that most of them are impractically large, picking any 3 as the secret key only allows for a keyspace of about 17 bits. And why is a crypto paper "published" in the International Journal of Chemical Sciences, anyway?
Re: (Score:1)
talking about a program generator (Score:1)
No (Score:2)
There was even a movie about how any U.S. encryption scheme could be defeated. It wouldn't be that difficult to do the same for any encryption.
Re: (Score:2)
Sure. Another movie.
The headline is complete nonsense (Score:2)
This is not related to "Internet Security" in any way. This is about theoretical cryptography, not practical cryptography. And theoretical cryptography happens to have a convenient, but fundamentally broken definition of "one way" function. In practice, you need far, far less and practical one-way functions most certainly exist.
Re: (Score:2)
>This is not related to "Internet Security" in any way.
Establishing computational bounds on breaking one way functions? Yes it is related to internet security.
Re: (Score:2)
>This is not related to "Internet Security" in any way.
Establishing computational bounds on breaking one way functions? Yes it is related to internet security.
Nope. It is not. It has no practical impact.
Re: (Score:1)
WARNING: Grave, horrible fallacy in TFS. (Score:2)
"And if you don't know how to solve that problem, you can actually get secure cryptography...."
No, then you *don't know* if there is secure cryptography!
Same reason a lion can still bite your ass if you stick your head in the sand so you don't see any lions.
Actually secure crypography would require *proving* that the problem *cannot be solved*.
And even then, it would only be inside the mathematical world. Inside the validity of the axioms (and other assumptions?).
Not in reality. Where there isn't even such
I question their differences themselves! (Score:2)
I am fairly certain, that in the majority of groupings, the majority of species have solely been made up, so somebody could get their name in the books.
Like calling humans with one eyebrow that splits like a "Y" (homo eyebrowsplitii monoaeaeiae..ae) a different species from humans with two eyebrows that split like a "Y" (homo eyebrowsplitii vulgaris). Just because you never saw two of them bang.
And don't forget getting mightily offended if somebody suggests they are the same. The sign of any good snob who t
IGNORE THE ABOVE COMMENT. (Score:2)
I misposted. Somehow ended up on the wrong story.
Well (Score:2)
It may or may not. I'd say we're dealing with a 50-50 chance than randomness theory holds the key here. Then again the chance that the odds are something else is also possible to some unknown extent. Basically I have no idea. Why are you even asking me?
Not Related?! (Score:2)
>two quite separate areas of mathematics and computer science — cryptography and algorithmic information theory,
These two topics are inextricably linked. Why would anyone think they are not? The 'algorithmic information theory' bit is referring to Kolmogorov Complexity which is a part of randomness theory which is fundamental to cryptography.
That said, the paper is quite interesting. This is my field (see the book in my sig) It's not going to change the world on its own, but the link between the ha
Oblig. Sneakers (Score:2)
Sounds like the plot of Sneakers. Only safety is in publishing I take it!
https://en.m.wikipedia.org/wik... [wikipedia.org]
Internet solution (Score:2)