At 5/4/16 08:40 AM, Gimmick wrote:
@egg82 have you heard of wappalyzer? Claims to find out what websites use which technology. I can't verify it's usefulness since I haven't used it, but then again I'm not really in a position where I'd need to use it.
I haven't, no. Installed it, checked it out, and I'm fairly impressed. I'll keep using it for now and see if it helps with my pentests. Basically I'm hoping it will reduce my absolutely massive potential attack surface into a smaller and more manageable real attack surface. Automatic information gathering for the win.
Also, since when was this a thing?
So I couldn't help but notice IBM was sharing a public-facing quantum computer with the internet. Looks interesting.
Since that was a thing that happened I decided I'd share my knowledge on how quantum computers actually work in terms of RSA encryption breaking. (You know, that HTTPS thing everyone's always on about)
RSA is an offshoot of the DH secure key-exchange algorithm. With Diffie-Hellman, each person in the line of communication ends up with a shared private and public key. The problem with DH is that, on a server, you would need a unique private key for every person that connects to it. DoS attacks ahoy. RSA solves this by basically only generating a single keypair, thus only needing to retain one key and preventing it from running out of memory after a few connections. The browser implements the same, and both the browser and the server only know eachother's public key for encrypting instead of actually handshaking a new key for eachother on every new connection as in the DH specification.
I hope that was clear enough to get a gist of what the differences are between DH and RSA, but since their encryption works in a similar fashion (prime factorization) and DH is easier to understand I decided I'd give my examples via that. Just know the same techniques applied to this example can be applied to a real DH exchange on a larger scale, and then RSA itself for the total compromise of any SSL connection. (SSL being the underlying technology behind HTTPS, so it's not actually limited to just HTTPS. Think SSH)
First, though, a quick clarification on how quantum computers actually work: They're not inherently faster than any normal computer because of some magic quantum mechanic bullshit. They work differently, not faster. Think of it like taking the question you've asked (what are the factors of x?) and twisting it into another question in a way only quantum mechanics can do to achieve an obtainable answer in a reasonable time. (way before the heat death of the universe, which is the amount of time classic computing would take) - also, quantum computers can't solve prime factors on their own because they don't deal in normal mathematics. You still need help from a classical computer to do classical computations.
Right, so there's the general idea. Now to be more specific, we'll talk about how the DH key exchange works. Remember RSA is very similar.
Alice wants to encrypt communications with Bob without either of them previously sharing any contact (as in a random client connecting to a random server)
Eve starts intercepting everything between them.
Alice picks two prime numbers p and g (let's say 23 and 5 respectively, following Wikipedia's article) and sends them to Bob. Eve of course picks these up.
Alice, Bob, and Eve now have the two numbers 23 and 5. It's important to note that in this example 5 is actually a primitive root of 23. It doesn't have to be a primitive root, but the discreet logarithm is lost if it isn't since you would end up with a bias in the resulting numbers, increasing the likelihood of guessing a (not the, but a) correct number.
Alice chooses a secret number a (6 in this case), and Bob chooses a secret number b (15, again following Wikipedia). These numbers are not shared with eachother, so Eve doesn't know what the secret numbers are.
Alice sends Bob a new, computed number A, which is actually just g^a%p (so 5^6%23 = 8, so A = 8)
Both Bob and Eve now also have the number 8.
Bob does the same with his b to get B (g^b%p, 5^15%23 = 9, so B = 19) and sends that to Alice.
Alice and Eve now have the number 19.
It's important to note that while all relevant information has been shared across the wire (Eve gets nothing else aside from encrypted data that Bob and Alice will soon share) still nobody actually has an encryption key.
Both Alice and Bob now compute s. In the case of Alice, s = B^a%p. In the case of Bob, s = A^b%p. Either computation lands you the number 2, which is the shared secret key used for encryption.
Since Eve neither has Alice's a nor Bob's b, she can't know the answer to the final problem presented and thus can't decrypt the messages now being sent between Bob and Alice (who are using the shared private key s, or 2). She can compute everything else with those numbers, just not that.
I found this visualization on Wikipedia extremely helpful in putting basic understanding behind the math when I did my simple implementation of DH in Flash.
This is the DH key exchange, simplified. The real exchange actually involves hundreds of numbers, and thankfully nobody needs to compute g and p since there's a bunch of them included in the specification. Knowing g and p doesn't weaken the security in the slightest, as you might have guessed from looking at the exchange.
The point of DH is the discrete logarithm. In order to break A or B, it requires essentially guessing a or b. You'd need to run through every number between 0 and g-1 to guess the (hopefully single, if g is a generator of p) right result; and since, again, most DH numbers are hundreds of digits long, you'll be there a while. (2^t, where t is the number of bits; eg. 2048-bit DH key would mean 2^2048 computational power required to solve for a or b. ie. brute force would take O*(2^t) time)
This is where quantum computers come in. Shor's Algorithm says: "for b=a^s%N where N, a, and b are known, find s" - which is exactly what we're trying to do here.
There's a lot of theoretical math (and quantum physics) involved, but the gist is this:
x mod y will result in a period. This basically means "how many different numbers will come out of this before it starts repeating?" (because mod results in repeating patterns) - using a primitive root will always yield a period N, but we don't know for sure whether or not that is actually the case. Either way, period finding is still only part of it.
Any way you look at it, finding the period is a start. Quantum Fourier transforms (Sec. 4, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer) help us by selecting a random number smaller than N for a and placing the possible values of the algorithm into superpositions, essentially resulting in wrong answers being closer to zero with destructive interference and right answers being closer to one with constructive interference. This means that we have, with high probability, found N's period p. If not, we simply try again with a new random value for a.
For prime factorization, all that's left is to find the greatest common denominator of N and a^(p/2)-1 and we have a factor! This immediately breaks RSA. DH still needs a little more work.
Keep in mind DH is based off the discrete logarithm while RSA is actually a prime factorization problem (which Shor's solves directly)
The best part about all of this? Mathematicians in the late 1700's conceived of both RSA and the quantum algorithms to break it. They were thinking longer-term than the people who actually made SSL.
