Locking the bad guys out with asymmetric encryption
- Thread starter JournalBot
- Start date
For anyone interested in this, I suggest the book The Science of Secrecy by Simon Singh. He also did a TV show by the same name, although I've never watched it.
Upvote
7
(7
/
0)
And before anyone says; yes, I know that RSA isn't the only key exchange algorithm in common use. I'm not ignoring Diffie Hellman through ignorance; I'm ignoring it through a desire to keep things relatively straightforward. Likewise DSA, ECC, and so on. There are oblique references if you know what to look for (e.g. discrete logarithm).
Upvote
26
(26
/
0)
If the structure and length of a message encrypted using the public key is captured and is short enough couldn't the message eventually be devised and then the rest of the session would also be readable. Of course there would be a delay.
Upvote
-2
(0
/
-2)
Great article. A few technicalities:
1. Amusingly, the "hard" mathematical problems that crypto is based on are all only speculated to be hard. RSA depends on the RSA assumption, which basically states that RSA is secure; Diffie Hellman key exchange depends on the Diffie Hellman assumption, which basically states that it's secure. To date no crypto algorithm has been proven secure (CPA-secure; using other nonstandard definitions of security, for exampl, the random pad is secure). For secure crypto to exist (using the current definitions of security), at the very least, P must not equal NP; additionally, one-way functions must exist, which like the assumptions above that essentially state that their respective algorithms are secure, essentially directly states that crypto exists.
2. Signing is not necessarily done by hashing first. Hashing and then signing the hash is called full-domain hashing and has not been proven secure even if the signing algorithm is secure (at least in the "standard model", meaning without unrealistic assumptions like the existence of random oracles).
3. Signing is not always done by "decrypting" the data to be signed. For one thing, an encryption algorithm may have different domain and range, and thus decrypting a plaintext may not make sense. For another thing, secure encryption doesn't imply secure signing by decrypting. Often the secret key of the encryption allows one to derive the public key. In that case, reversing the roles of public and secret keys would reveal both keys to the public. Additionally, many encryption algorithms (especially fully homomorphic ones) allow anyone to "rerandomize" an encryption, producing a fresh and random-looking encryption of the same message. If one signs by decrypting, rerandomizing doesn't let you see the plaintext so it doesn't violate the security of the encryption, but if you're signing by decrypting, it allows anyone to create a second "rerandomized" message with the same signature. (Although if rerandomizing depends on the public key, I suppose hiding that key would defeat this particular attack. Nonetheless, the point is that the security requirements of encryption and signing are different.)
1. Amusingly, the "hard" mathematical problems that crypto is based on are all only speculated to be hard. RSA depends on the RSA assumption, which basically states that RSA is secure; Diffie Hellman key exchange depends on the Diffie Hellman assumption, which basically states that it's secure. To date no crypto algorithm has been proven secure (CPA-secure; using other nonstandard definitions of security, for exampl, the random pad is secure). For secure crypto to exist (using the current definitions of security), at the very least, P must not equal NP; additionally, one-way functions must exist, which like the assumptions above that essentially state that their respective algorithms are secure, essentially directly states that crypto exists.
2. Signing is not necessarily done by hashing first. Hashing and then signing the hash is called full-domain hashing and has not been proven secure even if the signing algorithm is secure (at least in the "standard model", meaning without unrealistic assumptions like the existence of random oracles).
3. Signing is not always done by "decrypting" the data to be signed. For one thing, an encryption algorithm may have different domain and range, and thus decrypting a plaintext may not make sense. For another thing, secure encryption doesn't imply secure signing by decrypting. Often the secret key of the encryption allows one to derive the public key. In that case, reversing the roles of public and secret keys would reveal both keys to the public. Additionally, many encryption algorithms (especially fully homomorphic ones) allow anyone to "rerandomize" an encryption, producing a fresh and random-looking encryption of the same message. If one signs by decrypting, rerandomizing doesn't let you see the plaintext so it doesn't violate the security of the encryption, but if you're signing by decrypting, it allows anyone to create a second "rerandomized" message with the same signature. (Although if rerandomizing depends on the public key, I suppose hiding that key would defeat this particular attack. Nonetheless, the point is that the security requirements of encryption and signing are different.)
Upvote
13
(15
/
-2)
Why do I feel like this entire article was just a buildup for that last pun?
This is a actually a very well-written article. Great job explaining how these algorithms work in layman's terms. Now I can actually look at the security details in the lock icon in Chrome and understand what it's talking about.
Upvote
24
(24
/
0)
Great article, Peter. Congratulations.
Will you followup with a write up on all that can go wrong with PKI? CAs being compromised, CRIME and BEAST attacks, etc. All of these are practical attacks. The underlying math is supposedly secure, as Solomonoff's Secret points out.
--B
Will you followup with a write up on all that can go wrong with PKI? CAs being compromised, CRIME and BEAST attacks, etc. All of these are practical attacks. The underlying math is supposedly secure, as Solomonoff's Secret points out.
--B
Upvote
6
(6
/
0)
You're thinking in terms of, say, using the known format of a protocol header to attempt to figure out the key and so decrypt the rest of the network packet?toyotabedzrock":263qiqc7 said:
Upvote
0
(0
/
0)
I'm a developer and I think you guys explained this wonderfully. In fact, I bookmarked it for future reference.
Upvote
1
(1
/
0)
Public key encryption must be randomized, meaning mulitple encryptions using the same public key produce completely unrelated-looking ciphertexts. So encrypting every possible short message would likely not produce an encryption that matches the one you already saw. Not sure if that's the attack you had in mind.toyotabedzrock":21gabrew said:
Upvote
6
(6
/
0)
My point was that the underlying assumptions aren't known to be secure. They're only thought to be secure. (But the more standard ones have been extensively studied and nobody has found a weakness...as far as we know (and without using a quantum computer).)bsiu":1o7rm4b1 said:
Upvote
8
(8
/
0)
Interesting article, thanks. Could anyone elaborate on large 'distinct' prime numbers and how that works in this context? Maybe provide examples? In a bit of searching I found a definition of distinct primes but without much of a background in this aspect of crypto I'm a bit in the dark. And by 'bit', I mean really.
Thanks!
Upvote
2
(2
/
0)
Yes, correct, I've amended the post. You would want the private key corresponding to the certificate, then you could phish away.Bob.Brown":eak34av4 said:
Upvote
1
(1
/
0)
Distinct here just means that they are different prime numbers. That is, you can't just choose one number twice.cdclndc":n8djts7k said:
Perhaps oddly (it always seems odd to me, at any rate) picking prime numbers is relatively easy; there are "fast" algorithms (here "fast" means "polynomial time") for proving that a number is composite (not a prime). However, those algorithms don't tell you what the number's factors are; only that they exist. It seems strange that you can do one without the other.
Upvote
5
(5
/
0)
Light crypto experience here. I thought this was a great article with a human touch. The humourous points were well appreciated.
That said, I look forward to the ECC article.
That said, I look forward to the ECC article.
Upvote
10
(10
/
0)
If I encrypt "BUY" or "SELL" using Alice's public key and if Evil Eve knows I'll send one of those two messages and Eve can {ahem} eavesdrop on my communications, all she's got to do is encrypt both messages with Alice's public key and see which bits go by. That's one of the big advantages of the use of a random session key and hybrid encryption.Solomonoff's Secret":3j2mc16d said:
Upvote
-4
(0
/
-4)
No, that doesn't work. Eve would see, say, 394783210125435349. Eve would encrypt "BUY" and "SELL" and would get 6450972965346592346 and 93426527362593535. Eve would still know nothing about which message Alice sent.Bob.Brown":2gpailr7 said:
Generally, in order for public key encryption to be secure (against chosen-plaintext attacks, in other words, CPA-secure), it needs to pass the following game. Choose a security parameter k, a positive integer that basically determines the key length. Alice generates a key pair for the chosen k. Let Eve be some adversary and choose two messages m1 and m2. Alice chooses a random message m among m1 and m2 to encrypt with the key, getting encryption c. Eve gets the public key, m1, m2, and c but doesn't know which message was encrypted to get c. Eve can repeatedly choose messages to encrypt and see the encryptions. Eventually, she has to decide which of m1 and m2 was encrypted to get c. If she can guess with probably non-negligibly better than 1/2, specifically, 1/2 + 1/p(k) for some polynomial p, she wins. If any Eve wins with any messages m1 and m2, the algorithm is insecure.
Upvote
13
(13
/
0)
Upvote
1
(1
/
0)
Solomonoff's Secret":3bgc1dz8 said:
To elaborate further nobody actually uses the m^e mod N thing directly to encrypt anything since there is a list of attacks as long as your arm against it. The RSA cryptosystem uses a padded structure of the same length as N of the form MSB->LSB: 00 01 | TYPE | PAD | MESSAGE
So for encryption:
The 00 byte forces the padded message to strictly less than N (otherwise it would decrypt to m mod N and not m).
The 01 byte ensures that m^e >> N (otherwise decryption would be trivial by taking the eth root of the cipher text).
The type field ensures that signatures and public key encryptions are distinguishable so a client can detect if its being asked to "sign" a ciphertext (i.e. decrypt it - not that you should use the same key for both type of operation).
PAD is a zero terminated padding field (of not less than 8 random bytes) that is filled with random non-zero bytes so a minimum of 2^64 bytes of entropy to randomise the message.
On the decryption side you need to validate everything above is correct, and use things like blinding to avoid timing attacks, SPA, DPA, fault attacks, etc
In short even if you get the math NEVER ROLL YOUR OWN!
Upvote
12
(12
/
0)
bsiu":ukuckafb said:
CRIME and BEAST are attacks on TLS symmetric encryption and not attacks on PKI, attacks on trusted 3rd parties aren't really attacks on PKI either (if you trust someone with your house keys and they just leave them lying around so the keys and your stuff gets stolen you wouldn't blame your locks would you).
There are attacks on RSA but you shouldn't use vanilla RSA anyway, the remaining attacks are generally implementation errors so you start getting software specific (though some errors are quite common).
Upvote
1
(1
/
0)
Aha! That explains it. Although Evil Eve can see the (encrypted) 64 bits of padding, she cannot decrypt them without the corresponding private key. So, with a small number of known plaintext possibilities, Eve must make 2^64 or more encryption computations for each known plaintext possibility.Stubabe":ce7te454 said:
Upvote
1
(1
/
0)
p and q are prime; e and d and phiEricOnTheWebz":3zdmkivz said:
have no factors in common ("relatively prime", but I didn't want to use yet another jargon time), as I wrote.
Upvote
0
(0
/
0)
DrPizza":c8kntkai said:
They all basically on the fact that that certain relationships only hold if the number is prime, otherwise terms start to cancel internally.
e.g.
Fermat’s Little Theorem states for any prime number p, and for any number a such that 0 < a < p
a^(p − 1) = 1 (mod p).
For non primes p if a has any common factors then the equation will fail. Obviously trying every possible a isn't going to be any faster than trial factoring but rearrangements of formulas such as these allows faster systems to be produced. Also remember that many primeality tests are probabilistic (i.e. you would keep trying different values of a until the odds p isn't prime are vanishingly small) since absolute primeality testing of RSA sized primes would still take many hours on a modern computer so would make keygen too slow. e.g. for RSA keygen you normally aim for odds less that 1 in 2^100 that p is composite.
Upvote
3
(3
/
0)
Is AKS not fast enough to use in practice? It's deterministic and polynomial time, but even polynomial time doesn't guarantee that constant factors don't kill you.Stubabe":2hgfgtfy said:
Upvote
0
(0
/
0)
Of course you not only have to worry about the constant factor, but also the power. I don't know if there's a tight bound on the running time of AKS, but the known bounds have relatively high powers, so it'd probably be quite slow for large primes.DrPizza":2oewa6k7 said:
Upvote
2
(2
/
0)
DrPizza":20tmuyn9 said:
Miller–Rabin is a common one since you only need 2 witnesses to test a 1024bit prime to a very high degree of certainty so is extremely fast (<1sec). Remember, in many cases keygen is an almost interactive task but I couldn't comment if anyone uses the "fast" version AKS anywhere but its still a fair bit slower.
Upvote
2
(2
/
0)
Great article, but I have to complain about the side fill adds. I hate ghost links, i should know that i am clicking on a ad if its on ars. +1 for add block (which i used to have disabled on this site).
Upvote
2
(2
/
0)
DrPizza":18vq5rzu said:
And I thank you for that. Encryption is a concept I've understood for a long time, but the implementation aspect still escapes me.
Out of random curiosity, would it add any security to handshake then pass a symmetric key which both client and server could then use to encrypt data with a much stronger encryption?
Upvote
0
(0
/
0)
Peter, this is your article that I've enjoyed the most in years. Thank you so much for writing it.
I have a question related to Stuxnet - can you please explain the collision aspect of the attack which was used in terms of the rest of the article you wrote?
I have a question related to Stuxnet - can you please explain the collision aspect of the attack which was used in terms of the rest of the article you wrote?
Upvote
1
(1
/
0)
Very nice article. Since quantum computers were mentioned as way to efficiently crack RSA and other similar asymmetric cryptography schemes, it is worth mentioning an alternative improvement to cryptography: quantum key distribution. Although it is still seem as a curiosity by most non-physicists, some recent results have demonstrated Mbit/s data rates of remote secure key generation. It should take off in the next few years, although technology predictions are always very hard to make.
Furthermore the interest in it by the international research community (physics/engineering etc...) is at an all-time high, and increasing. One way to maybe demonstrate this is that many people in the IT community have heard of it or know how it works. For example the recent cover piece in Ars about QKD was also pretty good.
Furthermore the interest in it by the international research community (physics/engineering etc...) is at an all-time high, and increasing. One way to maybe demonstrate this is that many people in the IT community have heard of it or know how it works. For example the recent cover piece in Ars about QKD was also pretty good.
Upvote
1
(1
/
0)
atom944":2xqo0q6w said:
Seconded, that book is a very gradual and fun introduction to encryption. It starts with the simple Caesar cypher and without realising it you'll learn how to operate an enigma machine!
Upvote
1
(1
/
0)
here is a fairly good treatment on why factoring is hard and why you can tell if a number is prime quite easily, but cannot tell it's factors as easily: http://www.cs.berkeley.edu/~vazirani/algorithms.html
Upvote
1
(1
/
0)
Bob.Brown":1fih1fws said:
Typically a randomly generated AES key is used not only for the reasons you listed, but also because AES is faster. PKI is only used to establish the session and exchange the AES keys securely, but then just use AES for speed.
Upvote
1
(1
/
0)
The funny thing is if some random person solved the factorization problem, they could probably sell the solution to the CIA or NSA or someone for like, $100 million, and then sit on it until someone else solved it and be like "Yeah, I solved that a while ago. I hope you didn't think anything online was really secure."
Upvote
3
(3
/
0)
What a great article. I really like how you walked step-by-step through the math involved in producing the pub/priv key pair.
I've used plenty of asymmetric encryption, but never really thought about or understood why the two keys were related to each other and work the way they do.
I've used plenty of asymmetric encryption, but never really thought about or understood why the two keys were related to each other and work the way they do.
Upvote
0
(0
/
0)
Cryptography is hard, and asymmetric cryptography is especially brittle. For example, the article says that private keys can be used to encrypt data (but then goes on to use that "encryption" for authentication / signature generation). If the same private key is used for both real encryption (confidentiality) and signatures (authentication), then the confidentiality is completely broken. (Summary: The public key can be easily recovered from the signatures, without knowing the private key.)
Then there's the problem of checking padding. If e (the public exponent) is 3 (which is common), any message that is a perfect cube will pass signature validation. This has led to real attacks. The "solution" is to be very strict in what padding the sender is allowed to add to a message.
And there are attacks on DSA, due to incorrect use of the K parameter.
So don't try to roll your own security. You will almost certainly get it wrong. Even the TCP implementers got it wrong - incorrect use of authenticated encryption (MAC-then-Encrypt, rather than the secure Encrypt-then-MAC) led to the latest TLS/SSL attack.
Then there's the problem of checking padding. If e (the public exponent) is 3 (which is common), any message that is a perfect cube will pass signature validation. This has led to real attacks. The "solution" is to be very strict in what padding the sender is allowed to add to a message.
And there are attacks on DSA, due to incorrect use of the K parameter.
So don't try to roll your own security. You will almost certainly get it wrong. Even the TCP implementers got it wrong - incorrect use of authenticated encryption (MAC-then-Encrypt, rather than the secure Encrypt-then-MAC) led to the latest TLS/SSL attack.
Upvote
-1
(1
/
-2)
- Status